Unify isSafeToLoadUnconditionally and isDereferenceablePointer

[apilipenko]

Summary

There are several optimizations when we try to load speculatively. There are also two similar functions to determine whether it's a safe transformation:

• isSafeToLoadUnconditionally
• isDereferenceableAndAlignedPointer

Once we have D9791in place, we can unify these two functions. With this change isSafeToLoadUnconditionally calls isDereferenceableAndAlignedPointer to check whether speculative execution is possible.

As a side effect optimizations which use isSafeToLoadUnconditionally will benefit from dereferenceable attribute. Corresponding test cases added.

[apilipenko]

Since D9791 is landed this can go next. So, ping.

[hfinkel]

Please update this patch with full context (http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface).

[apilipenko]

Upload patch with full context.

[hfinkel]

lib/Analysis/Loads.cpp

72

Why can this part not be unified?

It seems this is the only difference. Why don't we just eliminate this function in favor of isDereferenceableAndAlignedPointer?

[apilipenko]

lib/Analysis/Loads.cpp

72

isDereferenceableAndAlignedPointer checks properties of the pointer. isSafeToLoadUnconditionally calls isDereferenceableAndAlignedPointer and also checks whether this pointer was dereferenced in current BB. So, isSafeToLoadUnconditionally is more powerful and must be used everywhere to check if the load can be speculated.

[apilipenko]

ping

[hfinkel]

lib/Analysis/Loads.cpp

72

I was unclear in my suggestion, rephrasing...

With this change isSafeToLoadUnconditionally, with ScanFrom == nullptr, is equivalent to isDereferenceableAndAlignedPointer. Thus, having these two functions separately exposed is not useful (and will only encourage people to use the less-powerful one directly out of ignorance).

Why don't you take the contents of isDereferenceableAndAlignedPointer and move it into this function. Or, move this function into ValueTracking. Either way, then replace all users of isDereferenceableAndAlignedPointer with isSafeToLoadUnconditionally (with a nullptr ScanFrom if necessary). You might take the existing isDereferenceableAndAlignedPointer and make it a static local function (instead of actually copying and pasting), which is probably better.

In the end, we should have one API function that other passes use, not two.

[apilipenko]

Get rid of isDerferenceableAndAlignedPointer public API function. This revision depends on D16180.

[reames]

Artur I spoke this morning about ways to decompose this patch into easier to review chunks. I believe he plans to separate out at least two small patches to reduce the diff size. Specifically:

1. One change to the order of arguments to isSafeToLoadUnconditionally. This is simply to reduce confusing diff lines and will go in directly without further review.
2. One change to push down isDereferenceablePointer down into isSafeToLoadUnconditionally. This will remove most of the transform pass differences. This will need review, but should be quick to examine.

Once those two are in, this patch should become much simpler.

[apilipenko]

Separated into D16226, D16227, D16230, D16231, D16232.

include/llvm/Analysis/Loads.h

 
 class AliasAnalysis;
 class DataLayout;
+class DominatorTree;
 class MDNode;
+class TargetLibraryInfo;
 
 /// 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 isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom,
-                                 unsigned Align);
+bool isSafeToLoadUnconditionally(Value *V, unsigned Align,
+                                 Instruction *ScanFrom,
+                                 const DataLayout &DL,
+                                 const DominatorTree *DT = nullptr,
+                                 const TargetLibraryInfo *TLI = nullptr);
 
 /// FindAvailableLoadedValue - Scan the ScanBB block backwards (starting at
 /// the instruction before ScanFrom) checking to see if we have the value at

lib/Analysis/Loads.cpp

 
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IntrinsicInst.h"

 ///
 /// This uses the pointee type to determine how many bytes need to be safe to
 /// load from the pointer.
