[instcombine] Allow sinking of calls with known writes to uses

[reames]

Summary

If we have a call whose only side effect is a write to a location which is known to be dead, we can sink said call to the users of the call's result value. This is analogous to the recent changes to delete said calls if unused, but framed as a sinking transform instead.

This is an alternative to (subset of?) D109917. Note that change leaves the nothrow and willreturn requirements in place.

[reames]

(with the right diff this time)

[nikic]

The logic here looks correct to me, but I'm still a bit uncomfortable with this addition: The core transform here is that if you have a potentially written pointer argument that is not read after the call, then it is safe to sink it. However, we currently don't have a way to indicate that this argument is not going to be read lateron, so this ends up doing some ad-hoc analysis that involves scanning all alloca users. It will be hard to meaningfully extend this, because we can't (or at least shouldn't) add sophisticated alias analysis to InstCombine. On the other hand, DSE could easily determine this as a matter of course, i.e. mark an argument as dead even if the call cannot be dropped entirely.

That would be more involved though and I don't want perfect to be the enemy of good. Is there an immediate need for this? From D109917 I got the impression that this was added purely for the sake of test coverage, and not because of a performance issue encountered in the wild.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3780

dyn_cast -> cast

3781

Should handle AddrSpaceCastInst as well.

[reames]

In D116200#3208032, @nikic wrote:

The logic here looks correct to me, but I'm still a bit uncomfortable with this addition: The core transform here is that if you have a potentially written pointer argument that is not read after the call, then it is safe to sink it. However, we currently don't have a way to indicate that this argument is not going to be read lateron, so this ends up doing some ad-hoc analysis that involves scanning all alloca users. It will be hard to meaningfully extend this, because we can't (or at least shouldn't) add sophisticated alias analysis to InstCombine. On the other hand, DSE could easily determine this as a matter of course, i.e. mark an argument as dead even if the call cannot be dropped entirely.

I do agree with your point about this being generalizable by DSE, but I want to highlight that the otherwise unused alloca case is an entirely real one. If you have an out-param which is not used in a C/C++ function, this is exactly the form we get.

That would be more involved though and I don't want perfect to be the enemy of good. Is there an immediate need for this? From D109917 I got the impression that this was added purely for the sake of test coverage, and not because of a performance issue encountered in the wild.

The original motivation for discovering the out-param example was test coverage, but the example is real. I haven't tried to quantify how broadly it covers in real code bases, but it's certainly something I have seen in the wild.

Personally, I think this is justified.

I'll also note that while doing non-trivial AA in InstCombine is probably a no-no, a simple use walk and a dominance check is pretty consistent with the existing structure. Doing just that would let us handle out-params which are only read on a success path. That is a very very common idiom. (i.e. picture a multiple condition if chain with one of them being a helper routine with an out-param)

[reames]

Address review comments

[anna]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3809

Just a comment here, I had faced this exact same issue (the current instruction writing to memory) while trying to support allocation sinking, which I alternatively addressed through D114648 by adding an extra condition that this check need not be done for noalias calls.

I like the fact that once this change lands I can do allocation sinking using this recently introduced API of wouldInstructionBeTriviallyDeadOnUnusedPaths. In other words, we will have a usage of the API in upstream, basically what I was aiming for :) .

[nikic]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3740

nit: Spurious change

3771

FWIW this could also use getUnderlyingObject() instead, as we don't care that the start of the alloca in particular is passed to the function, having an offset is fine.

3778

Unless something else already prevents this, I think you need a Visited set here to prevent potential infinite loops in unreachable code with cyclic references.

3789

Cast to IntrinsicInst isn't necessary here -- isLifetimeStartOrEnd() is actually defined on Instruction.

3789

This case is also untested. I think something we should check is that

lifetime.start
%x = call
lifetime.end

label:
use %x

doesn't get transformed into

lifetime.start
lifetime.end

label:
%x = call
use %x

I do believe the memory read check below protects against this, as we consider lifetime intrinsics to be reading memory as well.

[reames]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3771

Without handling for GEP below, underlying object doesn't gain us anything. I was planning on leaving offsets to a follow up patch with separate testing.

3778

Really good catch!

[reames]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3771

Ignore this comment. My brain was out of sync with the code, we do have GEP below.

[reames]

