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. This function is biased
93 /// towards the left argument, i.e. after
96 /// unionRegs(r1, r2);
98 /// the leader of the unioned congruence class is the same as the leader of
99 /// r1's congruence class prior to the union. This is actually relied upon
100 /// in the copy insertion code.
101 void unionRegs(unsigned, unsigned);
103 /// Get the color of a register. The color is 0 if the register has been
105 unsigned getRegColor(unsigned);
107 // Isolate a register.
108 void isolateReg(unsigned);
110 /// Get the color of a PHI. The color of a PHI is 0 if the PHI has been
111 /// isolated. Otherwise, it is the original color of its destination and
112 /// all of its operands (before they were isolated, if they were).
113 unsigned getPHIColor(MachineInstr
*);
116 void isolatePHI(MachineInstr
*);
118 /// Traverses a basic block, splitting any interferences found between
119 /// registers in the same congruence class. It takes two DenseMaps as
120 /// arguments that it also updates: CurrentDominatingParent, which maps
121 /// a color to the register in that congruence class whose definition was
122 /// most recently seen, and ImmediateDominatingParent, which maps a register
123 /// to the register in the same congruence class that most immediately
126 /// This function assumes that it is being called in a depth-first traversal
127 /// of the dominator tree.
128 void SplitInterferencesForBasicBlock(
130 DenseMap
<unsigned, unsigned> &CurrentDominatingParent
,
131 DenseMap
<unsigned, unsigned> &ImmediateDominatingParent
);
133 // Lowers a PHI instruction, inserting copies of the source and destination
134 // registers as necessary.
135 void InsertCopiesForPHI(MachineInstr
*, MachineBasicBlock
*);
137 // Merges the live interval of Reg into NewReg and renames Reg to NewReg
138 // everywhere that Reg appears. Requires Reg and NewReg to have non-
139 // overlapping lifetimes.
140 void MergeLIsAndRename(unsigned Reg
, unsigned NewReg
);
142 MachineRegisterInfo
*MRI
;
143 const TargetInstrInfo
*TII
;
144 MachineDominatorTree
*DT
;
147 BumpPtrAllocator Allocator
;
149 DenseMap
<unsigned, Node
*> RegNodeMap
;
151 // Maps a basic block to a list of its defs of registers that appear as PHI
153 DenseMap
<MachineBasicBlock
*, std::vector
<MachineInstr
*> > PHISrcDefs
;
155 // Maps a color to a pair of a MachineInstr* and a virtual register, which
156 // is the operand of that PHI corresponding to the current basic block.
157 DenseMap
<unsigned, std::pair
<MachineInstr
*, unsigned> > CurrentPHIForColor
;
159 // FIXME: Can these two data structures be combined? Would a std::multimap
162 // Stores pairs of predecessor basic blocks and the source registers of
163 // inserted copy instructions.
164 typedef DenseSet
<std::pair
<MachineBasicBlock
*, unsigned> > SrcCopySet
;
165 SrcCopySet InsertedSrcCopySet
;
167 // Maps pairs of predecessor basic blocks and colors to their defining copy
169 typedef DenseMap
<std::pair
<MachineBasicBlock
*, unsigned>, MachineInstr
*>
171 SrcCopyMap InsertedSrcCopyMap
;
173 // Maps inserted destination copy registers to their defining copy
175 typedef DenseMap
<unsigned, MachineInstr
*> DestCopyMap
;
176 DestCopyMap InsertedDestCopies
;
179 struct MIIndexCompare
{
180 MIIndexCompare(LiveIntervals
*LiveIntervals
) : LI(LiveIntervals
) { }
182 bool operator()(const MachineInstr
*LHS
, const MachineInstr
*RHS
) const {
183 return LI
->getInstructionIndex(LHS
) < LI
->getInstructionIndex(RHS
);
190 char StrongPHIElimination::ID
= 0;
191 INITIALIZE_PASS_BEGIN(StrongPHIElimination
, "strong-phi-node-elimination",
192 "Eliminate PHI nodes for register allocation, intelligently", false, false)
193 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree
)
194 INITIALIZE_PASS_DEPENDENCY(SlotIndexes
)
195 INITIALIZE_PASS_DEPENDENCY(LiveIntervals
)
196 INITIALIZE_PASS_END(StrongPHIElimination
, "strong-phi-node-elimination",
197 "Eliminate PHI nodes for register allocation, intelligently", false, false)
199 char &llvm::StrongPHIEliminationID
= StrongPHIElimination::ID
;
201 void StrongPHIElimination::getAnalysisUsage(AnalysisUsage
&AU
) const {
202 AU
.setPreservesCFG();
203 AU
.addRequired
<MachineDominatorTree
>();
204 AU
.addRequired
<SlotIndexes
>();
205 AU
.addPreserved
<SlotIndexes
>();
206 AU
.addRequired
<LiveIntervals
>();
207 AU
.addPreserved
<LiveIntervals
>();
208 MachineFunctionPass::getAnalysisUsage(AU
);
211 static MachineOperand
*findLastUse(MachineBasicBlock
*MBB
, unsigned Reg
) {
212 // FIXME: This only needs to check from the first terminator, as only the
213 // first terminator can use a virtual register.
214 for (MachineBasicBlock::reverse_iterator RI
= MBB
->rbegin(); ; ++RI
) {
215 assert (RI
!= MBB
->rend());
216 MachineInstr
*MI
= &*RI
;
218 for (MachineInstr::mop_iterator OI
= MI
->operands_begin(),
219 OE
= MI
->operands_end(); OI
!= OE
; ++OI
) {
220 MachineOperand
&MO
= *OI
;
221 if (MO
.isReg() && MO
.isUse() && MO
.getReg() == Reg
)
228 bool StrongPHIElimination::runOnMachineFunction(MachineFunction
&MF
) {
229 MRI
= &MF
.getRegInfo();
230 TII
= MF
.getTarget().getInstrInfo();
231 DT
= &getAnalysis
<MachineDominatorTree
>();
232 LI
= &getAnalysis
<LiveIntervals
>();
234 for (MachineFunction::iterator I
= MF
.begin(), E
= MF
.end();
236 for (MachineBasicBlock::iterator BBI
= I
->begin(), BBE
= I
->end();
237 BBI
!= BBE
&& BBI
->isPHI(); ++BBI
) {
238 unsigned DestReg
= BBI
->getOperand(0).getReg();
240 PHISrcDefs
[I
].push_back(BBI
);
242 for (unsigned i
= 1; i
< BBI
->getNumOperands(); i
+= 2) {
243 MachineOperand
&SrcMO
= BBI
->getOperand(i
);
244 unsigned SrcReg
= SrcMO
.getReg();
246 unionRegs(DestReg
, SrcReg
);
248 MachineInstr
*DefMI
= MRI
->getVRegDef(SrcReg
);
250 PHISrcDefs
[DefMI
->getParent()].push_back(DefMI
);
255 // Perform a depth-first traversal of the dominator tree, splitting
256 // interferences amongst PHI-congruence classes.
257 DenseMap
<unsigned, unsigned> CurrentDominatingParent
;
258 DenseMap
<unsigned, unsigned> ImmediateDominatingParent
;
259 for (df_iterator
<MachineDomTreeNode
*> DI
= df_begin(DT
->getRootNode()),
260 DE
= df_end(DT
->getRootNode()); DI
!= DE
; ++DI
) {
261 SplitInterferencesForBasicBlock(*DI
->getBlock(),
262 CurrentDominatingParent
,
263 ImmediateDominatingParent
);
266 // Insert copies for all PHI source and destination registers.
267 for (MachineFunction::iterator I
= MF
.begin(), E
= MF
.end();
269 for (MachineBasicBlock::iterator BBI
= I
->begin(), BBE
= I
->end();
270 BBI
!= BBE
&& BBI
->isPHI(); ++BBI
) {
271 InsertCopiesForPHI(BBI
, I
);
275 // FIXME: Preserve the equivalence classes during copy insertion and use
276 // the preversed equivalence classes instead of recomputing them.
278 for (MachineFunction::iterator I
= MF
.begin(), E
= MF
.end();
280 for (MachineBasicBlock::iterator BBI
= I
->begin(), BBE
= I
->end();
281 BBI
!= BBE
&& BBI
->isPHI(); ++BBI
) {
282 unsigned DestReg
= BBI
->getOperand(0).getReg();
285 for (unsigned i
= 1; i
< BBI
->getNumOperands(); i
+= 2) {
286 unsigned SrcReg
= BBI
->getOperand(i
).getReg();
288 unionRegs(DestReg
, SrcReg
);
293 DenseMap
<unsigned, unsigned> RegRenamingMap
;
294 bool Changed
= false;
295 for (MachineFunction::iterator I
= MF
.begin(), E
= MF
.end();
297 MachineBasicBlock::iterator BBI
= I
->begin(), BBE
= I
->end();
298 while (BBI
!= BBE
&& BBI
->isPHI()) {
299 MachineInstr
*PHI
= BBI
;
301 assert(PHI
->getNumOperands() > 0);
303 unsigned SrcReg
= PHI
->getOperand(1).getReg();
304 unsigned SrcColor
= getRegColor(SrcReg
);
305 unsigned NewReg
= RegRenamingMap
[SrcColor
];
308 RegRenamingMap
[SrcColor
] = SrcReg
;
310 MergeLIsAndRename(SrcReg
, NewReg
);
312 unsigned DestReg
= PHI
->getOperand(0).getReg();
313 if (!InsertedDestCopies
.count(DestReg
))
314 MergeLIsAndRename(DestReg
, NewReg
);
316 for (unsigned i
= 3; i
< PHI
->getNumOperands(); i
+= 2) {
317 unsigned SrcReg
= PHI
->getOperand(i
).getReg();
318 MergeLIsAndRename(SrcReg
, NewReg
);
322 LI
->RemoveMachineInstrFromMaps(PHI
);
323 PHI
->eraseFromParent();
328 // Due to the insertion of copies to split live ranges, the live intervals are
329 // guaranteed to not overlap, except in one case: an original PHI source and a
330 // PHI destination copy. In this case, they have the same value and thus don't
331 // truly intersect, so we merge them into the value live at that point.
332 // FIXME: Is there some better way we can handle this?
333 for (DestCopyMap::iterator I
= InsertedDestCopies
.begin(),
334 E
= InsertedDestCopies
.end(); I
!= E
; ++I
) {
335 unsigned DestReg
= I
->first
;
336 unsigned DestColor
= getRegColor(DestReg
);
337 unsigned NewReg
= RegRenamingMap
[DestColor
];
339 LiveInterval
&DestLI
= LI
->getInterval(DestReg
);
340 LiveInterval
&NewLI
= LI
->getInterval(NewReg
);
342 assert(DestLI
.ranges
.size() == 1
343 && "PHI destination copy's live interval should be a single live "
344 "range from the beginning of the BB to the copy instruction.");
345 LiveRange
*DestLR
= DestLI
.begin();
346 VNInfo
*NewVNI
= NewLI
.getVNInfoAt(DestLR
->start
);
348 NewVNI
= NewLI
.createValueCopy(DestLR
->valno
, LI
->getVNInfoAllocator());
349 MachineInstr
*CopyInstr
= I
->second
;
350 CopyInstr
->getOperand(1).setIsKill(true);
353 LiveRange
NewLR(DestLR
->start
, DestLR
->end
, NewVNI
);
354 NewLI
.addRange(NewLR
);
356 LI
->removeInterval(DestReg
);
357 MRI
->replaceRegWith(DestReg
, NewReg
);
360 // Adjust the live intervals of all PHI source registers to handle the case
361 // where the PHIs in successor blocks were the only later uses of the source
363 for (SrcCopySet::iterator I
= InsertedSrcCopySet
.begin(),
364 E
= InsertedSrcCopySet
.end(); I
!= E
; ++I
) {
365 MachineBasicBlock
*MBB
= I
->first
;
366 unsigned SrcReg
= I
->second
;
367 if (unsigned RenamedRegister
= RegRenamingMap
[getRegColor(SrcReg
)])
368 SrcReg
= RenamedRegister
;
370 LiveInterval
&SrcLI
= LI
->getInterval(SrcReg
);
372 bool isLiveOut
= false;
373 for (MachineBasicBlock::succ_iterator SI
= MBB
->succ_begin(),
374 SE
= MBB
->succ_end(); SI
!= SE
; ++SI
) {
375 if (SrcLI
.liveAt(LI
->getMBBStartIdx(*SI
))) {
384 MachineOperand
*LastUse
= findLastUse(MBB
, SrcReg
);
386 SlotIndex LastUseIndex
= LI
->getInstructionIndex(LastUse
->getParent());
387 SrcLI
.removeRange(LastUseIndex
.getDefIndex(), LI
->getMBBEndIdx(MBB
));
388 LastUse
->setIsKill(true);
396 InsertedSrcCopySet
.clear();
397 InsertedSrcCopyMap
.clear();
398 InsertedDestCopies
.clear();
403 void StrongPHIElimination::addReg(unsigned Reg
) {
404 if (RegNodeMap
.count(Reg
))
406 RegNodeMap
[Reg
] = new (Allocator
) Node(Reg
);
409 StrongPHIElimination::Node
*
410 StrongPHIElimination::Node::getLeader() {
412 Node
*Parent
= parent
.getPointer();
413 Node
*Grandparent
= Parent
->parent
.getPointer();
415 while (Parent
!= Grandparent
) {
416 N
->parent
.setPointer(Grandparent
);
418 Parent
= Parent
->parent
.getPointer();
419 Grandparent
= Parent
->parent
.getPointer();
425 unsigned StrongPHIElimination::getRegColor(unsigned Reg
) {
426 DenseMap
<unsigned, Node
*>::iterator RI
= RegNodeMap
.find(Reg
);
427 if (RI
== RegNodeMap
.end())
429 Node
*Node
= RI
->second
;
430 if (Node
->parent
.getInt() & Node::kRegisterIsolatedFlag
)
432 return Node
->getLeader()->value
;
435 void StrongPHIElimination::unionRegs(unsigned Reg1
, unsigned Reg2
) {
436 Node
*Node1
= RegNodeMap
[Reg1
]->getLeader();
437 Node
*Node2
= RegNodeMap
[Reg2
]->getLeader();
439 if (Node1
->rank
> Node2
->rank
) {
440 Node2
->parent
.setPointer(Node1
->getLeader());
441 } else if (Node1
->rank
< Node2
->rank
) {
442 Node1
->parent
.setPointer(Node2
->getLeader());
443 } else if (Node1
!= Node2
) {
444 Node2
->parent
.setPointer(Node1
->getLeader());
449 void StrongPHIElimination::isolateReg(unsigned Reg
) {
450 Node
*Node
= RegNodeMap
[Reg
];
451 Node
->parent
.setInt(Node
->parent
.getInt() | Node::kRegisterIsolatedFlag
);
454 unsigned StrongPHIElimination::getPHIColor(MachineInstr
*PHI
) {
455 assert(PHI
->isPHI());
457 unsigned DestReg
= PHI
->getOperand(0).getReg();
458 Node
*DestNode
= RegNodeMap
[DestReg
];
459 if (DestNode
->parent
.getInt() & Node::kPHIIsolatedFlag
)
462 for (unsigned i
= 1; i
< PHI
->getNumOperands(); i
+= 2) {
463 unsigned SrcColor
= getRegColor(PHI
->getOperand(i
).getReg());
470 void StrongPHIElimination::isolatePHI(MachineInstr
*PHI
) {
471 assert(PHI
->isPHI());
472 Node
*Node
= RegNodeMap
[PHI
->getOperand(0).getReg()];
473 Node
->parent
.setInt(Node
->parent
.getInt() | Node::kPHIIsolatedFlag
);
476 /// SplitInterferencesForBasicBlock - traverses a basic block, splitting any
477 /// interferences found between registers in the same congruence class. It
478 /// takes two DenseMaps as arguments that it also updates:
480 /// 1) CurrentDominatingParent, which maps a color to the register in that
481 /// congruence class whose definition was most recently seen.
483 /// 2) ImmediateDominatingParent, which maps a register to the register in the
484 /// same congruence class that most immediately dominates it.
486 /// This function assumes that it is being called in a depth-first traversal
487 /// of the dominator tree.
489 /// The algorithm used here is a generalization of the dominance-based SSA test
490 /// for two variables. If there are variables a_1, ..., a_n such that
492 /// def(a_1) dom ... dom def(a_n),
494 /// then we can test for an interference between any two a_i by only using O(n)
495 /// interference tests between pairs of variables. If i < j and a_i and a_j
496 /// interfere, then a_i is alive at def(a_j), so it is also alive at def(a_i+1).
497 /// Thus, in order to test for an interference involving a_i, we need only check
498 /// for a potential interference with a_i+1.
500 /// This method can be generalized to arbitrary sets of variables by performing
501 /// a depth-first traversal of the dominator tree. As we traverse down a branch
502 /// of the dominator tree, we keep track of the current dominating variable and
503 /// only perform an interference test with that variable. However, when we go to
504 /// another branch of the dominator tree, the definition of the current dominating
505 /// variable may no longer dominate the current block. In order to correct this,
506 /// we need to use a stack of past choices of the current dominating variable
507 /// and pop from this stack until we find a variable whose definition actually
508 /// dominates the current block.
510 /// There will be one push on this stack for each variable that has become the
511 /// current dominating variable, so instead of using an explicit stack we can
512 /// simply associate the previous choice for a current dominating variable with
513 /// the new choice. This works better in our implementation, where we test for
514 /// interference in multiple distinct sets at once.
516 StrongPHIElimination::SplitInterferencesForBasicBlock(
517 MachineBasicBlock
&MBB
,
518 DenseMap
<unsigned, unsigned> &CurrentDominatingParent
,
519 DenseMap
<unsigned, unsigned> &ImmediateDominatingParent
) {
520 // Sort defs by their order in the original basic block, as the code below
521 // assumes that it is processing definitions in dominance order.
522 std::vector
<MachineInstr
*> &DefInstrs
= PHISrcDefs
[&MBB
];
523 std::sort(DefInstrs
.begin(), DefInstrs
.end(), MIIndexCompare(LI
));
525 for (std::vector
<MachineInstr
*>::const_iterator BBI
= DefInstrs
.begin(),
526 BBE
= DefInstrs
.end(); BBI
!= BBE
; ++BBI
) {
527 for (MachineInstr::const_mop_iterator I
= (*BBI
)->operands_begin(),
528 E
= (*BBI
)->operands_end(); I
!= E
; ++I
) {
529 const MachineOperand
&MO
= *I
;
531 // FIXME: This would be faster if it were possible to bail out of checking
532 // an instruction's operands after the explicit defs, but this is incorrect
533 // for variadic instructions, which may appear before register allocation
535 if (!MO
.isReg() || !MO
.isDef())
538 unsigned DestReg
= MO
.getReg();
539 if (!DestReg
|| !TargetRegisterInfo::isVirtualRegister(DestReg
))
542 // If the virtual register being defined is not used in any PHI or has
543 // already been isolated, then there are no more interferences to check.
544 unsigned DestColor
= getRegColor(DestReg
);
548 // The input to this pass sometimes is not in SSA form in every basic
549 // block, as some virtual registers have redefinitions. We could eliminate
550 // this by fixing the passes that generate the non-SSA code, or we could
551 // handle it here by tracking defining machine instructions rather than
552 // virtual registers. For now, we just handle the situation conservatively
553 // in a way that will possibly lead to false interferences.
554 unsigned &CurrentParent
= CurrentDominatingParent
[DestColor
];
555 unsigned NewParent
= CurrentParent
;
556 if (NewParent
== DestReg
)
559 // Pop registers from the stack represented by ImmediateDominatingParent
560 // until we find a parent that dominates the current instruction.
561 while (NewParent
&& (!DT
->dominates(MRI
->getVRegDef(NewParent
), *BBI
)
562 || !getRegColor(NewParent
)))
563 NewParent
= ImmediateDominatingParent
[NewParent
];
565 // If NewParent is nonzero, then its definition dominates the current
566 // instruction, so it is only necessary to check for the liveness of
567 // NewParent in order to check for an interference.
569 && LI
->getInterval(NewParent
).liveAt(LI
->getInstructionIndex(*BBI
))) {
570 // If there is an interference, always isolate the new register. This
571 // could be improved by using a heuristic that decides which of the two
572 // registers to isolate.
574 CurrentParent
= NewParent
;
576 // If there is no interference, update ImmediateDominatingParent and set
577 // the CurrentDominatingParent for this color to the current register.
578 ImmediateDominatingParent
[DestReg
] = NewParent
;
579 CurrentParent
= DestReg
;
584 // We now walk the PHIs in successor blocks and check for interferences. This
585 // is necesary because the use of a PHI's operands are logically contained in
586 // the predecessor block. The def of a PHI's destination register is processed
587 // along with the other defs in a basic block.
589 CurrentPHIForColor
.clear();
591 for (MachineBasicBlock::succ_iterator SI
= MBB
.succ_begin(),
592 SE
= MBB
.succ_end(); SI
!= SE
; ++SI
) {
593 for (MachineBasicBlock::iterator BBI
= (*SI
)->begin(), BBE
= (*SI
)->end();
594 BBI
!= BBE
&& BBI
->isPHI(); ++BBI
) {
595 MachineInstr
*PHI
= BBI
;
597 // If a PHI is already isolated, either by being isolated directly or
598 // having all of its operands isolated, ignore it.
599 unsigned Color
= getPHIColor(PHI
);
603 // Find the index of the PHI operand that corresponds to this basic block.
605 for (PredIndex
= 1; PredIndex
< PHI
->getNumOperands(); PredIndex
+= 2) {
606 if (PHI
->getOperand(PredIndex
+ 1).getMBB() == &MBB
)
609 assert(PredIndex
< PHI
->getNumOperands());
610 unsigned PredOperandReg
= PHI
->getOperand(PredIndex
).getReg();
612 // Pop registers from the stack represented by ImmediateDominatingParent
613 // until we find a parent that dominates the current instruction.
614 unsigned &CurrentParent
= CurrentDominatingParent
[Color
];
615 unsigned NewParent
= CurrentParent
;
617 && (!DT
->dominates(MRI
->getVRegDef(NewParent
)->getParent(), &MBB
)
618 || !getRegColor(NewParent
)))
619 NewParent
= ImmediateDominatingParent
[NewParent
];
620 CurrentParent
= NewParent
;
622 // If there is an interference with a register, always isolate the
623 // register rather than the PHI. It is also possible to isolate the
624 // PHI, but that introduces copies for all of the registers involved
626 if (NewParent
&& LI
->isLiveOutOfMBB(LI
->getInterval(NewParent
), &MBB
)
627 && NewParent
!= PredOperandReg
)
628 isolateReg(NewParent
);
630 std::pair
<MachineInstr
*, unsigned>
631 &CurrentPHI
= CurrentPHIForColor
[Color
];
633 // If two PHIs have the same operand from every shared predecessor, then
634 // they don't actually interfere. Otherwise, isolate the current PHI. This
635 // could possibly be improved, e.g. we could isolate the PHI with the
637 if (CurrentPHI
.first
&& CurrentPHI
.second
!= PredOperandReg
)
640 CurrentPHI
= std::make_pair(PHI
, PredOperandReg
);
645 void StrongPHIElimination::InsertCopiesForPHI(MachineInstr
*PHI
,
646 MachineBasicBlock
*MBB
) {
647 assert(PHI
->isPHI());
648 unsigned PHIColor
= getPHIColor(PHI
);
650 for (unsigned i
= 1; i
< PHI
->getNumOperands(); i
+= 2) {
651 MachineOperand
&SrcMO
= PHI
->getOperand(i
);
653 // If a source is defined by an implicit def, there is no need to insert a
654 // copy in the predecessor.
658 unsigned SrcReg
= SrcMO
.getReg();
659 assert(TargetRegisterInfo::isVirtualRegister(SrcReg
) &&
660 "Machine PHI Operands must all be virtual registers!");
662 MachineBasicBlock
*PredBB
= PHI
->getOperand(i
+ 1).getMBB();
663 unsigned SrcColor
= getRegColor(SrcReg
);
665 // If neither the PHI nor the operand were isolated, then we only need to
666 // set the phi-kill flag on the VNInfo at this PHI.
667 if (PHIColor
&& SrcColor
== PHIColor
) {
668 LiveInterval
&SrcInterval
= LI
->getInterval(SrcReg
);
669 SlotIndex PredIndex
= LI
->getMBBEndIdx(PredBB
);
670 VNInfo
*SrcVNI
= SrcInterval
.getVNInfoAt(PredIndex
.getPrevIndex());
672 SrcVNI
->setHasPHIKill(true);
676 unsigned CopyReg
= 0;
678 SrcCopyMap::const_iterator I
679 = InsertedSrcCopyMap
.find(std::make_pair(PredBB
, PHIColor
));
681 = I
!= InsertedSrcCopyMap
.end() ? I
->second
->getOperand(0).getReg() : 0;
685 const TargetRegisterClass
*RC
= MRI
->getRegClass(SrcReg
);
686 CopyReg
= MRI
->createVirtualRegister(RC
);
688 MachineBasicBlock::iterator
689 CopyInsertPoint
= findPHICopyInsertPoint(PredBB
, MBB
, SrcReg
);
690 unsigned SrcSubReg
= SrcMO
.getSubReg();
691 MachineInstr
*CopyInstr
= BuildMI(*PredBB
,
694 TII
->get(TargetOpcode::COPY
),
695 CopyReg
).addReg(SrcReg
, 0, SrcSubReg
);
696 LI
->InsertMachineInstrInMaps(CopyInstr
);
698 // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
699 // the newly added range.
700 LI
->addLiveRangeToEndOfBlock(CopyReg
, CopyInstr
);
701 InsertedSrcCopySet
.insert(std::make_pair(PredBB
, SrcReg
));
705 unionRegs(PHIColor
, CopyReg
);
706 assert(getRegColor(CopyReg
) != CopyReg
);
709 assert(getRegColor(CopyReg
) == CopyReg
);
712 if (!InsertedSrcCopyMap
.count(std::make_pair(PredBB
, PHIColor
)))
713 InsertedSrcCopyMap
[std::make_pair(PredBB
, PHIColor
)] = CopyInstr
;
716 SrcMO
.setReg(CopyReg
);
718 // If SrcReg is not live beyond the PHI, trim its interval so that it is no
719 // longer live-in to MBB. Note that SrcReg may appear in other PHIs that are
720 // processed later, but this is still correct to do at this point because we
721 // never rely on LiveIntervals being correct while inserting copies.
722 // FIXME: Should this just count uses at PHIs like the normal PHIElimination
724 LiveInterval
&SrcLI
= LI
->getInterval(SrcReg
);
725 SlotIndex MBBStartIndex
= LI
->getMBBStartIdx(MBB
);
726 SlotIndex PHIIndex
= LI
->getInstructionIndex(PHI
);
727 SlotIndex NextInstrIndex
= PHIIndex
.getNextIndex();
728 if (SrcLI
.liveAt(MBBStartIndex
) && SrcLI
.expiredAt(NextInstrIndex
))
729 SrcLI
.removeRange(MBBStartIndex
, PHIIndex
, true);
732 unsigned DestReg
= PHI
->getOperand(0).getReg();
733 unsigned DestColor
= getRegColor(DestReg
);
735 if (PHIColor
&& DestColor
== PHIColor
) {
736 LiveInterval
&DestLI
= LI
->getInterval(DestReg
);
738 // Set the phi-def flag for the VN at this PHI.
739 SlotIndex PHIIndex
= LI
->getInstructionIndex(PHI
);
740 VNInfo
*DestVNI
= DestLI
.getVNInfoAt(PHIIndex
.getDefIndex());
742 DestVNI
->setIsPHIDef(true);
744 // Prior to PHI elimination, the live ranges of PHIs begin at their defining
745 // instruction. After PHI elimination, PHI instructions are replaced by VNs
746 // with the phi-def flag set, and the live ranges of these VNs start at the
747 // beginning of the basic block.
748 SlotIndex MBBStartIndex
= LI
->getMBBStartIdx(MBB
);
749 DestVNI
->def
= MBBStartIndex
;
750 DestLI
.addRange(LiveRange(MBBStartIndex
,
751 PHIIndex
.getDefIndex(),
756 const TargetRegisterClass
*RC
= MRI
->getRegClass(DestReg
);
757 unsigned CopyReg
= MRI
->createVirtualRegister(RC
);
759 MachineInstr
*CopyInstr
= BuildMI(*MBB
,
760 MBB
->SkipPHIsAndLabels(MBB
->begin()),
762 TII
->get(TargetOpcode::COPY
),
763 DestReg
).addReg(CopyReg
);
764 LI
->InsertMachineInstrInMaps(CopyInstr
);
765 PHI
->getOperand(0).setReg(CopyReg
);
767 // Add the region from the beginning of MBB to the copy instruction to
768 // CopyReg's live interval, and give the VNInfo the phidef flag.
769 LiveInterval
&CopyLI
= LI
->getOrCreateInterval(CopyReg
);
770 SlotIndex MBBStartIndex
= LI
->getMBBStartIdx(MBB
);
771 SlotIndex DestCopyIndex
= LI
->getInstructionIndex(CopyInstr
);
772 VNInfo
*CopyVNI
= CopyLI
.getNextValue(MBBStartIndex
,
774 LI
->getVNInfoAllocator());
775 CopyVNI
->setIsPHIDef(true);
776 CopyLI
.addRange(LiveRange(MBBStartIndex
,
777 DestCopyIndex
.getDefIndex(),
780 // Adjust DestReg's live interval to adjust for its new definition at
782 LiveInterval
&DestLI
= LI
->getOrCreateInterval(DestReg
);
783 SlotIndex PHIIndex
= LI
->getInstructionIndex(PHI
);
784 DestLI
.removeRange(PHIIndex
.getDefIndex(), DestCopyIndex
.getDefIndex());
786 VNInfo
*DestVNI
= DestLI
.getVNInfoAt(DestCopyIndex
.getDefIndex());
788 DestVNI
->def
= DestCopyIndex
.getDefIndex();
790 InsertedDestCopies
[CopyReg
] = CopyInstr
;
793 void StrongPHIElimination::MergeLIsAndRename(unsigned Reg
, unsigned NewReg
) {
797 LiveInterval
&OldLI
= LI
->getInterval(Reg
);
798 LiveInterval
&NewLI
= LI
->getInterval(NewReg
);
800 // Merge the live ranges of the two registers.
801 DenseMap
<VNInfo
*, VNInfo
*> VNMap
;
802 for (LiveInterval::iterator LRI
= OldLI
.begin(), LRE
= OldLI
.end();
804 LiveRange OldLR
= *LRI
;
805 VNInfo
*OldVN
= OldLR
.valno
;
807 VNInfo
*&NewVN
= VNMap
[OldVN
];
809 NewVN
= NewLI
.createValueCopy(OldVN
, LI
->getVNInfoAllocator());
810 VNMap
[OldVN
] = NewVN
;
813 LiveRange
LR(OldLR
.start
, OldLR
.end
, NewVN
);
817 // Remove the LiveInterval for the register being renamed and replace all
818 // of its defs and uses with the new register.
819 LI
->removeInterval(Reg
);
820 MRI
->replaceRegWith(Reg
, NewReg
);