[X86] Memory folding for commutative instructions.

[RKSimon]

Summary

This patch improves support for commutative instructions in the x86 memory folding implementation by attempting to fold a commuted version of the instruction if the original folding fails - if that folding fails as well the instruction is 're-commuted' back to its original order before returning.

This mainly helps the stack inliner better fold reloads of 3 (or more) operand instructions (VEX encoded SSE etc.) but by performing this in the lowest foldMemoryOperandImpl implementation it also replaces the X86InstrInfo::optimizeLoadInstr version and is now used by FastISel too.

Unlike the X86InstrInfo::optimizeLoadInstr implementation it uses findCommutedOpIndices instead of hard coded commute operand indices.

[alexr]

[RKSimon]

Tidied up check for commutative instructions - we can avoid isCommutable and use findCommutedOpIndices directly and then fold anything that is commutable under certain cases (e.g. FMA instructions).

Added the missing test case.

[qcolombet]

Hi Simon

lib/Target/X86/X86InstrInfo.cpp

4218

I am not sure this is what we want generally speaking.
Indeed, if you look at the code you modified earlier (BTW having the full context would be easier for the review), we may not want to keep the commuted instruction unless the commute is in place:

MachineInstr *NewMI = commuteInstruction(MI, false);
// Unable to commute.
if (!NewMI) return 0;
if (NewMI != MI) { // <——— here if the instruction is different we do not commute.
  // New instruction. It doesn't need to be kept.
  NewMI->eraseFromParent();
  return 0;
}

Should we provide more arguments to have a finer control?

4218

I am not sure this is what we want generally speaking.
Indeed, if you look at the code you modified earlier (BTW having the full context would be easier for the review), we may not want to keep the commuted instruction unless the commute is in place:

MachineInstr *NewMI = commuteInstruction(MI, false);
Unable to commute.
if (!NewMI) return 0;
if (NewMI != MI) { <——— here if the instruction is different we do not commute.

// New instruction. It doesn't need to be kept.
NewMI->eraseFromParent();
return 0;

}
Should we provide more arguments to have a finer control?

4219

This assert is not valid.
This is legal for commuteInstruction to return nullptr.
Make an early exit here.
See r208371 for more details.

4219

This assert is not valid.
This is legal for commuteInstruction to return nullptr.
Make an early exit here.
See r208371 for more details.

4228

Ditto.

4228

Ditto.

[RKSimon]

Hi Quentin,

I've added error handling code for commuteInstruction returning nullptr or a new MachineInstr*, both before and after the commuted folding attempt. This appears to be enough and we don't need to alter either the commute or folding call arguments to support it - we can keep to in-place instruction commutes only.

Simon.

[qcolombet]

Hi Simon,

LGTM.

As a side question, do you see any performance difference with that patch?

Thanks,
-Quentin

[RKSimon]

As a side question, do you see any performance difference with that patch?

Thanks Quentin, on Jaguar I'm seeing a definite gain on (VEX encoded) SSE heavy code loops (physics, animation and vectormath), completely due to stack reload folding. On my Sandy Bridge Xeon the difference is a lot smaller / negligible. Although minor there are also improvements to code size / instruction packing.

Simon.

[RKSimon]

Closed by commit rL219584 (authored by @RKSimon).

[chapuni]

Excuse me, I have reverted this in r219595.
It broke i686 builders.

• http://bb.pgr.jp/builders/clang-3stage-i686-linux/builds/797
• http://bb.pgr.jp/builders/clang-3stage-i686-cygwin/builds/667

I'll send a reproducible testcase.ll later.

lib/Target/X86/X86FastISel.cpp

   AM.getFullAddress(AddrOps);
 
   MachineInstr *Result =
-    XII.foldMemoryOperandImpl(*FuncInfo.MF, MI, OpNo, AddrOps, Size, Alignment);
+    XII.foldMemoryOperandImpl(*FuncInfo.MF, MI, OpNo, AddrOps, Size, Alignment, /*AllowCommute=*/ true);
   if (!Result)
     return false;
 

lib/Target/X86/X86InstrInfo.h

                                       MachineInstr* MI,
                                       unsigned OpNum,
                                       const SmallVectorImpl<MachineOperand> &MOs,