Address previous review comments, dropping lifetime end/start to be done in a followup with separate discussion.

[reames]

Rebase over landed tests

[reames]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3789

I landed a test inspired by this in 11a46b1 so that we don't forget it in the follow on. It's annoying much more complicated than it looks as depending on the semantics of lifetime.start/end, this may actually be a valid transform. But let's defer that conversion to that patch. :)

[nikic]

LGTM

[ronlieb]

Hi Philip
This seems to break our amdgpu buildbot https://lab.llvm.org/buildbot/#/builders/193/builds/4050

[reames]

In D116200#3223025, @ronlieb wrote:

Hi Philip
This seems to break our amdgpu buildbot https://lab.llvm.org/buildbot/#/builders/193/builds/4050

Yeah, yours and pretty much every self host. Should be fixed in 356ada9. Sorry for the breakage.

(I'll add a test separately, just didn't want to delay the fix.)

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Instruction *InstCombinerImpl::visitFreeze(FreezeInst &I) {
 
   return nullptr;
 }
 
 /// Try to move the specified instruction from its current block into the
 /// beginning of DestBlock, which can only happen if it's safe to move the
 /// instruction past all of the instructions between it and the end of its
 /// block.
-static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
+static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock,
+                                 TargetLibraryInfo &TLI) {
   assert(I->getUniqueUndroppableUser() && "Invariants didn't hold!");
   BasicBlock *SrcBlock = I->getParent();
 
   // Cannot move control-flow-involving, volatile loads, vaarg, etc.
-  if (isa<PHINode>(I) || I->isEHPad() || I->mayHaveSideEffects() ||
+  if (isa<PHINode>(I) || I->isEHPad() || I->mayThrow() || !I->willReturn() ||
       I->isTerminator())
     return false;
 
   // Do not sink static or dynamic alloca instructions. Static allocas must
   // remain in the entry block, and dynamic allocas must not be sunk in between
   // a stacksave / stackrestore pair, which would incorrectly shorten its
   // lifetime.
   if (isa<AllocaInst>(I))
     return false;
 
   // Do not sink into catchswitch blocks.
   if (isa<CatchSwitchInst>(DestBlock->getTerminator()))
     return false;
 
   // Do not sink convergent call instructions.
   if (auto *CI = dyn_cast<CallInst>(I)) {
     if (CI->isConvergent())
       return false;
   }
+
+  // Unless we can prove that the memory write isn't visibile except on the
+  // path we're sinking to, we must bail.
+  if (I->mayWriteToMemory()) {
+    // Check for case where the call writes to an otherwise dead alloca.  This
+    // shows up for unused out-params in idiomatic C/C++ code.
+    auto *CB = cast<CallBase>(I);
+    if (!CB)
+      // TODO: handle e.g. store to alloca here - only worth doing if we extend
+      // to allow reload along used path as described below.  Otherwise, this
+      // is simply a store to a dead allocation which will be removed.
+      return false;
+    Optional<MemoryLocation> Dest = MemoryLocation::getForDest(CB, TLI);
+    if (!Dest)
+      return false;
+    auto *AI = dyn_cast<AllocaInst>(getUnderlyingObject(Dest->Ptr));
+    if (!AI)
+      // TODO: allow malloc?
+      return false;
+    // TODO: allow memory access dominated by move point?  Note that since AI
+    // could have a reference to itself captured by the call, we would need to
+    // account for cycles in doing so.
+    SmallVector<const User *> AllocaUsers;
+    SmallPtrSet<const User *, 4> Visited;
+    auto pushUsers = [&](const Instruction &I) {
+      for (const User *U : I.users()) {
+        if (Visited.insert(U).second)
+          AllocaUsers.push_back(U);
+      }
+    };
+    pushUsers(*AI);
+    while (!AllocaUsers.empty()) {
+      auto *UserI = cast<Instruction>(AllocaUsers.pop_back_val());
+      if (isa<BitCastInst>(UserI) || isa<GetElementPtrInst>(UserI) ||
+          isa<AddrSpaceCastInst>(UserI)) {
+        pushUsers(*UserI);
+        continue;
+      }
+      if (UserI == CB)
+        continue;
+      // TODO: support lifetime.start/end here
+      return false;
+    }
+  }
+
   // We can only sink load instructions if there is nothing between the load and
   // the end of block that could change the value.
   if (I->mayReadFromMemory()) {
     // We don't want to do any sophisticated alias analysis, so we only check
     // the instructions after I in I's parent block if we try to sink to its
     // successor block.
     if (DestBlock->getUniquePredecessor() != I->getParent())
       return false;
-    for (BasicBlock::iterator Scan = I->getIterator(),
+    for (BasicBlock::iterator Scan = std::next(I->getIterator()),
                               E = I->getParent()->end();
          Scan != E; ++Scan)
       if (Scan->mayWriteToMemory())
         return false;
   }
 
   I->dropDroppableUses([DestBlock](const Use *U) {
     if (auto *I = dyn_cast<Instruction>(U->getUser()))
auto getOptionalSinkBlockForInst =
       }
       return None;
     };
 
     auto OptBB = getOptionalSinkBlockForInst(I);
     if (OptBB) {
       auto *UserParent = *OptBB;
       // Okay, the CFG is simple enough, try to sink this instruction.
-      if (TryToSinkInstruction(I, UserParent)) {
+      if (TryToSinkInstruction(I, UserParent, TLI)) {
         LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n');
         MadeIRChange = true;
         // We'll add uses of the sunk instruction below, but since
         // sinking can expose opportunities for it's *operands* add
         // them to the worklist
         for (Use &U : I->operands())
           if (Instruction *OpI = dyn_cast<Instruction>(U.get()))
             Worklist.push(OpI);

llvm/test/Transforms/InstCombine/sink_sideeffecting_instruction.ll

 
 declare i32 @unknown(i32* %dest)
 declare i32 @unknown.as2(i32 addrspace(2)* %dest)
 
 define i32 @sink_write_to_use(i1 %c) {
 ; CHECK-LABEL: @sink_write_to_use(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAR:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull writeonly [[VAR]]) #[[ATTR1:[0-9]+]]
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EARLY_RETURN:%.*]], label [[USE_BLOCK:%.*]]
 ; CHECK:       early_return:
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       use_block:
+; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull writeonly [[VAR]]) #[[ATTR1:[0-9]+]]
 ; CHECK-NEXT:    ret i32 [[VAR3]]
 ;
 entry:
   %var = alloca i32, align 4
   %var3 = call i32 @unknown(i32* writeonly %var) argmemonly nounwind willreturn
   br i1 %c, label %early_return, label %use_block
 
 early_return:
   ret i32 0
 
 use_block:
   ret i32 %var3
 }
 
 define i32 @sink_readwrite_to_use(i1 %c) {
 ; CHECK-LABEL: @sink_readwrite_to_use(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAR:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull [[VAR]]) #[[ATTR1]]
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EARLY_RETURN:%.*]], label [[USE_BLOCK:%.*]]
 ; CHECK:       early_return:
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       use_block:
+; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull [[VAR]]) #[[ATTR1]]
 ; CHECK-NEXT:    ret i32 [[VAR3]]
 ;
 entry:
   %var = alloca i32, align 4
   %var3 = call i32 @unknown(i32* %var) argmemonly nounwind willreturn
   br i1 %c, label %early_return, label %use_block
 
 early_return:
   ret i32 0
 
 use_block:
   ret i32 %var3
 }
 
 define i32 @sink_bitcast(i1 %c) {
 ; CHECK-LABEL: @sink_bitcast(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAR:%.*]] = alloca i8, align 8
