Basic support for posix_memalign / __builtin_object_size interaction

[serge-sans-paille]

Summary

It actually implements support for seeing through loads, using alias analysis to
refine the result.

This is rather limited, but I didn't want to rely on more than available analysis at that point (to be gentle with compilation time), and it does seem to catch some common scenario, as showcased by the included tests.

[xbolva00]

llvm/lib/Analysis/MemoryBuiltins.cpp

156

why remove? no record above for posix_memalign was added..

[nikic]

This is pretty unusual in terms of approach, it would be more typical to do a limited upward walk to find the clobbering store (a la FindAvailableLoadedValue).

llvm/lib/Analysis/MemoryBuiltins.cpp

847

What about the case where the object size is taken prior to initialization? In the alloca case it will be an undef initialization -- is it fine to simply ignore that case? I'd probably expect min at least to return zero for that.

Probably more obviously problematic is the noalias case, because that one doesn't make any statement on the initial contents of the memory. For a typical allocator that will be either undef or null, but this is not a requirement of noalias (an obvious violation is strdup).

909

I don't get what this check is supposed to do. You're asking here whether an escaping pointer and an escape-source alias, for which the answer should always be "yes" for the SimpleCaptureInfo-based AA used here. Can you give an example where this check does something useful?

[nikic]

llvm/lib/Analysis/MemoryBuiltins.cpp

913

To double check, does this work when a non-pointer type is stored? You might want to add a test that stores an i32 or so into a bitcasted pointer.

[serge-sans-paille]

Following @nikic suggestion, use a CFG-based graph transversal à la FindAvailableLoadedValue

[serge-sans-paille]

Added test case for simple load interactions.

[serge-sans-paille]

Take into account posix_memalign return value, as suggested by @nikic

[xbolva00]

llvm/lib/Analysis/MemoryBuiltins.cpp

156

Still no answer

899

Do you need FakeCond at all?

llvm::isImpliedByDomCondition (CmpInst::Predicate Pred, const Value *LHS, const Value *RHS, const Instruction *ContextI, const DataLayout &DL)

[serge-sans-paille]

llvm/lib/Analysis/MemoryBuiltins.cpp

156

Yup, sorry: because it's API is so different (and unique ?) from other library functions. It doesn't fit any of the existing MallocFamily nor AllocType.

899

Indeed!

[nikic]

llvm/include/llvm/Analysis/MemoryBuiltins.h

179

Make it an optional parameter instead?

llvm/lib/Analysis/MemoryBuiltins.cpp

593

Can assign unconditionally.

828

With the getUniquePredecessor() variant noted before this wouldn't matter, but if you do explore branching cases, then I'm not sure returning unknown here makes sense. Consider a simple store; if (...) { ... } else { ... } load; case. The upwards walk would hit the store along one path first and then along the other again and return unknown at that pointer.

831

This should probably only be counted once on the top level?

836

We should be checking against a budget here, to avoid scanning 150k instructions in search of a matching store...

843

Use getPointerOperand() here.

Also probably need to check SI->getValueOperand()->getType()->isPointerTy(), unless compute() handles non-pointer values gracefully.

848

This should be checking aliasing with Load.getPointerOperand(), *not* &Load itself.

895

bos -> the load

916

Should queue on a worklist rather than recursing. For the posix_memalign use-case, it might make sense to just restrict to getUniquePredecessor(), as we probably don't care about branching cases there?

[serge-sans-paille]

take @nikic remarks into account.

llvm/include/llvm/Analysis/MemoryBuiltins.h

179

That's a choice: I wanted to keep it grouped with TLI so that all analyse are kept next to each other.

llvm/lib/Analysis/MemoryBuiltins.cpp

831

This is used to count the "Number of load instructions with unsolved size and offset", thus the detailed counting.

843

I *think* this is already guarenteed by the fact that we match against the load pointer operand, which is of type T**

[nikic]

llvm/lib/Analysis/MemoryBuiltins.cpp

828

I think this limit is still overly large -- I think our usual value starting value for limits like this is 32. If you think that's too low to be practically useful, I'd go with 128 here.

831

Right, but currently you're incrementing this once per unknown predecessor, rather than once per load, no?

843

This isn't guaranteed with opaque pointers -- but also for the more general MustAlias case below, which will strip pointer casts.

845

Should have a if(I.isDebugInst()) continue check here, to make sure debug insts can't affect optimization. (Before the limit check.)

854

Just wondering if it might be better to just bail entirely from the load-handling code if we don't have AA, rather than having extra code to support both? I don't particularly mind, but given how we essentially only care about the one lowerObjectSizeCall() usage that does have AA, this may not be particularly useful. We'd have to add some tests for a different caller that goes through these non-AA codepaths.

