bug fix for PR20020: anti-dependency-breaker causes miscompilation

[spatel]

Summary

This patch sets the 'KeepReg' bit for any tied registers during the PrescanInstruction() phase of the dependency breaking algorithm. It then checks those 'KeepReg' bits during the ScanInstruction() phase to avoid changing any tied registers. For more details, please see comments in:
http://llvm.org/bugs/show_bug.cgi?id=20020

The existing code also uses the 'Classes' variable as a marker for registers that shouldn't be changed (by setting the value to -1). If someone can explain why we need two data structures to mark unusable regs, I'd love to understand that.

I added two FIXME comments for code that I think can be removed by using register iterators that include self. I don't want to include those code changes with this patch, however, to keep things as small as possible.

The test case is larger than I'd like, but I don't know how to reduce it further and still produce the failing asm.

[hfinkel]

Can you please upload the patch with more context lines (as explained here: http://llvm.org/docs/Phabricator.html)?

lib/CodeGen/CriticalAntiDepBreaker.cpp

260 ↗

(On Diff #10985)

Can you put an assert inside the existing check that the tied registers are in KeepRegs?

[spatel]

lib/CodeGen/CriticalAntiDepBreaker.cpp

260 ↗

(On Diff #10985)

Do you mean:
if (MI->isRegTiedToUseOperand(i)) {
assert(KeepRegs.test(Reg) && "Register is tied but was not added to KeepRegs"));
continue;
}

But we're checking the KeepRegs value just above this and continuing at that point in the code, so this would only fire if someone inadvertently put code between these two 'if' checks?

[hfinkel]

lib/CodeGen/CriticalAntiDepBreaker.cpp

260 ↗

(On Diff #10985)

No, I mean replacing that with the assert (since PreScan should have caught them all). So instead of:

if (MI->isRegTiedToUseOperand(i)) continue;

We'd have:

assert(!MI->isRegTiedToUseOperand(i) && "Tied operand not in KeepRegs?");

[spatel]

Thanks, Hal! Updated with assert() and full diff.

But I now see that this change breaks test/Codegen/X86/atom-sched.ll because that test implicitly enabled -break-anti-dependencies. I'll have to investigate.

[spatel]

Updated patch to only set KeepRegs[reg] when a reg is tied AND live. This allows the existing Atom test case to work as expected.
This patch should make the code strictly safer (do less work) and avoid PR20020 while preserving all existing regression test behavior.

I removed the assert() that was in the previous draft because there is one existing test (test/Codegen/X86/select.ll - test17) where it would still fire. This is because that test has an instruction with a tied op, but we don't set KeepRegs for it because we only change the Classes[] value for the reg after-the-fact based on a register that aliases it around this code:

// If an alias of the reg is used during the live range, give up.

[hfinkel]

LGTM; thanks!

test/CodeGen/X86/pr20020.ll

73 ↗

(On Diff #11034)

Please remove any unneeded attributes.

[spatel]

Closed by commit rL212275 (authored by @spatel).

[danilaml]

llvm/trunk/lib/CodeGen/CriticalAntiDepBreaker.cpp

203

@spatel Hi, I was debugging some miscompile issue and came across what I think is very similar bug.
Do you remember why you check against -1 here? In my test-case (which I'm trying to reduce), the Classes[Reg] is some regclass non -1 value. According to the comments for Classes:

/// For live regs that are only used in one register class in a
    /// live range, the register class. If the register is not live, the
    /// corresponding value is null. If the register is live but used in
    /// multiple register classes, the corresponding value is -1 casted to a
    /// pointer.

My question is: why is this code is checking for -1 specifically, instead of != nullptr? If it's not live, would it still be OK? I have trouble following the logic in this pass.
The comments for scan indicate that

// Note: AntiDepReg may be referenced by a two-address instruction such that
// it's use operand is tied to a def operand ...
// In this case, both the use and def operands are in
// RegRefs because the def is inserted by PrescanInstruction and not erased
// during ScanInstruction.

which is evidently not true in my test case (e.g. XOR has 3 same-reg operands, one pair tied, so the ScanInstruction would remove all RegRefs added by Prescan due to the 3rd non-tied reg, and skip the first tied def when adding refs back).

[spatel]

llvm/trunk/lib/CodeGen/CriticalAntiDepBreaker.cpp

203

Wow - I barely remember creating this patch. I haven't looked at anything near here in so long, that I can't offer much help. I see that you posted D107582 - let's see if we can find someone more knowledgeable to review.

llvm/trunk/lib/CodeGen/CriticalAntiDepBreaker.cpp

for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) {
         Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
       }
     }
 
     // If we're still willing to consider this register, note the reference.
     if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1))
       RegRefs.insert(std::make_pair(Reg, &MO));
 
+    // If this reg is tied and live (Classes[Reg] is set to -1), we can't change
+    // it or any of its sub or super regs. We need to use KeepRegs to mark the
+    // reg because not all uses of the same reg within an instruction are
+    // necessarily tagged as tied.
+    // Example: an x86 "xor %eax, %eax" will have one source operand tied to the
+    // def register but not the second (see PR20020 for details).
+    // FIXME: can this check be relaxed to account for undef uses
+    // of a register? In the above 'xor' example, the uses of %eax are undef, so
+    // earlier instructions could still replace %eax even though the 'xor'
+    // itself can't be changed.
+    if (MI->isRegTiedToUseOperand(i) &&
+        Classes[Reg] == reinterpret_cast<TargetRegisterClass *>(-1)) {
+      for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
+           SubRegs.isValid(); ++SubRegs) {
+        KeepRegs.set(*SubRegs);
+      }
+      for (MCSuperRegIterator SuperRegs(Reg, TRI);
+           SuperRegs.isValid(); ++SuperRegs) {
+        KeepRegs.set(*SuperRegs);
+      }
+    }
+
     if (MO.isUse() && Special) {
       if (!KeepRegs.test(Reg)) {
         for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
              SubRegs.isValid(); ++SubRegs)
           KeepRegs.set(*SubRegs);
       }
     }
   }
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
             Classes[i] = nullptr;
             RegRefs.erase(i);
           }
 
       if (!MO.isReg()) continue;
       unsigned Reg = MO.getReg();
       if (Reg == 0) continue;
       if (!MO.isDef()) continue;
