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