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