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 /// Traverses a basic block, splitting any interferences found between
111 /// registers in the same congruence class. It takes two DenseMaps as
112 /// arguments that it also updates: CurrentDominatingParent, which maps
113 /// a color to the register in that congruence class whose definition was
114 /// most recently seen, and ImmediateDominatingParent, which maps a register
115 /// to the register in the same congruence class that most immediately
118 /// This function assumes that it is being called in a depth-first traversal
119 /// of the dominator tree.
120 void SplitInterferencesForBasicBlock(
122 DenseMap<unsigned, unsigned> &CurrentDominatingParent,
123 DenseMap<unsigned, unsigned> &ImmediateDominatingParent);
125 // Lowers a PHI instruction, inserting copies of the source and destination
126 // registers as necessary.
127 void InsertCopiesForPHI(MachineInstr*, MachineBasicBlock*);
129 // Merges the live interval of Reg into NewReg and renames Reg to NewReg
130 // everywhere that Reg appears. Requires Reg and NewReg to have non-
131 // overlapping lifetimes.
132 void MergeLIsAndRename(unsigned Reg, unsigned NewReg);
134 MachineRegisterInfo *MRI;
135 const TargetInstrInfo *TII;
136 MachineDominatorTree *DT;
139 BumpPtrAllocator Allocator;
141 DenseMap<unsigned, Node*> RegNodeMap;
143 // Maps a basic block to a list of its defs of registers that appear as PHI
145 DenseMap<MachineBasicBlock*, std::vector<MachineInstr*> > PHISrcDefs;
147 // Maps a color to a pair of a MachineInstr* and a virtual register, which
148 // is the operand of that PHI corresponding to the current basic block.
149 DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > CurrentPHIForColor;
151 // FIXME: Can these two data structures be combined? Would a std::multimap
154 // Stores pairs of predecessor basic blocks and the source registers of
155 // inserted copy instructions.
156 typedef DenseSet<std::pair<MachineBasicBlock*, unsigned> > SrcCopySet;
157 SrcCopySet InsertedSrcCopySet;
159 // Maps pairs of predecessor basic blocks and colors to their defining copy
161 typedef DenseMap<std::pair<MachineBasicBlock*, unsigned>, MachineInstr*>
163 SrcCopyMap InsertedSrcCopyMap;
165 // Maps inserted destination copy registers to their defining copy
167 typedef DenseMap<unsigned, MachineInstr*> DestCopyMap;
168 DestCopyMap InsertedDestCopies;
171 struct MIIndexCompare {
172 MIIndexCompare(LiveIntervals *LiveIntervals) : LI(LiveIntervals) { }
174 bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const {
175 return LI->getInstructionIndex(LHS) < LI->getInstructionIndex(RHS);
182 char StrongPHIElimination::ID = 0;
183 INITIALIZE_PASS_BEGIN(StrongPHIElimination, "strong-phi-node-elimination",
184 "Eliminate PHI nodes for register allocation, intelligently", false, false)
185 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
186 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
187 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
188 INITIALIZE_PASS_END(StrongPHIElimination, "strong-phi-node-elimination",
189 "Eliminate PHI nodes for register allocation, intelligently", false, false)
191 char &llvm::StrongPHIEliminationID = StrongPHIElimination::ID;
193 void StrongPHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
194 AU.setPreservesCFG();
195 AU.addRequired<MachineDominatorTree>();
196 AU.addRequired<SlotIndexes>();
197 AU.addPreserved<SlotIndexes>();
198 AU.addRequired<LiveIntervals>();
199 AU.addPreserved<LiveIntervals>();
200 MachineFunctionPass::getAnalysisUsage(AU);
203 static MachineOperand *findLastUse(MachineBasicBlock *MBB, unsigned Reg) {
204 // FIXME: This only needs to check from the first terminator, as only the
205 // first terminator can use a virtual register.
206 for (MachineBasicBlock::reverse_iterator RI = MBB->rbegin(); ; ++RI) {
207 assert (RI != MBB->rend());
208 MachineInstr *MI = &*RI;
210 for (MachineInstr::mop_iterator OI = MI->operands_begin(),
211 OE = MI->operands_end(); OI != OE; ++OI) {
212 MachineOperand &MO = *OI;
213 if (MO.isReg() && MO.isUse() && MO.getReg() == Reg)
220 bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) {
221 MRI = &MF.getRegInfo();
222 TII = MF.getTarget().getInstrInfo();
223 DT = &getAnalysis<MachineDominatorTree>();
224 LI = &getAnalysis<LiveIntervals>();
226 for (MachineFunction::iterator I = MF.begin(), E = MF.end();
228 for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
229 BBI != BBE && BBI->isPHI(); ++BBI) {
230 unsigned DestReg = BBI->getOperand(0).getReg();
232 PHISrcDefs[I].push_back(BBI);
234 for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
235 MachineOperand &SrcMO = BBI->getOperand(i);
236 unsigned SrcReg = SrcMO.getReg();
238 unionRegs(DestReg, SrcReg);
240 MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
242 PHISrcDefs[DefMI->getParent()].push_back(DefMI);
247 // Perform a depth-first traversal of the dominator tree, splitting
248 // interferences amongst PHI-congruence classes.
249 DenseMap<unsigned, unsigned> CurrentDominatingParent;
250 DenseMap<unsigned, unsigned> ImmediateDominatingParent;
251 for (df_iterator<MachineDomTreeNode*> DI = df_begin(DT->getRootNode()),
252 DE = df_end(DT->getRootNode()); DI != DE; ++DI) {
253 SplitInterferencesForBasicBlock(*DI->getBlock(),
254 CurrentDominatingParent,
255 ImmediateDominatingParent);
258 // Insert copies for all PHI source and destination registers.
259 for (MachineFunction::iterator I = MF.begin(), E = MF.end();
261 for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
262 BBI != BBE && BBI->isPHI(); ++BBI) {
263 InsertCopiesForPHI(BBI, I);
267 // FIXME: Preserve the equivalence classes during copy insertion and use
268 // the preversed equivalence classes instead of recomputing them.
270 for (MachineFunction::iterator I = MF.begin(), E = MF.end();
272 for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
273 BBI != BBE && BBI->isPHI(); ++BBI) {
274 unsigned DestReg = BBI->getOperand(0).getReg();
277 for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
278 unsigned SrcReg = BBI->getOperand(i).getReg();
280 unionRegs(DestReg, SrcReg);
285 DenseMap<unsigned, unsigned> RegRenamingMap;
286 bool Changed = false;
287 for (MachineFunction::iterator I = MF.begin(), E = MF.end();
289 MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
290 while (BBI != BBE && BBI->isPHI()) {
291 MachineInstr *PHI = BBI;
293 assert(PHI->getNumOperands() > 0);
295 unsigned SrcReg = PHI->getOperand(1).getReg();
296 unsigned SrcColor = getRegColor(SrcReg);
297 unsigned NewReg = RegRenamingMap[SrcColor];
300 RegRenamingMap[SrcColor] = SrcReg;
302 MergeLIsAndRename(SrcReg, NewReg);
304 unsigned DestReg = PHI->getOperand(0).getReg();
305 if (!InsertedDestCopies.count(DestReg))
306 MergeLIsAndRename(DestReg, NewReg);
308 for (unsigned i = 3; i < PHI->getNumOperands(); i += 2) {
309 unsigned SrcReg = PHI->getOperand(i).getReg();
310 MergeLIsAndRename(SrcReg, NewReg);
314 LI->RemoveMachineInstrFromMaps(PHI);
315 PHI->eraseFromParent();
320 // Due to the insertion of copies to split live ranges, the live intervals are
321 // guaranteed to not overlap, except in one case: an original PHI source and a
322 // PHI destination copy. In this case, they have the same value and thus don't
323 // truly intersect, so we merge them into the value live at that point.
324 // FIXME: Is there some better way we can handle this?
325 for (DestCopyMap::iterator I = InsertedDestCopies.begin(),
326 E = InsertedDestCopies.end(); I != E; ++I) {
327 unsigned DestReg = I->first;
328 unsigned DestColor = getRegColor(DestReg);
329 unsigned NewReg = RegRenamingMap[DestColor];
331 LiveInterval &DestLI = LI->getInterval(DestReg);
332 LiveInterval &NewLI = LI->getInterval(NewReg);
334 assert(DestLI.ranges.size() == 1
335 && "PHI destination copy's live interval should be a single live "
336 "range from the beginning of the BB to the copy instruction.");
337 LiveRange *DestLR = DestLI.begin();
338 VNInfo *NewVNI = NewLI.getVNInfoAt(DestLR->start);
340 NewVNI = NewLI.createValueCopy(DestLR->valno, LI->getVNInfoAllocator());
341 MachineInstr *CopyInstr = I->second;
342 CopyInstr->getOperand(1).setIsKill(true);
345 LiveRange NewLR(DestLR->start, DestLR->end, NewVNI);
346 NewLI.addRange(NewLR);
348 LI->removeInterval(DestReg);
349 MRI->replaceRegWith(DestReg, NewReg);
352 // Adjust the live intervals of all PHI source registers to handle the case
353 // where the PHIs in successor blocks were the only later uses of the source
355 for (SrcCopySet::iterator I = InsertedSrcCopySet.begin(),
356 E = InsertedSrcCopySet.end(); I != E; ++I) {
357 MachineBasicBlock *MBB = I->first;
358 unsigned SrcReg = I->second;
359 if (unsigned RenamedRegister = RegRenamingMap[getRegColor(SrcReg)])
360 SrcReg = RenamedRegister;
362 LiveInterval &SrcLI = LI->getInterval(SrcReg);
364 bool isLiveOut = false;
365 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
366 SE = MBB->succ_end(); SI != SE; ++SI) {
367 if (SrcLI.liveAt(LI->getMBBStartIdx(*SI))) {
376 MachineOperand *LastUse = findLastUse(MBB, SrcReg);
378 SlotIndex LastUseIndex = LI->getInstructionIndex(LastUse->getParent());
379 SrcLI.removeRange(LastUseIndex.getDefIndex(), LI->getMBBEndIdx(MBB));
380 LastUse->setIsKill(true);
388 InsertedSrcCopySet.clear();
389 InsertedSrcCopyMap.clear();
390 InsertedDestCopies.clear();
395 void StrongPHIElimination::addReg(unsigned Reg) {
396 if (RegNodeMap.count(Reg))
398 RegNodeMap[Reg] = new (Allocator) Node(Reg);
401 StrongPHIElimination::Node*
402 StrongPHIElimination::Node::getLeader() {
404 Node *Parent = parent.getPointer();
405 Node *Grandparent = Parent->parent.getPointer();
407 while (Parent != Grandparent) {
408 N->parent.setPointer(Grandparent);
410 Parent = Parent->parent.getPointer();
411 Grandparent = Parent->parent.getPointer();
417 unsigned StrongPHIElimination::getRegColor(unsigned Reg) {
418 DenseMap<unsigned, Node*>::iterator RI = RegNodeMap.find(Reg);
419 if (RI == RegNodeMap.end())
421 Node *Node = RI->second;
422 if (Node->parent.getInt() & Node::kRegisterIsolatedFlag)
424 return Node->getLeader()->value;
427 void StrongPHIElimination::unionRegs(unsigned Reg1, unsigned Reg2) {
428 Node *Node1 = RegNodeMap[Reg1]->getLeader();
429 Node *Node2 = RegNodeMap[Reg2]->getLeader();
431 if (Node1->rank > Node2->rank) {
432 Node2->parent.setPointer(Node1->getLeader());
433 } else if (Node1->rank < Node2->rank) {
434 Node1->parent.setPointer(Node2->getLeader());
435 } else if (Node1 != Node2) {
436 Node2->parent.setPointer(Node1->getLeader());
441 void StrongPHIElimination::isolateReg(unsigned Reg) {
442 Node *Node = RegNodeMap[Reg];
443 Node->parent.setInt(Node->parent.getInt() | Node::kRegisterIsolatedFlag);
446 unsigned StrongPHIElimination::getPHIColor(MachineInstr *PHI) {
447 assert(PHI->isPHI());
449 unsigned DestReg = PHI->getOperand(0).getReg();
450 Node *DestNode = RegNodeMap[DestReg];
451 if (DestNode->parent.getInt() & Node::kPHIIsolatedFlag)
454 for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
455 unsigned SrcColor = getRegColor(PHI->getOperand(i).getReg());
462 void StrongPHIElimination::isolatePHI(MachineInstr *PHI) {
463 assert(PHI->isPHI());
464 Node *Node = RegNodeMap[PHI->getOperand(0).getReg()];
465 Node->parent.setInt(Node->parent.getInt() | Node::kPHIIsolatedFlag);
468 /// SplitInterferencesForBasicBlock - traverses a basic block, splitting any
469 /// interferences found between registers in the same congruence class. It
470 /// takes two DenseMaps as arguments that it also updates:
472 /// 1) CurrentDominatingParent, which maps a color to the register in that
473 /// congruence class whose definition was most recently seen.
475 /// 2) ImmediateDominatingParent, which maps a register to the register in the
476 /// same congruence class that most immediately dominates it.
478 /// This function assumes that it is being called in a depth-first traversal
479 /// of the dominator tree.
481 /// The algorithm used here is a generalization of the dominance-based SSA test
482 /// for two variables. If there are variables a_1, ..., a_n such that
484 /// def(a_1) dom ... dom def(a_n),
486 /// then we can test for an interference between any two a_i by only using O(n)
487 /// interference tests between pairs of variables. If i < j and a_i and a_j
488 /// interfere, then a_i is alive at def(a_j), so it is also alive at def(a_i+1).
489 /// Thus, in order to test for an interference involving a_i, we need only check
490 /// for a potential interference with a_i+1.
492 /// This method can be generalized to arbitrary sets of variables by performing
493 /// a depth-first traversal of the dominator tree. As we traverse down a branch
494 /// of the dominator tree, we keep track of the current dominating variable and
495 /// only perform an interference test with that variable. However, when we go to
496 /// another branch of the dominator tree, the definition of the current dominating
497 /// variable may no longer dominate the current block. In order to correct this,
498 /// we need to use a stack of past choices of the current dominating variable
499 /// and pop from this stack until we find a variable whose definition actually
500 /// dominates the current block.
502 /// There will be one push on this stack for each variable that has become the
503 /// current dominating variable, so instead of using an explicit stack we can
504 /// simply associate the previous choice for a current dominating variable with
505 /// the new choice. This works better in our implementation, where we test for
506 /// interference in multiple distinct sets at once.
508 StrongPHIElimination::SplitInterferencesForBasicBlock(
509 MachineBasicBlock &MBB,
510 DenseMap<unsigned, unsigned> &CurrentDominatingParent,
511 DenseMap<unsigned, unsigned> &ImmediateDominatingParent) {
512 // Sort defs by their order in the original basic block, as the code below
513 // assumes that it is processing definitions in dominance order.
514 std::vector<MachineInstr*> &DefInstrs = PHISrcDefs[&MBB];
515 std::sort(DefInstrs.begin(), DefInstrs.end(), MIIndexCompare(LI));
517 for (std::vector<MachineInstr*>::const_iterator BBI = DefInstrs.begin(),
518 BBE = DefInstrs.end(); BBI != BBE; ++BBI) {
519 for (MachineInstr::const_mop_iterator I = (*BBI)->operands_begin(),
520 E = (*BBI)->operands_end(); I != E; ++I) {
521 const MachineOperand &MO = *I;
523 // FIXME: This would be faster if it were possible to bail out of checking
524 // an instruction's operands after the explicit defs, but this is incorrect
525 // for variadic instructions, which may appear before register allocation
527 if (!MO.isReg() || !MO.isDef())
530 unsigned DestReg = MO.getReg();
531 if (!DestReg || !TargetRegisterInfo::isVirtualRegister(DestReg))
534 // If the virtual register being defined is not used in any PHI or has
535 // already been isolated, then there are no more interferences to check.
536 unsigned DestColor = getRegColor(DestReg);
540 // The input to this pass sometimes is not in SSA form in every basic
541 // block, as some virtual registers have redefinitions. We could eliminate
542 // this by fixing the passes that generate the non-SSA code, or we could
543 // handle it here by tracking defining machine instructions rather than
544 // virtual registers. For now, we just handle the situation conservatively
545 // in a way that will possibly lead to false interferences.
546 unsigned NewParent = CurrentDominatingParent[DestColor];
547 if (NewParent == DestReg)
550 // Pop registers from the stack represented by ImmediateDominatingParent
551 // until we find a parent that dominates the current instruction.
552 while (NewParent && (!DT->dominates(MRI->getVRegDef(NewParent), *BBI)
553 || !getRegColor(NewParent)))
554 NewParent = ImmediateDominatingParent[NewParent];
556 // If NewParent is nonzero, then its definition dominates the current
557 // instruction, so it is only necessary to check for the liveness of
558 // NewParent in order to check for an interference.
560 && LI->getInterval(NewParent).liveAt(LI->getInstructionIndex(*BBI))) {
561 // If there is an interference, always isolate the new register. This
562 // could be improved by using a heuristic that decides which of the two
563 // registers to isolate.
565 CurrentDominatingParent[DestColor] = NewParent;
567 // If there is no interference, update ImmediateDominatingParent and set
568 // the CurrentDominatingParent for this color to the current register.
569 ImmediateDominatingParent[DestReg] = NewParent;
570 CurrentDominatingParent[DestColor] = DestReg;
575 // We now walk the PHIs in successor blocks and check for interferences. This
576 // is necesary because the use of a PHI's operands are logically contained in
577 // the predecessor block. The def of a PHI's destination register is processed
578 // along with the other defs in a basic block.
580 CurrentPHIForColor.clear();
582 for (MachineBasicBlock::succ_iterator SI = MBB.succ_begin(),
583 SE = MBB.succ_end(); SI != SE; ++SI) {
584 for (MachineBasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end();
585 BBI != BBE && BBI->isPHI(); ++BBI) {
586 MachineInstr *PHI = BBI;
588 // If a PHI is already isolated, either by being isolated directly or
589 // having all of its operands isolated, ignore it.
590 unsigned Color = getPHIColor(PHI);
594 // Find the index of the PHI operand that corresponds to this basic block.
596 for (PredIndex = 1; PredIndex < PHI->getNumOperands(); PredIndex += 2) {
597 if (PHI->getOperand(PredIndex + 1).getMBB() == &MBB)
600 assert(PredIndex < PHI->getNumOperands());
601 unsigned PredOperandReg = PHI->getOperand(PredIndex).getReg();
603 // Pop registers from the stack represented by ImmediateDominatingParent
604 // until we find a parent that dominates the current instruction.
605 unsigned NewParent = CurrentDominatingParent[Color];
607 && (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB)
608 || !getRegColor(NewParent)))
609 NewParent = ImmediateDominatingParent[NewParent];
610 CurrentDominatingParent[Color] = NewParent;
612 // If there is an interference with a register, always isolate the
613 // register rather than the PHI. It is also possible to isolate the
614 // PHI, but that introduces copies for all of the registers involved
616 if (NewParent && LI->isLiveOutOfMBB(LI->getInterval(NewParent), &MBB)
617 && NewParent != PredOperandReg)
618 isolateReg(NewParent);
620 std::pair<MachineInstr*, unsigned> CurrentPHI = CurrentPHIForColor[Color];
622 // If two PHIs have the same operand from every shared predecessor, then
623 // they don't actually interfere. Otherwise, isolate the current PHI. This
624 // could possibly be improved, e.g. we could isolate the PHI with the
626 if (CurrentPHI.first && CurrentPHI.second != PredOperandReg)
629 CurrentPHIForColor[Color] = std::make_pair(PHI, PredOperandReg);
634 void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI,
635 MachineBasicBlock *MBB) {
636 assert(PHI->isPHI());
637 unsigned PHIColor = getPHIColor(PHI);
639 for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
640 MachineOperand &SrcMO = PHI->getOperand(i);
642 // If a source is defined by an implicit def, there is no need to insert a
643 // copy in the predecessor.
647 unsigned SrcReg = SrcMO.getReg();
648 assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
649 "Machine PHI Operands must all be virtual registers!");
651 MachineBasicBlock *PredBB = PHI->getOperand(i + 1).getMBB();
652 unsigned SrcColor = getRegColor(SrcReg);
654 // If neither the PHI nor the operand were isolated, then we only need to
655 // set the phi-kill flag on the VNInfo at this PHI.
656 if (PHIColor && SrcColor == PHIColor) {
657 LiveInterval &SrcInterval = LI->getInterval(SrcReg);
658 SlotIndex PredIndex = LI->getMBBEndIdx(PredBB);
659 VNInfo *SrcVNI = SrcInterval.getVNInfoAt(PredIndex.getPrevIndex());
661 SrcVNI->setHasPHIKill(true);
665 unsigned CopyReg = 0;
667 SrcCopyMap::const_iterator I
668 = InsertedSrcCopyMap.find(std::make_pair(PredBB, PHIColor));
670 = I != InsertedSrcCopyMap.end() ? I->second->getOperand(0).getReg() : 0;
674 const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
675 CopyReg = MRI->createVirtualRegister(RC);
677 MachineBasicBlock::iterator
678 CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
679 unsigned SrcSubReg = SrcMO.getSubReg();
680 MachineInstr *CopyInstr = BuildMI(*PredBB,
683 TII->get(TargetOpcode::COPY),
684 CopyReg).addReg(SrcReg, 0, SrcSubReg);
685 LI->InsertMachineInstrInMaps(CopyInstr);
687 // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
688 // the newly added range.
689 LI->addLiveRangeToEndOfBlock(CopyReg, CopyInstr);
690 InsertedSrcCopySet.insert(std::make_pair(PredBB, SrcReg));
694 unionRegs(PHIColor, CopyReg);
695 assert(getRegColor(CopyReg) != CopyReg);
698 assert(getRegColor(CopyReg) == CopyReg);
701 if (!InsertedSrcCopyMap.count(std::make_pair(PredBB, PHIColor)))
702 InsertedSrcCopyMap[std::make_pair(PredBB, PHIColor)] = CopyInstr;
705 SrcMO.setReg(CopyReg);
707 // If SrcReg is not live beyond the PHI, trim its interval so that it is no
708 // longer live-in to MBB. Note that SrcReg may appear in other PHIs that are
709 // processed later, but this is still correct to do at this point because we
710 // never rely on LiveIntervals being correct while inserting copies.
711 // FIXME: Should this just count uses at PHIs like the normal PHIElimination
713 LiveInterval &SrcLI = LI->getInterval(SrcReg);
714 SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
715 SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
716 SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
717 if (SrcLI.liveAt(MBBStartIndex) && SrcLI.expiredAt(NextInstrIndex))
718 SrcLI.removeRange(MBBStartIndex, PHIIndex, true);
721 unsigned DestReg = PHI->getOperand(0).getReg();
722 unsigned DestColor = getRegColor(DestReg);
724 if (PHIColor && DestColor == PHIColor) {
725 LiveInterval &DestLI = LI->getInterval(DestReg);
727 // Set the phi-def flag for the VN at this PHI.
728 SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
729 VNInfo *DestVNI = DestLI.getVNInfoAt(PHIIndex.getDefIndex());
731 DestVNI->setIsPHIDef(true);
733 // Prior to PHI elimination, the live ranges of PHIs begin at their defining
734 // instruction. After PHI elimination, PHI instructions are replaced by VNs
735 // with the phi-def flag set, and the live ranges of these VNs start at the
736 // beginning of the basic block.
737 SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
738 DestVNI->def = MBBStartIndex;
739 DestLI.addRange(LiveRange(MBBStartIndex,
740 PHIIndex.getDefIndex(),
745 const TargetRegisterClass *RC = MRI->getRegClass(DestReg);
746 unsigned CopyReg = MRI->createVirtualRegister(RC);
748 MachineInstr *CopyInstr = BuildMI(*MBB,
749 MBB->SkipPHIsAndLabels(MBB->begin()),
751 TII->get(TargetOpcode::COPY),
752 DestReg).addReg(CopyReg);
753 LI->InsertMachineInstrInMaps(CopyInstr);
754 PHI->getOperand(0).setReg(CopyReg);
756 // Add the region from the beginning of MBB to the copy instruction to
757 // CopyReg's live interval, and give the VNInfo the phidef flag.
758 LiveInterval &CopyLI = LI->getOrCreateInterval(CopyReg);
759 SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
760 SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
761 VNInfo *CopyVNI = CopyLI.getNextValue(MBBStartIndex,
763 LI->getVNInfoAllocator());
764 CopyVNI->setIsPHIDef(true);
765 CopyLI.addRange(LiveRange(MBBStartIndex,
766 DestCopyIndex.getDefIndex(),
769 // Adjust DestReg's live interval to adjust for its new definition at
771 LiveInterval &DestLI = LI->getOrCreateInterval(DestReg);
772 SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
773 DestLI.removeRange(PHIIndex.getDefIndex(), DestCopyIndex.getDefIndex());
775 VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex());
777 DestVNI->def = DestCopyIndex.getDefIndex();
779 InsertedDestCopies[CopyReg] = CopyInstr;
782 void StrongPHIElimination::MergeLIsAndRename(unsigned Reg, unsigned NewReg) {
786 LiveInterval &OldLI = LI->getInterval(Reg);
787 LiveInterval &NewLI = LI->getInterval(NewReg);
789 // Merge the live ranges of the two registers.
790 DenseMap<VNInfo*, VNInfo*> VNMap;
791 for (LiveInterval::iterator LRI = OldLI.begin(), LRE = OldLI.end();
793 LiveRange OldLR = *LRI;
794 VNInfo *OldVN = OldLR.valno;
796 VNInfo *&NewVN = VNMap[OldVN];
798 NewVN = NewLI.createValueCopy(OldVN, LI->getVNInfoAllocator());
799 VNMap[OldVN] = NewVN;
802 LiveRange LR(OldLR.start, OldLR.end, NewVN);
806 // Remove the LiveInterval for the register being renamed and replace all
807 // of its defs and uses with the new register.
808 LI->removeInterval(Reg);
809 MRI->replaceRegWith(Reg, NewReg);