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