LLVM  10.0.0svn
LiveVariables.cpp
Go to the documentation of this file.
1 //===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the LiveVariable analysis pass. For each machine
10 // instruction in the function, this pass calculates the set of registers that
11 // are immediately dead after the instruction (i.e., the instruction calculates
12 // the value, but it is never used) and the set of registers that are used by
13 // the instruction, but are never used after the instruction (i.e., they are
14 // killed).
15 //
16 // This class computes live variables using a sparse implementation based on
17 // the machine code SSA form. This class computes live variable information for
18 // each virtual and _register allocatable_ physical register in a function. It
19 // uses the dominance properties of SSA form to efficiently compute live
20 // variables for virtual registers, and assumes that physical registers are only
21 // live within a single basic block (allowing it to do a single local analysis
22 // to resolve physical register lifetimes in each basic block). If a physical
23 // register is not register allocatable, it is not tracked. This is useful for
24 // things like the stack pointer and condition codes.
25 //
26 //===----------------------------------------------------------------------===//
27 
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/ADT/SmallPtrSet.h"
32 #include "llvm/ADT/SmallSet.h"
35 #include "llvm/CodeGen/Passes.h"
36 #include "llvm/Config/llvm-config.h"
37 #include "llvm/Support/Debug.h"
40 #include <algorithm>
41 using namespace llvm;
42 
43 char LiveVariables::ID = 0;
46  "Live Variable Analysis", false, false)
47 INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElim)
49  "Live Variable Analysis", false, false)
50 
51 
52 void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const {
53  AU.addRequiredID(UnreachableMachineBlockElimID);
54  AU.setPreservesAll();
56 }
57 
60  for (unsigned i = 0, e = Kills.size(); i != e; ++i)
61  if (Kills[i]->getParent() == MBB)
62  return Kills[i];
63  return nullptr;
64 }
65 
66 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
68  dbgs() << " Alive in blocks: ";
70  E = AliveBlocks.end(); I != E; ++I)
71  dbgs() << *I << ", ";
72  dbgs() << "\n Killed by:";
73  if (Kills.empty())
74  dbgs() << " No instructions.\n";
75  else {
76  for (unsigned i = 0, e = Kills.size(); i != e; ++i)
77  dbgs() << "\n #" << i << ": " << *Kills[i];
78  dbgs() << "\n";
79  }
80 }
81 #endif
82 
83 /// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg.
86  "getVarInfo: not a virtual register!");
87  VirtRegInfo.grow(RegIdx);
88  return VirtRegInfo[RegIdx];
89 }
90 
92  MachineBasicBlock *DefBlock,
93  MachineBasicBlock *MBB,
94  std::vector<MachineBasicBlock*> &WorkList) {
95  unsigned BBNum = MBB->getNumber();
96 
97  // Check to see if this basic block is one of the killing blocks. If so,
98  // remove it.
99  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
100  if (VRInfo.Kills[i]->getParent() == MBB) {
101  VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry
102  break;
103  }
104 
105  if (MBB == DefBlock) return; // Terminate recursion
106 
107  if (VRInfo.AliveBlocks.test(BBNum))
108  return; // We already know the block is live
109 
110  // Mark the variable known alive in this bb
111  VRInfo.AliveBlocks.set(BBNum);
112 
113  assert(MBB != &MF->front() && "Can't find reaching def for virtreg");
114  WorkList.insert(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend());
115 }
116 
118  MachineBasicBlock *DefBlock,
119  MachineBasicBlock *MBB) {
120  std::vector<MachineBasicBlock*> WorkList;
121  MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList);
122 
123  while (!WorkList.empty()) {
124  MachineBasicBlock *Pred = WorkList.back();
125  WorkList.pop_back();
126  MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList);
127  }
128 }
129 
131  MachineInstr &MI) {
132  assert(MRI->getVRegDef(reg) && "Register use before def!");
133 
134  unsigned BBNum = MBB->getNumber();
135 
136  VarInfo& VRInfo = getVarInfo(reg);
137 
138  // Check to see if this basic block is already a kill block.
139  if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) {
140  // Yes, this register is killed in this basic block already. Increase the
141  // live range by updating the kill instruction.
142  VRInfo.Kills.back() = &MI;
143  return;
144  }
145 
146 #ifndef NDEBUG
147  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
148  assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!");
149 #endif
150 
151  // This situation can occur:
152  //
153  // ,------.
154  // | |
155  // | v
156  // | t2 = phi ... t1 ...
157  // | |
158  // | v
159  // | t1 = ...
160  // | ... = ... t1 ...
161  // | |
162  // `------'
163  //
164  // where there is a use in a PHI node that's a predecessor to the defining
165  // block. We don't want to mark all predecessors as having the value "alive"
166  // in this case.
167  if (MBB == MRI->getVRegDef(reg)->getParent()) return;
168 
169  // Add a new kill entry for this basic block. If this virtual register is
170  // already marked as alive in this basic block, that means it is alive in at
171  // least one of the successor blocks, it's not a kill.
172  if (!VRInfo.AliveBlocks.test(BBNum))
173  VRInfo.Kills.push_back(&MI);
174 
175  // Update all dominating blocks to mark them as "known live".
177  E = MBB->pred_end(); PI != E; ++PI)
178  MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI);
179 }
180 
182  VarInfo &VRInfo = getVarInfo(Reg);
183 
184  if (VRInfo.AliveBlocks.empty())
185  // If vr is not alive in any block, then defaults to dead.
186  VRInfo.Kills.push_back(&MI);
187 }
188 
189 /// FindLastPartialDef - Return the last partial def of the specified register.
190 /// Also returns the sub-registers that're defined by the instruction.
191 MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg,
192  SmallSet<unsigned,4> &PartDefRegs) {
193  unsigned LastDefReg = 0;
194  unsigned LastDefDist = 0;
195  MachineInstr *LastDef = nullptr;
196  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
197  unsigned SubReg = *SubRegs;
198  MachineInstr *Def = PhysRegDef[SubReg];
199  if (!Def)
200  continue;
201  unsigned Dist = DistanceMap[Def];
202  if (Dist > LastDefDist) {
203  LastDefReg = SubReg;
204  LastDef = Def;
205  LastDefDist = Dist;
206  }
207  }
208 
209  if (!LastDef)
210  return nullptr;
211 
212  PartDefRegs.insert(LastDefReg);
213  for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) {
214  MachineOperand &MO = LastDef->getOperand(i);
215  if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0)
216  continue;
217  unsigned DefReg = MO.getReg();
218  if (TRI->isSubRegister(Reg, DefReg)) {
219  for (MCSubRegIterator SubRegs(DefReg, TRI, /*IncludeSelf=*/true);
220  SubRegs.isValid(); ++SubRegs)
221  PartDefRegs.insert(*SubRegs);
222  }
223  }
224  return LastDef;
225 }
226 
227 /// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add
228 /// implicit defs to a machine instruction if there was an earlier def of its
229 /// super-register.
230 void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr &MI) {
231  MachineInstr *LastDef = PhysRegDef[Reg];
232  // If there was a previous use or a "full" def all is well.
233  if (!LastDef && !PhysRegUse[Reg]) {
234  // Otherwise, the last sub-register def implicitly defines this register.
235  // e.g.
236  // AH =
237  // AL = ... implicit-def EAX, implicit killed AH
238  // = AH
239  // ...
240  // = EAX
241  // All of the sub-registers must have been defined before the use of Reg!
242  SmallSet<unsigned, 4> PartDefRegs;
243  MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs);
244  // If LastPartialDef is NULL, it must be using a livein register.
245  if (LastPartialDef) {
246  LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
247  true/*IsImp*/));
248  PhysRegDef[Reg] = LastPartialDef;
249  SmallSet<unsigned, 8> Processed;
250  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
251  unsigned SubReg = *SubRegs;
252  if (Processed.count(SubReg))
253  continue;
254  if (PartDefRegs.count(SubReg))
255  continue;
256  // This part of Reg was defined before the last partial def. It's killed
257  // here.
258  LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg,
259  false/*IsDef*/,
260  true/*IsImp*/));
261  PhysRegDef[SubReg] = LastPartialDef;
262  for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS)
263  Processed.insert(*SS);
264  }
265  }
266  } else if (LastDef && !PhysRegUse[Reg] &&
267  !LastDef->findRegisterDefOperand(Reg))
268  // Last def defines the super register, add an implicit def of reg.
269  LastDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
270  true/*IsImp*/));
271 
272  // Remember this use.
273  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
274  SubRegs.isValid(); ++SubRegs)
275  PhysRegUse[*SubRegs] = &MI;
276 }
277 
278 /// FindLastRefOrPartRef - Return the last reference or partial reference of
279 /// the specified register.
280 MachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) {
281  MachineInstr *LastDef = PhysRegDef[Reg];
282  MachineInstr *LastUse = PhysRegUse[Reg];
283  if (!LastDef && !LastUse)
284  return nullptr;
285 
286  MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
287  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
288  unsigned LastPartDefDist = 0;
289  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
290  unsigned SubReg = *SubRegs;
291  MachineInstr *Def = PhysRegDef[SubReg];
292  if (Def && Def != LastDef) {
293  // There was a def of this sub-register in between. This is a partial
294  // def, keep track of the last one.
295  unsigned Dist = DistanceMap[Def];
296  if (Dist > LastPartDefDist)
297  LastPartDefDist = Dist;
298  } else if (MachineInstr *Use = PhysRegUse[SubReg]) {
299  unsigned Dist = DistanceMap[Use];
300  if (Dist > LastRefOrPartRefDist) {
301  LastRefOrPartRefDist = Dist;
302  LastRefOrPartRef = Use;
303  }
304  }
305  }
306 
307  return LastRefOrPartRef;
308 }
309 
310 bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) {
311  MachineInstr *LastDef = PhysRegDef[Reg];
312  MachineInstr *LastUse = PhysRegUse[Reg];
313  if (!LastDef && !LastUse)
314  return false;
315 
316  MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
317  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
318  // The whole register is used.
319  // AL =
320  // AH =
321  //
322  // = AX
323  // = AL, implicit killed AX
324  // AX =
325  //
326  // Or whole register is defined, but not used at all.
327  // dead AX =
328  // ...
329  // AX =
330  //
331  // Or whole register is defined, but only partly used.
332  // dead AX = implicit-def AL
333  // = killed AL
334  // AX =
335  MachineInstr *LastPartDef = nullptr;
336  unsigned LastPartDefDist = 0;
337  SmallSet<unsigned, 8> PartUses;
338  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
339  unsigned SubReg = *SubRegs;
340  MachineInstr *Def = PhysRegDef[SubReg];
341  if (Def && Def != LastDef) {
342  // There was a def of this sub-register in between. This is a partial
343  // def, keep track of the last one.
344  unsigned Dist = DistanceMap[Def];
345  if (Dist > LastPartDefDist) {
346  LastPartDefDist = Dist;
347  LastPartDef = Def;
348  }
349  continue;
350  }
351  if (MachineInstr *Use = PhysRegUse[SubReg]) {
352  for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); SS.isValid();
353  ++SS)
354  PartUses.insert(*SS);
355  unsigned Dist = DistanceMap[Use];
356  if (Dist > LastRefOrPartRefDist) {
357  LastRefOrPartRefDist = Dist;
358  LastRefOrPartRef = Use;
359  }
360  }
361  }
362 
363  if (!PhysRegUse[Reg]) {
364  // Partial uses. Mark register def dead and add implicit def of
365  // sub-registers which are used.
366  // dead EAX = op implicit-def AL
367  // That is, EAX def is dead but AL def extends pass it.
368  PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true);
369  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
370  unsigned SubReg = *SubRegs;
371  if (!PartUses.count(SubReg))
372  continue;
373  bool NeedDef = true;
374  if (PhysRegDef[Reg] == PhysRegDef[SubReg]) {
375  MachineOperand *MO = PhysRegDef[Reg]->findRegisterDefOperand(SubReg);
376  if (MO) {
377  NeedDef = false;
378  assert(!MO->isDead());
379  }
380  }
381  if (NeedDef)
382  PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg,
383  true/*IsDef*/, true/*IsImp*/));
384  MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg);
385  if (LastSubRef)
386  LastSubRef->addRegisterKilled(SubReg, TRI, true);
387  else {
388  LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
389  for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true);
390  SS.isValid(); ++SS)
391  PhysRegUse[*SS] = LastRefOrPartRef;
392  }
393  for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS)
394  PartUses.erase(*SS);
395  }
396  } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) {
397  if (LastPartDef)
398  // The last partial def kills the register.
399  LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/,
400  true/*IsImp*/, true/*IsKill*/));
401  else {
402  MachineOperand *MO =
403  LastRefOrPartRef->findRegisterDefOperand(Reg, false, false, TRI);
404  bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg;
405  // If the last reference is the last def, then it's not used at all.
406  // That is, unless we are currently processing the last reference itself.
407  LastRefOrPartRef->addRegisterDead(Reg, TRI, true);
408  if (NeedEC) {
409  // If we are adding a subreg def and the superreg def is marked early
410  // clobber, add an early clobber marker to the subreg def.
411  MO = LastRefOrPartRef->findRegisterDefOperand(Reg);
412  if (MO)
413  MO->setIsEarlyClobber();
414  }
415  }
416  } else
417  LastRefOrPartRef->addRegisterKilled(Reg, TRI, true);
418  return true;
419 }
420 
421 void LiveVariables::HandleRegMask(const MachineOperand &MO) {
422  // Call HandlePhysRegKill() for all live registers clobbered by Mask.
423  // Clobbered registers are always dead, sp there is no need to use
424  // HandlePhysRegDef().
425  for (unsigned Reg = 1, NumRegs = TRI->getNumRegs(); Reg != NumRegs; ++Reg) {
426  // Skip dead regs.
427  if (!PhysRegDef[Reg] && !PhysRegUse[Reg])
428  continue;
429  // Skip mask-preserved regs.
430  if (!MO.clobbersPhysReg(Reg))
431  continue;
432  // Kill the largest clobbered super-register.
433  // This avoids needless implicit operands.
434  unsigned Super = Reg;
435  for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR)
436  if ((PhysRegDef[*SR] || PhysRegUse[*SR]) && MO.clobbersPhysReg(*SR))
437  Super = *SR;
438  HandlePhysRegKill(Super, nullptr);
439  }
440 }
441 
442 void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI,
444  // What parts of the register are previously defined?
446  if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
447  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
448  SubRegs.isValid(); ++SubRegs)
449  Live.insert(*SubRegs);
450  } else {
451  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
452  unsigned SubReg = *SubRegs;
453  // If a register isn't itself defined, but all parts that make up of it
454  // are defined, then consider it also defined.
455  // e.g.
456  // AL =
457  // AH =
458  // = AX
459  if (Live.count(SubReg))
460  continue;
461  if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) {
462  for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true);
463  SS.isValid(); ++SS)
464  Live.insert(*SS);
465  }
466  }
467  }
468 
469  // Start from the largest piece, find the last time any part of the register
470  // is referenced.
471  HandlePhysRegKill(Reg, MI);
472  // Only some of the sub-registers are used.
473  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
474  unsigned SubReg = *SubRegs;
475  if (!Live.count(SubReg))
476  // Skip if this sub-register isn't defined.
477  continue;
478  HandlePhysRegKill(SubReg, MI);
479  }
480 
481  if (MI)
482  Defs.push_back(Reg); // Remember this def.
483 }
484 
485 void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI,
487  while (!Defs.empty()) {
488  unsigned Reg = Defs.back();
489  Defs.pop_back();
490  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
491  SubRegs.isValid(); ++SubRegs) {
492  unsigned SubReg = *SubRegs;
493  PhysRegDef[SubReg] = &MI;
494  PhysRegUse[SubReg] = nullptr;
495  }
496  }
497 }
498 
499 void LiveVariables::runOnInstr(MachineInstr &MI,
501  assert(!MI.isDebugInstr());
502  // Process all of the operands of the instruction...
503  unsigned NumOperandsToProcess = MI.getNumOperands();
504 
505  // Unless it is a PHI node. In this case, ONLY process the DEF, not any
506  // of the uses. They will be handled in other basic blocks.
507  if (MI.isPHI())
508  NumOperandsToProcess = 1;
509 
510  // Clear kill and dead markers. LV will recompute them.
511  SmallVector<unsigned, 4> UseRegs;
512  SmallVector<unsigned, 4> DefRegs;
513  SmallVector<unsigned, 1> RegMasks;
514  for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
515  MachineOperand &MO = MI.getOperand(i);
516  if (MO.isRegMask()) {
517  RegMasks.push_back(i);
518  continue;
519  }
520  if (!MO.isReg() || MO.getReg() == 0)
521  continue;
522  unsigned MOReg = MO.getReg();
523  if (MO.isUse()) {
525  MRI->isReserved(MOReg)))
526  MO.setIsKill(false);
527  if (MO.readsReg())
528  UseRegs.push_back(MOReg);
529  } else {
530  assert(MO.isDef());
531  // FIXME: We should not remove any dead flags. However the MIPS RDDSP
532  // instruction needs it at the moment: http://llvm.org/PR27116.
534  !MRI->isReserved(MOReg))
535  MO.setIsDead(false);
536  DefRegs.push_back(MOReg);
537  }
538  }
539 
540  MachineBasicBlock *MBB = MI.getParent();
541  // Process all uses.
542  for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) {
543  unsigned MOReg = UseRegs[i];
545  HandleVirtRegUse(MOReg, MBB, MI);
546  else if (!MRI->isReserved(MOReg))
547  HandlePhysRegUse(MOReg, MI);
548  }
549 
550  // Process all masked registers. (Call clobbers).
551  for (unsigned i = 0, e = RegMasks.size(); i != e; ++i)
552  HandleRegMask(MI.getOperand(RegMasks[i]));
553 
554  // Process all defs.
555  for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) {
556  unsigned MOReg = DefRegs[i];
558  HandleVirtRegDef(MOReg, MI);
559  else if (!MRI->isReserved(MOReg))
560  HandlePhysRegDef(MOReg, &MI, Defs);
561  }
562  UpdatePhysRegDefs(MI, Defs);
563 }
564 
565 void LiveVariables::runOnBlock(MachineBasicBlock *MBB, const unsigned NumRegs) {
566  // Mark live-in registers as live-in.
568  for (const auto &LI : MBB->liveins()) {
570  "Cannot have a live-in virtual register!");
571  HandlePhysRegDef(LI.PhysReg, nullptr, Defs);
572  }
573 
574  // Loop over all of the instructions, processing them.
575  DistanceMap.clear();
576  unsigned Dist = 0;
577  for (MachineInstr &MI : *MBB) {
578  if (MI.isDebugInstr())
579  continue;
580  DistanceMap.insert(std::make_pair(&MI, Dist++));
581 
582  runOnInstr(MI, Defs);
583  }
584 
585  // Handle any virtual assignments from PHI nodes which might be at the
586  // bottom of this basic block. We check all of our successor blocks to see
587  // if they have PHI nodes, and if so, we simulate an assignment at the end
588  // of the current block.
589  if (!PHIVarInfo[MBB->getNumber()].empty()) {
590  SmallVectorImpl<unsigned> &VarInfoVec = PHIVarInfo[MBB->getNumber()];
591 
592  for (SmallVectorImpl<unsigned>::iterator I = VarInfoVec.begin(),
593  E = VarInfoVec.end(); I != E; ++I)
594  // Mark it alive only in the block we are representing.
595  MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(),
596  MBB);
597  }
598 
599  // MachineCSE may CSE instructions which write to non-allocatable physical
600  // registers across MBBs. Remember if any reserved register is liveout.
601  SmallSet<unsigned, 4> LiveOuts;
602  for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
603  SE = MBB->succ_end(); SI != SE; ++SI) {
604  MachineBasicBlock *SuccMBB = *SI;
605  if (SuccMBB->isEHPad())
606  continue;
607  for (const auto &LI : SuccMBB->liveins()) {
608  if (!TRI->isInAllocatableClass(LI.PhysReg))
609  // Ignore other live-ins, e.g. those that are live into landing pads.
610  LiveOuts.insert(LI.PhysReg);
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]) && !LiveOuts.count(i))
618  HandlePhysRegDef(i, nullptr, Defs);
619 }
620 
622  MF = &mf;
623  MRI = &mf.getRegInfo();
624  TRI = MF->getSubtarget().getRegisterInfo();
625 
626  const unsigned NumRegs = TRI->getNumRegs();
627  PhysRegDef.assign(NumRegs, nullptr);
628  PhysRegUse.assign(NumRegs, nullptr);
629  PHIVarInfo.resize(MF->getNumBlockIDs());
630  PHIJoins.clear();
631 
632  // FIXME: LiveIntervals will be updated to remove its dependence on
633  // LiveVariables to improve compilation time and eliminate bizarre pass
634  // dependencies. Until then, we can't change much in -O0.
635  if (!MRI->isSSA())
636  report_fatal_error("regalloc=... not currently supported with -O0");
637 
638  analyzePHINodes(mf);
639 
640  // Calculate live variable information in depth first order on the CFG of the
641  // function. This guarantees that we will see the definition of a virtual
642  // register before its uses due to dominance properties of SSA (except for PHI
643  // nodes, which are treated as a special case).
644  MachineBasicBlock *Entry = &MF->front();
646 
647  for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) {
648  runOnBlock(MBB, NumRegs);
649 
650  PhysRegDef.assign(NumRegs, nullptr);
651  PhysRegUse.assign(NumRegs, nullptr);
652  }
653 
654  // Convert and transfer the dead / killed information we have gathered into
655  // VirtRegInfo onto MI's.
656  for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) {
657  const unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
658  for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j)
659  if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg))
660  VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI);
661  else
662  VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI);
663  }
664 
665  // Check to make sure there are no unreachable blocks in the MC CFG for the
666  // function. If so, it is due to a bug in the instruction selector or some
667  // other part of the code generator if this happens.
668 #ifndef NDEBUG
669  for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i)
670  assert(Visited.count(&*i) != 0 && "unreachable basic block found");
671 #endif
672 
673  PhysRegDef.clear();
674  PhysRegUse.clear();
675  PHIVarInfo.clear();
676 
677  return false;
678 }
679 
680 /// replaceKillInstruction - Update register kill info by replacing a kill
681 /// instruction with a new one.
683  MachineInstr &NewMI) {
684  VarInfo &VI = getVarInfo(Reg);
685  std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
686 }
687 
688 /// removeVirtualRegistersKilled - Remove all killed info for the specified
689 /// instruction.
691  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
692  MachineOperand &MO = MI.getOperand(i);
693  if (MO.isReg() && MO.isKill()) {
694  MO.setIsKill(false);
695  unsigned Reg = MO.getReg();
697  bool removed = getVarInfo(Reg).removeKill(MI);
698  assert(removed && "kill not in register's VarInfo?");
699  (void)removed;
700  }
701  }
702  }
703 }
704 
705 /// analyzePHINodes - Gather information about the PHI nodes in here. In
706 /// particular, we want to map the variable information of a virtual register
707 /// which is used in a PHI node. We map that to the BB the vreg is coming from.
708 ///
709 void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
710  for (const auto &MBB : Fn)
711  for (const auto &BBI : MBB) {
712  if (!BBI.isPHI())
713  break;
714  for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
715  if (BBI.getOperand(i).readsReg())
716  PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()]
717  .push_back(BBI.getOperand(i).getReg());
718  }
719 }
720 
722  unsigned Reg,
723  MachineRegisterInfo &MRI) {
724  unsigned Num = MBB.getNumber();
725 
726  // Reg is live-through.
727  if (AliveBlocks.test(Num))
728  return true;
729 
730  // Registers defined in MBB cannot be live in.
731  const MachineInstr *Def = MRI.getVRegDef(Reg);
732  if (Def && Def->getParent() == &MBB)
733  return false;
734 
735  // Reg was not defined in MBB, was it killed here?
736  return findKill(&MBB);
737 }
738 
739 bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) {
741 
743  for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
744  Kills.insert(VI.Kills[i]->getParent());
745 
746  // Loop over all of the successors of the basic block, checking to see if
747  // the value is either live in the block, or if it is killed in the block.
748  for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
749  // Is it alive in this successor?
750  unsigned SuccIdx = SuccMBB->getNumber();
751  if (VI.AliveBlocks.test(SuccIdx))
752  return true;
753  // Or is it live because there is a use in a successor that kills it?
754  if (Kills.count(SuccMBB))
755  return true;
756  }
757 
758  return false;
759 }
760 
761 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
762 /// variables that are live out of DomBB will be marked as passing live through
763 /// BB.
765  MachineBasicBlock *DomBB,
766  MachineBasicBlock *SuccBB) {
767  const unsigned NumNew = BB->getNumber();
768 
770 
771  MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end();
772  for (; BBI != BBE && BBI->isPHI(); ++BBI) {
773  // Record the def of the PHI node.
774  Defs.insert(BBI->getOperand(0).getReg());
775 
776  // All registers used by PHI nodes in SuccBB must be live through BB.
777  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
778  if (BBI->getOperand(i+1).getMBB() == BB)
779  getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
780  }
781 
782  // Record all vreg defs and kills of all instructions in SuccBB.
783  for (; BBI != BBE; ++BBI) {
784  for (MachineInstr::mop_iterator I = BBI->operands_begin(),
785  E = BBI->operands_end(); I != E; ++I) {
786  if (I->isReg() && TargetRegisterInfo::isVirtualRegister(I->getReg())) {
787  if (I->isDef())
788  Defs.insert(I->getReg());
789  else if (I->isKill())
790  Kills.insert(I->getReg());
791  }
792  }
793  }
794 
795  // Update info for all live variables
796  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
797  unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
798 
799  // If the Defs is defined in the successor it can't be live in BB.
800  if (Defs.count(Reg))
801  continue;
802 
803  // If the register is either killed in or live through SuccBB it's also live
804  // through BB.
805  VarInfo &VI = getVarInfo(Reg);
806  if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber()))
807  VI.AliveBlocks.set(NumNew);
808  }
809 }
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
iterator end() const
pred_reverse_iterator pred_rbegin()
MachineOperand * findRegisterDefOperand(unsigned Reg, bool isDead=false, bool Overlap=false, const TargetRegisterInfo *TRI=nullptr)
Wrapper for findRegisterDefOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
pred_reverse_iterator pred_rend()
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
bool addRegisterDead(unsigned Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI defined a register without a use.
void set(unsigned Idx)
void push_back(const T &Elt)
Definition: SmallVector.h:211
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB)
isLiveOut - Determine if Reg is live out from MBB, when not considering PHI nodes.
unsigned Reg
void HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, MachineInstr &MI)
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:78
unsigned const TargetRegisterInfo * TRI
void setIsDead(bool Val=true)
MachineInstr * findKill(const MachineBasicBlock *MBB) const
findKill - Find a kill instruction in MBB. Return NULL if none is found.
std::vector< MachineBasicBlock * >::const_iterator const_pred_iterator
bool isPHI() const
bool erase(const T &V)
Definition: SmallSet.h:207
iterator_range< succ_iterator > successors()
static MachineOperand CreateReg(unsigned Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
iterator begin() const
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:93
bool isEarlyClobber() const
bool test(unsigned Idx) const
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
MCSuperRegIterator enumerates all super-registers of Reg.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
unsigned SubReg
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:83
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
char & UnreachableMachineBlockElimID
UnreachableMachineBlockElimination - This pass removes unreachable machine basic blocks.
void setIsEarlyClobber(bool Val=true)
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register. ...
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
char & LiveVariablesID
LiveVariables pass - This pass computes the set of blocks in which each variable is life and sets mac...
unsigned const MachineRegisterInfo * MRI
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Represent the analysis usage information of a pass.
static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New)
livevars
std::vector< MachineBasicBlock * >::const_iterator const_succ_iterator
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
VarInfo & getVarInfo(unsigned RegIdx)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
MCSubRegIterator enumerates all sub-registers of Reg.
size_t size() const
Definition: SmallVector.h:52
bool isDebugInstr() const
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *BB)
void setIsKill(bool Val=true)
void addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB)
addNewBlock - Add a new basic block BB between DomBB and SuccBB.
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction&#39;s which are the last use of this virtual register (kill it) in the...
Definition: LiveVariables.h:88
Iterator for intrusive lists based on ilist_node.
void replaceKillInstruction(unsigned Reg, MachineInstr &OldMI, MachineInstr &NewMI)
replaceKillInstruction - Update register kill info by replacing a kill instruction with a new one...
void HandleVirtRegDef(unsigned reg, MachineInstr &MI)
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
bool isLiveIn(const MachineBasicBlock &MBB, unsigned Reg, MachineRegisterInfo &MRI)
isLiveIn - Is Reg live in to MBB? This means that Reg is live through MBB, or it is killed in MBB...
MachineOperand class - Representation of each machine instruction operand.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static bool clobbersPhysReg(const uint32_t *RegMask, unsigned PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
void removeVirtualRegistersKilled(MachineInstr &MI)
removeVirtualRegistersKilled - Remove all killed info for the specified instruction.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:64
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define I(x, y, z)
Definition: MD5.cpp:58
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
iterator_range< livein_iterator > liveins() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SparseBitVectorIterator iterator
static const Function * getParent(const Value *V)
bool addRegisterKilled(unsigned IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI kills a register.
IRTranslator LLVM IR MI
INITIALIZE_PASS_BEGIN(LiveVariables, "livevars", "Live Variable Analysis", false, false) INITIALIZE_PASS_END(LiveVariables
Register getReg() const
getReg - Returns the register number.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164