Ignore/Drop droppable uses for code-sinking in InstCombine

[Tyker]

Summary

This patch allows code-sinking in InstCombine to be performed when instruction have uses in llvm.assume.

Use are considered droppable when it is preferable to modify the User such that the use disappears rather than to prevent a transformation because of the use.
for now uses are considered droppable if they are in an llvm.assume.

[jdoerfert]

Please add a commit message on this one and maybe remove the WIP tag as it is supposed to be reviewed and actually working, right?

[Tyker]

In D73832#1853677, @jdoerfert wrote:

Please add a commit message on this one and maybe remove the WIP tag as it is supposed to be reviewed and actually working, right?

the title kind says it all. yes it is working as expected and should be ready for review.

code-sinking in InstCombine is far from as aggressive as it could be. is it also done somewhere else ?
i think that instead of a single use in the successor block we could just code-sink to the successor block dominate all undroppable uses of the instruction if it exists.
or maybe find the highest common dominator of all undroppable uses and if it is not the current basic block code-sink the instruction to it.

[jdoerfert]

In D73832#1853708, @Tyker wrote:

In D73832#1853677, @jdoerfert wrote:

Please add a commit message on this one and maybe remove the WIP tag as it is supposed to be reviewed and actually working, right?

the title kind says it all. yes it is working as expected and should be ready for review.

Arguably, "droppable uses" is a new concept you need to explain in the commit message.

code-sinking in InstCombine is far from as aggressive as it could be. is it also done somewhere else ?
i think that instead of a single use in the successor block we could just code-sink to the successor block dominate all undroppable uses of the instruction if it exists.
or maybe find the highest common dominator of all undroppable uses and if it is not the current basic block code-sink the instruction to it.

There is for sure potential, I think we have another sinking pass but I'd need to check.

[Tyker]

rebased

[jdoerfert]

llvm/lib/Transforms/Utils/KnowledgeRetention.cpp

263 ↗

