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;
517  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
518  MachineInstr *MI = &*I;
519  ++I;
520 
521  if (!isCSECandidate(MI))
522  continue;
523 
524  bool FoundCSE = VNT.count(MI);
525  if (!FoundCSE) {
526  // Using trivial copy propagation to find more CSE opportunities.
527  if (PerformTrivialCopyPropagation(MI, MBB)) {
528  Changed = true;
529 
530  // After coalescing MI itself may become a copy.
531  if (MI->isCopyLike())
532  continue;
533 
534  // Try again to see if CSE is possible.
535  FoundCSE = VNT.count(MI);
536  }
537  }
538 
539  // Commute commutable instructions.
540  bool Commuted = false;
541  if (!FoundCSE && MI->isCommutable()) {
542  if (MachineInstr *NewMI = TII->commuteInstruction(*MI)) {
543  Commuted = true;
544  FoundCSE = VNT.count(NewMI);
545  if (NewMI != MI) {
546  // New instruction. It doesn't need to be kept.
547  NewMI->eraseFromParent();
548  Changed = true;
549  } else if (!FoundCSE)
550  // MI was changed but it didn't help, commute it back!
551  (void)TII->commuteInstruction(*MI);
552  }
553  }
554 
555  // If the instruction defines physical registers and the values *may* be
556  // used, then it's not safe to replace it with a common subexpression.
557  // It's also not safe if the instruction uses physical registers.
558  bool CrossMBBPhysDef = false;
559  SmallSet<MCRegister, 8> PhysRefs;
560  PhysDefVector PhysDefs;
561  bool PhysUseDef = false;
562  if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs,
563  PhysDefs, PhysUseDef)) {
564  FoundCSE = false;
565 
566  // ... Unless the CS is local or is in the sole predecessor block
567  // and it also defines the physical register which is not clobbered
568  // in between and the physical register uses were not clobbered.
569  // This can never be the case if the instruction both uses and
570  // defines the same physical register, which was detected above.
571  if (!PhysUseDef) {
572  unsigned CSVN = VNT.lookup(MI);
573  MachineInstr *CSMI = Exps[CSVN];
574  if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
575  FoundCSE = true;
576  }
577  }
578 
579  if (!FoundCSE) {
580  VNT.insert(MI, CurrVN++);
581  Exps.push_back(MI);
582  continue;
583  }
584 
585  // Found a common subexpression, eliminate it.
586  unsigned CSVN = VNT.lookup(MI);
587  MachineInstr *CSMI = Exps[CSVN];
588  LLVM_DEBUG(dbgs() << "Examining: " << *MI);
589  LLVM_DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
590 
591  // Prevent CSE-ing non-local convergent instructions.
592  // LLVM's current definition of `isConvergent` does not necessarily prove
593  // that non-local CSE is illegal. The following check extends the definition
594  // of `isConvergent` to assume a convergent instruction is dependent not
595  // only on additional conditions, but also on fewer conditions. LLVM does
596  // not have a MachineInstr attribute which expresses this extended
597  // definition, so it's necessary to use `isConvergent` to prevent illegally
598  // CSE-ing the subset of `isConvergent` instructions which do fall into this
599  // extended definition.
600  if (MI->isConvergent() && MI->getParent() != CSMI->getParent()) {
601  LLVM_DEBUG(dbgs() << "*** Convergent MI and subexpression exist in "
602  "different BBs, avoid CSE!\n");
603  VNT.insert(MI, CurrVN++);
604  Exps.push_back(MI);
605  continue;
606  }
607 
608  // Check if it's profitable to perform this CSE.
609  bool DoCSE = true;
610  unsigned NumDefs = MI->getNumDefs();
611 
612  for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
613  MachineOperand &MO = MI->getOperand(i);
614  if (!MO.isReg() || !MO.isDef())
615  continue;
616  Register OldReg = MO.getReg();
617  Register NewReg = CSMI->getOperand(i).getReg();
618 
619  // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
620  // we should make sure it is not dead at CSMI.
621  if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead())
622  ImplicitDefsToUpdate.push_back(i);
623 
624  // Keep track of implicit defs of CSMI and MI, to clear possibly
625  // made-redundant kill flags.
626  if (MO.isImplicit() && !MO.isDead() && OldReg == NewReg)
627  ImplicitDefs.push_back(OldReg);
628 
629  if (OldReg == NewReg) {
630  --NumDefs;
631  continue;
632  }
633 
635  Register::isVirtualRegister(NewReg) &&
636  "Do not CSE physical register defs!");
637 
638  if (!isProfitableToCSE(NewReg, OldReg, CSMI->getParent(), MI)) {
639  LLVM_DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
640  DoCSE = false;
641  break;
642  }
643 
644  // Don't perform CSE if the result of the new instruction cannot exist
645  // within the constraints (register class, bank, or low-level type) of
646  // the old instruction.
647  if (!MRI->constrainRegAttrs(NewReg, OldReg)) {
648  LLVM_DEBUG(
649  dbgs() << "*** Not the same register constraints, avoid CSE!\n");
650  DoCSE = false;
651  break;
652  }
653 
654  CSEPairs.push_back(std::make_pair(OldReg, NewReg));
655  --NumDefs;
656  }
657 
658  // Actually perform the elimination.
659  if (DoCSE) {
660  for (const std::pair<unsigned, unsigned> &CSEPair : CSEPairs) {
661  unsigned OldReg = CSEPair.first;
662  unsigned NewReg = CSEPair.second;
663  // OldReg may have been unused but is used now, clear the Dead flag
664  MachineInstr *Def = MRI->getUniqueVRegDef(NewReg);
665  assert(Def != nullptr && "CSEd register has no unique definition?");
666  Def->clearRegisterDeads(NewReg);
667  // Replace with NewReg and clear kill flags which may be wrong now.
668  MRI->replaceRegWith(OldReg, NewReg);
669  MRI->clearKillFlags(NewReg);
670  }
671 
672  // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
673  // we should make sure it is not dead at CSMI.
674  for (unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
675  CSMI->getOperand(ImplicitDefToUpdate).setIsDead(false);
676  for (const auto &PhysDef : PhysDefs)
677  if (!MI->getOperand(PhysDef.first).isDead())
678  CSMI->getOperand(PhysDef.first).setIsDead(false);
679 
680  // Go through implicit defs of CSMI and MI, and clear the kill flags on
681  // their uses in all the instructions between CSMI and MI.
682  // We might have made some of the kill flags redundant, consider:
683  // subs ... implicit-def %nzcv <- CSMI
684  // csinc ... implicit killed %nzcv <- this kill flag isn't valid anymore
685  // subs ... implicit-def %nzcv <- MI, to be eliminated
686  // csinc ... implicit killed %nzcv
687  // Since we eliminated MI, and reused a register imp-def'd by CSMI
688  // (here %nzcv), that register, if it was killed before MI, should have
689  // that kill flag removed, because it's lifetime was extended.
690  if (CSMI->getParent() == MI->getParent()) {
691  for (MachineBasicBlock::iterator II = CSMI, IE = MI; II != IE; ++II)
692  for (auto ImplicitDef : ImplicitDefs)
693  if (MachineOperand *MO = II->findRegisterUseOperand(
694  ImplicitDef, /*isKill=*/true, TRI))
695  MO->setIsKill(false);
696  } else {
697  // If the instructions aren't in the same BB, bail out and clear the
698  // kill flag on all uses of the imp-def'd register.
699  for (auto ImplicitDef : ImplicitDefs)
700  MRI->clearKillFlags(ImplicitDef);
701  }
702 
703  if (CrossMBBPhysDef) {
704  // Add physical register defs now coming in from a predecessor to MBB
705  // livein list.
706  while (!PhysDefs.empty()) {
707  auto LiveIn = PhysDefs.pop_back_val();
708  if (!MBB->isLiveIn(LiveIn.second))
709  MBB->addLiveIn(LiveIn.second);
710  }
711  ++NumCrossBBCSEs;
712  }
713 
714  MI->eraseFromParent();
715  ++NumCSEs;
716  if (!PhysRefs.empty())
717  ++NumPhysCSEs;
718  if (Commuted)
719  ++NumCommutes;
720  Changed = true;
721  } else {
722  VNT.insert(MI, CurrVN++);
723  Exps.push_back(MI);
724  }
725  CSEPairs.clear();
726  ImplicitDefsToUpdate.clear();
727  ImplicitDefs.clear();
728  }
729 
730  return Changed;
731 }
732 
733 /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
734 /// dominator tree node if its a leaf or all of its children are done. Walk
735 /// up the dominator tree to destroy ancestors which are now done.
736 void
737 MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node,
739  if (OpenChildren[Node])
740  return;
741 
742  // Pop scope.
743  ExitScope(Node->getBlock());
744 
745  // Now traverse upwards to pop ancestors whose offsprings are all done.
746  while (MachineDomTreeNode *Parent = Node->getIDom()) {
747  unsigned Left = --OpenChildren[Parent];
748  if (Left != 0)
749  break;
750  ExitScope(Parent->getBlock());
751  Node = Parent;
752  }
753 }
754 
755 bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) {
759 
760  CurrVN = 0;
761 
762  // Perform a DFS walk to determine the order of visit.
763  WorkList.push_back(Node);
764  do {
765  Node = WorkList.pop_back_val();
766  Scopes.push_back(Node);
767  OpenChildren[Node] = Node->getNumChildren();
768  append_range(WorkList, Node->children());
769  } while (!WorkList.empty());
770 
771  // Now perform CSE.
772  bool Changed = false;
773  for (MachineDomTreeNode *Node : Scopes) {
774  MachineBasicBlock *MBB = Node->getBlock();
775  EnterScope(MBB);
776  Changed |= ProcessBlockCSE(MBB);
777  // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
778  ExitScopeIfDone(Node, OpenChildren);
779  }
780 
781  return Changed;
782 }
783 
784 // We use stronger checks for PRE candidate rather than for CSE ones to embrace
785 // checks inside ProcessBlockCSE(), not only inside isCSECandidate(). This helps
786 // to exclude instrs created by PRE that won't be CSEed later.
787 bool MachineCSE::isPRECandidate(MachineInstr *MI) {
788  if (!isCSECandidate(MI) ||
789  MI->isNotDuplicable() ||
790  MI->mayLoad() ||
791  MI->isAsCheapAsAMove() ||
792  MI->getNumDefs() != 1 ||
793  MI->getNumExplicitDefs() != 1)
794  return false;
795 
796  for (const auto &def : MI->defs())
797  if (!Register::isVirtualRegister(def.getReg()))
798  return false;
799 
800  for (const auto &use : MI->uses())
801  if (use.isReg() && !Register::isVirtualRegister(use.getReg()))
802  return false;
803 
804  return true;
805 }
806 
807 bool MachineCSE::ProcessBlockPRE(MachineDominatorTree *DT,
809  bool Changed = false;
810  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;) {
811  MachineInstr *MI = &*I;
812  ++I;
813 
814  if (!isPRECandidate(MI))
815  continue;
816 
817  if (!PREMap.count(MI)) {
818  PREMap[MI] = MBB;
819  continue;
820  }
821 
822  auto MBB1 = PREMap[MI];
823  assert(
824  !DT->properlyDominates(MBB, MBB1) &&
825  "MBB cannot properly dominate MBB1 while DFS through dominators tree!");
826  auto CMBB = DT->findNearestCommonDominator(MBB, MBB1);
827  if (!CMBB->isLegalToHoistInto())
828  continue;
829 
830  if (!isProfitableToHoistInto(CMBB, MBB, MBB1))
831  continue;
832 
833  // Two instrs are partial redundant if their basic blocks are reachable
834  // from one to another but one doesn't dominate another.
835  if (CMBB != MBB1) {
836  auto BB = MBB->getBasicBlock(), BB1 = MBB1->getBasicBlock();
837  if (BB != nullptr && BB1 != nullptr &&
838  (isPotentiallyReachable(BB1, BB) ||
839  isPotentiallyReachable(BB, BB1))) {
840  // The following check extends the definition of `isConvergent` to
841  // assume a convergent instruction is dependent not only on additional
842  // conditions, but also on fewer conditions. LLVM does not have a
843  // MachineInstr attribute which expresses this extended definition, so
844  // it's necessary to use `isConvergent` to prevent illegally PRE-ing the
845  // subset of `isConvergent` instructions which do fall into this
846  // extended definition.
847  if (MI->isConvergent() && CMBB != MBB)
848  continue;
849 
850  assert(MI->getOperand(0).isDef() &&
851  "First operand of instr with one explicit def must be this def");
852  Register VReg = MI->getOperand(0).getReg();
853  Register NewReg = MRI->cloneVirtualRegister(VReg);
854  if (!isProfitableToCSE(NewReg, VReg, CMBB, MI))
855  continue;
856  MachineInstr &NewMI =
857  TII->duplicate(*CMBB, CMBB->getFirstTerminator(), *MI);
858 
859  // When hoisting, make sure we don't carry the debug location of
860  // the original instruction, as that's not correct and can cause
861  // unexpected jumps when debugging optimized code.
862  auto EmptyDL = DebugLoc();
863  NewMI.setDebugLoc(EmptyDL);
864 
865  NewMI.getOperand(0).setReg(NewReg);
866 
867  PREMap[MI] = CMBB;
868  ++NumPREs;
869  Changed = true;
870  }
871  }
872  }
873  return Changed;
874 }
875 
876 // This simple PRE (partial redundancy elimination) pass doesn't actually
877 // eliminate partial redundancy but transforms it to full redundancy,
878 // anticipating that the next CSE step will eliminate this created redundancy.
879 // If CSE doesn't eliminate this, than created instruction will remain dead
880 // and eliminated later by Remove Dead Machine Instructions pass.
881 bool MachineCSE::PerformSimplePRE(MachineDominatorTree *DT) {
883 
884  PREMap.clear();
885  bool Changed = false;
886  BBs.push_back(DT->getRootNode());
887  do {
888  auto Node = BBs.pop_back_val();
889  append_range(BBs, Node->children());
890 
891  MachineBasicBlock *MBB = Node->getBlock();
892  Changed |= ProcessBlockPRE(DT, MBB);
893 
894  } while (!BBs.empty());
895 
896  return Changed;
897 }
898 
899 bool MachineCSE::isProfitableToHoistInto(MachineBasicBlock *CandidateBB,
901  MachineBasicBlock *MBB1) {
902  if (CandidateBB->getParent()->getFunction().hasMinSize())
903  return true;
904  assert(DT->dominates(CandidateBB, MBB) && "CandidateBB should dominate MBB");
905  assert(DT->dominates(CandidateBB, MBB1) &&
906  "CandidateBB should dominate MBB1");
907  return MBFI->getBlockFreq(CandidateBB) <=
908  MBFI->getBlockFreq(MBB) + MBFI->getBlockFreq(MBB1);
909 }
910 
911 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
912  if (skipFunction(MF.getFunction()))
913  return false;
914 
915  TII = MF.getSubtarget().getInstrInfo();
917  MRI = &MF.getRegInfo();
918  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
919  DT = &getAnalysis<MachineDominatorTree>();
920  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
921  LookAheadLimit = TII->getMachineCSELookAheadLimit();
922  bool ChangedPRE, ChangedCSE;
923  ChangedPRE = PerformSimplePRE(DT);
924  ChangedCSE = PerformCSE(DT->getRootNode());
925  return ChangedPRE || ChangedCSE;
926 }
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:316
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
MachineInstr.h
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
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:580
llvm::MachineBasicBlock::getBasicBlock
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Definition: MachineBasicBlock.h:202
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:1168
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:1981
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:411
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:134
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:369
llvm::MachineInstr::isCopy
bool isCopy() const
Definition: MachineInstr.h:1291
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::MachineInstr::setDebugLoc
void setDebugLoc(DebugLoc dl)
Replace current source information with new such.
Definition: MachineInstr.h:1745
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:635
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
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::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:328
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:640
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:508
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:913
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:129
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:400
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:1899
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:431
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:630
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:164
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:59
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:225
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:234
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:1206
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:419
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:1748
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:180
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:367
llvm::MachineRegisterInfo::isConstantPhysReg
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
Definition: MachineRegisterInfo.cpp:513
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:596
RecyclingAllocator.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
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:268
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:1336
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:155
MachineOperand.h
llvm::Function::hasMinSize
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:669
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:45
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:314
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
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:2300
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37