1<!--===- docs/OpenMP-semantics.md 2 3 Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 See https://llvm.org/LICENSE.txt for license information. 5 SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 7--> 8 9# OpenMP Semantic Analysis 10 11```eval_rst 12.. contents:: 13 :local: 14``` 15 16## OpenMP for F18 17 181. Define and document the parse tree representation for 19 * Directives (listed below) 20 * Clauses (listed below) 21 * Documentation 221. All the directives and clauses need source provenance for messages 231. Define and document how an OpenMP directive in the parse tree 24will be represented as the parent of the statement(s) 25to which the directive applies. 26The parser itself will not be able to construct this representation; 27there will be subsequent passes that do so 28just like for example _do-stmt_ and _do-construct_. 291. Define and document the symbol table extensions 301. Define and document the module file extensions 31 32 33### Directives 34 35OpenMP divides directives into three categories as follows. 36The directives that are in the same categories share some characteristics. 37 38 39 40#### Declarative directives 41 42An OpenMP directive may only be placed in a declarative context. 43A declarative directive results in one or more declarations only; 44it is not associated with the immediate execution of any user code. 45 46List of existing ones: 47* declare simd 48* declare target 49* threadprivate 50* declare reduction 51 52There is a parser node for each of these directives and 53the parser node saves information associated with the directive, 54for example, 55the name of the procedure-name in the `declare simd` directive. 56 57Each parse tree node keeps source provenance, 58one for the directive name itself and 59one for the entire directive starting from the directive name. 60 61A top-level class, `OpenMPDeclarativeConstruct`, 62holds all four of the node types as discriminated unions 63along with the source provenance for the entire directive 64starting from `!$OMP`. 65 66In `parser-tree.h`, 67`OpenMPDeclarativeConstruct` is part 68of the `SpecificationConstruct` and `SpecificationPart` 69in F18 because 70a declarative directive can only be placed in the specification part 71of a Fortran program. 72 73All the `Names` or `Designators` associated 74with the declarative directive will be resolved in later phases. 75 76#### Executable directives 77 78An OpenMP directive that is **not** declarative. 79That is, it may only be placed in an executable context. 80It contains stand-alone directives and constructs 81that are associated with code blocks. 82The stand-alone directive is described in the next section. 83 84The constructs associated with code blocks listed below 85share a similar structure: 86_Begin Directive_, _Clause List_, _Code Block_, _End Directive_. 87The _End Directive_ is optional for constructs 88like Loop-associated constructs. 89 90* Block-associated constructs (`OpenMPBlockConstruct`) 91* Loop-associated constructs (`OpenMPLoopConstruct`) 92* Atomic construct (`OpenMPAtomicConstruct`) 93* Sections Construct (`OpenMPSectionsConstruct`, 94 contains Sections/Parallel Sections constructs) 95* Critical Construct (`OpenMPCriticalConstruct`) 96 97A top-level class, `OpenMPConstruct`, 98includes stand-alone directive and constructs 99listed above as discriminated unions. 100 101In the `parse-tree.h`, `OpenMPConstruct` is an element 102of the `ExecutableConstruct`. 103 104All the `Names` or `Designators` associated 105with the executable directive will be resolved in Semantic Analysis. 106 107When the backtracking parser can not identify the associated code blocks, 108the parse tree will be rewritten later in the Semantics Analysis. 109 110#### Stand-alone Directives 111 112An OpenMP executable directive that has no associated user code 113except for that which appears in clauses in the directive. 114 115List of existing ones: 116* taskyield 117* barrier 118* taskwait 119* target enter data 120* target exit data 121* target update 122* ordered 123* flush 124* cancel 125* cancellation point 126 127A higher-level class is created for each category 128which contains directives listed above that share a similar structure: 129* OpenMPSimpleStandaloneConstruct 130(taskyield, barrier, taskwait, 131target enter/exit data, target update, ordered) 132* OpenMPFlushConstruct 133* OpenMPCancelConstruct 134* OpenMPCancellationPointConstruct 135 136A top-level class, `OpenMPStandaloneConstruct`, 137holds all four of the node types as discriminated unions 138along with the source provenance for the entire directive. 139Also, each parser node for the stand-alone directive saves 140the source provenance for the directive name itself. 141 142### Clauses 143 144Each clause represented as a distinct class in `parse-tree.h`. 145A top-level class, `OmpClause`, 146includes all the clauses as discriminated unions. 147The parser node for `OmpClause` saves the source provenance 148for the entire clause. 149 150All the `Names` or `Designators` associated 151with the clauses will be resolved in Semantic Analysis. 152 153Note that the backtracking parser will not validate 154that the list of clauses associated 155with a directive is valid other than to make sure they are well-formed. 156In particular, 157the parser does not check that 158the association between directive and clauses is correct 159nor check that the values in the directives or clauses are correct. 160These checks are deferred to later phases of semantics to simplify the parser. 161 162## Symbol Table Extensions for OpenMP 163 164Name resolution can be impacted by the OpenMP code. 165In addition to the regular steps to do the name resolution, 166new scopes and symbols may need to be created 167when encountering certain OpenMP constructs. 168This section describes the extensions 169for OpenMP during Symbol Table construction. 170 171OpenMP uses the fork-join model of parallel execution and 172all OpenMP threads have access to 173a _shared_ memory place to store and retrieve variables 174but each thread can also have access to 175its _threadprivate_ memory that must not be accessed by other threads. 176 177For the directives and clauses that can control the data environments, 178compiler needs to determine two kinds of _access_ 179to variables used in the directive’s associated structured block: 180**shared** and **private**. 181Each variable referenced in the structured block 182has an original variable immediately outside of the OpenMP constructs. 183Reference to a shared variable in the structured block 184becomes a reference to the original variable. 185However, each private variable referenced in the structured block, 186a new version of the original variable (of the same type and size) 187will be created in the threadprivate memory. 188 189There are exceptions that directives/clauses 190need to create a new `Symbol` without creating a new `Scope`, 191but in general, 192when encountering each of the data environment controlling directives 193(discussed in the following sections), 194a new `Scope` will be created. 195For each private variable referenced in the structured block, 196a new `Symbol` is created out of the original variable 197and the new `Symbol` is associated 198with original variable’s `Symbol` via `HostAssocDetails`. 199A new set of OpenMP specific flags are added 200into `Flag` class in `symbol.h` to indicate the types of 201associations, 202data-sharing attributes, 203and data-mapping attributes 204in the OpenMP data environments. 205 206### New Symbol without new Scope 207 208OpenMP directives that require new `Symbol` to be created 209but not new `Scope` are listed in the following table 210in terms of the Symbol Table extensions for OpenMP: 211 212<table> 213 <tr> 214 <td rowspan="2" colspan="2" >Directives/Clauses 215 </td> 216 <td rowspan="2" >Create New 217<p> 218Symbol 219<p> 220w/ 221 </td> 222 <td colspan="2" >Add Flag 223 </td> 224 </tr> 225 <tr> 226 <td>on Symbol of 227 </td> 228 <td>Flag 229 </td> 230 </tr> 231 <tr> 232 <td rowspan="4" >Declarative Directives 233 </td> 234 <td>declare simd [(proc-name)] 235 </td> 236 <td>- 237 </td> 238 <td>The name of the enclosing function, subroutine, or interface body 239 to which it applies, or proc-name 240 </td> 241 <td>OmpDeclareSimd 242 </td> 243 </tr> 244 <tr> 245 <td>declare target 246 </td> 247 <td>- 248 </td> 249 <td>The name of the enclosing function, subroutine, or interface body 250 to which it applies 251 </td> 252 <td>OmpDeclareTarget 253 </td> 254 </tr> 255 <tr> 256 <td>threadprivate(list) 257 </td> 258 <td>- 259 </td> 260 <td>named variables and named common blocks 261 </td> 262 <td>OmpThreadPrivate 263 </td> 264 </tr> 265 <tr> 266 <td>declare reduction 267 </td> 268 <td>* 269 </td> 270 <td>reduction-identifier 271 </td> 272 <td>OmpDeclareReduction 273 </td> 274 </tr> 275 <tr> 276 <td>Stand-alone directives 277 </td> 278 <td>flush 279 </td> 280 <td>- 281 </td> 282 <td>variable, array section or common block name 283 </td> 284 <td>OmpFlushed 285 </td> 286 </tr> 287 <tr> 288 <td colspan="2" >critical [(name)] 289 </td> 290 <td>- 291 </td> 292 <td>name (user-defined identifier) 293 </td> 294 <td>OmpCriticalLock 295 </td> 296 </tr> 297 <tr> 298 <td colspan="2" >if ([ directive-name-modifier :] scalar-logical-expr) 299 </td> 300 <td>- 301 </td> 302 <td>directive-name-modifier 303 </td> 304 <td>OmpIfSpecified 305 </td> 306 </tr> 307</table> 308 309 310 - No Action 311 312 * Discussed in “Module File Extensions for OpenMP” section 313 314 315### New Symbol with new Scope 316 317For the following OpenMP regions: 318 319* `target` regions 320* `teams` regions 321* `parallel` regions 322* `simd` regions 323* task generating regions (created by `task` or `taskloop` constructs) 324* worksharing regions 325(created by `do`, `sections`, `single`, or `workshare` constructs) 326 327A new `Scope` will be created 328when encountering the above OpenMP constructs 329to ensure the correct data environment during the Code Generation. 330To determine whether a variable referenced in these regions 331needs the creation of a new `Symbol`, 332all the data-sharing attribute rules 333described in OpenMP Spec [2.15.1] apply during the Name Resolution. 334The available data-sharing attributes are: 335**_shared_**, 336**_private_**, 337**_linear_**, 338**_firstprivate_**, 339and **_lastprivate_**. 340The attribute is represented as `Flag` in the `Symbol` object. 341 342More details are listed in the following table: 343 344<table> 345 <tr> 346 <td rowspan="2" >Attribute 347 </td> 348 <td rowspan="2" >Create New Symbol 349 </td> 350 <td colspan="2" >Add Flag 351 </td> 352 </tr> 353 <tr> 354 <td>on Symbol of 355 </td> 356 <td>Flag 357 </td> 358 </tr> 359 <tr> 360 <td>shared 361 </td> 362 <td>No 363 </td> 364 <td>Original variable 365 </td> 366 <td>OmpShared 367 </td> 368 </tr> 369 <tr> 370 <td>private 371 </td> 372 <td>Yes 373 </td> 374 <td>New Symbol 375 </td> 376 <td>OmpPrivate 377 </td> 378 </tr> 379 <tr> 380 <td>linear 381 </td> 382 <td>Yes 383 </td> 384 <td>New Symbol 385 </td> 386 <td>OmpLinear 387 </td> 388 </tr> 389 <tr> 390 <td>firstprivate 391 </td> 392 <td>Yes 393 </td> 394 <td>New Symbol 395 </td> 396 <td>OmpFirstPrivate 397 </td> 398 </tr> 399 <tr> 400 <td>lastprivate 401 </td> 402 <td>Yes 403 </td> 404 <td>New Symbol 405 </td> 406 <td>OmpLastPrivate 407 </td> 408 </tr> 409</table> 410 411To determine the right data-sharing attribute, 412OpenMP defines that the data-sharing attributes 413of variables that are referenced in a construct can be 414_predetermined_, _explicitly determined_, or _implicitly determined_. 415 416#### Predetermined data-sharing attributes 417 418* Assumed-size arrays are **shared** 419* The loop iteration variable(s) 420in the associated _do-loop(s)_ of a 421_do_, 422_parallel do_, 423_taskloop_, 424or _distributeconstruct_ 425is (are) **private** 426* A loop iteration variable 427for a sequential loop in a _parallel_ or task generating construct 428is **private** in the innermost such construct that encloses the loop 429* Implied-do indices and _forall_ indices are **private** 430* The loop iteration variable in the associated _do-loop_ 431of a _simd_ construct with just one associated _do-loop_ 432is **linear** with a linear-step 433that is the increment of the associated _do-loop_ 434* The loop iteration variables in the associated _do-loop(s)_ of a _simd_ 435construct with multiple associated _do-loop(s)_ are **lastprivate** 436 437#### Explicitly determined data-sharing attributes 438 439Variables with _explicitly determined_ data-sharing attributes are: 440 441* Variables are referenced in a given construct 442* Variables are listed in a data-sharing attribute clause on the construct. 443 444The data-sharing attribute clauses are: 445* _default_ clause 446(discussed in “Implicitly determined data-sharing attributes”) 447* _shared_ clause 448* _private_ clause 449* _linear_ clause 450* _firstprivate_ clause 451* _lastprivate_ clause 452* _reduction_ clause 453(new `Symbol` created with the flag `OmpReduction` set) 454 455Note that variables with _predetermined_ data-sharing attributes 456may not be listed (with exceptions) in data-sharing attribute clauses. 457 458#### Implicitly determined data-sharing attributes 459 460Variables with implicitly determined data-sharing attributes are: 461 462* Variables are referenced in a given construct 463* Variables do not have _predetermined_ data-sharing attributes 464* Variables are not listed in a data-sharing attribute clause 465on the construct. 466 467Rules for variables with _implicitly determined_ data-sharing attributes: 468 469* In a _parallel_ construct, if no _default_ clause is present, 470these variables are **shared** 471* In a task generating construct, 472if no _default_ clause is present, 473a variable for which the data-sharing attribute 474is not determined by the rules above 475and that in the enclosing context is determined 476to be shared by all implicit tasks 477bound to the current team is **shared** 478* In a _target_ construct, 479variables that are not mapped after applying data-mapping attribute rules 480(discussed later) are **firstprivate** 481* In an orphaned task generating construct, 482if no _default_ clause is present, dummy arguments are **firstprivate** 483* In a task generating construct, if no _default_ clause is present, 484a variable for which the data-sharing attribute is not determined 485by the rules above is **firstprivate** 486* For constructs other than task generating constructs or _target_ constructs, 487if no _default_ clause is present, 488these variables reference the variables with the same names 489that exist in the enclosing context 490* In a _parallel_, _teams_, or task generating construct, 491the data-sharing attributes of these variables are determined 492by the _default_ clause, if present: 493 * _default(shared)_ 494 clause causes all variables referenced in the construct 495 that have _implicitly determined_ data-sharing attributes 496 to be **shared** 497 * _default(private)_ 498 clause causes all variables referenced in the construct 499 that have _implicitly determined_ data-sharing attributes 500 to be **private** 501 * _default(firstprivate)_ 502 clause causes all variables referenced in the construct 503 that have _implicitly determined_ data-sharing attributes 504 to be **firstprivate** 505 * _default(none)_ 506 clause requires that each variable 507 that is referenced in the construct, 508 and that does not have a _predetermined_ data-sharing attribute, 509 must have its data-sharing attribute _explicitly determined_ 510 by being listed in a data-sharing attribute clause 511 512 513### Data-mapping Attribute 514 515When encountering the _target data_ and _target_ directives, 516the data-mapping attributes of any variable referenced in a target region 517will be determined and represented as `Flag` in the `Symbol` object 518of the variable. 519No `Symbol` or `Scope` will be created. 520 521The basic steps to determine the data-mapping attribute are: 522 5231. If _map_ clause is present, 524the data-mapping attribute is determined by the _map-type_ 525on the clause and its corresponding `Flag` are listed below: 526 527<table> 528 <tr> 529 <td> 530data-mapping attribute 531 </td> 532 <td>Flag 533 </td> 534 </tr> 535 <tr> 536 <td>to 537 </td> 538 <td>OmpMapTo 539 </td> 540 </tr> 541 <tr> 542 <td>from 543 </td> 544 <td>OmpMapFrom 545 </td> 546 </tr> 547 <tr> 548 <td>tofrom 549(default if map-type is not present) 550 </td> 551 <td>OmpMapTo & OmpMapFrom 552 </td> 553 </tr> 554 <tr> 555 <td>alloc 556 </td> 557 <td>OmpMapAlloc 558 </td> 559 </tr> 560 <tr> 561 <td>release 562 </td> 563 <td>OmpMapRelease 564 </td> 565 </tr> 566 <tr> 567 <td>delete 568 </td> 569 <td>OmpMapDelete 570 </td> 571 </tr> 572</table> 573 5742. Otherwise, the following data-mapping rules apply 575for variables referenced in a _target_ construct 576that are _not_ declared in the construct and 577do not appear in data-sharing attribute or map clauses: 578 * If a variable appears in a _to_ or _link_ clause 579 on a _declare target_ directive then it is treated 580 as if it had appeared in a _map_ clause with a _map-type_ of **tofrom** 5813. Otherwise, the following implicit data-mapping attribute rules apply: 582 * If a _defaultmap(tofrom:scalar)_ clause is _not_ present 583 then a scalar variable is not mapped, 584 but instead has an implicit data-sharing attribute of **firstprivate** 585 * If a _defaultmap(tofrom:scalar)_ clause is present 586 then a scalar variable is treated as if it had appeared 587 in a map clause with a map-type of **tofrom** 588 * If a variable is not a scalar 589 then it is treated as if it had appeared in a map clause 590 with a _map-type_ of **tofrom** 591 592After the completion of the Name Resolution phase, 593all the data-sharing or data-mapping attributes marked for the `Symbols` 594may be used later in the Semantics Analysis and in the Code Generation. 595 596## Module File Extensions for OpenMP 597 598After the successful compilation of modules and submodules 599that may contain the following Declarative Directives, 600the entire directive starting from `!$OMP` needs to be written out 601into `.mod` files in their corresponding Specification Part: 602 603* _declare simd_ or _declare target_ 604 605 In the “New Symbol without new Scope” section, 606 we described that when encountering these two declarative directives, 607 new `Flag` will be applied to the Symbol of the name of 608 the enclosing function, subroutine, or interface body to 609 which it applies, or proc-name. 610 This `Flag` should be part of the API information 611 for the given subroutine or function 612 613* _declare reduction_ 614 615 The _reduction-identifier_ in this directive 616 can be use-associated or host-associated. 617 However, it will not act like other Symbols 618 because user may have a reduction name 619 that is the same as a Fortran entity name in the same scope. 620 Therefore a specific data structure needs to be created 621 to save the _reduction-identifier_ information 622 in the Scope and this directive needs to be written into `.mod` files 623 624## Phases of OpenMP Analysis 625 6261. Create the parse tree for OpenMP 627 1. Add types for directives and clauses 628 1. Add type(s) that will be used for directives 629 2. Add type(s) that will be used for clauses 630 3. Add other types, e.g. wrappers or other containers 631 4. Use std::variant to encapsulate meaningful types 632 2. Implemented in the parser for OpenMP (openmp-grammar.h) 6332. Create canonical nesting 634 1. Restructure parse tree to reflect the association 635 of directives and stmts 636 1. Associate `OpenMPLoopConstruct` 637 with `DoConstruct` and `OpenMPEndLoopDirective` 638 1. Investigate, and perhaps reuse, 639 the algorithm used to restructure do-loops 640 2. Add a pass near the code that restructures do-loops; 641 but do not extend the code that handles do-loop for OpenMP; 642 keep this code separate. 643 3. Report errors that prevent restructuring 644 (e.g. loop directive not followed by loop) 645 We should abort in case of errors 646 because there is no point to perform further checks 647 if it is not a legal OpenMP construct 6483. Validate the structured-block 649 1. Structured-block is a block of executable statements 650 1. Single entry and single exit 651 1. Access to the structured block must not be the result of a branch 652 1. The point of exit cannot be a branch out of the structured block 6534. Check that directive and clause combinations are legal 654 1. Begin and End directive should match 655 1. Simply check that the clauses are allowed by the directives 656 1. Write as a separate pass for simplicity and correctness of the parse tree 6575. Write parse tree tests 658 1. At this point, the parse tree should be perfectly formed 659 1. Write tests that check for correct form and provenance information 660 1. Write tests for errors that can occur during the restructuring 6616. Scope, symbol tables, and name resolution 662 1. Update the existing code to handle names and scopes introduced by OpenMP 663 1. Write tests to make sure names are properly implemented 6647. Check semantics that is specific to each directive 665 1. Validate the directive and its clauses 666 1. Some clause checks require the result of name resolution, 667 i.e. “A list item may appear in a _linear_ or _firstprivate_ clause 668 but not both.” 669 1. TBD: 670 Validate the nested statement for legality in the scope of the directive 671 1. Check the nesting of regions [OpenMP 4.5 spec 2.17] 6728. Module file utilities 673 1. Write necessary OpenMP declarative directives to `.mod` files 674 2. Update the existing code 675 to read available OpenMP directives from the `.mod` files 676