flang/docs/OpenMP-semantics.md

   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
  18 1. Define and document the parse tree representation for
  19     * Directives (listed below)
  20     * Clauses (listed below)
  21     * Documentation
  22 1. All the directives and clauses need source provenance for messages
  23 1. Define and document how an OpenMP directive in the parse tree
  24 will be represented as the parent of the statement(s)
  25 to which the directive applies.
  26 The parser itself will not be able to construct this representation;
  27 there will be subsequent passes that do so
  28 just like for example _do-stmt_ and _do-construct_.
  29 1. Define and document the symbol table extensions
  30 1. Define and document the module file extensions
  31
  32
  33 ### Directives
  34
  35 OpenMP divides directives into three categories as follows.
  36 The directives that are in the same categories share some characteristics.
  37
  38
  39
  40 #### Declarative directives
  41
  42 An OpenMP directive may only be placed in a declarative context.
  43 A declarative directive results in one or more declarations only;
  44 it is not associated with the immediate execution of any user code.
  45
  46 List of existing ones:
  47 * declare simd
  48 * declare target
  49 * threadprivate
  50 * declare reduction
  51
  52 There is a parser node for each of these directives and
  53 the parser node saves information associated with the directive,
  54 for example,
  55 the name of the procedure-name in the `declare simd` directive.
  56
  57 Each parse tree node keeps source provenance,
  58 one for the directive name itself and
  59 one for the entire directive starting from the directive name.
  60
  61 A top-level class, `OpenMPDeclarativeConstruct`,
  62 holds all four of the node types as discriminated unions
  63 along with the source provenance for the entire directive
  64 starting from `!$OMP`.
  65
  66 In `parser-tree.h`,
  67 `OpenMPDeclarativeConstruct` is part
  68 of the `SpecificationConstruct` and `SpecificationPart`
  69 in F18 because
  70 a declarative directive can only be placed in the specification part
  71 of a Fortran program.
  72
  73 All the `Names` or `Designators` associated
  74 with the declarative directive will be resolved in later phases.
  75
  76 #### Executable directives
  77
  78 An OpenMP directive that is **not** declarative.
  79 That is, it may only be placed in an executable context.
  80 It contains stand-alone directives and constructs
  81 that are associated with code blocks.
  82 The stand-alone directive is described in the next section.
  83
  84 The constructs associated with code blocks listed below
  85 share a similar structure:
  86 _Begin Directive_, _Clause List_, _Code Block_, _End Directive_.
  87 The _End Directive_ is optional for constructs
  88 like 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
  97 A top-level class, `OpenMPConstruct`,
  98 includes stand-alone directive and constructs
  99 listed above as discriminated unions.
 100
 101 In the `parse-tree.h`, `OpenMPConstruct` is an element
 102 of the `ExecutableConstruct`.
 103
 104 All the `Names` or `Designators` associated
 105 with the executable directive will be resolved in Semantic Analysis.
 106
 107 When the backtracking parser can not identify the associated code blocks,
 108 the parse tree will be rewritten later in the Semantics Analysis.
 109
 110 #### Stand-alone Directives
 111
 112 An OpenMP executable directive that has no associated user code
 113 except for that which appears in clauses in the directive.
 114
 115 List 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
 127 A higher-level class is created for each category
 128 which contains directives listed above that share a similar structure:
 129 * OpenMPSimpleStandaloneConstruct
 130 (taskyield, barrier, taskwait,
 131 target enter/exit data, target update, ordered)
 132 * OpenMPFlushConstruct
 133 * OpenMPCancelConstruct
 134 * OpenMPCancellationPointConstruct
 135
 136 A top-level class, `OpenMPStandaloneConstruct`,
 137 holds all four of the node types as discriminated unions
 138 along with the source provenance for the entire directive.
 139 Also, each parser node for the stand-alone directive saves
 140 the source provenance for the directive name itself.
 141
 142 ### Clauses
 143
 144 Each clause represented as a distinct class in `parse-tree.h`.
 145 A top-level class, `OmpClause`,
 146 includes all the clauses as discriminated unions.
 147 The parser node for `OmpClause` saves the source provenance
 148 for the entire clause.
 149
 150 All the `Names` or `Designators` associated
 151 with the clauses will be resolved in Semantic Analysis.
 152
 153 Note that the backtracking parser will not validate
 154 that the list of clauses associated
 155 with a directive is valid other than to make sure they are well-formed.
 156 In particular,
 157 the parser does not check that
 158 the association between directive and clauses is correct
 159 nor check that the values in the directives or clauses are correct.
 160 These checks are deferred to later phases of semantics to simplify the parser.
 161
 162 ## Symbol Table Extensions for OpenMP
 163
 164 Name resolution can be impacted by the OpenMP code.
 165 In addition to the regular steps to do the name resolution,
 166 new scopes and symbols may need to be created
 167 when encountering certain OpenMP constructs.
 168 This section describes the extensions
 169 for OpenMP during Symbol Table construction.
 170
 171 OpenMP uses the fork-join model of parallel execution and
 172 all OpenMP threads have access to
 173 a _shared_ memory place to store and retrieve variables
 174 but each thread can also have access to
 175 its _threadprivate_ memory that must not be accessed by other threads.
 176
 177 For the directives and clauses that can control the data environments,
 178 compiler needs to determine two kinds of _access_
 179 to variables used in the directive’s associated structured block:
 180 **shared** and **private**.
 181 Each variable referenced in the structured block
 182 has an original variable immediately outside of the OpenMP constructs.
 183 Reference to a shared variable in the structured block
 184 becomes a reference to the original variable.
 185 However, each private variable referenced in the structured block,
 186 a new version of the original variable (of the same type and size)
 187 will be created in the threadprivate memory.
 188
 189 There are exceptions that directives/clauses
 190 need to create a new `Symbol` without creating a new `Scope`,
 191 but in general,
 192 when encountering each of the data environment controlling directives
 193 (discussed in the following sections),
 194 a new `Scope` will be created.
 195 For each private variable referenced in the structured block,
 196 a new `Symbol` is created out of the original variable
 197 and the new `Symbol` is associated
 198 with original variable’s `Symbol` via `HostAssocDetails`.
 199 A new set of OpenMP specific flags are added
 200 into `Flag` class in `symbol.h` to indicate the types of
 201 associations,
 202 data-sharing attributes,
 203 and data-mapping attributes
 204 in the OpenMP data environments.
 205
 206 ### New Symbol without new Scope
 207
 208 OpenMP directives that require new `Symbol` to be created
 209 but not new `Scope` are listed in the following table
 210 in 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>
 218 Symbol
 219 <p>
 220 w/
 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
 317 For 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
 327 A new `Scope` will be created
 328 when encountering the above OpenMP constructs
 329 to ensure the correct data environment during the Code Generation.
 330 To determine whether a variable referenced in these regions
 331 needs the creation of a new `Symbol`,
 332 all the data-sharing attribute rules
 333 described in OpenMP Spec [2.15.1] apply during the Name Resolution.
 334 The available data-sharing attributes are:
 335 **_shared_**,
 336 **_private_**,
 337 **_linear_**,
 338 **_firstprivate_**,
 339 and **_lastprivate_**.
 340 The attribute is represented as `Flag` in the `Symbol` object.
 341
 342 More 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
 411 To determine the right data-sharing attribute,
 412 OpenMP defines that the data-sharing attributes
 413 of 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)
 420 in the associated _do-loop(s)_ of a
 421 _do_,
 422 _parallel do_,
 423 _taskloop_,
 424 or _distributeconstruct_
 425 is (are) **private**
 426 * A loop iteration variable
 427 for a sequential loop in a _parallel_ or task generating construct
 428 is **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_
 431 of a _simd_ construct with just one associated _do-loop_
 432 is **linear** with a linear-step
 433 that is the increment of the associated _do-loop_
 434 * The loop iteration variables in the associated _do-loop(s)_ of a _simd_
 435 construct with multiple associated _do-loop(s)_ are **lastprivate**
 436
 437 #### Explicitly determined data-sharing attributes
 438
 439 Variables 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
 444 The 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
 455 Note that variables with _predetermined_ data-sharing attributes
 456 may not be listed (with exceptions) in data-sharing attribute clauses.
 457
 458 #### Implicitly determined data-sharing attributes
 459
 460 Variables 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
 465 on the construct.
 466
 467 Rules for variables with _implicitly determined_ data-sharing attributes:
 468
 469 * In a _parallel_ construct, if no _default_ clause is present,
 470 these variables are **shared**
 471 * In a task generating construct,
 472 if no _default_ clause is present,
 473 a variable for which the data-sharing attribute
 474 is not determined by the rules above
 475 and that in the enclosing context is determined
 476 to be shared by all implicit tasks
 477 bound to the current team is **shared**
 478 * In a _target_ construct,
 479 variables that are not mapped after applying data-mapping attribute rules
 480 (discussed later) are **firstprivate**
 481 * In an orphaned task generating construct,
 482 if no _default_ clause is present, dummy arguments are **firstprivate**
 483 * In a task generating construct, if no _default_ clause is present,
 484 a variable for which the data-sharing attribute is not determined
 485 by the rules above is **firstprivate**
 486 * For constructs other than task generating constructs or _target_ constructs,
 487 if no _default_ clause is present,
 488 these variables reference the variables with the same names
 489 that exist in the enclosing context
 490 * In a _parallel_, _teams_, or task generating construct,
 491 the data-sharing attributes of these variables are determined
 492 by 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
 515 When encountering the _target data_ and _target_ directives,
 516 the data-mapping attributes of any variable referenced in a target region
 517 will be determined and represented as `Flag` in the `Symbol` object
 518 of the variable.
 519 No `Symbol` or `Scope` will be created.
 520
 521 The basic steps to determine the data-mapping attribute are:
 522
 523 1. If _map_ clause is present,
 524 the data-mapping attribute is determined by the _map-type_
 525 on the clause and its corresponding `Flag` are listed below:
 526
 527 <table>
 528   <tr>
 529    <td>
 530 data-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
 574 2. Otherwise, the following data-mapping rules apply
 575 for variables referenced in a _target_ construct
 576 that are _not_ declared in the construct and
 577 do 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**
 581 3. 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
 592 After the completion of the Name Resolution phase,
 593 all the data-sharing or data-mapping attributes marked for the `Symbols`
 594 may be used later in the Semantics Analysis and in the Code Generation.
 595
 596 ## Module File Extensions for OpenMP
 597
 598 After the successful compilation of modules and submodules
 599 that may contain the following Declarative Directives,
 600 the entire directive starting from `!$OMP` needs to be written out
 601 into `.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
 626 1. 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)
 633 2. 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
 648 3. 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
 653 4. 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
 657 5. 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
 661 6. 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
 664 7. 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]
 672 8. 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