[CodeGen] Make MachineInstr::isIdenticalTo() symmetric.

[bjope]

Summary

MachineInstr::isIdenticalTo() is for some reason not
symmetric when comparing bundles, which gives us the
property:

I1->isIdenticalTo(*I2) != I2->isIdenticalTo(*I1)

when comparing bundles where one bundle is longer than
the other.

This patch makes sure that bundles of different length
always are considered as not being identical. Thus, the
result of the comparison will be the same regardless of
which side that happens to be to the left.

[bjope]

Needs review (just adding this comment to make this posted to llvm-commits).

[andrew.w.kaylor]

lib/CodeGen/MachineInstr.cpp

1003 ↗

(On Diff #80555)

The getOpcode() check above should guarantee that Other.isBundle() will return true, but it would be nice to mention that explicitly in the comment here. As someone reading this code for the first time, I saw one call to isBundle() followed by a comment saying "Both instructions are bundles" and it took me a minute to understand how we could know that.

1005 ↗

(On Diff #80555)

These calls to getBundleEnd() are introducing a bit of redundancy. The implementation of getBundleEnd() iterates from the given instruction until it finds an MI that returns false for isBundledWithSucc(). It should always be a small redundancy, but it could be eliminated by just checking isBundledWithSucc() here.

1011 ↗

(On Diff #80555)

I don't really like the way this loop is defined with the actual expected condition for return being checked outside the loop. You could avoid that if you rewrite it like this:

// Loop until we reach the end of both bundles.
while (I1->isBundledWithSucc() && I2->isBundledWithSucc()) {
  // If we've reached the end of just one of the two bundles, but not both,
  // the instructions are not identical.
  if (!I1->isBundledWithSucc() || !I2->isBundledWithSucc())
    return false;
  ...
}

[bjope]

Thanks for your feedback Andy!

lib/CodeGen/MachineInstr.cpp

1003 ↗

(On Diff #80555)

Ok, I agree, such an explanation would be good. I actually got confused in the same way myself.
I can update the comment as part of this patch (even though my initial thought was to make a rather minimal fix for the actual fault).

1005 ↗

(On Diff #80555)

I'll see if I can do something with isBundledWithSucc instead of using end-iterators. But for someone looking at the code for the first time, then I think using end-iterators are easier to understand (we are after all using iterators for stepping between instructions, and we must be really careful not to dereference the end-iterator etc).

(The old code that were using the end iterator for the basic block was really confusing. And I thought that using the bundle-end-iterator at least made the code less error-prone even if it includes a small redundancy.)

1011 ↗

(On Diff #80555)

I should probably have explained why my loop was designed that way :-)

(1)
My loop also handles the weird case that one bundle is empty (I'm not sure if that is legal, but there are no asserts, and I've seen this happen in our downstream backend when doing late optimisations on bundled code, removing instructions from a bundle). Even though it could be seen as a fault to have empty bundles, my loop is defensive and works even for such weird situations.
With your suggestion I either need to add asserts before the while loop that both bundles are non-empty (if empty bundles should be considered as illegal), or deem the bundles as different if only one of them is empty. The latter check is the one that you moved into the loop, so I would need to duplicate that check outside the loop. So this is one reason why I decided to go for an ugly "while(true)" loop and only have the logic for "reached the end of both bundles" in one place.

(2)
When I look into the future I see that there will be more patches in this code. We need to make it possible to skip past DBG_VALUE when stepping the iterators (or otherwise, for example, BranchFolding could end up doing different optimisation depending on the existence of DBG_VALUE inside the bundle). With that said, maybe the existence of DBG_VALUE inside bundles also is a weird scenario? We have it in our downstream backend, but that could be our own problem/fault.
The idea was to make the loop valid also if the stepping of iterators could skip DBG_VALUE. So I need to check if I reached the end of the bundle somewhere between stepping the iterator and dereferencing the iterator (the recursive call to isIdenticalTo). I'm not really sure how to do that in your example (it does not include stepping of the iterators). All my attempts of having the exit condition as a loop-condition has become messy when considering a future patch where the iterators could be stepped more than one step at a time. For such loops we need additional checks to avoid calling isIdentical when iterating past the bundle end.

My primary goal is to fix the bug. A secondary, much less important, goal is to make it easy to do a future fix about how to handle DBG_VALUE inside the bundle. Maybe I should forget about the secondary goal for now to get the bugfix accepted.
I hope that we at least agree that the old code was incorrect and the isIdenticalTo should be symmetric?

[bjope]

Updated according to suggestion from andrew.w.kaylor.

But I kept the extra check for only reaching the end of one of the bundles outside the loop. This way we also handle the rather unexpected scenario when a bundle is empty.

[andrew.w.kaylor]

I have one nitpick about a typo in a comment, but otherwise this looks good to me.

lib/CodeGen/MachineInstr.cpp

1003 ↗

(On Diff #81752)

s/than/that

llvm/trunk/lib/CodeGen/MachineInstr.cpp

bool MachineInstr::isIdenticalTo(const MachineInstr &Other,
                                  MICheckType Check) const {
   // If opcodes or number of operands are not the same then the two
   // instructions are obviously not identical.
   if (Other.getOpcode() != getOpcode() ||
       Other.getNumOperands() != getNumOperands())
     return false;
 
   if (isBundle()) {
-    // Both instructions are bundles, compare MIs inside the bundle.
+    // We have passed the test above that both instructions have the same
+    // opcode, so we know that both instructions are bundles here. Let's compare
+    // MIs inside the bundle.
+    assert(Other.isBundle() && "Expected that both instructions are bundles.");
     MachineBasicBlock::const_instr_iterator I1 = getIterator();
-    MachineBasicBlock::const_instr_iterator E1 = getParent()->instr_end();
     MachineBasicBlock::const_instr_iterator I2 = Other.getIterator();
-    MachineBasicBlock::const_instr_iterator E2 = Other.getParent()->instr_end();
-    while (++I1 != E1 && I1->isInsideBundle()) {
+    // Loop until we analysed the last intruction inside at least one of the
+    // bundles.
+    while (I1->isBundledWithSucc() && I2->isBundledWithSucc()) {
+      ++I1;
       ++I2;
-      if (I2 == E2 || !I2->isInsideBundle() || !I1->isIdenticalTo(*I2, Check))
+      if (!I1->isIdenticalTo(*I2, Check))
         return false;
     }
+    // If we've reached the end of just one of the two bundles, but not both,
+    // the instructions are not identical.
+    if (I1->isBundledWithSucc() || I2->isBundledWithSucc())
+      return false;
   }
 
   // Check operands to make sure they match.
   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = getOperand(i);
     const MachineOperand &OMO = Other.getOperand(i);
     if (!MO.isReg()) {
       if (!MO.isIdenticalTo(OMO))