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> DisableInlineAsm(
45 "loongarch-disable-inline-asm-barrier-opt",
46 cl::desc("Disable optimization of memory barriers in InlineAsm"),
47 cl::init(Val: false), cl::Hidden);
48
49static cl::opt<bool> ReplaceEliminatedMBToNop(
50 "loongarch-replace-eliminated-dbar-to-nop",
51 cl::desc("Replace eliminated DBARs with NOPs to preserve code layout"),
52 cl::init(Val: false), cl::Hidden);
53
54namespace {
55
56#define AMO_CASES \
57 CASE(AMSWAP, B) \
58 CASE(AMSWAP, H) \
59 CASE(AMSWAP, W) \
60 CASE(AMSWAP, D) \
61 CASE(AMADD, B) \
62 CASE(AMADD, H) \
63 CASE(AMADD, W) \
64 CASE(AMADD, D) \
65 CASE(AMAND, W) \
66 CASE(AMAND, D) \
67 CASE(AMOR, W) \
68 CASE(AMOR, D) \
69 CASE(AMXOR, W) \
70 CASE(AMXOR, D) \
71 CASE(AMMAX, W) \
72 CASE(AMMAX, D) \
73 CASE(AMMAX, WU) \
74 CASE(AMMAX, DU) \
75 CASE(AMMIN, W) \
76 CASE(AMMIN, D) \
77 CASE(AMMIN, WU) \
78 CASE(AMMIN, DU) \
79 CASE(AMCAS, B) \
80 CASE(AMCAS, H) \
81 CASE(AMCAS, W) \
82 CASE(AMCAS, D)
83
84static std::optional<std::pair<StringRef, StringRef>> parseMB(StringRef Asm) {
85 auto T1 = llvm::getToken(Source: Asm);
86 if (!T1.first.equals_insensitive(RHS: "dbar"))
87 return std::nullopt;
88 auto T2 = llvm::getToken(Source: T1.second);
89 if (T2.first.empty())
90 return std::nullopt;
91 auto T3 = llvm::getToken(Source: T2.second);
92 if (T3.first.trim().empty() || T3.first.starts_with(Prefix: '#'))
93 return std::pair(T1.first, T2.first);
94 return std::nullopt;
95}
96
97static std::optional<std::pair<StringRef, StringRef>>
98isAsmMB(const MachineInstr &MI) {
99 if (DisableInlineAsm)
100 return std::nullopt;
101 if (!MI.isInlineAsm())
102 return std::nullopt;
103 auto Asm = MI.getOperand(i: InlineAsm::MIOp_AsmString).getSymbolName();
104 return parseMB(Asm);
105}
106
107static StringRef getAMDB(StringRef Name) {
108#define CASE(Name, Suffix) \
109 .Case(#Name "." #Suffix, MergeAMOWithMB ? #Name "_DB." #Suffix : "") \
110 .Case(#Name "_DB." #Suffix, #Name "_DB." #Suffix)
111 return StringSwitch<StringRef>(Name.upper()) AMO_CASES.Default(Value: {});
112#undef CASE
113}
114
115static std::optional<std::pair<StringRef, StringRef>> parseAM(StringRef Asm) {
116 auto T1 = llvm::getToken(Source: Asm);
117 auto OpName = getAMDB(Name: T1.first);
118 if (OpName.empty())
119 return std::nullopt;
120 auto T2 = llvm::getToken(Source: T1.second, Delimiters: ",");
121 if (T2.first.empty())
122 return std::nullopt;
123 auto T3 = llvm::getToken(Source: T2.second, Delimiters: ",");
124 if (T3.first.empty())
125 return std::nullopt;
126 auto T4 = llvm::getToken(Source: T3.second, Delimiters: ",");
127 if (T4.first.empty())
128 return std::nullopt;
129 auto T5 = llvm::getToken(Source: T4.second);
130 if (T5.first.trim().empty() || T5.first.starts_with(Prefix: '#')) {
131 StringRef Operands(T2.first.data(),
132 T4.first.data() + T4.first.size() - T2.first.data());
133 return std::pair(OpName, Operands);
134 }
135 return std::nullopt;
136}
137
138static std::optional<std::pair<StringRef, StringRef>>
139isAsmAM(const MachineInstr &MI) {
140 if (DisableInlineAsm)
141 return std::nullopt;
142 if (!MI.isInlineAsm())
143 return std::nullopt;
144 auto Asm = MI.getOperand(i: InlineAsm::MIOp_AsmString).getSymbolName();
145 return parseAM(Asm);
146}
147
148static bool isMB(const MachineInstr &MI) {
149 return MI.getOpcode() == LoongArch::DBAR;
150}
151
152static bool isLL(const MachineInstr &MI) {
153 switch (MI.getOpcode()) {
154 case LoongArch::LL_W:
155 case LoongArch::LL_D:
156 return true;
157 default:
158 return false;
159 }
160}
161
162static bool isSC(const MachineInstr &MI) {
163 switch (MI.getOpcode()) {
164 case LoongArch::SC_W:
165 case LoongArch::SC_D:
166 case LoongArch::SC_Q:
167 return true;
168 default:
169 return false;
170 }
171}
172
173static std::optional<unsigned> isAM(const MachineInstr &MI) {
174#define CASE(Name, Suffix) \
175 case LoongArch::Name##_##Suffix: \
176 if (!MergeAMOWithMB) \
177 return std::nullopt; \
178 [[fallthrough]]; \
179 case LoongArch::Name##__DB_##Suffix: \
180 return LoongArch::Name##__DB_##Suffix;
181 switch (MI.getOpcode()) {
182 AMO_CASES
183 default:
184 return std::nullopt;
185 }
186#undef CASE
187}
188
189static bool isSafeToSkip(const MachineInstr &MI) {
190 if (MI.mayLoadOrStore())
191 return false;
192 if (MI.isCall() || MI.isReturn())
193 return false;
194 if (MI.isInlineAsm())
195 return isAsmMB(MI) != std::nullopt;
196 if (MI.hasUnmodeledSideEffects())
197 return isMB(MI);
198 return true;
199}
200
201struct BarrierHint {
202 BarrierHint(unsigned Hint) : Hint(Hint) {}
203
204 bool subsumes(const BarrierHint &O) const { return (Hint & O.Hint) == Hint; }
205
206 BarrierHint merge(const BarrierHint &O) const {
207 return BarrierHint(Hint & O.Hint);
208 }
209
210 static inline bool isValid(unsigned Hint) { return (Hint & ~0x1f) == 0; }
211
212 unsigned Hint;
213};
214
215struct InstBarrier {
216 InstBarrier(MachineInstr &MI)
217 : MI(&MI), Pre(0), Post(0), Data(0), IsMB(false), IsAM(false),
218 IsAsm(false) {
219 if (isMB(MI)) {
220 unsigned Hint = MI.getOperand(i: 0).getImm();
221 if (!BarrierHint::isValid(Hint))
222 return;
223 IsMB = true;
224 Pre = Post = BarrierHint(Hint);
225 } else if (isLL(MI)) {
226 IsAM = true;
227 Pre = BarrierHint(0b10000);
228 Post = BarrierHint(0b11111);
229 } else if (isSC(MI)) {
230 IsAM = true;
231 Pre = BarrierHint(0b11111);
232 Post = BarrierHint(0b10000);
233 } else if (auto R = isAM(MI)) {
234 IsAM = true;
235 OpcAMDB = *R;
236 Pre = Post = BarrierHint(0b10000);
237 } else if (auto R = isAsmMB(MI)) {
238 OpName = (*R).first;
239 Operands = (*R).second;
240 auto B = parseAsmMB(Operand: Operands, MI);
241 if (!B || !BarrierHint::isValid(Hint: (*B).first))
242 return;
243 IsMB = true;
244 IsAsm = true;
245 HintOff = (*B).second;
246 Pre = Post = BarrierHint((*B).first);
247 } else if (auto R = isAsmAM(MI)) {
248 OpName = (*R).first;
249 Operands = (*R).second;
250 IsAM = true;
251 IsAsm = true;
252 Pre = Post = BarrierHint(0b10000);
253 }
254 }
255
256 static std::optional<std::pair<unsigned, unsigned>>
257 parseAsmMB(StringRef Operand, MachineInstr &MI) {
258 unsigned Hint, HintOff = 0;
259 // DBAR N | 0xN
260 if (!Operand.starts_with(Prefix: '$')) {
261 if (Operand.getAsInteger(Radix: 0, Result&: Hint))
262 return std::nullopt;
263 return std::pair(Hint, HintOff);
264 }
265 // DBAR $N
266 unsigned N = 0, Off, AsmDescOp;
267 if (Operand.drop_front().getAsInteger(Radix: 0, Result&: Off))
268 return std::nullopt;
269 AsmDescOp = InlineAsm::MIOp_FirstOperand;
270 while (AsmDescOp != MI.getNumOperands()) {
271 const MachineOperand &MO = MI.getOperand(i: AsmDescOp);
272 assert(MO.isImm() && "Unexpected operand type!");
273 const InlineAsm::Flag F(MO.getImm());
274 if (N == Off) {
275 if (!F.isImmKind())
276 return std::nullopt;
277 HintOff = AsmDescOp + 1;
278 Hint = MI.getOperand(i: HintOff).getImm();
279 return std::pair(Hint, HintOff);
280 }
281 AsmDescOp += 1 + F.getNumOperandRegisters();
282 ++N;
283 }
284 return std::nullopt;
285 }
286
287 MachineInstr *MI;
288 BarrierHint Pre;
289 BarrierHint Post;
290 StringRef OpName;
291 StringRef Operands;
292 union {
293 unsigned OpcAMDB;
294 unsigned HintOff;
295 unsigned Data;
296 };
297 bool IsMB;
298 bool IsAM;
299 bool IsAsm;
300};
301
302class LoongArchMemoryBarrierOpt : public MachineFunctionPass {
303public:
304 static char ID;
305
306 LoongArchMemoryBarrierOpt() : MachineFunctionPass(ID) {}
307
308 StringRef getPassName() const override {
309 return LOONGARCH_MEMORY_BARRIER_OPT_NAME;
310 }
311
312 void getAnalysisUsage(AnalysisUsage &AU) const override {
313 AU.addRequired<MachineDominatorTreeWrapperPass>();
314 AU.addPreserved<MachineDominatorTreeWrapperPass>();
315 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
316 AU.addPreserved<MachinePostDominatorTreeWrapperPass>();
317 MachineFunctionPass::getAnalysisUsage(AU);
318 }
319
320 bool runOnMachineFunction(MachineFunction &Fn) override;
321
322private:
323 enum : unsigned {
324 CandidateA = 1u << 0,
325 CandidateB = 1u << 1,
326 };
327
328 unsigned resolveBarrierRedundancy(const MachineInstr *A,
329 const MachineInstr *B) const;
330 bool eliminateRedundantBarrier(InstBarrier &IA, InstBarrier &IB) const;
331
332 MachineFunction *MF;
333 const MachineDominatorTree *MDT;
334 const MachinePostDominatorTree *MPDT;
335};
336
337static bool checkAllPathSafe(const MachineBasicBlock *MBBA,
338 const MachineBasicBlock *MBBB, bool IsAToB) {
339 const MachineBasicBlock *Start = IsAToB ? MBBA : MBBB;
340 const MachineBasicBlock *End = IsAToB ? MBBB : MBBA;
341
342 SmallVector<const MachineBasicBlock *, 16> Worklist;
343 DenseSet<const MachineBasicBlock *> Visited;
344
345 Worklist.push_back(Elt: Start);
346 Visited.insert(V: Start);
347
348 while (!Worklist.empty()) {
349 const MachineBasicBlock *BB = Worklist.pop_back_val();
350
351 if (BB == End)
352 continue;
353
354 if (BB != Start) {
355 for (const MachineInstr &MI : *BB) {
356 if (!isSafeToSkip(MI))
357 return false;
358 }
359 }
360
361 if (IsAToB) {
362 for (const MachineBasicBlock *Succ : BB->successors()) {
363 if (Visited.insert(V: Succ).second)
364 Worklist.push_back(Elt: Succ);
365 }
366 } else {
367 for (const MachineBasicBlock *Pred : BB->predecessors()) {
368 if (Visited.insert(V: Pred).second)
369 Worklist.push_back(Elt: Pred);
370 }
371 }
372 }
373
374 return true;
375}
376
377// Returns a bitmask indicating removal candidates: A (bit 1) and B (bit 2).
378unsigned LoongArchMemoryBarrierOpt::resolveBarrierRedundancy(
379 const MachineInstr *A, const MachineInstr *B) const {
380 const MachineBasicBlock *MBBA = A->getParent();
381 const MachineBasicBlock *MBBB = B->getParent();
382
383 if (MBBA == MBBB) {
384 /* A -> B */
385 for (auto It = std::next(x: A->getIterator()); It != MBBA->end(); ++It) {
386 if (It == B->getIterator())
387 return CandidateA | CandidateB;
388 if (!isSafeToSkip(MI: *It))
389 return 0;
390 }
391 return 0;
392 }
393
394 // Cross-block walk
395 bool ADomB = MDT->dominates(A: MBBA, B: MBBB);
396 bool BPostDomA = MPDT->dominates(A: MBBB, B: MBBA);
397 unsigned Mask = 0;
398 if (!ADomB && !BPostDomA)
399 return 0;
400
401 /* A -> MBBA->end() */
402 for (auto It = std::next(x: A->getIterator()); It != MBBA->end(); ++It)
403 if (!isSafeToSkip(MI: *It))
404 return 0;
405 /* B -> MBBB->begin() */
406 for (auto It = MBBB->begin(); It != B->getIterator(); ++It)
407 if (!isSafeToSkip(MI: *It))
408 return 0;
409
410 /* MBBA -> MBBB */
411 if (BPostDomA)
412 if (checkAllPathSafe(MBBA, MBBB, IsAToB: true /*IsAToB*/))
413 Mask |= CandidateA;
414
415 /* MBBB -> MBBA */
416 if (ADomB)
417 if (checkAllPathSafe(MBBA, MBBB, IsAToB: false /*IsAToB*/))
418 Mask |= CandidateB;
419
420 return Mask;
421}
422
423// Update DBAR hint
424static void updateMB(InstBarrier &I, BarrierHint Hint, MachineFunction *MF) {
425 assert(I.IsMB && "Unexpected!");
426 I.Pre = I.Post = Hint;
427 if (!I.IsAsm) {
428 I.MI->getOperand(i: 0).setImm(Hint.Hint);
429 return;
430 }
431 if (I.HintOff) {
432 I.MI->getOperand(i: I.HintOff).setImm(Hint.Hint);
433 return;
434 }
435 MachineOperand &MO = I.MI->getOperand(i: InlineAsm::MIOp_AsmString);
436 auto New = I.OpName.str() + " " + llvm::utostr(X: Hint.Hint);
437 MO.ChangeToES(SymName: MF->createExternalSymbolName(Name: New), TargetFlags: MO.getTargetFlags());
438}
439
440// Replace AMO to AMO_DB
441static void replaceAM(InstBarrier &I, MachineFunction *MF) {
442 if (!I.IsAM)
443 return;
444 if (I.OpcAMDB) {
445 auto &ST = MF->getSubtarget<LoongArchSubtarget>();
446 I.MI->setDesc(ST.getInstrInfo()->get(Opcode: I.OpcAMDB));
447 return;
448 }
449 if (!I.IsAsm)
450 return;
451 MachineOperand &MO = I.MI->getOperand(i: InlineAsm::MIOp_AsmString);
452 auto New = I.OpName.str() + " " + I.Operands.str();
453 MO.ChangeToES(SymName: MF->createExternalSymbolName(Name: New), TargetFlags: MO.getTargetFlags());
454}
455
456bool LoongArchMemoryBarrierOpt::eliminateRedundantBarrier(
457 InstBarrier &IA, InstBarrier &IB) const {
458 MachineInstr *A = IA.MI;
459 MachineInstr *B = IB.MI;
460
461 if (!A || !B)
462 return false; // Already erased
463 if (A == B)
464 return false;
465
466 unsigned Mask = resolveBarrierRedundancy(A, B);
467 if (!Mask)
468 return false;
469
470 auto eraseOrReplaceWithNop = [&](MachineInstr *MI) {
471 if (ReplaceEliminatedMBToNop) {
472 auto &ST = MF->getSubtarget<LoongArchSubtarget>();
473 BuildMI(BB&: *MI->getParent(), I: MI->getIterator(), MIMD: MI->getDebugLoc(),
474 MCID: ST.getInstrInfo()->get(Opcode: LoongArch::ANDI), DestReg: LoongArch::R0)
475 .addReg(RegNo: LoongArch::R0)
476 .addImm(Val: 0);
477 }
478 MI->eraseFromParent();
479 };
480
481 // A B
482 // DBAR x + DBAR y -> DBAR (x & y)
483 // DBAR x + AMO_DB -> AMO_DB
484 // DBAR x + AMO -> AMO_DB
485 // DBAR x + LL -> LL
486 if ((Mask & CandidateA) && IA.IsMB) {
487 if (!IB.Pre.subsumes(O: IA.Post)) {
488 if (!IB.IsMB || (RequireNoPathBypass && !(Mask & CandidateB)))
489 return false;
490 updateMB(I&: IB, Hint: IB.Pre.merge(O: IA.Post), MF);
491 }
492 replaceAM(I&: IB, MF);
493 eraseOrReplaceWithNop(A);
494 IA.MI = nullptr;
495 return true;
496 }
497
498 // A B
499 // DBAR x + DBAR y -> DBAR (x & y)
500 // AMO_DB + DBAR x -> AMO_DB
501 // AMO + DBAR x -> AMO_DB
502 // SC + DBAR x -> SC
503 if ((Mask & CandidateB) && IB.IsMB) {
504 if (!IA.Post.subsumes(O: IB.Pre)) {
505 if (!IA.IsMB || (RequireNoPathBypass && !(Mask & CandidateA)))
506 return false;
507 updateMB(I&: IA, Hint: IA.Post.merge(O: IB.Pre), MF);
508 }
509 replaceAM(I&: IA, MF);
510 eraseOrReplaceWithNop(B);
511 IB.MI = nullptr;
512 return true;
513 }
514
515 return false;
516}
517
518bool LoongArchMemoryBarrierOpt::runOnMachineFunction(MachineFunction &Fn) {
519 if (skipFunction(F: Fn.getFunction()))
520 return false;
521
522 MF = &Fn;
523 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
524 MPDT = &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
525
526 SmallVector<InstBarrier, 32> Sites;
527 bool Changed = false;
528
529 for (MachineBasicBlock &MBB : Fn)
530 for (MachineInstr &MI : MBB) {
531 InstBarrier IB(MI);
532 if (IB.IsMB || IB.IsAM)
533 Sites.push_back(Elt: IB);
534 }
535
536 for (size_t a = 0; a < Sites.size(); ++a) {
537 for (size_t b = a + 1; b < Sites.size(); ++b) {
538 InstBarrier &IA = Sites[a];
539 InstBarrier &IB = Sites[b];
540 Changed |= eliminateRedundantBarrier(IA, IB);
541 Changed |= eliminateRedundantBarrier(IA&: IB, IB&: IA);
542 }
543 }
544
545 return Changed;
546}
547} // namespace
548
549char LoongArchMemoryBarrierOpt::ID = 0;
550INITIALIZE_PASS_BEGIN(LoongArchMemoryBarrierOpt, DEBUG_TYPE,
551 LOONGARCH_MEMORY_BARRIER_OPT_NAME, false, false)
552INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
553INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
554INITIALIZE_PASS_END(LoongArchMemoryBarrierOpt, DEBUG_TYPE,
555 LOONGARCH_MEMORY_BARRIER_OPT_NAME, false, false)
556
557FunctionPass *llvm::createLoongArchMemoryBarrierOptPass() {
558 return new LoongArchMemoryBarrierOpt();
559}
560