[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

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

[reames]

llvm/lib/Analysis/MemoryBuiltins.cpp

526

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/MemoryBuiltins.h

 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
 
 inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
   return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
 }
 
 //===----------------------------------------------------------------------===//
+//  Utility functions to reason about whether memory might be deallocated
+//
+
+/// Return false iff we can prove that the object associated with the pointer
+/// 'V' can not be deallocated in the scope of Function F.  Note that callers
+/// need to be careful when reasoning about potentially recursive functions as
+/// there are potentially many copies of V and Scope, the result describes a
+/// single dynamic frame of the Scope function.
+bool mayObjectBeDeallocatedInScope(const Value *V, const Function *Scope);
+
+//===----------------------------------------------------------------------===//
 //  Utility functions to compute size of objects.
 //
 
 /// Various options to control the behavior of getObjectSize.
 struct ObjectSizeOpts {
   /// Controls how we handle conditional statements with unknown conditions.
   enum class Mode : uint8_t {
     /// Fail to evaluate an unknown condition.

llvm/include/llvm/Analysis/ValueTracking.h

constexpr unsigned MaxAnalysisRecursionDepth = 6;
   /// 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,
                                     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.
   /// Memory dependence arises for example if the instruction reads from
   /// memory or may produce effects or undefined behaviour. Memory dependent
   /// instructions generally cannot be reorderd with respect to other memory
   /// dependent instructions or moved into non-dominated basic blocks.
   /// Instructions which just compute a value based on the values of their

llvm/lib/Analysis/Loads.cpp

if (const auto *Call = dyn_cast<CallBase>(V)) {
     // separate recursive walk.
     ObjectSizeOpts Opts;
     // TODO: It may be okay to round to align, but that would imply that
     // accessing slightly out of bounds was legal, and we're currently
     // inconsistent about that.  For the moment, be conservative.
     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) &&
-          // TODO: We're currently inconsistent about whether deref(N) is a
-          // global fact or a point in time fact.  Once D61652 eventually
-          // lands, this check will be restricted to the point in time
-          // variant. For that variant, we need to prove that object hasn't
-          // been conditionally freed before ontext instruction - if it has, we
-          // might be hoisting over the inverse conditional and creating a
-          // dynamic use after free. 
-          !PointerMayBeCapturedBefore(V, true, true, CtxI, DT, true)) {
+          !mayObjectBeDeallocatedInScope(V, CtxI->getFunction())) {
         // As we recursed through GEPs to get here, we've incrementally
         // checked that each step advanced by a multiple of the alignment. If
         // our base is properly aligned, then the original offset accessed
         // must also be. 
         Type *Ty = V->getType();
         assert(Ty->isSized() && "must be sized");
         APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0);
         return isAligned(V, Offset, Alignment, DL);

llvm/lib/Analysis/MemoryBuiltins.cpp

const CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) {
   StringRef FnName = Callee->getName();
   LibFunc TLIFn;
   if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn))
     return nullptr;
 
   return isLibFreeFunction(Callee, TLIFn) ? dyn_cast<CallInst>(I) : nullptr;
 }
 
 
+bool llvm::mayObjectBeDeallocatedInScope(const Value *V,
+                                         const Function *Scope) {
+  // Global variables are never deallocated.
+  if (isa<GlobalValue>(V))
+    return false;
+
+  // Constants aren't allocated per se, thus they're never deallocated either.
+  if (isa<Constant>(V))
+    return false;
+
+  // An alloca in the current function is deallocated at the end of the
+  // function scope.  An alloca in another function might be in a callee.
+  if (auto *AI = dyn_cast<AllocaInst>(V))
+    return AI->getFunction() != Scope;
+
+  // TODO: We can most likely add the following cases, subject to individual
+  // review and discussion to make sure we're not missing anything.
+  // * function w/nofree and nosync attributes
+  // * noalias + nofree argument => no-free object
+  //   (seperately need either nosync or not captured)
+  // * GC allocated objects (before lowering from abstract machine)
+  // * others?
+
+  // conservative answer
+  return true;
+}
+
 //===----------------------------------------------------------------------===//
 //  Utility functions to compute size of objects.
 //
 static APInt getSizeWithOverflow(const SizeOffsetType &Data) {
   if (Data.second.isNegative() || Data.first.ult(Data.second))
     return APInt(Data.first.getBitWidth(), 0);
   return Data.first - Data.second;
 }

llvm/lib/Analysis/ValueTracking.cpp

return F.hasFnAttribute(Attribute::SanitizeThread) ||
     // Speculative load may load data from dirty regions.
     F.hasFnAttribute(Attribute::SanitizeAddress) ||
     F.hasFnAttribute(Attribute::SanitizeHWAddress);
 }
 
 
 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;
 
   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
     if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i)))
       if (C->canTrap())
         return false;
 
   switch (Inst->getOpcode()) {
   default:
     return true;
bool llvm::isSafeToSpeculativelyExecute(const Value *V,
   }
   case Instruction::Load: {
     const LoadInst *LI = cast<LoadInst>(Inst);
     if (mustSuppressSpeculation(*LI))
       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);
     const Function *Callee = CI->getCalledFunction();
 
     // The called function could have undefined behavior or side-effects, even
     // if marked readnone nounwind.
     return Callee && Callee->isSpeculatable();

llvm/lib/Transforms/Scalar/LICM.cpp

 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
                   MemorySSAUpdater *MSSAU, ScalarEvolution *SE,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  BlockFrequencyInfo *BFI, const Loop *CurLoop,
                  ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU,
                  OptimizationRemarkEmitter *ORE);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
+                                           const TargetLibraryInfo *TLI,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
 static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
                                      AliasSetTracker *CurAST, Loop *CurLoop,
                                      AAResults *AA);
 static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
       // TODO: It may be safe to hoist if we are hoisting to a conditional block
       // and we have accurately duplicated the control flow from the loop header
       // to that block.
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, &Flags,
                              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);
         HoistedInstructions.push_back(&I);
         Changed = true;
         continue;
       }
 
static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
   else if (isa<CallInst>(I))
     ++NumMovedCalls;
   ++NumHoisted;
 }
 
 /// 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(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 =
       SafetyInfo->isGuaranteedToExecute(Inst, DT, CurLoop);
 
   if (!GuaranteedToExecute) {
     auto *LI = dyn_cast<LoadInst>(&Inst);
     if (LI && CurLoop->isLoopInvariant(LI->getPointerOperand()))
for (User *U : ASIV->users()) {
 
         Align InstAlignment = Load->getAlign();
 
         // Note that proving a load safe to speculate requires proving
         // sufficient alignment at the target location.  Proving it guaranteed
         // 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);
           }
       } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
         // Stores *of* the pointer are not interesting, only stores *to* the
         // pointer.
         if (UI->getOperand(1) != ASIV)
           continue;
for (User *U : ASIV->users()) {
             return DT->dominates(Store->getParent(), Exit);
           });
 
         // If the store is not guaranteed to execute, we may still get
         // deref info through it.
         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.
 
       // Merge the AA tags.
       if (LoopUses.empty()) {
         // On the first load/store, just take its AA tags.
         UI->getAAMetadata(AATags);