summaryrefslogtreecommitdiffstats
path: root/mlir/lib/Transforms/Utils/LoopUtils.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Introduce affine terminatorAlex Zinenko2019-03-291-40/+48
| | | | | | | | | | | | | | | | | | | | | | Due to legacy reasons (ML/CFG function separation), regions in affine control flow operations require contained blocks not to have terminators. This is inconsistent with the notion of the block and may complicate code motion between regions of affine control operations and other regions. Introduce `affine.terminator`, a special terminator operation that must be used to terminate blocks inside affine operations and transfers the control back to he region enclosing the affine operation. For brevity and readability reasons, allow `affine.for` and `affine.if` to omit the `affine.terminator` in their regions when using custom printing and parsing format. The custom parser injects the `affine.terminator` if it is missing so as to always have it present in constructed operations. Update transformations to account for the presence of terminator. In particular, most code motion transformation between loops should leave the terminator in place, and code motion between loops and non-affine blocks should drop the terminator. PiperOrigin-RevId: 240536998
* Replace usages of Instruction with Operation in the /IR directory.River Riddle2019-03-291-19/+19
| | | | | | This is step 2/N to renaming Instruction to Operation. PiperOrigin-RevId: 240459216
* Rename the Instruction class to Operation. This just renames the class, ↵River Riddle2019-03-291-1/+1
| | | | | | | | usages of Instruction will still refer to a typedef in the interim. This is step 1/N to renaming Instruction to Operation. PiperOrigin-RevId: 240431520
* Replace usages of "operator->" with "." for the AffineOps.River Riddle2019-03-291-76/+76
| | | | | Note: The "operator->" method is a temporary helper for the de-const transition and is gradually being phased out. PiperOrigin-RevId: 240179439
* NFC: Rename the 'for' operation in the AffineOps dialect to 'affine.for' and ↵River Riddle2019-03-291-9/+9
| | | | | | set the namespace of the AffineOps dialect to 'affine'. PiperOrigin-RevId: 240165792
* Remove OpPointer, cleaning up a ton of code. This also moves Ops to usingChris Lattner2019-03-291-47/+37
| | | | | | | | | inherited constructors, which is cleaner and means you can now use DimOp() to get a null op, instead of having to use Instruction::getNull<DimOp>(). This removes another 200 lines of code. PiperOrigin-RevId: 240068113
* Push a bunch of 'consts' out of the *Op structure, in prep for removingChris Lattner2019-03-291-1/+1
| | | | | | OpPointer. PiperOrigin-RevId: 240044712
* Improve comment for `augmentMapAndBounds`Nicolas Vasilache2019-03-291-2/+6
| | | | | | Followup from a previous CL. PiperOrigin-RevId: 239591775
* Move to new `const` model, part 1: remove ConstOpPointer.Chris Lattner2019-03-291-1/+1
| | | | | | | | This eliminate ConstOpPointer (but keeps OpPointer for now) by making OpPointer implicitly launder const in a const incorrect way. It will eventually go away entirely, this is a progressive step towards the new const model. PiperOrigin-RevId: 239512640
* Properly propagate induction variable in tilingNicolas Vasilache2019-03-291-16/+47
| | | | | | | This CL fixes an issue where cloned loop induction variables were not properly propagated and beefs up the corresponding test. PiperOrigin-RevId: 239422961
* Extend loop unrolling and unroll-jamming to non-matching bound operands andUday Bondhugula2019-03-291-67/+82
| | | | | | | | | | | | | | | | | | | | | multi-result upper bounds, complete TODOs, fix/improve test cases. - complete TODOs for loop unroll/unroll-and-jam. Something as simple as "for %i = 0 to %N" wasn't being unrolled earlier (unless it had been written as "for %i = ()[s0] -> (0)()[%N] to %N"; addressed now. - update/replace getTripCountExpr with buildTripCountMapAndOperands; makes it more powerful as it composes inputs into it - getCleanupLowerBound and getUnrolledLoopUpperBound actually needed the same code; refactor and remove one. - reorganize test cases, write previous ones better; most of these changes are "label replacements". - fix wrongly labeled test cases in unroll-jam.mlir PiperOrigin-RevId: 238014653
* Move the success/failure functions out of LogicalResult and into the mlir ↵River Riddle2019-03-291-13/+13
| | | | | | namespace. PiperOrigin-RevId: 237712180
* Rename Status to LogicalResult to avoid conflictions with the Status in ↵River Riddle2019-03-291-22/+22
| | | | | | xla/tensorflow/etc. PiperOrigin-RevId: 237537341
* Move UtilResult into the Support directory and rename it to Status. Status ↵River Riddle2019-03-291-26/+25
| | | | | | | | | | | | provides an unambiguous way to specify success/failure results. These can be generated by 'Status::success()' and Status::failure()'. Status provides no implicit conversion to bool and should be consumed by one of the following utility functions: * bool succeeded(Status) - Return if the status corresponds to a success value. * bool failed(Status) - Return if the status corresponds to a failure value. PiperOrigin-RevId: 237153884
* Fix lower/upper bound mismatch in stripmineSinkNicolas Vasilache2019-03-291-1/+1
| | | | | | Also beef up the corresponding test case. PiperOrigin-RevId: 236878818
* NFC. Move all of the remaining operations left in BuiltinOps to StandardOps. ↵River Riddle2019-03-291-1/+0
| | | | | | The only thing left in BuiltinOps are the core MLIR types. The standard types can't be moved because they are referenced within the IR directory, e.g. in things like Builder. PiperOrigin-RevId: 236403665
* Use consistent names for dialect op source filesLei Zhang2019-03-291-1/+1
| | | | | | | | | | | | | | | This CL changes dialect op source files (.h, .cpp, .td) to follow the following convention: <full-dialect-name>/<dialect-namespace>Ops.{h|cpp|td} Builtin and standard dialects are specially treated, though. Both of them do not have dialect namespace; the former is still named as BuiltinOps.* and the latter is named as Ops.*. Purely mechanical. NFC. PiperOrigin-RevId: 236371358
* Change some of the debug messages to use emitError / emitWarning / emitNote ↵Uday Bondhugula2019-03-291-2/+2
| | | | | | - NFC PiperOrigin-RevId: 236169676
* Add a stripmineSink and imperfectly nested tiling primitives.Nicolas Vasilache2019-03-291-0/+95
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This CL adds a primitive to perform stripmining of a loop by a given factor and sinking it under multiple target loops. In turn this is used to implement imperfectly nested loop tiling (with interchange) by repeatedly calling the stripmineSink primitive. The API returns the point loops and allows repeated invocations of tiling to achieve declarative, multi-level, imperfectly-nested tiling. Note that this CL is only concerned with the mechanical aspects and does not worry about analysis and legality. The API is demonstrated in an example which creates an EDSC block, emits the corresponding MLIR and applies imperfectly-nested tiling: ```cpp auto block = edsc::block({ For(ArrayRef<edsc::Expr>{i, j}, {zero, zero}, {M, N}, {one, one}, { For(k1, zero, O, one, { C({i, j, k1}) = A({i, j, k1}) + B({i, j, k1}) }), For(k2, zero, O, one, { C({i, j, k2}) = A({i, j, k2}) + B({i, j, k2}) }), }), }); // clang-format on emitter.emitStmts(block.getBody()); auto l_i = emitter.getAffineForOp(i), l_j = emitter.getAffineForOp(j), l_k1 = emitter.getAffineForOp(k1), l_k2 = emitter.getAffineForOp(k2); auto indicesL1 = mlir::tile({l_i, l_j}, {512, 1024}, {l_k1, l_k2}); auto l_ii1 = indicesL1[0][0], l_jj1 = indicesL1[1][0]; mlir::tile({l_jj1, l_ii1}, {32, 16}, l_jj1); ``` The edsc::Expr for the induction variables (i, j, k_1, k_2) provide the programmatic hooks from which tiling can be applied declaratively. PiperOrigin-RevId: 235548228
* Refactor AffineExprFlattener and move FlatAffineConstraints out of IR intoUday Bondhugula2019-03-291-1/+1
| | | | | | | | | | | | | | | | | Analysis - NFC - refactor AffineExprFlattener (-> SimpleAffineExprFlattener) so that it doesn't depend on FlatAffineConstraints, and so that FlatAffineConstraints could be moved out of IR/; the simplification that the IR needs for AffineExpr's doesn't depend on FlatAffineConstraints - have AffineExprFlattener derive from SimpleAffineExprFlattener to use for all Analysis/Transforms purposes; override addLocalFloorDivId in the derived class - turn addAffineForOpDomain into a method on FlatAffineConstraints - turn AffineForOp::getAsValueMap into an AffineValueMap ctor PiperOrigin-RevId: 235283610
* LoopFusion: perform a series of loop interchanges to increase the loop depth ↵MLIR Team2019-03-291-0/+34
| | | | | | | | | | | | | | at which slices of producer loop nests can be fused into constumer loop nests. *) Adds utility to LoopUtils to perform loop interchange of two AffineForOps. *) Adds utility to LoopUtils to sink a loop to a specified depth within a loop nest, using a series of loop interchanges. *) Computes dependences between all loads and stores in the loop nest, and classifies each loop as parallel or sequential. *) Computes loop interchange permutation required to sink sequential loops (and raise parallel loop nests) while preserving relative order among them. *) Checks each dependence against the permutation to make sure that dependences would not be violated by the loop interchange transformation. *) Calls loop interchange in LoopFusion pass on consumer loop nests before fusing in producers, sinking loops with loop carried dependences deeper into the consumer loop nest. *) Adds and updates related unit tests. PiperOrigin-RevId: 234158370
* Automated rollback of changelist 232717775.Uday Bondhugula2019-03-291-7/+7
| | | | PiperOrigin-RevId: 232807986
* NFC: Rename the 'for' operation in the AffineOps dialect to 'affine.for'. ↵River Riddle2019-03-291-7/+7
| | | | | | The is the second step to adding a namespace to the AffineOps dialect. PiperOrigin-RevId: 232717775
* NFC: Rename affine_apply to affine.apply. This is the first step to adding a ↵River Riddle2019-03-291-1/+1
| | | | | | namespace to the affine dialect. PiperOrigin-RevId: 232707862
* Remove InstWalker and move all instruction walking to the api facilities on ↵River Riddle2019-03-291-5/+2
| | | | | | Function/Block/Instruction. PiperOrigin-RevId: 232388113
* Remove remaining usages of OperationInst in lib/Transforms.River Riddle2019-03-291-5/+4
| | | | PiperOrigin-RevId: 232323671
* Replace the walkOps/visitOperationInst variants from the InstWalkers with ↵River Riddle2019-03-291-1/+1
| | | | | | the Instruction variants. PiperOrigin-RevId: 232322030
* Fold the functionality of OperationInst into Instruction. OperationInst ↵River Riddle2019-03-291-1/+1
| | | | | | still exists as a forward declaration and will be removed incrementally in a set of followup cleanup patches. PiperOrigin-RevId: 232198540
* Define the AffineForOp and replace ForInst with it. This patch is largely ↵River Riddle2019-03-291-81/+89
| | | | | | mechanical, i.e. changing usages of ForInst to OpPointer<AffineForOp>. An important difference is that upon construction an AffineForOp no longer automatically creates the body and induction variable. To generate the body/iv, 'createBody' can be called on an AffineForOp with no body. PiperOrigin-RevId: 232060516
* Change AffineApplyOp to produce a single result, simplifying the code thatChris Lattner2019-03-291-10/+8
| | | | | | works with it, and updating the g3docs. PiperOrigin-RevId: 231120927
* Change the ForInst induction variable to be a block argument of the body ↵River Riddle2019-03-291-11/+15
| | | | | | instead of the ForInst itself. This is a necessary step in converting ForInst into an operation. PiperOrigin-RevId: 231064139
* Drop AffineMap::Null and IntegerSet::NullNicolas Vasilache2019-03-291-4/+4
| | | | | | | | | | | | | | | | | | | | Addresses b/122486036 This CL addresses some leftover crumbs in AffineMap and IntegerSet by removing the Null method and cleaning up the constructors. As the ::Null uses were tracked down, opportunities appeared to untangle some of the Parsing logic and make it explicit where AffineMap/IntegerSet have ambiguous syntax. Previously, ambiguous cases were hidden behind the implicit pointer values of AffineMap* and IntegerSet* that were passed as function parameters. Depending the values of those pointers one of 3 behaviors could occur. This parsing logic convolution is one of the rare cases where I would advocate for code duplication. The more proper fix would be to make the syntax unambiguous or to allow some lookahead. PiperOrigin-RevId: 231058512
* Add cloning functionality to Block and Function, this also adds support for ↵River Riddle2019-03-291-7/+7
| | | | | | remapping successor block operands of terminator operations. We define a new BlockAndValueMapping class to simplify mapping between cloned values. PiperOrigin-RevId: 230768759
* loop unroll update: unroll factor one for a single iteration loopUday Bondhugula2019-03-291-1/+4
| | | | | | | | - unrolling a single iteration loop by a factor of one should promote its body into its parent; this makes it consistent with the behavior/expectation that unrolling a loop by a factor equal to its trip count makes the loop go away. PiperOrigin-RevId: 230426499
* Allocate private/local buffers for slices accurately during fusionUday Bondhugula2019-03-291-3/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | - the size of the private memref created for the slice should be based on the memref region accessed at the depth at which the slice is being materialized, i.e., symbolic in the outer IVs up until that depth, as opposed to the region accessed based on the entire domain. - leads to a significant contraction of the temporary / intermediate memref whenever the memref isn't reduced to a single scalar (through store fwd'ing). Other changes - update to promoteIfSingleIteration - avoid introducing unnecessary identity map affine_apply from IV; makes it much easier to write and read test cases and pass output for all passes that use promoteIfSingleIteration; loop-fusion test cases become much simpler - fix replaceAllMemrefUsesWith bug that was exposed by the above update - 'domInstFilter' could be one of the ops erased due to a memref replacement in it. - fix getConstantBoundOnDimSize bug: a division by the coefficient of the identifier was missing (the latter need not always be 1); add lbFloorDivisors output argument - rename getBoundingConstantSizeAndShape -> getConstantBoundingSizeAndShape PiperOrigin-RevId: 230405218
* Extend InstVisitor and Walker to handle arbitrary CFG functions, expand theChris Lattner2019-03-291-1/+1
| | | | | | | | | | | Function::walk functionality into f->walkInsts/Ops which allows visiting all instructions, not just ops. Eliminate Function::getBody() and Function::getReturn() helpers which crash in CFG functions, and were only kept around as a bridge. This is step 25/n towards merging instructions and statements. PiperOrigin-RevId: 227243966
* Standardize naming of statements -> instructions, revisting the code base to beChris Lattner2019-03-291-144/+144
| | | | | | | | | consistent and moving the using declarations over. Hopefully this is the last truly massive patch in this refactoring. This is step 21/n towards merging instructions and statements, NFC. PiperOrigin-RevId: 227178245
* Rename BasicBlock and StmtBlock to Block, and make a pass cleaning it up. I ↵Chris Lattner2019-03-291-7/+7
| | | | | | | | | | | did not make an effort to rename all of the 'bb' names in the codebase, since they are still correct and any specific missed once can be fixed up on demand. The last major renaming is Statement -> Instruction, which is why Statement and Stmt still appears in various places. This is step 19/n towards merging instructions and statements, NFC. PiperOrigin-RevId: 227163082
* Eliminate the using decls for MLFunction and CFGFunction standardizing onChris Lattner2019-03-291-4/+4
| | | | | | | | Function. This is step 18/n towards merging instructions and statements, NFC. PiperOrigin-RevId: 227139399
* Merge Operation into OperationInst and standardize nomenclature aroundChris Lattner2019-03-291-1/+1
| | | | | | | | OperationInst. This is a big mechanical patch. This is step 16/n towards merging instructions and statements, NFC. PiperOrigin-RevId: 227093712
* Merge CFGFuncBuilder/MLFuncBuilder/FuncBuilder together into a single newChris Lattner2019-03-291-9/+9
| | | | | | | | FuncBuilder class. Also rename SSAValue.cpp to Value.cpp This is step 12/n towards merging instructions and statements, NFC. PiperOrigin-RevId: 227067644
* Merge SSAValue, CFGValue, and MLValue together into a single Value class, whichChris Lattner2019-03-291-9/+7
| | | | | | | | | is the new base of the SSA value hierarchy. This CL also standardizes all the nomenclature and comments to use 'Value' where appropriate. This also eliminates a large number of cast<MLValue>(x)'s, which is very soothing. This is step 11/n towards merging instructions and statements, NFC. PiperOrigin-RevId: 227064624
* Rename findFunction from the ML side of the house to be named getFunction(),Chris Lattner2019-03-291-1/+1
| | | | | | | | | | | | making it more similar to the CFG side of things. It is true that in a deeply nested case that this is not a guaranteed O(1) time operation, and that 'get' could lead compiler hackers to think this is cheap, but we need to merge these and we can look into solutions for this in the future if it becomes a problem in practice. This is step 9/n towards merging instructions and statements, NFC. PiperOrigin-RevId: 226983931
* Refactor MLFunction to contain a StmtBlock for its body instead of inheritingChris Lattner2019-03-291-1/+1
| | | | | | | | | | from it. This is necessary progress to squaring away the parent relationship that a StmtBlock has with its enclosing if/for/fn, and makes room for functions to have more than one block in the future. This also removes IfClause and ForStmtBody. This is step 5/n towards merging instructions and statements, NFC. PiperOrigin-RevId: 226936541
* Refactor ForStmt: having it contain a StmtBlock instead of subclassingChris Lattner2019-03-291-9/+10
| | | | | | | | | | | | | | StmtBlock. This is more consistent with IfStmt and also conceptually makes more sense - a forstmt "isn't" its body, it contains its body. This is step 1/N towards merging BasicBlock and StmtBlock. This is required because in the new regime StmtBlock will have a use list (just like BasicBlock does) of operands, and ForStmt already has a use list for its induction variable. This is a mechanical patch, NFC. PiperOrigin-RevId: 226684158
* Update/Fix LoopUtils::stmtBodySkew to handle loop step.Uday Bondhugula2019-03-291-56/+64
| | | | | | | | | | | - loop step wasn't handled and there wasn't a TODO or an assertion; fix this. - rename 'delay' to shift for consistency/readability. - other readability changes. - remove duplicate attribute print for DmaStartOp; fix misplaced attribute print for DmaWaitOp - add build method for AddFOp (unrelated to this CL, but add it anyway) PiperOrigin-RevId: 224892958
* Move definitions of lopoUnroll* functions to LoopUtils.cpp.Alex Zinenko2019-03-291-0/+117
| | | | | | | | | | | These functions are declared in Transforms/LoopUtils.h (included to the Transforms/Utils library) but were defined in the loop unrolling pass in Transforms/LoopUnroll.cpp. As a result, targets depending only on TransformUtils library but not on Transforms could get link errors. Move the definitions to Transforms/Utils/LoopUtils.cpp where they should actually live. This does not modify any code. PiperOrigin-RevId: 221508882
* [MLIR] Make upper bound implementation exclusiveNicolas Vasilache2019-03-291-10/+10
| | | | | | | This CL implement exclusive upper bound behavior as per b/116854378. A followup CL will update the semantics of the for loop. PiperOrigin-RevId: 220448963
* Move transform utilities out to their own TransformUtils library, instead ofChris Lattner2019-03-291-0/+316
just having the pattern matcher in its own library. At this point, lib/Transforms/*.cpp are all actually passes themselves (and will probably eventually be themselves move to a new subdirectory as we accrete more). PiperOrigin-RevId: 218745193
OpenPOWER on IntegriCloud