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