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