-bool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom,
-                                       unsigned Align) {
-  const DataLayout &DL = ScanFrom->getModule()->getDataLayout();
-
+bool llvm::isSafeToLoadUnconditionally(Value *V, unsigned Align,
+                                       Instruction *ScanFrom,
+                                       const DataLayout &DL,
+                                       const DominatorTree *DT,
+                                       const TargetLibraryInfo *TLI) {
   // Zero alignment means that the load has the ABI alignment for the target
   if (Align == 0)
     Align = DL.getABITypeAlignment(V->getType()->getPointerElementType());
   assert(isPowerOf2_32(Align));
 
-  int64_t ByteOffset = 0;
-  Value *Base = V;
-  Base = GetPointerBaseWithConstantOffset(V, ByteOffset, DL);
+  if (isDereferenceableAndAlignedPointer(V, Align, DL, DT ? ScanFrom : nullptr,
+                                         DT, TLI))
+    return true;
 
-  if (ByteOffset < 0) // out of bounds
+  if (!ScanFrom)
     return false;
 
-  Type *BaseType = nullptr;
-  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();
-    BaseAlign = AI->getAlignment();
-  } else if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) {
-    // Global variables are not necessarily safe to load from if they are
-    // overridden. Their size may change or they may be weak and require a test
-    // to determine if they were in fact provided.
-    if (!GV->mayBeOverridden()) {
-      BaseType = GV->getType()->getElementType();
-      BaseAlign = GV->getAlignment();
-    }
-  }
-
-  PointerType *AddrTy = cast<PointerType>(V->getType());
-  uint64_t LoadSize = DL.getTypeStoreSize(AddrTy->getElementType());
-
-  // If we found a base allocated type from either an alloca or global variable,
-  // try to see if we are definitively within the allocated region. We need to
-  // know the size of the base type and the loaded type to do anything in this
-  // case.
-  if (BaseType && BaseType->isSized()) {
-    if (BaseAlign == 0)
-      BaseAlign = DL.getPrefTypeAlignment(BaseType);
-
-    if (Align <= BaseAlign) {
-      // Check if the load is within the bounds of the underlying object.
-      if (ByteOffset + LoadSize <= DL.getTypeAllocSize(BaseType) &&
-          ((ByteOffset % Align) == 0))
-        return true;
-    }
-  }
-
   // 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,

   // the load entirely).
   BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin();
 
-  // We can at least always strip pointer casts even though we can't use the
-  // base here.
   V = V->stripPointerCasts();
+  PointerType *AddrTy = cast<PointerType>(V->getType());
+  uint64_t LoadSize = DL.getTypeStoreSize(AddrTy->getElementType());
 
   while (BBI != E) {
     --BBI;

lib/Analysis/ValueTracking.cpp

 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/Loads.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"

         LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeThread))
       return false;
     const DataLayout &DL = LI->getModule()->getDataLayout();
