critical-anti-dependency breaker: don't use reg def info from kill insts (PR20308)

[spatel]

Summary

In PR20308 ( http://llvm.org/bugs/show_bug.cgi?id=20308 ), the critical-anti-dependency breaker caused a miscompile because it broke a WAR hazard using a register that it thinks is available based on info from a kill inst. We should never use any def/use info from a kill because they are really just nops.

This patch adds guard checks for kills around calls to ScanInstruction() where the DefIndices array is set. For good measure, add an assert in ScanInstruction() so we don't hit this bug again.

The test case is a reduced version of the code from the bug report.

[atrick]

I'm signing off on this because it seems reasonably safe, though might not be solving the underlying problem. It does need to be reviewed by someone else. Both Hal and Will Schmidt have worked on similar issues very recently so they will be more informed.

I have to say, the presence of the KILL instruction in your Pre-sched code looks fairly misleading if not wrong. It is certainly incorrect in terms of liveness. If the call's %RDI argument is not "undef" then who defines it? If it is live into the call, the KILL should not define it. I would take a closer look at MachineCopyPropagation and other CodeGen passes to determine where things went wrong.

%RAX<def> = MOV64rm %RIP, 1, %noreg, <ga:@Part_Class>[TF=5], %noreg; mem:LD8[GOT]
%RDI<def> = KILL %RBP
CALL64pcrel32 <ga:@Object_NewImage>[TF=6], <regmask>, %RSP<imp-use>, %RDI<imp-use>, %ESI<imp-use>, %EDX<imp-use>, %ECX<imp-use>, %R8<imp-use,kill>, %R9<imp-use,kill>, %RSP<imp-def>, %EAX<imp-def>

[spatel]

Thanks for the prompt review, Andy. I've added Will Schmidt as a reviewer.

I agree that the output of MachineCopyPropagation looks wrong; yesterday was my first look at that code, so I didn't want to hold up this patch while investigating that. At the least, this patch makes PostRA slightly more efficient by not spending time processing kills.

If it's ok with everyone, I'll add a fixme comment in MachineCopyPropagation, open a new bug, and take a look. If anyone more familiar with that code can help, I'd certainly appreciate it.

[wschmidt]

Well, I think this is probably ok since KILL doesn't translate into something real that actually clobbers all or part of a register. So long as true register kills (clobbers) are honored by the anti-dependence breaker, I don't see a problem. KILL seems a bit like a crutch that should be used very sparingly; actual dependencies should be represented on the machine instructions.

Just FYI, I'm Bill Schmidt, not Will Schmidt. (I am the one you were looking for, but there are two of us. Will is willschm, and I'm wschmidt. We have a lottery each week to see which of us is the evil twin so we know how to act.)

[spatel]

MachineCopyPropagation appears to also be the root cause for:
http://llvm.org/bugs/show_bug.cgi?id=18663

This was patched in the AggressiveAntiDepBreaker by Will with:
http://llvm.org/viewvc/llvm-project?view=revision&revision=214429

I don't see a PR for MachineCopyPropagation yet...

[wschmidt]

Actually, you do need to add willschm as a reviewer, as he is the person who committed the patch in the previous comment. I don't immediately see how to add one myself, so will let you handle it... sorry, Phabricator n00b here.

[spatel]

Added willschm as reviewer because Abbott & Costello aren't available.

On 2nd reading of bug 18863, I see that it was left open to track the issue in MachineCopyPropagation. I'll add what I'm seeing in my test case there.

[willschm]

Changes look OK to me. I would defer final say/ technical commentary to Hal, (versus myself). Hal should have a better understanding of all the parts here than I do.

[hfinkel]

I think that we might still want to process Kill instructions that have a subregister/subregister relationship. These are the kinds of kills that the code is expecting, and there is logic to group these and rename them together. We probably don't want to completely disable that functionality. Does that makes sense?

When we commit a fix to this, please also revert r214429 (which was my related temporary fix to a subset of this problem).

