xref: /freebsd/contrib/llvm-project/llvm/lib/Target/Mips/MipsExpandPseudo.cpp (revision 5e3190f700637fcfc1a52daeaa4a031fdd2557c7)
1 //===-- MipsExpandPseudoInsts.cpp - Expand pseudo instructions ------------===//
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 file contains a pass that expands pseudo instructions into target
10 // instructions to allow proper scheduling, if-conversion, and other late
11 // optimizations. This pass should be run after register allocation but before
12 // the post-regalloc scheduling pass.
13 //
14 // This is currently only used for expanding atomic pseudos after register
15 // allocation. We do this to avoid the fast register allocator introducing
16 // spills between ll and sc. These stores cause some MIPS implementations to
17 // abort the atomic RMW sequence.
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #include "Mips.h"
22 #include "MipsInstrInfo.h"
23 #include "MipsSubtarget.h"
24 #include "llvm/CodeGen/LivePhysRegs.h"
25 #include "llvm/CodeGen/MachineFunctionPass.h"
26 #include "llvm/CodeGen/MachineInstrBuilder.h"
27 
28 using namespace llvm;
29 
30 #define DEBUG_TYPE "mips-pseudo"
31 
32 namespace {
33   class MipsExpandPseudo : public MachineFunctionPass {
34   public:
35     static char ID;
36     MipsExpandPseudo() : MachineFunctionPass(ID) {}
37 
38     const MipsInstrInfo *TII;
39     const MipsSubtarget *STI;
40 
41     bool runOnMachineFunction(MachineFunction &Fn) override;
42 
43     MachineFunctionProperties getRequiredProperties() const override {
44       return MachineFunctionProperties().set(
45           MachineFunctionProperties::Property::NoVRegs);
46     }
47 
48     StringRef getPassName() const override {
49       return "Mips pseudo instruction expansion pass";
50     }
51 
52   private:
53     bool expandAtomicCmpSwap(MachineBasicBlock &MBB,
54                              MachineBasicBlock::iterator MBBI,
55                              MachineBasicBlock::iterator &NextMBBI);
56     bool expandAtomicCmpSwapSubword(MachineBasicBlock &MBB,
57                                     MachineBasicBlock::iterator MBBI,
58                                     MachineBasicBlock::iterator &NextMBBI);
59 
60     bool expandAtomicBinOp(MachineBasicBlock &BB,
61                            MachineBasicBlock::iterator I,
62                            MachineBasicBlock::iterator &NMBBI, unsigned Size);
63     bool expandAtomicBinOpSubword(MachineBasicBlock &BB,
64                                   MachineBasicBlock::iterator I,
65                                   MachineBasicBlock::iterator &NMBBI);
66 
67     bool expandMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
68                   MachineBasicBlock::iterator &NMBB);
69     bool expandMBB(MachineBasicBlock &MBB);
70    };
71   char MipsExpandPseudo::ID = 0;
72 }
73 
74 bool MipsExpandPseudo::expandAtomicCmpSwapSubword(
75     MachineBasicBlock &BB, MachineBasicBlock::iterator I,
76     MachineBasicBlock::iterator &NMBBI) {
77 
78   MachineFunction *MF = BB.getParent();
79 
80   const bool ArePtrs64bit = STI->getABI().ArePtrs64bit();
81   DebugLoc DL = I->getDebugLoc();
82   unsigned LL, SC;
83 
84   unsigned ZERO = Mips::ZERO;
85   unsigned BNE = Mips::BNE;
86   unsigned BEQ = Mips::BEQ;
87   unsigned SEOp =
88       I->getOpcode() == Mips::ATOMIC_CMP_SWAP_I8_POSTRA ? Mips::SEB : Mips::SEH;
89 
90   if (STI->inMicroMipsMode()) {
91       LL = STI->hasMips32r6() ? Mips::LL_MMR6 : Mips::LL_MM;
92       SC = STI->hasMips32r6() ? Mips::SC_MMR6 : Mips::SC_MM;
93       BNE = STI->hasMips32r6() ? Mips::BNEC_MMR6 : Mips::BNE_MM;
94       BEQ = STI->hasMips32r6() ? Mips::BEQC_MMR6 : Mips::BEQ_MM;
95   } else {
96     LL = STI->hasMips32r6() ? (ArePtrs64bit ? Mips::LL64_R6 : Mips::LL_R6)
97                             : (ArePtrs64bit ? Mips::LL64 : Mips::LL);
98     SC = STI->hasMips32r6() ? (ArePtrs64bit ? Mips::SC64_R6 : Mips::SC_R6)
99                             : (ArePtrs64bit ? Mips::SC64 : Mips::SC);
100   }
101 
102   Register Dest = I->getOperand(0).getReg();
103   Register Ptr = I->getOperand(1).getReg();
104   Register Mask = I->getOperand(2).getReg();
105   Register ShiftCmpVal = I->getOperand(3).getReg();
106   Register Mask2 = I->getOperand(4).getReg();
107   Register ShiftNewVal = I->getOperand(5).getReg();
108   Register ShiftAmnt = I->getOperand(6).getReg();
109   Register Scratch = I->getOperand(7).getReg();
110   Register Scratch2 = I->getOperand(8).getReg();
111 
112   // insert new blocks after the current block
113   const BasicBlock *LLVM_BB = BB.getBasicBlock();
114   MachineBasicBlock *loop1MBB = MF->CreateMachineBasicBlock(LLVM_BB);
115   MachineBasicBlock *loop2MBB = MF->CreateMachineBasicBlock(LLVM_BB);
116   MachineBasicBlock *sinkMBB = MF->CreateMachineBasicBlock(LLVM_BB);
117   MachineBasicBlock *exitMBB = MF->CreateMachineBasicBlock(LLVM_BB);
118   MachineFunction::iterator It = ++BB.getIterator();
119   MF->insert(It, loop1MBB);
120   MF->insert(It, loop2MBB);
121   MF->insert(It, sinkMBB);
122   MF->insert(It, exitMBB);
123 
124   // Transfer the remainder of BB and its successor edges to exitMBB.
125   exitMBB->splice(exitMBB->begin(), &BB,
126                   std::next(MachineBasicBlock::iterator(I)), BB.end());
127   exitMBB->transferSuccessorsAndUpdatePHIs(&BB);
128 
129   //  thisMBB:
130   //    ...
131   //    fallthrough --> loop1MBB
132   BB.addSuccessor(loop1MBB, BranchProbability::getOne());
133   loop1MBB->addSuccessor(sinkMBB);
134   loop1MBB->addSuccessor(loop2MBB);
135   loop1MBB->normalizeSuccProbs();
136   loop2MBB->addSuccessor(loop1MBB);
137   loop2MBB->addSuccessor(sinkMBB);
138   loop2MBB->normalizeSuccProbs();
139   sinkMBB->addSuccessor(exitMBB, BranchProbability::getOne());
140 
141   // loop1MBB:
142   //   ll dest, 0(ptr)
143   //   and Mask', dest, Mask
144   //   bne Mask', ShiftCmpVal, exitMBB
145   BuildMI(loop1MBB, DL, TII->get(LL), Scratch).addReg(Ptr).addImm(0);
146   BuildMI(loop1MBB, DL, TII->get(Mips::AND), Scratch2)
147       .addReg(Scratch)
148       .addReg(Mask);
149   BuildMI(loop1MBB, DL, TII->get(BNE))
150     .addReg(Scratch2).addReg(ShiftCmpVal).addMBB(sinkMBB);
151 
152   // loop2MBB:
153   //   and dest, dest, mask2
154   //   or dest, dest, ShiftNewVal
155   //   sc dest, dest, 0(ptr)
156   //   beq dest, $0, loop1MBB
157   BuildMI(loop2MBB, DL, TII->get(Mips::AND), Scratch)
158       .addReg(Scratch, RegState::Kill)
159       .addReg(Mask2);
160   BuildMI(loop2MBB, DL, TII->get(Mips::OR), Scratch)
161       .addReg(Scratch, RegState::Kill)
162       .addReg(ShiftNewVal);
163   BuildMI(loop2MBB, DL, TII->get(SC), Scratch)
164       .addReg(Scratch, RegState::Kill)
165       .addReg(Ptr)
166       .addImm(0);
167   BuildMI(loop2MBB, DL, TII->get(BEQ))
168       .addReg(Scratch, RegState::Kill)
169       .addReg(ZERO)
170       .addMBB(loop1MBB);
171 
172   //  sinkMBB:
173   //    srl     srlres, Mask', shiftamt
174   //    sign_extend dest,srlres
175   BuildMI(sinkMBB, DL, TII->get(Mips::SRLV), Dest)
176       .addReg(Scratch2)
177       .addReg(ShiftAmnt);
178   if (STI->hasMips32r2()) {
179     BuildMI(sinkMBB, DL, TII->get(SEOp), Dest).addReg(Dest);
180   } else {
181     const unsigned ShiftImm =
182         I->getOpcode() == Mips::ATOMIC_CMP_SWAP_I16_POSTRA ? 16 : 24;
183     BuildMI(sinkMBB, DL, TII->get(Mips::SLL), Dest)
184         .addReg(Dest, RegState::Kill)
185         .addImm(ShiftImm);
186     BuildMI(sinkMBB, DL, TII->get(Mips::SRA), Dest)
187         .addReg(Dest, RegState::Kill)
188         .addImm(ShiftImm);
189   }
190 
191   LivePhysRegs LiveRegs;
192   computeAndAddLiveIns(LiveRegs, *loop1MBB);
193   computeAndAddLiveIns(LiveRegs, *loop2MBB);
194   computeAndAddLiveIns(LiveRegs, *sinkMBB);
195   computeAndAddLiveIns(LiveRegs, *exitMBB);
196 
197   NMBBI = BB.end();
198   I->eraseFromParent();
199   return true;
200 }
201 
202 bool MipsExpandPseudo::expandAtomicCmpSwap(MachineBasicBlock &BB,
203                                            MachineBasicBlock::iterator I,
204                                            MachineBasicBlock::iterator &NMBBI) {
205 
206   const unsigned Size =
207       I->getOpcode() == Mips::ATOMIC_CMP_SWAP_I32_POSTRA ? 4 : 8;
208   MachineFunction *MF = BB.getParent();
209 
210   const bool ArePtrs64bit = STI->getABI().ArePtrs64bit();
211   DebugLoc DL = I->getDebugLoc();
212 
213   unsigned LL, SC, ZERO, BNE, BEQ, MOVE;
214 
215   if (Size == 4) {
216     if (STI->inMicroMipsMode()) {
217       LL = STI->hasMips32r6() ? Mips::LL_MMR6 : Mips::LL_MM;
218       SC = STI->hasMips32r6() ? Mips::SC_MMR6 : Mips::SC_MM;
219       BNE = STI->hasMips32r6() ? Mips::BNEC_MMR6 : Mips::BNE_MM;
220       BEQ = STI->hasMips32r6() ? Mips::BEQC_MMR6 : Mips::BEQ_MM;
221     } else {
222       LL = STI->hasMips32r6()
223                ? (ArePtrs64bit ? Mips::LL64_R6 : Mips::LL_R6)
224                : (ArePtrs64bit ? Mips::LL64 : Mips::LL);
225       SC = STI->hasMips32r6()
226                ? (ArePtrs64bit ? Mips::SC64_R6 : Mips::SC_R6)
227                : (ArePtrs64bit ? Mips::SC64 : Mips::SC);
228       BNE = Mips::BNE;
229       BEQ = Mips::BEQ;
230     }
231 
232     ZERO = Mips::ZERO;
233     MOVE = Mips::OR;
234   } else {
235     LL = STI->hasMips64r6() ? Mips::LLD_R6 : Mips::LLD;
236     SC = STI->hasMips64r6() ? Mips::SCD_R6 : Mips::SCD;
237     ZERO = Mips::ZERO_64;
238     BNE = Mips::BNE64;
239     BEQ = Mips::BEQ64;
240     MOVE = Mips::OR64;
241   }
242 
243   Register Dest = I->getOperand(0).getReg();
244   Register Ptr = I->getOperand(1).getReg();
245   Register OldVal = I->getOperand(2).getReg();
246   Register NewVal = I->getOperand(3).getReg();
247   Register Scratch = I->getOperand(4).getReg();
248 
249   // insert new blocks after the current block
250   const BasicBlock *LLVM_BB = BB.getBasicBlock();
251   MachineBasicBlock *loop1MBB = MF->CreateMachineBasicBlock(LLVM_BB);
252   MachineBasicBlock *loop2MBB = MF->CreateMachineBasicBlock(LLVM_BB);
253   MachineBasicBlock *exitMBB = MF->CreateMachineBasicBlock(LLVM_BB);
254   MachineFunction::iterator It = ++BB.getIterator();
255   MF->insert(It, loop1MBB);
256   MF->insert(It, loop2MBB);
257   MF->insert(It, exitMBB);
258 
259   // Transfer the remainder of BB and its successor edges to exitMBB.
260   exitMBB->splice(exitMBB->begin(), &BB,
261                   std::next(MachineBasicBlock::iterator(I)), BB.end());
262   exitMBB->transferSuccessorsAndUpdatePHIs(&BB);
263 
264   //  thisMBB:
265   //    ...
266   //    fallthrough --> loop1MBB
267   BB.addSuccessor(loop1MBB, BranchProbability::getOne());
268   loop1MBB->addSuccessor(exitMBB);
269   loop1MBB->addSuccessor(loop2MBB);
270   loop1MBB->normalizeSuccProbs();
271   loop2MBB->addSuccessor(loop1MBB);
272   loop2MBB->addSuccessor(exitMBB);
273   loop2MBB->normalizeSuccProbs();
274 
275   // loop1MBB:
276   //   ll dest, 0(ptr)
277   //   bne dest, oldval, exitMBB
278   BuildMI(loop1MBB, DL, TII->get(LL), Dest).addReg(Ptr).addImm(0);
279   BuildMI(loop1MBB, DL, TII->get(BNE))
280     .addReg(Dest, RegState::Kill).addReg(OldVal).addMBB(exitMBB);
281 
282   // loop2MBB:
283   //   move scratch, NewVal
284   //   sc Scratch, Scratch, 0(ptr)
285   //   beq Scratch, $0, loop1MBB
286   BuildMI(loop2MBB, DL, TII->get(MOVE), Scratch).addReg(NewVal).addReg(ZERO);
287   BuildMI(loop2MBB, DL, TII->get(SC), Scratch)
288     .addReg(Scratch).addReg(Ptr).addImm(0);
289   BuildMI(loop2MBB, DL, TII->get(BEQ))
290     .addReg(Scratch, RegState::Kill).addReg(ZERO).addMBB(loop1MBB);
291 
292   LivePhysRegs LiveRegs;
293   computeAndAddLiveIns(LiveRegs, *loop1MBB);
294   computeAndAddLiveIns(LiveRegs, *loop2MBB);
295   computeAndAddLiveIns(LiveRegs, *exitMBB);
296 
297   NMBBI = BB.end();
298   I->eraseFromParent();
299   return true;
300 }
301 
302 bool MipsExpandPseudo::expandAtomicBinOpSubword(
303     MachineBasicBlock &BB, MachineBasicBlock::iterator I,
304     MachineBasicBlock::iterator &NMBBI) {
305 
306   MachineFunction *MF = BB.getParent();
307 
308   const bool ArePtrs64bit = STI->getABI().ArePtrs64bit();
309   DebugLoc DL = I->getDebugLoc();
310 
311   unsigned LL, SC, SLT, SLTu, OR, MOVN, MOVZ, SELNEZ, SELEQZ;
312   unsigned BEQ = Mips::BEQ;
313   unsigned SEOp = Mips::SEH;
314 
315   if (STI->inMicroMipsMode()) {
316       LL = STI->hasMips32r6() ? Mips::LL_MMR6 : Mips::LL_MM;
317       SC = STI->hasMips32r6() ? Mips::SC_MMR6 : Mips::SC_MM;
318       BEQ = STI->hasMips32r6() ? Mips::BEQC_MMR6 : Mips::BEQ_MM;
319       SLT = Mips::SLT_MM;
320       SLTu = Mips::SLTu_MM;
321       OR = STI->hasMips32r6() ? Mips::OR_MMR6 : Mips::OR_MM;
322       MOVN = Mips::MOVN_I_MM;
323       MOVZ = Mips::MOVZ_I_MM;
324       SELNEZ = STI->hasMips32r6() ? Mips::SELNEZ_MMR6 : Mips::SELNEZ;
325       SELEQZ = STI->hasMips32r6() ? Mips::SELEQZ_MMR6 : Mips::SELEQZ;
326   } else {
327     LL = STI->hasMips32r6() ? (ArePtrs64bit ? Mips::LL64_R6 : Mips::LL_R6)
328                             : (ArePtrs64bit ? Mips::LL64 : Mips::LL);
329     SC = STI->hasMips32r6() ? (ArePtrs64bit ? Mips::SC64_R6 : Mips::SC_R6)
330                             : (ArePtrs64bit ? Mips::SC64 : Mips::SC);
331     SLT = Mips::SLT;
332     SLTu = Mips::SLTu;
333     OR = Mips::OR;
334     MOVN = Mips::MOVN_I_I;
335     MOVZ = Mips::MOVZ_I_I;
336     SELNEZ = Mips::SELNEZ;
337     SELEQZ = Mips::SELEQZ;
338   }
339 
340   bool IsSwap = false;
341   bool IsNand = false;
342   bool IsMin = false;
343   bool IsMax = false;
344   bool IsUnsigned = false;
345 
346   unsigned Opcode = 0;
347   switch (I->getOpcode()) {
348   case Mips::ATOMIC_LOAD_NAND_I8_POSTRA:
349     SEOp = Mips::SEB;
350     [[fallthrough]];
351   case Mips::ATOMIC_LOAD_NAND_I16_POSTRA:
352     IsNand = true;
353     break;
354   case Mips::ATOMIC_SWAP_I8_POSTRA:
355     SEOp = Mips::SEB;
356     [[fallthrough]];
357   case Mips::ATOMIC_SWAP_I16_POSTRA:
358     IsSwap = true;
359     break;
360   case Mips::ATOMIC_LOAD_ADD_I8_POSTRA:
361     SEOp = Mips::SEB;
362     [[fallthrough]];
363   case Mips::ATOMIC_LOAD_ADD_I16_POSTRA:
364     Opcode = Mips::ADDu;
365     break;
366   case Mips::ATOMIC_LOAD_SUB_I8_POSTRA:
367     SEOp = Mips::SEB;
368     [[fallthrough]];
369   case Mips::ATOMIC_LOAD_SUB_I16_POSTRA:
370     Opcode = Mips::SUBu;
371     break;
372   case Mips::ATOMIC_LOAD_AND_I8_POSTRA:
373     SEOp = Mips::SEB;
374     [[fallthrough]];
375   case Mips::ATOMIC_LOAD_AND_I16_POSTRA:
376     Opcode = Mips::AND;
377     break;
378   case Mips::ATOMIC_LOAD_OR_I8_POSTRA:
379     SEOp = Mips::SEB;
380     [[fallthrough]];
381   case Mips::ATOMIC_LOAD_OR_I16_POSTRA:
382     Opcode = Mips::OR;
383     break;
384   case Mips::ATOMIC_LOAD_XOR_I8_POSTRA:
385     SEOp = Mips::SEB;
386     [[fallthrough]];
387   case Mips::ATOMIC_LOAD_XOR_I16_POSTRA:
388     Opcode = Mips::XOR;
389     break;
390   case Mips::ATOMIC_LOAD_UMIN_I8_POSTRA:
391   case Mips::ATOMIC_LOAD_UMIN_I16_POSTRA:
392     IsUnsigned = true;
393     [[fallthrough]];
394   case Mips::ATOMIC_LOAD_MIN_I8_POSTRA:
395   case Mips::ATOMIC_LOAD_MIN_I16_POSTRA:
396     IsMin = true;
397     break;
398   case Mips::ATOMIC_LOAD_UMAX_I8_POSTRA:
399   case Mips::ATOMIC_LOAD_UMAX_I16_POSTRA:
400     IsUnsigned = true;
401     [[fallthrough]];
402   case Mips::ATOMIC_LOAD_MAX_I8_POSTRA:
403   case Mips::ATOMIC_LOAD_MAX_I16_POSTRA:
404     IsMax = true;
405     break;
406   default:
407     llvm_unreachable("Unknown subword atomic pseudo for expansion!");
408   }
409 
410   Register Dest = I->getOperand(0).getReg();
411   Register Ptr = I->getOperand(1).getReg();
412   Register Incr = I->getOperand(2).getReg();
413   Register Mask = I->getOperand(3).getReg();
414   Register Mask2 = I->getOperand(4).getReg();
415   Register ShiftAmnt = I->getOperand(5).getReg();
416   Register OldVal = I->getOperand(6).getReg();
417   Register BinOpRes = I->getOperand(7).getReg();
418   Register StoreVal = I->getOperand(8).getReg();
419 
420   const BasicBlock *LLVM_BB = BB.getBasicBlock();
421   MachineBasicBlock *loopMBB = MF->CreateMachineBasicBlock(LLVM_BB);
422   MachineBasicBlock *sinkMBB = MF->CreateMachineBasicBlock(LLVM_BB);
423   MachineBasicBlock *exitMBB = MF->CreateMachineBasicBlock(LLVM_BB);
424   MachineFunction::iterator It = ++BB.getIterator();
425   MF->insert(It, loopMBB);
426   MF->insert(It, sinkMBB);
427   MF->insert(It, exitMBB);
428 
429   exitMBB->splice(exitMBB->begin(), &BB, std::next(I), BB.end());
430   exitMBB->transferSuccessorsAndUpdatePHIs(&BB);
431 
432   BB.addSuccessor(loopMBB, BranchProbability::getOne());
433   loopMBB->addSuccessor(sinkMBB);
434   loopMBB->addSuccessor(loopMBB);
435   loopMBB->normalizeSuccProbs();
436 
437   BuildMI(loopMBB, DL, TII->get(LL), OldVal).addReg(Ptr).addImm(0);
438   if (IsNand) {
439     //  and andres, oldval, incr2
440     //  nor binopres, $0, andres
441     //  and newval, binopres, mask
442     BuildMI(loopMBB, DL, TII->get(Mips::AND), BinOpRes)
443         .addReg(OldVal)
444         .addReg(Incr);
445     BuildMI(loopMBB, DL, TII->get(Mips::NOR), BinOpRes)
446         .addReg(Mips::ZERO)
447         .addReg(BinOpRes);
448     BuildMI(loopMBB, DL, TII->get(Mips::AND), BinOpRes)
449         .addReg(BinOpRes)
450         .addReg(Mask);
451   } else if (IsMin || IsMax) {
452 
453     assert(I->getNumOperands() == 10 &&
454            "Atomics min|max|umin|umax use an additional register");
455     Register Scratch4 = I->getOperand(9).getReg();
456 
457     unsigned SLTScratch4 = IsUnsigned ? SLTu : SLT;
458     unsigned SELIncr = IsMax ? SELNEZ : SELEQZ;
459     unsigned SELOldVal = IsMax ? SELEQZ : SELNEZ;
460     unsigned MOVIncr = IsMax ? MOVN : MOVZ;
461 
462     // For little endian we need to clear uninterested bits.
463     if (STI->isLittle()) {
464       // and OldVal, OldVal, Mask
465       // and Incr, Incr, Mask
466       BuildMI(loopMBB, DL, TII->get(Mips::AND), OldVal)
467           .addReg(OldVal)
468           .addReg(Mask);
469       BuildMI(loopMBB, DL, TII->get(Mips::AND), Incr).addReg(Incr).addReg(Mask);
470     }
471 
472     // unsigned: sltu Scratch4, oldVal, Incr
473     // signed:   slt Scratch4, oldVal, Incr
474     BuildMI(loopMBB, DL, TII->get(SLTScratch4), Scratch4)
475         .addReg(OldVal)
476         .addReg(Incr);
477 
478     if (STI->hasMips64r6() || STI->hasMips32r6()) {
479       // max: seleqz BinOpRes, OldVal, Scratch4
480       //      selnez Scratch4, Incr, Scratch4
481       //      or BinOpRes, BinOpRes, Scratch4
482       // min: selnqz BinOpRes, OldVal, Scratch4
483       //      seleqz Scratch4, Incr, Scratch4
484       //      or BinOpRes, BinOpRes, Scratch4
485       BuildMI(loopMBB, DL, TII->get(SELOldVal), BinOpRes)
486           .addReg(OldVal)
487           .addReg(Scratch4);
488       BuildMI(loopMBB, DL, TII->get(SELIncr), Scratch4)
489           .addReg(Incr)
490           .addReg(Scratch4);
491       BuildMI(loopMBB, DL, TII->get(OR), BinOpRes)
492           .addReg(BinOpRes)
493           .addReg(Scratch4);
494     } else {
495       // max: move BinOpRes, OldVal
496       //      movn BinOpRes, Incr, Scratch4, BinOpRes
497       // min: move BinOpRes, OldVal
498       //      movz BinOpRes, Incr, Scratch4, BinOpRes
499       BuildMI(loopMBB, DL, TII->get(OR), BinOpRes)
500           .addReg(OldVal)
501           .addReg(Mips::ZERO);
502       BuildMI(loopMBB, DL, TII->get(MOVIncr), BinOpRes)
503           .addReg(Incr)
504           .addReg(Scratch4)
505           .addReg(BinOpRes);
506     }
507 
508     //  and BinOpRes, BinOpRes, Mask
509     BuildMI(loopMBB, DL, TII->get(Mips::AND), BinOpRes)
510         .addReg(BinOpRes)
511         .addReg(Mask);
512 
513   } else if (!IsSwap) {
514     //  <binop> binopres, oldval, incr2
515     //  and newval, binopres, mask
516     BuildMI(loopMBB, DL, TII->get(Opcode), BinOpRes)
517         .addReg(OldVal)
518         .addReg(Incr);
519     BuildMI(loopMBB, DL, TII->get(Mips::AND), BinOpRes)
520         .addReg(BinOpRes)
521         .addReg(Mask);
522   } else { // atomic.swap
523     //  and newval, incr2, mask
524     BuildMI(loopMBB, DL, TII->get(Mips::AND), BinOpRes)
525         .addReg(Incr)
526         .addReg(Mask);
527   }
528 
529   // and StoreVal, OlddVal, Mask2
530   // or StoreVal, StoreVal, BinOpRes
531   // StoreVal<tied1> = sc StoreVal, 0(Ptr)
532   // beq StoreVal, zero, loopMBB
533   BuildMI(loopMBB, DL, TII->get(Mips::AND), StoreVal)
534     .addReg(OldVal).addReg(Mask2);
535   BuildMI(loopMBB, DL, TII->get(Mips::OR), StoreVal)
536     .addReg(StoreVal).addReg(BinOpRes);
537   BuildMI(loopMBB, DL, TII->get(SC), StoreVal)
538     .addReg(StoreVal).addReg(Ptr).addImm(0);
539   BuildMI(loopMBB, DL, TII->get(BEQ))
540     .addReg(StoreVal).addReg(Mips::ZERO).addMBB(loopMBB);
541 
542   //  sinkMBB:
543   //    and     maskedoldval1,oldval,mask
544   //    srl     srlres,maskedoldval1,shiftamt
545   //    sign_extend dest,srlres
546 
547   sinkMBB->addSuccessor(exitMBB, BranchProbability::getOne());
548 
549   BuildMI(sinkMBB, DL, TII->get(Mips::AND), Dest)
550     .addReg(OldVal).addReg(Mask);
551   BuildMI(sinkMBB, DL, TII->get(Mips::SRLV), Dest)
552       .addReg(Dest).addReg(ShiftAmnt);
553 
554   if (STI->hasMips32r2()) {
555     BuildMI(sinkMBB, DL, TII->get(SEOp), Dest).addReg(Dest);
556   } else {
557     const unsigned ShiftImm = SEOp == Mips::SEH ? 16 : 24;
558     BuildMI(sinkMBB, DL, TII->get(Mips::SLL), Dest)
559         .addReg(Dest, RegState::Kill)
560         .addImm(ShiftImm);
561     BuildMI(sinkMBB, DL, TII->get(Mips::SRA), Dest)
562         .addReg(Dest, RegState::Kill)
563         .addImm(ShiftImm);
564   }
565 
566   LivePhysRegs LiveRegs;
567   computeAndAddLiveIns(LiveRegs, *loopMBB);
568   computeAndAddLiveIns(LiveRegs, *sinkMBB);
569   computeAndAddLiveIns(LiveRegs, *exitMBB);
570 
571   NMBBI = BB.end();
572   I->eraseFromParent();
573 
574   return true;
575 }
576 
577 bool MipsExpandPseudo::expandAtomicBinOp(MachineBasicBlock &BB,
578                                          MachineBasicBlock::iterator I,
579                                          MachineBasicBlock::iterator &NMBBI,
580                                          unsigned Size) {
581   MachineFunction *MF = BB.getParent();
582 
583   const bool ArePtrs64bit = STI->getABI().ArePtrs64bit();
584   DebugLoc DL = I->getDebugLoc();
585 
586   unsigned LL, SC, ZERO, BEQ, SLT, SLTu, OR, MOVN, MOVZ, SELNEZ, SELEQZ;
587 
588   if (Size == 4) {
589     if (STI->inMicroMipsMode()) {
590       LL = STI->hasMips32r6() ? Mips::LL_MMR6 : Mips::LL_MM;
591       SC = STI->hasMips32r6() ? Mips::SC_MMR6 : Mips::SC_MM;
592       BEQ = STI->hasMips32r6() ? Mips::BEQC_MMR6 : Mips::BEQ_MM;
593       SLT = Mips::SLT_MM;
594       SLTu = Mips::SLTu_MM;
595       OR = STI->hasMips32r6() ? Mips::OR_MMR6 : Mips::OR_MM;
596       MOVN = Mips::MOVN_I_MM;
597       MOVZ = Mips::MOVZ_I_MM;
598       SELNEZ = STI->hasMips32r6() ? Mips::SELNEZ_MMR6 : Mips::SELNEZ;
599       SELEQZ = STI->hasMips32r6() ? Mips::SELEQZ_MMR6 : Mips::SELEQZ;
600     } else {
601       LL = STI->hasMips32r6()
602                ? (ArePtrs64bit ? Mips::LL64_R6 : Mips::LL_R6)
603                : (ArePtrs64bit ? Mips::LL64 : Mips::LL);
604       SC = STI->hasMips32r6()
605                ? (ArePtrs64bit ? Mips::SC64_R6 : Mips::SC_R6)
606                : (ArePtrs64bit ? Mips::SC64 : Mips::SC);
607       BEQ = Mips::BEQ;
608       SLT = Mips::SLT;
609       SLTu = Mips::SLTu;
610       OR = Mips::OR;
611       MOVN = Mips::MOVN_I_I;
612       MOVZ = Mips::MOVZ_I_I;
613       SELNEZ = Mips::SELNEZ;
614       SELEQZ = Mips::SELEQZ;
615     }
616 
617     ZERO = Mips::ZERO;
618   } else {
619     LL = STI->hasMips64r6() ? Mips::LLD_R6 : Mips::LLD;
620     SC = STI->hasMips64r6() ? Mips::SCD_R6 : Mips::SCD;
621     ZERO = Mips::ZERO_64;
622     BEQ = Mips::BEQ64;
623     SLT = Mips::SLT64;
624     SLTu = Mips::SLTu64;
625     OR = Mips::OR64;
626     MOVN = Mips::MOVN_I64_I64;
627     MOVZ = Mips::MOVZ_I64_I64;
628     SELNEZ = Mips::SELNEZ64;
629     SELEQZ = Mips::SELEQZ64;
630   }
631 
632   Register OldVal = I->getOperand(0).getReg();
633   Register Ptr = I->getOperand(1).getReg();
634   Register Incr = I->getOperand(2).getReg();
635   Register Scratch = I->getOperand(3).getReg();
636 
637   unsigned Opcode = 0;
638   unsigned AND = 0;
639   unsigned NOR = 0;
640 
641   bool IsOr = false;
642   bool IsNand = false;
643   bool IsMin = false;
644   bool IsMax = false;
645   bool IsUnsigned = false;
646 
647   switch (I->getOpcode()) {
648   case Mips::ATOMIC_LOAD_ADD_I32_POSTRA:
649     Opcode = Mips::ADDu;
650     break;
651   case Mips::ATOMIC_LOAD_SUB_I32_POSTRA:
652     Opcode = Mips::SUBu;
653     break;
654   case Mips::ATOMIC_LOAD_AND_I32_POSTRA:
655     Opcode = Mips::AND;
656     break;
657   case Mips::ATOMIC_LOAD_OR_I32_POSTRA:
658     Opcode = Mips::OR;
659     break;
660   case Mips::ATOMIC_LOAD_XOR_I32_POSTRA:
661     Opcode = Mips::XOR;
662     break;
663   case Mips::ATOMIC_LOAD_NAND_I32_POSTRA:
664     IsNand = true;
665     AND = Mips::AND;
666     NOR = Mips::NOR;
667     break;
668   case Mips::ATOMIC_SWAP_I32_POSTRA:
669     IsOr = true;
670     break;
671   case Mips::ATOMIC_LOAD_ADD_I64_POSTRA:
672     Opcode = Mips::DADDu;
673     break;
674   case Mips::ATOMIC_LOAD_SUB_I64_POSTRA:
675     Opcode = Mips::DSUBu;
676     break;
677   case Mips::ATOMIC_LOAD_AND_I64_POSTRA:
678     Opcode = Mips::AND64;
679     break;
680   case Mips::ATOMIC_LOAD_OR_I64_POSTRA:
681     Opcode = Mips::OR64;
682     break;
683   case Mips::ATOMIC_LOAD_XOR_I64_POSTRA:
684     Opcode = Mips::XOR64;
685     break;
686   case Mips::ATOMIC_LOAD_NAND_I64_POSTRA:
687     IsNand = true;
688     AND = Mips::AND64;
689     NOR = Mips::NOR64;
690     break;
691   case Mips::ATOMIC_SWAP_I64_POSTRA:
692     IsOr = true;
693     break;
694   case Mips::ATOMIC_LOAD_UMIN_I32_POSTRA:
695   case Mips::ATOMIC_LOAD_UMIN_I64_POSTRA:
696     IsUnsigned = true;
697     [[fallthrough]];
698   case Mips::ATOMIC_LOAD_MIN_I32_POSTRA:
699   case Mips::ATOMIC_LOAD_MIN_I64_POSTRA:
700     IsMin = true;
701     break;
702   case Mips::ATOMIC_LOAD_UMAX_I32_POSTRA:
703   case Mips::ATOMIC_LOAD_UMAX_I64_POSTRA:
704     IsUnsigned = true;
705     [[fallthrough]];
706   case Mips::ATOMIC_LOAD_MAX_I32_POSTRA:
707   case Mips::ATOMIC_LOAD_MAX_I64_POSTRA:
708     IsMax = true;
709     break;
710   default:
711     llvm_unreachable("Unknown pseudo atomic!");
712   }
713 
714   const BasicBlock *LLVM_BB = BB.getBasicBlock();
715   MachineBasicBlock *loopMBB = MF->CreateMachineBasicBlock(LLVM_BB);
716   MachineBasicBlock *exitMBB = MF->CreateMachineBasicBlock(LLVM_BB);
717   MachineFunction::iterator It = ++BB.getIterator();
718   MF->insert(It, loopMBB);
719   MF->insert(It, exitMBB);
720 
721   exitMBB->splice(exitMBB->begin(), &BB, std::next(I), BB.end());
722   exitMBB->transferSuccessorsAndUpdatePHIs(&BB);
723 
724   BB.addSuccessor(loopMBB, BranchProbability::getOne());
725   loopMBB->addSuccessor(exitMBB);
726   loopMBB->addSuccessor(loopMBB);
727   loopMBB->normalizeSuccProbs();
728 
729   BuildMI(loopMBB, DL, TII->get(LL), OldVal).addReg(Ptr).addImm(0);
730   assert((OldVal != Ptr) && "Clobbered the wrong ptr reg!");
731   assert((OldVal != Incr) && "Clobbered the wrong reg!");
732   if (IsMin || IsMax) {
733 
734     assert(I->getNumOperands() == 5 &&
735            "Atomics min|max|umin|umax use an additional register");
736     MCRegister Scratch2 = I->getOperand(4).getReg().asMCReg();
737 
738     // On Mips64 result of slt is GPR32.
739     MCRegister Scratch2_32 =
740         (Size == 8) ? STI->getRegisterInfo()->getSubReg(Scratch2, Mips::sub_32)
741                     : Scratch2;
742 
743     unsigned SLTScratch2 = IsUnsigned ? SLTu : SLT;
744     unsigned SELIncr = IsMax ? SELNEZ : SELEQZ;
745     unsigned SELOldVal = IsMax ? SELEQZ : SELNEZ;
746     unsigned MOVIncr = IsMax ? MOVN : MOVZ;
747 
748     // unsigned: sltu Scratch2, oldVal, Incr
749     // signed:   slt Scratch2, oldVal, Incr
750     BuildMI(loopMBB, DL, TII->get(SLTScratch2), Scratch2_32)
751         .addReg(OldVal)
752         .addReg(Incr);
753 
754     if (STI->hasMips64r6() || STI->hasMips32r6()) {
755       // max: seleqz Scratch, OldVal, Scratch2
756       //      selnez Scratch2, Incr, Scratch2
757       //      or Scratch, Scratch, Scratch2
758       // min: selnez Scratch, OldVal, Scratch2
759       //      seleqz Scratch2, Incr, Scratch2
760       //      or Scratch, Scratch, Scratch2
761       BuildMI(loopMBB, DL, TII->get(SELOldVal), Scratch)
762           .addReg(OldVal)
763           .addReg(Scratch2);
764       BuildMI(loopMBB, DL, TII->get(SELIncr), Scratch2)
765           .addReg(Incr)
766           .addReg(Scratch2);
767       BuildMI(loopMBB, DL, TII->get(OR), Scratch)
768           .addReg(Scratch)
769           .addReg(Scratch2);
770     } else {
771       // max: move Scratch, OldVal
772       //      movn Scratch, Incr, Scratch2, Scratch
773       // min: move Scratch, OldVal
774       //      movz Scratch, Incr, Scratch2, Scratch
775       BuildMI(loopMBB, DL, TII->get(OR), Scratch)
776           .addReg(OldVal)
777           .addReg(ZERO);
778       BuildMI(loopMBB, DL, TII->get(MOVIncr), Scratch)
779           .addReg(Incr)
780           .addReg(Scratch2)
781           .addReg(Scratch);
782     }
783 
784   } else if (Opcode) {
785     BuildMI(loopMBB, DL, TII->get(Opcode), Scratch).addReg(OldVal).addReg(Incr);
786   } else if (IsNand) {
787     assert(AND && NOR &&
788            "Unknown nand instruction for atomic pseudo expansion");
789     BuildMI(loopMBB, DL, TII->get(AND), Scratch).addReg(OldVal).addReg(Incr);
790     BuildMI(loopMBB, DL, TII->get(NOR), Scratch).addReg(ZERO).addReg(Scratch);
791   } else {
792     assert(IsOr && OR && "Unknown instruction for atomic pseudo expansion!");
793     (void)IsOr;
794     BuildMI(loopMBB, DL, TII->get(OR), Scratch).addReg(Incr).addReg(ZERO);
795   }
796 
797   BuildMI(loopMBB, DL, TII->get(SC), Scratch)
798       .addReg(Scratch)
799       .addReg(Ptr)
800       .addImm(0);
801   BuildMI(loopMBB, DL, TII->get(BEQ))
802       .addReg(Scratch)
803       .addReg(ZERO)
804       .addMBB(loopMBB);
805 
806   NMBBI = BB.end();
807   I->eraseFromParent();
808 
809   LivePhysRegs LiveRegs;
810   computeAndAddLiveIns(LiveRegs, *loopMBB);
811   computeAndAddLiveIns(LiveRegs, *exitMBB);
812 
813   return true;
814 }
815 
816 bool MipsExpandPseudo::expandMI(MachineBasicBlock &MBB,
817                                 MachineBasicBlock::iterator MBBI,
818                                 MachineBasicBlock::iterator &NMBB) {
819 
820   bool Modified = false;
821 
822   switch (MBBI->getOpcode()) {
823   case Mips::ATOMIC_CMP_SWAP_I32_POSTRA:
824   case Mips::ATOMIC_CMP_SWAP_I64_POSTRA:
825     return expandAtomicCmpSwap(MBB, MBBI, NMBB);
826   case Mips::ATOMIC_CMP_SWAP_I8_POSTRA:
827   case Mips::ATOMIC_CMP_SWAP_I16_POSTRA:
828     return expandAtomicCmpSwapSubword(MBB, MBBI, NMBB);
829   case Mips::ATOMIC_SWAP_I8_POSTRA:
830   case Mips::ATOMIC_SWAP_I16_POSTRA:
831   case Mips::ATOMIC_LOAD_NAND_I8_POSTRA:
832   case Mips::ATOMIC_LOAD_NAND_I16_POSTRA:
833   case Mips::ATOMIC_LOAD_ADD_I8_POSTRA:
834   case Mips::ATOMIC_LOAD_ADD_I16_POSTRA:
835   case Mips::ATOMIC_LOAD_SUB_I8_POSTRA:
836   case Mips::ATOMIC_LOAD_SUB_I16_POSTRA:
837   case Mips::ATOMIC_LOAD_AND_I8_POSTRA:
838   case Mips::ATOMIC_LOAD_AND_I16_POSTRA:
839   case Mips::ATOMIC_LOAD_OR_I8_POSTRA:
840   case Mips::ATOMIC_LOAD_OR_I16_POSTRA:
841   case Mips::ATOMIC_LOAD_XOR_I8_POSTRA:
842   case Mips::ATOMIC_LOAD_XOR_I16_POSTRA:
843   case Mips::ATOMIC_LOAD_MIN_I8_POSTRA:
844   case Mips::ATOMIC_LOAD_MIN_I16_POSTRA:
845   case Mips::ATOMIC_LOAD_MAX_I8_POSTRA:
846   case Mips::ATOMIC_LOAD_MAX_I16_POSTRA:
847   case Mips::ATOMIC_LOAD_UMIN_I8_POSTRA:
848   case Mips::ATOMIC_LOAD_UMIN_I16_POSTRA:
849   case Mips::ATOMIC_LOAD_UMAX_I8_POSTRA:
850   case Mips::ATOMIC_LOAD_UMAX_I16_POSTRA:
851     return expandAtomicBinOpSubword(MBB, MBBI, NMBB);
852   case Mips::ATOMIC_LOAD_ADD_I32_POSTRA:
853   case Mips::ATOMIC_LOAD_SUB_I32_POSTRA:
854   case Mips::ATOMIC_LOAD_AND_I32_POSTRA:
855   case Mips::ATOMIC_LOAD_OR_I32_POSTRA:
856   case Mips::ATOMIC_LOAD_XOR_I32_POSTRA:
857   case Mips::ATOMIC_LOAD_NAND_I32_POSTRA:
858   case Mips::ATOMIC_SWAP_I32_POSTRA:
859   case Mips::ATOMIC_LOAD_MIN_I32_POSTRA:
860   case Mips::ATOMIC_LOAD_MAX_I32_POSTRA:
861   case Mips::ATOMIC_LOAD_UMIN_I32_POSTRA:
862   case Mips::ATOMIC_LOAD_UMAX_I32_POSTRA:
863     return expandAtomicBinOp(MBB, MBBI, NMBB, 4);
864   case Mips::ATOMIC_LOAD_ADD_I64_POSTRA:
865   case Mips::ATOMIC_LOAD_SUB_I64_POSTRA:
866   case Mips::ATOMIC_LOAD_AND_I64_POSTRA:
867   case Mips::ATOMIC_LOAD_OR_I64_POSTRA:
868   case Mips::ATOMIC_LOAD_XOR_I64_POSTRA:
869   case Mips::ATOMIC_LOAD_NAND_I64_POSTRA:
870   case Mips::ATOMIC_SWAP_I64_POSTRA:
871   case Mips::ATOMIC_LOAD_MIN_I64_POSTRA:
872   case Mips::ATOMIC_LOAD_MAX_I64_POSTRA:
873   case Mips::ATOMIC_LOAD_UMIN_I64_POSTRA:
874   case Mips::ATOMIC_LOAD_UMAX_I64_POSTRA:
875     return expandAtomicBinOp(MBB, MBBI, NMBB, 8);
876   default:
877     return Modified;
878   }
879 }
880 
881 bool MipsExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
882   bool Modified = false;
883 
884   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
885   while (MBBI != E) {
886     MachineBasicBlock::iterator NMBBI = std::next(MBBI);
887     Modified |= expandMI(MBB, MBBI, NMBBI);
888     MBBI = NMBBI;
889   }
890 
891   return Modified;
892 }
893 
894 bool MipsExpandPseudo::runOnMachineFunction(MachineFunction &MF) {
895   STI = &MF.getSubtarget<MipsSubtarget>();
896   TII = STI->getInstrInfo();
897 
898   bool Modified = false;
899   for (MachineBasicBlock &MBB : MF)
900     Modified |= expandMBB(MBB);
901 
902   if (Modified)
903     MF.RenumberBlocks();
904 
905   return Modified;
906 }
907 
908 /// createMipsExpandPseudoPass - returns an instance of the pseudo instruction
909 /// expansion pass.
910 FunctionPass *llvm::createMipsExpandPseudoPass() {
911   return new MipsExpandPseudo();
912 }
913