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