[InstCombine] Insert instructions before adding them to worklist

[kuhar]

Summary

This patch adds instructions to the InstCombine worklist after they are properly inserted. This way we don't get <badref>s printed when logging added instructions.
It also adds a check in Worklist::Add that ensures that all added instructions have parents.

Simple test case that illustrates the difference when run with --debug-only=instcombine:

define i32 @test35(i32 %a, i32 %b) {
  %1 = or i32 %a, 1135
  %2 = or i32 %1, %b
  ret i32 %2
}

Before this patch:

INSTCOMBINE ITERATION #1 on test35
IC: ADDING: 3 instrs to worklist
IC: Visiting:   %1 = or i32 %a, 1135
IC: Visiting:   %2 = or i32 %1, %b
IC: ADD:   %2 = or i32 %a, %b
IC: Old =   %3 = or i32 %1, %b
    New =   <badref> = or i32 %2, 1135
IC: ADD:   <badref> = or i32 %2, 1135
...

With this patch:

INSTCOMBINE ITERATION #1 on test35
IC: ADDING: 3 instrs to worklist
IC: Visiting:   %1 = or i32 %a, 1135
IC: Visiting:   %2 = or i32 %1, %b
IC: ADD:   %2 = or i32 %a, %b
IC: Old =   %3 = or i32 %1, %b
    New =   <badref> = or i32 %2, 1135
IC: ADD:   %3 = or i32 %2, 1135
...

[davide]

This looks fine, I wonder whether it's worth testing [how easy it's to test, that is]

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3347

Remove the print of 'New' here?
I think we always produce redundant debug output for the Result instruction, so we still get something like this with <badref>:

IC: Old =   %t2 = insertelement <4 x float> %t1, float 2.000000e+00, i32 2
    New =   <badref> = shufflevector <4 x float> %b, <4 x float> <float undef, float 1.000000e+00, float 2.000000e+00, float undef>, <4 x i32> <i32 0, i32 5, i32 6, i32 3>
IC: ADD:   %t2 = shufflevector <4 x float> %b, <4 x float> <float undef, float 1.000000e+00, float 2.000000e+00, float undef>, <4 x i32> <i32 0, i32 5, i32 6, i32 3>

[kuhar]

This looks fine, I wonder whether it's worth testing [how easy it's to test, that is]

I'd rather not create that rely on debug messages. As an alternative, we could add an assertion in Worklist::Add checking if the added instruction has a parent. What do you think?

[lebedev.ri]

I'm not convinced this is an improvement overall.

As a concrete point: we will no longer print the 'new' if said 'new' isn't a new instruction;
as in, printing of new will now depend on the fact that it will be added into worklist,
which won't be the case if we returned preexisting instruction.

[spatel]

In D71093#1772839, @lebedev.ri wrote:

I'm not convinced this is an improvement overall.

As a concrete point: we will no longer print the 'new' if said 'new' isn't a new instruction;
as in, printing of new will now depend on the fact that it will be added into worklist,
which won't be the case if we returned preexisting instruction.

If we return the existing instruction, don't we always fall down to the else at line 3372 and print it there?

[lebedev.ri]

In D71093#1773021, @spatel wrote:

In D71093#1772839, @lebedev.ri wrote:

I'm not convinced this is an improvement overall.

As a concrete point: we will no longer print the 'new' if said 'new' isn't a new instruction;
as in, printing of new will now depend on the fact that it will be added into worklist,
which won't be the case if we returned preexisting instruction.

If we return the existing instruction, don't we always fall down to the else at line 3372 and print it there?

No, because we only get there if we return *the same* instruction we just visited.
I'm talking about the case like:

%x = mul i8 %y, 42
%t0 = sub i8 0, %x
%t1 = sub i8 0, %t0

visit %t1
... returned %x
%x != %t1

[spatel]

In D71093#1773043, @lebedev.ri wrote:

In D71093#1773021, @spatel wrote:

In D71093#1772839, @lebedev.ri wrote:

I'm not convinced this is an improvement overall.

As a concrete point: we will no longer print the 'new' if said 'new' isn't a new instruction;
as in, printing of new will now depend on the fact that it will be added into worklist,
which won't be the case if we returned preexisting instruction.

If we return the existing instruction, don't we always fall down to the else at line 3372 and print it there?

No, because we only get there if we return *the same* instruction we just visited.
I'm talking about the case like:

%x = mul i8 %y, 42
%t0 = sub i8 0, %x
%t1 = sub i8 0, %t0

visit %t1
... returned %x
%x != %t1

Ah, disregard my suggestion then. Sorry for the noise. I don't have strong feelings about the debug spew, so feel free to proceed with whatever the consensus leads to.

