Replacing recursion by cycle in file "SimplifyCFG.cpp", removing the deprecated option.

[dbakunevich]

Summary

This change is directed at this TODO:

// TODO: While this recursion limit does prevent pathological behavior, it would be better to track visited instructions to avoid cycles.

These changes are intended to replace recursion with a loop in "dominatesMergePoint". After the replacement, the deprecated option remained, which was also removed.

[nikic]

This is not what the TODO is about. The TODO is about not visiting operands repeatedly if they occur multiple times.

[lebedev.ri]

I will hopefully soon post a patch that removes dominatesMergePoint(), it's just wrong so i'm not sure it's worth improving it.

[dbakunevich]

In D108455#2957051, @nikic wrote:

This is not what the TODO is about. The TODO is about not visiting operands repeatedly if they occur multiple times.

In D108455#2957067, @lebedev.ri wrote:

I will hopefully soon post a patch that removes dominatesMergePoint(), it's just wrong so i'm not sure it's worth improving it.

I realized that I misunderstood this "todo". It is necessary to add another "SmallPtrSet", which will keep track of set unique elements.

Does it make sense to make these changes or wait for "dominatesMergePoint ()" to be removed in the future?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static cl::opt<bool> MergeCondStoresAggressively(
     cl::desc("When merging conditional stores, do so even if the resultant "
              "basic blocks are unlikely to be if-converted as a result"));
 
 static cl::opt<bool> SpeculateOneExpensiveInst(
     "speculate-one-expensive-inst", cl::Hidden, cl::init(true),
     cl::desc("Allow exactly one expensive instruction to be speculatively "
              "executed"));
 
-static cl::opt<unsigned> MaxSpeculationDepth(
-    "max-speculation-depth", cl::Hidden, cl::init(10),
-    cl::desc("Limit maximum recursion depth when calculating costs of "
-             "speculatively executed instructions"));
-
 static cl::opt<int>
     MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden,
                       cl::init(10),
                       cl::desc("Max size of a block which is still considered "
                                "small enough to thread through"));
 
 // Two is chosen to allow one negation and a logical combine.
 static cl::opt<unsigned>

 /// which works well enough for us.
 ///
 /// If AggressiveInsts is non-null, and if V does not dominate BB, we check to
 /// see if V (which must be an instruction) and its recursive operands
 /// that do not dominate BB have a combined cost lower than Budget and
 /// are non-trapping.  If both are true, the instruction is inserted into the
 /// set and true is returned.
 ///
 /// The cost for most non-trapping instructions is defined as 1 except for
 /// Select whose cost is 2.
 ///
 /// After this function returns, Cost is increased by the cost of
 /// V plus its non-dominating operands.  If that cost is greater than
 /// Budget, false is returned and Cost is undefined.
 static bool dominatesMergePoint(Value *V, BasicBlock *BB,
                                 SmallPtrSetImpl<Instruction *> &AggressiveInsts,
                                 InstructionCost &Cost,
                                 InstructionCost Budget,
-                                const TargetTransformInfo &TTI,
-                                unsigned Depth = 0) {
-  // It is possible to hit a zero-cost cycle (phi/gep instructions for example),
-  // so limit the recursion depth.
-  // TODO: While this recursion limit does prevent pathological behavior, it
-  // would be better to track visited instructions to avoid cycles.
-  if (Depth == MaxSpeculationDepth)
-    return false;
+                                const TargetTransformInfo &TTI) {
+  SmallVector<Value *, 4> Stack;
+
+  Stack.emplace_back(V);
+
+  while (Stack.size() != 0){
+    Value * CurV = Stack.pop_back_val();
+    Instruction *I = dyn_cast<Instruction>(CurV);
 
-  Instruction *I = dyn_cast<Instruction>(V);
     if (!I) {
       // Non-instructions all dominate instructions, but not all constantexprs
       // can be executed unconditionally.
       if (ConstantExpr *C = dyn_cast<ConstantExpr>(V))
         if (C->canTrap())
           return false;
-    return true;
+      continue;
     }
     BasicBlock *PBB = I->getParent();
 
-  // We don't want to allow weird loops that might have the "if condition" in
-  // the bottom of this block.
     if (PBB == BB)
       return false;
 
     // If this instruction is defined in a block that contains an unconditional
     // branch to BB, then it must be in the 'conditional' part of the "if
     // statement".  If not, it definitely dominates the region.
     BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator());
     if (!BI || BI->isConditional() || BI->getSuccessor(0) != BB)
-    return true;
+      continue;
 
     // If we have seen this instruction before, don't count it again.
-  if (AggressiveInsts.count(I))
-    return true;
+    if (AggressiveInsts.contains(I))
+      continue;
 
     // Okay, it looks like the instruction IS in the "condition".  Check to
     // see if it's a cheap instruction to unconditionally compute, and if it
     // only uses stuff defined outside of the condition.  If so, hoist it out.
     if (!isSafeToSpeculativelyExecute(I))
       return false;
 
     Cost += computeSpeculationCost(I, TTI);
 
     // Allow exactly one instruction to be speculated regardless of its cost
     // (as long as it is safe to do so).
     // This is intended to flatten the CFG even if the instruction is a division
     // or other expensive operation. The speculation of an expensive instruction
     // is expected to be undone in CodeGenPrepare if the speculation has not
     // enabled further IR optimizations.
     if (Cost > Budget &&
-      (!SpeculateOneExpensiveInst || !AggressiveInsts.empty() || Depth > 0 ||
+        (!SpeculateOneExpensiveInst || !AggressiveInsts.empty() ||
          !Cost.isValid()))
             return false;
 
     // Okay, we can only really hoist these out if their operands do
     // not take us over the cost threshold.
     for (Use &Op : I->operands())
-    if (!dominatesMergePoint(Op, BB, AggressiveInsts, Cost, Budget, TTI,
-                             Depth + 1))
-      return false;
+      Stack.emplace_back(Op);
     // Okay, it's safe to do this!  Remember this instruction.
     AggressiveInsts.insert(I);
+  }
   return true;
 }
 
 /// Extract ConstantInt from value, looking through IntToPtr
 /// and PointerNullValue. Return NULL if value is not a constant int.
 static ConstantInt *GetConstantInt(Value *V, const DataLayout &DL) {
   // Normal constant int.
   ConstantInt *CI = dyn_cast<ConstantInt>(V);