[SCEV] Construct SCEV iteratively.
authorFlorian Hahn <flo@fhahn.com>
Wed, 29 Jun 2022 10:29:31 +0000 (11:29 +0100)
committerFlorian Hahn <flo@fhahn.com>
Wed, 29 Jun 2022 10:29:31 +0000 (11:29 +0100)
commit675080a4533b91b3b62e51d3659629bc020fb940
tree4e88748899420802588a2a835b62f37212b11e6f
parent4ee6b7806bc04e3d037c0679260a54828ce7ad4c
[SCEV] Construct SCEV iteratively.

This patch updates SCEV construction to work iteratively instead of recursively
in most cases. It resolves stack overflow issues when trying to construct SCEVs
for certain inputs, e.g. PR45201.

The basic approach is to to use a worklist to queue operands of V which
need to be created before V. To do so, the current patch adds a
getOperandsToCreate function which collects the operands SCEV
construction depends on for a given value. This is a slight duplication
with createSCEV.

At the moment, SCEVs for phis are still created recursively.

Fixes #32078, #42594, #44546, #49293, #49599,  #55333, #55511

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D114650
llvm/include/llvm/Analysis/ScalarEvolution.h
llvm/lib/Analysis/ScalarEvolution.cpp