TTobias Hieta[mlir] Fix infinite recursion in alias initializer
| 文件 | 最后提交记录 | 最后更新时间 |
|---|---|---|
[MLIR][ANALYSIS] Add liveness analysis utility This commit adds a utility to implement liveness analysis using the sparse backward data-flow analysis framework. Theoretically, liveness analysis assigns liveness to each (value, program point) pair in the program and it is thus a dense analysis. However, since values are immutable in MLIR, a sparse analysis, which will assign liveness to each value in the program, suffices here. Liveness analysis has many applications. It can be used to avoid the computation of extraneous operations that have no effect on the memory or the final output of a program. It can also be used to optimize register allocation. Both of these applications help achieve one very important goal: reducing runtime. A value is considered "live" iff it: (1) has memory effects OR (2) is returned by a public function OR (3) is used to compute a value of type (1) or (2). It is also to be noted that a value could be of multiple types (1/2/3) at the same time. A value "has memory effects" iff it: (1.a) is an operand of an op with memory effects OR (1.b) is a non-forwarded branch operand and a block where its op could take the control has an op with memory effects. A value A is said to be "used to compute" value B iff B cannot be computed in the absence of A. Thus, in this implementation, we say that value A is used to compute value B iff: (3.a) B is a result of an op with operand A OR (3.b) A is used to compute some value C and C is used to compute B. --- It is important to note that there already exists an MLIR liveness utility here: llvm-project/mlir/include/mlir/Analysis/Liveness.h. So, what is the need for this new liveness analysis utility being added by this commit? That need is explained as follows:- The similarities between these two utilities is that both use the fixpoint iteration method to converge to the final result of liveness. And, both have the same theoretical understanding of liveness as well. However, the main difference between (a) the existing utility and (b) the added utility is the "scope of the analysis". (a) is restricted to analysing each block independently while (b) analyses blocks together, i.e., it looks at how the control flows from one block to the other, how a caller calls a callee, etc. The restriction in the former implies that some potentially non-live values could be marked live and thus the full potential of liveness analysis will not be realised. This can be understood using the example below: 1 func.func private @private_dead_return_value_removal_0() -> (i32, i32) { 2 %0 = arith.constant 0 : i32 3 %1 = arith.addi %0, %0 : i32 4 return %0, %1 : i32, i32 5 } 6 func.func @public_dead_return_value_removal_0() -> (i32) { 7 %0:2 = func.call @private_dead_return_value_removal_0() : () -> (i32, i32) 8 return %0#0 : i32 9 } Here, if we just restrict our analysis to a per-block basis like (a), we will say that the %1 on line 3 is live because it is computed and then returned outside its block by the function. But, if we perform a backward data-flow analysis like (b) does, we will say that %0#1 of line 7 is not live because it isn't returned by the public function and thus, %1 of line 3 is also not live. So, while (a) will be unable to suggest any IR optimizations, (b) can enable this IR to convert to:- 1 func.func private @private_dead_return_value_removal_0() -> i32 { 2 %0 = arith.constant 0 : i32 3 return %0 : i32 4 } 5 func.func @public_dead_return_value_removal_0() -> i32 { 6 %0 = call @private_dead_return_value_removal_0() : () -> i32 7 return %0 : i32 8 } One operation was removed and one unnecessary return value of the function was removed and the function signature was modified. This is an optimization that (b) can enable but (a) cannot. Such optimizations can help remove a lot of extraneous computations that are currently being done. Signed-off-by: Srishti Srivastava <srishtisrivastava.ai@gmail.com> Reviewed By: matthiaskramm, jcai19 Differential Revision: https://reviews.llvm.org/D153779 | 2 年前 | |
[mlir] NFC: untangle SCF Patterns.h and Transforms.h These two headers both contained a strange mix of definitions related to both patterns and non-pattern transforms. Put patterns and "populate" functions into Patterns.h and standalone transforms into Transforms.h. Depends On: D155223 Reviewed By: nicolasvasilache Differential Revision: https://reviews.llvm.org/D155454 | 2 年前 | |
[mlir] Fix infinite recursion in alias initializer The alias initializer keeps a list of child indices around. When an alias is then marked as non-deferrable, all children are also marked non-deferrable. This is currently done naively which leads to an infinite recursion if using mutable types or attributes containing a cycle. This patch fixes this by adding an early return if the alias is already marked non-deferrable. Since this function is the only way to mark an alias as non-deferrable, it is guaranteed that if it is marked non-deferrable, all its children are as well, and it is not required to walk all the children. This incidentally makes the non-deferrable marking also O(n) instead of O(n^2) (although not performance sensitive obviously). Differential Revision: https://reviews.llvm.org/D158932 | 2 年前 | |
[mlir] Add a builtin distinct attribute A distinct attribute associates a referenced attribute with a unique identifier. Every call to its create function allocates a new distinct attribute instance. The address of the attribute instance temporarily serves as its unique identifier. Similar to the names of SSA values, the final unique identifiers are generated during pretty printing. Examples: #distinct = distinct[0]<42.0 : f32> #distinct1 = distinct[1]<42.0 : f32> #distinct2 = distinct[2]<array<i32: 10, 42>> This mechanism is meant to generate attributes with a unique identifier, which can be used to mark groups of operations that share a common properties such as if they are aliasing. The design of the distinct attribute ensures minimal memory footprint per distinct attribute since it only contains a reference to another attribute. All distinct attributes are stored outside of the storage uniquer in a thread local store that is part of the context. It uses one bump pointer allocator per thread to ensure distinct attributes can be created in-parallel. Reviewed By: rriddle, Dinistro, zero9178 Differential Revision: https://reviews.llvm.org/D153360 | 2 年前 | |
[mlir][Interfaces] TilingInterface: Add test case for linalg.copy on memrefs Differential Revision: https://reviews.llvm.org/D153347 | 3 年前 | |
[mlir-opt] Add a '-dump-pass-pipeline' option Add an option to dump the pipeline that will be run to stderr. A dedicated option is needed since the existing test-dump-pipeline pipeline won't be usable with -pass-pipeline after D135745. Reviewed By: rriddle, mehdi_amini Differential Revision: https://reviews.llvm.org/D135747 | 3 年前 | |
[mlir] Rework the implementation of TypeID This commit restructures how TypeID is implemented to ideally avoid the current problems related to shared libraries. This is done by changing the "implicit" fallback path to use the name of the type, instead of using a static template variable (which breaks shared libraries). The major downside to this is that it adds some additional initialization costs for the implicit path. Given the use of type names for uniqueness in the fallback, we also no longer allow types defined in anonymous namespaces to have an implicit TypeID. To simplify defining an ID for these classes, a new MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID macro was added to allow for explicitly defining a TypeID directly on an internal class. To help identify when types are using the fallback, -debug-only=typeid can be used to log which types are using implicit ids. This change generally only requires changes to the test passes, which are all defined in anonymous namespaces, and thus can't use the fallback any longer. Differential Revision: https://reviews.llvm.org/D122775 | 4 年前 | |
[mlir:PDL] Expand how native constraint/rewrite functions can be defined This commit refactors the expected form of native constraint and rewrite functions, and greatly reduces the necessary user complexity required when defining a native function. Namely, this commit adds in automatic processing of the necessary PDLValue glue code, and allows for users to define constraint/rewrite functions using the C++ types that they actually want to use. As an example, lets see a simple example rewrite defined today: static void rewriteFn(PatternRewriter &rewriter, PDLResultList &results, ArrayRef<PDLValue> args) { ValueRange operandValues = args[0].cast<ValueRange>(); TypeRange typeValues = args[1].cast<TypeRange>(); ... // Create an operation at some point and pass it back to PDL. Operation *op = rewriter.create<SomeOp>(...); results.push_back(op); } After this commit, that same rewrite could be defined as: static Operation *rewriteFn(PatternRewriter &rewriter ValueRange operandValues, TypeRange typeValues) { ... // Create an operation at some point and pass it back to PDL. return rewriter.create<SomeOp>(...); } Differential Revision: https://reviews.llvm.org/D122086 | 4 年前 | |
Add missing dependent test dialect in a MLIR test pass Fix #62317 | 3 年前 | |
Fix MLIR test pass crash The pass tried to fold in reverse-post-order, but it cause an issue when a parent is folded before the chilren as they will still be present in the worklist. Use reverse-preorder instead here. Fixes #64089 | 2 年前 | |
[mlir][TilingInterface] Add pattern to tile using TilingInterface and implement TilingInterface for Linalg ops. This patch adds support for tiling operations that implement the TilingInterface. - It separates the loop constructs that are used to iterate over tile from the implementation of the tiling itself. For example, the use of destructive updates is more related to use of scf.for for iterating over tiles that are tensors. - To test the transformation, TilingInterface is implemented for LinalgOps. The separation of the looping constructs used from the implementation of tile code generation greatly simplifies the latter. - The implementation of TilingInterface for LinalgOp is kept as an external model for now till this approach can be fully flushed out to replace the existing tiling + fusion approaches in Linalg. Differential Revision: https://reviews.llvm.org/D127133 | 4 年前 |