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