This is an archive of the discontinued LLVM Phabricator instance.

Differential D34640

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

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

Details

Reviewers
MatzeB
Commits
rG0b7688e6c004: Create a PHI value when merging with a known undef live-in
rL306466: Create a PHI value when merging with a known undef live-in
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
Herald added a subscriber: qcolombet. · View Herald TranscriptJun 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

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

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
497–501

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
Closed by commit rL306466: Create a PHI value when merging with a known undef live-in (authored by kparzysz). · Explain WhyJun 27 2017, 2:30 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
497–501

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
497–501

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.

Revision Contents

PathSize
lib/
CodeGen/
22 lines
test/
CodeGen/
Hexagon/
145 lines

Diff 104009

lib/CodeGen/LiveRangeCalc.cpp

Show All 14 Lines
#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SetVector.h"
#include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h"
using namespace llvm; using namespace llvm;
#define DEBUG_TYPE "regalloc" #define DEBUG_TYPE "regalloc"
// Reserve an address that indicates a value that is known to be "undef".
static VNInfo UndefVNI(0xbad, SlotIndex());
void LiveRangeCalc::resetLiveOutMap() { void LiveRangeCalc::resetLiveOutMap() {
unsigned NumBlocks = MF->getNumBlockIDs(); unsigned NumBlocks = MF->getNumBlockIDs();
Seen.clear(); Seen.clear();
Seen.resize(NumBlocks); Seen.resize(NumBlocks);
EntryInfoMap.clear(); EntryInfoMap.clear();
Map.resize(NumBlocks); Map.resize(NumBlocks);
} }
▲ Show 20 Lines • Show All 247 Lines • ▼ Show 20 Linesbool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
// that are potentially defined-on-exit to the work list. // that are potentially defined-on-exit to the work list.
for (MachineBasicBlock *P : MBB.predecessors()) for (MachineBasicBlock *P : MBB.predecessors())
WorkList.insert(P->getNumber()); WorkList.insert(P->getNumber());
for (unsigned i = 0; i != WorkList.size(); ++i) { for (unsigned i = 0; i != WorkList.size(); ++i) {
// Determine if the exit from the block is reached by some def. // Determine if the exit from the block is reached by some def.
unsigned N = WorkList[i]; unsigned N = WorkList[i];
MachineBasicBlock &B = *MF->getBlockNumbered(N); MachineBasicBlock &B = *MF->getBlockNumbered(N);
if (Seen[N] && Map[&B].first != nullptr) if (Seen[N] && Map[&B].first != nullptr && Map[&B].first != &UndefVNI)
MatzeBUnsubmitted
Done
ReplyInline Actions

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).

MatzeB: Doesn't the `Map[&B].first == nullptr` case only exist to deal with undefs? Does it still…
kparzyszAuthorUnsubmitted
Not Done
ReplyInline Actions

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

kparzysz: Yes, it still happens. Actually there are 3 testcases in test/CodeGen/Hexagon where this…
return MarkDefined(B); return MarkDefined(B);
SlotIndex Begin, End; SlotIndex Begin, End;
std::tie(Begin, End) = Indexes->getMBBRange(&B); std::tie(Begin, End) = Indexes->getMBBRange(&B);
// Treat End as not belonging to B. // Treat End as not belonging to B.
// If LR has a segment S that starts at the next block, i.e. [End, ...), // If LR has a segment S that starts at the next block, i.e. [End, ...),
// std::upper_bound will return the segment following S. Instead, // std::upper_bound will return the segment following S. Instead,
// S should be treated as the first segment that does not overlap B. // S should be treated as the first segment that does not overlap B.
LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(), LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(),
▲ Show 20 Lines • Show All 87 Lines • ▼ Show 20 Lines for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
SlotIndex Start, End; SlotIndex Start, End;
std::tie(Start, End) = Indexes->getMBBRange(Pred); std::tie(Start, End) = Indexes->getMBBRange(Pred);
// First time we see Pred. Try to determine the live-out value, but set // First time we see Pred. Try to determine the live-out value, but set
// it as null if Pred is live-through with an unknown value. // it as null if Pred is live-through with an unknown value.
auto EP = LR.extendInBlock(Undefs, Start, End); auto EP = LR.extendInBlock(Undefs, Start, End);
VNInfo *VNI = EP.first; VNInfo *VNI = EP.first;
FoundUndef |= EP.second; FoundUndef |= EP.second;
setLiveOutValue(Pred, VNI); setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
if (VNI) { if (VNI) {
if (TheVNI && TheVNI != VNI) if (TheVNI && TheVNI != VNI)
UniqueVNI = false; UniqueVNI = false;
TheVNI = VNI; TheVNI = VNI;
} }
if (VNI || EP.second) if (VNI || EP.second)
continue; continue;
Show All 13 Lines#endif
// Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
// neither require it. Skip the sorting overhead for small updates. // neither require it. Skip the sorting overhead for small updates.
if (WorkList.size() > 4) if (WorkList.size() > 4)
array_pod_sort(WorkList.begin(), WorkList.end()); array_pod_sort(WorkList.begin(), WorkList.end());
// If a unique reaching def was found, blit in the live ranges immediately. // If a unique reaching def was found, blit in the live ranges immediately.
if (UniqueVNI) { if (UniqueVNI) {
assert(TheVNI != nullptr); assert(TheVNI != nullptr && TheVNI != &UndefVNI);
LiveRangeUpdater Updater(&LR); LiveRangeUpdater Updater(&LR);
for (unsigned BN : WorkList) { for (unsigned BN : WorkList) {
SlotIndex Start, End; SlotIndex Start, End;
std::tie(Start, End) = Indexes->getMBBRange(BN); std::tie(Start, End) = Indexes->getMBBRange(BN);
// Trim the live range in UseMBB. // Trim the live range in UseMBB.
if (BN == UseMBBNum && Use.isValid()) if (BN == UseMBBNum && Use.isValid())
End = Use; End = Use;
else else
▲ Show 20 Lines • Show All 57 Lines • ▼ Show 20 Lines for (LiveInBlock &I : LiveIn) {
// IDom dominates all of our predecessors, but it may not be their // IDom dominates all of our predecessors, but it may not be their
// immediate dominator. Check if any of them have live-out values that are // immediate dominator. Check if any of them have live-out values that are
// properly dominated by IDom. If so, we need a phi-def here. // properly dominated by IDom. If so, we need a phi-def here.
if (!needPHI) { if (!needPHI) {
IDomValue = Map[IDom->getBlock()]; IDomValue = Map[IDom->getBlock()];
// Cache the DomTree node that defined the value. // Cache the DomTree node that defined the value.
if (IDomValue.first && !IDomValue.second) if (IDomValue.first && IDomValue.first != &UndefVNI)
if (!IDomValue.second)
Map[IDom->getBlock()].second = IDomValue.second = Map[IDom->getBlock()].second = IDomValue.second =
DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
MatzeBUnsubmitted
Not Done
ReplyInline Actions

This can be && instead of a nested if.

MatzeB: This can be `&&` instead of a nested if.
kparzyszAuthorUnsubmitted
Not Done
ReplyInline Actions

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

kparzysz: But then the condition wouldn't fit in a single line.
MatzeBUnsubmitted
Not Done
ReplyInline Actions

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.

MatzeB: But it's two lines either way, isn't it? Not that I care too deeply about it, but my motivation…
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI) { PE = MBB->pred_end(); PI != PE; ++PI) {
LiveOutPair &Value = Map[*PI]; LiveOutPair &Value = Map[*PI];
if (!Value.first || Value.first == IDomValue.first) if (!Value.first || Value.first == IDomValue.first)
continue; continue;
if (Value.first == &UndefVNI) {
needPHI = true;
break;
}
// Cache the DomTree node that defined the value. // Cache the DomTree node that defined the value.
if (!Value.second) if (!Value.second)
Value.second = Value.second =
DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
// This predecessor is carrying something other than IDomValue. // This predecessor is carrying something other than IDomValue.
// It could be because IDomValue hasn't propagated yet, or it could be // It could be because IDomValue hasn't propagated yet, or it could be
Show All 26 Lines for (LiveInBlock &I : LiveIn) {
if (I.Kill.isValid()) { if (I.Kill.isValid()) {
if (VNI) if (VNI)
LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI)); LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
} else { } else {
if (VNI) if (VNI)
LR.addSegment(LiveInterval::Segment(Start, End, VNI)); LR.addSegment(LiveInterval::Segment(Start, End, VNI));
LOP = LiveOutPair(VNI, Node); LOP = LiveOutPair(VNI, Node);
} }
} else if (IDomValue.first) { } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
// No phi-def here. Remember incoming value. // No phi-def here. Remember incoming value.
I.Value = IDomValue.first; I.Value = IDomValue.first;
// If the IDomValue is killed in the block, don't propagate through. // If the IDomValue is killed in the block, don't propagate through.
if (I.Kill.isValid()) if (I.Kill.isValid())
continue; continue;
// Propagate IDomValue if it isn't killed: // Propagate IDomValue if it isn't killed:
Show All 9 Lines

test/CodeGen/Hexagon/regalloc-liveout-undef.ll

  • This file was added.
; RUN: llc -march=hexagon -verify-machineinstrs < %s | FileCheck %s
;
; Check that this compiles successfully.
; CHECK: call f0
target triple = "hexagon"
@g0 = external local_unnamed_addr constant [4 x [36 x i32]], align 8
define i32 @fred(i32 %a0, i32 %a1) local_unnamed_addr #0 {
b2:
%v3 = load i8*, i8** undef, align 4
%v4 = load i16, i16* undef, align 2
%v5 = sdiv i16 %v4, 18
%v6 = sext i16 %v5 to i32
br i1 undef, label %b12, label %b7
b7: ; preds = %b2
%v8 = load i32, i32* undef, align 4
%v9 = add nsw i32 %v8, 7
%v10 = sdiv i32 %v9, 18
%v11 = add nsw i32 %v10, 1
br label %b14
b12: ; preds = %b2
br i1 undef, label %b13, label %b14
b13: ; preds = %b12
br label %b17
b14: ; preds = %b12, %b7
%v15 = phi i32 [ %v6, %b12 ], [ %v11, %b7 ]
br label %b16
b16: ; preds = %b16, %b14
store i32 0, i32* undef, align 4
br i1 undef, label %b16, label %b17
b17: ; preds = %b16, %b13
%v18 = phi i32 [ 0, %b13 ], [ %v15, %b16 ]
%v19 = load i32, i32* undef, align 4
%v20 = load i32, i32* undef, align 4
%v21 = mul i32 %a1, 1152
%v22 = mul i32 %v18, 36
%v23 = add i32 %v21, %v22
%v24 = add i32 %v23, 4608
%v25 = getelementptr i8, i8* %v3, i32 %v24
%v26 = tail call fastcc i32 @f1(i32* nonnull undef, i32* nonnull undef, i32 0, i32 0) #0
%v27 = bitcast i8* %v25 to i32*
%v28 = load i32, i32* getelementptr inbounds ([4 x [36 x i32]], [4 x [36 x i32]]* @g0, i32 0, i32 2, i32 3), align 4
%v29 = sub nsw i32 7, %v20
br label %b30
b30: ; preds = %b30, %b17
%v31 = phi i32* [ undef, %b17 ], [ %v98, %b30 ]
%v32 = phi i32* [ %v27, %b17 ], [ undef, %b30 ]
%v33 = phi i32 [ %v18, %b17 ], [ %v99, %b30 ]
%v34 = icmp slt i32 %v33, %v19
%v35 = select i1 %v34, i32 0, i32 undef
%v36 = load i32, i32* undef, align 4
%v37 = ashr i32 %v36, %v29
store i32 %v37, i32* undef, align 4
%v38 = load i32, i32* undef, align 4
%v39 = ashr i32 %v38, %v29
store i32 %v39, i32* undef, align 4
store i32 undef, i32* undef, align 4
%v40 = load i32, i32* undef, align 4
%v41 = ashr i32 %v40, %v29
store i32 %v41, i32* undef, align 4
%v42 = load i32, i32* %v31, align 4
%v43 = load i32, i32* undef, align 4
%v44 = load i32, i32* undef, align 4
%v45 = load i32, i32* undef, align 4
%v46 = load i32, i32* undef, align 4
%v47 = sub nsw i32 %v45, 0
%v48 = sub nsw i32 %v43, 0
%v49 = sub nsw i32 %v42, %v48
%v50 = ashr i32 %v49, 1
%v51 = tail call i32 @llvm.hexagon.M2.mpy.up(i32 1859775393, i32 0) #1
%v52 = shl i32 %v51, 1
%v53 = add nsw i32 %v50, 0
%v54 = sub nsw i32 %v50, 0
%v55 = add nsw i32 %v53, %v52
%v56 = tail call i32 @llvm.hexagon.M2.mpy.up(i32 2074309917, i32 undef) #1
%v57 = shl i32 %v56, 2
%v58 = add nsw i32 %v55, %v57
%v59 = add nsw i32 %v54, 0
%v60 = sub nsw i32 %v55, %v57
%v61 = load i32, i32* undef, align 4
%v62 = load i32, i32* null, align 4
%v63 = load i32, i32* undef, align 4
%v64 = load i32, i32* undef, align 4
%v65 = load i32, i32* undef, align 4
%v66 = sub nsw i32 %v64, 0
%v67 = sub nsw i32 %v62, 0
%v68 = sub nsw i32 %v61, %v67
%v69 = ashr i32 %v68, 1
%v70 = add nsw i32 %v69, 0
%v71 = sub nsw i32 %v69, 0
%v72 = add nsw i32 %v70, 0
%v73 = sub nsw i32 %v70, 0
%v74 = tail call i32 @llvm.hexagon.M2.mpy.up(i32 2074309917, i32 undef) #1
%v75 = shl i32 %v74, 2
%v76 = tail call i32 @llvm.hexagon.M2.mpy.up(i32 1518500250, i32 undef) #1
%v77 = shl i32 %v76, 2
%v78 = add nsw i32 %v72, %v75
%v79 = add nsw i32 %v71, %v77
%v80 = add nsw i32 %v73, 0
call fastcc void @f0(i32* %v32, i32* nonnull undef, i32 %v35) #0
%v81 = tail call i32 @llvm.hexagon.M2.mpy.up(i32 %v28, i32 %v60) #1
%v82 = add nsw i32 %v81, 0
store i32 %v82, i32* undef, align 4
%v83 = tail call i32 @llvm.hexagon.M2.mpy.up(i32 undef, i32 %v59) #1
%v84 = tail call i32 @llvm.hexagon.M2.mpy.up(i32 undef, i32 undef) #1
%v85 = add i32 %v83, 0
%v86 = add i32 %v85, %v84
store i32 %v86, i32* undef, align 4
%v87 = tail call i32 @llvm.hexagon.M2.mpy.up(i32 undef, i32 undef) #1
%v88 = add nsw i32 %v87, 0
store i32 %v88, i32* undef, align 4
%v89 = load i32, i32* undef, align 8
%v90 = shl i32 %v89, 2
%v91 = tail call i32 @llvm.hexagon.M2.mpy.up(i32 undef, i32 %v58) #1
%v92 = tail call i32 @llvm.hexagon.M2.mpy.up(i32 undef, i32 undef) #1
%v93 = add i32 %v91, %v90
%v94 = add i32 %v93, %v92
store i32 %v94, i32* undef, align 4
%v95 = ashr i32 %v78, 2
store i32 %v95, i32* %v32, align 4
%v96 = ashr i32 %v79, 2
store i32 %v96, i32* undef, align 4
%v97 = ashr i32 %v80, 2
store i32 %v97, i32* undef, align 4
%v98 = getelementptr inbounds i32, i32* %v31, i32 18
%v99 = add nsw i32 %v33, 1
br label %b30
}
declare i32 @llvm.hexagon.M2.mpy.up(i32, i32) #1
declare hidden fastcc void @f0(i32* nocapture readonly, i32* nocapture, i32) unnamed_addr #0
declare hidden fastcc i32 @f1(i32* nocapture, i32* nocapture, i32, i32) unnamed_addr #0
attributes #0 = { nounwind "target-cpu"="hexagonv60" }
attributes #1 = { nounwind readnone }