Restrict tail duplication in the presence of subregisters

[kparzysz]

Summary

Tail duplication can be confused by subregisters in phi nodes. The Hexagon testcase leads to an abort without this fix.

[echristo]

Matthias is probably better than I am to review at the moment.

[MatzeB]

Hi Krzysztof,

I tried to reproduce the problem with your testcase but it works without a problem in a debug build on llvm r250716 for me. So I am just guessing what the exact problem is that you are fixing: Is tail duplication incorrectly ignoring the subregisters when changing the code? Or is it producing copies that the hexagon target cannot handle? For the former I wonder if it wouldn't be easier to fix TailDuplication if it is the latter can't you run into the same problem of after PHI Elimination inserts copies?

[kparzysz]

Hi Matthias. You need at least r250868.

[kparzysz]

IR Dump After Expand ISel Pseudo-instructions

# Machine code for function foo: SSA
Function Live Ins: %R0 in %vreg3, %D1 in %vreg4

BB#0: derived from LLVM BB %entry
    Live Ins: %R0 %D1
        %vreg4<def> = COPY %D1; DoubleRegs:%vreg4
        %vreg3<def> = COPY %R0; IntRegs:%vreg3
        %vreg5<def> = C2_cmpgti %vreg3, -1; PredRegs:%vreg5 IntRegs:%vreg3
        J2_jumpf %vreg5, <BB#2>, %PC<imp-def,dead>; PredRegs:%vreg5
        J2_jump <BB#1>, %PC<imp-def,dead>
    Successors according to CFG: BB#2(12) BB#1(20)

BB#1: derived from LLVM BB %tail
    Predecessors according to CFG: BB#0 BB#2
        J2_jump <BB#4>, %PC<imp-def,dead>
    Successors according to CFG: BB#4

BB#2: derived from LLVM BB %next
    Predecessors according to CFG: BB#0
        %vreg6<def> = C2_cmpeqi %vreg3, 0; PredRegs:%vreg6 IntRegs:%vreg3
        J2_jumpf %vreg6, <BB#1>, %PC<imp-def,dead>; PredRegs:%vreg6
        J2_jump <BB#3>, %PC<imp-def,dead>
    Successors according to CFG: BB#3(12) BB#1(20)

BB#3: derived from LLVM BB %b1
    Predecessors according to CFG: BB#2
    Successors according to CFG: BB#4

BB#4: derived from LLVM BB %join
    Predecessors according to CFG: BB#1 BB#3
        %vreg2<def> = PHI %vreg4:subreg_loreg, <BB#1>, %vreg4:subreg_hireg, <BB#3>; IntRegs:%vreg2 DoubleRegs:%vreg4
        %R0<def> = COPY %vreg2; IntRegs:%vreg2
        JMPret %R31, %PC<imp-def,dead>, %R0<imp-use>

# End machine code for function foo.
`

The problem will appear in BB#4: the phi node mixed registers from IntRegs and DoubleRegs. On Hexagon, a register from DoubleRegs is a pair of IntRegs, and subreg_loreg/subreg_hireg are the low/high register from that pair. In that sense, DoubleReg with a subregister is "equivalent" to IntReg, but without any subregisters, it is not copyable into an IntReg.

# *** IR Dump After Tail Duplication ***:
# Machine code for function foo: SSA
Function Live Ins: %R0 in %vreg3, %D1 in %vreg4

BB#0: derived from LLVM BB %entry
    Live Ins: %R0 %D1
        %vreg4<def> = COPY %D1; DoubleRegs:%vreg4
        %vreg3<def> = COPY %R0; IntRegs:%vreg3
        %vreg5<def> = C2_cmpgti %vreg3, -1; PredRegs:%vreg5 IntRegs:%vreg3
        J2_jumpf %vreg5, <BB#2>, %PC<imp-def>; PredRegs:%vreg5
        J2_jump <BB#4>, %PC<imp-def>
    Successors according to CFG: BB#2(12) BB#4(20)

BB#2: derived from LLVM BB %next
    Predecessors according to CFG: BB#0
        %vreg6<def> = C2_cmpeqi %vreg3, 0; PredRegs:%vreg6 IntRegs:%vreg3
        J2_jumpf %vreg6, <BB#4>, %PC<imp-def>; PredRegs:%vreg6
    Successors according to CFG: BB#3(12) BB#4(20)

BB#3: derived from LLVM BB %b1
    Predecessors according to CFG: BB#2
    Successors according to CFG: BB#4

BB#4: derived from LLVM BB %join
    Predecessors according to CFG: BB#3 BB#0 BB#2
        %vreg2<def> = PHI %vreg4:subreg_loreg, <BB#0>, %vreg4:subreg_hireg, <BB#3>, %vreg4, <BB#2>; IntRegs:%vreg2 DoubleRegs:%vreg4
        %R0<def> = COPY %vreg2; IntRegs:%vreg2
        JMPret %R31, %PC<imp-def,dead>, %R0<imp-use>

# End machine code for function foo.

[MatzeB]

ok, so this looks like a bug in the TailDuplication code, I wonder what it would take to actually fix TailDuplication rather than just disabling it. I guess disabling TailDuplication is still better than producing wrong code, so you can apply the patch if you must. But please state in the comment or somewhere that this aspect of the TailDuplication code is broken and should be fixed (or if possible try to fix it yourself so it produces the uses the correct subregister for the newly added phi operands).

[kparzysz]

Thanks, I will look into fixing this the proper way.

Meanwhile, I committed this patch under r250877.

[kparzysz]

The phi operands are added by the SSA updater. I don't think it's prepared to handle subregisters. I remember that I had tried to fix it, but I gave up---it seemed like too much work at the time.

[MatzeB]

Closing review that is already committed.

lib/CodeGen/TailDuplication.cpp

       return false;
   }
 
+  // Check if any of the successors of TailBB has a PHI node in which the
+  // value corresponding to TailBB uses a subregister.
+  for (auto SB : TailBB.successors()) {
+    for (auto &I : *SB) {
+      if (!I.isPHI())
+        break;
+      unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);
+      assert(Idx != 0);
+      MachineOperand &PU = I.getOperand(Idx);
+      if (PU.getSubReg() != 0)
+        return false;
+    }
+  }
+
   if (HasIndirectbr && PreRegAlloc)
     return true;
 

test/CodeGen/Hexagon/tail-dup-subreg-abort.ll

+; RUN: llc -march=hexagon -O2 -disable-cgp < %s
+; REQUIRES: asserts
+;
+; Tail duplication can ignore subregister information on PHI nodes, and as
+; a result, generate COPY instructions between registers of different classes.
+; This could lead to HexagonInstrInfo::copyPhysReg aborting on an unhandled
+; src/dst combination.
+;
+define i32 @foo(i32 %x, i64 %y) nounwind {
+entry:
+  %a = icmp slt i32 %x, 0
+  %lo = trunc i64 %y to i32
+  br i1 %a, label %next, label %tail
+tail:
+  br label %join
+next:
+  %c = icmp eq i32 %x, 0
+  br i1 %c, label %b1, label %tail
+b1:
+  %t1 = lshr i64 %y, 32
+  %hi = trunc i64 %t1 to i32
+  br label %join
+join:
+  %val = phi i32 [ %hi, %b1 ], [ %lo, %tail ]
+  ret i32 %val
+}
+
+