LLVM  16.0.0git
MachineCSE.cpp
Go to the documentation of this file.
1 //===- MachineCSE.cpp - Machine Common Subexpression Elimination Pass -----===//
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 pass performs global common subexpression elimination on machine
10 // instructions using a scoped hash table based value numbering scheme. It
11 // must be run while the machine function is still in SSA form.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/CFG.h"
31 #include "llvm/CodeGen/Passes.h"
36 #include "llvm/InitializePasses.h"
37 #include "llvm/MC/MCRegister.h"
38 #include "llvm/MC/MCRegisterInfo.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Support/Allocator.h"
41 #include "llvm/Support/Debug.h"
44 #include <cassert>
45 #include <iterator>
46 #include <utility>
47 #include <vector>
48 
49 using namespace llvm;
50 
51 #define DEBUG_TYPE "machine-cse"
52 
53 STATISTIC(NumCoalesces, "Number of copies coalesced");
54 STATISTIC(NumCSEs, "Number of common subexpression eliminated");
55 STATISTIC(NumPREs, "Number of partial redundant expression"
56  " transformed to fully redundant");
57 STATISTIC(NumPhysCSEs,
58  "Number of physreg referencing common subexpr eliminated");
59 STATISTIC(NumCrossBBCSEs,
60  "Number of cross-MBB physreg referencing CS eliminated");
61 STATISTIC(NumCommutes, "Number of copies coalesced after commuting");
62 
63 // Threshold to avoid excessive cost to compute isProfitableToCSE.
64 static cl::opt<int>
65  CSUsesThreshold("csuses-threshold", cl::Hidden, cl::init(1024),
66  cl::desc("Threshold for the size of CSUses"));
67 
68 namespace {
69 
70  class MachineCSE : public MachineFunctionPass {
71  const TargetInstrInfo *TII;
72  const TargetRegisterInfo *TRI;
73  AliasAnalysis *AA;
77 
78  public:
79  static char ID; // Pass identification
80 
81  MachineCSE() : MachineFunctionPass(ID) {
83  }
84 
85  bool runOnMachineFunction(MachineFunction &MF) override;
86 
87  void getAnalysisUsage(AnalysisUsage &AU) const override {
88  AU.setPreservesCFG();
96  }
97 
98  MachineFunctionProperties getRequiredProperties() const override {
101  }
102 
103  void releaseMemory() override {
104  ScopeMap.clear();
105  PREMap.clear();
106  Exps.clear();
107  }
108 
109  private:
110  using AllocatorTy = RecyclingAllocator<BumpPtrAllocator,
112  using ScopedHTType =
114  AllocatorTy>;
115  using ScopeType = ScopedHTType::ScopeTy;
116  using PhysDefVector = SmallVector<std::pair<unsigned, unsigned>, 2>;
117 
118  unsigned LookAheadLimit = 0;
121  PREMap;
122  ScopedHTType VNT;
124  unsigned CurrVN = 0;
125 
126  bool PerformTrivialCopyPropagation(MachineInstr *MI,
128  bool isPhysDefTriviallyDead(MCRegister Reg,
131  bool hasLivePhysRegDefUses(const MachineInstr *MI,
132  const MachineBasicBlock *MBB,
133  SmallSet<MCRegister, 8> &PhysRefs,
134  PhysDefVector &PhysDefs, bool &PhysUseDef) const;
135  bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
136  SmallSet<MCRegister, 8> &PhysRefs,
137  PhysDefVector &PhysDefs, bool &NonLocal) const;
138  bool isCSECandidate(MachineInstr *MI);
139  bool isProfitableToCSE(Register CSReg, Register Reg,
141  void EnterScope(MachineBasicBlock *MBB);
142  void ExitScope(MachineBasicBlock *MBB);
143  bool ProcessBlockCSE(MachineBasicBlock *MBB);
144  void ExitScopeIfDone(MachineDomTreeNode *Node,
146  bool PerformCSE(MachineDomTreeNode *Node);
147 
148  bool isPRECandidate(MachineInstr *MI, SmallSet<MCRegister, 8> &PhysRefs);
149  bool ProcessBlockPRE(MachineDominatorTree *MDT, MachineBasicBlock *MBB);
150  bool PerformSimplePRE(MachineDominatorTree *DT);
151  /// Heuristics to see if it's profitable to move common computations of MBB
152  /// and MBB1 to CandidateBB.
153  bool isProfitableToHoistInto(MachineBasicBlock *CandidateBB,
155  MachineBasicBlock *MBB1);
156  };
157 
158 } // end anonymous namespace
159 
160 char MachineCSE::ID = 0;
161 
163 
165  "Machine Common Subexpression Elimination", false, false)
169  "Machine Common Subexpression Elimination", false, false)
170 
171 /// The source register of a COPY machine instruction can be propagated to all
172 /// its users, and this propagation could increase the probability of finding
173 /// common subexpressions. If the COPY has only one user, the COPY itself can
174 /// be removed.
175 bool MachineCSE::PerformTrivialCopyPropagation(MachineInstr *MI,
177  bool Changed = false;
178  for (MachineOperand &MO : MI->operands()) {
179  if (!MO.isReg() || !MO.isUse())
180  continue;
181  Register Reg = MO.getReg();
183  continue;
184  bool OnlyOneUse = MRI->hasOneNonDBGUse(Reg);
186  if (!DefMI->isCopy())
187  continue;
188  Register SrcReg = DefMI->getOperand(1).getReg();
189  if (!Register::isVirtualRegister(SrcReg))
190  continue;
191  if (DefMI->getOperand(0).getSubReg())
192  continue;
193  // FIXME: We should trivially coalesce subregister copies to expose CSE
194  // opportunities on instructions with truncated operands (see
195  // cse-add-with-overflow.ll). This can be done here as follows:
196  // if (SrcSubReg)
197  // RC = TRI->getMatchingSuperRegClass(MRI->getRegClass(SrcReg), RC,
198  // SrcSubReg);
199  // MO.substVirtReg(SrcReg, SrcSubReg, *TRI);
200  //
201  // The 2-addr pass has been updated to handle coalesced subregs. However,
202  // some machine-specific code still can't handle it.
203  // To handle it properly we also need a way find a constrained subregister
204  // class given a super-reg class and subreg index.
205  if (DefMI->getOperand(1).getSubReg())
206  continue;
207  if (!MRI->constrainRegAttrs(SrcReg, Reg))
208  continue;
209  LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
210  LLVM_DEBUG(dbgs() << "*** to: " << *MI);
211 
212  // Propagate SrcReg of copies to MI.
213  MO.setReg(SrcReg);
214  MRI->clearKillFlags(SrcReg);
215  // Coalesce single use copies.
216  if (OnlyOneUse) {
217  // If (and only if) we've eliminated all uses of the copy, also
218  // copy-propagate to any debug-users of MI, or they'll be left using
219  // an undefined value.
221 
223  ++NumCoalesces;
224  }
225  Changed = true;
226  }
227 
228  return Changed;
229 }
230 
231 bool MachineCSE::isPhysDefTriviallyDead(
234  unsigned LookAheadLeft = LookAheadLimit;
235  while (LookAheadLeft) {
236  // Skip over dbg_value's.
238 
239  if (I == E)
240  // Reached end of block, we don't know if register is dead or not.
241  return false;
242 
243  bool SeenDef = false;
244  for (const MachineOperand &MO : I->operands()) {
245  if (MO.isRegMask() && MO.clobbersPhysReg(Reg))
246  SeenDef = true;
247  if (!MO.isReg() || !MO.getReg())
248  continue;
249  if (!TRI->regsOverlap(MO.getReg(), Reg))
250  continue;
251  if (MO.isUse())
252  // Found a use!
253  return false;
254  SeenDef = true;
255  }
256  if (SeenDef)
257  // See a def of Reg (or an alias) before encountering any use, it's
258  // trivially dead.
259  return true;
260 
261  --LookAheadLeft;
262  ++I;
263  }
264  return false;
265 }
266 
268  const MachineOperand &MO,
269  const MachineFunction &MF,
270  const TargetRegisterInfo &TRI,
271  const TargetInstrInfo &TII) {
272  // MachineRegisterInfo::isConstantPhysReg directly called by
273  // MachineRegisterInfo::isCallerPreservedOrConstPhysReg expects the
274  // reserved registers to be frozen. That doesn't cause a problem post-ISel as
275  // most (if not all) targets freeze reserved registers right after ISel.
276  //
277  // It does cause issues mid-GlobalISel, however, hence the additional
278  // reservedRegsFrozen check.
279  const MachineRegisterInfo &MRI = MF.getRegInfo();
280  return TRI.isCallerPreservedPhysReg(Reg, MF) || TII.isIgnorableUse(MO) ||
282 }
283 
284 /// hasLivePhysRegDefUses - Return true if the specified instruction read/write
285 /// physical registers (except for dead defs of physical registers). It also
286 /// returns the physical register def by reference if it's the only one and the
287 /// instruction does not uses a physical register.
288 bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI,
289  const MachineBasicBlock *MBB,
290  SmallSet<MCRegister, 8> &PhysRefs,
291  PhysDefVector &PhysDefs,
292  bool &PhysUseDef) const {
293  // First, add all uses to PhysRefs.
294  for (const MachineOperand &MO : MI->operands()) {
295  if (!MO.isReg() || MO.isDef())
296  continue;
297  Register Reg = MO.getReg();
298  if (!Reg)
299  continue;
301  continue;
302  // Reading either caller preserved or constant physregs is ok.
303  if (!isCallerPreservedOrConstPhysReg(Reg.asMCReg(), MO, *MI->getMF(), *TRI,
304  *TII))
305  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
306  PhysRefs.insert(*AI);
307  }
308 
309  // Next, collect all defs into PhysDefs. If any is already in PhysRefs
310  // (which currently contains only uses), set the PhysUseDef flag.
311  PhysUseDef = false;
312  MachineBasicBlock::const_iterator I = MI; I = std::next(I);
313  for (const auto &MOP : llvm::enumerate(MI->operands())) {
314  const MachineOperand &MO = MOP.value();
315  if (!MO.isReg() || !MO.isDef())
316  continue;
317  Register Reg = MO.getReg();
318  if (!Reg)
319  continue;
321  continue;
322  // Check against PhysRefs even if the def is "dead".
323  if (PhysRefs.count(Reg.asMCReg()))
324  PhysUseDef = true;
325  // If the def is dead, it's ok. But the def may not marked "dead". That's
326  // common since this pass is run before livevariables. We can scan
327  // forward a few instructions and check if it is obviously dead.
328  if (!MO.isDead() && !isPhysDefTriviallyDead(Reg.asMCReg(), I, MBB->end()))
329  PhysDefs.push_back(std::make_pair(MOP.index(), Reg));
330  }
331 
332  // Finally, add all defs to PhysRefs as well.
333  for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i)
334  for (MCRegAliasIterator AI(PhysDefs[i].second, TRI, true); AI.isValid();
335  ++AI)
336  PhysRefs.insert(*AI);
337 
338  return !PhysRefs.empty();
339 }
340 
341 bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
342  SmallSet<MCRegister, 8> &PhysRefs,
343  PhysDefVector &PhysDefs,
344  bool &NonLocal) const {
345  // For now conservatively returns false if the common subexpression is
346  // not in the same basic block as the given instruction. The only exception
347  // is if the common subexpression is in the sole predecessor block.
348  const MachineBasicBlock *MBB = MI->getParent();
349  const MachineBasicBlock *CSMBB = CSMI->getParent();
350 
351  bool CrossMBB = false;
352  if (CSMBB != MBB) {
353  if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB)
354  return false;
355 
356  for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) {
357  if (MRI->isAllocatable(PhysDefs[i].second) ||
358  MRI->isReserved(PhysDefs[i].second))
359  // Avoid extending live range of physical registers if they are
360  //allocatable or reserved.
361  return false;
362  }
363  CrossMBB = true;
364  }
365  MachineBasicBlock::const_iterator I = CSMI; I = std::next(I);
368  unsigned LookAheadLeft = LookAheadLimit;
369  while (LookAheadLeft) {
370  // Skip over dbg_value's.
371  while (I != E && I != EE && I->isDebugInstr())
372  ++I;
373 
374  if (I == EE) {
375  assert(CrossMBB && "Reaching end-of-MBB without finding MI?");
376  (void)CrossMBB;
377  CrossMBB = false;
378  NonLocal = true;
379  I = MBB->begin();
380  EE = MBB->end();
381  continue;
382  }
383 
384  if (I == E)
385  return true;
386 
387  for (const MachineOperand &MO : I->operands()) {
388  // RegMasks go on instructions like calls that clobber lots of physregs.
389  // Don't attempt to CSE across such an instruction.
390  if (MO.isRegMask())
391  return false;
392  if (!MO.isReg() || !MO.isDef())
393  continue;
394  Register MOReg = MO.getReg();
395  if (Register::isVirtualRegister(MOReg))
396  continue;
397  if (PhysRefs.count(MOReg.asMCReg()))
398  return false;
399  }
400 
401  --LookAheadLeft;
402  ++I;
403  }
404 
405  return false;
406 }
407 
408 bool MachineCSE::isCSECandidate(MachineInstr *MI) {
409  if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || MI->isKill() ||
410  MI->isInlineAsm() || MI->isDebugInstr())
411  return false;
412 
413  // Ignore copies.
414  if (MI->isCopyLike())
415  return false;
416 
417  // Ignore stuff that we obviously can't move.
418  if (MI->mayStore() || MI->isCall() || MI->isTerminator() ||
419  MI->mayRaiseFPException() || MI->hasUnmodeledSideEffects())
420  return false;
421 
422  if (MI->mayLoad()) {
423  // Okay, this instruction does a load. As a refinement, we allow the target
424  // to decide whether the loaded value is actually a constant. If so, we can
425  // actually use it as a load.
426  if (!MI->isDereferenceableInvariantLoad())
427  // FIXME: we should be able to hoist loads with no other side effects if
428  // there are no other instructions which can change memory in this loop.
429  // This is a trivial form of alias analysis.
430  return false;
431  }
432 
433  // Ignore stack guard loads, otherwise the register that holds CSEed value may
434  // be spilled and get loaded back with corrupted data.
435  if (MI->getOpcode() == TargetOpcode::LOAD_STACK_GUARD)
436  return false;
437 
438  return true;
439 }
440 
441 /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
442 /// common expression that defines Reg. CSBB is basic block where CSReg is
443 /// defined.
444 bool MachineCSE::isProfitableToCSE(Register CSReg, Register Reg,
446  // FIXME: Heuristics that works around the lack the live range splitting.
447 
448  // If CSReg is used at all uses of Reg, CSE should not increase register
449  // pressure of CSReg.
450  bool MayIncreasePressure = true;
452  MayIncreasePressure = false;
454  int NumOfUses = 0;
455  for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) {
456  CSUses.insert(&MI);
457  // Too costly to compute if NumOfUses is very large. Conservatively assume
458  // MayIncreasePressure to avoid spending too much time here.
459  if (++NumOfUses > CSUsesThreshold) {
460  MayIncreasePressure = true;
461  break;
462  }
463  }
464  if (!MayIncreasePressure)
466  if (!CSUses.count(&MI)) {
467  MayIncreasePressure = true;
468  break;
469  }
470  }
471  }
472  if (!MayIncreasePressure) return true;
473 
474  // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in
475  // an immediate predecessor. We don't want to increase register pressure and
476  // end up causing other computation to be spilled.
477  if (TII->isAsCheapAsAMove(*MI)) {
478  MachineBasicBlock *BB = MI->getParent();
479  if (CSBB != BB && !CSBB->isSuccessor(BB))
480  return false;
481  }
482 
483  // Heuristics #2: If the expression doesn't not use a vr and the only use
484  // of the redundant computation are copies, do not cse.
485  bool HasVRegUse = false;
486  for (const MachineOperand &MO : MI->operands()) {
487  if (MO.isReg() && MO.isUse() && Register::isVirtualRegister(MO.getReg())) {
488  HasVRegUse = true;
489  break;
490  }
491  }
492  if (!HasVRegUse) {
493  bool HasNonCopyUse = false;
495  // Ignore copies.
496  if (!MI.isCopyLike()) {
497  HasNonCopyUse = true;
498  break;
499  }
500  }
501  if (!HasNonCopyUse)
502  return false;
503  }
504 
505  // Heuristics #3: If the common subexpression is used by PHIs, do not reuse
506  // it unless the defined value is already used in the BB of the new use.
507  bool HasPHI = false;
508  for (MachineInstr &UseMI : MRI->use_nodbg_instructions(CSReg)) {
509  HasPHI |= UseMI.isPHI();
510  if (UseMI.getParent() == MI->getParent())
511  return true;
512  }
513 
514  return !HasPHI;
515 }
516 
517 void MachineCSE::EnterScope(MachineBasicBlock *MBB) {
518  LLVM_DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n');
519  ScopeType *Scope = new ScopeType(VNT);
520  ScopeMap[MBB] = Scope;
521 }
522 
523 void MachineCSE::ExitScope(MachineBasicBlock *MBB) {
524  LLVM_DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n');
526  assert(SI != ScopeMap.end());
527  delete SI->second;
528  ScopeMap.erase(SI);
529 }
530 
531 bool MachineCSE::ProcessBlockCSE(MachineBasicBlock *MBB) {
532  bool Changed = false;
533 
535  SmallVector<unsigned, 2> ImplicitDefsToUpdate;
536  SmallVector<unsigned, 2> ImplicitDefs;
538  if (!isCSECandidate(&MI))
539  continue;
540 
541  bool FoundCSE = VNT.count(&MI);
542  if (!FoundCSE) {
543  // Using trivial copy propagation to find more CSE opportunities.
544  if (PerformTrivialCopyPropagation(&MI, MBB)) {
545  Changed = true;
546 
547  // After coalescing MI itself may become a copy.
548  if (MI.isCopyLike())
549  continue;
550 
551  // Try again to see if CSE is possible.
552  FoundCSE = VNT.count(&MI);
553  }
554  }
555 
556  // Commute commutable instructions.
557  bool Commuted = false;
558  if (!FoundCSE && MI.isCommutable()) {
559  if (MachineInstr *NewMI = TII->commuteInstruction(MI)) {
560  Commuted = true;
561  FoundCSE = VNT.count(NewMI);
562  if (NewMI != &MI) {
563  // New instruction. It doesn't need to be kept.
564  NewMI->eraseFromParent();
565  Changed = true;
566  } else if (!FoundCSE)
567  // MI was changed but it didn't help, commute it back!
568  (void)TII->commuteInstruction(MI);
569  }
570  }
571 
572  // If the instruction defines physical registers and the values *may* be
573  // used, then it's not safe to replace it with a common subexpression.
574  // It's also not safe if the instruction uses physical registers.
575  bool CrossMBBPhysDef = false;
576  SmallSet<MCRegister, 8> PhysRefs;
577  PhysDefVector PhysDefs;
578  bool PhysUseDef = false;
579  if (FoundCSE &&
580  hasLivePhysRegDefUses(&MI, MBB, PhysRefs, PhysDefs, PhysUseDef)) {
581  FoundCSE = false;
582 
583  // ... Unless the CS is local or is in the sole predecessor block
584  // and it also defines the physical register which is not clobbered
585  // in between and the physical register uses were not clobbered.
586  // This can never be the case if the instruction both uses and
587  // defines the same physical register, which was detected above.
588  if (!PhysUseDef) {
589  unsigned CSVN = VNT.lookup(&MI);
590  MachineInstr *CSMI = Exps[CSVN];
591  if (PhysRegDefsReach(CSMI, &MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
592  FoundCSE = true;
593  }
594  }
595 
596  if (!FoundCSE) {
597  VNT.insert(&MI, CurrVN++);
598  Exps.push_back(&MI);
599  continue;
600  }
601 
602  // Found a common subexpression, eliminate it.
603  unsigned CSVN = VNT.lookup(&MI);
604  MachineInstr *CSMI = Exps[CSVN];
605  LLVM_DEBUG(dbgs() << "Examining: " << MI);
606  LLVM_DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
607 
608  // Prevent CSE-ing non-local convergent instructions.
609  // LLVM's current definition of `isConvergent` does not necessarily prove
610  // that non-local CSE is illegal. The following check extends the definition
611  // of `isConvergent` to assume a convergent instruction is dependent not
612  // only on additional conditions, but also on fewer conditions. LLVM does
613  // not have a MachineInstr attribute which expresses this extended
614  // definition, so it's necessary to use `isConvergent` to prevent illegally
615  // CSE-ing the subset of `isConvergent` instructions which do fall into this
616  // extended definition.
617  if (MI.isConvergent() && MI.getParent() != CSMI->getParent()) {
618  LLVM_DEBUG(dbgs() << "*** Convergent MI and subexpression exist in "
619  "different BBs, avoid CSE!\n");
620  VNT.insert(&MI, CurrVN++);
621  Exps.push_back(&MI);
622  continue;
623  }
624 
625  // Check if it's profitable to perform this CSE.
626  bool DoCSE = true;
627  unsigned NumDefs = MI.getNumDefs();
628 
629  for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) {
630  MachineOperand &MO = MI.getOperand(i);
631  if (!MO.isReg() || !MO.isDef())
632  continue;
633  Register OldReg = MO.getReg();
634  Register NewReg = CSMI->getOperand(i).getReg();
635 
636  // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
637  // we should make sure it is not dead at CSMI.
638  if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead())
639  ImplicitDefsToUpdate.push_back(i);
640 
641  // Keep track of implicit defs of CSMI and MI, to clear possibly
642  // made-redundant kill flags.
643  if (MO.isImplicit() && !MO.isDead() && OldReg == NewReg)
644  ImplicitDefs.push_back(OldReg);
645 
646  if (OldReg == NewReg) {
647  --NumDefs;
648  continue;
649  }
650 
652  Register::isVirtualRegister(NewReg) &&
653  "Do not CSE physical register defs!");
654 
655  if (!isProfitableToCSE(NewReg, OldReg, CSMI->getParent(), &MI)) {
656  LLVM_DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
657  DoCSE = false;
658  break;
659  }
660 
661  // Don't perform CSE if the result of the new instruction cannot exist
662  // within the constraints (register class, bank, or low-level type) of
663  // the old instruction.
664  if (!MRI->constrainRegAttrs(NewReg, OldReg)) {
665  LLVM_DEBUG(
666  dbgs() << "*** Not the same register constraints, avoid CSE!\n");
667  DoCSE = false;
668  break;
669  }
670 
671  CSEPairs.push_back(std::make_pair(OldReg, NewReg));
672  --NumDefs;
673  }
674 
675  // Actually perform the elimination.
676  if (DoCSE) {
677  for (const std::pair<unsigned, unsigned> &CSEPair : CSEPairs) {
678  unsigned OldReg = CSEPair.first;
679  unsigned NewReg = CSEPair.second;
680  // OldReg may have been unused but is used now, clear the Dead flag
681  MachineInstr *Def = MRI->getUniqueVRegDef(NewReg);
682  assert(Def != nullptr && "CSEd register has no unique definition?");
683  Def->clearRegisterDeads(NewReg);
684  // Replace with NewReg and clear kill flags which may be wrong now.
685  MRI->replaceRegWith(OldReg, NewReg);
686  MRI->clearKillFlags(NewReg);
687  }
688 
689  // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
690  // we should make sure it is not dead at CSMI.
691  for (unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
692  CSMI->getOperand(ImplicitDefToUpdate).setIsDead(false);
693  for (const auto &PhysDef : PhysDefs)
694  if (!MI.getOperand(PhysDef.first).isDead())
695  CSMI->getOperand(PhysDef.first).setIsDead(false);
696 
697  // Go through implicit defs of CSMI and MI, and clear the kill flags on
698  // their uses in all the instructions between CSMI and MI.
699  // We might have made some of the kill flags redundant, consider:
700  // subs ... implicit-def %nzcv <- CSMI
701  // csinc ... implicit killed %nzcv <- this kill flag isn't valid anymore
702  // subs ... implicit-def %nzcv <- MI, to be eliminated
703  // csinc ... implicit killed %nzcv
704  // Since we eliminated MI, and reused a register imp-def'd by CSMI
705  // (here %nzcv), that register, if it was killed before MI, should have
706  // that kill flag removed, because it's lifetime was extended.
707  if (CSMI->getParent() == MI.getParent()) {
708  for (MachineBasicBlock::iterator II = CSMI, IE = &MI; II != IE; ++II)
709  for (auto ImplicitDef : ImplicitDefs)
710  if (MachineOperand *MO = II->findRegisterUseOperand(
711  ImplicitDef, /*isKill=*/true, TRI))
712  MO->setIsKill(false);
713  } else {
714  // If the instructions aren't in the same BB, bail out and clear the
715  // kill flag on all uses of the imp-def'd register.
716  for (auto ImplicitDef : ImplicitDefs)
717  MRI->clearKillFlags(ImplicitDef);
718  }
719 
720  if (CrossMBBPhysDef) {
721  // Add physical register defs now coming in from a predecessor to MBB
722  // livein list.
723  while (!PhysDefs.empty()) {
724  auto LiveIn = PhysDefs.pop_back_val();
725  if (!MBB->isLiveIn(LiveIn.second))
726  MBB->addLiveIn(LiveIn.second);
727  }
728  ++NumCrossBBCSEs;
729  }
730 
731  MI.eraseFromParent();
732  ++NumCSEs;
733  if (!PhysRefs.empty())
734  ++NumPhysCSEs;
735  if (Commuted)
736  ++NumCommutes;
737  Changed = true;
738  } else {
739  VNT.insert(&MI, CurrVN++);
740  Exps.push_back(&MI);
741  }
742  CSEPairs.clear();
743  ImplicitDefsToUpdate.clear();
744  ImplicitDefs.clear();
745  }
746 
747  return Changed;
748 }
749 
750 /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
751 /// dominator tree node if its a leaf or all of its children are done. Walk
752 /// up the dominator tree to destroy ancestors which are now done.
753 void
754 MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node,
756  if (OpenChildren[Node])
757  return;
758 
759  // Pop scope.
760  ExitScope(Node->getBlock());
761 
762  // Now traverse upwards to pop ancestors whose offsprings are all done.
763  while (MachineDomTreeNode *Parent = Node->getIDom()) {
764  unsigned Left = --OpenChildren[Parent];
765  if (Left != 0)
766  break;
767  ExitScope(Parent->getBlock());
768  Node = Parent;
769  }
770 }
771 
772 bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) {
776 
777  CurrVN = 0;
778 
779  // Perform a DFS walk to determine the order of visit.
780  WorkList.push_back(Node);
781  do {
782  Node = WorkList.pop_back_val();
783  Scopes.push_back(Node);
784  OpenChildren[Node] = Node->getNumChildren();
785  append_range(WorkList, Node->children());
786  } while (!WorkList.empty());
787 
788  // Now perform CSE.
789  bool Changed = false;
790  for (MachineDomTreeNode *Node : Scopes) {
791  MachineBasicBlock *MBB = Node->getBlock();
792  EnterScope(MBB);
793  Changed |= ProcessBlockCSE(MBB);
794  // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
795  ExitScopeIfDone(Node, OpenChildren);
796  }
797 
798  return Changed;
799 }
800 
801 // We use stronger checks for PRE candidate rather than for CSE ones to embrace
802 // checks inside ProcessBlockCSE(), not only inside isCSECandidate(). This helps
803 // to exclude instrs created by PRE that won't be CSEed later.
804 bool MachineCSE::isPRECandidate(MachineInstr *MI,
805  SmallSet<MCRegister, 8> &PhysRefs) {
806  if (!isCSECandidate(MI) ||
807  MI->isNotDuplicable() ||
808  MI->mayLoad() ||
809  TII->isAsCheapAsAMove(*MI) ||
810  MI->getNumDefs() != 1 ||
811  MI->getNumExplicitDefs() != 1)
812  return false;
813 
814  for (const MachineOperand &MO : MI->operands()) {
815  if (MO.isReg() && !Register::isVirtualRegister(MO.getReg())) {
816  if (MO.isDef())
817  return false;
818  else
819  PhysRefs.insert(MO.getReg());
820  }
821  }
822 
823  return true;
824 }
825 
826 bool MachineCSE::ProcessBlockPRE(MachineDominatorTree *DT,
828  bool Changed = false;
830  SmallSet<MCRegister, 8> PhysRefs;
831  if (!isPRECandidate(&MI, PhysRefs))
832  continue;
833 
834  if (!PREMap.count(&MI)) {
835  PREMap[&MI] = MBB;
836  continue;
837  }
838 
839  auto MBB1 = PREMap[&MI];
840  assert(
841  !DT->properlyDominates(MBB, MBB1) &&
842  "MBB cannot properly dominate MBB1 while DFS through dominators tree!");
843  auto CMBB = DT->findNearestCommonDominator(MBB, MBB1);
844  if (!CMBB->isLegalToHoistInto())
845  continue;
846 
847  if (!isProfitableToHoistInto(CMBB, MBB, MBB1))
848  continue;
849 
850  // Two instrs are partial redundant if their basic blocks are reachable
851  // from one to another but one doesn't dominate another.
852  if (CMBB != MBB1) {
853  auto BB = MBB->getBasicBlock(), BB1 = MBB1->getBasicBlock();
854  if (BB != nullptr && BB1 != nullptr &&
855  (isPotentiallyReachable(BB1, BB) ||
856  isPotentiallyReachable(BB, BB1))) {
857  // The following check extends the definition of `isConvergent` to
858  // assume a convergent instruction is dependent not only on additional
859  // conditions, but also on fewer conditions. LLVM does not have a
860  // MachineInstr attribute which expresses this extended definition, so
861  // it's necessary to use `isConvergent` to prevent illegally PRE-ing the
862  // subset of `isConvergent` instructions which do fall into this
863  // extended definition.
864  if (MI.isConvergent() && CMBB != MBB)
865  continue;
866 
867  // If this instruction uses physical registers then we can only do PRE
868  // if it's using the value that is live at the place we're hoisting to.
869  bool NonLocal;
870  PhysDefVector PhysDefs;
871  if (!PhysRefs.empty() &&
872  !PhysRegDefsReach(&*(CMBB->getFirstTerminator()), &MI, PhysRefs,
873  PhysDefs, NonLocal))
874  continue;
875 
876  assert(MI.getOperand(0).isDef() &&
877  "First operand of instr with one explicit def must be this def");
878  Register VReg = MI.getOperand(0).getReg();
879  Register NewReg = MRI->cloneVirtualRegister(VReg);
880  if (!isProfitableToCSE(NewReg, VReg, CMBB, &MI))
881  continue;
882  MachineInstr &NewMI =
883  TII->duplicate(*CMBB, CMBB->getFirstTerminator(), MI);
884 
885  // When hoisting, make sure we don't carry the debug location of
886  // the original instruction, as that's not correct and can cause
887  // unexpected jumps when debugging optimized code.
888  auto EmptyDL = DebugLoc();
889  NewMI.setDebugLoc(EmptyDL);
890 
891  NewMI.getOperand(0).setReg(NewReg);
892 
893  PREMap[&MI] = CMBB;
894  ++NumPREs;
895  Changed = true;
896  }
897  }
898  }
899  return Changed;
900 }
901 
902 // This simple PRE (partial redundancy elimination) pass doesn't actually
903 // eliminate partial redundancy but transforms it to full redundancy,
904 // anticipating that the next CSE step will eliminate this created redundancy.
905 // If CSE doesn't eliminate this, than created instruction will remain dead
906 // and eliminated later by Remove Dead Machine Instructions pass.
907 bool MachineCSE::PerformSimplePRE(MachineDominatorTree *DT) {
909 
910  PREMap.clear();
911  bool Changed = false;
912  BBs.push_back(DT->getRootNode());
913  do {
914  auto Node = BBs.pop_back_val();
915  append_range(BBs, Node->children());
916 
917  MachineBasicBlock *MBB = Node->getBlock();
918  Changed |= ProcessBlockPRE(DT, MBB);
919 
920  } while (!BBs.empty());
921 
922  return Changed;
923 }
924 
925 bool MachineCSE::isProfitableToHoistInto(MachineBasicBlock *CandidateBB,
927  MachineBasicBlock *MBB1) {
928  if (CandidateBB->getParent()->getFunction().hasMinSize())
929  return true;
930  assert(DT->dominates(CandidateBB, MBB) && "CandidateBB should dominate MBB");
931  assert(DT->dominates(CandidateBB, MBB1) &&
932  "CandidateBB should dominate MBB1");
933  return MBFI->getBlockFreq(CandidateBB) <=
934  MBFI->getBlockFreq(MBB) + MBFI->getBlockFreq(MBB1);
935 }
936 
937 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
938  if (skipFunction(MF.getFunction()))
939  return false;
940 
941  TII = MF.getSubtarget().getInstrInfo();
943  MRI = &MF.getRegInfo();
944  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
945  DT = &getAnalysis<MachineDominatorTree>();
946  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
947  LookAheadLimit = TII->getMachineCSELookAheadLimit();
948  bool ChangedPRE, ChangedCSE;
949  ChangedPRE = PerformSimplePRE(DT);
950  ChangedCSE = PerformCSE(DT->getRootNode());
951  return ChangedPRE || ChangedCSE;
952 }
llvm::MachineDominatorTree::findNearestCommonDominator
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
Definition: MachineDominators.h:160
i
i
Definition: README.txt:29
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:357
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::MachineRegisterInfo::constrainRegAttrs
bool constrainRegAttrs(Register Reg, Register ConstrainingReg, unsigned MinNumRegs=0)
Constrain the register class or the register bank of the virtual register Reg (and low-level type) to...
Definition: MachineRegisterInfo.cpp:90
llvm::ScopedHashTableVal
Definition: ScopedHashTable.h:46
UseMI
MachineInstrBuilder & UseMI
Definition: AArch64ExpandPseudoInsts.cpp:107
llvm::MachineBasicBlock::isLiveIn
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
Definition: MachineBasicBlock.cpp:601
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::MachineBasicBlock::getBasicBlock
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Definition: MachineBasicBlock.h:213
llvm::MachineDominatorTree::properlyDominates
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:146
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
Pass.h
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:95
llvm::MachineOperand::setIsKill
void setIsKill(bool Val=true)
Definition: MachineOperand.h:509
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::enumerate
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:2263
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
Allocator.h
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::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:127
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:551
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:236
DenseMap.h
TargetInstrInfo.h
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::MachineDominatorTree::getRootNode
MachineDomTreeNode * getRootNode() const
Definition: MachineDominators.h:105
llvm::MachineFunctionProperties::Property::IsSSA
@ IsSSA
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:127
llvm::BumpPtrAllocator
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:375
llvm::MachineInstr::isCopy
bool isCopy() const
Definition: MachineInstr.h:1336
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::MachineDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:114
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::MachineBlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Definition: MachineBlockFrequencyInfo.cpp:231
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
MachineRegisterInfo.h
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::AlignStyle::Left
@ Left
llvm::HexagonInstrInfo::isAsCheapAsAMove
bool isAsCheapAsAMove(const MachineInstr &MI) const override
Definition: HexagonInstrInfo.cpp:154
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:369
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:670
llvm::MachineOperand::isImplicit
bool isImplicit() const
Definition: MachineOperand.h:379
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::AAResults
Definition: AliasAnalysis.h:294
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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::MachineBasicBlock::isSuccessor
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Definition: MachineBasicBlock.cpp:934
SI
@ SI
Definition: SIInstrInfo.cpp:7985
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
TargetOpcodes.h
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::isPotentiallyReachable
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition: CFG.cpp:231
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:196
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
SmallPtrSet.h
llvm::MachineRegisterInfo::reservedRegsFrozen
bool reservedRegsFrozen() const
reservedRegsFrozen - Returns true after freezeReservedRegs() was called to ensure the set of reserved...
Definition: MachineRegisterInfo.h:905
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::initializeMachineCSEPass
void initializeMachineCSEPass(PassRegistry &)
llvm::TargetRegisterInfo::isCallerPreservedPhysReg
virtual bool isCallerPreservedPhysReg(MCRegister PhysReg, const MachineFunction &MF) const
Physical registers that may be modified within a function but are guaranteed to be restored before an...
Definition: TargetRegisterInfo.h:565
ScopedHashTable.h
llvm::MachineInstrExpressionTrait
Special DenseMapInfo traits to compare MachineInstr* by value of the instruction rather than by point...
Definition: MachineInstr.h:1929
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
MCRegister.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::ScopedHashTable
Definition: ScopedHashTable.h:43
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
Passes.h
llvm::MachineRegisterInfo::clearKillFlags
void clearKillFlags(Register Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
Definition: MachineRegisterInfo.cpp:433
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:660
llvm::MachineLoopInfoID
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
Definition: MachineLoopInfo.cpp:43
llvm::cl::opt
Definition: CommandLine.h:1411
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::TargetRegisterInfo::regsOverlap
bool regsOverlap(Register RegA, Register RegB) const
Returns true if the two registers are equal or alias each other.
Definition: TargetRegisterInfo.h:421
llvm::logicalview::LVCompareKind::Scopes
@ Scopes
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
Elimination
Machine Common Subexpression Elimination
Definition: MachineCSE.cpp:169
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:384
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:446
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:716
MCRegisterInfo.h
MachineFunctionPass.h
DEBUG_TYPE
#define DEBUG_TYPE
Definition: MachineCSE.cpp:51
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
llvm::MachineCSEID
char & MachineCSEID
MachineCSE - This pass performs global CSE on machine instructions.
Definition: MachineCSE.cpp:162
llvm::MachineRegisterInfo::isAllocatable
bool isAllocatable(MCRegister PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
Definition: MachineRegisterInfo.h:948
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:265
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::Register::asMCReg
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition: Register.h:120
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::MachineFunction
Definition: MachineFunction.h:257
CFG.h
llvm::skipDebugInstructionsForward
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
Definition: MachineBasicBlock.h:1288
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
llvm::MachineRegisterInfo::hasOneNonDBGUse
bool hasOneNonDBGUse(Register RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register.
Definition: MachineRegisterInfo.cpp:415
isCallerPreservedOrConstPhysReg
static bool isCallerPreservedOrConstPhysReg(MCRegister Reg, const MachineOperand &MO, const MachineFunction &MF, const TargetRegisterInfo &TRI, const TargetInstrInfo &TII)
Definition: MachineCSE.cpp:267
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(MachineCSE, DEBUG_TYPE, "Machine Common Subexpression Elimination", false, false) INITIALIZE_PASS_END(MachineCSE
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2013
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineOperand::getSubReg
unsigned getSubReg() const
Definition: MachineOperand.h:364
llvm::MachineBasicBlock::addLiveIn
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
Definition: MachineBasicBlock.h:408
llvm::MachineRegisterInfo::isConstantPhysReg
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
Definition: MachineRegisterInfo.cpp:515
llvm::MachineRegisterInfo::replaceRegWith
void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
Definition: MachineRegisterInfo.cpp:378
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::RecyclingAllocator
RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...
Definition: RecyclingAllocator.h:26
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:626
RecyclingAllocator.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::MachineInstr::setDebugLoc
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
Definition: MachineInstr.h:1767
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::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:813
Machine
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:370
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:309
llvm::MachineRegisterInfo::cloneVirtualRegister
Register cloneVirtualRegister(Register VReg, StringRef Name="")
Create and return a new virtual register in the function with the same attributes as the given regist...
Definition: MachineRegisterInfo.cpp:170
llvm::MachineOperand::setReg
void setReg(Register Reg)
Change the register this operand corresponds to.
Definition: MachineOperand.cpp:56
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:108
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:929
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
CSUsesThreshold
static cl::opt< int > CSUsesThreshold("csuses-threshold", cl::Hidden, cl::init(1024), cl::desc("Threshold for the size of CSUses"))
MachineOperand.h
llvm::Function::hasMinSize
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:642
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::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:412
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
MachineFunction.h
llvm::MachineInstr::eraseFromParent
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
Definition: MachineInstr.cpp:691
llvm::MachineInstrBundleIterator< const MachineInstr >
InitializePasses.h
MachineBlockFrequencyInfo.h
llvm::SmallSet::empty
bool empty() const
Definition: SmallSet.h:158
TargetRegisterInfo.h
llvm::MachineBasicBlock::getName
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Definition: MachineBasicBlock.cpp:316
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:311
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:788
MachineDominators.h
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
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::MachineInstr::changeDebugValuesDefReg
void changeDebugValuesDefReg(Register Reg)
Find all DBG_VALUEs that point to the register def in this instruction and point them to Reg instead.
Definition: MachineInstr.cpp:2295