[kuhar]

I added an assertion checking if the instructions added have a parent (block).
Also restored the previous debug message.

For the context, I find this invariant useful for 2 reasons:

• as mentioned, we don't print badrefs
• I'm experimenting with new InstCombine iteration strategies geared towards GPU code and more local rewrites. To know control visitation better, I need to know which basic blocks to re-visit.

[kuhar]

Ping.

Do you have any other feedback? @spatel @lebedev.ri

[spatel]

In D71093#1783629, @kuhar wrote:

Ping.

Do you have any other feedback? @spatel @lebedev.ri

LGTM, but better see if @lebedev.ri concurs.
Do you have a small IR example with before/after output that we can put here in the review? That way there's at least a record of what the improvement looks like.

[kuhar]

In D71093#1783729, @spatel wrote:

Do you have a small IR example with before/after output that we can put here in the review? That way there's at least a record of what the improvement looks like.

Sure, I added one to the description.

[lebedev.ri]

I'm sorry, i'm not following the patch's logic anymore.
First it was about relying on Add() printing ADD: line, and now
all the printing stuff seems to be gone and the patch is adding some
invariants on when the instruction should be inserted into worklist?

Does the current diff still achieve the same initial goal of not printing badref?
How? If not, the description is not longer applicable, and post a new patch instead?

Apologies if i'm horribly misreading the patch?

llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h

96–97

The described behavior sounds like a bug to me.
More importantly, it's not related to the printing changes?

[kuhar]

In D71093#1783809, @lebedev.ri wrote:

I'm sorry, i'm not following the patch's logic anymore.
First it was about relying on Add() printing ADD: line, and now
all the printing stuff seems to be gone and the patch is adding some
invariants on when the instruction should be inserted into worklist?

Since the beginning, the patch was about ensuring that the instructions added to the worklist are properly inserted. One manifestation of instructions not being correctly inserted that was easy to observe was debug ADD lines with <badrefs> being printed.
One confusing thing that happened was that I followed a suggestion of reducing the amount of debug output printed and removing the line containing NEW that directly preceded ADD. But this change is no more and the amount of the debug output is the same.

Does the current diff still achieve the same initial goal of not printing badref?

Yes.

How? If not, the description is not longer applicable, and post a new patch instead?

By ensuring that instructions are inserted. I moved adding instructions later in one place in InstCombine that solves the issue.
In addition, the patch asserts that all inserted instructions have a parent (block). This is stronger than making debug logs pretty, but serves the same goal of ensuring instructions are properly inserted.

Apologies if i'm horribly misreading the patch?

I think having many iterations made is a bit messy. I also may have simplified the original description of the patch, and though that explaining the change in terms of printing will make it simpler to understand. I apologize and will try to make future patches like this be described more directly.

[kuhar]

llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h

96–97

The users that I refer to here are new instructions that are being constructed; InstCombine inserts them in subsequent calls to Add(). This happens in a few places and it's not obvious to me make it more straight-forward.
With the changes to the worklist here, everything works like before and the order of iteration is exactly the same.

Let me know if you want me to dig up some concrete examples for this behavior here.

[lebedev.ri]

In D71093#1783911, @kuhar wrote:

In D71093#1783809, @lebedev.ri wrote:

...

Okay.
Thank you for detailed responses.

I'm mainly confused because, as per the patch's description:

IC: Old = %3 = or i32 %1, %b

New =   <badref> = or i32 %2, 1135

But i think now the patch as it is now is okay,
if @spatel accepted i will not block this any further.

[nikic]

llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h

96–97

I'd appreciate an example for this. I can see how it can happen in principle, but not really why we'd write the code that way in practice.

[kuhar]

llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h

96–97

Consider the test llvm/test/Transforms/InstCombine/zext-or-icmp.ll, function zext_or_icmp_icmp:

define i8 @zext_or_icmp_icmp(i8 %a, i8 %b) {
  %mask = and i8 %a, 1
  %toBool1 = icmp eq i8 %mask, 0
  %toBool2 = icmp eq i8 %b, 0
  %bothCond = or i1 %toBool1, %toBool2
  %zext = zext i1 %bothCond to i8
  ret i8 %zext
}

Instcombine starts like this:

INSTCOMBINE ITERATION #1 on zext_or_icmp_icmp
IC: ADDING: 6 instrs to worklist
IC: Visiting:   %mask = and i8 %a, 1
IC: Visiting:   %toBool1 = icmp eq i8 %mask, 0
IC: Visiting:   %toBool2 = icmp eq i8 %b, 0
IC: Visiting:   %bothCond = or i1 %toBool1, %toBool2
IC: Visiting:   %zext = zext i1 %bothCond to i8
IC: ADD:   %toBool11 = zext i1 %toBool1 to i8
IC: ADD:   %toBool22 = zext i1 %toBool2 to i8
IC: ADD:   %1 = xor i8 %mask, 1

