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