[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

3767

dyn_cast -> cast

3768

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

3788

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

3726

nit: Spurious change

3758

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.

3765

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.

3776

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

3776

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

3758

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.

3765

Really good catch!

[reames]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3758

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

3776

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>(Dest->Ptr->stripPointerCasts());
+    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 *, 4> AllocaUsers(AI->users());
+    while (!AllocaUsers.empty()) {
+      auto *UserI = dyn_cast<Instruction>(AllocaUsers.pop_back_val());
+      if (isa<BitCastInst>(UserI) || isa<GetElementPtrInst>(UserI)) {
+        AllocaUsers.append(UserI->user_begin(), UserI->user_end());
+        continue;
+      }
+      if (UserI == CB)
+        continue;
+      auto *II = dyn_cast<IntrinsicInst>(UserI);
+      if (!II || !II->isLifetimeStartOrEnd())
+        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

 bb14:                                             ; preds = %bb12, %bb
   %var15 = phi i32 [ %var13, %bb12 ], [ 0, %bb ]
   call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %var2)
   ret i32 %var15
 }
 
 declare i32 @unknown(i32* %dest)
 
-define i32 @sink_to_use(i1 %c) {
-; CHECK-LABEL: @sink_to_use(
+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 [[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:    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: