LLVM  7.0.0svn
LegalizeTypes.cpp
Go to the documentation of this file.
1 //===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the SelectionDAG::LegalizeTypes method. It transforms
11 // an arbitrary well-formed SelectionDAG to only consist of legal types. This
12 // is common code shared among the LegalizeTypes*.cpp files.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "LegalizeTypes.h"
17 #include "SDNodeDbgValue.h"
18 #include "llvm/ADT/SetVector.h"
20 #include "llvm/IR/CallingConv.h"
21 #include "llvm/IR/DataLayout.h"
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "legalize-types"
28 
29 static cl::opt<bool>
30 EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden);
31 
32 /// Do extensive, expensive, sanity checking.
33 void DAGTypeLegalizer::PerformExpensiveChecks() {
34  // If a node is not processed, then none of its values should be mapped by any
35  // of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues.
36 
37  // If a node is processed, then each value with an illegal type must be mapped
38  // by exactly one of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues.
39  // Values with a legal type may be mapped by ReplacedValues, but not by any of
40  // the other maps.
41 
42  // Note that these invariants may not hold momentarily when processing a node:
43  // the node being processed may be put in a map before being marked Processed.
44 
45  // Note that it is possible to have nodes marked NewNode in the DAG. This can
46  // occur in two ways. Firstly, a node may be created during legalization but
47  // never passed to the legalization core. This is usually due to the implicit
48  // folding that occurs when using the DAG.getNode operators. Secondly, a new
49  // node may be passed to the legalization core, but when analyzed may morph
50  // into a different node, leaving the original node as a NewNode in the DAG.
51  // A node may morph if one of its operands changes during analysis. Whether
52  // it actually morphs or not depends on whether, after updating its operands,
53  // it is equivalent to an existing node: if so, it morphs into that existing
54  // node (CSE). An operand can change during analysis if the operand is a new
55  // node that morphs, or it is a processed value that was mapped to some other
56  // value (as recorded in ReplacedValues) in which case the operand is turned
57  // into that other value. If a node morphs then the node it morphed into will
58  // be used instead of it for legalization, however the original node continues
59  // to live on in the DAG.
60  // The conclusion is that though there may be nodes marked NewNode in the DAG,
61  // all uses of such nodes are also marked NewNode: the result is a fungus of
62  // NewNodes growing on top of the useful nodes, and perhaps using them, but
63  // not used by them.
64 
65  // If a value is mapped by ReplacedValues, then it must have no uses, except
66  // by nodes marked NewNode (see above).
67 
68  // The final node obtained by mapping by ReplacedValues is not marked NewNode.
69  // Note that ReplacedValues should be applied iteratively.
70 
71  // Note that the ReplacedValues map may also map deleted nodes (by iterating
72  // over the DAG we never dereference deleted nodes). This means that it may
73  // also map nodes marked NewNode if the deallocated memory was reallocated as
74  // another node, and that new node was not seen by the LegalizeTypes machinery
75  // (for example because it was created but not used). In general, we cannot
76  // distinguish between new nodes and deleted nodes.
77  SmallVector<SDNode*, 16> NewNodes;
78  for (SDNode &Node : DAG.allnodes()) {
79  // Remember nodes marked NewNode - they are subject to extra checking below.
80  if (Node.getNodeId() == NewNode)
81  NewNodes.push_back(&Node);
82 
83  for (unsigned i = 0, e = Node.getNumValues(); i != e; ++i) {
84  SDValue Res(&Node, i);
85  EVT VT = Res.getValueType();
86  bool Failed = false;
87 
88  unsigned Mapped = 0;
89  if (ReplacedValues.find(Res) != 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  SDValue NewVal = ReplacedValues[Res];
101  DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(NewVal);
102  while (I != ReplacedValues.end()) {
103  NewVal = I->second;
104  I = ReplacedValues.find(NewVal);
105  }
106  assert(NewVal.getNode()->getNodeId() != NewNode &&
107  "ReplacedValues maps to a new node!");
108  }
109  if (PromotedIntegers.find(Res) != PromotedIntegers.end())
110  Mapped |= 2;
111  if (SoftenedFloats.find(Res) != SoftenedFloats.end())
112  Mapped |= 4;
113  if (ScalarizedVectors.find(Res) != ScalarizedVectors.end())
114  Mapped |= 8;
115  if (ExpandedIntegers.find(Res) != ExpandedIntegers.end())
116  Mapped |= 16;
117  if (ExpandedFloats.find(Res) != ExpandedFloats.end())
118  Mapped |= 32;
119  if (SplitVectors.find(Res) != SplitVectors.end())
120  Mapped |= 64;
121  if (WidenedVectors.find(Res) != WidenedVectors.end())
122  Mapped |= 128;
123  if (PromotedFloats.find(Res) != PromotedFloats.end())
124  Mapped |= 256;
125 
126  if (Node.getNodeId() != Processed) {
127  // Since we allow ReplacedValues to map deleted nodes, it may map nodes
128  // marked NewNode too, since a deleted node may have been reallocated as
129  // another node that has not been seen by the LegalizeTypes machinery.
130  if ((Node.getNodeId() == NewNode && Mapped > 1) ||
131  (Node.getNodeId() != NewNode && Mapped != 0)) {
132  dbgs() << "Unprocessed value in a map!";
133  Failed = true;
134  }
135  } else if (isTypeLegal(VT) || IgnoreNodeResults(&Node)) {
136  if (Mapped > 1) {
137  dbgs() << "Value with legal type was transformed!";
138  Failed = true;
139  }
140  } else {
141  // If the value can be kept in HW registers, softening machinery can
142  // leave it unchanged and don't put it to any map.
143  if (Mapped == 0 &&
144  !(getTypeAction(VT) == TargetLowering::TypeSoftenFloat &&
145  isLegalInHWReg(VT))) {
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  dbgs() << "\n";
174  llvm_unreachable(nullptr);
175  }
176  }
177  }
178 
179  // Checked that NewNodes are only used by other NewNodes.
180  for (unsigned i = 0, e = NewNodes.size(); i != e; ++i) {
181  SDNode *N = NewNodes[i];
182  for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
183  UI != UE; ++UI)
184  assert(UI->getNodeId() == NewNode && "NewNode used by non-NewNode!");
185  }
186 }
187 
188 /// This is the main entry point for the type legalizer. This does a top-down
189 /// traversal of the dag, legalizing types as it goes. Returns "true" if it made
190 /// any changes.
192  bool Changed = false;
193 
194  // Create a dummy node (which is not added to allnodes), that adds a reference
195  // to the root node, preventing it from being deleted, and tracking any
196  // changes of the root.
197  HandleSDNode Dummy(DAG.getRoot());
198  Dummy.setNodeId(Unanalyzed);
199 
200  // The root of the dag may dangle to deleted nodes until the type legalizer is
201  // done. Set it to null to avoid confusion.
202  DAG.setRoot(SDValue());
203 
204  // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess'
205  // (and remembering them) if they are leaves and assigning 'Unanalyzed' if
206  // non-leaves.
207  for (SDNode &Node : DAG.allnodes()) {
208  if (Node.getNumOperands() == 0) {
209  AddToWorklist(&Node);
210  } else {
211  Node.setNodeId(Unanalyzed);
212  }
213  }
214 
215  // Now that we have a set of nodes to process, handle them all.
216  while (!Worklist.empty()) {
217 #ifndef EXPENSIVE_CHECKS
219 #endif
220  PerformExpensiveChecks();
221 
222  SDNode *N = Worklist.back();
223  Worklist.pop_back();
224  assert(N->getNodeId() == ReadyToProcess &&
225  "Node should be ready if on worklist!");
226 
227  DEBUG(dbgs() << "Legalizing node: "; N->dump(&DAG));
228  if (IgnoreNodeResults(N)) {
229  DEBUG(dbgs() << "Ignoring node results\n");
230  goto ScanOperands;
231  }
232 
233  // Scan the values produced by the node, checking to see if any result
234  // types are illegal.
235  for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) {
236  EVT ResultVT = N->getValueType(i);
237  DEBUG(dbgs() << "Analyzing result type: " <<
238  ResultVT.getEVTString() << "\n");
239  switch (getTypeAction(ResultVT)) {
241  DEBUG(dbgs() << "Legal result type\n");
242  break;
243  // The following calls must take care of *all* of the node's results,
244  // not just the illegal result they were passed (this includes results
245  // with a legal type). Results can be remapped using ReplaceValueWith,
246  // or their promoted/expanded/etc values registered in PromotedIntegers,
247  // ExpandedIntegers etc.
249  PromoteIntegerResult(N, i);
250  Changed = true;
251  goto NodeDone;
253  ExpandIntegerResult(N, i);
254  Changed = true;
255  goto NodeDone;
257  Changed = SoftenFloatResult(N, i);
258  if (Changed)
259  goto NodeDone;
260  // If not changed, the result type should be legally in register.
261  assert(isLegalInHWReg(ResultVT) &&
262  "Unchanged SoftenFloatResult should be legal in register!");
263  goto ScanOperands;
265  ExpandFloatResult(N, i);
266  Changed = true;
267  goto NodeDone;
269  ScalarizeVectorResult(N, i);
270  Changed = true;
271  goto NodeDone;
273  SplitVectorResult(N, i);
274  Changed = true;
275  goto NodeDone;
277  WidenVectorResult(N, i);
278  Changed = true;
279  goto NodeDone;
281  PromoteFloatResult(N, i);
282  Changed = true;
283  goto NodeDone;
284  }
285  }
286 
287 ScanOperands:
288  // Scan the operand list for the node, handling any nodes with operands that
289  // are illegal.
290  {
291  unsigned NumOperands = N->getNumOperands();
292  bool NeedsReanalyzing = false;
293  unsigned i;
294  for (i = 0; i != NumOperands; ++i) {
295  if (IgnoreNodeResults(N->getOperand(i).getNode()))
296  continue;
297 
298  const auto Op = N->getOperand(i);
299  DEBUG(dbgs() << "Analyzing operand: "; Op.dump(&DAG));
300  EVT OpVT = Op.getValueType();
301  switch (getTypeAction(OpVT)) {
303  DEBUG(dbgs() << "Legal operand\n");
304  continue;
305  // The following calls must either replace all of the node's results
306  // using ReplaceValueWith, and return "false"; or update the node's
307  // operands in place, and return "true".
309  NeedsReanalyzing = PromoteIntegerOperand(N, i);
310  Changed = true;
311  break;
313  NeedsReanalyzing = ExpandIntegerOperand(N, i);
314  Changed = true;
315  break;
317  NeedsReanalyzing = SoftenFloatOperand(N, i);
318  Changed = true;
319  break;
321  NeedsReanalyzing = ExpandFloatOperand(N, i);
322  Changed = true;
323  break;
325  NeedsReanalyzing = ScalarizeVectorOperand(N, i);
326  Changed = true;
327  break;
329  NeedsReanalyzing = SplitVectorOperand(N, i);
330  Changed = true;
331  break;
333  NeedsReanalyzing = WidenVectorOperand(N, i);
334  Changed = true;
335  break;
337  NeedsReanalyzing = PromoteFloatOperand(N, i);
338  Changed = true;
339  break;
340  }
341  break;
342  }
343 
344  // The sub-method updated N in place. Check to see if any operands are new,
345  // and if so, mark them. If the node needs revisiting, don't add all users
346  // to the worklist etc.
347  if (NeedsReanalyzing) {
348  assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
349 
350  N->setNodeId(NewNode);
351  // Recompute the NodeId and correct processed operands, adding the node to
352  // the worklist if ready.
353  SDNode *M = AnalyzeNewNode(N);
354  if (M == N)
355  // The node didn't morph - nothing special to do, it will be revisited.
356  continue;
357 
358  // The node morphed - this is equivalent to legalizing by replacing every
359  // value of N with the corresponding value of M. So do that now.
360  assert(N->getNumValues() == M->getNumValues() &&
361  "Node morphing changed the number of results!");
362  for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
363  // Replacing the value takes care of remapping the new value.
364  ReplaceValueWith(SDValue(N, i), SDValue(M, i));
365  assert(N->getNodeId() == NewNode && "Unexpected node state!");
366  // The node continues to live on as part of the NewNode fungus that
367  // grows on top of the useful nodes. Nothing more needs to be done
368  // with it - move on to the next node.
369  continue;
370  }
371 
372  if (i == NumOperands) {
373  DEBUG(dbgs() << "Legally typed node: "; N->dump(&DAG); dbgs() << "\n");
374  }
375  }
376 NodeDone:
377 
378  // If we reach here, the node was processed, potentially creating new nodes.
379  // Mark it as processed and add its users to the worklist as appropriate.
380  assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
381  N->setNodeId(Processed);
382 
383  for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
384  UI != E; ++UI) {
385  SDNode *User = *UI;
386  int NodeId = User->getNodeId();
387 
388  // This node has two options: it can either be a new node or its Node ID
389  // may be a count of the number of operands it has that are not ready.
390  if (NodeId > 0) {
391  User->setNodeId(NodeId-1);
392 
393  // If this was the last use it was waiting on, add it to the ready list.
394  if (NodeId-1 == ReadyToProcess)
395  Worklist.push_back(User);
396  continue;
397  }
398 
399  // If this is an unreachable new node, then ignore it. If it ever becomes
400  // reachable by being used by a newly created node then it will be handled
401  // by AnalyzeNewNode.
402  if (NodeId == NewNode)
403  continue;
404 
405  // Otherwise, this node is new: this is the first operand of it that
406  // became ready. Its new NodeId is the number of operands it has minus 1
407  // (as this node is now processed).
408  assert(NodeId == Unanalyzed && "Unknown node ID!");
409  User->setNodeId(User->getNumOperands() - 1);
410 
411  // If the node only has a single operand, it is now ready.
412  if (User->getNumOperands() == 1)
413  Worklist.push_back(User);
414  }
415  }
416 
417 #ifndef EXPENSIVE_CHECKS
419 #endif
420  PerformExpensiveChecks();
421 
422  // If the root changed (e.g. it was a dead load) update the root.
423  DAG.setRoot(Dummy.getValue());
424 
425  // Remove dead nodes. This is important to do for cleanliness but also before
426  // the checking loop below. Implicit folding by the DAG.getNode operators and
427  // node morphing can cause unreachable nodes to be around with their flags set
428  // to new.
429  DAG.RemoveDeadNodes();
430 
431  // In a debug build, scan all the nodes to make sure we found them all. This
432  // ensures that there are no cycles and that everything got processed.
433 #ifndef NDEBUG
434  for (SDNode &Node : DAG.allnodes()) {
435  bool Failed = false;
436 
437  // Check that all result types are legal.
438  // A value type is illegal if its TypeAction is not TypeLegal,
439  // and TLI.RegClassForVT does not have a register class for this type.
440  // For example, the x86_64 target has f128 that is not TypeLegal,
441  // to have softened operators, but it also has FR128 register class to
442  // pass and return f128 values. Hence a legalized node can have f128 type.
443  if (!IgnoreNodeResults(&Node))
444  for (unsigned i = 0, NumVals = Node.getNumValues(); i < NumVals; ++i)
445  if (!isTypeLegal(Node.getValueType(i)) &&
446  !TLI.isTypeLegal(Node.getValueType(i))) {
447  dbgs() << "Result type " << i << " illegal: ";
448  Node.dump(&DAG);
449  Failed = true;
450  }
451 
452  // Check that all operand types are legal.
453  for (unsigned i = 0, NumOps = Node.getNumOperands(); i < NumOps; ++i)
454  if (!IgnoreNodeResults(Node.getOperand(i).getNode()) &&
455  !isTypeLegal(Node.getOperand(i).getValueType()) &&
456  !TLI.isTypeLegal(Node.getOperand(i).getValueType())) {
457  dbgs() << "Operand type " << i << " illegal: ";
458  Node.getOperand(i).dump(&DAG);
459  Failed = true;
460  }
461 
462  if (Node.getNodeId() != Processed) {
463  if (Node.getNodeId() == NewNode)
464  dbgs() << "New node not analyzed?\n";
465  else if (Node.getNodeId() == Unanalyzed)
466  dbgs() << "Unanalyzed node not noticed?\n";
467  else if (Node.getNodeId() > 0)
468  dbgs() << "Operand not processed?\n";
469  else if (Node.getNodeId() == ReadyToProcess)
470  dbgs() << "Not added to worklist?\n";
471  Failed = true;
472  }
473 
474  if (Failed) {
475  Node.dump(&DAG); dbgs() << "\n";
476  llvm_unreachable(nullptr);
477  }
478  }
479 #endif
480 
481  return Changed;
482 }
483 
484 /// The specified node is the root of a subtree of potentially new nodes.
485 /// Correct any processed operands (this may change the node) and calculate the
486 /// NodeId. If the node itself changes to a processed node, it is not remapped -
487 /// the caller needs to take care of this. Returns the potentially changed node.
488 SDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) {
489  // If this was an existing node that is already done, we're done.
490  if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed)
491  return N;
492 
493  // Remove any stale map entries.
494  ExpungeNode(N);
495 
496  // Okay, we know that this node is new. Recursively walk all of its operands
497  // to see if they are new also. The depth of this walk is bounded by the size
498  // of the new tree that was constructed (usually 2-3 nodes), so we don't worry
499  // about revisiting of nodes.
500  //
501  // As we walk the operands, keep track of the number of nodes that are
502  // processed. If non-zero, this will become the new nodeid of this node.
503  // Operands may morph when they are analyzed. If so, the node will be
504  // updated after all operands have been analyzed. Since this is rare,
505  // the code tries to minimize overhead in the non-morphing case.
506 
507  std::vector<SDValue> NewOps;
508  unsigned NumProcessed = 0;
509  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
510  SDValue OrigOp = N->getOperand(i);
511  SDValue Op = OrigOp;
512 
513  AnalyzeNewValue(Op); // Op may morph.
514 
515  if (Op.getNode()->getNodeId() == Processed)
516  ++NumProcessed;
517 
518  if (!NewOps.empty()) {
519  // Some previous operand changed. Add this one to the list.
520  NewOps.push_back(Op);
521  } else if (Op != OrigOp) {
522  // This is the first operand to change - add all operands so far.
523  NewOps.insert(NewOps.end(), N->op_begin(), N->op_begin() + i);
524  NewOps.push_back(Op);
525  }
526  }
527 
528  // Some operands changed - update the node.
529  if (!NewOps.empty()) {
530  SDNode *M = DAG.UpdateNodeOperands(N, NewOps);
531  if (M != N) {
532  // The node morphed into a different node. Normally for this to happen
533  // the original node would have to be marked NewNode. However this can
534  // in theory momentarily not be the case while ReplaceValueWith is doing
535  // its stuff. Mark the original node NewNode to help sanity checking.
536  N->setNodeId(NewNode);
537  if (M->getNodeId() != NewNode && M->getNodeId() != Unanalyzed)
538  // It morphed into a previously analyzed node - nothing more to do.
539  return M;
540 
541  // It morphed into a different new node. Do the equivalent of passing
542  // it to AnalyzeNewNode: expunge it and calculate the NodeId. No need
543  // to remap the operands, since they are the same as the operands we
544  // remapped above.
545  N = M;
546  ExpungeNode(N);
547  }
548  }
549 
550  // Calculate the NodeId.
551  N->setNodeId(N->getNumOperands() - NumProcessed);
552  if (N->getNodeId() == ReadyToProcess)
553  Worklist.push_back(N);
554 
555  return N;
556 }
557 
558 /// Call AnalyzeNewNode, updating the node in Val if needed.
559 /// If the node changes to a processed node, then remap it.
560 void DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) {
561  Val.setNode(AnalyzeNewNode(Val.getNode()));
562  if (Val.getNode()->getNodeId() == Processed)
563  // We were passed a processed node, or it morphed into one - remap it.
564  RemapValue(Val);
565 }
566 
567 /// If N has a bogus mapping in ReplacedValues, eliminate it.
568 /// This can occur when a node is deleted then reallocated as a new node -
569 /// the mapping in ReplacedValues applies to the deleted node, not the new
570 /// one.
571 /// The only map that can have a deleted node as a source is ReplacedValues.
572 /// Other maps can have deleted nodes as targets, but since their looked-up
573 /// values are always immediately remapped using RemapValue, resulting in a
574 /// not-deleted node, this is harmless as long as ReplacedValues/RemapValue
575 /// always performs correct mappings. In order to keep the mapping correct,
576 /// ExpungeNode should be called on any new nodes *before* adding them as
577 /// either source or target to ReplacedValues (which typically means calling
578 /// Expunge when a new node is first seen, since it may no longer be marked
579 /// NewNode by the time it is added to ReplacedValues).
580 void DAGTypeLegalizer::ExpungeNode(SDNode *N) {
581  if (N->getNodeId() != NewNode)
582  return;
583 
584  // If N is not remapped by ReplacedValues then there is nothing to do.
585  unsigned i, e;
586  for (i = 0, e = N->getNumValues(); i != e; ++i)
587  if (ReplacedValues.find(SDValue(N, i)) != ReplacedValues.end())
588  break;
589 
590  if (i == e)
591  return;
592 
593  // Remove N from all maps - this is expensive but rare.
594 
595  for (DenseMap<SDValue, SDValue>::iterator I = PromotedIntegers.begin(),
596  E = PromotedIntegers.end(); I != E; ++I) {
597  assert(I->first.getNode() != N);
598  RemapValue(I->second);
599  }
600 
601  for (DenseMap<SDValue, SDValue>::iterator I = SoftenedFloats.begin(),
602  E = SoftenedFloats.end(); I != E; ++I) {
603  assert(I->first.getNode() != N);
604  RemapValue(I->second);
605  }
606 
607  for (DenseMap<SDValue, SDValue>::iterator I = ScalarizedVectors.begin(),
608  E = ScalarizedVectors.end(); I != E; ++I) {
609  assert(I->first.getNode() != N);
610  RemapValue(I->second);
611  }
612 
613  for (DenseMap<SDValue, SDValue>::iterator I = WidenedVectors.begin(),
614  E = WidenedVectors.end(); I != E; ++I) {
615  assert(I->first.getNode() != N);
616  RemapValue(I->second);
617  }
618 
619  for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
620  I = ExpandedIntegers.begin(), E = ExpandedIntegers.end(); I != E; ++I){
621  assert(I->first.getNode() != N);
622  RemapValue(I->second.first);
623  RemapValue(I->second.second);
624  }
625 
626  for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
627  I = ExpandedFloats.begin(), E = ExpandedFloats.end(); I != E; ++I) {
628  assert(I->first.getNode() != N);
629  RemapValue(I->second.first);
630  RemapValue(I->second.second);
631  }
632 
633  for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
634  I = SplitVectors.begin(), E = SplitVectors.end(); I != E; ++I) {
635  assert(I->first.getNode() != N);
636  RemapValue(I->second.first);
637  RemapValue(I->second.second);
638  }
639 
640  for (DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.begin(),
641  E = ReplacedValues.end(); I != E; ++I)
642  RemapValue(I->second);
643 
644  for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
645  ReplacedValues.erase(SDValue(N, i));
646 }
647 
648 /// If the specified value was already legalized to another value,
649 /// replace it by that value.
650 void DAGTypeLegalizer::RemapValue(SDValue &N) {
651  DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(N);
652  if (I != ReplacedValues.end()) {
653  // Use path compression to speed up future lookups if values get multiply
654  // replaced with other values.
655  RemapValue(I->second);
656  N = I->second;
657 
658  // Note that it is possible to have N.getNode()->getNodeId() == NewNode at
659  // this point because it is possible for a node to be put in the map before
660  // being processed.
661  }
662 }
663 
664 namespace {
665  /// This class is a DAGUpdateListener that listens for updates to nodes and
666  /// recomputes their ready state.
667  class NodeUpdateListener : public SelectionDAG::DAGUpdateListener {
668  DAGTypeLegalizer &DTL;
669  SmallSetVector<SDNode*, 16> &NodesToAnalyze;
670  public:
671  explicit NodeUpdateListener(DAGTypeLegalizer &dtl,
674  DTL(dtl), NodesToAnalyze(nta) {}
675 
676  void NodeDeleted(SDNode *N, SDNode *E) override {
679  "Invalid node ID for RAUW deletion!");
680  // It is possible, though rare, for the deleted node N to occur as a
681  // target in a map, so note the replacement N -> E in ReplacedValues.
682  assert(E && "Node not replaced?");
683  DTL.NoteDeletion(N, E);
684 
685  // In theory the deleted node could also have been scheduled for analysis.
686  // So remove it from the set of nodes which will be analyzed.
687  NodesToAnalyze.remove(N);
688 
689  // In general nothing needs to be done for E, since it didn't change but
690  // only gained new uses. However N -> E was just added to ReplacedValues,
691  // and the result of a ReplacedValues mapping is not allowed to be marked
692  // NewNode. So if E is marked NewNode, then it needs to be analyzed.
694  NodesToAnalyze.insert(E);
695  }
696 
697  void NodeUpdated(SDNode *N) override {
698  // Node updates can mean pretty much anything. It is possible that an
699  // operand was set to something already processed (f.e.) in which case
700  // this node could become ready. Recompute its flags.
703  "Invalid node ID for RAUW deletion!");
705  NodesToAnalyze.insert(N);
706  }
707  };
708 }
709 
710 
711 /// The specified value was legalized to the specified other value.
712 /// Update the DAG and NodeIds replacing any uses of From to use To instead.
713 void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) {
714  assert(From.getNode() != To.getNode() && "Potential legalization loop!");
715 
716  // If expansion produced new nodes, make sure they are properly marked.
717  ExpungeNode(From.getNode());
718  AnalyzeNewValue(To); // Expunges To.
719 
720  // Anything that used the old node should now use the new one. Note that this
721  // can potentially cause recursive merging.
722  SmallSetVector<SDNode*, 16> NodesToAnalyze;
723  NodeUpdateListener NUL(*this, NodesToAnalyze);
724  do {
725  DAG.ReplaceAllUsesOfValueWith(From, To);
726 
727  // The old node may still be present in a map like ExpandedIntegers or
728  // PromotedIntegers. Inform maps about the replacement.
729  ReplacedValues[From] = To;
730 
731  // Process the list of nodes that need to be reanalyzed.
732  while (!NodesToAnalyze.empty()) {
733  SDNode *N = NodesToAnalyze.back();
734  NodesToAnalyze.pop_back();
736  // The node was analyzed while reanalyzing an earlier node - it is safe
737  // to skip. Note that this is not a morphing node - otherwise it would
738  // still be marked NewNode.
739  continue;
740 
741  // Analyze the node's operands and recalculate the node ID.
742  SDNode *M = AnalyzeNewNode(N);
743  if (M != N) {
744  // The node morphed into a different node. Make everyone use the new
745  // node instead.
746  assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!");
747  assert(N->getNumValues() == M->getNumValues() &&
748  "Node morphing changed the number of results!");
749  for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
750  SDValue OldVal(N, i);
751  SDValue NewVal(M, i);
752  if (M->getNodeId() == Processed)
753  RemapValue(NewVal);
754  DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal);
755  // OldVal may be a target of the ReplacedValues map which was marked
756  // NewNode to force reanalysis because it was updated. Ensure that
757  // anything that ReplacedValues mapped to OldVal will now be mapped
758  // all the way to NewVal.
759  ReplacedValues[OldVal] = NewVal;
760  }
761  // The original node continues to exist in the DAG, marked NewNode.
762  }
763  }
764  // When recursively update nodes with new nodes, it is possible to have
765  // new uses of From due to CSE. If this happens, replace the new uses of
766  // From with To.
767  } while (!From.use_empty());
768 }
769 
770 void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) {
771  assert(Result.getValueType() ==
772  TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
773  "Invalid type for promoted integer");
774  AnalyzeNewValue(Result);
775 
776  SDValue &OpEntry = PromotedIntegers[Op];
777  assert(!OpEntry.getNode() && "Node is already promoted!");
778  OpEntry = Result;
779 }
780 
781 void DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) {
782  // f128 of x86_64 could be kept in SSE registers,
783  // but sometimes softened to i128.
784  assert((Result.getValueType() ==
785  TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) ||
786  Op.getValueType() ==
787  TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType())) &&
788  "Invalid type for softened float");
789  AnalyzeNewValue(Result);
790 
791  SDValue &OpEntry = SoftenedFloats[Op];
792  // Allow repeated calls to save f128 type nodes
793  // or any node with type that transforms to itself.
794  // Many operations on these types are not softened.
795  assert((!OpEntry.getNode()||
796  Op.getValueType() ==
797  TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType())) &&
798  "Node is already converted to integer!");
799  OpEntry = Result;
800 }
801 
802 void DAGTypeLegalizer::SetPromotedFloat(SDValue Op, SDValue Result) {
803  assert(Result.getValueType() ==
804  TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
805  "Invalid type for promoted float");
806  AnalyzeNewValue(Result);
807 
808  SDValue &OpEntry = PromotedFloats[Op];
809  assert(!OpEntry.getNode() && "Node is already promoted!");
810  OpEntry = Result;
811 }
812 
813 void DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) {
814  // Note that in some cases vector operation operands may be greater than
815  // the vector element type. For example BUILD_VECTOR of type <1 x i1> with
816  // a constant i8 operand.
818  "Invalid type for scalarized vector");
819  AnalyzeNewValue(Result);
820 
821  SDValue &OpEntry = ScalarizedVectors[Op];
822  assert(!OpEntry.getNode() && "Node is already scalarized!");
823  OpEntry = Result;
824 }
825 
826 void DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo,
827  SDValue &Hi) {
828  std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op];
829  RemapValue(Entry.first);
830  RemapValue(Entry.second);
831  assert(Entry.first.getNode() && "Operand isn't expanded");
832  Lo = Entry.first;
833  Hi = Entry.second;
834 }
835 
836 void DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo,
837  SDValue Hi) {
838  assert(Lo.getValueType() ==
839  TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
840  Hi.getValueType() == Lo.getValueType() &&
841  "Invalid type for expanded integer");
842  // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
843  AnalyzeNewValue(Lo);
844  AnalyzeNewValue(Hi);
845 
846  // Transfer debug values. Don't invalidate the source debug value until it's
847  // been transferred to the high and low bits.
848  if (DAG.getDataLayout().isBigEndian()) {
849  DAG.transferDbgValues(Op, Hi, 0, Hi.getValueSizeInBits(), false);
850  DAG.transferDbgValues(Op, Lo, Hi.getValueSizeInBits(),
851  Lo.getValueSizeInBits());
852  } else {
853  DAG.transferDbgValues(Op, Lo, 0, Lo.getValueSizeInBits(), false);
854  DAG.transferDbgValues(Op, Hi, Lo.getValueSizeInBits(),
855  Hi.getValueSizeInBits());
856  }
857 
858  // Remember that this is the result of the node.
859  std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op];
860  assert(!Entry.first.getNode() && "Node already expanded");
861  Entry.first = Lo;
862  Entry.second = Hi;
863 }
864 
865 void DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo,
866  SDValue &Hi) {
867  std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op];
868  RemapValue(Entry.first);
869  RemapValue(Entry.second);
870  assert(Entry.first.getNode() && "Operand isn't expanded");
871  Lo = Entry.first;
872  Hi = Entry.second;
873 }
874 
875 void DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo,
876  SDValue Hi) {
877  assert(Lo.getValueType() ==
878  TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
879  Hi.getValueType() == Lo.getValueType() &&
880  "Invalid type for expanded float");
881  // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
882  AnalyzeNewValue(Lo);
883  AnalyzeNewValue(Hi);
884 
885  // Remember that this is the result of the node.
886  std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op];
887  assert(!Entry.first.getNode() && "Node already expanded");
888  Entry.first = Lo;
889  Entry.second = Hi;
890 }
891 
892 void DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo,
893  SDValue &Hi) {
894  std::pair<SDValue, SDValue> &Entry = SplitVectors[Op];
895  RemapValue(Entry.first);
896  RemapValue(Entry.second);
897  assert(Entry.first.getNode() && "Operand isn't split");
898  Lo = Entry.first;
899  Hi = Entry.second;
900 }
901 
902 void DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo,
903  SDValue Hi) {
908  Hi.getValueType() == Lo.getValueType() &&
909  "Invalid type for split vector");
910  // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
911  AnalyzeNewValue(Lo);
912  AnalyzeNewValue(Hi);
913 
914  // Remember that this is the result of the node.
915  std::pair<SDValue, SDValue> &Entry = SplitVectors[Op];
916  assert(!Entry.first.getNode() && "Node already split");
917  Entry.first = Lo;
918  Entry.second = Hi;
919 }
920 
921 void DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) {
922  assert(Result.getValueType() ==
923  TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
924  "Invalid type for widened vector");
925  AnalyzeNewValue(Result);
926 
927  SDValue &OpEntry = WidenedVectors[Op];
928  assert(!OpEntry.getNode() && "Node already widened!");
929  OpEntry = Result;
930 }
931 
932 
933 //===----------------------------------------------------------------------===//
934 // Utilities.
935 //===----------------------------------------------------------------------===//
936 
937 /// Convert to an integer of the same size.
938 SDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) {
939  unsigned BitWidth = Op.getValueSizeInBits();
940  return DAG.getNode(ISD::BITCAST, SDLoc(Op),
941  EVT::getIntegerVT(*DAG.getContext(), BitWidth), Op);
942 }
943 
944 /// Convert to a vector of integers of the same size.
945 SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(SDValue Op) {
946  assert(Op.getValueType().isVector() && "Only applies to vectors!");
947  unsigned EltWidth = Op.getScalarValueSizeInBits();
948  EVT EltNVT = EVT::getIntegerVT(*DAG.getContext(), EltWidth);
949  auto EltCnt = Op.getValueType().getVectorElementCount();
950  return DAG.getNode(ISD::BITCAST, SDLoc(Op),
951  EVT::getVectorVT(*DAG.getContext(), EltNVT, EltCnt), Op);
952 }
953 
954 SDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op,
955  EVT DestVT) {
956  SDLoc dl(Op);
957  // Create the stack frame object. Make sure it is aligned for both
958  // the source and destination types.
959  SDValue StackPtr = DAG.CreateStackTemporary(Op.getValueType(), DestVT);
960  // Emit a store to the stack slot.
961  SDValue Store =
962  DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, MachinePointerInfo());
963  // Result is a load from the stack slot.
964  return DAG.getLoad(DestVT, dl, Store, StackPtr, MachinePointerInfo());
965 }
966 
967 /// Replace the node's results with custom code provided by the target and
968 /// return "true", or do nothing and return "false".
969 /// The last parameter is FALSE if we are dealing with a node with legal
970 /// result types and illegal operand. The second parameter denotes the type of
971 /// illegal OperandNo in that case.
972 /// The last parameter being TRUE means we are dealing with a
973 /// node with illegal result types. The second parameter denotes the type of
974 /// illegal ResNo in that case.
975 bool DAGTypeLegalizer::CustomLowerNode(SDNode *N, EVT VT, bool LegalizeResult) {
976  // See if the target wants to custom lower this node.
977  if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom)
978  return false;
979 
981  if (LegalizeResult)
982  TLI.ReplaceNodeResults(N, Results, DAG);
983  else
984  TLI.LowerOperationWrapper(N, Results, DAG);
985 
986  if (Results.empty())
987  // The target didn't want to custom lower it after all.
988  return false;
989 
990  // When called from DAGTypeLegalizer::ExpandIntegerResult, we might need to
991  // provide the same kind of custom splitting behavior.
992  if (Results.size() == N->getNumValues() + 1 && LegalizeResult) {
993  // We've legalized a return type by splitting it. If there is a chain,
994  // replace that too.
995  SetExpandedInteger(SDValue(N, 0), Results[0], Results[1]);
996  if (N->getNumValues() > 1)
997  ReplaceValueWith(SDValue(N, 1), Results[2]);
998  return true;
999  }
1000 
1001  // Make everything that once used N's values now use those in Results instead.
1002  assert(Results.size() == N->getNumValues() &&
1003  "Custom lowering returned the wrong number of results!");
1004  for (unsigned i = 0, e = Results.size(); i != e; ++i) {
1005  ReplaceValueWith(SDValue(N, i), Results[i]);
1006  }
1007  return true;
1008 }
1009 
1010 
1011 /// Widen the node's results with custom code provided by the target and return
1012 /// "true", or do nothing and return "false".
1013 bool DAGTypeLegalizer::CustomWidenLowerNode(SDNode *N, EVT VT) {
1014  // See if the target wants to custom lower this node.
1015  if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom)
1016  return false;
1017 
1019  TLI.ReplaceNodeResults(N, Results, DAG);
1020 
1021  if (Results.empty())
1022  // The target didn't want to custom widen lower its result after all.
1023  return false;
1024 
1025  // Update the widening map.
1026  assert(Results.size() == N->getNumValues() &&
1027  "Custom lowering returned the wrong number of results!");
1028  for (unsigned i = 0, e = Results.size(); i != e; ++i) {
1029  // If this is a chain output just replace it.
1030  if (Results[i].getValueType() == MVT::Other)
1031  ReplaceValueWith(SDValue(N, i), Results[i]);
1032  else
1033  SetWidenedVector(SDValue(N, i), Results[i]);
1034  }
1035  return true;
1036 }
1037 
1038 SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(SDNode *N, unsigned ResNo) {
1039  for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
1040  if (i != ResNo)
1041  ReplaceValueWith(SDValue(N, i), SDValue(N->getOperand(i)));
1042  return SDValue(N->getOperand(ResNo));
1043 }
1044 
1045 /// Use ISD::EXTRACT_ELEMENT nodes to extract the low and high parts of the
1046 /// given value.
1047 void DAGTypeLegalizer::GetPairElements(SDValue Pair,
1048  SDValue &Lo, SDValue &Hi) {
1049  SDLoc dl(Pair);
1050  EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.getValueType());
1051  Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair,
1052  DAG.getIntPtrConstant(0, dl));
1053  Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair,
1054  DAG.getIntPtrConstant(1, dl));
1055 }
1056 
1057 /// Build an integer with low bits Lo and high bits Hi.
1058 SDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) {
1059  // Arbitrarily use dlHi for result SDLoc
1060  SDLoc dlHi(Hi);
1061  SDLoc dlLo(Lo);
1062  EVT LVT = Lo.getValueType();
1063  EVT HVT = Hi.getValueType();
1064  EVT NVT = EVT::getIntegerVT(*DAG.getContext(),
1065  LVT.getSizeInBits() + HVT.getSizeInBits());
1066 
1067  Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo);
1068  Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi);
1069  Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi,
1070  DAG.getConstant(LVT.getSizeInBits(), dlHi,
1071  TLI.getPointerTy(DAG.getDataLayout())));
1072  return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi);
1073 }
1074 
1075 /// Convert the node into a libcall with the same prototype.
1076 SDValue DAGTypeLegalizer::LibCallify(RTLIB::Libcall LC, SDNode *N,
1077  bool isSigned) {
1078  unsigned NumOps = N->getNumOperands();
1079  SDLoc dl(N);
1080  if (NumOps == 0) {
1081  return TLI.makeLibCall(DAG, LC, N->getValueType(0), None, isSigned,
1082  dl).first;
1083  } else if (NumOps == 1) {
1084  SDValue Op = N->getOperand(0);
1085  return TLI.makeLibCall(DAG, LC, N->getValueType(0), Op, isSigned,
1086  dl).first;
1087  } else if (NumOps == 2) {
1088  SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
1089  return TLI.makeLibCall(DAG, LC, N->getValueType(0), Ops, isSigned,
1090  dl).first;
1091  }
1092  SmallVector<SDValue, 8> Ops(NumOps);
1093  for (unsigned i = 0; i < NumOps; ++i)
1094  Ops[i] = N->getOperand(i);
1095 
1096  return TLI.makeLibCall(DAG, LC, N->getValueType(0), Ops, isSigned, dl).first;
1097 }
1098 
1099 /// Expand a node into a call to a libcall. Similar to ExpandLibCall except that
1100 /// the first operand is the in-chain.
1101 std::pair<SDValue, SDValue>
1102 DAGTypeLegalizer::ExpandChainLibCall(RTLIB::Libcall LC, SDNode *Node,
1103  bool isSigned) {
1104  SDValue InChain = Node->getOperand(0);
1105 
1108  for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) {
1109  EVT ArgVT = Node->getOperand(i).getValueType();
1110  Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
1111  Entry.Node = Node->getOperand(i);
1112  Entry.Ty = ArgTy;
1113  Entry.IsSExt = isSigned;
1114  Entry.IsZExt = !isSigned;
1115  Args.push_back(Entry);
1116  }
1117  SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
1118  TLI.getPointerTy(DAG.getDataLayout()));
1119 
1120  Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext());
1121 
1123  CLI.setDebugLoc(SDLoc(Node))
1124  .setChain(InChain)
1125  .setLibCallee(TLI.getLibcallCallingConv(LC), RetTy, Callee,
1126  std::move(Args))
1127  .setSExtResult(isSigned)
1128  .setZExtResult(!isSigned);
1129 
1130  std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
1131 
1132  return CallInfo;
1133 }
1134 
1135 /// Promote the given target boolean to a target boolean of the given type.
1136 /// A target boolean is an integer value, not necessarily of type i1, the bits
1137 /// of which conform to getBooleanContents.
1138 ///
1139 /// ValVT is the type of values that produced the boolean.
1140 SDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, EVT ValVT) {
1141  SDLoc dl(Bool);
1142  EVT BoolVT = getSetCCResultType(ValVT);
1143  ISD::NodeType ExtendCode =
1144  TargetLowering::getExtendForContent(TLI.getBooleanContents(ValVT));
1145  return DAG.getNode(ExtendCode, dl, BoolVT, Bool);
1146 }
1147 
1148 /// Return the lower LoVT bits of Op in Lo and the upper HiVT bits in Hi.
1149 void DAGTypeLegalizer::SplitInteger(SDValue Op,
1150  EVT LoVT, EVT HiVT,
1151  SDValue &Lo, SDValue &Hi) {
1152  SDLoc dl(Op);
1153  assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() ==
1154  Op.getValueSizeInBits() && "Invalid integer splitting!");
1155  Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op);
1156  unsigned ReqShiftAmountInBits =
1158  MVT ShiftAmountTy =
1159  TLI.getScalarShiftAmountTy(DAG.getDataLayout(), Op.getValueType());
1160  if (ReqShiftAmountInBits > ShiftAmountTy.getSizeInBits())
1161  ShiftAmountTy = MVT::getIntegerVT(NextPowerOf2(ReqShiftAmountInBits));
1162  Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op,
1163  DAG.getConstant(LoVT.getSizeInBits(), dl, ShiftAmountTy));
1164  Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi);
1165 }
1166 
1167 /// Return the lower and upper halves of Op's bits in a value type half the
1168 /// size of Op's.
1169 void DAGTypeLegalizer::SplitInteger(SDValue Op,
1170  SDValue &Lo, SDValue &Hi) {
1171  EVT HalfVT =
1172  EVT::getIntegerVT(*DAG.getContext(), Op.getValueSizeInBits() / 2);
1173  SplitInteger(Op, HalfVT, HalfVT, Lo, Hi);
1174 }
1175 
1176 
1177 //===----------------------------------------------------------------------===//
1178 // Entry Point
1179 //===----------------------------------------------------------------------===//
1180 
1181 /// This transforms the SelectionDAG into a SelectionDAG that only uses types
1182 /// natively supported by the target. Returns "true" if it made any changes.
1183 ///
1184 /// Note that this is an involved process that may invalidate pointers into
1185 /// the graph.
1187  return DAGTypeLegalizer(*this).run();
1188 }
BITCAST - This operator converts between integer, vector and FP values, as if the value was stored to...
Definition: ISDOpcodes.h:546
static MVT getIntegerVT(unsigned BitWidth)
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
Definition: MathExtras.h:544
EVT getValueType() const
Return the ValueType of the referenced return value.
EXTRACT_ELEMENT - This is used to get the lower or upper (determined by a Constant, which is required to be operand #1) half of the integer or float value specified as operand #0.
Definition: ISDOpcodes.h:184
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
bool LegalizeTypes()
This transforms the SelectionDAG into a SelectionDAG that only uses types natively supported by the t...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
EVT getValueType(unsigned ResNo) const
Return the type of a specified result.
Clients of various APIs that cause global effects on the DAG can optionally implement this interface...
Definition: SelectionDAG.h:265
friend struct DAGUpdateListener
DAGUpdateListener is a friend so it can manipulate the listener stack.
Definition: SelectionDAG.h:307
Libcall
RTLIB::Libcall enum - This enum defines all of the runtime library calls the backend can emit...
uint32_t NodeId
Definition: RDFGraph.h:261
static ISD::NodeType getExtendForContent(BooleanContent Content)
Function Alias Analysis Results
CallLoweringInfo & setDebugLoc(const SDLoc &dl)
This takes an arbitrary SelectionDAG as input and hacks on it until only value types the target machi...
Definition: LegalizeTypes.h:32
void setNodeId(int Id)
Set unique node id.
SDNode * getNode() const
get the SDNode which holds the desired result
const SDValue & setRoot(SDValue N)
Set the current root tag of the SelectionDAG.
Definition: SelectionDAG.h:455
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:129
unsigned getValueSizeInBits() const
Returns the size of the value in bits.
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
Definition: ISDOpcodes.h:39
This node&#39;s ID needs to be set to the number of its unprocessed operands.
Definition: LegalizeTypes.h:48
Shift and rotation operations.
Definition: ISDOpcodes.h:380
Type * getTypeForEVT(LLVMContext &Context) const
This method returns an LLVM type corresponding to the specified EVT.
Definition: ValueTypes.cpp:205
CallLoweringInfo & setChain(SDValue InChain)
unsigned getScalarValueSizeInBits() const
MVT::ElementCount getVectorElementCount() const
Definition: ValueTypes.h:281
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:158
void pop_back()
Remove the last element of the SetVector.
Definition: SetVector.h:222
SelectionDAG & getDAG() const
iterator_range< allnodes_iterator > allnodes()
Definition: SelectionDAG.h:438
unsigned getSizeInBits() const
Return the size of the specified value type in bits.
Definition: ValueTypes.h:292
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
CallLoweringInfo & setZExtResult(bool Value=true)
op_iterator op_begin() const
amdgpu Simplify well known AMD library false Value * Callee
bool use_empty() const
Return true if there are no nodes using value ResNo of Node.
static cl::opt< bool > EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden)
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
bool run()
This is the main entry point for the type legalizer.
use_iterator use_begin() const
Provide iteration support to walk over all uses of an SDNode.
Machine Value Type.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
unsigned getVectorNumElements() const
Given a vector type, return the number of elements it contains.
Definition: ValueTypes.h:273
This is a new node, not before seen, that was created in the process of legalizing some other node...
Definition: LegalizeTypes.h:44
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const SDValue & getOperand(unsigned Num) const
void RemoveDeadNodes()
This method deletes all unreachable nodes in the SelectionDAG.
This class provides iterator support for SDUse operands that use a specific SDNode.
std::string getEVTString() const
This function returns value type as a string, e.g. "i32".
Definition: ValueTypes.cpp:119
std::vector< ArgListEntry > ArgListTy
Extended Value Type.
Definition: ValueTypes.h:34
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:632
This structure contains all information that is necessary for lowering calls.
This class contains a discriminated union of information about pointers in memory operands...
unsigned getNumOperands() const
Return the number of values used by this operation.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned first
void NoteDeletion(SDNode *Old, SDNode *New)
void dump() const
Dump this node, for debugging.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
void setNode(SDNode *N)
set the SDNode
EVT getVectorElementType() const
Given a vector type, return the type of each element.
Definition: ValueTypes.h:265
SDNode * UpdateNodeOperands(SDNode *N, SDValue Op)
Mutate the specified node in-place to have the specified operands.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
Represents one node in the SelectionDAG.
This is a node that has already been processed.
Definition: LegalizeTypes.h:51
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static EVT getVectorVT(LLVMContext &Context, EVT VT, unsigned NumElements, bool IsScalable=false)
Returns the EVT that represents a vector NumElements in length, where each element is of type VT...
Definition: ValueTypes.h:73
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
static use_iterator use_end()
ZERO_EXTEND - Used for integer types, zeroing the new bits.
Definition: ISDOpcodes.h:446
ANY_EXTEND - Used for integer types. The high bits are undefined.
Definition: ISDOpcodes.h:449
int getNodeId() const
Return the unique node id.
bool isVector() const
Return true if this is a vector value type.
Definition: ValueTypes.h:151
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:73
const SDValue & getRoot() const
Return the root tag of the SelectionDAG.
Definition: SelectionDAG.h:446
This class is used to form a handle around another node that is persistent and is updated across invo...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
All operands have been processed, so this node is ready to be handled.
Definition: LegalizeTypes.h:40
#define DEBUG(X)
Definition: Debug.h:118
TRUNCATE - Completely drop the high bits.
Definition: ISDOpcodes.h:452
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation...
static EVT getIntegerVT(LLVMContext &Context, unsigned BitWidth)
Returns the EVT that represents an integer with the given number of bits.
Definition: ValueTypes.h:64
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
CallLoweringInfo & setLibCallee(CallingConv::ID CC, Type *ResultType, SDValue Target, ArgListTy &&ArgsList)
DAGTypeLegalizer(SelectionDAG &dag)