867

nit: getValueOperand()

879

Second part of this comment is now outdated :)

897

nit: Load.getPointerOperand()

931

As a small optimization, we could short-circuit on unknown here.

[serge-sans-paille]

Another review round trip.

[nikic]

LGTM

llvm/lib/Analysis/MemoryBuiltins.cpp

906

Should be Unknown().

llvm/test/Transforms/LowerConstantIntrinsics/builtin-object-size-load.ll

2 ↗

(On Diff #420801)

We should pass in the AA parameter in LowerConstantIntrinsics to avoid the need for -instcombine here, but we can do that separately...

llvm/include/llvm/Analysis/MemoryBuiltins.h

 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/ValueHandle.h"
 #include <cstdint>
 #include <utility>
 
 namespace llvm {
 
 class AllocaInst;
+class AAResults;
 class Argument;
 class CallInst;
 class ConstantPointerNull;
 class DataLayout;
 class ExtractElementInst;
 class ExtractValueInst;
 class GEPOperator;
 class GlobalAlias;
struct ObjectSizeOpts {
   Mode EvalMode = Mode::Exact;
   /// Whether to round the result up to the alignment of allocas, byval
   /// arguments, and global variables.
   bool RoundToAlign = false;
   /// If this is true, null pointers in address space 0 will be treated as
   /// though they can't be evaluated. Otherwise, null is always considered to
   /// point to a 0 byte region of memory.
   bool NullIsUnknownSize = false;
+  /// If set, used for more accurate evaluation
+  AAResults *AA = nullptr;
 };
 
 /// Compute the size of the object pointed by Ptr. Returns true and the
 /// object size in Size if successful, and false otherwise. In this context, by
 /// object we mean the region of memory starting at Ptr to the end of the
 /// underlying object pointed to by Ptr.
 ///
 /// WARNING: The object size returned is the allocation size.  This does not
 /// imply dereferenceability at site of use since the object may be freeed in
 /// between.
 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
                    const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
 
 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
 /// Type. Returns null on failure. If MustSucceed is true, this function will
 /// not return null, and may return conservative values governed by the second
 /// argument of the call to objectsize.
 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
                            const TargetLibraryInfo *TLI, bool MustSucceed);
-
-
+Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
+                           const TargetLibraryInfo *TLI, AAResults *AA,
+                           bool MustSucceed);
 
 using SizeOffsetType = std::pair<APInt, APInt>;
 
 /// Evaluate the size and offset of an object pointed to by a Value*
 /// statically. Fails if size or offset are not known at compile time.
 class ObjectSizeOffsetVisitor
   : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
   const DataLayout &DL;

llvm/lib/Analysis/MemoryBuiltins.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/TargetFolder.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/Utils/Local.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {
     {LibFunc_realloc,                           {ReallocLike,      2,  1, -1, -1, MallocFamily::Malloc}},
     {LibFunc_vec_realloc,                       {ReallocLike,      2,  1, -1, -1, MallocFamily::VecMalloc}},
     {LibFunc_reallocf,                          {ReallocLike,      2,  1, -1, -1, MallocFamily::Malloc}},
     {LibFunc_strdup,                            {StrDupLike,       1, -1, -1, -1, MallocFamily::Malloc}},
     {LibFunc_dunder_strdup,                     {StrDupLike,       1, -1, -1, -1, MallocFamily::Malloc}},
     {LibFunc_strndup,                           {StrDupLike,       2,  1, -1, -1, MallocFamily::Malloc}},
     {LibFunc_dunder_strndup,                    {StrDupLike,       2,  1, -1, -1, MallocFamily::Malloc}},
     {LibFunc___kmpc_alloc_shared,               {MallocLike,       1,  0, -1, -1, MallocFamily::KmpcAllocShared}},
-    // TODO: Handle "int posix_memalign(void **, size_t, size_t)"
 };
 // clang-format on
 
 static const Function *getCalledFunction(const Value *V,
                                          bool &IsNoBuiltin) {
   // Don't care about intrinsics in this case.
   if (isa<IntrinsicInst>(V))
     return nullptr;
bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
   Size = getSizeWithOverflow(Data).getZExtValue();
   return true;
 }
 
 Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize,
                                  const DataLayout &DL,
                                  const TargetLibraryInfo *TLI,
                                  bool MustSucceed) {
+  return lowerObjectSizeCall(ObjectSize, DL, TLI, /*AAResults=*/nullptr,
+                             MustSucceed);
+}
+
+Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize,
+                                 const DataLayout &DL,
+                                 const TargetLibraryInfo *TLI, AAResults *AA,
+                                 bool MustSucceed) {
   assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize &&
          "ObjectSize must be a call to llvm.objectsize!");
 
   bool MaxVal = cast<ConstantInt>(ObjectSize->getArgOperand(1))->isZero();
   ObjectSizeOpts EvalOptions;
