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