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