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 MachineBasicBlock *MBB = MF->getBlockNumbered(N: BN);
287 SlotIndex Start, End;
288 std::tie(args&: Start, args&: End) = Indexes->getMBBRange(MBB);
289 // Trim the live range in UseMBB.
290 if (BN == UseMBBNum && Use.isValid())
291 End = Use;
292 else
293 Map[MBB] = LiveOutPair(TheVNI, nullptr);
294 Updater.add(Start, End, VNI: TheVNI);
295 }
296 return true;
297 }
298
299 // Prepare the defined/undefined bit vectors.
300 EntryInfoMap::iterator Entry;
301 bool DidInsert;
302 std::tie(args&: Entry, args&: DidInsert) = EntryInfos.insert(
303 KV: std::make_pair(x: &LR, y: std::make_pair(x: BitVector(), y: BitVector())));
304 if (DidInsert) {
305 // Initialize newly inserted entries.
306 unsigned N = MF->getNumBlockIDs();
307 Entry->second.first.resize(N);
308 Entry->second.second.resize(N);
309 }
310 BitVector &DefOnEntry = Entry->second.first;
311 BitVector &UndefOnEntry = Entry->second.second;
312
313 // Multiple values were found, so transfer the work list to the LiveIn array
314 // where UpdateSSA will use it as a work list.
315 LiveIn.reserve(N: WorkList.size());
316 for (unsigned BN : WorkList) {
317 MachineBasicBlock *MBB = MF->getBlockNumbered(N: BN);
318 if (!Undefs.empty() &&
319 !isDefOnEntry(LR, Undefs, MBB&: *MBB, DefOnEntry, UndefOnEntry))
320 continue;
321 addLiveInBlock(LR, DomNode: DomTree->getNode(BB: MBB));
322 if (MBB == &UseMBB)
323 LiveIn.back().Kill = Use;
324 }
325
326 return false;
327}
328
329// This is essentially the same iterative algorithm that SSAUpdater uses,
330// except we already have a dominator tree, so we don't have to recompute it.
331void LiveRangeCalc::updateSSA() {
332 assert(Indexes && "Missing SlotIndexes");
333 assert(DomTree && "Missing dominator tree");
334
335 // Interate until convergence.
336 bool Changed;
337 do {
338 Changed = false;
339 // Propagate live-out values down the dominator tree, inserting phi-defs
340 // when necessary.
341 for (LiveInBlock &I : LiveIn) {
342 MachineDomTreeNode *Node = I.DomNode;
343 // Skip block if the live-in value has already been determined.
344 if (!Node)
345 continue;
346 MachineBasicBlock *MBB = Node->getBlock();
347 MachineDomTreeNode *IDom = Node->getIDom();
348 LiveOutPair IDomValue;
349
350 // We need a live-in value to a block with no immediate dominator?
351 // This is probably an unreachable block that has survived somehow.
352 bool needPHI = !IDom || !Seen.test(Idx: IDom->getBlock()->getNumber());
353
354 // IDom dominates all of our predecessors, but it may not be their
355 // immediate dominator. Check if any of them have live-out values that are
356 // properly dominated by IDom. If so, we need a phi-def here.
357 if (!needPHI) {
358 IDomValue = Map[IDom->getBlock()];
359
360 // Cache the DomTree node that defined the value.
361 if (IDomValue.first && IDomValue.first != &UndefVNI &&
362 !IDomValue.second) {
363 Map[IDom->getBlock()].second = IDomValue.second =
364 DomTree->getNode(BB: Indexes->getMBBFromIndex(index: IDomValue.first->def));
365 }
366
367 for (MachineBasicBlock *Pred : MBB->predecessors()) {
368 LiveOutPair &Value = Map[Pred];
369 if (!Value.first || Value.first == IDomValue.first)
370 continue;
371 if (Value.first == &UndefVNI) {
372 needPHI = true;
373 break;
374 }
375
376 // Cache the DomTree node that defined the value.
377 if (!Value.second)
378 Value.second =
379 DomTree->getNode(BB: Indexes->getMBBFromIndex(index: Value.first->def));
380
381 // This predecessor is carrying something other than IDomValue.
382 // It could be because IDomValue hasn't propagated yet, or it could be
383 // because MBB is in the dominance frontier of that value.
384 if (DomTree->dominates(A: IDom, B: Value.second)) {
385 needPHI = true;
386 break;
387 }
388 }
389 }
390
391 // The value may be live-through even if Kill is set, as can happen when
392 // we are called from extendRange. In that case LiveOutSeen is true, and
393 // LiveOut indicates a foreign or missing value.
394 LiveOutPair &LOP = Map[MBB];
395
396 // Create a phi-def if required.
397 if (needPHI) {
398 Changed = true;
399 assert(Alloc && "Need VNInfo allocator to create PHI-defs");
400 SlotIndex Start, End;
401 std::tie(args&: Start, args&: End) = Indexes->getMBBRange(MBB);
402 LiveRange &LR = I.LR;
403 VNInfo *VNI = LR.getNextValue(Def: Start, VNInfoAllocator&: *Alloc);
404 I.Value = VNI;
405 // This block is done, we know the final value.
406 I.DomNode = nullptr;
407
408 // Add liveness since updateFromLiveIns now skips this node.
409 if (I.Kill.isValid()) {
410 if (VNI)
411 LR.addSegment(S: LiveInterval::Segment(Start, I.Kill, VNI));
412 } else {
413 if (VNI)
414 LR.addSegment(S: LiveInterval::Segment(Start, End, VNI));
415 LOP = LiveOutPair(VNI, Node);
416 }
417 } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
418 // No phi-def here. Remember incoming value.
419 I.Value = IDomValue.first;
420
421 // If the IDomValue is killed in the block, don't propagate through.
422 if (I.Kill.isValid())
423 continue;
424
425 // Propagate IDomValue if it isn't killed:
426 // MBB is live-out and doesn't define its own value.
427 if (LOP.first == IDomValue.first)
428 continue;
429 Changed = true;
430 LOP = IDomValue;
431 }
432 }
433 } while (Changed);
434}
435
436bool LiveRangeCalc::isJointlyDominated(const MachineBasicBlock *MBB,
437 ArrayRef<SlotIndex> Defs,
438 const SlotIndexes &Indexes) {
439 const MachineFunction &MF = *MBB->getParent();
440 BitVector DefBlocks(MF.getNumBlockIDs());
441 for (SlotIndex I : Defs)
442 DefBlocks.set(Indexes.getMBBFromIndex(index: I)->getNumber());
443
444 unsigned EntryNum = MF.front().getNumber();
445 SetVector<unsigned> PredQueue;
446 PredQueue.insert(X: MBB->getNumber());
447 for (unsigned i = 0; i != PredQueue.size(); ++i) {
448 unsigned BN = PredQueue[i];
449 if (DefBlocks[BN])
450 continue;
451 if (BN == EntryNum) {
452 // We found a path from MBB back to the entry block without hitting any of
453 // the def blocks.
454 return false;
455 }
456 const MachineBasicBlock *B = MF.getBlockNumbered(N: BN);
457 for (const MachineBasicBlock *P : B->predecessors())
458 PredQueue.insert(X: P->getNumber());
459 }
460 return true;
461}
462