Factor out Instruction::isSafeToSpeculativelyExecute's code for

testing for dereferenceable pointers into a helper function,
isDereferenceablePointer.  Teach it how to reason about GEPs
with simple non-zero indices.

Also eliminate ArgumentPromtion's IsAlwaysValidPointer,
which didn't check for weak externals or out of range gep
indices.

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

diff --git a/include/llvm/Value.h b/include/llvm/Value.h
index 8740f353ab5188d4e591cd9f7cbb4935f9df6cb2..8dc4105b9e4c0bf16773c8fce10316e1e253a8a3 100644 (file)
--- a/include/llvm/Value.h
+++ b/include/llvm/Value.h
@@ -294,6 +294,10 @@ public:
   const Value *getUnderlyingObject(unsigned MaxLookup = 6) const {
     return const_cast<Value*>(this)->getUnderlyingObject(MaxLookup);
   }
+
+  /// isDereferenceablePointer - Test if this value is always a pointer to
+  /// allocated and suitably aligned memory for a simple load or store.
+  bool isDereferenceablePointer() const;
   
   /// DoPHITranslation - If this value is a PHI node with CurBB as its parent,
   /// return the value in the PHI node corresponding to PredBB.  If not, return

diff --git a/lib/Transforms/IPO/ArgumentPromotion.cpp b/lib/Transforms/IPO/ArgumentPromotion.cpp
index 78d9f1816e48923cedd2acfdd591c32a4652433e..fe30381170dc5006fbf2080a98ef2b9f360c2bc5 100644 (file)
--- a/lib/Transforms/IPO/ArgumentPromotion.cpp
+++ b/lib/Transforms/IPO/ArgumentPromotion.cpp
@@ -188,19 +188,6 @@ CallGraphNode *ArgPromotion::PromoteArguments(CallGraphNode *CGN) {
   return DoPromotion(F, ArgsToPromote, ByValArgsToTransform);
 }
 
-/// IsAlwaysValidPointer - Return true if the specified pointer is always legal
-/// to load.
-static bool IsAlwaysValidPointer(Value *V) {
-  if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true;
-  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V))
-    return IsAlwaysValidPointer(GEP->getOperand(0));
-  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
-    if (CE->getOpcode() == Instruction::GetElementPtr)
-      return IsAlwaysValidPointer(CE->getOperand(0));
-
-  return false;
-}
-
 /// AllCalleesPassInValidPointerForArgument - Return true if we can prove that
 /// all callees pass in a valid pointer for the specified function argument.
 static bool AllCalleesPassInValidPointerForArgument(Argument *Arg) {
@@ -216,7 +203,7 @@ static bool AllCalleesPassInValidPointerForArgument(Argument *Arg) {
     CallSite CS(*UI);
     assert(CS && "Should only have direct calls!");
 
-    if (!IsAlwaysValidPointer(CS.getArgument(ArgNo)))
+    if (!CS.getArgument(ArgNo)->isDereferenceablePointer())
       return false;
   }
   return true;

diff --git a/lib/VMCore/Instruction.cpp b/lib/VMCore/Instruction.cpp
index 05bed4c64316fa77e406ec96153c6ccd0c700bd0..fdddba988c3d133c751089637bd130baf0ee5a31 100644 (file)
--- a/lib/VMCore/Instruction.cpp
+++ b/lib/VMCore/Instruction.cpp
@@ -398,25 +398,10 @@ bool Instruction::isSafeToSpeculativelyExecute() const {
     return Op && !Op->isNullValue() && !Op->isAllOnesValue();
   }
   case Load: {
-    if (cast<LoadInst>(this)->isVolatile())
+    const LoadInst *LI = cast<LoadInst>(this);
+    if (LI->isVolatile())
       return false;
-    // Note that it is not safe to speculate into a malloc'd region because
-    // malloc may return null.
-    // It's also not safe to follow a bitcast, for example:
-    //   bitcast i8* (alloca i8) to i32*
-    // would result in a 4-byte load from a 1-byte alloca.
-    Value *Op0 = getOperand(0);
-    if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op0)) {
-      // TODO: it's safe to do this for any GEP with constant indices that
-      // compute inside the allocated type, but not for any inbounds gep.
-      if (GEP->hasAllZeroIndices())
-        Op0 = GEP->getPointerOperand();
-    }
-    if (isa<AllocaInst>(Op0))
-      return true;
-    if (GlobalVariable *GV = dyn_cast<GlobalVariable>(getOperand(0)))
-      return !GV->hasExternalWeakLinkage();
-    return false;
+    return LI->getPointerOperand()->isDereferenceablePointer();
   }
   case Call:
     return false; // The called function could have undefined behavior or

diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp
index b8c677565467a6d56cb107faf5401bdee33b44be..d5e39979608d1f431412d5cdff30783810b5bb87 100644 (file)
--- a/lib/VMCore/Value.cpp
+++ b/lib/VMCore/Value.cpp
@@ -22,6 +22,7 @@
 #include "llvm/ValueSymbolTable.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/GetElementPtrTypeIterator.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/LeakDetector.h"
 #include "llvm/Support/ManagedStatic.h"
