Page MenuHomePhabricator

Create a PHI value when merging with a known undef live-in
ClosedPublic

Authored by kparzysz on Jun 26 2017, 12:47 PM.

Details

Summary

The following snippet illustrates the problem.

During register allocation, the value defined at 868 for vreg154:isub_hi (lane mask 0x0001) is extended to the use at 1564 via a single segment. That segment spans over the entry to BB#6, which is reachable from two places: the end of BB#5 (dominated by 868), and the end of BB#6. The value of vreg154:isub_hi is undefined when coming from the end of BB#6, which causes the verifier to complain.

To fix this, create a PHI when a defined value is merged with an undef value at the entry to a block. Currently, undef values are simply ignored when determining the need for PHIs, which leads to a problem when there is a unique defined value.

704B    BB#5: derived from LLVM BB %b17
            Predecessors according to CFG: BB#2 BB#4
868B            %vreg154<def> = COPY %vreg148; DoubleRegs:%vreg154,%vreg148
            Successors according to CFG: BB#6(?%)

1172B   BB#6: derived from LLVM BB %b30
            Predecessors according to CFG: BB#5 BB#6
1212B           %vreg66<def> = C2_cmpgt %vreg152, %vreg154:isub_lo; PredRegs:%vreg66 IntRegs:%vreg152 DoubleRegs:%vreg154
1564B           %vreg153<def> = COPY %vreg154; DoubleRegs:%vreg153,%vreg154
1572B           %vreg154<def> = COPY %vreg153; DoubleRegs:%vreg154,%vreg153
1856B           %vreg154:isub_lo<def,read-undef> = A2_addi %vreg154:isub_lo, 1; DoubleRegs:%vreg154
1984B           J2_jump <BB#6>, %PC<imp-def,dead>
            Successors according to CFG: BB#6(?%)

# End machine code for function fred.

*** Bad machine code: Register not marked live out of predecessor ***
- function:    fred
- basic block: BB#6 b30 (0x50bb8b8) [1172B;1992B)
- liverange:   [868r,1564r:1)[1572r,1572d:0)  0@1572r 1@868r
- v. register: %vreg154
- lanemask:    00000001
- ValNo:       1 (def 868r)
 live into BB#6@1172B, not live before 1992B
LLVM ERROR: Found 1 machine code errors.

Diff Detail

Repository
rL LLVM

Event Timeline

kparzysz created this revision.Jun 26 2017, 12:47 PM
MatzeB edited edge metadata.Jun 26 2017, 4:33 PM

From what I remember the notion of a nullptr in Map for a block we had already Seen was introduced with the changes supporting undefs when recalculating liveness. I assumed that had the same role as the special VNI you introduce here. Can you elaborate the difference (and/or eliminate the cases looking for nullptr)?

Could you create a .mir test that just does llc -run-pass=liveintervals?

lib/CodeGen/LiveRangeCalc.cpp
289 ↗(On Diff #104009)

Doesn't the Map[&B].first == nullptr case only exist to deal with undefs? Does it still happen with your changes?

(If you still need it, at least refactor it so we only do 1 lookup in Map).

kparzysz marked an inline comment as done.Jun 27 2017, 6:14 AM

The case where a block is in Seen, but the value is null refers to the situation where the register is live-through this block, but at the moment we don't know what value it has. The "UndefVNI" case denotes a situation where we know that this block undefines the register.

lib/CodeGen/LiveRangeCalc.cpp
289 ↗(On Diff #104009)

Yes, it still happens. Actually there are 3 testcases in test/CodeGen/Hexagon where this occurs with these changes.

kparzysz updated this revision to Diff 104149.Jun 27 2017, 6:20 AM
kparzysz marked an inline comment as done.

Replaced the .ll testcase with a shorter .mir. Avoided two Map lookups when checking block live-out value.

MatzeB accepted this revision.Jun 27 2017, 1:50 PM

Thanks, LGTM.

lib/CodeGen/LiveRangeCalc.cpp
500–501 ↗(On Diff #104149)

This can be && instead of a nested if.

test/CodeGen/Hexagon/regalloc-liveout-undef.mir
3–6 ↗(On Diff #104149)

Sounds like we need some AU.addUsedIfAvailable<>() calls in the getUsageInfo of the MachineVerifier. Doesn't need to be in this patch though.

This revision is now accepted and ready to land.Jun 27 2017, 1:50 PM
This revision was automatically updated to reflect the committed changes.
kparzysz added inline comments.Jun 27 2017, 2:31 PM
lib/CodeGen/LiveRangeCalc.cpp
500–501 ↗(On Diff #104149)

But then the condition wouldn't fit in a single line.

MatzeB added inline comments.Jun 27 2017, 2:42 PM
lib/CodeGen/LiveRangeCalc.cpp
500–501 ↗(On Diff #104149)

But it's two lines either way, isn't it? Not that I care too deeply about it, but my motivation for a single if, is that when I see two ifs, I usually start looking for "else code" or "common code after the inner if" that aren't present here.