LLVM  16.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 (MachineInstr *MI : Kills)
62  if (MI->getParent() == MBB)
63  return MI;
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 (MachineInstr *Kill : VRInfo.Kills)
145  assert(Kill->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 MOReg : UseRegs) {
538  if (Register::isVirtualRegister(MOReg))
539  HandleVirtRegUse(MOReg, MBB, MI);
540  else if (!MRI->isReserved(MOReg))
541  HandlePhysRegUse(MOReg, MI);
542  }
543 
544  // Process all masked registers. (Call clobbers).
545  for (unsigned Mask : RegMasks)
546  HandleRegMask(MI.getOperand(Mask));
547 
548  // Process all defs.
549  for (unsigned MOReg : DefRegs) {
550  if (Register::isVirtualRegister(MOReg))
551  HandleVirtRegDef(MOReg, MI);
552  else if (!MRI->isReserved(MOReg))
553  HandlePhysRegDef(MOReg, &MI, Defs);
554  }
555  UpdatePhysRegDefs(MI, Defs);
556 }
557 
558 void LiveVariables::runOnBlock(MachineBasicBlock *MBB, const unsigned NumRegs) {
559  // Mark live-in registers as live-in.
561  for (const auto &LI : MBB->liveins()) {
562  assert(Register::isPhysicalRegister(LI.PhysReg) &&
563  "Cannot have a live-in virtual register!");
564  HandlePhysRegDef(LI.PhysReg, nullptr, Defs);
565  }
566 
567  // Loop over all of the instructions, processing them.
568  DistanceMap.clear();
569  unsigned Dist = 0;
570  for (MachineInstr &MI : *MBB) {
571  if (MI.isDebugOrPseudoInstr())
572  continue;
573  DistanceMap.insert(std::make_pair(&MI, Dist++));
574 
575  runOnInstr(MI, Defs);
576  }
577 
578  // Handle any virtual assignments from PHI nodes which might be at the
579  // bottom of this basic block. We check all of our successor blocks to see
580  // if they have PHI nodes, and if so, we simulate an assignment at the end
581  // of the current block.
582  if (!PHIVarInfo[MBB->getNumber()].empty()) {
583  SmallVectorImpl<unsigned> &VarInfoVec = PHIVarInfo[MBB->getNumber()];
584 
585  for (unsigned I : VarInfoVec)
586  // Mark it alive only in the block we are representing.
588  MBB);
589  }
590 
591  // MachineCSE may CSE instructions which write to non-allocatable physical
592  // registers across MBBs. Remember if any reserved register is liveout.
593  SmallSet<unsigned, 4> LiveOuts;
594  for (const MachineBasicBlock *SuccMBB : MBB->successors()) {
595  if (SuccMBB->isEHPad())
596  continue;
597  for (const auto &LI : SuccMBB->liveins()) {
598  if (!TRI->isInAllocatableClass(LI.PhysReg))
599  // Ignore other live-ins, e.g. those that are live into landing pads.
600  LiveOuts.insert(LI.PhysReg);
601  }
602  }
603 
604  // Loop over PhysRegDef / PhysRegUse, killing any registers that are
605  // available at the end of the basic block.
606  for (unsigned i = 0; i != NumRegs; ++i)
607  if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i))
608  HandlePhysRegDef(i, nullptr, Defs);
609 }
610 
612  MF = &mf;
613  MRI = &mf.getRegInfo();
614  TRI = MF->getSubtarget().getRegisterInfo();
615 
616  const unsigned NumRegs = TRI->getNumRegs();
617  PhysRegDef.assign(NumRegs, nullptr);
618  PhysRegUse.assign(NumRegs, nullptr);
619  PHIVarInfo.resize(MF->getNumBlockIDs());
620  PHIJoins.clear();
621 
622  // FIXME: LiveIntervals will be updated to remove its dependence on
623  // LiveVariables to improve compilation time and eliminate bizarre pass
624  // dependencies. Until then, we can't change much in -O0.
625  if (!MRI->isSSA())
626  report_fatal_error("regalloc=... not currently supported with -O0");
627 
628  analyzePHINodes(mf);
629 
630  // Calculate live variable information in depth first order on the CFG of the
631  // function. This guarantees that we will see the definition of a virtual
632  // register before its uses due to dominance properties of SSA (except for PHI
633  // nodes, which are treated as a special case).
634  MachineBasicBlock *Entry = &MF->front();
636 
637  for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) {
638  runOnBlock(MBB, NumRegs);
639 
640  PhysRegDef.assign(NumRegs, nullptr);
641  PhysRegUse.assign(NumRegs, nullptr);
642  }
643 
644  // Convert and transfer the dead / killed information we have gathered into
645  // VirtRegInfo onto MI's.
646  for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) {
648  for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j)
649  if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg))
650  VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI);
651  else
652  VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI);
653  }
654 
655  // Check to make sure there are no unreachable blocks in the MC CFG for the
656  // function. If so, it is due to a bug in the instruction selector or some
657  // other part of the code generator if this happens.
658 #ifndef NDEBUG
659  for (const MachineBasicBlock &MBB : *MF)
660  assert(Visited.contains(&MBB) && "unreachable basic block found");
661 #endif
662 
663  PhysRegDef.clear();
664  PhysRegUse.clear();
665  PHIVarInfo.clear();
666 
667  return false;
668 }
669 
671  assert(Reg.isVirtual());
672 
673  VarInfo &VI = getVarInfo(Reg);
674  VI.AliveBlocks.clear();
675  VI.Kills.clear();
676 
678  MachineBasicBlock &DefBB = *DefMI.getParent();
679 
680  // Handle the case where all uses have been removed.
681  if (MRI->use_nodbg_empty(Reg)) {
682  VI.Kills.push_back(&DefMI);
683  DefMI.addRegisterDead(Reg, nullptr);
684  return;
685  }
686  DefMI.clearRegisterDeads(Reg);
687 
688  // Initialize a worklist of BBs that Reg is live-to-end of. (Here
689  // "live-to-end" means Reg is live at the end of a block even if it is only
690  // live because of phi uses in a successor. This is different from isLiveOut()
691  // which does not consider phi uses.)
692  SmallVector<MachineBasicBlock *> LiveToEndBlocks;
693  SparseBitVector<> UseBlocks;
694  for (auto &UseMO : MRI->use_nodbg_operands(Reg)) {
695  UseMO.setIsKill(false);
696  MachineInstr &UseMI = *UseMO.getParent();
697  MachineBasicBlock &UseBB = *UseMI.getParent();
698  UseBlocks.set(UseBB.getNumber());
699  if (UseMI.isPHI()) {
700  // If Reg is used in a phi then it is live-to-end of the corresponding
701  // predecessor.
702  unsigned Idx = UseMI.getOperandNo(&UseMO);
703  LiveToEndBlocks.push_back(UseMI.getOperand(Idx + 1).getMBB());
704  } else if (&UseBB == &DefBB) {
705  // A non-phi use in the same BB as the single def must come after the def.
706  } else {
707  // Otherwise Reg must be live-to-end of all predecessors.
708  LiveToEndBlocks.append(UseBB.pred_begin(), UseBB.pred_end());
709  }
710  }
711 
712  // Iterate over the worklist adding blocks to AliveBlocks.
713  bool LiveToEndOfDefBB = false;
714  while (!LiveToEndBlocks.empty()) {
715  MachineBasicBlock &BB = *LiveToEndBlocks.pop_back_val();
716  if (&BB == &DefBB) {
717  LiveToEndOfDefBB = true;
718  continue;
719  }
720  if (VI.AliveBlocks.test(BB.getNumber()))
721  continue;
722  VI.AliveBlocks.set(BB.getNumber());
723  LiveToEndBlocks.append(BB.pred_begin(), BB.pred_end());
724  }
725 
726  // Recompute kill flags. For each block in which Reg is used but is not
727  // live-through, find the last instruction that uses Reg. Ignore phi nodes
728  // because they should not be included in Kills.
729  for (unsigned UseBBNum : UseBlocks) {
730  if (VI.AliveBlocks.test(UseBBNum))
731  continue;
732  MachineBasicBlock &UseBB = *MF->getBlockNumbered(UseBBNum);
733  if (&UseBB == &DefBB && LiveToEndOfDefBB)
734  continue;
735  for (auto &MI : reverse(UseBB)) {
736  if (MI.isDebugOrPseudoInstr())
737  continue;
738  if (MI.isPHI())
739  break;
740  if (MI.readsRegister(Reg)) {
741  assert(!MI.killsRegister(Reg));
742  MI.addRegisterKilled(Reg, nullptr);
743  VI.Kills.push_back(&MI);
744  break;
745  }
746  }
747  }
748 }
749 
750 /// replaceKillInstruction - Update register kill info by replacing a kill
751 /// instruction with a new one.
753  MachineInstr &NewMI) {
754  VarInfo &VI = getVarInfo(Reg);
755  std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
756 }
757 
758 /// removeVirtualRegistersKilled - Remove all killed info for the specified
759 /// instruction.
761  for (MachineOperand &MO : MI.operands()) {
762  if (MO.isReg() && MO.isKill()) {
763  MO.setIsKill(false);
764  Register Reg = MO.getReg();
767  assert(removed && "kill not in register's VarInfo?");
768  (void)removed;
769  }
770  }
771  }
772 }
773 
774 /// analyzePHINodes - Gather information about the PHI nodes in here. In
775 /// particular, we want to map the variable information of a virtual register
776 /// which is used in a PHI node. We map that to the BB the vreg is coming from.
777 ///
778 void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
779  for (const auto &MBB : Fn)
780  for (const auto &BBI : MBB) {
781  if (!BBI.isPHI())
782  break;
783  for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
784  if (BBI.getOperand(i).readsReg())
785  PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()]
786  .push_back(BBI.getOperand(i).getReg());
787  }
788 }
789 
792  unsigned Num = MBB.getNumber();
793 
794  // Reg is live-through.
795  if (AliveBlocks.test(Num))
796  return true;
797 
798  // Registers defined in MBB cannot be live in.
799  const MachineInstr *Def = MRI.getVRegDef(Reg);
800  if (Def && Def->getParent() == &MBB)
801  return false;
802 
803  // Reg was not defined in MBB, was it killed here?
804  return findKill(&MBB);
805 }
806 
809 
811  for (MachineInstr *MI : VI.Kills)
812  Kills.insert(MI->getParent());
813 
814  // Loop over all of the successors of the basic block, checking to see if
815  // the value is either live in the block, or if it is killed in the block.
816  for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
817  // Is it alive in this successor?
818  unsigned SuccIdx = SuccMBB->getNumber();
819  if (VI.AliveBlocks.test(SuccIdx))
820  return true;
821  // Or is it live because there is a use in a successor that kills it?
822  if (Kills.count(SuccMBB))
823  return true;
824  }
825 
826  return false;
827 }
828 
829 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
830 /// variables that are live out of DomBB will be marked as passing live through
831 /// BB.
833  MachineBasicBlock *DomBB,
834  MachineBasicBlock *SuccBB) {
835  const unsigned NumNew = BB->getNumber();
836 
837  DenseSet<unsigned> Defs, Kills;
838 
839  MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end();
840  for (; BBI != BBE && BBI->isPHI(); ++BBI) {
841  // Record the def of the PHI node.
842  Defs.insert(BBI->getOperand(0).getReg());
843 
844  // All registers used by PHI nodes in SuccBB must be live through BB.
845  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
846  if (BBI->getOperand(i+1).getMBB() == BB)
847  getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
848  }
849 
850  // Record all vreg defs and kills of all instructions in SuccBB.
851  for (; BBI != BBE; ++BBI) {
852  for (const MachineOperand &Op : BBI->operands()) {
853  if (Op.isReg() && Register::isVirtualRegister(Op.getReg())) {
854  if (Op.isDef())
855  Defs.insert(Op.getReg());
856  else if (Op.isKill())
857  Kills.insert(Op.getReg());
858  }
859  }
860  }
861 
862  // Update info for all live variables
863  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
865 
866  // If the Defs is defined in the successor it can't be live in BB.
867  if (Defs.count(Reg))
868  continue;
869 
870  // If the register is either killed in or live through SuccBB it's also live
871  // through BB.
872  VarInfo &VI = getVarInfo(Reg);
873  if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber()))
874  VI.AliveBlocks.set(NumNew);
875  }
876 }
877 
878 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
879 /// variables that are live out of DomBB will be marked as passing live through
880 /// BB. LiveInSets[BB] is *not* updated (because it is not needed during
881 /// PHIElimination).
883  MachineBasicBlock *DomBB,
884  MachineBasicBlock *SuccBB,
885  std::vector<SparseBitVector<>> &LiveInSets) {
886  const unsigned NumNew = BB->getNumber();
887 
888  SparseBitVector<> &BV = LiveInSets[SuccBB->getNumber()];
889  for (unsigned R : BV) {
890  Register VirtReg = Register::index2VirtReg(R);
892  VI.AliveBlocks.set(NumNew);
893  }
894  // All registers used by PHI nodes in SuccBB must be live through BB.
895  for (MachineBasicBlock::iterator BBI = SuccBB->begin(),
896  BBE = SuccBB->end();
897  BBI != BBE && BBI->isPHI(); ++BBI) {
898  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
899  if (BBI->getOperand(i + 1).getMBB() == BB &&
900  BBI->getOperand(i).readsReg())
901  getVarInfo(BBI->getOperand(i).getReg())
902  .AliveBlocks.set(NumNew);
903  }
904 }
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:790
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:1948
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:353
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
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:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LiveVariables::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: LiveVariables.cpp:611
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::LiveVariables::ID
static char ID
Definition: LiveVariables.h:49
UseMI
MachineInstrBuilder & UseMI
Definition: AArch64ExpandPseudoInsts.cpp:105
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:800
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:50
llvm::SparseBitVector::clear
void clear()
Definition: SparseBitVector.h:452
llvm::MachineOperand::setIsKill
void setIsKill(bool Val=true)
Definition: MachineOperand.h:509
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:90
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1181
llvm::TargetRegisterInfo::isInAllocatableClass
bool isInAllocatableClass(MCRegister RegNo) const
Return true if the register is in the allocation of any register class.
Definition: TargetRegisterInfo.h:365
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::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineRegisterInfo::getUniqueVRegDef
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
Definition: MachineRegisterInfo.cpp:407
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:125
livevars
livevars
Definition: LiveVariables.cpp:49
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:798
llvm::MachineBasicBlock::liveins
iterator_range< livein_iterator > liveins() const
Definition: MachineBasicBlock.h:449
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:770
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: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:167
DepthFirstIterator.h
MachineRegisterInfo.h
llvm::SparseBitVector::empty
bool empty() const
Definition: SparseBitVector.h:796
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:389
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::SparseBitVector
Definition: SparseBitVector.h:256
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:865
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:666
llvm::LiveVariables::VarInfo::removeKill
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:95
llvm::MachineRegisterInfo::use_nodbg_operands
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:534
llvm::LiveVariables::VarInfo
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:80
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:369
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:930
llvm::LiveVariables::recomputeForSingleDefVirtReg
void recomputeForSingleDefVirtReg(Register Reg)
Recompute liveness from scratch for a virtual register Reg that is known to have a single def that do...
Definition: LiveVariables.cpp:670
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:1869
false
Definition: StackSlotColoring.cpp:141
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:752
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:252
llvm::MachineBasicBlock::pred_rbegin
pred_reverse_iterator pred_rbegin()
Definition: MachineBasicBlock.h:357
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:145
llvm::LiveVariables::VarInfo::dump
void dump() const
Definition: LiveVariables.cpp:68
SmallPtrSet.h
llvm::SmallVectorImpl::append
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:669
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:396
llvm::LiveVariables::HandleVirtRegDef
void HandleVirtRegDef(Register reg, MachineInstr &MI)
Definition: LiveVariables.cpp:178
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
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:183
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:656
llvm::MachineOperand::clobbersPhysReg
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
Definition: MachineOperand.h:626
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:832
VI
@ VI
Definition: SIInstrInfo.cpp:7894
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:165
llvm::MachineOperand::setIsDead
void setIsDead(bool Val=true)
Definition: MachineOperand.h:515
llvm::MachineBasicBlock::pred_end
pred_iterator pred_end()
Definition: MachineBasicBlock.h:355
llvm::SparseBitVector::set
void set(unsigned Idx)
Definition: SparseBitVector.h:508
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:384
llvm::SparseBitVector::test
bool test(unsigned Idx) const
Definition: SparseBitVector.h:472
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:435
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:644
llvm::MachineOperand::isRegMask
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Definition: MachineOperand.h:344
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:386
llvm::X86AS::SS
@ SS
Definition: X86.h:201
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:383
llvm::SmallSet::erase
bool erase(const T &V)
Definition: SmallSet.h:206
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:70
llvm::MachineRegisterInfo::use_nodbg_empty
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
Definition: MachineRegisterInfo.h:574
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1115
llvm::UnreachableMachineBlockElimID
char & UnreachableMachineBlockElimID
UnreachableMachineBlockElimination - This pass removes unreachable machine basic blocks.
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:392
llvm::MachineOperand::setIsEarlyClobber
void setIsEarlyClobber(bool Val=true)
Definition: MachineOperand.h:532
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:807
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
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::MachineFunction::getBlockNumbered
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Definition: MachineFunction.h:788
llvm::MachineOperand::readsReg
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
Definition: MachineOperand.h:457
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
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::SmallSet::insert
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:178
llvm::LiveVariables::removeVirtualRegistersKilled
void removeVirtualRegistersKilled(MachineInstr &MI)
removeVirtualRegistersKilled - Remove all killed info for the specified instruction.
Definition: LiveVariables.cpp:760
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:597
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:106
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:519
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:659
llvm::MachineInstr::addOperand
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
Definition: MachineInstr.cpp:184
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:42
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:365
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:361
llvm::LiveVariables
Definition: LiveVariables.h:47
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:389
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:1479
llvm::MachineInstrBundleIterator< MachineInstr >
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
SubReg
unsigned SubReg
Definition: AArch64AdvSIMDScalarPass.cpp:104
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
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:365
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:791
llvm::LiveVariables::VarInfo::AliveBlocks
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:85