X86FixupBWInsts: Forward liveness analysis is no longer necessary.

[MatzeB]

Summary

With r274952 and rXXXX in place there are no cases left where a forward
liveness analysis yields different results to a backward one. So we can
remove the forward stepping logic.

[kbsmith1]

What have you done to prove to yourself that this code is no longer necessary?
If unnecessary, then both before and after the change, the code for 401.bzip2 from spec20006 ought to
be identical.

One way of showing that this code is no longer necessary would be to use the new code and simply
add an assertion after line 389 that NewMI was always nullptr. Once that code had been in for a while,
you could make the extra forward pass be a debug-only code in an attempt to catch other regressions
that might occur in live-reg tracking.

Also, I kind of liked the better abstraction of tryReplaceInstr. I thought that was an improvement, and is another
reason I don't think just a simple revert is the ideal fix.

[MatzeB]

In D22083#476412, @kbsmith1 wrote:

What have you done to prove to yourself that this code is no longer necessary?
If unnecessary, then both before and after the change, the code for 401.bzip2 from spec20006 ought to
be identical.

I can certainly explain to you what caused these ridiculous live-in lists. Basically looking at a set of register units and then adding all registers with that unit leads to al, ax, eax, rax getting added even if just al is live (additonally the code would unnecessarily add all the pristine registers). So I am pretty sure these wrong live-in lists causes the way too conversative lifeness when walking the block from the end.

One way of showing that this code is no longer necessary would be to use the new code and simply
add an assertion after line 389 that NewMI was always nullptr. Once that code had been in for a while,
you could make the extra forward pass be a debug-only code in an attempt to catch other regressions
that might occur in live-reg tracking.

Also, I kind of liked the better abstraction of tryReplaceInstr. I thought that was an improvement, and is another
reason I don't think just a simple revert is the ideal fix.

Fair enough do a round of testing with the full llvm test-suite including externals (spec95,spec2k,spec2k6) to see that there is really no change. Keeping the tryReplaceInstr() function around is fine, this review is mainly here to get the discussion started :)

[MatzeB]

In D22083#477465, @MatzeB wrote:

In D22083#476412, @kbsmith1 wrote:

What have you done to prove to yourself that this code is no longer necessary?
If unnecessary, then both before and after the change, the code for 401.bzip2 from spec20006 ought to
be identical.

I can certainly explain to you what caused these ridiculous live-in lists. Basically looking at a set of register units and then adding all registers with that unit leads to al, ax, eax, rax getting added even if just al is live (additonally the code would unnecessarily add all the pristine registers). So I am pretty sure these wrong live-in lists causes the way too conversative lifeness when walking the block from the end.

One way of showing that this code is no longer necessary would be to use the new code and simply
add an assertion after line 389 that NewMI was always nullptr. Once that code had been in for a while,
you could make the extra forward pass be a debug-only code in an attempt to catch other regressions
that might occur in live-reg tracking.

Also, I kind of liked the better abstraction of tryReplaceInstr. I thought that was an improvement, and is another
reason I don't think just a simple revert is the ideal fix.

Fair enough do a round of testing with the full llvm test-suite including externals (spec95,spec2k,spec2k6) to see that there is really no change. Keeping the tryReplaceInstr() function around is fine, this review is mainly here to get the discussion started :)

Adding the missing words: "Fair enough, I will do a round of testing..."

[kbsmith1]

OK, sounds reasonable.

[MatzeB]

I added an assert that the forward liveness analysis would not find additional transformation opportunities. As expected most of the problems were fixed with http://reviews.llvm.org/D22027 in place. However it turned out that there existed another subtle case where forward and backward analysis could disagree, I fixed that one in r274952.

[MatzeB]

Reworked the patch, title and description.

[kbsmith1]

LGTM

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

void FixupBWInstPass::processBasicBlock(MachineFunction &MF,
   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);
 
-  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.
-    // FIXME - Register liveness should be investigated further. This really
-    // shouldn't be necessary.  See PR28142.
-    LiveRegs.clear();
-    LiveRegs.addLiveIns(MBB);
-
-    auto NextCandidateIter = MIReplacements.begin();
-    auto EndCandidateIter = MIReplacements.end();
-
-    for (auto I = MBB.begin(); I != MBB.end(); ++I) {
-      MachineInstr *MI = &*I;
-      SmallVector<std::pair<unsigned, const MachineOperand*>, 4> Clobbers;
-      LiveRegs.stepForward(*MI, Clobbers);
-
-      if (NextCandidateIter == EndCandidateIter)
-        break;
-
-      // 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);
     }
   }
 }

llvm/trunk/test/CodeGen/X86/fixup-bw-inst-fwlive.mir

-# RUN: llc -run-pass x86-fixup-bw-insts -mtriple=x86_64-- -o /dev/null %s 2>&1 | FileCheck %s
-
-# Verify that the forwards live-ness checking code in fixup-bw-inst works.
-
---- |
-  target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
-
-  define i8 @foo(i8 %p1) {
-  entry:
-    %t1 = or i8 %p1, 0
-    br label %false
-  false:
-    ret i8 %t1
-  }
-
-...
-
----
-name:            foo
-allVRegsAllocated: true
-isSSA:           false
-tracksRegLiveness: true
-liveins:
-  - { reg: '%edi' }
-body:             |
-  bb.0.entry:
-    liveins: %edi
-    successors: %bb.1.false
-    
-    %al = MOV8rr %dil, implicit %edi
-    ; CHECK: %eax = MOV32rr undef %edi, implicit %dil
-
-  bb.1.false:
-    liveins: %al, %ax, %eax, %rax
-    RETQ %al
-
-...