LLVM  13.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  // Check if it's profitable to perform this CSE.
592  bool DoCSE = true;
593  unsigned NumDefs = MI->getNumDefs();
594 
595  for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
596  MachineOperand &MO = MI->getOperand(i);
597  if (!MO.isReg() || !MO.isDef())
598  continue;
599  Register OldReg = MO.getReg();
600  Register NewReg = CSMI->getOperand(i).getReg();
601 
602  // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
603  // we should make sure it is not dead at CSMI.
604  if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead())
605  ImplicitDefsToUpdate.push_back(i);
606 
607  // Keep track of implicit defs of CSMI and MI, to clear possibly
608  // made-redundant kill flags.
609  if (MO.isImplicit() && !MO.isDead() && OldReg == NewReg)
610  ImplicitDefs.push_back(OldReg);
611 
612  if (OldReg == NewReg) {
613  --NumDefs;
614  continue;
615  }
616 
618  Register::isVirtualRegister(NewReg) &&
619  "Do not CSE physical register defs!");
620 
621  if (!isProfitableToCSE(NewReg, OldReg, CSMI->getParent(), MI)) {
622  LLVM_DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
623  DoCSE = false;
624  break;
625  }
626 
627  // Don't perform CSE if the result of the new instruction cannot exist
628  // within the constraints (register class, bank, or low-level type) of
629  // the old instruction.
630  if (!MRI->constrainRegAttrs(NewReg, OldReg)) {
631  LLVM_DEBUG(
632  dbgs() << "*** Not the same register constraints, avoid CSE!\n");
633  DoCSE = false;
634  break;
635  }
636 
637  CSEPairs.push_back(std::make_pair(OldReg, NewReg));
638  --NumDefs;
639  }
640 
641  // Actually perform the elimination.
642  if (DoCSE) {
643  for (const std::pair<unsigned, unsigned> &CSEPair : CSEPairs) {
644  unsigned OldReg = CSEPair.first;
645  unsigned NewReg = CSEPair.second;
646  // OldReg may have been unused but is used now, clear the Dead flag
647  MachineInstr *Def = MRI->getUniqueVRegDef(NewReg);
648  assert(Def != nullptr && "CSEd register has no unique definition?");
649  Def->clearRegisterDeads(NewReg);
650  // Replace with NewReg and clear kill flags which may be wrong now.
651  MRI->replaceRegWith(OldReg, NewReg);
652  MRI->clearKillFlags(NewReg);
653  }
654 
655  // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
656  // we should make sure it is not dead at CSMI.
657  for (unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
658  CSMI->getOperand(ImplicitDefToUpdate).setIsDead(false);
659  for (const auto &PhysDef : PhysDefs)
660  if (!MI->getOperand(PhysDef.first).isDead())
661  CSMI->getOperand(PhysDef.first).setIsDead(false);
662 
663  // Go through implicit defs of CSMI and MI, and clear the kill flags on
664  // their uses in all the instructions between CSMI and MI.
665  // We might have made some of the kill flags redundant, consider:
666  // subs ... implicit-def %nzcv <- CSMI
667  // csinc ... implicit killed %nzcv <- this kill flag isn't valid anymore
668  // subs ... implicit-def %nzcv <- MI, to be eliminated
669  // csinc ... implicit killed %nzcv
670  // Since we eliminated MI, and reused a register imp-def'd by CSMI
671  // (here %nzcv), that register, if it was killed before MI, should have
672  // that kill flag removed, because it's lifetime was extended.
673  if (CSMI->getParent() == MI->getParent()) {
674  for (MachineBasicBlock::iterator II = CSMI, IE = MI; II != IE; ++II)
675  for (auto ImplicitDef : ImplicitDefs)
676  if (MachineOperand *MO = II->findRegisterUseOperand(
677  ImplicitDef, /*isKill=*/true, TRI))
678  MO->setIsKill(false);
679  } else {
680  // If the instructions aren't in the same BB, bail out and clear the
681  // kill flag on all uses of the imp-def'd register.
682  for (auto ImplicitDef : ImplicitDefs)
683  MRI->clearKillFlags(ImplicitDef);
684  }
685 
686  if (CrossMBBPhysDef) {
687  // Add physical register defs now coming in from a predecessor to MBB
688  // livein list.
689  while (!PhysDefs.empty()) {
690  auto LiveIn = PhysDefs.pop_back_val();
691  if (!MBB->isLiveIn(LiveIn.second))
692  MBB->addLiveIn(LiveIn.second);
693  }
694  ++NumCrossBBCSEs;
695  }
696 
697  MI->eraseFromParent();
698  ++NumCSEs;
699  if (!PhysRefs.empty())
700  ++NumPhysCSEs;
701  if (Commuted)
702  ++NumCommutes;
703  Changed = true;
704  } else {
705  VNT.insert(MI, CurrVN++);
706  Exps.push_back(MI);
707  }
708  CSEPairs.clear();
709  ImplicitDefsToUpdate.clear();
710  ImplicitDefs.clear();
711  }
712 
713  return Changed;
714 }
715 
716 /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
717 /// dominator tree node if its a leaf or all of its children are done. Walk
718 /// up the dominator tree to destroy ancestors which are now done.
719 void
720 MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node,
722  if (OpenChildren[Node])
723  return;
724 
725  // Pop scope.
726  ExitScope(Node->getBlock());
727 
728  // Now traverse upwards to pop ancestors whose offsprings are all done.
729  while (MachineDomTreeNode *Parent = Node->getIDom()) {
730  unsigned Left = --OpenChildren[Parent];
731  if (Left != 0)
732  break;
733  ExitScope(Parent->getBlock());
734  Node = Parent;
735  }
736 }
737 
738 bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) {
742 
743  CurrVN = 0;
744 
745  // Perform a DFS walk to determine the order of visit.
746  WorkList.push_back(Node);
747  do {
748  Node = WorkList.pop_back_val();
749  Scopes.push_back(Node);
750  OpenChildren[Node] = Node->getNumChildren();
751  append_range(WorkList, Node->children());
752  } while (!WorkList.empty());
753 
754  // Now perform CSE.
755  bool Changed = false;
756  for (MachineDomTreeNode *Node : Scopes) {
757  MachineBasicBlock *MBB = Node->getBlock();
758  EnterScope(MBB);
759  Changed |= ProcessBlockCSE(MBB);
760  // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
761  ExitScopeIfDone(Node, OpenChildren);
762  }
763 
764  return Changed;
765 }
766 
767 // We use stronger checks for PRE candidate rather than for CSE ones to embrace
768 // checks inside ProcessBlockCSE(), not only inside isCSECandidate(). This helps
769 // to exclude instrs created by PRE that won't be CSEed later.
770 bool MachineCSE::isPRECandidate(MachineInstr *MI) {
771  if (!isCSECandidate(MI) ||
772  MI->isNotDuplicable() ||
773  MI->mayLoad() ||
774  MI->isAsCheapAsAMove() ||
775  MI->getNumDefs() != 1 ||
776  MI->getNumExplicitDefs() != 1)
777  return false;
778 
779  for (const auto &def : MI->defs())
780  if (!Register::isVirtualRegister(def.getReg()))
781  return false;
782 
783  for (const auto &use : MI->uses())
784  if (use.isReg() && !Register::isVirtualRegister(use.getReg()))
785  return false;
786 
787  return true;
788 }
789 
790 bool MachineCSE::ProcessBlockPRE(MachineDominatorTree *DT,
792  bool Changed = false;
793  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;) {
794  MachineInstr *MI = &*I;
795  ++I;
796 
797  if (!isPRECandidate(MI))
798  continue;
799 
800  if (!PREMap.count(MI)) {
801  PREMap[MI] = MBB;
802  continue;
803  }
804 
805  auto MBB1 = PREMap[MI];
806  assert(
807  !DT->properlyDominates(MBB, MBB1) &&
808  "MBB cannot properly dominate MBB1 while DFS through dominators tree!");
809  auto CMBB = DT->findNearestCommonDominator(MBB, MBB1);
810  if (!CMBB->isLegalToHoistInto())
811  continue;
812 
813  if (!isProfitableToHoistInto(CMBB, MBB, MBB1))
814  continue;
815 
816  // Two instrs are partial redundant if their basic blocks are reachable
817  // from one to another but one doesn't dominate another.
818  if (CMBB != MBB1) {
819  auto BB = MBB->getBasicBlock(), BB1 = MBB1->getBasicBlock();
820  if (BB != nullptr && BB1 != nullptr &&
821  (isPotentiallyReachable(BB1, BB) ||
822  isPotentiallyReachable(BB, BB1))) {
823 
824  assert(MI->getOperand(0).isDef() &&
825  "First operand of instr with one explicit def must be this def");
826  Register VReg = MI->getOperand(0).getReg();
827  Register NewReg = MRI->cloneVirtualRegister(VReg);
828  if (!isProfitableToCSE(NewReg, VReg, CMBB, MI))
829  continue;
830  MachineInstr &NewMI =
831  TII->duplicate(*CMBB, CMBB->getFirstTerminator(), *MI);
832 
833  // When hoisting, make sure we don't carry the debug location of
834  // the original instruction, as that's not correct and can cause
835  // unexpected jumps when debugging optimized code.
836  auto EmptyDL = DebugLoc();
837  NewMI.setDebugLoc(EmptyDL);
838 
839  NewMI.getOperand(0).setReg(NewReg);
840 
841  PREMap[MI] = CMBB;
842  ++NumPREs;
843  Changed = true;
844  }
845  }
846  }
847  return Changed;
848 }
849 
850 // This simple PRE (partial redundancy elimination) pass doesn't actually
851 // eliminate partial redundancy but transforms it to full redundancy,
852 // anticipating that the next CSE step will eliminate this created redundancy.
853 // If CSE doesn't eliminate this, than created instruction will remain dead
854 // and eliminated later by Remove Dead Machine Instructions pass.
855 bool MachineCSE::PerformSimplePRE(MachineDominatorTree *DT) {
857 
858  PREMap.clear();
859  bool Changed = false;
860  BBs.push_back(DT->getRootNode());
861  do {
862  auto Node = BBs.pop_back_val();
863  append_range(BBs, Node->children());
864 
865  MachineBasicBlock *MBB = Node->getBlock();
866  Changed |= ProcessBlockPRE(DT, MBB);
867 
868  } while (!BBs.empty());
869 
870  return Changed;
871 }
872 
873 bool MachineCSE::isProfitableToHoistInto(MachineBasicBlock *CandidateBB,
875  MachineBasicBlock *MBB1) {
876  if (CandidateBB->getParent()->getFunction().hasMinSize())
877  return true;
878  assert(DT->dominates(CandidateBB, MBB) && "CandidateBB should dominate MBB");
879  assert(DT->dominates(CandidateBB, MBB1) &&
880  "CandidateBB should dominate MBB1");
881  return MBFI->getBlockFreq(CandidateBB) <=
882  MBFI->getBlockFreq(MBB) + MBFI->getBlockFreq(MBB1);
883 }
884 
885 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
886  if (skipFunction(MF.getFunction()))
887  return false;
888 
889  TII = MF.getSubtarget().getInstrInfo();
891  MRI = &MF.getRegInfo();
892  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
893  DT = &getAnalysis<MachineDominatorTree>();
894  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
895  LookAheadLimit = TII->getMachineCSELookAheadLimit();
896  bool ChangedPRE, ChangedCSE;
897  ChangedPRE = PerformSimplePRE(DT);
898  ChangedCSE = PerformCSE(DT->getRootNode());
899  return ChangedPRE || ChangedCSE;
900 }
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:149
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:100
MachineInstr.h
llvm
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:100
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:572
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:135
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:497
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:1923
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:231
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:1279
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:1735
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
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
llvm::MachineBlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Definition: MachineBlockFrequencyInfo.cpp:228
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:122
MachineRegisterInfo.h
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
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:565
llvm::MachineOperand::isImplicit
bool isImplicit() const
Definition: MachineOperand.h:377
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:456
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:367
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:488
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:900
llvm::MachineBasicBlock::isSuccessor
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Definition: MachineBasicBlock.cpp:931
SI
@ SI
Definition: SIInstrInfo.cpp:7342
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:223
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:402
SmallPtrSet.h
llvm::MachineRegisterInfo::reservedRegsFrozen
bool reservedRegsFrozen() const
reservedRegsFrozen - Returns true after freezeReservedRegs() was called to ensure the set of reserved...
Definition: MachineRegisterInfo.h:875
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:544
ScopedHashTable.h
llvm::MachineInstrExpressionTrait
Special DenseMapInfo traits to compare MachineInstr* by value of the instruction rather than by point...
Definition: MachineInstr.h:1900
MCRegister.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::ScopedHashTable
Definition: ScopedHashTable.h:43
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:555
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:503
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:318
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::skipDebugInstructionsForward
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=false)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
Definition: MachineBasicBlock.h:1115
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:382
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:918
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
llvm::MachineOperand::isRegMask
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Definition: MachineOperand.h:342
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:357
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:227
CFG.h
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:1690
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:372
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:362
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:521
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:365
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:101
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1269
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:703
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:677
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:311
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:22
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:2297
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38