efriedma added inline comments.
================ Comment at: llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp:825 + // The local stack holds all alloca instructions and all byval arguments. + AllocaDerivedValueTracker Tracker; + for (Argument &Arg : F.args()) { ---------------- avl wrote: > efriedma wrote: > > avl wrote: > > > efriedma wrote: > > > > avl wrote: > > > > > efriedma wrote: > > > > > > Do you have to redo the AllocaDerivedValueTracker analysis? Is it > > > > > > not enough that the call you're trying to TRE is marked "tail"? > > > > > >Do you have to redo the AllocaDerivedValueTracker analysis? > > > > > > > > > > AllocaDerivedValueTracker analysis(done in markTails) could be reused > > > > > here. > > > > > But marking, done in markTails(), looks like separate tasks. i.e. it > > > > > is better > > > > > to make TRE not depending on markTails(). There is a review for this > > > > > - https://reviews.llvm.org/D60031 > > > > > Thus such separation looks useful(To not reuse result of markTails > > > > > but have it computed inplace). > > > > > > > > > > > Is it not enough that the call you're trying to TRE is marked > > > > > > "tail"? > > > > > > > > > > It is not enough that call which is subject to TRE is marked "Tail". > > > > > It also should be checked that other calls does not capture pointer > > > > > to local stack: > > > > > > > > > > ``` > > > > > // do not do TRE if any pointer to local stack has escaped. > > > > > if (!Tracker.EscapePoints.empty()) > > > > > return false; > > > > > > > > > > ``` > > > > > > > > > > It is not enough that call which is subject to TRE is marked "Tail". > > > > > It also should be checked that other calls does not capture pointer > > > > > to local stack: > > > > > > > > If there's an escaped pointer to the local stack, we wouldn't infer > > > > "tail" in the first place, would we? > > > If function receives pointer to alloca then it would not be marked with > > > "Tail". Then we do not have a possibility to understand whether this > > > function receives pointer to alloca but does not capture it: > > > > > > ``` > > > void test(int recurseCount) > > > { > > > if (recurseCount == 0) return; > > > int temp = 10; > > > globalIncrement(&temp); > > > test(recurseCount - 1); > > > } > > > ``` > > > > > > test - marked with Tail. > > > globalIncrement - not marked with Tail. But TRE could be done since it > > > does not capture pointer. But if it will capture the pointer then we > > > could not do TRE. So we need to check !Tracker.EscapePoints.empty(). > > > > > > > > > > > > test - marked with Tail. > > > > For the given code, TRE won't mark the recursive call "tail". That > > transform isn't legal: the recursive call could access the caller's version > > of "temp". > >For the given code, TRE won't mark the recursive call "tail". That transform > >isn't legal: the recursive call could access the caller's version of "temp". > > it looks like recursive call could NOT access the caller's version of "temp": > > ``` > test(recurseCount - 1); > ``` > > Caller`s version of temp is accessed by non-recursive call: > > ``` > globalIncrement(&temp); > ``` > > If globalIncrement does not capture the "&temp" then TRE looks to be legal > for that case. > > globalIncrement() would not be marked with "Tail". test() would be marked > with Tail. > > Thus the pre-requisite for TRE would be: tail-recursive call must not receive > pointer to local stack(Tail) and non-recursive calls must not capture the > pointer to local stack. Can you give a complete IR example where we infer "tail", but TRE is illegal? Can you give a complete IR example, we we don't infer "tail", but we still do the TRE transform here? Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D82085/new/ https://reviews.llvm.org/D82085 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits