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/CodeGen/MachineCSE.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/ScopedHashTable.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/SmallSet.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/ADT/Statistic.h"
22#include "llvm/Analysis/CFG.h"
23#include "llvm/CodeGen/MachineBasicBlock.h"
24#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
25#include "llvm/CodeGen/MachineDominators.h"
26#include "llvm/CodeGen/MachineFunction.h"
27#include "llvm/CodeGen/MachineFunctionPass.h"
28#include "llvm/CodeGen/MachineInstr.h"
29#include "llvm/CodeGen/MachineLoopInfo.h"
30#include "llvm/CodeGen/MachineOperand.h"
31#include "llvm/CodeGen/MachineRegisterInfo.h"
32#include "llvm/CodeGen/Passes.h"
33#include "llvm/CodeGen/TargetInstrInfo.h"
34#include "llvm/CodeGen/TargetOpcodes.h"
35#include "llvm/CodeGen/TargetRegisterInfo.h"
36#include "llvm/CodeGen/TargetSubtargetInfo.h"
37#include "llvm/InitializePasses.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"
43#include "llvm/Support/RecyclingAllocator.h"
44#include "llvm/Support/raw_ostream.h"
45#include <cassert>
46#include <iterator>
47#include <utility>
48
49using namespace llvm;
50
51#define DEBUG_TYPE "machine-cse"
52
53STATISTIC(NumCoalesces, "Number of copies coalesced");
54STATISTIC(NumCSEs, "Number of common subexpression eliminated");
55STATISTIC(NumPREs, "Number of partial redundant expression"
56 " transformed to fully redundant");
57STATISTIC(NumPhysCSEs,
58 "Number of physreg referencing common subexpr eliminated");
59STATISTIC(NumCrossBBCSEs,
60 "Number of cross-MBB physreg referencing CS eliminated");
61STATISTIC(NumCommutes, "Number of copies coalesced after commuting");
62
63// Threshold to avoid excessive cost to compute isProfitableToCSE.
64static cl::opt<int>
65 CSUsesThreshold("csuses-threshold", cl::Hidden, cl::init(Val: 1024),
66 cl::desc("Threshold for the size of CSUses"));
67
68static cl::opt<bool> AggressiveMachineCSE(
69 "aggressive-machine-cse", cl::Hidden, cl::init(Val: false),
70 cl::desc("Override the profitability heuristics for Machine CSE"));
71
72namespace {
73
74class MachineCSEImpl {
75 const TargetInstrInfo *TII = nullptr;
76 const TargetRegisterInfo *TRI = nullptr;
77 MachineDominatorTree *DT = nullptr;
78 MachineRegisterInfo *MRI = nullptr;
79 MachineBlockFrequencyInfo *MBFI = nullptr;
80
81public:
82 MachineCSEImpl(MachineDominatorTree *DT, MachineBlockFrequencyInfo *MBFI)
83 : DT(DT), MBFI(MBFI) {}
84 bool run(MachineFunction &MF);
85
86private:
87 using AllocatorTy =
88 RecyclingAllocator<BumpPtrAllocator,
89 ScopedHashTableVal<MachineInstr *, unsigned>>;
90 using ScopedHTType =
91 ScopedHashTable<MachineInstr *, unsigned, MachineInstrExpressionTrait,
92 AllocatorTy>;
93 using ScopeType = ScopedHTType::ScopeTy;
94 using PhysDefVector = SmallVector<std::pair<unsigned, Register>, 2>;
95
96 unsigned LookAheadLimit = 0;
97 DenseMap<MachineBasicBlock *, ScopeType *> ScopeMap;
98 DenseMap<MachineInstr *, MachineBasicBlock *, MachineInstrExpressionTrait>
99 PREMap;
100 ScopedHTType VNT;
101 SmallVector<MachineInstr *, 64> Exps;
102 unsigned CurrVN = 0;
103
104 bool PerformTrivialCopyPropagation(MachineInstr *MI, MachineBasicBlock *MBB);
105 bool isPhysDefTriviallyDead(MCRegister Reg,
106 MachineBasicBlock::const_iterator I,
107 MachineBasicBlock::const_iterator E) const;
108 bool hasLivePhysRegDefUses(const MachineInstr *MI,
109 const MachineBasicBlock *MBB,
110 SmallSet<MCRegister, 8> &PhysRefs,
111 PhysDefVector &PhysDefs, bool &PhysUseDef) const;
112 bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
113 const SmallSet<MCRegister, 8> &PhysRefs,
114 const PhysDefVector &PhysDefs, bool &NonLocal) const;
115 bool isCSECandidate(MachineInstr *MI);
116 bool isProfitableToCSE(Register CSReg, Register Reg, MachineBasicBlock *CSBB,
117 MachineInstr *MI);
118 void EnterScope(MachineBasicBlock *MBB);
119 void ExitScope(MachineBasicBlock *MBB);
120 bool ProcessBlockCSE(MachineBasicBlock *MBB);
121 void ExitScopeIfDone(MachineDomTreeNode *Node,
122 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren);
123 bool PerformCSE(MachineDomTreeNode *Node);
124
125 bool isPRECandidate(MachineInstr *MI, SmallSet<MCRegister, 8> &PhysRefs);
126 bool ProcessBlockPRE(MachineDominatorTree *MDT, MachineBasicBlock *MBB);
127 bool PerformSimplePRE(MachineDominatorTree *DT);
128 /// Heuristics to see if it's profitable to move common computations of MBB
129 /// and MBB1 to CandidateBB.
130 bool isProfitableToHoistInto(MachineBasicBlock *CandidateBB,
131 MachineBasicBlock *MBB, MachineBasicBlock *MBB1);
132 void releaseMemory();
133};
134
135class MachineCSELegacy : public MachineFunctionPass {
136public:
137 static char ID; // Pass identification
138
139 MachineCSELegacy() : MachineFunctionPass(ID) {}
140
141 bool runOnMachineFunction(MachineFunction &MF) override;
142
143 void getAnalysisUsage(AnalysisUsage &AU) const override {
144 AU.setPreservesCFG();
145 MachineFunctionPass::getAnalysisUsage(AU);
146 AU.addRequired<MachineDominatorTreeWrapperPass>();
147 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
148 }
149
150 MachineFunctionProperties getRequiredProperties() const override {
151 return MachineFunctionProperties().setIsSSA();
152 }
153};
154} // end anonymous namespace
155
156char MachineCSELegacy::ID = 0;
157
158char &llvm::MachineCSELegacyID = MachineCSELegacy::ID;
159
160INITIALIZE_PASS_BEGIN(MachineCSELegacy, DEBUG_TYPE,
161 "Machine Common Subexpression Elimination", false, false)
162INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
163INITIALIZE_PASS_END(MachineCSELegacy, DEBUG_TYPE,
164 "Machine Common Subexpression Elimination", false, false)
165
166/// The source register of a COPY machine instruction can be propagated to all
167/// its users, and this propagation could increase the probability of finding
168/// common subexpressions. If the COPY has only one user, the COPY itself can
169/// be removed.
170bool MachineCSEImpl::PerformTrivialCopyPropagation(MachineInstr *MI,
171 MachineBasicBlock *MBB) {
172 bool Changed = false;
173 for (MachineOperand &MO : MI->all_uses()) {
174 Register Reg = MO.getReg();
175 if (!Reg.isVirtual())
176 continue;
177 bool OnlyOneUse = MRI->hasOneNonDBGUse(RegNo: Reg);
178 MachineInstr *DefMI = MRI->getVRegDef(Reg);
179 if (!DefMI || !DefMI->isCopy())
180 continue;
181 Register SrcReg = DefMI->getOperand(i: 1).getReg();
182 if (!SrcReg.isVirtual())
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(i: 1).getSubReg())
197 continue;
198 if (!MRI->constrainRegAttrs(Reg: SrcReg, ConstrainingReg: 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(Reg: 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.
211 DefMI->changeDebugValuesDefReg(Reg: SrcReg);
212
213 DefMI->eraseFromParent();
214 ++NumCoalesces;
215 }
216 Changed = true;
217 }
218
219 return Changed;
220}
221
222bool MachineCSEImpl::isPhysDefTriviallyDead(
223 MCRegister Reg, MachineBasicBlock::const_iterator I,
224 MachineBasicBlock::const_iterator E) const {
225 unsigned LookAheadLeft = LookAheadLimit;
226 while (LookAheadLeft) {
227 // Skip over dbg_value's.
228 I = skipDebugInstructionsForward(It: I, End: E);
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(PhysReg: Reg))
237 SeenDef = true;
238 if (!MO.isReg() || !MO.getReg())
239 continue;
240 if (!TRI->regsOverlap(RegA: MO.getReg(), RegB: 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
258static bool isCallerPreservedOrConstPhysReg(MCRegister Reg,
259 const MachineOperand &MO,
260 const MachineFunction &MF,
261 const TargetRegisterInfo &TRI,
262 const TargetInstrInfo &TII) {
263 // MachineRegisterInfo::isConstantPhysReg directly called by
264 // MachineRegisterInfo::isCallerPreservedOrConstPhysReg expects the
265 // reserved registers to be frozen. That doesn't cause a problem post-ISel as
266 // most (if not all) targets freeze reserved registers right after ISel.
267 //
268 // It does cause issues mid-GlobalISel, however, hence the additional
269 // reservedRegsFrozen check.
270 const MachineRegisterInfo &MRI = MF.getRegInfo();
271 return TRI.isCallerPreservedPhysReg(PhysReg: Reg, MF) || TII.isIgnorableUse(MO) ||
272 (MRI.reservedRegsFrozen() && MRI.isConstantPhysReg(PhysReg: Reg));
273}
274
275/// hasLivePhysRegDefUses - Return true if the specified instruction read/write
276/// physical registers (except for dead defs of physical registers). It also
277/// returns the physical register def by reference if it's the only one and the
278/// instruction does not uses a physical register.
279bool MachineCSEImpl::hasLivePhysRegDefUses(const MachineInstr *MI,
280 const MachineBasicBlock *MBB,
281 SmallSet<MCRegister, 8> &PhysRefs,
282 PhysDefVector &PhysDefs,
283 bool &PhysUseDef) const {
284 // First, add all uses to PhysRefs.
285 for (const MachineOperand &MO : MI->all_uses()) {
286 Register Reg = MO.getReg();
287 if (!Reg)
288 continue;
289 if (Reg.isVirtual())
290 continue;
291 // Reading either caller preserved or constant physregs is ok.
292 if (!isCallerPreservedOrConstPhysReg(Reg: Reg.asMCReg(), MO, MF: *MI->getMF(), TRI: *TRI,
293 TII: *TII))
294 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
295 PhysRefs.insert(V: *AI);
296 }
297
298 // Next, collect all defs into PhysDefs. If any is already in PhysRefs
299 // (which currently contains only uses), set the PhysUseDef flag.
300 PhysUseDef = false;
301 MachineBasicBlock::const_iterator I = MI; I = std::next(x: I);
302 for (const auto &MOP : llvm::enumerate(First: MI->operands())) {
303 const MachineOperand &MO = MOP.value();
304 if (!MO.isReg() || !MO.isDef())
305 continue;
306 Register Reg = MO.getReg();
307 if (!Reg)
308 continue;
309 if (Reg.isVirtual())
310 continue;
311 // Check against PhysRefs even if the def is "dead".
312 if (PhysRefs.count(V: Reg.asMCReg()))
313 PhysUseDef = true;
314 // If the def is dead, it's ok. But the def may not marked "dead". That's
315 // common since this pass is run before livevariables. We can scan
316 // forward a few instructions and check if it is obviously dead.
317 if (!MO.isDead() && !isPhysDefTriviallyDead(Reg: Reg.asMCReg(), I, E: MBB->end()))
318 PhysDefs.emplace_back(Args: MOP.index(), Args&: Reg);
319 }
320
321 // Finally, add all defs to PhysRefs as well.
322 for (const auto &Def : PhysDefs)
323 for (MCRegAliasIterator AI(Def.second, TRI, true); AI.isValid(); ++AI)
324 PhysRefs.insert(V: *AI);
325
326 return !PhysRefs.empty();
327}
328
329bool MachineCSEImpl::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
330 const SmallSet<MCRegister, 8> &PhysRefs,
331 const 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 (const auto &PhysDef : PhysDefs) {
345 if (MRI->isAllocatable(PhysReg: PhysDef.second) || MRI->isReserved(PhysReg: PhysDef.second))
346 // Avoid extending live range of physical registers if they are
347 //allocatable or reserved.
348 return false;
349 }
350 CrossMBB = true;
351 }
352 MachineBasicBlock::const_iterator I = CSMI; I = std::next(x: I);
353 MachineBasicBlock::const_iterator E = MI;
354 MachineBasicBlock::const_iterator EE = CSMBB->end();
355 unsigned LookAheadLeft = LookAheadLimit;
356 while (LookAheadLeft) {
357 // Skip over dbg_value's.
358 while (I != E && I != EE && I->isDebugInstr())
359 ++I;
360
361 if (I == EE) {
362 assert(CrossMBB && "Reaching end-of-MBB without finding MI?");
363 (void)CrossMBB;
364 CrossMBB = false;
365 NonLocal = true;
366 I = MBB->begin();
367 EE = MBB->end();
368 continue;
369 }
370
371 if (I == E)
372 return true;
373
374 for (const MachineOperand &MO : I->operands()) {
375 // RegMasks go on instructions like calls that clobber lots of physregs.
376 // Don't attempt to CSE across such an instruction.
377 if (MO.isRegMask())
378 return false;
379 if (!MO.isReg() || !MO.isDef())
380 continue;
381 Register MOReg = MO.getReg();
382 if (MOReg.isVirtual())
383 continue;
384 if (PhysRefs.count(V: MOReg.asMCReg()))
385 return false;
386 }
387
388 --LookAheadLeft;
389 ++I;
390 }
391
392 return false;
393}
394
395bool MachineCSEImpl::isCSECandidate(MachineInstr *MI) {
396 if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || MI->isKill() ||
397 MI->isInlineAsm() || MI->isDebugInstr() || MI->isJumpTableDebugInfo() ||
398 MI->isFakeUse())
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())
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.
432bool MachineCSEImpl::isProfitableToCSE(Register CSReg, Register Reg,
433 MachineBasicBlock *CSBB,
434 MachineInstr *MI) {
435 if (AggressiveMachineCSE)
436 return true;
437
438 // FIXME: Heuristics that works around the lack the live range splitting.
439
440 // If CSReg is used at all uses of Reg, CSE should not increase register
441 // pressure of CSReg.
442 bool MayIncreasePressure = true;
443 if (CSReg.isVirtual() && Reg.isVirtual()) {
444 MayIncreasePressure = false;
445 SmallPtrSet<MachineInstr*, 8> CSUses;
446 int NumOfUses = 0;
447 for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg: CSReg)) {
448 CSUses.insert(Ptr: &MI);
449 // Too costly to compute if NumOfUses is very large. Conservatively assume
450 // MayIncreasePressure to avoid spending too much time here.
451 if (++NumOfUses > CSUsesThreshold) {
452 MayIncreasePressure = true;
453 break;
454 }
455 }
456 if (!MayIncreasePressure)
457 for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
458 if (!CSUses.count(Ptr: &MI)) {
459 MayIncreasePressure = true;
460 break;
461 }
462 }
463 }
464 if (!MayIncreasePressure) return true;
465
466 // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in
467 // an immediate predecessor. We don't want to increase register pressure and
468 // end up causing other computation to be spilled.
469 if (TII->isAsCheapAsAMove(MI: *MI)) {
470 MachineBasicBlock *BB = MI->getParent();
471 if (CSBB != BB && !CSBB->isSuccessor(MBB: BB))
472 return false;
473 }
474
475 // Heuristics #2: If the expression doesn't not use a vr and the only use
476 // of the redundant computation are copies, do not cse.
477 bool HasVRegUse = false;
478 for (const MachineOperand &MO : MI->all_uses()) {
479 if (MO.getReg().isVirtual()) {
480 HasVRegUse = true;
481 break;
482 }
483 }
484 if (!HasVRegUse) {
485 bool HasNonCopyUse = false;
486 for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
487 // Ignore copies.
488 if (!MI.isCopyLike()) {
489 HasNonCopyUse = true;
490 break;
491 }
492 }
493 if (!HasNonCopyUse)
494 return false;
495 }
496
497 // Heuristics #3: If the common subexpression is used by PHIs, do not reuse
498 // it unless the defined value is already used in the BB of the new use.
499 bool HasPHI = false;
500 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg: CSReg)) {
501 HasPHI |= UseMI.isPHI();
502 if (UseMI.getParent() == MI->getParent())
503 return true;
504 }
505
506 return !HasPHI;
507}
508
509void MachineCSEImpl::EnterScope(MachineBasicBlock *MBB) {
510 LLVM_DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n');
511 ScopeType *Scope = new ScopeType(VNT);
512 ScopeMap[MBB] = Scope;
513}
514
515void MachineCSEImpl::ExitScope(MachineBasicBlock *MBB) {
516 LLVM_DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n');
517 auto SI = ScopeMap.find(Val: MBB);
518 assert(SI != ScopeMap.end());
519 delete SI->second;
520 ScopeMap.erase(I: SI);
521}
522
523bool MachineCSEImpl::ProcessBlockCSE(MachineBasicBlock *MBB) {
524 bool Changed = false;
525
526 SmallVector<std::pair<Register, Register>, 8> CSEPairs;
527 SmallVector<unsigned, 2> ImplicitDefsToUpdate;
528 SmallVector<Register, 2> ImplicitDefs;
529 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: *MBB)) {
530 if (!isCSECandidate(MI: &MI))
531 continue;
532
533 bool FoundCSE = VNT.count(Key: &MI);
534 if (!FoundCSE) {
535 // Using trivial copy propagation to find more CSE opportunities.
536 if (PerformTrivialCopyPropagation(MI: &MI, MBB)) {
537 Changed = true;
538
539 // After coalescing MI itself may become a copy.
540 if (MI.isCopyLike())
541 continue;
542
543 // Try again to see if CSE is possible.
544 FoundCSE = VNT.count(Key: &MI);
545 }
546 }
547
548 // Commute commutable instructions.
549 bool Commuted = false;
550 if (!FoundCSE && MI.isCommutable()) {
551 if (MachineInstr *NewMI = TII->commuteInstruction(MI)) {
552 Commuted = true;
553 FoundCSE = VNT.count(Key: NewMI);
554 if (NewMI != &MI) {
555 // New instruction. It doesn't need to be kept.
556 NewMI->eraseFromParent();
557 Changed = true;
558 } else if (!FoundCSE)
559 // MI was changed but it didn't help, commute it back!
560 (void)TII->commuteInstruction(MI);
561 }
562 }
563
564 // If the instruction defines physical registers and the values *may* be
565 // used, then it's not safe to replace it with a common subexpression.
566 // It's also not safe if the instruction uses physical registers.
567 bool CrossMBBPhysDef = false;
568 SmallSet<MCRegister, 8> PhysRefs;
569 PhysDefVector PhysDefs;
570 bool PhysUseDef = false;
571 if (FoundCSE &&
572 hasLivePhysRegDefUses(MI: &MI, MBB, PhysRefs, PhysDefs, PhysUseDef)) {
573 FoundCSE = false;
574
575 // ... Unless the CS is local or is in the sole predecessor block
576 // and it also defines the physical register which is not clobbered
577 // in between and the physical register uses were not clobbered.
578 // This can never be the case if the instruction both uses and
579 // defines the same physical register, which was detected above.
580 if (!PhysUseDef) {
581 unsigned CSVN = VNT.lookup(Key: &MI);
582 MachineInstr *CSMI = Exps[CSVN];
583 if (PhysRegDefsReach(CSMI, MI: &MI, PhysRefs, PhysDefs, NonLocal&: CrossMBBPhysDef))
584 FoundCSE = true;
585 }
586 }
587
588 if (!FoundCSE) {
589 VNT.insert(Key: &MI, Val: CurrVN++);
590 Exps.push_back(Elt: &MI);
591 continue;
592 }
593
594 // Found a common subexpression, eliminate it.
595 unsigned CSVN = VNT.lookup(Key: &MI);
596 MachineInstr *CSMI = Exps[CSVN];
597 LLVM_DEBUG(dbgs() << "Examining: " << MI);
598 LLVM_DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
599
600 // Prevent CSE-ing non-local convergent instructions.
601 // LLVM's current definition of `isConvergent` does not necessarily prove
602 // that non-local CSE is illegal. The following check extends the definition
603 // of `isConvergent` to assume a convergent instruction is dependent not
604 // only on additional conditions, but also on fewer conditions. LLVM does
605 // not have a MachineInstr attribute which expresses this extended
606 // definition, so it's necessary to use `isConvergent` to prevent illegally
607 // CSE-ing the subset of `isConvergent` instructions which do fall into this
608 // extended definition.
609 if (MI.isConvergent() && MI.getParent() != CSMI->getParent()) {
610 LLVM_DEBUG(dbgs() << "*** Convergent MI and subexpression exist in "
611 "different BBs, avoid CSE!\n");
612 VNT.insert(Key: &MI, Val: CurrVN++);
613 Exps.push_back(Elt: &MI);
614 continue;
615 }
616
617 // Check if it's profitable to perform this CSE.
618 bool DoCSE = true;
619 unsigned NumDefs = MI.getNumDefs();
620
621 for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) {
622 MachineOperand &MO = MI.getOperand(i);
623 if (!MO.isReg() || !MO.isDef())
624 continue;
625 Register OldReg = MO.getReg();
626 Register NewReg = CSMI->getOperand(i).getReg();
627
628 // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
629 // we should make sure it is not dead at CSMI.
630 if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead())
631 ImplicitDefsToUpdate.push_back(Elt: i);
632
633 // Keep track of implicit defs of CSMI and MI, to clear possibly
634 // made-redundant kill flags.
635 if (MO.isImplicit() && !MO.isDead() && OldReg == NewReg)
636 ImplicitDefs.push_back(Elt: OldReg);
637
638 if (OldReg == NewReg) {
639 --NumDefs;
640 continue;
641 }
642
643 assert(OldReg.isVirtual() && NewReg.isVirtual() &&
644 "Do not CSE physical register defs!");
645
646 if (!isProfitableToCSE(CSReg: NewReg, Reg: OldReg, CSBB: CSMI->getParent(), MI: &MI)) {
647 LLVM_DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
648 DoCSE = false;
649 break;
650 }
651
652 // Don't perform CSE if the result of the new instruction cannot exist
653 // within the constraints (register class, bank, or low-level type) of
654 // the old instruction.
655 if (!MRI->constrainRegAttrs(Reg: NewReg, ConstrainingReg: OldReg)) {
656 LLVM_DEBUG(
657 dbgs() << "*** Not the same register constraints, avoid CSE!\n");
658 DoCSE = false;
659 break;
660 }
661
662 CSEPairs.emplace_back(Args&: OldReg, Args&: NewReg);
663 --NumDefs;
664 }
665
666 // Actually perform the elimination.
667 if (DoCSE) {
668 for (const std::pair<Register, Register> &CSEPair : CSEPairs) {
669 Register OldReg = CSEPair.first;
670 Register NewReg = CSEPair.second;
671 // OldReg may have been unused but is used now, clear the Dead flag
672 MachineInstr *Def = MRI->getUniqueVRegDef(Reg: NewReg);
673 assert(Def != nullptr && "CSEd register has no unique definition?");
674 Def->clearRegisterDeads(Reg: NewReg);
675 // Replace with NewReg and clear kill flags which may be wrong now.
676 MRI->replaceRegWith(FromReg: OldReg, ToReg: NewReg);
677 MRI->clearKillFlags(Reg: NewReg);
678 }
679
680 // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
681 // we should make sure it is not dead at CSMI.
682 for (unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
683 CSMI->getOperand(i: ImplicitDefToUpdate).setIsDead(false);
684 for (const auto &PhysDef : PhysDefs)
685 if (!MI.getOperand(i: PhysDef.first).isDead())
686 CSMI->getOperand(i: PhysDef.first).setIsDead(false);
687
688 // Go through implicit defs of CSMI and MI, and clear the kill flags on
689 // their uses in all the instructions between CSMI and MI.
690 // We might have made some of the kill flags redundant, consider:
691 // subs ... implicit-def %nzcv <- CSMI
692 // csinc ... implicit killed %nzcv <- this kill flag isn't valid anymore
693 // subs ... implicit-def %nzcv <- MI, to be eliminated
694 // csinc ... implicit killed %nzcv
695 // Since we eliminated MI, and reused a register imp-def'd by CSMI
696 // (here %nzcv), that register, if it was killed before MI, should have
697 // that kill flag removed, because it's lifetime was extended.
698 if (CSMI->getParent() == MI.getParent()) {
699 for (MachineBasicBlock::iterator II = CSMI, IE = &MI; II != IE; ++II)
700 for (auto ImplicitDef : ImplicitDefs)
701 if (MachineOperand *MO = II->findRegisterUseOperand(
702 Reg: ImplicitDef, TRI, /*isKill=*/true))
703 MO->setIsKill(false);
704 } else {
705 // If the instructions aren't in the same BB, bail out and clear the
706 // kill flag on all uses of the imp-def'd register.
707 for (auto ImplicitDef : ImplicitDefs)
708 MRI->clearKillFlags(Reg: ImplicitDef);
709 }
710
711 if (CrossMBBPhysDef) {
712 // Add physical register defs now coming in from a predecessor to MBB
713 // livein list.
714 while (!PhysDefs.empty()) {
715 auto LiveIn = PhysDefs.pop_back_val();
716 if (!MBB->isLiveIn(Reg: LiveIn.second))
717 MBB->addLiveIn(PhysReg: LiveIn.second);
718 }
719 ++NumCrossBBCSEs;
720 }
721
722 MI.eraseFromParent();
723 ++NumCSEs;
724 if (!PhysRefs.empty())
725 ++NumPhysCSEs;
726 if (Commuted)
727 ++NumCommutes;
728 Changed = true;
729 } else {
730 VNT.insert(Key: &MI, Val: CurrVN++);
731 Exps.push_back(Elt: &MI);
732 }
733 CSEPairs.clear();
734 ImplicitDefsToUpdate.clear();
735 ImplicitDefs.clear();
736 }
737
738 return Changed;
739}
740
741/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
742/// dominator tree node if its a leaf or all of its children are done. Walk
743/// up the dominator tree to destroy ancestors which are now done.
744void MachineCSEImpl::ExitScopeIfDone(
745 MachineDomTreeNode *Node,
746 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren) {
747 if (OpenChildren[Node])
748 return;
749
750 // Pop scope.
751 ExitScope(MBB: Node->getBlock());
752
753 // Now traverse upwards to pop ancestors whose offsprings are all done.
754 while (MachineDomTreeNode *Parent = Node->getIDom()) {
755 unsigned Left = --OpenChildren[Parent];
756 if (Left != 0)
757 break;
758 ExitScope(MBB: Parent->getBlock());
759 Node = Parent;
760 }
761}
762
763bool MachineCSEImpl::PerformCSE(MachineDomTreeNode *Node) {
764 SmallVector<MachineDomTreeNode*, 32> Scopes;
765 SmallVector<MachineDomTreeNode*, 8> WorkList;
766 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
767
768 CurrVN = 0;
769
770 // Perform a DFS walk to determine the order of visit.
771 WorkList.push_back(Elt: Node);
772 do {
773 Node = WorkList.pop_back_val();
774 Scopes.push_back(Elt: Node);
775 size_t WorkListSize = WorkList.size();
776 append_range(C&: WorkList, R: Node->children());
777 OpenChildren[Node] = WorkList.size() - WorkListSize; // Number of children.
778 } while (!WorkList.empty());
779
780 // Now perform CSE.
781 bool Changed = false;
782 for (MachineDomTreeNode *Node : Scopes) {
783 MachineBasicBlock *MBB = Node->getBlock();
784 EnterScope(MBB);
785 Changed |= ProcessBlockCSE(MBB);
786 // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
787 ExitScopeIfDone(Node, OpenChildren);
788 }
789
790 return Changed;
791}
792
793// We use stronger checks for PRE candidate rather than for CSE ones to embrace
794// checks inside ProcessBlockCSE(), not only inside isCSECandidate(). This helps
795// to exclude instrs created by PRE that won't be CSEed later.
796bool MachineCSEImpl::isPRECandidate(MachineInstr *MI,
797 SmallSet<MCRegister, 8> &PhysRefs) {
798 if (!isCSECandidate(MI) ||
799 MI->isNotDuplicable() ||
800 MI->mayLoad() ||
801 TII->isAsCheapAsAMove(MI: *MI) ||
802 MI->getNumDefs() != 1 ||
803 MI->getNumExplicitDefs() != 1)
804 return false;
805
806 for (const MachineOperand &MO : MI->operands()) {
807 if (MO.isReg() && !MO.getReg().isVirtual()) {
808 if (MO.isDef())
809 return false;
810 else
811 PhysRefs.insert(V: MO.getReg());
812 }
813 }
814
815 return true;
816}
817
818bool MachineCSEImpl::ProcessBlockPRE(MachineDominatorTree *DT,
819 MachineBasicBlock *MBB) {
820 bool Changed = false;
821 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: *MBB)) {
822 SmallSet<MCRegister, 8> PhysRefs;
823 if (!isPRECandidate(MI: &MI, PhysRefs))
824 continue;
825
826 auto [It, Inserted] = PREMap.try_emplace(Key: &MI, Args&: MBB);
827 if (Inserted)
828 continue;
829
830 auto *MBB1 = It->second;
831 assert(
832 !DT->properlyDominates(MBB, MBB1) &&
833 "MBB cannot properly dominate MBB1 while DFS through dominators tree!");
834 auto CMBB = DT->findNearestCommonDominator(A: MBB, B: MBB1);
835 if (!CMBB->isLegalToHoistInto())
836 continue;
837
838 if (!isProfitableToHoistInto(CandidateBB: CMBB, MBB, MBB1))
839 continue;
840
841 // Two instrs are partial redundant if their basic blocks are reachable
842 // from one to another but one doesn't dominate another.
843 if (CMBB != MBB1) {
844 auto BB = MBB->getBasicBlock(), BB1 = MBB1->getBasicBlock();
845 if (BB != nullptr && BB1 != nullptr &&
846 (isPotentiallyReachable(From: BB1, To: BB) ||
847 isPotentiallyReachable(From: BB, To: BB1))) {
848 // The following check extends the definition of `isConvergent` to
849 // assume a convergent instruction is dependent not only on additional
850 // conditions, but also on fewer conditions. LLVM does not have a
851 // MachineInstr attribute which expresses this extended definition, so
852 // it's necessary to use `isConvergent` to prevent illegally PRE-ing the
853 // subset of `isConvergent` instructions which do fall into this
854 // extended definition.
855 if (MI.isConvergent() && CMBB != MBB)
856 continue;
857
858 // If this instruction uses physical registers then we can only do PRE
859 // if it's using the value that is live at the place we're hoisting to.
860 bool NonLocal;
861 PhysDefVector PhysDefs;
862 if (!PhysRefs.empty() &&
863 !PhysRegDefsReach(CSMI: &*(CMBB->getFirstTerminator()), MI: &MI, PhysRefs,
864 PhysDefs, NonLocal))
865 continue;
866
867 assert(MI.getOperand(0).isDef() &&
868 "First operand of instr with one explicit def must be this def");
869 Register VReg = MI.getOperand(i: 0).getReg();
870 Register NewReg = MRI->cloneVirtualRegister(VReg);
871 if (!isProfitableToCSE(CSReg: NewReg, Reg: VReg, CSBB: CMBB, MI: &MI))
872 continue;
873 MachineInstr &NewMI =
874 TII->duplicate(MBB&: *CMBB, InsertBefore: CMBB->getFirstTerminator(), Orig: MI);
875
876 // When hoisting, make sure we don't carry the debug location of
877 // the original instruction, as that's not correct and can cause
878 // unexpected jumps when debugging optimized code.
879 auto EmptyDL = DebugLoc();
880 NewMI.setDebugLoc(EmptyDL);
881
882 NewMI.getOperand(i: 0).setReg(NewReg);
883
884 PREMap[&MI] = CMBB;
885 ++NumPREs;
886 Changed = true;
887 }
888 }
889 }
890 return Changed;
891}
892
893// This simple PRE (partial redundancy elimination) pass doesn't actually
894// eliminate partial redundancy but transforms it to full redundancy,
895// anticipating that the next CSE step will eliminate this created redundancy.
896// If CSE doesn't eliminate this, than created instruction will remain dead
897// and eliminated later by Remove Dead Machine Instructions pass.
898bool MachineCSEImpl::PerformSimplePRE(MachineDominatorTree *DT) {
899 SmallVector<MachineDomTreeNode *, 32> BBs;
900
901 PREMap.clear();
902 bool Changed = false;
903 BBs.push_back(Elt: DT->getRootNode());
904 do {
905 auto Node = BBs.pop_back_val();
906 append_range(C&: BBs, R: Node->children());
907
908 MachineBasicBlock *MBB = Node->getBlock();
909 Changed |= ProcessBlockPRE(DT, MBB);
910
911 } while (!BBs.empty());
912
913 return Changed;
914}
915
916bool MachineCSEImpl::isProfitableToHoistInto(MachineBasicBlock *CandidateBB,
917 MachineBasicBlock *MBB,
918 MachineBasicBlock *MBB1) {
919 if (CandidateBB->getParent()->getFunction().hasMinSize())
920 return true;
921 assert(DT->dominates(CandidateBB, MBB) && "CandidateBB should dominate MBB");
922 assert(DT->dominates(CandidateBB, MBB1) &&
923 "CandidateBB should dominate MBB1");
924 return MBFI->getBlockFreq(MBB: CandidateBB) <=
925 MBFI->getBlockFreq(MBB) + MBFI->getBlockFreq(MBB: MBB1);
926}
927
928void MachineCSEImpl::releaseMemory() {
929 ScopeMap.clear();
930 PREMap.clear();
931 Exps.clear();
932}
933
934bool MachineCSEImpl::run(MachineFunction &MF) {
935 TII = MF.getSubtarget().getInstrInfo();
936 TRI = MF.getSubtarget().getRegisterInfo();
937 MRI = &MF.getRegInfo();
938 LookAheadLimit = TII->getMachineCSELookAheadLimit();
939 bool ChangedPRE, ChangedCSE;
940 ChangedPRE = PerformSimplePRE(DT);
941 ChangedCSE = PerformCSE(Node: DT->getRootNode());
942 releaseMemory();
943 return ChangedPRE || ChangedCSE;
944}
945
946PreservedAnalyses MachineCSEPass::run(MachineFunction &MF,
947 MachineFunctionAnalysisManager &MFAM) {
948 MFPropsModifier _(*this, MF);
949
950 MachineDominatorTree &MDT = MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
951 MachineBlockFrequencyInfo &MBFI =
952 MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF);
953 MachineCSEImpl Impl(&MDT, &MBFI);
954 bool Changed = Impl.run(MF);
955 if (!Changed)
956 return PreservedAnalyses::all();
957
958 auto PA = getMachineFunctionPassPreservedAnalyses();
959 PA.preserveSet<CFGAnalyses>();
960 return PA;
961}
962
963bool MachineCSELegacy::runOnMachineFunction(MachineFunction &MF) {
964 if (skipFunction(F: MF.getFunction()))
965 return false;
966
967 MachineDominatorTree &MDT =
968 getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
969 MachineBlockFrequencyInfo &MBFI =
970 getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
971 MachineCSEImpl Impl(&MDT, &MBFI);
972 return Impl.run(MF);
973}
974