-; CHECK-NEXT:    [[BITCAST:%.*]] = bitcast i8* [[VAR]] to i32*
-; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull [[BITCAST]]) #[[ATTR1]]
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EARLY_RETURN:%.*]], label [[USE_BLOCK:%.*]]
 ; CHECK:       early_return:
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       use_block:
+; CHECK-NEXT:    [[BITCAST:%.*]] = bitcast i8* [[VAR]] to i32*
+; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull [[BITCAST]]) #[[ATTR1]]
 ; CHECK-NEXT:    ret i32 [[VAR3]]
 ;
 entry:
   %var = alloca i8, align 8
   %bitcast = bitcast i8* %var to i32*
   %var3 = call i32 @unknown(i32* %bitcast) argmemonly nounwind willreturn
   br i1 %c, label %early_return, label %use_block
 
 early_return:
   ret i32 0
 
 use_block:
   ret i32 %var3
 }
 
 
 define i32 @sink_gep1(i1 %c) {
 ; CHECK-LABEL: @sink_gep1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAR1:%.*]] = alloca [2 x i32], align 8
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[VAR1]], i64 0, i64 1
-; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull [[GEP]]) #[[ATTR1]]
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EARLY_RETURN:%.*]], label [[USE_BLOCK:%.*]]
 ; CHECK:       early_return:
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       use_block:
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[VAR1]], i64 0, i64 1
+; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull [[GEP]]) #[[ATTR1]]
 ; CHECK-NEXT:    ret i32 [[VAR3]]
 ;
 entry:
   %var = alloca i64, align 8
   %bitcast = bitcast i64* %var to i32*
   %gep = getelementptr i32, i32* %bitcast, i32 1
   %var3 = call i32 @unknown(i32* %gep) argmemonly nounwind willreturn
   br i1 %c, label %early_return, label %use_block
 
 early_return:
   ret i32 0
 
 use_block:
   ret i32 %var3
 }
 
 define i32 @sink_gep2(i1 %c) {
 ; CHECK-LABEL: @sink_gep2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAR1:%.*]] = alloca [2 x i32], align 8
