| 文件 | 最后提交记录 | 最后更新时间 |
|---|---|---|
Apply clang-tidy fixes for readability-identifier-naming in TestBackwardDataFlowAnalysis.cpp (NFC) | 3 年前 | |
[mlir][dataflow] Consolidate AbstractSparseLattice::markPessimisticFixpoint() and AbstractDenseLattice::reset() into Abstract{Sparse,Dense}DataFlowAnalysis::setToEntryState(). ### Rationale For a program point where we cannot reason about incoming dataflow (e.g. an argument of an entry block), the framework needs to initialize the state. Currently, AbstractSparseDataFlowAnalysis initializes such state to the "pessimistic fixpoint", and AbstractDenseDataFlowAnalysis calls the state's reset() function. However, entry states aren't necessarily the pessimistic fixpoint. Example: in reaching definition, the pessimistic fixpoint is {all definitions}, but the entry state is {}. This awkwardness might be why the dense analysis API currently uses reset() instead of markPessimisticFixpoint(). This patch consolidates entry point initialization into a single function setToEntryState(). ### API Location Note that setToEntryState() is defined in the analysis rather than the lattice, so that we allow different analyses to use the same lattice but different entry states. ### Removal of the concept of optimistic/known value The concept of optimistic/known value is too specific to SCCP. Furthermore, the known value is not really used: In the current SCCP implementation, the known value (pessimistic fixpoint) is always Attribute{} (non-constant). This means there's no point storing a knownValue in each state. If we do need to re-introduce optimistic/known value, we should put it in the SCCP analysis, not the sparse analysis API. ### Terminology Please let me know if "entry state" is a good terminology. I chose "entry" from Wikipedia (https://en.wikipedia.org/wiki/Data-flow_analysis#Basic_principles). Another term I can think of is "boundary" (https://suif.stanford.edu/~courses/cs243/lectures/L3-DFA2-revised.pdf) which might be better since it also makes sense for backward analysis. Reviewed By: Mogball Differential Revision: https://reviews.llvm.org/D132086 | 3 年前 | |
[mlir] allow dense dataflow to customize call and region operations Initial implementations of dense dataflow analyses feature special cases for operations that have region- or call-based control flow by leveraging the corresponding interfaces. This is not necessarily sufficient as these operations may influence the dataflow state by themselves as well we through the control flow. For example, linalg.generic and similar operations have region-based control flow and their proper memory effects, so any memory-related analyses such as last-writer require processing linalg.generic directly instead of, or in addition to, the region-based flow. Provide hooks to customize the processing of operations with region- cand call-based contol flow in forward and backward dense dataflow analysis. These hooks are trigerred when control flow is transferred between the "main" operation, i.e. the call or the region owner, and another region. Such an apporach allows the analyses to update the lattice before and/or after the regions. In the linalg.generic example, the reads from memory are interpreted as happening before the body region and the writes to memory are interpreted as happening after the body region. Using these hooks in generic analysis may require introducing additional interfaces, but for now assume that the specific analysis have spceial cases for the (rare) operaitons with call- and region-based control flow that need additional processing. Reviewed By: Mogball, phisiart Differential Revision: https://reviews.llvm.org/D155757 | 3 年前 | |
[mlir] allow dense dataflow to customize call and region operations Initial implementations of dense dataflow analyses feature special cases for operations that have region- or call-based control flow by leveraging the corresponding interfaces. This is not necessarily sufficient as these operations may influence the dataflow state by themselves as well we through the control flow. For example, linalg.generic and similar operations have region-based control flow and their proper memory effects, so any memory-related analyses such as last-writer require processing linalg.generic directly instead of, or in addition to, the region-based flow. Provide hooks to customize the processing of operations with region- cand call-based contol flow in forward and backward dense dataflow analysis. These hooks are trigerred when control flow is transferred between the "main" operation, i.e. the call or the region owner, and another region. Such an apporach allows the analyses to update the lattice before and/or after the regions. In the linalg.generic example, the reads from memory are interpreted as happening before the body region and the writes to memory are interpreted as happening after the body region. Using these hooks in generic analysis may require introducing additional interfaces, but for now assume that the specific analysis have spceial cases for the (rare) operaitons with call- and region-based control flow that need additional processing. Reviewed By: Mogball, phisiart Differential Revision: https://reviews.llvm.org/D155757 | 3 年前 | |
[mlir] add backward dense dataflow analysis This is the counterpart to the forward dense dataflow analysis and integrates into the dataflow framework. The implementation follows the structure of existing dataflow analyses. Reviewed By: Mogball, phisiart Differential Revision: https://reviews.llvm.org/D154713 | 3 年前 | |
[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 | 3 年前 |