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