[x86] reassociate integer multiplies using machine combiner pass

[spatel]

Summary

If I've done this correctly, then the patch is nearly trivial. :)
Is MachineOperand.isDead() the proper predicate for the EFLAGS operand of an integer math op that we want to reassociate?

This is part of fixing:
https://llvm.org/bugs/show_bug.cgi?id=21768

[Gerolf]

The machine code verifier used the isDead flag, so my assumption would be that it is safe to assume it is set correctly at the point of use in this code. If there is a way to assert this that would be even better.

lib/Target/X86/X86InstrInfo.cpp

6309 ↗

(On Diff #31066)

The intention of the code is checking for a binary operator with EFLAG. When the flag is dead the function returns false.
I see two things to think about: first, why not having a function that makes it explicit incl. an assertion that the third operand actually is an eflag? In the current implementation the assumptions are implicit, so a function would make them more explicit/clear.
Second, the host function checks whether or not a virtual register is defined in \param Inst. It returns true when that is the case. Why doesn't the code check for virtual defs when eflags is dead? So I think its purpose is to eliminate dead instructions in general and binary operators with eflags is perhaps just a special case.

[spatel]

lib/Target/X86/X86InstrInfo.cpp

6309 ↗

(On Diff #31066)

Thanks, Gerolf. I agree that I should make this more clear by splitting off the check and adding an assert.

To make my intention for this check more clear: if the EFLAGS operand on an integer math op is *not* dead, then I was thinking that those ops are involved in some kind of overflow or other exception-checking sequence, so it's not safe to rearrange the math. If the EFLAGS operands *are* dead, then the ops are part of normal integer math, so it is safe to do the reassociation.

[kbsmith1]

Test LGTM. Slight comment on the code.

lib/Target/X86/X86InstrInfo.cpp

6312 ↗

(On Diff #31066)

Is there any possibility of 4 operand instructions where operand number 3 is dead, but is not EFLAGS? It seems like a check for (Inst.getOperand(3).isReg && Inst.getOperand(3).getReg() == X86::EFLAGS && !Inst.getOperand(3).isDead()) would be safer and more future proof.

[kbsmith1]

Slight correction to my comment on the code.

lib/Target/X86/X86InstrInfo.cpp

6312 ↗

(On Diff #31066)

My proposed code isn't really quite correct. I think the correct formulation would be:
if (!Inst.getOperand(3).isReg() || Inst.getOperand(3).getReg() != X86::EFLAGS || !Inst.getOperand(3).isDead()) return false.

[spatel]

Patch updated based on feedback from Gerolf and Kevin (thanks!):

1. Rename hasVirtualRegDefsInBasicBlock -> hasReassociableOperands (the function is more general now)
2. Update comment on EFLAGS check to make it clearer (I hope)
3. Add asserts about that 3rd operand which we assume must be EFLAGS

[kbsmith1]

LGTM

[spatel]

lib/Target/X86/X86InstrInfo.cpp

6506 ↗

(On Diff #31089)

Is it ok that I'm not explicitly adding a dead EFLAGS operand (if this is an integer instruction)? I see that the operand gets added later anyway based on the instruction type, but I wonder if it's poor form to not do it right here.

[Gerolf]

The machine code verifier used the isDead flag, so my assumption would be that it is safe to assume it is set correctly at the point of use in this code. If there is a way to assert this that would be even better.

lib/Target/X86/X86InstrInfo.cpp

6309 ↗

(On Diff #31089)

Thanks for the clarification.

[spatel]

lib/Target/X86/X86InstrInfo.cpp

6506 ↗

(On Diff #31089)

For future reference: I stepped through this in the debugger, and the EFLAGS implicit operand is added when the instruction is created, so there does not appear to be any need to do this explicitly.

llvm/trunk/lib/Target/X86/X86InstrInfo.cpp

 bool X86InstrInfo::
 hasHighOperandLatency(const TargetSchedModel &SchedModel,
                       const MachineRegisterInfo *MRI,
                       const MachineInstr *DefMI, unsigned DefIdx,
                       const MachineInstr *UseMI, unsigned UseIdx) const {
   return isHighLatencyDef(DefMI->getOpcode());
 }
 
-static bool hasVirtualRegDefsInBasicBlock(const MachineInstr &Inst,
-                                          const MachineBasicBlock *MBB) {
-  assert(Inst.getNumOperands() == 3 && "Reassociation needs binary operators");
+static bool hasReassociableOperands(const MachineInstr &Inst,
+  assert((Inst.getNumOperands() == 3 || Inst.getNumOperands() == 4) &&
+         "Reassociation needs binary operators");
   const MachineOperand &Op1 = Inst.getOperand(1);
   const MachineOperand &Op2 = Inst.getOperand(2);
   const MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
 
-  // We need virtual register definitions.
+  // Integer binary math/logic instructions have a third source operand:
+  // the EFLAGS register. That operand must be both defined here and never
+  // used; ie, it must be dead. If the EFLAGS operand is live, then we can
+  // not change anything because rearranging the operands could affect other
+  // instructions that depend on the exact status flags (zero, sign, etc.)
+  // that are set by using these particular operands with this operation.
+  if (Inst.getNumOperands() == 4) {
+    assert(Inst.getOperand(3).isReg() &&
+           Inst.getOperand(3).getReg() == X86::EFLAGS &&
+           "Unexpected operand in reassociable instruction");
+    if (!Inst.getOperand(3).isDead())
+      return false;
+  }
+  
+  // We need virtual register definitions for the operands that we will
+  // reassociate.
   MachineInstr *MI1 = nullptr;
   MachineInstr *MI2 = nullptr;
   if (Op1.isReg() && TargetRegisterInfo::isVirtualRegister(Op1.getReg()))
     MI1 = MRI.getUniqueVRegDef(Op1.getReg());
   if (Op2.isReg() && TargetRegisterInfo::isVirtualRegister(Op2.getReg()))
     MI2 = MRI.getUniqueVRegDef(Op2.getReg());
 
   // And they need to be in the trace (otherwise, they won't have a depth).
   if (MI1 && MI2 && MI1->getParent() == MBB && MI2->getParent() == MBB)
     return true;
 
   return false;
 }
 
-static bool hasReassocSibling(const MachineInstr &Inst, bool &Commuted) {
+static bool hasReassociableSibling(const MachineInstr &Inst, bool &Commuted) {
   const MachineBasicBlock *MBB = Inst.getParent();
   const MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
   MachineInstr *MI1 = MRI.getUniqueVRegDef(Inst.getOperand(1).getReg());
   MachineInstr *MI2 = MRI.getUniqueVRegDef(Inst.getOperand(2).getReg());
   unsigned AssocOpcode = Inst.getOpcode();
 
   // If only one operand has the same opcode and it's the second source operand,
   // the operands must be commuted.
   Commuted = MI1->getOpcode() != AssocOpcode && MI2->getOpcode() == AssocOpcode;
   if (Commuted)
     std::swap(MI1, MI2);
 
   // 1. The previous instruction must be the same type as Inst.
   // 2. The previous instruction must have virtual register definitions for its
   //    operands in the same basic block as Inst.
   // 3. The previous instruction's result must only be used by Inst.
   if (MI1->getOpcode() == AssocOpcode &&
-      hasVirtualRegDefsInBasicBlock(*MI1, MBB) &&
+      hasReassociableOperands(*MI1, MBB) &&
       MRI.hasOneNonDBGUse(MI1->getOperand(0).getReg()))
     return true;
 
   return false;
 }
 
 // TODO: There are many more machine instruction opcodes to match:
 //       1. Other data types (integer, vectors)
 //       2. Other math / logic operations (and, or)
 static bool isAssociativeAndCommutative(const MachineInstr &Inst) {
   switch (Inst.getOpcode()) {
+  case X86::IMUL16rr:
+  case X86::IMUL32rr:
+  case X86::IMUL64rr:
+    return true;
   case X86::ADDSDrr:
   case X86::ADDSSrr:
   case X86::VADDSDrr:
   case X86::VADDSSrr:
   case X86::MULSDrr:
   case X86::MULSSrr:
   case X86::VMULSDrr:
   case X86::VMULSSrr:
     return Inst.getParent()->getParent()->getTarget().Options.UnsafeFPMath;
   default:
     return false;
   }
 }
 
 /// Return true if the input instruction is part of a chain of dependent ops
 /// that are suitable for reassociation, otherwise return false.
 /// If the instruction's operands must be commuted to have a previous
 /// instruction of the same type define the first source operand, Commuted will
 /// be set to true.
-static bool isReassocCandidate(const MachineInstr &Inst, bool &Commuted) {
+static bool isReassociationCandidate(const MachineInstr &Inst, bool &Commuted) {
   // 1. The operation must be associative and commutative.
   // 2. The instruction must have virtual register definitions for its
   //    operands in the same basic block.
   // 3. The instruction must have a reassociable sibling.
   if (isAssociativeAndCommutative(Inst) &&
-      hasVirtualRegDefsInBasicBlock(Inst, Inst.getParent()) &&
-      hasReassocSibling(Inst, Commuted))
+      hasReassociableOperands(Inst, Inst.getParent()) &&
+      hasReassociableSibling(Inst, Commuted))
     return true;
 
   return false;
 }
 
 // FIXME: This has the potential to be expensive (compile time) while not
 // improving the code at all. Some ways to limit the overhead:
 // 1. Track successful transforms; bail out if hit rate gets too low.
 // 2. Only enable at -O3 or some other non-default optimization level.
 // 3. Pre-screen pattern candidates here: if an operand of the previous
 //    instruction is known to not increase the critical path, then don't match
 //    that pattern.
 bool X86InstrInfo::getMachineCombinerPatterns(MachineInstr &Root,
         SmallVectorImpl<MachineCombinerPattern::MC_PATTERN> &Patterns) const {
   // TODO: There is nothing x86-specific here except the instruction type.
   // This logic could be hoisted into the machine combiner pass itself.
 
   // Look for this reassociation pattern:
   //   B = A op X (Prev)
   //   C = B op Y (Root)
 
   bool Commute;
-  if (isReassocCandidate(Root, Commute)) {
+  if (isReassociationCandidate(Root, Commute)) {
     // We found a sequence of instructions that may be suitable for a
     // reassociation of operands to increase ILP. Specify each commutation
     // possibility for the Prev instruction in the sequence and let the
     // machine combiner decide if changing the operands is worthwhile.
     if (Commute) {
       Patterns.push_back(MachineCombinerPattern::MC_REASSOC_AX_YB);
       Patterns.push_back(MachineCombinerPattern::MC_REASSOC_XA_YB);
     } else {

llvm/trunk/test/CodeGen/X86/machine-combiner-int.ll

+; RUN: llc -mtriple=x86_64-unknown-unknown -mcpu=x86-64 < %s | FileCheck %s
+
+; Verify that integer multiplies are reassociated. The first multiply in 
+; each test should be independent of the result of the preceding add (lea).
+
+define i16 @reassociate_muls_i16(i16 %x0, i16 %x1, i16 %x2, i16 %x3) {
+; CHECK-LABEL: reassociate_muls_i16:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    leal   (%rdi,%rsi), %eax
+; CHECK-NEXT:    imull  %ecx, %edx
+; CHECK-NEXT:    imull  %edx, %eax
+; CHECK-NEXT:    retq
+  %t0 = add i16 %x0, %x1
+  %t1 = mul i16 %x2, %t0
+  %t2 = mul i16 %x3, %t1
+  ret i16 %t2
+}
+
+define i32 @reassociate_muls_i32(i32 %x0, i32 %x1, i32 %x2, i32 %x3) {
+; CHECK-LABEL: reassociate_muls_i32:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    leal   (%rdi,%rsi), %eax
+; CHECK-NEXT:    imull  %ecx, %edx
+; CHECK-NEXT:    imull  %edx, %eax
+; CHECK-NEXT:    retq
+  %t0 = add i32 %x0, %x1
+  %t1 = mul i32 %x2, %t0
+  %t2 = mul i32 %x3, %t1
+  ret i32 %t2
+}
+
+define i64 @reassociate_muls_i64(i64 %x0, i64 %x1, i64 %x2, i64 %x3) {
+; CHECK-LABEL: reassociate_muls_i64:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    leaq   (%rdi,%rsi), %rax
+; CHECK-NEXT:    imulq  %rcx, %rdx
+; CHECK-NEXT:    imulq  %rdx, %rax
+; CHECK-NEXT:    retq
+  %t0 = add i64 %x0, %x1
+  %t1 = mul i64 %x2, %t0
+  %t2 = mul i64 %x3, %t1
+  ret i64 %t2
+}