FranckQC edited a comment on pull request #9482: URL: https://github.com/apache/tvm/pull/9482#issuecomment-972608426
Many thanks for the interesting questions and comments, I really appreciate it. > > > I have another three questions about the pass. > > 1. Since function calls are non-eligible, it seems to prevent many common non-stateful builtin computations from being optimized, such as `tir.floordiv`, `tir.shift_right`, `tir.likely`, `tir.log` and etc. TVM already have op annotation like `PURE`: > https://github.com/apache/tvm/blob/main/include/tvm/tir/op_attr_types.h#L60-L67 > what if to add an annotation type like `DETERMINISTIC` to mark the function return same output on same input. It should be > safe to eliminate common calls if the call op is both pure and deterministic. Yes, I definitely agree that we could, in the future, relax the restriction which currently prevent function calls from being commoned-out, for some functions that we know to be pure, including some builtin. I think just the "pure" tag would be enough for this purpose, if it has the meaning that I imagine, which is this one (quoted from Wikipedia) : ################# a pure function is a function that has the following properties: 1. The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams). 2. The function application has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or input/output streams). Thus a pure function is a computational analogue of a mathematical function. Some authors, particularly from the imperative language community, use the term "pure" for all functions that just have the above property 2. ################# What is crucial for us for commoning-out function calls is only the condition 1. As long as the function returns always the same output for the same input, we are fine with putting the result of applying the function to some input into a variable (or any kind of "cache"). Please note that in the Wikipedia article they later mention that the condition 2 is needed for perfoming CSE, but they are talking about a different problem that we are discussing (and they aren't very precise about it). They do not talk about commoning-out function calls here. They are talking about commoning-out some redundant terms, between which some function calls happen, as in : x = a+b+c; f(); // Here, if f can change the content of some variables like a, b or c, it prevents the CSE on the redundant term (a+b+c) y = a+b+c; But this kind of consideration does not concern us, as TIR is in a (weak) SSA form : the content of variables won't be updated, and can be assumed to be the same everywhere through the execution of the program. Thus, only condition 1 matters to us. If the kPure tag has both the meaning of 1 and 2, then we will be to just use it in the future when relaxing the condition. If it's only the condition 2, then we will indeed need another tag. > 2. Is the let binding semantic in tir explicitly what we want? Is the value expr is specified to be evaluated at let scope entry? otherwise there may be no reuse effect if let-binding allow the value expr get lazily expanded in let body. I must admit that I am not entirely sure now that I think of it... Anyone to confirm on that? > 3. Is this possible for some complex (but common) expr to be lifted out of control flow scope? eg > ```python > if cond0: > tir.evaluate(complex_e) # slow path > else: > if cond2: > tir.evaluate(complex_e) # slow path > else: > ... # general fast path > ``` > > > > > > > > > > > > after CSE maybe comes to > ```python > x = tir.Var("int32") > with tir.let(x, complex_e): # always evaluate slow path > if cond0: > tir.evaluate(x) > else: > if cond2: > tir.evaluate(x) > else: > ... # general fast path > ``` Yes, that is possible. Although, now that I think of it, it would probably better to not do it in the exact example that you provided, as the expression `complex_e` of the slow path now becomes always evaluated, even if we end up going in the general fast branch... We should only lift things through "if" statements if both the then branch and the else branch computes it. This restriction doesn't improve the semantics preservation (which was previously fine), but it will avoid this kind of anti-optimization. That should be easily fixable. Many thanks! -- 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. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
