DKXXXL edited a comment on issue #4468: [RFC] Data-flow Analysis Functionality on TVM IR URL: https://github.com/apache/incubator-tvm/issues/4468#issuecomment-561917833 ### Other things: IsLattice The basic usage is just: ```cpp template <typename T> struct STD_SET_IS_LATTICE : public IsLattice<std::set<T>> { using SET = std::set<T>; public: SET join(const SET& a, const SET& b); SET meet(const SET& a, const SET& b); const SET& top(); const SET& bottom(); bool equal(const SET& a, const SET& b); static const STD_SET_IS_LATTICE<T>& __ops() { static const STD_SET_IS_LATTICE<T> op; return op; } static const STD_SET_IS_LATTICE<T>& ops = STD_SET_IS_LATTICE<T>::__ops(); }; ``` and when trying to make things concrete, you can try to declare something like `class X : ffdfa<std::set, STD_SET_IS_LATTICE , STD_SET_IS_LATTICE::ops>` . ### Other things: A Concrete computing example for Live Variable Analysis To make the proposal more understandable, we compute on a concrete example, on a program given as below: ```python Block1 a = b Block2 If (iszero b) then x = 1 else x = 2 c = x + 2 # {} as Alive, at the exit point of ASTNode Block1 ``` Note that we will calculate, the live variables at entry/exit point for each ASTNode (except for variables to not disrupt the format). We know at the end there is no live variable, and due to the recursive calls, this empty set will be propagated up to the exit points of Block2 and Statement `c = x+2`(the leaf of the AST): ```python Block1 a = b Block2 If (iszero b) then x = 1 else x = 2 # {x} as Alive -- exit point of If Statement # {x} as Alive -- entry point of 'c=x+2' c = x + 2 # {} as Alive -- exit point of 'c=x+2' # {} as Alive -- exit point of Block2 # {} as Alive -- exit point of Block1 ``` A single assignment statement will change live variable accordingly, and due to how `Block` is dealt with, the exitpoint of IfStatement will have the same value as the entry point of the following statement. IfStatement is dealt with according to the pseudo-code, and note that the conditional will have its information as well. Reflecting from that pseudo-code, because `LiveVariableAnalysis Conditional AfterCondition` is evaluated, and MemorizedVersion will record all the input and output of the `LiveVaraibleAnalysis` call once evaluated, so this conditional will be a key in the cache dictionary. At the end, it will be the following: ```cpp # {b} as Alive, entry of Block1, since recursion directly propagate it up Block1 # {b} as Alive, entry of 'a = b' a = b # {b} as Alive, exit of 'a = b' # {b} as Alive, entry of Block2, since recursion directly propagate it up Block2 # {b} as Alive, entry of If Statement # {b} as Alive, entry of '(iszero b)' If (iszero b) # {} as Alive, exit of '(iszero b)' # {} as Alive, entry of 'x=1' then x = 1 # {x} as Alive -- exit of 'x=1' # {} as Alive, entry of 'x=2' else x = 2 # {x} as Alive -- exit of 'x=2' # {x} as Alive -- exit point of If Statement # {x} as Alive -- entry point of 'c=x+2' c = x + 2 # {} as Alive -- exit point of 'c=x+2' # {} as Alive -- exit point of Block2 # {} as Alive -- exit point of Block1 ```
---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected] With regards, Apache Git Services
