1# 'affine' Dialect 2 3This dialect provides a powerful abstraction for affine operations and analyses. 4 5[TOC] 6 7## Polyhedral Structures 8 9MLIR uses techniques from polyhedral compilation to make dependence analysis and 10loop transformations efficient and reliable. This section introduces some of the 11core concepts that are used throughout the document. 12 13### Dimensions and Symbols 14 15Dimensions and symbols are the two kinds of identifiers that can appear in the 16polyhedral structures, and are always of [`index`](../LangRef.md#index-type) 17type. Dimensions are declared in parentheses and symbols are declared in square 18brackets. 19 20Examples: 21 22```mlir 23// A 2d to 3d affine mapping. 24// d0/d1 are dimensions, s0 is a symbol 25#affine_map2to3 = affine_map<(d0, d1)[s0] -> (d0, d1 + s0, d1 - s0)> 26``` 27 28Dimensional identifiers correspond to the dimensions of the underlying structure 29being represented (a map, set, or more concretely a loop nest or a tensor); for 30example, a three-dimensional loop nest has three dimensional identifiers. Symbol 31identifiers represent an unknown quantity that can be treated as constant for a 32region of interest. 33 34Dimensions and symbols are bound to SSA values by various operations in MLIR and 35use the same parenthesized vs square bracket list to distinguish the two. 36 37Syntax: 38 39``` 40// Uses of SSA values that are passed to dimensional identifiers. 41dim-use-list ::= `(` ssa-use-list? `)` 42 43// Uses of SSA values that are used to bind symbols. 44symbol-use-list ::= `[` ssa-use-list? `]` 45 46// Most things that bind SSA values bind dimensions and symbols. 47dim-and-symbol-use-list ::= dim-use-list symbol-use-list? 48``` 49 50SSA values bound to dimensions and symbols must always have 'index' type. 51 52Example: 53 54```mlir 55#affine_map2to3 = affine_map<(d0, d1)[s0] -> (d0, d1 + s0, d1 - s0)> 56// Binds %N to the s0 symbol in affine_map2to3. 57%x = alloc()[%N] : memref<40x50xf32, #affine_map2to3> 58``` 59 60### Restrictions on Dimensions and Symbols 61 62The affine dialect imposes certain restrictions on dimension and symbolic 63identifiers to enable powerful analysis and transformation. An SSA value's use 64can be bound to a symbolic identifier if that SSA value is either 651. a region argument for an op with trait `AffineScope` (eg. `FuncOp`), 662. a value defined at the top level of an `AffineScope` op (i.e., immediately 67enclosed by the latter), 683. a value that dominates the `AffineScope` op enclosing the value's use, 694. the result of a [`constant` operation](Standard.md#constant-operation), 705. the result of an [`affine.apply` 71operation](#affineapply-operation) that recursively takes as arguments any valid 72symbolic identifiers, or 736. the result of a [`dim` operation](Standard.md#dim-operation) on either a 74memref that is an argument to a `AffineScope` op or a memref where the 75corresponding dimension is either static or a dynamic one in turn bound to a 76valid symbol. 77*Note:* if the use of an SSA value is not contained in any op with the 78`AffineScope` trait, only the rules 4-6 can be applied. 79 80Note that as a result of rule (3) above, symbol validity is sensitive to the 81location of the SSA use. Dimensions may be bound not only to anything that a 82symbol is bound to, but also to induction variables of enclosing 83[`affine.for`](#affinefor-operation) and 84[`affine.parallel`](#affineparallel-operation) operations, and the result of an 85[`affine.apply` operation](#affineapply-operation) (which recursively may use 86other dimensions and symbols). 87 88### Affine Expressions 89 90Syntax: 91 92``` 93affine-expr ::= `(` affine-expr `)` 94 | affine-expr `+` affine-expr 95 | affine-expr `-` affine-expr 96 | `-`? integer-literal `*` affine-expr 97 | affine-expr `ceildiv` integer-literal 98 | affine-expr `floordiv` integer-literal 99 | affine-expr `mod` integer-literal 100 | `-`affine-expr 101 | bare-id 102 | `-`? integer-literal 103 104multi-dim-affine-expr ::= `(` `)` 105 | `(` affine-expr (`,` affine-expr)* `)` 106``` 107 108`ceildiv` is the ceiling function which maps the result of the division of its 109first argument by its second argument to the smallest integer greater than or 110equal to that result. `floordiv` is a function which maps the result of the 111division of its first argument by its second argument to the largest integer 112less than or equal to that result. `mod` is the modulo operation: since its 113second argument is always positive, its results are always positive in our 114usage. The `integer-literal` operand for ceildiv, floordiv, and mod is always 115expected to be positive. `bare-id` is an identifier which must have type 116[index](../LangRef.md#index-type). The precedence of operations in an affine 117expression are ordered from highest to lowest in the order: (1) 118parenthesization, (2) negation, (3) modulo, multiplication, floordiv, and 119ceildiv, and (4) addition and subtraction. All of these operators associate from 120left to right. 121 122A _multidimensional affine expression_ is a comma separated list of 123one-dimensional affine expressions, with the entire list enclosed in 124parentheses. 125 126**Context:** An affine function, informally, is a linear function plus a 127constant. More formally, a function f defined on a vector $$\vec{v} \in 128\mathbb{Z}^n$$ is a multidimensional affine function of $$\vec{v}$$ if 129$$f(\vec{v})$$ can be expressed in the form $$M \vec{v} + \vec{c}$$ where $$M$$ 130is a constant matrix from $$\mathbb{Z}^{m \times n}$$ and $$\vec{c}$$ is a 131constant vector from $$\mathbb{Z}$$. $$m$$ is the dimensionality of such an 132affine function. MLIR further extends the definition of an affine function to 133allow 'floordiv', 'ceildiv', and 'mod' with respect to positive integer 134constants. Such extensions to affine functions have often been referred to as 135quasi-affine functions by the polyhedral compiler community. MLIR uses the term 136'affine map' to refer to these multidimensional quasi-affine functions. As 137examples, $$(i+j+1, j)$$, $$(i \mod 2, j+i)$$, $$(j, i/4, i \mod 4)$$, $$(2i+1, 138j)$$ are two-dimensional affine functions of $$(i, j)$$, but $$(i \cdot j, 139i^2)$$, $$(i \mod j, i/j)$$ are not affine functions of $$(i, j)$$. 140 141### Affine Maps 142 143Syntax: 144 145``` 146affine-map-inline 147 ::= dim-and-symbol-id-lists `->` multi-dim-affine-expr 148``` 149 150The identifiers in the dimensions and symbols lists must be unique. These are 151the only identifiers that may appear in 'multi-dim-affine-expr'. Affine maps 152with one or more symbols in its specification are known as "symbolic affine 153maps", and those with no symbols as "non-symbolic affine maps". 154 155**Context:** Affine maps are mathematical functions that transform a list of 156dimension indices and symbols into a list of results, with affine expressions 157combining the indices and symbols. Affine maps distinguish between 158[indices and symbols](#dimensions-and-symbols) because indices are inputs to the 159affine map when the map is called (through an operation such as 160[affine.apply](#affineapply-operation)), whereas symbols are bound when 161the map is established (e.g. when a memref is formed, establishing a 162memory [layout map](../LangRef.md#layout-map)). 163 164Affine maps are used for various core structures in MLIR. The restrictions we 165impose on their form allows powerful analysis and transformation, while keeping 166the representation closed with respect to several operations of interest. 167 168#### Named affine mappings 169 170Syntax: 171 172``` 173affine-map-id ::= `#` suffix-id 174 175// Definitions of affine maps are at the top of the file. 176affine-map-def ::= affine-map-id `=` affine-map-inline 177module-header-def ::= affine-map-def 178 179// Uses of affine maps may use the inline form or the named form. 180affine-map ::= affine-map-id | affine-map-inline 181``` 182 183Affine mappings may be defined inline at the point of use, or may be hoisted to 184the top of the file and given a name with an affine map definition, and used by 185name. 186 187Examples: 188 189```mlir 190// Affine map out-of-line definition and usage example. 191#affine_map42 = affine_map<(d0, d1)[s0] -> (d0, d0 + d1 + s0 floordiv 2)> 192 193// Use an affine mapping definition in an alloc operation, binding the 194// SSA value %N to the symbol s0. 195%a = alloc()[%N] : memref<4x4xf32, #affine_map42> 196 197// Same thing with an inline affine mapping definition. 198%b = alloc()[%N] : memref<4x4xf32, affine_map<(d0, d1)[s0] -> (d0, d0 + d1 + s0 floordiv 2)>> 199``` 200 201### Semi-affine maps 202 203Semi-affine maps are extensions of affine maps to allow multiplication, 204`floordiv`, `ceildiv`, and `mod` with respect to symbolic identifiers. 205Semi-affine maps are thus a strict superset of affine maps. 206 207Syntax of semi-affine expressions: 208 209``` 210semi-affine-expr ::= `(` semi-affine-expr `)` 211 | semi-affine-expr `+` semi-affine-expr 212 | semi-affine-expr `-` semi-affine-expr 213 | symbol-or-const `*` semi-affine-expr 214 | semi-affine-expr `ceildiv` symbol-or-const 215 | semi-affine-expr `floordiv` symbol-or-const 216 | semi-affine-expr `mod` symbol-or-const 217 | bare-id 218 | `-`? integer-literal 219 220symbol-or-const ::= `-`? integer-literal | symbol-id 221 222multi-dim-semi-affine-expr ::= `(` semi-affine-expr (`,` semi-affine-expr)* `)` 223``` 224 225The precedence and associativity of operations in the syntax above is the same 226as that for [affine expressions](#affine-expressions). 227 228Syntax of semi-affine maps: 229 230``` 231semi-affine-map-inline 232 ::= dim-and-symbol-id-lists `->` multi-dim-semi-affine-expr 233``` 234 235Semi-affine maps may be defined inline at the point of use, or may be hoisted to 236the top of the file and given a name with a semi-affine map definition, and used 237by name. 238 239``` 240semi-affine-map-id ::= `#` suffix-id 241 242// Definitions of semi-affine maps are at the top of file. 243semi-affine-map-def ::= semi-affine-map-id `=` semi-affine-map-inline 244module-header-def ::= semi-affine-map-def 245 246// Uses of semi-affine maps may use the inline form or the named form. 247semi-affine-map ::= semi-affine-map-id | semi-affine-map-inline 248``` 249 250### Integer Sets 251 252An integer set is a conjunction of affine constraints on a list of identifiers. 253The identifiers associated with the integer set are separated out into two 254classes: the set's dimension identifiers, and the set's symbolic identifiers. 255The set is viewed as being parametric on its symbolic identifiers. In the 256syntax, the list of set's dimension identifiers are enclosed in parentheses 257while its symbols are enclosed in square brackets. 258 259Syntax of affine constraints: 260 261``` 262affine-constraint ::= affine-expr `>=` `0` 263 | affine-expr `==` `0` 264affine-constraint-conjunction ::= affine-constraint (`,` affine-constraint)* 265``` 266 267Integer sets may be defined inline at the point of use, or may be hoisted to the 268top of the file and given a name with an integer set definition, and used by 269name. 270 271``` 272integer-set-id ::= `#` suffix-id 273 274integer-set-inline 275 ::= dim-and-symbol-id-lists `:` '(' affine-constraint-conjunction? ')' 276 277// Declarations of integer sets are at the top of the file. 278integer-set-decl ::= integer-set-id `=` integer-set-inline 279 280// Uses of integer sets may use the inline form or the named form. 281integer-set ::= integer-set-id | integer-set-inline 282``` 283 284The dimensionality of an integer set is the number of identifiers appearing in 285dimension list of the set. The affine-constraint non-terminals appearing in the 286syntax above are only allowed to contain identifiers from dims and symbols. A 287set with no constraints is a set that is unbounded along all of the set's 288dimensions. 289 290Example: 291 292```mlir 293// A example two-dimensional integer set with two symbols. 294#set42 = affine_set<(d0, d1)[s0, s1] 295 : (d0 >= 0, -d0 + s0 - 1 >= 0, d1 >= 0, -d1 + s1 - 1 >= 0)> 296 297// Inside a Region 298affine.if #set42(%i, %j)[%M, %N] { 299 ... 300} 301``` 302 303`d0` and `d1` correspond to dimensional identifiers of the set, while `s0` and 304`s1` are symbol identifiers. 305 306## Operations 307 308[include "Dialects/AffineOps.md"] 309 310### 'affine.load' operation 311 312Syntax: 313 314``` 315operation ::= ssa-id `=` `affine.load` ssa-use `[` multi-dim-affine-map-of-ssa-ids `]` `:` memref-type 316``` 317 318The `affine.load` op reads an element from a memref, where the index for each 319memref dimension is an affine expression of loop induction variables and 320symbols. The output of 'affine.load' is a new value with the same type as the 321elements of the memref. An affine expression of loop IVs and symbols must be 322specified for each dimension of the memref. The keyword 'symbol' can be used to 323indicate SSA identifiers which are symbolic. 324 325Example: 326 327```mlir 328 329 Example 1: 330 331 %1 = affine.load %0[%i0 + 3, %i1 + 7] : memref<100x100xf32> 332 333 Example 2: Uses 'symbol' keyword for symbols '%n' and '%m'. 334 335 %1 = affine.load %0[%i0 + symbol(%n), %i1 + symbol(%m)] 336 : memref<100x100xf32> 337 338``` 339 340### 'affine.store' operation 341 342Syntax: 343 344``` 345operation ::= ssa-id `=` `affine.store` ssa-use, ssa-use `[` multi-dim-affine-map-of-ssa-ids `]` `:` memref-type 346``` 347 348The `affine.store` op writes an element to a memref, where the index for each 349memref dimension is an affine expression of loop induction variables and 350symbols. The 'affine.store' op stores a new value which is the same type as the 351elements of the memref. An affine expression of loop IVs and symbols must be 352specified for each dimension of the memref. The keyword 'symbol' can be used to 353indicate SSA identifiers which are symbolic. 354 355Example: 356 357```mlir 358 359 Example 1: 360 361 affine.store %v0, %0[%i0 + 3, %i1 + 7] : memref<100x100xf32> 362 363 Example 2: Uses 'symbol' keyword for symbols '%n' and '%m'. 364 365 affine.store %v0, %0[%i0 + symbol(%n), %i1 + symbol(%m)] 366 : memref<100x100xf32> 367 368``` 369 370### 'affine.dma_start' operation 371 372Syntax: 373 374``` 375operation ::= `affine.dma_Start` ssa-use `[` multi-dim-affine-map-of-ssa-ids `]`, `[` multi-dim-affine-map-of-ssa-ids `]`, `[` multi-dim-affine-map-of-ssa-ids `]`, ssa-use `:` memref-type 376``` 377 378The `affine.dma_start` op starts a non-blocking DMA operation that transfers 379data from a source memref to a destination memref. The source and destination 380memref need not be of the same dimensionality, but need to have the same 381elemental type. The operands include the source and destination memref's 382each followed by its indices, size of the data transfer in terms of the 383number of elements (of the elemental type of the memref), a tag memref with 384its indices, and optionally at the end, a stride and a 385number_of_elements_per_stride arguments. The tag location is used by an 386AffineDmaWaitOp to check for completion. The indices of the source memref, 387destination memref, and the tag memref have the same restrictions as any 388affine.load/store. In particular, index for each memref dimension must be an 389affine expression of loop induction variables and symbols. 390The optional stride arguments should be of 'index' type, and specify a 391stride for the slower memory space (memory space with a lower memory space 392id), transferring chunks of number_of_elements_per_stride every stride until 393%num_elements are transferred. Either both or no stride arguments should be 394specified. The value of 'num_elements' must be a multiple of 395'number_of_elements_per_stride'. 396 397 398Example: 399 400```mlir 401For example, a DmaStartOp operation that transfers 256 elements of a memref 402'%src' in memory space 0 at indices [%i + 3, %j] to memref '%dst' in memory 403space 1 at indices [%k + 7, %l], would be specified as follows: 404 405 %num_elements = constant 256 406 %idx = constant 0 : index 407 %tag = alloc() : memref<1xi32, 4> 408 affine.dma_start %src[%i + 3, %j], %dst[%k + 7, %l], %tag[%idx], 409 %num_elements : 410 memref<40x128xf32, 0>, memref<2x1024xf32, 1>, memref<1xi32, 2> 411 412 If %stride and %num_elt_per_stride are specified, the DMA is expected to 413 transfer %num_elt_per_stride elements every %stride elements apart from 414 memory space 0 until %num_elements are transferred. 415 416 affine.dma_start %src[%i, %j], %dst[%k, %l], %tag[%idx], %num_elements, 417 %stride, %num_elt_per_stride : ... 418``` 419 420### 'affine.dma_wait' operation 421 422Syntax: 423 424``` 425operation ::= `affine.dma_Start` ssa-use `[` multi-dim-affine-map-of-ssa-ids `]`, `[` multi-dim-affine-map-of-ssa-ids `]`, `[` multi-dim-affine-map-of-ssa-ids `]`, ssa-use `:` memref-type 426``` 427 428The `affine.dma_start` op blocks until the completion of a DMA operation 429associated with the tag element '%tag[%index]'. %tag is a memref, and %index 430has to be an index with the same restrictions as any load/store index. 431In particular, index for each memref dimension must be an affine expression of 432loop induction variables and symbols. %num_elements is the number of elements 433associated with the DMA operation. For example: 434 435Example: 436 437```mlir 438affine.dma_start %src[%i, %j], %dst[%k, %l], %tag[%index], %num_elements : 439 memref<2048xf32, 0>, memref<256xf32, 1>, memref<1xi32, 2> 440... 441... 442affine.dma_wait %tag[%index], %num_elements : memref<1xi32, 2> 443``` 444