LLVM  13.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.back();
123  WorkList.pop_back();
124  MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList);
125  }
126 }
127 
129  MachineInstr &MI) {
130  assert(MRI->getVRegDef(Reg) && "Register use before def!");
131 
132  unsigned BBNum = MBB->getNumber();
133 
134  VarInfo &VRInfo = getVarInfo(Reg);
135 
136  // Check to see if this basic block is already a kill block.
137  if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) {
138  // Yes, this register is killed in this basic block already. Increase the
139  // live range by updating the kill instruction.
140  VRInfo.Kills.back() = &MI;
141  return;
142  }
143 
144 #ifndef NDEBUG
145  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
146  assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!");
147 #endif
148 
149  // This situation can occur:
150  //
151  // ,------.
152  // | |
153  // | v
154  // | t2 = phi ... t1 ...
155  // | |
156  // | v
157  // | t1 = ...
158  // | ... = ... t1 ...
159  // | |
160  // `------'
161  //
162  // where there is a use in a PHI node that's a predecessor to the defining
163  // block. We don't want to mark all predecessors as having the value "alive"
164  // in this case.
165  if (MBB == MRI->getVRegDef(Reg)->getParent())
166  return;
167 
168  // Add a new kill entry for this basic block. If this virtual register is
169  // already marked as alive in this basic block, that means it is alive in at
170  // least one of the successor blocks, it's not a kill.
171  if (!VRInfo.AliveBlocks.test(BBNum))
172  VRInfo.Kills.push_back(&MI);
173 
174  // Update all dominating blocks to mark them as "known live".
175  for (MachineBasicBlock *Pred : MBB->predecessors())
176  MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(Reg)->getParent(), Pred);
177 }
178 
180  VarInfo &VRInfo = getVarInfo(Reg);
181 
182  if (VRInfo.AliveBlocks.empty())
183  // If vr is not alive in any block, then defaults to dead.
184  VRInfo.Kills.push_back(&MI);
185 }
186 
187 /// FindLastPartialDef - Return the last partial def of the specified register.
188 /// Also returns the sub-registers that're defined by the instruction.
189 MachineInstr *
190 LiveVariables::FindLastPartialDef(Register Reg,
191  SmallSet<unsigned, 4> &PartDefRegs) {
192  unsigned LastDefReg = 0;
193  unsigned LastDefDist = 0;
194  MachineInstr *LastDef = nullptr;
195  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
196  unsigned SubReg = *SubRegs;
197  MachineInstr *Def = PhysRegDef[SubReg];
198  if (!Def)
199  continue;
200  unsigned Dist = DistanceMap[Def];
201  if (Dist > LastDefDist) {
202  LastDefReg = SubReg;
203  LastDef = Def;
204  LastDefDist = Dist;
205  }
206  }
207 
208  if (!LastDef)
209  return nullptr;
210 
211  PartDefRegs.insert(LastDefReg);
212  for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) {
213  MachineOperand &MO = LastDef->getOperand(i);
214  if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0)
215  continue;
216  Register DefReg = MO.getReg();
217  if (TRI->isSubRegister(Reg, DefReg)) {
218  for (MCSubRegIterator SubRegs(DefReg, TRI, /*IncludeSelf=*/true);
219  SubRegs.isValid(); ++SubRegs)
220  PartDefRegs.insert(*SubRegs);
221  }
222  }
223  return LastDef;
224 }
225 
226 /// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add
227 /// implicit defs to a machine instruction if there was an earlier def of its
228 /// super-register.
229 void LiveVariables::HandlePhysRegUse(Register Reg, MachineInstr &MI) {
230  MachineInstr *LastDef = PhysRegDef[Reg];
231  // If there was a previous use or a "full" def all is well.
232  if (!LastDef && !PhysRegUse[Reg]) {
233  // Otherwise, the last sub-register def implicitly defines this register.
234  // e.g.
235  // AH =
236  // AL = ... implicit-def EAX, implicit killed AH
237  // = AH
238  // ...
239  // = EAX
240  // All of the sub-registers must have been defined before the use of Reg!
241  SmallSet<unsigned, 4> PartDefRegs;
242  MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs);
243  // If LastPartialDef is NULL, it must be using a livein register.
244  if (LastPartialDef) {
245  LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
246  true/*IsImp*/));
247  PhysRegDef[Reg] = LastPartialDef;
248  SmallSet<unsigned, 8> Processed;
249  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
250  unsigned SubReg = *SubRegs;
251  if (Processed.count(SubReg))
252  continue;
253  if (PartDefRegs.count(SubReg))
254  continue;
255  // This part of Reg was defined before the last partial def. It's killed
256  // here.
258  false/*IsDef*/,
259  true/*IsImp*/));
260  PhysRegDef[SubReg] = LastPartialDef;
261  for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS)
262  Processed.insert(*SS);
263  }
264  }
265  } else if (LastDef && !PhysRegUse[Reg] &&
266  !LastDef->findRegisterDefOperand(Reg))
267  // Last def defines the super register, add an implicit def of reg.
268  LastDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
269  true/*IsImp*/));
270 
271  // Remember this use.
272  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
273  SubRegs.isValid(); ++SubRegs)
274  PhysRegUse[*SubRegs] = &MI;
275 }
276 
277 /// FindLastRefOrPartRef - Return the last reference or partial reference of
278 /// the specified register.
279 MachineInstr *LiveVariables::FindLastRefOrPartRef(Register Reg) {
280  MachineInstr *LastDef = PhysRegDef[Reg];
281  MachineInstr *LastUse = PhysRegUse[Reg];
282  if (!LastDef && !LastUse)
283  return nullptr;
284 
285  MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
286  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
287  unsigned LastPartDefDist = 0;
288  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
289  unsigned SubReg = *SubRegs;
290  MachineInstr *Def = PhysRegDef[SubReg];
291  if (Def && Def != LastDef) {
292  // There was a def of this sub-register in between. This is a partial
293  // def, keep track of the last one.
294  unsigned Dist = DistanceMap[Def];
295  if (Dist > LastPartDefDist)
296  LastPartDefDist = Dist;
297  } else if (MachineInstr *Use = PhysRegUse[SubReg]) {
298  unsigned Dist = DistanceMap[Use];
299  if (Dist > LastRefOrPartRefDist) {
300  LastRefOrPartRefDist = Dist;
301  LastRefOrPartRef = Use;
302  }
303  }
304  }
305 
306  return LastRefOrPartRef;
307 }
308 
309 bool LiveVariables::HandlePhysRegKill(Register Reg, MachineInstr *MI) {
310  MachineInstr *LastDef = PhysRegDef[Reg];
311  MachineInstr *LastUse = PhysRegUse[Reg];
312  if (!LastDef && !LastUse)
313  return false;
314 
315  MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
316  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
317  // The whole register is used.
318  // AL =
319  // AH =
320  //
321  // = AX
322  // = AL, implicit killed AX
323  // AX =
324  //
325  // Or whole register is defined, but not used at all.
326  // dead AX =
327  // ...
328  // AX =
329  //
330  // Or whole register is defined, but only partly used.
331  // dead AX = implicit-def AL
332  // = killed AL
333  // AX =
334  MachineInstr *LastPartDef = nullptr;
335  unsigned LastPartDefDist = 0;
336  SmallSet<unsigned, 8> PartUses;
337  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
338  unsigned SubReg = *SubRegs;
339  MachineInstr *Def = PhysRegDef[SubReg];
340  if (Def && Def != LastDef) {
341  // There was a def of this sub-register in between. This is a partial
342  // def, keep track of the last one.
343  unsigned Dist = DistanceMap[Def];
344  if (Dist > LastPartDefDist) {
345  LastPartDefDist = Dist;
346  LastPartDef = Def;
347  }
348  continue;
349  }
350  if (MachineInstr *Use = PhysRegUse[SubReg]) {
351  for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); SS.isValid();
352  ++SS)
353  PartUses.insert(*SS);
354  unsigned Dist = DistanceMap[Use];
355  if (Dist > LastRefOrPartRefDist) {
356  LastRefOrPartRefDist = Dist;
357  LastRefOrPartRef = Use;
358  }
359  }
360  }
361 
362  if (!PhysRegUse[Reg]) {
363  // Partial uses. Mark register def dead and add implicit def of
364  // sub-registers which are used.
365  // dead EAX = op implicit-def AL
366  // That is, EAX def is dead but AL def extends pass it.
367  PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true);
368  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
369  unsigned SubReg = *SubRegs;
370  if (!PartUses.count(SubReg))
371  continue;
372  bool NeedDef = true;
373  if (PhysRegDef[Reg] == PhysRegDef[SubReg]) {
374  MachineOperand *MO = PhysRegDef[Reg]->findRegisterDefOperand(SubReg);
375  if (MO) {
376  NeedDef = false;
377  assert(!MO->isDead());
378  }
379  }
380  if (NeedDef)
381  PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg,
382  true/*IsDef*/, true/*IsImp*/));
383  MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg);
384  if (LastSubRef)
385  LastSubRef->addRegisterKilled(SubReg, TRI, true);
386  else {
387  LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
388  for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true);
389  SS.isValid(); ++SS)
390  PhysRegUse[*SS] = LastRefOrPartRef;
391  }
392  for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++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, 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 
420 void 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 (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR)
435  if ((PhysRegDef[*SR] || PhysRegUse[*SR]) && MO.clobbersPhysReg(*SR))
436  Super = *SR;
437  HandlePhysRegKill(Super, nullptr);
438  }
439 }
440 
441 void LiveVariables::HandlePhysRegDef(Register Reg, MachineInstr *MI,
443  // What parts of the register are previously defined?
445  if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
446  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
447  SubRegs.isValid(); ++SubRegs)
448  Live.insert(*SubRegs);
449  } else {
450  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
451  unsigned SubReg = *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  for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true);
462  SS.isValid(); ++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 (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
473  unsigned SubReg = *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 
484 void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI,
486  while (!Defs.empty()) {
487  Register Reg = Defs.back();
488  Defs.pop_back();
489  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
490  SubRegs.isValid(); ++SubRegs) {
491  unsigned SubReg = *SubRegs;
492  PhysRegDef[SubReg] = &MI;
493  PhysRegUse[SubReg] = nullptr;
494  }
495  }
496 }
497 
498 void LiveVariables::runOnInstr(MachineInstr &MI,
500  assert(!MI.isDebugInstr());
501  // Process all of the operands of the instruction...
502  unsigned NumOperandsToProcess = MI.getNumOperands();
503 
504  // Unless it is a PHI node. In this case, ONLY process the DEF, not any
505  // of the uses. They will be handled in other basic blocks.
506  if (MI.isPHI())
507  NumOperandsToProcess = 1;
508 
509  // Clear kill and dead markers. LV will recompute them.
510  SmallVector<unsigned, 4> UseRegs;
511  SmallVector<unsigned, 4> DefRegs;
512  SmallVector<unsigned, 1> RegMasks;
513  for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
514  MachineOperand &MO = MI.getOperand(i);
515  if (MO.isRegMask()) {
516  RegMasks.push_back(i);
517  continue;
518  }
519  if (!MO.isReg() || MO.getReg() == 0)
520  continue;
521  Register MOReg = MO.getReg();
522  if (MO.isUse()) {
523  if (!(Register::isPhysicalRegister(MOReg) && MRI->isReserved(MOReg)))
524  MO.setIsKill(false);
525  if (MO.readsReg())
526  UseRegs.push_back(MOReg);
527  } else {
528  assert(MO.isDef());
529  // FIXME: We should not remove any dead flags. However the MIPS RDDSP
530  // instruction needs it at the moment: http://llvm.org/PR27116.
531  if (Register::isPhysicalRegister(MOReg) && !MRI->isReserved(MOReg))
532  MO.setIsDead(false);
533  DefRegs.push_back(MOReg);
534  }
535  }
536 
537  MachineBasicBlock *MBB = MI.getParent();
538  // Process all uses.
539  for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) {
540  unsigned MOReg = UseRegs[i];
541  if (Register::isVirtualRegister(MOReg))
542  HandleVirtRegUse(MOReg, MBB, MI);
543  else if (!MRI->isReserved(MOReg))
544  HandlePhysRegUse(MOReg, MI);
545  }
546 
547  // Process all masked registers. (Call clobbers).
548  for (unsigned i = 0, e = RegMasks.size(); i != e; ++i)
549  HandleRegMask(MI.getOperand(RegMasks[i]));
550 
551  // Process all defs.
552  for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) {
553  unsigned MOReg = DefRegs[i];
554  if (Register::isVirtualRegister(MOReg))
555  HandleVirtRegDef(MOReg, MI);
556  else if (!MRI->isReserved(MOReg))
557  HandlePhysRegDef(MOReg, &MI, Defs);
558  }
559  UpdatePhysRegDefs(MI, Defs);
560 }
561 
562 void LiveVariables::runOnBlock(MachineBasicBlock *MBB, const unsigned NumRegs) {
563  // Mark live-in registers as live-in.
565  for (const auto &LI : MBB->liveins()) {
566  assert(Register::isPhysicalRegister(LI.PhysReg) &&
567  "Cannot have a live-in virtual register!");
568  HandlePhysRegDef(LI.PhysReg, nullptr, Defs);
569  }
570 
571  // Loop over all of the instructions, processing them.
572  DistanceMap.clear();
573  unsigned Dist = 0;
574  for (MachineInstr &MI : *MBB) {
575  if (MI.isDebugInstr())
576  continue;
577  DistanceMap.insert(std::make_pair(&MI, Dist++));
578 
579  runOnInstr(MI, Defs);
580  }
581 
582  // Handle any virtual assignments from PHI nodes which might be at the
583  // bottom of this basic block. We check all of our successor blocks to see
584  // if they have PHI nodes, and if so, we simulate an assignment at the end
585  // of the current block.
586  if (!PHIVarInfo[MBB->getNumber()].empty()) {
587  SmallVectorImpl<unsigned> &VarInfoVec = PHIVarInfo[MBB->getNumber()];
588 
589  for (unsigned I : VarInfoVec)
590  // Mark it alive only in the block we are representing.
592  MBB);
593  }
594 
595  // MachineCSE may CSE instructions which write to non-allocatable physical
596  // registers across MBBs. Remember if any reserved register is liveout.
597  SmallSet<unsigned, 4> LiveOuts;
598  for (const MachineBasicBlock *SuccMBB : MBB->successors()) {
599  if (SuccMBB->isEHPad())
600  continue;
601  for (const auto &LI : SuccMBB->liveins()) {
602  if (!TRI->isInAllocatableClass(LI.PhysReg))
603  // Ignore other live-ins, e.g. those that are live into landing pads.
604  LiveOuts.insert(LI.PhysReg);
605  }
606  }
607 
608  // Loop over PhysRegDef / PhysRegUse, killing any registers that are
609  // available at the end of the basic block.
610  for (unsigned i = 0; i != NumRegs; ++i)
611  if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i))
612  HandlePhysRegDef(i, nullptr, Defs);
613 }
614 
616  MF = &mf;
617  MRI = &mf.getRegInfo();
618  TRI = MF->getSubtarget().getRegisterInfo();
619 
620  const unsigned NumRegs = TRI->getNumRegs();
621  PhysRegDef.assign(NumRegs, nullptr);
622  PhysRegUse.assign(NumRegs, nullptr);
623  PHIVarInfo.resize(MF->getNumBlockIDs());
624  PHIJoins.clear();
625 
626  // FIXME: LiveIntervals will be updated to remove its dependence on
627  // LiveVariables to improve compilation time and eliminate bizarre pass
628  // dependencies. Until then, we can't change much in -O0.
629  if (!MRI->isSSA())
630  report_fatal_error("regalloc=... not currently supported with -O0");
631 
632  analyzePHINodes(mf);
633 
634  // Calculate live variable information in depth first order on the CFG of the
635  // function. This guarantees that we will see the definition of a virtual
636  // register before its uses due to dominance properties of SSA (except for PHI
637  // nodes, which are treated as a special case).
638  MachineBasicBlock *Entry = &MF->front();
640 
641  for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) {
642  runOnBlock(MBB, NumRegs);
643 
644  PhysRegDef.assign(NumRegs, nullptr);
645  PhysRegUse.assign(NumRegs, nullptr);
646  }
647 
648  // Convert and transfer the dead / killed information we have gathered into
649  // VirtRegInfo onto MI's.
650  for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) {
652  for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j)
653  if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg))
654  VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI);
655  else
656  VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI);
657  }
658 
659  // Check to make sure there are no unreachable blocks in the MC CFG for the
660  // function. If so, it is due to a bug in the instruction selector or some
661  // other part of the code generator if this happens.
662 #ifndef NDEBUG
663  for (const MachineBasicBlock &MBB : *MF)
664  assert(Visited.contains(&MBB) && "unreachable basic block found");
665 #endif
666 
667  PhysRegDef.clear();
668  PhysRegUse.clear();
669  PHIVarInfo.clear();
670 
671  return false;
672 }
673 
674 /// replaceKillInstruction - Update register kill info by replacing a kill
675 /// instruction with a new one.
677  MachineInstr &NewMI) {
678  VarInfo &VI = getVarInfo(Reg);
679  std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
680 }
681 
682 /// removeVirtualRegistersKilled - Remove all killed info for the specified
683 /// instruction.
685  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
686  MachineOperand &MO = MI.getOperand(i);
687  if (MO.isReg() && MO.isKill()) {
688  MO.setIsKill(false);
689  Register Reg = MO.getReg();
692  assert(removed && "kill not in register's VarInfo?");
693  (void)removed;
694  }
695  }
696  }
697 }
698 
699 /// analyzePHINodes - Gather information about the PHI nodes in here. In
700 /// particular, we want to map the variable information of a virtual register
701 /// which is used in a PHI node. We map that to the BB the vreg is coming from.
702 ///
703 void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
704  for (const auto &MBB : Fn)
705  for (const auto &BBI : MBB) {
706  if (!BBI.isPHI())
707  break;
708  for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
709  if (BBI.getOperand(i).readsReg())
710  PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()]
711  .push_back(BBI.getOperand(i).getReg());
712  }
713 }
714 
717  unsigned Num = MBB.getNumber();
718 
719  // Reg is live-through.
720  if (AliveBlocks.test(Num))
721  return true;
722 
723  // Registers defined in MBB cannot be live in.
724  const MachineInstr *Def = MRI.getVRegDef(Reg);
725  if (Def && Def->getParent() == &MBB)
726  return false;
727 
728  // Reg was not defined in MBB, was it killed here?
729  return findKill(&MBB);
730 }
731 
734 
736  for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
737  Kills.insert(VI.Kills[i]->getParent());
738 
739  // Loop over all of the successors of the basic block, checking to see if
740  // the value is either live in the block, or if it is killed in the block.
741  for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
742  // Is it alive in this successor?
743  unsigned SuccIdx = SuccMBB->getNumber();
744  if (VI.AliveBlocks.test(SuccIdx))
745  return true;
746  // Or is it live because there is a use in a successor that kills it?
747  if (Kills.count(SuccMBB))
748  return true;
749  }
750 
751  return false;
752 }
753 
754 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
755 /// variables that are live out of DomBB will be marked as passing live through
756 /// BB.
758  MachineBasicBlock *DomBB,
759  MachineBasicBlock *SuccBB) {
760  const unsigned NumNew = BB->getNumber();
761 
762  DenseSet<unsigned> Defs, Kills;
763 
764  MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end();
765  for (; BBI != BBE && BBI->isPHI(); ++BBI) {
766  // Record the def of the PHI node.
767  Defs.insert(BBI->getOperand(0).getReg());
768 
769  // All registers used by PHI nodes in SuccBB must be live through BB.
770  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
771  if (BBI->getOperand(i+1).getMBB() == BB)
772  getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
773  }
774 
775  // Record all vreg defs and kills of all instructions in SuccBB.
776  for (; BBI != BBE; ++BBI) {
777  for (const MachineOperand &Op : BBI->operands()) {
778  if (Op.isReg() && Register::isVirtualRegister(Op.getReg())) {
779  if (Op.isDef())
780  Defs.insert(Op.getReg());
781  else if (Op.isKill())
782  Kills.insert(Op.getReg());
783  }
784  }
785  }
786 
787  // Update info for all live variables
788  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
790 
791  // If the Defs is defined in the successor it can't be live in BB.
792  if (Defs.count(Reg))
793  continue;
794 
795  // If the register is either killed in or live through SuccBB it's also live
796  // through BB.
797  VarInfo &VI = getVarInfo(Reg);
798  if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber()))
799  VI.AliveBlocks.set(NumNew);
800  }
801 }
802 
803 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
804 /// variables that are live out of DomBB will be marked as passing live through
805 /// BB. LiveInSets[BB] is *not* updated (because it is not needed during
806 /// PHIElimination).
808  MachineBasicBlock *DomBB,
809  MachineBasicBlock *SuccBB,
810  std::vector<SparseBitVector<>> &LiveInSets) {
811  const unsigned NumNew = BB->getNumber();
812 
813  SparseBitVector<> &BV = LiveInSets[SuccBB->getNumber()];
814  for (unsigned R : BV) {
815  Register VirtReg = Register::index2VirtReg(R);
817  VI.AliveBlocks.set(NumNew);
818  }
819  // All registers used by PHI nodes in SuccBB must be live through BB.
820  for (MachineBasicBlock::iterator BBI = SuccBB->begin(),
821  BBE = SuccBB->end();
822  BBI != BBE && BBI->isPHI(); ++BBI) {
823  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
824  if (BBI->getOperand(i + 1).getMBB() == BB &&
825  BBI->getOperand(i).readsReg())
826  getVarInfo(BBI->getOperand(i).getReg())
827  .AliveBlocks.set(NumNew);
828  }
829 }
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:715
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:100
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:499
llvm
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:615
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:788
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:497
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:345
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::X86AS::SS
@ SS
Definition: X86.h:184
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:682
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
replace
static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New)
Definition: ConstantMerge.cpp:114
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
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
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:132
llvm::MachineOperand::isKill
bool isKill() const
Definition: MachineOperand.h:387
llvm::SparseBitVector
Definition: SparseBitVector.h:255
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:749
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:565
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:367
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:488
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:900
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:676
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
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: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:179
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
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:555
llvm::MachineOperand::clobbersPhysReg
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
Definition: MachineOperand.h:614
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:757
VI
@ VI
Definition: SIInstrInfo.cpp:7343
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:503
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:318
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:382
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:433
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:342
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:357
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:227
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:965
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:520
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:732
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:759
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:372
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:455
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
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:684
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:481
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:128
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:1444
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