summaryrefslogtreecommitdiffstats
path: root/mlir/lib/Transforms/LoopFusion.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Drop AffineMap::Null and IntegerSet::NullNicolas Vasilache2019-03-291-8/+8
| | | | | | | | | | | | | | | | | | | | 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
* Wrap cl::opt flags within passes in a category with the pass name. This ↵River Riddle2019-03-291-2/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | improves the help output of tools like mlir-opt. Example: dma-generate options: -dma-fast-mem-capacity - Set fast memory space ... -dma-fast-mem-space=<uint> - Set fast memory space ... loop-fusion options: -fusion-compute-tolerance=<number> - Fractional increase in ... -fusion-maximal - Enables maximal loop fusion loop-tile options: -tile-size=<uint> - Use this tile size for ... loop-unroll options: -unroll-factor=<uint> - Use this unroll factor ... -unroll-full - Fully unroll loops -unroll-full-threshold=<uint> - Unroll all loops with ... -unroll-num-reps=<uint> - Unroll innermost loops ... loop-unroll-jam options: -unroll-jam-factor=<uint> - Use this unroll jam factor ... PiperOrigin-RevId: 231019363
* Update replaceAllMemRefUsesWith to generate single result affine_apply's forUday Bondhugula2019-03-291-12/+12
| | | | | | | | | | | index remapping - generate a sequence of single result affine_apply's for the index remapping (instead of one multi result affine_apply) - update dma-generate and loop-fusion test cases; while on this, change test cases to use single result affine apply ops - some fusion comment fix/cleanup PiperOrigin-RevId: 230985830
* Change the dependence check in the loop fusion pass to use the MLIR ↵MLIR Team2019-03-291-13/+32
| | | | | | instruction list ordering (instead of the dependence graph node id ordering). This breaks the overloading of dependence graph node ids as both edge endpoints and instruction list position. PiperOrigin-RevId: 230849232
* loop-fusion: debug info cleanupUday Bondhugula2019-03-291-27/+33
| | | | PiperOrigin-RevId: 230817383
* Migrate VectorOrTensorType/MemRefType shape api to use int64_t instead of int.River Riddle2019-03-291-1/+1
| | | | PiperOrigin-RevId: 230605756
* Fix single producer check in loop fusion pass.MLIR Team2019-03-291-3/+3
| | | | PiperOrigin-RevId: 230565482
* Update fusion cost model + some additional infrastructure and debug ↵Uday Bondhugula2019-03-291-42/+203
| | | | | | | | | | | | | information for -loop-fusion - update fusion cost model to fuse while tolerating a certain amount of redundant computation; add cl option -fusion-compute-tolerance evaluate memory footprint and intermediate memory reduction - emit debug info from -loop-fusion showing what was fused and why - introduce function to compute memory footprint for a loop nest - getMemRefRegion readability update - NFC PiperOrigin-RevId: 230541857
* Allocate private/local buffers for slices accurately during fusionUday Bondhugula2019-03-291-19/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | - 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
* Handle escaping memrefs in loop fusion pass:MLIR Team2019-03-291-5/+40
| | | | | | | *) Do not remove loop nests which write to memrefs which escape the function. *) Do not remove memrefs which escape the function (e.g. are used in the return instruction). PiperOrigin-RevId: 230398630
* Mark (void)indexRemap to please compiler for unused variable checkLei Zhang2019-03-291-0/+1
| | | | PiperOrigin-RevId: 229957023
* LoopFusion: Creates private MemRefs which are used only by operations in the ↵MLIR Team2019-03-291-38/+193
| | | | | | | | | | fused loop. *) Enables reduction of private memref size based on MemRef region accessed by fused slice. *) Enables maximal fusion by creating a private memref to break a fusion-preventing dependence. *) Adds maximal fusion flag to enable fusing as much as possible (though it still fuses the minimum cost computation slice). PiperOrigin-RevId: 229936698
* Some loop fusion code cleanup/simplification post cl/229575126Uday Bondhugula2019-03-291-33/+16
| | | | | | - enforce the assumptions better / in a simpler way PiperOrigin-RevId: 229612424
* LoopFusion improvements:MLIR Team2019-03-291-164/+244
| | | | | | | | *) Adds support for fusing into consumer loop nests with multiple loads from the same memref. *) Adds support for reducing slice loop trip count by projecting out destination loop IVs greater than destination loop depth. *) Removes dependence on src loop depth and simplifies cost model computation. PiperOrigin-RevId: 229575126
* Address documentation/readability related comments from cl/227252907 on memrefUday Bondhugula2019-03-291-7/+1
| | | | | | store forwarding - NFC. PiperOrigin-RevId: 229561933
* Minor code cleanup - NFC.Uday Bondhugula2019-03-291-4/+4
| | | | | | - readability changes PiperOrigin-RevId: 229443430
* LoopFusion: automate selection of source loop nest slice depth and ↵MLIR Team2019-03-291-22/+353
| | | | | | | | | | | | destination loop nest insertion depth based on a simple cost model (cost model can be extended/replaced at a later time). *) LoopFusion: Adds fusion cost function which compares the cost of the fused loop nest, with the cost of the two unfused loop nests to determine if it is profitable to fuse the candidate loop nests. The fusion cost function is run for various combinations for src/dst loop depths attempting find the minimum cost setting for src/dst loop depths which does not increase the computational cost when the loop nests are fused. Combinations of src/dst loop depth are evaluated attempting to maximize loop depth (i.e. take a bigger computation slice from the source loop nest, and insert it deeper in the destination loop nest for better locality). *) LoopFusion: Adds utility to compute op instance count for loop nests, sliced loop nests, and to compute the cost of a loop nest fused with another sliced loop nest. *) LoopFusion: canonicalizes slice bound AffineMaps (and updates related tests). *) Analysis::Utils: Splits getBackwardComputationSlice into two functions: one which calculates and returns the slice loop bounds for analysis by LoopFusion, and the other for insertion of the computation slice (ones fusion has calculated the min-cost src/dst loop depths). *) Test: Adds multiple unit tests to test the new functionality. PiperOrigin-RevId: 229219757
* Extend loop-fusion's slicing utility + other fixes / updatesUday Bondhugula2019-03-291-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | - refactor toAffineFromEq and the code surrounding it; refactor code into FlatAffineConstraints::getSliceBounds - add FlatAffineConstraints methods to detect identifiers as mod's and div's of other identifiers - add FlatAffineConstraints::getConstantLower/UpperBound - Address b/122118218 (don't assert on invalid fusion depths cmdline flags - instead, don't do anything; change cmdline flags src-loop-depth -> fusion-src-loop-depth - AffineExpr/Map print method update: don't fail on null instances (since we have a wrapper around a pointer, it's avoidable); rationale: dump/print methods should never fail if possible. - Update memref-dataflow-opt to add an optimization to avoid a unnecessary call to IsRangeOneToOne when it's trivially going to be true. - Add additional test cases to exercise the new support - update a few existing test cases since the maps are now generated uniformly with all destination loop operands appearing for the backward slice - Fix projectOut - fix wrong range for getBestElimCandidate. - Fix for getConstantBoundOnDimSize() - didn't show up in any test cases since we didn't have any non-hyperrectangular ones. PiperOrigin-RevId: 228265152
* Misc readability and doc / code comment related improvements - NFCUday Bondhugula2019-03-291-6/+3
| | | | | | | | | | | | | | | | | | - when SSAValue/MLValue existed, code at several places was forced to create additional aggregate temporaries of SmallVector<SSAValue/MLValue> to handle the conversion; get rid of such redundant code - use filling ctors instead of explicit loops - for smallvectors, change insert(list.end(), ...) -> append(... - improve comments at various places - turn getMemRefAccess into MemRefAccess ctor and drop duplicated getMemRefAccess. In the next CL, provide getAccess() accessors for load, store, DMA op's to return a MemRefAccess. PiperOrigin-RevId: 228243638
* Update and generalize various passes to work on both CFG and ML functions,Chris Lattner2019-03-291-2/+2
| | | | | | | | | | | | | simplifying them in minor ways. The only significant cleanup here is the constant folding pass. All the other changes are simple and easy, but this is still enough to shrink the compiler by 45LOC. The one pass left to merge is the CSE pass, which will be move involved, so I'm splitting it out to its own patch (which I'll tackle right after this). This is step 28/n towards merging instructions and statements. PiperOrigin-RevId: 227328115
* Introduce memref store to load forwarding - a simple memref dataflow analysisUday Bondhugula2019-03-291-39/+4
| | | | | | | | | | | | | | | | | - the load/store forwarding relies on memref dependence routines as well as SSA/dominance to identify the memref store instance uniquely supplying a value to a memref load, and replaces the result of that load with the value being stored. The memref is also deleted when possible if only stores remain. - add methods for post dominance for MLFunction blocks. - remove duplicated getLoopDepth/getNestingDepth - move getNestingDepth, getMemRefAccess, getNumCommonSurroundingLoops into Analysis/Utils (were earlier static) - add a helper method in FlatAffineConstraints - isRangeOneToOne. PiperOrigin-RevId: 227252907
* Extend InstVisitor and Walker to handle arbitrary CFG functions, expand theChris Lattner2019-03-291-1/+6
| | | | | | | | | | | 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-90/+90
| | | | | | | | | 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-1/+1
| | | | | | | | | | | 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-7/+7
| | | | | | | | 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-14/+14
| | | | | | | | OperationInst. This is a big mechanical patch. This is step 16/n towards merging instructions and statements, NFC. PiperOrigin-RevId: 227093712
* Merge SSAValue, CFGValue, and MLValue together into a single Value class, whichChris Lattner2019-03-291-20/+19
| | | | | | | | | 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
* 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
* Computation slice update: adds parameters to insertBackwardComputationSlice ↵MLIR Team2019-03-291-1/+35
| | | | | | | | which specify the source loop nest depth at which to perform iteration space slicing, and the destination loop nest depth at which to insert the compution slice. Updates LoopFusion pass to take these parameters as command line flags for experimentation. PiperOrigin-RevId: 226514297
* Improve loop fusion algorithm by using a memref dependence graph.MLIR Team2019-03-291-252/+342
| | | | | | Fixed TODO for reduction fusion unit test. PiperOrigin-RevId: 226277226
* Loop Fusion pass update: introduce utilities to perform generalized loop ↵MLIR Team2019-03-291-157/+340
| | | | | | | | | | | | fusion based on slicing; encompasses standard loop fusion. *) Adds simple greedy fusion algorithm to drive experimentation. This algorithm greedily fuses loop nests with single-writer/single-reader memref dependences to improve locality. *) Adds support for fusing slices of a loop nest computation: fusing one loop nest into another by adjusting the source loop nest's iteration bounds (after it is fused into the destination loop nest). This is accomplished by solving for the source loop nest's IVs in terms of the destination loop nests IVs and symbols using the dependece polyhedron, then creating AffineMaps of these functions for the loop bounds of the fused source loop. *) Adds utility function 'insertMemRefComputationSlice' which computes and inserts computation slice from loop nest surrounding a source memref access into the loop nest surrounding the destingation memref access. *) Adds FlatAffineConstraints::toAffineMap function which returns and AffineMap which represents an equality contraint where one dimension identifier is represented as a function of all others in the equality constraint. *) Adds multiple fusion unit tests. PiperOrigin-RevId: 225842944
* Adds support for returning the direction of the dependence between memref ↵MLIR Team2019-03-291-2/+6
| | | | | | | | | | accesses (distance/direction vectors). Updates MemRefDependenceCheck to check and report on all memref access pairs at all loop nest depths. Updates old and adds new memref dependence check tests. Resolves multiple TODOs. PiperOrigin-RevId: 220816515
* Initialize Pass with PassID.Jacques Pienaar2019-03-291-1/+1
| | | | | | The passID is not currently stored in Pass but this avoids the unused variable warning. The passID is used to uniquely identify passes, currently this is only stored/used in PassInfo. PiperOrigin-RevId: 220485662
* Add static pass registrationJacques Pienaar2019-03-291-0/+5
| | | | | | | | Add static pass registration and change mlir-opt to use it. Future work is needed to refactor the registration for PassManager usage. Change build targets to alwayslink to enforce registration. PiperOrigin-RevId: 220390178
* Adds a dependence check to test whether two accesses to the same memref ↵MLIR Team2019-03-291-0/+244
access the same element. - Builds access functions and iterations domains for each access. - Builds dependence polyhedron constraint system which has equality constraints for equated access functions and inequality constraints for iteration domain loop bounds. - Runs elimination on the dependence polyhedron to test if no dependence exists between the accesses. - Adds a trivial LoopFusion transformation pass with a simple test policy to test dependence between accesses to the same memref in adjacent loops. - The LoopFusion pass will be extended in subsequent CLs. PiperOrigin-RevId: 219630898
OpenPOWER on IntegriCloud