1//===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Implementation of the LiveRangeCalc class.
11//
12//===----------------------------------------------------------------------===//
13
14#include "LiveRangeCalc.h"
15#include "llvm/CodeGen/MachineDominators.h"
16#include "llvm/CodeGen/MachineRegisterInfo.h"
17
18using namespace llvm;
19
20#define DEBUG_TYPE "regalloc"
21
22void LiveRangeCalc::reset(const MachineFunction *mf,
23                          SlotIndexes *SI,
24                          MachineDominatorTree *MDT,
25                          VNInfo::Allocator *VNIA) {
26  MF = mf;
27  MRI = &MF->getRegInfo();
28  Indexes = SI;
29  DomTree = MDT;
30  Alloc = VNIA;
31
32  unsigned N = MF->getNumBlockIDs();
33  Seen.clear();
34  Seen.resize(N);
35  LiveOut.resize(N);
36  LiveIn.clear();
37}
38
39
40void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
41  assert(MRI && Indexes && "call reset() first");
42
43  // Visit all def operands. If the same instruction has multiple defs of Reg,
44  // LR.createDeadDef() will deduplicate.
45  for (MachineOperand &MO : MRI->def_operands(Reg)) {
46    const MachineInstr *MI = MO.getParent();
47    // Find the corresponding slot index.
48    SlotIndex Idx;
49    if (MI->isPHI())
50      // PHI defs begin at the basic block start index.
51      Idx = Indexes->getMBBStartIdx(MI->getParent());
52    else
53      // Instructions are either normal 'r', or early clobber 'e'.
54      Idx = Indexes->getInstructionIndex(MI)
55        .getRegSlot(MO.isEarlyClobber());
56
57    // Create the def in LR. This may find an existing def.
58    LR.createDeadDef(Idx, *Alloc);
59  }
60}
61
62
63void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg) {
64  assert(MRI && Indexes && "call reset() first");
65
66  // Visit all operands that read Reg. This may include partial defs.
67  for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
68    // Clear all kill flags. They will be reinserted after register allocation
69    // by LiveIntervalAnalysis::addKillFlags().
70    if (MO.isUse())
71      MO.setIsKill(false);
72    if (!MO.readsReg())
73      continue;
74    // MI is reading Reg. We may have visited MI before if it happens to be
75    // reading Reg multiple times. That is OK, extend() is idempotent.
76    const MachineInstr *MI = MO.getParent();
77    unsigned OpNo = (&MO - &MI->getOperand(0));
78
79    // Find the SlotIndex being read.
80    SlotIndex Idx;
81    if (MI->isPHI()) {
82      assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
83      // PHI operands are paired: (Reg, PredMBB).
84      // Extend the live range to be live-out from PredMBB.
85      Idx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
86    } else {
87      // This is a normal instruction.
88      Idx = Indexes->getInstructionIndex(MI).getRegSlot();
89      // Check for early-clobber redefs.
90      unsigned DefIdx;
91      if (MO.isDef()) {
92        if (MO.isEarlyClobber())
93          Idx = Idx.getRegSlot(true);
94      } else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
95        // FIXME: This would be a lot easier if tied early-clobber uses also
96        // had an early-clobber flag.
97        if (MI->getOperand(DefIdx).isEarlyClobber())
98          Idx = Idx.getRegSlot(true);
99      }
100    }
101    extend(LR, Idx, Reg);
102  }
103}
104
105
106// Transfer information from the LiveIn vector to the live ranges.
107void LiveRangeCalc::updateLiveIns() {
108  LiveRangeUpdater Updater;
109  for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
110         E = LiveIn.end(); I != E; ++I) {
111    if (!I->DomNode)
112      continue;
113    MachineBasicBlock *MBB = I->DomNode->getBlock();
114    assert(I->Value && "No live-in value found");
115    SlotIndex Start, End;
116    std::tie(Start, End) = Indexes->getMBBRange(MBB);
117
118    if (I->Kill.isValid())
119      // Value is killed inside this block.
120      End = I->Kill;
121    else {
122      // The value is live-through, update LiveOut as well.
123      // Defer the Domtree lookup until it is needed.
124      assert(Seen.test(MBB->getNumber()));
125      LiveOut[MBB] = LiveOutPair(I->Value, (MachineDomTreeNode *)nullptr);
126    }
127    Updater.setDest(&I->LR);
128    Updater.add(Start, End, I->Value);
129  }
130  LiveIn.clear();
131}
132
133
134void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg) {
135  assert(Kill.isValid() && "Invalid SlotIndex");
136  assert(Indexes && "Missing SlotIndexes");
137  assert(DomTree && "Missing dominator tree");
138
139  MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill.getPrevSlot());
140  assert(KillMBB && "No MBB at Kill");
141
142  // Is there a def in the same MBB we can extend?
143  if (LR.extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill))
144    return;
145
146  // Find the single reaching def, or determine if Kill is jointly dominated by
147  // multiple values, and we may need to create even more phi-defs to preserve
148  // VNInfo SSA form.  Perform a search for all predecessor blocks where we
149  // know the dominating VNInfo.
150  if (findReachingDefs(LR, *KillMBB, Kill, PhysReg))
151    return;
152
153  // When there were multiple different values, we may need new PHIs.
154  calculateValues();
155}
156
157
158// This function is called by a client after using the low-level API to add
159// live-out and live-in blocks.  The unique value optimization is not
160// available, SplitEditor::transferValues handles that case directly anyway.
161void LiveRangeCalc::calculateValues() {
162  assert(Indexes && "Missing SlotIndexes");
163  assert(DomTree && "Missing dominator tree");
164  updateSSA();
165  updateLiveIns();
166}
167
168
169bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB,
170                                     SlotIndex Kill, unsigned PhysReg) {
171  unsigned KillMBBNum = KillMBB.getNumber();
172
173  // Block numbers where LR should be live-in.
174  SmallVector<unsigned, 16> WorkList(1, KillMBBNum);
175
176  // Remember if we have seen more than one value.
177  bool UniqueVNI = true;
178  VNInfo *TheVNI = nullptr;
179
180  // Using Seen as a visited set, perform a BFS for all reaching defs.
181  for (unsigned i = 0; i != WorkList.size(); ++i) {
182    MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
183
184#ifndef NDEBUG
185    if (MBB->pred_empty()) {
186      MBB->getParent()->verify();
187      llvm_unreachable("Use not jointly dominated by defs.");
188    }
189
190    if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
191        !MBB->isLiveIn(PhysReg)) {
192      MBB->getParent()->verify();
193      errs() << "The register needs to be live in to BB#" << MBB->getNumber()
194             << ", but is missing from the live-in list.\n";
195      llvm_unreachable("Invalid global physical register");
196    }
197#endif
198
199    for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
200         PE = MBB->pred_end(); PI != PE; ++PI) {
201       MachineBasicBlock *Pred = *PI;
202
203       // Is this a known live-out block?
204       if (Seen.test(Pred->getNumber())) {
205         if (VNInfo *VNI = LiveOut[Pred].first) {
206           if (TheVNI && TheVNI != VNI)
207             UniqueVNI = false;
208           TheVNI = VNI;
209         }
210         continue;
211       }
212
213       SlotIndex Start, End;
214       std::tie(Start, End) = Indexes->getMBBRange(Pred);
215
216       // First time we see Pred.  Try to determine the live-out value, but set
217       // it as null if Pred is live-through with an unknown value.
218       VNInfo *VNI = LR.extendInBlock(Start, End);
219       setLiveOutValue(Pred, VNI);
220       if (VNI) {
221         if (TheVNI && TheVNI != VNI)
222           UniqueVNI = false;
223         TheVNI = VNI;
224         continue;
225       }
226
227       // No, we need a live-in value for Pred as well
228       if (Pred != &KillMBB)
229          WorkList.push_back(Pred->getNumber());
230       else
231          // Loopback to KillMBB, so value is really live through.
232         Kill = SlotIndex();
233    }
234  }
235
236  LiveIn.clear();
237
238  // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
239  // neither require it. Skip the sorting overhead for small updates.
240  if (WorkList.size() > 4)
241    array_pod_sort(WorkList.begin(), WorkList.end());
242
243  // If a unique reaching def was found, blit in the live ranges immediately.
244  if (UniqueVNI) {
245    LiveRangeUpdater Updater(&LR);
246    for (SmallVectorImpl<unsigned>::const_iterator I = WorkList.begin(),
247         E = WorkList.end(); I != E; ++I) {
248       SlotIndex Start, End;
249       std::tie(Start, End) = Indexes->getMBBRange(*I);
250       // Trim the live range in KillMBB.
251       if (*I == KillMBBNum && Kill.isValid())
252         End = Kill;
253       else
254         LiveOut[MF->getBlockNumbered(*I)] =
255           LiveOutPair(TheVNI, nullptr);
256       Updater.add(Start, End, TheVNI);
257    }
258    return true;
259  }
260
261  // Multiple values were found, so transfer the work list to the LiveIn array
262  // where UpdateSSA will use it as a work list.
263  LiveIn.reserve(WorkList.size());
264  for (SmallVectorImpl<unsigned>::const_iterator
265       I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
266    MachineBasicBlock *MBB = MF->getBlockNumbered(*I);
267    addLiveInBlock(LR, DomTree->getNode(MBB));
268    if (MBB == &KillMBB)
269      LiveIn.back().Kill = Kill;
270  }
271
272  return false;
273}
274
275
276// This is essentially the same iterative algorithm that SSAUpdater uses,
277// except we already have a dominator tree, so we don't have to recompute it.
278void LiveRangeCalc::updateSSA() {
279  assert(Indexes && "Missing SlotIndexes");
280  assert(DomTree && "Missing dominator tree");
281
282  // Interate until convergence.
283  unsigned Changes;
284  do {
285    Changes = 0;
286    // Propagate live-out values down the dominator tree, inserting phi-defs
287    // when necessary.
288    for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
289           E = LiveIn.end(); I != E; ++I) {
290      MachineDomTreeNode *Node = I->DomNode;
291      // Skip block if the live-in value has already been determined.
292      if (!Node)
293        continue;
294      MachineBasicBlock *MBB = Node->getBlock();
295      MachineDomTreeNode *IDom = Node->getIDom();
296      LiveOutPair IDomValue;
297
298      // We need a live-in value to a block with no immediate dominator?
299      // This is probably an unreachable block that has survived somehow.
300      bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
301
302      // IDom dominates all of our predecessors, but it may not be their
303      // immediate dominator. Check if any of them have live-out values that are
304      // properly dominated by IDom. If so, we need a phi-def here.
305      if (!needPHI) {
306        IDomValue = LiveOut[IDom->getBlock()];
307
308        // Cache the DomTree node that defined the value.
309        if (IDomValue.first && !IDomValue.second)
310          LiveOut[IDom->getBlock()].second = IDomValue.second =
311            DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
312
313        for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
314               PE = MBB->pred_end(); PI != PE; ++PI) {
315          LiveOutPair &Value = LiveOut[*PI];
316          if (!Value.first || Value.first == IDomValue.first)
317            continue;
318
319          // Cache the DomTree node that defined the value.
320          if (!Value.second)
321            Value.second =
322              DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
323
324          // This predecessor is carrying something other than IDomValue.
325          // It could be because IDomValue hasn't propagated yet, or it could be
326          // because MBB is in the dominance frontier of that value.
327          if (DomTree->dominates(IDom, Value.second)) {
328            needPHI = true;
329            break;
330          }
331        }
332      }
333
334      // The value may be live-through even if Kill is set, as can happen when
335      // we are called from extendRange. In that case LiveOutSeen is true, and
336      // LiveOut indicates a foreign or missing value.
337      LiveOutPair &LOP = LiveOut[MBB];
338
339      // Create a phi-def if required.
340      if (needPHI) {
341        ++Changes;
342        assert(Alloc && "Need VNInfo allocator to create PHI-defs");
343        SlotIndex Start, End;
344        std::tie(Start, End) = Indexes->getMBBRange(MBB);
345        LiveRange &LR = I->LR;
346        VNInfo *VNI = LR.getNextValue(Start, *Alloc);
347        I->Value = VNI;
348        // This block is done, we know the final value.
349        I->DomNode = nullptr;
350
351        // Add liveness since updateLiveIns now skips this node.
352        if (I->Kill.isValid())
353          LR.addSegment(LiveInterval::Segment(Start, I->Kill, VNI));
354        else {
355          LR.addSegment(LiveInterval::Segment(Start, End, VNI));
356          LOP = LiveOutPair(VNI, Node);
357        }
358      } else if (IDomValue.first) {
359        // No phi-def here. Remember incoming value.
360        I->Value = IDomValue.first;
361
362        // If the IDomValue is killed in the block, don't propagate through.
363        if (I->Kill.isValid())
364          continue;
365
366        // Propagate IDomValue if it isn't killed:
367        // MBB is live-out and doesn't define its own value.
368        if (LOP.first == IDomValue.first)
369          continue;
370        ++Changes;
371        LOP = IDomValue;
372      }
373    }
374  } while (Changes);
375}
376