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#include <utility>
32
33using namespace llvm;
34
35#define DEBUG_TYPE "regalloc"
36
37// Reserve an address that indicates a value that is known to be "undef".
38static VNInfo UndefVNI(0xbad, SlotIndex());
39
40void LiveRangeCalc::resetLiveOutMap() {
41 unsigned NumBlocks = MF->getNumBlockIDs();
42 Seen.clear();
43 Seen.resize(N: NumBlocks);
44 EntryInfos.clear();
45 Map.resize(s: NumBlocks);
46}
47
48void LiveRangeCalc::reset(const MachineFunction *mf,
49 SlotIndexes *SI,
50 MachineDominatorTree *MDT,
51 VNInfo::Allocator *VNIA) {
52 MF = mf;
53 MRI = &MF->getRegInfo();
54 Indexes = SI;
55 DomTree = MDT;
56 Alloc = VNIA;
57 resetLiveOutMap();
58 LiveIn.clear();
59}
60
61void LiveRangeCalc::updateFromLiveIns() {
62 LiveRangeUpdater Updater;
63 for (const LiveInBlock &I : LiveIn) {
64 if (!I.DomNode)
65 continue;
66 MachineBasicBlock *MBB = I.DomNode->getBlock();
67 assert(I.Value && "No live-in value found");
68 SlotIndex Start, End;
69 std::tie(args&: Start, args&: End) = Indexes->getMBBRange(MBB);
70
71 if (I.Kill.isValid())
72 // Value is killed inside this block.
73 End = I.Kill;
74 else {
75 // The value is live-through, update LiveOut as well.
76 // Defer the Domtree lookup until it is needed.
77 assert(Seen.test(MBB->getNumber()));
78 Map[MBB] = LiveOutPair(I.Value, nullptr);
79 }
80 Updater.setDest(&I.LR);
81 Updater.add(Start, End, VNI: I.Value);
82 }
83 LiveIn.clear();
84}
85
86void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, Register PhysReg,
87 ArrayRef<SlotIndex> Undefs) {
88 assert(Use.isValid() && "Invalid SlotIndex");
89 assert(Indexes && "Missing SlotIndexes");
90 assert(DomTree && "Missing dominator tree");
91
92 MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(index: Use.getPrevSlot());
93 assert(UseMBB && "No MBB at Use");
94
95 // Is there a def in the same MBB we can extend?
96 auto EP = LR.extendInBlock(Undefs, StartIdx: Indexes->getMBBStartIdx(mbb: UseMBB), Kill: Use);
97 if (EP.first != nullptr || EP.second)
98 return;
99
100 // Find the single reaching def, or determine if Use is jointly dominated by
101 // multiple values, and we may need to create even more phi-defs to preserve
102 // VNInfo SSA form. Perform a search for all predecessor blocks where we
103 // know the dominating VNInfo.
104 if (findReachingDefs(LR, UseMBB&: *UseMBB, Use, PhysReg, Undefs))
105 return;
106
107 // When there were multiple different values, we may need new PHIs.
108 calculateValues();
109}
110
111// This function is called by a client after using the low-level API to add
112// live-out and live-in blocks. The unique value optimization is not
113// available, SplitEditor::transferValues handles that case directly anyway.
114void LiveRangeCalc::calculateValues() {
115 assert(Indexes && "Missing SlotIndexes");
116 assert(DomTree && "Missing dominator tree");
117 updateSSA();
118 updateFromLiveIns();
119}
120
121bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
122 MachineBasicBlock &MBB, BitVector &DefOnEntry,
123 BitVector &UndefOnEntry) {
124 unsigned BN = MBB.getNumber();
125 if (DefOnEntry[BN])
126 return true;
127 if (UndefOnEntry[BN])
128 return false;
129
130 auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
131 for (MachineBasicBlock *S : B.successors())
132 DefOnEntry[S->getNumber()] = true;
133 DefOnEntry[BN] = true;
134 return true;
135 };
136
137 SetVector<unsigned> WorkList;
138 // Checking if the entry of MBB is reached by some def: add all predecessors
139 // that are potentially defined-on-exit to the work list.
140 for (MachineBasicBlock *P : MBB.predecessors())
141 WorkList.insert(X: P->getNumber());
142
143 for (unsigned i = 0; i != WorkList.size(); ++i) {
144 // Determine if the exit from the block is reached by some def.
145 unsigned N = WorkList[i];
146 MachineBasicBlock &B = *MF->getBlockNumbered(N);
147 if (Seen[N]) {
148 const LiveOutPair &LOB = Map[&B];
149 if (LOB.first != nullptr && LOB.first != &UndefVNI)
150 return MarkDefined(B);
151 }
152 SlotIndex Begin, End;
153 std::tie(args&: Begin, args&: End) = Indexes->getMBBRange(MBB: &B);
154 // Treat End as not belonging to B.
155 // If LR has a segment S that starts at the next block, i.e. [End, ...),
156 // std::upper_bound will return the segment following S. Instead,
157 // S should be treated as the first segment that does not overlap B.
158 LiveRange::iterator UB = upper_bound(Range&: LR, Value: End.getPrevSlot());
159 if (UB != LR.begin()) {
160 LiveRange::Segment &Seg = *std::prev(x: UB);
161 if (Seg.end > Begin) {
162 // There is a segment that overlaps B. If the range is not explicitly
163 // undefined between the end of the segment and the end of the block,
164 // treat the block as defined on exit. If it is, go to the next block
165 // on the work list.
166 if (LR.isUndefIn(Undefs, Begin: Seg.end, End))
167 continue;
168 return MarkDefined(B);
169 }
170 }
171
172 // No segment overlaps with this block. If this block is not defined on
173 // entry, or it undefines the range, do not process its predecessors.
174 if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
175 UndefOnEntry[N] = true;
176 continue;
177 }
178 if (DefOnEntry[N])
179 return MarkDefined(B);
180
181 // Still don't know: add all predecessors to the work list.
182 for (MachineBasicBlock *P : B.predecessors())
183 WorkList.insert(X: P->getNumber());
184 }
185
186 UndefOnEntry[BN] = true;
187 return false;
188}
189
190bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
191 SlotIndex Use, Register PhysReg,
192 ArrayRef<SlotIndex> Undefs) {
193 unsigned UseMBBNum = UseMBB.getNumber();
194
195 // Block numbers where LR should be live-in.
196 SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
197
198 // Remember if we have seen more than one value.
199 bool UniqueVNI = true;
200 VNInfo *TheVNI = nullptr;
201
202 bool FoundUndef = false;
203
204 // Using Seen as a visited set, perform a BFS for all reaching defs.
205 for (unsigned i = 0; i != WorkList.size(); ++i) {
206 MachineBasicBlock *MBB = MF->getBlockNumbered(N: WorkList[i]);
207
208#ifndef NDEBUG
209 if (MBB->pred_empty()) {
210 MBB->getParent()->verify(nullptr, nullptr, &errs());
211 errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo())
212 << " does not have a corresponding definition on every path:\n";
213 const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
214 if (MI != nullptr)
215 errs() << Use << " " << *MI;
216 report_fatal_error("Use not jointly dominated by defs.");
217 }
218
219 if (PhysReg.isPhysical()) {
220 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
221 bool IsLiveIn = MBB->isLiveIn(PhysReg);
222 for (MCRegAliasIterator Alias(PhysReg, TRI, false); !IsLiveIn && Alias.isValid(); ++Alias)
223 IsLiveIn = MBB->isLiveIn(*Alias);
224 if (!IsLiveIn) {
225 MBB->getParent()->verify(nullptr, nullptr, &errs());
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 }
232#endif
233 FoundUndef |= MBB->pred_empty();
234
235 for (MachineBasicBlock *Pred : MBB->predecessors()) {
236 // Is this a known live-out block?
237 if (Seen.test(Idx: Pred->getNumber())) {
238 if (VNInfo *VNI = Map[Pred].first) {
239 if (TheVNI && TheVNI != VNI)
240 UniqueVNI = false;
241 TheVNI = VNI;
242 }
243 continue;
244 }
245
246 SlotIndex Start, End;
247 std::tie(args&: Start, args&: End) = Indexes->getMBBRange(MBB: Pred);
248
249 // First time we see Pred. Try to determine the live-out value, but set
250 // it as null if Pred is live-through with an unknown value.
251 auto EP = LR.extendInBlock(Undefs, StartIdx: Start, Kill: End);
252 VNInfo *VNI = EP.first;
253 FoundUndef |= EP.second;
254 setLiveOutValue(MBB: Pred, VNI: EP.second ? &UndefVNI : VNI);
255 if (VNI) {
256 if (TheVNI && TheVNI != VNI)
257 UniqueVNI = false;
258 TheVNI = VNI;
259 }
260 if (VNI || EP.second)
261 continue;
262
263 // No, we need a live-in value for Pred as well
264 if (Pred != &UseMBB)
265 WorkList.push_back(Elt: Pred->getNumber());
266 else
267 // Loopback to UseMBB, so value is really live through.
268 Use = SlotIndex();
269 }
270 }
271
272 LiveIn.clear();
273 FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
274 if (!Undefs.empty() && FoundUndef)
275 UniqueVNI = false;
276
277 // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
278 // neither require it. Skip the sorting overhead for small updates.
279 if (WorkList.size() > 4)
280 array_pod_sort(Start: WorkList.begin(), End: WorkList.end());
281
282 // If a unique reaching def was found, blit in the live ranges immediately.
283 if (UniqueVNI) {
284 assert(TheVNI != nullptr && TheVNI != &UndefVNI);
285 LiveRangeUpdater Updater(&LR);
286 for (unsigned BN : WorkList) {
287 SlotIndex Start, End;
288 std::tie(args&: Start, args&: End) = Indexes->getMBBRange(Num: BN);
289 // Trim the live range in UseMBB.
290 if (BN == UseMBBNum && Use.isValid())
291 End = Use;
292 else
293 Map[MF->getBlockNumbered(N: BN)] = 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