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