xref: /freebsd/contrib/llvm-project/llvm/lib/Target/Mips/MipsExpandPseudo.cpp (revision 725a9f47324d42037db93c27ceb40d4956872f3e)
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     IsUnsigned = true;
392     IsMin = true;
393     break;
394   case Mips::ATOMIC_LOAD_UMIN_I16_POSTRA:
395     IsUnsigned = true;
396     IsMin = true;
397     break;
398   case Mips::ATOMIC_LOAD_MIN_I8_POSTRA:
399     SEOp = Mips::SEB;
400     IsMin = true;
401     break;
402   case Mips::ATOMIC_LOAD_MIN_I16_POSTRA:
403     IsMin = true;
404     break;
405   case Mips::ATOMIC_LOAD_UMAX_I8_POSTRA:
406     IsUnsigned = true;
407     IsMax = true;
408     break;
409   case Mips::ATOMIC_LOAD_UMAX_I16_POSTRA:
410     IsUnsigned = true;
411     IsMax = true;
412     break;
413   case Mips::ATOMIC_LOAD_MAX_I8_POSTRA:
414     SEOp = Mips::SEB;
415     IsMax = true;
416     break;
417   case Mips::ATOMIC_LOAD_MAX_I16_POSTRA:
418     IsMax = true;
419     break;
420   default:
421     llvm_unreachable("Unknown subword atomic pseudo for expansion!");
422   }
423 
424   Register Dest = I->getOperand(0).getReg();
425   Register Ptr = I->getOperand(1).getReg();
426   Register Incr = I->getOperand(2).getReg();
427   Register Mask = I->getOperand(3).getReg();
428   Register Mask2 = I->getOperand(4).getReg();
429   Register ShiftAmnt = I->getOperand(5).getReg();
430   Register OldVal = I->getOperand(6).getReg();
431   Register BinOpRes = I->getOperand(7).getReg();
432   Register StoreVal = I->getOperand(8).getReg();
433 
434   const BasicBlock *LLVM_BB = BB.getBasicBlock();
435   MachineBasicBlock *loopMBB = MF->CreateMachineBasicBlock(LLVM_BB);
436   MachineBasicBlock *sinkMBB = MF->CreateMachineBasicBlock(LLVM_BB);
437   MachineBasicBlock *exitMBB = MF->CreateMachineBasicBlock(LLVM_BB);
438   MachineFunction::iterator It = ++BB.getIterator();
439   MF->insert(It, loopMBB);
440   MF->insert(It, sinkMBB);
441   MF->insert(It, exitMBB);
442 
443   exitMBB->splice(exitMBB->begin(), &BB, std::next(I), BB.end());
444   exitMBB->transferSuccessorsAndUpdatePHIs(&BB);
445 
446   BB.addSuccessor(loopMBB, BranchProbability::getOne());
447   loopMBB->addSuccessor(sinkMBB);
448   loopMBB->addSuccessor(loopMBB);
449   loopMBB->normalizeSuccProbs();
450 
451   BuildMI(loopMBB, DL, TII->get(LL), OldVal).addReg(Ptr).addImm(0);
452   if (IsNand) {
453     //  and andres, oldval, incr2
454     //  nor binopres, $0, andres
455     //  and newval, binopres, mask
456     BuildMI(loopMBB, DL, TII->get(Mips::AND), BinOpRes)
457         .addReg(OldVal)
458         .addReg(Incr);
459     BuildMI(loopMBB, DL, TII->get(Mips::NOR), BinOpRes)
460         .addReg(Mips::ZERO)
461         .addReg(BinOpRes);
462     BuildMI(loopMBB, DL, TII->get(Mips::AND), BinOpRes)
463         .addReg(BinOpRes)
464         .addReg(Mask);
465   } else if (IsMin || IsMax) {
466 
467     assert(I->getNumOperands() == 10 &&
468            "Atomics min|max|umin|umax use an additional register");
469     Register Scratch4 = I->getOperand(9).getReg();
470 
471     unsigned SLTScratch4 = IsUnsigned ? SLTu : SLT;
472     unsigned SELIncr = IsMax ? SELNEZ : SELEQZ;
473     unsigned SELOldVal = IsMax ? SELEQZ : SELNEZ;
474     unsigned MOVIncr = IsMax ? MOVN : MOVZ;
475 
476     // For little endian we need to clear uninterested bits.
477     if (STI->isLittle()) {
478       if (!IsUnsigned) {
479         BuildMI(loopMBB, DL, TII->get(Mips::SRAV), OldVal)
480             .addReg(OldVal)
481             .addReg(ShiftAmnt);
482         BuildMI(loopMBB, DL, TII->get(Mips::SRAV), Incr)
483             .addReg(Incr)
484             .addReg(ShiftAmnt);
485         if (STI->hasMips32r2()) {
486           BuildMI(loopMBB, DL, TII->get(SEOp), OldVal).addReg(OldVal);
487           BuildMI(loopMBB, DL, TII->get(SEOp), Incr).addReg(Incr);
488         } else {
489           const unsigned ShiftImm = SEOp == Mips::SEH ? 16 : 24;
490           BuildMI(loopMBB, DL, TII->get(Mips::SLL), OldVal)
491               .addReg(OldVal, RegState::Kill)
492               .addImm(ShiftImm);
493           BuildMI(loopMBB, DL, TII->get(Mips::SRA), OldVal)
494               .addReg(OldVal, RegState::Kill)
495               .addImm(ShiftImm);
496           BuildMI(loopMBB, DL, TII->get(Mips::SLL), Incr)
497               .addReg(Incr, RegState::Kill)
498               .addImm(ShiftImm);
499           BuildMI(loopMBB, DL, TII->get(Mips::SRA), Incr)
500               .addReg(Incr, RegState::Kill)
501               .addImm(ShiftImm);
502         }
503       } else {
504         // and OldVal, OldVal, Mask
505         // and Incr, Incr, Mask
506         BuildMI(loopMBB, DL, TII->get(Mips::AND), OldVal)
507             .addReg(OldVal)
508             .addReg(Mask);
509         BuildMI(loopMBB, DL, TII->get(Mips::AND), Incr)
510             .addReg(Incr)
511             .addReg(Mask);
512       }
513     }
514     // unsigned: sltu Scratch4, oldVal, Incr
515     // signed:   slt Scratch4, oldVal, Incr
516     BuildMI(loopMBB, DL, TII->get(SLTScratch4), Scratch4)
517         .addReg(OldVal)
518         .addReg(Incr);
519 
520     if (STI->hasMips64r6() || STI->hasMips32r6()) {
521       // max: seleqz BinOpRes, OldVal, Scratch4
522       //      selnez Scratch4, Incr, Scratch4
523       //      or BinOpRes, BinOpRes, Scratch4
524       // min: selnqz BinOpRes, OldVal, Scratch4
525       //      seleqz Scratch4, Incr, Scratch4
526       //      or BinOpRes, BinOpRes, Scratch4
527       BuildMI(loopMBB, DL, TII->get(SELOldVal), BinOpRes)
528           .addReg(OldVal)
529           .addReg(Scratch4);
530       BuildMI(loopMBB, DL, TII->get(SELIncr), Scratch4)
531           .addReg(Incr)
532           .addReg(Scratch4);
533       BuildMI(loopMBB, DL, TII->get(OR), BinOpRes)
534           .addReg(BinOpRes)
535           .addReg(Scratch4);
536     } else {
537       // max: move BinOpRes, OldVal
538       //      movn BinOpRes, Incr, Scratch4, BinOpRes
539       // min: move BinOpRes, OldVal
540       //      movz BinOpRes, Incr, Scratch4, BinOpRes
541       BuildMI(loopMBB, DL, TII->get(OR), BinOpRes)
542           .addReg(OldVal)
543           .addReg(Mips::ZERO);
544       BuildMI(loopMBB, DL, TII->get(MOVIncr), BinOpRes)
545           .addReg(Incr)
546           .addReg(Scratch4)
547           .addReg(BinOpRes);
548     }
549 
550     //  and BinOpRes, BinOpRes, Mask
551     BuildMI(loopMBB, DL, TII->get(Mips::AND), BinOpRes)
552         .addReg(BinOpRes)
553         .addReg(Mask);
554 
555   } else if (!IsSwap) {
556     //  <binop> binopres, oldval, incr2
557     //  and newval, binopres, mask
558     BuildMI(loopMBB, DL, TII->get(Opcode), BinOpRes)
559         .addReg(OldVal)
560         .addReg(Incr);
561     BuildMI(loopMBB, DL, TII->get(Mips::AND), BinOpRes)
562         .addReg(BinOpRes)
563         .addReg(Mask);
564   } else { // atomic.swap
565     //  and newval, incr2, mask
566     BuildMI(loopMBB, DL, TII->get(Mips::AND), BinOpRes)
567         .addReg(Incr)
568         .addReg(Mask);
569   }
570 
571   // and StoreVal, OlddVal, Mask2
572   // or StoreVal, StoreVal, BinOpRes
573   // StoreVal<tied1> = sc StoreVal, 0(Ptr)
574   // beq StoreVal, zero, loopMBB
575   BuildMI(loopMBB, DL, TII->get(Mips::AND), StoreVal)
576     .addReg(OldVal).addReg(Mask2);
577   BuildMI(loopMBB, DL, TII->get(Mips::OR), StoreVal)
578     .addReg(StoreVal).addReg(BinOpRes);
579   BuildMI(loopMBB, DL, TII->get(SC), StoreVal)
580     .addReg(StoreVal).addReg(Ptr).addImm(0);
581   BuildMI(loopMBB, DL, TII->get(BEQ))
582     .addReg(StoreVal).addReg(Mips::ZERO).addMBB(loopMBB);
583 
584   //  sinkMBB:
585   //    and     maskedoldval1,oldval,mask
586   //    srl     srlres,maskedoldval1,shiftamt
587   //    sign_extend dest,srlres
588 
589   sinkMBB->addSuccessor(exitMBB, BranchProbability::getOne());
590 
591   BuildMI(sinkMBB, DL, TII->get(Mips::AND), Dest)
592     .addReg(OldVal).addReg(Mask);
593   BuildMI(sinkMBB, DL, TII->get(Mips::SRLV), Dest)
594       .addReg(Dest).addReg(ShiftAmnt);
595 
596   if (STI->hasMips32r2()) {
597     BuildMI(sinkMBB, DL, TII->get(SEOp), Dest).addReg(Dest);
598   } else {
599     const unsigned ShiftImm = SEOp == Mips::SEH ? 16 : 24;
600     BuildMI(sinkMBB, DL, TII->get(Mips::SLL), Dest)
601         .addReg(Dest, RegState::Kill)
602         .addImm(ShiftImm);
603     BuildMI(sinkMBB, DL, TII->get(Mips::SRA), Dest)
604         .addReg(Dest, RegState::Kill)
605         .addImm(ShiftImm);
606   }
607 
608   LivePhysRegs LiveRegs;
609   computeAndAddLiveIns(LiveRegs, *loopMBB);
610   computeAndAddLiveIns(LiveRegs, *sinkMBB);
611   computeAndAddLiveIns(LiveRegs, *exitMBB);
612 
613   NMBBI = BB.end();
614   I->eraseFromParent();
615 
616   return true;
617 }
618 
619 bool MipsExpandPseudo::expandAtomicBinOp(MachineBasicBlock &BB,
620                                          MachineBasicBlock::iterator I,
621                                          MachineBasicBlock::iterator &NMBBI,
622                                          unsigned Size) {
623   MachineFunction *MF = BB.getParent();
624 
625   const bool ArePtrs64bit = STI->getABI().ArePtrs64bit();
626   DebugLoc DL = I->getDebugLoc();
627 
628   unsigned LL, SC, ZERO, BEQ, SLT, SLTu, OR, MOVN, MOVZ, SELNEZ, SELEQZ;
629 
630   if (Size == 4) {
631     if (STI->inMicroMipsMode()) {
632       LL = STI->hasMips32r6() ? Mips::LL_MMR6 : Mips::LL_MM;
633       SC = STI->hasMips32r6() ? Mips::SC_MMR6 : Mips::SC_MM;
634       BEQ = STI->hasMips32r6() ? Mips::BEQC_MMR6 : Mips::BEQ_MM;
635       SLT = Mips::SLT_MM;
636       SLTu = Mips::SLTu_MM;
637       OR = STI->hasMips32r6() ? Mips::OR_MMR6 : Mips::OR_MM;
638       MOVN = Mips::MOVN_I_MM;
639       MOVZ = Mips::MOVZ_I_MM;
640       SELNEZ = STI->hasMips32r6() ? Mips::SELNEZ_MMR6 : Mips::SELNEZ;
641       SELEQZ = STI->hasMips32r6() ? Mips::SELEQZ_MMR6 : Mips::SELEQZ;
642     } else {
643       LL = STI->hasMips32r6()
644                ? (ArePtrs64bit ? Mips::LL64_R6 : Mips::LL_R6)
645                : (ArePtrs64bit ? Mips::LL64 : Mips::LL);
646       SC = STI->hasMips32r6()
647                ? (ArePtrs64bit ? Mips::SC64_R6 : Mips::SC_R6)
648                : (ArePtrs64bit ? Mips::SC64 : Mips::SC);
649       BEQ = Mips::BEQ;
650       SLT = Mips::SLT;
651       SLTu = Mips::SLTu;
652       OR = Mips::OR;
653       MOVN = Mips::MOVN_I_I;
654       MOVZ = Mips::MOVZ_I_I;
655       SELNEZ = Mips::SELNEZ;
656       SELEQZ = Mips::SELEQZ;
657     }
658 
659     ZERO = Mips::ZERO;
660   } else {
661     LL = STI->hasMips64r6() ? Mips::LLD_R6 : Mips::LLD;
662     SC = STI->hasMips64r6() ? Mips::SCD_R6 : Mips::SCD;
663     ZERO = Mips::ZERO_64;
664     BEQ = Mips::BEQ64;
665     SLT = Mips::SLT64;
666     SLTu = Mips::SLTu64;
667     OR = Mips::OR64;
668     MOVN = Mips::MOVN_I64_I64;
669     MOVZ = Mips::MOVZ_I64_I64;
670     SELNEZ = Mips::SELNEZ64;
671     SELEQZ = Mips::SELEQZ64;
672   }
673 
674   Register OldVal = I->getOperand(0).getReg();
675   Register Ptr = I->getOperand(1).getReg();
676   Register Incr = I->getOperand(2).getReg();
677   Register Scratch = I->getOperand(3).getReg();
678 
679   unsigned Opcode = 0;
680   unsigned AND = 0;
681   unsigned NOR = 0;
682 
683   bool IsOr = false;
684   bool IsNand = false;
685   bool IsMin = false;
686   bool IsMax = false;
687   bool IsUnsigned = false;
688 
689   switch (I->getOpcode()) {
690   case Mips::ATOMIC_LOAD_ADD_I32_POSTRA:
691     Opcode = Mips::ADDu;
692     break;
693   case Mips::ATOMIC_LOAD_SUB_I32_POSTRA:
694     Opcode = Mips::SUBu;
695     break;
696   case Mips::ATOMIC_LOAD_AND_I32_POSTRA:
697     Opcode = Mips::AND;
698     break;
699   case Mips::ATOMIC_LOAD_OR_I32_POSTRA:
700     Opcode = Mips::OR;
701     break;
702   case Mips::ATOMIC_LOAD_XOR_I32_POSTRA:
703     Opcode = Mips::XOR;
704     break;
705   case Mips::ATOMIC_LOAD_NAND_I32_POSTRA:
706     IsNand = true;
707     AND = Mips::AND;
708     NOR = Mips::NOR;
709     break;
710   case Mips::ATOMIC_SWAP_I32_POSTRA:
711     IsOr = true;
712     break;
713   case Mips::ATOMIC_LOAD_ADD_I64_POSTRA:
714     Opcode = Mips::DADDu;
715     break;
716   case Mips::ATOMIC_LOAD_SUB_I64_POSTRA:
717     Opcode = Mips::DSUBu;
718     break;
719   case Mips::ATOMIC_LOAD_AND_I64_POSTRA:
720     Opcode = Mips::AND64;
721     break;
722   case Mips::ATOMIC_LOAD_OR_I64_POSTRA:
723     Opcode = Mips::OR64;
724     break;
725   case Mips::ATOMIC_LOAD_XOR_I64_POSTRA:
726     Opcode = Mips::XOR64;
727     break;
728   case Mips::ATOMIC_LOAD_NAND_I64_POSTRA:
729     IsNand = true;
730     AND = Mips::AND64;
731     NOR = Mips::NOR64;
732     break;
733   case Mips::ATOMIC_SWAP_I64_POSTRA:
734     IsOr = true;
735     break;
736   case Mips::ATOMIC_LOAD_UMIN_I32_POSTRA:
737   case Mips::ATOMIC_LOAD_UMIN_I64_POSTRA:
738     IsUnsigned = true;
739     [[fallthrough]];
740   case Mips::ATOMIC_LOAD_MIN_I32_POSTRA:
741   case Mips::ATOMIC_LOAD_MIN_I64_POSTRA:
742     IsMin = true;
743     break;
744   case Mips::ATOMIC_LOAD_UMAX_I32_POSTRA:
745   case Mips::ATOMIC_LOAD_UMAX_I64_POSTRA:
746     IsUnsigned = true;
747     [[fallthrough]];
748   case Mips::ATOMIC_LOAD_MAX_I32_POSTRA:
749   case Mips::ATOMIC_LOAD_MAX_I64_POSTRA:
750     IsMax = true;
751     break;
752   default:
753     llvm_unreachable("Unknown pseudo atomic!");
754   }
755 
756   const BasicBlock *LLVM_BB = BB.getBasicBlock();
757   MachineBasicBlock *loopMBB = MF->CreateMachineBasicBlock(LLVM_BB);
758   MachineBasicBlock *exitMBB = MF->CreateMachineBasicBlock(LLVM_BB);
759   MachineFunction::iterator It = ++BB.getIterator();
760   MF->insert(It, loopMBB);
761   MF->insert(It, exitMBB);
762 
763   exitMBB->splice(exitMBB->begin(), &BB, std::next(I), BB.end());
764   exitMBB->transferSuccessorsAndUpdatePHIs(&BB);
765 
766   BB.addSuccessor(loopMBB, BranchProbability::getOne());
767   loopMBB->addSuccessor(exitMBB);
768   loopMBB->addSuccessor(loopMBB);
769   loopMBB->normalizeSuccProbs();
770 
771   BuildMI(loopMBB, DL, TII->get(LL), OldVal).addReg(Ptr).addImm(0);
772   assert((OldVal != Ptr) && "Clobbered the wrong ptr reg!");
773   assert((OldVal != Incr) && "Clobbered the wrong reg!");
774   if (IsMin || IsMax) {
775 
776     assert(I->getNumOperands() == 5 &&
777            "Atomics min|max|umin|umax use an additional register");
778     MCRegister Scratch2 = I->getOperand(4).getReg().asMCReg();
779 
780     // On Mips64 result of slt is GPR32.
781     MCRegister Scratch2_32 =
782         (Size == 8) ? STI->getRegisterInfo()->getSubReg(Scratch2, Mips::sub_32)
783                     : Scratch2;
784 
785     unsigned SLTScratch2 = IsUnsigned ? SLTu : SLT;
786     unsigned SELIncr = IsMax ? SELNEZ : SELEQZ;
787     unsigned SELOldVal = IsMax ? SELEQZ : SELNEZ;
788     unsigned MOVIncr = IsMax ? MOVN : MOVZ;
789 
790     // unsigned: sltu Scratch2, oldVal, Incr
791     // signed:   slt Scratch2, oldVal, Incr
792     BuildMI(loopMBB, DL, TII->get(SLTScratch2), Scratch2_32)
793         .addReg(OldVal)
794         .addReg(Incr);
795 
796     if (STI->hasMips64r6() || STI->hasMips32r6()) {
797       // max: seleqz Scratch, OldVal, Scratch2
798       //      selnez Scratch2, Incr, Scratch2
799       //      or Scratch, Scratch, Scratch2
800       // min: selnez Scratch, OldVal, Scratch2
801       //      seleqz Scratch2, Incr, Scratch2
802       //      or Scratch, Scratch, Scratch2
803       BuildMI(loopMBB, DL, TII->get(SELOldVal), Scratch)
804           .addReg(OldVal)
805           .addReg(Scratch2);
806       BuildMI(loopMBB, DL, TII->get(SELIncr), Scratch2)
807           .addReg(Incr)
808           .addReg(Scratch2);
809       BuildMI(loopMBB, DL, TII->get(OR), Scratch)
810           .addReg(Scratch)
811           .addReg(Scratch2);
812     } else {
813       // max: move Scratch, OldVal
814       //      movn Scratch, Incr, Scratch2, Scratch
815       // min: move Scratch, OldVal
816       //      movz Scratch, Incr, Scratch2, Scratch
817       BuildMI(loopMBB, DL, TII->get(OR), Scratch)
818           .addReg(OldVal)
819           .addReg(ZERO);
820       BuildMI(loopMBB, DL, TII->get(MOVIncr), Scratch)
821           .addReg(Incr)
822           .addReg(Scratch2)
823           .addReg(Scratch);
824     }
825 
826   } else if (Opcode) {
827     BuildMI(loopMBB, DL, TII->get(Opcode), Scratch).addReg(OldVal).addReg(Incr);
828   } else if (IsNand) {
829     assert(AND && NOR &&
830            "Unknown nand instruction for atomic pseudo expansion");
831     BuildMI(loopMBB, DL, TII->get(AND), Scratch).addReg(OldVal).addReg(Incr);
832     BuildMI(loopMBB, DL, TII->get(NOR), Scratch).addReg(ZERO).addReg(Scratch);
833   } else {
834     assert(IsOr && OR && "Unknown instruction for atomic pseudo expansion!");
835     (void)IsOr;
836     BuildMI(loopMBB, DL, TII->get(OR), Scratch).addReg(Incr).addReg(ZERO);
837   }
838 
839   BuildMI(loopMBB, DL, TII->get(SC), Scratch)
840       .addReg(Scratch)
841       .addReg(Ptr)
842       .addImm(0);
843   BuildMI(loopMBB, DL, TII->get(BEQ))
844       .addReg(Scratch)
845       .addReg(ZERO)
846       .addMBB(loopMBB);
847 
848   NMBBI = BB.end();
849   I->eraseFromParent();
850 
851   LivePhysRegs LiveRegs;
852   computeAndAddLiveIns(LiveRegs, *loopMBB);
853   computeAndAddLiveIns(LiveRegs, *exitMBB);
854 
855   return true;
856 }
857 
858 bool MipsExpandPseudo::expandMI(MachineBasicBlock &MBB,
859                                 MachineBasicBlock::iterator MBBI,
860                                 MachineBasicBlock::iterator &NMBB) {
861 
862   bool Modified = false;
863 
864   switch (MBBI->getOpcode()) {
865   case Mips::ATOMIC_CMP_SWAP_I32_POSTRA:
866   case Mips::ATOMIC_CMP_SWAP_I64_POSTRA:
867     return expandAtomicCmpSwap(MBB, MBBI, NMBB);
868   case Mips::ATOMIC_CMP_SWAP_I8_POSTRA:
869   case Mips::ATOMIC_CMP_SWAP_I16_POSTRA:
870     return expandAtomicCmpSwapSubword(MBB, MBBI, NMBB);
871   case Mips::ATOMIC_SWAP_I8_POSTRA:
872   case Mips::ATOMIC_SWAP_I16_POSTRA:
873   case Mips::ATOMIC_LOAD_NAND_I8_POSTRA:
874   case Mips::ATOMIC_LOAD_NAND_I16_POSTRA:
875   case Mips::ATOMIC_LOAD_ADD_I8_POSTRA:
876   case Mips::ATOMIC_LOAD_ADD_I16_POSTRA:
877   case Mips::ATOMIC_LOAD_SUB_I8_POSTRA:
878   case Mips::ATOMIC_LOAD_SUB_I16_POSTRA:
879   case Mips::ATOMIC_LOAD_AND_I8_POSTRA:
880   case Mips::ATOMIC_LOAD_AND_I16_POSTRA:
881   case Mips::ATOMIC_LOAD_OR_I8_POSTRA:
882   case Mips::ATOMIC_LOAD_OR_I16_POSTRA:
883   case Mips::ATOMIC_LOAD_XOR_I8_POSTRA:
884   case Mips::ATOMIC_LOAD_XOR_I16_POSTRA:
885   case Mips::ATOMIC_LOAD_MIN_I8_POSTRA:
886   case Mips::ATOMIC_LOAD_MIN_I16_POSTRA:
887   case Mips::ATOMIC_LOAD_MAX_I8_POSTRA:
888   case Mips::ATOMIC_LOAD_MAX_I16_POSTRA:
889   case Mips::ATOMIC_LOAD_UMIN_I8_POSTRA:
890   case Mips::ATOMIC_LOAD_UMIN_I16_POSTRA:
891   case Mips::ATOMIC_LOAD_UMAX_I8_POSTRA:
892   case Mips::ATOMIC_LOAD_UMAX_I16_POSTRA:
893     return expandAtomicBinOpSubword(MBB, MBBI, NMBB);
894   case Mips::ATOMIC_LOAD_ADD_I32_POSTRA:
895   case Mips::ATOMIC_LOAD_SUB_I32_POSTRA:
896   case Mips::ATOMIC_LOAD_AND_I32_POSTRA:
897   case Mips::ATOMIC_LOAD_OR_I32_POSTRA:
898   case Mips::ATOMIC_LOAD_XOR_I32_POSTRA:
899   case Mips::ATOMIC_LOAD_NAND_I32_POSTRA:
900   case Mips::ATOMIC_SWAP_I32_POSTRA:
901   case Mips::ATOMIC_LOAD_MIN_I32_POSTRA:
902   case Mips::ATOMIC_LOAD_MAX_I32_POSTRA:
903   case Mips::ATOMIC_LOAD_UMIN_I32_POSTRA:
904   case Mips::ATOMIC_LOAD_UMAX_I32_POSTRA:
905     return expandAtomicBinOp(MBB, MBBI, NMBB, 4);
906   case Mips::ATOMIC_LOAD_ADD_I64_POSTRA:
907   case Mips::ATOMIC_LOAD_SUB_I64_POSTRA:
908   case Mips::ATOMIC_LOAD_AND_I64_POSTRA:
909   case Mips::ATOMIC_LOAD_OR_I64_POSTRA:
910   case Mips::ATOMIC_LOAD_XOR_I64_POSTRA:
911   case Mips::ATOMIC_LOAD_NAND_I64_POSTRA:
912   case Mips::ATOMIC_SWAP_I64_POSTRA:
913   case Mips::ATOMIC_LOAD_MIN_I64_POSTRA:
914   case Mips::ATOMIC_LOAD_MAX_I64_POSTRA:
915   case Mips::ATOMIC_LOAD_UMIN_I64_POSTRA:
916   case Mips::ATOMIC_LOAD_UMAX_I64_POSTRA:
917     return expandAtomicBinOp(MBB, MBBI, NMBB, 8);
918   default:
919     return Modified;
920   }
921 }
922 
923 bool MipsExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
924   bool Modified = false;
925 
926   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
927   while (MBBI != E) {
928     MachineBasicBlock::iterator NMBBI = std::next(MBBI);
929     Modified |= expandMI(MBB, MBBI, NMBBI);
930     MBBI = NMBBI;
931   }
932 
933   return Modified;
934 }
935 
936 bool MipsExpandPseudo::runOnMachineFunction(MachineFunction &MF) {
937   STI = &MF.getSubtarget<MipsSubtarget>();
938   TII = STI->getInstrInfo();
939 
940   bool Modified = false;
941   for (MachineBasicBlock &MBB : MF)
942     Modified |= expandMBB(MBB);
943 
944   if (Modified)
945     MF.RenumberBlocks();
946 
947   return Modified;
948 }
949 
950 /// createMipsExpandPseudoPass - returns an instance of the pseudo instruction
951 /// expansion pass.
952 FunctionPass *llvm::createMipsExpandPseudoPass() {
953   return new MipsExpandPseudo();
954 }
955