summaryrefslogtreecommitdiffstats
path: root/mlir/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* NFC: Rename affine_apply to affine.apply. This is the first step to adding a ↵River Riddle2019-03-291-2/+2
| | | | | | namespace to the affine dialect. PiperOrigin-RevId: 232707862
* Adds the ability to compute the MemRefRegion of a sliced loop nest. Utilizes ↵MLIR Team2019-03-291-37/+77
| | | | | | | | | this feature during loop fusion cost computation, to compute what the write region of a fusion candidate loop nest slice would be (without having to materialize the slice or change the IR). *) Adds parameter to public API of MemRefRegion::compute for passing in the slice loop bounds to compute the memref region of the loop nest slice. *) Exposes public method MemRefRegion::getRegionSize for computing the size of the memref region in bytes. PiperOrigin-RevId: 232706165
* Remove findInstPositionInBlock from the Block api.River Riddle2019-03-292-9/+21
| | | | PiperOrigin-RevId: 232704766
* Refactor the affine analysis by moving some functionality to IR and some to ↵River Riddle2019-03-296-2836/+9
| | | | | | | | | | | | | | AffineOps. This is important for allowing the affine dialect to define canonicalizations directly on the operations instead of relying on transformation passes, e.g. ComposeAffineMaps. A summary of the refactoring: * AffineStructures has moved to IR. * simplifyAffineExpr/simplifyAffineMap/getFlattenedAffineExpr have moved to IR. * makeComposedAffineApply/fullyComposeAffineMapAndOperands have moved to AffineOps. * ComposeAffineMaps is replaced by AffineApplyOp::canonicalize and deleted. PiperOrigin-RevId: 232586468
* Remove InstWalker and move all instruction walking to the api facilities on ↵River Riddle2019-03-293-34/+23
| | | | | | Function/Block/Instruction. PiperOrigin-RevId: 232388113
* NFC: Move AffineApplyOp to the AffineOps dialect. This also moves the ↵River Riddle2019-03-293-5/+5
| | | | | | isValidDim/isValidSymbol methods from Value to the AffineOps dialect. PiperOrigin-RevId: 232386632
* Refactor common code getting memref access in getMemRefRegion - NFCUday Bondhugula2019-03-292-66/+52
| | | | | | | | | | | | | | | - use getAccessMap() instead of repeating it - fold getMemRefRegion into MemRefRegion ctor (more natural, avoid heap allocation and unique_ptr where possible) - change extractForInductionVars - MutableArrayRef -> ArrayRef for the arguments. Since the method is just returning copies of 'Value *', the client can't mutate the pointers themselves; it's fine to mutate the 'Value''s themselves, but that doesn't mutate the pointers to those. - change the way extractForInductionVars returns (see b/123437690) PiperOrigin-RevId: 232359277
* Update MemRefAccess::getAccessMap to always canonicalize map + operandsUday Bondhugula2019-03-291-0/+1
| | | | | | | | | | - with this we won't see duplicate / unused operands when getting access maps, or when constructing FlatAffineConstraints based on such maps - we can probably change fullyComposeAffineMapAndOperands to ensure this TODO(b/123879896). PiperOrigin-RevId: 232356600
* Replace the walkOps/visitOperationInst variants from the InstWalkers with ↵River Riddle2019-03-291-1/+1
| | | | | | the Instruction variants. PiperOrigin-RevId: 232322030
* Update dma-generate pass to (1) work on blocks of instructions (instead of justUday Bondhugula2019-03-292-22/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | loops), (2) take into account fast memory space capacity and lower 'dmaDepth' to fit, (3) add location information for debug info / errors - change dma-generate pass to work on blocks of instructions (start/end iterators) instead of 'for' loops; complete TODOs - allows DMA generation for straightline blocks of operation instructions interspersed b/w loops - take into account fast memory capacity: check whether memory footprint fits in fastMemoryCapacity parameter, and recurse/lower the depth at which DMA generation is performed until it does fit in the provided memory - add location information to MemRefRegion; any insufficient fast memory capacity errors or debug info w.r.t dma generation shows location information - allow DMA generation pass to be instantiated with a fast memory capacity option (besides command line flag) - change getMemRefRegion to return unique_ptr's - change getMemRefFootprintBytes to work on a 'Block' instead of 'ForInst' - other helper methods; add postDomInstFilter option for replaceAllMemRefUsesWith; drop forInst->walkOps, add Block::walkOps methods Eg. output $ mlir-opt -dma-generate -dma-fast-mem-capacity=1 /tmp/single.mlir /tmp/single.mlir:9:13: error: Total size of all DMA buffers' for this block exceeds fast memory capacity for %i3 = (d0) -> (d0)(%i1) to (d0) -> (d0 + 32)(%i1) { ^ $ mlir-opt -debug-only=dma-generate -dma-generate -dma-fast-mem-capacity=400 /tmp/single.mlir /tmp/single.mlir:9:13: note: 8 KiB of DMA buffers in fast memory space for this block for %i3 = (d0) -> (d0)(%i1) to (d0) -> (d0 + 32)(%i1) { PiperOrigin-RevId: 232297044
* Begin the process of fully removing OperationInst. This patch cleans up ↵River Riddle2019-03-2910-135/+96
| | | | | | references to OperationInst in the /include, /AffineOps, and lib/Analysis. PiperOrigin-RevId: 232199262
* Fold the functionality of OperationInst into Instruction. OperationInst ↵River Riddle2019-03-298-8/+8
| | | | | | 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-298-142/+158
| | | | | | 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
* Post commit fixesNicolas Vasilache2019-03-291-4/+6
| | | | | | | | | | | | This CL introduces a hotfix post refactoring of NestedMatchers: - fix uninitialized read to skip - avoid bumpptr allocating with 0 elements Interestingly the latter issue only surfaced in fastbuild mode with no-san and manifested itself by a SIGILL. All other combinations that were tried failed to reproduce the issue (dbg, opt, fastbuild with asan) PiperOrigin-RevId: 231787642
* Address Performance issue in NestedMatcherNicolas Vasilache2019-03-292-121/+51
| | | | | | | | | | | | | | | | | | | | | | A performance issue was reported due to the usage of NestedMatcher in ComposeAffineMaps. The main culprit was the ubiquitous copies that were occuring when appending even a single element in `matchOne`. This CL generally simplifies the implementation and removes one level of indirection by getting rid of auxiliary storage as well as simplifying the API. The users of the API are updated accordingly. The implementation was tested on a heavily unrolled example with ComposeAffineMaps and is now close in performance with an implementation based on stateless InstWalker. As a reminder, the whole ComposeAffineMaps pass is slated to disappear but the bug report was very useful as a stress test for NestedMatchers. Lastly, the following cleanups reported by @aminim were addressed: 1. make NestedPatternContext scoped within runFunction rather than at the Pass level. This was caused by a previous misunderstanding of Pass lifetime; 2. use defensive assertions in the constructor of NestedPatternContext to make it clear a unique such locally scoped context is allowed to exist. PiperOrigin-RevId: 231781279
* Fix getFullMemRefAsRegion() and FlatAffineConstraints::resetUday Bondhugula2019-03-291-3/+7
| | | | PiperOrigin-RevId: 231426734
* Recommit: Define a AffineOps dialect as well as an AffineIfOp operation. ↵River Riddle2019-03-294-44/+34
| | | | | | Replace all instances of IfInst with AffineIfOp and delete IfInst. PiperOrigin-RevId: 231342063
* Automated rollback of changelist 231318632.Nicolas Vasilache2019-03-294-34/+44
| | | | PiperOrigin-RevId: 231327161
* Define a AffineOps dialect as well as an AffineIfOp operation. Replace all ↵River Riddle2019-03-294-44/+34
| | | | | | instances of IfInst with AffineIfOp and delete IfInst. PiperOrigin-RevId: 231318632
* Change AffineApplyOp to produce a single result, simplifying the code thatChris Lattner2019-03-293-26/+3
| | | | | | 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-297-25/+25
| | | | | | 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-292-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
* Cleanup resource management and rename recursive matchersNicolas Vasilache2019-03-293-264/+241
| | | | | | | | | | | | | | | This CL follows up on a memory leak issue related to SmallVector growth that escapes the BumpPtrAllocator. The fix is to properly use ArrayRef and placement new to define away the issue. The following renaming is also applied: 1. MLFunctionMatcher -> NestedPattern 2. MLFunctionMatches -> NestedMatch As a consequence all allocations are now guaranteed to live on the BumpPtrAllocator. PiperOrigin-RevId: 231047766
* Allow operations to hold a blocklist and add support for parsing/printing a ↵River Riddle2019-03-292-7/+41
| | | | | | block list for verbose printing. PiperOrigin-RevId: 230951462
* Update dma-generate: update for multiple load/store op's per memrefUday Bondhugula2019-03-292-2/+120
| | | | | | | | | | - introduce a way to compute union using symbolic rectangular bounding boxes - handle multiple load/store op's to the same memref by taking a union of the regions - command-line argument to provide capacity of the fast memory space - minor change to replaceAllMemRefUsesWith to not generate affine_apply if the supplied index remap was identity PiperOrigin-RevId: 230848185
* Add order bit to instructions to lazily track dominance queries. This ↵River Riddle2019-03-291-50/+6
| | | | | | | | improves the performance of dominance queries, which are used quite often within the compiler(especially within the verifier). This reduced the execution time of a few internal tests from ~2 minutes to ~4 seconds. PiperOrigin-RevId: 230819723
* Add cloning functionality to Block and Function, this also adds support for ↵River Riddle2019-03-291-2/+1
| | | | | | remapping successor block operands of terminator operations. We define a new BlockAndValueMapping class to simplify mapping between cloned values. PiperOrigin-RevId: 230768759
* Migrate VectorOrTensorType/MemRefType shape api to use int64_t instead of int.River Riddle2019-03-292-6/+6
| | | | PiperOrigin-RevId: 230605756
* Update fusion cost model + some additional infrastructure and debug ↵Uday Bondhugula2019-03-292-15/+103
| | | | | | | | | | | | | 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
* Improve / fix documentation for affine map composition utilities - NFCUday Bondhugula2019-03-291-8/+0
| | | | | | | | | - improve/fix doc comments for affine apply composition related methods. - drop makeSingleValueComposedAffineApply - really redundant and out of line in a public API; it's just returning the first result of the composed affine apply op, and not making a single result affine map or an affine_apply op. PiperOrigin-RevId: 230406169
* Allocate private/local buffers for slices accurately during fusionUday Bondhugula2019-03-293-9/+29
| | | | | | | | | | | | | | | | | | | | | | | | | | | | - 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
* Fix FlatAffineConstraints::removeIdRangeUday Bondhugula2019-03-291-3/+21
| | | | | | | - the number of symbols/local ids was being incorrectly updated; the code in cl/230112574 exposes this. PiperOrigin-RevId: 230358327
* Rewrite OpStats to use llvm formatting utilities.River Riddle2019-03-291-29/+25
| | | | | | | | | | | | | | | | | | | Example Output: Operations encountered: ----------------------- addf , 11 constant , 4 return , 19 some_op , 1 tf.AvgPool , 3 tf.DepthwiseConv2dNative , 3 tf.FusedBatchNorm , 2 tfl.add , 7 tfl.average_pool_2d , 1 tfl.leaky_relu , 1 PiperOrigin-RevId: 229937190
* Fix AffineApply corner caseNicolas Vasilache2019-03-291-26/+33
| | | | | | | | | | | | | This CL adds a test reported by andydavis@ and fixes the corner case that appears when operands do not come from an AffineApply and no Dim composition is needed. In such cases, we would need to create an empty map which is disallowed. The composition in such cases becomes trivial: there is no composition. This CL also updates the name AffineNormalizer to AffineApplyNormalizer. PiperOrigin-RevId: 229819234
* LoopFusion improvements:MLIR Team2019-03-292-27/+46
| | | | | | | | *) 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
* Minor code cleanup - NFC.Uday Bondhugula2019-03-292-7/+9
| | | | | | - readability changes PiperOrigin-RevId: 229443430
* Fix outdated commentsUday Bondhugula2019-03-291-1/+1
| | | | PiperOrigin-RevId: 229300301
* LoopFusion: automate selection of source loop nest slice depth and ↵MLIR Team2019-03-291-30/+48
| | | | | | | | | | | | 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
* Simplify compositions of AffineApplyNicolas Vasilache2019-03-293-338/+52
| | | | | | | | This CL is the 6th and last on the path to simplifying AffineMap composition. This removes `AffineValueMap::forwardSubstitutions` and replaces it by simple calls to `fullyComposeAffineMapAndOperands`. PiperOrigin-RevId: 228962580
* Uniformize composition of AffineApplyOp by constructionNicolas Vasilache2019-03-291-126/+112
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This CL is the 5th on the path to simplifying AffineMap composition. This removes the distinction between normalized single-result AffineMap and more general composed multi-result map. One nice byproduct of making the implementation driven by single-result is that the multi-result extension is a trivial change: the implementation is still single-result and we just use: ``` unsigned idx = getIndexOf(...); map.getResult(idx); ``` This CL also fixes an AffineNormalizer implementation issue related to symbols. Namely it stops performing substitutions on symbols in AffineNormalizer and instead concatenates them all to be consistent with the call to `AffineMap::compose(AffineMap)`. This latter call to `compose` cannot perform simplifications of symbols coming from different maps based on positions only: i.e. dims are applied and renumbered but symbols must be concatenated. The only way to determine whether symbols from different AffineApply are the same is to look at the concrete values. The canonicalizeMapAndOperands is thus extended with behavior to support replacing operands that appear multiple times. Lastly, this CL demonstrates that the implementation is correct by rewriting ComposeAffineMaps using only `makeComposedAffineApply`. The implementation uses a matcher because AffineApplyOp are introduced as composed operations on the fly instead of iteratively forwardSubstituting. For this purpose, a walker would revisit freshly introduced AffineApplyOp. Regardless, ComposeAffineMaps is scheduled to disappear, this CL replaces the implementation based on iterative `forwardSubstitute` by a composed-by-construction `makeComposedAffineApply`. Remaining calls to `forwardSubstitute` will be removed in the next CL. PiperOrigin-RevId: 228830443
* Add safeguard against FM explosionUday Bondhugula2019-03-291-0/+10
| | | | | | | | | | | | | | | - FM has a worst case exponential complexity. For our purposes, this worst case is rarely expected, but could still appear due to improperly constructed constraints (a logical/memory error in other methods for eg.) or artificially created arbitrarily complex integer sets (adversarial / fuzz tests). Add a check to detect such an explosion in the number of constraints and conservatively return false from isEmpty() (instead of running out of memory or running for too long). - Add an artifical virus test case. PiperOrigin-RevId: 228753496
* Fix affine expr flattener bug + improve simplification in a particular scenarioUday Bondhugula2019-03-292-67/+81
| | | | | | | | | | | | | - fix visitDivExpr: constraints constructed for localVarCst used the original divisor instead of the simplified divisor; fix this. Add a simple test case in memref-bound-check that reproduces this bug - although this was encountered in the context of slicing for fusion. - improve mod expr flattening: when flattening mod expressions, cancel out the GCD of the numerator and denominator so that we can get a simpler flattened form along with a simpler floordiv local var for it PiperOrigin-RevId: 228539928
* Delete FuncBuilder::createChecked. It is perhaps still a good idea, but has noChris Lattner2019-03-291-2/+1
| | | | | | | | clients. Let's re-add it in the future if there is ever a reason to. NFC. Unrelatedly, add a use of a variable to unbreak the non-assert build. PiperOrigin-RevId: 228284026
* Move makeNormalizedAffineApplyNicolas Vasilache2019-03-292-207/+204
| | | | | | | | This CL is the 3rd on the path to simplifying AffineMap composition. This CL just moves `makeNormalizedAffineApply` from VectorAnalysis to AffineAnalysis where it more naturally belongs. PiperOrigin-RevId: 228277182
* Introduce AffineMap::compose(AffineMap)Nicolas Vasilache2019-03-291-18/+14
| | | | | | | | | | | This CL is the 2nd on the path to simplifying AffineMap composition. This CL uses the now accepted `AffineExpr::compose(AffineMap)` to implement `AffineMap::compose(AffineMap)`. Implications of keeping the simplification function in Analysis are documented where relevant. PiperOrigin-RevId: 228276646
* Fix 0-d memref corner case for getMemRefRegion()Uday Bondhugula2019-03-291-0/+9
| | | | | | | - fix crash on test/Transforms/canonicalize.mlir with -memref-bound-check PiperOrigin-RevId: 228268486
* Introduce AffineExpr::compose(AffineMap)Nicolas Vasilache2019-03-292-28/+6
| | | | | | | | | | | This CL is the 1st on the path to simplifying AffineMap composition. This CL uses the now accepted AffineExpr.replaceDimsAndSymbols to implement `AffineExpr::compose(AffineMap)`. Arguably, `simplifyAffineExpr` should be part of IR and not Analysis but this CL does not yet pull the trigger on that. PiperOrigin-RevId: 228265845
* Extend loop-fusion's slicing utility + other fixes / updatesUday Bondhugula2019-03-293-142/+477
| | | | | | | | | | | | | | | | | | | | | | | | - 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-294-85/+84
| | | | | | | | | | | | | | | | | | - 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
* Rename getAffineBinaryExpr -> getAffineBinaryOpExpr, getBinaryAffineOpExpr ->Uday Bondhugula2019-03-291-3/+3
| | | | | | | | getAffineBinaryOpExpr for consistency (NFC) - this is consistent with the name of the class and getAffineDimExpr/ConstantExpr, etc. PiperOrigin-RevId: 228164959
OpenPOWER on IntegriCloud