1 //===- LiveRangeCalc.cpp - Calculate live ranges -------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Implementation of the LiveRangeCalc class.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/CodeGen/LiveRangeCalc.h"
14 #include "llvm/ADT/BitVector.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/CodeGen/LiveInterval.h"
19 #include "llvm/CodeGen/MachineBasicBlock.h"
20 #include "llvm/CodeGen/MachineDominators.h"
21 #include "llvm/CodeGen/MachineFunction.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/CodeGen/MachineOperand.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/SlotIndexes.h"
26 #include "llvm/CodeGen/TargetRegisterInfo.h"
27 #include "llvm/MC/LaneBitmask.h"
28 #include "llvm/Support/ErrorHandling.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include <algorithm>
31 #include <cassert>
32 #include <iterator>
33 #include <tuple>
34 #include <utility>
35
36 using namespace llvm;
37
38 #define DEBUG_TYPE "regalloc"
39
40 // Reserve an address that indicates a value that is known to be "undef".
41 static VNInfo UndefVNI(0xbad, SlotIndex());
42
resetLiveOutMap()43 void LiveRangeCalc::resetLiveOutMap() {
44 unsigned NumBlocks = MF->getNumBlockIDs();
45 Seen.clear();
46 Seen.resize(NumBlocks);
47 EntryInfos.clear();
48 Map.resize(NumBlocks);
49 }
50
reset(const MachineFunction * mf,SlotIndexes * SI,MachineDominatorTree * MDT,VNInfo::Allocator * VNIA)51 void LiveRangeCalc::reset(const MachineFunction *mf,
52 SlotIndexes *SI,
53 MachineDominatorTree *MDT,
54 VNInfo::Allocator *VNIA) {
55 MF = mf;
56 MRI = &MF->getRegInfo();
57 Indexes = SI;
58 DomTree = MDT;
59 Alloc = VNIA;
60 resetLiveOutMap();
61 LiveIn.clear();
62 }
63
updateFromLiveIns()64 void LiveRangeCalc::updateFromLiveIns() {
65 LiveRangeUpdater Updater;
66 for (const LiveInBlock &I : LiveIn) {
67 if (!I.DomNode)
68 continue;
69 MachineBasicBlock *MBB = I.DomNode->getBlock();
70 assert(I.Value && "No live-in value found");
71 SlotIndex Start, End;
72 std::tie(Start, End) = Indexes->getMBBRange(MBB);
73
74 if (I.Kill.isValid())
75 // Value is killed inside this block.
76 End = I.Kill;
77 else {
78 // The value is live-through, update LiveOut as well.
79 // Defer the Domtree lookup until it is needed.
80 assert(Seen.test(MBB->getNumber()));
81 Map[MBB] = LiveOutPair(I.Value, nullptr);
82 }
83 Updater.setDest(&I.LR);
84 Updater.add(Start, End, I.Value);
85 }
86 LiveIn.clear();
87 }
88
extend(LiveRange & LR,SlotIndex Use,unsigned PhysReg,ArrayRef<SlotIndex> Undefs)89 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
90 ArrayRef<SlotIndex> Undefs) {
91 assert(Use.isValid() && "Invalid SlotIndex");
92 assert(Indexes && "Missing SlotIndexes");
93 assert(DomTree && "Missing dominator tree");
94
95 MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
96 assert(UseMBB && "No MBB at Use");
97
98 // Is there a def in the same MBB we can extend?
99 auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
100 if (EP.first != nullptr || EP.second)
101 return;
102
103 // Find the single reaching def, or determine if Use is jointly dominated by
104 // multiple values, and we may need to create even more phi-defs to preserve
105 // VNInfo SSA form. Perform a search for all predecessor blocks where we
106 // know the dominating VNInfo.
107 if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
108 return;
109
110 // When there were multiple different values, we may need new PHIs.
111 calculateValues();
112 }
113
114 // This function is called by a client after using the low-level API to add
115 // live-out and live-in blocks. The unique value optimization is not
116 // available, SplitEditor::transferValues handles that case directly anyway.
calculateValues()117 void LiveRangeCalc::calculateValues() {
118 assert(Indexes && "Missing SlotIndexes");
119 assert(DomTree && "Missing dominator tree");
120 updateSSA();
121 updateFromLiveIns();
122 }
123
isDefOnEntry(LiveRange & LR,ArrayRef<SlotIndex> Undefs,MachineBasicBlock & MBB,BitVector & DefOnEntry,BitVector & UndefOnEntry)124 bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
125 MachineBasicBlock &MBB, BitVector &DefOnEntry,
126 BitVector &UndefOnEntry) {
127 unsigned BN = MBB.getNumber();
128 if (DefOnEntry[BN])
129 return true;
130 if (UndefOnEntry[BN])
131 return false;
132
133 auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
134 for (MachineBasicBlock *S : B.successors())
135 DefOnEntry[S->getNumber()] = true;
136 DefOnEntry[BN] = true;
137 return true;
138 };
139
140 SetVector<unsigned> WorkList;
141 // Checking if the entry of MBB is reached by some def: add all predecessors
142 // that are potentially defined-on-exit to the work list.
143 for (MachineBasicBlock *P : MBB.predecessors())
144 WorkList.insert(P->getNumber());
145
146 for (unsigned i = 0; i != WorkList.size(); ++i) {
147 // Determine if the exit from the block is reached by some def.
148 unsigned N = WorkList[i];
149 MachineBasicBlock &B = *MF->getBlockNumbered(N);
150 if (Seen[N]) {
151 const LiveOutPair &LOB = Map[&B];
152 if (LOB.first != nullptr && LOB.first != &UndefVNI)
153 return MarkDefined(B);
154 }
155 SlotIndex Begin, End;
156 std::tie(Begin, End) = Indexes->getMBBRange(&B);
157 // Treat End as not belonging to B.
158 // If LR has a segment S that starts at the next block, i.e. [End, ...),
159 // std::upper_bound will return the segment following S. Instead,
160 // S should be treated as the first segment that does not overlap B.
161 LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(),
162 End.getPrevSlot());
163 if (UB != LR.begin()) {
164 LiveRange::Segment &Seg = *std::prev(UB);
165 if (Seg.end > Begin) {
166 // There is a segment that overlaps B. If the range is not explicitly
167 // undefined between the end of the segment and the end of the block,
168 // treat the block as defined on exit. If it is, go to the next block
169 // on the work list.
170 if (LR.isUndefIn(Undefs, Seg.end, End))
171 continue;
172 return MarkDefined(B);
173 }
174 }
175
176 // No segment overlaps with this block. If this block is not defined on
177 // entry, or it undefines the range, do not process its predecessors.
178 if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
179 UndefOnEntry[N] = true;
180 continue;
181 }
182 if (DefOnEntry[N])
183 return MarkDefined(B);
184
185 // Still don't know: add all predecessors to the work list.
186 for (MachineBasicBlock *P : B.predecessors())
187 WorkList.insert(P->getNumber());
188 }
189
190 UndefOnEntry[BN] = true;
191 return false;
192 }
193
findReachingDefs(LiveRange & LR,MachineBasicBlock & UseMBB,SlotIndex Use,unsigned PhysReg,ArrayRef<SlotIndex> Undefs)194 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
195 SlotIndex Use, unsigned PhysReg,
196 ArrayRef<SlotIndex> Undefs) {
197 unsigned UseMBBNum = UseMBB.getNumber();
198
199 // Block numbers where LR should be live-in.
200 SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
201
202 // Remember if we have seen more than one value.
203 bool UniqueVNI = true;
204 VNInfo *TheVNI = nullptr;
205
206 bool FoundUndef = false;
207
208 // Using Seen as a visited set, perform a BFS for all reaching defs.
209 for (unsigned i = 0; i != WorkList.size(); ++i) {
210 MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
211
212 #ifndef NDEBUG
213 if (MBB->pred_empty()) {
214 MBB->getParent()->verify();
215 errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo())
216 << " does not have a corresponding definition on every path:\n";
217 const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
218 if (MI != nullptr)
219 errs() << Use << " " << *MI;
220 report_fatal_error("Use not jointly dominated by defs.");
221 }
222
223 if (Register::isPhysicalRegister(PhysReg) && !MBB->isLiveIn(PhysReg)) {
224 MBB->getParent()->verify();
225 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
226 errs() << "The register " << printReg(PhysReg, TRI)
227 << " needs to be live in to " << printMBBReference(*MBB)
228 << ", but is missing from the live-in list.\n";
229 report_fatal_error("Invalid global physical register");
230 }
231 #endif
232 FoundUndef |= MBB->pred_empty();
233
234 for (MachineBasicBlock *Pred : MBB->predecessors()) {
235 // Is this a known live-out block?
236 if (Seen.test(Pred->getNumber())) {
237 if (VNInfo *VNI = Map[Pred].first) {
238 if (TheVNI && TheVNI != VNI)
239 UniqueVNI = false;
240 TheVNI = VNI;
241 }
242 continue;
243 }
244
245 SlotIndex Start, End;
246 std::tie(Start, End) = Indexes->getMBBRange(Pred);
247
248 // First time we see Pred. Try to determine the live-out value, but set
249 // it as null if Pred is live-through with an unknown value.
250 auto EP = LR.extendInBlock(Undefs, Start, End);
251 VNInfo *VNI = EP.first;
252 FoundUndef |= EP.second;
253 setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
254 if (VNI) {
255 if (TheVNI && TheVNI != VNI)
256 UniqueVNI = false;
257 TheVNI = VNI;
258 }
259 if (VNI || EP.second)
260 continue;
261
262 // No, we need a live-in value for Pred as well
263 if (Pred != &UseMBB)
264 WorkList.push_back(Pred->getNumber());
265 else
266 // Loopback to UseMBB, so value is really live through.
267 Use = SlotIndex();
268 }
269 }
270
271 LiveIn.clear();
272 FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
273 if (!Undefs.empty() && FoundUndef)
274 UniqueVNI = false;
275
276 // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
277 // neither require it. Skip the sorting overhead for small updates.
278 if (WorkList.size() > 4)
279 array_pod_sort(WorkList.begin(), WorkList.end());
280
281 // If a unique reaching def was found, blit in the live ranges immediately.
282 if (UniqueVNI) {
283 assert(TheVNI != nullptr && TheVNI != &UndefVNI);
284 LiveRangeUpdater Updater(&LR);
285 for (unsigned BN : WorkList) {
286 SlotIndex Start, End;
287 std::tie(Start, End) = Indexes->getMBBRange(BN);
288 // Trim the live range in UseMBB.
289 if (BN == UseMBBNum && Use.isValid())
290 End = Use;
291 else
292 Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
293 Updater.add(Start, End, TheVNI);
294 }
295 return true;
296 }
297
298 // Prepare the defined/undefined bit vectors.
299 EntryInfoMap::iterator Entry;
300 bool DidInsert;
301 std::tie(Entry, DidInsert) = EntryInfos.insert(
302 std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
303 if (DidInsert) {
304 // Initialize newly inserted entries.
305 unsigned N = MF->getNumBlockIDs();
306 Entry->second.first.resize(N);
307 Entry->second.second.resize(N);
308 }
309 BitVector &DefOnEntry = Entry->second.first;
310 BitVector &UndefOnEntry = Entry->second.second;
311
312 // Multiple values were found, so transfer the work list to the LiveIn array
313 // where UpdateSSA will use it as a work list.
314 LiveIn.reserve(WorkList.size());
315 for (unsigned BN : WorkList) {
316 MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
317 if (!Undefs.empty() &&
318 !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
319 continue;
320 addLiveInBlock(LR, DomTree->getNode(MBB));
321 if (MBB == &UseMBB)
322 LiveIn.back().Kill = Use;
323 }
324
325 return false;
326 }
327
328 // This is essentially the same iterative algorithm that SSAUpdater uses,
329 // except we already have a dominator tree, so we don't have to recompute it.
updateSSA()330 void LiveRangeCalc::updateSSA() {
331 assert(Indexes && "Missing SlotIndexes");
332 assert(DomTree && "Missing dominator tree");
333
334 // Interate until convergence.
335 bool Changed;
336 do {
337 Changed = false;
338 // Propagate live-out values down the dominator tree, inserting phi-defs
339 // when necessary.
340 for (LiveInBlock &I : LiveIn) {
341 MachineDomTreeNode *Node = I.DomNode;
342 // Skip block if the live-in value has already been determined.
343 if (!Node)
344 continue;
345 MachineBasicBlock *MBB = Node->getBlock();
346 MachineDomTreeNode *IDom = Node->getIDom();
347 LiveOutPair IDomValue;
348
349 // We need a live-in value to a block with no immediate dominator?
350 // This is probably an unreachable block that has survived somehow.
351 bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
352
353 // IDom dominates all of our predecessors, but it may not be their
354 // immediate dominator. Check if any of them have live-out values that are
355 // properly dominated by IDom. If so, we need a phi-def here.
356 if (!needPHI) {
357 IDomValue = Map[IDom->getBlock()];
358
359 // Cache the DomTree node that defined the value.
360 if (IDomValue.first && IDomValue.first != &UndefVNI &&
361 !IDomValue.second) {
362 Map[IDom->getBlock()].second = IDomValue.second =
363 DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
364 }
365
366 for (MachineBasicBlock *Pred : MBB->predecessors()) {
367 LiveOutPair &Value = Map[Pred];
368 if (!Value.first || Value.first == IDomValue.first)
369 continue;
370 if (Value.first == &UndefVNI) {
371 needPHI = true;
372 break;
373 }
374
375 // Cache the DomTree node that defined the value.
376 if (!Value.second)
377 Value.second =
378 DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
379
380 // This predecessor is carrying something other than IDomValue.
381 // It could be because IDomValue hasn't propagated yet, or it could be
382 // because MBB is in the dominance frontier of that value.
383 if (DomTree->dominates(IDom, Value.second)) {
384 needPHI = true;
385 break;
386 }
387 }
388 }
389
390 // The value may be live-through even if Kill is set, as can happen when
391 // we are called from extendRange. In that case LiveOutSeen is true, and
392 // LiveOut indicates a foreign or missing value.
393 LiveOutPair &LOP = Map[MBB];
394
395 // Create a phi-def if required.
396 if (needPHI) {
397 Changed = true;
398 assert(Alloc && "Need VNInfo allocator to create PHI-defs");
399 SlotIndex Start, End;
400 std::tie(Start, End) = Indexes->getMBBRange(MBB);
401 LiveRange &LR = I.LR;
402 VNInfo *VNI = LR.getNextValue(Start, *Alloc);
403 I.Value = VNI;
404 // This block is done, we know the final value.
405 I.DomNode = nullptr;
406
407 // Add liveness since updateFromLiveIns now skips this node.
408 if (I.Kill.isValid()) {
409 if (VNI)
410 LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
411 } else {
412 if (VNI)
413 LR.addSegment(LiveInterval::Segment(Start, End, VNI));
414 LOP = LiveOutPair(VNI, Node);
415 }
416 } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
417 // No phi-def here. Remember incoming value.
418 I.Value = IDomValue.first;
419
420 // If the IDomValue is killed in the block, don't propagate through.
421 if (I.Kill.isValid())
422 continue;
423
424 // Propagate IDomValue if it isn't killed:
425 // MBB is live-out and doesn't define its own value.
426 if (LOP.first == IDomValue.first)
427 continue;
428 Changed = true;
429 LOP = IDomValue;
430 }
431 }
432 } while (Changed);
433 }
434
isJointlyDominated(const MachineBasicBlock * MBB,ArrayRef<SlotIndex> Defs,const SlotIndexes & Indexes)435 bool LiveRangeCalc::isJointlyDominated(const MachineBasicBlock *MBB,
436 ArrayRef<SlotIndex> Defs,
437 const SlotIndexes &Indexes) {
438 const MachineFunction &MF = *MBB->getParent();
439 BitVector DefBlocks(MF.getNumBlockIDs());
440 for (SlotIndex I : Defs)
441 DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber());
442
443 SetVector<unsigned> PredQueue;
444 PredQueue.insert(MBB->getNumber());
445 for (unsigned i = 0; i != PredQueue.size(); ++i) {
446 unsigned BN = PredQueue[i];
447 if (DefBlocks[BN])
448 return true;
449 const MachineBasicBlock *B = MF.getBlockNumbered(BN);
450 for (const MachineBasicBlock *P : B->predecessors())
451 PredQueue.insert(P->getNumber());
452 }
453 return false;
454 }
455