[X86]: Improve Liveness checking for X86FixupBWInsts.cpp

[kbsmith1]

Summary

This improves the liveness checking for X86FixupBWInsts.cpp. Sometimes computing liveness
going backwards is overly conservative because the live-outs of the block can contain super-regs
that are not really live. This change finds candidates for BW Fixup where the tranform failed, and
when that happens, runs the liveness going forward to see if that gives a better answer.

[ab]

Can you add a testcase?

I'm hoping this is better fixed elsewhere, and we can avoid relying on kill-flags.

lib/Target/X86/X86FixupBWInsts.cpp

102–103

Have you considered returning MI itself to signify 'WasCandidate = true' ?

374

auto ?

[kbsmith1]

I'd love to add a test case. Of the spec2000 in tests, 175, 176, 252, 254, 256, and 300 all hit instances where
this new code finds new opportunities when going forward, that are missed when going backwards.

Unfortunately, so far, in looking at the cases, they are all quite large functions, and not at all amenable to
really being unit test cases.

And whether that would continue to check this code would depend on the vagaries of register allocation.

And, if you have better suggestions for how to fix this elsewhere, that would be great. The only way I really know
to solve this problem properly is for this transform to run its own, very specific data-flow.

lib/Target/X86/X86FixupBWInsts.cpp

102–103

That seems more obscure than simply having this also return the bool WasCandidate. I like the code this way because it is simple.

374

Sure, done.

[kbsmith1]

Added minimalist (as possible) test, and changed to use auto as suggested.

[echristo]

One inline comment.

-eric

test/CodeGen/X86/fixup-bw-inst-fwlive.ll

12–13 ↗

(On Diff #59964)

Can you add some more documentation on what the checks are rather than "complex" for the next person that has to do something with this testcase? :)

[kbsmith1]

Updated the comment in the test.

[ab]

This seems perfect for MIR: you could have a tiny test with two blocks, a MOV8rr and a spurious live-out.
There's one for FixupBW in test/CodeGen/X86/fixup-bw-copy.mir, but test/CodeGen/X86/eflags-copy-expansion.mir might be more a better start.

Other than that, I have no objection to the patch, but I'm worried we're papering over liveness deficiencies. Realistically though, we can't fix everything, so this is probably the best we can do right now.

As to this specific test: looks like BranchFolding, when merging tails, indiscriminately marks every register defined but not killed (it might really be live, but not necessarily) before the tail as live-in the new tail block. It queries the RegisterScavenger, which walks the original block forward, using kill flags; maybe it should walk the tail block backward instead? I might have missed something though; I'll ask Matthias or Quentin. I also have no idea if it fixes every problems you've seen.

lib/Target/X86/X86FixupBWInsts.cpp

337–339

Drop the typedef?

[kbsmith1]

Addressed comments from Ahmed. Got rid of typedef, and created MIR based test.

[kbsmith1]

Ping. I believe I have addressed all comments.

[ab]

I filed https://llvm.org/PR28142 for the BranchFolding/RegScavenger issue. Can you add a FIXME somewhere linking to that?

With that, LGTM.

lib/Target/X86/X86FixupBWInsts.cpp

class FixupBWInstPass : public MachineFunctionPass {
   /// OK, otherwise return nullptr.
   MachineInstr *tryReplaceLoad(unsigned New32BitOpcode, MachineInstr *MI) const;
 
   /// Change the MachineInstr \p MI into the equivalent 32-bit copy if it is
   /// safe to do so.  Return the replacement instruction if OK, otherwise return
   /// nullptr.
   MachineInstr *tryReplaceCopy(MachineInstr *MI) const;
 
+  // Change the MachineInstr \p MI into an eqivalent 32 bit instruction if
+  // possible.  Return the replacement instruction if OK, return nullptr
+  // otherwise. Set WasCandidate to true or false depending on whether the
+  // MI was a candidate for this sort of transformation.
+  MachineInstr *tryReplaceInstr(MachineInstr *MI, MachineBasicBlock &MBB,
+                                bool &WasCandidate) const;
 public:
   static char ID;
 
   const char *getPassName() const override {
     return FIXUPBW_DESC;
   }
 