+
+      // If we've already marked this reg as unchangeable, carry on.
+      if (KeepRegs.test(Reg)) continue;
+      
       // Ignore two-addr defs.
       if (MI->isRegTiedToUseOperand(i)) continue;
 
+      // FIXME: we should use a SubRegIterator that includes self (as above), so
+      // we don't have to repeat all this code for the reg itself.
       DefIndices[Reg] = Count;
       KillIndices[Reg] = ~0u;
       assert(((KillIndices[Reg] == ~0u) !=
               (DefIndices[Reg] == ~0u)) &&
              "Kill and Def maps aren't consistent for Reg!");
       KeepRegs.reset(Reg);
       Classes[Reg] = nullptr;
       RegRefs.erase(Reg);
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     // class is consistent across all uses.
     if (!Classes[Reg] && NewRC)
       Classes[Reg] = NewRC;
     else if (!NewRC || Classes[Reg] != NewRC)
       Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
 
     RegRefs.insert(std::make_pair(Reg, &MO));
 
+    // FIXME: we should use an MCRegAliasIterator that includes self so we don't
+    // have to repeat all this code for the reg itself.
+    
     // It wasn't previously live but now it is, this is a kill.
     if (KillIndices[Reg] == ~0u) {
       KillIndices[Reg] = Count;
       DefIndices[Reg] = ~0u;
           assert(((KillIndices[Reg] == ~0u) !=
                   (DefIndices[Reg] == ~0u)) &&
                "Kill and Def maps aren't consistent for Reg!");
     }

llvm/trunk/test/CodeGen/X86/pr20020.ll

