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 && "PHI destination copy's live interval should be a single live "
288 "range from the beginning of the BB to the copy instruction.");
289 LiveRange* DestLR = DestLI.begin();
290 VNInfo* NewVNI = NewLI.getVNInfoAt(DestLR->start);
292 NewVNI = NewLI.createValueCopy(DestLR->valno, LI->getVNInfoAllocator());
293 MachineInstr* CopyInstr = I->second;
294 CopyInstr->getOperand(1).setIsKill(true);
297 LiveRange NewLR(DestLR->start, DestLR->end, NewVNI);
298 NewLI.addRange(NewLR);
300 LI->removeInterval(DestReg);
301 MRI->replaceRegWith(DestReg, NewReg);
304 // Adjust the live intervals of all PHI source registers to handle the case
305 // where the PHIs in successor blocks were the only later uses of the source
307 for (SrcCopySet::iterator I = InsertedSrcCopySet.begin(),
308 E = InsertedSrcCopySet.end(); I != E; ++I) {
309 MachineBasicBlock* MBB = I->first;
310 unsigned SrcReg = I->second;
311 if (unsigned RenamedRegister = RegRenamingMap[getRegColor(SrcReg)])
312 SrcReg = RenamedRegister;
314 LiveInterval& SrcLI = LI->getInterval(SrcReg);
316 bool isLiveOut = false;
317 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
318 SE = MBB->succ_end(); SI != SE; ++SI) {
319 if (SrcLI.liveAt(LI->getMBBStartIdx(*SI))) {
328 MachineOperand* LastUse = findLastUse(MBB, SrcReg);
330 SlotIndex LastUseIndex = LI->getInstructionIndex(LastUse->getParent());
331 SrcLI.removeRange(LastUseIndex.getDefIndex(), LI->getMBBEndIdx(MBB));
332 LastUse->setIsKill(true);
339 InsertedSrcCopySet.clear();
340 InsertedSrcCopyMap.clear();
341 InsertedDestCopies.clear();
346 void StrongPHIElimination::addReg(unsigned Reg) {
347 if (RegNodeMap.count(Reg))
349 RegNodeMap[Reg] = new (Allocator) Node(Reg);
352 StrongPHIElimination::Node*
353 StrongPHIElimination::Node::getLeader() {
354 Node* parentPointer = parent.getPointer();
355 if (parentPointer == this)
357 Node* newParent = parentPointer->getLeader();
358 parent.setPointer(newParent);
362 unsigned StrongPHIElimination::getRegColor(unsigned Reg) {
363 DenseMap<unsigned, Node*>::iterator RI = RegNodeMap.find(Reg);
364 if (RI == RegNodeMap.end())
366 Node* Node = RI->second;
367 if (Node->parent.getInt() & Node::kRegisterIsolatedFlag)
369 return Node->getLeader()->value;
372 void StrongPHIElimination::unionRegs(unsigned Reg1, unsigned Reg2) {
373 Node* Node1 = RegNodeMap[Reg1]->getLeader();
374 Node* Node2 = RegNodeMap[Reg2]->getLeader();
376 if (Node1->rank > Node2->rank) {
377 Node2->parent.setPointer(Node1->getLeader());
378 } else if (Node1->rank < Node2->rank) {
379 Node1->parent.setPointer(Node2->getLeader());
380 } else if (Node1 != Node2) {
381 Node2->parent.setPointer(Node1->getLeader());
386 void StrongPHIElimination::isolateReg(unsigned Reg) {
387 Node* Node = RegNodeMap[Reg];
388 Node->parent.setInt(Node->parent.getInt() | Node::kRegisterIsolatedFlag);
391 unsigned StrongPHIElimination::getPHIColor(MachineInstr* PHI) {
392 assert(PHI->isPHI());
394 unsigned DestReg = PHI->getOperand(0).getReg();
395 Node* DestNode = RegNodeMap[DestReg];
396 if (DestNode->parent.getInt() & Node::kPHIIsolatedFlag)
399 for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
400 unsigned SrcColor = getRegColor(PHI->getOperand(i).getReg());
407 void StrongPHIElimination::isolatePHI(MachineInstr* PHI) {
408 assert(PHI->isPHI());
409 Node* Node = RegNodeMap[PHI->getOperand(0).getReg()];
410 Node->parent.setInt(Node->parent.getInt() | Node::kPHIIsolatedFlag);
413 void StrongPHIElimination::PartitionRegisters(MachineFunction& MF) {
414 for (MachineFunction::iterator I = MF.begin(), E = MF.end();
416 for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
417 BBI != BBE && BBI->isPHI(); ++BBI) {
418 unsigned DestReg = BBI->getOperand(0).getReg();
421 for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
422 unsigned SrcReg = BBI->getOperand(i).getReg();
424 unionRegs(DestReg, SrcReg);
430 /// SplitInterferencesForBasicBlock - traverses a basic block, splitting any
431 /// interferences found between registers in the same congruence class. It
432 /// takes two DenseMaps as arguments that it also updates:
434 /// 1) CurrentDominatingParent, which maps a color to the register in that
435 /// congruence class whose definition was most recently seen.
437 /// 2) ImmediateDominatingParent, which maps a register to the register in the
438 /// same congruence class that most immediately dominates it.
440 /// This function assumes that it is being called in a depth-first traversal
441 /// of the dominator tree.
443 /// The algorithm used here is a generalization of the dominance-based SSA test
444 /// for two variables. If there are variables a_1, ..., a_n such that
446 /// def(a_1) dom ... dom def(a_n),
448 /// then we can test for an interference between any two a_i by only using O(n)
449 /// interference tests between pairs of variables. If i < j and a_i and a_j
450 /// interfere, then a_i is alive at def(a_j), so it is also alive at def(a_i+1).
451 /// Thus, in order to test for an interference involving a_i, we need only check
452 /// for a potential interference with a_i+1.
454 /// This method can be generalized to arbitrary sets of variables by performing
455 /// a depth-first traversal of the dominator tree. As we traverse down a branch
456 /// of the dominator tree, we keep track of the current dominating variable and
457 /// only perform an interference test with that variable. However, when we go to
458 /// another branch of the dominator tree, the definition of the current dominating
459 /// variable may no longer dominate the current block. In order to correct this,
460 /// we need to use a stack of past choices of the current dominating variable
461 /// and pop from this stack until we find a variable whose definition actually
462 /// dominates the current block.
464 /// There will be one push on this stack for each variable that has become the
465 /// current dominating variable, so instead of using an explicit stack we can
466 /// simply associate the previous choice for a current dominating variable with
467 /// the new choice. This works better in our implementation, where we test for
468 /// interference in multiple distinct sets at once.
470 StrongPHIElimination::SplitInterferencesForBasicBlock(
471 MachineBasicBlock& MBB,
472 DenseMap<unsigned, unsigned>& CurrentDominatingParent,
473 DenseMap<unsigned, unsigned>& ImmediateDominatingParent) {
474 for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
476 for (MachineInstr::const_mop_iterator I = BBI->operands_begin(),
477 E = BBI->operands_end(); I != E; ++I) {
478 const MachineOperand& MO = *I;
480 // FIXME: This would be faster if it were possible to bail out of checking
481 // an instruction's operands after the explicit defs, but this is incorrect
482 // for variadic instructions, which may appear before register allocation
484 if (!MO.isReg() || !MO.isDef())
487 unsigned DestReg = MO.getReg();
488 if (!DestReg || !TargetRegisterInfo::isVirtualRegister(DestReg))
491 // If the virtual register being defined is not used in any PHI or has
492 // already been isolated, then there are no more interferences to check.
493 unsigned DestColor = getRegColor(DestReg);
497 // The input to this pass sometimes is not in SSA form in every basic
498 // block, as some virtual registers have redefinitions. We could eliminate
499 // this by fixing the passes that generate the non-SSA code, or we could
500 // handle it here by tracking defining machine instructions rather than
501 // virtual registers. For now, we just handle the situation conservatively
502 // in a way that will possibly lead to false interferences.
503 unsigned NewParent = CurrentDominatingParent[DestColor];
504 if (NewParent == DestReg)
507 // Pop registers from the stack represented by ImmediateDominatingParent
508 // until we find a parent that dominates the current instruction.
509 while (NewParent && (!DT->dominates(MRI->getVRegDef(NewParent), BBI)
510 || !getRegColor(NewParent)))
511 NewParent = ImmediateDominatingParent[NewParent];
513 // If NewParent is nonzero, then its definition dominates the current
514 // instruction, so it is only necessary to check for the liveness of
515 // NewParent in order to check for an interference.
517 && LI->getInterval(NewParent).liveAt(LI->getInstructionIndex(BBI))) {
518 // If there is an interference, always isolate the new register. This
519 // could be improved by using a heuristic that decides which of the two
520 // registers to isolate.
522 CurrentDominatingParent[DestColor] = NewParent;
524 // If there is no interference, update ImmediateDominatingParent and set
525 // the CurrentDominatingParent for this color to the current register.
526 ImmediateDominatingParent[DestReg] = NewParent;
527 CurrentDominatingParent[DestColor] = DestReg;
532 // We now walk the PHIs in successor blocks and check for interferences. This
533 // is necesary because the use of a PHI's operands are logically contained in
534 // the predecessor block. The def of a PHI's destination register is processed
535 // along with the other defs in a basic block.
537 // The map CurrentPHIForColor maps a color to a pair of a MachineInstr* and a
538 // virtual register, which is the operand of that PHI corresponding to the
539 // current basic block.
540 // FIXME: This should use a container that doesn't always perform heap
542 DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > CurrentPHIForColor;
544 for (MachineBasicBlock::succ_iterator SI = MBB.succ_begin(),
545 SE = MBB.succ_end(); SI != SE; ++SI) {
546 for (MachineBasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end();
547 BBI != BBE && BBI->isPHI(); ++BBI) {
548 MachineInstr* PHI = BBI;
550 // If a PHI is already isolated, either by being isolated directly or
551 // having all of its operands isolated, ignore it.
552 unsigned Color = getPHIColor(PHI);
556 // Find the index of the PHI operand that corresponds to this basic block.
558 for (PredIndex = 1; PredIndex < PHI->getNumOperands(); PredIndex += 2) {
559 if (PHI->getOperand(PredIndex + 1).getMBB() == &MBB)
562 assert(PredIndex < PHI->getNumOperands());
563 unsigned PredOperandReg = PHI->getOperand(PredIndex).getReg();
565 // Pop registers from the stack represented by ImmediateDominatingParent
566 // until we find a parent that dominates the current instruction.
567 unsigned NewParent = CurrentDominatingParent[Color];
569 && (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB)
570 || !getRegColor(NewParent)))
571 NewParent = ImmediateDominatingParent[NewParent];
572 CurrentDominatingParent[Color] = NewParent;
574 // If there is an interference with a register, always isolate the
575 // register rather than the PHI. It is also possible to isolate the
576 // PHI, but that introduces copies for all of the registers involved
578 if (NewParent && LI->isLiveOutOfMBB(LI->getInterval(NewParent), &MBB)
579 && NewParent != PredOperandReg)
580 isolateReg(NewParent);
582 std::pair<MachineInstr*, unsigned> CurrentPHI = CurrentPHIForColor[Color];
584 // If two PHIs have the same operand from every shared predecessor, then
585 // they don't actually interfere. Otherwise, isolate the current PHI. This
586 // could possibly be improved, e.g. we could isolate the PHI with the
588 if (CurrentPHI.first && CurrentPHI.second != PredOperandReg)
591 CurrentPHIForColor[Color] = std::make_pair(PHI, PredOperandReg);
596 void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
597 MachineBasicBlock* MBB) {
598 assert(PHI->isPHI());
599 unsigned PHIColor = getPHIColor(PHI);
601 for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
602 MachineOperand& SrcMO = PHI->getOperand(i);
604 // If a source is defined by an implicit def, there is no need to insert a
605 // copy in the predecessor.
609 unsigned SrcReg = SrcMO.getReg();
610 assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
611 "Machine PHI Operands must all be virtual registers!");
613 MachineBasicBlock* PredBB = PHI->getOperand(i + 1).getMBB();
614 unsigned SrcColor = getRegColor(SrcReg);
616 // If neither the PHI nor the operand were isolated, then we only need to
617 // set the phi-kill flag on the VNInfo at this PHI.
618 if (PHIColor && SrcColor == PHIColor) {
619 LiveInterval& SrcInterval = LI->getInterval(SrcReg);
620 SlotIndex PredIndex = LI->getMBBEndIdx(PredBB);
621 VNInfo* SrcVNI = SrcInterval.getVNInfoAt(PredIndex.getPrevIndex());
623 SrcVNI->setHasPHIKill(true);
627 unsigned CopyReg = 0;
629 SrcCopyMap::const_iterator I
630 = InsertedSrcCopyMap.find(std::make_pair(PredBB, PHIColor));
632 = I != InsertedSrcCopyMap.end() ? I->second->getOperand(0).getReg() : 0;
636 const TargetRegisterClass* RC = MRI->getRegClass(SrcReg);
637 CopyReg = MRI->createVirtualRegister(RC);
639 MachineBasicBlock::iterator
640 CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
641 unsigned SrcSubReg = SrcMO.getSubReg();
642 MachineInstr* CopyInstr = BuildMI(*PredBB,
645 TII->get(TargetOpcode::COPY),
646 CopyReg).addReg(SrcReg, 0, SrcSubReg);
647 LI->InsertMachineInstrInMaps(CopyInstr);
649 // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
650 // the newly added range.
651 LI->addLiveRangeToEndOfBlock(CopyReg, CopyInstr);
652 InsertedSrcCopySet.insert(std::make_pair(PredBB, SrcReg));
656 unionRegs(PHIColor, CopyReg);
657 assert(getRegColor(CopyReg) != CopyReg);
660 assert(getRegColor(CopyReg) == CopyReg);
663 if (!InsertedSrcCopyMap.count(std::make_pair(PredBB, PHIColor)))
664 InsertedSrcCopyMap[std::make_pair(PredBB, PHIColor)] = CopyInstr;
667 SrcMO.setReg(CopyReg);
669 // If SrcReg is not live beyond the PHI, trim its interval so that it is no
670 // longer live-in to MBB. Note that SrcReg may appear in other PHIs that are
671 // processed later, but this is still correct to do at this point because we
672 // never rely on LiveIntervals being correct while inserting copies.
673 // FIXME: Should this just count uses at PHIs like the normal PHIElimination
675 LiveInterval& SrcLI = LI->getInterval(SrcReg);
676 SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
677 SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
678 SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
679 if (SrcLI.liveAt(MBBStartIndex) && SrcLI.expiredAt(NextInstrIndex))
680 SrcLI.removeRange(MBBStartIndex, PHIIndex, true);
683 unsigned DestReg = PHI->getOperand(0).getReg();
684 unsigned DestColor = getRegColor(DestReg);
686 if (PHIColor && DestColor == PHIColor) {
687 LiveInterval& DestLI = LI->getInterval(DestReg);
689 // Set the phi-def flag for the VN at this PHI.
690 SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
691 VNInfo* DestVNI = DestLI.getVNInfoAt(PHIIndex.getDefIndex());
693 DestVNI->setIsPHIDef(true);
695 // Prior to PHI elimination, the live ranges of PHIs begin at their defining
696 // instruction. After PHI elimination, PHI instructions are replaced by VNs
697 // with the phi-def flag set, and the live ranges of these VNs start at the
698 // beginning of the basic block.
699 SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
700 DestVNI->def = MBBStartIndex;
701 DestLI.addRange(LiveRange(MBBStartIndex,
702 PHIIndex.getDefIndex(),
707 const TargetRegisterClass* RC = MRI->getRegClass(DestReg);
708 unsigned CopyReg = MRI->createVirtualRegister(RC);
710 MachineInstr* CopyInstr = BuildMI(*MBB,
711 MBB->SkipPHIsAndLabels(MBB->begin()),
713 TII->get(TargetOpcode::COPY),
714 DestReg).addReg(CopyReg);
715 LI->InsertMachineInstrInMaps(CopyInstr);
716 PHI->getOperand(0).setReg(CopyReg);
718 // Add the region from the beginning of MBB to the copy instruction to
719 // CopyReg's live interval, and give the VNInfo the phidef flag.
720 LiveInterval& CopyLI = LI->getOrCreateInterval(CopyReg);
721 SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
722 SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
723 VNInfo* CopyVNI = CopyLI.getNextValue(MBBStartIndex,
725 LI->getVNInfoAllocator());
726 CopyVNI->setIsPHIDef(true);
727 CopyLI.addRange(LiveRange(MBBStartIndex,
728 DestCopyIndex.getDefIndex(),
731 // Adjust DestReg's live interval to adjust for its new definition at
733 LiveInterval& DestLI = LI->getOrCreateInterval(DestReg);
734 SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
735 DestLI.removeRange(PHIIndex.getDefIndex(), DestCopyIndex.getDefIndex());
737 VNInfo* DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex());
739 DestVNI->def = DestCopyIndex.getDefIndex();
741 InsertedDestCopies[CopyReg] = CopyInstr;
744 void StrongPHIElimination::MergeLIsAndRename(unsigned Reg, unsigned NewReg) {
748 LiveInterval& OldLI = LI->getInterval(Reg);
749 LiveInterval& NewLI = LI->getInterval(NewReg);
751 // Merge the live ranges of the two registers.
752 DenseMap<VNInfo*, VNInfo*> VNMap;
753 for (LiveInterval::iterator LRI = OldLI.begin(), LRE = OldLI.end();
755 LiveRange OldLR = *LRI;
756 VNInfo* OldVN = OldLR.valno;
758 VNInfo*& NewVN = VNMap[OldVN];
760 NewVN = NewLI.createValueCopy(OldVN, LI->getVNInfoAllocator());
761 VNMap[OldVN] = NewVN;
764 LiveRange LR(OldLR.start, OldLR.end, NewVN);
768 // Remove the LiveInterval for the register being renamed and replace all
769 // of its defs and uses with the new register.
770 LI->removeInterval(Reg);
771 MRI->replaceRegWith(Reg, NewReg);