Hoist loads known to be in bounds of allocations

[reames]

Summary

Extend the dereferenceability analysis to exploit our existing implementation for computing a minimal object size. If we can tell we're within a known allocation, we can speculate the load without changing dereferenceability. This does assume that allocations are dereferenceable within their entire extend, but that seems like an entirely reasonable definition. (It also appears to be true of the existing code.)

[sanjoy]

lib/Analysis/Loads.cpp

123

Does this work in the presence of free? That is:

char *ptr = malloc(20)
free(ptr);
for (;;) {
  if (false)
    v = ptr[0];
}

[reames]

The test case Sanjoy added shows a fatal flaw in this approach. If free is possible, my reason would have to be context sensitive and that's not worth implementing at this time.

lib/Analysis/Loads.cpp

 //===- Loads.cpp - Local load analysis ------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines simple local analyses for load instructions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
     return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, Size,
                                               DL, CtxI, DT, Visited);
 
   if (auto CS = ImmutableCallSite(V))
     if (const Value *RV = CS.getReturnedArgOperand())
       return isDereferenceableAndAlignedPointer(RV, Align, Size, DL, CtxI, DT,
                                                 Visited);
 
+  // Check for cases where we know the minimum size of an object - this handles
+  // cases where we can see the allocation, or we're loading from global
+  // variable with a known size.  This does assume that our definition of
+  // "object" size ensures the entire size is dereferenceable. 
+  uint64_t ObjSize;
+  ObjectSizeOpts Opts;
+  Opts.EvalMode = ObjectSizeOpts::Mode::Min;
+  if (getObjectSize(V, ObjSize, DL, nullptr, Opts) &&
+      Size.ule(ObjSize))
+    return isAligned(V, Align, DL);
+
   // If we don't know, assume the worst.
   return false;
 }
 
 bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
                                               const DataLayout &DL,
                                               const Instruction *CtxI,
                                               const DominatorTree *DT) {

test/Transforms/LICM/hoisting.ll

loop:
   %sum.next = add i32 %sel, %sum
   %indvar.next = add i32 %indvar, 1
   %cond = icmp slt i32 %indvar.next, %n
   br i1 %cond, label %loop, label %loopexit
 
 loopexit:
   ret i32 %sum
 }
+
+@g = external global i1
+
+declare align 8 i8* @my_alloc(i64) allocsize(0)
+declare align 8 i8* @not_alloc(i64)
+
+; Can hoist a load if we know the size of the underlying allocation
+; since we know the entire allocation must be dereferenceable
+define void @test_sized_alloc() {
+; CHECK-LABEL: test_sized_alloc
+; CHECK: @my_alloc
+; CHECK-NEXT: load i8, i8* %p
+  %p = call i8* @my_alloc(i64 20);
+  br label %header
+
+header:
+  %vol = load volatile i1, i1* @g
+  br i1 %vol, label %taken, label %exit
+taken:
+  %v = load i8, i8* %p
+  %cmp = icmp eq i8 %v, 0
+  br i1 %cmp, label %exit, label %header
+exit:
+  ret void
+}
+
+define void @test_sized_alloc_select(i1 %arg) {
+; CHECK-LABEL: test_sized_alloc_select
+; CHECK: @my_alloc
+; CHECK-NEXT: @my_alloc
+; CHECK-NEXT: %p = select i1 %arg, i8* %p1, i8* %p2
+; CHECK-NEXT: load i8, i8* %p
+  %p1 = call i8* @my_alloc(i64 20);
+  %p2 = call i8* @my_alloc(i64 24);
+  %p = select i1 %arg, i8* %p1, i8* %p2
+  br label %header
+
+header:
+  %vol = load volatile i1, i1* @g
+  br i1 %vol, label %taken, label %exit
+taken:
+  %v = load i8, i8* %p
+  %cmp = icmp eq i8 %v, 0
+  br i1 %cmp, label %exit, label %header
+exit:
+  ret void
+}
+
+define void @test_sized_alloc_out_of_bounds() {
+; CHECK-LABEL: test_sized_alloc_out_of_bounds
+; CHECK: @my_alloc
+  %p = call i8* @my_alloc(i64 0);
+  br label %header
+
+header:
+  %vol = load volatile i1, i1* @g
+  br i1 %vol, label %taken, label %exit
+taken:
+; CHECK-LABEL: taken:
+; CHECK-NEXT: load i8, i8* %p
+  %v = load i8, i8* %p
+  %cmp = icmp eq i8 %v, 0
+  br i1 %cmp, label %exit, label %header
+exit:
+  ret void
+}
+
+define void @test_sized_not_alloc() {
+; CHECK-LABEL: test_sized_not_alloc
+; CHECK: @not_alloc
+  %p = call i8* @not_alloc(i64 20);
+  br label %header
+
+header:
+  %vol = load volatile i1, i1* @g
+  br i1 %vol, label %taken, label %exit
+taken:
+; CHECK-LABEL: taken:
+; CHECK-NEXT: load i8, i8* %p
+  %v = load i8, i8* %p
+  %cmp = icmp eq i8 %v, 0
+  br i1 %cmp, label %exit, label %header
+exit:
+  ret void
+}