[InstCombine] Don't let an alignment assume prevent new/delete removals.

[hjyamauchi]

Summary

Remove allocations with alignment assume.

[davidxl]

Can this be generalized to all assumes? nor just the code pattern that checks alignment?

[lebedev.ri]

This is really a temporary workaround until bundle representation of assumptions is used.
It might be better to work on that instead
See also D75462.

[jdoerfert]

This is the right fix for alignment: D71739

For all assumes (and later other stuff, think lifetime markers or annotations) you can check if the User::isDroppable, and eventually drop via Value::dropDroppableUses if you cannot update them properly.

[hjyamauchi]

In D81854#2096685, @jdoerfert wrote:

This is the right fix for alignment: D71739

For all assumes (and later other stuff, think lifetime markers or annotations) you can check if the User::isDroppable, and eventually drop via Value::dropDroppableUses if you cannot update them properly.

@lebedev.ri, @jdoerfert: I acknowledge D71739. What's the status of it? Are you open to having this patch as a temporary measure until that's checked in?

[davidxl]

perhaps add a FIXME comment to point to the related patch and final state.

[jdoerfert]

In D81854#2098885, @yamauchi wrote:

In D81854#2096685, @jdoerfert wrote:

This is the right fix for alignment: D71739

For all assumes (and later other stuff, think lifetime markers or annotations) you can check if the User::isDroppable, and eventually drop via Value::dropDroppableUses if you cannot update them properly.

@lebedev.ri, @jdoerfert: I acknowledge D71739. What's the status of it? Are you open to having this patch as a temporary measure until that's checked in?

I pinged the other patch. It is basically ready, minor changes only. Let's wait a day or so and see if @Tyker responds.

[jdoerfert]

@Tyker merged D71739, if it sticks, can you check if this is still necessary?

[hjyamauchi]

Update past D71739.

[hjyamauchi]

In D81854#2114240, @jdoerfert wrote:

@Tyker merged D71739, if it sticks, can you check if this is still necessary?

Thanks. This is still necessary for this particular alloc removal case, but D71739 made it much simpler.

[davidxl]

lgtm

[jdoerfert]

Looks much better indeed ;)

Please add a commit message.

[hjyamauchi]

Update a test which was somehow missed.

[hjyamauchi]

PTAL.

[davidxl]

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

101 ↗

