MachineInstr: Make isEqual agree with getHashValue in MachineInstrExpressionTrait

[rovka]

Summary

MachineInstr::isIdenticalTo has a lot of logic for dealing with register
Defs (i.e. deciding whether to take them into account or ignore them).
This logic gets things wrong in some obscure cases, for instance if an
operand is not a Def for both the current MI and the one we are comparing to.

I'm not sure if it's possible for this to happen for regular register
operands, but it may happen in the ARM backend for special operands
which use sentinel values for the register (i.e. 0, which is neither a
physical register nor a virtual one).

This causes MachineInstrExpressionTrait::isEqual (which uses
MachineInstr::isIdenticalTo) to return true for the following
instructions, which are the same except for the fact that one sets the
flags and the other one doesn't:
%1114 = ADDrsi %1113, %216, 17, 14, _, def _
%1115 = ADDrsi %1113, %216, 17, 14, _, _

OTOH, MachineInstrExpressionTrait::getHashValue returns different
values for the 2 instructions due to the different isDef on the last
operand. In practice this means that when trying to add those
instructions to a DenseMap, they will be considered different because of
their different hash values, but when growing the map we might get an
assertion while copying from the old buckets to the new buckets because
isEqual misleadingly returns true.

This patch makes sure that isEqual and getHashValue agree, by improving
the checks in MachineInstr::isIdenticalTo when we are ignoring virtual
register definitions (which is what the Trait uses). Firstly, instead of checking
isPhysicalRegister, we use !isVirtualRegister, so that we cover both physical
registers and sentinel values. Secondly, instead of checking
MachineOperand::isReg, we use MachineOperand::isIdenticalTo, which
checks isReg, isSubReg and isDef, which are the same values that the
hash function uses to compute the hash.

Note that the function is symmetric with this change, since if the
current operand is not a Def, we check MachineOperand::isIdenticalTo,
which returns false if the operands have different isDef's.

[rovka]

This is a latent issue that triggers on one of the buildbots if the planets align. I'm holding one of Sanjay's InstCombine patches (r314698) hostage because of this bug, so please have a look. Thanks!

[kparzysz]

Here's a comment from include/llvm/CodeGen/MachineInstr.h (definition of MachineInstrExpressionTrait)

/// Special DenseMapInfo traits to compare MachineInstr* by *value* of the
/// instruction rather than by pointer value.
/// The hashing and equality testing functions ignore definitions so this is
/// useful for CSE, etc.

The isEqual function explicitly requests IgnoreVRegDefs, supposedly on the basis that getHashValue would do the same. Your observation is that this is not the case. Assuming that this comment was true at some point, it may be worthwhile to check how the deviation was introduced.

[rovka]

In D38789#894648, @kparzysz wrote:

Here's a comment from include/llvm/CodeGen/MachineInstr.h (definition of MachineInstrExpressionTrait)

/// Special DenseMapInfo traits to compare MachineInstr* by *value* of the
/// instruction rather than by pointer value.
/// The hashing and equality testing functions ignore definitions so this is
/// useful for CSE, etc.

The isEqual function explicitly requests IgnoreVRegDefs, supposedly on the basis that getHashValue would do the same. Your observation is that this is not the case. Assuming that this comment was true at some point, it may be worthwhile to check how the deviation was introduced.

Well, they ignore "proper" definitions (e.g. the %1114 vs %1115 in my example). That's a def on both instructions. But the last operand is only a def in one of the instructions, not both, so it's less clear what should happen. I tend to agree with the hashing function, which says that they are different.

Now that you mention it, I suppose they only need to be different if Check == IgnoreVRegDefs, since that is what the hashing function assumes, and only for non-virtual registers (physical and sentries). I'll update the patch to that effect.

I think in light of that idea, we should have some tests making sure that MachineInstrExpressionTrait::isEqual and getHashValue agree about things (independent of the tests for MachineInstr::isIdenticalTo).

[rovka]

Update to take into account isDef only when ignoring virtual defs, since this is what the getHashValue function assumes.
First of all, this changes from using isPhysicalRegister to using !isVirtualRegisters, which also includes the sentinel values that we're interested in.
Secondly, it changes from checking MO.getReg to checking MO.isIdenticalTo, which takes into account MO.getReg, MO.getSubReg and MO.isDef. These are the same things that the hash function combines when getting the hashes.

[rovka]

Add unit tests and update summary before commit.

lib/CodeGen/MachineInstr.cpp

for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 
     // Clients may or may not want to ignore defs when testing for equality.
     // For example, machine CSE pass only cares about finding common
     // subexpressions, so it's safe to ignore virtual register defs.
     if (MO.isDef()) {
       if (Check == IgnoreDefs)
         continue;
       else if (Check == IgnoreVRegDefs) {
-        if (TargetRegisterInfo::isPhysicalRegister(MO.getReg()) ||
-            TargetRegisterInfo::isPhysicalRegister(OMO.getReg()))
-          if (MO.getReg() != OMO.getReg())
+        if (!TargetRegisterInfo::isVirtualRegister(MO.getReg()) ||
+            !TargetRegisterInfo::isVirtualRegister(OMO.getReg()))
+          if (!MO.isIdenticalTo(OMO))
             return false;
       } else {
         if (!MO.isIdenticalTo(OMO))
           return false;
         if (Check == CheckKillDead && MO.isDead() != OMO.isDead())
           return false;
       }
     } else {