[ConstFolding] Modified algorithm of `ConstantFoldConstantImpl` to be iterative

[nikolaypanchenko]

Summary

Vectorization of the loop may result to huge amount of runtime checks and if host machine has limited stack size, Constant Folding will hit the stack overflow and compilation will crash.
The change modifies the algorithm so that in such environment stack overflow won't happen.

[nikic]

Patch missing description. What's the motivation for the change?

[nikolaypanchenko]

In D142680#4084917, @nikic wrote:

Patch missing description. What's the motivation for the change?

Added. Cannot add a unit test as it will be too large.

[nikic]

Can you share how the produced constant expression looks like? Ideally we would not create it in the first place, which we can now do by removing some constant expression operator. I'd be interested in knowing what to target here.

llvm/lib/Analysis/ConstantFolding.cpp

 //===----------------------------------------------------------------------===//
 
 namespace {
 
 Constant *
 ConstantFoldConstantImpl(const Constant *C, const DataLayout &DL,
                          const TargetLibraryInfo *TLI,
                          SmallDenseMap<Constant *, Constant *> &FoldedOps) {
-  if (!isa<ConstantVector>(C) && !isa<ConstantExpr>(C))
-    return const_cast<Constant *>(C);
+  SmallVector<Constant *> Worklist = {const_cast<Constant *>(C)};
+
+  // "Recursively" iterate over all users of the constant. Try to fold constant
+  // if all its operand were processed before.
+  while (!Worklist.empty()) {
+    Constant *CurrentC = Worklist.back();
+    if (FoldedOps.count(CurrentC)) {
+      Worklist.pop_back();
+      continue;
+    }
+
+    if (!isa<ConstantVector>(CurrentC) && !isa<ConstantExpr>(CurrentC)) {
+      Worklist.pop_back();
+      FoldedOps.try_emplace(CurrentC, CurrentC);
+      continue;
+    }
 
     SmallVector<Constant *, 8> Ops;
-  for (const Use &OldU : C->operands()) {
-    Constant *OldC = cast<Constant>(&OldU);
+    for (const Use &U : CurrentC->operands()) {
+      Constant *OldC = cast<Constant>(&U);
       Constant *NewC = OldC;
-    // Recursively fold the ConstantExpr's operands. If we have already folded
-    // a ConstantExpr, we don't have to process it again.
       if (isa<ConstantVector>(OldC) || isa<ConstantExpr>(OldC)) {
         auto It = FoldedOps.find(OldC);
         if (It == FoldedOps.end()) {
-        NewC = ConstantFoldConstantImpl(OldC, DL, TLI, FoldedOps);
-        FoldedOps.insert({OldC, NewC});
+          NewC = nullptr;
+          Worklist.push_back(OldC);
         } else {
           NewC = It->second;
         }
       }
+      if (NewC)
         Ops.push_back(NewC);
     }
 
-  if (auto *CE = dyn_cast<ConstantExpr>(C)) {
+    // If all operands of the constant were processed, try to fold them
+    if (Ops.size() == CurrentC->getNumOperands()) {
+      assert(Worklist.back() == CurrentC &&
+             "Some operand of the Constant was added to the Worklist.");
+      Worklist.pop_back();
+
+      if (auto *CE = dyn_cast<ConstantExpr>(CurrentC)) {
         if (Constant *Res =
                 ConstantFoldInstOperandsImpl(CE, CE->getOpcode(), Ops, DL, TLI))
-      return Res;
-    return const_cast<Constant *>(C);
+          FoldedOps.try_emplace(CurrentC, Res);
+        else
+          FoldedOps.try_emplace(CurrentC, CurrentC);
+      } else {
+        FoldedOps.try_emplace(CurrentC, ConstantVector::get(Ops));
       }
-
-  assert(isa<ConstantVector>(C));
-  return ConstantVector::get(Ops);
+    }
+  }
+  return FoldedOps.find(C)->second;
 }
 
 } // end anonymous namespace
 
 Constant *llvm::ConstantFoldInstruction(Instruction *I, const DataLayout &DL,
                                         const TargetLibraryInfo *TLI) {
   // Handle PHI nodes quickly here...
   if (auto *PN = dyn_cast<PHINode>(I)) {