1 //===-- MipsExpandPseudoInsts.cpp - Expand pseudo instructions ------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains a pass that expands pseudo instructions into target
11 // instructions to allow proper scheduling, if-conversion, and other late
12 // optimizations. This pass should be run after register allocation but before
13 // the post-regalloc scheduling pass.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "Mips.h"
18 #include "MipsInstrInfo.h"
19 #include "MipsSubtarget.h"
20 #include "llvm/CodeGen/LivePhysRegs.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "mips-pseudo"
27 
28 namespace {
29   class MipsExpandPseudo : public MachineFunctionPass {
30   public:
31     static char ID;
32     MipsExpandPseudo() : MachineFunctionPass(ID) {}
33 
34     const MipsInstrInfo *TII;
35     const MipsSubtarget *STI;
36 
37     bool runOnMachineFunction(MachineFunction &Fn) override;
38 
39     MachineFunctionProperties getRequiredProperties() const override {
40       return MachineFunctionProperties().set(
41           MachineFunctionProperties::Property::NoVRegs);
42     }
43 
44     StringRef getPassName() const override {
45       return "Mips pseudo instruction expansion pass";
46     }
47 
48   private:
49     bool expandAtomicCmpSwap(MachineBasicBlock &MBB,
50                              MachineBasicBlock::iterator MBBI,
51                              MachineBasicBlock::iterator &NextMBBI);
52     bool expandAtomicCmpSwapSubword(MachineBasicBlock &MBB,
53                                     MachineBasicBlock::iterator MBBI,
54                                     MachineBasicBlock::iterator &NextMBBI);
55     bool expandMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
56                   MachineBasicBlock::iterator &NMBB);
57     bool expandMBB(MachineBasicBlock &MBB);
58    };
59   char MipsExpandPseudo::ID = 0;
60 }
61 
62 static void addPostLoopLiveIns(MachineBasicBlock *MBB, LivePhysRegs &LiveRegs) {
63   for (auto I = LiveRegs.begin(); I != LiveRegs.end(); ++I)
64     MBB->addLiveIn(*I);
65 }
66 
67 bool MipsExpandPseudo::expandAtomicCmpSwapSubword(
68     MachineBasicBlock &BB, MachineBasicBlock::iterator I,
69     MachineBasicBlock::iterator &NMBBI) {
70 
71   MachineFunction *MF = BB.getParent();
72 
73   const bool ArePtrs64bit = STI->getABI().ArePtrs64bit();
74   DebugLoc DL = I->getDebugLoc();
75   unsigned LL, SC;
76 
77   unsigned ZERO = Mips::ZERO;
78   unsigned BNE = Mips::BNE;
79   unsigned BEQ = Mips::BEQ;
80   unsigned SEOp =
81       I->getOpcode() == Mips::ATOMIC_CMP_SWAP_I8_FRAG ? Mips::SEB : Mips::SEH;
82 
83   if (STI->inMicroMipsMode()) {
84     LL = Mips::LL_MM;
85     SC = Mips::SC_MM;
86   } else {
87     LL = STI->hasMips32r6() ? (ArePtrs64bit ? Mips::LL64_R6 : Mips::LL_R6)
88                             : (ArePtrs64bit ? Mips::LL64 : Mips::LL);
89     SC = STI->hasMips32r6() ? (ArePtrs64bit ? Mips::SC64_R6 : Mips::SC_R6)
90                             : (ArePtrs64bit ? Mips::SC64 : Mips::SC);
91   }
92 
93   unsigned Dest = I->getOperand(0).getReg();
94   unsigned Ptr = I->getOperand(1).getReg();
95   unsigned Mask = I->getOperand(2).getReg();
96   unsigned ShiftCmpVal = I->getOperand(3).getReg();
97   unsigned Mask2 = I->getOperand(4).getReg();
98   unsigned ShiftNewVal = I->getOperand(5).getReg();
99   unsigned ShiftAmnt = I->getOperand(6).getReg();
100 
101   LivePhysRegs LiveRegs(&TII->getRegisterInfo());
102   for (auto MBBI = std::prev(BB.end()); MBBI != I; --MBBI)
103     LiveRegs.stepBackward(*MBBI);
104 
105   // insert new blocks after the current block
106   const BasicBlock *LLVM_BB = BB.getBasicBlock();
107   MachineBasicBlock *loop1MBB = MF->CreateMachineBasicBlock(LLVM_BB);
108   MachineBasicBlock *loop2MBB = MF->CreateMachineBasicBlock(LLVM_BB);
109   MachineBasicBlock *sinkMBB = MF->CreateMachineBasicBlock(LLVM_BB);
110   MachineBasicBlock *exitMBB = MF->CreateMachineBasicBlock(LLVM_BB);
111   MachineFunction::iterator It = ++BB.getIterator();
112   MF->insert(It, loop1MBB);
113   MF->insert(It, loop2MBB);
114   MF->insert(It, sinkMBB);
115   MF->insert(It, exitMBB);
116 
117   // Transfer the remainder of BB and its successor edges to exitMBB.
118   exitMBB->splice(exitMBB->begin(), &BB,
119                   std::next(MachineBasicBlock::iterator(I)), BB.end());
120   exitMBB->transferSuccessorsAndUpdatePHIs(&BB);
121 
122   //  thisMBB:
123   //    ...
124   //    fallthrough --> loop1MBB
125   BB.addSuccessor(loop1MBB, BranchProbability::getOne());
126   loop1MBB->addSuccessor(sinkMBB);
127   loop1MBB->addSuccessor(loop2MBB);
128   loop2MBB->addSuccessor(loop1MBB);
129   loop2MBB->addSuccessor(sinkMBB);
130   sinkMBB->addSuccessor(exitMBB, BranchProbability::getOne());
131 
132   // loop1MBB:
133   //   ll dest, 0(ptr)
134   //   and Mask', dest, Mask
135   //   bne Mask', ShiftCmpVal, exitMBB
136   BuildMI(loop1MBB, DL, TII->get(LL), Dest).addReg(Ptr).addImm(0);
137   BuildMI(loop1MBB, DL, TII->get(Mips::AND), Mask)
138       .addReg(Dest)
139       .addReg(Mask);
140   BuildMI(loop1MBB, DL, TII->get(BNE))
141     .addReg(Mask).addReg(ShiftCmpVal).addMBB(sinkMBB);
142   loop1MBB->addLiveIn(Ptr);
143   loop1MBB->addLiveIn(Mask);
144   loop1MBB->addLiveIn(ShiftCmpVal);
145 
146   // loop2MBB:
147   //   and dest, dest, mask2
148   //   or dest, dest, ShiftNewVal
149   //   sc dest, dest, 0(ptr)
150   //   beq dest, $0, loop1MBB
151   BuildMI(loop2MBB, DL, TII->get(Mips::AND), Dest)
152       .addReg(Dest, RegState::Kill)
153       .addReg(Mask2);
154   BuildMI(loop2MBB, DL, TII->get(Mips::OR), Dest)
155       .addReg(Dest, RegState::Kill)
156       .addReg(ShiftNewVal);
157   BuildMI(loop2MBB, DL, TII->get(SC), Dest)
158       .addReg(Dest, RegState::Kill)
159       .addReg(Ptr)
160       .addImm(0);
161   BuildMI(loop2MBB, DL, TII->get(BEQ))
162       .addReg(Dest, RegState::Kill)
163       .addReg(ZERO)
164       .addMBB(loop1MBB);
165   loop2MBB->addLiveIn(Ptr);
166   loop2MBB->addLiveIn(Mask2);
167   loop2MBB->addLiveIn(Dest);
168   loop2MBB->addLiveIn(ShiftNewVal);
169 
170   //  sinkMBB:
171   //    srl     srlres, Mask', shiftamt
172   //    sign_extend dest,srlres
173   BuildMI(sinkMBB, DL, TII->get(Mips::SRLV), Dest)
174       .addReg(Mask)
175       .addReg(ShiftAmnt);
176   if (STI->hasMips32r2()) {
177     BuildMI(sinkMBB, DL, TII->get(SEOp), Dest).addReg(Dest);
178   } else {
179     const unsigned ShiftImm =
180         I->getOpcode() == Mips::ATOMIC_CMP_SWAP_I16_FRAG ? 16 : 24;
181     BuildMI(sinkMBB, DL, TII->get(Mips::SLL), Dest)
182         .addReg(Dest, RegState::Kill)
183         .addImm(ShiftImm);
184     BuildMI(sinkMBB, DL, TII->get(Mips::SRA), Dest)
185         .addReg(Dest, RegState::Kill)
186         .addImm(ShiftImm);
187   }
188   sinkMBB->addLiveIn(Mask);
189   sinkMBB->addLiveIn(ShiftAmnt);
190 
191   addPostLoopLiveIns(exitMBB, LiveRegs);
192   exitMBB->addLiveIn(Dest);
193 
194   NMBBI = BB.end();
195   I->eraseFromParent();
196   return true;
197 }
198 
199 bool MipsExpandPseudo::expandAtomicCmpSwap(MachineBasicBlock &BB,
200                                            MachineBasicBlock::iterator I,
201                                            MachineBasicBlock::iterator &NMBBI) {
202 
203   const unsigned Size = I->getOpcode() == Mips::ATOMIC_CMP_SWAP_I32 ? 4 : 8;
204   MachineFunction *MF = BB.getParent();
205 
206   const bool ArePtrs64bit = STI->getABI().ArePtrs64bit();
207   DebugLoc DL = I->getDebugLoc();
208 
209   LivePhysRegs LiveRegs(&TII->getRegisterInfo());
210   LiveRegs.addLiveOuts(BB);
211   for (auto MBBI = std::prev(BB.end()); MBBI != I; --MBBI)
212     LiveRegs.stepBackward(*MBBI);
213 
214   unsigned LL, SC, ZERO, BNE, BEQ;
215 
216   if (Size == 4) {
217     if (STI->inMicroMipsMode()) {
218       LL = Mips::LL_MM;
219       SC = Mips::SC_MM;
220     } else {
221       LL = STI->hasMips32r6()
222                ? (ArePtrs64bit ? Mips::LL64_R6 : Mips::LL_R6)
223                : (ArePtrs64bit ? Mips::LL64 : Mips::LL);
224       SC = STI->hasMips32r6()
225                ? (ArePtrs64bit ? Mips::SC64_R6 : Mips::SC_R6)
226                : (ArePtrs64bit ? Mips::SC64 : Mips::SC);
227     }
228 
229     ZERO = Mips::ZERO;
230     BNE = Mips::BNE;
231     BEQ = Mips::BEQ;
232   } else {
233     LL = STI->hasMips64r6() ? Mips::LLD_R6 : Mips::LLD;
234     SC = STI->hasMips64r6() ? Mips::SCD_R6 : Mips::SCD;
235     ZERO = Mips::ZERO_64;
236     BNE = Mips::BNE64;
237     BEQ = Mips::BEQ64;
238   }
239 
240   unsigned Dest = I->getOperand(0).getReg();
241   unsigned Ptr = I->getOperand(1).getReg();
242   unsigned OldVal = I->getOperand(2).getReg();
243   unsigned NewVal = I->getOperand(3).getReg();
244 
245   // insert new blocks after the current block
246   const BasicBlock *LLVM_BB = BB.getBasicBlock();
247   MachineBasicBlock *loop1MBB = MF->CreateMachineBasicBlock(LLVM_BB);
248   MachineBasicBlock *loop2MBB = MF->CreateMachineBasicBlock(LLVM_BB);
249   MachineBasicBlock *exitMBB = MF->CreateMachineBasicBlock(LLVM_BB);
250   MachineFunction::iterator It = ++BB.getIterator();
251   MF->insert(It, loop1MBB);
252   MF->insert(It, loop2MBB);
253   MF->insert(It, exitMBB);
254 
255   // Transfer the remainder of BB and its successor edges to exitMBB.
256   exitMBB->splice(exitMBB->begin(), &BB,
257                   std::next(MachineBasicBlock::iterator(I)), BB.end());
258   exitMBB->transferSuccessorsAndUpdatePHIs(&BB);
259 
260   //  thisMBB:
261   //    ...
262   //    fallthrough --> loop1MBB
263   BB.addSuccessor(loop1MBB, BranchProbability::getOne());
264   loop1MBB->addSuccessor(exitMBB);
265   loop1MBB->addSuccessor(loop2MBB);
266   loop2MBB->addSuccessor(loop1MBB);
267   loop2MBB->addSuccessor(exitMBB);
268 
269   // loop1MBB:
270   //   ll dest, 0(ptr)
271   //   bne dest, oldval, exitMBB
272   BuildMI(loop1MBB, DL, TII->get(LL), Dest).addReg(Ptr).addImm(0);
273   BuildMI(loop1MBB, DL, TII->get(BNE))
274     .addReg(Dest).addReg(OldVal).addMBB(exitMBB);
275   loop1MBB->addLiveIn(Ptr);
276   loop1MBB->addLiveIn(OldVal);
277 
278   // loop2MBB:
279   //   sc success, newval, 0(ptr)
280   //   beq success, $0, loop1MBB
281   BuildMI(loop2MBB, DL, TII->get(SC), NewVal)
282     .addReg(NewVal).addReg(Ptr).addImm(0);
283   BuildMI(loop2MBB, DL, TII->get(BEQ))
284     .addReg(NewVal, RegState::Kill).addReg(ZERO).addMBB(loop1MBB);
285   loop2MBB->addLiveIn(Ptr);
286   loop2MBB->addLiveIn(NewVal);
287 
288   addPostLoopLiveIns(exitMBB, LiveRegs);
289 
290   NMBBI = BB.end();
291   I->eraseFromParent();
292   return true;
293 }
294 
295 bool MipsExpandPseudo::expandMI(MachineBasicBlock &MBB,
296                                 MachineBasicBlock::iterator MBBI,
297                                 MachineBasicBlock::iterator &NMBB) {
298 
299   bool Modified = false;
300   switch (MBBI->getOpcode()) {
301     case Mips::ATOMIC_CMP_SWAP_I32:
302     case Mips::ATOMIC_CMP_SWAP_I64:
303       return expandAtomicCmpSwap(MBB, MBBI, NMBB);
304     case Mips::ATOMIC_CMP_SWAP_I8_FRAG:
305     case Mips::ATOMIC_CMP_SWAP_I16_FRAG:
306       return expandAtomicCmpSwapSubword(MBB, MBBI, NMBB);
307     default:
308       return Modified;
309   }
310 }
311 
312 bool MipsExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
313   bool Modified = false;
314 
315   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
316   while (MBBI != E) {
317     MachineBasicBlock::iterator NMBBI = std::next(MBBI);
318     Modified |= expandMI(MBB, MBBI, NMBBI);
319     MBBI = NMBBI;
320   }
321 
322   return Modified;
323 }
324 
325 bool MipsExpandPseudo::runOnMachineFunction(MachineFunction &MF) {
326   STI = &static_cast<const MipsSubtarget &>(MF.getSubtarget());
327   TII = STI->getInstrInfo();
328 
329   bool Modified = false;
330   for (MachineFunction::iterator MFI = MF.begin(), E = MF.end(); MFI != E;
331        ++MFI)
332     Modified |= expandMBB(*MFI);
333 
334   return Modified;
335 }
336 
337 /// createMipsExpandPseudoPass - returns an instance of the pseudo instruction
338 /// expansion pass.
339 FunctionPass *llvm::createMipsExpandPseudoPass() {
340   return new MipsExpandPseudo();
341 }
342