| 文件 | 最后提交记录 | 最后更新时间 |
|---|---|---|
[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][Analysis] Guard data flow analysis from no block function Foo analysis for testing the data flow analysis does not support the region without any block. Although that analysis is assumed to be used for testing purpose, it is generally better to be explicit about the scope the framework supports. The original issue was reported here. https://github.com/llvm/llvm-project/issues/60580 Reviewed By: springerm Differential Revision: https://reviews.llvm.org/D144359 | 3 年前 | |
[mlir] Make LocalAliasAnalysis extesible This is an alternative to https://reviews.llvm.org/D138761 . Instead of adding ad-hoc attributes to existing LocalAliasAnalysis, expose aliasImpl method so user can override it. Differential Revision: https://reviews.llvm.org/D140348 | 3 年前 | |
[mlir][Pass] Include anchor op in -pass-pipeline In D134622 the printed form of a pass manager is changed to include the name of the op that the pass manager is anchored on. This updates the -pass-pipeline argument format to include the anchor op as well, so that the printed form of a pipeline can be directly passed to -pass-pipeline. In most cases this requires updating -pass-pipeline='pipeline' to -pass-pipeline='builtin.module(pipeline)'. This also fixes an outdated assert that prevented running a PassManager anchored on 'any'. Reviewed By: rriddle Differential Revision: https://reviews.llvm.org/D134900 | 3 年前 | |
[mlir][Pass] Include anchor op in -pass-pipeline In D134622 the printed form of a pass manager is changed to include the name of the op that the pass manager is anchored on. This updates the -pass-pipeline argument format to include the anchor op as well, so that the printed form of a pipeline can be directly passed to -pass-pipeline. In most cases this requires updating -pass-pipeline='pipeline' to -pass-pipeline='builtin.module(pipeline)'. This also fixes an outdated assert that prevented running a PassManager anchored on 'any'. Reviewed By: rriddle Differential Revision: https://reviews.llvm.org/D134900 | 3 年前 | |
[mlir][CallGraph] Add special call graph node for representing unknown callees The callgraph currently contains a special external node that is used both as the quasi caller for any externally callable as well as callees that could not be resolved. This has one negative side effect however, which is the motivation for this patch: It leads to every externally callable which contains a call that could not be resolved (eg. an indirect call), to be put into one giant SCC when iterating over the SCCs of the call graph. This patch fixes that issue by creating a second special callgraph node that acts as the callee for any unresolved callable. This breaks the cycles produced in the callgraph, yielding proper SCCs for all direct calls. Differential Revision: https://reviews.llvm.org/D133585 | 3 年前 | |
[mlir][Analysis] Introduce LoopInfo in mlir This commit introduces an instantiation of LLVM's LoopInfo for CFGs in MLIR. To test the LoopInfo, a test pass is added the checks the analysis results for a set of CFGs. Reviewed By: ftynse Differential Revision: https://reviews.llvm.org/D147323 | 3 年前 | |
[mlir][Pass] Include anchor op in -pass-pipeline In D134622 the printed form of a pass manager is changed to include the name of the op that the pass manager is anchored on. This updates the -pass-pipeline argument format to include the anchor op as well, so that the printed form of a pipeline can be directly passed to -pass-pipeline. In most cases this requires updating -pass-pipeline='pipeline' to -pass-pipeline='builtin.module(pipeline)'. This also fixes an outdated assert that prevented running a PassManager anchored on 'any'. Reviewed By: rriddle Differential Revision: https://reviews.llvm.org/D134900 | 3 年前 | |
[mlir][NFC] Remove trailing whitespaces from *.td and *.mlir files. This is generated by running sed --in-place 's/[[:space:]]\+$//' mlir/**/*.td sed --in-place 's/[[:space:]]\+$//' mlir/**/*.mlir Reviewed By: rriddle, dcaballe Differential Revision: https://reviews.llvm.org/D138866 | 3 年前 | |
[mlir][Pass] Include anchor op in -pass-pipeline In D134622 the printed form of a pass manager is changed to include the name of the op that the pass manager is anchored on. This updates the -pass-pipeline argument format to include the anchor op as well, so that the printed form of a pipeline can be directly passed to -pass-pipeline. In most cases this requires updating -pass-pipeline='pipeline' to -pass-pipeline='builtin.module(pipeline)'. This also fixes an outdated assert that prevented running a PassManager anchored on 'any'. Reviewed By: rriddle Differential Revision: https://reviews.llvm.org/D134900 | 3 年前 | |
[mlir][Pass] Include anchor op in -pass-pipeline In D134622 the printed form of a pass manager is changed to include the name of the op that the pass manager is anchored on. This updates the -pass-pipeline argument format to include the anchor op as well, so that the printed form of a pipeline can be directly passed to -pass-pipeline. In most cases this requires updating -pass-pipeline='pipeline' to -pass-pipeline='builtin.module(pipeline)'. This also fixes an outdated assert that prevented running a PassManager anchored on 'any'. Reviewed By: rriddle Differential Revision: https://reviews.llvm.org/D134900 | 3 年前 | |
[mlir] Attach InferTypeOpInterface on SameOperandsAndResultType operations when possible This allows for inferring the result types of operations in certain situations by using the type of an operand. This commit allowed for automatically supporting type inference for many more operations with no additional effort, e.g. nearly all Arithmetic operations now support result type inferrence with no additional changes. Differential Revision: https://reviews.llvm.org/D124581 | 4 年前 | |
[mlir][Pass] Include anchor op in -pass-pipeline In D134622 the printed form of a pass manager is changed to include the name of the op that the pass manager is anchored on. This updates the -pass-pipeline argument format to include the anchor op as well, so that the printed form of a pipeline can be directly passed to -pass-pipeline. In most cases this requires updating -pass-pipeline='pipeline' to -pass-pipeline='builtin.module(pipeline)'. This also fixes an outdated assert that prevented running a PassManager anchored on 'any'. Reviewed By: rriddle Differential Revision: https://reviews.llvm.org/D134900 | 3 年前 |
| 文件 | 最后提交记录 | 最后更新时间 |
|---|---|---|
| 2 年前 | ||
| 3 年前 | ||
| 3 年前 | ||
| 3 年前 | ||
| 3 年前 | ||
| 3 年前 | ||
| 3 年前 | ||
| 3 年前 | ||
| 3 年前 | ||
| 3 年前 | ||
| 3 年前 | ||
| 4 年前 | ||
| 3 年前 |