Exploit dereferenceable_or_null attribute in LICM pass

[apilipenko]

Summary

Allow hoisting of loads from values marked with dereferenceable_or_null attribute. For values marked with the attribute perform context-sensitive analysis to determine whether it's known-non-null or not.

By now context-sensitive non-null analysis is implemented in two different ways: using LazyValueInfo and using dominating conditions. I don't know which one is better, so it's up for discussion.

[sanjoy]

After going through the LazyValueInfo code, I cannot easily think of a case where walking dominating uses will be more powerful than LVI. Do you have such an example? If not, then I think we should just use LVI.

[apilipenko]

In D9253#163644, @sanjoy wrote:

After going through the LazyValueInfo code, I cannot easily think of a case where walking dominating uses will be more powerful than LVI. Do you have such an example? If not, then I think we should just use LVI.

LVI is definitely more powerful. The concern about LVI is that it's expensive analysis and when used widely can affect compilation time. Dominating uses is much simple and covers most of the explicit null checks.

[sanjoy]

I meant to get to this after your reply, but I somehow forgot. Sorry for that!

I'd say you should split out the LVI related to changes into a later patch. That later LVI change should come with test cases that show when it is more powerful than the domtree based approach. Given our use cases, I suspect LVI won't be necessary.

Other than that, I'm okay with this patch (the domtree part). There may be some concerns about compile time, but impact on compile time should not affect anyone not generating dereferenceable_or_null values. I don't want to LGTM it at this point only because

a. I want to have a look at the final version of the patch, without the `getDereferenceableOrNullBytes` accessors or the LVI dependency, before an LGTM
b. Even after (a), I think we should wait on at least one other review to take a look

include/llvm/IR/Argument.h

71 ↗

