1 //===-- RISCVISelDAGToDAG.cpp - A dag to dag inst selector for RISCV ------===//
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 defines an instruction selector for the RISCV target.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "MCTargetDesc/RISCVMCTargetDesc.h"
14 #include "RISCV.h"
15 #include "RISCVTargetMachine.h"
16 #include "Utils/RISCVMatInt.h"
17 #include "llvm/CodeGen/MachineFrameInfo.h"
18 #include "llvm/CodeGen/SelectionDAGISel.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/MathExtras.h"
21 #include "llvm/Support/raw_ostream.h"
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "riscv-isel"
25 
26 // RISCV-specific code to select RISCV machine instructions for
27 // SelectionDAG operations.
28 namespace {
29 class RISCVDAGToDAGISel final : public SelectionDAGISel {
30   const RISCVSubtarget *Subtarget = nullptr;
31 
32 public:
33   explicit RISCVDAGToDAGISel(RISCVTargetMachine &TargetMachine)
34       : SelectionDAGISel(TargetMachine) {}
35 
36   StringRef getPassName() const override {
37     return "RISCV DAG->DAG Pattern Instruction Selection";
38   }
39 
40   bool runOnMachineFunction(MachineFunction &MF) override {
41     Subtarget = &MF.getSubtarget<RISCVSubtarget>();
42     return SelectionDAGISel::runOnMachineFunction(MF);
43   }
44 
45   void PostprocessISelDAG() override;
46 
47   void Select(SDNode *Node) override;
48 
49   bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
50                                     std::vector<SDValue> &OutOps) override;
51 
52   bool SelectAddrFI(SDValue Addr, SDValue &Base);
53 
54 // Include the pieces autogenerated from the target description.
55 #include "RISCVGenDAGISel.inc"
56 
57 private:
58   void doPeepholeLoadStoreADDI();
59 };
60 }
61 
62 void RISCVDAGToDAGISel::PostprocessISelDAG() {
63   doPeepholeLoadStoreADDI();
64 }
65 
66 static SDNode *selectImm(SelectionDAG *CurDAG, const SDLoc &DL, int64_t Imm,
67                          MVT XLenVT) {
68   RISCVMatInt::InstSeq Seq;
69   RISCVMatInt::generateInstSeq(Imm, XLenVT == MVT::i64, Seq);
70 
71   SDNode *Result = nullptr;
72   SDValue SrcReg = CurDAG->getRegister(RISCV::X0, XLenVT);
73   for (RISCVMatInt::Inst &Inst : Seq) {
74     SDValue SDImm = CurDAG->getTargetConstant(Inst.Imm, DL, XLenVT);
75     if (Inst.Opc == RISCV::LUI)
76       Result = CurDAG->getMachineNode(RISCV::LUI, DL, XLenVT, SDImm);
77     else
78       Result = CurDAG->getMachineNode(Inst.Opc, DL, XLenVT, SrcReg, SDImm);
79 
80     // Only the first instruction has X0 as its source.
81     SrcReg = SDValue(Result, 0);
82   }
83 
84   return Result;
85 }
86 
87 // Returns true if the Node is an ISD::AND with a constant argument. If so,
88 // set Mask to that constant value.
89 static bool isConstantMask(SDNode *Node, uint64_t &Mask) {
90   if (Node->getOpcode() == ISD::AND &&
91       Node->getOperand(1).getOpcode() == ISD::Constant) {
92     Mask = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
93     return true;
94   }
95   return false;
96 }
97 
98 void RISCVDAGToDAGISel::Select(SDNode *Node) {
99   // If we have a custom node, we have already selected.
100   if (Node->isMachineOpcode()) {
101     LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << "\n");
102     Node->setNodeId(-1);
103     return;
104   }
105 
106   // Instruction Selection not handled by the auto-generated tablegen selection
107   // should be handled here.
108   unsigned Opcode = Node->getOpcode();
109   MVT XLenVT = Subtarget->getXLenVT();
110   SDLoc DL(Node);
111   EVT VT = Node->getValueType(0);
112 
113   switch (Opcode) {
114   case ISD::Constant: {
115     auto ConstNode = cast<ConstantSDNode>(Node);
116     if (VT == XLenVT && ConstNode->isNullValue()) {
117       SDValue New = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), SDLoc(Node),
118                                            RISCV::X0, XLenVT);
119       ReplaceNode(Node, New.getNode());
120       return;
121     }
122     int64_t Imm = ConstNode->getSExtValue();
123     if (XLenVT == MVT::i64) {
124       ReplaceNode(Node, selectImm(CurDAG, SDLoc(Node), Imm, XLenVT));
125       return;
126     }
127     break;
128   }
129   case ISD::FrameIndex: {
130     SDValue Imm = CurDAG->getTargetConstant(0, DL, XLenVT);
131     int FI = cast<FrameIndexSDNode>(Node)->getIndex();
132     SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
133     ReplaceNode(Node, CurDAG->getMachineNode(RISCV::ADDI, DL, VT, TFI, Imm));
134     return;
135   }
136   case ISD::SRL: {
137     if (!Subtarget->is64Bit())
138       break;
139     SDValue Op0 = Node->getOperand(0);
140     SDValue Op1 = Node->getOperand(1);
141     uint64_t Mask;
142     // Match (srl (and val, mask), imm) where the result would be a
143     // zero-extended 32-bit integer. i.e. the mask is 0xffffffff or the result
144     // is equivalent to this (SimplifyDemandedBits may have removed lower bits
145     // from the mask that aren't necessary due to the right-shifting).
146     if (Op1.getOpcode() == ISD::Constant &&
147         isConstantMask(Op0.getNode(), Mask)) {
148       uint64_t ShAmt = cast<ConstantSDNode>(Op1.getNode())->getZExtValue();
149 
150       if ((Mask | maskTrailingOnes<uint64_t>(ShAmt)) == 0xffffffff) {
151         SDValue ShAmtVal =
152             CurDAG->getTargetConstant(ShAmt, SDLoc(Node), XLenVT);
153         CurDAG->SelectNodeTo(Node, RISCV::SRLIW, XLenVT, Op0.getOperand(0),
154                              ShAmtVal);
155         return;
156       }
157     }
158     break;
159   }
160   case RISCVISD::READ_CYCLE_WIDE:
161     assert(!Subtarget->is64Bit() && "READ_CYCLE_WIDE is only used on riscv32");
162 
163     ReplaceNode(Node, CurDAG->getMachineNode(RISCV::ReadCycleWide, DL, MVT::i32,
164                                              MVT::i32, MVT::Other,
165                                              Node->getOperand(0)));
166     return;
167   }
168 
169   // Select the default instruction.
170   SelectCode(Node);
171 }
172 
173 bool RISCVDAGToDAGISel::SelectInlineAsmMemoryOperand(
174     const SDValue &Op, unsigned ConstraintID, std::vector<SDValue> &OutOps) {
175   switch (ConstraintID) {
176   case InlineAsm::Constraint_m:
177     // We just support simple memory operands that have a single address
178     // operand and need no special handling.
179     OutOps.push_back(Op);
180     return false;
181   case InlineAsm::Constraint_A:
182     OutOps.push_back(Op);
183     return false;
184   default:
185     break;
186   }
187 
188   return true;
189 }
190 
191 bool RISCVDAGToDAGISel::SelectAddrFI(SDValue Addr, SDValue &Base) {
192   if (auto FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
193     Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), Subtarget->getXLenVT());
194     return true;
195   }
196   return false;
197 }
198 
199 // Merge an ADDI into the offset of a load/store instruction where possible.
200 // (load (add base, off), 0) -> (load base, off)
201 // (store val, (add base, off)) -> (store val, base, off)
202 void RISCVDAGToDAGISel::doPeepholeLoadStoreADDI() {
203   SelectionDAG::allnodes_iterator Position(CurDAG->getRoot().getNode());
204   ++Position;
205 
206   while (Position != CurDAG->allnodes_begin()) {
207     SDNode *N = &*--Position;
208     // Skip dead nodes and any non-machine opcodes.
209     if (N->use_empty() || !N->isMachineOpcode())
210       continue;
211 
212     int OffsetOpIdx;
213     int BaseOpIdx;
214 
215     // Only attempt this optimisation for I-type loads and S-type stores.
216     switch (N->getMachineOpcode()) {
217     default:
218       continue;
219     case RISCV::LB:
220     case RISCV::LH:
221     case RISCV::LW:
222     case RISCV::LBU:
223     case RISCV::LHU:
224     case RISCV::LWU:
225     case RISCV::LD:
226     case RISCV::FLW:
227     case RISCV::FLD:
228       BaseOpIdx = 0;
229       OffsetOpIdx = 1;
230       break;
231     case RISCV::SB:
232     case RISCV::SH:
233     case RISCV::SW:
234     case RISCV::SD:
235     case RISCV::FSW:
236     case RISCV::FSD:
237       BaseOpIdx = 1;
238       OffsetOpIdx = 2;
239       break;
240     }
241 
242     // Currently, the load/store offset must be 0 to be considered for this
243     // peephole optimisation.
244     if (!isa<ConstantSDNode>(N->getOperand(OffsetOpIdx)) ||
245         N->getConstantOperandVal(OffsetOpIdx) != 0)
246       continue;
247 
248     SDValue Base = N->getOperand(BaseOpIdx);
249 
250     // If the base is an ADDI, we can merge it in to the load/store.
251     if (!Base.isMachineOpcode() || Base.getMachineOpcode() != RISCV::ADDI)
252       continue;
253 
254     SDValue ImmOperand = Base.getOperand(1);
255 
256     if (auto Const = dyn_cast<ConstantSDNode>(ImmOperand)) {
257       ImmOperand = CurDAG->getTargetConstant(
258           Const->getSExtValue(), SDLoc(ImmOperand), ImmOperand.getValueType());
259     } else if (auto GA = dyn_cast<GlobalAddressSDNode>(ImmOperand)) {
260       ImmOperand = CurDAG->getTargetGlobalAddress(
261           GA->getGlobal(), SDLoc(ImmOperand), ImmOperand.getValueType(),
262           GA->getOffset(), GA->getTargetFlags());
263     } else {
264       continue;
265     }
266 
267     LLVM_DEBUG(dbgs() << "Folding add-immediate into mem-op:\nBase:    ");
268     LLVM_DEBUG(Base->dump(CurDAG));
269     LLVM_DEBUG(dbgs() << "\nN: ");
270     LLVM_DEBUG(N->dump(CurDAG));
271     LLVM_DEBUG(dbgs() << "\n");
272 
273     // Modify the offset operand of the load/store.
274     if (BaseOpIdx == 0) // Load
275       CurDAG->UpdateNodeOperands(N, Base.getOperand(0), ImmOperand,
276                                  N->getOperand(2));
277     else // Store
278       CurDAG->UpdateNodeOperands(N, N->getOperand(0), Base.getOperand(0),
279                                  ImmOperand, N->getOperand(3));
280 
281     // The add-immediate may now be dead, in which case remove it.
282     if (Base.getNode()->use_empty())
283       CurDAG->RemoveDeadNode(Base.getNode());
284   }
285 }
286 
287 // This pass converts a legalized DAG into a RISCV-specific DAG, ready
288 // for instruction scheduling.
289 FunctionPass *llvm::createRISCVISelDag(RISCVTargetMachine &TM) {
290   return new RISCVDAGToDAGISel(TM);
291 }
292