[LICM] Check for noalias call instead of alloc like fn

[nikic]

Summary

When determining whether the memory is local to the function (and we can thus introduce spurious writes without thread-safety issues), check for a noalias call rather than the hardcoded list of memory allocation functions. Noalias calls are the more general way to determine allocation functions, as long as we're only interested in the property that the returned value is distinct from any other accessible memory.

[fhahn]

LGTM, thanks!

It seems at least DSE's isInvisibleToCallerAfterRet and isInvisibleToCallerBeforeRet could also use isNoAliasCall instead of isAllocLikeFn

llvm/lib/Transforms/Scalar/LICM.cpp

1939

While you are here, maybe also update this comment here?

[aganea]

Hello @nikic! It seems that rG3cef3cf02f09e397c471cf008060c89b34951959 is breaking some usages. While trying to land D108850, it was breaking on a two stage bot: https://lab.llvm.org/buildbot/#/builders/123/builds/8383
I managed to create a reproducer (to be applied on ToT):

lldCommon_bug.patch95 KBDownload

The issue can be seen in lld/COFF/DriverUtils_test.cpp, essentially the pointer is moved out of mb but it is not copied in the buffer created for the placement new in make<std::unique_ptr<MemoryBuffer>>. The target buffer pointed by getSpecificAllocSingleton<T>().Allocate() is left untouched, which later fails on deletion.

To repro:

> cd ~/llvm-project/
> git checkout 3cef3cf02f09e397c471cf008060c89b34951959
...
> mkdir stage1 && cd stage1
> cmake ../llvm -GNinja -DLLVM_ENABLE_PROJECTS='llvm;lld;clang' -DLLVM_ENABLE_ASSERTIONS=ON -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER=/usr/bin/clang-13 -DCMAKE_CXX_COMPILER=/usr/bin/clang++-13 -DCMAKE_LINKER=/usr/bin/ld.lld-13
...
> ninja
...

and then:

> cd ~/llvm-project/
> git checkout main && git pull && git checkout -b test_bug
...
> git apply lldCommon_bug.patch
...
> mkdir stage2 && cd stage2
> cmake ../llvm -GNinja -DLLVM_ENABLE_PROJECTS='llvm;lld' -DLLVM_ENABLE_ASSERTIONS=ON -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER=/home/ubuntu/llvm-project/stage1/bin/clang -DCMAKE_CXX_COMPILER=/home/ubuntu/llvm-project/stage1/bin/clang++ -DCMAKE_LINKER=/home/ubuntu/llvm-project/stage1/bin/ld.lld
...
> ninja check-lld-coff
...
Testing Time: 7.67s
  Unsupported:   8
  Passed     :  13
  Failed     : 372
FAILED: tools/lld/test/CMakeFiles/check-lld-coff
cd /home/ubuntu/llvm-project/stage2/tools/lld/test && /usr/bin/python3.8 /home/ubuntu/llvm-project/stage2/./bin/llvm-lit -sv /home/ubuntu/llvm-project/lld/test/COFF
ninja: build stopped: subcommand failed.

Would you have a chance to look into it please?

[nikic]

@aganea Could you please provide either the preprocessed source and cc1 invocation, or the unoptimized IR (-Xclang -disable-llvm-optzns) for the problematic file?

[aganea]

@nikic Please see:

repro_lldCommon_bug.7z186 KBDownload

The outcome is that we're not moving the pointer in the target buffer anymore:
(left side is git checkout 3cef3cf02f09e397c471cf008060c89b34951959^, right side is git checkout 3cef3cf02f09e397c471cf008060c89b34951959)

Let me know if there's anything else. Thanks in advance!

[nikic]

@aganea Thanks. I've looked into this, and believe the DSE optimization is correct -- the issue is an incorrect noalias annotation in https://github.com/llvm/llvm-project/blob/cd0a923b4c0c96d687303848dc1aaf39b5fe985f/llvm/include/llvm/Support/Allocator.h#L144. The BumpPtrAllocator returns memory that is already otherwise accessible to LLVM, which violates the noalias contract. It only becomes an actual issue in conjunction with DestroyAll in SpecificBumpPtrAllocator, which will scan over all allocations, and thus end up accessing the allocation through a pointer not based on the noalias return value.

[nikic]

I've put up D117664, which should fix this.

llvm/lib/Transforms/Scalar/LICM.cpp

bool isNotCapturedBeforeOrInLoop(const Value *V, const Loop *L,
   // TODO: ReturnCaptures=true shouldn't be necessary here.
   return !PointerMayBeCapturedBefore(V, /* ReturnCaptures */ true,
                                      /* StoreCaptures */ true,
                                      L->getHeader()->getTerminator(), DT);
 }
 
 /// Return true iff we can prove that a caller of this function can not inspect
 /// the contents of the provided object in a well defined program.
