1 //===-- RISCVExpandPseudoInsts.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. This pass should be run after register allocation but before
12 // the post-regalloc scheduling pass.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "RISCV.h"
17 #include "RISCVInstrInfo.h"
18 #include "RISCVTargetMachine.h"
19 
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 RISCV_EXPAND_PSEUDO_NAME "RISCV pseudo instruction expansion pass"
27 
28 namespace {
29 
30 class RISCVExpandPseudo : public MachineFunctionPass {
31 public:
32   const RISCVInstrInfo *TII;
33   static char ID;
34 
35   RISCVExpandPseudo() : MachineFunctionPass(ID) {
36     initializeRISCVExpandPseudoPass(*PassRegistry::getPassRegistry());
37   }
38 
39   bool runOnMachineFunction(MachineFunction &MF) override;
40 
41   StringRef getPassName() const override { return RISCV_EXPAND_PSEUDO_NAME; }
42 
43 private:
44   bool expandMBB(MachineBasicBlock &MBB);
45   bool expandMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
46                 MachineBasicBlock::iterator &NextMBBI);
47   bool expandAtomicBinOp(MachineBasicBlock &MBB,
48                          MachineBasicBlock::iterator MBBI, AtomicRMWInst::BinOp,
49                          bool IsMasked, int Width,
50                          MachineBasicBlock::iterator &NextMBBI);
51   bool expandAtomicMinMaxOp(MachineBasicBlock &MBB,
52                             MachineBasicBlock::iterator MBBI,
53                             AtomicRMWInst::BinOp, bool IsMasked, int Width,
54                             MachineBasicBlock::iterator &NextMBBI);
55 };
56 
57 char RISCVExpandPseudo::ID = 0;
58 
59 bool RISCVExpandPseudo::runOnMachineFunction(MachineFunction &MF) {
60   TII = static_cast<const RISCVInstrInfo *>(MF.getSubtarget().getInstrInfo());
61   bool Modified = false;
62   for (auto &MBB : MF)
63     Modified |= expandMBB(MBB);
64   return Modified;
65 }
66 
67 bool RISCVExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
68   bool Modified = false;
69 
70   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
71   while (MBBI != E) {
72     MachineBasicBlock::iterator NMBBI = std::next(MBBI);
73     Modified |= expandMI(MBB, MBBI, NMBBI);
74     MBBI = NMBBI;
75   }
76 
77   return Modified;
78 }
79 
80 bool RISCVExpandPseudo::expandMI(MachineBasicBlock &MBB,
81                                  MachineBasicBlock::iterator MBBI,
82                                  MachineBasicBlock::iterator &NextMBBI) {
83   switch (MBBI->getOpcode()) {
84   case RISCV::PseudoAtomicLoadNand32:
85     return expandAtomicBinOp(MBB, MBBI, AtomicRMWInst::Nand, false, 32,
86                              NextMBBI);
87   case RISCV::PseudoMaskedAtomicSwap32:
88     return expandAtomicBinOp(MBB, MBBI, AtomicRMWInst::Xchg, true, 32,
89                              NextMBBI);
90   case RISCV::PseudoMaskedAtomicLoadAdd32:
91     return expandAtomicBinOp(MBB, MBBI, AtomicRMWInst::Add, true, 32, NextMBBI);
92   case RISCV::PseudoMaskedAtomicLoadSub32:
93     return expandAtomicBinOp(MBB, MBBI, AtomicRMWInst::Sub, true, 32, NextMBBI);
94   case RISCV::PseudoMaskedAtomicLoadNand32:
95     return expandAtomicBinOp(MBB, MBBI, AtomicRMWInst::Nand, true, 32,
96                              NextMBBI);
97   case RISCV::PseudoMaskedAtomicLoadMax32:
98     return expandAtomicMinMaxOp(MBB, MBBI, AtomicRMWInst::Max, true, 32,
99                                 NextMBBI);
100   case RISCV::PseudoMaskedAtomicLoadMin32:
101     return expandAtomicMinMaxOp(MBB, MBBI, AtomicRMWInst::Min, true, 32,
102                                 NextMBBI);
103   case RISCV::PseudoMaskedAtomicLoadUMax32:
104     return expandAtomicMinMaxOp(MBB, MBBI, AtomicRMWInst::UMax, true, 32,
105                                 NextMBBI);
106   case RISCV::PseudoMaskedAtomicLoadUMin32:
107     return expandAtomicMinMaxOp(MBB, MBBI, AtomicRMWInst::UMin, true, 32,
108                                 NextMBBI);
109   }
110 
111   return false;
112 }
113 
114 static unsigned getLRForRMW32(AtomicOrdering Ordering) {
115   switch (Ordering) {
116   default:
117     llvm_unreachable("Unexpected AtomicOrdering");
118   case AtomicOrdering::Monotonic:
119     return RISCV::LR_W;
120   case AtomicOrdering::Acquire:
121     return RISCV::LR_W_AQ;
122   case AtomicOrdering::Release:
123     return RISCV::LR_W;
124   case AtomicOrdering::AcquireRelease:
125     return RISCV::LR_W_AQ;
126   case AtomicOrdering::SequentiallyConsistent:
127     return RISCV::LR_W_AQ_RL;
128   }
129 }
130 
131 static unsigned getSCForRMW32(AtomicOrdering Ordering) {
132   switch (Ordering) {
133   default:
134     llvm_unreachable("Unexpected AtomicOrdering");
135   case AtomicOrdering::Monotonic:
136     return RISCV::SC_W;
137   case AtomicOrdering::Acquire:
138     return RISCV::SC_W;
139   case AtomicOrdering::Release:
140     return RISCV::SC_W_RL;
141   case AtomicOrdering::AcquireRelease:
142     return RISCV::SC_W_RL;
143   case AtomicOrdering::SequentiallyConsistent:
144     return RISCV::SC_W_AQ_RL;
145   }
146 }
147 
148 static void doAtomicBinOpExpansion(const RISCVInstrInfo *TII, MachineInstr &MI,
149                                    DebugLoc DL, MachineBasicBlock *ThisMBB,
150                                    MachineBasicBlock *LoopMBB,
151                                    MachineBasicBlock *DoneMBB,
152                                    AtomicRMWInst::BinOp BinOp, int Width) {
153   assert(Width == 32 && "RV64 atomic expansion currently unsupported");
154   unsigned DestReg = MI.getOperand(0).getReg();
155   unsigned ScratchReg = MI.getOperand(1).getReg();
156   unsigned AddrReg = MI.getOperand(2).getReg();
157   unsigned IncrReg = MI.getOperand(3).getReg();
158   AtomicOrdering Ordering =
159       static_cast<AtomicOrdering>(MI.getOperand(4).getImm());
160 
161   // .loop:
162   //   lr.w dest, (addr)
163   //   binop scratch, dest, val
164   //   sc.w scratch, scratch, (addr)
165   //   bnez scratch, loop
166   BuildMI(LoopMBB, DL, TII->get(getLRForRMW32(Ordering)), DestReg)
167       .addReg(AddrReg);
168   switch (BinOp) {
169   default:
170     llvm_unreachable("Unexpected AtomicRMW BinOp");
171   case AtomicRMWInst::Nand:
172     BuildMI(LoopMBB, DL, TII->get(RISCV::AND), ScratchReg)
173         .addReg(DestReg)
174         .addReg(IncrReg);
175     BuildMI(LoopMBB, DL, TII->get(RISCV::XORI), ScratchReg)
176         .addReg(ScratchReg)
177         .addImm(-1);
178     break;
179   }
180   BuildMI(LoopMBB, DL, TII->get(getSCForRMW32(Ordering)), ScratchReg)
181       .addReg(AddrReg)
182       .addReg(ScratchReg);
183   BuildMI(LoopMBB, DL, TII->get(RISCV::BNE))
184       .addReg(ScratchReg)
185       .addReg(RISCV::X0)
186       .addMBB(LoopMBB);
187 }
188 
189 static void insertMaskedMerge(const RISCVInstrInfo *TII, DebugLoc DL,
190                               MachineBasicBlock *MBB, unsigned DestReg,
191                               unsigned OldValReg, unsigned NewValReg,
192                               unsigned MaskReg, unsigned ScratchReg) {
193   assert(OldValReg != ScratchReg && "OldValReg and ScratchReg must be unique");
194   assert(OldValReg != MaskReg && "OldValReg and MaskReg must be unique");
195   assert(ScratchReg != MaskReg && "ScratchReg and MaskReg must be unique");
196 
197   // We select bits from newval and oldval using:
198   // https://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge
199   // r = oldval ^ ((oldval ^ newval) & masktargetdata);
200   BuildMI(MBB, DL, TII->get(RISCV::XOR), ScratchReg)
201       .addReg(OldValReg)
202       .addReg(NewValReg);
203   BuildMI(MBB, DL, TII->get(RISCV::AND), ScratchReg)
204       .addReg(ScratchReg)
205       .addReg(MaskReg);
206   BuildMI(MBB, DL, TII->get(RISCV::XOR), DestReg)
207       .addReg(OldValReg)
208       .addReg(ScratchReg);
209 }
210 
211 static void doMaskedAtomicBinOpExpansion(
212     const RISCVInstrInfo *TII, MachineInstr &MI, DebugLoc DL,
213     MachineBasicBlock *ThisMBB, MachineBasicBlock *LoopMBB,
214     MachineBasicBlock *DoneMBB, AtomicRMWInst::BinOp BinOp, int Width) {
215   assert(Width == 32 && "RV64 atomic expansion currently unsupported");
216   unsigned DestReg = MI.getOperand(0).getReg();
217   unsigned ScratchReg = MI.getOperand(1).getReg();
218   unsigned AddrReg = MI.getOperand(2).getReg();
219   unsigned IncrReg = MI.getOperand(3).getReg();
220   unsigned MaskReg = MI.getOperand(4).getReg();
221   AtomicOrdering Ordering =
222       static_cast<AtomicOrdering>(MI.getOperand(5).getImm());
223 
224   // .loop:
225   //   lr.w destreg, (alignedaddr)
226   //   binop scratch, destreg, incr
227   //   xor scratch, destreg, scratch
228   //   and scratch, scratch, masktargetdata
229   //   xor scratch, destreg, scratch
230   //   sc.w scratch, scratch, (alignedaddr)
231   //   bnez scratch, loop
232   BuildMI(LoopMBB, DL, TII->get(getLRForRMW32(Ordering)), DestReg)
233       .addReg(AddrReg);
234   switch (BinOp) {
235   default:
236     llvm_unreachable("Unexpected AtomicRMW BinOp");
237   case AtomicRMWInst::Xchg:
238     BuildMI(LoopMBB, DL, TII->get(RISCV::ADD), ScratchReg)
239         .addReg(RISCV::X0)
240         .addReg(IncrReg);
241     break;
242   case AtomicRMWInst::Add:
243     BuildMI(LoopMBB, DL, TII->get(RISCV::ADD), ScratchReg)
244         .addReg(DestReg)
245         .addReg(IncrReg);
246     break;
247   case AtomicRMWInst::Sub:
248     BuildMI(LoopMBB, DL, TII->get(RISCV::SUB), ScratchReg)
249         .addReg(DestReg)
250         .addReg(IncrReg);
251     break;
252   case AtomicRMWInst::Nand:
253     BuildMI(LoopMBB, DL, TII->get(RISCV::AND), ScratchReg)
254         .addReg(DestReg)
255         .addReg(IncrReg);
256     BuildMI(LoopMBB, DL, TII->get(RISCV::XORI), ScratchReg)
257         .addReg(ScratchReg)
258         .addImm(-1);
259     break;
260   }
261 
262   insertMaskedMerge(TII, DL, LoopMBB, ScratchReg, DestReg, ScratchReg, MaskReg,
263                     ScratchReg);
264 
265   BuildMI(LoopMBB, DL, TII->get(getSCForRMW32(Ordering)), ScratchReg)
266       .addReg(AddrReg)
267       .addReg(ScratchReg);
268   BuildMI(LoopMBB, DL, TII->get(RISCV::BNE))
269       .addReg(ScratchReg)
270       .addReg(RISCV::X0)
271       .addMBB(LoopMBB);
272 }
273 
274 bool RISCVExpandPseudo::expandAtomicBinOp(
275     MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
276     AtomicRMWInst::BinOp BinOp, bool IsMasked, int Width,
277     MachineBasicBlock::iterator &NextMBBI) {
278   MachineInstr &MI = *MBBI;
279   DebugLoc DL = MI.getDebugLoc();
280 
281   MachineFunction *MF = MBB.getParent();
282   auto LoopMBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
283   auto DoneMBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
284 
285   // Insert new MBBs.
286   MF->insert(++MBB.getIterator(), LoopMBB);
287   MF->insert(++LoopMBB->getIterator(), DoneMBB);
288 
289   // Set up successors and transfer remaining instructions to DoneMBB.
290   LoopMBB->addSuccessor(LoopMBB);
291   LoopMBB->addSuccessor(DoneMBB);
292   DoneMBB->splice(DoneMBB->end(), &MBB, MI, MBB.end());
293   DoneMBB->transferSuccessors(&MBB);
294   MBB.addSuccessor(LoopMBB);
295 
296   if (!IsMasked)
297     doAtomicBinOpExpansion(TII, MI, DL, &MBB, LoopMBB, DoneMBB, BinOp, Width);
298   else
299     doMaskedAtomicBinOpExpansion(TII, MI, DL, &MBB, LoopMBB, DoneMBB, BinOp,
300                                  Width);
301 
302   NextMBBI = MBB.end();
303   MI.eraseFromParent();
304 
305   LivePhysRegs LiveRegs;
306   computeAndAddLiveIns(LiveRegs, *LoopMBB);
307   computeAndAddLiveIns(LiveRegs, *DoneMBB);
308 
309   return true;
310 }
311 
312 static void insertSext(const RISCVInstrInfo *TII, DebugLoc DL,
313                        MachineBasicBlock *MBB, unsigned ValReg,
314                        unsigned ShamtReg) {
315   BuildMI(MBB, DL, TII->get(RISCV::SLL), ValReg)
316       .addReg(ValReg)
317       .addReg(ShamtReg);
318   BuildMI(MBB, DL, TII->get(RISCV::SRA), ValReg)
319       .addReg(ValReg)
320       .addReg(ShamtReg);
321 }
322 
323 bool RISCVExpandPseudo::expandAtomicMinMaxOp(
324     MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
325     AtomicRMWInst::BinOp BinOp, bool IsMasked, int Width,
326     MachineBasicBlock::iterator &NextMBBI) {
327   assert(IsMasked == true &&
328          "Should only need to expand masked atomic max/min");
329   assert(Width == 32 && "RV64 atomic expansion currently unsupported");
330 
331   MachineInstr &MI = *MBBI;
332   DebugLoc DL = MI.getDebugLoc();
333   MachineFunction *MF = MBB.getParent();
334   auto LoopHeadMBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
335   auto LoopIfBodyMBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
336   auto LoopTailMBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
337   auto DoneMBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
338 
339   // Insert new MBBs.
340   MF->insert(++MBB.getIterator(), LoopHeadMBB);
341   MF->insert(++LoopHeadMBB->getIterator(), LoopIfBodyMBB);
342   MF->insert(++LoopIfBodyMBB->getIterator(), LoopTailMBB);
343   MF->insert(++LoopTailMBB->getIterator(), DoneMBB);
344 
345   // Set up successors and transfer remaining instructions to DoneMBB.
346   LoopHeadMBB->addSuccessor(LoopIfBodyMBB);
347   LoopHeadMBB->addSuccessor(LoopTailMBB);
348   LoopIfBodyMBB->addSuccessor(LoopTailMBB);
349   LoopTailMBB->addSuccessor(LoopHeadMBB);
350   LoopTailMBB->addSuccessor(DoneMBB);
351   DoneMBB->splice(DoneMBB->end(), &MBB, MI, MBB.end());
352   DoneMBB->transferSuccessors(&MBB);
353   MBB.addSuccessor(LoopHeadMBB);
354 
355   unsigned DestReg = MI.getOperand(0).getReg();
356   unsigned Scratch1Reg = MI.getOperand(1).getReg();
357   unsigned Scratch2Reg = MI.getOperand(2).getReg();
358   unsigned AddrReg = MI.getOperand(3).getReg();
359   unsigned IncrReg = MI.getOperand(4).getReg();
360   unsigned MaskReg = MI.getOperand(5).getReg();
361   bool IsSigned = BinOp == AtomicRMWInst::Min || BinOp == AtomicRMWInst::Max;
362   AtomicOrdering Ordering =
363       static_cast<AtomicOrdering>(MI.getOperand(IsSigned ? 7 : 6).getImm());
364 
365   //
366   // .loophead:
367   //   lr.w destreg, (alignedaddr)
368   //   and scratch2, destreg, mask
369   //   mv scratch1, destreg
370   //   [sext scratch2 if signed min/max]
371   //   ifnochangeneeded scratch2, incr, .looptail
372   BuildMI(LoopHeadMBB, DL, TII->get(getLRForRMW32(Ordering)), DestReg)
373       .addReg(AddrReg);
374   BuildMI(LoopHeadMBB, DL, TII->get(RISCV::AND), Scratch2Reg)
375       .addReg(DestReg)
376       .addReg(MaskReg);
377   BuildMI(LoopHeadMBB, DL, TII->get(RISCV::ADDI), Scratch1Reg)
378       .addReg(DestReg)
379       .addImm(0);
380 
381   switch (BinOp) {
382   default:
383     llvm_unreachable("Unexpected AtomicRMW BinOp");
384   case AtomicRMWInst::Max: {
385     insertSext(TII, DL, LoopHeadMBB, Scratch2Reg, MI.getOperand(6).getReg());
386     BuildMI(LoopHeadMBB, DL, TII->get(RISCV::BGE))
387         .addReg(Scratch2Reg)
388         .addReg(IncrReg)
389         .addMBB(LoopTailMBB);
390     break;
391   }
392   case AtomicRMWInst::Min: {
393     insertSext(TII, DL, LoopHeadMBB, Scratch2Reg, MI.getOperand(6).getReg());
394     BuildMI(LoopHeadMBB, DL, TII->get(RISCV::BGE))
395         .addReg(IncrReg)
396         .addReg(Scratch2Reg)
397         .addMBB(LoopTailMBB);
398     break;
399   }
400   case AtomicRMWInst::UMax:
401     BuildMI(LoopHeadMBB, DL, TII->get(RISCV::BGEU))
402         .addReg(Scratch2Reg)
403         .addReg(IncrReg)
404         .addMBB(LoopTailMBB);
405     break;
406   case AtomicRMWInst::UMin:
407     BuildMI(LoopHeadMBB, DL, TII->get(RISCV::BGEU))
408         .addReg(IncrReg)
409         .addReg(Scratch2Reg)
410         .addMBB(LoopTailMBB);
411     break;
412   }
413 
414   // .loopifbody:
415   //   xor scratch1, destreg, incr
416   //   and scratch1, scratch1, mask
417   //   xor scratch1, destreg, scratch1
418   insertMaskedMerge(TII, DL, LoopIfBodyMBB, Scratch1Reg, DestReg, IncrReg,
419                     MaskReg, Scratch1Reg);
420 
421   // .looptail:
422   //   sc.w scratch1, scratch1, (addr)
423   //   bnez scratch1, loop
424   BuildMI(LoopTailMBB, DL, TII->get(getSCForRMW32(Ordering)), Scratch1Reg)
425       .addReg(AddrReg)
426       .addReg(Scratch1Reg);
427   BuildMI(LoopTailMBB, DL, TII->get(RISCV::BNE))
428       .addReg(Scratch1Reg)
429       .addReg(RISCV::X0)
430       .addMBB(LoopHeadMBB);
431 
432   NextMBBI = MBB.end();
433   MI.eraseFromParent();
434 
435   LivePhysRegs LiveRegs;
436   computeAndAddLiveIns(LiveRegs, *LoopHeadMBB);
437   computeAndAddLiveIns(LiveRegs, *LoopIfBodyMBB);
438   computeAndAddLiveIns(LiveRegs, *LoopTailMBB);
439   computeAndAddLiveIns(LiveRegs, *DoneMBB);
440 
441   return true;
442 }
443 
444 } // end of anonymous namespace
445 
446 INITIALIZE_PASS(RISCVExpandPseudo, "riscv-expand-pseudo",
447                 RISCV_EXPAND_PSEUDO_NAME, false, false)
448 namespace llvm {
449 
450 FunctionPass *createRISCVExpandPseudoPass() { return new RISCVExpandPseudo(); }
451 
452 } // end of namespace llvm
453