-; CHECK-NEXT:    [[VAR1_SUB:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[VAR1]], i64 0, i64 0
-; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull [[VAR1_SUB]]) #[[ATTR1]]
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EARLY_RETURN:%.*]], label [[USE_BLOCK:%.*]]
 ; CHECK:       early_return:
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       use_block:
+; CHECK-NEXT:    [[VAR1_SUB:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[VAR1]], i64 0, i64 0
+; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull [[VAR1_SUB]]) #[[ATTR1]]
 ; CHECK-NEXT:    ret i32 [[VAR3]]
 ;
 entry:
   %var = alloca i64, align 8
   %bitcast = bitcast i64* %var to i32*
   %var3 = call i32 @unknown(i32* %bitcast) argmemonly nounwind willreturn
   br i1 %c, label %early_return, label %use_block
 
 early_return:
   ret i32 0
 
 use_block:
   ret i32 %var3
 }
 
 define i32 @sink_addrspacecast(i1 %c) {
 ; CHECK-LABEL: @sink_addrspacecast(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAR:%.*]] = alloca i32, align 8
-; CHECK-NEXT:    [[CAST:%.*]] = addrspacecast i32* [[VAR]] to i32 addrspace(2)*
-; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown.as2(i32 addrspace(2)* [[CAST]]) #[[ATTR1]]
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EARLY_RETURN:%.*]], label [[USE_BLOCK:%.*]]
 ; CHECK:       early_return:
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       use_block:
+; CHECK-NEXT:    [[CAST:%.*]] = addrspacecast i32* [[VAR]] to i32 addrspace(2)*
+; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown.as2(i32 addrspace(2)* [[CAST]]) #[[ATTR1]]
 ; CHECK-NEXT:    ret i32 [[VAR3]]
 ;
 entry:
   %var = alloca i32, align 8
   %cast = addrspacecast i32* %var to i32 addrspace(2)*
   %var3 = call i32 @unknown.as2(i32 addrspace(2)* %cast) argmemonly nounwind willreturn
   br i1 %c, label %early_return, label %use_block
 

 use_block:
   br label %merge
 }
 
 define i32 @sink_lifetime3(i1 %c) {
 ; CHECK-LABEL: @sink_lifetime3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[VAR:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull [[VAR]]) #[[ATTR1]]
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EARLY_RETURN:%.*]], label [[USE_BLOCK:%.*]]
 ; CHECK:       early_return:
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       use_block:
+; CHECK-NEXT:    [[VAR3:%.*]] = call i32 @unknown(i32* nonnull [[VAR]]) #[[ATTR1]]
 ; CHECK-NEXT:    ret i32 [[VAR3]]
 ;
 entry:
   %var = alloca i32, align 4
   %bitcast = bitcast i32* %var to i8*
   call void @llvm.lifetime.start.p0i8(i64 4, i8* %bitcast)
   call void @llvm.lifetime.end.p0i8(i64 4, i8* %bitcast)
   ; If unknown accesses %var, that's UB