PHINode::getBasicBlockIndex is O(n) in the number of inputs

[oota-llvm.git] / lib / Transforms / Utils / Local.cpp

diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp
index f0097d0362c3328cde2adea5fb5fa7661dd48878..7e7973ae0b737b3cc76533cdc2103e039c00186e 100644 (file)
--- a/lib/Transforms/Utils/Local.cpp
+++ b/lib/Transforms/Utils/Local.cpp
@@ -44,7 +44,7 @@ using namespace llvm;
 /// 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,
+                                            uint64_t &ByteOffset,
                                             unsigned MaxLookup = 6) {
   if (!isa<PointerType>(V->getType()))
     return V;
@@ -75,31 +75,40 @@ static Value *getUnderlyingObjectWithOffset(Value *V, const TargetData *TD,
 /// 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,
-                                       const TargetData *TD) {
-  unsigned ByteOffset = 0;
+                                       unsigned Align, const TargetData *TD) {
+  uint64_t 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.
+  unsigned BaseAlign = 0;
+  if (const AllocaInst *AI = dyn_cast<AllocaInst>(Base)) {
+    // An alloca is safe to load from as load as it is suitably aligned.
     BaseType = AI->getAllocatedType();
-  else if (const GlobalValue *GV = dyn_cast<GlobalValue>(Base)) {
+    BaseAlign = AI->getAlignment();
+  } 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())
+    if (!isa<GlobalAlias>(GV) && !GV->mayBeOverridden()) {
       BaseType = GV->getType()->getElementType();
+      BaseAlign = GV->getAlignment();
+    }
   }
 
-  if (BaseType) {
-    if (!TD)
-      return true; // Loading directly from an alloca or global is OK.
-    if (BaseType->isSized()) {
+  if (BaseType && BaseType->isSized()) {
+    if (TD && BaseAlign == 0)
+      BaseAlign = TD->getPrefTypeAlignment(BaseType);
+
+    if (Align <= BaseAlign) {
+      if (!TD)
+        return true; // Loading directly from an alloca or global is OK.
+
       // 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))
+      uint64_t LoadSize = TD->getTypeStoreSize(AddrTy->getElementType());
+      if (ByteOffset + LoadSize <= TD->getTypeAllocSize(BaseType) &&
+          (Align == 0 || (ByteOffset % Align) == 0))
         return true;
     }
   }