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