[x86] machine combiner reassociation: mark EFLAGS operand as 'dead'

[spatel]

Summary

In the commentary for D11660, I noted that I wasn't sure if it was alright to create new integer machine instructions without also creating the implicit EFLAGS operand. From what I can see, the implicit operand is always created by the MachineInstrBuilder based on the instruction type, so we don't have to do that explicitly. However, in reviewing the debug output, I noticed that the operand was not marked as 'dead'. I think the machine combiner should do that to preserve future optimization opportunities that may be checking for that dead EFLAGS operand themselves.

[Gerolf]

Why would reassociation result in dead eflags again? Because it can kick-in only when eflags are dead before reassoc, so they must be dead after? The comment should be clear about why setting the attribute is correct.

-Gerolf

[kbsmith1]

LGTM after addressing Gerolf's comment.

[spatel]

Patch updated:

1. Added comment to better explain why the new operands must be dead.
2. Added more asserts to verify that assumptions are intact.
3. Split the EFLAGS check into its own function because eventually we'll want to hoist the non-architecture-specific logic into the MachineCombiner itself (there's already a TODO comment about this).

[arphaman]

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

2 ↗

(On Diff #31241)

Is there a specific reason you're using '-print-machineinstrs' instead of '-stop-after machine-combiner' here?

28 ↗

(On Diff #31241)

This line would not be needed if you use the stop-after option that I mentioned above.

[spatel]

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

2 ↗

(On Diff #31241)

Nope - just wasn't aware of that option. I'll update the patch. Thanks for the suggestion!

[spatel]

Patch updated: test case now uses '-stop-after machine-combiner' to be more efficient.

[Gerolf]

Thanks for your follow-ups. I leave it up to you if you want to address my remaining comments.
LGTM.

lib/Target/X86/X86InstrInfo.cpp

6441 ↗

(On Diff #31274)

How about: This is an ..... Set special operand attributes post re-association?

6443 ↗

(On Diff #31274)

Would setSpecialOperandAttributes() be a better name?

6450 ↗

(On Diff #31274)

Looks a bit of an overkill here.

[spatel]

lib/Target/X86/X86InstrInfo.cpp

6443 ↗

(On Diff #31274)

Yes, that's a better name. Thanks!

6450 ↗

(On Diff #31274)

Agree - it's assert-heavy. But I wanted to be extra safe for when some of the code gets hoisted up to the machine combiner. It may not be so obvious what the architecture-specific assumptions are at that point. I'll leave this in for now, and if it feels unnecessary later, we can get rid of it.

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

if (Commute) {
       Patterns.push_back(MachineCombinerPattern::MC_REASSOC_XA_BY);
     }
     return true;
   }
 
   return false;
 }
 
+/// This is an architecture-specific helper function of reassociateOps.
+/// Set special operand attributes for new instructions after reassociation.
+static void setSpecialOperandAttr(MachineInstr &OldMI1, MachineInstr &OldMI2,
+                                  MachineInstr &NewMI1, MachineInstr &NewMI2) {
+  // Integer instructions define an implicit EFLAGS source register operand as
+  // the third source (fourth total) operand.
+  if (OldMI1.getNumOperands() != 4 || OldMI2.getNumOperands() != 4)
+    return;
+
+  assert(NewMI1.getNumOperands() == 4 && NewMI2.getNumOperands() == 4 &&
+         "Unexpected instruction type for reassociation");
+  
+  MachineOperand &OldOp1 = OldMI1.getOperand(3);
+  MachineOperand &OldOp2 = OldMI2.getOperand(3);
+  MachineOperand &NewOp1 = NewMI1.getOperand(3);
+  MachineOperand &NewOp2 = NewMI2.getOperand(3);
+
+  assert(OldOp1.isReg() && OldOp1.getReg() == X86::EFLAGS && OldOp1.isDead() &&
+         "Must have dead EFLAGS operand in reassociable instruction");
+  assert(OldOp2.isReg() && OldOp2.getReg() == X86::EFLAGS && OldOp2.isDead() &&
+         "Must have dead EFLAGS operand in reassociable instruction");
+
+  (void)OldOp1;
+  (void)OldOp2;
+
+  assert(NewOp1.isReg() && NewOp1.getReg() == X86::EFLAGS &&
+         "Unexpected operand in reassociable instruction");
+  assert(NewOp2.isReg() && NewOp2.getReg() == X86::EFLAGS &&
+         "Unexpected operand in reassociable instruction");
+
+  // Mark the new EFLAGS operands as dead to be helpful to subsequent iterations
+  // of this pass or other passes. The EFLAGS operands must be dead in these new
+  // instructions because the EFLAGS operands in the original instructions must
+  // be dead in order for reassociation to occur.
+  NewOp1.setIsDead();
+  NewOp2.setIsDead();
+}
+
 /// Attempt the following reassociation to reduce critical path length:
 ///   B = A op X (Prev)
 ///   C = B op Y (Root)
 ///   ===>
 ///   B = X op Y
 ///   C = A op B
 static void reassociateOps(MachineInstr &Root, MachineInstr &Prev,
                            MachineCombinerPattern::MC_PATTERN Pattern,
static void reassociateOps(MachineInstr &Root, MachineInstr &Prev,
   bool KillX = OpX.isKill();
   bool KillY = OpY.isKill();
 
   // Create new instructions for insertion.
   MachineInstrBuilder MIB1 =
     BuildMI(*MF, Prev.getDebugLoc(), TII->get(Opcode), NewVR)
       .addReg(RegX, getKillRegState(KillX))
       .addReg(RegY, getKillRegState(KillY));
-  InsInstrs.push_back(MIB1);
-
   MachineInstrBuilder MIB2 =
     BuildMI(*MF, Root.getDebugLoc(), TII->get(Opcode), RegC)
       .addReg(RegA, getKillRegState(KillA))
       .addReg(NewVR, getKillRegState(true));
-  InsInstrs.push_back(MIB2);
 
-  // Record old instructions for deletion.
+  setSpecialOperandAttr(Root, Prev, *MIB1, *MIB2);
+
+  // Record new instructions for insertion and old instructions for deletion.
+  InsInstrs.push_back(MIB1);
+  InsInstrs.push_back(MIB2);
   DelInstrs.push_back(&Prev);
   DelInstrs.push_back(&Root);
 }
 
 void X86InstrInfo::genAlternativeCodeSequence(
     MachineInstr &Root,
     MachineCombinerPattern::MC_PATTERN Pattern,
     SmallVectorImpl<MachineInstr *> &InsInstrs,

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

-; RUN: llc -mtriple=x86_64-unknown-unknown -mcpu=x86-64 < %s | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mcpu=x86-64 | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mcpu=x86-64 -stop-after machine-combiner -o /dev/null 2>&1 | FileCheck %s --check-prefix=DEAD
 
 ; 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
+
+; DEAD:       ADD32rr
+; DEAD-NEXT:  IMUL32rr{{.*}}implicit-def dead %eflags
+; DEAD-NEXT:  IMUL32rr{{.*}}implicit-def dead %eflags
+
   %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: