LLVM  14.0.0git
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 
29 #include "llvm/ADT/DenseSet.h"
31 #include "llvm/ADT/STLExtras.h"
32 #include "llvm/ADT/SmallPtrSet.h"
33 #include "llvm/ADT/SmallSet.h"
36 #include "llvm/CodeGen/Passes.h"
37 #include "llvm/Config/llvm-config.h"
38 #include "llvm/Support/Debug.h"
41 #include <algorithm>
42 using namespace llvm;
43 
44 char LiveVariables::ID = 0;
47  "Live Variable Analysis", false, false)
48 INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElim)
50  "Live Variable Analysis", false, false)
51 
52 
53 void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const {
54  AU.addRequiredID(UnreachableMachineBlockElimID);
55  AU.setPreservesAll();
57 }
58 
61  for (unsigned i = 0, e = Kills.size(); i != e; ++i)
62  if (Kills[i]->getParent() == MBB)
63  return Kills[i];
64  return nullptr;
65 }
66 
67 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
69  dbgs() << " Alive in blocks: ";
70  for (unsigned AB : AliveBlocks)
71  dbgs() << AB << ", ";
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.
85  assert(Reg.isVirtual() && "getVarInfo: not a virtual register!");
86  VirtRegInfo.grow(Reg);
87  return VirtRegInfo[Reg];
88 }
89 
91  VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *MBB,
93  unsigned BBNum = MBB->getNumber();
94 
95  // Check to see if this basic block is one of the killing blocks. If so,
96  // remove it.
97  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
98  if (VRInfo.Kills[i]->getParent() == MBB) {
99  VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry
100  break;
101  }
102 
103  if (MBB == DefBlock) return; // Terminate recursion
104 
105  if (VRInfo.AliveBlocks.test(BBNum))
106  return; // We already know the block is live
107 
108  // Mark the variable known alive in this bb
109  VRInfo.AliveBlocks.set(BBNum);
110 
111  assert(MBB != &MF->front() && "Can't find reaching def for virtreg");
112  WorkList.insert(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend());
113 }
114 
116  MachineBasicBlock *DefBlock,
119  MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList);
120 
121  while (!WorkList.empty()) {
122  MachineBasicBlock *Pred = WorkList.pop_back_val();
123  MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList);
124  }
125 }
126 
128  MachineInstr &MI) {
129  assert(MRI->getVRegDef(Reg) && "Register use before def!");
130 
131  unsigned BBNum = MBB->getNumber();
132 
133  VarInfo &VRInfo = getVarInfo(Reg);
134 
135  // Check to see if this basic block is already a kill block.
136  if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) {
137  // Yes, this register is killed in this basic block already. Increase the
138  // live range by updating the kill instruction.
139  VRInfo.Kills.back() = &MI;
140  return;
141  }
142 
143 #ifndef NDEBUG
144  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
145  assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!");
146 #endif
147 
148  // This situation can occur:
149  //
150  // ,------.
151  // | |
152  // | v
153  // | t2 = phi ... t1 ...
154  // | |
155  // | v
156  // | t1 = ...
157  // | ... = ... t1 ...
158  // | |
159  // `------'
160  //
161  // where there is a use in a PHI node that's a predecessor to the defining
162  // block. We don't want to mark all predecessors as having the value "alive"
163  // in this case.
164  if (MBB == MRI->getVRegDef(Reg)->getParent())
165  return;
166 
167  // Add a new kill entry for this basic block. If this virtual register is
168  // already marked as alive in this basic block, that means it is alive in at
169  // least one of the successor blocks, it's not a kill.
170  if (!VRInfo.AliveBlocks.test(BBNum))
171  VRInfo.Kills.push_back(&MI);
172 
173  // Update all dominating blocks to mark them as "known live".
174  for (MachineBasicBlock *Pred : MBB->predecessors())
175  MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(Reg)->getParent(), Pred);
176 }
177 
179  VarInfo &VRInfo = getVarInfo(Reg);
180 
181  if (VRInfo.AliveBlocks.empty())
182  // If vr is not alive in any block, then defaults to dead.
183  VRInfo.Kills.push_back(&MI);
184 }
185 
186 /// FindLastPartialDef - Return the last partial def of the specified register.
187 /// Also returns the sub-registers that're defined by the instruction.
188 MachineInstr *
189 LiveVariables::FindLastPartialDef(Register Reg,
190  SmallSet<unsigned, 4> &PartDefRegs) {
191  unsigned LastDefReg = 0;
192  unsigned LastDefDist = 0;
193  MachineInstr *LastDef = nullptr;
194  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
195  unsigned SubReg = *SubRegs;
196  MachineInstr *Def = PhysRegDef[SubReg];
197  if (!Def)
198  continue;
199  unsigned Dist = DistanceMap[Def];
200  if (Dist > LastDefDist) {
201  LastDefReg = SubReg;
202  LastDef = Def;
203  LastDefDist = Dist;
204  }
205  }
206 
207  if (!LastDef)
208  return nullptr;
209 
210  PartDefRegs.insert(LastDefReg);
211  for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) {
212  MachineOperand &MO = LastDef->getOperand(i);
213  if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0)
214  continue;
215  Register DefReg = MO.getReg();
216  if (TRI->isSubRegister(Reg, DefReg)) {
217  for (MCSubRegIterator SubRegs(DefReg, TRI, /*IncludeSelf=*/true);
218  SubRegs.isValid(); ++SubRegs)
219  PartDefRegs.insert(*SubRegs);
220  }
221  }
222  return LastDef;
223 }
224 
225 /// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add
226 /// implicit defs to a machine instruction if there was an earlier def of its
227 /// super-register.
228 void LiveVariables::HandlePhysRegUse(Register Reg, MachineInstr &MI) {
229  MachineInstr *LastDef = PhysRegDef[Reg];
230  // If there was a previous use or a "full" def all is well.
231  if (!LastDef && !PhysRegUse[Reg]) {
232  // Otherwise, the last sub-register def implicitly defines this register.
233  // e.g.
234  // AH =
235  // AL = ... implicit-def EAX, implicit killed AH
236  // = AH
237  // ...
238  // = EAX
239  // All of the sub-registers must have been defined before the use of Reg!
240  SmallSet<unsigned, 4> PartDefRegs;
241  MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs);
242  // If LastPartialDef is NULL, it must be using a livein register.
243  if (LastPartialDef) {
244  LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
245  true/*IsImp*/));
246  PhysRegDef[Reg] = LastPartialDef;
247  SmallSet<unsigned, 8> Processed;
248  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
249  unsigned SubReg = *SubRegs;
250  if (Processed.count(SubReg))
251  continue;
252  if (PartDefRegs.count(SubReg))
253  continue;
254  // This part of Reg was defined before the last partial def. It's killed
255  // here.
257  false/*IsDef*/,
258  true/*IsImp*/));
259  PhysRegDef[SubReg] = LastPartialDef;
260  for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS)
261  Processed.insert(*SS);
262  }
263  }
264  } else if (LastDef && !PhysRegUse[Reg] &&
265  !LastDef->findRegisterDefOperand(Reg))
266  // Last def defines the super register, add an implicit def of reg.
267  LastDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
268  true/*IsImp*/));
269 
270  // Remember this use.
271  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
272  SubRegs.isValid(); ++SubRegs)
273  PhysRegUse[*SubRegs] = &MI;
274 }
275 
276 /// FindLastRefOrPartRef - Return the last reference or partial reference of
277 /// the specified register.
278 MachineInstr *LiveVariables::FindLastRefOrPartRef(Register Reg) {
279  MachineInstr *LastDef = PhysRegDef[Reg];
280  MachineInstr *LastUse = PhysRegUse[Reg];
281  if (!LastDef && !LastUse)
282  return nullptr;
283 
284  MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
285  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
286  unsigned LastPartDefDist = 0;
287  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
288  unsigned SubReg = *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 
308 bool LiveVariables::HandlePhysRegKill(Register 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, implicit killed AX
322  // AX =
323  //
324  // Or whole register is defined, but not used at all.
325  // dead AX =
326  // ...
327  // AX =
328  //
329  // Or whole register is defined, but only partly used.
330  // dead AX = implicit-def AL
331  // = killed AL
332  // AX =
333  MachineInstr *LastPartDef = nullptr;
334  unsigned LastPartDefDist = 0;
335  SmallSet<unsigned, 8> PartUses;
336  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
337  unsigned SubReg = *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  for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); SS.isValid();
351  ++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  // dead EAX = op implicit-def AL
365  // That is, EAX def is dead but AL def extends pass it.
366  PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true);
367  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
368  unsigned SubReg = *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  for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true);
388  SS.isValid(); ++SS)
389  PhysRegUse[*SS] = LastRefOrPartRef;
390  }
391  for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS)
392  PartUses.erase(*SS);
393  }
394  } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) {
395  if (LastPartDef)
396  // The last partial def kills the register.
397  LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/,
398  true/*IsImp*/, true/*IsKill*/));
399  else {
400  MachineOperand *MO =
401  LastRefOrPartRef->findRegisterDefOperand(Reg, false, false, TRI);
402  bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg;
403  // If the last reference is the last def, then it's not used at all.
404  // That is, unless we are currently processing the last reference itself.
405  LastRefOrPartRef->addRegisterDead(Reg, TRI, true);
406  if (NeedEC) {
407  // If we are adding a subreg def and the superreg def is marked early
408  // clobber, add an early clobber marker to the subreg def.
409  MO = LastRefOrPartRef->findRegisterDefOperand(Reg);
410  if (MO)
411  MO->setIsEarlyClobber();
412  }
413  }
414  } else
415  LastRefOrPartRef->addRegisterKilled(Reg, TRI, true);
416  return true;
417 }
418 
419 void LiveVariables::HandleRegMask(const MachineOperand &MO) {
420  // Call HandlePhysRegKill() for all live registers clobbered by Mask.
421  // Clobbered registers are always dead, sp there is no need to use
422  // HandlePhysRegDef().
423  for (unsigned Reg = 1, NumRegs = TRI->getNumRegs(); Reg != NumRegs; ++Reg) {
424  // Skip dead regs.
425  if (!PhysRegDef[Reg] && !PhysRegUse[Reg])
426  continue;
427  // Skip mask-preserved regs.
428  if (!MO.clobbersPhysReg(Reg))
429  continue;
430  // Kill the largest clobbered super-register.
431  // This avoids needless implicit operands.
432  unsigned Super = Reg;
433  for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR)
434  if ((PhysRegDef[*SR] || PhysRegUse[*SR]) && MO.clobbersPhysReg(*SR))
435  Super = *SR;
436  HandlePhysRegKill(Super, nullptr);
437  }
438 }
439 
440 void LiveVariables::HandlePhysRegDef(Register Reg, MachineInstr *MI,
442  // What parts of the register are previously defined?
444  if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
445  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
446  SubRegs.isValid(); ++SubRegs)
447  Live.insert(*SubRegs);
448  } else {
449  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
450  unsigned SubReg = *SubRegs;
451  // If a register isn't itself defined, but all parts that make up of it
452  // are defined, then consider it also defined.
453  // e.g.
454  // AL =
455  // AH =
456  // = AX
457  if (Live.count(SubReg))
458  continue;
459  if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) {
460  for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true);
461  SS.isValid(); ++SS)
462  Live.insert(*SS);
463  }
464  }
465  }
466 
467  // Start from the largest piece, find the last time any part of the register
468  // is referenced.
469  HandlePhysRegKill(Reg, MI);
470  // Only some of the sub-registers are used.
471  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
472  unsigned SubReg = *SubRegs;
473  if (!Live.count(SubReg))
474  // Skip if this sub-register isn't defined.
475  continue;
476  HandlePhysRegKill(SubReg, MI);
477  }
478 
479  if (MI)
480  Defs.push_back(Reg); // Remember this def.
481 }
482 
483 void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI,
485  while (!Defs.empty()) {
486  Register Reg = Defs.pop_back_val();
487  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
488  SubRegs.isValid(); ++SubRegs) {
489  unsigned SubReg = *SubRegs;
490  PhysRegDef[SubReg] = &MI;
491  PhysRegUse[SubReg] = nullptr;
492  }
493  }
494 }
495 
496 void LiveVariables::runOnInstr(MachineInstr &MI,
498  assert(!MI.isDebugOrPseudoInstr());
499  // Process all of the operands of the instruction...
500  unsigned NumOperandsToProcess = MI.getNumOperands();
501 
502  // Unless it is a PHI node. In this case, ONLY process the DEF, not any
503  // of the uses. They will be handled in other basic blocks.
504  if (MI.isPHI())
505  NumOperandsToProcess = 1;
506 
507  // Clear kill and dead markers. LV will recompute them.
508  SmallVector<unsigned, 4> UseRegs;
509  SmallVector<unsigned, 4> DefRegs;
510  SmallVector<unsigned, 1> RegMasks;
511  for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
512  MachineOperand &MO = MI.getOperand(i);
513  if (MO.isRegMask()) {
514  RegMasks.push_back(i);
515  continue;
516  }
517  if (!MO.isReg() || MO.getReg() == 0)
518  continue;
519  Register MOReg = MO.getReg();
520  if (MO.isUse()) {
521  if (!(Register::isPhysicalRegister(MOReg) && MRI->isReserved(MOReg)))
522  MO.setIsKill(false);
523  if (MO.readsReg())
524  UseRegs.push_back(MOReg);
525  } else {
526  assert(MO.isDef());
527  // FIXME: We should not remove any dead flags. However the MIPS RDDSP
528  // instruction needs it at the moment: http://llvm.org/PR27116.
529  if (Register::isPhysicalRegister(MOReg) && !MRI->isReserved(MOReg))
530  MO.setIsDead(false);
531  DefRegs.push_back(MOReg);
532  }
533  }
534 
535  MachineBasicBlock *MBB = MI.getParent();
536  // Process all uses.
537  for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) {
538  unsigned MOReg = UseRegs[i];
539  if (Register::isVirtualRegister(MOReg))
540  HandleVirtRegUse(MOReg, MBB, MI);
541  else if (!MRI->isReserved(MOReg))
542  HandlePhysRegUse(MOReg, MI);
543  }
544 
545  // Process all masked registers. (Call clobbers).
546  for (unsigned i = 0, e = RegMasks.size(); i != e; ++i)
547  HandleRegMask(MI.getOperand(RegMasks[i]));
548 
549  // Process all defs.
550  for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) {
551  unsigned MOReg = DefRegs[i];
552  if (Register::isVirtualRegister(MOReg))
553  HandleVirtRegDef(MOReg, MI);
554  else if (!MRI->isReserved(MOReg))
555  HandlePhysRegDef(MOReg, &MI, Defs);
556  }
557  UpdatePhysRegDefs(MI, Defs);
558 }
559 
560 void LiveVariables::runOnBlock(MachineBasicBlock *MBB, const unsigned NumRegs) {
561  // Mark live-in registers as live-in.
563  for (const auto &LI : MBB->liveins()) {
564  assert(Register::isPhysicalRegister(LI.PhysReg) &&
565  "Cannot have a live-in virtual register!");
566  HandlePhysRegDef(LI.PhysReg, nullptr, Defs);
567  }
568 
569  // Loop over all of the instructions, processing them.
570  DistanceMap.clear();
571  unsigned Dist = 0;
572  for (MachineInstr &MI : *MBB) {
573  if (MI.isDebugOrPseudoInstr())
574  continue;
575  DistanceMap.insert(std::make_pair(&MI, Dist++));
576 
577  runOnInstr(MI, Defs);
578  }
579 
580  // Handle any virtual assignments from PHI nodes which might be at the
581  // bottom of this basic block. We check all of our successor blocks to see
582  // if they have PHI nodes, and if so, we simulate an assignment at the end
583  // of the current block.
584  if (!PHIVarInfo[MBB->getNumber()].empty()) {
585  SmallVectorImpl<unsigned> &VarInfoVec = PHIVarInfo[MBB->getNumber()];
586 
587  for (unsigned I : VarInfoVec)
588  // Mark it alive only in the block we are representing.
590  MBB);
591  }
592 
593  // MachineCSE may CSE instructions which write to non-allocatable physical
594  // registers across MBBs. Remember if any reserved register is liveout.
595  SmallSet<unsigned, 4> LiveOuts;
596  for (const MachineBasicBlock *SuccMBB : MBB->successors()) {
597  if (SuccMBB->isEHPad())
598  continue;
599  for (const auto &LI : SuccMBB->liveins()) {
600  if (!TRI->isInAllocatableClass(LI.PhysReg))
601  // Ignore other live-ins, e.g. those that are live into landing pads.
602  LiveOuts.insert(LI.PhysReg);
603  }
604  }
605 
606  // Loop over PhysRegDef / PhysRegUse, killing any registers that are
607  // available at the end of the basic block.
608  for (unsigned i = 0; i != NumRegs; ++i)
609  if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i))
610  HandlePhysRegDef(i, nullptr, Defs);
611 }
612 
614  MF = &mf;
615  MRI = &mf.getRegInfo();
616  TRI = MF->getSubtarget().getRegisterInfo();
617 
618  const unsigned NumRegs = TRI->getNumRegs();
619  PhysRegDef.assign(NumRegs, nullptr);
620  PhysRegUse.assign(NumRegs, nullptr);
621  PHIVarInfo.resize(MF->getNumBlockIDs());
622  PHIJoins.clear();
623 
624  // FIXME: LiveIntervals will be updated to remove its dependence on
625  // LiveVariables to improve compilation time and eliminate bizarre pass
626  // dependencies. Until then, we can't change much in -O0.
627  if (!MRI->isSSA())
628  report_fatal_error("regalloc=... not currently supported with -O0");
629 
630  analyzePHINodes(mf);
631 
632  // Calculate live variable information in depth first order on the CFG of the
633  // function. This guarantees that we will see the definition of a virtual
634  // register before its uses due to dominance properties of SSA (except for PHI
635  // nodes, which are treated as a special case).
636  MachineBasicBlock *Entry = &MF->front();
638 
639  for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) {
640  runOnBlock(MBB, NumRegs);
641 
642  PhysRegDef.assign(NumRegs, nullptr);
643  PhysRegUse.assign(NumRegs, nullptr);
644  }
645 
646  // Convert and transfer the dead / killed information we have gathered into
647  // VirtRegInfo onto MI's.
648  for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) {
650  for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j)
651  if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg))
652  VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI);
653  else
654  VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI);
655  }
656 
657  // Check to make sure there are no unreachable blocks in the MC CFG for the
658  // function. If so, it is due to a bug in the instruction selector or some
659  // other part of the code generator if this happens.
660 #ifndef NDEBUG
661  for (const MachineBasicBlock &MBB : *MF)
662  assert(Visited.contains(&MBB) && "unreachable basic block found");
663 #endif
664 
665  PhysRegDef.clear();
666  PhysRegUse.clear();
667  PHIVarInfo.clear();
668 
669  return false;
670 }
671 
672 /// replaceKillInstruction - Update register kill info by replacing a kill
673 /// instruction with a new one.
675  MachineInstr &NewMI) {
676  VarInfo &VI = getVarInfo(Reg);
677  std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
678 }
679 
680 /// removeVirtualRegistersKilled - Remove all killed info for the specified
681 /// instruction.
683  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
684  MachineOperand &MO = MI.getOperand(i);
685  if (MO.isReg() && MO.isKill()) {
686  MO.setIsKill(false);
687  Register Reg = MO.getReg();
690  assert(removed && "kill not in register's VarInfo?");
691  (void)removed;
692  }
693  }
694  }
695 }
696 
697 /// analyzePHINodes - Gather information about the PHI nodes in here. In
698 /// particular, we want to map the variable information of a virtual register
699 /// which is used in a PHI node. We map that to the BB the vreg is coming from.
700 ///
701 void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
702  for (const auto &MBB : Fn)
703  for (const auto &BBI : MBB) {
704  if (!BBI.isPHI())
705  break;
706  for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
707  if (BBI.getOperand(i).readsReg())
708  PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()]
709  .push_back(BBI.getOperand(i).getReg());
710  }
711 }
712 
715  unsigned Num = MBB.getNumber();
716 
717  // Reg is live-through.
718  if (AliveBlocks.test(Num))
719  return true;
720 
721  // Registers defined in MBB cannot be live in.
722  const MachineInstr *Def = MRI.getVRegDef(Reg);
723  if (Def && Def->getParent() == &MBB)
724  return false;
725 
726  // Reg was not defined in MBB, was it killed here?
727  return findKill(&MBB);
728 }
729 
732 
734  for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
735  Kills.insert(VI.Kills[i]->getParent());
736 
737  // Loop over all of the successors of the basic block, checking to see if
738  // the value is either live in the block, or if it is killed in the block.
739  for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
740  // Is it alive in this successor?
741  unsigned SuccIdx = SuccMBB->getNumber();
742  if (VI.AliveBlocks.test(SuccIdx))
743  return true;
744  // Or is it live because there is a use in a successor that kills it?
745  if (Kills.count(SuccMBB))
746  return true;
747  }
748 
749  return false;
750 }
751 
752 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
753 /// variables that are live out of DomBB will be marked as passing live through
754 /// BB.
756  MachineBasicBlock *DomBB,
757  MachineBasicBlock *SuccBB) {
758  const unsigned NumNew = BB->getNumber();
759 
760  DenseSet<unsigned> Defs, Kills;
761 
762  MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end();
763  for (; BBI != BBE && BBI->isPHI(); ++BBI) {
764  // Record the def of the PHI node.
765  Defs.insert(BBI->getOperand(0).getReg());
766 
767  // All registers used by PHI nodes in SuccBB must be live through BB.
768  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
769  if (BBI->getOperand(i+1).getMBB() == BB)
770  getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
771  }
772 
773  // Record all vreg defs and kills of all instructions in SuccBB.
774  for (; BBI != BBE; ++BBI) {
775  for (const MachineOperand &Op : BBI->operands()) {
776  if (Op.isReg() && Register::isVirtualRegister(Op.getReg())) {
777  if (Op.isDef())
778  Defs.insert(Op.getReg());
779  else if (Op.isKill())
780  Kills.insert(Op.getReg());
781  }
782  }
783  }
784 
785  // Update info for all live variables
786  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
788 
789  // If the Defs is defined in the successor it can't be live in BB.
790  if (Defs.count(Reg))
791  continue;
792 
793  // If the register is either killed in or live through SuccBB it's also live
794  // through BB.
795  VarInfo &VI = getVarInfo(Reg);
796  if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber()))
797  VI.AliveBlocks.set(NumNew);
798  }
799 }
800 
801 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
802 /// variables that are live out of DomBB will be marked as passing live through
803 /// BB. LiveInSets[BB] is *not* updated (because it is not needed during
804 /// PHIElimination).
806  MachineBasicBlock *DomBB,
807  MachineBasicBlock *SuccBB,
808  std::vector<SparseBitVector<>> &LiveInSets) {
809  const unsigned NumNew = BB->getNumber();
810 
811  SparseBitVector<> &BV = LiveInSets[SuccBB->getNumber()];
812  for (unsigned R : BV) {
813  Register VirtReg = Register::index2VirtReg(R);
815  VI.AliveBlocks.set(NumNew);
816  }
817  // All registers used by PHI nodes in SuccBB must be live through BB.
818  for (MachineBasicBlock::iterator BBI = SuccBB->begin(),
819  BBE = SuccBB->end();
820  BBI != BBE && BBI->isPHI(); ++BBI) {
821  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
822  if (BBI->getOperand(i + 1).getMBB() == BB &&
823  BBI->getOperand(i).readsReg())
824  getVarInfo(BBI->getOperand(i).getReg())
825  .AliveBlocks.set(NumNew);
826  }
827 }
i
i
Definition: README.txt:29
llvm::LiveVariables::VarInfo::isLiveIn
bool isLiveIn(const MachineBasicBlock &MBB, Register Reg, MachineRegisterInfo &MRI)
isLiveIn - Is Reg live in to MBB? This means that Reg is live through MBB, or it is killed in MBB.
Definition: LiveVariables.cpp:713
llvm::MachineInstr::addRegisterDead
bool addRegisterDead(Register Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI defined a register without a use.
Definition: MachineInstr.cpp:1957
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:491
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::LiveVariables::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: LiveVariables.cpp:613
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::LiveVariables::ID
static char ID
Definition: LiveVariables.h:48
llvm::MachineOperand::CreateReg
static MachineOperand CreateReg(Register 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)
Definition: MachineOperand.h:791
llvm::LiveVariables::MarkVirtRegAliveInBlock
void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *BB)
Definition: LiveVariables.cpp:115
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::SparseBitVector::clear
void clear()
Definition: SparseBitVector.h:451
llvm::MachineOperand::setIsKill
void setIsKill(bool Val=true)
Definition: MachineOperand.h:500
llvm::LiveVariables::VarInfo::Kills
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction's which are the last use of this virtual register (kill it) in the...
Definition: LiveVariables.h:89
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::TargetRegisterInfo::isInAllocatableClass
bool isInAllocatableClass(MCRegister RegNo) const
Return true if the register is in the allocation of any register class.
Definition: TargetRegisterInfo.h:361
ErrorHandling.h
llvm::MCRegisterInfo::getNumRegs
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Definition: MCRegisterInfo.h:491
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:124
livevars
livevars
Definition: LiveVariables.cpp:49
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:753
llvm::MachineBasicBlock::liveins
iterator_range< livein_iterator > liveins() const
Definition: MachineBasicBlock.h:412
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:757
llvm::SmallPtrSet< const MachineBasicBlock *, 8 >
llvm::Register::index2VirtReg
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
replace
static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New)
Definition: ConstantMerge.cpp:116
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl::count
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:97
llvm::LiveVariables::VarInfo::findKill
MachineInstr * findKill(const MachineBasicBlock *MBB) const
findKill - Find a kill instruction in MBB. Return NULL if none is found.
Definition: LiveVariables.cpp:60
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
DepthFirstIterator.h
MachineRegisterInfo.h
llvm::SparseBitVector::empty
bool empty() const
Definition: SparseBitVector.h:795
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineOperand::isKill
bool isKill() const
Definition: MachineOperand.h:390
llvm::SparseBitVector
Definition: SparseBitVector.h:255
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:820
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:636
llvm::LiveVariables::VarInfo::removeKill
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:94
llvm::LiveVariables::VarInfo
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:79
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:370
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:499
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:915
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
LiveVariables.h
DenseSet.h
llvm::MachineInstr::addRegisterKilled
bool addRegisterKilled(Register IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI kills a register.
Definition: MachineInstr.cpp:1878
false
Definition: StackSlotColoring.cpp:142
llvm::LiveVariables::replaceKillInstruction
void replaceKillInstruction(Register Reg, MachineInstr &OldMI, MachineInstr &NewMI)
replaceKillInstruction - Update register kill info by replacing a kill instruction with a new one.
Definition: LiveVariables.cpp:674
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:251
llvm::MachineBasicBlock::pred_rbegin
pred_reverse_iterator pred_rbegin()
Definition: MachineBasicBlock.h:320
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
llvm::LiveVariables::VarInfo::dump
void dump() const
Definition: LiveVariables.cpp:68
SmallPtrSet.h
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:400
llvm::LiveVariables::HandleVirtRegDef
void HandleVirtRegDef(Register reg, MachineInstr &MI)
Definition: LiveVariables.cpp:178
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::MachineRegisterInfo::isSSA
bool isSSA() const
Definition: MachineRegisterInfo.h:185
Passes.h
llvm::DenseSet< unsigned >
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:626
llvm::MachineOperand::clobbersPhysReg
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
Definition: MachineOperand.h:617
llvm::LiveVariables::addNewBlock
void addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB)
addNewBlock - Add a new basic block BB between DomBB and SuccBB.
Definition: LiveVariables.cpp:755
VI
@ VI
Definition: SIInstrInfo.cpp:7679
llvm::SmallSet::count
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164
llvm::MachineOperand::setIsDead
void setIsDead(bool Val=true)
Definition: MachineOperand.h:506
llvm::SparseBitVector::set
void set(unsigned Idx)
Definition: SparseBitVector.h:507
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:321
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:385
llvm::SparseBitVector::test
bool test(unsigned Idx) const
Definition: SparseBitVector.h:471
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LiveVariablesID
char & LiveVariablesID
LiveVariables pass - This pass computes the set of blocks in which each variable is life and sets mac...
Definition: LiveVariables.cpp:45
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineOperand::isEarlyClobber
bool isEarlyClobber() const
Definition: MachineOperand.h:436
removed
currently compiles eax eax je LBB0_3 testl eax jne LBB0_4 the testl could be removed
Definition: README.txt:1552
llvm::MCSuperRegIterator
MCSuperRegIterator enumerates all super-registers of Reg.
Definition: MCRegisterInfo.h:641
llvm::MachineOperand::isRegMask
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Definition: MachineOperand.h:345
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:349
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::SmallSet::erase
bool erase(const T &V)
Definition: SmallSet.h:207
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:69
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1056
llvm::UnreachableMachineBlockElimID
char & UnreachableMachineBlockElimID
UnreachableMachineBlockElimination - This pass removes unreachable machine basic blocks.
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
llvm::MachineOperand::setIsEarlyClobber
void setIsEarlyClobber(bool Val=true)
Definition: MachineOperand.h:523
llvm::X86AS::SS
@ SS
Definition: X86.h:189
llvm::LiveVariables::isLiveOut
bool isLiveOut(Register Reg, const MachineBasicBlock &MBB)
isLiveOut - Determine if Reg is live out from MBB, when not considering PHI nodes.
Definition: LiveVariables.cpp:730
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:375
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:180
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:286
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
j
return j(j<< 16)
llvm::MachineOperand::readsReg
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
Definition: MachineOperand.h:458
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::MCRegisterInfo::isSubRegister
bool isSubRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a sub-register of RegA.
Definition: MCRegisterInfo.h:560
llvm::LiveVariables::removeVirtualRegistersKilled
void removeVirtualRegistersKilled(MachineInstr &MI)
removeVirtualRegistersKilled - Remove all killed info for the specified instruction.
Definition: LiveVariables.cpp:682
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:594
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:492
llvm::MachineInstr::addOperand
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
Definition: MachineInstr.cpp:207
llvm::LiveVariables::HandleVirtRegUse
void HandleVirtRegUse(Register reg, MachineBasicBlock *MBB, MachineInstr &MI)
Definition: LiveVariables.cpp:127
llvm::LiveVariables::getVarInfo
VarInfo & getVarInfo(Register Reg)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
Definition: LiveVariables.cpp:84
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LiveVariables, "livevars", "Live Variable Analysis", false, false) INITIALIZE_PASS_END(LiveVariables
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::MachineBasicBlock::pred_rend
pred_reverse_iterator pred_rend()
Definition: MachineBasicBlock.h:324
llvm::LiveVariables
Definition: LiveVariables.h:46
raw_ostream.h
llvm::VirtRegInfo
VirtRegInfo - Information about a virtual register used by a set of operands.
Definition: MachineInstrBundle.h:218
llvm::SmallPtrSetImpl< NodeRef >::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:388
llvm::MachineInstr::findRegisterDefOperand
MachineOperand * findRegisterDefOperand(Register 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...
Definition: MachineInstr.h:1457
llvm::MachineInstrBundleIterator< MachineInstr >
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
SubReg
unsigned SubReg
Definition: AArch64AdvSIMDScalarPass.cpp:104
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
SmallSet.h
llvm::SmallPtrSetImpl::insert
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:364
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:773
llvm::LiveVariables::VarInfo::AliveBlocks
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:84