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