flang/docs/BijectiveInternalNameUniquing.md

   1 # Bijective Internal Name Uniquing
   2
   3 ```eval_rst
   4 .. contents::
   5    :local:
   6 ```
   7
   8 FIR has a flat namespace.  No two objects may have the same name at
   9 the module level.  (These would be functions, globals, etc.)
  10 This necessitates some sort of encoding scheme to unique
  11 symbols from the front-end into FIR.
  12
  13 Another requirement is
  14 to be able to reverse these unique names and recover the associated
  15 symbol in the symbol table.
  16
  17 Fortran is case insensitive, which allows the compiler to convert the
  18 user's identifiers to all lower case.  Such a universal conversion implies
  19 that all upper case letters are available for use in uniquing.
  20
  21 ## Prefix `_Q`
  22
  23 All uniqued names have the prefix sequence `_Q` to indicate the name has
  24 been uniqued.  (Q is chosen because it is a
  25 [low frequency letter](http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html)
  26 in English.)
  27
  28 ## Scope Building
  29
  30 Symbols can be scoped by the module, submodule, or procedure that contains
  31 that symbol.  After the `_Q` sigil, names are constructed from outermost to
  32 innermost scope as
  33
  34    * Module name prefixed with `M`
  35    * Submodule name prefixed with `S`
  36    * Procedure name prefixed with `F`
  37
  38 Given:
  39 ```
  40     submodule (mod:s1mod) s2mod
  41       ...
  42       subroutine sub
  43         ...
  44       contains
  45         function fun
  46 ```
  47
  48 The uniqued name of `fun` becomes:
  49 ```
  50     _QMmodSs1modSs2modFsubPfun
  51 ```
  52
  53 ## Common blocks
  54
  55    * A common block name will be prefixed with `B`
  56
  57 Given:
  58 ```
  59    common /variables/ i, j
  60 ```
  61
  62 The uniqued name of `variables` becomes:
  63 ```
  64     _QBvariables
  65 ```
  66
  67 Given:
  68 ```
  69    common i, j
  70 ```
  71
  72 The uniqued name in case of `blank common block` becomes:
  73 ```
  74     _QB
  75 ```
  76
  77 ## Module scope global data
  78
  79    * A global data entity is prefixed with `E`
  80    * A global entity that is constant (parameter) will be prefixed with `EC`
  81
  82 Given:
  83 ```
  84     module mod
  85       integer :: intvar
  86       real, parameter :: pi = 3.14
  87     end module
  88 ```
  89
  90 The uniqued name of `intvar` becomes:
  91 ```
  92     _QMmodEintvar
  93 ```
  94
  95 The uniqued name of `pi` becomes:
  96 ```
  97     _QMmodECpi
  98 ```
  99
 100 ## Procedures/Subprograms
 101
 102    * A procedure/subprogram is prefixed with `P`
 103
 104 Given:
 105 ```
 106     subroutine sub
 107 ```
 108 The uniqued name of `sub` becomes:
 109 ```
 110     _QPsub
 111 ```
 112
 113 ## Derived types and related
 114
 115    * A derived type is prefixed with `T`
 116    * If a derived type has KIND parameters, they are listed in a consistent
 117      canonical order where each takes the form `Ki` and where _i_ is the
 118      compile-time constant value. (All type parameters are integer.)  If _i_
 119      is a negative value, the prefix `KN` will be used and _i_ will reflect
 120      the magnitude of the value.
 121
 122 Given:
 123 ```
 124     module mymodule
 125       type mytype
 126         integer :: member
 127       end type
 128       ...
 129 ```
 130 The uniqued name of `mytype` becomes:
 131 ```
 132     _QMmymoduleTmytype
 133 ```
 134
 135 Given:
 136 ```
 137     type yourtype(k1,k2)
 138       integer, kind :: k1, k2
 139       real :: mem1
 140       complex :: mem2
 141     end type
 142 ```
 143
 144 The uniqued name of `yourtype` where `k1=4` and `k2=-6` (at compile-time):
 145 ```
 146     _QTyourtypeK4KN6
 147 ```
 148
 149    * A derived type dispatch table is prefixed with `D`.  The dispatch table
 150      for `type t` would be `_QDTt`
 151    * A type descriptor instance is prefixed with `C`.  Intrinsic types can
 152      be encoded with their names and kinds.  The type descriptor for the
 153      type `yourtype` above would be `_QCTyourtypeK4KN6`.  The type
 154      descriptor for `REAL(4)` would be `_QCrealK4`.
 155
 156 ## Compiler generated names
 157
 158 Compiler generated names do not have to be mapped back to Fortran.  These
 159 names will be prefixed with `_QQ` and followed by a unique compiler
 160 generated identifier. There is, of course, no mapping back to a symbol
 161 derived from the input source in this case as no such symbol exists.