LiveVariables.cpp revision bffdf66b8050b45188cb265f27e81c41277ab0ca 
1//===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===//
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// This file implements the LiveVariable analysis pass.  For each machine
11// instruction in the function, this pass calculates the set of registers that
12// are immediately dead after the instruction (i.e., the instruction calculates
13// the value, but it is never used) and the set of registers that are used by
14// the instruction, but are never used after the instruction (i.e., they are
15// killed).
16//
17// This class computes live variables using are sparse implementation based on
18// the machine code SSA form.  This class computes live variable information for
19// each virtual and _register allocatable_ physical register in a function.  It
20// uses the dominance properties of SSA form to efficiently compute live
21// variables for virtual registers, and assumes that physical registers are only
22// live within a single basic block (allowing it to do a single local analysis
23// to resolve physical register lifetimes in each basic block).  If a physical
24// register is not register allocatable, it is not tracked.  This is useful for
25// things like the stack pointer and condition codes.
26//
27//===----------------------------------------------------------------------===//
28
29#include "llvm/CodeGen/LiveVariables.h"
30#include "llvm/CodeGen/MachineInstr.h"
31#include "llvm/CodeGen/MachineRegisterInfo.h"
32#include "llvm/Target/TargetRegisterInfo.h"
33#include "llvm/Target/TargetInstrInfo.h"
34#include "llvm/Target/TargetMachine.h"
35#include "llvm/ADT/DepthFirstIterator.h"
36#include "llvm/ADT/SmallPtrSet.h"
37#include "llvm/ADT/SmallSet.h"
38#include "llvm/ADT/STLExtras.h"
39#include "llvm/Config/alloca.h"
40#include <algorithm>
41using namespace llvm;
42
43char LiveVariables::ID = 0;
44static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis");
45
46void LiveVariables::VarInfo::dump() const {
47  cerr << "  Alive in blocks: ";
48  for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i)
49    if (AliveBlocks[i]) cerr << i << ", ";
50  cerr << "  Used in blocks: ";
51  for (unsigned i = 0, e = UsedBlocks.size(); i != e; ++i)
52    if (UsedBlocks[i]) cerr << i << ", ";
53  cerr << "\n  Killed by:";
54  if (Kills.empty())
55    cerr << " No instructions.\n";
56  else {
57    for (unsigned i = 0, e = Kills.size(); i != e; ++i)
58      cerr << "\n    #" << i << ": " << *Kills[i];
59    cerr << "\n";
60  }
61}
62
63/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg.
64LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) {
65  assert(TargetRegisterInfo::isVirtualRegister(RegIdx) &&
66         "getVarInfo: not a virtual register!");
67  RegIdx -= TargetRegisterInfo::FirstVirtualRegister;
68  if (RegIdx >= VirtRegInfo.size()) {
69    if (RegIdx >= 2*VirtRegInfo.size())
70      VirtRegInfo.resize(RegIdx*2);
71    else
72      VirtRegInfo.resize(2*VirtRegInfo.size());
73  }
74  VarInfo &VI = VirtRegInfo[RegIdx];
75  VI.AliveBlocks.resize(MF->getNumBlockIDs());
76  VI.UsedBlocks.resize(MF->getNumBlockIDs());
77  return VI;
78}
79
80void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo,
81                                            MachineBasicBlock *DefBlock,
82                                            MachineBasicBlock *MBB,
83                                    std::vector<MachineBasicBlock*> &WorkList) {
84  unsigned BBNum = MBB->getNumber();
85
86  // Check to see if this basic block is one of the killing blocks.  If so,
87  // remove it.
88  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
89    if (VRInfo.Kills[i]->getParent() == MBB) {
90      VRInfo.Kills.erase(VRInfo.Kills.begin()+i);  // Erase entry
91      break;
92    }
93
94  if (MBB == DefBlock) return;  // Terminate recursion
95
96  if (VRInfo.AliveBlocks[BBNum])
97    return;  // We already know the block is live
98
99  // Mark the variable known alive in this bb
100  VRInfo.AliveBlocks[BBNum] = true;
101
102  for (MachineBasicBlock::const_pred_reverse_iterator PI = MBB->pred_rbegin(),
103         E = MBB->pred_rend(); PI != E; ++PI)
104    WorkList.push_back(*PI);
105}
106
107void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
108                                            MachineBasicBlock *DefBlock,
109                                            MachineBasicBlock *MBB) {
110  std::vector<MachineBasicBlock*> WorkList;
111  MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList);
112
113  while (!WorkList.empty()) {
114    MachineBasicBlock *Pred = WorkList.back();
115    WorkList.pop_back();
116    MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList);
117  }
118}
119
120void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB,
121                                     MachineInstr *MI) {
122  assert(MRI->getVRegDef(reg) && "Register use before def!");
123
124  unsigned BBNum = MBB->getNumber();
125
126  VarInfo& VRInfo = getVarInfo(reg);
127  VRInfo.UsedBlocks[BBNum] = true;
128  VRInfo.NumUses++;
129
130  // Check to see if this basic block is already a kill block.
131  if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) {
132    // Yes, this register is killed in this basic block already. Increase the
133    // live range by updating the kill instruction.
134    VRInfo.Kills.back() = MI;
135    return;
136  }
137
138#ifndef NDEBUG
139  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
140    assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!");
141#endif
142
143  // This situation can occur:
144  //
145  //     ,------.
146  //     |      |
147  //     |      v
148  //     |   t2 = phi ... t1 ...
149  //     |      |
150  //     |      v
151  //     |   t1 = ...
152  //     |  ... = ... t1 ...
153  //     |      |
154  //     `------'
155  //
156  // where there is a use in a PHI node that's a predecessor to the defining
157  // block. We don't want to mark all predecessors as having the value "alive"
158  // in this case.
159  if (MBB == MRI->getVRegDef(reg)->getParent()) return;
160
161  // Add a new kill entry for this basic block. If this virtual register is
162  // already marked as alive in this basic block, that means it is alive in at
163  // least one of the successor blocks, it's not a kill.
164  if (!VRInfo.AliveBlocks[BBNum])
165    VRInfo.Kills.push_back(MI);
166
167  // Update all dominating blocks to mark them as "known live".
168  for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
169         E = MBB->pred_end(); PI != E; ++PI)
170    MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI);
171}
172
173/// FindLastPartialDef - Return the last partial def of the specified register.
174/// Also returns the sub-register that's defined.
175MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg,
176                                                unsigned &PartDefReg) {
177  unsigned LastDefReg = 0;
178  unsigned LastDefDist = 0;
179  MachineInstr *LastDef = NULL;
180  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
181       unsigned SubReg = *SubRegs; ++SubRegs) {
182    MachineInstr *Def = PhysRegDef[SubReg];
183    if (!Def)
184      continue;
185    unsigned Dist = DistanceMap[Def];
186    if (Dist > LastDefDist) {
187      LastDefReg  = SubReg;
188      LastDef     = Def;
189      LastDefDist = Dist;
190    }
191  }
192  PartDefReg = LastDefReg;
193  return LastDef;
194}
195
196/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add
197/// implicit defs to a machine instruction if there was an earlier def of its
198/// super-register.
199void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) {
200  // If there was a previous use or a "full" def all is well.
201  if (!PhysRegDef[Reg] && !PhysRegUse[Reg]) {
202    // Otherwise, the last sub-register def implicitly defines this register.
203    // e.g.
204    // AH =
205    // AL = ... <imp-def EAX>, <imp-kill AH>
206    //    = AH
207    // ...
208    //    = EAX
209    // All of the sub-registers must have been defined before the use of Reg!
210    unsigned PartDefReg = 0;
211    MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefReg);
212    // If LastPartialDef is NULL, it must be using a livein register.
213    if (LastPartialDef) {
214      LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
215                                                           true/*IsImp*/));
216      PhysRegDef[Reg] = LastPartialDef;
217      std::set<unsigned> Processed;
218      for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
219           unsigned SubReg = *SubRegs; ++SubRegs) {
220        if (Processed.count(SubReg))
221          continue;
222        if (SubReg == PartDefReg || TRI->isSubRegister(PartDefReg, SubReg))
223          continue;
224        // This part of Reg was defined before the last partial def. It's killed
225        // here.
226        LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg,
227                                                             false/*IsDef*/,
228                                                             true/*IsImp*/));
229        PhysRegDef[SubReg] = LastPartialDef;
230        for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
231          Processed.insert(*SS);
232      }
233    }
234  }
235
236  // There was an earlier def of a super-register. Add implicit def to that MI.
237  //
238  //   A: EAX = ...
239  //   B: ... = AX
240  //
241  // Add implicit def to A if there isn't a use of AX (or EAX) before B.
242  if (!PhysRegUse[Reg]) {
243    MachineInstr *Def = PhysRegDef[Reg];
244    if (Def && !Def->modifiesRegister(Reg))
245      Def->addOperand(MachineOperand::CreateReg(Reg,
246                                                true  /*IsDef*/,
247                                                true  /*IsImp*/));
248  }
249
250  // Remember this use.
251  PhysRegUse[Reg]  = MI;
252  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
253       unsigned SubReg = *SubRegs; ++SubRegs)
254    PhysRegUse[SubReg] =  MI;
255}
256
257/// hasRegisterUseBelow - Return true if the specified register is used after
258/// the current instruction and before it's next definition.
259bool LiveVariables::hasRegisterUseBelow(unsigned Reg,
260                                        MachineBasicBlock::iterator I,
261                                        MachineBasicBlock *MBB) {
262  if (I == MBB->end())
263    return false;
264
265  // First find out if there are any uses / defs below.
266  bool hasDistInfo = true;
267  unsigned CurDist = DistanceMap[I];
268  SmallVector<MachineInstr*, 4> Uses;
269  SmallVector<MachineInstr*, 4> Defs;
270  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
271         RE = MRI->reg_end(); RI != RE; ++RI) {
272    MachineOperand &UDO = RI.getOperand();
273    MachineInstr *UDMI = &*RI;
274    if (UDMI->getParent() != MBB)
275      continue;
276    DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
277    bool isBelow = false;
278    if (DI == DistanceMap.end()) {
279      // Must be below if it hasn't been assigned a distance yet.
280      isBelow = true;
281      hasDistInfo = false;
282    } else if (DI->second > CurDist)
283      isBelow = true;
284    if (isBelow) {
285      if (UDO.isUse())
286        Uses.push_back(UDMI);
287      if (UDO.isDef())
288        Defs.push_back(UDMI);
289    }
290  }
291
292  if (Uses.empty())
293    // No uses below.
294    return false;
295  else if (!Uses.empty() && Defs.empty())
296    // There are uses below but no defs below.
297    return true;
298  // There are both uses and defs below. We need to know which comes first.
299  if (!hasDistInfo) {
300    // Complete DistanceMap for this MBB. This information is computed only
301    // once per MBB.
302    ++I;
303    ++CurDist;
304    for (MachineBasicBlock::iterator E = MBB->end(); I != E; ++I, ++CurDist)
305      DistanceMap.insert(std::make_pair(I, CurDist));
306  }
307
308  unsigned EarliestUse = DistanceMap[Uses[0]];
309  for (unsigned i = 1, e = Uses.size(); i != e; ++i) {
310    unsigned Dist = DistanceMap[Uses[i]];
311    if (Dist < EarliestUse)
312      EarliestUse = Dist;
313  }
314  for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
315    unsigned Dist = DistanceMap[Defs[i]];
316    if (Dist < EarliestUse)
317      // The register is defined before its first use below.
318      return false;
319  }
320  return true;
321}
322
323bool LiveVariables::HandlePhysRegKill(unsigned Reg) {
324  if (!PhysRegUse[Reg] && !PhysRegDef[Reg])
325    return false;
326
327  MachineInstr *LastRefOrPartRef = PhysRegUse[Reg]
328    ? PhysRegUse[Reg] : PhysRegDef[Reg];
329  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
330  // The whole register is used.
331  // AL =
332  // AH =
333  //
334  //    = AX
335  //    = AL, AX<imp-use, kill>
336  // AX =
337  //
338  // Or whole register is defined, but not used at all.
339  // AX<dead> =
340  // ...
341  // AX =
342  //
343  // Or whole register is defined, but only partly used.
344  // AX<dead> = AL<imp-def>
345  //    = AL<kill>
346  // AX =
347  std::set<unsigned> PartUses;
348  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
349       unsigned SubReg = *SubRegs; ++SubRegs) {
350    if (MachineInstr *Use = PhysRegUse[SubReg]) {
351      PartUses.insert(SubReg);
352      for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
353        PartUses.insert(*SS);
354      unsigned Dist = DistanceMap[Use];
355      if (Dist > LastRefOrPartRefDist) {
356        LastRefOrPartRefDist = Dist;
357        LastRefOrPartRef = Use;
358      }
359    }
360  }
361  if (LastRefOrPartRef == PhysRegDef[Reg])
362    // Not used at all.
363    LastRefOrPartRef->addRegisterDead(Reg, TRI, true);
364
365  /* Partial uses. Mark register def dead and add implicit def of
366     sub-registers which are used.
367    FIXME: LiveIntervalAnalysis can't handle this yet!
368    EAX<dead>  = op  AL<imp-def>
369    That is, EAX def is dead but AL def extends pass it.
370    Enable this after live interval analysis is fixed to improve codegen!
371  else if (!PhysRegUse[Reg]) {
372    PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true);
373    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
374         unsigned SubReg = *SubRegs; ++SubRegs) {
375      if (PartUses.count(SubReg)) {
376        PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg,
377                                                              true, true));
378        LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
379        for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
380          PartUses.erase(*SS);
381      }
382    }
383  } */
384  else
385    LastRefOrPartRef->addRegisterKilled(Reg, TRI, true);
386  return true;
387}
388
389void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) {
390  // What parts of the register are previously defined?
391  SmallSet<unsigned, 32> Live;
392  if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
393    Live.insert(Reg);
394    for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS)
395      Live.insert(*SS);
396  } else {
397    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
398         unsigned SubReg = *SubRegs; ++SubRegs) {
399      // If a register isn't itself defined, but all parts that make up of it
400      // are defined, then consider it also defined.
401      // e.g.
402      // AL =
403      // AH =
404      //    = AX
405      if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) {
406        Live.insert(SubReg);
407        for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
408          Live.insert(*SS);
409      }
410    }
411  }
412
413  // Start from the largest piece, find the last time any part of the register
414  // is referenced.
415  if (!HandlePhysRegKill(Reg)) {
416    // Only some of the sub-registers are used.
417    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
418         unsigned SubReg = *SubRegs; ++SubRegs) {
419      if (!Live.count(SubReg))
420        // Skip if this sub-register isn't defined.
421        continue;
422      if (HandlePhysRegKill(SubReg)) {
423        Live.erase(SubReg);
424        for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
425          Live.erase(*SS);
426      }
427    }
428    assert(Live.empty() && "Not all defined registers are killed / dead?");
429  }
430
431  if (MI) {
432    // Does this extend the live range of a super-register?
433    std::set<unsigned> Processed;
434    for (const unsigned *SuperRegs = TRI->getSuperRegisters(Reg);
435         unsigned SuperReg = *SuperRegs; ++SuperRegs) {
436      if (Processed.count(SuperReg))
437        continue;
438      MachineInstr *LastRef = PhysRegUse[SuperReg]
439        ? PhysRegUse[SuperReg] : PhysRegDef[SuperReg];
440      if (LastRef && LastRef != MI) {
441        // The larger register is previously defined. Now a smaller part is
442        // being re-defined. Treat it as read/mod/write if there are uses
443        // below.
444        // EAX =
445        // AX  =        EAX<imp-use,kill>, EAX<imp-def>
446        // ...
447        ///    =  EAX
448        if (hasRegisterUseBelow(SuperReg, MI, MI->getParent())) {
449          MI->addOperand(MachineOperand::CreateReg(SuperReg, false/*IsDef*/,
450                                                   true/*IsImp*/,true/*IsKill*/));
451          MI->addOperand(MachineOperand::CreateReg(SuperReg, true/*IsDef*/,
452                                                   true/*IsImp*/));
453          PhysRegDef[SuperReg]  = MI;
454          PhysRegUse[SuperReg]  = NULL;
455          Processed.insert(SuperReg);
456          for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) {
457            PhysRegDef[*SS]  = MI;
458            PhysRegUse[*SS]  = NULL;
459            Processed.insert(*SS);
460          }
461        } else {
462          // Otherwise, the super register is killed.
463          if (HandlePhysRegKill(SuperReg)) {
464            PhysRegDef[SuperReg]  = NULL;
465            PhysRegUse[SuperReg]  = NULL;
466            for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) {
467              PhysRegDef[*SS]  = NULL;
468              PhysRegUse[*SS]  = NULL;
469              Processed.insert(*SS);
470            }
471          }
472        }
473      }
474    }
475
476    // Remember this def.
477    PhysRegDef[Reg]  = MI;
478    PhysRegUse[Reg]  = NULL;
479    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
480         unsigned SubReg = *SubRegs; ++SubRegs) {
481      PhysRegDef[SubReg]  = MI;
482      PhysRegUse[SubReg]  = NULL;
483    }
484  }
485}
486
487bool LiveVariables::runOnMachineFunction(MachineFunction &mf) {
488  MF = &mf;
489  MRI = &mf.getRegInfo();
490  TRI = MF->getTarget().getRegisterInfo();
491
492  ReservedRegisters = TRI->getReservedRegs(mf);
493
494  unsigned NumRegs = TRI->getNumRegs();
495  PhysRegDef  = new MachineInstr*[NumRegs];
496  PhysRegUse  = new MachineInstr*[NumRegs];
497  PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()];
498  std::fill(PhysRegDef,  PhysRegDef  + NumRegs, (MachineInstr*)0);
499  std::fill(PhysRegUse,  PhysRegUse  + NumRegs, (MachineInstr*)0);
500
501  /// Get some space for a respectable number of registers.
502  VirtRegInfo.resize(64);
503
504  analyzePHINodes(mf);
505
506  // Calculate live variable information in depth first order on the CFG of the
507  // function.  This guarantees that we will see the definition of a virtual
508  // register before its uses due to dominance properties of SSA (except for PHI
509  // nodes, which are treated as a special case).
510  MachineBasicBlock *Entry = MF->begin();
511  SmallPtrSet<MachineBasicBlock*,16> Visited;
512
513  for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
514         DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
515       DFI != E; ++DFI) {
516    MachineBasicBlock *MBB = *DFI;
517
518    // Mark live-in registers as live-in.
519    for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(),
520           EE = MBB->livein_end(); II != EE; ++II) {
521      assert(TargetRegisterInfo::isPhysicalRegister(*II) &&
522             "Cannot have a live-in virtual register!");
523      HandlePhysRegDef(*II, 0);
524    }
525
526    // Loop over all of the instructions, processing them.
527    DistanceMap.clear();
528    unsigned Dist = 0;
529    for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
530         I != E; ++I) {
531      MachineInstr *MI = I;
532      DistanceMap.insert(std::make_pair(MI, Dist++));
533
534      // Process all of the operands of the instruction...
535      unsigned NumOperandsToProcess = MI->getNumOperands();
536
537      // Unless it is a PHI node.  In this case, ONLY process the DEF, not any
538      // of the uses.  They will be handled in other basic blocks.
539      if (MI->getOpcode() == TargetInstrInfo::PHI)
540        NumOperandsToProcess = 1;
541
542      SmallVector<unsigned, 4> UseRegs;
543      SmallVector<unsigned, 4> DefRegs;
544      for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
545        const MachineOperand &MO = MI->getOperand(i);
546        if (MO.isRegister() && MO.getReg()) {
547          unsigned MOReg = MO.getReg();
548          if (!MOReg)
549            continue;
550          if (MO.isUse())
551            UseRegs.push_back(MOReg);
552          if (MO.isDef())
553            DefRegs.push_back(MOReg);
554        }
555      }
556
557      // Process all uses.
558      for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) {
559        unsigned MOReg = UseRegs[i];
560        if (TargetRegisterInfo::isVirtualRegister(MOReg))
561          HandleVirtRegUse(MOReg, MBB, MI);
562        else if (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
563                 !ReservedRegisters[MOReg])
564          HandlePhysRegUse(MOReg, MI);
565      }
566
567      // Process all defs.
568      for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) {
569        unsigned MOReg = DefRegs[i];
570        if (TargetRegisterInfo::isVirtualRegister(MOReg)) {
571          VarInfo &VRInfo = getVarInfo(MOReg);
572
573          if (VRInfo.AliveBlocks.none())
574            // If vr is not alive in any block, then defaults to dead.
575            VRInfo.Kills.push_back(MI);
576        } else if (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
577                   !ReservedRegisters[MOReg]) {
578          HandlePhysRegDef(MOReg, MI);
579        }
580      }
581    }
582
583    // Handle any virtual assignments from PHI nodes which might be at the
584    // bottom of this basic block.  We check all of our successor blocks to see
585    // if they have PHI nodes, and if so, we simulate an assignment at the end
586    // of the current block.
587    if (!PHIVarInfo[MBB->getNumber()].empty()) {
588      SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()];
589
590      for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(),
591             E = VarInfoVec.end(); I != E; ++I)
592        // Mark it alive only in the block we are representing.
593        MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(),
594                                MBB);
595    }
596
597    // Finally, if the last instruction in the block is a return, make sure to
598    // mark it as using all of the live-out values in the function.
599    if (!MBB->empty() && MBB->back().getDesc().isReturn()) {
600      MachineInstr *Ret = &MBB->back();
601
602      for (MachineRegisterInfo::liveout_iterator
603           I = MF->getRegInfo().liveout_begin(),
604           E = MF->getRegInfo().liveout_end(); I != E; ++I) {
605        assert(TargetRegisterInfo::isPhysicalRegister(*I) &&
606               "Cannot have a live-out virtual register!");
607        HandlePhysRegUse(*I, Ret);
608
609        // Add live-out registers as implicit uses.
610        if (!Ret->readsRegister(*I))
611          Ret->addOperand(MachineOperand::CreateReg(*I, false, true));
612      }
613    }
614
615    // Loop over PhysRegDef / PhysRegUse, killing any registers that are
616    // available at the end of the basic block.
617    for (unsigned i = 0; i != NumRegs; ++i)
618      if (PhysRegDef[i] || PhysRegUse[i])
619        HandlePhysRegDef(i, 0);
620
621    std::fill(PhysRegDef,  PhysRegDef  + NumRegs, (MachineInstr*)0);
622    std::fill(PhysRegUse,  PhysRegUse  + NumRegs, (MachineInstr*)0);
623  }
624
625  // Convert and transfer the dead / killed information we have gathered into
626  // VirtRegInfo onto MI's.
627  for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i)
628    for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j)
629      if (VirtRegInfo[i].Kills[j] ==
630          MRI->getVRegDef(i + TargetRegisterInfo::FirstVirtualRegister))
631        VirtRegInfo[i]
632          .Kills[j]->addRegisterDead(i +
633                                     TargetRegisterInfo::FirstVirtualRegister,
634                                     TRI);
635      else
636        VirtRegInfo[i]
637          .Kills[j]->addRegisterKilled(i +
638                                       TargetRegisterInfo::FirstVirtualRegister,
639                                       TRI);
640
641  // Check to make sure there are no unreachable blocks in the MC CFG for the
642  // function.  If so, it is due to a bug in the instruction selector or some
643  // other part of the code generator if this happens.
644#ifndef NDEBUG
645  for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i)
646    assert(Visited.count(&*i) != 0 && "unreachable basic block found");
647#endif
648
649  delete[] PhysRegDef;
650  delete[] PhysRegUse;
651  delete[] PHIVarInfo;
652
653  return false;
654}
655
656/// instructionChanged - When the address of an instruction changes, this method
657/// should be called so that live variables can update its internal data
658/// structures.  This removes the records for OldMI, transfering them to the
659/// records for NewMI.
660void LiveVariables::instructionChanged(MachineInstr *OldMI,
661                                       MachineInstr *NewMI) {
662  // If the instruction defines any virtual registers, update the VarInfo,
663  // kill and dead information for the instruction.
664  for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) {
665    MachineOperand &MO = OldMI->getOperand(i);
666    if (MO.isRegister() && MO.getReg() &&
667        TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
668      unsigned Reg = MO.getReg();
669      VarInfo &VI = getVarInfo(Reg);
670      if (MO.isDef()) {
671        if (MO.isDead()) {
672          MO.setIsDead(false);
673          addVirtualRegisterDead(Reg, NewMI);
674        }
675      }
676      if (MO.isKill()) {
677        MO.setIsKill(false);
678        addVirtualRegisterKilled(Reg, NewMI);
679      }
680      // If this is a kill of the value, update the VI kills list.
681      if (VI.removeKill(OldMI))
682        VI.Kills.push_back(NewMI);   // Yes, there was a kill of it
683    }
684  }
685}
686
687/// removeVirtualRegistersKilled - Remove all killed info for the specified
688/// instruction.
689void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) {
690  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
691    MachineOperand &MO = MI->getOperand(i);
692    if (MO.isRegister() && MO.isKill()) {
693      MO.setIsKill(false);
694      unsigned Reg = MO.getReg();
695      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
696        bool removed = getVarInfo(Reg).removeKill(MI);
697        assert(removed && "kill not in register's VarInfo?");
698      }
699    }
700  }
701}
702
703/// removeVirtualRegistersDead - Remove all of the dead registers for the
704/// specified instruction from the live variable information.
705void LiveVariables::removeVirtualRegistersDead(MachineInstr *MI) {
706  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
707    MachineOperand &MO = MI->getOperand(i);
708    if (MO.isRegister() && MO.isDead()) {
709      MO.setIsDead(false);
710      unsigned Reg = MO.getReg();
711      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
712        bool removed = getVarInfo(Reg).removeKill(MI);
713        assert(removed && "kill not in register's VarInfo?");
714      }
715    }
716  }
717}
718
719/// analyzePHINodes - Gather information about the PHI nodes in here. In
720/// particular, we want to map the variable information of a virtual register
721/// which is used in a PHI node. We map that to the BB the vreg is coming from.
722///
723void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
724  for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end();
725       I != E; ++I)
726    for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
727         BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
728      for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
729        PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()]
730          .push_back(BBI->getOperand(i).getReg());
731}
732