[deref-at-point] restrict inference of dereferenceability based on allocsize attribute

[reames]

Summary

(Patch description completely redone.)

Support deriving dereferenceability facts from allocation sites with known object sizes while correctly accounting for any possibly frees between allocation and use site. (At the moment, that's super conservative and only allowing it in functions where we know we can't free.)

This is part of the work on deref-at-point semantics. I'm making the change unconditional as the miscompile in this case is way too easy to trip by accident, and the optimization was only recently added (by me).

After this lands, the TLI wiring will be done separately in another review. That way a single review isn't both fixing a bug, and enabling further optimization.

[jdoerfert]

FWIW, the conceptual problem was known and D61652 was supposed to address this. We never merged it and we might not need it since we have free now.

[reames]

Rework of patch description, and candidate fix for issue exposed in first WIP.

[reames]

Really should have made sure the last build had fully finished running make check before posting patch...

[jdoerfert]

llvm/lib/Analysis/MemoryBuiltins.cpp

526 ↗

(On Diff #322529)

I think we need to address some of the TODOs to avoid regressions.

[reames]

llvm/lib/Analysis/MemoryBuiltins.cpp

526 ↗

(On Diff #322529)

As stated in the review description, the regression is intentional. As the author of the change being partially reverted, I think this is the right step forward.

[reames]

Rebase over the infrastructure added for deref-at-point semantics. This is effectively unconditionally using deref-at-point, but since if we don't, we have a miscompile actively happening, I'm not too worried about that.

[reames]

While trying to add the test case, ran across something weird. Not sure if the patch is wrong or my brain is just fried. Will take a fresh look tomorrow.

[reames]

Restrict scope further - only fix the existing latent issue w/allocsize.

(Good news, the weirdness from last night was human error.)

[reames]

llvm/test/Transforms/LoopVectorize/X86/load-deref-pred.ll

95 ↗

(On Diff #333425)

Please ignore these changes. This a result of autogen format change. I have landed a change which includes these, and the next rebase will wipe them out. I'd usually do that now, but build times are substantial given the Value.h change. :)

[reames]

ping

[jdoerfert]

LG, thanks for cleaning this up.

[nikic]

As we don't have any default-enabled nosync inference, doesn't this effectively disable this code entirely (for the default pipeline)?

[reames]

In D95815#2663147, @nikic wrote:

As we don't have any default-enabled nosync inference, doesn't this effectively disable this code entirely (for the default pipeline)?

Not really.

Remember, the currently hooked up code doesn't get the benefit of TLI. (Because doing so immediately broke badly.) As a result, it only handles things which are a) allocas and the like, or b) explicitly marked allocsize. We do take a hit on the allocsize cases - except that the single consumer I know of is a GCd frontend which is special cased in the canBeFreed stuff anyways. If anything, this should give us a net benefit because we can expose the malloc/new cases by adding TLI as a parameter (to be done and reviewed separately.)

llvm/include/llvm/Analysis/ValueTracking.h

   /// for such instructions, moving them may change the resulting value.
   bool isSafeToSpeculativelyExecute(const Value *V,
                                     const Instruction *CtxI = nullptr,
-                                    const DominatorTree *DT = nullptr);
+                                    const DominatorTree *DT = nullptr,
+                                    const TargetLibraryInfo *TLI = nullptr);
 
   /// Returns true if the result or effects of the given instructions \p I
   /// depend on or influence global memory.

llvm/lib/Analysis/Loads.cpp

     Opts.RoundToAlign = false;
     Opts.NullIsUnknownSize = true;
     uint64_t ObjSize;
-    // TODO: Plumb through TLI so that malloc routines and such working.
-    if (getObjectSize(V, ObjSize, DL, nullptr, Opts)) {
+    if (getObjectSize(V, ObjSize, DL, TLI, Opts)) {
       APInt KnownDerefBytes(Size.getBitWidth(), ObjSize);
       if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(Size) &&
           isKnownNonZero(V, DL, 0, nullptr, CtxI, DT) &&

llvm/lib/Analysis/ValueTracking.cpp

 
 bool llvm::isSafeToSpeculativelyExecute(const Value *V,
                                         const Instruction *CtxI,
-                                        const DominatorTree *DT) {
+                                        const DominatorTree *DT,
+                                        const TargetLibraryInfo *TLI) {
   const Operator *Inst = dyn_cast<Operator>(V);
   if (!Inst)
     return false;

     const DataLayout &DL = LI->getModule()->getDataLayout();
     return isDereferenceableAndAlignedPointer(
         LI->getPointerOperand(), LI->getType(), MaybeAlign(LI->getAlignment()),
-        DL, CtxI, DT);
+        DL, CtxI, DT, TLI);
   }
   case Instruction::Call: {
     auto *CI = cast<const CallInst>(Inst);

llvm/lib/Transforms/Scalar/LICM.cpp

                  OptimizationRemarkEmitter *ORE);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
+                                           const TargetLibraryInfo *TLI,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,

                              ORE) &&
           worthSinkOrHoistInst(I, CurLoop->getLoopPreheader(), ORE, BFI) &&
           isSafeToExecuteUnconditionally(
-              I, DT, CurLoop, SafetyInfo, ORE,
+              I, DT, TLI, CurLoop, SafetyInfo, ORE,
               CurLoop->getLoopPreheader()->getTerminator())) {
         hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
               MSSAU, SE, ORE);

 /// or if it is a trapping instruction and is guaranteed to execute.
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
+                                           const TargetLibraryInfo *TLI,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI) {
-  if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
+  if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT, TLI))
     return true;
 
   bool GuaranteedToExecute =

         // to execute does as well.  Thus we can increase our guaranteed
         // alignment as well. 
         if (!DereferenceableInPH || (InstAlignment > Alignment))
