/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===// |
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 implements the SelectionDAG::LegalizeTypes method. It transforms |
10 | | // an arbitrary well-formed SelectionDAG to only consist of legal types. This |
11 | | // is common code shared among the LegalizeTypes*.cpp files. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #include "LegalizeTypes.h" |
16 | | #include "SDNodeDbgValue.h" |
17 | | #include "llvm/ADT/SetVector.h" |
18 | | #include "llvm/CodeGen/MachineFunction.h" |
19 | | #include "llvm/IR/CallingConv.h" |
20 | | #include "llvm/IR/DataLayout.h" |
21 | | #include "llvm/Support/CommandLine.h" |
22 | | #include "llvm/Support/ErrorHandling.h" |
23 | | #include "llvm/Support/raw_ostream.h" |
24 | | using namespace llvm; |
25 | | |
26 | | #define DEBUG_TYPE "legalize-types" |
27 | | |
28 | | static cl::opt<bool> |
29 | | EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden); |
30 | | |
31 | | /// Do extensive, expensive, sanity checking. |
32 | 4.98k | void DAGTypeLegalizer::PerformExpensiveChecks() { |
33 | 4.98k | // If a node is not processed, then none of its values should be mapped by any |
34 | 4.98k | // of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. |
35 | 4.98k | |
36 | 4.98k | // If a node is processed, then each value with an illegal type must be mapped |
37 | 4.98k | // by exactly one of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. |
38 | 4.98k | // Values with a legal type may be mapped by ReplacedValues, but not by any of |
39 | 4.98k | // the other maps. |
40 | 4.98k | |
41 | 4.98k | // Note that these invariants may not hold momentarily when processing a node: |
42 | 4.98k | // the node being processed may be put in a map before being marked Processed. |
43 | 4.98k | |
44 | 4.98k | // Note that it is possible to have nodes marked NewNode in the DAG. This can |
45 | 4.98k | // occur in two ways. Firstly, a node may be created during legalization but |
46 | 4.98k | // never passed to the legalization core. This is usually due to the implicit |
47 | 4.98k | // folding that occurs when using the DAG.getNode operators. Secondly, a new |
48 | 4.98k | // node may be passed to the legalization core, but when analyzed may morph |
49 | 4.98k | // into a different node, leaving the original node as a NewNode in the DAG. |
50 | 4.98k | // A node may morph if one of its operands changes during analysis. Whether |
51 | 4.98k | // it actually morphs or not depends on whether, after updating its operands, |
52 | 4.98k | // it is equivalent to an existing node: if so, it morphs into that existing |
53 | 4.98k | // node (CSE). An operand can change during analysis if the operand is a new |
54 | 4.98k | // node that morphs, or it is a processed value that was mapped to some other |
55 | 4.98k | // value (as recorded in ReplacedValues) in which case the operand is turned |
56 | 4.98k | // into that other value. If a node morphs then the node it morphed into will |
57 | 4.98k | // be used instead of it for legalization, however the original node continues |
58 | 4.98k | // to live on in the DAG. |
59 | 4.98k | // The conclusion is that though there may be nodes marked NewNode in the DAG, |
60 | 4.98k | // all uses of such nodes are also marked NewNode: the result is a fungus of |
61 | 4.98k | // NewNodes growing on top of the useful nodes, and perhaps using them, but |
62 | 4.98k | // not used by them. |
63 | 4.98k | |
64 | 4.98k | // If a value is mapped by ReplacedValues, then it must have no uses, except |
65 | 4.98k | // by nodes marked NewNode (see above). |
66 | 4.98k | |
67 | 4.98k | // The final node obtained by mapping by ReplacedValues is not marked NewNode. |
68 | 4.98k | // Note that ReplacedValues should be applied iteratively. |
69 | 4.98k | |
70 | 4.98k | // Note that the ReplacedValues map may also map deleted nodes (by iterating |
71 | 4.98k | // over the DAG we never dereference deleted nodes). This means that it may |
72 | 4.98k | // also map nodes marked NewNode if the deallocated memory was reallocated as |
73 | 4.98k | // another node, and that new node was not seen by the LegalizeTypes machinery |
74 | 4.98k | // (for example because it was created but not used). In general, we cannot |
75 | 4.98k | // distinguish between new nodes and deleted nodes. |
76 | 4.98k | SmallVector<SDNode*, 16> NewNodes; |
77 | 124k | for (SDNode &Node : DAG.allnodes()) { |
78 | 124k | // Remember nodes marked NewNode - they are subject to extra checking below. |
79 | 124k | if (Node.getNodeId() == NewNode) |
80 | 1.81k | NewNodes.push_back(&Node); |
81 | 124k | |
82 | 277k | for (unsigned i = 0, e = Node.getNumValues(); i != e; ++i153k ) { |
83 | 153k | SDValue Res(&Node, i); |
84 | 153k | EVT VT = Res.getValueType(); |
85 | 153k | bool Failed = false; |
86 | 153k | // Don't create a value in map. |
87 | 153k | auto ResId = (ValueToIdMap.count(Res)) ? ValueToIdMap[Res]50.2k : 0103k ; |
88 | 153k | |
89 | 153k | unsigned Mapped = 0; |
90 | 153k | if (ResId && (ReplacedValues.find(ResId) != ReplacedValues.end())50.2k ) { |
91 | 4.71k | Mapped |= 1; |
92 | 4.71k | // Check that remapped values are only used by nodes marked NewNode. |
93 | 4.71k | for (SDNode::use_iterator UI = Node.use_begin(), UE = Node.use_end(); |
94 | 6.16k | UI != UE; ++UI1.44k ) |
95 | 1.44k | if (UI.getUse().getResNo() == i) |
96 | 1.44k | assert(UI->getNodeId() == NewNode && |
97 | 4.71k | "Remapped value has non-trivial use!"); |
98 | 4.71k | |
99 | 4.71k | // Check that the final result of applying ReplacedValues is not |
100 | 4.71k | // marked NewNode. |
101 | 4.71k | auto NewValId = ReplacedValues[ResId]; |
102 | 4.71k | auto I = ReplacedValues.find(NewValId); |
103 | 4.80k | while (I != ReplacedValues.end()) { |
104 | 86 | NewValId = I->second; |
105 | 86 | I = ReplacedValues.find(NewValId); |
106 | 86 | } |
107 | 4.71k | SDValue NewVal = getSDValue(NewValId); |
108 | 4.71k | (void)NewVal; |
109 | 4.71k | assert(NewVal.getNode()->getNodeId() != NewNode && |
110 | 4.71k | "ReplacedValues maps to a new node!"); |
111 | 4.71k | } |
112 | 153k | if (ResId && PromotedIntegers.find(ResId) != PromotedIntegers.end()50.2k ) |
113 | 1.12k | Mapped |= 2; |
114 | 153k | if (ResId && SoftenedFloats.find(ResId) != SoftenedFloats.end()50.2k ) |
115 | 1.93k | Mapped |= 4; |
116 | 153k | if (ResId && ScalarizedVectors.find(ResId) != ScalarizedVectors.end()50.2k ) |
117 | 265 | Mapped |= 8; |
118 | 153k | if (ResId && ExpandedIntegers.find(ResId) != ExpandedIntegers.end()50.2k ) |
119 | 6.52k | Mapped |= 16; |
120 | 153k | if (ResId && ExpandedFloats.find(ResId) != ExpandedFloats.end()50.2k ) |
121 | 0 | Mapped |= 32; |
122 | 153k | if (ResId && SplitVectors.find(ResId) != SplitVectors.end()50.2k ) |
123 | 716 | Mapped |= 64; |
124 | 153k | if (ResId && WidenedVectors.find(ResId) != WidenedVectors.end()50.2k ) |
125 | 0 | Mapped |= 128; |
126 | 153k | if (ResId && PromotedFloats.find(ResId) != PromotedFloats.end()50.2k ) |
127 | 0 | Mapped |= 256; |
128 | 153k | |
129 | 153k | if (Node.getNodeId() != Processed) { |
130 | 58.3k | // Since we allow ReplacedValues to map deleted nodes, it may map nodes |
131 | 58.3k | // marked NewNode too, since a deleted node may have been reallocated as |
132 | 58.3k | // another node that has not been seen by the LegalizeTypes machinery. |
133 | 58.3k | if ((Node.getNodeId() == NewNode && Mapped > 11.81k ) || |
134 | 58.3k | (Node.getNodeId() != NewNode && Mapped != 056.5k )) { |
135 | 0 | dbgs() << "Unprocessed value in a map!"; |
136 | 0 | Failed = true; |
137 | 0 | } |
138 | 95.0k | } else if (isTypeLegal(VT) || IgnoreNodeResults(&Node)25.8k ) { |
139 | 77.8k | if (Mapped > 1) { |
140 | 0 | dbgs() << "Value with legal type was transformed!"; |
141 | 0 | Failed = true; |
142 | 0 | } |
143 | 77.8k | } else { |
144 | 17.2k | // If the value can be kept in HW registers, softening machinery can |
145 | 17.2k | // leave it unchanged and don't put it to any map. |
146 | 17.2k | if (Mapped == 0 && |
147 | 17.2k | !(5.68k getTypeAction(VT) == TargetLowering::TypeSoftenFloat5.68k && |
148 | 5.68k | isLegalInHWReg(VT))) { |
149 | 0 | dbgs() << "Processed value not in any map!"; |
150 | 0 | Failed = true; |
151 | 17.2k | } else if (Mapped & (Mapped - 1)) { |
152 | 0 | dbgs() << "Value in multiple maps!"; |
153 | 0 | Failed = true; |
154 | 0 | } |
155 | 17.2k | } |
156 | 153k | |
157 | 153k | if (Failed) { |
158 | 0 | if (Mapped & 1) |
159 | 0 | dbgs() << " ReplacedValues"; |
160 | 0 | if (Mapped & 2) |
161 | 0 | dbgs() << " PromotedIntegers"; |
162 | 0 | if (Mapped & 4) |
163 | 0 | dbgs() << " SoftenedFloats"; |
164 | 0 | if (Mapped & 8) |
165 | 0 | dbgs() << " ScalarizedVectors"; |
166 | 0 | if (Mapped & 16) |
167 | 0 | dbgs() << " ExpandedIntegers"; |
168 | 0 | if (Mapped & 32) |
169 | 0 | dbgs() << " ExpandedFloats"; |
170 | 0 | if (Mapped & 64) |
171 | 0 | dbgs() << " SplitVectors"; |
172 | 0 | if (Mapped & 128) |
173 | 0 | dbgs() << " WidenedVectors"; |
174 | 0 | if (Mapped & 256) |
175 | 0 | dbgs() << " PromotedFloats"; |
176 | 0 | dbgs() << "\n"; |
177 | 0 | llvm_unreachable(nullptr); |
178 | 0 | } |
179 | 153k | } |
180 | 124k | } |
181 | 4.98k | |
182 | 4.98k | // Checked that NewNodes are only used by other NewNodes. |
183 | 6.79k | for (unsigned i = 0, e = NewNodes.size(); 4.98k i != e; ++i1.81k ) { |
184 | 1.81k | SDNode *N = NewNodes[i]; |
185 | 1.81k | for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); |
186 | 1.81k | UI != UE; ++UI0 ) |
187 | 1.81k | assert(UI->getNodeId() == NewNode && "NewNode used by non-NewNode!"); |
188 | 1.81k | } |
189 | 4.98k | } |
190 | | |
191 | | /// This is the main entry point for the type legalizer. This does a top-down |
192 | | /// traversal of the dag, legalizing types as it goes. Returns "true" if it made |
193 | | /// any changes. |
194 | 1.28M | bool DAGTypeLegalizer::run() { |
195 | 1.28M | bool Changed = false; |
196 | 1.28M | |
197 | 1.28M | // Create a dummy node (which is not added to allnodes), that adds a reference |
198 | 1.28M | // to the root node, preventing it from being deleted, and tracking any |
199 | 1.28M | // changes of the root. |
200 | 1.28M | HandleSDNode Dummy(DAG.getRoot()); |
201 | 1.28M | Dummy.setNodeId(Unanalyzed); |
202 | 1.28M | |
203 | 1.28M | // The root of the dag may dangle to deleted nodes until the type legalizer is |
204 | 1.28M | // done. Set it to null to avoid confusion. |
205 | 1.28M | DAG.setRoot(SDValue()); |
206 | 1.28M | |
207 | 1.28M | // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess' |
208 | 1.28M | // (and remembering them) if they are leaves and assigning 'Unanalyzed' if |
209 | 1.28M | // non-leaves. |
210 | 25.6M | for (SDNode &Node : DAG.allnodes()) { |
211 | 25.6M | if (Node.getNumOperands() == 0) { |
212 | 12.6M | AddToWorklist(&Node); |
213 | 13.0M | } else { |
214 | 13.0M | Node.setNodeId(Unanalyzed); |
215 | 13.0M | } |
216 | 25.6M | } |
217 | 1.28M | |
218 | 1.28M | // Now that we have a set of nodes to process, handle them all. |
219 | 32.1M | while (!Worklist.empty()) { |
220 | 30.8M | #ifndef EXPENSIVE_CHECKS |
221 | 30.8M | if (EnableExpensiveChecks) |
222 | 4.79k | #endif |
223 | 4.79k | PerformExpensiveChecks(); |
224 | 30.8M | |
225 | 30.8M | SDNode *N = Worklist.back(); |
226 | 30.8M | Worklist.pop_back(); |
227 | 30.8M | assert(N->getNodeId() == ReadyToProcess && |
228 | 30.8M | "Node should be ready if on worklist!"); |
229 | 30.8M | |
230 | 30.8M | LLVM_DEBUG(dbgs() << "Legalizing node: "; N->dump(&DAG)); |
231 | 30.8M | if (IgnoreNodeResults(N)) { |
232 | 4.63M | LLVM_DEBUG(dbgs() << "Ignoring node results\n"); |
233 | 4.63M | goto ScanOperands; |
234 | 4.63M | } |
235 | 26.1M | |
236 | 26.1M | // Scan the values produced by the node, checking to see if any result |
237 | 26.1M | // types are illegal. |
238 | 56.7M | for (unsigned i = 0, NumResults = N->getNumValues(); 26.1M i < NumResults; ++i30.5M ) { |
239 | 31.8M | EVT ResultVT = N->getValueType(i); |
240 | 31.8M | LLVM_DEBUG(dbgs() << "Analyzing result type: " << ResultVT.getEVTString() |
241 | 31.8M | << "\n"); |
242 | 31.8M | switch (getTypeAction(ResultVT)) { |
243 | 31.8M | case TargetLowering::TypeLegal: |
244 | 30.5M | LLVM_DEBUG(dbgs() << "Legal result type\n"); |
245 | 30.5M | break; |
246 | 31.8M | // The following calls must take care of *all* of the node's results, |
247 | 31.8M | // not just the illegal result they were passed (this includes results |
248 | 31.8M | // with a legal type). Results can be remapped using ReplaceValueWith, |
249 | 31.8M | // or their promoted/expanded/etc values registered in PromotedIntegers, |
250 | 31.8M | // ExpandedIntegers etc. |
251 | 31.8M | case TargetLowering::TypePromoteInteger: |
252 | 736k | PromoteIntegerResult(N, i); |
253 | 736k | Changed = true; |
254 | 736k | goto NodeDone; |
255 | 31.8M | case TargetLowering::TypeExpandInteger: |
256 | 262k | ExpandIntegerResult(N, i); |
257 | 262k | Changed = true; |
258 | 262k | goto NodeDone; |
259 | 31.8M | case TargetLowering::TypeSoftenFloat: |
260 | 7.54k | Changed = SoftenFloatResult(N, i); |
261 | 7.54k | if (Changed) |
262 | 7.06k | goto NodeDone; |
263 | 478 | // If not changed, the result type should be legally in register. |
264 | 478 | assert(isLegalInHWReg(ResultVT) && |
265 | 478 | "Unchanged SoftenFloatResult should be legal in register!"); |
266 | 478 | goto ScanOperands; |
267 | 478 | case TargetLowering::TypeExpandFloat: |
268 | 250 | ExpandFloatResult(N, i); |
269 | 250 | Changed = true; |
270 | 250 | goto NodeDone; |
271 | 76.3k | case TargetLowering::TypeScalarizeVector: |
272 | 76.3k | ScalarizeVectorResult(N, i); |
273 | 76.3k | Changed = true; |
274 | 76.3k | goto NodeDone; |
275 | 173k | case TargetLowering::TypeSplitVector: |
276 | 173k | SplitVectorResult(N, i); |
277 | 173k | Changed = true; |
278 | 173k | goto NodeDone; |
279 | 24.4k | case TargetLowering::TypeWidenVector: |
280 | 24.4k | WidenVectorResult(N, i); |
281 | 24.4k | Changed = true; |
282 | 24.4k | goto NodeDone; |
283 | 8.20k | case TargetLowering::TypePromoteFloat: |
284 | 8.20k | PromoteFloatResult(N, i); |
285 | 8.20k | Changed = true; |
286 | 8.20k | goto NodeDone; |
287 | 31.8M | } |
288 | 31.8M | } |
289 | 26.1M | |
290 | 29.5M | ScanOperands: |
291 | 29.5M | // Scan the operand list for the node, handling any nodes with operands that |
292 | 29.5M | // are illegal. |
293 | 29.5M | { |
294 | 29.5M | unsigned NumOperands = N->getNumOperands(); |
295 | 29.5M | bool NeedsReanalyzing = false; |
296 | 29.5M | unsigned i; |
297 | 70.5M | for (i = 0; i != NumOperands; ++i40.9M ) { |
298 | 42.2M | if (IgnoreNodeResults(N->getOperand(i).getNode())) |
299 | 7.48M | continue; |
300 | 34.7M | |
301 | 34.7M | const auto Op = N->getOperand(i); |
302 | 34.7M | LLVM_DEBUG(dbgs() << "Analyzing operand: "; Op.dump(&DAG)); |
303 | 34.7M | EVT OpVT = Op.getValueType(); |
304 | 34.7M | switch (getTypeAction(OpVT)) { |
305 | 34.7M | case TargetLowering::TypeLegal: |
306 | 33.4M | LLVM_DEBUG(dbgs() << "Legal operand\n"); |
307 | 33.4M | continue; |
308 | 34.7M | // The following calls must either replace all of the node's results |
309 | 34.7M | // using ReplaceValueWith, and return "false"; or update the node's |
310 | 34.7M | // operands in place, and return "true". |
311 | 34.7M | case TargetLowering::TypePromoteInteger: |
312 | 851k | NeedsReanalyzing = PromoteIntegerOperand(N, i); |
313 | 851k | Changed = true; |
314 | 851k | break; |
315 | 34.7M | case TargetLowering::TypeExpandInteger: |
316 | 209k | NeedsReanalyzing = ExpandIntegerOperand(N, i); |
317 | 209k | Changed = true; |
318 | 209k | break; |
319 | 34.7M | case TargetLowering::TypeSoftenFloat: |
320 | 3.17k | NeedsReanalyzing = SoftenFloatOperand(N, i); |
321 | 3.17k | Changed = true; |
322 | 3.17k | break; |
323 | 34.7M | case TargetLowering::TypeExpandFloat: |
324 | 94 | NeedsReanalyzing = ExpandFloatOperand(N, i); |
325 | 94 | Changed = true; |
326 | 94 | break; |
327 | 34.7M | case TargetLowering::TypeScalarizeVector: |
328 | 23.1k | NeedsReanalyzing = ScalarizeVectorOperand(N, i); |
329 | 23.1k | Changed = true; |
330 | 23.1k | break; |
331 | 34.7M | case TargetLowering::TypeSplitVector: |
332 | 176k | NeedsReanalyzing = SplitVectorOperand(N, i); |
333 | 176k | Changed = true; |
334 | 176k | break; |
335 | 34.7M | case TargetLowering::TypeWidenVector: |
336 | 21.5k | NeedsReanalyzing = WidenVectorOperand(N, i); |
337 | 21.5k | Changed = true; |
338 | 21.5k | break; |
339 | 34.7M | case TargetLowering::TypePromoteFloat: |
340 | 3.07k | NeedsReanalyzing = PromoteFloatOperand(N, i); |
341 | 3.07k | Changed = true; |
342 | 3.07k | break; |
343 | 1.28M | } |
344 | 1.28M | break; |
345 | 1.28M | } |
346 | 29.5M | |
347 | 29.5M | // The sub-method updated N in place. Check to see if any operands are new, |
348 | 29.5M | // and if so, mark them. If the node needs revisiting, don't add all users |
349 | 29.5M | // to the worklist etc. |
350 | 29.5M | if (NeedsReanalyzing) { |
351 | 436k | assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); |
352 | 436k | |
353 | 436k | N->setNodeId(NewNode); |
354 | 436k | // Recompute the NodeId and correct processed operands, adding the node to |
355 | 436k | // the worklist if ready. |
356 | 436k | SDNode *M = AnalyzeNewNode(N); |
357 | 436k | if (M == N) |
358 | 436k | // The node didn't morph - nothing special to do, it will be revisited. |
359 | 436k | continue; |
360 | 0 | |
361 | 0 | // The node morphed - this is equivalent to legalizing by replacing every |
362 | 0 | // value of N with the corresponding value of M. So do that now. |
363 | 0 | assert(N->getNumValues() == M->getNumValues() && |
364 | 0 | "Node morphing changed the number of results!"); |
365 | 0 | for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) |
366 | 0 | // Replacing the value takes care of remapping the new value. |
367 | 0 | ReplaceValueWith(SDValue(N, i), SDValue(M, i)); |
368 | 0 | assert(N->getNodeId() == NewNode && "Unexpected node state!"); |
369 | 0 | // The node continues to live on as part of the NewNode fungus that |
370 | 0 | // grows on top of the useful nodes. Nothing more needs to be done |
371 | 0 | // with it - move on to the next node. |
372 | 0 | continue; |
373 | 0 | } |
374 | 29.0M | |
375 | 29.0M | if (i == NumOperands) { |
376 | 28.2M | LLVM_DEBUG(dbgs() << "Legally typed node: "; N->dump(&DAG); |
377 | 28.2M | dbgs() << "\n"); |
378 | 28.2M | } |
379 | 29.0M | } |
380 | 30.3M | NodeDone: |
381 | 30.3M | |
382 | 30.3M | // If we reach here, the node was processed, potentially creating new nodes. |
383 | 30.3M | // Mark it as processed and add its users to the worklist as appropriate. |
384 | 30.3M | assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); |
385 | 30.3M | N->setNodeId(Processed); |
386 | 30.3M | |
387 | 30.3M | for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); |
388 | 71.7M | UI != E; ++UI41.3M ) { |
389 | 41.3M | SDNode *User = *UI; |
390 | 41.3M | int NodeId = User->getNodeId(); |
391 | 41.3M | |
392 | 41.3M | // This node has two options: it can either be a new node or its Node ID |
393 | 41.3M | // may be a count of the number of operands it has that are not ready. |
394 | 41.3M | if (NodeId > 0) { |
395 | 27.0M | User->setNodeId(NodeId-1); |
396 | 27.0M | |
397 | 27.0M | // If this was the last use it was waiting on, add it to the ready list. |
398 | 27.0M | if (NodeId-1 == ReadyToProcess) |
399 | 14.3M | Worklist.push_back(User); |
400 | 27.0M | continue; |
401 | 27.0M | } |
402 | 14.2M | |
403 | 14.2M | // If this is an unreachable new node, then ignore it. If it ever becomes |
404 | 14.2M | // reachable by being used by a newly created node then it will be handled |
405 | 14.2M | // by AnalyzeNewNode. |
406 | 14.2M | if (NodeId == NewNode) |
407 | 7.53k | continue; |
408 | 14.2M | |
409 | 14.2M | // Otherwise, this node is new: this is the first operand of it that |
410 | 14.2M | // became ready. Its new NodeId is the number of operands it has minus 1 |
411 | 14.2M | // (as this node is now processed). |
412 | 14.2M | assert(NodeId == Unanalyzed && "Unknown node ID!"); |
413 | 14.2M | User->setNodeId(User->getNumOperands() - 1); |
414 | 14.2M | |
415 | 14.2M | // If the node only has a single operand, it is now ready. |
416 | 14.2M | if (User->getNumOperands() == 1) |
417 | 1.94M | Worklist.push_back(User); |
418 | 14.2M | } |
419 | 30.3M | } |
420 | 1.28M | |
421 | 1.28M | #ifndef EXPENSIVE_CHECKS |
422 | 1.28M | if (EnableExpensiveChecks) |
423 | 189 | #endif |
424 | 189 | PerformExpensiveChecks(); |
425 | 1.28M | |
426 | 1.28M | // If the root changed (e.g. it was a dead load) update the root. |
427 | 1.28M | DAG.setRoot(Dummy.getValue()); |
428 | 1.28M | |
429 | 1.28M | // Remove dead nodes. This is important to do for cleanliness but also before |
430 | 1.28M | // the checking loop below. Implicit folding by the DAG.getNode operators and |
431 | 1.28M | // node morphing can cause unreachable nodes to be around with their flags set |
432 | 1.28M | // to new. |
433 | 1.28M | DAG.RemoveDeadNodes(); |
434 | 1.28M | |
435 | 1.28M | // In a debug build, scan all the nodes to make sure we found them all. This |
436 | 1.28M | // ensures that there are no cycles and that everything got processed. |
437 | | #ifndef NDEBUG |
438 | | for (SDNode &Node : DAG.allnodes()) { |
439 | | bool Failed = false; |
440 | | |
441 | | // Check that all result types are legal. |
442 | | // A value type is illegal if its TypeAction is not TypeLegal, |
443 | | // and TLI.RegClassForVT does not have a register class for this type. |
444 | | // For example, the x86_64 target has f128 that is not TypeLegal, |
445 | | // to have softened operators, but it also has FR128 register class to |
446 | | // pass and return f128 values. Hence a legalized node can have f128 type. |
447 | | if (!IgnoreNodeResults(&Node)) |
448 | | for (unsigned i = 0, NumVals = Node.getNumValues(); i < NumVals; ++i) |
449 | | if (!isTypeLegal(Node.getValueType(i)) && |
450 | | !TLI.isTypeLegal(Node.getValueType(i))) { |
451 | | dbgs() << "Result type " << i << " illegal: "; |
452 | | Node.dump(&DAG); |
453 | | Failed = true; |
454 | | } |
455 | | |
456 | | // Check that all operand types are legal. |
457 | | for (unsigned i = 0, NumOps = Node.getNumOperands(); i < NumOps; ++i) |
458 | | if (!IgnoreNodeResults(Node.getOperand(i).getNode()) && |
459 | | !isTypeLegal(Node.getOperand(i).getValueType()) && |
460 | | !TLI.isTypeLegal(Node.getOperand(i).getValueType())) { |
461 | | dbgs() << "Operand type " << i << " illegal: "; |
462 | | Node.getOperand(i).dump(&DAG); |
463 | | Failed = true; |
464 | | } |
465 | | |
466 | | if (Node.getNodeId() != Processed) { |
467 | | if (Node.getNodeId() == NewNode) |
468 | | dbgs() << "New node not analyzed?\n"; |
469 | | else if (Node.getNodeId() == Unanalyzed) |
470 | | dbgs() << "Unanalyzed node not noticed?\n"; |
471 | | else if (Node.getNodeId() > 0) |
472 | | dbgs() << "Operand not processed?\n"; |
473 | | else if (Node.getNodeId() == ReadyToProcess) |
474 | | dbgs() << "Not added to worklist?\n"; |
475 | | Failed = true; |
476 | | } |
477 | | |
478 | | if (Failed) { |
479 | | Node.dump(&DAG); dbgs() << "\n"; |
480 | | llvm_unreachable(nullptr); |
481 | | } |
482 | | } |
483 | | #endif |
484 | | |
485 | 1.28M | return Changed; |
486 | 1.28M | } |
487 | | |
488 | | /// The specified node is the root of a subtree of potentially new nodes. |
489 | | /// Correct any processed operands (this may change the node) and calculate the |
490 | | /// NodeId. If the node itself changes to a processed node, it is not remapped - |
491 | | /// the caller needs to take care of this. Returns the potentially changed node. |
492 | 14.5M | SDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) { |
493 | 14.5M | // If this was an existing node that is already done, we're done. |
494 | 14.5M | if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed9.72M ) |
495 | 9.70M | return N; |
496 | 4.85M | |
497 | 4.85M | // Okay, we know that this node is new. Recursively walk all of its operands |
498 | 4.85M | // to see if they are new also. The depth of this walk is bounded by the size |
499 | 4.85M | // of the new tree that was constructed (usually 2-3 nodes), so we don't worry |
500 | 4.85M | // about revisiting of nodes. |
501 | 4.85M | // |
502 | 4.85M | // As we walk the operands, keep track of the number of nodes that are |
503 | 4.85M | // processed. If non-zero, this will become the new nodeid of this node. |
504 | 4.85M | // Operands may morph when they are analyzed. If so, the node will be |
505 | 4.85M | // updated after all operands have been analyzed. Since this is rare, |
506 | 4.85M | // the code tries to minimize overhead in the non-morphing case. |
507 | 4.85M | |
508 | 4.85M | std::vector<SDValue> NewOps; |
509 | 4.85M | unsigned NumProcessed = 0; |
510 | 15.2M | for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i10.4M ) { |
511 | 10.4M | SDValue OrigOp = N->getOperand(i); |
512 | 10.4M | SDValue Op = OrigOp; |
513 | 10.4M | |
514 | 10.4M | AnalyzeNewValue(Op); // Op may morph. |
515 | 10.4M | |
516 | 10.4M | if (Op.getNode()->getNodeId() == Processed) |
517 | 5.98M | ++NumProcessed; |
518 | 10.4M | |
519 | 10.4M | if (!NewOps.empty()) { |
520 | 4.39k | // Some previous operand changed. Add this one to the list. |
521 | 4.39k | NewOps.push_back(Op); |
522 | 10.4M | } else if (Op != OrigOp) { |
523 | 2.74k | // This is the first operand to change - add all operands so far. |
524 | 2.74k | NewOps.insert(NewOps.end(), N->op_begin(), N->op_begin() + i); |
525 | 2.74k | NewOps.push_back(Op); |
526 | 2.74k | } |
527 | 10.4M | } |
528 | 4.85M | |
529 | 4.85M | // Some operands changed - update the node. |
530 | 4.85M | if (!NewOps.empty()) { |
531 | 2.74k | SDNode *M = DAG.UpdateNodeOperands(N, NewOps); |
532 | 2.74k | if (M != N) { |
533 | 110 | // The node morphed into a different node. Normally for this to happen |
534 | 110 | // the original node would have to be marked NewNode. However this can |
535 | 110 | // in theory momentarily not be the case while ReplaceValueWith is doing |
536 | 110 | // its stuff. Mark the original node NewNode to help sanity checking. |
537 | 110 | N->setNodeId(NewNode); |
538 | 110 | if (M->getNodeId() != NewNode && M->getNodeId() != Unanalyzed) |
539 | 110 | // It morphed into a previously analyzed node - nothing more to do. |
540 | 110 | return M; |
541 | 0 | |
542 | 0 | // It morphed into a different new node. Do the equivalent of passing |
543 | 0 | // it to AnalyzeNewNode: expunge it and calculate the NodeId. No need |
544 | 0 | // to remap the operands, since they are the same as the operands we |
545 | 0 | // remapped above. |
546 | 0 | N = M; |
547 | 0 | } |
548 | 2.74k | } |
549 | 4.85M | |
550 | 4.85M | // Calculate the NodeId. |
551 | 4.85M | N->setNodeId(N->getNumOperands() - NumProcessed); |
552 | 4.85M | if (N->getNodeId() == ReadyToProcess) |
553 | 1.94M | Worklist.push_back(N); |
554 | 4.85M | |
555 | 4.85M | return N; |
556 | 4.85M | } |
557 | | |
558 | | /// Call AnalyzeNewNode, updating the node in Val if needed. |
559 | | /// If the node changes to a processed node, then remap it. |
560 | 13.1M | void DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) { |
561 | 13.1M | Val.setNode(AnalyzeNewNode(Val.getNode())); |
562 | 13.1M | if (Val.getNode()->getNodeId() == Processed) |
563 | 6.48M | // We were passed a processed node, or it morphed into one - remap it. |
564 | 6.48M | RemapValue(Val); |
565 | 13.1M | } |
566 | | |
567 | | /// If the specified value was already legalized to another value, |
568 | | /// replace it by that value. |
569 | 6.48M | void DAGTypeLegalizer::RemapValue(SDValue &V) { |
570 | 6.48M | auto Id = getTableId(V); |
571 | 6.48M | V = getSDValue(Id); |
572 | 6.48M | } |
573 | | |
574 | 16.5M | void DAGTypeLegalizer::RemapId(TableId &Id) { |
575 | 16.5M | auto I = ReplacedValues.find(Id); |
576 | 16.5M | if (I != ReplacedValues.end()) { |
577 | 25.7k | assert(Id != I->second && "Id is mapped to itself."); |
578 | 25.7k | // Use path compression to speed up future lookups if values get multiply |
579 | 25.7k | // replaced with other values. |
580 | 25.7k | RemapId(I->second); |
581 | 25.7k | Id = I->second; |
582 | 25.7k | |
583 | 25.7k | // Note that N = IdToValueMap[Id] it is possible to have |
584 | 25.7k | // N.getNode()->getNodeId() == NewNode at this point because it is possible |
585 | 25.7k | // for a node to be put in the map before being processed. |
586 | 25.7k | } |
587 | 16.5M | } |
588 | | |
589 | | namespace { |
590 | | /// This class is a DAGUpdateListener that listens for updates to nodes and |
591 | | /// recomputes their ready state. |
592 | | class NodeUpdateListener : public SelectionDAG::DAGUpdateListener { |
593 | | DAGTypeLegalizer &DTL; |
594 | | SmallSetVector<SDNode*, 16> &NodesToAnalyze; |
595 | | public: |
596 | | explicit NodeUpdateListener(DAGTypeLegalizer &dtl, |
597 | | SmallSetVector<SDNode*, 16> &nta) |
598 | | : SelectionDAG::DAGUpdateListener(dtl.getDAG()), |
599 | 989k | DTL(dtl), NodesToAnalyze(nta) {} |
600 | | |
601 | 573 | void NodeDeleted(SDNode *N, SDNode *E) override { |
602 | 573 | assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && |
603 | 573 | N->getNodeId() != DAGTypeLegalizer::Processed && |
604 | 573 | "Invalid node ID for RAUW deletion!"); |
605 | 573 | // It is possible, though rare, for the deleted node N to occur as a |
606 | 573 | // target in a map, so note the replacement N -> E in ReplacedValues. |
607 | 573 | assert(E && "Node not replaced?"); |
608 | 573 | DTL.NoteDeletion(N, E); |
609 | 573 | |
610 | 573 | // In theory the deleted node could also have been scheduled for analysis. |
611 | 573 | // So remove it from the set of nodes which will be analyzed. |
612 | 573 | NodesToAnalyze.remove(N); |
613 | 573 | |
614 | 573 | // In general nothing needs to be done for E, since it didn't change but |
615 | 573 | // only gained new uses. However N -> E was just added to ReplacedValues, |
616 | 573 | // and the result of a ReplacedValues mapping is not allowed to be marked |
617 | 573 | // NewNode. So if E is marked NewNode, then it needs to be analyzed. |
618 | 573 | if (E->getNodeId() == DAGTypeLegalizer::NewNode) |
619 | 0 | NodesToAnalyze.insert(E); |
620 | 573 | } |
621 | | |
622 | 991k | void NodeUpdated(SDNode *N) override { |
623 | 991k | // Node updates can mean pretty much anything. It is possible that an |
624 | 991k | // operand was set to something already processed (f.e.) in which case |
625 | 991k | // this node could become ready. Recompute its flags. |
626 | 991k | assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && |
627 | 991k | N->getNodeId() != DAGTypeLegalizer::Processed && |
628 | 991k | "Invalid node ID for RAUW deletion!"); |
629 | 991k | N->setNodeId(DAGTypeLegalizer::NewNode); |
630 | 991k | NodesToAnalyze.insert(N); |
631 | 991k | } |
632 | | }; |
633 | | } |
634 | | |
635 | | |
636 | | /// The specified value was legalized to the specified other value. |
637 | | /// Update the DAG and NodeIds replacing any uses of From to use To instead. |
638 | 989k | void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) { |
639 | 989k | assert(From.getNode() != To.getNode() && "Potential legalization loop!"); |
640 | 989k | |
641 | 989k | // If expansion produced new nodes, make sure they are properly marked. |
642 | 989k | AnalyzeNewValue(To); |
643 | 989k | |
644 | 989k | // Anything that used the old node should now use the new one. Note that this |
645 | 989k | // can potentially cause recursive merging. |
646 | 989k | SmallSetVector<SDNode*, 16> NodesToAnalyze; |
647 | 989k | NodeUpdateListener NUL(*this, NodesToAnalyze); |
648 | 989k | do { |
649 | 989k | |
650 | 989k | // The old node may be present in a map like ExpandedIntegers or |
651 | 989k | // PromotedIntegers. Inform maps about the replacement. |
652 | 989k | auto FromId = getTableId(From); |
653 | 989k | auto ToId = getTableId(To); |
654 | 989k | |
655 | 989k | if (FromId != ToId) |
656 | 989k | ReplacedValues[FromId] = ToId; |
657 | 989k | DAG.ReplaceAllUsesOfValueWith(From, To); |
658 | 989k | |
659 | 989k | // Process the list of nodes that need to be reanalyzed. |
660 | 1.98M | while (!NodesToAnalyze.empty()) { |
661 | 991k | SDNode *N = NodesToAnalyze.back(); |
662 | 991k | NodesToAnalyze.pop_back(); |
663 | 991k | if (N->getNodeId() != DAGTypeLegalizer::NewNode) |
664 | 600 | // The node was analyzed while reanalyzing an earlier node - it is safe |
665 | 600 | // to skip. Note that this is not a morphing node - otherwise it would |
666 | 600 | // still be marked NewNode. |
667 | 600 | continue; |
668 | 990k | |
669 | 990k | // Analyze the node's operands and recalculate the node ID. |
670 | 990k | SDNode *M = AnalyzeNewNode(N); |
671 | 990k | if (M != N) { |
672 | 0 | // The node morphed into a different node. Make everyone use the new |
673 | 0 | // node instead. |
674 | 0 | assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!"); |
675 | 0 | assert(N->getNumValues() == M->getNumValues() && |
676 | 0 | "Node morphing changed the number of results!"); |
677 | 0 | for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { |
678 | 0 | SDValue OldVal(N, i); |
679 | 0 | SDValue NewVal(M, i); |
680 | 0 | if (M->getNodeId() == Processed) |
681 | 0 | RemapValue(NewVal); |
682 | 0 | // OldVal may be a target of the ReplacedValues map which was marked |
683 | 0 | // NewNode to force reanalysis because it was updated. Ensure that |
684 | 0 | // anything that ReplacedValues mapped to OldVal will now be mapped |
685 | 0 | // all the way to NewVal. |
686 | 0 | auto OldValId = getTableId(OldVal); |
687 | 0 | auto NewValId = getTableId(NewVal); |
688 | 0 | DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal); |
689 | 0 | if (OldValId != NewValId) |
690 | 0 | ReplacedValues[OldValId] = NewValId; |
691 | 0 | } |
692 | 0 | // The original node continues to exist in the DAG, marked NewNode. |
693 | 0 | } |
694 | 990k | } |
695 | 989k | // When recursively update nodes with new nodes, it is possible to have |
696 | 989k | // new uses of From due to CSE. If this happens, replace the new uses of |
697 | 989k | // From with To. |
698 | 989k | } while (!From.use_empty()); |
699 | 989k | } |
700 | | |
701 | 735k | void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) { |
702 | 735k | assert(Result.getValueType() == |
703 | 735k | TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && |
704 | 735k | "Invalid type for promoted integer"); |
705 | 735k | AnalyzeNewValue(Result); |
706 | 735k | |
707 | 735k | auto &OpIdEntry = PromotedIntegers[getTableId(Op)]; |
708 | 735k | assert((OpIdEntry == 0) && "Node is already promoted!"); |
709 | 735k | OpIdEntry = getTableId(Result); |
710 | 735k | Result->setFlags(Op->getFlags()); |
711 | 735k | |
712 | 735k | DAG.transferDbgValues(Op, Result); |
713 | 735k | } |
714 | | |
715 | 7.06k | void DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) { |
716 | 7.06k | // f128 of x86_64 could be kept in SSE registers, |
717 | 7.06k | // but sometimes softened to i128. |
718 | 7.06k | assert((Result.getValueType() == |
719 | 7.06k | TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) || |
720 | 7.06k | Op.getValueType() == |
721 | 7.06k | TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType())) && |
722 | 7.06k | "Invalid type for softened float"); |
723 | 7.06k | AnalyzeNewValue(Result); |
724 | 7.06k | |
725 | 7.06k | auto &OpIdEntry = SoftenedFloats[getTableId(Op)]; |
726 | 7.06k | // Allow repeated calls to save f128 type nodes |
727 | 7.06k | // or any node with type that transforms to itself. |
728 | 7.06k | // Many operations on these types are not softened. |
729 | 7.06k | assert(((OpIdEntry == 0) || |
730 | 7.06k | Op.getValueType() == |
731 | 7.06k | TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType())) && |
732 | 7.06k | "Node is already converted to integer!"); |
733 | 7.06k | OpIdEntry = getTableId(Result); |
734 | 7.06k | } |
735 | | |
736 | 6.69k | void DAGTypeLegalizer::SetPromotedFloat(SDValue Op, SDValue Result) { |
737 | 6.69k | assert(Result.getValueType() == |
738 | 6.69k | TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && |
739 | 6.69k | "Invalid type for promoted float"); |
740 | 6.69k | AnalyzeNewValue(Result); |
741 | 6.69k | |
742 | 6.69k | auto &OpIdEntry = PromotedFloats[getTableId(Op)]; |
743 | 6.69k | assert((OpIdEntry == 0) && "Node is already promoted!"); |
744 | 6.69k | OpIdEntry = getTableId(Result); |
745 | 6.69k | } |
746 | | |
747 | 76.4k | void DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) { |
748 | 76.4k | // Note that in some cases vector operation operands may be greater than |
749 | 76.4k | // the vector element type. For example BUILD_VECTOR of type <1 x i1> with |
750 | 76.4k | // a constant i8 operand. |
751 | 76.4k | assert(Result.getValueSizeInBits() >= Op.getScalarValueSizeInBits() && |
752 | 76.4k | "Invalid type for scalarized vector"); |
753 | 76.4k | AnalyzeNewValue(Result); |
754 | 76.4k | |
755 | 76.4k | auto &OpIdEntry = ScalarizedVectors[getTableId(Op)]; |
756 | 76.4k | assert((OpIdEntry == 0) && "Node is already scalarized!"); |
757 | 76.4k | OpIdEntry = getTableId(Result); |
758 | 76.4k | } |
759 | | |
760 | | void DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo, |
761 | 398k | SDValue &Hi) { |
762 | 398k | std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)]; |
763 | 398k | assert((Entry.first != 0) && "Operand isn't expanded"); |
764 | 398k | Lo = getSDValue(Entry.first); |
765 | 398k | Hi = getSDValue(Entry.second); |
766 | 398k | } |
767 | | |
768 | | void DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo, |
769 | 261k | SDValue Hi) { |
770 | 261k | assert(Lo.getValueType() == |
771 | 261k | TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && |
772 | 261k | Hi.getValueType() == Lo.getValueType() && |
773 | 261k | "Invalid type for expanded integer"); |
774 | 261k | // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. |
775 | 261k | AnalyzeNewValue(Lo); |
776 | 261k | AnalyzeNewValue(Hi); |
777 | 261k | |
778 | 261k | // Transfer debug values. Don't invalidate the source debug value until it's |
779 | 261k | // been transferred to the high and low bits. |
780 | 261k | if (DAG.getDataLayout().isBigEndian()) { |
781 | 10.9k | DAG.transferDbgValues(Op, Hi, 0, Hi.getValueSizeInBits(), false); |
782 | 10.9k | DAG.transferDbgValues(Op, Lo, Hi.getValueSizeInBits(), |
783 | 10.9k | Lo.getValueSizeInBits()); |
784 | 250k | } else { |
785 | 250k | DAG.transferDbgValues(Op, Lo, 0, Lo.getValueSizeInBits(), false); |
786 | 250k | DAG.transferDbgValues(Op, Hi, Lo.getValueSizeInBits(), |
787 | 250k | Hi.getValueSizeInBits()); |
788 | 250k | } |
789 | 261k | |
790 | 261k | // Remember that this is the result of the node. |
791 | 261k | std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)]; |
792 | 261k | assert((Entry.first == 0) && "Node already expanded"); |
793 | 261k | Entry.first = getTableId(Lo); |
794 | 261k | Entry.second = getTableId(Hi); |
795 | 261k | } |
796 | | |
797 | | void DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo, |
798 | 280 | SDValue &Hi) { |
799 | 280 | std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)]; |
800 | 280 | assert((Entry.first != 0) && "Operand isn't expanded"); |
801 | 280 | Lo = getSDValue(Entry.first); |
802 | 280 | Hi = getSDValue(Entry.second); |
803 | 280 | } |
804 | | |
805 | | void DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo, |
806 | 250 | SDValue Hi) { |
807 | 250 | assert(Lo.getValueType() == |
808 | 250 | TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && |
809 | 250 | Hi.getValueType() == Lo.getValueType() && |
810 | 250 | "Invalid type for expanded float"); |
811 | 250 | // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. |
812 | 250 | AnalyzeNewValue(Lo); |
813 | 250 | AnalyzeNewValue(Hi); |
814 | 250 | |
815 | 250 | std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)]; |
816 | 250 | assert((Entry.first == 0) && "Node already expanded"); |
817 | 250 | Entry.first = getTableId(Lo); |
818 | 250 | Entry.second = getTableId(Hi); |
819 | 250 | } |
820 | | |
821 | | void DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo, |
822 | 289k | SDValue &Hi) { |
823 | 289k | std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)]; |
824 | 289k | Lo = getSDValue(Entry.first); |
825 | 289k | Hi = getSDValue(Entry.second); |
826 | 289k | assert(Lo.getNode() && "Operand isn't split"); |
827 | 289k | ; |
828 | 289k | } |
829 | | |
830 | | void DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo, |
831 | 173k | SDValue Hi) { |
832 | 173k | assert(Lo.getValueType().getVectorElementType() == |
833 | 173k | Op.getValueType().getVectorElementType() && |
834 | 173k | 2*Lo.getValueType().getVectorNumElements() == |
835 | 173k | Op.getValueType().getVectorNumElements() && |
836 | 173k | Hi.getValueType() == Lo.getValueType() && |
837 | 173k | "Invalid type for split vector"); |
838 | 173k | // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. |
839 | 173k | AnalyzeNewValue(Lo); |
840 | 173k | AnalyzeNewValue(Hi); |
841 | 173k | |
842 | 173k | // Remember that this is the result of the node. |
843 | 173k | std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)]; |
844 | 173k | assert((Entry.first == 0) && "Node already split"); |
845 | 173k | Entry.first = getTableId(Lo); |
846 | 173k | Entry.second = getTableId(Hi); |
847 | 173k | } |
848 | | |
849 | 24.4k | void DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) { |
850 | 24.4k | assert(Result.getValueType() == |
851 | 24.4k | TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && |
852 | 24.4k | "Invalid type for widened vector"); |
853 | 24.4k | AnalyzeNewValue(Result); |
854 | 24.4k | |
855 | 24.4k | auto &OpIdEntry = WidenedVectors[getTableId(Op)]; |
856 | 24.4k | assert((OpIdEntry == 0) && "Node already widened!"); |
857 | 24.4k | OpIdEntry = getTableId(Result); |
858 | 24.4k | } |
859 | | |
860 | | |
861 | | //===----------------------------------------------------------------------===// |
862 | | // Utilities. |
863 | | //===----------------------------------------------------------------------===// |
864 | | |
865 | | /// Convert to an integer of the same size. |
866 | 37.6k | SDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) { |
867 | 37.6k | unsigned BitWidth = Op.getValueSizeInBits(); |
868 | 37.6k | return DAG.getNode(ISD::BITCAST, SDLoc(Op), |
869 | 37.6k | EVT::getIntegerVT(*DAG.getContext(), BitWidth), Op); |
870 | 37.6k | } |
871 | | |
872 | | /// Convert to a vector of integers of the same size. |
873 | 76 | SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(SDValue Op) { |
874 | 76 | assert(Op.getValueType().isVector() && "Only applies to vectors!"); |
875 | 76 | unsigned EltWidth = Op.getScalarValueSizeInBits(); |
876 | 76 | EVT EltNVT = EVT::getIntegerVT(*DAG.getContext(), EltWidth); |
877 | 76 | auto EltCnt = Op.getValueType().getVectorElementCount(); |
878 | 76 | return DAG.getNode(ISD::BITCAST, SDLoc(Op), |
879 | 76 | EVT::getVectorVT(*DAG.getContext(), EltNVT, EltCnt), Op); |
880 | 76 | } |
881 | | |
882 | | SDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op, |
883 | 2.99k | EVT DestVT) { |
884 | 2.99k | SDLoc dl(Op); |
885 | 2.99k | // Create the stack frame object. Make sure it is aligned for both |
886 | 2.99k | // the source and destination types. |
887 | 2.99k | SDValue StackPtr = DAG.CreateStackTemporary(Op.getValueType(), DestVT); |
888 | 2.99k | // Emit a store to the stack slot. |
889 | 2.99k | SDValue Store = |
890 | 2.99k | DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, MachinePointerInfo()); |
891 | 2.99k | // Result is a load from the stack slot. |
892 | 2.99k | return DAG.getLoad(DestVT, dl, Store, StackPtr, MachinePointerInfo()); |
893 | 2.99k | } |
894 | | |
895 | | /// Replace the node's results with custom code provided by the target and |
896 | | /// return "true", or do nothing and return "false". |
897 | | /// The last parameter is FALSE if we are dealing with a node with legal |
898 | | /// result types and illegal operand. The second parameter denotes the type of |
899 | | /// illegal OperandNo in that case. |
900 | | /// The last parameter being TRUE means we are dealing with a |
901 | | /// node with illegal result types. The second parameter denotes the type of |
902 | | /// illegal ResNo in that case. |
903 | 2.43M | bool DAGTypeLegalizer::CustomLowerNode(SDNode *N, EVT VT, bool LegalizeResult) { |
904 | 2.43M | // See if the target wants to custom lower this node. |
905 | 2.43M | if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) |
906 | 2.41M | return false; |
907 | 18.1k | |
908 | 18.1k | SmallVector<SDValue, 8> Results; |
909 | 18.1k | if (LegalizeResult) |
910 | 9.39k | TLI.ReplaceNodeResults(N, Results, DAG); |
911 | 8.76k | else |
912 | 8.76k | TLI.LowerOperationWrapper(N, Results, DAG); |
913 | 18.1k | |
914 | 18.1k | if (Results.empty()) |
915 | 7.65k | // The target didn't want to custom lower it after all. |
916 | 7.65k | return false; |
917 | 10.5k | |
918 | 10.5k | // When called from DAGTypeLegalizer::ExpandIntegerResult, we might need to |
919 | 10.5k | // provide the same kind of custom splitting behavior. |
920 | 10.5k | if (Results.size() == N->getNumValues() + 1 && LegalizeResult65 ) { |
921 | 65 | // We've legalized a return type by splitting it. If there is a chain, |
922 | 65 | // replace that too. |
923 | 65 | SetExpandedInteger(SDValue(N, 0), Results[0], Results[1]); |
924 | 65 | if (N->getNumValues() > 1) |
925 | 29 | ReplaceValueWith(SDValue(N, 1), Results[2]); |
926 | 65 | return true; |
927 | 65 | } |
928 | 10.4k | |
929 | 10.4k | // Make everything that once used N's values now use those in Results instead. |
930 | 10.4k | assert(Results.size() == N->getNumValues() && |
931 | 10.4k | "Custom lowering returned the wrong number of results!"); |
932 | 21.9k | for (unsigned i = 0, e = Results.size(); i != e; ++i11.5k ) { |
933 | 11.5k | ReplaceValueWith(SDValue(N, i), Results[i]); |
934 | 11.5k | } |
935 | 10.4k | return true; |
936 | 10.4k | } |
937 | | |
938 | | |
939 | | /// Widen the node's results with custom code provided by the target and return |
940 | | /// "true", or do nothing and return "false". |
941 | 24.4k | bool DAGTypeLegalizer::CustomWidenLowerNode(SDNode *N, EVT VT) { |
942 | 24.4k | // See if the target wants to custom lower this node. |
943 | 24.4k | if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) |
944 | 22.2k | return false; |
945 | 2.20k | |
946 | 2.20k | SmallVector<SDValue, 8> Results; |
947 | 2.20k | TLI.ReplaceNodeResults(N, Results, DAG); |
948 | 2.20k | |
949 | 2.20k | if (Results.empty()) |
950 | 715 | // The target didn't want to custom widen lower its result after all. |
951 | 715 | return false; |
952 | 1.49k | |
953 | 1.49k | // Update the widening map. |
954 | 1.49k | assert(Results.size() == N->getNumValues() && |
955 | 1.49k | "Custom lowering returned the wrong number of results!"); |
956 | 3.35k | for (unsigned i = 0, e = Results.size(); i != e; ++i1.86k ) { |
957 | 1.86k | // If this is a chain output just replace it. |
958 | 1.86k | if (Results[i].getValueType() == MVT::Other) |
959 | 367 | ReplaceValueWith(SDValue(N, i), Results[i]); |
960 | 1.49k | else |
961 | 1.49k | SetWidenedVector(SDValue(N, i), Results[i]); |
962 | 1.86k | } |
963 | 1.49k | return true; |
964 | 1.49k | } |
965 | | |
966 | 82 | SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(SDNode *N, unsigned ResNo) { |
967 | 246 | for (unsigned i = 0, e = N->getNumValues(); i != e; ++i164 ) |
968 | 164 | if (i != ResNo) |
969 | 82 | ReplaceValueWith(SDValue(N, i), SDValue(N->getOperand(i))); |
970 | 82 | return SDValue(N->getOperand(ResNo)); |
971 | 82 | } |
972 | | |
973 | | /// Use ISD::EXTRACT_ELEMENT nodes to extract the low and high parts of the |
974 | | /// given value. |
975 | | void DAGTypeLegalizer::GetPairElements(SDValue Pair, |
976 | 2.90k | SDValue &Lo, SDValue &Hi) { |
977 | 2.90k | SDLoc dl(Pair); |
978 | 2.90k | EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.getValueType()); |
979 | 2.90k | Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair, |
980 | 2.90k | DAG.getIntPtrConstant(0, dl)); |
981 | 2.90k | Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair, |
982 | 2.90k | DAG.getIntPtrConstant(1, dl)); |
983 | 2.90k | } |
984 | | |
985 | | /// Build an integer with low bits Lo and high bits Hi. |
986 | 6.08k | SDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) { |
987 | 6.08k | // Arbitrarily use dlHi for result SDLoc |
988 | 6.08k | SDLoc dlHi(Hi); |
989 | 6.08k | SDLoc dlLo(Lo); |
990 | 6.08k | EVT LVT = Lo.getValueType(); |
991 | 6.08k | EVT HVT = Hi.getValueType(); |
992 | 6.08k | EVT NVT = EVT::getIntegerVT(*DAG.getContext(), |
993 | 6.08k | LVT.getSizeInBits() + HVT.getSizeInBits()); |
994 | 6.08k | |
995 | 6.08k | EVT ShiftAmtVT = TLI.getShiftAmountTy(NVT, DAG.getDataLayout(), false); |
996 | 6.08k | Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo); |
997 | 6.08k | Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi); |
998 | 6.08k | Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi, |
999 | 6.08k | DAG.getConstant(LVT.getSizeInBits(), dlHi, ShiftAmtVT)); |
1000 | 6.08k | return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi); |
1001 | 6.08k | } |
1002 | | |
1003 | | /// Convert the node into a libcall with the same prototype. |
1004 | | SDValue DAGTypeLegalizer::LibCallify(RTLIB::Libcall LC, SDNode *N, |
1005 | 27 | bool isSigned) { |
1006 | 27 | unsigned NumOps = N->getNumOperands(); |
1007 | 27 | SDLoc dl(N); |
1008 | 27 | if (NumOps == 0) { |
1009 | 0 | return TLI.makeLibCall(DAG, LC, N->getValueType(0), None, isSigned, |
1010 | 0 | dl).first; |
1011 | 27 | } else if (NumOps == 1) { |
1012 | 1 | SDValue Op = N->getOperand(0); |
1013 | 1 | return TLI.makeLibCall(DAG, LC, N->getValueType(0), Op, isSigned, |
1014 | 1 | dl).first; |
1015 | 26 | } else if (NumOps == 2) { |
1016 | 26 | SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) }; |
1017 | 26 | return TLI.makeLibCall(DAG, LC, N->getValueType(0), Ops, isSigned, |
1018 | 26 | dl).first; |
1019 | 26 | } |
1020 | 0 | SmallVector<SDValue, 8> Ops(NumOps); |
1021 | 0 | for (unsigned i = 0; i < NumOps; ++i) |
1022 | 0 | Ops[i] = N->getOperand(i); |
1023 | 0 |
|
1024 | 0 | return TLI.makeLibCall(DAG, LC, N->getValueType(0), Ops, isSigned, dl).first; |
1025 | 0 | } |
1026 | | |
1027 | | /// Expand a node into a call to a libcall. Similar to ExpandLibCall except that |
1028 | | /// the first operand is the in-chain. |
1029 | | std::pair<SDValue, SDValue> |
1030 | | DAGTypeLegalizer::ExpandChainLibCall(RTLIB::Libcall LC, SDNode *Node, |
1031 | 86 | bool isSigned) { |
1032 | 86 | SDValue InChain = Node->getOperand(0); |
1033 | 86 | |
1034 | 86 | TargetLowering::ArgListTy Args; |
1035 | 86 | TargetLowering::ArgListEntry Entry; |
1036 | 287 | for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i201 ) { |
1037 | 201 | EVT ArgVT = Node->getOperand(i).getValueType(); |
1038 | 201 | Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext()); |
1039 | 201 | Entry.Node = Node->getOperand(i); |
1040 | 201 | Entry.Ty = ArgTy; |
1041 | 201 | Entry.IsSExt = isSigned; |
1042 | 201 | Entry.IsZExt = !isSigned; |
1043 | 201 | Args.push_back(Entry); |
1044 | 201 | } |
1045 | 86 | SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC), |
1046 | 86 | TLI.getPointerTy(DAG.getDataLayout())); |
1047 | 86 | |
1048 | 86 | Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext()); |
1049 | 86 | |
1050 | 86 | TargetLowering::CallLoweringInfo CLI(DAG); |
1051 | 86 | CLI.setDebugLoc(SDLoc(Node)) |
1052 | 86 | .setChain(InChain) |
1053 | 86 | .setLibCallee(TLI.getLibcallCallingConv(LC), RetTy, Callee, |
1054 | 86 | std::move(Args)) |
1055 | 86 | .setSExtResult(isSigned) |
1056 | 86 | .setZExtResult(!isSigned); |
1057 | 86 | |
1058 | 86 | std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI); |
1059 | 86 | |
1060 | 86 | return CallInfo; |
1061 | 86 | } |
1062 | | |
1063 | | /// Promote the given target boolean to a target boolean of the given type. |
1064 | | /// A target boolean is an integer value, not necessarily of type i1, the bits |
1065 | | /// of which conform to getBooleanContents. |
1066 | | /// |
1067 | | /// ValVT is the type of values that produced the boolean. |
1068 | 252k | SDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, EVT ValVT) { |
1069 | 252k | SDLoc dl(Bool); |
1070 | 252k | EVT BoolVT = getSetCCResultType(ValVT); |
1071 | 252k | ISD::NodeType ExtendCode = |
1072 | 252k | TargetLowering::getExtendForContent(TLI.getBooleanContents(ValVT)); |
1073 | 252k | return DAG.getNode(ExtendCode, dl, BoolVT, Bool); |
1074 | 252k | } |
1075 | | |
1076 | | /// Return the lower LoVT bits of Op in Lo and the upper HiVT bits in Hi. |
1077 | | void DAGTypeLegalizer::SplitInteger(SDValue Op, |
1078 | | EVT LoVT, EVT HiVT, |
1079 | 48.9k | SDValue &Lo, SDValue &Hi) { |
1080 | 48.9k | SDLoc dl(Op); |
1081 | 48.9k | assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() == |
1082 | 48.9k | Op.getValueSizeInBits() && "Invalid integer splitting!"); |
1083 | 48.9k | Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op); |
1084 | 48.9k | unsigned ReqShiftAmountInBits = |
1085 | 48.9k | Log2_32_Ceil(Op.getValueType().getSizeInBits()); |
1086 | 48.9k | MVT ShiftAmountTy = |
1087 | 48.9k | TLI.getScalarShiftAmountTy(DAG.getDataLayout(), Op.getValueType()); |
1088 | 48.9k | if (ReqShiftAmountInBits > ShiftAmountTy.getSizeInBits()) |
1089 | 163 | ShiftAmountTy = MVT::getIntegerVT(NextPowerOf2(ReqShiftAmountInBits)); |
1090 | 48.9k | Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op, |
1091 | 48.9k | DAG.getConstant(LoVT.getSizeInBits(), dl, ShiftAmountTy)); |
1092 | 48.9k | Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi); |
1093 | 48.9k | } |
1094 | | |
1095 | | /// Return the lower and upper halves of Op's bits in a value type half the |
1096 | | /// size of Op's. |
1097 | | void DAGTypeLegalizer::SplitInteger(SDValue Op, |
1098 | 31.2k | SDValue &Lo, SDValue &Hi) { |
1099 | 31.2k | EVT HalfVT = |
1100 | 31.2k | EVT::getIntegerVT(*DAG.getContext(), Op.getValueSizeInBits() / 2); |
1101 | 31.2k | SplitInteger(Op, HalfVT, HalfVT, Lo, Hi); |
1102 | 31.2k | } |
1103 | | |
1104 | | |
1105 | | //===----------------------------------------------------------------------===// |
1106 | | // Entry Point |
1107 | | //===----------------------------------------------------------------------===// |
1108 | | |
1109 | | /// This transforms the SelectionDAG into a SelectionDAG that only uses types |
1110 | | /// natively supported by the target. Returns "true" if it made any changes. |
1111 | | /// |
1112 | | /// Note that this is an involved process that may invalidate pointers into |
1113 | | /// the graph. |
1114 | 1.28M | bool SelectionDAG::LegalizeTypes() { |
1115 | 1.28M | return DAGTypeLegalizer(*this).run(); |
1116 | 1.28M | } |