LiveVariables.cpp revision a4025df42d2393da7041cd11e48a3d44b0ae2bb1 
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
282/// FindLastRefOrPartRef - Return the last reference or partial reference of
283/// the specified register.
284MachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) {
285  MachineInstr *LastDef = PhysRegDef[Reg];
286  MachineInstr *LastUse = PhysRegUse[Reg];
287  if (!LastDef && !LastUse)
288    return false;
289
290  MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
291  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
292  MachineInstr *LastPartDef = 0;
293  unsigned LastPartDefDist = 0;
294  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
295       unsigned SubReg = *SubRegs; ++SubRegs) {
296    MachineInstr *Def = PhysRegDef[SubReg];
297    if (Def && Def != LastDef) {
298      // There was a def of this sub-register in between. This is a partial
299      // def, keep track of the last one.
300      unsigned Dist = DistanceMap[Def];
301      if (Dist > LastPartDefDist) {
302        LastPartDefDist = Dist;
303        LastPartDef = Def;
304      }
305      continue;
306    }
307    if (MachineInstr *Use = PhysRegUse[SubReg]) {
308      unsigned Dist = DistanceMap[Use];
309      if (Dist > LastRefOrPartRefDist) {
310        LastRefOrPartRefDist = Dist;
311        LastRefOrPartRef = Use;
312      }
313    }
314  }
315
316  return LastRefOrPartRef;
317}
318
319bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) {
320  MachineInstr *LastDef = PhysRegDef[Reg];
321  MachineInstr *LastUse = PhysRegUse[Reg];
322  if (!LastDef && !LastUse)
323    return false;
324
325  MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
326  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
327  // The whole register is used.
328  // AL =
329  // AH =
330  //
331  //    = AX
332  //    = AL, AX<imp-use, kill>
333  // AX =
334  //
335  // Or whole register is defined, but not used at all.
336  // AX<dead> =
337  // ...
338  // AX =
339  //
340  // Or whole register is defined, but only partly used.
341  // AX<dead> = AL<imp-def>
342  //    = AL<kill>
343  // AX =
344  MachineInstr *LastPartDef = 0;
345  unsigned LastPartDefDist = 0;
346  SmallSet<unsigned, 8> PartUses;
347  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
348       unsigned SubReg = *SubRegs; ++SubRegs) {
349    MachineInstr *Def = PhysRegDef[SubReg];
350    if (Def && Def != LastDef) {
351      // There was a def of this sub-register in between. This is a partial
352      // def, keep track of the last one.
353      unsigned Dist = DistanceMap[Def];
354      if (Dist > LastPartDefDist) {
355        LastPartDefDist = Dist;
356        LastPartDef = Def;
357      }
358      continue;
359    }
360    if (MachineInstr *Use = PhysRegUse[SubReg]) {
361      PartUses.insert(SubReg);
362      for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
363        PartUses.insert(*SS);
364      unsigned Dist = DistanceMap[Use];
365      if (Dist > LastRefOrPartRefDist) {
366        LastRefOrPartRefDist = Dist;
367        LastRefOrPartRef = Use;
368      }
369    }
370  }
371
372  if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) {
373    if (LastPartDef)
374      // The last partial def kills the register.
375      LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/,
376                                                true/*IsImp*/, true/*IsKill*/));
377    else {
378      MachineOperand *MO =
379        LastRefOrPartRef->findRegisterDefOperand(Reg, false, TRI);
380      bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg;
381      // If the last reference is the last def, then it's not used at all.
382      // That is, unless we are currently processing the last reference itself.
383      LastRefOrPartRef->addRegisterDead(Reg, TRI, true);
384      if (NeedEC) {
385        // If we are adding a subreg def and the superreg def is marked early
386        // clobber, add an early clobber marker to the subreg def.
387        MO = LastRefOrPartRef->findRegisterDefOperand(Reg);
388        if (MO)
389          MO->setIsEarlyClobber();
390      }
391    }
392  } else if (!PhysRegUse[Reg]) {
393    // Partial uses. Mark register def dead and add implicit def of
394    // sub-registers which are used.
395    // EAX<dead>  = op  AL<imp-def>
396    // That is, EAX def is dead but AL def extends pass it.
397    PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true);
398    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
399         unsigned SubReg = *SubRegs; ++SubRegs) {
400      if (!PartUses.count(SubReg))
401        continue;
402      bool NeedDef = true;
403      if (PhysRegDef[Reg] == PhysRegDef[SubReg]) {
404        MachineOperand *MO = PhysRegDef[Reg]->findRegisterDefOperand(SubReg);
405        if (MO) {
406          NeedDef = false;
407          assert(!MO->isDead());
408        }
409      }
410      if (NeedDef)
411        PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg,
412                                                 true/*IsDef*/, true/*IsImp*/));
413      MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg);
414      if (LastSubRef)
415        LastSubRef->addRegisterKilled(SubReg, TRI, true);
416      else {
417        LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
418        PhysRegUse[SubReg] = LastRefOrPartRef;
419        for (const unsigned *SSRegs = TRI->getSubRegisters(SubReg);
420             unsigned SSReg = *SSRegs; ++SSRegs)
421          PhysRegUse[SSReg] = LastRefOrPartRef;
422      }
423      for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
424        PartUses.erase(*SS);
425    }
426  } else
427    LastRefOrPartRef->addRegisterKilled(Reg, TRI, true);
428  return true;
429}
430
431void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI,
432                                     SmallVector<unsigned, 4> &Defs) {
433  // What parts of the register are previously defined?
434  SmallSet<unsigned, 32> Live;
435  if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
436    Live.insert(Reg);
437    for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS)
438      Live.insert(*SS);
439  } else {
440    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
441         unsigned SubReg = *SubRegs; ++SubRegs) {
442      // If a register isn't itself defined, but all parts that make up of it
443      // are defined, then consider it also defined.
444      // e.g.
445      // AL =
446      // AH =
447      //    = AX
448      if (Live.count(SubReg))
449        continue;
450      if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) {
451        Live.insert(SubReg);
452        for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
453          Live.insert(*SS);
454      }
455    }
456  }
457
458  // Start from the largest piece, find the last time any part of the register
459  // is referenced.
460  HandlePhysRegKill(Reg, MI);
461  // Only some of the sub-registers are used.
462  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
463       unsigned SubReg = *SubRegs; ++SubRegs) {
464    if (!Live.count(SubReg))
465      // Skip if this sub-register isn't defined.
466      continue;
467    HandlePhysRegKill(SubReg, MI);
468  }
469
470  if (MI)
471    Defs.push_back(Reg);  // Remember this def.
472}
473
474void LiveVariables::UpdatePhysRegDefs(MachineInstr *MI,
475                                      SmallVector<unsigned, 4> &Defs) {
476  while (!Defs.empty()) {
477    unsigned Reg = Defs.back();
478    Defs.pop_back();
479    PhysRegDef[Reg]  = MI;
480    PhysRegUse[Reg]  = NULL;
481    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
482         unsigned SubReg = *SubRegs; ++SubRegs) {
483      PhysRegDef[SubReg]  = MI;
484      PhysRegUse[SubReg]  = NULL;
485    }
486  }
487}
488
489namespace {
490  struct RegSorter {
491    const TargetRegisterInfo *TRI;
492
493    RegSorter(const TargetRegisterInfo *tri) : TRI(tri) { }
494    bool operator()(unsigned A, unsigned B) {
495      if (TRI->isSubRegister(A, B))
496        return true;
497      else if (TRI->isSubRegister(B, A))
498        return false;
499      return A < B;
500    }
501  };
502}
503
504bool LiveVariables::runOnMachineFunction(MachineFunction &mf) {
505  MF = &mf;
506  MRI = &mf.getRegInfo();
507  TRI = MF->getTarget().getRegisterInfo();
508
509  ReservedRegisters = TRI->getReservedRegs(mf);
510
511  unsigned NumRegs = TRI->getNumRegs();
512  PhysRegDef  = new MachineInstr*[NumRegs];
513  PhysRegUse  = new MachineInstr*[NumRegs];
514  PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()];
515  std::fill(PhysRegDef,  PhysRegDef  + NumRegs, (MachineInstr*)0);
516  std::fill(PhysRegUse,  PhysRegUse  + NumRegs, (MachineInstr*)0);
517
518  /// Get some space for a respectable number of registers.
519  VirtRegInfo.resize(64);
520
521  analyzePHINodes(mf);
522
523  // Calculate live variable information in depth first order on the CFG of the
524  // function.  This guarantees that we will see the definition of a virtual
525  // register before its uses due to dominance properties of SSA (except for PHI
526  // nodes, which are treated as a special case).
527  MachineBasicBlock *Entry = MF->begin();
528  SmallPtrSet<MachineBasicBlock*,16> Visited;
529
530  for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
531         DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
532       DFI != E; ++DFI) {
533    MachineBasicBlock *MBB = *DFI;
534
535    // Mark live-in registers as live-in.
536    SmallVector<unsigned, 4> Defs;
537    for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(),
538           EE = MBB->livein_end(); II != EE; ++II) {
539      assert(TargetRegisterInfo::isPhysicalRegister(*II) &&
540             "Cannot have a live-in virtual register!");
541      HandlePhysRegDef(*II, 0, Defs);
542    }
543
544    // Loop over all of the instructions, processing them.
545    DistanceMap.clear();
546    unsigned Dist = 0;
547    for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
548         I != E; ++I) {
549      MachineInstr *MI = I;
550      DistanceMap.insert(std::make_pair(MI, Dist++));
551
552      // Process all of the operands of the instruction...
553      unsigned NumOperandsToProcess = MI->getNumOperands();
554
555      // Unless it is a PHI node.  In this case, ONLY process the DEF, not any
556      // of the uses.  They will be handled in other basic blocks.
557      if (MI->getOpcode() == TargetInstrInfo::PHI)
558        NumOperandsToProcess = 1;
559
560      SmallVector<unsigned, 4> UseRegs;
561      SmallVector<unsigned, 4> DefRegs;
562      for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
563        const MachineOperand &MO = MI->getOperand(i);
564        if (!MO.isReg() || MO.getReg() == 0)
565          continue;
566        unsigned MOReg = MO.getReg();
567        if (MO.isUse())
568          UseRegs.push_back(MOReg);
569        if (MO.isDef())
570          DefRegs.push_back(MOReg);
571      }
572
573      // Process all uses.
574      for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) {
575        unsigned MOReg = UseRegs[i];
576        if (TargetRegisterInfo::isVirtualRegister(MOReg))
577          HandleVirtRegUse(MOReg, MBB, MI);
578        else if (!ReservedRegisters[MOReg])
579          HandlePhysRegUse(MOReg, MI);
580      }
581
582      // Process all defs.
583      for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) {
584        unsigned MOReg = DefRegs[i];
585        if (TargetRegisterInfo::isVirtualRegister(MOReg))
586          HandleVirtRegDef(MOReg, MI);
587        else if (!ReservedRegisters[MOReg])
588          HandlePhysRegDef(MOReg, MI, Defs);
589      }
590      UpdatePhysRegDefs(MI, Defs);
591    }
592
593    // Handle any virtual assignments from PHI nodes which might be at the
594    // bottom of this basic block.  We check all of our successor blocks to see
595    // if they have PHI nodes, and if so, we simulate an assignment at the end
596    // of the current block.
597    if (!PHIVarInfo[MBB->getNumber()].empty()) {
598      SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()];
599
600      for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(),
601             E = VarInfoVec.end(); I != E; ++I)
602        // Mark it alive only in the block we are representing.
603        MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(),
604                                MBB);
605    }
606
607    // Finally, if the last instruction in the block is a return, make sure to
608    // mark it as using all of the live-out values in the function.
609    if (!MBB->empty() && MBB->back().getDesc().isReturn()) {
610      MachineInstr *Ret = &MBB->back();
611
612      for (MachineRegisterInfo::liveout_iterator
613           I = MF->getRegInfo().liveout_begin(),
614           E = MF->getRegInfo().liveout_end(); I != E; ++I) {
615        assert(TargetRegisterInfo::isPhysicalRegister(*I) &&
616               "Cannot have a live-out virtual register!");
617        HandlePhysRegUse(*I, Ret);
618
619        // Add live-out registers as implicit uses.
620        if (!Ret->readsRegister(*I))
621          Ret->addOperand(MachineOperand::CreateReg(*I, false, true));
622      }
623    }
624
625    // Loop over PhysRegDef / PhysRegUse, killing any registers that are
626    // available at the end of the basic block.
627    for (unsigned i = 0; i != NumRegs; ++i)
628      if (PhysRegDef[i] || PhysRegUse[i])
629        HandlePhysRegDef(i, 0, Defs);
630
631    std::fill(PhysRegDef,  PhysRegDef  + NumRegs, (MachineInstr*)0);
632    std::fill(PhysRegUse,  PhysRegUse  + NumRegs, (MachineInstr*)0);
633  }
634
635  // Convert and transfer the dead / killed information we have gathered into
636  // VirtRegInfo onto MI's.
637  for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i)
638    for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j)
639      if (VirtRegInfo[i].Kills[j] ==
640          MRI->getVRegDef(i + TargetRegisterInfo::FirstVirtualRegister))
641        VirtRegInfo[i]
642          .Kills[j]->addRegisterDead(i +
643                                     TargetRegisterInfo::FirstVirtualRegister,
644                                     TRI);
645      else
646        VirtRegInfo[i]
647          .Kills[j]->addRegisterKilled(i +
648                                       TargetRegisterInfo::FirstVirtualRegister,
649                                       TRI);
650
651  // Check to make sure there are no unreachable blocks in the MC CFG for the
652  // function.  If so, it is due to a bug in the instruction selector or some
653  // other part of the code generator if this happens.
654#ifndef NDEBUG
655  for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i)
656    assert(Visited.count(&*i) != 0 && "unreachable basic block found");
657#endif
658
659  delete[] PhysRegDef;
660  delete[] PhysRegUse;
661  delete[] PHIVarInfo;
662
663  return false;
664}
665
666/// replaceKillInstruction - Update register kill info by replacing a kill
667/// instruction with a new one.
668void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI,
669                                           MachineInstr *NewMI) {
670  VarInfo &VI = getVarInfo(Reg);
671  std::replace(VI.Kills.begin(), VI.Kills.end(), OldMI, NewMI);
672}
673
674/// removeVirtualRegistersKilled - Remove all killed info for the specified
675/// instruction.
676void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) {
677  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
678    MachineOperand &MO = MI->getOperand(i);
679    if (MO.isReg() && MO.isKill()) {
680      MO.setIsKill(false);
681      unsigned Reg = MO.getReg();
682      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
683        bool removed = getVarInfo(Reg).removeKill(MI);
684        assert(removed && "kill not in register's VarInfo?");
685        removed = true;
686      }
687    }
688  }
689}
690
691/// analyzePHINodes - Gather information about the PHI nodes in here. In
692/// particular, we want to map the variable information of a virtual register
693/// which is used in a PHI node. We map that to the BB the vreg is coming from.
694///
695void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
696  for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end();
697       I != E; ++I)
698    for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
699         BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
700      for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
701        PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()]
702          .push_back(BBI->getOperand(i).getReg());
703}
704
705bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB,
706                                      unsigned Reg,
707                                      MachineRegisterInfo &MRI) {
708  unsigned Num = MBB.getNumber();
709
710  // Reg is live-through.
711  if (AliveBlocks.test(Num))
712    return true;
713
714  // Registers defined in MBB cannot be live in.
715  const MachineInstr *Def = MRI.getVRegDef(Reg);
716  if (Def && Def->getParent() == &MBB)
717    return false;
718
719 // Reg was not defined in MBB, was it killed here?
720  return findKill(&MBB);
721}
722
723/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
724/// variables that are live out of DomBB will be marked as passing live through
725/// BB.
726void LiveVariables::addNewBlock(MachineBasicBlock *BB,
727                                MachineBasicBlock *DomBB,
728                                MachineBasicBlock *SuccBB) {
729  const unsigned NumNew = BB->getNumber();
730
731  // All registers used by PHI nodes in SuccBB must be live through BB.
732  for (MachineBasicBlock::const_iterator BBI = SuccBB->begin(),
733         BBE = SuccBB->end();
734       BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
735    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
736      if (BBI->getOperand(i+1).getMBB() == BB)
737        getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
738
739  // Update info for all live variables
740  for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister,
741         E = MRI->getLastVirtReg()+1; Reg != E; ++Reg) {
742    VarInfo &VI = getVarInfo(Reg);
743    if (!VI.AliveBlocks.test(NumNew) && VI.isLiveIn(*SuccBB, Reg, *MRI))
744      VI.AliveBlocks.set(NumNew);
745  }
746}
747