1//===-- HexagonISelDAGToDAG.cpp - A dag to dag inst selector for Hexagon --===//
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 Hexagon target.
10//
11//===----------------------------------------------------------------------===//
12
13#include "HexagonISelDAGToDAG.h"
14#include "Hexagon.h"
15#include "HexagonISelLowering.h"
16#include "HexagonMachineFunctionInfo.h"
17#include "HexagonTargetMachine.h"
18#include "llvm/CodeGen/FunctionLoweringInfo.h"
19#include "llvm/CodeGen/MachineInstrBuilder.h"
20#include "llvm/CodeGen/SelectionDAGISel.h"
21#include "llvm/IR/Intrinsics.h"
22#include "llvm/IR/IntrinsicsHexagon.h"
23#include "llvm/Support/CommandLine.h"
24#include "llvm/Support/Debug.h"
25using namespace llvm;
26
27#define DEBUG_TYPE "hexagon-isel"
28#define PASS_NAME "Hexagon DAG->DAG Pattern Instruction Selection"
29
30static
31cl::opt<bool>
32EnableAddressRebalancing("isel-rebalance-addr", cl::Hidden, cl::init(Val: true),
33 cl::desc("Rebalance address calculation trees to improve "
34 "instruction selection"));
35
36// Rebalance only if this allows e.g. combining a GA with an offset or
37// factoring out a shift.
38static
39cl::opt<bool>
40RebalanceOnlyForOptimizations("rebalance-only-opt", cl::Hidden, cl::init(Val: false),
41 cl::desc("Rebalance address tree only if this allows optimizations"));
42
43static
44cl::opt<bool>
45RebalanceOnlyImbalancedTrees("rebalance-only-imbal", cl::Hidden,
46 cl::init(Val: false), cl::desc("Rebalance address tree only if it is imbalanced"));
47
48static cl::opt<bool> CheckSingleUse("hexagon-isel-su", cl::Hidden,
49 cl::init(Val: true), cl::desc("Enable checking of SDNode's single-use status"));
50
51//===----------------------------------------------------------------------===//
52// Instruction Selector Implementation
53//===----------------------------------------------------------------------===//
54
55#define GET_DAGISEL_BODY HexagonDAGToDAGISel
56#include "HexagonGenDAGISel.inc"
57
58namespace llvm {
59/// createHexagonISelDag - This pass converts a legalized DAG into a
60/// Hexagon-specific DAG, ready for instruction scheduling.
61FunctionPass *createHexagonISelDag(HexagonTargetMachine &TM,
62 CodeGenOptLevel OptLevel) {
63 return new HexagonDAGToDAGISelLegacy(TM, OptLevel);
64}
65}
66
67HexagonDAGToDAGISelLegacy::HexagonDAGToDAGISelLegacy(HexagonTargetMachine &tm,
68 CodeGenOptLevel OptLevel)
69 : SelectionDAGISelLegacy(
70 ID, std::make_unique<HexagonDAGToDAGISel>(args&: tm, args&: OptLevel)) {}
71
72char HexagonDAGToDAGISelLegacy::ID = 0;
73
74INITIALIZE_PASS(HexagonDAGToDAGISelLegacy, DEBUG_TYPE, PASS_NAME, false, false)
75
76void HexagonDAGToDAGISel::SelectIndexedLoad(LoadSDNode *LD, const SDLoc &dl) {
77 SDValue Chain = LD->getChain();
78 SDValue Base = LD->getBasePtr();
79 SDValue Offset = LD->getOffset();
80 int32_t Inc = cast<ConstantSDNode>(Val: Offset.getNode())->getSExtValue();
81 EVT LoadedVT = LD->getMemoryVT();
82 unsigned Opcode = 0;
83
84 // Check for zero extended loads. Treat any-extend loads as zero extended
85 // loads.
86 ISD::LoadExtType ExtType = LD->getExtensionType();
87 bool IsZeroExt = (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD);
88 bool IsValidInc = HII->isValidAutoIncImm(VT: LoadedVT, Offset: Inc);
89
90 assert(LoadedVT.isSimple());
91 switch (LoadedVT.getSimpleVT().SimpleTy) {
92 case MVT::i8:
93 if (IsZeroExt)
94 Opcode = IsValidInc ? Hexagon::L2_loadrub_pi : Hexagon::L2_loadrub_io;
95 else
96 Opcode = IsValidInc ? Hexagon::L2_loadrb_pi : Hexagon::L2_loadrb_io;
97 break;
98 case MVT::i16:
99 if (IsZeroExt)
100 Opcode = IsValidInc ? Hexagon::L2_loadruh_pi : Hexagon::L2_loadruh_io;
101 else
102 Opcode = IsValidInc ? Hexagon::L2_loadrh_pi : Hexagon::L2_loadrh_io;
103 break;
104 case MVT::i32:
105 case MVT::f32:
106 case MVT::v2i16:
107 case MVT::v4i8:
108 Opcode = IsValidInc ? Hexagon::L2_loadri_pi : Hexagon::L2_loadri_io;
109 break;
110 case MVT::i64:
111 case MVT::f64:
112 case MVT::v2i32:
113 case MVT::v4i16:
114 case MVT::v8i8:
115 Opcode = IsValidInc ? Hexagon::L2_loadrd_pi : Hexagon::L2_loadrd_io;
116 break;
117 case MVT::v64i8:
118 case MVT::v32i16:
119 case MVT::v16i32:
120 case MVT::v8i64:
121 case MVT::v128i8:
122 case MVT::v64i16:
123 case MVT::v32i32:
124 case MVT::v16i64:
125 if (isAlignedMemNode(N: LD)) {
126 if (LD->isNonTemporal())
127 Opcode = IsValidInc ? Hexagon::V6_vL32b_nt_pi : Hexagon::V6_vL32b_nt_ai;
128 else
129 Opcode = IsValidInc ? Hexagon::V6_vL32b_pi : Hexagon::V6_vL32b_ai;
130 } else {
131 Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi : Hexagon::V6_vL32Ub_ai;
132 }
133 break;
134 default:
135 llvm_unreachable("Unexpected memory type in indexed load");
136 }
137
138 SDValue IncV = CurDAG->getSignedTargetConstant(Val: Inc, DL: dl, VT: MVT::i32);
139 MachineMemOperand *MemOp = LD->getMemOperand();
140
141 auto getExt64 = [this,ExtType] (MachineSDNode *N, const SDLoc &dl)
142 -> MachineSDNode* {
143 if (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD) {
144 SDValue Zero = CurDAG->getTargetConstant(Val: 0, DL: dl, VT: MVT::i32);
145 return CurDAG->getMachineNode(Opcode: Hexagon::A4_combineir, dl, VT: MVT::i64,
146 Op1: Zero, Op2: SDValue(N, 0));
147 }
148 if (ExtType == ISD::SEXTLOAD)
149 return CurDAG->getMachineNode(Opcode: Hexagon::A2_sxtw, dl, VT: MVT::i64,
150 Op1: SDValue(N, 0));
151 return N;
152 };
153
154 // Loaded value Next address Chain
155 SDValue From[3] = { SDValue(LD,0), SDValue(LD,1), SDValue(LD,2) };
156 SDValue To[3];
157
158 EVT ValueVT = LD->getValueType(ResNo: 0);
159 if (ValueVT == MVT::i64 && ExtType != ISD::NON_EXTLOAD) {
160 // A load extending to i64 will actually produce i32, which will then
161 // need to be extended to i64.
162 assert(LoadedVT.getSizeInBits() <= 32);
163 ValueVT = MVT::i32;
164 }
165
166 if (IsValidInc) {
167 MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, VT1: ValueVT,
168 VT2: MVT::i32, VT3: MVT::Other, Op1: Base,
169 Op2: IncV, Op3: Chain);
170 CurDAG->setNodeMemRefs(N: L, NewMemRefs: {MemOp});
171 To[1] = SDValue(L, 1); // Next address.
172 To[2] = SDValue(L, 2); // Chain.
173 // Handle special case for extension to i64.
174 if (LD->getValueType(ResNo: 0) == MVT::i64)
175 L = getExt64(L, dl);
176 To[0] = SDValue(L, 0); // Loaded (extended) value.
177 } else {
178 SDValue Zero = CurDAG->getTargetConstant(Val: 0, DL: dl, VT: MVT::i32);
179 MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, VT1: ValueVT, VT2: MVT::Other,
180 Op1: Base, Op2: Zero, Op3: Chain);
181 CurDAG->setNodeMemRefs(N: L, NewMemRefs: {MemOp});
182 To[2] = SDValue(L, 1); // Chain.
183 MachineSDNode *A = CurDAG->getMachineNode(Opcode: Hexagon::A2_addi, dl, VT: MVT::i32,
184 Op1: Base, Op2: IncV);
185 To[1] = SDValue(A, 0); // Next address.
186 // Handle special case for extension to i64.
187 if (LD->getValueType(ResNo: 0) == MVT::i64)
188 L = getExt64(L, dl);
189 To[0] = SDValue(L, 0); // Loaded (extended) value.
190 }
191 ReplaceUses(F: From, T: To, Num: 3);
192 CurDAG->RemoveDeadNode(N: LD);
193}
194
195MachineSDNode *HexagonDAGToDAGISel::LoadInstrForLoadIntrinsic(SDNode *IntN) {
196 if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
197 return nullptr;
198
199 SDLoc dl(IntN);
200 unsigned IntNo = IntN->getConstantOperandVal(Num: 1);
201
202 static std::map<unsigned,unsigned> LoadPciMap = {
203 { Intrinsic::hexagon_circ_ldb, Hexagon::L2_loadrb_pci },
204 { Intrinsic::hexagon_circ_ldub, Hexagon::L2_loadrub_pci },
205 { Intrinsic::hexagon_circ_ldh, Hexagon::L2_loadrh_pci },
206 { Intrinsic::hexagon_circ_lduh, Hexagon::L2_loadruh_pci },
207 { Intrinsic::hexagon_circ_ldw, Hexagon::L2_loadri_pci },
208 { Intrinsic::hexagon_circ_ldd, Hexagon::L2_loadrd_pci },
209 };
210 auto FLC = LoadPciMap.find(x: IntNo);
211 if (FLC != LoadPciMap.end()) {
212 EVT ValTy = (IntNo == Intrinsic::hexagon_circ_ldd) ? MVT::i64 : MVT::i32;
213 EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
214 // Operands: { Base, Increment, Modifier, Chain }
215 auto Inc = cast<ConstantSDNode>(Val: IntN->getOperand(Num: 5));
216 SDValue I =
217 CurDAG->getSignedTargetConstant(Val: Inc->getSExtValue(), DL: dl, VT: MVT::i32);
218 MachineSDNode *Res = CurDAG->getMachineNode(Opcode: FLC->second, dl, ResultTys: RTys,
219 Ops: { IntN->getOperand(Num: 2), I, IntN->getOperand(Num: 4),
220 IntN->getOperand(Num: 0) });
221 return Res;
222 }
223
224 return nullptr;
225}
226
227SDNode *HexagonDAGToDAGISel::StoreInstrForLoadIntrinsic(MachineSDNode *LoadN,
228 SDNode *IntN) {
229 // The "LoadN" is just a machine load instruction. The intrinsic also
230 // involves storing it. Generate an appropriate store to the location
231 // given in the intrinsic's operand(3).
232 uint64_t F = HII->get(Opcode: LoadN->getMachineOpcode()).TSFlags;
233 unsigned SizeBits = (F >> HexagonII::MemAccessSizePos) &
234 HexagonII::MemAccesSizeMask;
235 unsigned Size = 1U << (SizeBits-1);
236
237 SDLoc dl(IntN);
238 MachinePointerInfo PI;
239 SDValue TS;
240 SDValue Loc = IntN->getOperand(Num: 3);
241
242 if (Size >= 4)
243 TS = CurDAG->getStore(Chain: SDValue(LoadN, 2), dl, Val: SDValue(LoadN, 0), Ptr: Loc, PtrInfo: PI,
244 Alignment: Align(Size));
245 else
246 TS = CurDAG->getTruncStore(Chain: SDValue(LoadN, 2), dl, Val: SDValue(LoadN, 0), Ptr: Loc,
247 PtrInfo: PI, SVT: MVT::getIntegerVT(BitWidth: Size * 8), Alignment: Align(Size));
248
249 SDNode *StoreN;
250 {
251 HandleSDNode Handle(TS);
252 SelectStore(N: TS.getNode());
253 StoreN = Handle.getValue().getNode();
254 }
255
256 // Load's results are { Loaded value, Updated pointer, Chain }
257 ReplaceUses(F: SDValue(IntN, 0), T: SDValue(LoadN, 1));
258 ReplaceUses(F: SDValue(IntN, 1), T: SDValue(StoreN, 0));
259 return StoreN;
260}
261
262bool HexagonDAGToDAGISel::tryLoadOfLoadIntrinsic(LoadSDNode *N) {
263 // The intrinsics for load circ/brev perform two operations:
264 // 1. Load a value V from the specified location, using the addressing
265 // mode corresponding to the intrinsic.
266 // 2. Store V into a specified location. This location is typically a
267 // local, temporary object.
268 // In many cases, the program using these intrinsics will immediately
269 // load V again from the local object. In those cases, when certain
270 // conditions are met, the last load can be removed.
271 // This function identifies and optimizes this pattern. If the pattern
272 // cannot be optimized, it returns nullptr, which will cause the load
273 // to be selected separately from the intrinsic (which will be handled
274 // in SelectIntrinsicWChain).
275
276 SDValue Ch = N->getOperand(Num: 0);
277 SDValue Loc = N->getOperand(Num: 1);
278
279 // Assume that the load and the intrinsic are connected directly with a
280 // chain:
281 // t1: i32,ch = int.load ..., ..., ..., Loc, ... // <-- C
282 // t2: i32,ch = load t1:1, Loc, ...
283 SDNode *C = Ch.getNode();
284
285 if (C->getOpcode() != ISD::INTRINSIC_W_CHAIN)
286 return false;
287
288 // The second load can only be eliminated if its extension type matches
289 // that of the load instruction corresponding to the intrinsic. The user
290 // can provide an address of an unsigned variable to store the result of
291 // a sign-extending intrinsic into (or the other way around).
292 ISD::LoadExtType IntExt;
293 switch (C->getConstantOperandVal(Num: 1)) {
294 case Intrinsic::hexagon_circ_ldub:
295 case Intrinsic::hexagon_circ_lduh:
296 IntExt = ISD::ZEXTLOAD;
297 break;
298 case Intrinsic::hexagon_circ_ldw:
299 case Intrinsic::hexagon_circ_ldd:
300 IntExt = ISD::NON_EXTLOAD;
301 break;
302 default:
303 IntExt = ISD::SEXTLOAD;
304 break;
305 }
306 if (N->getExtensionType() != IntExt)
307 return false;
308
309 // Make sure the target location for the loaded value in the load intrinsic
310 // is the location from which LD (or N) is loading.
311 if (C->getNumOperands() < 4 || Loc.getNode() != C->getOperand(Num: 3).getNode())
312 return false;
313
314 if (MachineSDNode *L = LoadInstrForLoadIntrinsic(IntN: C)) {
315 SDNode *S = StoreInstrForLoadIntrinsic(LoadN: L, IntN: C);
316 SDValue F[] = { SDValue(N,0), SDValue(N,1), SDValue(C,0), SDValue(C,1) };
317 SDValue T[] = { SDValue(L,0), SDValue(S,0), SDValue(L,1), SDValue(S,0) };
318 ReplaceUses(F, T, Num: std::size(T));
319 // This transformation will leave the intrinsic dead. If it remains in
320 // the DAG, the selection code will see it again, but without the load,
321 // and it will generate a store that is normally required for it.
322 CurDAG->RemoveDeadNode(N: C);
323 return true;
324 }
325 return false;
326}
327
328// Convert the bit-reverse load intrinsic to appropriate target instruction.
329bool HexagonDAGToDAGISel::SelectBrevLdIntrinsic(SDNode *IntN) {
330 if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
331 return false;
332
333 const SDLoc &dl(IntN);
334 unsigned IntNo = IntN->getConstantOperandVal(Num: 1);
335
336 static const std::map<unsigned, unsigned> LoadBrevMap = {
337 { Intrinsic::hexagon_L2_loadrb_pbr, Hexagon::L2_loadrb_pbr },
338 { Intrinsic::hexagon_L2_loadrub_pbr, Hexagon::L2_loadrub_pbr },
339 { Intrinsic::hexagon_L2_loadrh_pbr, Hexagon::L2_loadrh_pbr },
340 { Intrinsic::hexagon_L2_loadruh_pbr, Hexagon::L2_loadruh_pbr },
341 { Intrinsic::hexagon_L2_loadri_pbr, Hexagon::L2_loadri_pbr },
342 { Intrinsic::hexagon_L2_loadrd_pbr, Hexagon::L2_loadrd_pbr }
343 };
344 auto FLI = LoadBrevMap.find(x: IntNo);
345 if (FLI != LoadBrevMap.end()) {
346 EVT ValTy =
347 (IntNo == Intrinsic::hexagon_L2_loadrd_pbr) ? MVT::i64 : MVT::i32;
348 EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
349 // Operands of Intrinsic: {chain, enum ID of intrinsic, baseptr,
350 // modifier}.
351 // Operands of target instruction: { Base, Modifier, Chain }.
352 MachineSDNode *Res = CurDAG->getMachineNode(
353 Opcode: FLI->second, dl, ResultTys: RTys,
354 Ops: {IntN->getOperand(Num: 2), IntN->getOperand(Num: 3), IntN->getOperand(Num: 0)});
355
356 MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(Val: IntN)->getMemOperand();
357 CurDAG->setNodeMemRefs(N: Res, NewMemRefs: {MemOp});
358
359 ReplaceUses(F: SDValue(IntN, 0), T: SDValue(Res, 0));
360 ReplaceUses(F: SDValue(IntN, 1), T: SDValue(Res, 1));
361 ReplaceUses(F: SDValue(IntN, 2), T: SDValue(Res, 2));
362 CurDAG->RemoveDeadNode(N: IntN);
363 return true;
364 }
365 return false;
366}
367
368static SDValue getCircRegister(SelectionDAG &DAG, SDLoc DL, SDNode *N,
369 unsigned MOp, unsigned CSOp) {
370 SDValue RC = DAG.getTargetConstant(Val: Hexagon::CircRegsRegClassID, DL, VT: MVT::i32);
371 SDValue SubRegCS = DAG.getTargetConstant(Val: Hexagon::isub_lo, DL, VT: MVT::i32);
372 SDValue SubRegM = DAG.getTargetConstant(Val: Hexagon::isub_hi, DL, VT: MVT::i32);
373 const SDValue RegSequenceOps[] = {RC, N->getOperand(Num: MOp), SubRegM,
374 N->getOperand(Num: CSOp), SubRegCS};
375 SDNode *M_CS = DAG.getMachineNode(Opcode: TargetOpcode::REG_SEQUENCE, dl: DL, VT: MVT::i64,
376 Ops: RegSequenceOps);
377 return SDValue(M_CS, 0);
378}
379
380/// Generate a machine instruction node for the new circular buffer intrinsics.
381/// The new versions use a CSx register instead of the K field.
382bool HexagonDAGToDAGISel::SelectNewCircIntrinsic(SDNode *IntN) {
383 if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
384 return false;
385
386 SDLoc DL(IntN);
387 unsigned IntNo = IntN->getConstantOperandVal(Num: 1);
388 SmallVector<SDValue, 7> Ops;
389
390 static std::map<unsigned,unsigned> LoadNPcMap = {
391 { Intrinsic::hexagon_L2_loadrub_pci, Hexagon::PS_loadrub_pci },
392 { Intrinsic::hexagon_L2_loadrb_pci, Hexagon::PS_loadrb_pci },
393 { Intrinsic::hexagon_L2_loadruh_pci, Hexagon::PS_loadruh_pci },
394 { Intrinsic::hexagon_L2_loadrh_pci, Hexagon::PS_loadrh_pci },
395 { Intrinsic::hexagon_L2_loadri_pci, Hexagon::PS_loadri_pci },
396 { Intrinsic::hexagon_L2_loadrd_pci, Hexagon::PS_loadrd_pci },
397 { Intrinsic::hexagon_L2_loadrub_pcr, Hexagon::PS_loadrub_pcr },
398 { Intrinsic::hexagon_L2_loadrb_pcr, Hexagon::PS_loadrb_pcr },
399 { Intrinsic::hexagon_L2_loadruh_pcr, Hexagon::PS_loadruh_pcr },
400 { Intrinsic::hexagon_L2_loadrh_pcr, Hexagon::PS_loadrh_pcr },
401 { Intrinsic::hexagon_L2_loadri_pcr, Hexagon::PS_loadri_pcr },
402 { Intrinsic::hexagon_L2_loadrd_pcr, Hexagon::PS_loadrd_pcr }
403 };
404 auto FLI = LoadNPcMap.find (x: IntNo);
405 if (FLI != LoadNPcMap.end()) {
406 EVT ValTy = MVT::i32;
407 if (IntNo == Intrinsic::hexagon_L2_loadrd_pci ||
408 IntNo == Intrinsic::hexagon_L2_loadrd_pcr)
409 ValTy = MVT::i64;
410 EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
411 // Handle load.*_pci case which has 6 operands.
412 if (IntN->getNumOperands() == 6) {
413 auto Inc = cast<ConstantSDNode>(Val: IntN->getOperand(Num: 3));
414 SDValue I = CurDAG->getTargetConstant(Val: Inc->getSExtValue(), DL, VT: MVT::i32);
415 SDValue M_CS = getCircRegister(DAG&: *CurDAG, DL, N: IntN, MOp: 4, CSOp: 5);
416 // Operands: { Base, Increment, Modifier_Start, Chain }.
417 Ops = {IntN->getOperand(Num: 2), I, M_CS, IntN->getOperand(Num: 0)};
418 } else {
419 // Handle load.*_pcr case which has 5 operands.
420 SDValue M_CS = getCircRegister(DAG&: *CurDAG, DL, N: IntN, MOp: 3, CSOp: 4);
421 // Operands: { Base, Modifier_Start, Chain }.
422 Ops = {IntN->getOperand(Num: 2), M_CS, IntN->getOperand(Num: 0)};
423 }
424 MachineSDNode *Res = CurDAG->getMachineNode(Opcode: FLI->second, dl: DL, ResultTys: RTys, Ops);
425 ReplaceUses(F: SDValue(IntN, 0), T: SDValue(Res, 0));
426 ReplaceUses(F: SDValue(IntN, 1), T: SDValue(Res, 1));
427 ReplaceUses(F: SDValue(IntN, 2), T: SDValue(Res, 2));
428 CurDAG->RemoveDeadNode(N: IntN);
429 return true;
430 }
431
432 static std::map<unsigned,unsigned> StoreNPcMap = {
433 { Intrinsic::hexagon_S2_storerb_pci, Hexagon::PS_storerb_pci },
434 { Intrinsic::hexagon_S2_storerh_pci, Hexagon::PS_storerh_pci },
435 { Intrinsic::hexagon_S2_storerf_pci, Hexagon::PS_storerf_pci },
436 { Intrinsic::hexagon_S2_storeri_pci, Hexagon::PS_storeri_pci },
437 { Intrinsic::hexagon_S2_storerd_pci, Hexagon::PS_storerd_pci },
438 { Intrinsic::hexagon_S2_storerb_pcr, Hexagon::PS_storerb_pcr },
439 { Intrinsic::hexagon_S2_storerh_pcr, Hexagon::PS_storerh_pcr },
440 { Intrinsic::hexagon_S2_storerf_pcr, Hexagon::PS_storerf_pcr },
441 { Intrinsic::hexagon_S2_storeri_pcr, Hexagon::PS_storeri_pcr },
442 { Intrinsic::hexagon_S2_storerd_pcr, Hexagon::PS_storerd_pcr }
443 };
444 auto FSI = StoreNPcMap.find (x: IntNo);
445 if (FSI != StoreNPcMap.end()) {
446 EVT RTys[] = { MVT::i32, MVT::Other };
447 // Handle store.*_pci case which has 7 operands.
448 if (IntN->getNumOperands() == 7) {
449 auto Inc = cast<ConstantSDNode>(Val: IntN->getOperand(Num: 3));
450 SDValue I = CurDAG->getTargetConstant(Val: Inc->getSExtValue(), DL, VT: MVT::i32);
451 SDValue M_CS = getCircRegister(DAG&: *CurDAG, DL, N: IntN, MOp: 4, CSOp: 6);
452 // Operands: { Base, Increment, Modifier_Start, Value, Chain }.
453 Ops = {IntN->getOperand(Num: 2), I, M_CS, IntN->getOperand(Num: 5),
454 IntN->getOperand(Num: 0)};
455 } else {
456 // Handle store.*_pcr case which has 6 operands.
457 SDValue M_CS = getCircRegister(DAG&: *CurDAG, DL, N: IntN, MOp: 3, CSOp: 5);
458 // Operands: { Base, Modifier_Start, Value, Chain }.
459 Ops = {IntN->getOperand(Num: 2), M_CS, IntN->getOperand(Num: 4),
460 IntN->getOperand(Num: 0)};
461 }
462 MachineSDNode *Res = CurDAG->getMachineNode(Opcode: FSI->second, dl: DL, ResultTys: RTys, Ops);
463 ReplaceUses(F: SDValue(IntN, 0), T: SDValue(Res, 0));
464 ReplaceUses(F: SDValue(IntN, 1), T: SDValue(Res, 1));
465 CurDAG->RemoveDeadNode(N: IntN);
466 return true;
467 }
468
469 return false;
470}
471
472void HexagonDAGToDAGISel::SelectLoad(SDNode *N) {
473 SDLoc dl(N);
474 LoadSDNode *LD = cast<LoadSDNode>(Val: N);
475
476 // Handle indexed loads.
477 ISD::MemIndexedMode AM = LD->getAddressingMode();
478 if (AM != ISD::UNINDEXED) {
479 SelectIndexedLoad(LD, dl);
480 return;
481 }
482
483 // Handle patterns using circ/brev load intrinsics.
484 if (tryLoadOfLoadIntrinsic(N: LD))
485 return;
486
487 SelectCode(N: LD);
488}
489
490void HexagonDAGToDAGISel::SelectIndexedStore(StoreSDNode *ST, const SDLoc &dl) {
491 SDValue Chain = ST->getChain();
492 SDValue Base = ST->getBasePtr();
493 SDValue Offset = ST->getOffset();
494 SDValue Value = ST->getValue();
495 // Get the constant value.
496 int32_t Inc = cast<ConstantSDNode>(Val: Offset.getNode())->getSExtValue();
497 EVT StoredVT = ST->getMemoryVT();
498 EVT ValueVT = Value.getValueType();
499
500 bool IsValidInc = HII->isValidAutoIncImm(VT: StoredVT, Offset: Inc);
501 unsigned Opcode = 0;
502
503 assert(StoredVT.isSimple());
504 switch (StoredVT.getSimpleVT().SimpleTy) {
505 case MVT::i8:
506 Opcode = IsValidInc ? Hexagon::S2_storerb_pi : Hexagon::S2_storerb_io;
507 break;
508 case MVT::i16:
509 Opcode = IsValidInc ? Hexagon::S2_storerh_pi : Hexagon::S2_storerh_io;
510 break;
511 case MVT::i32:
512 case MVT::f32:
513 case MVT::v2i16:
514 case MVT::v4i8:
515 Opcode = IsValidInc ? Hexagon::S2_storeri_pi : Hexagon::S2_storeri_io;
516 break;
517 case MVT::i64:
518 case MVT::f64:
519 case MVT::v2i32:
520 case MVT::v4i16:
521 case MVT::v8i8:
522 Opcode = IsValidInc ? Hexagon::S2_storerd_pi : Hexagon::S2_storerd_io;
523 break;
524 case MVT::v64i8:
525 case MVT::v32i16:
526 case MVT::v16i32:
527 case MVT::v8i64:
528 case MVT::v128i8:
529 case MVT::v64i16:
530 case MVT::v32i32:
531 case MVT::v16i64:
532 if (isAlignedMemNode(N: ST)) {
533 if (ST->isNonTemporal())
534 Opcode = IsValidInc ? Hexagon::V6_vS32b_nt_pi : Hexagon::V6_vS32b_nt_ai;
535 else
536 Opcode = IsValidInc ? Hexagon::V6_vS32b_pi : Hexagon::V6_vS32b_ai;
537 } else {
538 Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi : Hexagon::V6_vS32Ub_ai;
539 }
540 break;
541 default:
542 llvm_unreachable("Unexpected memory type in indexed store");
543 }
544
545 if (ST->isTruncatingStore() && ValueVT.getSizeInBits() == 64) {
546 assert(StoredVT.getSizeInBits() < 64 && "Not a truncating store");
547 Value = CurDAG->getTargetExtractSubreg(SRIdx: Hexagon::isub_lo,
548 DL: dl, VT: MVT::i32, Operand: Value);
549 }
550
551 SDValue IncV = CurDAG->getSignedTargetConstant(Val: Inc, DL: dl, VT: MVT::i32);
552 MachineMemOperand *MemOp = ST->getMemOperand();
553
554 // Next address Chain
555 SDValue From[2] = { SDValue(ST,0), SDValue(ST,1) };
556 SDValue To[2];
557
558 if (IsValidInc) {
559 // Build post increment store.
560 SDValue Ops[] = { Base, IncV, Value, Chain };
561 MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, VT1: MVT::i32, VT2: MVT::Other,
562 Ops);
563 CurDAG->setNodeMemRefs(N: S, NewMemRefs: {MemOp});
564 To[0] = SDValue(S, 0);
565 To[1] = SDValue(S, 1);
566 } else {
567 SDValue Zero = CurDAG->getTargetConstant(Val: 0, DL: dl, VT: MVT::i32);
568 SDValue Ops[] = { Base, Zero, Value, Chain };
569 MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, VT: MVT::Other, Ops);
570 CurDAG->setNodeMemRefs(N: S, NewMemRefs: {MemOp});
571 To[1] = SDValue(S, 0);
572 MachineSDNode *A = CurDAG->getMachineNode(Opcode: Hexagon::A2_addi, dl, VT: MVT::i32,
573 Op1: Base, Op2: IncV);
574 To[0] = SDValue(A, 0);
575 }
576
577 ReplaceUses(F: From, T: To, Num: 2);
578 CurDAG->RemoveDeadNode(N: ST);
579}
580
581void HexagonDAGToDAGISel::SelectStore(SDNode *N) {
582 SDLoc dl(N);
583 StoreSDNode *ST = cast<StoreSDNode>(Val: N);
584
585 // Handle indexed stores.
586 ISD::MemIndexedMode AM = ST->getAddressingMode();
587 if (AM != ISD::UNINDEXED) {
588 SelectIndexedStore(ST, dl);
589 return;
590 }
591
592 SelectCode(N: ST);
593}
594
595void HexagonDAGToDAGISel::SelectSHL(SDNode *N) {
596 SDLoc dl(N);
597 SDValue Shl_0 = N->getOperand(Num: 0);
598 SDValue Shl_1 = N->getOperand(Num: 1);
599
600 auto Default = [this,N] () -> void { SelectCode(N); };
601
602 if (N->getValueType(ResNo: 0) != MVT::i32 || Shl_1.getOpcode() != ISD::Constant)
603 return Default();
604
605 // RHS is const.
606 int32_t ShlConst = cast<ConstantSDNode>(Val&: Shl_1)->getSExtValue();
607
608 if (Shl_0.getOpcode() == ISD::MUL) {
609 SDValue Mul_0 = Shl_0.getOperand(i: 0); // Val
610 SDValue Mul_1 = Shl_0.getOperand(i: 1); // Const
611 // RHS of mul is const.
612 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val&: Mul_1)) {
613 int32_t ValConst = static_cast<int32_t>(
614 static_cast<uint32_t>(C->getSExtValue()) << ShlConst);
615 if (isInt<9>(x: ValConst)) {
616 SDValue Val = CurDAG->getTargetConstant(Val: ValConst, DL: dl, VT: MVT::i32);
617 SDNode *Result = CurDAG->getMachineNode(Opcode: Hexagon::M2_mpysmi, dl,
618 VT: MVT::i32, Op1: Mul_0, Op2: Val);
619 ReplaceNode(F: N, T: Result);
620 return;
621 }
622 }
623 return Default();
624 }
625
626 if (Shl_0.getOpcode() == ISD::SUB) {
627 SDValue Sub_0 = Shl_0.getOperand(i: 0); // Const 0
628 SDValue Sub_1 = Shl_0.getOperand(i: 1); // Val
629 if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Val&: Sub_0)) {
630 if (C1->getSExtValue() != 0 || Sub_1.getOpcode() != ISD::SHL)
631 return Default();
632 SDValue Shl2_0 = Sub_1.getOperand(i: 0); // Val
633 SDValue Shl2_1 = Sub_1.getOperand(i: 1); // Const
634 if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(Val&: Shl2_1)) {
635 int32_t ValConst =
636 static_cast<int32_t>(1U << (ShlConst + C2->getSExtValue()));
637 if (isInt<9>(x: -ValConst)) {
638 SDValue Val =
639 CurDAG->getSignedTargetConstant(Val: -ValConst, DL: dl, VT: MVT::i32);
640 SDNode *Result = CurDAG->getMachineNode(Opcode: Hexagon::M2_mpysmi, dl,
641 VT: MVT::i32, Op1: Shl2_0, Op2: Val);
642 ReplaceNode(F: N, T: Result);
643 return;
644 }
645 }
646 }
647 }
648
649 return Default();
650}
651
652//
653// Handling intrinsics for circular load and bitreverse load.
654//
655void HexagonDAGToDAGISel::SelectIntrinsicWChain(SDNode *N) {
656 if (MachineSDNode *L = LoadInstrForLoadIntrinsic(IntN: N)) {
657 StoreInstrForLoadIntrinsic(LoadN: L, IntN: N);
658 CurDAG->RemoveDeadNode(N);
659 return;
660 }
661
662 // Handle bit-reverse load intrinsics.
663 if (SelectBrevLdIntrinsic(IntN: N))
664 return;
665
666 if (SelectNewCircIntrinsic(IntN: N))
667 return;
668
669 unsigned IntNo = N->getConstantOperandVal(Num: 1);
670 if (IntNo == Intrinsic::hexagon_V6_vgathermw ||
671 IntNo == Intrinsic::hexagon_V6_vgathermw_128B ||
672 IntNo == Intrinsic::hexagon_V6_vgathermh ||
673 IntNo == Intrinsic::hexagon_V6_vgathermh_128B ||
674 IntNo == Intrinsic::hexagon_V6_vgathermhw ||
675 IntNo == Intrinsic::hexagon_V6_vgathermhw_128B ||
676 IntNo == Intrinsic::hexagon_V6_vgather_vscattermh ||
677 IntNo == Intrinsic::hexagon_V6_vgather_vscattermh_128B) {
678 SelectV65Gather(N);
679 return;
680 }
681 if (IntNo == Intrinsic::hexagon_V6_vgathermwq ||
682 IntNo == Intrinsic::hexagon_V6_vgathermwq_128B ||
683 IntNo == Intrinsic::hexagon_V6_vgathermhq ||
684 IntNo == Intrinsic::hexagon_V6_vgathermhq_128B ||
685 IntNo == Intrinsic::hexagon_V6_vgathermhwq ||
686 IntNo == Intrinsic::hexagon_V6_vgathermhwq_128B) {
687 SelectV65GatherPred(N);
688 return;
689 }
690
691 SelectCode(N);
692}
693
694void HexagonDAGToDAGISel::SelectIntrinsicWOChain(SDNode *N) {
695 unsigned IID = cast<ConstantSDNode>(Val: N->getOperand(Num: 0))->getZExtValue();
696 unsigned Bits;
697
698 // On v79 and above, IEEE HVX instructions are no longer present.
699 // The related intrinsics must be translated to QFloat implicitly in order
700 // to provide backward compatibility.
701 if (HST->useHVXV79Ops() && isIEEEHVXIntrinsic(IID)) {
702 translateIEEEIntrinsicToQFloat(N, Opcode&: IID);
703 return;
704 }
705
706 switch (IID) {
707 case Intrinsic::hexagon_S2_vsplatrb:
708 Bits = 8;
709 break;
710 case Intrinsic::hexagon_S2_vsplatrh:
711 Bits = 16;
712 break;
713 case Intrinsic::hexagon_V6_vaddcarry:
714 case Intrinsic::hexagon_V6_vaddcarry_128B:
715 case Intrinsic::hexagon_V6_vsubcarry:
716 case Intrinsic::hexagon_V6_vsubcarry_128B:
717 SelectHVXDualOutput(N);
718 return;
719 default:
720 SelectCode(N);
721 return;
722 }
723
724 SDValue V = N->getOperand(Num: 1);
725 SDValue U;
726 // Splat intrinsics.
727 if (keepsLowBits(Val: V, NumBits: Bits, Src&: U)) {
728 SDValue R = CurDAG->getNode(Opcode: N->getOpcode(), DL: SDLoc(N), VT: N->getValueType(ResNo: 0),
729 N1: N->getOperand(Num: 0), N2: U);
730 ReplaceNode(F: N, T: R.getNode());
731 SelectCode(N: R.getNode());
732 return;
733 }
734 SelectCode(N);
735}
736
737void HexagonDAGToDAGISel::SelectExtractSubvector(SDNode *N) {
738 SDValue Inp = N->getOperand(Num: 0);
739 MVT ResTy = N->getValueType(ResNo: 0).getSimpleVT();
740 unsigned Idx = N->getConstantOperandVal(Num: 1);
741
742 [[maybe_unused]] MVT InpTy = Inp.getValueType().getSimpleVT();
743 [[maybe_unused]] unsigned ResLen = ResTy.getVectorNumElements();
744 assert(InpTy.getVectorElementType() == ResTy.getVectorElementType());
745 assert(2 * ResLen == InpTy.getVectorNumElements());
746 assert(ResTy.getSizeInBits() == 32);
747 assert(Idx == 0 || Idx == ResLen);
748
749 unsigned SubReg = Idx == 0 ? Hexagon::isub_lo : Hexagon::isub_hi;
750 SDValue Ext = CurDAG->getTargetExtractSubreg(SRIdx: SubReg, DL: SDLoc(N), VT: ResTy, Operand: Inp);
751
752 ReplaceNode(F: N, T: Ext.getNode());
753}
754
755//
756// Map floating point constant values.
757//
758void HexagonDAGToDAGISel::SelectConstantFP(SDNode *N) {
759 SDLoc dl(N);
760 auto *CN = cast<ConstantFPSDNode>(Val: N);
761 APInt A = CN->getValueAPF().bitcastToAPInt();
762 if (N->getValueType(ResNo: 0) == MVT::f32) {
763 SDValue V = CurDAG->getTargetConstant(Val: A.getZExtValue(), DL: dl, VT: MVT::i32);
764 ReplaceNode(F: N, T: CurDAG->getMachineNode(Opcode: Hexagon::A2_tfrsi, dl, VT: MVT::f32, Op1: V));
765 return;
766 }
767 if (N->getValueType(ResNo: 0) == MVT::f64) {
768 SDValue V = CurDAG->getTargetConstant(Val: A.getZExtValue(), DL: dl, VT: MVT::i64);
769 ReplaceNode(F: N, T: CurDAG->getMachineNode(Opcode: Hexagon::CONST64, dl, VT: MVT::f64, Op1: V));
770 return;
771 }
772
773 SelectCode(N);
774}
775
776//
777// Map boolean values.
778//
779void HexagonDAGToDAGISel::SelectConstant(SDNode *N) {
780 if (N->getValueType(ResNo: 0) == MVT::i1) {
781 assert(!(N->getAsZExtVal() >> 1));
782 unsigned Opc = (cast<ConstantSDNode>(Val: N)->getSExtValue() != 0)
783 ? Hexagon::PS_true
784 : Hexagon::PS_false;
785 ReplaceNode(F: N, T: CurDAG->getMachineNode(Opcode: Opc, dl: SDLoc(N), VT: MVT::i1));
786 return;
787 }
788
789 SelectCode(N);
790}
791
792void HexagonDAGToDAGISel::SelectFrameIndex(SDNode *N) {
793 MachineFrameInfo &MFI = MF->getFrameInfo();
794 const HexagonFrameLowering *HFI = HST->getFrameLowering();
795 int FX = cast<FrameIndexSDNode>(Val: N)->getIndex();
796 Align StkA = HFI->getStackAlign();
797 Align MaxA = MFI.getMaxAlign();
798 SDValue FI = CurDAG->getTargetFrameIndex(FI: FX, VT: MVT::i32);
799 SDLoc DL(N);
800 SDValue Zero = CurDAG->getTargetConstant(Val: 0, DL, VT: MVT::i32);
801 SDNode *R = nullptr;
802
803 // Use PS_fi when:
804 // - the object is fixed, or
805 // - there are no objects with higher-than-default alignment, or
806 // - there are no dynamically allocated objects.
807 // Otherwise, use PS_fia.
808 if (FX < 0 || MaxA <= StkA || !MFI.hasVarSizedObjects()) {
809 R = CurDAG->getMachineNode(Opcode: Hexagon::PS_fi, dl: DL, VT: MVT::i32, Op1: FI, Op2: Zero);
810 } else {
811 auto &HMFI = *MF->getInfo<HexagonMachineFunctionInfo>();
812 Register AR = HMFI.getStackAlignBaseReg();
813 assert(AR.isValid() && "Missing stack align base register");
814 SDValue CH = CurDAG->getEntryNode();
815 SDValue Ops[] = { CurDAG->getCopyFromReg(Chain: CH, dl: DL, Reg: AR, VT: MVT::i32), FI, Zero };
816 R = CurDAG->getMachineNode(Opcode: Hexagon::PS_fia, dl: DL, VT: MVT::i32, Ops);
817 }
818
819 ReplaceNode(F: N, T: R);
820}
821
822void HexagonDAGToDAGISel::SelectAddSubCarry(SDNode *N) {
823 unsigned OpcCarry = N->getOpcode() == HexagonISD::ADDC ? Hexagon::A4_addp_c
824 : Hexagon::A4_subp_c;
825 SDNode *C = CurDAG->getMachineNode(Opcode: OpcCarry, dl: SDLoc(N), VTs: N->getVTList(),
826 Ops: { N->getOperand(Num: 0), N->getOperand(Num: 1),
827 N->getOperand(Num: 2) });
828 ReplaceNode(F: N, T: C);
829}
830
831void HexagonDAGToDAGISel::SelectVAlign(SDNode *N) {
832 MVT ResTy = N->getValueType(ResNo: 0).getSimpleVT();
833 if (HST->isHVXVectorType(VecTy: ResTy, IncludeBool: true))
834 return SelectHvxVAlign(N);
835
836 const SDLoc &dl(N);
837 unsigned VecLen = ResTy.getSizeInBits();
838 if (VecLen == 32) {
839 SDValue Ops[] = {
840 CurDAG->getTargetConstant(Val: Hexagon::DoubleRegsRegClassID, DL: dl, VT: MVT::i32),
841 N->getOperand(Num: 0),
842 CurDAG->getTargetConstant(Val: Hexagon::isub_hi, DL: dl, VT: MVT::i32),
843 N->getOperand(Num: 1),
844 CurDAG->getTargetConstant(Val: Hexagon::isub_lo, DL: dl, VT: MVT::i32)
845 };
846 SDNode *R = CurDAG->getMachineNode(Opcode: TargetOpcode::REG_SEQUENCE, dl,
847 VT: MVT::i64, Ops);
848
849 // Shift right by "(Addr & 0x3) * 8" bytes.
850 SDNode *C;
851 SDValue M0 = CurDAG->getTargetConstant(Val: 0x18, DL: dl, VT: MVT::i32);
852 SDValue M1 = CurDAG->getTargetConstant(Val: 0x03, DL: dl, VT: MVT::i32);
853 if (HST->useCompound()) {
854 C = CurDAG->getMachineNode(Opcode: Hexagon::S4_andi_asl_ri, dl, VT: MVT::i32,
855 Op1: M0, Op2: N->getOperand(Num: 2), Op3: M1);
856 } else {
857 SDNode *T = CurDAG->getMachineNode(Opcode: Hexagon::S2_asl_i_r, dl, VT: MVT::i32,
858 Op1: N->getOperand(Num: 2), Op2: M1);
859 C = CurDAG->getMachineNode(Opcode: Hexagon::A2_andir, dl, VT: MVT::i32,
860 Op1: SDValue(T, 0), Op2: M0);
861 }
862 SDNode *S = CurDAG->getMachineNode(Opcode: Hexagon::S2_lsr_r_p, dl, VT: MVT::i64,
863 Op1: SDValue(R, 0), Op2: SDValue(C, 0));
864 SDValue E = CurDAG->getTargetExtractSubreg(SRIdx: Hexagon::isub_lo, DL: dl, VT: ResTy,
865 Operand: SDValue(S, 0));
866 ReplaceNode(F: N, T: E.getNode());
867 } else {
868 assert(VecLen == 64);
869 SDNode *Pu = CurDAG->getMachineNode(Opcode: Hexagon::C2_tfrrp, dl, VT: MVT::v8i1,
870 Op1: N->getOperand(Num: 2));
871 SDNode *VA = CurDAG->getMachineNode(Opcode: Hexagon::S2_valignrb, dl, VT: ResTy,
872 Op1: N->getOperand(Num: 0), Op2: N->getOperand(Num: 1),
873 Op3: SDValue(Pu,0));
874 ReplaceNode(F: N, T: VA);
875 }
876}
877
878void HexagonDAGToDAGISel::SelectVAlignAddr(SDNode *N) {
879 const SDLoc &dl(N);
880 SDValue A = N->getOperand(Num: 1);
881 int Mask = -cast<ConstantSDNode>(Val: A.getNode())->getSExtValue();
882 assert(isPowerOf2_32(-Mask));
883
884 SDValue M = CurDAG->getTargetConstant(Val: Mask, DL: dl, VT: MVT::i32);
885 SDNode *AA = CurDAG->getMachineNode(Opcode: Hexagon::A2_andir, dl, VT: MVT::i32,
886 Op1: N->getOperand(Num: 0), Op2: M);
887 ReplaceNode(F: N, T: AA);
888}
889
890// Handle these nodes here to avoid having to write patterns for all
891// combinations of input/output types. In all cases, the resulting
892// instruction is the same.
893void HexagonDAGToDAGISel::SelectTypecast(SDNode *N) {
894 SDValue Op = N->getOperand(Num: 0);
895 MVT OpTy = Op.getValueType().getSimpleVT();
896 SDNode *T = CurDAG->MorphNodeTo(N, Opc: N->getOpcode(),
897 VTs: CurDAG->getVTList(VT: OpTy), Ops: {Op});
898 ReplaceNode(F: T, T: Op.getNode());
899}
900
901void HexagonDAGToDAGISel::SelectP2D(SDNode *N) {
902 MVT ResTy = N->getValueType(ResNo: 0).getSimpleVT();
903 SDNode *T = CurDAG->getMachineNode(Opcode: Hexagon::C2_mask, dl: SDLoc(N), VT: ResTy,
904 Op1: N->getOperand(Num: 0));
905 ReplaceNode(F: N, T);
906}
907
908void HexagonDAGToDAGISel::SelectD2P(SDNode *N) {
909 const SDLoc &dl(N);
910 MVT ResTy = N->getValueType(ResNo: 0).getSimpleVT();
911 SDValue Zero = CurDAG->getTargetConstant(Val: 0, DL: dl, VT: MVT::i32);
912 SDNode *T = CurDAG->getMachineNode(Opcode: Hexagon::A4_vcmpbgtui, dl, VT: ResTy,
913 Op1: N->getOperand(Num: 0), Op2: Zero);
914 ReplaceNode(F: N, T);
915}
916
917void HexagonDAGToDAGISel::SelectV2Q(SDNode *N) {
918 const SDLoc &dl(N);
919 MVT ResTy = N->getValueType(ResNo: 0).getSimpleVT();
920 // The argument to V2Q should be a single vector.
921 MVT OpTy = N->getOperand(Num: 0).getValueType().getSimpleVT(); (void)OpTy;
922 assert(HST->getVectorLength() * 8 == OpTy.getSizeInBits());
923
924 SDValue C = CurDAG->getSignedTargetConstant(Val: -1, DL: dl, VT: MVT::i32);
925 SDNode *R = CurDAG->getMachineNode(Opcode: Hexagon::A2_tfrsi, dl, VT: MVT::i32, Op1: C);
926 SDNode *T = CurDAG->getMachineNode(Opcode: Hexagon::V6_vandvrt, dl, VT: ResTy,
927 Op1: N->getOperand(Num: 0), Op2: SDValue(R,0));
928 ReplaceNode(F: N, T);
929}
930
931void HexagonDAGToDAGISel::SelectQ2V(SDNode *N) {
932 const SDLoc &dl(N);
933 MVT ResTy = N->getValueType(ResNo: 0).getSimpleVT();
934 // The result of V2Q should be a single vector.
935 assert(HST->getVectorLength() * 8 == ResTy.getSizeInBits());
936
937 SDValue C = CurDAG->getSignedTargetConstant(Val: -1, DL: dl, VT: MVT::i32);
938 SDNode *R = CurDAG->getMachineNode(Opcode: Hexagon::A2_tfrsi, dl, VT: MVT::i32, Op1: C);
939 SDNode *T = CurDAG->getMachineNode(Opcode: Hexagon::V6_vandqrt, dl, VT: ResTy,
940 Op1: N->getOperand(Num: 0), Op2: SDValue(R,0));
941 ReplaceNode(F: N, T);
942}
943
944void HexagonDAGToDAGISel::FDiv(SDNode *N) {
945 const SDLoc &dl(N);
946 ArrayRef<EVT> ResultType(N->value_begin(), N->value_end());
947 SmallVector<SDValue, 2> Ops;
948 Ops = {N->getOperand(Num: 0), N->getOperand(Num: 1)};
949 SDVTList VTs;
950 VTs = CurDAG->getVTList(VT1: MVT::f32, VT2: MVT::f32);
951 SDNode *ResScale = CurDAG->getMachineNode(Opcode: Hexagon::F2_sfrecipa, dl, VTs, Ops);
952 SDNode *D = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffixupd, dl, VT: MVT::f32, Ops);
953
954 SDValue C = CurDAG->getTargetConstant(Val: 0x3f800000, DL: dl, VT: MVT::i32);
955 SDNode *constNode =
956 CurDAG->getMachineNode(Opcode: Hexagon::A2_tfrsi, dl, VT: MVT::f32, Op1: C);
957
958 SDNode *n = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffixupn, dl, VT: MVT::f32, Ops);
959 SDNode *Err = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffms_lib, dl, VT: MVT::f32,
960 Op1: SDValue(constNode, 0), Op2: SDValue(D, 0),
961 Op3: SDValue(ResScale, 0));
962 SDNode *NewRec = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffma_lib, dl, VT: MVT::f32,
963 Op1: SDValue(ResScale, 0), Op2: SDValue(Err, 0),
964 Op3: SDValue(ResScale, 0));
965 SDNode *newErr = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffms_lib, dl, VT: MVT::f32,
966 Op1: SDValue(constNode, 0), Op2: SDValue(D, 0),
967 Op3: SDValue(NewRec, 0));
968 SDNode *q = CurDAG->getMachineNode(
969 Opcode: Hexagon::A2_andir, dl, VT: MVT::f32, Op1: SDValue(n, 0),
970 Op2: CurDAG->getTargetConstant(Val: 0x80000000, DL: dl, VT: MVT::i32));
971 SDNode *NewQ =
972 CurDAG->getMachineNode(Opcode: Hexagon::F2_sffma_lib, dl, VT: MVT::f32, Op1: SDValue(q, 0),
973 Op2: SDValue(n, 0), Op3: SDValue(NewRec, 0));
974 SDNode *NNewRec = CurDAG->getMachineNode(
975 Opcode: Hexagon::F2_sffma_lib, dl, VT: MVT::f32, Op1: SDValue(NewRec, 0),
976 Op2: SDValue(newErr, 0), Op3: SDValue(NewRec, 0));
977 SDNode *qErr =
978 CurDAG->getMachineNode(Opcode: Hexagon::F2_sffms_lib, dl, VT: MVT::f32, Op1: SDValue(n, 0),
979 Op2: SDValue(D, 0), Op3: SDValue(NewQ, 0));
980 SDNode *NNewQ = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffma_lib, dl, VT: MVT::f32,
981 Op1: SDValue(NewQ, 0), Op2: SDValue(qErr, 0),
982 Op3: SDValue(NNewRec, 0));
983
984 SDNode *NqErr =
985 CurDAG->getMachineNode(Opcode: Hexagon::F2_sffms_lib, dl, VT: MVT::f32, Op1: SDValue(n, 0),
986 Op2: SDValue(NNewQ, 0), Op3: SDValue(D, 0));
987 std::array<SDValue, 4> temp1 = {SDValue(NNewQ, 0), SDValue(NqErr, 0),
988 SDValue(NNewRec, 0), SDValue(ResScale, 1)};
989 ArrayRef<SDValue> OpValue1(temp1);
990 SDNode *FinalNewQ =
991 CurDAG->getMachineNode(Opcode: Hexagon::F2_sffma_sc, dl, VT: MVT::f32, Ops: OpValue1);
992 ReplaceNode(F: N, T: FinalNewQ);
993}
994
995void HexagonDAGToDAGISel::FastFDiv(SDNode *N) {
996 const SDLoc &dl(N);
997 ArrayRef<EVT> ResultType(N->value_begin(), N->value_end());
998 SmallVector<SDValue, 2> Ops;
999 Ops = {N->getOperand(Num: 0), N->getOperand(Num: 1)};
1000 SDVTList VTs;
1001 VTs = CurDAG->getVTList(VT1: MVT::f32, VT2: MVT::f32);
1002 SDNode *ResScale = CurDAG->getMachineNode(Opcode: Hexagon::F2_sfrecipa, dl, VTs, Ops);
1003 SDNode *D = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffixupd, dl, VT: MVT::f32, Ops);
1004
1005 SDValue C = CurDAG->getTargetConstant(Val: 0x3f800000, DL: dl, VT: MVT::i32);
1006 SDNode *constNode =
1007 CurDAG->getMachineNode(Opcode: Hexagon::A2_tfrsi, dl, VT: MVT::f32, Op1: C);
1008
1009 SDNode *n = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffixupn, dl, VT: MVT::f32, Ops);
1010 SDNode *Err = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffms_lib, dl, VT: MVT::f32,
1011 Op1: SDValue(constNode, 0), Op2: SDValue(D, 0),
1012 Op3: SDValue(ResScale, 0));
1013 SDNode *NewRec = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffma_lib, dl, VT: MVT::f32,
1014 Op1: SDValue(ResScale, 0), Op2: SDValue(Err, 0),
1015 Op3: SDValue(ResScale, 0));
1016 SDNode *newErr = CurDAG->getMachineNode(Opcode: Hexagon::F2_sffms_lib, dl, VT: MVT::f32,
1017 Op1: SDValue(constNode, 0), Op2: SDValue(D, 0),
1018 Op3: SDValue(NewRec, 0));
1019
1020 SDNode *NNewRec = CurDAG->getMachineNode(
1021 Opcode: Hexagon::F2_sffma_lib, dl, VT: MVT::f32, Op1: SDValue(NewRec, 0),
1022 Op2: SDValue(newErr, 0), Op3: SDValue(NewRec, 0));
1023 SDNode *FinalNewQ = CurDAG->getMachineNode(
1024 Opcode: Hexagon::F2_sfmpy, dl, VT: MVT::f32, Op1: SDValue(NNewRec, 0), Op2: SDValue(n, 0));
1025 ReplaceNode(F: N, T: FinalNewQ);
1026}
1027
1028void HexagonDAGToDAGISel::SelectFDiv(SDNode *N) {
1029 if (N->getFlags().hasAllowReassociation())
1030 FastFDiv(N);
1031 else
1032 FDiv(N);
1033}
1034
1035void HexagonDAGToDAGISel::Select(SDNode *N) {
1036 if (N->isMachineOpcode())
1037 return N->setNodeId(-1); // Already selected.
1038
1039 auto isHvxOp = [this](SDNode *N) {
1040 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
1041 if (HST->isHVXVectorType(VecTy: N->getValueType(ResNo: i), IncludeBool: true))
1042 return true;
1043 }
1044 for (SDValue I : N->ops()) {
1045 if (HST->isHVXVectorType(VecTy: I.getValueType(), IncludeBool: true))
1046 return true;
1047 }
1048 return false;
1049 };
1050
1051 if (HST->useHVXOps() && isHvxOp(N)) {
1052 switch (N->getOpcode()) {
1053 case ISD::EXTRACT_SUBVECTOR: return SelectHvxExtractSubvector(N);
1054 case ISD::VECTOR_SHUFFLE: return SelectHvxShuffle(N);
1055
1056 case HexagonISD::VROR: return SelectHvxRor(N);
1057 }
1058 }
1059
1060 switch (N->getOpcode()) {
1061 case ISD::Constant: return SelectConstant(N);
1062 case ISD::ConstantFP: return SelectConstantFP(N);
1063 case ISD::FrameIndex: return SelectFrameIndex(N);
1064 case ISD::SHL: return SelectSHL(N);
1065 case ISD::LOAD: return SelectLoad(N);
1066 case ISD::STORE: return SelectStore(N);
1067 case ISD::INTRINSIC_W_CHAIN: return SelectIntrinsicWChain(N);
1068 case ISD::INTRINSIC_WO_CHAIN: return SelectIntrinsicWOChain(N);
1069 case ISD::EXTRACT_SUBVECTOR: return SelectExtractSubvector(N);
1070
1071 case HexagonISD::ADDC:
1072 case HexagonISD::SUBC: return SelectAddSubCarry(N);
1073 case HexagonISD::VALIGN: return SelectVAlign(N);
1074 case HexagonISD::VALIGNADDR: return SelectVAlignAddr(N);
1075 case HexagonISD::TYPECAST: return SelectTypecast(N);
1076 case HexagonISD::P2D: return SelectP2D(N);
1077 case HexagonISD::D2P: return SelectD2P(N);
1078 case HexagonISD::Q2V: return SelectQ2V(N);
1079 case HexagonISD::V2Q: return SelectV2Q(N);
1080 case ISD::FDIV:
1081 return SelectFDiv(N);
1082 }
1083
1084 SelectCode(N);
1085}
1086
1087bool HexagonDAGToDAGISel::SelectInlineAsmMemoryOperand(
1088 const SDValue &Op, InlineAsm::ConstraintCode ConstraintID,
1089 std::vector<SDValue> &OutOps) {
1090 SDValue Inp = Op, Res;
1091
1092 switch (ConstraintID) {
1093 default:
1094 return true;
1095 case InlineAsm::ConstraintCode::o: // Offsetable.
1096 case InlineAsm::ConstraintCode::v: // Not offsetable.
1097 case InlineAsm::ConstraintCode::m: // Memory.
1098 if (SelectAddrFI(N&: Inp, R&: Res))
1099 OutOps.push_back(x: Res);
1100 else
1101 OutOps.push_back(x: Inp);
1102 break;
1103 }
1104
1105 OutOps.push_back(x: CurDAG->getTargetConstant(Val: 0, DL: SDLoc(Op), VT: MVT::i32));
1106 return false;
1107}
1108
1109static bool isMemOPCandidate(SDNode *I, SDNode *U) {
1110 // I is an operand of U. Check if U is an arithmetic (binary) operation
1111 // usable in a memop, where the other operand is a loaded value, and the
1112 // result of U is stored in the same location.
1113
1114 if (!U->hasOneUse())
1115 return false;
1116 unsigned Opc = U->getOpcode();
1117 switch (Opc) {
1118 case ISD::ADD:
1119 case ISD::SUB:
1120 case ISD::AND:
1121 case ISD::OR:
1122 break;
1123 default:
1124 return false;
1125 }
1126
1127 SDValue S0 = U->getOperand(Num: 0);
1128 SDValue S1 = U->getOperand(Num: 1);
1129 SDValue SY = (S0.getNode() == I) ? S1 : S0;
1130
1131 SDNode *UUse = *U->user_begin();
1132 if (UUse->getNumValues() != 1)
1133 return false;
1134
1135 // Check if one of the inputs to U is a load instruction and the output
1136 // is used by a store instruction. If so and they also have the same
1137 // base pointer, then don't preoprocess this node sequence as it
1138 // can be matched to a memop.
1139 SDNode *SYNode = SY.getNode();
1140 if (UUse->getOpcode() == ISD::STORE && SYNode->getOpcode() == ISD::LOAD) {
1141 SDValue LDBasePtr = cast<MemSDNode>(Val: SYNode)->getBasePtr();
1142 SDValue STBasePtr = cast<MemSDNode>(Val: UUse)->getBasePtr();
1143 if (LDBasePtr == STBasePtr)
1144 return true;
1145 }
1146 return false;
1147}
1148
1149
1150// Transform: (or (select c x 0) z) -> (select c (or x z) z)
1151// (or (select c 0 y) z) -> (select c z (or y z))
1152void HexagonDAGToDAGISel::ppSimplifyOrSelect0(std::vector<SDNode*> &&Nodes) {
1153 SelectionDAG &DAG = *CurDAG;
1154
1155 for (auto *I : Nodes) {
1156 if (I->getOpcode() != ISD::OR)
1157 continue;
1158
1159 auto IsSelect0 = [](const SDValue &Op) -> bool {
1160 if (Op.getOpcode() != ISD::SELECT)
1161 return false;
1162 return isNullConstant(V: Op.getOperand(i: 1)) ||
1163 isNullConstant(V: Op.getOperand(i: 2));
1164 };
1165
1166 SDValue N0 = I->getOperand(Num: 0), N1 = I->getOperand(Num: 1);
1167 EVT VT = I->getValueType(ResNo: 0);
1168 bool SelN0 = IsSelect0(N0);
1169 SDValue SOp = SelN0 ? N0 : N1;
1170 SDValue VOp = SelN0 ? N1 : N0;
1171
1172 if (SOp.getOpcode() == ISD::SELECT && SOp.getNode()->hasOneUse()) {
1173 SDValue SC = SOp.getOperand(i: 0);
1174 SDValue SX = SOp.getOperand(i: 1);
1175 SDValue SY = SOp.getOperand(i: 2);
1176 SDLoc DLS = SOp;
1177 if (isNullConstant(V: SY)) {
1178 SDValue NewOr = DAG.getNode(Opcode: ISD::OR, DL: DLS, VT, N1: SX, N2: VOp);
1179 SDValue NewSel = DAG.getNode(Opcode: ISD::SELECT, DL: DLS, VT, N1: SC, N2: NewOr, N3: VOp);
1180 DAG.ReplaceAllUsesWith(From: I, To: NewSel.getNode());
1181 } else if (isNullConstant(V: SX)) {
1182 SDValue NewOr = DAG.getNode(Opcode: ISD::OR, DL: DLS, VT, N1: SY, N2: VOp);
1183 SDValue NewSel = DAG.getNode(Opcode: ISD::SELECT, DL: DLS, VT, N1: SC, N2: VOp, N3: NewOr);
1184 DAG.ReplaceAllUsesWith(From: I, To: NewSel.getNode());
1185 }
1186 }
1187 }
1188}
1189
1190// Transform: (store ch val (add x (add (shl y c) e)))
1191// to: (store ch val (add x (shl (add y d) c))),
1192// where e = (shl d c) for some integer d.
1193// The purpose of this is to enable generation of loads/stores with
1194// shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
1195// value c must be 0, 1 or 2.
1196void HexagonDAGToDAGISel::ppAddrReorderAddShl(std::vector<SDNode*> &&Nodes) {
1197 SelectionDAG &DAG = *CurDAG;
1198
1199 for (auto *I : Nodes) {
1200 if (I->getOpcode() != ISD::STORE)
1201 continue;
1202
1203 // I matched: (store ch val Off)
1204 SDValue Off = I->getOperand(Num: 2);
1205 // Off needs to match: (add x (add (shl y c) (shl d c))))
1206 if (Off.getOpcode() != ISD::ADD)
1207 continue;
1208 // Off matched: (add x T0)
1209 SDValue T0 = Off.getOperand(i: 1);
1210 // T0 needs to match: (add T1 T2):
1211 if (T0.getOpcode() != ISD::ADD)
1212 continue;
1213 // T0 matched: (add T1 T2)
1214 SDValue T1 = T0.getOperand(i: 0);
1215 SDValue T2 = T0.getOperand(i: 1);
1216 // T1 needs to match: (shl y c)
1217 if (T1.getOpcode() != ISD::SHL)
1218 continue;
1219 SDValue C = T1.getOperand(i: 1);
1220 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Val: C.getNode());
1221 if (CN == nullptr)
1222 continue;
1223 unsigned CV = CN->getZExtValue();
1224 if (CV > 2)
1225 continue;
1226 // T2 needs to match e, where e = (shl d c) for some d.
1227 ConstantSDNode *EN = dyn_cast<ConstantSDNode>(Val: T2.getNode());
1228 if (EN == nullptr)
1229 continue;
1230 unsigned EV = EN->getZExtValue();
1231 if (EV % (1 << CV) != 0)
1232 continue;
1233 unsigned DV = EV / (1 << CV);
1234
1235 // Replace T0 with: (shl (add y d) c)
1236 SDLoc DL = SDLoc(I);
1237 EVT VT = T0.getValueType();
1238 SDValue D = DAG.getConstant(Val: DV, DL, VT);
1239 // NewAdd = (add y d)
1240 SDValue NewAdd = DAG.getNode(Opcode: ISD::ADD, DL, VT, N1: T1.getOperand(i: 0), N2: D);
1241 // NewShl = (shl NewAdd c)
1242 SDValue NewShl = DAG.getNode(Opcode: ISD::SHL, DL, VT, N1: NewAdd, N2: C);
1243 ReplaceNode(F: T0.getNode(), T: NewShl.getNode());
1244 }
1245}
1246
1247// Transform: (load ch (add x (and (srl y c) Mask)))
1248// to: (load ch (add x (shl (srl y d) d-c)))
1249// where
1250// Mask = 00..0 111..1 0.0
1251// | | +-- d-c 0s, and d-c is 0, 1 or 2.
1252// | +-------- 1s
1253// +-------------- at most c 0s
1254// Motivating example:
1255// DAG combiner optimizes (add x (shl (srl y 5) 2))
1256// to (add x (and (srl y 3) 1FFFFFFC))
1257// which results in a constant-extended and(##...,lsr). This transformation
1258// undoes this simplification for cases where the shl can be folded into
1259// an addressing mode.
1260void HexagonDAGToDAGISel::ppAddrRewriteAndSrl(std::vector<SDNode*> &&Nodes) {
1261 SelectionDAG &DAG = *CurDAG;
1262
1263 for (SDNode *N : Nodes) {
1264 unsigned Opc = N->getOpcode();
1265 if (Opc != ISD::LOAD && Opc != ISD::STORE)
1266 continue;
1267 SDValue Addr = Opc == ISD::LOAD ? N->getOperand(Num: 1) : N->getOperand(Num: 2);
1268 // Addr must match: (add x T0)
1269 if (Addr.getOpcode() != ISD::ADD)
1270 continue;
1271 SDValue T0 = Addr.getOperand(i: 1);
1272 // T0 must match: (and T1 Mask)
1273 if (T0.getOpcode() != ISD::AND)
1274 continue;
1275
1276 // We have an AND.
1277 //
1278 // Check the first operand. It must be: (srl y c).
1279 SDValue S = T0.getOperand(i: 0);
1280 if (S.getOpcode() != ISD::SRL)
1281 continue;
1282 ConstantSDNode *SN = dyn_cast<ConstantSDNode>(Val: S.getOperand(i: 1).getNode());
1283 if (SN == nullptr)
1284 continue;
1285 if (SN->getAPIntValue().getBitWidth() != 32)
1286 continue;
1287 uint32_t CV = SN->getZExtValue();
1288
1289 // Check the second operand: the supposed mask.
1290 ConstantSDNode *MN = dyn_cast<ConstantSDNode>(Val: T0.getOperand(i: 1).getNode());
1291 if (MN == nullptr)
1292 continue;
1293 if (MN->getAPIntValue().getBitWidth() != 32)
1294 continue;
1295 uint32_t Mask = MN->getZExtValue();
1296 // Examine the mask.
1297 uint32_t TZ = llvm::countr_zero(Val: Mask);
1298 uint32_t M1 = llvm::countr_one(Value: Mask >> TZ);
1299 uint32_t LZ = llvm::countl_zero(Val: Mask);
1300 // Trailing zeros + middle ones + leading zeros must equal the width.
1301 if (TZ + M1 + LZ != 32)
1302 continue;
1303 // The number of trailing zeros will be encoded in the addressing mode.
1304 if (TZ > 2)
1305 continue;
1306 // The number of leading zeros must be at most c.
1307 if (LZ > CV)
1308 continue;
1309
1310 // All looks good.
1311 SDValue Y = S.getOperand(i: 0);
1312 EVT VT = Addr.getValueType();
1313 SDLoc dl(S);
1314 // TZ = D-C, so D = TZ+C.
1315 SDValue D = DAG.getConstant(Val: TZ+CV, DL: dl, VT);
1316 SDValue DC = DAG.getConstant(Val: TZ, DL: dl, VT);
1317 SDValue NewSrl = DAG.getNode(Opcode: ISD::SRL, DL: dl, VT, N1: Y, N2: D);
1318 SDValue NewShl = DAG.getNode(Opcode: ISD::SHL, DL: dl, VT, N1: NewSrl, N2: DC);
1319 ReplaceNode(F: T0.getNode(), T: NewShl.getNode());
1320 }
1321}
1322
1323// Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1324// (op ... 1 ...))
1325void HexagonDAGToDAGISel::ppHoistZextI1(std::vector<SDNode*> &&Nodes) {
1326 SelectionDAG &DAG = *CurDAG;
1327
1328 for (SDNode *N : Nodes) {
1329 unsigned Opc = N->getOpcode();
1330 if (Opc != ISD::ZERO_EXTEND)
1331 continue;
1332 SDValue OpI1 = N->getOperand(Num: 0);
1333 EVT OpVT = OpI1.getValueType();
1334 if (!OpVT.isSimple() || OpVT.getSimpleVT() != MVT::i1)
1335 continue;
1336 for (SDUse &Use : N->uses()) {
1337 SDNode *U = Use.getUser();
1338 if (U->getNumValues() != 1)
1339 continue;
1340 EVT UVT = U->getValueType(ResNo: 0);
1341 if (!UVT.isSimple() || !UVT.isInteger() || UVT.getSimpleVT() == MVT::i1)
1342 continue;
1343 // Do not generate select for all i1 vector type.
1344 if (UVT.isVectorOf(EltVT: MVT::i1))
1345 continue;
1346 // SELECT on HLX vectors needs custom lowering, which has already run.
1347 if (HST->isHLXVectorType(VecTy: UVT))
1348 continue;
1349 if (isMemOPCandidate(I: N, U))
1350 continue;
1351
1352 // Potentially simplifiable operation.
1353 unsigned I1N = Use.getOperandNo();
1354 SmallVector<SDValue,2> Ops(U->getNumOperands());
1355 for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i)
1356 Ops[i] = U->getOperand(Num: i);
1357 EVT BVT = Ops[I1N].getValueType();
1358
1359 const SDLoc &dl(U);
1360 SDValue C0 = DAG.getConstant(Val: 0, DL: dl, VT: BVT);
1361 SDValue C1 = DAG.getConstant(Val: 1, DL: dl, VT: BVT);
1362 SDValue If0, If1;
1363
1364 if (isa<MachineSDNode>(Val: U)) {
1365 unsigned UseOpc = U->getMachineOpcode();
1366 Ops[I1N] = C0;
1367 If0 = SDValue(DAG.getMachineNode(Opcode: UseOpc, dl, VT: UVT, Ops), 0);
1368 Ops[I1N] = C1;
1369 If1 = SDValue(DAG.getMachineNode(Opcode: UseOpc, dl, VT: UVT, Ops), 0);
1370 } else {
1371 unsigned UseOpc = U->getOpcode();
1372 Ops[I1N] = C0;
1373 If0 = DAG.getNode(Opcode: UseOpc, DL: dl, VT: UVT, Ops);
1374 Ops[I1N] = C1;
1375 If1 = DAG.getNode(Opcode: UseOpc, DL: dl, VT: UVT, Ops);
1376 }
1377 // We're generating a SELECT way after legalization, so keep the types
1378 // simple.
1379 unsigned UW = UVT.getSizeInBits();
1380 EVT SVT = (UW == 32 || UW == 64) ? MVT::getIntegerVT(BitWidth: UW) : UVT;
1381 SDValue Sel = DAG.getNode(Opcode: ISD::SELECT, DL: dl, VT: SVT, N1: OpI1,
1382 N2: DAG.getBitcast(VT: SVT, V: If1),
1383 N3: DAG.getBitcast(VT: SVT, V: If0));
1384 SDValue Ret = DAG.getBitcast(VT: UVT, V: Sel);
1385 DAG.ReplaceAllUsesWith(From: U, To: Ret.getNode());
1386 }
1387 }
1388}
1389
1390void HexagonDAGToDAGISel::PreprocessISelDAG() {
1391 // Repack all nodes before calling each preprocessing function,
1392 // because each of them can modify the set of nodes.
1393 auto getNodes = [this]() -> std::vector<SDNode *> {
1394 std::vector<SDNode *> T;
1395 T.reserve(n: CurDAG->allnodes_size());
1396 for (SDNode &N : CurDAG->allnodes())
1397 T.push_back(x: &N);
1398 return T;
1399 };
1400
1401 if (HST->useHVXOps())
1402 PreprocessHvxISelDAG();
1403
1404 // Transform: (or (select c x 0) z) -> (select c (or x z) z)
1405 // (or (select c 0 y) z) -> (select c z (or y z))
1406 ppSimplifyOrSelect0(Nodes: getNodes());
1407
1408 // Transform: (store ch val (add x (add (shl y c) e)))
1409 // to: (store ch val (add x (shl (add y d) c))),
1410 // where e = (shl d c) for some integer d.
1411 // The purpose of this is to enable generation of loads/stores with
1412 // shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
1413 // value c must be 0, 1 or 2.
1414 ppAddrReorderAddShl(Nodes: getNodes());
1415
1416 // Transform: (load ch (add x (and (srl y c) Mask)))
1417 // to: (load ch (add x (shl (srl y d) d-c)))
1418 // where
1419 // Mask = 00..0 111..1 0.0
1420 // | | +-- d-c 0s, and d-c is 0, 1 or 2.
1421 // | +-------- 1s
1422 // +-------------- at most c 0s
1423 // Motivating example:
1424 // DAG combiner optimizes (add x (shl (srl y 5) 2))
1425 // to (add x (and (srl y 3) 1FFFFFFC))
1426 // which results in a constant-extended and(##...,lsr). This transformation
1427 // undoes this simplification for cases where the shl can be folded into
1428 // an addressing mode.
1429 ppAddrRewriteAndSrl(Nodes: getNodes());
1430
1431 // Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1432 // (op ... 1 ...))
1433 ppHoistZextI1(Nodes: getNodes());
1434
1435 DEBUG_WITH_TYPE("isel", {
1436 dbgs() << "Preprocessed (Hexagon) selection DAG:";
1437 CurDAG->dump();
1438 });
1439
1440 if (EnableAddressRebalancing) {
1441 rebalanceAddressTrees();
1442
1443 DEBUG_WITH_TYPE("isel", {
1444 dbgs() << "Address tree balanced selection DAG:";
1445 CurDAG->dump();
1446 });
1447 }
1448}
1449
1450void HexagonDAGToDAGISel::emitFunctionEntryCode() {
1451 auto &HST = MF->getSubtarget<HexagonSubtarget>();
1452 auto &HFI = *HST.getFrameLowering();
1453 if (!HFI.needsAligna(MF: *MF))
1454 return;
1455
1456 auto &HRI = *HST.getRegisterInfo();
1457 Register AP = HRI.computeStackAlignBaseRegister(MF: *MF);
1458 assert(AP.isValid() && "Couldn't reserve stack align register");
1459 MF->getInfo<HexagonMachineFunctionInfo>()->setStackAlignBaseReg(AP);
1460}
1461
1462// Match a frame index that can be used in an addressing mode.
1463bool HexagonDAGToDAGISel::SelectAddrFI(SDValue &N, SDValue &R) {
1464 if (N.getOpcode() != ISD::FrameIndex)
1465 return false;
1466 auto &HFI = *HST->getFrameLowering();
1467 MachineFrameInfo &MFI = MF->getFrameInfo();
1468 int FX = cast<FrameIndexSDNode>(Val&: N)->getIndex();
1469 if (!MFI.isFixedObjectIndex(ObjectIdx: FX) && HFI.needsAligna(MF: *MF))
1470 return false;
1471 R = CurDAG->getTargetFrameIndex(FI: FX, VT: MVT::i32);
1472 return true;
1473}
1474
1475inline bool HexagonDAGToDAGISel::SelectAddrGA(SDValue &N, SDValue &R) {
1476 return SelectGlobalAddress(N, R, UseGP: false, Alignment: Align(1));
1477}
1478
1479inline bool HexagonDAGToDAGISel::SelectAddrGP(SDValue &N, SDValue &R) {
1480 return SelectGlobalAddress(N, R, UseGP: true, Alignment: Align(1));
1481}
1482
1483inline bool HexagonDAGToDAGISel::SelectAnyImm(SDValue &N, SDValue &R) {
1484 return SelectAnyImmediate(N, R, Alignment: Align(1));
1485}
1486
1487inline bool HexagonDAGToDAGISel::SelectAnyImm0(SDValue &N, SDValue &R) {
1488 return SelectAnyImmediate(N, R, Alignment: Align(1));
1489}
1490inline bool HexagonDAGToDAGISel::SelectAnyImm1(SDValue &N, SDValue &R) {
1491 return SelectAnyImmediate(N, R, Alignment: Align(2));
1492}
1493inline bool HexagonDAGToDAGISel::SelectAnyImm2(SDValue &N, SDValue &R) {
1494 return SelectAnyImmediate(N, R, Alignment: Align(4));
1495}
1496inline bool HexagonDAGToDAGISel::SelectAnyImm3(SDValue &N, SDValue &R) {
1497 return SelectAnyImmediate(N, R, Alignment: Align(8));
1498}
1499
1500inline bool HexagonDAGToDAGISel::SelectAnyInt(SDValue &N, SDValue &R) {
1501 EVT T = N.getValueType();
1502 if (!T.isInteger() || T.getSizeInBits() != 32 || !isa<ConstantSDNode>(Val: N))
1503 return false;
1504 uint32_t V = cast<const ConstantSDNode>(Val&: N)->getZExtValue();
1505 R = CurDAG->getTargetConstant(Val: V, DL: SDLoc(N), VT: N.getValueType());
1506 return true;
1507}
1508
1509bool HexagonDAGToDAGISel::SelectAnyImmediate(SDValue &N, SDValue &R,
1510 Align Alignment) {
1511 switch (N.getOpcode()) {
1512 case ISD::Constant: {
1513 if (N.getValueType() != MVT::i32)
1514 return false;
1515 uint32_t V = cast<const ConstantSDNode>(Val&: N)->getZExtValue();
1516 if (!isAligned(Lhs: Alignment, SizeInBytes: V))
1517 return false;
1518 R = CurDAG->getTargetConstant(Val: V, DL: SDLoc(N), VT: N.getValueType());
1519 return true;
1520 }
1521 case HexagonISD::JT:
1522 case HexagonISD::CP:
1523 // These are assumed to always be aligned at least 8-byte boundary.
1524 if (Alignment > Align(8))
1525 return false;
1526 R = N.getOperand(i: 0);
1527 return true;
1528 case ISD::ExternalSymbol:
1529 // Symbols may be aligned at any boundary.
1530 if (Alignment > Align(1))
1531 return false;
1532 R = N;
1533 return true;
1534 case ISD::BlockAddress:
1535 // Block address is always aligned at least 4-byte boundary.
1536 if (Alignment > Align(4) ||
1537 !isAligned(Lhs: Alignment, SizeInBytes: cast<BlockAddressSDNode>(Val&: N)->getOffset()))
1538 return false;
1539 R = N;
1540 return true;
1541 }
1542
1543 if (SelectGlobalAddress(N, R, UseGP: false, Alignment) ||
1544 SelectGlobalAddress(N, R, UseGP: true, Alignment))
1545 return true;
1546
1547 return false;
1548}
1549
1550bool HexagonDAGToDAGISel::SelectGlobalAddress(SDValue &N, SDValue &R,
1551 bool UseGP, Align Alignment) {
1552 switch (N.getOpcode()) {
1553 case ISD::ADD: {
1554 SDValue N0 = N.getOperand(i: 0);
1555 SDValue N1 = N.getOperand(i: 1);
1556 unsigned GAOpc = N0.getOpcode();
1557 if (UseGP && GAOpc != HexagonISD::CONST32_GP)
1558 return false;
1559 if (!UseGP && GAOpc != HexagonISD::CONST32)
1560 return false;
1561 if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(Val&: N1)) {
1562 if (!isAligned(Lhs: Alignment, SizeInBytes: Const->getZExtValue()))
1563 return false;
1564 SDValue Addr = N0.getOperand(i: 0);
1565 if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Val&: Addr)) {
1566 if (GA->getOpcode() == ISD::TargetGlobalAddress) {
1567 uint64_t NewOff = GA->getOffset() + (uint64_t)Const->getSExtValue();
1568 R = CurDAG->getTargetGlobalAddress(GV: GA->getGlobal(), DL: SDLoc(Const),
1569 VT: N.getValueType(), offset: NewOff);
1570 return true;
1571 }
1572 }
1573 }
1574 break;
1575 }
1576 case HexagonISD::CP:
1577 case HexagonISD::JT:
1578 case HexagonISD::CONST32:
1579 // The operand(0) of CONST32 is TargetGlobalAddress, which is what we
1580 // want in the instruction.
1581 if (!UseGP)
1582 R = N.getOperand(i: 0);
1583 return !UseGP;
1584 case HexagonISD::CONST32_GP:
1585 if (UseGP)
1586 R = N.getOperand(i: 0);
1587 return UseGP;
1588 default:
1589 return false;
1590 }
1591
1592 return false;
1593}
1594
1595bool HexagonDAGToDAGISel::DetectUseSxtw(SDValue &N, SDValue &R) {
1596 // This (complex pattern) function is meant to detect a sign-extension
1597 // i32->i64 on a per-operand basis. This would allow writing single
1598 // patterns that would cover a number of combinations of different ways
1599 // a sign-extensions could be written. For example:
1600 // (mul (DetectUseSxtw x) (DetectUseSxtw y)) -> (M2_dpmpyss_s0 x y)
1601 // could match either one of these:
1602 // (mul (sext x) (sext_inreg y))
1603 // (mul (sext-load *p) (sext_inreg y))
1604 // (mul (sext_inreg x) (sext y))
1605 // etc.
1606 //
1607 // The returned value will have type i64 and its low word will
1608 // contain the value being extended. The high bits are not specified.
1609 // The returned type is i64 because the original type of N was i64,
1610 // but the users of this function should only use the low-word of the
1611 // result, e.g.
1612 // (mul sxtw:x, sxtw:y) -> (M2_dpmpyss_s0 (LoReg sxtw:x), (LoReg sxtw:y))
1613
1614 if (N.getValueType() != MVT::i64)
1615 return false;
1616 unsigned Opc = N.getOpcode();
1617 switch (Opc) {
1618 case ISD::SIGN_EXTEND:
1619 case ISD::SIGN_EXTEND_INREG: {
1620 // sext_inreg has the source type as a separate operand.
1621 EVT T = Opc == ISD::SIGN_EXTEND
1622 ? N.getOperand(i: 0).getValueType()
1623 : cast<VTSDNode>(Val: N.getOperand(i: 1))->getVT();
1624 unsigned SW = T.getSizeInBits();
1625 if (SW == 32)
1626 R = N.getOperand(i: 0);
1627 else if (SW < 32)
1628 R = N;
1629 else
1630 return false;
1631 break;
1632 }
1633 case ISD::LOAD: {
1634 LoadSDNode *L = cast<LoadSDNode>(Val&: N);
1635 if (L->getExtensionType() != ISD::SEXTLOAD)
1636 return false;
1637 // All extending loads extend to i32, so even if the value in
1638 // memory is shorter than 32 bits, it will be i32 after the load.
1639 if (L->getMemoryVT().getSizeInBits() > 32)
1640 return false;
1641 R = N;
1642 break;
1643 }
1644 case ISD::SRA: {
1645 auto *S = dyn_cast<ConstantSDNode>(Val: N.getOperand(i: 1));
1646 if (!S || S->getZExtValue() != 32)
1647 return false;
1648 R = N;
1649 break;
1650 }
1651 case ISD::AssertSext: {
1652 EVT T = cast<VTSDNode>(Val: N.getOperand(i: 1))->getVT();
1653 if (T.getSizeInBits() == 32)
1654 R = N.getOperand(i: 0);
1655 else
1656 return false;
1657 break;
1658 }
1659
1660 default:
1661 return false;
1662 }
1663 EVT RT = R.getValueType();
1664 if (RT == MVT::i64)
1665 return true;
1666 assert(RT == MVT::i32);
1667 // This is only to produce a value of type i64. Do not rely on the
1668 // high bits produced by this.
1669 const SDLoc &dl(N);
1670 SDValue Ops[] = {
1671 CurDAG->getTargetConstant(Val: Hexagon::DoubleRegsRegClassID, DL: dl, VT: MVT::i32),
1672 R, CurDAG->getTargetConstant(Val: Hexagon::isub_hi, DL: dl, VT: MVT::i32),
1673 R, CurDAG->getTargetConstant(Val: Hexagon::isub_lo, DL: dl, VT: MVT::i32)
1674 };
1675 SDNode *T = CurDAG->getMachineNode(Opcode: TargetOpcode::REG_SEQUENCE, dl,
1676 VT: MVT::i64, Ops);
1677 R = SDValue(T, 0);
1678 return true;
1679}
1680
1681bool HexagonDAGToDAGISel::DetectUseSxth(SDValue &N, SDValue &R) {
1682 // This (complex pattern) function is meant to detect a sign-extension
1683 // i16->i32 or i16->vXi32 on a per-operand basis. This would allow writing
1684 // single patterns that would cover a number of combinations of different ways
1685 // a sign-extension could be written. For example:
1686 // (sra x (DetectUseSxth y)) -> (LX_shr_w_w x y)
1687 // could match either one of these:
1688 // (sra x (sext_inreg y))
1689 // (sra x (sext_inreg y))
1690 // (sra x (sext y))
1691 // etc.
1692 //
1693 // The returned value will have type i32 and will contain the value
1694 // being extended. The high bits are not specified.
1695 // The returned type is i32 because the original type of N was i32.
1696
1697 EVT RetTy = N.getValueType();
1698 if (RetTy != MVT::i32 &&
1699 (!RetTy.isVector() || RetTy.getVectorElementType() != MVT::i32))
1700 return false;
1701 unsigned Opc = N.getOpcode();
1702 switch (Opc) {
1703 case ISD::SIGN_EXTEND:
1704 case ISD::SIGN_EXTEND_INREG: {
1705 // sext_inreg has the source type as a separate operand.
1706 EVT T = Opc == ISD::SIGN_EXTEND ? N.getOperand(i: 0).getValueType()
1707 : cast<VTSDNode>(Val: N.getOperand(i: 1))->getVT();
1708 if (T.isVector())
1709 T = T.getVectorElementType();
1710 unsigned SW = T.getSizeInBits();
1711 if (SW > 16)
1712 return false;
1713 // Only an exactly-16-bit sign_extend_inreg may be unwrapped to its i32
1714 // operand. Consumers of the returned value (e.g. mpy(Rs.l/.h, ..)) read
1715 // just the low 16 bits and rely on those bits already holding the fully
1716 // sign-extended value, which is true only when the inreg width is 16.
1717 // For SW < 16 the high bits of operand 0 are not sign-filled -- e.g.
1718 // (sext_inreg X, i8) with X = 0x00000080 is -128, but bits [15:0] of
1719 // operand 0 are 0x0080 = +128 -- so the extension must be kept and the
1720 // node itself returned. AssertSext below gates on == 16 for the same
1721 // reason. SIGN_EXTEND always returns the node: its operand is a
1722 // narrower type (e.g. i16) that would fail the i32 result-type check.
1723 R = (Opc == ISD::SIGN_EXTEND_INREG && SW == 16) ? N.getOperand(i: 0) : N;
1724 break;
1725 }
1726 case ISD::LOAD: {
1727 LoadSDNode *L = cast<LoadSDNode>(Val&: N);
1728 if (L->getExtensionType() != ISD::SEXTLOAD)
1729 return false;
1730 // All extending loads extend to i32, so even if the value in
1731 // memory is shorter than 16 bits, it will be i32 after the load.
1732 if (L->getMemoryVT().getSizeInBits() > 16)
1733 return false;
1734 R = N;
1735 break;
1736 }
1737 case ISD::AssertSext: {
1738 EVT T = cast<VTSDNode>(Val: N.getOperand(i: 1))->getVT();
1739 if (T.isVector())
1740 T = T.getVectorElementType();
1741 if (T.getSizeInBits() == 16)
1742 R = N.getOperand(i: 0);
1743 else
1744 return false;
1745 break;
1746 }
1747 default:
1748 return false;
1749 }
1750 EVT RT = R.getValueType();
1751 if (RT == MVT::i32 ||
1752 (RT.isVector() && RT.getVectorElementType() == MVT::i32))
1753 return true;
1754 return false;
1755}
1756
1757/// Return the constant value of a node if it is a ConstantSDNode, or if it
1758/// is a SPLAT_VECTOR / BUILD_VECTOR whose all elements are the same constant.
1759/// Returns true and sets Val on success.
1760static bool getConstantSplatValue(SDValue N, uint64_t &Val) {
1761 if (auto *C = dyn_cast<ConstantSDNode>(Val&: N)) {
1762 Val = C->getZExtValue();
1763 return true;
1764 }
1765 if (N.getOpcode() == ISD::SPLAT_VECTOR) {
1766 if (auto *C = dyn_cast<ConstantSDNode>(Val: N.getOperand(i: 0))) {
1767 Val = C->getZExtValue();
1768 return true;
1769 }
1770 return false;
1771 }
1772 if (N.getOpcode() == ISD::BUILD_VECTOR) {
1773 auto *C0 = dyn_cast<ConstantSDNode>(Val: N.getOperand(i: 0));
1774 if (!C0)
1775 return false;
1776 Val = C0->getZExtValue();
1777 for (unsigned I = 1, E = N.getNumOperands(); I != E; ++I) {
1778 auto *CI = dyn_cast<ConstantSDNode>(Val: N.getOperand(i: I));
1779 if (!CI || CI->getZExtValue() != Val)
1780 return false;
1781 }
1782 return true;
1783 }
1784 return false;
1785}
1786
1787bool HexagonDAGToDAGISel::DetectUseZxth(SDValue &N, SDValue &R) {
1788 // This (complex pattern) function is meant to detect a zero-extension
1789 // i16->i32 or i16->vXi32 on a per-operand basis. This would allow writing
1790 // single patterns that would cover a number of combinations of different ways
1791 // a zero-extension could be written. For example:
1792 // (srl x (DetectUseZxth y)) -> (LX_shr_uw_uw x y)
1793 // could match either one of these:
1794 // (srl x (and y, 0xFFFF))
1795 // (srl x (zext y))
1796 // (srl x (AssertZext y))
1797 // etc.
1798 //
1799 // The returned value will have type i32 and will contain the value
1800 // being extended. The high bits are not specified.
1801 // The returned type is i32 because the original type of N was i32.
1802
1803 EVT RetTy = N.getValueType();
1804 if (RetTy != MVT::i32 &&
1805 (!RetTy.isVector() || RetTy.getVectorElementType() != MVT::i32))
1806 return false;
1807 unsigned Opc = N.getOpcode();
1808 switch (Opc) {
1809 case ISD::ZERO_EXTEND: {
1810 EVT T = N.getOperand(i: 0).getValueType();
1811 if (T.isVector())
1812 T = T.getVectorElementType();
1813 unsigned SW = T.getSizeInBits();
1814 if (SW <= 16)
1815 R = N;
1816 else
1817 return false;
1818 break;
1819 }
1820 case ISD::LOAD: {
1821 LoadSDNode *L = cast<LoadSDNode>(Val&: N);
1822 if (L->getExtensionType() != ISD::ZEXTLOAD)
1823 return false;
1824 // All extending loads extend to i32, so even if the value in
1825 // memory is shorter than 16 bits, it will be i32 after the load.
1826 if (L->getMemoryVT().getSizeInBits() > 16)
1827 return false;
1828 R = N;
1829 break;
1830 }
1831 case ISD::AssertZext: {
1832 EVT T = cast<VTSDNode>(Val: N.getOperand(i: 1))->getVT();
1833 if (T.isVector())
1834 T = T.getVectorElementType();
1835 if (T.getSizeInBits() == 16)
1836 R = N.getOperand(i: 0);
1837 else
1838 return false;
1839 break;
1840 }
1841 case ISD::SPLAT_VECTOR:
1842 case ISD::BUILD_VECTOR: {
1843 // Detect a splat/broadcast of a value that fits in 16 bits.
1844 // Case 1: constant splat with value <= 0xFFFF.
1845 uint64_t Val = 0;
1846 if (getConstantSplatValue(N, Val) && Val <= 0xFFFF) {
1847 R = N;
1848 break;
1849 }
1850 // Case 2: splat of a scalar that is itself a 16-bit zero-extension
1851 // (e.g. splat_vector(zext i16 x) or splat_vector(AssertZext x, i16)).
1852 // Only applies to SPLAT_VECTOR (single scalar operand).
1853 if (N.getOpcode() == ISD::SPLAT_VECTOR) {
1854 SDValue ScalarOp = N.getOperand(i: 0);
1855 unsigned ScalarOpc = ScalarOp.getOpcode();
1856 if (ScalarOpc == ISD::ZERO_EXTEND) {
1857 EVT T = ScalarOp.getOperand(i: 0).getValueType();
1858 if (T.isInteger() && T.getSizeInBits() <= 16) {
1859 R = N;
1860 break;
1861 }
1862 } else if (ScalarOpc == ISD::AssertZext) {
1863 EVT T = cast<VTSDNode>(Val: ScalarOp.getOperand(i: 1))->getVT();
1864 if (T.isInteger() && T.getSizeInBits() <= 16) {
1865 R = N;
1866 break;
1867 }
1868 }
1869 }
1870 return false;
1871 }
1872 case ISD::AND: {
1873 // Detect (and x, 0xFFFF) pattern — works for both scalar and vector
1874 // (splat_vector / BUILD_VECTOR of 0xFFFF).
1875 uint64_t Mask = 0;
1876 if (getConstantSplatValue(N: N.getOperand(i: 1), Val&: Mask) && Mask == 0xFFFF) {
1877 R = N.getOperand(i: 0);
1878 break;
1879 }
1880 return false;
1881 }
1882 case ISD::SRL: {
1883 // Detect (srl x, C) where C >= 16: the result fits in 16 bits because
1884 // shifting a 32-bit value right by at least 16 positions leaves at most
1885 // 16 significant bits. This covers patterns like (lshr x, splat(16))
1886 // that appear in fixed-point polynomial approximations.
1887 uint64_t ShiftVal = 0;
1888 if (getConstantSplatValue(N: N.getOperand(i: 1), Val&: ShiftVal) && ShiftVal >= 16) {
1889 R = N;
1890 break;
1891 }
1892 return false;
1893 }
1894 default:
1895 return false;
1896 }
1897 EVT RT = R.getValueType();
1898 if (RT == MVT::i32 ||
1899 (RT.isVector() && RT.getVectorElementType() == MVT::i32)) {
1900 return true;
1901 }
1902 return false;
1903}
1904
1905bool HexagonDAGToDAGISel::keepsLowBits(const SDValue &Val, unsigned NumBits,
1906 SDValue &Src) {
1907 unsigned Opc = Val.getOpcode();
1908 switch (Opc) {
1909 case ISD::SIGN_EXTEND:
1910 case ISD::ZERO_EXTEND:
1911 case ISD::ANY_EXTEND: {
1912 const SDValue &Op0 = Val.getOperand(i: 0);
1913 EVT T = Op0.getValueType();
1914 if (T.isInteger() && T.getSizeInBits() == NumBits) {
1915 Src = Op0;
1916 return true;
1917 }
1918 break;
1919 }
1920 case ISD::SIGN_EXTEND_INREG:
1921 case ISD::AssertSext:
1922 case ISD::AssertZext:
1923 if (Val.getOperand(i: 0).getValueType().isInteger()) {
1924 VTSDNode *T = cast<VTSDNode>(Val: Val.getOperand(i: 1));
1925 if (T->getVT().getSizeInBits() == NumBits) {
1926 Src = Val.getOperand(i: 0);
1927 return true;
1928 }
1929 }
1930 break;
1931 case ISD::AND: {
1932 // Check if this is an AND with NumBits of lower bits set to 1.
1933 uint64_t Mask = (1ULL << NumBits) - 1;
1934 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val: Val.getOperand(i: 0))) {
1935 if (C->getZExtValue() == Mask) {
1936 Src = Val.getOperand(i: 1);
1937 return true;
1938 }
1939 }
1940 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val: Val.getOperand(i: 1))) {
1941 if (C->getZExtValue() == Mask) {
1942 Src = Val.getOperand(i: 0);
1943 return true;
1944 }
1945 }
1946 break;
1947 }
1948 case ISD::OR:
1949 case ISD::XOR: {
1950 // OR/XOR with the lower NumBits bits set to 0.
1951 uint64_t Mask = (1ULL << NumBits) - 1;
1952 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val: Val.getOperand(i: 0))) {
1953 if ((C->getZExtValue() & Mask) == 0) {
1954 Src = Val.getOperand(i: 1);
1955 return true;
1956 }
1957 }
1958 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val: Val.getOperand(i: 1))) {
1959 if ((C->getZExtValue() & Mask) == 0) {
1960 Src = Val.getOperand(i: 0);
1961 return true;
1962 }
1963 }
1964 break;
1965 }
1966 default:
1967 break;
1968 }
1969 return false;
1970}
1971
1972bool HexagonDAGToDAGISel::isAlignedMemNode(const MemSDNode *N) const {
1973 return N->getAlign().value() >= N->getMemoryVT().getStoreSize();
1974}
1975
1976bool HexagonDAGToDAGISel::isSmallStackStore(const StoreSDNode *N) const {
1977 unsigned StackSize = MF->getFrameInfo().estimateStackSize(MF: *MF);
1978 switch (N->getMemoryVT().getStoreSize()) {
1979 case 1:
1980 return StackSize <= 56; // 1*2^6 - 8
1981 case 2:
1982 return StackSize <= 120; // 2*2^6 - 8
1983 case 4:
1984 return StackSize <= 248; // 4*2^6 - 8
1985 default:
1986 return false;
1987 }
1988}
1989
1990// Return true when the given node fits in a positive half word.
1991bool HexagonDAGToDAGISel::isPositiveHalfWord(const SDNode *N) const {
1992 if (const ConstantSDNode *CN = dyn_cast<const ConstantSDNode>(Val: N)) {
1993 int64_t V = CN->getSExtValue();
1994 return V > 0 && isInt<16>(x: V);
1995 }
1996 if (N->getOpcode() == ISD::SIGN_EXTEND_INREG) {
1997 const VTSDNode *VN = dyn_cast<const VTSDNode>(Val: N->getOperand(Num: 1));
1998 return VN->getVT().getSizeInBits() <= 16;
1999 }
2000 return false;
2001}
2002
2003bool HexagonDAGToDAGISel::hasOneUse(const SDNode *N) const {
2004 return !CheckSingleUse || N->hasOneUse();
2005}
2006
2007////////////////////////////////////////////////////////////////////////////////
2008// Rebalancing of address calculation trees
2009
2010static bool isOpcodeHandled(const SDNode *N) {
2011 switch (N->getOpcode()) {
2012 case ISD::ADD:
2013 case ISD::MUL:
2014 return true;
2015 case ISD::SHL:
2016 // We only handle constant shifts because these can be easily flattened
2017 // into multiplications by 2^Op1.
2018 return N->getNumOperands() >= 2 &&
2019 isa<ConstantSDNode>(Val: N->getOperand(Num: 1).getNode());
2020 default:
2021 return false;
2022 }
2023}
2024
2025/// Return the weight of an SDNode
2026int HexagonDAGToDAGISel::getWeight(SDNode *N) {
2027 if (!isOpcodeHandled(N))
2028 return 1;
2029 assert(RootWeights.count(N) && "Cannot get weight of unseen root!");
2030 assert(RootWeights[N] != -1 && "Cannot get weight of unvisited root!");
2031 assert(RootWeights[N] != -2 && "Cannot get weight of RAWU'd root!");
2032 return RootWeights[N];
2033}
2034
2035int HexagonDAGToDAGISel::getHeight(SDNode *N) {
2036 if (!isOpcodeHandled(N))
2037 return 0;
2038 assert(RootWeights.count(N) && RootWeights[N] >= 0 &&
2039 "Cannot query height of unvisited/RAUW'd node!");
2040 return RootHeights[N];
2041}
2042
2043namespace {
2044struct WeightedLeaf {
2045 SDValue Value;
2046 int Weight;
2047 int InsertionOrder;
2048
2049 WeightedLeaf() = default;
2050
2051 WeightedLeaf(SDValue Value, int Weight, int InsertionOrder) :
2052 Value(Value), Weight(Weight), InsertionOrder(InsertionOrder) {
2053 assert(Weight >= 0 && "Weight must be >= 0");
2054 }
2055
2056 static bool Compare(const WeightedLeaf &A, const WeightedLeaf &B) {
2057 assert(A.Value.getNode() && B.Value.getNode());
2058 return A.Weight == B.Weight ?
2059 (A.InsertionOrder > B.InsertionOrder) :
2060 (A.Weight > B.Weight);
2061 }
2062};
2063
2064/// A specialized priority queue for WeigthedLeaves. It automatically folds
2065/// constants and allows removal of non-top elements while maintaining the
2066/// priority order.
2067class LeafPrioQueue {
2068 SmallVector<WeightedLeaf, 8> Q;
2069 bool HaveConst;
2070 WeightedLeaf ConstElt;
2071 unsigned Opcode;
2072
2073public:
2074 bool empty() {
2075 return (!HaveConst && Q.empty());
2076 }
2077
2078 size_t size() {
2079 return Q.size() + HaveConst;
2080 }
2081
2082 bool hasConst() {
2083 return HaveConst;
2084 }
2085
2086 const WeightedLeaf &top() {
2087 if (HaveConst)
2088 return ConstElt;
2089 return Q.front();
2090 }
2091
2092 WeightedLeaf pop() {
2093 if (HaveConst) {
2094 HaveConst = false;
2095 return ConstElt;
2096 }
2097 std::pop_heap(first: Q.begin(), last: Q.end(), comp: WeightedLeaf::Compare);
2098 return Q.pop_back_val();
2099 }
2100
2101 void push(WeightedLeaf L, bool SeparateConst=true) {
2102 if (!HaveConst && SeparateConst && isa<ConstantSDNode>(Val: L.Value)) {
2103 if (Opcode == ISD::MUL &&
2104 cast<ConstantSDNode>(Val&: L.Value)->getSExtValue() == 1)
2105 return;
2106 if (Opcode == ISD::ADD &&
2107 cast<ConstantSDNode>(Val&: L.Value)->getSExtValue() == 0)
2108 return;
2109
2110 HaveConst = true;
2111 ConstElt = L;
2112 } else {
2113 Q.push_back(Elt: L);
2114 std::push_heap(first: Q.begin(), last: Q.end(), comp: WeightedLeaf::Compare);
2115 }
2116 }
2117
2118 /// Push L to the bottom of the queue regardless of its weight. If L is
2119 /// constant, it will not be folded with other constants in the queue.
2120 void pushToBottom(WeightedLeaf L) {
2121 L.Weight = 1000;
2122 push(L, SeparateConst: false);
2123 }
2124
2125 /// Search for a SHL(x, [<=MaxAmount]) subtree in the queue, return the one of
2126 /// lowest weight and remove it from the queue.
2127 WeightedLeaf findSHL(uint64_t MaxAmount);
2128
2129 WeightedLeaf findMULbyConst();
2130
2131 LeafPrioQueue(unsigned Opcode) :
2132 HaveConst(false), Opcode(Opcode) { }
2133};
2134} // end anonymous namespace
2135
2136WeightedLeaf LeafPrioQueue::findSHL(uint64_t MaxAmount) {
2137 int ResultPos;
2138 WeightedLeaf Result;
2139
2140 for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
2141 const WeightedLeaf &L = Q[Pos];
2142 const SDValue &Val = L.Value;
2143 if (Val.getOpcode() != ISD::SHL || Val.getNumOperands() < 2 ||
2144 !isa<ConstantSDNode>(Val: Val.getOperand(i: 1)) ||
2145 Val.getConstantOperandVal(i: 1) > MaxAmount)
2146 continue;
2147 if (!Result.Value.getNode() || Result.Weight > L.Weight ||
2148 (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
2149 {
2150 Result = L;
2151 ResultPos = Pos;
2152 }
2153 }
2154
2155 if (Result.Value.getNode()) {
2156 Q.erase(CI: &Q[ResultPos]);
2157 std::make_heap(first: Q.begin(), last: Q.end(), comp: WeightedLeaf::Compare);
2158 }
2159
2160 return Result;
2161}
2162
2163WeightedLeaf LeafPrioQueue::findMULbyConst() {
2164 int ResultPos;
2165 WeightedLeaf Result;
2166
2167 for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
2168 const WeightedLeaf &L = Q[Pos];
2169 const SDValue &Val = L.Value;
2170 if (Val.getOpcode() != ISD::MUL || Val.getNumOperands() < 2 ||
2171 !isa<ConstantSDNode>(Val: Val.getOperand(i: 1)) ||
2172 Val.getConstantOperandVal(i: 1) > 127)
2173 continue;
2174 if (!Result.Value.getNode() || Result.Weight > L.Weight ||
2175 (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
2176 {
2177 Result = L;
2178 ResultPos = Pos;
2179 }
2180 }
2181
2182 if (Result.Value.getNode()) {
2183 Q.erase(CI: &Q[ResultPos]);
2184 std::make_heap(first: Q.begin(), last: Q.end(), comp: WeightedLeaf::Compare);
2185 }
2186
2187 return Result;
2188}
2189
2190SDValue HexagonDAGToDAGISel::getMultiplierForSHL(SDNode *N) {
2191 if (N->getNumOperands() < 2)
2192 return SDValue();
2193 uint64_t MulFactor = 1ull << N->getConstantOperandVal(Num: 1);
2194 return CurDAG->getConstant(Val: MulFactor, DL: SDLoc(N),
2195 VT: N->getOperand(Num: 1).getValueType());
2196}
2197
2198/// @returns the value x for which 2^x is a factor of Val
2199static unsigned getPowerOf2Factor(SDValue Val) {
2200 if (Val.getOpcode() == ISD::MUL) {
2201 if (Val.getNumOperands() < 2)
2202 return 0;
2203 unsigned MaxFactor = 0;
2204 for (int i = 0; i < 2; ++i) {
2205 ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val: Val.getOperand(i));
2206 if (!C)
2207 continue;
2208 const APInt &CInt = C->getAPIntValue();
2209 if (CInt.getBoolValue())
2210 MaxFactor = CInt.countr_zero();
2211 }
2212 return MaxFactor;
2213 }
2214 if (Val.getOpcode() == ISD::SHL) {
2215 if (Val.getNumOperands() < 2 ||
2216 !isa<ConstantSDNode>(Val: Val.getOperand(i: 1).getNode()))
2217 return 0;
2218 return (unsigned) Val.getConstantOperandVal(i: 1);
2219 }
2220
2221 return 0;
2222}
2223
2224/// @returns true if V>>Amount will eliminate V's operation on its child
2225static bool willShiftRightEliminate(SDValue V, unsigned Amount) {
2226 if (V.getOpcode() == ISD::MUL) {
2227 if (V.getNumOperands() < 2)
2228 return false;
2229 SDValue Ops[] = { V.getOperand(i: 0), V.getOperand(i: 1) };
2230 for (int i = 0; i < 2; ++i)
2231 if (isa<ConstantSDNode>(Val: Ops[i].getNode()) &&
2232 V.getConstantOperandVal(i) % (1ULL << Amount) == 0) {
2233 uint64_t NewConst = V.getConstantOperandVal(i) >> Amount;
2234 return (NewConst == 1);
2235 }
2236 } else if (V.getOpcode() == ISD::SHL) {
2237 if (V.getNumOperands() < 2 ||
2238 !isa<ConstantSDNode>(Val: V.getOperand(i: 1).getNode()))
2239 return false;
2240 return (Amount == V.getConstantOperandVal(i: 1));
2241 }
2242
2243 return false;
2244}
2245
2246SDValue HexagonDAGToDAGISel::factorOutPowerOf2(SDValue V, unsigned Power) {
2247 // Ensure the node has at least 2 operands before accessing them.
2248 if (V.getNumOperands() < 2)
2249 return V;
2250
2251 SDValue Ops[] = { V.getOperand(i: 0), V.getOperand(i: 1) };
2252 if (V.getOpcode() == ISD::MUL) {
2253 for (int i=0; i < 2; ++i) {
2254 if (isa<ConstantSDNode>(Val: Ops[i].getNode()) &&
2255 V.getConstantOperandVal(i) % ((uint64_t)1 << Power) == 0) {
2256 uint64_t NewConst = V.getConstantOperandVal(i) >> Power;
2257 if (NewConst == 1)
2258 return Ops[!i];
2259 Ops[i] = CurDAG->getConstant(Val: NewConst,
2260 DL: SDLoc(V), VT: V.getValueType());
2261 break;
2262 }
2263 }
2264 } else if (V.getOpcode() == ISD::SHL) {
2265 if (!isa<ConstantSDNode>(Val: V.getOperand(i: 1).getNode()))
2266 return V;
2267 uint64_t ShiftAmount = V.getConstantOperandVal(i: 1);
2268 if (ShiftAmount == Power)
2269 return Ops[0];
2270 Ops[1] = CurDAG->getConstant(Val: ShiftAmount - Power,
2271 DL: SDLoc(V), VT: V.getValueType());
2272 }
2273
2274 return CurDAG->getNode(Opcode: V.getOpcode(), DL: SDLoc(V), VT: V.getValueType(), Ops);
2275}
2276
2277static bool isTargetConstant(const SDValue &V) {
2278 return V.getOpcode() == HexagonISD::CONST32 ||
2279 V.getOpcode() == HexagonISD::CONST32_GP;
2280}
2281
2282unsigned HexagonDAGToDAGISel::getUsesInFunction(const Value *V) {
2283 auto [It, Inserted] = GAUsesInFunction.try_emplace(Key: V);
2284 if (!Inserted)
2285 return It->second;
2286
2287 unsigned Result = 0;
2288 const Function &CurF = CurDAG->getMachineFunction().getFunction();
2289 for (const User *U : V->users()) {
2290 if (isa<Instruction>(Val: U) &&
2291 cast<Instruction>(Val: U)->getParent()->getParent() == &CurF)
2292 ++Result;
2293 }
2294
2295 It->second = Result;
2296
2297 return Result;
2298}
2299
2300/// Note - After calling this, N may be dead. It may have been replaced by a
2301/// new node, so always use the returned value in place of N.
2302///
2303/// @returns The SDValue taking the place of N (which could be N if it is
2304/// unchanged)
2305SDValue HexagonDAGToDAGISel::balanceSubTree(SDNode *N, bool TopLevel) {
2306 assert(RootWeights.count(N) && "Cannot balance non-root node.");
2307 assert(RootWeights[N] != -2 && "This node was RAUW'd!");
2308 assert(!TopLevel || N->getOpcode() == ISD::ADD);
2309
2310 // Return early if this node was already visited
2311 if (RootWeights[N] != -1)
2312 return SDValue(N, 0);
2313
2314 assert(isOpcodeHandled(N));
2315
2316 if (N->getNumOperands() < 2)
2317 return SDValue(N, 0);
2318
2319 SDValue Op0 = N->getOperand(Num: 0);
2320 SDValue Op1 = N->getOperand(Num: 1);
2321
2322 // Return early if the operands will remain unchanged or are all roots
2323 if ((!isOpcodeHandled(N: Op0.getNode()) || RootWeights.count(Val: Op0.getNode())) &&
2324 (!isOpcodeHandled(N: Op1.getNode()) || RootWeights.count(Val: Op1.getNode()))) {
2325 SDNode *Op0N = Op0.getNode();
2326 int Weight;
2327 if (isOpcodeHandled(N: Op0N) && RootWeights[Op0N] == -1) {
2328 Weight = getWeight(N: balanceSubTree(N: Op0N).getNode());
2329 // Weight = calculateWeight(Op0N);
2330 } else
2331 Weight = getWeight(N: Op0N);
2332
2333 SDNode *Op1N = Op1.getNode();
2334 if (isOpcodeHandled(N: Op1N) && RootWeights[Op1N] == -1) {
2335 Weight += getWeight(N: balanceSubTree(N: Op1N).getNode());
2336 // Weight += calculateWeight(Op1N);
2337 } else
2338 Weight += getWeight(N: Op1N);
2339
2340 RootWeights[N] = Weight;
2341
2342 // After recursive calls, check if Op0/Op1 are still valid before getting
2343 // height
2344 int Height0 = 0, Height1 = 0;
2345 if (isOpcodeHandled(N: Op0N) && RootWeights.count(Val: Op0N) &&
2346 RootWeights[Op0N] >= 0)
2347 Height0 = getHeight(N: Op0N);
2348 if (isOpcodeHandled(N: Op1N) && RootWeights.count(Val: Op1N) &&
2349 RootWeights[Op1N] >= 0)
2350 Height1 = getHeight(N: Op1N);
2351
2352 RootHeights[N] = std::max(a: Height0, b: Height1) + 1;
2353
2354 LLVM_DEBUG(dbgs() << "--> No need to balance root (Weight=" << Weight
2355 << " Height=" << RootHeights[N] << "): ");
2356 LLVM_DEBUG(N->dump(CurDAG));
2357
2358 return SDValue(N, 0);
2359 }
2360
2361 LLVM_DEBUG(dbgs() << "** Balancing root node: ");
2362 LLVM_DEBUG(N->dump(CurDAG));
2363
2364 unsigned NOpcode = N->getOpcode();
2365
2366 LeafPrioQueue Leaves(NOpcode);
2367 SmallVector<SDValue, 4> Worklist;
2368 Worklist.push_back(Elt: SDValue(N, 0));
2369
2370 // SHL nodes will be converted to MUL nodes
2371 if (NOpcode == ISD::SHL)
2372 NOpcode = ISD::MUL;
2373
2374 bool CanFactorize = false;
2375 WeightedLeaf Mul1, Mul2;
2376 unsigned MaxPowerOf2 = 0;
2377 WeightedLeaf GA;
2378
2379 // Do not try to factor out a shift if there is already a shift at the tip of
2380 // the tree.
2381 bool HaveTopLevelShift = false;
2382 if (TopLevel &&
2383 ((isOpcodeHandled(N: Op0.getNode()) && Op0.getOpcode() == ISD::SHL &&
2384 Op0.getNumOperands() >= 2 && Op0.getConstantOperandVal(i: 1) < 4) ||
2385 (isOpcodeHandled(N: Op1.getNode()) && Op1.getOpcode() == ISD::SHL &&
2386 Op1.getNumOperands() >= 2 && Op1.getConstantOperandVal(i: 1) < 4)))
2387 HaveTopLevelShift = true;
2388
2389 // Flatten the subtree into an ordered list of leaves; at the same time
2390 // determine whether the tree is already balanced.
2391 int InsertionOrder = 0;
2392 SmallDenseMap<SDValue, int> NodeHeights;
2393 bool Imbalanced = false;
2394 int CurrentWeight = 0;
2395 while (!Worklist.empty()) {
2396 SDValue Child = Worklist.pop_back_val();
2397
2398 if (Child.getNode() != N && RootWeights.count(Val: Child.getNode())) {
2399 // CASE 1: Child is a root note
2400
2401 int Weight = RootWeights[Child.getNode()];
2402 if (Weight == -1) {
2403 Child = balanceSubTree(N: Child.getNode());
2404 // calculateWeight(Child.getNode());
2405 Weight = getWeight(N: Child.getNode());
2406 } else if (Weight == -2) {
2407 // Whoops, this node was RAUWd by one of the balanceSubTree calls we
2408 // made. Our worklist isn't up to date anymore.
2409 // Restart the whole process.
2410 LLVM_DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");
2411 return balanceSubTree(N, TopLevel);
2412 }
2413
2414 NodeHeights[Child] = 1;
2415 CurrentWeight += Weight;
2416
2417 unsigned PowerOf2;
2418 if (TopLevel && !CanFactorize && !HaveTopLevelShift &&
2419 (Child.getOpcode() == ISD::MUL || Child.getOpcode() == ISD::SHL) &&
2420 Child.hasOneUse() && (PowerOf2 = getPowerOf2Factor(Val: Child))) {
2421 // Try to identify two factorizable MUL/SHL children greedily. Leave
2422 // them out of the priority queue for now so we can deal with them
2423 // after.
2424 if (!Mul1.Value.getNode()) {
2425 Mul1 = WeightedLeaf(Child, Weight, InsertionOrder++);
2426 MaxPowerOf2 = PowerOf2;
2427 } else {
2428 Mul2 = WeightedLeaf(Child, Weight, InsertionOrder++);
2429 MaxPowerOf2 = std::min(a: MaxPowerOf2, b: PowerOf2);
2430
2431 // Our addressing modes can only shift by a maximum of 3
2432 if (MaxPowerOf2 > 3)
2433 MaxPowerOf2 = 3;
2434
2435 CanFactorize = true;
2436 }
2437 } else
2438 Leaves.push(L: WeightedLeaf(Child, Weight, InsertionOrder++));
2439 } else if (!isOpcodeHandled(N: Child.getNode())) {
2440 // CASE 2: Child is an unhandled kind of node (e.g. constant)
2441 int Weight = getWeight(N: Child.getNode());
2442
2443 NodeHeights[Child] = getHeight(N: Child.getNode());
2444 CurrentWeight += Weight;
2445
2446 if (isTargetConstant(V: Child) && !GA.Value.getNode())
2447 GA = WeightedLeaf(Child, Weight, InsertionOrder++);
2448 else
2449 Leaves.push(L: WeightedLeaf(Child, Weight, InsertionOrder++));
2450 } else {
2451 // CASE 3: Child is a subtree of same opcode
2452 // Visit children first, then flatten.
2453 unsigned ChildOpcode = Child.getOpcode();
2454 assert(ChildOpcode == NOpcode ||
2455 (NOpcode == ISD::MUL && ChildOpcode == ISD::SHL));
2456
2457 if (Child->getNumOperands() < 2) {
2458 // Treat as a leaf if not enough operands
2459 int Weight = getWeight(N: Child.getNode());
2460 NodeHeights[Child] = getHeight(N: Child.getNode());
2461 CurrentWeight += Weight;
2462 Leaves.push(L: WeightedLeaf(Child, Weight, InsertionOrder++));
2463 continue;
2464 }
2465
2466 // Convert SHL to MUL
2467 SDValue Op1;
2468 if (ChildOpcode == ISD::SHL) {
2469 Op1 = getMultiplierForSHL(N: Child.getNode());
2470 assert(Op1.getNode() && "getMultiplierForSHL returned null");
2471 } else
2472 Op1 = Child->getOperand(Num: 1);
2473
2474 if (!NodeHeights.count(Val: Op1) || !NodeHeights.count(Val: Child->getOperand(Num: 0))) {
2475 assert(!NodeHeights.count(Child) && "Parent visited before children?");
2476 // Visit children first, then re-visit this node
2477 Worklist.push_back(Elt: Child);
2478 Worklist.push_back(Elt: Op1);
2479 Worklist.push_back(Elt: Child->getOperand(Num: 0));
2480 } else {
2481 // Back at this node after visiting the children
2482 if (std::abs(x: NodeHeights[Op1] - NodeHeights[Child->getOperand(Num: 0)]) > 1)
2483 Imbalanced = true;
2484
2485 NodeHeights[Child] = std::max(a: NodeHeights[Op1],
2486 b: NodeHeights[Child->getOperand(Num: 0)]) + 1;
2487 }
2488 }
2489 }
2490
2491 LLVM_DEBUG(dbgs() << "--> Current height=" << NodeHeights[SDValue(N, 0)]
2492 << " weight=" << CurrentWeight
2493 << " imbalanced=" << Imbalanced << "\n");
2494
2495 // Transform MUL(x, C * 2^Y) + SHL(z, Y) -> SHL(ADD(MUL(x, C), z), Y)
2496 // This factors out a shift in order to match memw(a<<Y+b).
2497 if (CanFactorize && (willShiftRightEliminate(V: Mul1.Value, Amount: MaxPowerOf2) ||
2498 willShiftRightEliminate(V: Mul2.Value, Amount: MaxPowerOf2))) {
2499 LLVM_DEBUG(dbgs() << "--> Found common factor for two MUL children!\n");
2500 int Weight = Mul1.Weight + Mul2.Weight;
2501 int Height = std::max(a: NodeHeights[Mul1.Value], b: NodeHeights[Mul2.Value]) + 1;
2502 SDValue Mul1Factored = factorOutPowerOf2(V: Mul1.Value, Power: MaxPowerOf2);
2503 SDValue Mul2Factored = factorOutPowerOf2(V: Mul2.Value, Power: MaxPowerOf2);
2504 SDValue Sum = CurDAG->getNode(Opcode: ISD::ADD, DL: SDLoc(N), VT: Mul1.Value.getValueType(),
2505 N1: Mul1Factored, N2: Mul2Factored);
2506 SDValue Const = CurDAG->getConstant(Val: MaxPowerOf2, DL: SDLoc(N),
2507 VT: Mul1.Value.getValueType());
2508 SDValue New = CurDAG->getNode(Opcode: ISD::SHL, DL: SDLoc(N), VT: Mul1.Value.getValueType(),
2509 N1: Sum, N2: Const);
2510 NodeHeights[New] = Height;
2511 Leaves.push(L: WeightedLeaf(New, Weight, Mul1.InsertionOrder));
2512 } else if (Mul1.Value.getNode()) {
2513 // We failed to factorize two MULs, so now the Muls are left outside the
2514 // queue... add them back.
2515 Leaves.push(L: Mul1);
2516 if (Mul2.Value.getNode())
2517 Leaves.push(L: Mul2);
2518 CanFactorize = false;
2519 }
2520
2521 // Combine GA + Constant -> GA+Offset, but only if GA is not used elsewhere
2522 // and the root node itself is not used more than twice. This reduces the
2523 // amount of additional constant extenders introduced by this optimization.
2524 bool CombinedGA = false;
2525 if (NOpcode == ISD::ADD && GA.Value.getNode() && Leaves.hasConst() &&
2526 GA.Value.hasOneUse() && N->use_size() < 3 &&
2527 GA.Value.getNumOperands() >= 1) {
2528 GlobalAddressSDNode *GANode =
2529 cast<GlobalAddressSDNode>(Val: GA.Value.getOperand(i: 0));
2530 ConstantSDNode *Offset = cast<ConstantSDNode>(Val: Leaves.top().Value);
2531
2532 if (getUsesInFunction(V: GANode->getGlobal()) == 1 && Offset->hasOneUse() &&
2533 getTargetLowering()->isOffsetFoldingLegal(GA: GANode)) {
2534 LLVM_DEBUG(dbgs() << "--> Combining GA and offset ("
2535 << Offset->getSExtValue() << "): ");
2536 LLVM_DEBUG(GANode->dump(CurDAG));
2537
2538 SDValue NewTGA =
2539 CurDAG->getTargetGlobalAddress(GV: GANode->getGlobal(), DL: SDLoc(GA.Value),
2540 VT: GANode->getValueType(ResNo: 0),
2541 offset: GANode->getOffset() + (uint64_t)Offset->getSExtValue());
2542 GA.Value = CurDAG->getNode(Opcode: GA.Value.getOpcode(), DL: SDLoc(GA.Value),
2543 VT: GA.Value.getValueType(), Operand: NewTGA);
2544 GA.Weight += Leaves.top().Weight;
2545
2546 NodeHeights[GA.Value] = getHeight(N: GA.Value.getNode());
2547 CombinedGA = true;
2548
2549 Leaves.pop(); // Remove the offset constant from the queue
2550 }
2551 }
2552
2553 if ((RebalanceOnlyForOptimizations && !CanFactorize && !CombinedGA) ||
2554 (RebalanceOnlyImbalancedTrees && !Imbalanced)) {
2555 RootWeights[N] = CurrentWeight;
2556 RootHeights[N] = NodeHeights[SDValue(N, 0)];
2557
2558 return SDValue(N, 0);
2559 }
2560
2561 // Combine GA + SHL(x, C<=31) so we will match Rx=add(#u8,asl(Rx,#U5))
2562 if (NOpcode == ISD::ADD && GA.Value.getNode()) {
2563 WeightedLeaf SHL = Leaves.findSHL(MaxAmount: 31);
2564 if (SHL.Value.getNode()) {
2565 int Height = std::max(a: NodeHeights[GA.Value], b: NodeHeights[SHL.Value]) + 1;
2566 GA.Value = CurDAG->getNode(Opcode: ISD::ADD, DL: SDLoc(GA.Value),
2567 VT: GA.Value.getValueType(),
2568 N1: GA.Value, N2: SHL.Value);
2569 GA.Weight = SHL.Weight; // Specifically ignore the GA weight here
2570 NodeHeights[GA.Value] = Height;
2571 }
2572 }
2573
2574 if (GA.Value.getNode())
2575 Leaves.push(L: GA);
2576
2577 // If this is the top level and we haven't factored out a shift, we should try
2578 // to move a constant to the bottom to match addressing modes like memw(rX+C)
2579 if (TopLevel && !CanFactorize && Leaves.hasConst()) {
2580 LLVM_DEBUG(dbgs() << "--> Pushing constant to tip of tree.");
2581 Leaves.pushToBottom(L: Leaves.pop());
2582 }
2583
2584 const DataLayout &DL = CurDAG->getDataLayout();
2585 const TargetLowering &TLI = *getTargetLowering();
2586
2587 // Rebuild the tree using Huffman's algorithm
2588 while (Leaves.size() > 1) {
2589 WeightedLeaf L0 = Leaves.pop();
2590
2591 // See whether we can grab a MUL to form an add(Rx,mpyi(Ry,#u6)),
2592 // otherwise just get the next leaf
2593 WeightedLeaf L1 = Leaves.findMULbyConst();
2594 if (!L1.Value.getNode())
2595 L1 = Leaves.pop();
2596
2597 assert(L0.Weight <= L1.Weight && "Priority queue is broken!");
2598
2599 SDValue V0 = L0.Value;
2600 int V0Weight = L0.Weight;
2601 SDValue V1 = L1.Value;
2602 int V1Weight = L1.Weight;
2603
2604 // Make sure that none of these nodes have been RAUW'd
2605 if ((RootWeights.count(Val: V0.getNode()) && RootWeights[V0.getNode()] == -2) ||
2606 (RootWeights.count(Val: V1.getNode()) && RootWeights[V1.getNode()] == -2)) {
2607 LLVM_DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");
2608 return balanceSubTree(N, TopLevel);
2609 }
2610
2611 ConstantSDNode *V0C = dyn_cast<ConstantSDNode>(Val&: V0);
2612 ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(Val&: V1);
2613 EVT VT = N->getValueType(ResNo: 0);
2614 SDValue NewNode;
2615
2616 if (V0C && !V1C) {
2617 std::swap(a&: V0, b&: V1);
2618 std::swap(a&: V0C, b&: V1C);
2619 }
2620
2621 // Calculate height of this node
2622 assert(NodeHeights.count(V0) && NodeHeights.count(V1) &&
2623 "Children must have been visited before re-combining them!");
2624 int Height = std::max(a: NodeHeights[V0], b: NodeHeights[V1]) + 1;
2625
2626 // Rebuild this node (and restore SHL from MUL if needed)
2627 if (V1C && NOpcode == ISD::MUL && V1C->getAPIntValue().isPowerOf2())
2628 NewNode = CurDAG->getNode(
2629 Opcode: ISD::SHL, DL: SDLoc(V0), VT, N1: V0,
2630 N2: CurDAG->getConstant(
2631 Val: V1C->getAPIntValue().logBase2(), DL: SDLoc(N),
2632 VT: TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
2633 else
2634 NewNode = CurDAG->getNode(Opcode: NOpcode, DL: SDLoc(N), VT, N1: V0, N2: V1);
2635
2636 NodeHeights[NewNode] = Height;
2637
2638 int Weight = V0Weight + V1Weight;
2639 Leaves.push(L: WeightedLeaf(NewNode, Weight, L0.InsertionOrder));
2640
2641 LLVM_DEBUG(dbgs() << "--> Built new node (Weight=" << Weight
2642 << ",Height=" << Height << "):\n");
2643 LLVM_DEBUG(NewNode.dump());
2644 }
2645
2646 assert(Leaves.size() == 1);
2647 SDValue NewRoot = Leaves.top().Value;
2648
2649 assert(NodeHeights.count(NewRoot));
2650 int Height = NodeHeights[NewRoot];
2651
2652 // Restore SHL if we earlier converted it to a MUL
2653 if (NewRoot.getOpcode() == ISD::MUL && NewRoot->getNumOperands() >= 2) {
2654 ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(Val: NewRoot.getOperand(i: 1));
2655 if (V1C && V1C->getAPIntValue().isPowerOf2()) {
2656 EVT VT = NewRoot.getValueType();
2657 SDValue V0 = NewRoot.getOperand(i: 0);
2658 NewRoot = CurDAG->getNode(
2659 Opcode: ISD::SHL, DL: SDLoc(NewRoot), VT, N1: V0,
2660 N2: CurDAG->getConstant(
2661 Val: V1C->getAPIntValue().logBase2(), DL: SDLoc(NewRoot),
2662 VT: TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
2663 }
2664 }
2665
2666 if (N != NewRoot.getNode()) {
2667 LLVM_DEBUG(dbgs() << "--> Root is now: ");
2668 LLVM_DEBUG(NewRoot.dump());
2669
2670 // Replace all uses of old root by new root
2671 CurDAG->ReplaceAllUsesWith(From: N, To: NewRoot.getNode());
2672 // Mark that we have RAUW'd N
2673 RootWeights[N] = -2;
2674 } else {
2675 LLVM_DEBUG(dbgs() << "--> Root unchanged.\n");
2676 }
2677
2678 RootWeights[NewRoot.getNode()] = Leaves.top().Weight;
2679 RootHeights[NewRoot.getNode()] = Height;
2680
2681 return NewRoot;
2682}
2683
2684void HexagonDAGToDAGISel::rebalanceAddressTrees() {
2685 for (SDNode &Node : llvm::make_early_inc_range(Range: CurDAG->allnodes())) {
2686 SDNode *N = &Node;
2687 if (N->getOpcode() != ISD::LOAD && N->getOpcode() != ISD::STORE)
2688 continue;
2689
2690 SDValue BasePtr = cast<MemSDNode>(Val: N)->getBasePtr();
2691 if (BasePtr.getOpcode() != ISD::ADD)
2692 continue;
2693
2694 // We've already processed this node
2695 if (RootWeights.count(Val: BasePtr.getNode()))
2696 continue;
2697
2698 LLVM_DEBUG(dbgs() << "** Rebalancing address calculation in node: ");
2699 LLVM_DEBUG(N->dump(CurDAG));
2700
2701 // FindRoots
2702 SmallVector<SDNode *, 4> Worklist;
2703
2704 if (BasePtr->getNumOperands() < 2)
2705 continue;
2706
2707 Worklist.push_back(Elt: BasePtr.getOperand(i: 0).getNode());
2708 Worklist.push_back(Elt: BasePtr.getOperand(i: 1).getNode());
2709
2710 while (!Worklist.empty()) {
2711 SDNode *N = Worklist.pop_back_val();
2712 unsigned Opcode = N->getOpcode();
2713
2714 if (!isOpcodeHandled(N))
2715 continue;
2716
2717 if (N->getNumOperands() < 2)
2718 continue;
2719
2720 Worklist.push_back(Elt: N->getOperand(Num: 0).getNode());
2721 Worklist.push_back(Elt: N->getOperand(Num: 1).getNode());
2722
2723 // Not a root if it has only one use and same opcode as its parent
2724 if (N->hasOneUse() && Opcode == N->user_begin()->getOpcode())
2725 continue;
2726
2727 // This root node has already been processed
2728 RootWeights.try_emplace(Key: N, Args: -1);
2729 }
2730
2731 // Balance node itself
2732 RootWeights[BasePtr.getNode()] = -1;
2733 SDValue NewBasePtr = balanceSubTree(N: BasePtr.getNode(), /*TopLevel=*/ true);
2734
2735 if (N->getOpcode() == ISD::LOAD) {
2736 if (N->getNumOperands() >= 3)
2737 N = CurDAG->UpdateNodeOperands(N, Op1: N->getOperand(Num: 0), Op2: NewBasePtr,
2738 Op3: N->getOperand(Num: 2));
2739 } else {
2740 if (N->getNumOperands() >= 4)
2741 N = CurDAG->UpdateNodeOperands(N, Op1: N->getOperand(Num: 0), Op2: N->getOperand(Num: 1),
2742 Op3: NewBasePtr, Op4: N->getOperand(Num: 3));
2743 }
2744
2745 LLVM_DEBUG(dbgs() << "--> Final node: ");
2746 LLVM_DEBUG(N->dump(CurDAG));
2747 }
2748
2749 CurDAG->RemoveDeadNodes();
2750 GAUsesInFunction.clear();
2751 RootHeights.clear();
2752 RootWeights.clear();
2753}
2754