LLVM  15.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 namespace {
64 
65  class MachineCSE : public MachineFunctionPass {
66  const TargetInstrInfo *TII;
67  const TargetRegisterInfo *TRI;
72 
73  public:
74  static char ID; // Pass identification
75 
76  MachineCSE() : MachineFunctionPass(ID) {
78  }
79 
80  bool runOnMachineFunction(MachineFunction &MF) override;
81 
82  void getAnalysisUsage(AnalysisUsage &AU) const override {
83  AU.setPreservesCFG();
91  }
92 
93  MachineFunctionProperties getRequiredProperties() const override {
96  }
97 
98  void releaseMemory() override {
99  ScopeMap.clear();
100  PREMap.clear();
101  Exps.clear();
102  }
103 
104  private:
105  using AllocatorTy = RecyclingAllocator<BumpPtrAllocator,
107  using ScopedHTType =
109  AllocatorTy>;
110  using ScopeType = ScopedHTType::ScopeTy;
111  using PhysDefVector = SmallVector<std::pair<unsigned, unsigned>, 2>;
112 
113  unsigned LookAheadLimit = 0;
116  PREMap;
117  ScopedHTType VNT;
119  unsigned CurrVN = 0;
120 
121  bool PerformTrivialCopyPropagation(MachineInstr *MI,
123  bool isPhysDefTriviallyDead(MCRegister Reg,
126  bool hasLivePhysRegDefUses(const MachineInstr *MI,
127  const MachineBasicBlock *MBB,
128  SmallSet<MCRegister, 8> &PhysRefs,
129  PhysDefVector &PhysDefs, bool &PhysUseDef) const;
130  bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
131  SmallSet<MCRegister, 8> &PhysRefs,
132  PhysDefVector &PhysDefs, bool &NonLocal) const;
133  bool isCSECandidate(MachineInstr *MI);
134  bool isProfitableToCSE(Register CSReg, Register Reg,
136  void EnterScope(MachineBasicBlock *MBB);
137  void ExitScope(MachineBasicBlock *MBB);
138  bool ProcessBlockCSE(MachineBasicBlock *MBB);
139  void ExitScopeIfDone(MachineDomTreeNode *Node,
141  bool PerformCSE(MachineDomTreeNode *Node);
142 
143  bool isPRECandidate(MachineInstr *MI);
144  bool ProcessBlockPRE(MachineDominatorTree *MDT, MachineBasicBlock *MBB);
145  bool PerformSimplePRE(MachineDominatorTree *DT);
146  /// Heuristics to see if it's profitable to move common computations of MBB
147  /// and MBB1 to CandidateBB.
148  bool isProfitableToHoistInto(MachineBasicBlock *CandidateBB,
150  MachineBasicBlock *MBB1);
151  };
152 
153 } // end anonymous namespace
154 
155 char MachineCSE::ID = 0;
156 
158 
160  "Machine Common Subexpression Elimination", false, false)
164  "Machine Common Subexpression Elimination", false, false)
165 
166 /// The source register of a COPY machine instruction can be propagated to all
167 /// its users, and this propagation could increase the probability of finding
168 /// common subexpressions. If the COPY has only one user, the COPY itself can
169 /// be removed.
170 bool MachineCSE::PerformTrivialCopyPropagation(MachineInstr *MI,
172  bool Changed = false;
173  for (MachineOperand &MO : MI->operands()) {
174  if (!MO.isReg() || !MO.isUse())
175  continue;
176  Register Reg = MO.getReg();
178  continue;
179  bool OnlyOneUse = MRI->hasOneNonDBGUse(Reg);
181  if (!DefMI->isCopy())
182  continue;
183  Register SrcReg = DefMI->getOperand(1).getReg();
184  if (!Register::isVirtualRegister(SrcReg))
185  continue;
186  if (DefMI->getOperand(0).getSubReg())
187  continue;
188  // FIXME: We should trivially coalesce subregister copies to expose CSE
189  // opportunities on instructions with truncated operands (see
190  // cse-add-with-overflow.ll). This can be done here as follows:
191  // if (SrcSubReg)
192  // RC = TRI->getMatchingSuperRegClass(MRI->getRegClass(SrcReg), RC,
193  // SrcSubReg);
194  // MO.substVirtReg(SrcReg, SrcSubReg, *TRI);
195  //
196  // The 2-addr pass has been updated to handle coalesced subregs. However,
197  // some machine-specific code still can't handle it.
198  // To handle it properly we also need a way find a constrained subregister
199  // class given a super-reg class and subreg index.
200  if (DefMI->getOperand(1).getSubReg())
201  continue;
202  if (!MRI->constrainRegAttrs(SrcReg, Reg))
203  continue;
204  LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
205  LLVM_DEBUG(dbgs() << "*** to: " << *MI);
206 
207  // Propagate SrcReg of copies to MI.
208  MO.setReg(SrcReg);
209  MRI->clearKillFlags(SrcReg);
210  // Coalesce single use copies.
211  if (OnlyOneUse) {
212  // If (and only if) we've eliminated all uses of the copy, also
213  // copy-propagate to any debug-users of MI, or they'll be left using
214  // an undefined value.
216 
218  ++NumCoalesces;
219  }
220  Changed = true;
221  }
222 
223  return Changed;
224 }
225 
226 bool MachineCSE::isPhysDefTriviallyDead(
229  unsigned LookAheadLeft = LookAheadLimit;
230  while (LookAheadLeft) {
231  // Skip over dbg_value's.
233 
234  if (I == E)
235  // Reached end of block, we don't know if register is dead or not.
236  return false;
237 
238  bool SeenDef = false;
239  for (const MachineOperand &MO : I->operands()) {
240  if (MO.isRegMask() && MO.clobbersPhysReg(Reg))
241  SeenDef = true;
242  if (!MO.isReg() || !MO.getReg())
243  continue;
244  if (!TRI->regsOverlap(MO.getReg(), Reg))
245  continue;
246  if (MO.isUse())
247  // Found a use!
248  return false;
249  SeenDef = true;
250  }
251  if (SeenDef)
252  // See a def of Reg (or an alias) before encountering any use, it's
253  // trivially dead.
254  return true;
255 
256  --LookAheadLeft;
257  ++I;
258  }
259  return false;
260 }
261 
263  const MachineFunction &MF,
264  const TargetRegisterInfo &TRI) {
265  // MachineRegisterInfo::isConstantPhysReg directly called by
266  // MachineRegisterInfo::isCallerPreservedOrConstPhysReg expects the
267  // reserved registers to be frozen. That doesn't cause a problem post-ISel as
268  // most (if not all) targets freeze reserved registers right after ISel.
269  //
270  // It does cause issues mid-GlobalISel, however, hence the additional
271  // reservedRegsFrozen check.
272  const MachineRegisterInfo &MRI = MF.getRegInfo();
273  return TRI.isCallerPreservedPhysReg(Reg, MF) ||
275 }
276 
277 /// hasLivePhysRegDefUses - Return true if the specified instruction read/write
278 /// physical registers (except for dead defs of physical registers). It also
279 /// returns the physical register def by reference if it's the only one and the
280 /// instruction does not uses a physical register.
281 bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI,
282  const MachineBasicBlock *MBB,
283  SmallSet<MCRegister, 8> &PhysRefs,
284  PhysDefVector &PhysDefs,
285  bool &PhysUseDef) const {
286  // First, add all uses to PhysRefs.
287  for (const MachineOperand &MO : MI->operands()) {
288  if (!MO.isReg() || MO.isDef())
289  continue;
290  Register Reg = MO.getReg();
291  if (!Reg)
292  continue;
294  continue;
295  // Reading either caller preserved or constant physregs is ok.
296  if (!isCallerPreservedOrConstPhysReg(Reg.asMCReg(), *MI->getMF(), *TRI))
297  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
298  PhysRefs.insert(*AI);
299  }
300 
301  // Next, collect all defs into PhysDefs. If any is already in PhysRefs
302  // (which currently contains only uses), set the PhysUseDef flag.
303  PhysUseDef = false;
304  MachineBasicBlock::const_iterator I = MI; I = std::next(I);
305  for (const auto &MOP : llvm::enumerate(MI->operands())) {
306  const MachineOperand &MO = MOP.value();
307  if (!MO.isReg() || !MO.isDef())
308  continue;
309  Register Reg = MO.getReg();
310  if (!Reg)
311  continue;
313  continue;
314  // Check against PhysRefs even if the def is "dead".
315  if (PhysRefs.count(Reg.asMCReg()))
316  PhysUseDef = true;
317  // If the def is dead, it's ok. But the def may not marked "dead". That's
318  // common since this pass is run before livevariables. We can scan
319  // forward a few instructions and check if it is obviously dead.
320  if (!MO.isDead() && !isPhysDefTriviallyDead(Reg.asMCReg(), I, MBB->end()))
321  PhysDefs.push_back(std::make_pair(MOP.index(), Reg));
322  }
323 
324  // Finally, add all defs to PhysRefs as well.
325  for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i)
326  for (MCRegAliasIterator AI(PhysDefs[i].second, TRI, true); AI.isValid();
327  ++AI)
328  PhysRefs.insert(*AI);
329 
330  return !PhysRefs.empty();
331 }
332 
333 bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
334  SmallSet<MCRegister, 8> &PhysRefs,
335  PhysDefVector &PhysDefs,
336  bool &NonLocal) const {
337  // For now conservatively returns false if the common subexpression is
338  // not in the same basic block as the given instruction. The only exception
339  // is if the common subexpression is in the sole predecessor block.
340  const MachineBasicBlock *MBB = MI->getParent();
341  const MachineBasicBlock *CSMBB = CSMI->getParent();
342 
343  bool CrossMBB = false;
344  if (CSMBB != MBB) {
345  if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB)
346  return false;
347 
348  for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) {
349  if (MRI->isAllocatable(PhysDefs[i].second) ||
350  MRI->isReserved(PhysDefs[i].second))
351  // Avoid extending live range of physical registers if they are
352  //allocatable or reserved.
353  return false;
354  }
355  CrossMBB = true;
356  }
357  MachineBasicBlock::const_iterator I = CSMI; I = std::next(I);
360  unsigned LookAheadLeft = LookAheadLimit;
361  while (LookAheadLeft) {
362  // Skip over dbg_value's.
363  while (I != E && I != EE && I->isDebugInstr())
364  ++I;
365 
366  if (I == EE) {
367  assert(CrossMBB && "Reaching end-of-MBB without finding MI?");
368  (void)CrossMBB;
369  CrossMBB = false;
370  NonLocal = true;
371  I = MBB->begin();
372  EE = MBB->end();
373  continue;
374  }
375 
376  if (I == E)
377  return true;
378 
379  for (const MachineOperand &MO : I->operands()) {
380  // RegMasks go on instructions like calls that clobber lots of physregs.
381  // Don't attempt to CSE across such an instruction.
382  if (MO.isRegMask())
383  return false;
384  if (!MO.isReg() || !MO.isDef())
385  continue;
386  Register MOReg = MO.getReg();
387  if (Register::isVirtualRegister(MOReg))
388  continue;
389  if (PhysRefs.count(MOReg.asMCReg()))
390  return false;
391  }
392 
393  --LookAheadLeft;
394  ++I;
395  }
396 
397  return false;
398 }
399 
400 bool MachineCSE::isCSECandidate(MachineInstr *MI) {
401  if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || MI->isKill() ||
402  MI->isInlineAsm() || MI->isDebugInstr())
403  return false;
404 
405  // Ignore copies.
406  if (MI->isCopyLike())
407  return false;
408 
409  // Ignore stuff that we obviously can't move.
410  if (MI->mayStore() || MI->isCall() || MI->isTerminator() ||
411  MI->mayRaiseFPException() || MI->hasUnmodeledSideEffects())
412  return false;
413 
414  if (MI->mayLoad()) {
415  // Okay, this instruction does a load. As a refinement, we allow the target
416  // to decide whether the loaded value is actually a constant. If so, we can
417  // actually use it as a load.
418  if (!MI->isDereferenceableInvariantLoad(AA))
419  // FIXME: we should be able to hoist loads with no other side effects if
420  // there are no other instructions which can change memory in this loop.
421  // This is a trivial form of alias analysis.
422  return false;
423  }
424 
425  // Ignore stack guard loads, otherwise the register that holds CSEed value may
426  // be spilled and get loaded back with corrupted data.
427  if (MI->getOpcode() == TargetOpcode::LOAD_STACK_GUARD)
428  return false;
429 
430  return true;
431 }
432 
433 /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
434 /// common expression that defines Reg. CSBB is basic block where CSReg is
435 /// defined.
436 bool MachineCSE::isProfitableToCSE(Register CSReg, Register Reg,
438  // FIXME: Heuristics that works around the lack the live range splitting.
439 
440  // If CSReg is used at all uses of Reg, CSE should not increase register
441  // pressure of CSReg.
442  bool MayIncreasePressure = true;
444  MayIncreasePressure = false;
446  for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) {
447  CSUses.insert(&MI);
448  }
450  if (!CSUses.count(&MI)) {
451  MayIncreasePressure = true;
452  break;
453  }
454  }
455  }
456  if (!MayIncreasePressure) return true;
457 
458  // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in
459  // an immediate predecessor. We don't want to increase register pressure and
460  // end up causing other computation to be spilled.
461  if (TII->isAsCheapAsAMove(*MI)) {
462  MachineBasicBlock *BB = MI->getParent();
463  if (CSBB != BB && !CSBB->isSuccessor(BB))
464  return false;
465  }
466 
467  // Heuristics #2: If the expression doesn't not use a vr and the only use
468  // of the redundant computation are copies, do not cse.
469  bool HasVRegUse = false;
470  for (const MachineOperand &MO : MI->operands()) {
471  if (MO.isReg() && MO.isUse() && Register::isVirtualRegister(MO.getReg())) {
472  HasVRegUse = true;
473  break;
474  }
475  }
476  if (!HasVRegUse) {
477  bool HasNonCopyUse = false;
479  // Ignore copies.
480  if (!MI.isCopyLike()) {
481  HasNonCopyUse = true;
482  break;
483  }
484  }
485  if (!HasNonCopyUse)
486  return false;
487  }
488 
489  // Heuristics #3: If the common subexpression is used by PHIs, do not reuse
490  // it unless the defined value is already used in the BB of the new use.
491  bool HasPHI = false;
492  for (MachineInstr &UseMI : MRI->use_nodbg_instructions(CSReg)) {
493  HasPHI |= UseMI.isPHI();
494  if (UseMI.getParent() == MI->getParent())
495  return true;
496  }
497 
498  return !HasPHI;
499 }
500 
501 void MachineCSE::EnterScope(MachineBasicBlock *MBB) {
502  LLVM_DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n');
503  ScopeType *Scope = new ScopeType(VNT);
504  ScopeMap[MBB] = Scope;
505 }
506 
507 void MachineCSE::ExitScope(MachineBasicBlock *MBB) {
508  LLVM_DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n');
510  assert(SI != ScopeMap.end());
511  delete SI->second;
512  ScopeMap.erase(SI);
513 }
514 
515 bool MachineCSE::ProcessBlockCSE(MachineBasicBlock *MBB) {
516  bool Changed = false;
517 
519  SmallVector<unsigned, 2> ImplicitDefsToUpdate;
520  SmallVector<unsigned, 2> ImplicitDefs;
522  if (!isCSECandidate(&MI))
523  continue;
524 
525  bool FoundCSE = VNT.count(&MI);
526  if (!FoundCSE) {
527  // Using trivial copy propagation to find more CSE opportunities.
528  if (PerformTrivialCopyPropagation(&MI, MBB)) {
529  Changed = true;
530 
531  // After coalescing MI itself may become a copy.
532  if (MI.isCopyLike())
533  continue;
534 
535  // Try again to see if CSE is possible.
536  FoundCSE = VNT.count(&MI);
537  }
538  }
539 
540  // Commute commutable instructions.
541  bool Commuted = false;
542  if (!FoundCSE && MI.isCommutable()) {
543  if (MachineInstr *NewMI = TII->commuteInstruction(MI)) {
544  Commuted = true;
545  FoundCSE = VNT.count(NewMI);
546  if (NewMI != &MI) {
547  // New instruction. It doesn't need to be kept.
548  NewMI->eraseFromParent();
549  Changed = true;
550  } else if (!FoundCSE)
551  // MI was changed but it didn't help, commute it back!
552  (void)TII->commuteInstruction(MI);
553  }
554  }
555 
556  // If the instruction defines physical registers and the values *may* be
557  // used, then it's not safe to replace it with a common subexpression.
558  // It's also not safe if the instruction uses physical registers.
559  bool CrossMBBPhysDef = false;
560  SmallSet<MCRegister, 8> PhysRefs;
561  PhysDefVector PhysDefs;
562  bool PhysUseDef = false;
563  if (FoundCSE &&
564  hasLivePhysRegDefUses(&MI, MBB, PhysRefs, PhysDefs, PhysUseDef)) {
565  FoundCSE = false;
566 
567  // ... Unless the CS is local or is in the sole predecessor block
568  // and it also defines the physical register which is not clobbered
569  // in between and the physical register uses were not clobbered.
570  // This can never be the case if the instruction both uses and
571  // defines the same physical register, which was detected above.
572  if (!PhysUseDef) {
573  unsigned CSVN = VNT.lookup(&MI);
574  MachineInstr *CSMI = Exps[CSVN];
575  if (PhysRegDefsReach(CSMI, &MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
576  FoundCSE = true;
577  }
578  }
579 
580  if (!FoundCSE) {
581  VNT.insert(&MI, CurrVN++);
582  Exps.push_back(&MI);
583  continue;
584  }
585 
586  // Found a common subexpression, eliminate it.
587  unsigned CSVN = VNT.lookup(&MI);
588  MachineInstr *CSMI = Exps[CSVN];
589  LLVM_DEBUG(dbgs() << "Examining: " << MI);
590  LLVM_DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
591 
592  // Prevent CSE-ing non-local convergent instructions.
593  // LLVM's current definition of `isConvergent` does not necessarily prove
594  // that non-local CSE is illegal. The following check extends the definition
595  // of `isConvergent` to assume a convergent instruction is dependent not
596  // only on additional conditions, but also on fewer conditions. LLVM does
597  // not have a MachineInstr attribute which expresses this extended
598  // definition, so it's necessary to use `isConvergent` to prevent illegally
599  // CSE-ing the subset of `isConvergent` instructions which do fall into this
600  // extended definition.
601  if (MI.isConvergent() && MI.getParent() != CSMI->getParent()) {
602  LLVM_DEBUG(dbgs() << "*** Convergent MI and subexpression exist in "
603  "different BBs, avoid CSE!\n");
604  VNT.insert(&MI, CurrVN++);
605  Exps.push_back(&MI);
606  continue;
607  }
608 
609  // Check if it's profitable to perform this CSE.
610  bool DoCSE = true;
611  unsigned NumDefs = MI.getNumDefs();
612 
613  for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) {
614  MachineOperand &MO = MI.getOperand(i);
615  if (!MO.isReg() || !MO.isDef())
616  continue;
617  Register OldReg = MO.getReg();
618  Register NewReg = CSMI->getOperand(i).getReg();
619 
620  // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
621  // we should make sure it is not dead at CSMI.
622  if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead())
623  ImplicitDefsToUpdate.push_back(i);
624 
625  // Keep track of implicit defs of CSMI and MI, to clear possibly
626  // made-redundant kill flags.
627  if (MO.isImplicit() && !MO.isDead() && OldReg == NewReg)
628  ImplicitDefs.push_back(OldReg);
629 
630  if (OldReg == NewReg) {
631  --NumDefs;
632  continue;
633  }
634 
636  Register::isVirtualRegister(NewReg) &&
637  "Do not CSE physical register defs!");
638 
639  if (!isProfitableToCSE(NewReg, OldReg, CSMI->getParent(), &MI)) {
640  LLVM_DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
641  DoCSE = false;
642  break;
643  }
644 
645  // Don't perform CSE if the result of the new instruction cannot exist
646  // within the constraints (register class, bank, or low-level type) of
647  // the old instruction.
648  if (!MRI->constrainRegAttrs(NewReg, OldReg)) {
649  LLVM_DEBUG(
650  dbgs() << "*** Not the same register constraints, avoid CSE!\n");
651  DoCSE = false;
652  break;
653  }
654 
655  CSEPairs.push_back(std::make_pair(OldReg, NewReg));
656  --NumDefs;
657  }
658 
659  // Actually perform the elimination.
660  if (DoCSE) {
661  for (const std::pair<unsigned, unsigned> &CSEPair : CSEPairs) {
662  unsigned OldReg = CSEPair.first;
663  unsigned NewReg = CSEPair.second;
664  // OldReg may have been unused but is used now, clear the Dead flag
665  MachineInstr *Def = MRI->getUniqueVRegDef(NewReg);
666  assert(Def != nullptr && "CSEd register has no unique definition?");
667  Def->clearRegisterDeads(NewReg);
668  // Replace with NewReg and clear kill flags which may be wrong now.
669  MRI->replaceRegWith(OldReg, NewReg);
670  MRI->clearKillFlags(NewReg);
671  }
672 
673  // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
674  // we should make sure it is not dead at CSMI.
675  for (unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
676  CSMI->getOperand(ImplicitDefToUpdate).setIsDead(false);
677  for (const auto &PhysDef : PhysDefs)
678  if (!MI.getOperand(PhysDef.first).isDead())
679  CSMI->getOperand(PhysDef.first).setIsDead(false);
680 
681  // Go through implicit defs of CSMI and MI, and clear the kill flags on
682  // their uses in all the instructions between CSMI and MI.
683  // We might have made some of the kill flags redundant, consider:
684  // subs ... implicit-def %nzcv <- CSMI
685  // csinc ... implicit killed %nzcv <- this kill flag isn't valid anymore
686  // subs ... implicit-def %nzcv <- MI, to be eliminated
687  // csinc ... implicit killed %nzcv
688  // Since we eliminated MI, and reused a register imp-def'd by CSMI
689  // (here %nzcv), that register, if it was killed before MI, should have
690  // that kill flag removed, because it's lifetime was extended.
691  if (CSMI->getParent() == MI.getParent()) {
692  for (MachineBasicBlock::iterator II = CSMI, IE = &MI; II != IE; ++II)
693  for (auto ImplicitDef : ImplicitDefs)
694  if (MachineOperand *MO = II->findRegisterUseOperand(
695  ImplicitDef, /*isKill=*/true, TRI))
696  MO->setIsKill(false);
697  } else {
698  // If the instructions aren't in the same BB, bail out and clear the
699  // kill flag on all uses of the imp-def'd register.
700  for (auto ImplicitDef : ImplicitDefs)
701  MRI->clearKillFlags(ImplicitDef);
702  }
703 
704  if (CrossMBBPhysDef) {
705  // Add physical register defs now coming in from a predecessor to MBB
706  // livein list.
707  while (!PhysDefs.empty()) {
708  auto LiveIn = PhysDefs.pop_back_val();
709  if (!MBB->isLiveIn(LiveIn.second))
710  MBB->addLiveIn(LiveIn.second);
711  }
712  ++NumCrossBBCSEs;
713  }
714 
715  MI.eraseFromParent();
716  ++NumCSEs;
717  if (!PhysRefs.empty())
718  ++NumPhysCSEs;
719  if (Commuted)
720  ++NumCommutes;
721  Changed = true;
722  } else {
723  VNT.insert(&MI, CurrVN++);
724  Exps.push_back(&MI);
725  }
726  CSEPairs.clear();
727  ImplicitDefsToUpdate.clear();
728  ImplicitDefs.clear();
729  }
730 
731  return Changed;
732 }
733 
734 /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
735 /// dominator tree node if its a leaf or all of its children are done. Walk
736 /// up the dominator tree to destroy ancestors which are now done.
737 void
738 MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node,
740  if (OpenChildren[Node])
741  return;
742 
743  // Pop scope.
744  ExitScope(Node->getBlock());
745 
746  // Now traverse upwards to pop ancestors whose offsprings are all done.
747  while (MachineDomTreeNode *Parent = Node->getIDom()) {
748  unsigned Left = --OpenChildren[Parent];
749  if (Left != 0)
750  break;
751  ExitScope(Parent->getBlock());
752  Node = Parent;
753  }
754 }
755 
756 bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) {
760 
761  CurrVN = 0;
762 
763  // Perform a DFS walk to determine the order of visit.
764  WorkList.push_back(Node);
765  do {
766  Node = WorkList.pop_back_val();
767  Scopes.push_back(Node);
768  OpenChildren[Node] = Node->getNumChildren();
769  append_range(WorkList, Node->children());
770  } while (!WorkList.empty());
771 
772  // Now perform CSE.
773  bool Changed = false;
774  for (MachineDomTreeNode *Node : Scopes) {
775  MachineBasicBlock *MBB = Node->getBlock();
776  EnterScope(MBB);
777  Changed |= ProcessBlockCSE(MBB);
778  // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
779  ExitScopeIfDone(Node, OpenChildren);
780  }
781 
782  return Changed;
783 }
784 
785 // We use stronger checks for PRE candidate rather than for CSE ones to embrace
786 // checks inside ProcessBlockCSE(), not only inside isCSECandidate(). This helps
787 // to exclude instrs created by PRE that won't be CSEed later.
788 bool MachineCSE::isPRECandidate(MachineInstr *MI) {
789  if (!isCSECandidate(MI) ||
790  MI->isNotDuplicable() ||
791  MI->mayLoad() ||
792  MI->isAsCheapAsAMove() ||
793  MI->getNumDefs() != 1 ||
794  MI->getNumExplicitDefs() != 1)
795  return false;
796 
797  for (const auto &def : MI->defs())
798  if (!Register::isVirtualRegister(def.getReg()))
799  return false;
800 
801  for (const auto &use : MI->uses())
802  if (use.isReg() && !Register::isVirtualRegister(use.getReg()))
803  return false;
804 
805  return true;
806 }
807 
808 bool MachineCSE::ProcessBlockPRE(MachineDominatorTree *DT,
810  bool Changed = false;
812  if (!isPRECandidate(&MI))
813  continue;
814 
815  if (!PREMap.count(&MI)) {
816  PREMap[&MI] = MBB;
817  continue;
818  }
819 
820  auto MBB1 = PREMap[&MI];
821  assert(
822  !DT->properlyDominates(MBB, MBB1) &&
823  "MBB cannot properly dominate MBB1 while DFS through dominators tree!");
824  auto CMBB = DT->findNearestCommonDominator(MBB, MBB1);
825  if (!CMBB->isLegalToHoistInto())
826  continue;
827 
828  if (!isProfitableToHoistInto(CMBB, MBB, MBB1))
829  continue;
830 
831  // Two instrs are partial redundant if their basic blocks are reachable
832  // from one to another but one doesn't dominate another.
833  if (CMBB != MBB1) {
834  auto BB = MBB->getBasicBlock(), BB1 = MBB1->getBasicBlock();
835  if (BB != nullptr && BB1 != nullptr &&
836  (isPotentiallyReachable(BB1, BB) ||
837  isPotentiallyReachable(BB, BB1))) {
838  // The following check extends the definition of `isConvergent` to
839  // assume a convergent instruction is dependent not only on additional
840  // conditions, but also on fewer conditions. LLVM does not have a
841  // MachineInstr attribute which expresses this extended definition, so
842  // it's necessary to use `isConvergent` to prevent illegally PRE-ing the
843  // subset of `isConvergent` instructions which do fall into this
844  // extended definition.
845  if (MI.isConvergent() && CMBB != MBB)
846  continue;
847 
848  assert(MI.getOperand(0).isDef() &&
849  "First operand of instr with one explicit def must be this def");
850  Register VReg = MI.getOperand(0).getReg();
851  Register NewReg = MRI->cloneVirtualRegister(VReg);
852  if (!isProfitableToCSE(NewReg, VReg, CMBB, &MI))
853  continue;
854  MachineInstr &NewMI =
855  TII->duplicate(*CMBB, CMBB->getFirstTerminator(), MI);
856 
857  // When hoisting, make sure we don't carry the debug location of
858  // the original instruction, as that's not correct and can cause
859  // unexpected jumps when debugging optimized code.
860  auto EmptyDL = DebugLoc();
861  NewMI.setDebugLoc(EmptyDL);
862 
863  NewMI.getOperand(0).setReg(NewReg);
864 
865  PREMap[&MI] = CMBB;
866  ++NumPREs;
867  Changed = true;
868  }
869  }
870  }
871  return Changed;
872 }
873 
874 // This simple PRE (partial redundancy elimination) pass doesn't actually
875 // eliminate partial redundancy but transforms it to full redundancy,
876 // anticipating that the next CSE step will eliminate this created redundancy.
877 // If CSE doesn't eliminate this, than created instruction will remain dead
878 // and eliminated later by Remove Dead Machine Instructions pass.
879 bool MachineCSE::PerformSimplePRE(MachineDominatorTree *DT) {
881 
882  PREMap.clear();
883  bool Changed = false;
884  BBs.push_back(DT->getRootNode());
885  do {
886  auto Node = BBs.pop_back_val();
887  append_range(BBs, Node->children());
888 
889  MachineBasicBlock *MBB = Node->getBlock();
890  Changed |= ProcessBlockPRE(DT, MBB);
891 
892  } while (!BBs.empty());
893 
894  return Changed;
895 }
896 
897 bool MachineCSE::isProfitableToHoistInto(MachineBasicBlock *CandidateBB,
899  MachineBasicBlock *MBB1) {
900  if (CandidateBB->getParent()->getFunction().hasMinSize())
901  return true;
902  assert(DT->dominates(CandidateBB, MBB) && "CandidateBB should dominate MBB");
903  assert(DT->dominates(CandidateBB, MBB1) &&
904  "CandidateBB should dominate MBB1");
905  return MBFI->getBlockFreq(CandidateBB) <=
906  MBFI->getBlockFreq(MBB) + MBFI->getBlockFreq(MBB1);
907 }
908 
909 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
910  if (skipFunction(MF.getFunction()))
911  return false;
912 
913  TII = MF.getSubtarget().getInstrInfo();
915  MRI = &MF.getRegInfo();
916  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
917  DT = &getAnalysis<MachineDominatorTree>();
918  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
919  LookAheadLimit = TII->getMachineCSELookAheadLimit();
920  bool ChangedPRE, ChangedCSE;
921  ChangedPRE = PerformSimplePRE(DT);
922  ChangedCSE = PerformCSE(DT->getRootNode());
923  return ChangedPRE || ChangedCSE;
924 }
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
use
Move duplicate certain instructions close to their use
Definition: Localizer.cpp:32
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:326
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:103
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:576
llvm::MachineBasicBlock::getBasicBlock
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Definition: MachineBasicBlock.h:205
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:93
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:1185
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:2057
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:125
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:234
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:372
llvm::MachineInstr::isCopy
bool isCopy() const
Definition: MachineInstr.h:1292
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
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1622
llvm::MachineBlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Definition: MachineBlockFrequencyInfo.cpp:230
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:103
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:153
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:338
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:666
llvm::MachineOperand::isImplicit
bool isImplicit() const
Definition: MachineOperand.h:379
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::AAResults
Definition: AliasAnalysis.h:511
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:501
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:925
llvm::MachineBasicBlock::isSuccessor
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Definition: MachineBasicBlock.cpp:909
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:232
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:900
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:553
ScopedHashTable.h
llvm::MachineInstrExpressionTrait
Special DenseMapInfo traits to compare MachineInstr* by value of the instruction rather than by point...
Definition: MachineInstr.h:1877
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:427
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:656
llvm::MachineLoopInfoID
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
Definition: MachineLoopInfo.cpp:43
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:166
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:419
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:57
Elimination
Machine Common Subexpression Elimination
Definition: MachineCSE.cpp:164
llvm::DenseMap
Definition: DenseMap.h:716
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:384
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:618
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:157
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:943
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:234
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:1238
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
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
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:1823
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:288
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
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:377
llvm::MachineRegisterInfo::isConstantPhysReg
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
Definition: MachineRegisterInfo.cpp:509
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:622
RecyclingAllocator.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::MachineInstr::setDebugLoc
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
Definition: MachineInstr.h:1723
AA
llvm::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:813
Machine
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:369
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:278
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:53
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:104
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1347
isCallerPreservedOrConstPhysReg
static bool isCallerPreservedOrConstPhysReg(MCRegister Reg, const MachineFunction &MF, const TargetRegisterInfo &TRI)
Definition: MachineCSE.cpp:262
llvm::SmallSet::empty
LLVM_NODISCARD bool empty() const
Definition: SmallSet.h:157
MachineOperand.h
llvm::Function::hasMinSize
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:661
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
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:650
llvm::MachineInstrBundleIterator< const MachineInstr >
InitializePasses.h
MachineBlockFrequencyInfo.h
TargetRegisterInfo.h
llvm::MachineBasicBlock::getName
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Definition: MachineBasicBlock.cpp:310
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:280
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:2248
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38