(On Diff #245463)

We do we disallow empty BundleOpInfo here?

llvm/test/Transforms/InstCombine/assume.ll

294

Why don't we sink this one anymore?

441

This test opens up the question if we want to sink simple instructions when we need to destroy assumes. I guess that is unrelated to this patch though.

466

Could you add a test case with a FIXME that show we drop too many assumes when we sink, e.g. the ones that are still dominated.

[Tyker]

llvm/lib/Transforms/Utils/KnowledgeRetention.cpp

263 ↗

(On Diff #245463)

i am not sure i understood the question.

we will return true for empty bundles.

this is a simple utility to check if the operand bundle of an llvm.assume still holds any information. it is used in a few places because instcombine was removing instructions like call void @llvm.assume(i1 true) ["nonnull"(%p)] because the argument to the call is known to be true so the assume was considered useless which is not true anymore.

llvm/test/Transforms/InstCombine/assume.ll

294

in this case there is a single use which is droppable (in an llvm.assume). so hasOneUse return true, but getSingleUndroppableUse returns null. so the old passe will sink the instruction whereas the new won't.

this doesn't matter however because this instruction is only used in an @llvm.assume so it is already dead and the backend will it cleanup.

[jdoerfert]

llvm/lib/Transforms/Utils/KnowledgeRetention.cpp

263 ↗

(On Diff #245463)

Oh, empty bundles like call void @llvm.assume(i1 true) ["cold"()] ?
Maybe we should put a comment here because I will forget again.

Nit: no != nullptr

[Tyker]

llvm/lib/Transforms/Utils/KnowledgeRetention.cpp

263 ↗

(On Diff #245463)

call void @llvm.assume(i1 true) ["cold"()] is not considered empty.

this function returns true for truly empty/absent bundles like call void @llvm.assume(i1 true).
or for bundles for which there was WasOn arguments but they have all been dropped. for example if we had call void @llvm.assume(i1 true) ["nonnull"(%p)] and the use of %p get gets dropped. all the only information the assume contains is that a value used to be nonnull, which is basically useless. so the function returns true for those bundles as well.

the general rule is this function returns true if the operand bundle of the assume doesn't hold any usable information. so if this function returns true and the argument of the assume is always true the whole assume should be removed.

i realize that this function probably deserve a more detailed comment.

[lebedev.ri]

llvm/lib/IR/AsmWriter.cpp

2557 ↗

(On Diff #245463)

Would it be better to ensure that we can't end up in such
seemingly-degenerate state in the first place,
by cleaning up bundles?

[Tyker]

llvm/lib/IR/AsmWriter.cpp

2557 ↗

(On Diff #245463)

i agree than not having that state would be better but i don't think it is possible without rebuilding instruction after we dropped uses in them.

an other solution could be to mark dropped uses with an undef value instead of a nullptr.

[Tyker]

llvm/lib/IR/AsmWriter.cpp

2557 ↗

(On Diff #245463)

i tried to find a better solution to represent "dropped" values. but not solution seems to be good.

• nullptr is problematic because many place assume that operands are never null.
• rebuilding instructions seems like too expensive for what we are trying to do.

maybe adding a new kind of value to represent it, that is ignored everywhere. but changing the IR for this seems like overkill.

any thought ?

[jdoerfert]

llvm/lib/IR/AsmWriter.cpp

2557 ↗

(On Diff #245463)

I like the undef solution if we clarify in the LangRef that an assume on undef is ignored.

If we could change the bundle tag we could set it to "ignore", and then pass undef.

llvm/test/Transforms/InstCombine/assume.ll

294

I see.

[Tyker]

rebased this patch on the changes of previous patches in the stack.

[Tyker]

rebased

[jdoerfert]

llvm/lib/Transforms/Utils/Local.cpp

416 ↗

(On Diff #249000)

Can you split the isAssumeWithEmptyBundle changes. They look good to me and can be commited, assuming you can add a simple test case showing that instcombine/instsimplify/... will remove certain assume(true) but not all.

For the Instcombine sutff I would probably prefer another opinion (@lebedev.ri @spatel @nikic)

[Tyker]

splitted into this patch and D76147

[jdoerfert]

I like this, let's see if someone else want to comment.

[jdoerfert]

LGTM.

[nikic]

Just a general question from my side: In what direction is this heading?

Is this particular transform (InstCombine code sinking) something where assumes were observed to be problematic in practice? Or is this more of a proof-of-concept that will be extended to other one-use checks in InstCombine? (There's a lot of them, and I'm slightly concerned about the amount of boilerplate that would have to be introduced to handle this everywhere.)

[Tyker]

In D73832#1933035, @nikic wrote:

Just a general question from my side: In what direction is this heading?

Is this particular transform (InstCombine code sinking) something where assumes were observed to be problematic in practice? Or is this more of a proof-of-concept that will be extended to other one-use checks in InstCombine? (There's a lot of them, and I'm slightly concerned about the amount of boilerplate that would have to be introduced to handle this everywhere.)

this is intended as a proof of concept, code-sinking seemed like an easy place to start. I agree with you that extending it to all of instcombine not going to be easy particularly on the testing side.
but we are going to add more assumes with patches like D75825 (disabled by default for now). so we need to minimize the negative impact of assume on other transformations. it is easier to do for assume with operand bundles rather than boolean assumes.

[MaskRay]

This patch caused an assertion failure on UserParent = PN->getIncomingBlock(*I->use_begin()); .

This can be triggered when a bootstrapped clang builds llvm-symbolizer with ThinLTO with minimized bitcode files clang -c -fthinlto-index=AutoUpgrade.o.thinlto.bc AutoUpgrade.bc -O3 (llvm/lib/IR/AutoUpgrade.cpp).

I am trying to figure out a minimal reproduce.

[MaskRay]

In D73832#1942542, @MaskRay wrote:

This patch caused an assertion failure on UserParent = PN->getIncomingBlock(*I->use_begin()); .

This can be triggered when a bootstrapped clang builds llvm-symbolizer with ThinLTO with minimized bitcode files clang -c -fthinlto-index=AutoUpgrade.o.thinlto.bc AutoUpgrade.bc -O3 (llvm/lib/IR/AutoUpgrade.cpp).

I am trying to figure out a minimal reproduce.

Pushed a probable fix: 4c52d51e784ca7603969f2a664e5430d41b9d5dc.

[nikic]

For the record, this change has caused a small but measurable compile-time regression (http://llvm-compile-time-tracker.com/compare.php?from=b539f18c565656cdd49fc0c37efbaa8e584b2d65&to=f1a9efabcb9bc37b663b0e03ed3d5a5aa7cc055e&stat=instructions). It's not a problem for this change taken by itself, but may be a problem if these APIs are going to see significantly wider use.

[Tyker]

In D73832#1942924, @MaskRay wrote:

Pushed a probable fix: 4c52d51e784ca7603969f2a664e5430d41b9d5dc.

thank you

In D73832#1943096, @nikic wrote:

For the record, this change has caused a small but measurable compile-time regression (http://llvm-compile-time-tracker.com/compare.php?from=b539f18c565656cdd49fc0c37efbaa8e584b2d65&to=f1a9efabcb9bc37b663b0e03ed3d5a5aa7cc055e&stat=instructions). It's not a problem for this change taken by itself, but may be a problem if these APIs are going to see significantly wider use.

i added a patch to minimize the overhead by storing inside the Use whether it is droppable. D76923.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Instruction *InstCombiner::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) {
-  assert(I->hasOneUse() && "Invariants didn't hold!");
+  assert(I->getSingleUndroppableUse() && "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() ||
       I->isTerminator())
     return false;
 
   // Do not sink static or dynamic alloca instructions. Static allocas must
static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
   // the end of block that could change the value.
   if (I->mayReadFromMemory()) {
     for (BasicBlock::iterator Scan = 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()))
+      return I->getParent() != DestBlock;
+    return true;
+  });
+  /// FIXME: We could remove droppable uses that are not dominated by
+  /// the new position.
+
   BasicBlock::iterator InsertPos = DestBlock->getFirstInsertionPt();
   I->moveBefore(&*InsertPos);
   ++NumSunkInst;
 
   // Also sink all related debug uses from the source basic block. Otherwise we
   // get debug use before the def. Attempt to salvage debug uses first, to
   // maximise the range variables have location for. If we cannot salvage, then
   // mark the location undef: we know it was supposed to receive a new location
if (!I->use_empty() &&
         if (isInstructionTriviallyDead(I, &TLI))
           eraseInstFromFunction(*I);
         MadeIRChange = true;
         continue;
       }
     }
 
     // See if we can trivially sink this instruction to a successor basic block.
-    if (EnableCodeSinking && I->hasOneUse()) {
+    if (EnableCodeSinking)
+      if (Use *SingleUse = I->getSingleUndroppableUse()) {
         BasicBlock *BB = I->getParent();
-      Instruction *UserInst = cast<Instruction>(*I->user_begin());
+        Instruction *UserInst = cast<Instruction>(SingleUse->getUser());
         BasicBlock *UserParent;
 
         // Get the block the use occurs in.
         if (PHINode *PN = dyn_cast<PHINode>(UserInst))
           UserParent = PN->getIncomingBlock(*I->use_begin());
         else
           UserParent = UserInst->getParent();
 
         if (UserParent != BB) {
           bool UserIsSuccessor = false;
           // See if the user is one of our successors.
-        for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
+          for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E;
+               ++SI)
             if (*SI == UserParent) {
               UserIsSuccessor = true;
               break;
             }
 
-        // If the user is one of our immediate successors, and if that successor
-        // only has us as a predecessors (we'd have to split the critical edge
-        // otherwise), we can keep going.
+          // If the user is one of our immediate successors, and if that
+          // successor only has us as a predecessors (we'd have to split the
+          // critical edge otherwise), we can keep going.
           if (UserIsSuccessor && UserParent->getUniquePredecessor()) {
             // Okay, the CFG is simple enough, try to sink this instruction.
             if (TryToSinkInstruction(I, UserParent)) {
               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);
             }
           }
         }
       }
 
     // Now that we have an instruction, try combining it to simplify it.
     Builder.SetInsertPoint(I);
     Builder.SetCurrentDebugLocation(I->getDebugLoc());
 
 #ifndef NDEBUG
     std::string OrigI;
 #endif

llvm/test/Transforms/InstCombine/assume.ll

 
 ; Make sure the above canonicalization does not trigger
 ; if the assume is control dependent on something else
 
 define i1 @nonnull3(i32** %a, i1 %control) {
 ; CHECK-LABEL: @nonnull3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LOAD:%.*]] = load i32*, i32** [[A:%.*]], align 8
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32* [[LOAD]], null
 ; CHECK-NEXT:    br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]]
 ; CHECK:       taken:
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32* [[LOAD]], null
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       not_taken:
 ; CHECK-NEXT:    [[RVAL_2:%.*]] = icmp sgt i32* [[LOAD]], null
 ; CHECK-NEXT:    ret i1 [[RVAL_2]]
 ;
 entry:
   %load = load i32*, i32** %a

 ;
   %shuf = shufflevector <4 x i8> %x, <4 x i8> undef, <4 x i32> <i32 1, i32 1, i32 2, i32 3>
   %t2 = bitcast <4 x i8> %shuf to i32
   %t3 = icmp ult i32 %t2, 65536
   call void @llvm.assume(i1 %t3)
   ret i32 %t2
 }
 
+define i1 @nonnull3A(i32** %a, i1 %control) {
+; CHECK-LABEL: @nonnull3A(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LOAD:%.*]] = load i32*, i32** [[A:%.*]], align 8
+; CHECK-NEXT:    br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32* [[LOAD]], null
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    ret i1 true
+; CHECK:       not_taken:
+; CHECK-NEXT:    [[RVAL_2:%.*]] = icmp sgt i32* [[LOAD]], null
+; CHECK-NEXT:    ret i1 [[RVAL_2]]
+;
+entry:
+  %load = load i32*, i32** %a
+  %cmp = icmp ne i32* %load, null
+  br i1 %control, label %taken, label %not_taken
+taken:
+  call void @llvm.assume(i1 %cmp)
+  ret i1 %cmp
+not_taken:
+  call void @llvm.assume(i1 %cmp)
+  %rval.2 = icmp sgt i32* %load, null
+  ret i1 %rval.2
+}
+
+define i1 @nonnull3B(i32** %a, i1 %control) {
+; CHECK-LABEL: @nonnull3B(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    [[LOAD:%.*]] = load i32*, i32** [[A:%.*]], align 8
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32* [[LOAD]], null
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]]) [ "nonnull"(i32* [[LOAD]]), "nonnull"(i1 [[CMP]]) ]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       not_taken:
+; CHECK-NEXT:    ret i1 [[CONTROL]]
+;
+entry:
+  %load = load i32*, i32** %a
+  %cmp = icmp ne i32* %load, null
+  br i1 %control, label %taken, label %not_taken
+taken:
+  call void @llvm.assume(i1 %cmp) ["nonnull"(i32* %load), "nonnull"(i1 %cmp)]
+  ret i1 %cmp
+not_taken:
+  call void @llvm.assume(i1 %cmp) ["nonnull"(i32* %load), "nonnull"(i1 %cmp)]
+  ret i1 %control
+}
+
+declare i1 @tmp1(i1)
+
+define i1 @nonnull3C(i32** %a, i1 %control) {
+; CHECK-LABEL: @nonnull3C(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    [[LOAD:%.*]] = load i32*, i32** [[A:%.*]], align 8
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32* [[LOAD]], null
+; CHECK-NEXT:    [[CMP2:%.*]] = call i1 @tmp1(i1 [[CMP]])
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       not_taken:
+; CHECK-NEXT:    ret i1 [[CONTROL]]
+;
+entry:
+  %load = load i32*, i32** %a
+  %cmp = icmp ne i32* %load, null
+  br i1 %control, label %taken, label %not_taken
+taken:
+  %cmp2 = call i1 @tmp1(i1 %cmp)
+  br label %exit
+exit:
+  ; FIXME: this shouldn't be dropped because it is still dominated by the new position of %load
+  call void @llvm.assume(i1 %cmp) ["nonnull"(i32* %load), "nonnull"(i1 %cmp)]
+  ret i1 %cmp2
+not_taken:
+  call void @llvm.assume(i1 %cmp)
+  ret i1 %control
+}
+
+define i1 @nonnull3D(i32** %a, i1 %control) {
+; CHECK-LABEL: @nonnull3D(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    [[LOAD:%.*]] = load i32*, i32** [[A:%.*]], align 8
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32* [[LOAD]], null
+; CHECK-NEXT:    [[CMP2:%.*]] = call i1 @tmp1(i1 [[CMP]])
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       not_taken:
+; CHECK-NEXT:    call void @llvm.assume(i1 true) [ "ignore"(i32* undef), "ignore"(i1 undef), "nonnull"(i1 [[CONTROL]]) ]
+; CHECK-NEXT:    ret i1 [[CONTROL]]
+;
+entry:
+  %load = load i32*, i32** %a
+  %cmp = icmp ne i32* %load, null
+  br i1 %control, label %taken, label %not_taken
+taken:
+  %cmp2 = call i1 @tmp1(i1 %cmp)
+  br label %exit
+exit:
+  ret i1 %cmp2
+not_taken:
+  call void @llvm.assume(i1 %cmp) ["nonnull"(i32* %load), "nonnull"(i1 %cmp), "nonnull"(i1 %control)]
+  ret i1 %control
+}
+
 declare void @llvm.dbg.value(metadata, metadata, metadata)
 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!5, !6, !7, !8}
 
 !0 = distinct !DICompileUnit(language: DW_LANG_C, file: !3, producer: "Me", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: null, retainedTypes: null, imports: null)
 !1 = !DILocalVariable(name: "", arg: 1, scope: !2, file: null, line: 1, type: null)
 !2 = distinct !DISubprogram(name: "debug", linkageName: "debug", scope: null, file: null, line: 0, type: null, isLocal: false, isDefinition: true, scopeLine: 1, flags: DIFlagPrototyped, isOptimized: true, unit: !0)