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