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