-          if (isSafeToExecuteUnconditionally(*Load, DT, CurLoop, SafetyInfo,
-                                             ORE, Preheader->getTerminator())) {
+          if (isSafeToExecuteUnconditionally(*Load, DT, TLI, CurLoop,
+                                             SafetyInfo, ORE,
+                                             Preheader->getTerminator())) {
             DereferenceableInPH = true;
             Alignment = std::max(Alignment, InstAlignment);
           }

         if (!DereferenceableInPH) {
           DereferenceableInPH = isDereferenceableAndAlignedPointer(
               Store->getPointerOperand(), Store->getValueOperand()->getType(),
-              Store->getAlign(), MDL, Preheader->getTerminator(), DT);
+              Store->getAlign(), MDL, Preheader->getTerminator(), DT, TLI);
         }
       } else
         return false; // Not a load or store.

llvm/test/Transforms/LICM/hoist-alloc.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -basic-aa -licm < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @unknown()
+declare void @init(i8* nocapture)
+declare void @use(i8)
+
+define i8 @test_sink_alloca() {
+; CHECK-LABEL: @test_sink_alloca(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca [32 x i8], align 1
+; CHECK-NEXT:    [[A_RAW:%.*]] = bitcast [32 x i8]* [[A]] to i8*
+; CHECK-NEXT:    call void @init(i8* [[A_RAW]])
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    call void @unknown()
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 200
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[ADDR_LE:%.*]] = getelementptr i8, i8* [[A_RAW]], i32 31
+; CHECK-NEXT:    [[RES_LE:%.*]] = load i8, i8* [[ADDR_LE]], align 1
+; CHECK-NEXT:    ret i8 [[RES_LE]]
+;
+entry:
+  %a = alloca [32 x i8]
+  %a.raw = bitcast [32 x i8]* %a to i8*
+  call void @init(i8* %a.raw)
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ %iv.next, %for.body ], [ 0, %entry ]
+  call void @unknown() ;; may throw
+  %addr = getelementptr i8, i8* %a.raw, i32 31
+  %res = load i8, i8* %addr
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, 200
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret i8 %res
+}
+
+define i8 @test_hoist_alloca() {
+; CHECK-LABEL: @test_hoist_alloca(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca [32 x i8], align 1
+; CHECK-NEXT:    [[A_RAW:%.*]] = bitcast [32 x i8]* [[A]] to i8*
+; CHECK-NEXT:    call void @init(i8* [[A_RAW]])
+; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i8, i8* [[A_RAW]], i32 31
+; CHECK-NEXT:    [[RES:%.*]] = load i8, i8* [[ADDR]], align 1
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    call void @unknown()
+; CHECK-NEXT:    call void @use(i8 [[RES]])
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 200
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[RES_LCSSA:%.*]] = phi i8 [ [[RES]], [[FOR_BODY]] ]
+; CHECK-NEXT:    ret i8 [[RES_LCSSA]]
+;
+entry:
+  %a = alloca [32 x i8]
+  %a.raw = bitcast [32 x i8]* %a to i8*
+  call void @init(i8* %a.raw)
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ %iv.next, %for.body ], [ 0, %entry ]
+  call void @unknown() ;; may throw
+  %addr = getelementptr i8, i8* %a.raw, i32 31
+  %res = load i8, i8* %addr
+  call void @use(i8 %res)
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, 200
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret i8 %res
+}
+
+; The attributes listed here are a) inferred by -O3 from the names
+; and b) required for a standalone test.  We're very inconsistent about
+; which decisions we drive from TLI vs assume attributes have been infered.
+declare void @free(i8* nocapture)
+declare noalias i8* @malloc(i64)
+
+define i8 @test_sink_malloc() {
+; CHECK-LABEL: @test_sink_malloc(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A_RAW:%.*]] = call nonnull i8* @malloc(i64 32)
+; CHECK-NEXT:    call void @init(i8* [[A_RAW]])
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    call void @unknown()
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 200
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[ADDR_LE:%.*]] = getelementptr i8, i8* [[A_RAW]], i32 31
+; CHECK-NEXT:    [[RES_LE:%.*]] = load i8, i8* [[ADDR_LE]], align 1
+; CHECK-NEXT:    call void @free(i8* [[A_RAW]])
+; CHECK-NEXT:    ret i8 [[RES_LE]]
+;
+entry:
+  ; Mark as nonnull to simplify test
+  %a.raw = call nonnull i8* @malloc(i64 32)
+  call void @init(i8* %a.raw)
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ %iv.next, %for.body ], [ 0, %entry ]
+  call void @unknown() ;; may throw
+  %addr = getelementptr i8, i8* %a.raw, i32 31
+  %res = load i8, i8* %addr
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, 200
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  call void @free(i8* %a.raw)
+  ret i8 %res
+}
+
+define i8 @test_hoist_malloc() {
+; CHECK-LABEL: @test_hoist_malloc(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A_RAW:%.*]] = call nonnull i8* @malloc(i64 32)
+; CHECK-NEXT:    call void @init(i8* [[A_RAW]])
+; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i8, i8* [[A_RAW]], i32 31
+; CHECK-NEXT:    [[RES:%.*]] = load i8, i8* [[ADDR]], align 1
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    call void @unknown()
+; CHECK-NEXT:    call void @use(i8 [[RES]])
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 200
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[RES_LCSSA:%.*]] = phi i8 [ [[RES]], [[FOR_BODY]] ]
+; CHECK-NEXT:    call void @free(i8* [[A_RAW]])
+; CHECK-NEXT:    ret i8 [[RES_LCSSA]]
+;
+entry:
+  %a.raw = call nonnull i8* @malloc(i64 32)
+  call void @init(i8* %a.raw)
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ %iv.next, %for.body ], [ 0, %entry ]
+  call void @unknown() ;; may throw
+  %addr = getelementptr i8, i8* %a.raw, i32 31
+  %res = load i8, i8* %addr
+  call void @use(i8 %res)
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, 200
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  call void @free(i8* %a.raw)
+  ret i8 %res
+}
+
+define i8 @test_hoist_malloc_leak() {
+; CHECK-LABEL: @test_hoist_malloc_leak(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A_RAW:%.*]] = call nonnull i8* @malloc(i64 32)
+; CHECK-NEXT:    call void @init(i8* [[A_RAW]])
+; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i8, i8* [[A_RAW]], i32 31
+; CHECK-NEXT:    [[RES:%.*]] = load i8, i8* [[ADDR]], align 1
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    call void @unknown()
+; CHECK-NEXT:    call void @use(i8 [[RES]])
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 200
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[RES_LCSSA:%.*]] = phi i8 [ [[RES]], [[FOR_BODY]] ]
+; CHECK-NEXT:    ret i8 [[RES_LCSSA]]
+;
+entry:
+  %a.raw = call nonnull i8* @malloc(i64 32)
+  call void @init(i8* %a.raw)
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ %iv.next, %for.body ], [ 0, %entry ]
+  call void @unknown() ;; may throw
+  %addr = getelementptr i8, i8* %a.raw, i32 31
+  %res = load i8, i8* %addr
+  call void @use(i8 %res)
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, 200
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret i8 %res
+}
+
+; In this case, we can't hoist the load out of the loop as the memory it
+; accesses may have been conditionally freed in a manner correlated with
+; whether the load is reached in the loop.
+define void @test_hoist_malloc_cond_free(i1 %c) {
+; CHECK-LABEL: @test_hoist_malloc_cond_free(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A_RAW:%.*]] = call nonnull i8* @malloc(i64 32)
+; CHECK-NEXT:    call void @init(i8* [[A_RAW]])
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[COND_FREE:%.*]], label [[PREHEADER:%.*]]
+; CHECK:       cond.free:
+; CHECK-NEXT:    call void @free(i8* [[A_RAW]])
+; CHECK-NEXT:    br label [[PREHEADER]]
+; CHECK:       preheader:
+; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i8, i8* [[A_RAW]], i32 31
+; CHECK-NEXT:    [[RES:%.*]] = load i8, i8* [[ADDR]], align 1
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 0, [[PREHEADER]] ]
+; CHECK-NEXT:    br i1 [[C]], label [[FOR_END:%.*]], label [[LOOP_LATCH]]
+; CHECK:       loop.latch:
+; CHECK-NEXT:    call void @unknown()
+; CHECK-NEXT:    call void @use(i8 [[RES]])
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 200
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %a.raw = call nonnull i8* @malloc(i64 32)
+  call void @init(i8* %a.raw)
+  br i1 %c, label %cond.free, label %preheader
+cond.free:
+  call void @free(i8* %a.raw)
+  br label %preheader
+preheader:
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ %iv.next, %loop.latch ], [ 0, %preheader ]
+  br i1 %c, label %for.end, label %loop.latch
+
+loop.latch:
+  call void @unknown() ;; may throw
+  %addr = getelementptr i8, i8* %a.raw, i32 31
+  %res = load i8, i8* %addr
+  call void @use(i8 %res)
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, 200
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret void
+}
+