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::ADD: {
79     // Optimize (add r, imm) to (addi (addi r, imm0) imm1) if applicable. The
80     // immediate must be in specific ranges and have a single use.
81     if (auto *ConstOp = dyn_cast<ConstantSDNode>(Node->getOperand(1))) {
82       if (!(ConstOp->hasOneUse()))
83         break;
84       // The imm must be in range [-4096,-2049] or [2048,4094].
85       int64_t Imm = ConstOp->getSExtValue();
86       if (!(-4096 <= Imm && Imm <= -2049) && !(2048 <= Imm && Imm <= 4094))
87         break;
88       // Break the imm to imm0+imm1.
89       SDLoc DL(Node);
90       EVT VT = Node->getValueType(0);
91       const SDValue ImmOp0 = CurDAG->getTargetConstant(Imm - Imm / 2, DL, VT);
92       const SDValue ImmOp1 = CurDAG->getTargetConstant(Imm / 2, DL, VT);
93       auto *NodeAddi0 = CurDAG->getMachineNode(RISCV::ADDI, DL, VT,
94                                                Node->getOperand(0), ImmOp0);
95       auto *NodeAddi1 = CurDAG->getMachineNode(RISCV::ADDI, DL, VT,
96                                                SDValue(NodeAddi0, 0), ImmOp1);
97       ReplaceNode(Node, NodeAddi1);
98       return;
99     }
100     break;
101   }
102   case ISD::Constant: {
103     auto ConstNode = cast<ConstantSDNode>(Node);
104     if (VT == XLenVT && ConstNode->isNullValue()) {
105       SDValue New = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), SDLoc(Node),
106                                            RISCV::X0, XLenVT);
107       ReplaceNode(Node, New.getNode());
108       return;
109     }
110     int64_t Imm = ConstNode->getSExtValue();
111     if (XLenVT == MVT::i64) {
112       ReplaceNode(Node, selectImm(CurDAG, SDLoc(Node), Imm, XLenVT));
113       return;
114     }
115     break;
116   }
117   case ISD::FrameIndex: {
118     SDValue Imm = CurDAG->getTargetConstant(0, DL, XLenVT);
119     int FI = cast<FrameIndexSDNode>(Node)->getIndex();
120     SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
121     ReplaceNode(Node, CurDAG->getMachineNode(RISCV::ADDI, DL, VT, TFI, Imm));
122     return;
123   }
124   case ISD::SRL: {
125     if (!Subtarget->is64Bit())
126       break;
127     SDValue Op0 = Node->getOperand(0);
128     SDValue Op1 = Node->getOperand(1);
129     uint64_t Mask;
130     // Match (srl (and val, mask), imm) where the result would be a
131     // zero-extended 32-bit integer. i.e. the mask is 0xffffffff or the result
132     // is equivalent to this (SimplifyDemandedBits may have removed lower bits
133     // from the mask that aren't necessary due to the right-shifting).
134     if (Op1.getOpcode() == ISD::Constant &&
135         isConstantMask(Op0.getNode(), Mask)) {
136       uint64_t ShAmt = cast<ConstantSDNode>(Op1.getNode())->getZExtValue();
137 
138       if ((Mask | maskTrailingOnes<uint64_t>(ShAmt)) == 0xffffffff) {
139         SDValue ShAmtVal =
140             CurDAG->getTargetConstant(ShAmt, SDLoc(Node), XLenVT);
141         CurDAG->SelectNodeTo(Node, RISCV::SRLIW, XLenVT, Op0.getOperand(0),
142                              ShAmtVal);
143         return;
144       }
145     }
146     break;
147   }
148   case RISCVISD::READ_CYCLE_WIDE:
149     assert(!Subtarget->is64Bit() && "READ_CYCLE_WIDE is only used on riscv32");
150 
151     ReplaceNode(Node, CurDAG->getMachineNode(RISCV::ReadCycleWide, DL, MVT::i32,
152                                              MVT::i32, MVT::Other,
153                                              Node->getOperand(0)));
154     return;
155   }
156 
157   // Select the default instruction.
158   SelectCode(Node);
159 }
160 
161 bool RISCVDAGToDAGISel::SelectInlineAsmMemoryOperand(
162     const SDValue &Op, unsigned ConstraintID, std::vector<SDValue> &OutOps) {
163   switch (ConstraintID) {
164   case InlineAsm::Constraint_m:
165     // We just support simple memory operands that have a single address
166     // operand and need no special handling.
167     OutOps.push_back(Op);
168     return false;
169   case InlineAsm::Constraint_A:
170     OutOps.push_back(Op);
171     return false;
172   default:
173     break;
174   }
175 
176   return true;
177 }
178 
179 bool RISCVDAGToDAGISel::SelectAddrFI(SDValue Addr, SDValue &Base) {
180   if (auto FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
181     Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), Subtarget->getXLenVT());
182     return true;
183   }
184   return false;
185 }
186 
187 // Merge an ADDI into the offset of a load/store instruction where possible.
188 // (load (addi base, off1), off2) -> (load base, off1+off2)
189 // (store val, (addi base, off1), off2) -> (store val, base, off1+off2)
190 // This is possible when off1+off2 fits a 12-bit immediate.
191 void RISCVDAGToDAGISel::doPeepholeLoadStoreADDI() {
192   SelectionDAG::allnodes_iterator Position(CurDAG->getRoot().getNode());
193   ++Position;
194 
195   while (Position != CurDAG->allnodes_begin()) {
196     SDNode *N = &*--Position;
197     // Skip dead nodes and any non-machine opcodes.
198     if (N->use_empty() || !N->isMachineOpcode())
199       continue;
200 
201     int OffsetOpIdx;
202     int BaseOpIdx;
203 
204     // Only attempt this optimisation for I-type loads and S-type stores.
205     switch (N->getMachineOpcode()) {
206     default:
207       continue;
208     case RISCV::LB:
209     case RISCV::LH:
210     case RISCV::LW:
211     case RISCV::LBU:
212     case RISCV::LHU:
213     case RISCV::LWU:
214     case RISCV::LD:
215     case RISCV::FLW:
216     case RISCV::FLD:
217       BaseOpIdx = 0;
218       OffsetOpIdx = 1;
219       break;
220     case RISCV::SB:
221     case RISCV::SH:
222     case RISCV::SW:
223     case RISCV::SD:
224     case RISCV::FSW:
225     case RISCV::FSD:
226       BaseOpIdx = 1;
227       OffsetOpIdx = 2;
228       break;
229     }
230 
231     if (!isa<ConstantSDNode>(N->getOperand(OffsetOpIdx)))
232       continue;
233 
234     SDValue Base = N->getOperand(BaseOpIdx);
235 
236     // If the base is an ADDI, we can merge it in to the load/store.
237     if (!Base.isMachineOpcode() || Base.getMachineOpcode() != RISCV::ADDI)
238       continue;
239 
240     SDValue ImmOperand = Base.getOperand(1);
241     uint64_t Offset2 = N->getConstantOperandVal(OffsetOpIdx);
242 
243     if (auto Const = dyn_cast<ConstantSDNode>(ImmOperand)) {
244       int64_t Offset1 = Const->getSExtValue();
245       int64_t CombinedOffset = Offset1 + Offset2;
246       if (!isInt<12>(CombinedOffset))
247         continue;
248       ImmOperand = CurDAG->getTargetConstant(CombinedOffset, SDLoc(ImmOperand),
249                                              ImmOperand.getValueType());
250     } else if (auto GA = dyn_cast<GlobalAddressSDNode>(ImmOperand)) {
251       // If the off1 in (addi base, off1) is a global variable's address (its
252       // low part, really), then we can rely on the alignment of that variable
253       // to provide a margin of safety before off1 can overflow the 12 bits.
254       // Check if off2 falls within that margin; if so off1+off2 can't overflow.
255       const DataLayout &DL = CurDAG->getDataLayout();
256       Align Alignment = GA->getGlobal()->getPointerAlignment(DL);
257       if (Offset2 != 0 && Alignment <= Offset2)
258         continue;
259       int64_t Offset1 = GA->getOffset();
260       int64_t CombinedOffset = Offset1 + Offset2;
261       ImmOperand = CurDAG->getTargetGlobalAddress(
262           GA->getGlobal(), SDLoc(ImmOperand), ImmOperand.getValueType(),
263           CombinedOffset, GA->getTargetFlags());
264     } else if (auto CP = dyn_cast<ConstantPoolSDNode>(ImmOperand)) {
265       // Ditto.
266       Align Alignment = CP->getAlign();
267       if (Offset2 != 0 && Alignment <= Offset2)
268         continue;
269       int64_t Offset1 = CP->getOffset();
270       int64_t CombinedOffset = Offset1 + Offset2;
271       ImmOperand = CurDAG->getTargetConstantPool(
272           CP->getConstVal(), ImmOperand.getValueType(), CP->getAlign(),
273           CombinedOffset, CP->getTargetFlags());
274     } else {
275       continue;
276     }
277 
278     LLVM_DEBUG(dbgs() << "Folding add-immediate into mem-op:\nBase:    ");
279     LLVM_DEBUG(Base->dump(CurDAG));
280     LLVM_DEBUG(dbgs() << "\nN: ");
281     LLVM_DEBUG(N->dump(CurDAG));
282     LLVM_DEBUG(dbgs() << "\n");
283 
284     // Modify the offset operand of the load/store.
285     if (BaseOpIdx == 0) // Load
286       CurDAG->UpdateNodeOperands(N, Base.getOperand(0), ImmOperand,
287                                  N->getOperand(2));
288     else // Store
289       CurDAG->UpdateNodeOperands(N, N->getOperand(0), Base.getOperand(0),
290                                  ImmOperand, N->getOperand(3));
291 
292     // The add-immediate may now be dead, in which case remove it.
293     if (Base.getNode()->use_empty())
294       CurDAG->RemoveDeadNode(Base.getNode());
295   }
296 }
297 
298 // This pass converts a legalized DAG into a RISCV-specific DAG, ready
299 // for instruction scheduling.
300 FunctionPass *llvm::createRISCVISelDag(RISCVTargetMachine &TM) {
301   return new RISCVDAGToDAGISel(TM);
302 }
303