+  if (AA)
+    EvalOptions.AA = AA;
+
   // Unless we have to fold this to something, try to be as accurate as
   // possible.
   if (MustSucceed)
     EvalOptions.EvalMode =
         MaxVal ? ObjectSizeOpts::Mode::Max : ObjectSizeOpts::Mode::Min;
   else
     EvalOptions.EvalMode = ObjectSizeOpts::Mode::Exact;
 
SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){
   return std::make_pair(align(Size, GV.getAlign()), Zero);
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) {
   // clueless
   return unknown();
 }
 
-SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) {
+SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst &LI) {
+  /*
+   * Poor's man tracking of the origin of the loaded address. The sole goal of
+   * this function to handle an allocation pattern based on posix_memalign:
+   *
+   *     void* buffer;
+   *     posix_memalign(&buffer, 8, 128);
+   *
+   * Note however that it also catches situation where the loaded address is
+   * always used to store known buffers to.
+   *
+   * We only consider loads from alloca or arguments with `noalias` attributes
+   * to avoid any aliasing issue.
+   */
+
+  auto Unknown = [this]() {
     ++ObjectVisitorLoad;
     return unknown();
+  };
+
+  Value *LoadingFrom = LI.getOperand(0)->stripPointerCasts();
+  Argument *A = dyn_cast<Argument>(LoadingFrom);
+  if (!(isa<AllocaInst>(LoadingFrom) || (A && A->hasNoAliasAttr())))
+    return Unknown();
+
+  /*
+   * Walk through users of the memory address we're loading from. All the users
+   * must store value at this address for this analysis to be valid.
+   */
+  SmallVector<Value *> WorkList;
+  for (User *U : LoadingFrom->users())
+    WorkList.push_back(U);
+
+  SmallSet<Value *, 8> Visited;
+  Visited.insert(&LI);
+  SmallVector<SizeOffsetType> SizeOffsets;
+
+  while (!WorkList.empty()) {
+    Value *V = WorkList.pop_back_val();
+    if (Visited.count(V))
+      continue;
+
+    // Ignore bit casts.
+    if (isa<BitCastInst>(V)) {
+      for (User *U : V->users())
+        WorkList.push_back(U);
+      continue;
+    }
+
+    // Track posix_memalign.
+    if (auto *CB = dyn_cast<CallBase>(V)) {
+      Function *Callee = CB->getCalledFunction();
+      // Bail out on indirect call.
+      if (!Callee)
+        return Unknown();
+
+      // These users can safely be ignored.
+      auto ID = CB->getIntrinsicID();
+      switch (ID) {
+      case Intrinsic::lifetime_start:
+      case Intrinsic::lifetime_end:
+        continue;
+      default:;
+      }
+
+      // posix_memalign case.
+      LibFunc TLIFn;
+      if (!TLI || !TLI->getLibFunc(*CB->getCalledFunction(), TLIFn) ||
+          !TLI->has(TLIFn))
+        return Unknown();
+
+      if (TLIFn != LibFunc_posix_memalign)
+        return unknown();
+
+      Value *Size = CB->getOperand(2);
+      auto *C = dyn_cast<ConstantInt>(Size);
+      if (!C)
+        return Unknown();
+
+      SizeOffsets.push_back(
+          {C->getValue(), APInt(C->getValue().getBitWidth(), 0)});
+    }
+
+    // Are we storing a computable value?
+    else if (auto *SI = dyn_cast<StoreInst>(V)) {
+      if (Options.AA && Options.AA->isNoAlias(SI->getOperand(0), &LI)) {
+        // According to AA, this store is dead at `LI` point, so skip it.
+        continue;
+      }
+      auto SizeOffset = compute(SI->getOperand(0));
+      SizeOffsets.push_back(SizeOffset);
+    }
+
+    // Bail out.
+    else {
+      return Unknown();
+    }
+  }
+
+  if (SizeOffsets.empty())
+    return Unknown();
+
+  return std::accumulate(SizeOffsets.begin() + 1, SizeOffsets.end(),
+                         SizeOffsets.front(),
+                         [this](SizeOffsetType LHS, SizeOffsetType RHS) {
+                           return combineSizeOffset(LHS, RHS);
+                         });
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::combineSizeOffset(SizeOffsetType LHS,
                                                           SizeOffsetType RHS) {
   if (!bothKnown(LHS) || !bothKnown(RHS))
     return unknown();
 
   switch (Options.EvalMode) {
   case ObjectSizeOpts::Mode::Min:

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

Instruction *InstCombinerImpl::visitCallInst(CallInst &CI) {
   if (II->isCommutative()) {
     if (CallInst *NewCall = canonicalizeConstantArg0ToArg1(CI))
       return NewCall;
   }
 
   Intrinsic::ID IID = II->getIntrinsicID();
   switch (IID) {
   case Intrinsic::objectsize:
-    if (Value *V = lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/false))
+    if (Value *V = lowerObjectSizeCall(II, DL, &TLI, AA, /*MustSucceed=*/false))
       return replaceInstUsesWith(CI, V);
     return nullptr;
   case Intrinsic::abs: {
     Value *IIOperand = II->getArgOperand(0);
     bool IntMinIsPoison = cast<Constant>(II->getArgOperand(1))->isOneValue();
 
     // abs(-x) -> abs(x)
     // TODO: Copy nsw if it was present on the neg?

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (unsigned i = 0, e = Users.size(); i != e; ++i) {
       if (!Users[i])
        continue;
 
       Instruction *I = cast<Instruction>(&*Users[i]);
 
       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
         if (II->getIntrinsicID() == Intrinsic::objectsize) {
           Value *Result =
-              lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/true);
+              lowerObjectSizeCall(II, DL, &TLI, AA, /*MustSucceed=*/true);
           replaceInstUsesWith(*I, Result);
           eraseInstFromFunction(*I);
           Users[i] = nullptr; // Skip examining in the next loop.
         }
       }
     }
     for (unsigned i = 0, e = Users.size(); i != e; ++i) {
       if (!Users[i])

llvm/test/Transforms/InstCombine/builtin-object-size-posix-memalign.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare dso_local i32 @posix_memalign(i8** noundef, i64 noundef, i64 noundef)
+declare i64 @llvm.objectsize.i64.p0i8(i8*, i1 immarg, i1 immarg, i1 immarg)
+
+
+define dso_local i64 @check_posix_memalign(i32 noundef %n) local_unnamed_addr {
+; CHECK-LABEL: @check_posix_memalign(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca i8*, align 8
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @posix_memalign(i8** noundef nonnull [[PTR]], i64 noundef 8, i64 noundef 17)
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[CALL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[STOREMERGE:%.*]] = phi i64 [ 17, [[IF_END]] ], [ -1, [[IF_THEN]] ]
+; CHECK-NEXT:    ret i64 [[STOREMERGE]]
+;
+entry:
+  %retval = alloca i64
+  %ptr = alloca i8*
+  %call = call i32 @posix_memalign(i8** noundef %ptr, i64 noundef 8, i64 noundef 17)
+  %tobool = icmp ne i32 %call, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:
+  store i64 -1, i64* %retval, align 8
+  br label %return
+
+if.end:
+  %0 = load i8*, i8** %ptr, align 8
+  %1 = call i64 @llvm.objectsize.i64.p0i8(i8* %0, i1 false, i1 true, i1 false)
+  store i64 %1, i64* %retval, align 8
+  br label %return
+
+return:
+  %2 = load i64, i64* %retval, align 8
+  ret i64 %2
+
+}
+
+
+define dso_local i64 @check_posix_memalign_null() {
+; CHECK-LABEL: @check_posix_memalign_null(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca float*, align 8
+; CHECK-NEXT:    store float* null, float** [[PTR]], align 8
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast float** [[PTR]] to i8**
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @posix_memalign(i8** noundef nonnull [[TMP0]], i64 noundef 8, i64 noundef 17)
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[CALL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[STOREMERGE:%.*]] = phi i64 [ 17, [[IF_END]] ], [ -2, [[IF_THEN]] ]
+; CHECK-NEXT:    ret i64 [[STOREMERGE]]
+;
+entry:
+  %retval = alloca i64
+  %ptr = alloca float*
+  ; Make sure we handle this kind of idiomatic initialization.
+  store float* null, float** %ptr
+  %0 = bitcast float** %ptr to i8**
+  %call = call i32 @posix_memalign(i8** noundef %0, i64 noundef 8, i64 noundef 17)
+  %tobool = icmp ne i32 %call, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:
+  store i64 -2, i64* %retval
+  br label %return
+
+if.end:
+  %1 = load float*, float** %ptr
+  %2 = bitcast float* %1 to i8*
+  %3 = call i64 @llvm.objectsize.i64.p0i8(i8* %2, i1 false, i1 true, i1 false)
+  store i64 %3, i64* %retval
+  br label %return
+
+return:
+  %4 = load i64, i64* %retval
+  ret i64 %4
+}
+
+