tree d5a6b9f45318b51308a3b8260406267e459da50e
parent 7241bbbfcf60679e9355c8783a20863bf4057c5f
author Michael Kruse <llvm-project@meinersbur.de> 1602869854 -0500
committer Copybara-Service <copybara-worker@google.com> 1604025728 -0700

[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

GitOrigin-RevId: 7175cffb2133048018df74c1b49d1d4962ea18f2