   FixupBWInstPass() : MachineFunctionPass(ID) {
MachineInstr *FixupBWInstPass::tryReplaceCopy(MachineInstr *MI) const {
   // Drop imp-defs/uses that would be redundant with the new def/use.
   for (auto &Op : MI->implicit_operands())
     if (Op.getReg() != (Op.isDef() ? NewDestReg : NewSrcReg))
       MIB.addOperand(Op);
 
   return MIB;
 }
 
-void FixupBWInstPass::processBasicBlock(MachineFunction &MF,
-                                        MachineBasicBlock &MBB) {
-
-  // This algorithm doesn't delete the instructions it is replacing
-  // right away.  By leaving the existing instructions in place, the
-  // register liveness information doesn't change, and this makes the
-  // analysis that goes on be better than if the replaced instructions
-  // were immediately removed.
-  //
-  // This algorithm always creates a replacement instruction
-  // and notes that and the original in a data structure, until the
-  // whole BB has been analyzed.  This keeps the replacement instructions
-  // from making it seem as if the larger register might be live.
-  SmallVector<std::pair<MachineInstr *, MachineInstr *>, 8> MIReplacements;
-
-  // Start computing liveness for this block. We iterate from the end to be able
-  // to update this for each instruction.
-  LiveRegs.clear();
-  // We run after PEI, so we need to AddPristinesAndCSRs.
-  LiveRegs.addLiveOuts(MBB);
-
-  for (auto I = MBB.rbegin(); I != MBB.rend(); ++I) {
-    MachineInstr *NewMI = nullptr;
-    MachineInstr *MI = &*I;
+MachineInstr *FixupBWInstPass::tryReplaceInstr(
+                  MachineInstr *MI, MachineBasicBlock &MBB,
+                  bool &WasCandidate) const {
+  WasCandidate = false;
 
-    // See if this is an instruction of the type we are currently looking for.
-    switch (MI->getOpcode()) {
 
-    case X86::MOV8rm:
-      // Only replace 8 bit loads with the zero extending versions if
-      // in an inner most loop and not optimizing for size. This takes
-      // an extra byte to encode, and provides limited performance upside.
-      if (MachineLoop *ML = MLI->getLoopFor(&MBB)) {
-        if (ML->begin() == ML->end() && !OptForSize)
-          NewMI = tryReplaceLoad(X86::MOVZX32rm8, MI);
-      }
-      break;
+      if (ML->begin() == ML->end() && !OptForSize) {
+        WasCandidate = true;
+      }
 
-    case X86::MOV16rm:
-      // Always try to replace 16 bit load with 32 bit zero extending.
-      // Code size is the same, and there is sometimes a perf advantage
-      // from eliminating a false dependence on the upper portion of
-      // the register.
-      NewMI = tryReplaceLoad(X86::MOVZX32rm16, MI);
-      break;
+    WasCandidate = true;
 
-    case X86::MOV8rr:
-    case X86::MOV16rr:
-      // Always try to replace 8/16 bit copies with a 32 bit copy.
-      // Code size is either less (16) or equal (8), and there is sometimes a
-      // perf advantage from eliminating a false dependence on the upper portion
-      // of the register.
-      NewMI = tryReplaceCopy(MI);
-      break;
+    WasCandidate = true;
 
-    default:
-      // nothing to do here.
-      break;
-    }
 
-    if (NewMI)
+  return NewMI;
+}
+
+void FixupBWInstPass::processBasicBlock(MachineFunction &MF,
+                                        MachineBasicBlock &MBB) {
+
+  // This algorithm doesn't delete the instructions it is replacing
+  // right away.  By leaving the existing instructions in place, the
+  // register liveness information doesn't change, and this makes the
+  // analysis that goes on be better than if the replaced instructions
+  // were immediately removed.
+  //
+  // This algorithm always creates a replacement instruction
+  // and notes that and the original in a data structure, until the
+  // whole BB has been analyzed.  This keeps the replacement instructions
+  // from making it seem as if the larger register might be live.
+  typedef SmallVector<std::pair<MachineInstr *, MachineInstr *>, 8>
+    MIReplacementsType;
+  MIReplacementsType MIReplacements;
+
+  // Start computing liveness for this block. We iterate from the end to be able
+  // to update this for each instruction.
+  LiveRegs.clear();
+  // We run after PEI, so we need to AddPristinesAndCSRs.
+  LiveRegs.addLiveOuts(MBB);
+
+  bool CandidateDidntGetTransformed = false;
+  bool WasCandidate = false;
+
+  for (auto I = MBB.rbegin(); I != MBB.rend(); ++I) {
+    MachineInstr *MI = &*I;
+    
+    MachineInstr *NewMI = tryReplaceInstr(MI, MBB, WasCandidate);
+
+    // Add this to replacements if it was a candidate, even if NewMI is
+    // nullptr.  We will revisit that in a bit.
+    if (WasCandidate) {
       MIReplacements.push_back(std::make_pair(MI, NewMI));
+      if (!NewMI)
+        CandidateDidntGetTransformed = true;
+    }
 
     // We're done with this instruction, update liveness for the next one.
     LiveRegs.stepBackward(*MI);
   }
 
+  if (CandidateDidntGetTransformed) {
+    // If there was a candidate that didn't get transformed then let's try
+    // doing the register liveness going forward.  Sometimes one direction
+    // is overly conservative compared to the other.
+    LiveRegs.clear();
+    LiveRegs.addLiveIns(MBB);
+
+    MIReplacementsType::iterator NextCandidateIter = MIReplacements.begin();
+
+    for (auto I = MBB.begin(); I != MBB.end(); ++I) {
+      MachineInstr *MI = &*I;
+      SmallVector<std::pair<unsigned, const MachineOperand*>, 4> Clobbers;
+      LiveRegs.stepForward(*MI, Clobbers);
+
+      // Only check and create a new instruction if this instruction is
+      // known to be a candidate that didn't get transformed.
+      if (NextCandidateIter->first == MI) {
+        if (NextCandidateIter->second == nullptr) {
+          MachineInstr *NewMI = tryReplaceInstr(MI, MBB, WasCandidate);
+          NextCandidateIter->second = NewMI;
+        }
+        ++NextCandidateIter;
+      }
+    }
+  }
+
   while (!MIReplacements.empty()) {
     MachineInstr *MI = MIReplacements.back().first;
     MachineInstr *NewMI = MIReplacements.back().second;
     MIReplacements.pop_back();
+    if (NewMI) {
       MBB.insert(MI, NewMI);
       MBB.erase(MI);
     }
   }
+}