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