1 //===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===//
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 // Implementation of the LiveRangeCalc class.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "regalloc"
15 #include "LiveRangeCalc.h"
16 #include "llvm/CodeGen/MachineDominators.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 void LiveRangeCalc::reset(const MachineFunction *mf,
23 MachineDominatorTree *MDT,
24 VNInfo::Allocator *VNIA) {
26 MRI = &MF->getRegInfo();
31 unsigned N = MF->getNumBlockIDs();
39 void LiveRangeCalc::createDeadDefs(LiveInterval *LI, unsigned Reg) {
40 assert(MRI && Indexes && "call reset() first");
42 // Visit all def operands. If the same instruction has multiple defs of Reg,
43 // LI->createDeadDef() will deduplicate.
44 for (MachineRegisterInfo::def_iterator
45 I = MRI->def_begin(Reg), E = MRI->def_end(); I != E; ++I) {
46 const MachineInstr *MI = &*I;
47 // Find the corresponding slot index.
50 // PHI defs begin at the basic block start index.
51 Idx = Indexes->getMBBStartIdx(MI->getParent());
53 // Instructions are either normal 'r', or early clobber 'e'.
54 Idx = Indexes->getInstructionIndex(MI)
55 .getRegSlot(I.getOperand().isEarlyClobber());
57 // Create the def in LI. This may find an existing def.
58 LI->createDeadDef(Idx, *Alloc);
63 void LiveRangeCalc::extendToUses(LiveInterval *LI, unsigned Reg) {
64 assert(MRI && Indexes && "call reset() first");
66 // Visit all operands that read Reg. This may include partial defs.
67 for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
68 E = MRI->reg_nodbg_end(); I != E; ++I) {
69 MachineOperand &MO = I.getOperand();
70 // Clear all kill flags. They will be reinserted after register allocation
71 // by LiveIntervalAnalysis::addKillFlags().
76 // MI is reading Reg. We may have visited MI before if it happens to be
77 // reading Reg multiple times. That is OK, extend() is idempotent.
78 const MachineInstr *MI = &*I;
80 // Find the SlotIndex being read.
83 assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
84 // PHI operands are paired: (Reg, PredMBB).
85 // Extend the live range to be live-out from PredMBB.
86 Idx = Indexes->getMBBEndIdx(MI->getOperand(I.getOperandNo()+1).getMBB());
88 // This is a normal instruction.
89 Idx = Indexes->getInstructionIndex(MI).getRegSlot();
90 // Check for early-clobber redefs.
93 if (MO.isEarlyClobber())
94 Idx = Idx.getRegSlot(true);
95 } else if (MI->isRegTiedToDefOperand(I.getOperandNo(), &DefIdx)) {
96 // FIXME: This would be a lot easier if tied early-clobber uses also
97 // had an early-clobber flag.
98 if (MI->getOperand(DefIdx).isEarlyClobber())
99 Idx = Idx.getRegSlot(true);
102 extend(LI, Idx, Reg);
107 // Transfer information from the LiveIn vector to the live ranges.
108 void LiveRangeCalc::updateLiveIns() {
109 LiveRangeUpdater Updater;
110 for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
111 E = LiveIn.end(); I != E; ++I) {
114 MachineBasicBlock *MBB = I->DomNode->getBlock();
115 assert(I->Value && "No live-in value found");
116 SlotIndex Start, End;
117 tie(Start, End) = Indexes->getMBBRange(MBB);
119 if (I->Kill.isValid())
120 // Value is killed inside this block.
123 // The value is live-through, update LiveOut as well.
124 // Defer the Domtree lookup until it is needed.
125 assert(Seen.test(MBB->getNumber()));
126 LiveOut[MBB] = LiveOutPair(I->Value, (MachineDomTreeNode *)0);
128 Updater.setDest(I->LI);
129 Updater.add(Start, End, I->Value);
135 void LiveRangeCalc::extend(LiveInterval *LI,
138 assert(LI && "Missing live range");
139 assert(Kill.isValid() && "Invalid SlotIndex");
140 assert(Indexes && "Missing SlotIndexes");
141 assert(DomTree && "Missing dominator tree");
143 MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill.getPrevSlot());
144 assert(KillMBB && "No MBB at Kill");
146 // Is there a def in the same MBB we can extend?
147 if (LI->extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill))
150 // Find the single reaching def, or determine if Kill is jointly dominated by
151 // multiple values, and we may need to create even more phi-defs to preserve
152 // VNInfo SSA form. Perform a search for all predecessor blocks where we
153 // know the dominating VNInfo.
154 if (findReachingDefs(LI, KillMBB, Kill, PhysReg))
157 // When there were multiple different values, we may need new PHIs.
162 // This function is called by a client after using the low-level API to add
163 // live-out and live-in blocks. The unique value optimization is not
164 // available, SplitEditor::transferValues handles that case directly anyway.
165 void LiveRangeCalc::calculateValues() {
166 assert(Indexes && "Missing SlotIndexes");
167 assert(DomTree && "Missing dominator tree");
173 bool LiveRangeCalc::findReachingDefs(LiveInterval *LI,
174 MachineBasicBlock *KillMBB,
177 unsigned KillMBBNum = KillMBB->getNumber();
179 // Block numbers where LI should be live-in.
180 SmallVector<unsigned, 16> WorkList(1, KillMBBNum);
182 // Remember if we have seen more than one value.
183 bool UniqueVNI = true;
186 // Using Seen as a visited set, perform a BFS for all reaching defs.
187 for (unsigned i = 0; i != WorkList.size(); ++i) {
188 MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
191 if (MBB->pred_empty()) {
192 MBB->getParent()->verify();
193 llvm_unreachable("Use not jointly dominated by defs.");
196 if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
197 !MBB->isLiveIn(PhysReg)) {
198 MBB->getParent()->verify();
199 errs() << "The register needs to be live in to BB#" << MBB->getNumber()
200 << ", but is missing from the live-in list.\n";
201 llvm_unreachable("Invalid global physical register");
205 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
206 PE = MBB->pred_end(); PI != PE; ++PI) {
207 MachineBasicBlock *Pred = *PI;
209 // Is this a known live-out block?
210 if (Seen.test(Pred->getNumber())) {
211 if (VNInfo *VNI = LiveOut[Pred].first) {
212 if (TheVNI && TheVNI != VNI)
219 SlotIndex Start, End;
220 tie(Start, End) = Indexes->getMBBRange(Pred);
222 // First time we see Pred. Try to determine the live-out value, but set
223 // it as null if Pred is live-through with an unknown value.
224 VNInfo *VNI = LI->extendInBlock(Start, End);
225 setLiveOutValue(Pred, VNI);
227 if (TheVNI && TheVNI != VNI)
233 // No, we need a live-in value for Pred as well
235 WorkList.push_back(Pred->getNumber());
237 // Loopback to KillMBB, so value is really live through.
244 // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
245 // neither require it. Skip the sorting overhead for small updates.
246 if (WorkList.size() > 4)
247 array_pod_sort(WorkList.begin(), WorkList.end());
249 // If a unique reaching def was found, blit in the live ranges immediately.
251 LiveRangeUpdater Updater(LI);
252 for (SmallVectorImpl<unsigned>::const_iterator
253 I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
254 SlotIndex Start, End;
255 tie(Start, End) = Indexes->getMBBRange(*I);
256 // Trim the live range in KillMBB.
257 if (*I == KillMBBNum && Kill.isValid())
260 LiveOut[MF->getBlockNumbered(*I)] =
261 LiveOutPair(TheVNI, (MachineDomTreeNode *)0);
262 Updater.add(Start, End, TheVNI);
267 // Multiple values were found, so transfer the work list to the LiveIn array
268 // where UpdateSSA will use it as a work list.
269 LiveIn.reserve(WorkList.size());
270 for (SmallVectorImpl<unsigned>::const_iterator
271 I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
272 MachineBasicBlock *MBB = MF->getBlockNumbered(*I);
273 addLiveInBlock(LI, DomTree->getNode(MBB));
275 LiveIn.back().Kill = Kill;
282 // This is essentially the same iterative algorithm that SSAUpdater uses,
283 // except we already have a dominator tree, so we don't have to recompute it.
284 void LiveRangeCalc::updateSSA() {
285 assert(Indexes && "Missing SlotIndexes");
286 assert(DomTree && "Missing dominator tree");
288 // Interate until convergence.
292 // Propagate live-out values down the dominator tree, inserting phi-defs
294 for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
295 E = LiveIn.end(); I != E; ++I) {
296 MachineDomTreeNode *Node = I->DomNode;
297 // Skip block if the live-in value has already been determined.
300 MachineBasicBlock *MBB = Node->getBlock();
301 MachineDomTreeNode *IDom = Node->getIDom();
302 LiveOutPair IDomValue;
304 // We need a live-in value to a block with no immediate dominator?
305 // This is probably an unreachable block that has survived somehow.
306 bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
308 // IDom dominates all of our predecessors, but it may not be their
309 // immediate dominator. Check if any of them have live-out values that are
310 // properly dominated by IDom. If so, we need a phi-def here.
312 IDomValue = LiveOut[IDom->getBlock()];
314 // Cache the DomTree node that defined the value.
315 if (IDomValue.first && !IDomValue.second)
316 LiveOut[IDom->getBlock()].second = IDomValue.second =
317 DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
319 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
320 PE = MBB->pred_end(); PI != PE; ++PI) {
321 LiveOutPair &Value = LiveOut[*PI];
322 if (!Value.first || Value.first == IDomValue.first)
325 // Cache the DomTree node that defined the value.
328 DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
330 // This predecessor is carrying something other than IDomValue.
331 // It could be because IDomValue hasn't propagated yet, or it could be
332 // because MBB is in the dominance frontier of that value.
333 if (DomTree->dominates(IDom, Value.second)) {
340 // The value may be live-through even if Kill is set, as can happen when
341 // we are called from extendRange. In that case LiveOutSeen is true, and
342 // LiveOut indicates a foreign or missing value.
343 LiveOutPair &LOP = LiveOut[MBB];
345 // Create a phi-def if required.
348 assert(Alloc && "Need VNInfo allocator to create PHI-defs");
349 SlotIndex Start, End;
350 tie(Start, End) = Indexes->getMBBRange(MBB);
351 VNInfo *VNI = I->LI->getNextValue(Start, *Alloc);
353 // This block is done, we know the final value.
356 // Add liveness since updateLiveIns now skips this node.
357 if (I->Kill.isValid())
358 I->LI->addRange(LiveRange(Start, I->Kill, VNI));
360 I->LI->addRange(LiveRange(Start, End, VNI));
361 LOP = LiveOutPair(VNI, Node);
363 } else if (IDomValue.first) {
364 // No phi-def here. Remember incoming value.
365 I->Value = IDomValue.first;
367 // If the IDomValue is killed in the block, don't propagate through.
368 if (I->Kill.isValid())
371 // Propagate IDomValue if it isn't killed:
372 // MBB is live-out and doesn't define its own value.
373 if (LOP.first == IDomValue.first)