[ScheduleDAG] Make sure to process all def operands before any use operands

[kparzysz]

Summary

An example from Hexagon where things went wrong:

%R0<def> = L2_loadrigp <ga:@fp04>      ; load function address
J2_callr %R0<kill>, ..., %R0<imp-def>  ; call *R0, return value in R0

ScheduleDAGInstrs::buildSchedGraph would visit all instructions going backwards, and in each instruction it would visit all operands in their order on the operand list. In the case of this call, it visited the use of R0 first, then removed it from the set Uses after it visited the def. This caused the DAG to be missing the data dependence edge on R0 between the load and the call.

The final result was that the load and the call were packetized together, which meant that the call used the prior value of R0 instead of the loaded one.

[atrick]

LGTM

[MatzeB]

llvm/trunk/lib/CodeGen/ScheduleDAGInstrs.cpp

974–975

This will subregister defs which are uses as well, should be `!MO.readsReg())!

[atrick]

llvm/trunk/lib/CodeGen/ScheduleDAGInstrs.cpp

974–975

Matthias, can you clarify? We don't want addPhysRefDefs to be called twice for the same subreg!

[MatzeB]

llvm/trunk/lib/CodeGen/ScheduleDAGInstrs.cpp

974–975

Something like this:
%vreg0:sub0 = ... is both a definition and a use! (at least if lanemask tracking is not enabled), we still need to record it as a use. physregs never have subregister indexes so MO.readsReg() will never return true for physreg definitions.

[MatzeB]

llvm/trunk/lib/CodeGen/ScheduleDAGInstrs.cpp

974–975

It would also be nice to split addPhysRegDeps() into addPhysRegUseDeps() and addPhysRegDefDeps().

[MatzeB]

llvm/trunk/lib/CodeGen/ScheduleDAGInstrs.cpp

974–975

Hmm it looks like the code before this patch only used output dependencies for this case. So this change is fine in preserving that behavior.

[atrick]

llvm/trunk/lib/CodeGen/ScheduleDAGInstrs.cpp

974–975

I *think* Matthias is saying that this patch will fail to call addVRegUseDeps for subregs. So, that needs to be fixed but in a way that doesn't call addPhysRegDeps twice on the same operand.

Maybe Matthias can suggest a fix!

[llvm-commits]

I am fine with the change as is now after realizing that it does not change the behaviour of the subregister def case. So this change is fine!

I am still confused as to why we could get away with ignoring those uses before. I guess output dependencies are enough to get the instruction order right, but this should be commented on and I'd like to check that it doesn't influence register pressure computation.

• Matthias

[kparzysz]

I think this is a fairly rare case. There has to be an explicit use and then an implicit def of the same register. This came up for us in the Perennial C++ test suite.

[atrick]

Just chatted with Matthias. This patch as fine as-is--it preserves behavior. Matthias will add a comment explaining the pre-existing behavior.

llvm/trunk/lib/CodeGen/ScheduleDAGInstrs.cpp

if (RPTracker) {
       RPTracker->recede(RegOpers);
     }
 
     assert(
         (CanHandleTerminators || (!MI->isTerminator() && !MI->isPosition())) &&
         "Cannot schedule terminators or labels!");
 
     // Add register-based dependencies (data, anti, and output).
+    // For some instructions (calls, returns, inline-asm, etc.) there can
+    // be explicit uses and implicit defs, in which case the use will appear
+    // on the operand list before the def. Do two passes over the operand
+    // list to make sure that defs are processed before any uses.
     bool HasVRegDef = false;
     for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
       const MachineOperand &MO = MI->getOperand(j);
-      if (!MO.isReg()) continue;
+      if (!MO.isReg() || !MO.isDef())
+        continue;
       unsigned Reg = MO.getReg();
-      if (Reg == 0) continue;
+      if (Reg == 0)
+        continue;
 
       if (TRI->isPhysicalRegister(Reg))
         addPhysRegDeps(SU, j);
       else {
-        if (MO.isDef()) {
-          HasVRegDef = true;
-          addVRegDefDeps(SU, j);
-        }
-        else if (MO.readsReg()) // ignore undef operands
-          addVRegUseDeps(SU, j);
-      }
-    }
+    }
+    // Now process all uses.
+    for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
+      const MachineOperand &MO = MI->getOperand(j);
+      if (!MO.isReg() || !MO.isUse())
+        continue;
+      unsigned Reg = MO.getReg();
+      if (Reg == 0)
+        continue;
+
+      if (TRI->isPhysicalRegister(Reg))
+        addPhysRegDeps(SU, j);
+
     // If we haven't seen any uses in this scheduling region, create a
     // dependence edge to ExitSU to model the live-out latency. This is required
     // for vreg defs with no in-region use, and prefetches with no vreg def.
     //
     // FIXME: NumDataSuccs would be more precise than NumSuccs here. This
     // check currently relies on being called before adding chain deps.
     if (SU->NumSuccs == 0 && SU->Latency > 1
         && (HasVRegDef || MI->mayLoad())) {

llvm/trunk/test/CodeGen/Hexagon/callr-dep-edge.ll

+; RUN: llc -march=hexagon < %s | FileCheck %s
+; Check that the callr and the load into r0 are not packetized together.
+
+target triple = "hexagon"
+
+@fp = common global i32 (...)* null, align 4
+
+; CHECK: r0 = memw
+; CHECK: {
+; CHECK: callr r0
+
+; Function Attrs: nounwind
+define i32 @foo() #0 {
+entry:
+  %0 = load i32 ()*, i32 ()** bitcast (i32 (...)** @fp to i32 ()**), align 4
+  %call = tail call i32 %0() #0
+  ret i32 %call
+}
+
+attributes #0 = { nounwind }