Instcombine wants to replace all uses of %toBool11 = zext i1 %toBool1 to i8 with %1 = xor i8 %mask, 1. One of the uses is <badref> = or i8 %toBool11, %toBool22:

IC: Replacing   %toBool11 = zext i1 %toBool1 to i8
    with   %1 = xor i8 %mask, 1
IC: Old =   %zext = zext i1 %bothCond to i8
    New =   <badref> = or i8 %1, %toBool22
IC: ADD:   %zext = or i8 %1, %toBool22

The way I understand the issue is that one of the uses is the instructions that currently being simplified. This instruction will be added to the worklist anyway once the simplification is finished.

[nikic]

llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h

96–97

Thanks for the example. This transform seems to be a pretty special case that manually runs other InstCombine transforms to prevent an infinite loop.

Assuming that this is the only case (at least I didn't get anything else running InstCombine tests), possibly we might just want to adjust the transform to insert the instruction earlier? Something along these lines:

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
index 5112fb1a6c3..70a7b9bfbba 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
@@ -1189,7 +1189,8 @@ Instruction *InstCombiner::visitZExt(ZExtInst &CI) {
       // zext (or icmp, icmp) -> or (zext icmp), (zext icmp)
       Value *LCast = Builder.CreateZExt(LHS, CI.getType(), LHS->getName());
       Value *RCast = Builder.CreateZExt(RHS, CI.getType(), RHS->getName());
-      BinaryOperator *Or = BinaryOperator::Create(Instruction::Or, LCast, RCast);
+      Value *Or = Builder.CreateOr(LCast, RCast);
+      Builder.SetInsertPoint(cast<Instruction>(Or));
 
       // Perform the elimination.
       if (auto *LZExt = dyn_cast<ZExtInst>(LCast))
@@ -1197,7 +1198,7 @@ Instruction *InstCombiner::visitZExt(ZExtInst &CI) {
       if (auto *RZExt = dyn_cast<ZExtInst>(RCast))
         transformZExtICmp(RHS, *RZExt);
 
-      return Or;
+      return replaceInstUsesWith(CI, Or);
     }
   }

I feel like doing this might be better than carving out an exception in the worklist management itself.

[kuhar]

Fix instruction insertion in InstCombineCasts for zext-or-icmp.

[kuhar]

llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h

96–97

You approach seems to like a better way than silently skipping some uses.

I ran the in-source test suite and compiled a few large projects with -O3 to make sure it works.

[kuhar]

This comment was removed by kuhar.

[nikic]

LGTM

llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h

 
 #define DEBUG_TYPE "instcombine"
 
 namespace llvm {
 
 /// InstCombineWorklist - This is the worklist management logic for
 /// InstCombine.
 class InstCombineWorklist {
-  SmallVector<Instruction*, 256> Worklist;
-  DenseMap<Instruction*, unsigned> WorklistMap;
+  SmallVector<Instruction *, 256> Worklist;
+  DenseMap<Instruction *, unsigned> WorklistMap;
 
 public:
   InstCombineWorklist() = default;
 
   InstCombineWorklist(InstCombineWorklist &&) = default;
   InstCombineWorklist &operator=(InstCombineWorklist &&) = default;
 
   bool isEmpty() const { return Worklist.empty(); }
 
   /// Add - Add the specified instruction to the worklist if it isn't already
   /// in it.
   void Add(Instruction *I) {
+    assert(I);
+    assert(I->getParent() && "Instruction not inserted yet?");
+
     if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) {
       LLVM_DEBUG(dbgs() << "IC: ADD: " << *I << '\n');
       Worklist.push_back(I);
     }
   }
 
   void AddValue(Value *V) {
     if (Instruction *I = dyn_cast<Instruction>(V))
public:
   /// AddUsersToWorkList - When an instruction is simplified, add all users of
   /// the instruction to the work lists because they might get more simplified
   /// now.
   ///
   void AddUsersToWorkList(Instruction &I) {
     for (User *U : I.users())
       Add(cast<Instruction>(U));
   }
 
 
   /// Zap - check that the worklist is empty and nuke the backing store for
   /// the map if it is large.
   void Zap() {
     assert(WorklistMap.empty() && "Worklist empty, but map not?");
 
     // Do an explicit clear, this shrinks the map if needed.
     WorklistMap.clear();
   }
 };
 
 } // end namespace llvm.
 
 #undef DEBUG_TYPE
 
 #endif

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

if (SrcI && SrcI->getOpcode() == Instruction::Or) {
     ICmpInst *LHS = dyn_cast<ICmpInst>(SrcI->getOperand(0));
     ICmpInst *RHS = dyn_cast<ICmpInst>(SrcI->getOperand(1));
     if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() &&
         (transformZExtICmp(LHS, CI, false) ||
          transformZExtICmp(RHS, CI, false))) {
       // zext (or icmp, icmp) -> or (zext icmp), (zext icmp)
       Value *LCast = Builder.CreateZExt(LHS, CI.getType(), LHS->getName());
       Value *RCast = Builder.CreateZExt(RHS, CI.getType(), RHS->getName());
-      BinaryOperator *Or = BinaryOperator::Create(Instruction::Or, LCast, RCast);
+      Value *Or = Builder.CreateOr(LCast, RCast, CI.getName());
+      if (auto *OrInst = dyn_cast<Instruction>(Or))
+        Builder.SetInsertPoint(OrInst);
 
       // Perform the elimination.
       if (auto *LZExt = dyn_cast<ZExtInst>(LCast))
         transformZExtICmp(LHS, *LZExt);
       if (auto *RZExt = dyn_cast<ZExtInst>(RCast))
         transformZExtICmp(RHS, *RZExt);
 
-      return Or;
+      return replaceInstUsesWith(CI, Or);
     }
   }
 
   // zext(trunc(X) & C) -> (X & zext(C)).
   Constant *C;
   Value *X;
   if (SrcI &&
       match(SrcI, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Constant(C)))) &&

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

