LLVM API Documentation

LegalizeTypes.cpp

Go to the documentation of this file.
00001 //===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the SelectionDAG::LegalizeTypes method.  It transforms
00011 // an arbitrary well-formed SelectionDAG to only consist of legal types.  This
00012 // is common code shared among the LegalizeTypes*.cpp files.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "LegalizeTypes.h"
00017 #include "llvm/CallingConv.h"
00018 #include "llvm/ADT/SetVector.h"
00019 #include "llvm/Support/CommandLine.h"
00020 #include "llvm/Support/ErrorHandling.h"
00021 #include "llvm/Target/TargetData.h"
00022 using namespace llvm;
00023 
00024 static cl::opt<bool>
00025 EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden);
00026 
00027 /// PerformExpensiveChecks - Do extensive, expensive, sanity checking.
00028 void DAGTypeLegalizer::PerformExpensiveChecks() {
00029   // If a node is not processed, then none of its values should be mapped by any
00030   // of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues.
00031 
00032   // If a node is processed, then each value with an illegal type must be mapped
00033   // by exactly one of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues.
00034   // Values with a legal type may be mapped by ReplacedValues, but not by any of
00035   // the other maps.
00036 
00037   // Note that these invariants may not hold momentarily when processing a node:
00038   // the node being processed may be put in a map before being marked Processed.
00039 
00040   // Note that it is possible to have nodes marked NewNode in the DAG.  This can
00041   // occur in two ways.  Firstly, a node may be created during legalization but
00042   // never passed to the legalization core.  This is usually due to the implicit
00043   // folding that occurs when using the DAG.getNode operators.  Secondly, a new
00044   // node may be passed to the legalization core, but when analyzed may morph
00045   // into a different node, leaving the original node as a NewNode in the DAG.
00046   // A node may morph if one of its operands changes during analysis.  Whether
00047   // it actually morphs or not depends on whether, after updating its operands,
00048   // it is equivalent to an existing node: if so, it morphs into that existing
00049   // node (CSE).  An operand can change during analysis if the operand is a new
00050   // node that morphs, or it is a processed value that was mapped to some other
00051   // value (as recorded in ReplacedValues) in which case the operand is turned
00052   // into that other value.  If a node morphs then the node it morphed into will
00053   // be used instead of it for legalization, however the original node continues
00054   // to live on in the DAG.
00055   // The conclusion is that though there may be nodes marked NewNode in the DAG,
00056   // all uses of such nodes are also marked NewNode: the result is a fungus of
00057   // NewNodes growing on top of the useful nodes, and perhaps using them, but
00058   // not used by them.
00059 
00060   // If a value is mapped by ReplacedValues, then it must have no uses, except
00061   // by nodes marked NewNode (see above).
00062 
00063   // The final node obtained by mapping by ReplacedValues is not marked NewNode.
00064   // Note that ReplacedValues should be applied iteratively.
00065 
00066   // Note that the ReplacedValues map may also map deleted nodes.  By iterating
00067   // over the DAG we only consider non-deleted nodes.
00068   SmallVector<SDNode*, 16> NewNodes;
00069   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
00070        E = DAG.allnodes_end(); I != E; ++I) {
00071     // Remember nodes marked NewNode - they are subject to extra checking below.
00072     if (I->getNodeId() == NewNode)
00073       NewNodes.push_back(I);
00074 
00075     for (unsigned i = 0, e = I->getNumValues(); i != e; ++i) {
00076       SDValue Res(I, i);
00077       bool Failed = false;
00078 
00079       unsigned Mapped = 0;
00080       if (ReplacedValues.find(Res) != ReplacedValues.end()) {
00081         Mapped |= 1;
00082         // Check that remapped values are only used by nodes marked NewNode.
00083         for (SDNode::use_iterator UI = I->use_begin(), UE = I->use_end();
00084              UI != UE; ++UI)
00085           if (UI.getUse().getResNo() == i)
00086             assert(UI->getNodeId() == NewNode &&
00087                    "Remapped value has non-trivial use!");
00088 
00089         // Check that the final result of applying ReplacedValues is not
00090         // marked NewNode.
00091         SDValue NewVal = ReplacedValues[Res];
00092         DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(NewVal);
00093         while (I != ReplacedValues.end()) {
00094           NewVal = I->second;
00095           I = ReplacedValues.find(NewVal);
00096         }
00097         assert(NewVal.getNode()->getNodeId() != NewNode &&
00098                "ReplacedValues maps to a new node!");
00099       }
00100       if (PromotedIntegers.find(Res) != PromotedIntegers.end())
00101         Mapped |= 2;
00102       if (SoftenedFloats.find(Res) != SoftenedFloats.end())
00103         Mapped |= 4;
00104       if (ScalarizedVectors.find(Res) != ScalarizedVectors.end())
00105         Mapped |= 8;
00106       if (ExpandedIntegers.find(Res) != ExpandedIntegers.end())
00107         Mapped |= 16;
00108       if (ExpandedFloats.find(Res) != ExpandedFloats.end())
00109         Mapped |= 32;
00110       if (SplitVectors.find(Res) != SplitVectors.end())
00111         Mapped |= 64;
00112       if (WidenedVectors.find(Res) != WidenedVectors.end())
00113         Mapped |= 128;
00114 
00115       if (I->getNodeId() != Processed) {
00116         if (Mapped != 0) {
00117           cerr << "Unprocessed value in a map!";
00118           Failed = true;
00119         }
00120       } else if (isTypeLegal(Res.getValueType()) || IgnoreNodeResults(I)) {
00121         if (Mapped > 1) {
00122           cerr << "Value with legal type was transformed!";
00123           Failed = true;
00124         }
00125       } else {
00126         if (Mapped == 0) {
00127           cerr << "Processed value not in any map!";
00128           Failed = true;
00129         } else if (Mapped & (Mapped - 1)) {
00130           cerr << "Value in multiple maps!";
00131           Failed = true;
00132         }
00133       }
00134 
00135       if (Failed) {
00136         if (Mapped & 1)
00137           cerr << " ReplacedValues";
00138         if (Mapped & 2)
00139           cerr << " PromotedIntegers";
00140         if (Mapped & 4)
00141           cerr << " SoftenedFloats";
00142         if (Mapped & 8)
00143           cerr << " ScalarizedVectors";
00144         if (Mapped & 16)
00145           cerr << " ExpandedIntegers";
00146         if (Mapped & 32)
00147           cerr << " ExpandedFloats";
00148         if (Mapped & 64)
00149           cerr << " SplitVectors";
00150         if (Mapped & 128)
00151           cerr << " WidenedVectors";
00152         cerr << "\n";
00153         llvm_unreachable(0);
00154       }
00155     }
00156   }
00157 
00158   // Checked that NewNodes are only used by other NewNodes.
00159   for (unsigned i = 0, e = NewNodes.size(); i != e; ++i) {
00160     SDNode *N = NewNodes[i];
00161     for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
00162          UI != UE; ++UI)
00163       assert(UI->getNodeId() == NewNode && "NewNode used by non-NewNode!");
00164   }
00165 }
00166 
00167 /// run - This is the main entry point for the type legalizer.  This does a
00168 /// top-down traversal of the dag, legalizing types as it goes.  Returns "true"
00169 /// if it made any changes.
00170 bool DAGTypeLegalizer::run() {
00171   bool Changed = false;
00172 
00173   // Create a dummy node (which is not added to allnodes), that adds a reference
00174   // to the root node, preventing it from being deleted, and tracking any
00175   // changes of the root.
00176   HandleSDNode Dummy(DAG.getRoot());
00177   Dummy.setNodeId(Unanalyzed);
00178 
00179   // The root of the dag may dangle to deleted nodes until the type legalizer is
00180   // done.  Set it to null to avoid confusion.
00181   DAG.setRoot(SDValue());
00182 
00183   // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess'
00184   // (and remembering them) if they are leaves and assigning 'Unanalyzed' if
00185   // non-leaves.
00186   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
00187        E = DAG.allnodes_end(); I != E; ++I) {
00188     if (I->getNumOperands() == 0) {
00189       I->setNodeId(ReadyToProcess);
00190       Worklist.push_back(I);
00191     } else {
00192       I->setNodeId(Unanalyzed);
00193     }
00194   }
00195 
00196   // Now that we have a set of nodes to process, handle them all.
00197   while (!Worklist.empty()) {
00198 #ifndef XDEBUG
00199     if (EnableExpensiveChecks)
00200 #endif
00201       PerformExpensiveChecks();
00202 
00203     SDNode *N = Worklist.back();
00204     Worklist.pop_back();
00205     assert(N->getNodeId() == ReadyToProcess &&
00206            "Node should be ready if on worklist!");
00207 
00208     if (IgnoreNodeResults(N))
00209       goto ScanOperands;
00210 
00211     // Scan the values produced by the node, checking to see if any result
00212     // types are illegal.
00213     for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) {
00214       EVT ResultVT = N->getValueType(i);
00215       switch (getTypeAction(ResultVT)) {
00216       default:
00217         assert(false && "Unknown action!");
00218       case Legal:
00219         break;
00220       // The following calls must take care of *all* of the node's results,
00221       // not just the illegal result they were passed (this includes results
00222       // with a legal type).  Results can be remapped using ReplaceValueWith,
00223       // or their promoted/expanded/etc values registered in PromotedIntegers,
00224       // ExpandedIntegers etc.
00225       case PromoteInteger:
00226         PromoteIntegerResult(N, i);
00227         Changed = true;
00228         goto NodeDone;
00229       case ExpandInteger:
00230         ExpandIntegerResult(N, i);
00231         Changed = true;
00232         goto NodeDone;
00233       case SoftenFloat:
00234         SoftenFloatResult(N, i);
00235         Changed = true;
00236         goto NodeDone;
00237       case ExpandFloat:
00238         ExpandFloatResult(N, i);
00239         Changed = true;
00240         goto NodeDone;
00241       case ScalarizeVector:
00242         ScalarizeVectorResult(N, i);
00243         Changed = true;
00244         goto NodeDone;
00245       case SplitVector:
00246         SplitVectorResult(N, i);
00247         Changed = true;
00248         goto NodeDone;
00249       case WidenVector:
00250         WidenVectorResult(N, i);
00251         Changed = true;
00252         goto NodeDone;
00253       }
00254     }
00255 
00256 ScanOperands:
00257     // Scan the operand list for the node, handling any nodes with operands that
00258     // are illegal.
00259     {
00260     unsigned NumOperands = N->getNumOperands();
00261     bool NeedsReanalyzing = false;
00262     unsigned i;
00263     for (i = 0; i != NumOperands; ++i) {
00264       if (IgnoreNodeResults(N->getOperand(i).getNode()))
00265         continue;
00266 
00267       EVT OpVT = N->getOperand(i).getValueType();
00268       switch (getTypeAction(OpVT)) {
00269       default:
00270         assert(false && "Unknown action!");
00271       case Legal:
00272         continue;
00273       // The following calls must either replace all of the node's results
00274       // using ReplaceValueWith, and return "false"; or update the node's
00275       // operands in place, and return "true".
00276       case PromoteInteger:
00277         NeedsReanalyzing = PromoteIntegerOperand(N, i);
00278         Changed = true;
00279         break;
00280       case ExpandInteger:
00281         NeedsReanalyzing = ExpandIntegerOperand(N, i);
00282         Changed = true;
00283         break;
00284       case SoftenFloat:
00285         NeedsReanalyzing = SoftenFloatOperand(N, i);
00286         Changed = true;
00287         break;
00288       case ExpandFloat:
00289         NeedsReanalyzing = ExpandFloatOperand(N, i);
00290         Changed = true;
00291         break;
00292       case ScalarizeVector:
00293         NeedsReanalyzing = ScalarizeVectorOperand(N, i);
00294         Changed = true;
00295         break;
00296       case SplitVector:
00297         NeedsReanalyzing = SplitVectorOperand(N, i);
00298         Changed = true;
00299         break;
00300       case WidenVector:
00301         NeedsReanalyzing = WidenVectorOperand(N, i);
00302         Changed = true;
00303         break;
00304       }
00305       break;
00306     }
00307 
00308     // The sub-method updated N in place.  Check to see if any operands are new,
00309     // and if so, mark them.  If the node needs revisiting, don't add all users
00310     // to the worklist etc.
00311     if (NeedsReanalyzing) {
00312       assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
00313       N->setNodeId(NewNode);
00314       // Recompute the NodeId and correct processed operands, adding the node to
00315       // the worklist if ready.
00316       SDNode *M = AnalyzeNewNode(N);
00317       if (M == N)
00318         // The node didn't morph - nothing special to do, it will be revisited.
00319         continue;
00320 
00321       // The node morphed - this is equivalent to legalizing by replacing every
00322       // value of N with the corresponding value of M.  So do that now.  However
00323       // there is no need to remember the replacement - morphing will make sure
00324       // it is never used non-trivially.
00325       assert(N->getNumValues() == M->getNumValues() &&
00326              "Node morphing changed the number of results!");
00327       for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
00328         // Replacing the value takes care of remapping the new value.  Do the
00329         // replacement without recording it in ReplacedValues.  This does not
00330         // expunge From but that is fine - it is not really a new node.
00331         ReplaceValueWithHelper(SDValue(N, i), SDValue(M, i));
00332       assert(N->getNodeId() == NewNode && "Unexpected node state!");
00333       // The node continues to live on as part of the NewNode fungus that
00334       // grows on top of the useful nodes.  Nothing more needs to be done
00335       // with it - move on to the next node.
00336       continue;
00337     }
00338 
00339     if (i == NumOperands) {
00340       DEBUG(cerr << "Legally typed node: "; N->dump(&DAG); cerr << "\n");
00341     }
00342     }
00343 NodeDone:
00344 
00345     // If we reach here, the node was processed, potentially creating new nodes.
00346     // Mark it as processed and add its users to the worklist as appropriate.
00347     assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
00348     N->setNodeId(Processed);
00349 
00350     for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
00351          UI != E; ++UI) {
00352       SDNode *User = *UI;
00353       int NodeId = User->getNodeId();
00354 
00355       // This node has two options: it can either be a new node or its Node ID
00356       // may be a count of the number of operands it has that are not ready.
00357       if (NodeId > 0) {
00358         User->setNodeId(NodeId-1);
00359 
00360         // If this was the last use it was waiting on, add it to the ready list.
00361         if (NodeId-1 == ReadyToProcess)
00362           Worklist.push_back(User);
00363         continue;
00364       }
00365 
00366       // If this is an unreachable new node, then ignore it.  If it ever becomes
00367       // reachable by being used by a newly created node then it will be handled
00368       // by AnalyzeNewNode.
00369       if (NodeId == NewNode)
00370         continue;
00371 
00372       // Otherwise, this node is new: this is the first operand of it that
00373       // became ready.  Its new NodeId is the number of operands it has minus 1
00374       // (as this node is now processed).
00375       assert(NodeId == Unanalyzed && "Unknown node ID!");
00376       User->setNodeId(User->getNumOperands() - 1);
00377 
00378       // If the node only has a single operand, it is now ready.
00379       if (User->getNumOperands() == 1)
00380         Worklist.push_back(User);
00381     }
00382   }
00383 
00384 #ifndef XDEBUG
00385   if (EnableExpensiveChecks)
00386 #endif
00387     PerformExpensiveChecks();
00388 
00389   // If the root changed (e.g. it was a dead load) update the root.
00390   DAG.setRoot(Dummy.getValue());
00391 
00392   // Remove dead nodes.  This is important to do for cleanliness but also before
00393   // the checking loop below.  Implicit folding by the DAG.getNode operators and
00394   // node morphing can cause unreachable nodes to be around with their flags set
00395   // to new.
00396   DAG.RemoveDeadNodes();
00397 
00398   // In a debug build, scan all the nodes to make sure we found them all.  This
00399   // ensures that there are no cycles and that everything got processed.
00400 #ifndef NDEBUG
00401   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
00402        E = DAG.allnodes_end(); I != E; ++I) {
00403     bool Failed = false;
00404 
00405     // Check that all result types are legal.
00406     if (!IgnoreNodeResults(I))
00407       for (unsigned i = 0, NumVals = I->getNumValues(); i < NumVals; ++i)
00408         if (!isTypeLegal(I->getValueType(i))) {
00409           cerr << "Result type " << i << " illegal!\n";
00410           Failed = true;
00411         }
00412 
00413     // Check that all operand types are legal.
00414     for (unsigned i = 0, NumOps = I->getNumOperands(); i < NumOps; ++i)
00415       if (!IgnoreNodeResults(I->getOperand(i).getNode()) &&
00416           !isTypeLegal(I->getOperand(i).getValueType())) {
00417         cerr << "Operand type " << i << " illegal!\n";
00418         Failed = true;
00419       }
00420 
00421     if (I->getNodeId() != Processed) {
00422        if (I->getNodeId() == NewNode)
00423          cerr << "New node not analyzed?\n";
00424        else if (I->getNodeId() == Unanalyzed)
00425          cerr << "Unanalyzed node not noticed?\n";
00426        else if (I->getNodeId() > 0)
00427          cerr << "Operand not processed?\n";
00428        else if (I->getNodeId() == ReadyToProcess)
00429          cerr << "Not added to worklist?\n";
00430        Failed = true;
00431     }
00432 
00433     if (Failed) {
00434       I->dump(&DAG); cerr << "\n";
00435       llvm_unreachable(0);
00436     }
00437   }
00438 #endif
00439 
00440   return Changed;
00441 }
00442 
00443 /// AnalyzeNewNode - The specified node is the root of a subtree of potentially
00444 /// new nodes.  Correct any processed operands (this may change the node) and
00445 /// calculate the NodeId.  If the node itself changes to a processed node, it
00446 /// is not remapped - the caller needs to take care of this.
00447 /// Returns the potentially changed node.
00448 SDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) {
00449   // If this was an existing node that is already done, we're done.
00450   if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed)
00451     return N;
00452 
00453   // Remove any stale map entries.
00454   ExpungeNode(N);
00455 
00456   // Okay, we know that this node is new.  Recursively walk all of its operands
00457   // to see if they are new also.  The depth of this walk is bounded by the size
00458   // of the new tree that was constructed (usually 2-3 nodes), so we don't worry
00459   // about revisiting of nodes.
00460   //
00461   // As we walk the operands, keep track of the number of nodes that are
00462   // processed.  If non-zero, this will become the new nodeid of this node.
00463   // Operands may morph when they are analyzed.  If so, the node will be
00464   // updated after all operands have been analyzed.  Since this is rare,
00465   // the code tries to minimize overhead in the non-morphing case.
00466 
00467   SmallVector<SDValue, 8> NewOps;
00468   unsigned NumProcessed = 0;
00469   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
00470     SDValue OrigOp = N->getOperand(i);
00471     SDValue Op = OrigOp;
00472 
00473     AnalyzeNewValue(Op); // Op may morph.
00474 
00475     if (Op.getNode()->getNodeId() == Processed)
00476       ++NumProcessed;
00477 
00478     if (!NewOps.empty()) {
00479       // Some previous operand changed.  Add this one to the list.
00480       NewOps.push_back(Op);
00481     } else if (Op != OrigOp) {
00482       // This is the first operand to change - add all operands so far.
00483       NewOps.insert(NewOps.end(), N->op_begin(), N->op_begin() + i);
00484       NewOps.push_back(Op);
00485     }
00486   }
00487 
00488   // Some operands changed - update the node.
00489   if (!NewOps.empty()) {
00490     SDNode *M = DAG.UpdateNodeOperands(SDValue(N, 0), &NewOps[0],
00491                                        NewOps.size()).getNode();
00492     if (M != N) {
00493       // The node morphed into a different node.  Normally for this to happen
00494       // the original node would have to be marked NewNode.  However this can
00495       // in theory momentarily not be the case while ReplaceValueWith is doing
00496       // its stuff.  Mark the original node NewNode to help sanity checking.
00497       N->setNodeId(NewNode);
00498       if (M->getNodeId() != NewNode && M->getNodeId() != Unanalyzed)
00499         // It morphed into a previously analyzed node - nothing more to do.
00500         return M;
00501 
00502       // It morphed into a different new node.  Do the equivalent of passing
00503       // it to AnalyzeNewNode: expunge it and calculate the NodeId.  No need
00504       // to remap the operands, since they are the same as the operands we
00505       // remapped above.
00506       N = M;
00507       ExpungeNode(N);
00508     }
00509   }
00510 
00511   // Calculate the NodeId.
00512   N->setNodeId(N->getNumOperands() - NumProcessed);
00513   if (N->getNodeId() == ReadyToProcess)
00514     Worklist.push_back(N);
00515 
00516   return N;
00517 }
00518 
00519 /// AnalyzeNewValue - Call AnalyzeNewNode, updating the node in Val if needed.
00520 /// If the node changes to a processed node, then remap it.
00521 void DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) {
00522   Val.setNode(AnalyzeNewNode(Val.getNode()));
00523   if (Val.getNode()->getNodeId() == Processed)
00524     // We were passed a processed node, or it morphed into one - remap it.
00525     RemapValue(Val);
00526 }
00527 
00528 /// ExpungeNode - If N has a bogus mapping in ReplacedValues, eliminate it.
00529 /// This can occur when a node is deleted then reallocated as a new node -
00530 /// the mapping in ReplacedValues applies to the deleted node, not the new
00531 /// one.
00532 /// The only map that can have a deleted node as a source is ReplacedValues.
00533 /// Other maps can have deleted nodes as targets, but since their looked-up
00534 /// values are always immediately remapped using RemapValue, resulting in a
00535 /// not-deleted node, this is harmless as long as ReplacedValues/RemapValue
00536 /// always performs correct mappings.  In order to keep the mapping correct,
00537 /// ExpungeNode should be called on any new nodes *before* adding them as
00538 /// either source or target to ReplacedValues (which typically means calling
00539 /// Expunge when a new node is first seen, since it may no longer be marked
00540 /// NewNode by the time it is added to ReplacedValues).
00541 void DAGTypeLegalizer::ExpungeNode(SDNode *N) {
00542   if (N->getNodeId() != NewNode)
00543     return;
00544 
00545   // If N is not remapped by ReplacedValues then there is nothing to do.
00546   unsigned i, e;
00547   for (i = 0, e = N->getNumValues(); i != e; ++i)
00548     if (ReplacedValues.find(SDValue(N, i)) != ReplacedValues.end())
00549       break;
00550 
00551   if (i == e)
00552     return;
00553 
00554   // Remove N from all maps - this is expensive but rare.
00555 
00556   for (DenseMap<SDValue, SDValue>::iterator I = PromotedIntegers.begin(),
00557        E = PromotedIntegers.end(); I != E; ++I) {
00558     assert(I->first.getNode() != N);
00559     RemapValue(I->second);
00560   }
00561 
00562   for (DenseMap<SDValue, SDValue>::iterator I = SoftenedFloats.begin(),
00563        E = SoftenedFloats.end(); I != E; ++I) {
00564     assert(I->first.getNode() != N);
00565     RemapValue(I->second);
00566   }
00567 
00568   for (DenseMap<SDValue, SDValue>::iterator I = ScalarizedVectors.begin(),
00569        E = ScalarizedVectors.end(); I != E; ++I) {
00570     assert(I->first.getNode() != N);
00571     RemapValue(I->second);
00572   }
00573 
00574   for (DenseMap<SDValue, SDValue>::iterator I = WidenedVectors.begin(),
00575        E = WidenedVectors.end(); I != E; ++I) {
00576     assert(I->first.getNode() != N);
00577     RemapValue(I->second);
00578   }
00579 
00580   for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
00581        I = ExpandedIntegers.begin(), E = ExpandedIntegers.end(); I != E; ++I){
00582     assert(I->first.getNode() != N);
00583     RemapValue(I->second.first);
00584     RemapValue(I->second.second);
00585   }
00586 
00587   for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
00588        I = ExpandedFloats.begin(), E = ExpandedFloats.end(); I != E; ++I) {
00589     assert(I->first.getNode() != N);
00590     RemapValue(I->second.first);
00591     RemapValue(I->second.second);
00592   }
00593 
00594   for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
00595        I = SplitVectors.begin(), E = SplitVectors.end(); I != E; ++I) {
00596     assert(I->first.getNode() != N);
00597     RemapValue(I->second.first);
00598     RemapValue(I->second.second);
00599   }
00600 
00601   for (DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.begin(),
00602        E = ReplacedValues.end(); I != E; ++I)
00603     RemapValue(I->second);
00604 
00605   for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
00606     ReplacedValues.erase(SDValue(N, i));
00607 }
00608 
00609 /// RemapValue - If the specified value was already legalized to another value,
00610 /// replace it by that value.
00611 void DAGTypeLegalizer::RemapValue(SDValue &N) {
00612   DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(N);
00613   if (I != ReplacedValues.end()) {
00614     // Use path compression to speed up future lookups if values get multiply
00615     // replaced with other values.
00616     RemapValue(I->second);
00617     N = I->second;
00618     assert(N.getNode()->getNodeId() != NewNode && "Mapped to new node!");
00619   }
00620 }
00621 
00622 namespace {
00623   /// NodeUpdateListener - This class is a DAGUpdateListener that listens for
00624   /// updates to nodes and recomputes their ready state.
00625   class VISIBILITY_HIDDEN NodeUpdateListener :
00626     public SelectionDAG::DAGUpdateListener {
00627     DAGTypeLegalizer &DTL;
00628     SmallSetVector<SDNode*, 16> &NodesToAnalyze;
00629   public:
00630     explicit NodeUpdateListener(DAGTypeLegalizer &dtl,
00631                                 SmallSetVector<SDNode*, 16> &nta)
00632       : DTL(dtl), NodesToAnalyze(nta) {}
00633 
00634     virtual void NodeDeleted(SDNode *N, SDNode *E) {
00635       assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess &&
00636              N->getNodeId() != DAGTypeLegalizer::Processed &&
00637              "Invalid node ID for RAUW deletion!");
00638       // It is possible, though rare, for the deleted node N to occur as a
00639       // target in a map, so note the replacement N -> E in ReplacedValues.
00640       assert(E && "Node not replaced?");
00641       DTL.NoteDeletion(N, E);
00642 
00643       // In theory the deleted node could also have been scheduled for analysis.
00644       // So remove it from the set of nodes which will be analyzed.
00645       NodesToAnalyze.remove(N);
00646 
00647       // In general nothing needs to be done for E, since it didn't change but
00648       // only gained new uses.  However N -> E was just added to ReplacedValues,
00649       // and the result of a ReplacedValues mapping is not allowed to be marked
00650       // NewNode.  So if E is marked NewNode, then it needs to be analyzed.
00651       if (E->getNodeId() == DAGTypeLegalizer::NewNode)
00652         NodesToAnalyze.insert(E);
00653     }
00654 
00655     virtual void NodeUpdated(SDNode *N) {
00656       // Node updates can mean pretty much anything.  It is possible that an
00657       // operand was set to something already processed (f.e.) in which case
00658       // this node could become ready.  Recompute its flags.
00659       assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess &&
00660              N->getNodeId() != DAGTypeLegalizer::Processed &&
00661              "Invalid node ID for RAUW deletion!");
00662       N->setNodeId(DAGTypeLegalizer::NewNode);
00663       NodesToAnalyze.insert(N);
00664     }
00665   };
00666 }
00667 
00668 
00669 /// ReplaceValueWithHelper - Internal helper for ReplaceValueWith.  Updates the
00670 /// DAG causing any uses of From to use To instead, but without expunging From
00671 /// or recording the replacement in ReplacedValues.  Do not call directly unless
00672 /// you really know what you are doing!
00673 void DAGTypeLegalizer::ReplaceValueWithHelper(SDValue From, SDValue To) {
00674   assert(From.getNode() != To.getNode() && "Potential legalization loop!");
00675 
00676   // If expansion produced new nodes, make sure they are properly marked.
00677   AnalyzeNewValue(To); // Expunges To.
00678 
00679   // Anything that used the old node should now use the new one.  Note that this
00680   // can potentially cause recursive merging.
00681   SmallSetVector<SDNode*, 16> NodesToAnalyze;
00682   NodeUpdateListener NUL(*this, NodesToAnalyze);
00683   DAG.ReplaceAllUsesOfValueWith(From, To, &NUL);
00684 
00685   // Process the list of nodes that need to be reanalyzed.
00686   while (!NodesToAnalyze.empty()) {
00687     SDNode *N = NodesToAnalyze.back();
00688     NodesToAnalyze.pop_back();
00689     if (N->getNodeId() != DAGTypeLegalizer::NewNode)
00690       // The node was analyzed while reanalyzing an earlier node - it is safe to
00691       // skip.  Note that this is not a morphing node - otherwise it would still
00692       // be marked NewNode.
00693       continue;
00694 
00695     // Analyze the node's operands and recalculate the node ID.
00696     SDNode *M = AnalyzeNewNode(N);
00697     if (M != N) {
00698       // The node morphed into a different node.  Make everyone use the new node
00699       // instead.
00700       assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!");
00701       assert(N->getNumValues() == M->getNumValues() &&
00702              "Node morphing changed the number of results!");
00703       for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
00704         SDValue OldVal(N, i);
00705         SDValue NewVal(M, i);
00706         if (M->getNodeId() == Processed)
00707           RemapValue(NewVal);
00708         DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal, &NUL);
00709       }
00710       // The original node continues to exist in the DAG, marked NewNode.
00711     }
00712   }
00713 }
00714 
00715 /// ReplaceValueWith - The specified value was legalized to the specified other
00716 /// value.  Update the DAG and NodeIds replacing any uses of From to use To
00717 /// instead.
00718 void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) {
00719   assert(From.getNode()->getNodeId() == ReadyToProcess &&
00720          "Only the node being processed may be remapped!");
00721 
00722   // If expansion produced new nodes, make sure they are properly marked.
00723   ExpungeNode(From.getNode());
00724   AnalyzeNewValue(To); // Expunges To.
00725 
00726   // The old node may still be present in a map like ExpandedIntegers or
00727   // PromotedIntegers.  Inform maps about the replacement.
00728   ReplacedValues[From] = To;
00729 
00730   // Do the replacement.
00731   ReplaceValueWithHelper(From, To);
00732 }
00733 
00734 void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) {
00735   assert(Result.getValueType() == TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
00736          "Invalid type for promoted integer");
00737   AnalyzeNewValue(Result);
00738 
00739   SDValue &OpEntry = PromotedIntegers[Op];
00740   assert(OpEntry.getNode() == 0 && "Node is already promoted!");
00741   OpEntry = Result;
00742 }
00743 
00744 void DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) {
00745   assert(Result.getValueType() == TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
00746          "Invalid type for softened float");
00747   AnalyzeNewValue(Result);
00748 
00749   SDValue &OpEntry = SoftenedFloats[Op];
00750   assert(OpEntry.getNode() == 0 && "Node is already converted to integer!");
00751   OpEntry = Result;
00752 }
00753 
00754 void DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) {
00755   assert(Result.getValueType() == Op.getValueType().getVectorElementType() &&
00756          "Invalid type for scalarized vector");
00757   AnalyzeNewValue(Result);
00758 
00759   SDValue &OpEntry = ScalarizedVectors[Op];
00760   assert(OpEntry.getNode() == 0 && "Node is already scalarized!");
00761   OpEntry = Result;
00762 }
00763 
00764 void DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo,
00765                                           SDValue &Hi) {
00766   std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op];
00767   RemapValue(Entry.first);
00768   RemapValue(Entry.second);
00769   assert(Entry.first.getNode() && "Operand isn't expanded");
00770   Lo = Entry.first;
00771   Hi = Entry.second;
00772 }
00773 
00774 void DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo,
00775                                           SDValue Hi) {
00776   assert(Lo.getValueType() == TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
00777          Hi.getValueType() == Lo.getValueType() &&
00778          "Invalid type for expanded integer");
00779   // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
00780   AnalyzeNewValue(Lo);
00781   AnalyzeNewValue(Hi);
00782 
00783   // Remember that this is the result of the node.
00784   std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op];
00785   assert(Entry.first.getNode() == 0 && "Node already expanded");
00786   Entry.first = Lo;
00787   Entry.second = Hi;
00788 }
00789 
00790 void DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo,
00791                                         SDValue &Hi) {
00792   std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op];
00793   RemapValue(Entry.first);
00794   RemapValue(Entry.second);
00795   assert(Entry.first.getNode() && "Operand isn't expanded");
00796   Lo = Entry.first;
00797   Hi = Entry.second;
00798 }
00799 
00800 void DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo,
00801                                         SDValue Hi) {
00802   assert(Lo.getValueType() == TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
00803          Hi.getValueType() == Lo.getValueType() &&
00804          "Invalid type for expanded float");
00805   // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
00806   AnalyzeNewValue(Lo);
00807   AnalyzeNewValue(Hi);
00808 
00809   // Remember that this is the result of the node.
00810   std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op];
00811   assert(Entry.first.getNode() == 0 && "Node already expanded");
00812   Entry.first = Lo;
00813   Entry.second = Hi;
00814 }
00815 
00816 void DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo,
00817                                       SDValue &Hi) {
00818   std::pair<SDValue, SDValue> &Entry = SplitVectors[Op];
00819   RemapValue(Entry.first);
00820   RemapValue(Entry.second);
00821   assert(Entry.first.getNode() && "Operand isn't split");
00822   Lo = Entry.first;
00823   Hi = Entry.second;
00824 }
00825 
00826 void DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo,
00827                                       SDValue Hi) {
00828   assert(Lo.getValueType().getVectorElementType() ==
00829          Op.getValueType().getVectorElementType() &&
00830          2*Lo.getValueType().getVectorNumElements() ==
00831          Op.getValueType().getVectorNumElements() &&
00832          Hi.getValueType() == Lo.getValueType() &&
00833          "Invalid type for split vector");
00834   // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
00835   AnalyzeNewValue(Lo);
00836   AnalyzeNewValue(Hi);
00837 
00838   // Remember that this is the result of the node.
00839   std::pair<SDValue, SDValue> &Entry = SplitVectors[Op];
00840   assert(Entry.first.getNode() == 0 && "Node already split");
00841   Entry.first = Lo;
00842   Entry.second = Hi;
00843 }
00844 
00845 void DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) {
00846   assert(Result.getValueType() == TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
00847          "Invalid type for widened vector");
00848   AnalyzeNewValue(Result);
00849 
00850   SDValue &OpEntry = WidenedVectors[Op];
00851   assert(OpEntry.getNode() == 0 && "Node already widened!");
00852   OpEntry = Result;
00853 }
00854 
00855 
00856 //===----------------------------------------------------------------------===//
00857 // Utilities.
00858 //===----------------------------------------------------------------------===//
00859 
00860 /// BitConvertToInteger - Convert to an integer of the same size.
00861 SDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) {
00862   unsigned BitWidth = Op.getValueType().getSizeInBits();
00863   return DAG.getNode(ISD::BIT_CONVERT, Op.getDebugLoc(),
00864                      EVT::getIntegerVT(*DAG.getContext(), BitWidth), Op);
00865 }
00866 
00867 /// BitConvertVectorToIntegerVector - Convert to a vector of integers of the
00868 /// same size.
00869 SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(SDValue Op) {
00870   assert(Op.getValueType().isVector() && "Only applies to vectors!");
00871   unsigned EltWidth = Op.getValueType().getVectorElementType().getSizeInBits();
00872   EVT EltNVT = EVT::getIntegerVT(*DAG.getContext(), EltWidth);
00873   unsigned NumElts = Op.getValueType().getVectorNumElements();
00874   return DAG.getNode(ISD::BIT_CONVERT, Op.getDebugLoc(),
00875                      EVT::getVectorVT(*DAG.getContext(), EltNVT, NumElts), Op);
00876 }
00877 
00878 SDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op,
00879                                                EVT DestVT) {
00880   DebugLoc dl = Op.getDebugLoc();
00881   // Create the stack frame object.  Make sure it is aligned for both
00882   // the source and destination types.
00883   SDValue StackPtr = DAG.CreateStackTemporary(Op.getValueType(), DestVT);
00884   // Emit a store to the stack slot.
00885   SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, NULL, 0);
00886   // Result is a load from the stack slot.
00887   return DAG.getLoad(DestVT, dl, Store, StackPtr, NULL, 0);
00888 }
00889 
00890 /// CustomLowerNode - Replace the node's results with custom code provided
00891 /// by the target and return "true", or do nothing and return "false".
00892 /// The last parameter is FALSE if we are dealing with a node with legal
00893 /// result types and illegal operand. The second parameter denotes the type of
00894 /// illegal OperandNo in that case.
00895 /// The last parameter being TRUE means we are dealing with a
00896 /// node with illegal result types. The second parameter denotes the type of
00897 /// illegal ResNo in that case.
00898 bool DAGTypeLegalizer::CustomLowerNode(SDNode *N, EVT VT, bool LegalizeResult) {
00899   // See if the target wants to custom lower this node.
00900   if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom)
00901     return false;
00902 
00903   SmallVector<SDValue, 8> Results;
00904   if (LegalizeResult)
00905     TLI.ReplaceNodeResults(N, Results, DAG);
00906   else
00907     TLI.LowerOperationWrapper(N, Results, DAG);
00908 
00909   if (Results.empty())
00910     // The target didn't want to custom lower it after all.
00911     return false;
00912 
00913   // Make everything that once used N's values now use those in Results instead.
00914   assert(Results.size() == N->getNumValues() &&
00915          "Custom lowering returned the wrong number of results!");
00916   for (unsigned i = 0, e = Results.size(); i != e; ++i)
00917     ReplaceValueWith(SDValue(N, i), Results[i]);
00918   return true;
00919 }
00920 
00921 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
00922 /// which is split into two not necessarily identical pieces.
00923 void DAGTypeLegalizer::GetSplitDestVTs(EVT InVT, EVT &LoVT, EVT &HiVT) {
00924   // Currently all types are split in half.
00925   if (!InVT.isVector()) {
00926     LoVT = HiVT = TLI.getTypeToTransformTo(*DAG.getContext(), InVT);
00927   } else {
00928     unsigned NumElements = InVT.getVectorNumElements();
00929     assert(!(NumElements & 1) && "Splitting vector, but not in half!");
00930     LoVT = HiVT = EVT::getVectorVT(*DAG.getContext(), InVT.getVectorElementType(), NumElements/2);
00931   }
00932 }
00933 
00934 /// GetPairElements - Use ISD::EXTRACT_ELEMENT nodes to extract the low and
00935 /// high parts of the given value.
00936 void DAGTypeLegalizer::GetPairElements(SDValue Pair,
00937                                        SDValue &Lo, SDValue &Hi) {
00938   DebugLoc dl = Pair.getDebugLoc();
00939   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.getValueType());
00940   Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair,
00941                    DAG.getIntPtrConstant(0));
00942   Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair,
00943                    DAG.getIntPtrConstant(1));
00944 }
00945 
00946 SDValue DAGTypeLegalizer::GetVectorElementPointer(SDValue VecPtr, EVT EltVT,
00947                                                   SDValue Index) {
00948   DebugLoc dl = Index.getDebugLoc();
00949   // Make sure the index type is big enough to compute in.
00950   if (Index.getValueType().bitsGT(TLI.getPointerTy()))
00951     Index = DAG.getNode(ISD::TRUNCATE, dl, TLI.getPointerTy(), Index);
00952   else
00953     Index = DAG.getNode(ISD::ZERO_EXTEND, dl, TLI.getPointerTy(), Index);
00954 
00955   // Calculate the element offset and add it to the pointer.
00956   unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size.
00957 
00958   Index = DAG.getNode(ISD::MUL, dl, Index.getValueType(), Index,
00959                       DAG.getConstant(EltSize, Index.getValueType()));
00960   return DAG.getNode(ISD::ADD, dl, Index.getValueType(), Index, VecPtr);
00961 }
00962 
00963 /// JoinIntegers - Build an integer with low bits Lo and high bits Hi.
00964 SDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) {
00965   // Arbitrarily use dlHi for result DebugLoc
00966   DebugLoc dlHi = Hi.getDebugLoc();
00967   DebugLoc dlLo = Lo.getDebugLoc();
00968   EVT LVT = Lo.getValueType();
00969   EVT HVT = Hi.getValueType();
00970   EVT NVT = EVT::getIntegerVT(*DAG.getContext(), LVT.getSizeInBits() + HVT.getSizeInBits());
00971 
00972   Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo);
00973   Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi);
00974   Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi,
00975                    DAG.getConstant(LVT.getSizeInBits(), TLI.getPointerTy()));
00976   return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi);
00977 }
00978 
00979 /// LibCallify - Convert the node into a libcall with the same prototype.
00980 SDValue DAGTypeLegalizer::LibCallify(RTLIB::Libcall LC, SDNode *N,
00981                                      bool isSigned) {
00982   unsigned NumOps = N->getNumOperands();
00983   DebugLoc dl = N->getDebugLoc();
00984   if (NumOps == 0) {
00985     return MakeLibCall(LC, N->getValueType(0), 0, 0, isSigned, dl);
00986   } else if (NumOps == 1) {
00987     SDValue Op = N->getOperand(0);
00988     return MakeLibCall(LC, N->getValueType(0), &Op, 1, isSigned, dl);
00989   } else if (NumOps == 2) {
00990     SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
00991     return MakeLibCall(LC, N->getValueType(0), Ops, 2, isSigned, dl);
00992   }
00993   SmallVector<SDValue, 8> Ops(NumOps);
00994   for (unsigned i = 0; i < NumOps; ++i)
00995     Ops[i] = N->getOperand(i);
00996 
00997   return MakeLibCall(LC, N->getValueType(0), &Ops[0], NumOps, isSigned, dl);
00998 }
00999 
01000 /// MakeLibCall - Generate a libcall taking the given operands as arguments and
01001 /// returning a result of type RetVT.
01002 SDValue DAGTypeLegalizer::MakeLibCall(RTLIB::Libcall LC, EVT RetVT,
01003                                       const SDValue *Ops, unsigned NumOps,
01004                                       bool isSigned, DebugLoc dl) {
01005   TargetLowering::ArgListTy Args;
01006   Args.reserve(NumOps);
01007 
01008   TargetLowering::ArgListEntry Entry;
01009   for (unsigned i = 0; i != NumOps; ++i) {
01010     Entry.Node = Ops[i];
01011     Entry.Ty = Entry.Node.getValueType().getTypeForEVT(*DAG.getContext());
01012     Entry.isSExt = isSigned;
01013     Entry.isZExt = !isSigned;
01014     Args.push_back(Entry);
01015   }
01016   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
01017                                          TLI.getPointerTy());
01018 
01019   const Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
01020   std::pair<SDValue,SDValue> CallInfo =
01021     TLI.LowerCallTo(DAG.getEntryNode(), RetTy, isSigned, !isSigned, false,
01022                     false, 0, TLI.getLibcallCallingConv(LC), false,
01023                     /*isReturnValueUsed=*/true,
01024                     Callee, Args, DAG, dl);
01025   return CallInfo.first;
01026 }
01027 
01028 /// PromoteTargetBoolean - Promote the given target boolean to a target boolean
01029 /// of the given type.  A target boolean is an integer value, not necessarily of
01030 /// type i1, the bits of which conform to getBooleanContents.
01031 SDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, EVT VT) {
01032   DebugLoc dl = Bool.getDebugLoc();
01033   ISD::NodeType ExtendCode;
01034   switch (TLI.getBooleanContents()) {
01035   default:
01036     assert(false && "Unknown BooleanContent!");
01037   case TargetLowering::UndefinedBooleanContent:
01038     // Extend to VT by adding rubbish bits.
01039     ExtendCode = ISD::ANY_EXTEND;
01040     break;
01041   case TargetLowering::ZeroOrOneBooleanContent:
01042     // Extend to VT by adding zero bits.
01043     ExtendCode = ISD::ZERO_EXTEND;
01044     break;
01045   case TargetLowering::ZeroOrNegativeOneBooleanContent: {
01046     // Extend to VT by copying the sign bit.
01047     ExtendCode = ISD::SIGN_EXTEND;
01048     break;
01049   }
01050   }
01051   return DAG.getNode(ExtendCode, dl, VT, Bool);
01052 }
01053 
01054 /// SplitInteger - Return the lower LoVT bits of Op in Lo and the upper HiVT
01055 /// bits in Hi.
01056 void DAGTypeLegalizer::SplitInteger(SDValue Op,
01057                                     EVT LoVT, EVT HiVT,
01058                                     SDValue &Lo, SDValue &Hi) {
01059   DebugLoc dl = Op.getDebugLoc();
01060   assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() ==
01061          Op.getValueType().getSizeInBits() && "Invalid integer splitting!");
01062   Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op);
01063   Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op,
01064                    DAG.getConstant(LoVT.getSizeInBits(), TLI.getPointerTy()));
01065   Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi);
01066 }
01067 
01068 /// SplitInteger - Return the lower and upper halves of Op's bits in a value
01069 /// type half the size of Op's.
01070 void DAGTypeLegalizer::SplitInteger(SDValue Op,
01071                                     SDValue &Lo, SDValue &Hi) {
01072   EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), Op.getValueType().getSizeInBits()/2);
01073   SplitInteger(Op, HalfVT, HalfVT, Lo, Hi);
01074 }
01075 
01076 
01077 //===----------------------------------------------------------------------===//
01078 //  Entry Point
01079 //===----------------------------------------------------------------------===//
01080 
01081 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
01082 /// only uses types natively supported by the target.  Returns "true" if it made
01083 /// any changes.
01084 ///
01085 /// Note that this is an involved process that may invalidate pointers into
01086 /// the graph.
01087 bool SelectionDAG::LegalizeTypes() {
01088   return DAGTypeLegalizer(*this).run();
01089 }