(On Diff #24384)

Given that these are simple getters and are basically extensions of r235132, I think they can go in without further review. Same applies to changes in CallSite.h, Function.h and Instructions.h. One way to do this would be to split these out as a separate review (and remove them from this one) and we can independently LGTM that one and check it in.

[apilipenko]

Missing dereferenceable_or_null getters are separated to another review (http://reviews.llvm.org/D9499). LVI changes removed.

[hfinkel]

include/llvm/Analysis/ValueTracking.h

239 ↗

(On Diff #24957)

return -> returns

244 ↗

(On Diff #24957)

What does this comment mean? It is saying anything nonobvious/nontrivial?

[reames]

I'm not particularly worried about compile time w.r.t. this patch. The much more invasive version of this in ValueTracking appears to be a non-issue. (Which reminds me, I need to actually enable that!)

With the current round of comments addressed (two comments, one bug fix), I'm willing to sign off on this. We've had plenty of time for interested reviewers to take a look and three different people have looked at it. Not sure what else we could wait for. :)

lib/Analysis/ValueTracking.cpp

3175 ↗

(On Diff #24957)

Er, the use can definitely be not a branch instruction. I think you're missing:
if (!BI) continue;

Add a test case which covers this please.

lib/Transforms/Scalar/LICM.cpp

645 ↗

(On Diff #24957)

This comment is now stale. Possibly:
// If it is not a trapping instruction, it is always safe to hoist. If the instruction is known not to trap when moved to the preheader, it is also safe to hoist.

[apilipenko]

include/llvm/Analysis/ValueTracking.h

244 ↗

(On Diff #24957)

That is the comment from original function description. I left it to say that this function can perform context insensitive analysis. Any suggestions for better wording?

[apilipenko]

Review findings addressed.

[reames]

LGTM w/final comments addressed. Would you like me to commit this for you?

include/llvm/Analysis/ValueTracking.h

244 ↗

(On Diff #24957)

Given this is the original comment describing the unchanged behaviour, I think you can leave it as is. If Hal disagrees, we can revise this in a separate change.

lib/Analysis/ValueTracking.cpp

3175 ↗

(On Diff #25048)

I'd prefer you use an early continue here rather than increase the nesting depth.

test/Transforms/LICM/hoist-deref-load.ll

226 ↗

(On Diff #25048)

Please remove any unnecessary attributes. Sorry for not noticing that before.

[apilipenko]

test/Transforms/LICM/hoist-deref-load.ll

226 ↗

(On Diff #25048)

Does it makes sense to remove them from existing test cases as well?

[apilipenko]

Review findings fixed.

[apilipenko]

In D9253#166890, @reames wrote:

LGTM w/final comments addressed. Would you like me to commit this for you?

Yes, please.

[reames]

Artur, when applying the patch I'm getting merge conflicts. They look simple, but I'd prefer you rebase just to make sure I don't make any mistakes while resolving them. You have more of the context than I do.

[apilipenko]

Rebased patch.

llvm/trunk/include/llvm/Analysis/ValueTracking.h

namespace llvm {
   void GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
                             const DataLayout &DL, LoopInfo *LI = nullptr,
                             unsigned MaxLookup = 6);
 
   /// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer
   /// are lifetime markers.
   bool onlyUsedByLifetimeMarkers(const Value *V);
 
-  /// isDereferenceablePointer - Return true if this is always a dereferenceable 
-  /// pointer.
-  ///
-  /// Test if this value is always a pointer to allocated and suitably aligned
-  /// memory for a simple load or store.
-  bool isDereferenceablePointer(const Value *V, const DataLayout &DL);
+  /// isDereferenceablePointer - Return true if this is always a dereferenceable
+  /// pointer. If the context instruction is specified perform context-sensitive
+  /// analysis and return true if the pointer is dereferenceable at the
+  /// specified instruction.
+  bool isDereferenceablePointer(const Value *V, const DataLayout &DL,
+                                const Instruction *CtxI = nullptr,
+                                const DominatorTree *DT = nullptr,
+                                const TargetLibraryInfo *TLI = nullptr);
   
   /// isSafeToSpeculativelyExecute - Return true if the instruction does not
   /// have any effects besides calculating the result and does not have
   /// undefined behavior.
   ///
   /// This method never returns true for an instruction that returns true for
   /// mayHaveSideEffects; however, this method also does some other checks in
   /// addition. It checks for undefined behavior, like dividing by zero or
   /// loading from an invalid pointer (but not for undefined results, like a
   /// shift with a shift amount larger than the width of the result). It checks
   /// for malloc and alloca because speculatively executing them might cause a
   /// memory leak. It also returns false for instructions related to control
   /// flow, specifically terminators and PHI nodes.
   ///
-  /// This method only looks at the instruction itself and its operands, so if
-  /// this method returns true, it is safe to move the instruction as long as
-  /// the correct dominance relationships for the operands and users hold.
-  /// However, this method can return true for instructions that read memory;
+  /// If the CtxI is specified this method performs context-sensitive analysis
+  /// and returns true if it is safe to execute the instruction immediately
+  /// before the CtxI.
+  ///
+  /// If the CtxI is NOT specified this method only looks at the instruction
+  /// itself and its operands, so if this method returns true, it is safe to
+  /// move the instruction as long as the correct dominance relationships for
+  /// the operands and users hold.
+  ///
+  /// This method can return true for instructions that read memory;
   /// for such instructions, moving them may change the resulting value.
-  bool isSafeToSpeculativelyExecute(const Value *V);
+  bool isSafeToSpeculativelyExecute(const Value *V,
+                                    const Instruction *CtxI = nullptr,
+                                    const DominatorTree *DT = nullptr,
+                                    const TargetLibraryInfo *TLI = nullptr);
 
   /// isKnownNonNull - Return true if this pointer couldn't possibly be null by
   /// its definition.  This returns true for allocas, non-extern-weak globals
   /// and byval arguments.
   bool isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI = nullptr);
 
+  /// isKnownNonNullAt - Return true if this pointer couldn't possibly be null.
+  /// If the context instruction is specified perform context-sensitive analysis
+  /// and return true if the pointer couldn't possibly be null at the specified
+  /// instruction.
+  bool isKnownNonNullAt(const Value *V,
+                        const Instruction *CtxI = nullptr,
+                        const DominatorTree *DT  = nullptr,
+                        const TargetLibraryInfo *TLI = nullptr);
+
   /// Return true if it is valid to use the assumptions provided by an
   /// assume intrinsic, I, at the point in the control-flow identified by the
   /// context instruction, CxtI.
   bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
                                const DominatorTree *DT = nullptr);
 
   enum class OverflowResult { AlwaysOverflows, MayOverflow, NeverOverflows };
   OverflowResult computeOverflowForUnsignedMul(Value *LHS, Value *RHS,

llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h

bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
                 LICMSafetyInfo *);
 
 /// \brief Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
-/// TargetLibraryInfo, Loop, AliasSet information for all instructions of the 
+/// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 /// loop and loop safety information as arguments. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
                  LICMSafetyInfo *);
 
-/// \brief Try to promote memory values to scalars by sinking stores out of 
+/// \brief Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are 
 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
 /// AliasSet information for all instructions of the loop and loop safety 
 /// information as arguments. It returns changed status.
 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &,
                                   SmallVectorImpl<Instruction*> &,

llvm/trunk/lib/Analysis/ValueTracking.cpp

for (const User *U : V->users()) {
     if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
         II->getIntrinsicID() != Intrinsic::lifetime_end)
       return false;
   }
   return true;
 }
 
 static bool isDereferenceableFromAttribute(const Value *BV, APInt Offset,
-                                           Type *Ty, const DataLayout &DL) {
+                                           Type *Ty, const DataLayout &DL,
+                                           const Instruction *CtxI,
+                                           const DominatorTree *DT,
+                                           const TargetLibraryInfo *TLI) {
   assert(Offset.isNonNegative() && "offset can't be negative");
   assert(Ty->isSized() && "must be sized");
   
   APInt DerefBytes(Offset.getBitWidth(), 0);
+  bool CheckForNonNull = false;
   if (const Argument *A = dyn_cast<Argument>(BV)) {
     DerefBytes = A->getDereferenceableBytes();
+    if (!DerefBytes.getBoolValue()) {
+      DerefBytes = A->getDereferenceableOrNullBytes();
+      CheckForNonNull = true;
+    }
   } else if (auto CS = ImmutableCallSite(BV)) {
     DerefBytes = CS.getDereferenceableBytes(0);
+    if (!DerefBytes.getBoolValue()) {
+      DerefBytes = CS.getDereferenceableOrNullBytes(0);
+      CheckForNonNull = true;
+    }
   }
   
   if (DerefBytes.getBoolValue())
     if (DerefBytes.uge(Offset + DL.getTypeStoreSize(Ty)))
+      if (!CheckForNonNull || isKnownNonNullAt(BV, CtxI, DT, TLI))
         return true;
-  
   return false;
 }
 
-static bool isDereferenceableFromAttribute(const Value *V, 
-                                           const DataLayout &DL) {
+static bool isDereferenceableFromAttribute(const Value *V, const DataLayout &DL,
+                                           const Instruction *CtxI,
+                                           const DominatorTree *DT,
+                                           const TargetLibraryInfo *TLI) {
   Type *VTy = V->getType();
   Type *Ty = VTy->getPointerElementType();
   if (!Ty->isSized())
     return false;
   
   APInt Offset(DL.getTypeStoreSizeInBits(VTy), 0);
-  return isDereferenceableFromAttribute(V, Offset, Ty, DL);
+  return isDereferenceableFromAttribute(V, Offset, Ty, DL, CtxI, DT, TLI);
 }
 
 /// Return true if Value is always a dereferenceable pointer.
 ///
 /// Test if V is always a pointer to allocated and suitably aligned memory for
 /// a simple load or store.
 static bool isDereferenceablePointer(const Value *V, const DataLayout &DL,
+                                     const Instruction *CtxI,
+                                     const DominatorTree *DT,
+                                     const TargetLibraryInfo *TLI,
                                      SmallPtrSetImpl<const Value *> &Visited) {
   // Note that it is not safe to speculate into a malloc'd region because
   // malloc may return null.
 
   // These are obviously ok.
   if (isa<AllocaInst>(V)) return true;
 
   // It's 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. However,
   // if we're casting from a pointer from a type of larger size
   // to a type of smaller size (or the same size), and the alignment
   // is at least as large as for the resulting pointer type, then
   // we can look through the bitcast.
   if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) {
     Type *STy = BC->getSrcTy()->getPointerElementType(),
          *DTy = BC->getDestTy()->getPointerElementType();
     if (STy->isSized() && DTy->isSized() &&
         (DL.getTypeStoreSize(STy) >= DL.getTypeStoreSize(DTy)) &&
         (DL.getABITypeAlignment(STy) >= DL.getABITypeAlignment(DTy)))
-      return isDereferenceablePointer(BC->getOperand(0), DL, Visited);
+      return isDereferenceablePointer(BC->getOperand(0), DL, CtxI,
+                                      DT, TLI, Visited);
   }
 
   // Global variables which can't collapse to null are ok.
   if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
     return !GV->hasExternalWeakLinkage();
 
   // byval arguments are okay.
   if (const Argument *A = dyn_cast<Argument>(V))
     if (A->hasByValAttr())
       return true;
     
-  if (isDereferenceableFromAttribute(V, DL))
+  if (isDereferenceableFromAttribute(V, DL, CtxI, DT, TLI))
     return true;
 
   // For GEPs, determine if the indexing lands within the allocated object.
   if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
     // Conservatively require that the base pointer be fully dereferenceable.
     if (!Visited.insert(GEP->getOperand(0)).second)
       return false;
-    if (!isDereferenceablePointer(GEP->getOperand(0), DL, Visited))
+    if (!isDereferenceablePointer(GEP->getOperand(0), DL, CtxI,
+                                  DT, TLI, Visited))
       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;
       Type *Ty = *GTI++;
       // Struct indices can't be out of bounds.
if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
     // Indices check out; this is dereferenceable.
     return true;
   }
 
   // For gc.relocate, look through relocations
   if (const IntrinsicInst *I = dyn_cast<IntrinsicInst>(V))
     if (I->getIntrinsicID() == Intrinsic::experimental_gc_relocate) {
       GCRelocateOperands RelocateInst(I);
-      return isDereferenceablePointer(RelocateInst.getDerivedPtr(), DL,
-                                      Visited);
+      return isDereferenceablePointer(RelocateInst.getDerivedPtr(), DL, CtxI,
+                                      DT, TLI, Visited);
     }
 
   if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
-    return isDereferenceablePointer(ASC->getOperand(0), DL, Visited);
+    return isDereferenceablePointer(ASC->getOperand(0), DL, CtxI,
+                                    DT, TLI, Visited);
 
   // If we don't know, assume the worst.
   return false;
 }
 
-bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL) {
+bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL,
+                                    const Instruction *CtxI,
+                                    const DominatorTree *DT,
+                                    const TargetLibraryInfo *TLI) {
   // When dereferenceability information is provided by a dereferenceable
   // attribute, we know exactly how many bytes are dereferenceable. If we can
   // determine the exact offset to the attributed variable, we can use that
   // information here.
   Type *VTy = V->getType();
   Type *Ty = VTy->getPointerElementType();
   if (Ty->isSized()) {
     APInt Offset(DL.getTypeStoreSizeInBits(VTy), 0);
     const Value *BV = V->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
     
     if (Offset.isNonNegative())
-      if (isDereferenceableFromAttribute(BV, Offset, Ty, DL))
+      if (isDereferenceableFromAttribute(BV, Offset, Ty, DL,
+                                         CtxI, DT, TLI))
         return true;
   }
 
   SmallPtrSet<const Value *, 32> Visited;
-  return ::isDereferenceablePointer(V, DL, Visited);
+  return ::isDereferenceablePointer(V, DL, CtxI, DT, TLI, Visited);
 }
 
-bool llvm::isSafeToSpeculativelyExecute(const Value *V) {
+bool llvm::isSafeToSpeculativelyExecute(const Value *V,
+                                        const Instruction *CtxI,
+                                        const DominatorTree *DT,
+                                        const TargetLibraryInfo *TLI) {
   const Operator *Inst = dyn_cast<Operator>(V);
   if (!Inst)
     return false;
 
   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
     if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i)))
       if (C->canTrap())
         return false;
bool llvm::isSafeToSpeculativelyExecute(const Value *V,
   }
   case Instruction::Load: {
     const LoadInst *LI = cast<LoadInst>(Inst);
     if (!LI->isUnordered() ||
         // Speculative load may create a race that did not exist in the source.
         LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeThread))
       return false;
     const DataLayout &DL = LI->getModule()->getDataLayout();
-    return isDereferenceablePointer(LI->getPointerOperand(), DL);
+    return isDereferenceablePointer(LI->getPointerOperand(), DL, CtxI, DT, TLI);
   }
   case Instruction::Call: {
     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
       switch (II->getIntrinsicID()) {
       // These synthetic intrinsics have no side-effects and just mark
       // information about their operands.
       // FIXME: There are other no-op synthetic instructions that potentially
       // should be considered at least *safe* to speculate...
bool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) {
 
   // operator new never returns null.
   if (isOperatorNewLikeFn(V, TLI, /*LookThroughBitCast=*/true))
     return true;
 
   return false;
 }
 
+static bool isKnownNonNullFromDominatingCondition(const Value *V,
+                                                  const Instruction *CtxI,
+                                                  const DominatorTree *DT) {
+  unsigned NumUsesExplored = 0;
+  for (auto U : V->users()) {
+    // Avoid massive lists
+    if (NumUsesExplored >= DomConditionsMaxUses)
+      break;
+    NumUsesExplored++;
+    // Consider only compare instructions uniquely controlling a branch
+    const ICmpInst *Cmp = dyn_cast<ICmpInst>(U);
+    if (!Cmp)
+      continue;
+
+    if (DomConditionsSingleCmpUse && !Cmp->hasOneUse())
+      continue;
+
+    for (auto *CmpU : Cmp->users()) {
+      const BranchInst *BI = dyn_cast<BranchInst>(CmpU);
+      if (!BI)
+        continue;
+      
+      assert(BI->isConditional() && "uses a comparison!");
+
+      BasicBlock *NonNullSuccessor = nullptr;
+      CmpInst::Predicate Pred;
+
+      if (match(const_cast<ICmpInst*>(Cmp),
+                m_c_ICmp(Pred, m_Specific(V), m_Zero()))) {
+        if (Pred == ICmpInst::ICMP_EQ)
+          NonNullSuccessor = BI->getSuccessor(1);
+        else if (Pred == ICmpInst::ICMP_NE)
+          NonNullSuccessor = BI->getSuccessor(0);
+      }
+
+      if (NonNullSuccessor) {
+        BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
+        if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
+          return true;
+      }
+    }
+  }
+
+  return false;
+}
+
+bool llvm::isKnownNonNullAt(const Value *V, const Instruction *CtxI,
+                   const DominatorTree *DT, const TargetLibraryInfo *TLI) {
+  if (isKnownNonNull(V, TLI))
+    return true;
+
+  return CtxI ? ::isKnownNonNullFromDominatingCondition(V, CtxI, DT) : false;
+}
+
 OverflowResult llvm::computeOverflowForUnsignedMul(Value *LHS, Value *RHS,
                                                    const DataLayout &DL,
                                                    AssumptionCache *AC,
                                                    const Instruction *CxtI,
                                                    const DominatorTree *DT) {
   // Multiplying n * m significant bits yields a result of n + m significant
   // bits. If the total number of significant bits does not exceed the
   // result bit width (minus 1), there is no overflow.

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
                  const Loop *CurLoop, AliasSetTracker *CurAST );
 static bool isGuaranteedToExecute(const Instruction &Inst,
                                   const DominatorTree *DT,
                                   const Loop *CurLoop,
                                   const LICMSafetyInfo *SafetyInfo);
 static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
                                            const DominatorTree *DT,
+                                           const TargetLibraryInfo *TLI,
                                            const Loop *CurLoop,
                                            const LICMSafetyInfo *SafetyInfo);
 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
                                      const AAMDNodes &AAInfo, 
                                      AliasSetTracker *CurAST);
 static Instruction *CloneInstructionInExitBlock(const Instruction &I,
                                                 BasicBlock &ExitBlock,
                                                 PHINode &PN,
                                                 const LoopInfo *LI);
 static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA,
