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