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