Improve isSafeToLoadUnconditionally to recognize that GEPs with constant

indices are safe if the result is known to be within the bounds of the
underlying object.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94829 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 83 insertions, 22 deletions

diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h
index f6d9f82d4a..321151802b 100644
--- a/include/llvm/Transforms/Utils/Local.h
+++ b/include/llvm/Transforms/Utils/Local.h
@@ -38,7 +38,8 @@ template<typename T> class SmallVectorImpl;
 /// from this value cannot trap.  If it is not obviously safe to load from the
 /// specified pointer, we do a quick local scan of the basic block containing
 /// ScanFrom, to determine if the address is already accessed.
-bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom);
+bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom,
+                                 const TargetData *TD = 0);
 
 //===----------------------------------------------------------------------===//
 //  Local constant propagation.
diff --git a/lib/Target/README.txt b/lib/Target/README.txt
index 716085cf1b..ce84cbb79d 100644
--- a/lib/Target/README.txt
+++ b/lib/Target/README.txt
@@ -1760,13 +1760,3 @@ entry:
 This function is equivalent to "ashr i32 %x, 5".  Testcase derived from gcc.
 
 //===---------------------------------------------------------------------===//
-
-isSafeToLoadUnconditionally should allow a GEP of a global/alloca with constant
-indicies within the bounds of the allocated object. Reduced example:
-
-const int a[] = {3,6};
-int b(int y) { int* x = y ? &a[0] : &a[1]; return *x; }
-
-All the loads should be eliminated.  Testcase derived from gcc.
-
-//===---------------------------------------------------------------------===//
diff --git a/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp b/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp
index ae728ddecf..306ed6728b 100644
--- a/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp
+++ b/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp
@@ -199,8 +199,8 @@ Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
     //
     if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
       // load (select (Cond, &V1, &V2))  --> select(Cond, load &V1, load &V2).
