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