flang/docs/ControlFlowGraph.md

   1 <!--===- docs/ControlFlowGraph.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 # Control Flow Graph
  10
  11 ```{contents}
  12 ---
  13 local:
  14 ---
  15 ```
  16
  17 ## Concept
  18 After a Fortran subprogram has been parsed, its names resolved, and all its
  19 semantic constraints successfully checked, the parse tree of its
  20 executable part is translated into another abstract representation,
  21 namely the _control flow graph_ described in this note.
  22
  23 This second representation of the subprogram's executable part is
  24 suitable for analysis and incremental modification as the subprogram
  25 is readied for code generation.
  26 Many high-level Fortran features are implemented by rewriting portions
  27 of a subprogram's control flow graph in place.
  28
  29 ### Control Flow Graph
  30 A _control flow graph_ is a collection of simple (_i.e.,_ "non-extended")
  31 basic _blocks_ that comprise straight-line sequences of _actions_ with a
  32 single entry point and a single exit point, and a collection of
  33 directed flow _edges_ (or _arcs_) denoting all possible transitions of
  34 control flow that may take place during execution from the end of
  35 one basic block to the beginning of another (or itself).
  36
  37 A block that has multiple distinct successors in the flow of control
  38 must end with an action that selects its successor.
  39
  40 The sequence of actions that constitutes a basic block may
  41 include references to user and library procedures.
  42 Subprogram calls with implicit control flow afterwards, namely
  43 alternate returns and `END=`/`ERR=` labels on input/output,
  44 will be lowered in translation to a representation that materializes
  45 that control flow into something similar to a computed `GO TO` or
  46 C language `switch` statement.
  47
  48 For convenience in optimization and to simplify the implementation of
  49 data flow confluence functions, we may choose to maintain the
  50 property that each flow arc is the sole outbound arc emanating from
  51 its originating block, the sole inbound arc arriving at its destination,
  52 or both.
  53 Empty blocks would inserted to "split" arcs when necessary to maintain this
  54 invariant property.
  55
  56 Fortran subprograms (other than internal subprograms) can have multiple
  57 entry points by using the obsolescent `ENTRY` statement.
  58 We will implement such subprograms by constructing a union
  59 of their dummy argument lists and using it as part of the definition
  60 of a new subroutine or function that can be called by each of
  61 the entry points, which are then all converted into wrapper routines that
  62 pass a selector value as an additional argument to drive a `switch` on entry
  63 to the new subprogram.
  64
  65 This transformation ensures that every subprogram's control
  66 flow graph has a well-defined `START` node.
  67
  68 Statement labels can be used in Fortran on any statement, but only
  69 the labels that decorate legal destinations of `GO TO` statements
  70 need to be implemented in the control flow graph.
  71 Specifically, non-executable statements like `DATA`, `NAMELIST`, and
  72 `FORMAT` statements will be extracted into data initialization
  73 records before or during the construction of the control flow
  74 graph, and will survive only as synonyms for `CONTINUE`.
  75
  76 Nests of multiple labeled `DO` loops that terminate on the same
  77 label will be have that label rewritten so that `GO TO` within
  78 the loop nest will arrive at the copy that most closely nests
  79 the context.
  80 The Fortran standard does not require us to do this, but XLF
  81 (at least) works this way.
  82
  83 ### Expressions and Statements (Operations and Actions)
  84 Expressions are trees, not DAGs, of intrinsic operations,
  85 resolved function references, constant literals, and
  86 data designators.
  87
  88 Expression nodes are represented in the compiler in a type-safe manner.
  89 There is a distinct class or class template for every category of
  90 intrinsic type, templatized over its supported kind type parameter values.
  91
  92 Operands are storage-owning indirections to other instances
  93 of `Expression`, instances of constant values, and to representations
  94 of data and function references.
  95 These indirections are not nullable apart from the situation in which
  96 the operands of an expression are being removed for use elsewhere before
  97 the expression is destructed.
  98
  99 The ranks and the extents of the shapes of the results of expressions
 100 are explicit for constant arrays and recoverable by analysis otherwise.
 101
 102 Parenthesized subexpressions are scrupulously preserved in accordance with
 103 the Fortran standard.
 104
 105 The expression tree is meant to be a representation that is
 106 as equally well suited for use in the symbol table (e.g., for
 107 a bound of an explicit shape array) as it is for an action
 108 in a basic block of the control flow graph (e.g., the right
 109 hand side of an assignment statement).
 110
 111 Each basic block comprises a linear sequence of _actions_.
 112 These are represented as a doubly-linked list so that insertion
 113 and deletion can be done in constant time.
 114
 115 Only the last action in a basic block can represent a change
 116 to the flow of control.
 117
 118 ### Scope Transitions
 119 Some of the various scopes of the symbol table are visible in the control flow
 120 graph as `SCOPE ENTRY` and `SCOPE EXIT` actions.
 121 `SCOPE ENTRY` actions are unique for their corresponding scopes,
 122 while `SCOPE EXIT` actions need not be so.
 123 It must be the case that
 124 any flow of control within the subprogram will enter only scopes that are
 125 not yet active, and exit only the most recently entered scope that has not
 126 yet been deactivated; i.e., when modeled by a push-down stack that is
 127 pushed by each traversal of a `SCOPE ENTRY` action,
 128 the entries of the stack are always distinct, only the scope at
 129 the top of the stack is ever popped by `SCOPE EXIT`, and the stack is empty
 130 when the subprogram terminates.
 131 Further, any references to resolved symbols must be to symbols whose scopes
 132 are active.
 133
 134 The `DEALLOCATE` actions and calls to `FINAL` procedures implied by scoped
 135 lifetimes will be explicit in the sequence of actions in the control flow
 136 graph.
 137
 138 Parallel regions might be partially represented by scopes, or by explicit
 139 operations similar to the scope entry and exit operations.
 140
 141 ### Data Flow Representation
 142 The subprogram text will be in static single assignment form by the time the
 143 subprogram arrives at the bridge to the LLVM IR builder.
 144 Merge points are actions at the heads of basic blocks whose operands
 145 are definition points; definition points are actions at the ends of
 146 basic blocks whose operands are expression trees (which may refer to
 147 merge points).
 148
 149 ### Rewriting Transformations
 150
 151 #### I/O
 152 #### Dynamic allocation
 153 #### Array constructors
 154
 155 #### Derived type initialization, deallocation, and finalization
 156 The machinery behind the complicated semantics of Fortran's derived types
 157 and `ALLOCATABLE` objects will be implemented in large part by the run time
 158 support library.
 159
 160 #### Actual argument temporaries
 161 #### Array assignments, `WHERE`, and `FORALL`
 162
 163 Array operations have shape.
 164
 165 `WHERE` masks have shape.
 166 Their effects on array operations are by means of explicit `MASK` operands that
 167 are part of array assignment operations.
 168
 169 #### Intrinsic function and subroutine calls