1//===---- LoongArchMemoryBarrierOpt.cpp - Memory barrier Optimization -----===//
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 removes or merges redundant memory barrier instructions.
10///
11/// - DBAR x + DBAR y -> DBAR (x & y)
12/// - DBAR x + AMO_DB -> AMO_DB
13/// - DBAR x + AMO -> AMO_DB
14/// - DBAR x + LL -> LL
15/// - AMO_DB + DBAR x -> AMO_DB
16/// - AMO + DBAR x -> AMO_DB
17/// - SC + DBAR x -> SC
18///
19//===----------------------------------------------------------------------===//
20
21#include "LoongArch.h"
22#include "LoongArchInstrInfo.h"
23#include "LoongArchSubtarget.h"
24#include "llvm/CodeGen/MachineDominators.h"
25#include "llvm/CodeGen/MachinePostDominators.h"
26#include "llvm/InitializePasses.h"
27
28using namespace llvm;
29
30#define DEBUG_TYPE "loongarch-memory-barrier-opt"
31#define LOONGARCH_MEMORY_BARRIER_OPT_NAME \
32 "LoongArch Memory Barrier Optimisation pass"
33
34static cl::opt<bool> RequireNoPathBypass(
35 "loongarch-require-no-path-bypass",
36 cl::desc("Optimize only when no paths bypass either memory barrier"),
37 cl::init(Val: true), cl::Hidden);
38
39static cl::opt<bool> MergeAMOWithMB(
40 "loongarch-merge-amo-with-dbar",
41 cl::desc("Merge AMOs with DBARs into AMO_DB during optimization"),
42 cl::init(Val: true), cl::Hidden);
43
44static cl::opt<bool> ReplaceEliminatedMBToNop(
45 "loongarch-replace-eliminated-dbar-to-nop",
46 cl::desc("Replace eliminated DBARs with NOPs to preserve code layout"),
47 cl::init(Val: false), cl::Hidden);
48
49namespace {
50
51#define AMO_CASES \
52 CASE(AMSWAP, B) \
53 CASE(AMSWAP, H) \
54 CASE(AMSWAP, W) \
55 CASE(AMSWAP, D) \
56 CASE(AMADD, B) \
57 CASE(AMADD, H) \
58 CASE(AMADD, W) \
59 CASE(AMADD, D) \
60 CASE(AMAND, W) \
61 CASE(AMAND, D) \
62 CASE(AMOR, W) \
63 CASE(AMOR, D) \
64 CASE(AMXOR, W) \
65 CASE(AMXOR, D) \
66 CASE(AMMAX, W) \
67 CASE(AMMAX, D) \
68 CASE(AMMAX, WU) \
69 CASE(AMMAX, DU) \
70 CASE(AMMIN, W) \
71 CASE(AMMIN, D) \
72 CASE(AMMIN, WU) \
73 CASE(AMMIN, DU) \
74 CASE(AMCAS, B) \
75 CASE(AMCAS, H) \
76 CASE(AMCAS, W) \
77 CASE(AMCAS, D)
78
79static bool isMB(const MachineInstr &MI) {
80 return MI.getOpcode() == LoongArch::DBAR;
81}
82
83static bool isLL(const MachineInstr &MI) {
84 switch (MI.getOpcode()) {
85 case LoongArch::LL_W:
86 case LoongArch::LL_D:
87 return true;
88 default:
89 return false;
90 }
91}
92
93static bool isSC(const MachineInstr &MI) {
94 switch (MI.getOpcode()) {
95 case LoongArch::SC_W:
96 case LoongArch::SC_D:
97 case LoongArch::SC_Q:
98 return true;
99 default:
100 return false;
101 }
102}
103
104static std::optional<unsigned> isAM(const MachineInstr &MI) {
105#define CASE(Name, Suffix) \
106 case LoongArch::Name##_##Suffix: \
107 if (!MergeAMOWithMB) \
108 return std::nullopt; \
109 [[fallthrough]]; \
110 case LoongArch::Name##__DB_##Suffix: \
111 return LoongArch::Name##__DB_##Suffix;
112 switch (MI.getOpcode()) {
113 AMO_CASES
114 default:
115 return std::nullopt;
116 }
117#undef CASE
118}
119
120static bool isSafeToSkip(const MachineInstr &MI) {
121 if (MI.mayLoadOrStore())
122 return false;
123 if (MI.isCall() || MI.isReturn())
124 return false;
125 if (MI.isInlineAsm())
126 return false;
127 if (MI.hasUnmodeledSideEffects())
128 return isMB(MI);
129 return true;
130}
131
132struct BarrierHint {
133 BarrierHint(unsigned Hint) : Hint(Hint) {}
134
135 bool subsumes(const BarrierHint &O) const { return (Hint & O.Hint) == Hint; }
136
137 BarrierHint merge(const BarrierHint &O) const {
138 return BarrierHint(Hint & O.Hint);
139 }
140
141 static inline bool isValid(unsigned Hint) { return (Hint & ~0x1f) == 0; }
142
143 unsigned Hint;
144};
145
146struct InstBarrier {
147 InstBarrier(MachineInstr &MI)
148 : MI(&MI), Pre(0), Post(0), OpcAMDB(0), IsMB(false), IsAM(false) {
149 if (isMB(MI)) {
150 unsigned Hint = MI.getOperand(i: 0).getImm();
151 if (!BarrierHint::isValid(Hint))
152 return;
153 IsMB = true;
154 Pre = Post = BarrierHint(Hint);
155 } else if (isLL(MI)) {
156 IsAM = true;
157 Pre = BarrierHint(0b10000);
158 Post = BarrierHint(0b11111);
159 } else if (isSC(MI)) {
160 IsAM = true;
161 Pre = BarrierHint(0b11111);
162 Post = BarrierHint(0b10000);
163 } else if (auto R = isAM(MI)) {
164 IsAM = true;
165 OpcAMDB = *R;
166 Pre = Post = BarrierHint(0b10000);
167 }
168 }
169
170 MachineInstr *MI;
171 BarrierHint Pre;
172 BarrierHint Post;
173 StringRef OpName;
174 StringRef Operands;
175 unsigned OpcAMDB;
176 bool IsMB;
177 bool IsAM;
178};
179
180class LoongArchMemoryBarrierOpt : public MachineFunctionPass {
181public:
182 static char ID;
183
184 LoongArchMemoryBarrierOpt() : MachineFunctionPass(ID) {}
185
186 StringRef getPassName() const override {
187 return LOONGARCH_MEMORY_BARRIER_OPT_NAME;
188 }
189
190 void getAnalysisUsage(AnalysisUsage &AU) const override {
191 AU.addRequired<MachineDominatorTreeWrapperPass>();
192 AU.addPreserved<MachineDominatorTreeWrapperPass>();
193 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
194 AU.addPreserved<MachinePostDominatorTreeWrapperPass>();
195 MachineFunctionPass::getAnalysisUsage(AU);
196 }
197
198 bool runOnMachineFunction(MachineFunction &Fn) override;
199
200private:
201 enum : unsigned {
202 CandidateA = 1u << 0,
203 CandidateB = 1u << 1,
204 };
205
206 unsigned resolveBarrierRedundancy(const MachineInstr *A,
207 const MachineInstr *B) const;
208 bool eliminateRedundantBarrier(InstBarrier &IA, InstBarrier &IB) const;
209
210 MachineFunction *MF;
211 const MachineDominatorTree *MDT;
212 const MachinePostDominatorTree *MPDT;
213};
214
215static bool checkAllPathSafe(const MachineBasicBlock *MBBA,
216 const MachineBasicBlock *MBBB, bool IsAToB) {
217 const MachineBasicBlock *Start = IsAToB ? MBBA : MBBB;
218 const MachineBasicBlock *End = IsAToB ? MBBB : MBBA;
219
220 SmallVector<const MachineBasicBlock *, 16> Worklist;
221 DenseSet<const MachineBasicBlock *> Visited;
222
223 Worklist.push_back(Elt: Start);
224 Visited.insert(V: Start);
225
226 while (!Worklist.empty()) {
227 const MachineBasicBlock *BB = Worklist.pop_back_val();
228
229 if (BB == End)
230 continue;
231
232 if (BB != Start) {
233 for (const MachineInstr &MI : *BB) {
234 if (!isSafeToSkip(MI))
235 return false;
236 }
237 }
238
239 if (IsAToB) {
240 for (const MachineBasicBlock *Succ : BB->successors()) {
241 if (Visited.insert(V: Succ).second)
242 Worklist.push_back(Elt: Succ);
243 }
244 } else {
245 for (const MachineBasicBlock *Pred : BB->predecessors()) {
246 if (Visited.insert(V: Pred).second)
247 Worklist.push_back(Elt: Pred);
248 }
249 }
250 }
251
252 return true;
253}
254
255// Returns a bitmask indicating removal candidates: A (bit 1) and B (bit 2).
256unsigned LoongArchMemoryBarrierOpt::resolveBarrierRedundancy(
257 const MachineInstr *A, const MachineInstr *B) const {
258 const MachineBasicBlock *MBBA = A->getParent();
259 const MachineBasicBlock *MBBB = B->getParent();
260
261 if (MBBA == MBBB) {
262 /* A -> B */
263 for (auto It = std::next(x: A->getIterator()); It != MBBA->end(); ++It) {
264 if (It == B->getIterator())
265 return CandidateA | CandidateB;
266 if (!isSafeToSkip(MI: *It))
267 return 0;
268 }
269 return 0;
270 }
271
272 // Cross-block walk
273 bool ADomB = MDT->dominates(A: MBBA, B: MBBB);
274 bool BPostDomA = MPDT->dominates(A: MBBB, B: MBBA);
275 unsigned Mask = 0;
276 if (!ADomB && !BPostDomA)
277 return 0;
278
279 /* A -> MBBA->end() */
280 for (auto It = std::next(x: A->getIterator()); It != MBBA->end(); ++It)
281 if (!isSafeToSkip(MI: *It))
282 return 0;
283 /* B -> MBBB->begin() */
284 for (auto It = MBBB->begin(); It != B->getIterator(); ++It)
285 if (!isSafeToSkip(MI: *It))
286 return 0;
287
288 /* MBBA -> MBBB */
289 if (BPostDomA)
290 if (checkAllPathSafe(MBBA, MBBB, IsAToB: true /*IsAToB*/))
291 Mask |= CandidateA;
292
293 /* MBBB -> MBBA */
294 if (ADomB)
295 if (checkAllPathSafe(MBBA, MBBB, IsAToB: false /*IsAToB*/))
296 Mask |= CandidateB;
297
298 return Mask;
299}
300
301// Update DBAR hint
302static void updateMB(InstBarrier &I, BarrierHint Hint, MachineFunction *MF) {
303 assert(I.IsMB && "Unexpected!");
304 I.Pre = I.Post = Hint;
305 I.MI->getOperand(i: 0).setImm(Hint.Hint);
306}
307
308// Replace AMO to AMO_DB
309static void replaceAM(InstBarrier &I, MachineFunction *MF) {
310 if (!I.IsAM)
311 return;
312 if (I.OpcAMDB) {
313 auto &ST = MF->getSubtarget<LoongArchSubtarget>();
314 I.MI->setDesc(ST.getInstrInfo()->get(Opcode: I.OpcAMDB));
315 }
316}
317
318bool LoongArchMemoryBarrierOpt::eliminateRedundantBarrier(
319 InstBarrier &IA, InstBarrier &IB) const {
320 MachineInstr *A = IA.MI;
321 MachineInstr *B = IB.MI;
322
323 if (!A || !B)
324 return false; // Already erased
325 if (A == B)
326 return false;
327
328 unsigned Mask = resolveBarrierRedundancy(A, B);
329 if (!Mask)
330 return false;
331
332 auto eraseOrReplaceWithNop = [&](MachineInstr *MI) {
333 if (ReplaceEliminatedMBToNop) {
334 auto &ST = MF->getSubtarget<LoongArchSubtarget>();
335 BuildMI(BB&: *MI->getParent(), I: MI->getIterator(), MIMD: MI->getDebugLoc(),
336 MCID: ST.getInstrInfo()->get(Opcode: LoongArch::ANDI), DestReg: LoongArch::R0)
337 .addReg(RegNo: LoongArch::R0)
338 .addImm(Val: 0);
339 }
340 MI->eraseFromParent();
341 };
342
343 // A B
344 // DBAR x + DBAR y -> DBAR (x & y)
345 // DBAR x + AMO_DB -> AMO_DB
346 // DBAR x + AMO -> AMO_DB
347 // DBAR x + LL -> LL
348 if ((Mask & CandidateA) && IA.IsMB) {
349 if (!IB.Pre.subsumes(O: IA.Post)) {
350 if (!IB.IsMB || (RequireNoPathBypass && !(Mask & CandidateB)))
351 return false;
352 updateMB(I&: IB, Hint: IB.Pre.merge(O: IA.Post), MF);
353 }
354 replaceAM(I&: IB, MF);
355 eraseOrReplaceWithNop(A);
356 IA.MI = nullptr;
357 return true;
358 }
359
360 // A B
361 // DBAR x + DBAR y -> DBAR (x & y)
362 // AMO_DB + DBAR x -> AMO_DB
363 // AMO + DBAR x -> AMO_DB
364 // SC + DBAR x -> SC
365 if ((Mask & CandidateB) && IB.IsMB) {
366 if (!IA.Post.subsumes(O: IB.Pre)) {
367 if (!IA.IsMB || (RequireNoPathBypass && !(Mask & CandidateA)))
368 return false;
369 updateMB(I&: IA, Hint: IA.Post.merge(O: IB.Pre), MF);
370 }
371 replaceAM(I&: IA, MF);
372 eraseOrReplaceWithNop(B);
373 IB.MI = nullptr;
374 return true;
375 }
376
377 return false;
378}
379
380bool LoongArchMemoryBarrierOpt::runOnMachineFunction(MachineFunction &Fn) {
381 if (skipFunction(F: Fn.getFunction()))
382 return false;
383
384 MF = &Fn;
385 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
386 MPDT = &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
387
388 SmallVector<InstBarrier, 32> Sites;
389 bool Changed = false;
390
391 for (MachineBasicBlock &MBB : Fn)
392 for (MachineInstr &MI : MBB) {
393 InstBarrier IB(MI);
394 if (IB.IsMB || IB.IsAM)
395 Sites.push_back(Elt: IB);
396 }
397
398 for (size_t a = 0; a < Sites.size(); ++a) {
399 for (size_t b = a + 1; b < Sites.size(); ++b) {
400 InstBarrier &IA = Sites[a];
401 InstBarrier &IB = Sites[b];
402 Changed |= eliminateRedundantBarrier(IA, IB);
403 Changed |= eliminateRedundantBarrier(IA&: IB, IB&: IA);
404 }
405 }
406
407 return Changed;
408}
409} // namespace
410
411char LoongArchMemoryBarrierOpt::ID = 0;
412INITIALIZE_PASS_BEGIN(LoongArchMemoryBarrierOpt, DEBUG_TYPE,
413 LOONGARCH_MEMORY_BARRIER_OPT_NAME, false, false)
414INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
415INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
416INITIALIZE_PASS_END(LoongArchMemoryBarrierOpt, DEBUG_TYPE,
417 LOONGARCH_MEMORY_BARRIER_OPT_NAME, false, false)
418
419FunctionPass *llvm::createLoongArchMemoryBarrierOptPass() {
420 return new LoongArchMemoryBarrierOpt();
421}
422