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