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