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