1# Investigating FIR as an MLIR Dialect 2 3## Introduction 4 5With the availability of the extensible MLIR framework as 6open-source, we've been investigating the potential to use MLIR as 7a substrate upon which to build a FIR dialect. This document will 8explain the motivations and the shape of this subproject using MLIR 9to define and implement a high-level operational representation of 10Fortran. (See also [Design: Fortran IR](https://bit.ly/2WWRus0) 11for more information.) 12 13### What is MLIR? 14 15The MLIR project is an open-sourced project on Github. 16[MLIR](https://github.com/tensorflow/mlir) is being built as a 17common multi-level intermediate representation (IR) for the 18TensorFlow machine learning tools. It provides a common IR 19framework for building multiple layers of representation called 20dialects. These dialects can be transformed (converted) from one to 21another allowing for optimizations and successive lowering of the 22IR down to backend code generators. MLIR supports multiple backends. The 23LLVM IR dialect is a pre-defined MLIR dialect 24that can be targeted 25for final code generation using the LLVM library and/or tools. 26MLIR is explicitly intended to be extensible such that 27other projects can add their own dialects. 28 29Out of the box, MLIR supports a refined polyhedral model for 30transforming affine operations on array data. These mathematically-based 31representations will help realize F18's higher level goals of composing, 32transforming, and optimizing Fortran array operations for HPC. 33 34### What is meant by a FIR dialect? 35 36MLIR has no support for Fortran out of the box. Support for Fortran must 37be built and added through the extensibility features of MLIR. This 38process of extending MLIR is called adding a dialect. In our case, we'll 39add a FIR dialect for representation of Fortran programs. 40 41Specifically, this means that we can proceed with the plan as laid out 42in the Fortran IR design document with the advantages of not having to 43build from scratch our own 44 45- IR infrastructure 46- LLVM IR bridge 47- Common optimization passes (For example: CSE, DCE, loop fusion, loop 48 invariant code motion, loop tiling, loop unroll and jam, loop 49 unrolling, vectorization, etc.) 50 51A dialect can be thought of 52as its own distinct IR, where the design and 53semantics of the IR are domain-specific for the purposes of the 54dialect. Specifically, MLIR supports a modern IR design with 55 56- A predefined set of operations with precise semantics 57- Structural/logical grouping of sets of operations 58- Explicit control flow 59- Explicit data-flow 60- Strong typing 61 62- Meta information 63 64 Informally, one can construct MLIR operations that are 65 conceptually composable containers. These containers can have 66 strongly typed metadata attached to them that can describe 67 any properties of interest. For example, one can define an 68 operation called "execute" and define it to have an attribute 69 "order", which may have a value that describes a sequential 70 execution order, a fully parallel unordered execution, or some 71 valid execution partial ordering. What meta information is 72 interesting depends on the context and is up to the MLIR user. 73 74This document describes FIR, which is a set of extensions upon the 75standard MLIR dialect. When lowering a Fortran parse tree to FIR, 76the compiler will produce a mix of operations defined in the FIR 77dialect, the MLIR __standard dialect__, and other pre-defined 78dialects, such as the [affine dialect](https://bit.ly/2XYDPNj). 79 80#### Disclaimers 81 82This document is not a tutorial on compilers, Fortran, MLIR, LLVM, 83intermediate representations, abstraction levels, semantics, nor type 84theory. 85 86## Requirements Unchanged 87 88The FIR dialect has the same requirements as spelled out in the 89Fortran IR design document. Specifically, the FIR dialect will 90capture the control flow structure of the Fortran source-level 91program. At the highest level of abstraction, Fortran computations 92will be captured as coarse-grain opaque 93operations corresponding to Fortran expressions 94(with links to `Fortran::evaluate::Expr<T>` objects from the 95front-end), where only the peripheral use-def information is 96exposed. These operations will, of course, necessarily be lowered 97to other various MLIR dialects, where they can be 98optimized. 99The compiler will continue to lower the representation 100of the input with successive transformations 101to MLIR's LLVM IR dialect, the target independent LLVM IR, machine 102IR, and eventually assembly and/or machine code. 103 104## Details 105 106Because MLIR is our adopted framework, our bridge to the FIR 107dialect of MLIR will use the concepts, libraries, coding 108conventions, etc. of the MLIR project. This means some of the class 109names will necessarily be changed from the original FIR design. For 110example, `Program` becomes `Module`, `Procedure` becomes 111`Function`, `BasicBlock` becomes `Block`, and `Statement` becomes 112`Operation`. 113 114Construction of the CFG structure reuses the original FIR pass that 115flattens and linearizes the Fortran parse tree structure prior to 116creating the FIR dialect of MLIR. 117 118`Afforestation` (a class in the original FIR code) 119of the FIR dialect tree structure has to be rewritten 120as the original framework is replaced by that of 121MLIR. Conceptually, the process and objective remains the same. 122 123### FIR Dialect Details 124 125The FIR dialect is a well-defined set of operations, types, etc. that 126captures the executable semantics and state of a correctly specified 127Fortran program. In Fortran, action statements [Fortran 2018 R515] and 128certain constructs specify the behavior of the program. Among these, 129Fortran expressions [Fortran 2018 Clause 10.1] are intrinsic to the 130computation of new values. 131 132#### FIR Operations 133 134Abstract expression operations are higher-level operations that are 135opaque computations in FIR. FIR does not know the exact computations 136involved. However, the framework requires explicit representation of how 137each operation interacts with others in terms of control flow, 138data-flow, and the types of its operands and results. These operations 139must then be lowered to sequences of operations as required by the 140standard MLIR dialect, the LLVM IR dialect, etc. 141 142##### Expression ops 143 144The following lists the FIR abstract expression operations: 145 146+ _Apply_Expr_ 147 148 This operation computes a (set of) value(s) by applying an abstract 149 expression to a set of SSA input values. 150 151 As well as its input values and type, an Apply_Expr takes two 152 attributes that serve to bind the exact opaque expression from the 153 front-end. The first attribute is the expression as recovered from 154 the parse tree. The second attribute is a dictionary that maps the 155 incoming values to positions in the expression representation, 156 allowing values to bind to nodes in the expression. 157 158+ _Locate_Expr_ 159 160 This operation computes a (set of) memory reference(s) by applying 161 an abstract expression to a set of SSA input values. 162 163 Exactly analogous to Apply_Expr, this operation also takes two 164 attributes to capture the expression from the front-end and to bind 165 arguments to nodes in the expression tree. 166 167+ _Alloca_Expr_ 168 169 This operation allocates a temporary object of some specified 170 type. The resulting object is undefined. It must be explicitly 171 initialized with subsequent operations. 172 173+ _Undefined_ 174 175 This operation yields the canonical undefined value of some 176 type. This operation lowers to the undef instruction in LLVM IR. It 177 is required for construction of register SSA form when load 178 operations load uninitialized values. 179 180+ _Load_Expr_ 181 182 This operation promotes a reference to a Fortran object (for 183 example, the result of a Locate_Expr operation) to an object value 184 irrespective of type. It takes one argument, a reference to an 185 abstract storage location. 186 187 Recall that the abstract expression operations listed here operate 188 on and produce SSA values. (Specifically, they are abstract 189 operations with precise control- and data-flow constraints.) 190 191+ _Store_Expr_ 192 193 This operation demotes a value to a reference to an object. It 194 takes two arguments: both a value and a reference to an abstract 195 storage location (for example, the result of a Global_Expr 196 operation) of the same type. 197 198##### Control flow ops 199 200Fortran has a number of mechanisms for specifying control flow, both 201structured (DO ... END DO) and unstructured (GOTO). Many of these can be 202directly lowered to the standard dialect's branch and conditional branch 203operations. 204 205There are a handful of multiway branch constructs to consider and these 206will be modeled as FIR (terminator) operations. The framework supports a 207generic terminator pattern operation. Specifically, a terminator is just 208an operation but it is augmented with successors (references to basic 209blocks) and successor arguments (for correct SSA form). 210 211+ _Select_ 212 213 Terminator operation for switching based on the return value of, 214 for example, an I/O action. 215 216+ _Select_Case_ 217 218 Terminator operation for switching on the value of an expression. 219 220+ _Select_Rank_ 221 222 Terminator operation for switching on the rank attribute of an 223 object. Must be lowered to the requisite operations on the object's 224 descriptor (which shall assumably contain the rank, dimension, 225 type, etc. of the Fortran object). 226 227+ _Select_Type_ 228 229 Terminator operation for switching on the type of an object. Must 230 be lowered to the requisite operations on the object's type 231 descriptor (which shall contain the encoded type of the Fortran 232 object). 233 234+ _Unreachable_ 235 236 This operation is a terminator on a Block and indicates that 237 control flow cannot reach this point. This happens when lowering 238 Fortran's [ERROR] STOP statement into a runtime call. It is lowered 239 into the LLVM IR as an unreachable instruction. 240 241For now, indirect branches (such as computed GOTO statements), will be 242lowered by mapping target blocks into an indirect index value used in a 243small chain of conditional branches. This could be changed to use the 244standard dialect indirect branch op, however. 245 246The standard dialect of MLIR supports calling procedures in full 247generality -- that is, both function calls in expressions and CALL 248statements to subroutines. Both cases will be lowered explicitly into 249FIR using the standard dialect CallOp operation. The call operation is 250an abstract application of a (presumably) opaque set of computations on 251the SSA input values that produces a (set of) SSA result 252value(s). (Semantically, a CallOp is a named morphism like the anonymous 253ApplyExpr or LocateExpr.) 254 255##### Miscellaneous ops 256 257The presence of certain attributes on specific objects allow for dynamic 258allocation and deallocation of those objects. These allocations and 259deallocations can be explicit through the ALLOCATE and DEALLOCATE 260statements or can be implied via side-effect. Dynamic allocation and 261deallocation are modeled with FIR operations. It should be pointed out 262that MLIR does not, at present, have a standard way of expressing an 263object that has process lifetime (that is, "global" data like COMMON 264blocks and MODULE variables) that is not a function. This is implemented 265with the Global_Expr operation below. 266 267+ _Allocmem_ 268 269 This operation allocates an object of a specified type and returns 270 a reference to it. The object's lifetime is dynamic/indefinite and 271 limited to a matching FreememOp operation that deallocates it. No 272 side-effect behaviors are implied. Initialization of the object 273 must be done explicitly in subsequent FIR operations. 274 275+ _Freemem_ 276 277 This operation deallocates an object via a Fortran reference. Any 278 use of the reference in subsequent code is undefined 279 behavior. There are no implicit behaviors, so finalizers must be 280 lowered explicitly into FIR. 281 282+ _Global_Expr_ 283 284 This operation is a placeholder for a reference to an object in a 285 storage location that has process lifetime (a global variable). It 286 must have a type and a symbol name for binding at link-time. 287 288+ _Extract_Value_ 289 290 This operation is similar to LLVM's `extractvalue` instruction. 291 It allows the 292 extraction of a value from a composite structure, such as a 293 standard tuple. 294 295+ _Insert_Value_ 296 297 The operation allows the insertion of a value into a composite 298 structure, such as a standard tuple. 299 300+ _Field_Value_ 301 302 This operation computes the offset of a component of a derived type 303 for use in ExtractValue or InsertValue operations. 304 305A number of Fortran action statements/constructs are related to 306synchronization/threading. (e.g., LOCK, UNLOCK, EVENT POST, DO 307CONCURRENT, co-arrays, etc.). The current plan is not to model these 308parallel execution semantics directly in FIR, but to lower these 309synchronization and threading statements to Fortran runtime calls. The 310implicit message passing semantics of co-arrays can be lowered to 311explicit calls as well, though the exact API is TBD. 312 313#### FIR Types 314 315Some Fortran intrinsic types are familiar and map well to MLIR standard 316types. (e.g., `INTEGER*k`, `REAL*k`, and `COMPLEX*k`.) 317However, the intrinsic 318type `CHARACTER*k(LEN=n)` has no analog. Finally, the intrinsic type 319`LOGICAL*k` and derived (user-defined) types should not be prematurely 320lowered to standard MLIR types because that may inhibit optimization and 321add complexity. (e.g., one could lower a `LOGICAL*`1 type to the standard 322`i8` type, but then it would have the same type as `INTEGER*1` and, 323depending on its usage, may have better been lowered to `i1`.) 324 325In addition to types from the surface syntax of Fortran, it is 326beneficial to introduce metatypes to FIR to capture Fortran attribute 327properties that alter the underlying object in an operational 328sense. Specifically, attributes such as `DIMENSION`, `CODIMENSION`, and 329`POINTER`, alter the size, behavior, and accepted use of a variable but 330not its type (in the Fortran sense). 331 332The additional FIR types are as follows. 333 334+ __FIRCharacterType__ 335 336 The Fortran intrinsic type CHARACTER with a kind value. This is 337 meant to represent the constant-sized memory reference and is 338 intentionally distinct from, for instance, an array of byte-sized 339 integers. The LEN parameter of a CHARACTER should be represented as 340 a second integer member in a FIR tuple type. Concretely, a Fortran 341 CHARACTER type is lowered into a pair: 342 343 `(FIRReferenceType<FIRCharacterType<K>>, Integer<K'>)` 344 345+ __FIRLogicalType__ 346 347 The Fortran intrinsic type LOGICAL with a kind value. 348 349+ __FIRRealType__ 350 351 The Fortran intrinsic type REAL with kind values (e.g., KIND=16) 352 that do not map to standard MLIR. 353 354+ __FIRReferenceType__ 355 356 The Fortran concept of "reference". Actual arguments are typically 357 passed as references to objects of some type, for example. All 358 objects that reside in memory are accessible via reference types. 359 360+ __FIRSequenceType__ 361 362 The Fortran concept of an object with rank > 0. Fortran does not 363 have an array type, but FIR characterizes objects with rank as 364 sequences of their base type. 365 366 In lowering a Fortran array object, the dimensions and extents of 367 the array may not be known at compile time, and therefore may need 368 to be lowered to a tuple type that describes the array's structure 369 (rank, type, dimension information, other attributes). 370 371+ __FIRTupleType__ 372 373 Fortran derived types naturally map to tuples. Can be used to build 374 other type packages as well, such as Fortran's CHARACTER type with 375 its LEN parameter, array object structure descriptors, etc. Each 376 distinct tuple type has a unique name and a run-time encoding, the 377 type descriptor. (Note: any subtyping relationships between derived 378 types must be established by and lowered from the front-end.) 379 380+ __FIRTypeDesc__ 381 382 The meta-type of all type descriptors. An instance of a type 383 descriptor is a constant object that encodes a Fortran (intrinsic, 384 derived) type for use by the runtime, etc. This type is 385 speculative, as it may be (more) satisfactory to encode a type 386 descriptor as a simple dope vector sequence. 387 388### Changes from Original Document 389 390Procedure calls will be unwrapped from Fortran expressions and lowered 391into FIR dialect calls to expose control flow. 392 393These computations will be presented in a memory-based SSA format, where 394memory objects will be referenced via special operation forms. 395 396There will be a pass to lower 397the memory-based SSA form to a 398register-based (proper) SSA form. There will be no 399Φ nodes. 400 401There will be no scope enter, scope exit pairs. 402 403There will be a pass to lower the FIR dialect to the MLIR standard 404dialect and/or LLVM IR dialect. 405 406