@@ -366,6 +367,60 @@ Value *Value::getUnderlyingObject(unsigned MaxLookup) {
   return V;
 }
 
+/// isDereferenceablePointer - Test if this value is always a pointer to
+// allocated and suitably aligned memory for a simple load or store.
+bool Value::isDereferenceablePointer() const {
+  // Note that it is not safe to speculate into a malloc'd region because
+  // malloc may return null.
+  // It's also not always safe to follow a bitcast, for example:
+  //   bitcast i8* (alloca i8) to i32*
+  // would result in a 4-byte load from a 1-byte alloca. Some cases could
+  // be handled using TargetData to check sizes and alignments though.
+
+  // These are obviously ok.
+  if (isa<AllocaInst>(this)) return true;
+
+  // Global variables which can't collapse to null are ok.
+  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(this))
+    return !GV->hasExternalWeakLinkage();
+
+  // For GEPs, determine if the indexing lands within the allocated object.
+  if (const GEPOperator *GEP = dyn_cast<GEPOperator>(this)) {
+    // Conservatively require that the base pointer be fully dereferenceable.
+    if (!GEP->getOperand(0)->isDereferenceablePointer())
+      return false;
+    // Check the indices.
+    gep_type_iterator GTI = gep_type_begin(GEP);
+    for (User::const_op_iterator I = GEP->op_begin()+1,
+         E = GEP->op_end(); I != E; ++I) {
+      Value *Index = *I;
+      const Type *Ty = *GTI++;
+      // Struct indices can't be out of bounds.
+      if (isa<StructType>(Ty))
+        continue;
+      ConstantInt *CI = dyn_cast<ConstantInt>(Index);
+      if (!CI)
+        return false;
+      // Zero is always ok.
+      if (CI->isZero())
+        continue;
+      // Check to see that it's within the bounds of an array.
+      const ArrayType *ATy = dyn_cast<ArrayType>(Ty);
+      if (!ATy)
+        return false;
+      if (CI->getValue().getActiveBits() > 64)
+        return false;
+      if (CI->getZExtValue() >= ATy->getNumElements())
+        return false;
+    }
+    // Indices check out; this is dereferenceable.
+    return true;
+  }
+
+  // If we don't know, assume the worst.
+  return false;
+}
+
 /// DoPHITranslation - If this value is a PHI node with CurBB as its parent,
 /// return the value in the PHI node corresponding to PredBB.  If not, return
 /// ourself.  This is useful if you want to know the value something has in a

diff --git a/test/Transforms/SimplifyCFG/speculate-with-offset.ll b/test/Transforms/SimplifyCFG/speculate-with-offset.ll
new file mode 100644 (file)
index 0000000..a737d56
--- /dev/null
+++ b/test/Transforms/SimplifyCFG/speculate-with-offset.ll
@@ -0,0 +1,94 @@
+; RUN: opt -simplifycfg -S < %s | FileCheck %s
+
+; This load is safe to speculate, as it's from a safe offset
+; within an alloca.
+
+; CHECK: @yes
+; CHECK-NOT: br
+
+define void @yes(i1 %c) nounwind {
+entry:
+  %a = alloca [4 x i64*], align 8
+  %__a.addr = getelementptr [4 x i64*]* %a, i64 0, i64 3
+  call void @frob(i64** %__a.addr)
+  br i1 %c, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %tmp5 = load i64** %__a.addr, align 8
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %storemerge = phi i64* [ undef, %if.then ], [ %tmp5, %if.end ]
+  ret void
+}
+
+; CHECK: @no0
+; CHECK: br i1 %c
+
+define void @no0(i1 %c) nounwind {
+entry:
+  %a = alloca [4 x i64*], align 8
+  %__a.addr = getelementptr [4 x i64*]* %a, i64 0, i64 4
+  call void @frob(i64** %__a.addr)
+  br i1 %c, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %tmp5 = load i64** %__a.addr, align 8
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %storemerge = phi i64* [ undef, %if.then ], [ %tmp5, %if.end ]
+  ret void
+}
+
+; CHECK: @no1
+; CHECK: br i1 %c
+
+define void @no1(i1 %c, i64 %n) nounwind {
+entry:
+  %a = alloca [4 x i64*], align 8
+  %__a.addr = getelementptr [4 x i64*]* %a, i64 0, i64 %n
+  call void @frob(i64** %__a.addr)
+  br i1 %c, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %tmp5 = load i64** %__a.addr, align 8
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %storemerge = phi i64* [ undef, %if.then ], [ %tmp5, %if.end ]
+  ret void
+}
+
+; CHECK: @no2
+; CHECK: br i1 %c
+
+define void @no2(i1 %c, i64 %n) nounwind {
+entry:
+  %a = alloca [4 x i64*], align 8
+  %__a.addr = getelementptr [4 x i64*]* %a, i64 1, i64 0
+  call void @frob(i64** %__a.addr)
+  br i1 %c, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %tmp5 = load i64** %__a.addr, align 8
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %storemerge = phi i64* [ undef, %if.then ], [ %tmp5, %if.end ]
+  ret void
+}
+
+declare void @frob(i64** nocapture %p)