while (!Worklist.isEmpty()) {
     // 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_DEBUG(raw_string_ostream SS(OrigI); I->print(SS); OrigI = SS.str(););
     LLVM_DEBUG(dbgs() << "IC: Visiting: " << OrigI << '\n');
 
     if (Instruction *Result = visit(*I)) {
       ++NumCombined;
       // Should we replace the old instruction with a new one?
       if (Result != I) {
         LLVM_DEBUG(dbgs() << "IC: Old = " << *I << '\n'
                           << "    New = " << *Result << '\n');
 
         if (I->getDebugLoc())
           Result->setDebugLoc(I->getDebugLoc());
         // Everything uses the new instruction now.
         I->replaceAllUsesWith(Result);
 
         // Move the name to the new instruction first.
         Result->takeName(I);
 
-        // Push the new instruction and any users onto the worklist.
-        Worklist.AddUsersToWorkList(*Result);
-        Worklist.Add(Result);
-
         // Insert the new instruction into the basic block...
         BasicBlock *InstParent = I->getParent();
         BasicBlock::iterator InsertPos = I->getIterator();
 
         // If we replace a PHI with something that isn't a PHI, fix up the
         // insertion point.
         if (!isa<PHINode>(Result) && isa<PHINode>(InsertPos))
           InsertPos = InstParent->getFirstInsertionPt();
 
         InstParent->getInstList().insert(InsertPos, Result);
 
+        // Push the new instruction and any users onto the worklist.
+        Worklist.AddUsersToWorkList(*Result);
+        Worklist.Add(Result);
+
         eraseInstFromFunction(*I);
       } else {
         LLVM_DEBUG(dbgs() << "IC: Mod = " << OrigI << '\n'
                           << "    New = " << *I << '\n');
 
         // If the instruction was modified, it's possible that it is now dead.
         // if so, remove it.
         if (isInstructionTriviallyDead(I, &TLI)) {

llvm/test/Transforms/InstCombine/zext-or-icmp.ll

define i8 @zext_or_icmp_icmp(i8 %a, i8 %b) {
   %zext = zext i1 %bothCond to i8
   ret i8 %zext
 
 ; CHECK-LABEL: zext_or_icmp_icmp(
 ; CHECK-NEXT:    %mask = and i8 %a, 1
 ; CHECK-NEXT:    %toBool2 = icmp eq i8 %b, 0
 ; CHECK-NEXT:    %toBool22 = zext i1 %toBool2 to i8
 ; CHECK-NEXT:    %1 = xor i8 %mask, 1
-; CHECK-NEXT:    %zext = or i8 %1, %toBool22
+; CHECK-NEXT:    %zext3 = or i8 %1, %toBool22
 ; CHECK-NEXT:    ret i8 %zext
 }
 
 ; Here, widening the or from i1 to i32 and removing one of the icmps would
 ; widen an undef value (created by the out-of-range shift), increasing the
 ; range of valid values for the return, so we can't do it.
 define i32 @dont_widen_undef() {
 entry: