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