[InstCombine] Signed saturation tests. NFC
[llvm-complete.git] / lib / CodeGen / LiveRangeCalc.cpp
blob24b57be0da00ea0b721e6588960b74322615286b
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.
11 //===----------------------------------------------------------------------===//
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>
36 using namespace llvm;
38 #define DEBUG_TYPE "regalloc"
40 // Reserve an address that indicates a value that is known to be "undef".
41 static VNInfo UndefVNI(0xbad, SlotIndex());
43 void LiveRangeCalc::resetLiveOutMap() {
44 unsigned NumBlocks = MF->getNumBlockIDs();
45 Seen.clear();
46 Seen.resize(NumBlocks);
47 EntryInfos.clear();
48 Map.resize(NumBlocks);
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();
64 static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
65 LiveRange &LR, const MachineOperand &MO) {
66 const MachineInstr &MI = *MO.getParent();
67 SlotIndex DefIdx =
68 Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber());
70 // Create the def in LR. This may find an existing def.
71 LR.createDeadDef(DefIdx, Alloc);
74 void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
75 assert(MRI && Indexes && "call reset() first");
77 // Step 1: Create minimal live segments for every definition of Reg.
78 // Visit all def operands. If the same instruction has multiple defs of Reg,
79 // createDeadDef() will deduplicate.
80 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
81 unsigned Reg = LI.reg;
82 for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
83 if (!MO.isDef() && !MO.readsReg())
84 continue;
86 unsigned SubReg = MO.getSubReg();
87 if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
88 LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
89 : MRI->getMaxLaneMaskForVReg(Reg);
90 // If this is the first time we see a subregister def, initialize
91 // subranges by creating a copy of the main range.
92 if (!LI.hasSubRanges() && !LI.empty()) {
93 LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
94 LI.createSubRangeFrom(*Alloc, ClassMask, LI);
97 LI.refineSubRanges(*Alloc, SubMask,
98 [&MO, this](LiveInterval::SubRange &SR) {
99 if (MO.isDef())
100 createDeadDef(*Indexes, *Alloc, SR, MO);
102 *Indexes, TRI);
105 // Create the def in the main liverange. We do not have to do this if
106 // subranges are tracked as we recreate the main range later in this case.
107 if (MO.isDef() && !LI.hasSubRanges())
108 createDeadDef(*Indexes, *Alloc, LI, MO);
111 // We may have created empty live ranges for partially undefined uses, we
112 // can't keep them because we won't find defs in them later.
113 LI.removeEmptySubRanges();
115 // Step 2: Extend live segments to all uses, constructing SSA form as
116 // necessary.
117 if (LI.hasSubRanges()) {
118 for (LiveInterval::SubRange &S : LI.subranges()) {
119 LiveRangeCalc SubLRC;
120 SubLRC.reset(MF, Indexes, DomTree, Alloc);
121 SubLRC.extendToUses(S, Reg, S.LaneMask, &LI);
123 LI.clear();
124 constructMainRangeFromSubranges(LI);
125 } else {
126 resetLiveOutMap();
127 extendToUses(LI, Reg, LaneBitmask::getAll());
131 void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
132 // First create dead defs at all defs found in subranges.
133 LiveRange &MainRange = LI;
134 assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
135 "Expect empty main liverange");
137 for (const LiveInterval::SubRange &SR : LI.subranges()) {
138 for (const VNInfo *VNI : SR.valnos) {
139 if (!VNI->isUnused() && !VNI->isPHIDef())
140 MainRange.createDeadDef(VNI->def, *Alloc);
143 resetLiveOutMap();
144 extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI);
147 void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
148 assert(MRI && Indexes && "call reset() first");
150 // Visit all def operands. If the same instruction has multiple defs of Reg,
151 // LR.createDeadDef() will deduplicate.
152 for (MachineOperand &MO : MRI->def_operands(Reg))
153 createDeadDef(*Indexes, *Alloc, LR, MO);
156 void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
157 LiveInterval *LI) {
158 SmallVector<SlotIndex, 4> Undefs;
159 if (LI != nullptr)
160 LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
162 // Visit all operands that read Reg. This may include partial defs.
163 bool IsSubRange = !Mask.all();
164 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
165 for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
166 // Clear all kill flags. They will be reinserted after register allocation
167 // by LiveIntervals::addKillFlags().
168 if (MO.isUse())
169 MO.setIsKill(false);
170 // MO::readsReg returns "true" for subregister defs. This is for keeping
171 // liveness of the entire register (i.e. for the main range of the live
172 // interval). For subranges, definitions of non-overlapping subregisters
173 // do not count as uses.
174 if (!MO.readsReg() || (IsSubRange && MO.isDef()))
175 continue;
177 unsigned SubReg = MO.getSubReg();
178 if (SubReg != 0) {
179 LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
180 if (MO.isDef())
181 SLM = ~SLM;
182 // Ignore uses not reading the current (sub)range.
183 if ((SLM & Mask).none())
184 continue;
187 // Determine the actual place of the use.
188 const MachineInstr *MI = MO.getParent();
189 unsigned OpNo = (&MO - &MI->getOperand(0));
190 SlotIndex UseIdx;
191 if (MI->isPHI()) {
192 assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
193 // The actual place where a phi operand is used is the end of the pred
194 // MBB. PHI operands are paired: (Reg, PredMBB).
195 UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
196 } else {
197 // Check for early-clobber redefs.
198 bool isEarlyClobber = false;
199 unsigned DefIdx;
200 if (MO.isDef())
201 isEarlyClobber = MO.isEarlyClobber();
202 else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
203 // FIXME: This would be a lot easier if tied early-clobber uses also
204 // had an early-clobber flag.
205 isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
207 UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
210 // MI is reading Reg. We may have visited MI before if it happens to be
211 // reading Reg multiple times. That is OK, extend() is idempotent.
212 extend(LR, UseIdx, Reg, Undefs);
216 void LiveRangeCalc::updateFromLiveIns() {
217 LiveRangeUpdater Updater;
218 for (const LiveInBlock &I : LiveIn) {
219 if (!I.DomNode)
220 continue;
221 MachineBasicBlock *MBB = I.DomNode->getBlock();
222 assert(I.Value && "No live-in value found");
223 SlotIndex Start, End;
224 std::tie(Start, End) = Indexes->getMBBRange(MBB);
226 if (I.Kill.isValid())
227 // Value is killed inside this block.
228 End = I.Kill;
229 else {
230 // The value is live-through, update LiveOut as well.
231 // Defer the Domtree lookup until it is needed.
232 assert(Seen.test(MBB->getNumber()));
233 Map[MBB] = LiveOutPair(I.Value, nullptr);
235 Updater.setDest(&I.LR);
236 Updater.add(Start, End, I.Value);
238 LiveIn.clear();
241 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
242 ArrayRef<SlotIndex> Undefs) {
243 assert(Use.isValid() && "Invalid SlotIndex");
244 assert(Indexes && "Missing SlotIndexes");
245 assert(DomTree && "Missing dominator tree");
247 MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
248 assert(UseMBB && "No MBB at Use");
250 // Is there a def in the same MBB we can extend?
251 auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
252 if (EP.first != nullptr || EP.second)
253 return;
255 // Find the single reaching def, or determine if Use is jointly dominated by
256 // multiple values, and we may need to create even more phi-defs to preserve
257 // VNInfo SSA form. Perform a search for all predecessor blocks where we
258 // know the dominating VNInfo.
259 if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
260 return;
262 // When there were multiple different values, we may need new PHIs.
263 calculateValues();
266 // This function is called by a client after using the low-level API to add
267 // live-out and live-in blocks. The unique value optimization is not
268 // available, SplitEditor::transferValues handles that case directly anyway.
269 void LiveRangeCalc::calculateValues() {
270 assert(Indexes && "Missing SlotIndexes");
271 assert(DomTree && "Missing dominator tree");
272 updateSSA();
273 updateFromLiveIns();
276 bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
277 MachineBasicBlock &MBB, BitVector &DefOnEntry,
278 BitVector &UndefOnEntry) {
279 unsigned BN = MBB.getNumber();
280 if (DefOnEntry[BN])
281 return true;
282 if (UndefOnEntry[BN])
283 return false;
285 auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
286 for (MachineBasicBlock *S : B.successors())
287 DefOnEntry[S->getNumber()] = true;
288 DefOnEntry[BN] = true;
289 return true;
292 SetVector<unsigned> WorkList;
293 // Checking if the entry of MBB is reached by some def: add all predecessors
294 // that are potentially defined-on-exit to the work list.
295 for (MachineBasicBlock *P : MBB.predecessors())
296 WorkList.insert(P->getNumber());
298 for (unsigned i = 0; i != WorkList.size(); ++i) {
299 // Determine if the exit from the block is reached by some def.
300 unsigned N = WorkList[i];
301 MachineBasicBlock &B = *MF->getBlockNumbered(N);
302 if (Seen[N]) {
303 const LiveOutPair &LOB = Map[&B];
304 if (LOB.first != nullptr && LOB.first != &UndefVNI)
305 return MarkDefined(B);
307 SlotIndex Begin, End;
308 std::tie(Begin, End) = Indexes->getMBBRange(&B);
309 // Treat End as not belonging to B.
310 // If LR has a segment S that starts at the next block, i.e. [End, ...),
311 // std::upper_bound will return the segment following S. Instead,
312 // S should be treated as the first segment that does not overlap B.
313 LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(),
314 End.getPrevSlot());
315 if (UB != LR.begin()) {
316 LiveRange::Segment &Seg = *std::prev(UB);
317 if (Seg.end > Begin) {
318 // There is a segment that overlaps B. If the range is not explicitly
319 // undefined between the end of the segment and the end of the block,
320 // treat the block as defined on exit. If it is, go to the next block
321 // on the work list.
322 if (LR.isUndefIn(Undefs, Seg.end, End))
323 continue;
324 return MarkDefined(B);
328 // No segment overlaps with this block. If this block is not defined on
329 // entry, or it undefines the range, do not process its predecessors.
330 if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
331 UndefOnEntry[N] = true;
332 continue;
334 if (DefOnEntry[N])
335 return MarkDefined(B);
337 // Still don't know: add all predecessors to the work list.
338 for (MachineBasicBlock *P : B.predecessors())
339 WorkList.insert(P->getNumber());
342 UndefOnEntry[BN] = true;
343 return false;
346 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
347 SlotIndex Use, unsigned PhysReg,
348 ArrayRef<SlotIndex> Undefs) {
349 unsigned UseMBBNum = UseMBB.getNumber();
351 // Block numbers where LR should be live-in.
352 SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
354 // Remember if we have seen more than one value.
355 bool UniqueVNI = true;
356 VNInfo *TheVNI = nullptr;
358 bool FoundUndef = false;
360 // Using Seen as a visited set, perform a BFS for all reaching defs.
361 for (unsigned i = 0; i != WorkList.size(); ++i) {
362 MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
364 #ifndef NDEBUG
365 if (MBB->pred_empty()) {
366 MBB->getParent()->verify();
367 errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo())
368 << " does not have a corresponding definition on every path:\n";
369 const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
370 if (MI != nullptr)
371 errs() << Use << " " << *MI;
372 report_fatal_error("Use not jointly dominated by defs.");
375 if (Register::isPhysicalRegister(PhysReg) && !MBB->isLiveIn(PhysReg)) {
376 MBB->getParent()->verify();
377 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
378 errs() << "The register " << printReg(PhysReg, TRI)
379 << " needs to be live in to " << printMBBReference(*MBB)
380 << ", but is missing from the live-in list.\n";
381 report_fatal_error("Invalid global physical register");
383 #endif
384 FoundUndef |= MBB->pred_empty();
386 for (MachineBasicBlock *Pred : MBB->predecessors()) {
387 // Is this a known live-out block?
388 if (Seen.test(Pred->getNumber())) {
389 if (VNInfo *VNI = Map[Pred].first) {
390 if (TheVNI && TheVNI != VNI)
391 UniqueVNI = false;
392 TheVNI = VNI;
394 continue;
397 SlotIndex Start, End;
398 std::tie(Start, End) = Indexes->getMBBRange(Pred);
400 // First time we see Pred. Try to determine the live-out value, but set
401 // it as null if Pred is live-through with an unknown value.
402 auto EP = LR.extendInBlock(Undefs, Start, End);
403 VNInfo *VNI = EP.first;
404 FoundUndef |= EP.second;
405 setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
406 if (VNI) {
407 if (TheVNI && TheVNI != VNI)
408 UniqueVNI = false;
409 TheVNI = VNI;
411 if (VNI || EP.second)
412 continue;
414 // No, we need a live-in value for Pred as well
415 if (Pred != &UseMBB)
416 WorkList.push_back(Pred->getNumber());
417 else
418 // Loopback to UseMBB, so value is really live through.
419 Use = SlotIndex();
423 LiveIn.clear();
424 FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
425 if (!Undefs.empty() && FoundUndef)
426 UniqueVNI = false;
428 // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
429 // neither require it. Skip the sorting overhead for small updates.
430 if (WorkList.size() > 4)
431 array_pod_sort(WorkList.begin(), WorkList.end());
433 // If a unique reaching def was found, blit in the live ranges immediately.
434 if (UniqueVNI) {
435 assert(TheVNI != nullptr && TheVNI != &UndefVNI);
436 LiveRangeUpdater Updater(&LR);
437 for (unsigned BN : WorkList) {
438 SlotIndex Start, End;
439 std::tie(Start, End) = Indexes->getMBBRange(BN);
440 // Trim the live range in UseMBB.
441 if (BN == UseMBBNum && Use.isValid())
442 End = Use;
443 else
444 Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
445 Updater.add(Start, End, TheVNI);
447 return true;
450 // Prepare the defined/undefined bit vectors.
451 EntryInfoMap::iterator Entry;
452 bool DidInsert;
453 std::tie(Entry, DidInsert) = EntryInfos.insert(
454 std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
455 if (DidInsert) {
456 // Initialize newly inserted entries.
457 unsigned N = MF->getNumBlockIDs();
458 Entry->second.first.resize(N);
459 Entry->second.second.resize(N);
461 BitVector &DefOnEntry = Entry->second.first;
462 BitVector &UndefOnEntry = Entry->second.second;
464 // Multiple values were found, so transfer the work list to the LiveIn array
465 // where UpdateSSA will use it as a work list.
466 LiveIn.reserve(WorkList.size());
467 for (unsigned BN : WorkList) {
468 MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
469 if (!Undefs.empty() &&
470 !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
471 continue;
472 addLiveInBlock(LR, DomTree->getNode(MBB));
473 if (MBB == &UseMBB)
474 LiveIn.back().Kill = Use;
477 return false;
480 // This is essentially the same iterative algorithm that SSAUpdater uses,
481 // except we already have a dominator tree, so we don't have to recompute it.
482 void LiveRangeCalc::updateSSA() {
483 assert(Indexes && "Missing SlotIndexes");
484 assert(DomTree && "Missing dominator tree");
486 // Interate until convergence.
487 bool Changed;
488 do {
489 Changed = false;
490 // Propagate live-out values down the dominator tree, inserting phi-defs
491 // when necessary.
492 for (LiveInBlock &I : LiveIn) {
493 MachineDomTreeNode *Node = I.DomNode;
494 // Skip block if the live-in value has already been determined.
495 if (!Node)
496 continue;
497 MachineBasicBlock *MBB = Node->getBlock();
498 MachineDomTreeNode *IDom = Node->getIDom();
499 LiveOutPair IDomValue;
501 // We need a live-in value to a block with no immediate dominator?
502 // This is probably an unreachable block that has survived somehow.
503 bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
505 // IDom dominates all of our predecessors, but it may not be their
506 // immediate dominator. Check if any of them have live-out values that are
507 // properly dominated by IDom. If so, we need a phi-def here.
508 if (!needPHI) {
509 IDomValue = Map[IDom->getBlock()];
511 // Cache the DomTree node that defined the value.
512 if (IDomValue.first && IDomValue.first != &UndefVNI &&
513 !IDomValue.second) {
514 Map[IDom->getBlock()].second = IDomValue.second =
515 DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
518 for (MachineBasicBlock *Pred : MBB->predecessors()) {
519 LiveOutPair &Value = Map[Pred];
520 if (!Value.first || Value.first == IDomValue.first)
521 continue;
522 if (Value.first == &UndefVNI) {
523 needPHI = true;
524 break;
527 // Cache the DomTree node that defined the value.
528 if (!Value.second)
529 Value.second =
530 DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
532 // This predecessor is carrying something other than IDomValue.
533 // It could be because IDomValue hasn't propagated yet, or it could be
534 // because MBB is in the dominance frontier of that value.
535 if (DomTree->dominates(IDom, Value.second)) {
536 needPHI = true;
537 break;
542 // The value may be live-through even if Kill is set, as can happen when
543 // we are called from extendRange. In that case LiveOutSeen is true, and
544 // LiveOut indicates a foreign or missing value.
545 LiveOutPair &LOP = Map[MBB];
547 // Create a phi-def if required.
548 if (needPHI) {
549 Changed = true;
550 assert(Alloc && "Need VNInfo allocator to create PHI-defs");
551 SlotIndex Start, End;
552 std::tie(Start, End) = Indexes->getMBBRange(MBB);
553 LiveRange &LR = I.LR;
554 VNInfo *VNI = LR.getNextValue(Start, *Alloc);
555 I.Value = VNI;
556 // This block is done, we know the final value.
557 I.DomNode = nullptr;
559 // Add liveness since updateFromLiveIns now skips this node.
560 if (I.Kill.isValid()) {
561 if (VNI)
562 LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
563 } else {
564 if (VNI)
565 LR.addSegment(LiveInterval::Segment(Start, End, VNI));
566 LOP = LiveOutPair(VNI, Node);
568 } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
569 // No phi-def here. Remember incoming value.
570 I.Value = IDomValue.first;
572 // If the IDomValue is killed in the block, don't propagate through.
573 if (I.Kill.isValid())
574 continue;
576 // Propagate IDomValue if it isn't killed:
577 // MBB is live-out and doesn't define its own value.
578 if (LOP.first == IDomValue.first)
579 continue;
580 Changed = true;
581 LOP = IDomValue;
584 } while (Changed);
587 bool LiveRangeCalc::isJointlyDominated(const MachineBasicBlock *MBB,
588 ArrayRef<SlotIndex> Defs,
589 const SlotIndexes &Indexes) {
590 const MachineFunction &MF = *MBB->getParent();
591 BitVector DefBlocks(MF.getNumBlockIDs());
592 for (SlotIndex I : Defs)
593 DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber());
595 SetVector<unsigned> PredQueue;
596 PredQueue.insert(MBB->getNumber());
597 for (unsigned i = 0; i != PredQueue.size(); ++i) {
598 unsigned BN = PredQueue[i];
599 if (DefBlocks[BN])
600 return true;
601 const MachineBasicBlock *B = MF.getBlockNumbered(BN);
602 for (const MachineBasicBlock *P : B->predecessors())
603 PredQueue.insert(P->getNumber());
605 return false;