Page MenuHomePhabricator

[NFCI][SCEV] Avoid recursion in SCEVExpander::isHighCostExpansion*()
ClosedPublic

Authored by lebedev.ri on Mar 17 2020, 2:54 AM.

Details

Summary

As noted in PR45201,
PR10090 SCEV doesn't always avoid
recursive algorithms, and that causes issues with large expression depths and/or smaller stack sizes.

In SCEVExpander::isHighCostExpansion*() case, the refactoring to avoid recursion
is rather idiomatic. We simply need to place the root expr into a vector,
and iterate over vector elements accounting for the cost of each one,
and add new exprs at the end of the vector, thus achieving FIFO breadth-first traversal.

Diff Detail

Event Timeline

lebedev.ri created this revision.Mar 17 2020, 2:54 AM
lebedev.ri retitled this revision from [SCEV] Avoid recursion in SCEVExpander::isHighCostExpansion*() to [NFCI][SCEV] Avoid recursion in SCEVExpander::isHighCostExpansion*().Mar 17 2020, 2:54 AM
mkazantsev added inline comments.Mar 18 2020, 3:40 AM
llvm/include/llvm/Analysis/ScalarEvolutionExpander.h
195

I'm not getting why do you need a worklist. On the 1st iteration of this loop, you put one value to the WorkList and then remove it. isHighCostExpansionHelper always puts one element to the worklist and then returns. Therefore the size of your FIFO is either 0 or 1. Do you really need to use deque for it?

mkazantsev accepted this revision.Mar 18 2020, 3:46 AM

LGTM

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h
195

Sorry, I misread the code. It may put multiple elements into it.

This revision is now accepted and ready to land.Mar 18 2020, 3:46 AM
mkazantsev added inline comments.Mar 18 2020, 3:48 AM
llvm/include/llvm/Analysis/ScalarEvolutionExpander.h
27

Can we go with queue?

mkazantsev added a comment.EditedMar 18 2020, 3:50 AM

As a suggestion: since this helper doesn't create new code, it doesn't seem to be important whether it is FIFO or LIFO. If that is so, I'd suggest using SmallVector and LIFO algorithm instead. It should have better memory footprint. OK if it does as follow-up.

lebedev.ri marked 3 inline comments as done.Mar 18 2020, 4:00 AM

LGTM

Thank you for the review!

As a suggestion: since this helper doesn't create new code, it doesn't seem to be important whether it is FIFO or LIFO. If that is so, I'd suggest using SmallVector and LIFO algorithm instead. It should have better memory footprint. OK if it does as follow-up.

I agree the order doesn't matter for correctness.
Currently we seem to be doing depth-first traversal (since we recurse before looking at other operands).
I don't have any evidence which approach is better in the sense that it would exhaust the budget faster,
so i'll go back to simple smallvector with back-insertion/extraction.

This revision was automatically updated to reflect the committed changes.