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