1 //===-- RISCVInstrInfo.cpp - RISCV Instruction Information ------*- C++ -*-===//
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 the RISCV implementation of the TargetInstrInfo class.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "RISCVInstrInfo.h"
15 #include "RISCV.h"
16 #include "RISCVSubtarget.h"
17 #include "RISCVTargetMachine.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineInstrBuilder.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/CodeGen/RegisterScavenging.h"
24 #include "llvm/Support/ErrorHandling.h"
25 #include "llvm/Support/TargetRegistry.h"
26 
27 #define GET_INSTRINFO_CTOR_DTOR
28 #include "RISCVGenInstrInfo.inc"
29 
30 using namespace llvm;
31 
32 RISCVInstrInfo::RISCVInstrInfo()
33     : RISCVGenInstrInfo(RISCV::ADJCALLSTACKDOWN, RISCV::ADJCALLSTACKUP) {}
34 
35 void RISCVInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
36                                  MachineBasicBlock::iterator MBBI,
37                                  const DebugLoc &DL, unsigned DstReg,
38                                  unsigned SrcReg, bool KillSrc) const {
39   assert(RISCV::GPRRegClass.contains(DstReg, SrcReg) &&
40          "Impossible reg-to-reg copy");
41 
42   BuildMI(MBB, MBBI, DL, get(RISCV::ADDI), DstReg)
43       .addReg(SrcReg, getKillRegState(KillSrc))
44       .addImm(0);
45 }
46 
47 void RISCVInstrInfo::storeRegToStackSlot(MachineBasicBlock &MBB,
48                                          MachineBasicBlock::iterator I,
49                                          unsigned SrcReg, bool IsKill, int FI,
50                                          const TargetRegisterClass *RC,
51                                          const TargetRegisterInfo *TRI) const {
52   DebugLoc DL;
53   if (I != MBB.end())
54     DL = I->getDebugLoc();
55 
56   if (RISCV::GPRRegClass.hasSubClassEq(RC))
57     BuildMI(MBB, I, DL, get(RISCV::SW))
58         .addReg(SrcReg, getKillRegState(IsKill))
59         .addFrameIndex(FI)
60         .addImm(0);
61   else
62     llvm_unreachable("Can't store this register to stack slot");
63 }
64 
65 void RISCVInstrInfo::loadRegFromStackSlot(MachineBasicBlock &MBB,
66                                           MachineBasicBlock::iterator I,
67                                           unsigned DstReg, int FI,
68                                           const TargetRegisterClass *RC,
69                                           const TargetRegisterInfo *TRI) const {
70   DebugLoc DL;
71   if (I != MBB.end())
72     DL = I->getDebugLoc();
73 
74   if (RISCV::GPRRegClass.hasSubClassEq(RC))
75     BuildMI(MBB, I, DL, get(RISCV::LW), DstReg).addFrameIndex(FI).addImm(0);
76   else
77     llvm_unreachable("Can't load this register from stack slot");
78 }
79 
80 void RISCVInstrInfo::movImm32(MachineBasicBlock &MBB,
81                               MachineBasicBlock::iterator MBBI,
82                               const DebugLoc &DL, unsigned DstReg, uint64_t Val,
83                               MachineInstr::MIFlag Flag) const {
84   assert(isInt<32>(Val) && "Can only materialize 32-bit constants");
85 
86   // TODO: If the value can be materialized using only one instruction, only
87   // insert a single instruction.
88 
89   uint64_t Hi20 = ((Val + 0x800) >> 12) & 0xfffff;
90   uint64_t Lo12 = SignExtend64<12>(Val);
91   BuildMI(MBB, MBBI, DL, get(RISCV::LUI), DstReg)
92       .addImm(Hi20)
93       .setMIFlag(Flag);
94   BuildMI(MBB, MBBI, DL, get(RISCV::ADDI), DstReg)
95       .addReg(DstReg, RegState::Kill)
96       .addImm(Lo12)
97       .setMIFlag(Flag);
98 }
99 
100 // The contents of values added to Cond are not examined outside of
101 // RISCVInstrInfo, giving us flexibility in what to push to it. For RISCV, we
102 // push BranchOpcode, Reg1, Reg2.
103 static void parseCondBranch(MachineInstr &LastInst, MachineBasicBlock *&Target,
104                             SmallVectorImpl<MachineOperand> &Cond) {
105   // Block ends with fall-through condbranch.
106   assert(LastInst.getDesc().isConditionalBranch() &&
107          "Unknown conditional branch");
108   Target = LastInst.getOperand(2).getMBB();
109   Cond.push_back(MachineOperand::CreateImm(LastInst.getOpcode()));
110   Cond.push_back(LastInst.getOperand(0));
111   Cond.push_back(LastInst.getOperand(1));
112 }
113 
114 static unsigned getOppositeBranchOpcode(int Opc) {
115   switch (Opc) {
116   default:
117     llvm_unreachable("Unrecognized conditional branch");
118   case RISCV::BEQ:
119     return RISCV::BNE;
120   case RISCV::BNE:
121     return RISCV::BEQ;
122   case RISCV::BLT:
123     return RISCV::BGE;
124   case RISCV::BGE:
125     return RISCV::BLT;
126   case RISCV::BLTU:
127     return RISCV::BGEU;
128   case RISCV::BGEU:
129     return RISCV::BLTU;
130   }
131 }
132 
133 bool RISCVInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
134                                    MachineBasicBlock *&TBB,
135                                    MachineBasicBlock *&FBB,
136                                    SmallVectorImpl<MachineOperand> &Cond,
137                                    bool AllowModify) const {
138   TBB = FBB = nullptr;
139   Cond.clear();
140 
141   // If the block has no terminators, it just falls into the block after it.
142   MachineBasicBlock::iterator I = MBB.getLastNonDebugInstr();
143   if (I == MBB.end() || !isUnpredicatedTerminator(*I))
144     return false;
145 
146   // Count the number of terminators and find the first unconditional or
147   // indirect branch.
148   MachineBasicBlock::iterator FirstUncondOrIndirectBr = MBB.end();
149   int NumTerminators = 0;
150   for (auto J = I.getReverse(); J != MBB.rend() && isUnpredicatedTerminator(*J);
151        J++) {
152     NumTerminators++;
153     if (J->getDesc().isUnconditionalBranch() ||
154         J->getDesc().isIndirectBranch()) {
155       FirstUncondOrIndirectBr = J.getReverse();
156     }
157   }
158 
159   // If AllowModify is true, we can erase any terminators after
160   // FirstUncondOrIndirectBR.
161   if (AllowModify && FirstUncondOrIndirectBr != MBB.end()) {
162     while (std::next(FirstUncondOrIndirectBr) != MBB.end()) {
163       std::next(FirstUncondOrIndirectBr)->eraseFromParent();
164       NumTerminators--;
165     }
166     I = FirstUncondOrIndirectBr;
167   }
168 
169   // We can't handle blocks that end in an indirect branch.
170   if (I->getDesc().isIndirectBranch())
171     return true;
172 
173   // We can't handle blocks with more than 2 terminators.
174   if (NumTerminators > 2)
175     return true;
176 
177   // Handle a single unconditional branch.
178   if (NumTerminators == 1 && I->getDesc().isUnconditionalBranch()) {
179     TBB = I->getOperand(0).getMBB();
180     return false;
181   }
182 
183   // Handle a single conditional branch.
184   if (NumTerminators == 1 && I->getDesc().isConditionalBranch()) {
185     parseCondBranch(*I, TBB, Cond);
186     return false;
187   }
188 
189   // Handle a conditional branch followed by an unconditional branch.
190   if (NumTerminators == 2 && std::prev(I)->getDesc().isConditionalBranch() &&
191       I->getDesc().isUnconditionalBranch()) {
192     parseCondBranch(*std::prev(I), TBB, Cond);
193     FBB = I->getOperand(0).getMBB();
194     return false;
195   }
196 
197   // Otherwise, we can't handle this.
198   return true;
199 }
200 
201 unsigned RISCVInstrInfo::removeBranch(MachineBasicBlock &MBB,
202                                       int *BytesRemoved) const {
203   if (BytesRemoved)
204     *BytesRemoved = 0;
205   MachineBasicBlock::iterator I = MBB.getLastNonDebugInstr();
206   if (I == MBB.end())
207     return 0;
208 
209   if (!I->getDesc().isUnconditionalBranch() &&
210       !I->getDesc().isConditionalBranch())
211     return 0;
212 
213   // Remove the branch.
214   I->eraseFromParent();
215   if (BytesRemoved)
216     *BytesRemoved += getInstSizeInBytes(*I);
217 
218   I = MBB.end();
219 
220   if (I == MBB.begin())
221     return 1;
222   --I;
223   if (!I->getDesc().isConditionalBranch())
224     return 1;
225 
226   // Remove the branch.
227   I->eraseFromParent();
228   if (BytesRemoved)
229     *BytesRemoved += getInstSizeInBytes(*I);
230   return 2;
231 }
232 
233 // Inserts a branch into the end of the specific MachineBasicBlock, returning
234 // the number of instructions inserted.
235 unsigned RISCVInstrInfo::insertBranch(
236     MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB,
237     ArrayRef<MachineOperand> Cond, const DebugLoc &DL, int *BytesAdded) const {
238   if (BytesAdded)
239     *BytesAdded = 0;
240 
241   // Shouldn't be a fall through.
242   assert(TBB && "InsertBranch must not be told to insert a fallthrough");
243   assert((Cond.size() == 3 || Cond.size() == 0) &&
244          "RISCV branch conditions have two components!");
245 
246   // Unconditional branch.
247   if (Cond.empty()) {
248     MachineInstr &MI = *BuildMI(&MBB, DL, get(RISCV::PseudoBR)).addMBB(TBB);
249     if (BytesAdded)
250       *BytesAdded += getInstSizeInBytes(MI);
251     return 1;
252   }
253 
254   // Either a one or two-way conditional branch.
255   unsigned Opc = Cond[0].getImm();
256   MachineInstr &CondMI =
257       *BuildMI(&MBB, DL, get(Opc)).add(Cond[1]).add(Cond[2]).addMBB(TBB);
258   if (BytesAdded)
259     *BytesAdded += getInstSizeInBytes(CondMI);
260 
261   // One-way conditional branch.
262   if (!FBB)
263     return 1;
264 
265   // Two-way conditional branch.
266   MachineInstr &MI = *BuildMI(&MBB, DL, get(RISCV::PseudoBR)).addMBB(FBB);
267   if (BytesAdded)
268     *BytesAdded += getInstSizeInBytes(MI);
269   return 2;
270 }
271 
272 unsigned RISCVInstrInfo::insertIndirectBranch(MachineBasicBlock &MBB,
273                                               MachineBasicBlock &DestBB,
274                                               const DebugLoc &DL,
275                                               int64_t BrOffset,
276                                               RegScavenger *RS) const {
277   assert(RS && "RegScavenger required for long branching");
278   assert(MBB.empty() &&
279          "new block should be inserted for expanding unconditional branch");
280   assert(MBB.pred_size() == 1);
281 
282   MachineFunction *MF = MBB.getParent();
283   MachineRegisterInfo &MRI = MF->getRegInfo();
284   const auto &TM = static_cast<const RISCVTargetMachine &>(MF->getTarget());
285   const auto &STI = MF->getSubtarget<RISCVSubtarget>();
286 
287   if (TM.isPositionIndependent() || STI.is64Bit())
288     report_fatal_error("Unable to insert indirect branch");
289 
290   if (!isInt<32>(BrOffset))
291     report_fatal_error(
292         "Branch offsets outside of the signed 32-bit range not supported");
293 
294   // FIXME: A virtual register must be used initially, as the register
295   // scavenger won't work with empty blocks (SIInstrInfo::insertIndirectBranch
296   // uses the same workaround).
297   unsigned ScratchReg = MRI.createVirtualRegister(&RISCV::GPRRegClass);
298   auto II = MBB.end();
299 
300   MachineInstr &LuiMI = *BuildMI(MBB, II, DL, get(RISCV::LUI), ScratchReg)
301                              .addMBB(&DestBB, RISCVII::MO_HI);
302   BuildMI(MBB, II, DL, get(RISCV::PseudoBRIND))
303       .addReg(ScratchReg, RegState::Kill)
304       .addMBB(&DestBB, RISCVII::MO_LO);
305 
306   RS->enterBasicBlockEnd(MBB);
307   unsigned Scav = RS->scavengeRegisterBackwards(
308       RISCV::GPRRegClass, MachineBasicBlock::iterator(LuiMI), false, 0);
309   MRI.replaceRegWith(ScratchReg, Scav);
310   MRI.clearVirtRegs();
311   RS->setRegUsed(Scav);
312   return 8;
313 }
314 
315 bool RISCVInstrInfo::reverseBranchCondition(
316     SmallVectorImpl<MachineOperand> &Cond) const {
317   assert((Cond.size() == 3) && "Invalid branch condition!");
318   Cond[0].setImm(getOppositeBranchOpcode(Cond[0].getImm()));
319   return false;
320 }
321 
322 MachineBasicBlock *
323 RISCVInstrInfo::getBranchDestBlock(const MachineInstr &MI) const {
324   assert(MI.getDesc().isBranch() && "Unexpected opcode!");
325   // The branch target is always the last operand.
326   int NumOp = MI.getNumExplicitOperands();
327   return MI.getOperand(NumOp - 1).getMBB();
328 }
329 
330 bool RISCVInstrInfo::isBranchOffsetInRange(unsigned BranchOp,
331                                            int64_t BrOffset) const {
332   // Ideally we could determine the supported branch offset from the
333   // RISCVII::FormMask, but this can't be used for Pseudo instructions like
334   // PseudoBR.
335   switch (BranchOp) {
336   default:
337     llvm_unreachable("Unexpected opcode!");
338   case RISCV::BEQ:
339   case RISCV::BNE:
340   case RISCV::BLT:
341   case RISCV::BGE:
342   case RISCV::BLTU:
343   case RISCV::BGEU:
344     return isIntN(13, BrOffset);
345   case RISCV::JAL:
346   case RISCV::PseudoBR:
347     return isIntN(21, BrOffset);
348   }
349 }
350 
351 unsigned RISCVInstrInfo::getInstSizeInBytes(const MachineInstr &MI) const {
352   unsigned Opcode = MI.getOpcode();
353 
354   switch (Opcode) {
355   default: { return get(Opcode).getSize(); }
356   case TargetOpcode::EH_LABEL:
357   case TargetOpcode::IMPLICIT_DEF:
358   case TargetOpcode::KILL:
359   case TargetOpcode::DBG_VALUE:
360     return 0;
361   case TargetOpcode::INLINEASM: {
362     const MachineFunction &MF = *MI.getParent()->getParent();
363     const auto &TM = static_cast<const RISCVTargetMachine &>(MF.getTarget());
364     return getInlineAsmLength(MI.getOperand(0).getSymbolName(),
365                               *TM.getMCAsmInfo());
366   }
367   }
368 }
369