(On Diff #274180)

what is this change about?

[hjyamauchi]

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

101 ↗

(On Diff #274180)

This is another example that this patch improves (fixing a problem that an assume was preventing the removal of an alloca).

[davidxl]

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

88 ↗

(On Diff #274180)

This comment is out of date then

[hjyamauchi]

Address comment.

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

88 ↗

(On Diff #274180)

Updated.

[davidxl]

lgtm

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

static bool isNeverEqualToUnescapedAlloc(Value *V, const TargetLibraryInfo *TLI,
   // Two distinct allocations will never be equal.
   // We rely on LookThroughBitCast in isAllocLikeFn being false, since looking
   // through bitcasts of V can cause
   // the result statement below to be true, even when AI and V (ex:
   // i8* ->i32* ->i8* of AI) are the same allocations.
   return isAllocLikeFn(V, TLI) && V != AI;
 }
 
+// Detect an alignment check pattern like:
+//   %alloc = call i8* @_ZnwmSt11align_val_t(i64 32, i64 16) builtin
+//   %pti = ptrtoint i8* %alloc to i64
+//   %and = and i64 %pti, 15
+//   %icmp = icmp eq i64 %and, 0
+//   call void @llvm.assume(i1 %icmp)
+// If detected, store the non-alloc instructions into 'Users'.
+static bool isAllocAlignmentAssume(PtrToIntInst *PTII, Instruction *AI,
+                                   SmallVectorImpl<WeakTrackingVH> &Users,
+                                   const TargetLibraryInfo *TLI) {
+  if (!isAllocationFn(AI, TLI))
+    return false;
+
+  if (!(PTII->getOperand(0) == AI && PTII->hasOneUse()))
+    return false;
+
+  if (!isa<BinaryOperator>(*PTII->user_begin()))
+    return false;
+
+  auto *BO = cast<BinaryOperator>(*PTII->user_begin());
+  if (!(BO->getOpcode() == Instruction::And &&
+        (isa<ConstantInt>(BO->getOperand(0)) ||
+         isa<ConstantInt>(BO->getOperand(1))) &&
+        BO->hasOneUse()))
+    return false;
+
+  if (!isa<ICmpInst>(*BO->user_begin()))
+    return false;
+
+  auto *ICI = cast<ICmpInst>(*BO->user_begin());
+  if (!(ICI->hasOneUse() && (isa<ConstantInt>(ICI->getOperand(0)) ||
+                             isa<ConstantInt>(ICI->getOperand(1)))))
+    return false;
+
+  if (!isa<IntrinsicInst>(*ICI->user_begin()))
+    return false;
+
+  auto *II = cast<IntrinsicInst>(*ICI->user_begin());
+  if (II->getIntrinsicID() != Intrinsic::assume)
+    return false;
+
+  Users.emplace_back(PTII);
+  Users.emplace_back(BO);
+  Users.emplace_back(ICI);
+  Users.emplace_back(II);
+  return true;
+}
+
+// Erase the alignment assume pattern captured by isAllocAlignmentAssume() from
+// the function and 'Users'.
+static void eraseAllocAlignmentAssume(unsigned I,
+                                      SmallVectorImpl<WeakTrackingVH> &Users,
+                                      InstCombiner &IC) {
+  IntrinsicInst *II = dyn_cast<IntrinsicInst>(&*Users[I]);
+  assert(II->getIntrinsicID() == Intrinsic::assume);
+  auto *ICI = cast<ICmpInst>(II->getOperand(0));
+  assert(ICI->hasOneUse());
+  Users[I] = nullptr;
+  IC.eraseInstFromFunction(*II);
+  auto *BO = cast<BinaryOperator>(isa<ConstantInt>(ICI->getOperand(0))
+                                      ? ICI->getOperand(1)
+                                      : ICI->getOperand(0));
+  assert(BO->hasOneUse());
+  auto *PTII = cast<PtrToIntInst>(isa<ConstantInt>(BO->getOperand(0))
+                                      ? BO->getOperand(1)
+                                      : BO->getOperand(0));
+  assert(PTII->hasOneUse());
+  bool FoundICI = false, FoundBO = false, FoundPTII = false;
+  for (unsigned J = 0, E = Users.size(); J < E; ++J) {
+    Value *U = Users[J];
+    if (U == ICI || U == BO || U == PTII) {
+      if (U == ICI)
+        FoundICI = true;
+      if (U == BO)
+        FoundBO = true;
+      if (U == PTII)
+        FoundPTII = true;
+      Users[J] = nullptr;
+    }
+  }
+  assert(FoundICI && FoundBO && FoundPTII);
+  IC.eraseInstFromFunction(*ICI);
+  IC.eraseInstFromFunction(*BO);
+  IC.eraseInstFromFunction(*PTII);
+}
+
 static bool isAllocSiteRemovable(Instruction *AI,
                                  SmallVectorImpl<WeakTrackingVH> &Users,
                                  const TargetLibraryInfo *TLI) {
   SmallVector<Instruction*, 4> Worklist;
   Worklist.push_back(AI);
 
   do {
     Instruction *PI = Worklist.pop_back_val();
     for (User *U : PI->users()) {
       Instruction *I = cast<Instruction>(U);
       switch (I->getOpcode()) {
       default:
         // Give up the moment we see something we can't handle.
         return false;
 
+      case Instruction::PtrToInt: {
+        if (isAllocAlignmentAssume(cast<PtrToIntInst>(I), AI, Users, TLI))
+          continue;
+        return false;
+      }
+
       case Instruction::AddrSpaceCast:
       case Instruction::BitCast:
       case Instruction::GetElementPtr:
         Users.emplace_back(I);
         Worklist.push_back(I);
         continue;
 
       case Instruction::ICmp: {
for (unsigned i = 0, e = Users.size(); i != e; ++i) {
 
       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
         if (II->getIntrinsicID() == Intrinsic::objectsize) {
           Value *Result =
               lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/true);
           replaceInstUsesWith(*I, Result);
           eraseInstFromFunction(*I);
           Users[i] = nullptr; // Skip examining in the next loop.
-        }
+        } else if (II->getIntrinsicID() == Intrinsic::assume)
+          eraseAllocAlignmentAssume(i, Users, *this);
       }
     }
     for (unsigned i = 0, e = Users.size(); i != e; ++i) {
       if (!Users[i])
         continue;
 
       Instruction *I = cast<Instruction>(&*Users[i]);
 

llvm/test/Transforms/InstCombine/malloc-free-delete.ll

 declare void @_ZdlPvjSt11align_val_t(i8*, i32, i32) nobuiltin
 ; delete(void*, unsigned long, align_val_t)
 declare void @_ZdlPvmSt11align_val_t(i8*, i64, i64) nobuiltin
 ; delete[](void*, unsigned int, align_val_t)
 declare void @_ZdaPvjSt11align_val_t(i8*, i32, i32) nobuiltin
 ; delete[](void*, unsigned long, align_val_t)
 declare void @_ZdaPvmSt11align_val_t(i8*, i64, i64) nobuiltin
 
+declare void @llvm.assume(i1)
+
 define void @test8() {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:    ret void
 ;
   %nt = alloca i8
   %nw = call i8* @_Znwm(i64 32) builtin
   call void @_ZdlPv(i8* %nw) builtin
   %na = call i8* @_Znam(i64 32) builtin
;
   %nwa2 = call i8* @_ZnwmSt11align_val_t(i64 32, i64 8) builtin
   call void @_ZdlPvmSt11align_val_t(i8* %nwa2, i64 32, i64 8) builtin
   %nwja2 = call i8* @_ZnwjSt11align_val_t(i32 32, i32 8) builtin
   call void @_ZdlPvjSt11align_val_t(i8* %nwa2, i32 32, i32 8) builtin
   %naa2 = call i8* @_ZnamSt11align_val_t(i64 32, i64 8) builtin
   call void @_ZdaPvmSt11align_val_t(i8* %naa2, i64 32, i64 8) builtin
   %naja2 = call i8* @_ZnajSt11align_val_t(i32 32, i32 8) builtin
   call void @_ZdaPvjSt11align_val_t(i8* %naja2, i32 32, i32 8) builtin
+
+  ; Check that the alignment assume does not prevent the removal.
+  %nwa3 = call i8* @_ZnwmSt11align_val_t(i64 32, i64 16) builtin
+  %pti = ptrtoint i8* %nwa3 to i64
+  %and = and i64 %pti, 15
+  %icmp = icmp eq i64 %and, 0
+  call void @llvm.assume(i1 %icmp)
+  call void @_ZdlPvmSt11align_val_t(i8* %nwa3, i64 32, i64 16) builtin
+
   ret void
 }
 
 declare noalias i8* @"\01??2@YAPEAX_K@Z"(i64) nobuiltin
 declare void @"\01??3@YAXPEAX@Z"(i8*) nobuiltin
 
 define void @test9() {
 ; CHECK-LABEL: @test9(

 ; CHECK-NEXT:    ret void
 ;
   call void @_ZdlPv(i8* null)
   ret void
 }
 
 define void @test11() {
 ; CHECK-LABEL: @test11(
-; CHECK-NEXT:    [[CALL:%.*]] = call dereferenceable(8) i8* @_Znwm(i64 8) #6
+; CHECK-NEXT:    [[CALL:%.*]] = call dereferenceable(8) i8* @_Znwm(i64 8) #7
 ; CHECK-NEXT:    call void @_ZdlPv(i8* nonnull [[CALL]])
 ; CHECK-NEXT:    ret void
 ;
   %call = call i8* @_Znwm(i64 8) builtin
   call void @_ZdlPv(i8* %call)
   ret void
 }