-    return isDereferenceableAndAlignedPointer(
-        LI->getPointerOperand(), LI->getAlignment(), DL, CtxI, DT, TLI);
+    return
+      isSafeToLoadUnconditionally(const_cast<Value*>(LI->getPointerOperand()),
+                                  LI->getAlignment(),
+                                  const_cast<Instruction*>(CtxI), DL, DT, TLI);
   }
   case Instruction::Call: {
     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

     if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
       // load (select (Cond, &V1, &V2))  --> select(Cond, load &V1, load &V2).
       unsigned Align = LI.getAlignment();
-      if (isSafeToLoadUnconditionally(SI->getOperand(1), SI, Align) &&
-          isSafeToLoadUnconditionally(SI->getOperand(2), SI, Align)) {
+      if (isSafeToLoadUnconditionally(SI->getOperand(1), Align, SI, DL) &&
+          isSafeToLoadUnconditionally(SI->getOperand(2), Align, SI, DL)) {
         LoadInst *V1 = Builder->CreateLoad(SI->getOperand(1),
                                            SI->getOperand(1)->getName()+".val");
         LoadInst *V2 = Builder->CreateLoad(SI->getOperand(2),

lib/Transforms/Scalar/SROA.cpp

     // If this pointer is always safe to load, or if we can prove that there
     // is already a load in the block, then we can move the load to the pred
     // block.
-    if (isDereferenceablePointer(InVal, DL) ||
-        isSafeToLoadUnconditionally(InVal, TI, MaxAlign))
+    if (isSafeToLoadUnconditionally(InVal, MaxAlign, TI, DL))
       continue;
 
     return false;

   Value *TValue = SI.getTrueValue();
   Value *FValue = SI.getFalseValue();
   const DataLayout &DL = SI.getModule()->getDataLayout();
-  bool TDerefable = isDereferenceablePointer(TValue, DL);
-  bool FDerefable = isDereferenceablePointer(FValue, DL);
 
   for (User *U : SI.users()) {
     LoadInst *LI = dyn_cast<LoadInst>(U);

     // Both operands to the select need to be dereferencable, either
     // absolutely (e.g. allocas) or at this point because we can see other
     // accesses to it.
-    if (!TDerefable &&
-        !isSafeToLoadUnconditionally(TValue, LI, LI->getAlignment()))
+    if (!isSafeToLoadUnconditionally(TValue, LI->getAlignment(), LI, DL))
       return false;
-    if (!FDerefable &&
-        !isSafeToLoadUnconditionally(FValue, LI, LI->getAlignment()))
+    if (!isSafeToLoadUnconditionally(FValue, LI->getAlignment(), LI, DL))
       return false;
   }
 

lib/Transforms/Scalar/ScalarReplAggregates.cpp

 /// the select can be loaded unconditionally.
 static bool isSafeSelectToSpeculate(SelectInst *SI) {
   const DataLayout &DL = SI->getModule()->getDataLayout();
-  bool TDerefable = isDereferenceablePointer(SI->getTrueValue(), DL);
-  bool FDerefable = isDereferenceablePointer(SI->getFalseValue(), DL);
 
   for (User *U : SI->users()) {
     LoadInst *LI = dyn_cast<LoadInst>(U);

 
     // Both operands to the select need to be dereferencable, either absolutely
     // (e.g. allocas) or at this point because we can see other accesses to it.
-    if (!TDerefable &&
-        !isSafeToLoadUnconditionally(SI->getTrueValue(), LI,
-                                     LI->getAlignment()))
+    if (!isSafeToLoadUnconditionally(SI->getTrueValue(),
+                                     LI->getAlignment(), LI, DL))
       return false;
-    if (!FDerefable &&
-        !isSafeToLoadUnconditionally(SI->getFalseValue(), LI,
-                                     LI->getAlignment()))
+    if (!isSafeToLoadUnconditionally(SI->getFalseValue(),
+                                     LI->getAlignment(), LI, DL))
       return false;
   }
 

 
     // If this pointer is always safe to load, or if we can prove that there is
     // already a load in the block, then we can move the load to the pred block.
-    if (isDereferenceablePointer(InVal, DL) ||
-        isSafeToLoadUnconditionally(InVal, Pred->getTerminator(), MaxAlign))
+    if (isSafeToLoadUnconditionally(InVal, MaxAlign, Pred->getTerminator(), DL))
       continue;
 
     return false;

lib/Transforms/Scalar/TailRecursionElimination.cpp

       // does not write to memory and the load provably won't trap.
       // FIXME: Writes to memory only matter if they may alias the pointer
       // being loaded from.
+      const DataLayout &DL = L->getModule()->getDataLayout();
       if (CI->mayWriteToMemory() ||
-          !isSafeToLoadUnconditionally(L->getPointerOperand(), L,
-                                       L->getAlignment()))
+          !isSafeToLoadUnconditionally(L->getPointerOperand(),
+                                       L->getAlignment(), L, DL))
         return false;
     }
   }

test/Transforms/InstCombine/select.ll

   ret i32 %v
 }
 
+define i32 @test78_deref(i1 %flag, i32* dereferenceable(4) %x, i32* dereferenceable(4) %y, i32* %z) {
+; Test that we can speculate the loads around the select even when we can't
+; fold the load completely away.
+; CHECK-LABEL: @test78_deref(
+; CHECK:         %[[V1:.*]] = load i32, i32* %x
+; CHECK-NEXT:    %[[V2:.*]] = load i32, i32* %y
+; CHECK-NEXT:    %[[S:.*]] = select i1 %flag, i32 %[[V1]], i32 %[[V2]]
+; CHECK-NEXT:    ret i32 %[[S]]
+entry:
+  %p = select i1 %flag, i32* %x, i32* %y
+  %v = load i32, i32* %p
+  ret i32 %v
+}
+
 define i32 @test78_neg(i1 %flag, i32* %x, i32* %y, i32* %z) {
 ; The same as @test78 but we can't speculate the load because it can trap
 ; if under-aligned.

test/Transforms/TailCallElim/reorder_load.ll

   %tmp10 = add i32 %second, %tmp8    ; <i32> [#uses=1]
   ret i32 %tmp10
 }
+
+; This load can be moved above the call because the function won't write to it
+; and the a_arg is dereferenceable.
+define fastcc i32 @raise_load_5(i32* dereferenceable(4) %a_arg, i32 %a_len_arg, i32 %start_arg) readonly {
+; CHECK-LABEL: @raise_load_5(
+; CHECK-NOT: call
+; CHECK: load i32, i32*
+; CHECK-NOT: call
+; CHECK: }
+entry:
+  %tmp2 = icmp sge i32 %start_arg, %a_len_arg    ; <i1> [#uses=1]
+  br i1 %tmp2, label %if, label %else
+
+if:   ; preds = %entry
+  ret i32 0
+
+else:   ; preds = %entry
+  %tmp7 = add i32 %start_arg, 1   ; <i32> [#uses=1]
+  %tmp8 = call fastcc i32 @raise_load_5(i32* %a_arg, i32 %a_len_arg, i32 %tmp7)    ; <i32> [#uses=1]
+  %tmp9 = load i32, i32* %a_arg    ; <i32> [#uses=1]
+  %tmp10 = add i32 %tmp9, %tmp8   ; <i32> [#uses=1]
+  ret i32 %tmp10
+}