-bool isKnownNonEscaping(Value *Object, const Loop *L,
-                        const TargetLibraryInfo *TLI, DominatorTree *DT) {
+bool isKnownNonEscaping(Value *Object, const Loop *L, DominatorTree *DT) {
   if (isa<AllocaInst>(Object))
     // Since the alloca goes out of scope, we know the caller can't retain a
     // reference to it and be well defined.  Thus, we don't need to check for
     // capture.
     return true;
 
   // For all other objects we need to know that the caller can't possibly
   // have gotten a reference to the object.  There are two components of
   // that:
   //   1) Object can't be escaped by this function.  This is what
   //      PointerMayBeCaptured checks.
   //   2) Object can't have been captured at definition site.  For this, we
-  //      need to know the return value is noalias.  At the moment, we use a
-  //      weaker condition and handle only AllocLikeFunctions (which are
-  //      known to be noalias).  TODO
-  return isAllocLikeFn(Object, TLI) &&
-         isNotCapturedBeforeOrInLoop(Object, L, DT);
+  //      need to know the return value is noalias.
+  return isNoAliasCall(Object) && isNotCapturedBeforeOrInLoop(Object, L, DT);
 }
 
 } // namespace
 
 /// Try to promote memory values to scalars by sinking stores out of the
 /// loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant.
bool llvm::promoteLoopAccessesToScalars(
   bool IsKnownThreadLocalObject = false;
   if (SafetyInfo->anyBlockMayThrow()) {
     // If a loop can throw, we have to insert a store along each unwind edge.
     // That said, we can't actually make the unwind edge explicit. Therefore,
     // we have to prove that the store is dead along the unwind edge.  We do
     // this by proving that the caller can't have a reference to the object
     // after return and thus can't possibly load from the object.
     Value *Object = getUnderlyingObject(SomePtr);
-    if (!isKnownNonEscaping(Object, CurLoop, TLI, DT))
+    if (!isKnownNonEscaping(Object, CurLoop, DT))
       return false;
     // Subtlety: Alloca's aren't visible to callers, but *are* potentially
     // visible to other threads if captured and used during their lifetimes.
     IsKnownThreadLocalObject = !isa<AllocaInst>(Object);
   }
 
   // Check that all accesses to pointers in the aliass set use the same type.
   // We cannot (yet) promote a memory location that is loaded and stored in
bool llvm::promoteLoopAccessesToScalars(
   // stores along paths which originally didn't have them without violating the
   // memory model.
   if (!SafeToInsertStore) {
     if (IsKnownThreadLocalObject)
       SafeToInsertStore = true;
     else {
       Value *Object = getUnderlyingObject(SomePtr);
       SafeToInsertStore =
-          (isAllocLikeFn(Object, TLI) || isa<AllocaInst>(Object)) &&
+          (isNoAliasCall(Object) || isa<AllocaInst>(Object)) &&
           isNotCapturedBeforeOrInLoop(Object, CurLoop, DT);
     }
   }
 
   // If we've still failed to prove we can sink the store, hoist the load
   // only, if possible.
   if (!SafeToInsertStore && !FoundLoadToPromote)
     // If we cannot hoist the load either, give up.

llvm/test/Transforms/LICM/promote-tls.ll

 ; CHECK-NEXT:    br label [[FOR_HEADER:%.*]]
 ; CHECK:       for.header:
 ; CHECK-NEXT:    [[NEW1:%.*]] = phi i32 [ [[ADDR_PROMOTED]], [[FOR_BODY_LR_PH]] ], [ [[NEW:%.*]], [[FOR_BODY:%.*]] ]
 ; CHECK-NEXT:    [[I_02:%.*]] = phi i32 [ 0, [[FOR_BODY_LR_PH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[GUARD:%.*]] = load volatile i8*, i8** @p, align 8
 ; CHECK-NEXT:    [[EXITCMP:%.*]] = icmp eq i8* [[GUARD]], null
 ; CHECK-NEXT:    br i1 [[EXITCMP]], label [[FOR_BODY]], label [[EARLY_EXIT:%.*]]
 ; CHECK:       early-exit:
+; CHECK-NEXT:    [[NEW1_LCSSA:%.*]] = phi i32 [ [[NEW1]], [[FOR_HEADER]] ]
+; CHECK-NEXT:    store i32 [[NEW1_LCSSA]], i32* [[ADDR]], align 4
 ; CHECK-NEXT:    ret i32* null
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[NEW]] = add i32 [[NEW1]], 1
-; CHECK-NEXT:    store i32 [[NEW]], i32* [[ADDR]], align 4
 ; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_02]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[INC]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_HEADER]], label [[FOR_COND_FOR_END_CRIT_EDGE:%.*]]
 ; CHECK:       for.cond.for.end_crit_edge:
+; CHECK-NEXT:    [[NEW_LCSSA:%.*]] = phi i32 [ [[NEW]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[SPLIT:%.*]] = phi i32* [ [[ADDR]], [[FOR_BODY]] ]
+; CHECK-NEXT:    store i32 [[NEW_LCSSA]], i32* [[ADDR]], align 4
 ; CHECK-NEXT:    ret i32* null
 ;
 entry:
   %mem = call dereferenceable(16) noalias i8* @custom_malloc(i64 16)
   %addr = bitcast i8* %mem to i32*
   br label %for.body.lr.ph
 
 for.body.lr.ph:                                   ; preds = %entry