-      if (isSafeToLoadUnconditionally(SI->getOperand(1), SI) &&
-          isSafeToLoadUnconditionally(SI->getOperand(2), SI)) {
+      if (isSafeToLoadUnconditionally(SI->getOperand(1), SI, TD) &&
+          isSafeToLoadUnconditionally(SI->getOperand(2), SI, TD)) {
         Value *V1 = Builder->CreateLoad(SI->getOperand(1),
                                         SI->getOperand(1)->getName()+".val");
         Value *V2 = Builder->CreateLoad(SI->getOperand(2),
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index 292a4b311d..9c18452665 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -1650,7 +1650,8 @@ bool GVN::processNonLocalLoad(LoadInst *LI,
   // put anywhere; this can be improved, but should be conservatively safe.
   if (!allSingleSucc &&
       // FIXME: REEVALUTE THIS.
-      !isSafeToLoadUnconditionally(LoadPtr, UnavailablePred->getTerminator())) {
+      !isSafeToLoadUnconditionally(LoadPtr,
+                                   UnavailablePred->getTerminator(), TD)) {
     assert(NewInsts.empty() && "Should not have inserted instructions");
     return false;
   }
diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp
index 92bdf2de44..f0097d0362 100644
--- a/lib/Transforms/Utils/Local.cpp
+++ b/lib/Transforms/Utils/Local.cpp
@@ -38,20 +38,73 @@ using namespace llvm;
 //  Local analysis.
 //
 
+/// getUnderlyingObjectWithOffset - Strip off up to MaxLookup GEPs and
+/// bitcasts to get back to the underlying object being addressed, keeping
+/// track of the offset in bytes from the GEPs relative to the result.
+/// This is closely related to Value::getUnderlyingObject but is located
+/// here to avoid making VMCore depend on TargetData.
+static Value *getUnderlyingObjectWithOffset(Value *V, const TargetData *TD,
+                                            unsigned &ByteOffset,
+                                            unsigned MaxLookup = 6) {
+  if (!isa<PointerType>(V->getType()))
+    return V;
+  for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
+    if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
+      if (!GEP->hasAllConstantIndices())
+        return V;
+      SmallVector<Value*, 8> Indices(GEP->op_begin() + 1, GEP->op_end());
+      ByteOffset += TD->getIndexedOffset(GEP->getPointerOperandType(),
+                                         &Indices[0], Indices.size());
+      V = GEP->getPointerOperand();
+    } else if (Operator::getOpcode(V) == Instruction::BitCast) {
+      V = cast<Operator>(V)->getOperand(0);
+    } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
+      if (GA->mayBeOverridden())
+        return V;
+      V = GA->getAliasee();
+    } else {
+      return V;
+    }
+    assert(isa<PointerType>(V->getType()) && "Unexpected operand type!");
+  }
+  return V;
+}
+
 /// isSafeToLoadUnconditionally - Return true if we know that executing a load
 /// from this value cannot trap.  If it is not obviously safe to load from the
 /// specified pointer, we do a quick local scan of the basic block containing
 /// ScanFrom, to determine if the address is already accessed.
-bool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) {
-  // If it is an alloca it is always safe to load from.
-  if (isa<AllocaInst>(V)) return true;
+bool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom,
+                                       const TargetData *TD) {
+  unsigned ByteOffset = 0;
+  Value *Base = V;
+  if (TD)
+    Base = getUnderlyingObjectWithOffset(V, TD, ByteOffset);
+
+  const Type *BaseType = 0;
+  if (const AllocaInst *AI = dyn_cast<AllocaInst>(Base))
+    // If it is an alloca it is always safe to load from.
+    BaseType = AI->getAllocatedType();
+  else if (const GlobalValue *GV = dyn_cast<GlobalValue>(Base)) {
+    // Global variables are safe to load from but their size cannot be
+    // guaranteed if they are overridden.
+    if (!isa<GlobalAlias>(GV) && !GV->mayBeOverridden())
+      BaseType = GV->getType()->getElementType();
+  }
 
-  // If it is a global variable it is mostly safe to load from.
-  if (const GlobalValue *GV = dyn_cast<GlobalVariable>(V))
-    // Don't try to evaluate aliases.  External weak GV can be null.
-    return !isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage();
+  if (BaseType) {
+    if (!TD)
+      return true; // Loading directly from an alloca or global is OK.
+    if (BaseType->isSized()) {
+      // Check if the load is within the bounds of the underlying object.
+      const PointerType *AddrTy = cast<PointerType>(V->getType());
+      unsigned LoadSize = TD->getTypeStoreSize(AddrTy->getElementType());
+      if (ByteOffset + LoadSize <= TD->getTypeAllocSize(BaseType))
+        return true;
+    }
+  }
 
-  // Otherwise, be a little bit agressive by scanning the local block where we
+  // Otherwise, be a little bit aggressive by scanning the local block where we
   // want to check to see if the pointer is already being loaded or stored
   // from/to.  If so, the previous load or store would have already trapped,
   // so there is no harm doing an extra load (also, CSE will later eliminate
diff --git a/test/Transforms/InstCombine/load-select.ll b/test/Transforms/InstCombine/load-select.ll
new file mode 100644
index 0000000000..707d337e83
--- /dev/null
+++ b/test/Transforms/InstCombine/load-select.ll
@@ -0,0 +1,16 @@
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-p:32:32:32-i1:8:32-i8:8:32-i16:16:32-i32:32:32-i64:32:32-f32:32:32-f64:32:32-v64:64:64-v128:128:128-a0:0:32-n32"
+
+@a = constant [2 x i32] [i32 3, i32 6]            ; <[2 x i32]*> [#uses=2]
+
+define arm_apcscc i32 @b(i32 %y) nounwind readonly {
+; CHECK: @b
+; CHECK-NOT: load
+; CHECK: ret i32
+entry:
+  %0 = icmp eq i32 %y, 0                          ; <i1> [#uses=1]
+  %storemerge = select i1 %0, i32* getelementptr inbounds ([2 x i32]* @a, i32 0, i32 1), i32* getelementptr inbounds ([2 x i32]* @a, i32 0, i32 0) ; <i32*> [#uses=1]
+  %1 = load i32* %storemerge, align 4             ; <i32> [#uses=1]
+  ret i32 %1
+}