1 //===- StrongPHIElimination.cpp - Eliminate PHI nodes by inserting copies -===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass eliminates PHI instructions by aggressively coalescing the copies
11 // that would be inserted by a naive algorithm and only inserting the copies
12 // that are necessary. The coalescing technique initially assumes that all
13 // registers appearing in a PHI instruction do not interfere. It then eliminates
14 // proven interferences, using dominators to only perform a linear number of
15 // interference tests instead of the quadratic number of interference tests
16 // that this would naively require. This is a technique derived from:
18 // Budimlic, et al. Fast copy coalescing and live-range identification.
19 // In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language
20 // Design and Implementation (Berlin, Germany, June 17 - 19, 2002).
21 // PLDI '02. ACM, New York, NY, 25-32.
23 // The original implementation constructs a data structure they call a dominance
24 // forest for this purpose. The dominance forest was shown to be unnecessary,
25 // as it is possible to emulate the creation and traversal of a dominance forest
26 // by directly using the dominator tree, rather than actually constructing the
27 // dominance forest. This technique is explained in:
29 // Boissinot, et al. Revisiting Out-of-SSA Translation for Correctness, Code
30 // Quality and Efficiency,
31 // In Proceedings of the 7th annual IEEE/ACM International Symposium on Code
32 // Generation and Optimization (Seattle, Washington, March 22 - 25, 2009).
33 // CGO '09. IEEE, Washington, DC, 114-125.
35 // Careful implementation allows for all of the dominator forest interference
36 // checks to be performed at once in a single depth-first traversal of the
37 // dominator tree, which is what is implemented here.
39 //===----------------------------------------------------------------------===//
41 #define DEBUG_TYPE "strongphielim"
42 #include "PHIEliminationUtils.h"
43 #include "llvm/CodeGen/Passes.h"
44 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
45 #include "llvm/CodeGen/MachineDominators.h"
46 #include "llvm/CodeGen/MachineFunctionPass.h"
47 #include "llvm/CodeGen/MachineInstrBuilder.h"
48 #include "llvm/CodeGen/MachineRegisterInfo.h"
49 #include "llvm/Target/TargetInstrInfo.h"
50 #include "llvm/Support/Debug.h"
54 class StrongPHIElimination : public MachineFunctionPass {
56 static char ID; // Pass identification, replacement for typeid
57 StrongPHIElimination() : MachineFunctionPass(ID) {
58 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
61 virtual void getAnalysisUsage(AnalysisUsage&) const;
62 bool runOnMachineFunction(MachineFunction&);
65 /// This struct represents a single node in the union-find data structure
66 /// representing the variable congruence classes. There is one difference
67 /// from a normal union-find data structure. We steal two bits from the parent
68 /// pointer . One of these bits is used to represent whether the register
69 /// itself has been isolated, and the other is used to represent whether the
70 /// PHI with that register as its destination has been isolated.
72 /// Note that this leads to the strange situation where the leader of a
73 /// congruence class may no longer logically be a member, due to being
77 kRegisterIsolatedFlag = 1,
80 Node(unsigned v) : value(v), rank(0) { parent.setPointer(this); }
84 PointerIntPair<Node*, 2> parent;
89 /// Add a register in a new congruence class containing only itself.
90 void addReg(unsigned);
92 /// Join the congruence classes of two registers.
93 void unionRegs(unsigned, unsigned);
95 /// Get the color of a register. The color is 0 if the register has been
97 unsigned getRegColor(unsigned);
99 // Isolate a register.
100 void isolateReg(unsigned);
102 /// Get the color of a PHI. The color of a PHI is 0 if the PHI has been
103 /// isolated. Otherwise, it is the original color of its destination and
104 /// all of its operands (before they were isolated, if they were).
105 unsigned getPHIColor(MachineInstr*);
108 void isolatePHI(MachineInstr*);
110 void PartitionRegisters(MachineFunction& MF);
112 /// Traverses a basic block, splitting any interferences found between
113 /// registers in the same congruence class. It takes two DenseMaps as
114 /// arguments that it also updates: CurrentDominatingParent, which maps
115 /// a color to the register in that congruence class whose definition was
116 /// most recently seen, and ImmediateDominatingParent, which maps a register
117 /// to the register in the same congruence class that most immediately
120 /// This function assumes that it is being called in a depth-first traversal
121 /// of the dominator tree.
122 void SplitInterferencesForBasicBlock(
124 DenseMap<unsigned, unsigned>& CurrentDominatingParent,
125 DenseMap<unsigned, unsigned>& ImmediateDominatingParent);
127 // Lowers a PHI instruction, inserting copies of the source and destination
128 // registers as necessary.
129 void InsertCopiesForPHI(MachineInstr*, MachineBasicBlock*);
131 // Merges the live interval of Reg into NewReg and renames Reg to NewReg
132 // everywhere that Reg appears. Requires Reg and NewReg to have non-
133 // overlapping lifetimes.
134 void MergeLIsAndRename(unsigned Reg, unsigned NewReg);
136 MachineRegisterInfo* MRI;
137 const TargetInstrInfo* TII;
138 MachineDominatorTree* DT;
141 BumpPtrAllocator Allocator;
143 DenseMap<unsigned, Node*> RegNodeMap;
145 // FIXME: Can these two data structures be combined? Would a std::multimap
148 // Stores pairs of predecessor basic blocks and the source registers of
149 // inserted copy instructions.
150 typedef DenseSet<std::pair<MachineBasicBlock*, unsigned> > SrcCopySet;
151 SrcCopySet InsertedSrcCopySet;
153 // Maps pairs of predecessor basic blocks and colors to their defining copy
155 typedef DenseMap<std::pair<MachineBasicBlock*, unsigned>, MachineInstr*>
157 SrcCopyMap InsertedSrcCopyMap;
159 // Maps inserted destination copy registers to their defining copy
161 typedef DenseMap<unsigned, MachineInstr*> DestCopyMap;
162 DestCopyMap InsertedDestCopies;
166 char StrongPHIElimination::ID = 0;
167 INITIALIZE_PASS_BEGIN(StrongPHIElimination, "strong-phi-node-elimination",
168 "Eliminate PHI nodes for register allocation, intelligently", false, false)
169 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
170 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
171 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
172 INITIALIZE_PASS_END(StrongPHIElimination, "strong-phi-node-elimination",
173 "Eliminate PHI nodes for register allocation, intelligently", false, false)
175 char &llvm::StrongPHIEliminationID = StrongPHIElimination::ID;
177 void StrongPHIElimination::getAnalysisUsage(AnalysisUsage& AU) const {
178 AU.setPreservesCFG();
179 AU.addRequired<MachineDominatorTree>();
180 AU.addRequired<SlotIndexes>();
181 AU.addPreserved<SlotIndexes>();
182 AU.addRequired<LiveIntervals>();
183 AU.addPreserved<LiveIntervals>();
184 MachineFunctionPass::getAnalysisUsage(AU);
187 static MachineOperand* findLastUse(MachineBasicBlock* MBB, unsigned Reg) {
188 // FIXME: This only needs to check from the first terminator, as only the
189 // first terminator can use a virtual register.
190 for (MachineBasicBlock::reverse_iterator RI = MBB->rbegin(); ; ++RI) {
191 assert (RI != MBB->rend());
192 MachineInstr* MI = &*RI;
194 for (MachineInstr::mop_iterator OI = MI->operands_begin(),
195 OE = MI->operands_end(); OI != OE; ++OI) {
196 MachineOperand& MO = *OI;
197 if (MO.isReg() && MO.isUse() && MO.getReg() == Reg)
204 bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
205 MRI = &MF.getRegInfo();
206 TII = MF.getTarget().getInstrInfo();
207 DT = &getAnalysis<MachineDominatorTree>();
208 LI = &getAnalysis<LiveIntervals>();
210 PartitionRegisters(MF);
212 // Perform a depth-first traversal of the dominator tree, splitting
213 // interferences amongst PHI-congruence classes.
214 DenseMap<unsigned, unsigned> CurrentDominatingParent;
215 DenseMap<unsigned, unsigned> ImmediateDominatingParent;
216 for (df_iterator<MachineDomTreeNode*> DI = df_begin(DT->getRootNode()),
217 DE = df_end(DT->getRootNode()); DI != DE; ++DI) {
218 SplitInterferencesForBasicBlock(*DI->getBlock(),
219 CurrentDominatingParent,
220 ImmediateDominatingParent);
223 // Insert copies for all PHI source and destination registers.
224 for (MachineFunction::iterator I = MF.begin(), E = MF.end();
226 for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
227 BBI != BBE && BBI->isPHI(); ++BBI) {
228 InsertCopiesForPHI(BBI, I);
232 // FIXME: Preserve the equivalence classes during copy insertion and use
233 // the preversed equivalence classes instead of recomputing them.
235 PartitionRegisters(MF);
237 DenseMap<unsigned, unsigned> RegRenamingMap;
238 bool Changed = false;
239 for (MachineFunction::iterator I = MF.begin(), E = MF.end();
241 MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
242 while (BBI != BBE && BBI->isPHI()) {
243 MachineInstr* PHI = BBI;
245 assert(PHI->getNumOperands() > 0);
247 unsigned SrcReg = PHI->getOperand(1).getReg();
248 unsigned SrcColor = getRegColor(SrcReg);
249 unsigned NewReg = RegRenamingMap[SrcColor];
252 RegRenamingMap[SrcColor] = SrcReg;
254 MergeLIsAndRename(SrcReg, NewReg);
256 unsigned DestReg = PHI->getOperand(0).getReg();
257 if (!InsertedDestCopies.count(DestReg))
258 MergeLIsAndRename(DestReg, NewReg);
260 for (unsigned i = 3; i < PHI->getNumOperands(); i += 2) {
261 unsigned SrcReg = PHI->getOperand(i).getReg();
262 MergeLIsAndRename(SrcReg, NewReg);
266 LI->RemoveMachineInstrFromMaps(PHI);
267 PHI->eraseFromParent();
272 // Due to the insertion of copies to split live ranges, the live intervals are
273 // guaranteed to not overlap, except in one case: an original PHI source and a
274 // PHI destination copy. In this case, they have the same value and thus don't
275 // truly intersect, so we merge them into the value live at that point.
276 // FIXME: Is there some better way we can handle this?
277 for (DestCopyMap::iterator I = InsertedDestCopies.begin(),
278 E = InsertedDestCopies.end(); I != E; ++I) {
279 unsigned DestReg = I->first;
280 unsigned DestColor = getRegColor(DestReg);
281 unsigned NewReg = RegRenamingMap[DestColor];
283 LiveInterval& DestLI = LI->getInterval(DestReg);
284 LiveInterval& NewLI = LI->getInterval(NewReg);
286 assert(DestLI.ranges.size() == 1);
287 LiveRange* DestLR = DestLI.begin();
288 VNInfo* NewVNI = NewLI.getVNInfoAt(DestLR->start);
290 NewVNI = NewLI.createValueCopy(DestLR->valno, LI->getVNInfoAllocator());
291 MachineInstr* CopyInstr = I->second;
292 CopyInstr->getOperand(1).setIsKill(true);
295 LiveRange NewLR(DestLR->start, DestLR->end, NewVNI);
296 NewLI.addRange(NewLR);
298 LI->removeInterval(DestReg);
299 MRI->replaceRegWith(DestReg, NewReg);
302 // Adjust the live intervals of all PHI source registers to handle the case
303 // where the PHIs in successor blocks were the only later uses of the source
305 for (SrcCopySet::iterator I = InsertedSrcCopySet.begin(),
306 E = InsertedSrcCopySet.end(); I != E; ++I) {
307 MachineBasicBlock* MBB = I->first;
308 unsigned SrcReg = I->second;
309 if (unsigned RenamedRegister = RegRenamingMap[getRegColor(SrcReg)])
310 SrcReg = RenamedRegister;
312 LiveInterval& SrcLI = LI->getInterval(SrcReg);
314 bool isLiveOut = false;
315 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
316 SE = MBB->succ_end(); SI != SE; ++SI) {
317 if (SrcLI.liveAt(LI->getMBBStartIdx(*SI))) {
326 MachineOperand* LastUse = findLastUse(MBB, SrcReg);
328 SlotIndex LastUseIndex = LI->getInstructionIndex(LastUse->getParent());
329 SrcLI.removeRange(LastUseIndex.getDefIndex(), LI->getMBBEndIdx(MBB));
330 LastUse->setIsKill(true);
337 InsertedSrcCopySet.clear();
338 InsertedSrcCopyMap.clear();
339 InsertedDestCopies.clear();
344 void StrongPHIElimination::addReg(unsigned Reg) {
345 if (RegNodeMap.count(Reg))
347 RegNodeMap[Reg] = new (Allocator) Node(Reg);
350 StrongPHIElimination::Node*
351 StrongPHIElimination::Node::getLeader() {
352 Node* parentPointer = parent.getPointer();
353 if (parentPointer == this)
355 Node* newParent = parentPointer->getLeader();
356 parent.setPointer(newParent);
360 unsigned StrongPHIElimination::getRegColor(unsigned Reg) {
361 DenseMap<unsigned, Node*>::iterator RI = RegNodeMap.find(Reg);
362 if (RI == RegNodeMap.end())
364 Node* Node = RI->second;
365 if (Node->parent.getInt() & Node::kRegisterIsolatedFlag)
367 return Node->getLeader()->value;
370 void StrongPHIElimination::unionRegs(unsigned Reg1, unsigned Reg2) {
371 Node* Node1 = RegNodeMap[Reg1]->getLeader();
372 Node* Node2 = RegNodeMap[Reg2]->getLeader();
374 if (Node1->rank > Node2->rank) {
375 Node2->parent.setPointer(Node1->getLeader());
376 } else if (Node1->rank < Node2->rank) {
377 Node1->parent.setPointer(Node2->getLeader());
378 } else if (Node1 != Node2) {
379 Node2->parent.setPointer(Node1->getLeader());
384 void StrongPHIElimination::isolateReg(unsigned Reg) {
385 Node* Node = RegNodeMap[Reg];
386 Node->parent.setInt(Node->parent.getInt() | Node::kRegisterIsolatedFlag);
389 unsigned StrongPHIElimination::getPHIColor(MachineInstr* PHI) {
390 assert(PHI->isPHI());
392 unsigned DestReg = PHI->getOperand(0).getReg();
393 Node* DestNode = RegNodeMap[DestReg];
394 if (DestNode->parent.getInt() & Node::kPHIIsolatedFlag)
397 for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
398 unsigned SrcColor = getRegColor(PHI->getOperand(i).getReg());
405 void StrongPHIElimination::isolatePHI(MachineInstr* PHI) {
406 assert(PHI->isPHI());
407 Node* Node = RegNodeMap[PHI->getOperand(0).getReg()];
408 Node->parent.setInt(Node->parent.getInt() | Node::kPHIIsolatedFlag);
411 void StrongPHIElimination::PartitionRegisters(MachineFunction& MF) {
412 for (MachineFunction::iterator I = MF.begin(), E = MF.end();
414 for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
415 BBI != BBE && BBI->isPHI(); ++BBI) {
416 unsigned DestReg = BBI->getOperand(0).getReg();
419 for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
420 unsigned SrcReg = BBI->getOperand(i).getReg();
422 unionRegs(DestReg, SrcReg);
428 /// SplitInterferencesForBasicBlock - traverses a basic block, splitting any
429 /// interferences found between registers in the same congruence class. It
430 /// takes two DenseMaps as arguments that it also updates:
432 /// 1) CurrentDominatingParent, which maps a color to the register in that
433 /// congruence class whose definition was most recently seen.
435 /// 2) ImmediateDominatingParent, which maps a register to the register in the
436 /// same congruence class that most immediately dominates it.
438 /// This function assumes that it is being called in a depth-first traversal
439 /// of the dominator tree.
441 /// The algorithm used here is a generalization of the dominance-based SSA test
442 /// for two variables. If there are variables a_1, ..., a_n such that
444 /// def(a_1) dom ... dom def(a_n),
446 /// then we can test for an interference between any two a_i by only using O(n)
447 /// interference tests between pairs of variables. If i < j and a_i and a_j
448 /// interfere, then a_i is alive at def(a_j), so it is also alive at def(a_i+1).
449 /// Thus, in order to test for an interference involving a_i, we need only check
450 /// for a potential interference with a_i+1.
452 /// This method can be generalized to arbitrary sets of variables by performing
453 /// a depth-first traversal of the dominator tree. As we traverse down a branch
454 /// of the dominator tree, we keep track of the current dominating variable and
455 /// only perform an interference test with that variable. However, when we go to
456 /// another branch of the dominator tree, the definition of the current dominating
457 /// variable may no longer dominate the current block. In order to correct this,
458 /// we need to use a stack of past choices of the current dominating variable
459 /// and pop from this stack until we find a variable whose definition actually
460 /// dominates the current block.
462 /// There will be one push on this stack for each variable that has become the
463 /// current dominating variable, so instead of using an explicit stack we can
464 /// simply associate the previous choice for a current dominating variable with
465 /// the new choice. This works better in our implementation, where we test for
466 /// interference in multiple distinct sets at once.
468 StrongPHIElimination::SplitInterferencesForBasicBlock(
469 MachineBasicBlock& MBB,
470 DenseMap<unsigned, unsigned>& CurrentDominatingParent,
471 DenseMap<unsigned, unsigned>& ImmediateDominatingParent) {
472 for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
474 for (MachineInstr::const_mop_iterator I = BBI->operands_begin(),
475 E = BBI->operands_end(); I != E && I->isReg() && I->isDef(); ++I) {
476 const MachineOperand& MO = *I;
478 unsigned DestReg = MO.getReg();
479 if (!DestReg || !TargetRegisterInfo::isVirtualRegister(DestReg))
482 // If the virtual register being defined is not used in any PHI or has
483 // already been isolated, then there are no more interferences to check.
484 unsigned DestColor = getRegColor(DestReg);
488 // The input to this pass sometimes is not in SSA form in every basic
489 // block, as some virtual registers have redefinitions. We could eliminate
490 // this by fixing the passes that generate the non-SSA code, or we could
491 // handle it here by tracking defining machine instructions rather than
492 // virtual registers. For now, we just handle the situation conservatively
493 // in a way that will possibly lead to false interferences.
494 unsigned NewParent = CurrentDominatingParent[DestColor];
495 if (NewParent == DestReg)
498 // Pop registers from the stack represented by ImmediateDominatingParent
499 // until we find a parent that dominates the current instruction.
500 while (NewParent && (!DT->dominates(MRI->getVRegDef(NewParent), BBI)
501 || !getRegColor(NewParent)))
502 NewParent = ImmediateDominatingParent[NewParent];
504 // If NewParent is nonzero, then its definition dominates the current
505 // instruction, so it is only necessary to check for the liveness of
506 // NewParent in order to check for an interference.
508 && LI->getInterval(NewParent).liveAt(LI->getInstructionIndex(BBI))) {
509 // If there is an interference, always isolate the new register. This
510 // could be improved by using a heuristic that decides which of the two
511 // registers to isolate.
513 CurrentDominatingParent[DestColor] = NewParent;
515 // If there is no interference, update ImmediateDominatingParent and set
516 // the CurrentDominatingParent for this color to the current register.
517 ImmediateDominatingParent[DestReg] = NewParent;
518 CurrentDominatingParent[DestColor] = DestReg;
523 // We now walk the PHIs in successor blocks and check for interferences. This
524 // is necesary because the use of a PHI's operands are logically contained in
525 // the predecessor block. The def of a PHI's destination register is processed
526 // along with the other defs in a basic block.
528 // The map CurrentPHIForColor maps a color to a pair of a MachineInstr* and a
529 // virtual register, which is the operand of that PHI corresponding to the
530 // current basic block.
531 // FIXME: This should use a container that doesn't always perform heap
533 DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > CurrentPHIForColor;
535 for (MachineBasicBlock::succ_iterator SI = MBB.succ_begin(),
536 SE = MBB.succ_end(); SI != SE; ++SI) {
537 for (MachineBasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end();
538 BBI != BBE && BBI->isPHI(); ++BBI) {
539 MachineInstr* PHI = BBI;
541 // If a PHI is already isolated, either by being isolated directly or
542 // having all of its operands isolated, ignore it.
543 unsigned Color = getPHIColor(PHI);
547 // Find the index of the PHI operand that corresponds to this basic block.
549 for (PredIndex = 1; PredIndex < PHI->getNumOperands(); PredIndex += 2) {
550 if (PHI->getOperand(PredIndex + 1).getMBB() == &MBB)
553 assert(PredIndex < PHI->getNumOperands());
554 unsigned PredOperandReg = PHI->getOperand(PredIndex).getReg();
556 // Pop registers from the stack represented by ImmediateDominatingParent
557 // until we find a parent that dominates the current instruction.
558 unsigned NewParent = CurrentDominatingParent[Color];
560 && (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB)
561 || !getRegColor(NewParent)))
562 NewParent = ImmediateDominatingParent[NewParent];
563 CurrentDominatingParent[Color] = NewParent;
565 // If there is an interference with a register, always isolate the
566 // register rather than the PHI. It is also possible to isolate the
567 // PHI, but that introduces copies for all of the registers involved
569 if (NewParent && LI->isLiveOutOfMBB(LI->getInterval(NewParent), &MBB)
570 && NewParent != PredOperandReg)
571 isolateReg(NewParent);
573 std::pair<MachineInstr*, unsigned> CurrentPHI = CurrentPHIForColor[Color];
575 // If two PHIs have the same operand from every shared predecessor, then
576 // they don't actually interfere. Otherwise, isolate the current PHI. This
577 // could possibly be improved, e.g. we could isolate the PHI with the
579 if (CurrentPHI.first && CurrentPHI.second != PredOperandReg)
582 CurrentPHIForColor[Color] = std::make_pair(PHI, PredOperandReg);
587 void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
588 MachineBasicBlock* MBB) {
589 assert(PHI->isPHI());
590 unsigned PHIColor = getPHIColor(PHI);
592 for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
593 MachineOperand& SrcMO = PHI->getOperand(i);
595 // If a source is defined by an implicit def, there is no need to insert a
596 // copy in the predecessor.
600 unsigned SrcReg = SrcMO.getReg();
601 assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
602 "Machine PHI Operands must all be virtual registers!");
604 MachineBasicBlock* PredBB = PHI->getOperand(i + 1).getMBB();
605 unsigned SrcColor = getRegColor(SrcReg);
607 // If neither the PHI nor the operand were isolated, then we only need to
608 // set the phi-kill flag on the VNInfo at this PHI.
609 if (PHIColor && SrcColor == PHIColor) {
610 LiveInterval& SrcInterval = LI->getInterval(SrcReg);
611 SlotIndex PredIndex = LI->getMBBEndIdx(PredBB);
612 VNInfo* SrcVNI = SrcInterval.getVNInfoAt(PredIndex.getPrevIndex());
614 SrcVNI->setHasPHIKill(true);
618 unsigned CopyReg = 0;
620 SrcCopyMap::const_iterator I
621 = InsertedSrcCopyMap.find(std::make_pair(PredBB, PHIColor));
623 = I != InsertedSrcCopyMap.end() ? I->second->getOperand(0).getReg() : 0;
627 const TargetRegisterClass* RC = MRI->getRegClass(SrcReg);
628 CopyReg = MRI->createVirtualRegister(RC);
630 MachineBasicBlock::iterator
631 CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
632 unsigned SrcSubReg = SrcMO.getSubReg();
633 MachineInstr* CopyInstr = BuildMI(*PredBB,
636 TII->get(TargetOpcode::COPY),
637 CopyReg).addReg(SrcReg, 0, SrcSubReg);
638 LI->InsertMachineInstrInMaps(CopyInstr);
640 // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
641 // the newly added range.
642 LI->addLiveRangeToEndOfBlock(CopyReg, CopyInstr);
643 InsertedSrcCopySet.insert(std::make_pair(PredBB, SrcReg));
647 unionRegs(PHIColor, CopyReg);
648 assert(getRegColor(CopyReg) != CopyReg);
651 assert(getRegColor(CopyReg) == CopyReg);
654 if (!InsertedSrcCopyMap.count(std::make_pair(PredBB, PHIColor)))
655 InsertedSrcCopyMap[std::make_pair(PredBB, PHIColor)] = CopyInstr;
658 SrcMO.setReg(CopyReg);
660 // If SrcReg is not live beyond the PHI, trim its interval so that it is no
661 // longer live-in to MBB. Note that SrcReg may appear in other PHIs that are
662 // processed later, but this is still correct to do at this point because we
663 // never rely on LiveIntervals being correct while inserting copies.
664 // FIXME: Should this just count uses at PHIs like the normal PHIElimination
666 LiveInterval& SrcLI = LI->getInterval(SrcReg);
667 SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
668 SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
669 SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
670 if (SrcLI.liveAt(MBBStartIndex) && SrcLI.expiredAt(NextInstrIndex))
671 SrcLI.removeRange(MBBStartIndex, PHIIndex, true);
674 unsigned DestReg = PHI->getOperand(0).getReg();
675 unsigned DestColor = getRegColor(DestReg);
677 if (PHIColor && DestColor == PHIColor) {
678 LiveInterval& DestLI = LI->getInterval(DestReg);
680 // Set the phi-def flag for the VN at this PHI.
681 SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
682 VNInfo* DestVNI = DestLI.getVNInfoAt(PHIIndex.getDefIndex());
684 DestVNI->setIsPHIDef(true);
686 // Prior to PHI elimination, the live ranges of PHIs begin at their defining
687 // instruction. After PHI elimination, PHI instructions are replaced by VNs
688 // with the phi-def flag set, and the live ranges of these VNs start at the
689 // beginning of the basic block.
690 SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
691 DestVNI->def = MBBStartIndex;
692 DestLI.addRange(LiveRange(MBBStartIndex,
693 PHIIndex.getDefIndex(),
698 const TargetRegisterClass* RC = MRI->getRegClass(DestReg);
699 unsigned CopyReg = MRI->createVirtualRegister(RC);
701 MachineInstr* CopyInstr = BuildMI(*MBB,
702 MBB->SkipPHIsAndLabels(MBB->begin()),
704 TII->get(TargetOpcode::COPY),
705 DestReg).addReg(CopyReg);
706 LI->InsertMachineInstrInMaps(CopyInstr);
707 PHI->getOperand(0).setReg(CopyReg);
709 // Add the region from the beginning of MBB to the copy instruction to
710 // CopyReg's live interval, and give the VNInfo the phidef flag.
711 LiveInterval& CopyLI = LI->getOrCreateInterval(CopyReg);
712 SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
713 SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
714 VNInfo* CopyVNI = CopyLI.getNextValue(MBBStartIndex,
716 LI->getVNInfoAllocator());
717 CopyVNI->setIsPHIDef(true);
718 CopyLI.addRange(LiveRange(MBBStartIndex,
719 DestCopyIndex.getDefIndex(),
722 // Adjust DestReg's live interval to adjust for its new definition at
724 LiveInterval& DestLI = LI->getOrCreateInterval(DestReg);
725 SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
726 DestLI.removeRange(PHIIndex.getDefIndex(), DestCopyIndex.getDefIndex());
728 VNInfo* DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex());
730 DestVNI->def = DestCopyIndex.getDefIndex();
732 InsertedDestCopies[CopyReg] = CopyInstr;
735 void StrongPHIElimination::MergeLIsAndRename(unsigned Reg, unsigned NewReg) {
739 LiveInterval& OldLI = LI->getInterval(Reg);
740 LiveInterval& NewLI = LI->getInterval(NewReg);
742 // Merge the live ranges of the two registers.
743 DenseMap<VNInfo*, VNInfo*> VNMap;
744 for (LiveInterval::iterator LRI = OldLI.begin(), LRE = OldLI.end();
746 LiveRange OldLR = *LRI;
747 VNInfo* OldVN = OldLR.valno;
749 VNInfo*& NewVN = VNMap[OldVN];
751 NewVN = NewLI.createValueCopy(OldVN, LI->getVNInfoAllocator());
752 VNMap[OldVN] = NewVN;
755 LiveRange LR(OldLR.start, OldLR.end, NewVN);
759 // Remove the LiveInterval for the register being renamed and replace all
760 // of its defs and uses with the new register.
761 LI->removeInterval(Reg);
762 MRI->replaceRegWith(Reg, NewReg);