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