-                               DominatorTree *DT, Loop *CurLoop,
-                               AliasSetTracker *CurAST,
+                               DominatorTree *DT, TargetLibraryInfo *TLI,
+                               Loop *CurLoop, AliasSetTracker *CurAST,
                                LICMSafetyInfo *SafetyInfo);
 
 namespace {
   struct LICM : public LoopPass {
     static char ID; // Pass identification, replacement for typeid
     LICM() : LoopPass(ID) {
       initializeLICMPass(*PassRegistry::getPassRegistry());
     }
for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) {
     }
 
     // Check to see if we can sink this instruction to the exit blocks
     // of the loop.  We can do this if the all users of the instruction are
     // outside of the loop.  In this case, it doesn't even matter if the
     // operands of the instruction are loop invariant.
     //
     if (isNotUsedInLoop(I, CurLoop) &&
-        canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo)) {
+        canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) {
       ++II;
       Changed |= sink(I, LI, DT, CurLoop, CurAST);
     }
   }
   return Changed;
 }
 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) {
         continue;
       }
 
       // Try hoisting the instruction out to the preheader.  We can only do this
       // if all of the operands of the instruction are loop invariant and if it
       // is safe to hoist the instruction.
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
-          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo) &&
-          isSafeToExecuteUnconditionally(I, DT, CurLoop, SafetyInfo))
+          canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
+          isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo))
         Changed |= hoist(I, CurLoop->getLoopPreheader());
     }
 
   const std::vector<DomTreeNode*> &Children = N->getChildren();
   for (unsigned i = 0, e = Children.size(); i != e; ++i)
     Changed |=
         hoistRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
   return Changed;
