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