add some missing quotes in debug output
[llvm/avr.git] / lib / CodeGen / SelectionDAG / LegalizeTypes.cpp
blob5992f5d534da4aec83f1986fba4f20ad2db91737
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.
14 //===----------------------------------------------------------------------===//
16 #include "LegalizeTypes.h"
17 #include "llvm/CallingConv.h"
18 #include "llvm/Target/TargetData.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/Support/CommandLine.h"
21 #include "llvm/Support/ErrorHandling.h"
22 #include "llvm/Support/raw_ostream.h"
23 using namespace llvm;
25 static cl::opt<bool>
26 EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden);
28 /// PerformExpensiveChecks - Do extensive, expensive, sanity checking.
29 void DAGTypeLegalizer::PerformExpensiveChecks() {
30 // If a node is not processed, then none of its values should be mapped by any
31 // of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues.
33 // If a node is processed, then each value with an illegal type must be mapped
34 // by exactly one of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues.
35 // Values with a legal type may be mapped by ReplacedValues, but not by any of
36 // the other maps.
38 // Note that these invariants may not hold momentarily when processing a node:
39 // the node being processed may be put in a map before being marked Processed.
41 // Note that it is possible to have nodes marked NewNode in the DAG. This can
42 // occur in two ways. Firstly, a node may be created during legalization but
43 // never passed to the legalization core. This is usually due to the implicit
44 // folding that occurs when using the DAG.getNode operators. Secondly, a new
45 // node may be passed to the legalization core, but when analyzed may morph
46 // into a different node, leaving the original node as a NewNode in the DAG.
47 // A node may morph if one of its operands changes during analysis. Whether
48 // it actually morphs or not depends on whether, after updating its operands,
49 // it is equivalent to an existing node: if so, it morphs into that existing
50 // node (CSE). An operand can change during analysis if the operand is a new
51 // node that morphs, or it is a processed value that was mapped to some other
52 // value (as recorded in ReplacedValues) in which case the operand is turned
53 // into that other value. If a node morphs then the node it morphed into will
54 // be used instead of it for legalization, however the original node continues
55 // to live on in the DAG.
56 // The conclusion is that though there may be nodes marked NewNode in the DAG,
57 // all uses of such nodes are also marked NewNode: the result is a fungus of
58 // NewNodes growing on top of the useful nodes, and perhaps using them, but
59 // not used by them.
61 // If a value is mapped by ReplacedValues, then it must have no uses, except
62 // by nodes marked NewNode (see above).
64 // The final node obtained by mapping by ReplacedValues is not marked NewNode.
65 // Note that ReplacedValues should be applied iteratively.
67 // Note that the ReplacedValues map may also map deleted nodes. By iterating
68 // over the DAG we only consider non-deleted nodes.
69 SmallVector<SDNode*, 16> NewNodes;
70 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
71 E = DAG.allnodes_end(); I != E; ++I) {
72 // Remember nodes marked NewNode - they are subject to extra checking below.
73 if (I->getNodeId() == NewNode)
74 NewNodes.push_back(I);
76 for (unsigned i = 0, e = I->getNumValues(); i != e; ++i) {
77 SDValue Res(I, i);
78 bool Failed = false;
80 unsigned Mapped = 0;
81 if (ReplacedValues.find(Res) != ReplacedValues.end()) {
82 Mapped |= 1;
83 // Check that remapped values are only used by nodes marked NewNode.
84 for (SDNode::use_iterator UI = I->use_begin(), UE = I->use_end();
85 UI != UE; ++UI)
86 if (UI.getUse().getResNo() == i)
87 assert(UI->getNodeId() == NewNode &&
88 "Remapped value has non-trivial use!");
90 // Check that the final result of applying ReplacedValues is not
91 // marked NewNode.
92 SDValue NewVal = ReplacedValues[Res];
93 DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(NewVal);
94 while (I != ReplacedValues.end()) {
95 NewVal = I->second;
96 I = ReplacedValues.find(NewVal);
98 assert(NewVal.getNode()->getNodeId() != NewNode &&
99 "ReplacedValues maps to a new node!");
101 if (PromotedIntegers.find(Res) != PromotedIntegers.end())
102 Mapped |= 2;
103 if (SoftenedFloats.find(Res) != SoftenedFloats.end())
104 Mapped |= 4;
105 if (ScalarizedVectors.find(Res) != ScalarizedVectors.end())
106 Mapped |= 8;
107 if (ExpandedIntegers.find(Res) != ExpandedIntegers.end())
108 Mapped |= 16;
109 if (ExpandedFloats.find(Res) != ExpandedFloats.end())
110 Mapped |= 32;
111 if (SplitVectors.find(Res) != SplitVectors.end())
112 Mapped |= 64;
113 if (WidenedVectors.find(Res) != WidenedVectors.end())
114 Mapped |= 128;
116 if (I->getNodeId() != Processed) {
117 if (Mapped != 0) {
118 errs() << "Unprocessed value in a map!";
119 Failed = true;
121 } else if (isTypeLegal(Res.getValueType()) || IgnoreNodeResults(I)) {
122 if (Mapped > 1) {
123 errs() << "Value with legal type was transformed!";
124 Failed = true;
126 } else {
127 if (Mapped == 0) {
128 errs() << "Processed value not in any map!";
129 Failed = true;
130 } else if (Mapped & (Mapped - 1)) {
131 errs() << "Value in multiple maps!";
132 Failed = true;
136 if (Failed) {
137 if (Mapped & 1)
138 errs() << " ReplacedValues";
139 if (Mapped & 2)
140 errs() << " PromotedIntegers";
141 if (Mapped & 4)
142 errs() << " SoftenedFloats";
143 if (Mapped & 8)
144 errs() << " ScalarizedVectors";
145 if (Mapped & 16)
146 errs() << " ExpandedIntegers";
147 if (Mapped & 32)
148 errs() << " ExpandedFloats";
149 if (Mapped & 64)
150 errs() << " SplitVectors";
151 if (Mapped & 128)
152 errs() << " WidenedVectors";
153 errs() << "\n";
154 llvm_unreachable(0);
159 // Checked that NewNodes are only used by other NewNodes.
160 for (unsigned i = 0, e = NewNodes.size(); i != e; ++i) {
161 SDNode *N = NewNodes[i];
162 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
163 UI != UE; ++UI)
164 assert(UI->getNodeId() == NewNode && "NewNode used by non-NewNode!");
168 /// run - This is the main entry point for the type legalizer. This does a
169 /// top-down traversal of the dag, legalizing types as it goes. Returns "true"
170 /// if it made any changes.
171 bool DAGTypeLegalizer::run() {
172 bool Changed = false;
174 // Create a dummy node (which is not added to allnodes), that adds a reference
175 // to the root node, preventing it from being deleted, and tracking any
176 // changes of the root.
177 HandleSDNode Dummy(DAG.getRoot());
178 Dummy.setNodeId(Unanalyzed);
180 // The root of the dag may dangle to deleted nodes until the type legalizer is
181 // done. Set it to null to avoid confusion.
182 DAG.setRoot(SDValue());
184 // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess'
185 // (and remembering them) if they are leaves and assigning 'Unanalyzed' if
186 // non-leaves.
187 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
188 E = DAG.allnodes_end(); I != E; ++I) {
189 if (I->getNumOperands() == 0) {
190 I->setNodeId(ReadyToProcess);
191 Worklist.push_back(I);
192 } else {
193 I->setNodeId(Unanalyzed);
197 // Now that we have a set of nodes to process, handle them all.
198 while (!Worklist.empty()) {
199 #ifndef XDEBUG
200 if (EnableExpensiveChecks)
201 #endif
202 PerformExpensiveChecks();
204 SDNode *N = Worklist.back();
205 Worklist.pop_back();
206 assert(N->getNodeId() == ReadyToProcess &&
207 "Node should be ready if on worklist!");
209 if (IgnoreNodeResults(N))
210 goto ScanOperands;
212 // Scan the values produced by the node, checking to see if any result
213 // types are illegal.
214 for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) {
215 EVT ResultVT = N->getValueType(i);
216 switch (getTypeAction(ResultVT)) {
217 default:
218 assert(false && "Unknown action!");
219 case Legal:
220 break;
221 // The following calls must take care of *all* of the node's results,
222 // not just the illegal result they were passed (this includes results
223 // with a legal type). Results can be remapped using ReplaceValueWith,
224 // or their promoted/expanded/etc values registered in PromotedIntegers,
225 // ExpandedIntegers etc.
226 case PromoteInteger:
227 PromoteIntegerResult(N, i);
228 Changed = true;
229 goto NodeDone;
230 case ExpandInteger:
231 ExpandIntegerResult(N, i);
232 Changed = true;
233 goto NodeDone;
234 case SoftenFloat:
235 SoftenFloatResult(N, i);
236 Changed = true;
237 goto NodeDone;
238 case ExpandFloat:
239 ExpandFloatResult(N, i);
240 Changed = true;
241 goto NodeDone;
242 case ScalarizeVector:
243 ScalarizeVectorResult(N, i);
244 Changed = true;
245 goto NodeDone;
246 case SplitVector:
247 SplitVectorResult(N, i);
248 Changed = true;
249 goto NodeDone;
250 case WidenVector:
251 WidenVectorResult(N, i);
252 Changed = true;
253 goto NodeDone;
257 ScanOperands:
258 // Scan the operand list for the node, handling any nodes with operands that
259 // are illegal.
261 unsigned NumOperands = N->getNumOperands();
262 bool NeedsReanalyzing = false;
263 unsigned i;
264 for (i = 0; i != NumOperands; ++i) {
265 if (IgnoreNodeResults(N->getOperand(i).getNode()))
266 continue;
268 EVT OpVT = N->getOperand(i).getValueType();
269 switch (getTypeAction(OpVT)) {
270 default:
271 assert(false && "Unknown action!");
272 case Legal:
273 continue;
274 // The following calls must either replace all of the node's results
275 // using ReplaceValueWith, and return "false"; or update the node's
276 // operands in place, and return "true".
277 case PromoteInteger:
278 NeedsReanalyzing = PromoteIntegerOperand(N, i);
279 Changed = true;
280 break;
281 case ExpandInteger:
282 NeedsReanalyzing = ExpandIntegerOperand(N, i);
283 Changed = true;
284 break;
285 case SoftenFloat:
286 NeedsReanalyzing = SoftenFloatOperand(N, i);
287 Changed = true;
288 break;
289 case ExpandFloat:
290 NeedsReanalyzing = ExpandFloatOperand(N, i);
291 Changed = true;
292 break;
293 case ScalarizeVector:
294 NeedsReanalyzing = ScalarizeVectorOperand(N, i);
295 Changed = true;
296 break;
297 case SplitVector:
298 NeedsReanalyzing = SplitVectorOperand(N, i);
299 Changed = true;
300 break;
301 case WidenVector:
302 NeedsReanalyzing = WidenVectorOperand(N, i);
303 Changed = true;
304 break;
306 break;
309 // The sub-method updated N in place. Check to see if any operands are new,
310 // and if so, mark them. If the node needs revisiting, don't add all users
311 // to the worklist etc.
312 if (NeedsReanalyzing) {
313 assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
314 N->setNodeId(NewNode);
315 // Recompute the NodeId and correct processed operands, adding the node to
316 // the worklist if ready.
317 SDNode *M = AnalyzeNewNode(N);
318 if (M == N)
319 // The node didn't morph - nothing special to do, it will be revisited.
320 continue;
322 // The node morphed - this is equivalent to legalizing by replacing every
323 // value of N with the corresponding value of M. So do that now. However
324 // there is no need to remember the replacement - morphing will make sure
325 // it is never used non-trivially.
326 assert(N->getNumValues() == M->getNumValues() &&
327 "Node morphing changed the number of results!");
328 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
329 // Replacing the value takes care of remapping the new value. Do the
330 // replacement without recording it in ReplacedValues. This does not
331 // expunge From but that is fine - it is not really a new node.
332 ReplaceValueWithHelper(SDValue(N, i), SDValue(M, i));
333 assert(N->getNodeId() == NewNode && "Unexpected node state!");
334 // The node continues to live on as part of the NewNode fungus that
335 // grows on top of the useful nodes. Nothing more needs to be done
336 // with it - move on to the next node.
337 continue;
340 if (i == NumOperands) {
341 DEBUG(errs() << "Legally typed node: "; N->dump(&DAG); errs() << "\n");
344 NodeDone:
346 // If we reach here, the node was processed, potentially creating new nodes.
347 // Mark it as processed and add its users to the worklist as appropriate.
348 assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
349 N->setNodeId(Processed);
351 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
352 UI != E; ++UI) {
353 SDNode *User = *UI;
354 int NodeId = User->getNodeId();
356 // This node has two options: it can either be a new node or its Node ID
357 // may be a count of the number of operands it has that are not ready.
358 if (NodeId > 0) {
359 User->setNodeId(NodeId-1);
361 // If this was the last use it was waiting on, add it to the ready list.
362 if (NodeId-1 == ReadyToProcess)
363 Worklist.push_back(User);
364 continue;
367 // If this is an unreachable new node, then ignore it. If it ever becomes
368 // reachable by being used by a newly created node then it will be handled
369 // by AnalyzeNewNode.
370 if (NodeId == NewNode)
371 continue;
373 // Otherwise, this node is new: this is the first operand of it that
374 // became ready. Its new NodeId is the number of operands it has minus 1
375 // (as this node is now processed).
376 assert(NodeId == Unanalyzed && "Unknown node ID!");
377 User->setNodeId(User->getNumOperands() - 1);
379 // If the node only has a single operand, it is now ready.
380 if (User->getNumOperands() == 1)
381 Worklist.push_back(User);
385 #ifndef XDEBUG
386 if (EnableExpensiveChecks)
387 #endif
388 PerformExpensiveChecks();
390 // If the root changed (e.g. it was a dead load) update the root.
391 DAG.setRoot(Dummy.getValue());
393 // Remove dead nodes. This is important to do for cleanliness but also before
394 // the checking loop below. Implicit folding by the DAG.getNode operators and
395 // node morphing can cause unreachable nodes to be around with their flags set
396 // to new.
397 DAG.RemoveDeadNodes();
399 // In a debug build, scan all the nodes to make sure we found them all. This
400 // ensures that there are no cycles and that everything got processed.
401 #ifndef NDEBUG
402 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
403 E = DAG.allnodes_end(); I != E; ++I) {
404 bool Failed = false;
406 // Check that all result types are legal.
407 if (!IgnoreNodeResults(I))
408 for (unsigned i = 0, NumVals = I->getNumValues(); i < NumVals; ++i)
409 if (!isTypeLegal(I->getValueType(i))) {
410 errs() << "Result type " << i << " illegal!\n";
411 Failed = true;
414 // Check that all operand types are legal.
415 for (unsigned i = 0, NumOps = I->getNumOperands(); i < NumOps; ++i)
416 if (!IgnoreNodeResults(I->getOperand(i).getNode()) &&
417 !isTypeLegal(I->getOperand(i).getValueType())) {
418 errs() << "Operand type " << i << " illegal!\n";
419 Failed = true;
422 if (I->getNodeId() != Processed) {
423 if (I->getNodeId() == NewNode)
424 errs() << "New node not analyzed?\n";
425 else if (I->getNodeId() == Unanalyzed)
426 errs() << "Unanalyzed node not noticed?\n";
427 else if (I->getNodeId() > 0)
428 errs() << "Operand not processed?\n";
429 else if (I->getNodeId() == ReadyToProcess)
430 errs() << "Not added to worklist?\n";
431 Failed = true;
434 if (Failed) {
435 I->dump(&DAG); errs() << "\n";
436 llvm_unreachable(0);
439 #endif
441 return Changed;
444 /// AnalyzeNewNode - The specified node is the root of a subtree of potentially
445 /// new nodes. Correct any processed operands (this may change the node) and
446 /// calculate the NodeId. If the node itself changes to a processed node, it
447 /// is not remapped - the caller needs to take care of this.
448 /// Returns the potentially changed node.
449 SDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) {
450 // If this was an existing node that is already done, we're done.
451 if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed)
452 return N;
454 // Remove any stale map entries.
455 ExpungeNode(N);
457 // Okay, we know that this node is new. Recursively walk all of its operands
458 // to see if they are new also. The depth of this walk is bounded by the size
459 // of the new tree that was constructed (usually 2-3 nodes), so we don't worry
460 // about revisiting of nodes.
462 // As we walk the operands, keep track of the number of nodes that are
463 // processed. If non-zero, this will become the new nodeid of this node.
464 // Operands may morph when they are analyzed. If so, the node will be
465 // updated after all operands have been analyzed. Since this is rare,
466 // the code tries to minimize overhead in the non-morphing case.
468 SmallVector<SDValue, 8> NewOps;
469 unsigned NumProcessed = 0;
470 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
471 SDValue OrigOp = N->getOperand(i);
472 SDValue Op = OrigOp;
474 AnalyzeNewValue(Op); // Op may morph.
476 if (Op.getNode()->getNodeId() == Processed)
477 ++NumProcessed;
479 if (!NewOps.empty()) {
480 // Some previous operand changed. Add this one to the list.
481 NewOps.push_back(Op);
482 } else if (Op != OrigOp) {
483 // This is the first operand to change - add all operands so far.
484 NewOps.insert(NewOps.end(), N->op_begin(), N->op_begin() + i);
485 NewOps.push_back(Op);
489 // Some operands changed - update the node.
490 if (!NewOps.empty()) {
491 SDNode *M = DAG.UpdateNodeOperands(SDValue(N, 0), &NewOps[0],
492 NewOps.size()).getNode();
493 if (M != N) {
494 // The node morphed into a different node. Normally for this to happen
495 // the original node would have to be marked NewNode. However this can
496 // in theory momentarily not be the case while ReplaceValueWith is doing
497 // its stuff. Mark the original node NewNode to help sanity checking.
498 N->setNodeId(NewNode);
499 if (M->getNodeId() != NewNode && M->getNodeId() != Unanalyzed)
500 // It morphed into a previously analyzed node - nothing more to do.
501 return M;
503 // It morphed into a different new node. Do the equivalent of passing
504 // it to AnalyzeNewNode: expunge it and calculate the NodeId. No need
505 // to remap the operands, since they are the same as the operands we
506 // remapped above.
507 N = M;
508 ExpungeNode(N);
512 // Calculate the NodeId.
513 N->setNodeId(N->getNumOperands() - NumProcessed);
514 if (N->getNodeId() == ReadyToProcess)
515 Worklist.push_back(N);
517 return N;
520 /// AnalyzeNewValue - Call AnalyzeNewNode, updating the node in Val if needed.
521 /// If the node changes to a processed node, then remap it.
522 void DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) {
523 Val.setNode(AnalyzeNewNode(Val.getNode()));
524 if (Val.getNode()->getNodeId() == Processed)
525 // We were passed a processed node, or it morphed into one - remap it.
526 RemapValue(Val);
529 /// ExpungeNode - If N has a bogus mapping in ReplacedValues, eliminate it.
530 /// This can occur when a node is deleted then reallocated as a new node -
531 /// the mapping in ReplacedValues applies to the deleted node, not the new
532 /// one.
533 /// The only map that can have a deleted node as a source is ReplacedValues.
534 /// Other maps can have deleted nodes as targets, but since their looked-up
535 /// values are always immediately remapped using RemapValue, resulting in a
536 /// not-deleted node, this is harmless as long as ReplacedValues/RemapValue
537 /// always performs correct mappings. In order to keep the mapping correct,
538 /// ExpungeNode should be called on any new nodes *before* adding them as
539 /// either source or target to ReplacedValues (which typically means calling
540 /// Expunge when a new node is first seen, since it may no longer be marked
541 /// NewNode by the time it is added to ReplacedValues).
542 void DAGTypeLegalizer::ExpungeNode(SDNode *N) {
543 if (N->getNodeId() != NewNode)
544 return;
546 // If N is not remapped by ReplacedValues then there is nothing to do.
547 unsigned i, e;
548 for (i = 0, e = N->getNumValues(); i != e; ++i)
549 if (ReplacedValues.find(SDValue(N, i)) != ReplacedValues.end())
550 break;
552 if (i == e)
553 return;
555 // Remove N from all maps - this is expensive but rare.
557 for (DenseMap<SDValue, SDValue>::iterator I = PromotedIntegers.begin(),
558 E = PromotedIntegers.end(); I != E; ++I) {
559 assert(I->first.getNode() != N);
560 RemapValue(I->second);
563 for (DenseMap<SDValue, SDValue>::iterator I = SoftenedFloats.begin(),
564 E = SoftenedFloats.end(); I != E; ++I) {
565 assert(I->first.getNode() != N);
566 RemapValue(I->second);
569 for (DenseMap<SDValue, SDValue>::iterator I = ScalarizedVectors.begin(),
570 E = ScalarizedVectors.end(); I != E; ++I) {
571 assert(I->first.getNode() != N);
572 RemapValue(I->second);
575 for (DenseMap<SDValue, SDValue>::iterator I = WidenedVectors.begin(),
576 E = WidenedVectors.end(); I != E; ++I) {
577 assert(I->first.getNode() != N);
578 RemapValue(I->second);
581 for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
582 I = ExpandedIntegers.begin(), E = ExpandedIntegers.end(); I != E; ++I){
583 assert(I->first.getNode() != N);
584 RemapValue(I->second.first);
585 RemapValue(I->second.second);
588 for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
589 I = ExpandedFloats.begin(), E = ExpandedFloats.end(); I != E; ++I) {
590 assert(I->first.getNode() != N);
591 RemapValue(I->second.first);
592 RemapValue(I->second.second);
595 for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
596 I = SplitVectors.begin(), E = SplitVectors.end(); I != E; ++I) {
597 assert(I->first.getNode() != N);
598 RemapValue(I->second.first);
599 RemapValue(I->second.second);
602 for (DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.begin(),
603 E = ReplacedValues.end(); I != E; ++I)
604 RemapValue(I->second);
606 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
607 ReplacedValues.erase(SDValue(N, i));
610 /// RemapValue - If the specified value was already legalized to another value,
611 /// replace it by that value.
612 void DAGTypeLegalizer::RemapValue(SDValue &N) {
613 DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(N);
614 if (I != ReplacedValues.end()) {
615 // Use path compression to speed up future lookups if values get multiply
616 // replaced with other values.
617 RemapValue(I->second);
618 N = I->second;
619 assert(N.getNode()->getNodeId() != NewNode && "Mapped to new node!");
623 namespace {
624 /// NodeUpdateListener - This class is a DAGUpdateListener that listens for
625 /// updates to nodes and recomputes their ready state.
626 class VISIBILITY_HIDDEN NodeUpdateListener :
627 public SelectionDAG::DAGUpdateListener {
628 DAGTypeLegalizer &DTL;
629 SmallSetVector<SDNode*, 16> &NodesToAnalyze;
630 public:
631 explicit NodeUpdateListener(DAGTypeLegalizer &dtl,
632 SmallSetVector<SDNode*, 16> &nta)
633 : DTL(dtl), NodesToAnalyze(nta) {}
635 virtual void NodeDeleted(SDNode *N, SDNode *E) {
636 assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess &&
637 N->getNodeId() != DAGTypeLegalizer::Processed &&
638 "Invalid node ID for RAUW deletion!");
639 // It is possible, though rare, for the deleted node N to occur as a
640 // target in a map, so note the replacement N -> E in ReplacedValues.
641 assert(E && "Node not replaced?");
642 DTL.NoteDeletion(N, E);
644 // In theory the deleted node could also have been scheduled for analysis.
645 // So remove it from the set of nodes which will be analyzed.
646 NodesToAnalyze.remove(N);
648 // In general nothing needs to be done for E, since it didn't change but
649 // only gained new uses. However N -> E was just added to ReplacedValues,
650 // and the result of a ReplacedValues mapping is not allowed to be marked
651 // NewNode. So if E is marked NewNode, then it needs to be analyzed.
652 if (E->getNodeId() == DAGTypeLegalizer::NewNode)
653 NodesToAnalyze.insert(E);
656 virtual void NodeUpdated(SDNode *N) {
657 // Node updates can mean pretty much anything. It is possible that an
658 // operand was set to something already processed (f.e.) in which case
659 // this node could become ready. Recompute its flags.
660 assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess &&
661 N->getNodeId() != DAGTypeLegalizer::Processed &&
662 "Invalid node ID for RAUW deletion!");
663 N->setNodeId(DAGTypeLegalizer::NewNode);
664 NodesToAnalyze.insert(N);
670 /// ReplaceValueWithHelper - Internal helper for ReplaceValueWith. Updates the
671 /// DAG causing any uses of From to use To instead, but without expunging From
672 /// or recording the replacement in ReplacedValues. Do not call directly unless
673 /// you really know what you are doing!
674 void DAGTypeLegalizer::ReplaceValueWithHelper(SDValue From, SDValue To) {
675 assert(From.getNode() != To.getNode() && "Potential legalization loop!");
677 // If expansion produced new nodes, make sure they are properly marked.
678 AnalyzeNewValue(To); // Expunges To.
680 // Anything that used the old node should now use the new one. Note that this
681 // can potentially cause recursive merging.
682 SmallSetVector<SDNode*, 16> NodesToAnalyze;
683 NodeUpdateListener NUL(*this, NodesToAnalyze);
684 DAG.ReplaceAllUsesOfValueWith(From, To, &NUL);
686 // Process the list of nodes that need to be reanalyzed.
687 while (!NodesToAnalyze.empty()) {
688 SDNode *N = NodesToAnalyze.back();
689 NodesToAnalyze.pop_back();
690 if (N->getNodeId() != DAGTypeLegalizer::NewNode)
691 // The node was analyzed while reanalyzing an earlier node - it is safe to
692 // skip. Note that this is not a morphing node - otherwise it would still
693 // be marked NewNode.
694 continue;
696 // Analyze the node's operands and recalculate the node ID.
697 SDNode *M = AnalyzeNewNode(N);
698 if (M != N) {
699 // The node morphed into a different node. Make everyone use the new node
700 // instead.
701 assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!");
702 assert(N->getNumValues() == M->getNumValues() &&
703 "Node morphing changed the number of results!");
704 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
705 SDValue OldVal(N, i);
706 SDValue NewVal(M, i);
707 if (M->getNodeId() == Processed)
708 RemapValue(NewVal);
709 DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal, &NUL);
711 // The original node continues to exist in the DAG, marked NewNode.
716 /// ReplaceValueWith - The specified value was legalized to the specified other
717 /// value. Update the DAG and NodeIds replacing any uses of From to use To
718 /// instead.
719 void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) {
720 assert(From.getNode()->getNodeId() == ReadyToProcess &&
721 "Only the node being processed may be remapped!");
723 // If expansion produced new nodes, make sure they are properly marked.
724 ExpungeNode(From.getNode());
725 AnalyzeNewValue(To); // Expunges To.
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;
731 // Do the replacement.
732 ReplaceValueWithHelper(From, To);
735 void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) {
736 assert(Result.getValueType() == TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
737 "Invalid type for promoted integer");
738 AnalyzeNewValue(Result);
740 SDValue &OpEntry = PromotedIntegers[Op];
741 assert(OpEntry.getNode() == 0 && "Node is already promoted!");
742 OpEntry = Result;
745 void DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) {
746 assert(Result.getValueType() == TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
747 "Invalid type for softened float");
748 AnalyzeNewValue(Result);
750 SDValue &OpEntry = SoftenedFloats[Op];
751 assert(OpEntry.getNode() == 0 && "Node is already converted to integer!");
752 OpEntry = Result;
755 void DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) {
756 assert(Result.getValueType() == Op.getValueType().getVectorElementType() &&
757 "Invalid type for scalarized vector");
758 AnalyzeNewValue(Result);
760 SDValue &OpEntry = ScalarizedVectors[Op];
761 assert(OpEntry.getNode() == 0 && "Node is already scalarized!");
762 OpEntry = Result;
765 void DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo,
766 SDValue &Hi) {
767 std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op];
768 RemapValue(Entry.first);
769 RemapValue(Entry.second);
770 assert(Entry.first.getNode() && "Operand isn't expanded");
771 Lo = Entry.first;
772 Hi = Entry.second;
775 void DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo,
776 SDValue Hi) {
777 assert(Lo.getValueType() == TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
778 Hi.getValueType() == Lo.getValueType() &&
779 "Invalid type for expanded integer");
780 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
781 AnalyzeNewValue(Lo);
782 AnalyzeNewValue(Hi);
784 // Remember that this is the result of the node.
785 std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op];
786 assert(Entry.first.getNode() == 0 && "Node already expanded");
787 Entry.first = Lo;
788 Entry.second = Hi;
791 void DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo,
792 SDValue &Hi) {
793 std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op];
794 RemapValue(Entry.first);
795 RemapValue(Entry.second);
796 assert(Entry.first.getNode() && "Operand isn't expanded");
797 Lo = Entry.first;
798 Hi = Entry.second;
801 void DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo,
802 SDValue Hi) {
803 assert(Lo.getValueType() == TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
804 Hi.getValueType() == Lo.getValueType() &&
805 "Invalid type for expanded float");
806 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
807 AnalyzeNewValue(Lo);
808 AnalyzeNewValue(Hi);
810 // Remember that this is the result of the node.
811 std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op];
812 assert(Entry.first.getNode() == 0 && "Node already expanded");
813 Entry.first = Lo;
814 Entry.second = Hi;
817 void DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo,
818 SDValue &Hi) {
819 std::pair<SDValue, SDValue> &Entry = SplitVectors[Op];
820 RemapValue(Entry.first);
821 RemapValue(Entry.second);
822 assert(Entry.first.getNode() && "Operand isn't split");
823 Lo = Entry.first;
824 Hi = Entry.second;
827 void DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo,
828 SDValue Hi) {
829 assert(Lo.getValueType().getVectorElementType() ==
830 Op.getValueType().getVectorElementType() &&
831 2*Lo.getValueType().getVectorNumElements() ==
832 Op.getValueType().getVectorNumElements() &&
833 Hi.getValueType() == Lo.getValueType() &&
834 "Invalid type for split vector");
835 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
836 AnalyzeNewValue(Lo);
837 AnalyzeNewValue(Hi);
839 // Remember that this is the result of the node.
840 std::pair<SDValue, SDValue> &Entry = SplitVectors[Op];
841 assert(Entry.first.getNode() == 0 && "Node already split");
842 Entry.first = Lo;
843 Entry.second = Hi;
846 void DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) {
847 assert(Result.getValueType() == TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
848 "Invalid type for widened vector");
849 AnalyzeNewValue(Result);
851 SDValue &OpEntry = WidenedVectors[Op];
852 assert(OpEntry.getNode() == 0 && "Node already widened!");
853 OpEntry = Result;
857 //===----------------------------------------------------------------------===//
858 // Utilities.
859 //===----------------------------------------------------------------------===//
861 /// BitConvertToInteger - Convert to an integer of the same size.
862 SDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) {
863 unsigned BitWidth = Op.getValueType().getSizeInBits();
864 return DAG.getNode(ISD::BIT_CONVERT, Op.getDebugLoc(),
865 EVT::getIntegerVT(*DAG.getContext(), BitWidth), Op);
868 /// BitConvertVectorToIntegerVector - Convert to a vector of integers of the
869 /// same size.
870 SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(SDValue Op) {
871 assert(Op.getValueType().isVector() && "Only applies to vectors!");
872 unsigned EltWidth = Op.getValueType().getVectorElementType().getSizeInBits();
873 EVT EltNVT = EVT::getIntegerVT(*DAG.getContext(), EltWidth);
874 unsigned NumElts = Op.getValueType().getVectorNumElements();
875 return DAG.getNode(ISD::BIT_CONVERT, Op.getDebugLoc(),
876 EVT::getVectorVT(*DAG.getContext(), EltNVT, NumElts), Op);
879 SDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op,
880 EVT DestVT) {
881 DebugLoc dl = Op.getDebugLoc();
882 // Create the stack frame object. Make sure it is aligned for both
883 // the source and destination types.
884 SDValue StackPtr = DAG.CreateStackTemporary(Op.getValueType(), DestVT);
885 // Emit a store to the stack slot.
886 SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, NULL, 0);
887 // Result is a load from the stack slot.
888 return DAG.getLoad(DestVT, dl, Store, StackPtr, NULL, 0);
891 /// CustomLowerNode - Replace the node's results with custom code provided
892 /// by the target and return "true", or do nothing and return "false".
893 /// The last parameter is FALSE if we are dealing with a node with legal
894 /// result types and illegal operand. The second parameter denotes the type of
895 /// illegal OperandNo in that case.
896 /// The last parameter being TRUE means we are dealing with a
897 /// node with illegal result types. The second parameter denotes the type of
898 /// illegal ResNo in that case.
899 bool DAGTypeLegalizer::CustomLowerNode(SDNode *N, EVT VT, bool LegalizeResult) {
900 // See if the target wants to custom lower this node.
901 if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom)
902 return false;
904 SmallVector<SDValue, 8> Results;
905 if (LegalizeResult)
906 TLI.ReplaceNodeResults(N, Results, DAG);
907 else
908 TLI.LowerOperationWrapper(N, Results, DAG);
910 if (Results.empty())
911 // The target didn't want to custom lower it after all.
912 return false;
914 // Make everything that once used N's values now use those in Results instead.
915 assert(Results.size() == N->getNumValues() &&
916 "Custom lowering returned the wrong number of results!");
917 for (unsigned i = 0, e = Results.size(); i != e; ++i)
918 ReplaceValueWith(SDValue(N, i), Results[i]);
919 return true;
922 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
923 /// which is split into two not necessarily identical pieces.
924 void DAGTypeLegalizer::GetSplitDestVTs(EVT InVT, EVT &LoVT, EVT &HiVT) {
925 // Currently all types are split in half.
926 if (!InVT.isVector()) {
927 LoVT = HiVT = TLI.getTypeToTransformTo(*DAG.getContext(), InVT);
928 } else {
929 unsigned NumElements = InVT.getVectorNumElements();
930 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
931 LoVT = HiVT = EVT::getVectorVT(*DAG.getContext(), InVT.getVectorElementType(), NumElements/2);
935 /// GetPairElements - Use ISD::EXTRACT_ELEMENT nodes to extract the low and
936 /// high parts of the given value.
937 void DAGTypeLegalizer::GetPairElements(SDValue Pair,
938 SDValue &Lo, SDValue &Hi) {
939 DebugLoc dl = Pair.getDebugLoc();
940 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.getValueType());
941 Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair,
942 DAG.getIntPtrConstant(0));
943 Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair,
944 DAG.getIntPtrConstant(1));
947 SDValue DAGTypeLegalizer::GetVectorElementPointer(SDValue VecPtr, EVT EltVT,
948 SDValue Index) {
949 DebugLoc dl = Index.getDebugLoc();
950 // Make sure the index type is big enough to compute in.
951 if (Index.getValueType().bitsGT(TLI.getPointerTy()))
952 Index = DAG.getNode(ISD::TRUNCATE, dl, TLI.getPointerTy(), Index);
953 else
954 Index = DAG.getNode(ISD::ZERO_EXTEND, dl, TLI.getPointerTy(), Index);
956 // Calculate the element offset and add it to the pointer.
957 unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size.
959 Index = DAG.getNode(ISD::MUL, dl, Index.getValueType(), Index,
960 DAG.getConstant(EltSize, Index.getValueType()));
961 return DAG.getNode(ISD::ADD, dl, Index.getValueType(), Index, VecPtr);
964 /// JoinIntegers - Build an integer with low bits Lo and high bits Hi.
965 SDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) {
966 // Arbitrarily use dlHi for result DebugLoc
967 DebugLoc dlHi = Hi.getDebugLoc();
968 DebugLoc dlLo = Lo.getDebugLoc();
969 EVT LVT = Lo.getValueType();
970 EVT HVT = Hi.getValueType();
971 EVT NVT = EVT::getIntegerVT(*DAG.getContext(), LVT.getSizeInBits() + HVT.getSizeInBits());
973 Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo);
974 Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi);
975 Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi,
976 DAG.getConstant(LVT.getSizeInBits(), TLI.getPointerTy()));
977 return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi);
980 /// LibCallify - Convert the node into a libcall with the same prototype.
981 SDValue DAGTypeLegalizer::LibCallify(RTLIB::Libcall LC, SDNode *N,
982 bool isSigned) {
983 unsigned NumOps = N->getNumOperands();
984 DebugLoc dl = N->getDebugLoc();
985 if (NumOps == 0) {
986 return MakeLibCall(LC, N->getValueType(0), 0, 0, isSigned, dl);
987 } else if (NumOps == 1) {
988 SDValue Op = N->getOperand(0);
989 return MakeLibCall(LC, N->getValueType(0), &Op, 1, isSigned, dl);
990 } else if (NumOps == 2) {
991 SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
992 return MakeLibCall(LC, N->getValueType(0), Ops, 2, isSigned, dl);
994 SmallVector<SDValue, 8> Ops(NumOps);
995 for (unsigned i = 0; i < NumOps; ++i)
996 Ops[i] = N->getOperand(i);
998 return MakeLibCall(LC, N->getValueType(0), &Ops[0], NumOps, isSigned, dl);
1001 /// MakeLibCall - Generate a libcall taking the given operands as arguments and
1002 /// returning a result of type RetVT.
1003 SDValue DAGTypeLegalizer::MakeLibCall(RTLIB::Libcall LC, EVT RetVT,
1004 const SDValue *Ops, unsigned NumOps,
1005 bool isSigned, DebugLoc dl) {
1006 TargetLowering::ArgListTy Args;
1007 Args.reserve(NumOps);
1009 TargetLowering::ArgListEntry Entry;
1010 for (unsigned i = 0; i != NumOps; ++i) {
1011 Entry.Node = Ops[i];
1012 Entry.Ty = Entry.Node.getValueType().getTypeForEVT(*DAG.getContext());
1013 Entry.isSExt = isSigned;
1014 Entry.isZExt = !isSigned;
1015 Args.push_back(Entry);
1017 SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
1018 TLI.getPointerTy());
1020 const Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
1021 std::pair<SDValue,SDValue> CallInfo =
1022 TLI.LowerCallTo(DAG.getEntryNode(), RetTy, isSigned, !isSigned, false,
1023 false, 0, TLI.getLibcallCallingConv(LC), false,
1024 /*isReturnValueUsed=*/true,
1025 Callee, Args, DAG, dl);
1026 return CallInfo.first;
1029 /// PromoteTargetBoolean - Promote the given target boolean to a target boolean
1030 /// of the given type. A target boolean is an integer value, not necessarily of
1031 /// type i1, the bits of which conform to getBooleanContents.
1032 SDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, EVT VT) {
1033 DebugLoc dl = Bool.getDebugLoc();
1034 ISD::NodeType ExtendCode;
1035 switch (TLI.getBooleanContents()) {
1036 default:
1037 assert(false && "Unknown BooleanContent!");
1038 case TargetLowering::UndefinedBooleanContent:
1039 // Extend to VT by adding rubbish bits.
1040 ExtendCode = ISD::ANY_EXTEND;
1041 break;
1042 case TargetLowering::ZeroOrOneBooleanContent:
1043 // Extend to VT by adding zero bits.
1044 ExtendCode = ISD::ZERO_EXTEND;
1045 break;
1046 case TargetLowering::ZeroOrNegativeOneBooleanContent: {
1047 // Extend to VT by copying the sign bit.
1048 ExtendCode = ISD::SIGN_EXTEND;
1049 break;
1052 return DAG.getNode(ExtendCode, dl, VT, Bool);
1055 /// SplitInteger - Return the lower LoVT bits of Op in Lo and the upper HiVT
1056 /// bits in Hi.
1057 void DAGTypeLegalizer::SplitInteger(SDValue Op,
1058 EVT LoVT, EVT HiVT,
1059 SDValue &Lo, SDValue &Hi) {
1060 DebugLoc dl = Op.getDebugLoc();
1061 assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() ==
1062 Op.getValueType().getSizeInBits() && "Invalid integer splitting!");
1063 Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op);
1064 Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op,
1065 DAG.getConstant(LoVT.getSizeInBits(), TLI.getPointerTy()));
1066 Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi);
1069 /// SplitInteger - Return the lower and upper halves of Op's bits in a value
1070 /// type half the size of Op's.
1071 void DAGTypeLegalizer::SplitInteger(SDValue Op,
1072 SDValue &Lo, SDValue &Hi) {
1073 EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), Op.getValueType().getSizeInBits()/2);
1074 SplitInteger(Op, HalfVT, HalfVT, Lo, Hi);
1078 //===----------------------------------------------------------------------===//
1079 // Entry Point
1080 //===----------------------------------------------------------------------===//
1082 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
1083 /// only uses types natively supported by the target. Returns "true" if it made
1084 /// any changes.
1086 /// Note that this is an involved process that may invalidate pointers into
1087 /// the graph.
1088 bool SelectionDAG::LegalizeTypes() {
1089 return DAGTypeLegalizer(*this).run();