for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end();
          (I != E) && !SafetyInfo->MayThrow; ++I)
       SafetyInfo->MayThrow |= I->mayThrow();
 }
 
 /// canSinkOrHoistInst - Return true if the hoister and sinker can handle this
 /// instruction.
 ///
 bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT,
-                        Loop *CurLoop, AliasSetTracker *CurAST,
-                        LICMSafetyInfo *SafetyInfo) {
+                        TargetLibraryInfo *TLI, Loop *CurLoop,
+                        AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
   // Loads have extra constraints we have to verify before we can hoist them.
   if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     if (!LI->isUnordered())
       return false;        // Don't hoist volatile/atomic loads!
 
     // Loads from constant memory are always safe to move, even if they end up
     // in the same alias set as something that ends up being modified.
     if (AA->pointsToConstantMemory(LI->getOperand(0)))
bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT,
   // Only these instructions are hoistable/sinkable.
   if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) &&
       !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) &&
       !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) &&
       !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) &&
       !isa<InsertValueInst>(I))
     return false;
 
-  return isSafeToExecuteUnconditionally(I, DT, CurLoop, SafetyInfo);
+  return isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo);
 }
 
 /// Returns true if a PHINode is a trivially replaceable with an
 /// Instruction.
 /// This is true when all incoming values are that instruction.
 /// This pattern occurs most often with LCSSA PHI nodes.
 ///
 static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) {
static bool hoist(Instruction &I, BasicBlock *Preheader) {
   I.moveBefore(Preheader->getTerminator());
 
   if (isa<LoadInst>(I)) ++NumMovedLoads;
   else if (isa<CallInst>(I)) ++NumMovedCalls;
   ++NumHoisted;
   return true;
 }
 
-/// Only sink or hoist an instruction if it is not a trapping instruction
+/// Only sink or hoist an instruction if it is not a trapping instruction,
+/// or if the instruction is known not to trap when moved to the preheader.
 /// or if it is a trapping instruction and is guaranteed to execute.
-///
-static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
+static bool isSafeToExecuteUnconditionally(const Instruction &Inst, 
                                            const DominatorTree *DT,
+                                           const TargetLibraryInfo *TLI,
                                            const Loop *CurLoop,
                                            const LICMSafetyInfo *SafetyInfo) {
-  // If it is not a trapping instruction, it is always safe to hoist.
-  if (isSafeToSpeculativelyExecute(&Inst))
+  const Instruction *CtxI = CurLoop->getLoopPreheader()->getTerminator();
+  if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT, TLI))
     return true;
 
   return isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
 }
 
 static bool isGuaranteedToExecute(const Instruction &Inst,
                                   const DominatorTree *DT,
                                   const Loop *CurLoop,

llvm/trunk/test/Transforms/LICM/hoist-deref-load.ll

for.inc:                                          ; preds = %for.body, %if.then
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, %n
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.inc, %entry
   ret void
 }
 