+; RUN: llc < %s -mtriple=x86_64-apple-macosx -disable-lsr -post-RA-scheduler=1 -break-anti-dependencies=critical  | FileCheck %s
+
+; In PR20020, the critical anti-dependency breaker algorithm mistakenly
+; changes the register operands of an 'xorl %eax, %eax' to 'xorl %ecx, %ecx'
+; and then immediately reloads %rcx with a value based on the wrong %rax
+
+; CHECK-NOT: xorl %ecx, %ecx
+; CHECK: leaq 1(%rax), %rcx
+
+
+%struct.planet = type { double, double, double }
+
+; Function Attrs: nounwind ssp uwtable
+define void @advance(i32 %nbodies, %struct.planet* nocapture %bodies) #0 {
+entry:
+  %cmp4 = icmp sgt i32 %nbodies, 0
+  br i1 %cmp4, label %for.body.preheader, label %for.end38
+
+for.body.preheader:                               ; preds = %entry
+  %gep = getelementptr %struct.planet* %bodies, i64 1, i32 1
+  %gep13 = bitcast double* %gep to %struct.planet*
+  %0 = add i32 %nbodies, -1
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.inc20
+  %iv19 = phi i32 [ %0, %for.body.preheader ], [ %iv.next, %for.inc20 ]
+  %iv = phi %struct.planet* [ %gep13, %for.body.preheader ], [ %gep14, %for.inc20 ]
+  %iv9 = phi i64 [ %iv.next10, %for.inc20 ], [ 0, %for.body.preheader ]
+  %iv.next10 = add nuw nsw i64 %iv9, 1
+  %1 = trunc i64 %iv.next10 to i32
+  %cmp22 = icmp slt i32 %1, %nbodies
+  br i1 %cmp22, label %for.body3.lr.ph, label %for.inc20
+
+for.body3.lr.ph:                                  ; preds = %for.body
+  %x = getelementptr inbounds %struct.planet* %bodies, i64 %iv9, i32 0
+  %y = getelementptr inbounds %struct.planet* %bodies, i64 %iv9, i32 1
+  %vx = getelementptr inbounds %struct.planet* %bodies, i64 %iv9, i32 2
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
+  %iv20 = phi i32 [ %iv.next21, %for.body3 ], [ %iv19, %for.body3.lr.ph ]
+  %iv15 = phi %struct.planet* [ %gep16, %for.body3 ], [ %iv, %for.body3.lr.ph ]
+  %iv1517 = bitcast %struct.planet* %iv15 to double*
+  %2 = load double* %x, align 8
+  %gep18 = getelementptr double* %iv1517, i64 -1
+  %3 = load double* %gep18, align 8
+  %sub = fsub double %2, %3
+  %4 = load double* %y, align 8
+  %5 = load double* %iv1517, align 8
+  %sub8 = fsub double %4, %5
+  %add10 = fadd double %sub, %sub8
+  %call = tail call double @sqrt(double %sub8) #2
+  store double %add10, double* %vx, align 8
+  %gep16 = getelementptr %struct.planet* %iv15, i64 1
+  %iv.next21 = add i32 %iv20, -1
+  %exitcond = icmp eq i32 %iv.next21, 0
+  br i1 %exitcond, label %for.inc20, label %for.body3
+
+for.inc20:                                        ; preds = %for.body3, %for.body
+  %lftr.wideiv11 = trunc i64 %iv.next10 to i32
+  %gep14 = getelementptr %struct.planet* %iv, i64 1
+  %iv.next = add i32 %iv19, -1
+  %exitcond12 = icmp eq i32 %lftr.wideiv11, %nbodies
+  br i1 %exitcond12, label %for.end38, label %for.body
+
+for.end38:                                        ; preds = %for.inc20, %entry
+  ret void
+}
+
+; Function Attrs: nounwind
+declare double @sqrt(double) #1
+
+attributes #0 = { "no-frame-pointer-elim-non-leaf" }