P.S. In the future, please make sure to upload full-context diffs (see the instructions here: http://llvm.org/docs/Phabricator.html).

lib/CodeGen/CriticalAntiDepBreaker.cpp

95 ↗

(On Diff #12686)

I think we could say this in a better way; how about something like this:

"Kill instructions can define registers, but are really nops, and there might be a real definition earlier that needs to be paired with uses dominated by this kill."

[spatel]

In D4977#16, @hfinkel wrote:

I think that we might still want to process Kill instructions that have a subregister/subregister relationship. These are the kinds of
kills that the code is expecting, and there is logic to group these and rename them together. We probably don't want to
completely disable that functionality. Does that makes sense?

Yes, that makes sense for the Aggressive antidep breaker. I hadn't looked at the Aggressive implementation until now.

I don't see any handling for kills in the Critical antidep breaker though. These 2 implementations seem quite different at first glance. I can add a note in the code comments for this patch to also consider the behavior in the Aggressive class.

When we commit a fix to this, please also revert r214429 (which was my related temporary fix to a subset of this problem).

Sure - I posted the testcase in this patch into bug 18663 with my basic analysis of what's happening in MCP.

Just to be clear, do you approve this patch (with some changes to the comments) as a temporary fix to avoid the miscompile?

P.S. In the future, please make sure to upload full-context diffs (see the instructions here: http://llvm.org/docs/Phabricator.html).

Sorry - will do.

[hfinkel]

Yes, this looks good to me.

(Sorry for confusing the issue w/ my comments on the aggressive anti-dep breaker -- thanks for checking on the overlap).

[spatel]

Closed by commit rL216114 (authored by @spatel).

llvm/trunk/lib/CodeGen/CriticalAntiDepBreaker.cpp

 
 void CriticalAntiDepBreaker::FinishBlock() {
   RegRefs.clear();
   KeepRegs.reset();
 }
 
 void CriticalAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count,
                                      unsigned InsertPosIndex) {
-  if (MI->isDebugValue())
+  // Kill instructions can define registers but are really nops, and there might
+  // be a real definition earlier that needs to be paired with uses dominated by
+  // this kill.
+
+  // FIXME: It may be possible to remove the isKill() restriction once PR18663
+  // has been properly fixed. There can be value in processing kills as seen in
+  // the AggressiveAntiDepBreaker class.
+  if (MI->isDebugValue() || MI->isKill())
     return;
   assert(Count < InsertPosIndex && "Instruction index out of expected range!");
 
   for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) {
     if (KillIndices[Reg] != ~0u) {
       // If Reg is currently live, then mark that it can't be renamed as
       // we don't know the extent of its live-range anymore (now that it
       // has been scheduled).
void CriticalAntiDepBreaker::PrescanInstruction(MachineInstr *MI) {
   }
 }
 
 void CriticalAntiDepBreaker::ScanInstruction(MachineInstr *MI,
                                              unsigned Count) {
   // Update liveness.
   // Proceeding upwards, registers that are defed but not used in this
   // instruction are now dead.
+  assert(!MI->isKill() && "Attempting to scan a kill instruction");
 
   if (!TII->isPredicated(MI)) {
     // Predicated defs are modeled as read + write, i.e. similar to two
     // address updates.
     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
       MachineOperand &MO = MI->getOperand(i);
 
       if (MO.isRegMask())
#endif
 
   // Attempt to break anti-dependence edges on the critical path. Walk the
   // instructions from the bottom up, tracking information about liveness
   // as we go to help determine which registers are available.
   unsigned Broken = 0;
   unsigned Count = InsertPosIndex - 1;
   for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) {
     MachineInstr *MI = --I;
-    if (MI->isDebugValue())
+    // Kill instructions can define registers but are really nops, and there
+    // might be a real definition earlier that needs to be paired with uses
+    // dominated by this kill.
+    
+    // FIXME: It may be possible to remove the isKill() restriction once PR18663
+    // has been properly fixed. There can be value in processing kills as seen
+    // in the AggressiveAntiDepBreaker class.
+    if (MI->isDebugValue() || MI->isKill())
       continue;
 
     // Check if this instruction has a dependence on the critical path that
     // is an anti-dependence that we may be able to break. If it is, set
     // AntiDepReg to the non-zero register associated with the anti-dependence.
     //
     // We limit our attention to the critical path as a heuristic to avoid
     // breaking anti-dependence edges that aren't going to significantly

llvm/trunk/test/CodeGen/X86/critical-anti-dep-breaker.ll

+; RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu -relocation-model=pic -post-RA-scheduler=1 -break-anti-dependencies=critical  | FileCheck %s
+
+; PR20308 ( http://llvm.org/bugs/show_bug.cgi?id=20308 )
+; The critical-anti-dependency-breaker must not use register def information from a kill inst.
+; This test case expects such an instruction to appear as a comment with def info for RDI.
+; There is an anti-dependency (WAR) hazard using RAX using default reg allocation and scheduling.
+; The post-RA-scheduler and critical-anti-dependency breaker can eliminate that hazard using R10.
+; That is the first free register that isn't used as a param in the call to "@Image".
+
+@PartClass = external global i32
+@NullToken = external global i64
+
+; CHECK-LABEL: Part_Create:
+; CHECK-DAG: # kill: RDI<def> 
+; CHECK-DAG: movq PartClass@GOTPCREL(%rip), %r10
+define i32 @Part_Create(i64* %Anchor, i32 %TypeNum, i32 %F, i32 %Z, i32* %Status, i64* %PartTkn) {
+  %PartObj = alloca i64*, align 8
+  %Vchunk = alloca i64, align 8
+  %1 = load i64* @NullToken, align 4
+  store i64 %1, i64* %Vchunk, align 8
+  %2 = load i32* @PartClass, align 4
+  call i32 @Image(i64* %Anchor, i32 %2, i32 0, i32 0, i32* %Status, i64* %PartTkn, i64** %PartObj)
+  call i32 @Create(i64* %Anchor)
+  ret i32 %2
+}
+
+declare i32 @Image(i64*, i32, i32, i32, i32*, i64*, i64**)
+declare i32 @Create(i64*)