aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/CodeGen/LiveVariables.h11
-rw-r--r--lib/CodeGen/LiveIntervalAnalysis.cpp86
-rw-r--r--lib/CodeGen/LiveVariables.cpp1
-rw-r--r--lib/CodeGen/PHIElimination.cpp1
-rw-r--r--test/CodeGen/X86/2010-02-23-SingleDefPhiJoin.ll146
5 files changed, 193 insertions, 52 deletions
diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h
index a7bf600e1e..fc5ea6f968 100644
--- a/include/llvm/CodeGen/LiveVariables.h
+++ b/include/llvm/CodeGen/LiveVariables.h
@@ -124,6 +124,11 @@ private:
///
std::vector<VarInfo> VirtRegInfo;
+ /// PHIJoins - list of virtual registers that are PHI joins. These registers
+ /// may have multiple definitions, and they require special handling when
+ /// building live intervals.
+ SparseBitVector<> PHIJoins;
+
/// ReservedRegisters - This vector keeps track of which registers
/// are reserved register which are not allocatable by the target machine.
/// We can not track liveness for values that are in this set.
@@ -295,6 +300,12 @@ public:
void addNewBlock(MachineBasicBlock *BB,
MachineBasicBlock *DomBB,
MachineBasicBlock *SuccBB);
+
+ /// isPHIJoin - Return true if Reg is a phi join register.
+ bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); }
+
+ /// setPHIJoin - Mark Reg as a phi join register.
+ void setPHIJoin(unsigned Reg) { PHIJoins.set(Reg); }
};
} // End llvm namespace
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 0b38ffb970..ebcfd60a71 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -329,24 +329,43 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
DEBUG(dbgs() << " +" << NewLR);
interval.addRange(NewLR);
- // Iterate over all of the blocks that the variable is completely
- // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
- // live interval.
- for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
- E = vi.AliveBlocks.end(); I != E; ++I) {
- MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
- LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
- interval.addRange(LR);
- DEBUG(dbgs() << " +" << LR);
+ bool PHIJoin = lv_->isPHIJoin(interval.reg);
+
+ if (PHIJoin) {
+ // A phi join register is killed at the end of the MBB and revived as a new
+ // valno in the killing blocks.
+ assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
+ DEBUG(dbgs() << " phi-join");
+ ValNo->addKill(indexes_->getTerminatorGap(mbb));
+ ValNo->setHasPHIKill(true);
+ } else {
+ // Iterate over all of the blocks that the variable is completely
+ // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
+ // live interval.
+ for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
+ E = vi.AliveBlocks.end(); I != E; ++I) {
+ MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
+ LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
+ interval.addRange(LR);
+ DEBUG(dbgs() << " +" << LR);
+ }
}
// Finally, this virtual register is live from the start of any killing
// block to the 'use' slot of the killing instruction.
for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
MachineInstr *Kill = vi.Kills[i];
- SlotIndex killIdx =
- getInstructionIndex(Kill).getDefIndex();
- LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo);
+ SlotIndex Start = getMBBStartIdx(Kill->getParent());
+ SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex();
+
+ // Create interval with one of a NEW value number. Note that this value
+ // number isn't actually defined by an instruction, weird huh? :)
+ if (PHIJoin) {
+ ValNo = interval.getNextValue(SlotIndex(Start, true), 0, false,
+ VNInfoAllocator);
+ ValNo->setIsPHIDef(true);
+ }
+ LiveRange LR(Start, killIdx, ValNo);
interval.addRange(LR);
ValNo->addKill(killIdx);
DEBUG(dbgs() << " +" << LR);
@@ -409,48 +428,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
interval.print(dbgs(), tri_);
});
} else {
- // Otherwise, this must be because of phi elimination. If this is the
- // first redefinition of the vreg that we have seen, go back and change
- // the live range in the PHI block to be a different value number.
- if (interval.containsOneValue()) {
-
- VNInfo *VNI = interval.getValNumInfo(0);
- // Phi elimination may have reused the register for multiple identical
- // phi nodes. There will be a kill per phi. Remove the old ranges that
- // we now know have an incorrect number.
- for (unsigned ki=0, ke=vi.Kills.size(); ki != ke; ++ki) {
- MachineInstr *Killer = vi.Kills[ki];
- SlotIndex Start = getMBBStartIdx(Killer->getParent());
- SlotIndex End = getInstructionIndex(Killer).getDefIndex();
- DEBUG({
- dbgs() << "\n\t\trenaming [" << Start << "," << End << "] in: ";
- interval.print(dbgs(), tri_);
- });
- interval.removeRange(Start, End);
-
- // Replace the interval with one of a NEW value number. Note that
- // this value number isn't actually defined by an instruction, weird
- // huh? :)
- LiveRange LR(Start, End,
- interval.getNextValue(SlotIndex(Start, true),
- 0, false, VNInfoAllocator));
- LR.valno->setIsPHIDef(true);
- interval.addRange(LR);
- LR.valno->addKill(End);
- }
-
- MachineBasicBlock *killMBB = getMBBFromIndex(VNI->def);
- VNI->addKill(indexes_->getTerminatorGap(killMBB));
- VNI->setHasPHIKill(true);
- DEBUG({
- dbgs() << " RESULT: ";
- interval.print(dbgs(), tri_);
- });
- }
-
+ assert(lv_->isPHIJoin(interval.reg) && "Multiply defined register");
// In the case of PHI elimination, each variable definition is only
// live until the end of the block. We've already taken care of the
// rest of the live range.
+
SlotIndex defIndex = MIIdx.getDefIndex();
if (MO.isEarlyClobber())
defIndex = MIIdx.getUseIndex();
@@ -468,7 +450,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
interval.addRange(LR);
ValNo->addKill(indexes_->getTerminatorGap(mbb));
ValNo->setHasPHIKill(true);
- DEBUG(dbgs() << " +" << LR);
+ DEBUG(dbgs() << " phi-join +" << LR);
}
}
diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp
index 8a124dc79b..68c85394d4 100644
--- a/lib/CodeGen/LiveVariables.cpp
+++ b/lib/CodeGen/LiveVariables.cpp
@@ -510,6 +510,7 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) {
PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()];
std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0);
std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0);
+ PHIJoins.clear();
/// Get some space for a respectable number of registers.
VirtRegInfo.resize(64);
diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp
index 9e4bc0c273..bdfd448acd 100644
--- a/lib/CodeGen/PHIElimination.cpp
+++ b/lib/CodeGen/PHIElimination.cpp
@@ -223,6 +223,7 @@ void llvm::PHIElimination::LowerAtomicPHINode(
// Increment use count of the newly created virtual register.
VI.NumUses++;
+ LV->setPHIJoin(IncomingReg);
// When we are reusing the incoming register, it may already have been
// killed in this block. The old kill will also have been inserted at
diff --git a/test/CodeGen/X86/2010-02-23-SingleDefPhiJoin.ll b/test/CodeGen/X86/2010-02-23-SingleDefPhiJoin.ll
new file mode 100644
index 0000000000..aeed401461
--- /dev/null
+++ b/test/CodeGen/X86/2010-02-23-SingleDefPhiJoin.ll
@@ -0,0 +1,146 @@
+; RUN: llc < %s
+; PR6363
+;
+; This test case creates a phi join register with a single definition. The other
+; predecessor blocks are implicit-def.
+;
+; If LiveIntervalAnalysis fails to recognize this as a phi join, the coalescer
+; will detect an infinity valno loop.
+;
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @decode(i8* nocapture %input, i32 %offset, i8* nocapture %output) nounwind {
+entry:
+ br i1 undef, label %meshBB86, label %meshBB102
+
+bb: ; preds = %meshBB106, %meshBB102
+ br i1 false, label %bb9, label %meshBB90
+
+bb.nph: ; preds = %meshBB90
+ br label %meshBB114
+
+bb.nph.fragment: ; preds = %meshBB114
+ br label %meshBB118
+
+bb1.fragment: ; preds = %meshBB118
+ br i1 false, label %bb2, label %bb3
+
+bb2: ; preds = %bb1.fragment
+ br label %meshBB74
+
+bb2.fragment15: ; preds = %meshBB74
+ br label %meshBB98
+
+bb3: ; preds = %bb1.fragment
+ br i1 undef, label %meshBB, label %meshBB102
+
+bb4: ; preds = %meshBB
+ br label %meshBB118
+
+bb4.fragment: ; preds = %meshBB118
+ br label %meshBB82
+
+bb5: ; preds = %meshBB102, %meshBB82
+ br i1 false, label %bb6, label %bb7
+
+bb6: ; preds = %bb5
+ br label %bb7
+
+bb7: ; preds = %meshBB98, %bb6, %bb5
+ br label %meshBB114
+
+bb7.fragment: ; preds = %meshBB114
+ br i1 undef, label %meshBB74, label %bb9
+
+bb9: ; preds = %bb7.fragment, %bb
+ br label %bb1.i23
+
+bb1.i23: ; preds = %meshBB110, %bb9
+ br i1 undef, label %meshBB106, label %meshBB110
+
+skip_to_newline.exit26: ; preds = %meshBB106
+ br label %meshBB86
+
+skip_to_newline.exit26.fragment: ; preds = %meshBB86
+ br i1 false, label %meshBB90, label %meshBB106
+
+bb11.fragment: ; preds = %meshBB90, %meshBB86
+ br label %meshBB122
+
+bb1.i: ; preds = %meshBB122, %meshBB
+ %ooffset.2.lcssa.phi.SV.phi203 = phi i32 [ 0, %meshBB122 ], [ %ooffset.2.lcssa.phi.SV.phi233, %meshBB ] ; <i32> [#uses=1]
+ br label %meshBB98
+
+bb1.i.fragment: ; preds = %meshBB98
+ br i1 undef, label %meshBB78, label %meshBB
+
+skip_to_newline.exit: ; preds = %meshBB78
+ br i1 undef, label %bb12, label %meshBB110
+
+bb12: ; preds = %skip_to_newline.exit
+ br label %meshBB94
+
+bb12.fragment: ; preds = %meshBB94
+ br i1 false, label %bb13, label %meshBB78
+
+bb13: ; preds = %bb12.fragment
+ br label %meshBB82
+
+bb13.fragment: ; preds = %meshBB82
+ br i1 undef, label %meshBB94, label %meshBB122
+
+bb14: ; preds = %meshBB94
+ ret i32 %ooffset.2.lcssa.phi.SV.phi250
+
+bb15: ; preds = %meshBB122, %meshBB110, %meshBB78
+ unreachable
+
+meshBB: ; preds = %bb1.i.fragment, %bb3
+ %ooffset.2.lcssa.phi.SV.phi233 = phi i32 [ undef, %bb3 ], [ %ooffset.2.lcssa.phi.SV.phi209, %bb1.i.fragment ] ; <i32> [#uses=1]
+ br i1 undef, label %bb1.i, label %bb4
+
+meshBB74: ; preds = %bb7.fragment, %bb2
+ br i1 false, label %meshBB118, label %bb2.fragment15
+
+meshBB78: ; preds = %bb12.fragment, %bb1.i.fragment
+ %ooffset.2.lcssa.phi.SV.phi239 = phi i32 [ %ooffset.2.lcssa.phi.SV.phi209, %bb1.i.fragment ], [ %ooffset.2.lcssa.phi.SV.phi250, %bb12.fragment ] ; <i32> [#uses=1]
+ br i1 false, label %bb15, label %skip_to_newline.exit
+
+meshBB82: ; preds = %bb13, %bb4.fragment
+ br i1 false, label %bb5, label %bb13.fragment
+
+meshBB86: ; preds = %skip_to_newline.exit26, %entry
+ br i1 undef, label %skip_to_newline.exit26.fragment, label %bb11.fragment
+
+meshBB90: ; preds = %skip_to_newline.exit26.fragment, %bb
+ br i1 false, label %bb11.fragment, label %bb.nph
+
+meshBB94: ; preds = %bb13.fragment, %bb12
+ %ooffset.2.lcssa.phi.SV.phi250 = phi i32 [ 0, %bb13.fragment ], [ %ooffset.2.lcssa.phi.SV.phi239, %bb12 ] ; <i32> [#uses=2]
+ br i1 false, label %bb12.fragment, label %bb14
+
+meshBB98: ; preds = %bb1.i, %bb2.fragment15
+ %ooffset.2.lcssa.phi.SV.phi209 = phi i32 [ undef, %bb2.fragment15 ], [ %ooffset.2.lcssa.phi.SV.phi203, %bb1.i ] ; <i32> [#uses=2]
+ br i1 undef, label %bb1.i.fragment, label %bb7
+
+meshBB102: ; preds = %bb3, %entry
+ br i1 undef, label %bb5, label %bb
+
+meshBB106: ; preds = %skip_to_newline.exit26.fragment, %bb1.i23
+ br i1 undef, label %bb, label %skip_to_newline.exit26
+
+meshBB110: ; preds = %skip_to_newline.exit, %bb1.i23
+ br i1 false, label %bb15, label %bb1.i23
+
+meshBB114: ; preds = %bb7, %bb.nph
+ %meshStackVariable115.phi = phi i32 [ 19, %bb7 ], [ 8, %bb.nph ] ; <i32> [#uses=0]
+ br i1 undef, label %bb.nph.fragment, label %bb7.fragment
+
+meshBB118: ; preds = %meshBB74, %bb4, %bb.nph.fragment
+ %meshCmp121 = icmp eq i32 undef, 10 ; <i1> [#uses=1]
+ br i1 %meshCmp121, label %bb4.fragment, label %bb1.fragment
+
+meshBB122: ; preds = %bb13.fragment, %bb11.fragment
+ br i1 false, label %bb1.i, label %bb15
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-25 23:20:39 +0000