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/MachineRegisterInfo.h"
24#include "llvm/CodeGen/SlotIndexes.h"
25#include "llvm/CodeGen/TargetRegisterInfo.h"
26#include "llvm/Support/ErrorHandling.h"
27#include "llvm/Support/raw_ostream.h"
28#include <cassert>
29#include <iterator>
30#include <tuple>
31
32using namespace llvm;
33
34#define DEBUG_TYPE "regalloc"
35
36// Reserve an address that indicates a value that is known to be "undef".
37static VNInfo UndefVNI(0xbad, SlotIndex());
38
39void LiveRangeCalc::resetLiveOutMap() {
40 unsigned NumBlocks = MF->getNumBlockIDs();
41 Seen.clear();
42 Seen.resize(N: NumBlocks);
43 EntryInfos.clear();
44 Map.resize(S: NumBlocks);
45}
46
47void LiveRangeCalc::reset(const MachineFunction *mf,
48 SlotIndexes *SI,
49 MachineDominatorTree *MDT,
50 VNInfo::Allocator *VNIA) {
51 MF = mf;
52 MRI = &MF->getRegInfo();
53 Indexes = SI;
54 DomTree = MDT;
55 Alloc = VNIA;
56 resetLiveOutMap();
57 LiveIn.clear();
58}
59
60void LiveRangeCalc::updateFromLiveIns() {
61 LiveRangeUpdater Updater;
62 for (const LiveInBlock &I : LiveIn) {
63 if (!I.DomNode)
64 continue;
65 MachineBasicBlock *MBB = I.DomNode->getBlock();
66 assert(I.Value && "No live-in value found");
67 SlotIndex Start, End;
68 std::tie(args&: Start, args&: End) = Indexes->getMBBRange(MBB);
69
70 if (I.Kill.isValid())
71 // Value is killed inside this block.
72 End = I.Kill;
73 else {
74 // The value is live-through, update LiveOut as well.
75 // Defer the Domtree lookup until it is needed.
76 assert(Seen.test(MBB->getNumber()));
77 Map[MBB] = LiveOutPair(I.Value, nullptr);
78 }
79 Updater.setDest(&I.LR);
80 Updater.add(Start, End, VNI: I.Value);
81 }
82 LiveIn.clear();
83}
84
85void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, Register PhysReg,
86 ArrayRef<SlotIndex> Undefs) {
87 assert(Use.isValid() && "Invalid SlotIndex");
88 assert(Indexes && "Missing SlotIndexes");
89 assert(DomTree && "Missing dominator tree");
90
91 MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(index: Use.getPrevSlot());
92 assert(UseMBB && "No MBB at Use");
93
94 // Is there a def in the same MBB we can extend?
95 auto EP = LR.extendInBlock(Undefs, StartIdx: Indexes->getMBBStartIdx(mbb: UseMBB), Kill: Use);
96 if (EP.first != nullptr || EP.second)
97 return;
98
99 // Find the single reaching def, or determine if Use is jointly dominated by
100 // multiple values, and we may need to create even more phi-defs to preserve
101 // VNInfo SSA form. Perform a search for all predecessor blocks where we
102 // know the dominating VNInfo.
103 if (findReachingDefs(LR, UseMBB&: *UseMBB, Use, PhysReg, Undefs))
104 return;
105
106 // When there were multiple different values, we may need new PHIs.
107 calculateValues();
108}
109
110// This function is called by a client after using the low-level API to add
111// live-out and live-in blocks. The unique value optimization is not
112// available, SplitEditor::transferValues handles that case directly anyway.
113void LiveRangeCalc::calculateValues() {
114 assert(Indexes && "Missing SlotIndexes");
115 assert(DomTree && "Missing dominator tree");
116 updateSSA();
117 updateFromLiveIns();
118}
119
120bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
121 MachineBasicBlock &MBB, BitVector &DefOnEntry,
122 BitVector &UndefOnEntry) {
123 unsigned BN = MBB.getNumber();
124 if (DefOnEntry[BN])
125 return true;
126 if (UndefOnEntry[BN])
127 return false;
128
129 auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
130 for (MachineBasicBlock *S : B.successors())
131 DefOnEntry[S->getNumber()] = true;
132 DefOnEntry[BN] = true;
133 return true;
134 };
135
136 SetVector<unsigned> WorkList;
137 // Checking if the entry of MBB is reached by some def: add all predecessors
138 // that are potentially defined-on-exit to the work list.
139 for (MachineBasicBlock *P : MBB.predecessors())
140 WorkList.insert(X: P->getNumber());
141
142 for (unsigned i = 0; i != WorkList.size(); ++i) {
143 // Determine if the exit from the block is reached by some def.
144 unsigned N = WorkList[i];
145 MachineBasicBlock &B = *MF->getBlockNumbered(N);
146 if (Seen[N]) {
147 const LiveOutPair &LOB = Map[&B];
148 if (LOB.first != nullptr && LOB.first != &UndefVNI)
149 return MarkDefined(B);
150 }
151 SlotIndex Begin, End;
152 std::tie(args&: Begin, args&: End) = Indexes->getMBBRange(MBB: &B);
153 // Treat End as not belonging to B.
154 // If LR has a segment S that starts at the next block, i.e. [End, ...),
155 // std::upper_bound will return the segment following S. Instead,
156 // S should be treated as the first segment that does not overlap B.
157 LiveRange::iterator UB = upper_bound(Range&: LR, Value: End.getPrevSlot());
158 if (UB != LR.begin()) {
159 LiveRange::Segment &Seg = *std::prev(x: UB);
160 if (Seg.end > Begin) {
161 // There is a segment that overlaps B. If the range is not explicitly
162 // undefined between the end of the segment and the end of the block,
163 // treat the block as defined on exit. If it is, go to the next block
164 // on the work list.
165 if (LR.isUndefIn(Undefs, Begin: Seg.end, End))
166 continue;
167 return MarkDefined(B);
168 }
169 }
170
171 // No segment overlaps with this block. If this block is not defined on
172 // entry, or it undefines the range, do not process its predecessors.
173 if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
174 UndefOnEntry[N] = true;
175 continue;
176 }
177 if (DefOnEntry[N])
178 return MarkDefined(B);
179
180 // Still don't know: add all predecessors to the work list.
181 for (MachineBasicBlock *P : B.predecessors())
182 WorkList.insert(X: P->getNumber());
183 }
184
185 UndefOnEntry[BN] = true;
186 return false;
187}
188
189bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
190 SlotIndex Use, Register PhysReg,
191 ArrayRef<SlotIndex> Undefs) {
192 unsigned UseMBBNum = UseMBB.getNumber();
193
194 // Block numbers where LR should be live-in.
195 SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
196
197 // Remember if we have seen more than one value.
198 bool UniqueVNI = true;
199 VNInfo *TheVNI = nullptr;
200
201 bool FoundUndef = false;
202
203 // Using Seen as a visited set, perform a BFS for all reaching defs.
204 for (unsigned i = 0; i != WorkList.size(); ++i) {
205 MachineBasicBlock *MBB = MF->getBlockNumbered(N: WorkList[i]);
206
207#ifndef NDEBUG
208 if (MBB->pred_empty()) {
209 MBB->getParent()->verify(nullptr, nullptr, &errs());
210 errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo())
211 << " does not have a corresponding definition on every path:\n";
212 const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
213 if (MI != nullptr)
214 errs() << Use << " " << *MI;
215 report_fatal_error("Use not jointly dominated by defs.");
216 }
217
218 if (PhysReg.isPhysical()) {
219 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
220 bool IsLiveIn = MBB->isLiveIn(PhysReg);
221 for (MCRegAliasIterator Alias(PhysReg, TRI, false); !IsLiveIn && Alias.isValid(); ++Alias)
222 IsLiveIn = MBB->isLiveIn(*Alias);
223 if (!IsLiveIn) {
224 MBB->getParent()->verify(nullptr, nullptr, &errs());
225 errs() << "The register " << printReg(PhysReg, TRI)
226 << " needs to be live in to " << printMBBReference(*MBB)
227 << ", but is missing from the live-in list.\n";
228 report_fatal_error("Invalid global physical register");
229 }
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(Idx: 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(args&: Start, args&: End) = Indexes->getMBBRange(MBB: 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, StartIdx: Start, Kill: End);
251 VNInfo *VNI = EP.first;
252 FoundUndef |= EP.second;
253 setLiveOutValue(MBB: Pred, VNI: 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(Elt: 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(Start: WorkList.begin(), End: 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(args&: Start, args&: End) = Indexes->getMBBRange(Num: BN);
288 // Trim the live range in UseMBB.
289 if (BN == UseMBBNum && Use.isValid())
290 End = Use;
291 else
292 Map[MF->getBlockNumbered(N: BN)] = LiveOutPair(TheVNI, nullptr);
293 Updater.add(Start, End, VNI: TheVNI);
294 }
295 return true;
296 }
297
298 // Prepare the defined/undefined bit vectors.
299 EntryInfoMap::iterator Entry;
300 bool DidInsert;
301 std::tie(args&: Entry, args&: DidInsert) = EntryInfos.insert(
302 KV: std::make_pair(x: &LR, y: std::make_pair(x: BitVector(), y: 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(N: WorkList.size());
315 for (unsigned BN : WorkList) {
316 MachineBasicBlock *MBB = MF->getBlockNumbered(N: BN);
317 if (!Undefs.empty() &&
318 !isDefOnEntry(LR, Undefs, MBB&: *MBB, DefOnEntry, UndefOnEntry))
319 continue;
320 addLiveInBlock(LR, DomNode: DomTree->getNode(BB: 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.
330void 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(Idx: 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(BB: Indexes->getMBBFromIndex(index: 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(BB: Indexes->getMBBFromIndex(index: 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(A: IDom, B: 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(args&: Start, args&: End) = Indexes->getMBBRange(MBB);
401 LiveRange &LR = I.LR;
402 VNInfo *VNI = LR.getNextValue(Def: Start, VNInfoAllocator&: *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(S: LiveInterval::Segment(Start, I.Kill, VNI));
411 } else {
412 if (VNI)
413 LR.addSegment(S: 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
435bool 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(index: I)->getNumber());
442
443 unsigned EntryNum = MF.front().getNumber();
444 SetVector<unsigned> PredQueue;
445 PredQueue.insert(X: MBB->getNumber());
446 for (unsigned i = 0; i != PredQueue.size(); ++i) {
447 unsigned BN = PredQueue[i];
448 if (DefBlocks[BN])
449 continue;
450 if (BN == EntryNum) {
451 // We found a path from MBB back to the entry block without hitting any of
452 // the def blocks.
453 return false;
454 }
455 const MachineBasicBlock *B = MF.getBlockNumbered(N: BN);
456 for (const MachineBasicBlock *P : B->predecessors())
457 PredQueue.insert(X: P->getNumber());
458 }
459 return true;
460}
461