From e8415fea4b4d21842dd5fed0827a41a73eeafb4b Mon Sep 17 00:00:00 2001
From: Nick Lewycky <nicholas@mxc.ca>
Date: Fri, 20 Jan 2012 08:35:20 +0000
Subject: Fix CountCodeReductionForAlloca to more accurately represent what
 SROA can and can't handle. Also don't produce non-zero results for things
 which won't be transformed by SROA at all just because we saw the
 loads/stores before we saw the use of the address.

llvm-svn: 148536
---
 llvm/lib/Analysis/InlineCost.cpp | 76 +++++++++++++++++++++++++++++++---------
 1 file changed, 60 insertions(+), 16 deletions(-)

(limited to 'llvm/lib/Analysis/InlineCost.cpp')

diff --git a/llvm/lib/Analysis/InlineCost.cpp b/llvm/lib/Analysis/InlineCost.cpp
index 226b4732a49..fb5861c7a19 100644
--- a/llvm/lib/Analysis/InlineCost.cpp
+++ b/llvm/lib/Analysis/InlineCost.cpp
@@ -221,23 +221,67 @@ unsigned CodeMetrics::CountCodeReductionForConstant(Value *V) {
 unsigned CodeMetrics::CountCodeReductionForAlloca(Value *V) {
   if (!V->getType()->isPointerTy()) return 0;  // Not a pointer
   unsigned Reduction = 0;
-  for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
-    Instruction *I = cast<Instruction>(*UI);
-    if (isa<LoadInst>(I) || isa<StoreInst>(I))
-      Reduction += InlineConstants::InstrCost;
-    else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
-      // If the GEP has variable indices, we won't be able to do much with it.
-      if (GEP->hasAllConstantIndices())
-        Reduction += CountCodeReductionForAlloca(GEP);
-    } else if (BitCastInst *BCI = dyn_cast<BitCastInst>(I)) {
-      // Track pointer through bitcasts.
-      Reduction += CountCodeReductionForAlloca(BCI);
-    } else {
-      // If there is some other strange instruction, we're not going to be able
-      // to do much if we inline this.
-      return 0;
+
+  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){
+      Instruction *I = cast<Instruction>(*UI);
+      if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
+        if (!LI->isSimple())
+          return 0;
+        Reduction += InlineConstants::InstrCost;
+      } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
+        if (!SI->isSimple())
+          return 0;
+        Reduction += InlineConstants::InstrCost;
+      } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
+        // If the GEP has variable indices, we won't be able to do much with it.
+        if (!GEP->hasAllConstantIndices())
+          return 0;
+        // A non-zero GEP will likely become a mask operation after SROA.
+        if (GEP->hasAllZeroIndices())
+          Reduction += InlineConstants::InstrCost;
+        Worklist.push_back(GEP);
+      } else if (BitCastInst *BCI = dyn_cast<BitCastInst>(I)) {
+        // Track pointer through bitcasts.
+        Worklist.push_back(BCI);
+        Reduction += InlineConstants::InstrCost;
+      } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
+        // SROA can handle a select of alloca iff all uses of the alloca are
+        // loads, and dereferenceable. We assume it's dereferenceable since
+        // we're told the input is an alloca.
+        for (Value::use_iterator UI = SI->use_begin(), UE = SI->use_end();
+             UI != UE; ++UI) {
+          LoadInst *LI = dyn_cast<LoadInst>(*UI);
+          if (LI == 0 || !LI->isSimple()) return 0;
+        }
+        // We don't know whether we'll be deleting the rest of the chain of
+        // instructions from the SelectInst on, because we don't know whether
+        // the other side of the select is also an alloca or not.
+        continue;
+      } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+        switch (II->getIntrinsicID()) {
+        default:
+          return 0;
+        case Intrinsic::memset:
+        case Intrinsic::memcpy:
+        case Intrinsic::memmove:
+        case Intrinsic::lifetime_start:
+        case Intrinsic::lifetime_end:
+	  // SROA can usually chew through these intrinsics.
+          Reduction += InlineConstants::InstrCost;
+          break;
+        }
+      } else {
+        // If there is some other strange instruction, we're not going to be
+        // able to do much if we inline this.
+        return 0;
+      }
     }
-  }
+  } while (!Worklist.empty());
 
   return Reduction;
 }
-- 
cgit v1.2.3