-                                      unsigned Size, unsigned Alignment) const;
+                                      unsigned Size, unsigned Alignment, bool AllowCommute) const;
 
   void
   getUnconditionalBranch(MCInst &Branch,

lib/Target/X86/X86InstrInfo.cpp

   if (!DefMI->isSafeToMove(this, nullptr, SawStore))
     return nullptr;
 
-  // We try to commute MI if possible.
-  unsigned IdxEnd = (MI->isCommutable()) ? 2 : 1;
-  for (unsigned Idx = 0; Idx < IdxEnd; Idx++) {
-    // Collect information about virtual register operands of MI.
-    unsigned SrcOperandId = 0;
-    bool FoundSrcOperand = false;
-    for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
-      MachineOperand &MO = MI->getOperand(i);
-      if (!MO.isReg())
-        continue;
-      unsigned Reg = MO.getReg();
-      if (Reg != FoldAsLoadDefReg)
-        continue;
-      // Do not fold if we have a subreg use or a def or multiple uses.
-      if (MO.getSubReg() || MO.isDef() || FoundSrcOperand)
-        return nullptr;
+  // Collect information about virtual register operands of MI.
+  unsigned SrcOperandId = 0;
+  bool FoundSrcOperand = false;
+  for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
+    MachineOperand &MO = MI->getOperand(i);
+    if (!MO.isReg())
+      continue;
+    unsigned Reg = MO.getReg();
+    if (Reg != FoldAsLoadDefReg)
+    // Do not fold if we have a subreg use or a def or multiple uses.
+    if (MO.getSubReg() || MO.isDef() || FoundSrcOperand)
+      return nullptr;
 
-      SrcOperandId = i;
-      FoundSrcOperand = true;
-    }
-    if (!FoundSrcOperand) return nullptr;
 
-    // Check whether we can fold the def into SrcOperandId.
-    SmallVector<unsigned, 8> Ops;
-    Ops.push_back(SrcOperandId);
-    MachineInstr *FoldMI = foldMemoryOperand(MI, Ops, DefMI);
-    if (FoldMI) {
-      FoldAsLoadDefReg = 0;
-      return FoldMI;
-    }
 
-    if (Idx == 1) {
-      // MI was changed but it didn't help, commute it back!
-      commuteInstruction(MI, false);
-      return nullptr;
-    }
-
-    // Check whether we can commute MI and enable folding.
-    if (MI->isCommutable()) {
-      MachineInstr *NewMI = commuteInstruction(MI, false);
-      // Unable to commute.
-      if (!NewMI) return nullptr;
-      if (NewMI != MI) {
-        // New instruction. It doesn't need to be kept.
-        NewMI->eraseFromParent();
-        return nullptr;
-      }
-    }
-  }
   return nullptr;
 }
 

 X86InstrInfo::foldMemoryOperandImpl(MachineFunction &MF,
                                     MachineInstr *MI, unsigned i,
                                     const SmallVectorImpl<MachineOperand> &MOs,
-                                    unsigned Size, unsigned Align) const {
+                                    unsigned Size, unsigned Align, bool AllowCommute) const {
   const DenseMap<unsigned,
                  std::pair<unsigned,unsigned> > *OpcodeTablePtr = nullptr;
   bool isCallRegIndirect = Subtarget.callRegIndirect();

     }
   }
 
+  // If the instruction and target operand are commutable, commute the instruction and try again.
+  if (AllowCommute && MI->isCommutable()) {
+    unsigned OriginalOpIdx = i, CommuteOpIdx1, CommuteOpIdx2;
+    if (findCommutedOpIndices(MI, CommuteOpIdx1, CommuteOpIdx2)) {
+      if ((CommuteOpIdx1 == OriginalOpIdx) || (CommuteOpIdx2 == OriginalOpIdx)) {
+        MI = commuteInstruction(MI, false);
+        assert (MI && "commutable instruction failed to commute!");
+
+        unsigned CommuteOpIdx = (CommuteOpIdx1 == OriginalOpIdx ? CommuteOpIdx2 : CommuteOpIdx1);
+        NewMI = foldMemoryOperandImpl(MF, MI, CommuteOpIdx, MOs, Size, Align, /*AllowCommute=*/ false);
+        if (NewMI)
+          return NewMI;
+
+        // Folding failed again - undo the commute before returning.
+        MI = commuteInstruction(MI, false);
+        assert (MI && "commutable instruction failed to commute!");
+
+        // Return here to prevent duplicate fuse failure report.
+        return nullptr;
+      }
+    }
+  }
+
   // No fusion
   if (PrintFailedFusing && !MI->isCopy())
     dbgs() << "We failed to fuse operand " << i << " in " << *MI;

 
   SmallVector<MachineOperand,4> MOs;
   MOs.push_back(MachineOperand::CreateFI(FrameIndex));
-  return foldMemoryOperandImpl(MF, MI, Ops[0], MOs, Size, Alignment);
+  return foldMemoryOperandImpl(MF, MI, Ops[0], MOs, Size, Alignment, /*AllowCommute=*/ true);
 }
 
 static bool isPartialRegisterLoad(const MachineInstr &LoadMI,

     break;
   }
   }
-  return foldMemoryOperandImpl(MF, MI, Ops[0], MOs, 0, Alignment);
+  return foldMemoryOperandImpl(MF, MI, Ops[0], MOs, 0, Alignment, /*AllowCommute=*/ true);
 }