From 3d1d895c866b76ac4d862301f36e2b95d803f0ab Mon Sep 17 00:00:00 2001
From: Chandler Carruth <chandlerc@gmail.com>
Date: Wed, 14 Mar 2012 07:32:53 +0000
Subject: [PATCH] Refactor the inline cost bonus calculation for constants to
 use a worklist rather than a recursive call.

No functionality changed.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152706 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/InlineCost.cpp | 46 +++++++++++++++++++++++++--------------------
 1 file changed, 26 insertions(+), 20 deletions(-)

diff --git a/lib/Analysis/InlineCost.cpp b/lib/Analysis/InlineCost.cpp
index 68d3d4676c2..f8d49a22a7f 100644
--- a/lib/Analysis/InlineCost.cpp
+++ b/lib/Analysis/InlineCost.cpp
@@ -165,18 +165,24 @@ void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB,
 unsigned InlineCostAnalyzer::FunctionInfo::countCodeReductionForConstant(
     const CodeMetrics &Metrics, Value *V) {
   unsigned Reduction = 0;
-  for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
-    User *U = *UI;
-    if (isa<BranchInst>(U) || isa<SwitchInst>(U)) {
-      // We will be able to eliminate all but one of the successors.
-      const TerminatorInst &TI = cast<TerminatorInst>(*U);
-      const unsigned NumSucc = TI.getNumSuccessors();
-      unsigned Instrs = 0;
-      for (unsigned I = 0; I != NumSucc; ++I)
-        Instrs += Metrics.NumBBInsts.lookup(TI.getSuccessor(I));
-      // We don't know which blocks will be eliminated, so use the average size.
-      Reduction += InlineConstants::InstrCost*Instrs*(NumSucc-1)/NumSucc;
-    } else {
+  SmallVector<Value *, 4> Worklist;
+  Worklist.push_back(V);
+  do {
+    Value *V = Worklist.pop_back_val();
+    for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
+      User *U = *UI;
+      if (isa<BranchInst>(U) || isa<SwitchInst>(U)) {
+        // We will be able to eliminate all but one of the successors.
+        const TerminatorInst &TI = cast<TerminatorInst>(*U);
+        const unsigned NumSucc = TI.getNumSuccessors();
+        unsigned Instrs = 0;
+        for (unsigned I = 0; I != NumSucc; ++I)
+          Instrs += Metrics.NumBBInsts.lookup(TI.getSuccessor(I));
+        // We don't know which blocks will be eliminated, so use the average size.
+        Reduction += InlineConstants::InstrCost*Instrs*(NumSucc-1)/NumSucc;
+        continue;
+      }
+
       // Figure out if this instruction will be removed due to simple constant
       // propagation.
       Instruction &Inst = cast<Instruction>(*U);
@@ -198,17 +204,17 @@ unsigned InlineCostAnalyzer::FunctionInfo::countCodeReductionForConstant(
           AllOperandsConstant = false;
           break;
         }
+      if (!AllOperandsConstant)
+        continue;
 
-      if (AllOperandsConstant) {
-        // We will get to remove this instruction...
-        Reduction += InlineConstants::InstrCost;
+      // We will get to remove this instruction...
+      Reduction += InlineConstants::InstrCost;
 
-        // And any other instructions that use it which become constants
-        // themselves.
-        Reduction += countCodeReductionForConstant(Metrics, &Inst);
-      }
+      // And any other instructions that use it which become constants
+      // themselves.
+      Worklist.push_back(&Inst);
     }
-  }
+  } while (!Worklist.empty());
   return Reduction;
 }
 
-- 
2.11.0