+; This test represents the following function:
+; void test1(int * __restrict__ a, int *b, int &c, int n) {
+;   if (c != null)
+;     for (int i = 0; i < n; ++i)
+;       if (a[i] > 0)
+;         a[i] = c*b[i];
+; }
+; and we want to hoist the load of %c out of the loop. This can be done only
+; because the dereferenceable_or_null attribute is on %c and there is a null
+; check on %c.
+
+; CHECK-LABEL: @test5
+; CHECK: load i32, i32* %c, align 4
+; CHECK: for.body:
+
+define void @test5(i32* noalias %a, i32* %b, i32* dereferenceable_or_null(4) %c, i32 %n) #0 {
+entry:
+  %not_null = icmp ne i32* %c, null
+  br i1 %not_null, label %not.null, label %for.end
+
+not.null:
+  %cmp11 = icmp sgt i32 %n, 0
+  br i1 %cmp11, label %for.body, label %for.end
+
+for.body:                                         ; preds = %not.null, %for.inc
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %not.null ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %0, 0
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %1 = load i32, i32* %c, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %2 = load i32, i32* %arrayidx3, align 4
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc, %entry, %not.null
+  ret void
+}
+
+; This is the same as @test5, but without the null check on %c.
+; Without this check, we should not hoist the load of %c.
+
+; This test case has an icmp on c but the use of this comparison is
+; not a branch. 
+
+; CHECK-LABEL: @test6
+; CHECK: if.then:
+; CHECK: load i32, i32* %c, align 4
+
+define i1 @test6(i32* noalias %a, i32* %b, i32* dereferenceable_or_null(4) %c, i32 %n) #0 {
+entry:
+  %not_null = icmp ne i32* %c, null
+  %cmp11 = icmp sgt i32 %n, 0
+  br i1 %cmp11, label %for.body, label %for.end
+
+for.body:                                         ; preds = %entry, %for.inc
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %0, 0
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %1 = load i32, i32* %c, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %2 = load i32, i32* %arrayidx3, align 4
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc, %entry
+  ret i1 %not_null
+}
+
 attributes #0 = { nounwind uwtable }