HomePhabricator

[Polly] Reuse multiple uses in operand tree.

Authored by Meinersbur on Oct 16 2020, 10:37 AM.

Description

[Polly] Reuse multiple uses in operand tree.

Recursively traversing the operand tree leads to an exponential blowup
if instructions are used multiple times due to every path leading to an
additional copy of the instructions after forwarding. This problem was
marked as a TODO in the code and was reported as a bug in llvm.org/PR47340.

Fix by caching already visited instructions and returning the cached
version when already visited. Instead of calling forwardTree() twice,
return a ForwardingAction structure that contains a lambda which will
carry-out the forwarding when requested. The lambdas are executed in
reverse-postorder to mimic the previous recursive calls unless there
is a reuse.

Fixes llvm.org/PR47340

Details

Committed
MeinersburOct 20 2020, 4:05 PM
Parents
rGbe8e4de7240e: [GWP-ASan] Rework utilities (NFC)
Branches
Unknown
Tags
Unknown