LLVM API Documentation

SelectionDAG.cpp

Go to the documentation of this file.
00001 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This implements the SelectionDAG class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/CodeGen/SelectionDAG.h"
00015 #include "llvm/Constants.h"
00016 #include "llvm/GlobalValue.h"
00017 #include "llvm/Intrinsics.h"
00018 #include "llvm/Assembly/Writer.h"
00019 #include "llvm/CodeGen/MachineBasicBlock.h"
00020 #include "llvm/Support/MathExtras.h"
00021 #include "llvm/Target/MRegisterInfo.h"
00022 #include "llvm/Target/TargetLowering.h"
00023 #include "llvm/Target/TargetInstrInfo.h"
00024 #include "llvm/Target/TargetMachine.h"
00025 #include "llvm/ADT/SetVector.h"
00026 #include "llvm/ADT/StringExtras.h"
00027 #include <iostream>
00028 #include <set>
00029 #include <cmath>
00030 #include <algorithm>
00031 using namespace llvm;
00032 
00033 static bool isCommutativeBinOp(unsigned Opcode) {
00034   switch (Opcode) {
00035   case ISD::ADD:
00036   case ISD::MUL:
00037   case ISD::MULHU:
00038   case ISD::MULHS:
00039   case ISD::FADD:
00040   case ISD::FMUL:
00041   case ISD::AND:
00042   case ISD::OR:
00043   case ISD::XOR: return true;
00044   default: return false; // FIXME: Need commutative info for user ops!
00045   }
00046 }
00047 
00048 // isInvertibleForFree - Return true if there is no cost to emitting the logical
00049 // inverse of this node.
00050 static bool isInvertibleForFree(SDOperand N) {
00051   if (isa<ConstantSDNode>(N.Val)) return true;
00052   if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse())
00053     return true;
00054   return false;
00055 }
00056 
00057 //===----------------------------------------------------------------------===//
00058 //                              ConstantFPSDNode Class
00059 //===----------------------------------------------------------------------===//
00060 
00061 /// isExactlyValue - We don't rely on operator== working on double values, as
00062 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
00063 /// As such, this method can be used to do an exact bit-for-bit comparison of
00064 /// two floating point values.
00065 bool ConstantFPSDNode::isExactlyValue(double V) const {
00066   return DoubleToBits(V) == DoubleToBits(Value);
00067 }
00068 
00069 //===----------------------------------------------------------------------===//
00070 //                              ISD Namespace
00071 //===----------------------------------------------------------------------===//
00072 
00073 /// isBuildVectorAllOnes - Return true if the specified node is a
00074 /// BUILD_VECTOR where all of the elements are ~0 or undef.
00075 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
00076   // Look through a bit convert.
00077   if (N->getOpcode() == ISD::BIT_CONVERT)
00078     N = N->getOperand(0).Val;
00079   
00080   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
00081   
00082   unsigned i = 0, e = N->getNumOperands();
00083   
00084   // Skip over all of the undef values.
00085   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
00086     ++i;
00087   
00088   // Do not accept an all-undef vector.
00089   if (i == e) return false;
00090   
00091   // Do not accept build_vectors that aren't all constants or which have non-~0
00092   // elements.
00093   SDOperand NotZero = N->getOperand(i);
00094   if (isa<ConstantSDNode>(NotZero)) {
00095     if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue())
00096       return false;
00097   } else if (isa<ConstantFPSDNode>(NotZero)) {
00098     MVT::ValueType VT = NotZero.getValueType();
00099     if (VT== MVT::f64) {
00100       if (DoubleToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) !=
00101           (uint64_t)-1)
00102         return false;
00103     } else {
00104       if (FloatToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) !=
00105           (uint32_t)-1)
00106         return false;
00107     }
00108   } else
00109     return false;
00110   
00111   // Okay, we have at least one ~0 value, check to see if the rest match or are
00112   // undefs.
00113   for (++i; i != e; ++i)
00114     if (N->getOperand(i) != NotZero &&
00115         N->getOperand(i).getOpcode() != ISD::UNDEF)
00116       return false;
00117   return true;
00118 }
00119 
00120 
00121 /// isBuildVectorAllZeros - Return true if the specified node is a
00122 /// BUILD_VECTOR where all of the elements are 0 or undef.
00123 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
00124   // Look through a bit convert.
00125   if (N->getOpcode() == ISD::BIT_CONVERT)
00126     N = N->getOperand(0).Val;
00127   
00128   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
00129   
00130   unsigned i = 0, e = N->getNumOperands();
00131   
00132   // Skip over all of the undef values.
00133   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
00134     ++i;
00135   
00136   // Do not accept an all-undef vector.
00137   if (i == e) return false;
00138   
00139   // Do not accept build_vectors that aren't all constants or which have non-~0
00140   // elements.
00141   SDOperand Zero = N->getOperand(i);
00142   if (isa<ConstantSDNode>(Zero)) {
00143     if (!cast<ConstantSDNode>(Zero)->isNullValue())
00144       return false;
00145   } else if (isa<ConstantFPSDNode>(Zero)) {
00146     if (!cast<ConstantFPSDNode>(Zero)->isExactlyValue(0.0))
00147       return false;
00148   } else
00149     return false;
00150   
00151   // Okay, we have at least one ~0 value, check to see if the rest match or are
00152   // undefs.
00153   for (++i; i != e; ++i)
00154     if (N->getOperand(i) != Zero &&
00155         N->getOperand(i).getOpcode() != ISD::UNDEF)
00156       return false;
00157   return true;
00158 }
00159 
00160 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
00161 /// when given the operation for (X op Y).
00162 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
00163   // To perform this operation, we just need to swap the L and G bits of the
00164   // operation.
00165   unsigned OldL = (Operation >> 2) & 1;
00166   unsigned OldG = (Operation >> 1) & 1;
00167   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
00168                        (OldL << 1) |       // New G bit
00169                        (OldG << 2));        // New L bit.
00170 }
00171 
00172 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
00173 /// 'op' is a valid SetCC operation.
00174 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
00175   unsigned Operation = Op;
00176   if (isInteger)
00177     Operation ^= 7;   // Flip L, G, E bits, but not U.
00178   else
00179     Operation ^= 15;  // Flip all of the condition bits.
00180   if (Operation > ISD::SETTRUE2)
00181     Operation &= ~8;     // Don't let N and U bits get set.
00182   return ISD::CondCode(Operation);
00183 }
00184 
00185 
00186 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
00187 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
00188 /// if the operation does not depend on the sign of the input (setne and seteq).
00189 static int isSignedOp(ISD::CondCode Opcode) {
00190   switch (Opcode) {
00191   default: assert(0 && "Illegal integer setcc operation!");
00192   case ISD::SETEQ:
00193   case ISD::SETNE: return 0;
00194   case ISD::SETLT:
00195   case ISD::SETLE:
00196   case ISD::SETGT:
00197   case ISD::SETGE: return 1;
00198   case ISD::SETULT:
00199   case ISD::SETULE:
00200   case ISD::SETUGT:
00201   case ISD::SETUGE: return 2;
00202   }
00203 }
00204 
00205 /// getSetCCOrOperation - Return the result of a logical OR between different
00206 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
00207 /// returns SETCC_INVALID if it is not possible to represent the resultant
00208 /// comparison.
00209 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
00210                                        bool isInteger) {
00211   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
00212     // Cannot fold a signed integer setcc with an unsigned integer setcc.
00213     return ISD::SETCC_INVALID;
00214 
00215   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
00216 
00217   // If the N and U bits get set then the resultant comparison DOES suddenly
00218   // care about orderedness, and is true when ordered.
00219   if (Op > ISD::SETTRUE2)
00220     Op &= ~16;     // Clear the U bit if the N bit is set.
00221   
00222   // Canonicalize illegal integer setcc's.
00223   if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
00224     Op = ISD::SETNE;
00225   
00226   return ISD::CondCode(Op);
00227 }
00228 
00229 /// getSetCCAndOperation - Return the result of a logical AND between different
00230 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
00231 /// function returns zero if it is not possible to represent the resultant
00232 /// comparison.
00233 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
00234                                         bool isInteger) {
00235   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
00236     // Cannot fold a signed setcc with an unsigned setcc.
00237     return ISD::SETCC_INVALID;
00238 
00239   // Combine all of the condition bits.
00240   ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
00241   
00242   // Canonicalize illegal integer setcc's.
00243   if (isInteger) {
00244     switch (Result) {
00245     default: break;
00246     case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
00247     case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
00248     case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
00249     case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
00250     }
00251   }
00252   
00253   return Result;
00254 }
00255 
00256 const TargetMachine &SelectionDAG::getTarget() const {
00257   return TLI.getTargetMachine();
00258 }
00259 
00260 //===----------------------------------------------------------------------===//
00261 //                              SelectionDAG Class
00262 //===----------------------------------------------------------------------===//
00263 
00264 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
00265 /// SelectionDAG, including nodes (like loads) that have uses of their token
00266 /// chain but no other uses and no side effect.  If a node is passed in as an
00267 /// argument, it is used as the seed for node deletion.
00268 void SelectionDAG::RemoveDeadNodes(SDNode *N) {
00269   // Create a dummy node (which is not added to allnodes), that adds a reference
00270   // to the root node, preventing it from being deleted.
00271   HandleSDNode Dummy(getRoot());
00272 
00273   bool MadeChange = false;
00274   
00275   // If we have a hint to start from, use it.
00276   if (N && N->use_empty()) {
00277     DestroyDeadNode(N);
00278     MadeChange = true;
00279   }
00280 
00281   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
00282     if (I->use_empty() && I->getOpcode() != 65535) {
00283       // Node is dead, recursively delete newly dead uses.
00284       DestroyDeadNode(I);
00285       MadeChange = true;
00286     }
00287   
00288   // Walk the nodes list, removing the nodes we've marked as dead.
00289   if (MadeChange) {
00290     for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ) {
00291       SDNode *N = I++;
00292       if (N->use_empty())
00293         AllNodes.erase(N);
00294     }
00295   }
00296   
00297   // If the root changed (e.g. it was a dead load, update the root).
00298   setRoot(Dummy.getValue());
00299 }
00300 
00301 /// DestroyDeadNode - We know that N is dead.  Nuke it from the CSE maps for the
00302 /// graph.  If it is the last user of any of its operands, recursively process
00303 /// them the same way.
00304 /// 
00305 void SelectionDAG::DestroyDeadNode(SDNode *N) {
00306   // Okay, we really are going to delete this node.  First take this out of the
00307   // appropriate CSE map.
00308   RemoveNodeFromCSEMaps(N);
00309   
00310   // Next, brutally remove the operand list.  This is safe to do, as there are
00311   // no cycles in the graph.
00312   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
00313     SDNode *O = I->Val;
00314     O->removeUser(N);
00315     
00316     // Now that we removed this operand, see if there are no uses of it left.
00317     if (O->use_empty())
00318       DestroyDeadNode(O);
00319   }
00320   delete[] N->OperandList;
00321   N->OperandList = 0;
00322   N->NumOperands = 0;
00323 
00324   // Mark the node as dead.
00325   N->MorphNodeTo(65535);
00326 }
00327 
00328 void SelectionDAG::DeleteNode(SDNode *N) {
00329   assert(N->use_empty() && "Cannot delete a node that is not dead!");
00330 
00331   // First take this out of the appropriate CSE map.
00332   RemoveNodeFromCSEMaps(N);
00333 
00334   // Finally, remove uses due to operands of this node, remove from the 
00335   // AllNodes list, and delete the node.
00336   DeleteNodeNotInCSEMaps(N);
00337 }
00338 
00339 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
00340 
00341   // Remove it from the AllNodes list.
00342   AllNodes.remove(N);
00343     
00344   // Drop all of the operands and decrement used nodes use counts.
00345   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
00346     I->Val->removeUser(N);
00347   delete[] N->OperandList;
00348   N->OperandList = 0;
00349   N->NumOperands = 0;
00350   
00351   delete N;
00352 }
00353 
00354 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
00355 /// correspond to it.  This is useful when we're about to delete or repurpose
00356 /// the node.  We don't want future request for structurally identical nodes
00357 /// to return N anymore.
00358 void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
00359   bool Erased = false;
00360   switch (N->getOpcode()) {
00361   case ISD::HANDLENODE: return;  // noop.
00362   case ISD::Constant:
00363     Erased = Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(),
00364                                             N->getValueType(0)));
00365     break;
00366   case ISD::TargetConstant:
00367     Erased = TargetConstants.erase(std::make_pair(
00368                                     cast<ConstantSDNode>(N)->getValue(),
00369                                                   N->getValueType(0)));
00370     break;
00371   case ISD::ConstantFP: {
00372     uint64_t V = DoubleToBits(cast<ConstantFPSDNode>(N)->getValue());
00373     Erased = ConstantFPs.erase(std::make_pair(V, N->getValueType(0)));
00374     break;
00375   }
00376   case ISD::TargetConstantFP: {
00377     uint64_t V = DoubleToBits(cast<ConstantFPSDNode>(N)->getValue());
00378     Erased = TargetConstantFPs.erase(std::make_pair(V, N->getValueType(0)));
00379     break;
00380   }
00381   case ISD::STRING:
00382     Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue());
00383     break;
00384   case ISD::CONDCODE:
00385     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
00386            "Cond code doesn't exist!");
00387     Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
00388     CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
00389     break;
00390   case ISD::GlobalAddress: {
00391     GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(N);
00392     Erased = GlobalValues.erase(std::make_pair(GN->getGlobal(),
00393                                                GN->getOffset()));
00394     break;
00395   }
00396   case ISD::TargetGlobalAddress: {
00397     GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(N);
00398     Erased =TargetGlobalValues.erase(std::make_pair(GN->getGlobal(),
00399                                                     GN->getOffset()));
00400     break;
00401   }
00402   case ISD::FrameIndex:
00403     Erased = FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
00404     break;
00405   case ISD::TargetFrameIndex:
00406     Erased = TargetFrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
00407     break;
00408   case ISD::JumpTable:
00409     Erased = JumpTableIndices.erase(cast<JumpTableSDNode>(N)->getIndex());
00410     break;
00411   case ISD::TargetJumpTable:
00412     Erased = 
00413       TargetJumpTableIndices.erase(cast<JumpTableSDNode>(N)->getIndex());
00414     break;
00415   case ISD::ConstantPool:
00416     Erased = ConstantPoolIndices.
00417       erase(std::make_pair(cast<ConstantPoolSDNode>(N)->get(),
00418                         std::make_pair(cast<ConstantPoolSDNode>(N)->getOffset(),
00419                                  cast<ConstantPoolSDNode>(N)->getAlignment())));
00420     break;
00421   case ISD::TargetConstantPool:
00422     Erased = TargetConstantPoolIndices.
00423       erase(std::make_pair(cast<ConstantPoolSDNode>(N)->get(),
00424                         std::make_pair(cast<ConstantPoolSDNode>(N)->getOffset(),
00425                                  cast<ConstantPoolSDNode>(N)->getAlignment())));
00426     break;
00427   case ISD::BasicBlock:
00428     Erased = BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock());
00429     break;
00430   case ISD::ExternalSymbol:
00431     Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
00432     break;
00433   case ISD::TargetExternalSymbol:
00434     Erased =
00435       TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
00436     break;
00437   case ISD::VALUETYPE:
00438     Erased = ValueTypeNodes[cast<VTSDNode>(N)->getVT()] != 0;
00439     ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0;
00440     break;
00441   case ISD::Register:
00442     Erased = RegNodes.erase(std::make_pair(cast<RegisterSDNode>(N)->getReg(),
00443                                            N->getValueType(0)));
00444     break;
00445   case ISD::SRCVALUE: {
00446     SrcValueSDNode *SVN = cast<SrcValueSDNode>(N);
00447     Erased =ValueNodes.erase(std::make_pair(SVN->getValue(), SVN->getOffset()));
00448     break;
00449   }    
00450   case ISD::LOAD:
00451     Erased = Loads.erase(std::make_pair(N->getOperand(1),
00452                                         std::make_pair(N->getOperand(0),
00453                                                        N->getValueType(0))));
00454     break;
00455   default:
00456     if (N->getNumValues() == 1) {
00457       if (N->getNumOperands() == 0) {
00458         Erased = NullaryOps.erase(std::make_pair(N->getOpcode(),
00459                                                  N->getValueType(0)));
00460       } else if (N->getNumOperands() == 1) {
00461         Erased = 
00462           UnaryOps.erase(std::make_pair(N->getOpcode(),
00463                                         std::make_pair(N->getOperand(0),
00464                                                        N->getValueType(0))));
00465       } else if (N->getNumOperands() == 2) {
00466         Erased = 
00467           BinaryOps.erase(std::make_pair(N->getOpcode(),
00468                                          std::make_pair(N->getOperand(0),
00469                                                         N->getOperand(1))));
00470       } else { 
00471         std::vector<SDOperand> Ops(N->op_begin(), N->op_end());
00472         Erased = 
00473           OneResultNodes.erase(std::make_pair(N->getOpcode(),
00474                                               std::make_pair(N->getValueType(0),
00475                                                              Ops)));
00476       }
00477     } else {
00478       // Remove the node from the ArbitraryNodes map.
00479       std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end());
00480       std::vector<SDOperand>     Ops(N->op_begin(), N->op_end());
00481       Erased =
00482         ArbitraryNodes.erase(std::make_pair(N->getOpcode(),
00483                                             std::make_pair(RV, Ops)));
00484     }
00485     break;
00486   }
00487 #ifndef NDEBUG
00488   // Verify that the node was actually in one of the CSE maps, unless it has a 
00489   // flag result (which cannot be CSE'd) or is one of the special cases that are
00490   // not subject to CSE.
00491   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag &&
00492       !N->isTargetOpcode()) {
00493     N->dump();
00494     assert(0 && "Node is not in map!");
00495   }
00496 #endif
00497 }
00498 
00499 /// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps.  It
00500 /// has been taken out and modified in some way.  If the specified node already
00501 /// exists in the CSE maps, do not modify the maps, but return the existing node
00502 /// instead.  If it doesn't exist, add it and return null.
00503 ///
00504 SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
00505   assert(N->getNumOperands() && "This is a leaf node!");
00506   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
00507     return 0;    // Never add these nodes.
00508   
00509   // Check that remaining values produced are not flags.
00510   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
00511     if (N->getValueType(i) == MVT::Flag)
00512       return 0;   // Never CSE anything that produces a flag.
00513   
00514   if (N->getNumValues() == 1) {
00515     if (N->getNumOperands() == 1) {
00516       SDNode *&U = UnaryOps[std::make_pair(N->getOpcode(),
00517                                            std::make_pair(N->getOperand(0),
00518                                                           N->getValueType(0)))];
00519       if (U) return U;
00520       U = N;
00521     } else if (N->getNumOperands() == 2) {
00522       SDNode *&B = BinaryOps[std::make_pair(N->getOpcode(),
00523                                             std::make_pair(N->getOperand(0),
00524                                                            N->getOperand(1)))];
00525       if (B) return B;
00526       B = N;
00527     } else {
00528       std::vector<SDOperand> Ops(N->op_begin(), N->op_end());
00529       SDNode *&ORN = OneResultNodes[std::make_pair(N->getOpcode(),
00530                                       std::make_pair(N->getValueType(0), Ops))];
00531       if (ORN) return ORN;
00532       ORN = N;
00533     }
00534   } else {  
00535     if (N->getOpcode() == ISD::LOAD) {
00536       SDNode *&L = Loads[std::make_pair(N->getOperand(1),
00537                                         std::make_pair(N->getOperand(0),
00538                                                        N->getValueType(0)))];
00539       if (L) return L;
00540       L = N;
00541     } else {
00542       // Remove the node from the ArbitraryNodes map.
00543       std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end());
00544       std::vector<SDOperand>     Ops(N->op_begin(), N->op_end());
00545       SDNode *&AN = ArbitraryNodes[std::make_pair(N->getOpcode(),
00546                                                   std::make_pair(RV, Ops))];
00547       if (AN) return AN;
00548       AN = N;
00549     }
00550   }
00551   return 0;
00552 }
00553 
00554 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
00555 /// were replaced with those specified.  If this node is never memoized, 
00556 /// return null, otherwise return a pointer to the slot it would take.  If a
00557 /// node already exists with these operands, the slot will be non-null.
00558 SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op) {
00559   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
00560     return 0;    // Never add these nodes.
00561   
00562   // Check that remaining values produced are not flags.
00563   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
00564     if (N->getValueType(i) == MVT::Flag)
00565       return 0;   // Never CSE anything that produces a flag.
00566   
00567   if (N->getNumValues() == 1) {
00568     return &UnaryOps[std::make_pair(N->getOpcode(),
00569                                     std::make_pair(Op, N->getValueType(0)))];
00570   } else {  
00571     // Remove the node from the ArbitraryNodes map.
00572     std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end());
00573     std::vector<SDOperand> Ops;
00574     Ops.push_back(Op);
00575     return &ArbitraryNodes[std::make_pair(N->getOpcode(),
00576                                           std::make_pair(RV, Ops))];
00577   }
00578   return 0;
00579 }
00580 
00581 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
00582 /// were replaced with those specified.  If this node is never memoized, 
00583 /// return null, otherwise return a pointer to the slot it would take.  If a
00584 /// node already exists with these operands, the slot will be non-null.
00585 SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, 
00586                                             SDOperand Op1, SDOperand Op2) {
00587   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
00588     return 0;    // Never add these nodes.
00589   
00590   // Check that remaining values produced are not flags.
00591   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
00592     if (N->getValueType(i) == MVT::Flag)
00593       return 0;   // Never CSE anything that produces a flag.
00594   
00595   if (N->getNumValues() == 1) {
00596     return &BinaryOps[std::make_pair(N->getOpcode(),
00597                                      std::make_pair(Op1, Op2))];
00598   } else {  
00599     std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end());
00600     std::vector<SDOperand> Ops;
00601     Ops.push_back(Op1);
00602     Ops.push_back(Op2);
00603     return &ArbitraryNodes[std::make_pair(N->getOpcode(),
00604                                           std::make_pair(RV, Ops))];
00605   }
00606   return 0;
00607 }
00608 
00609 
00610 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
00611 /// were replaced with those specified.  If this node is never memoized, 
00612 /// return null, otherwise return a pointer to the slot it would take.  If a
00613 /// node already exists with these operands, the slot will be non-null.
00614 SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, 
00615                                             const std::vector<SDOperand> &Ops) {
00616   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
00617     return 0;    // Never add these nodes.
00618   
00619   // Check that remaining values produced are not flags.
00620   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
00621     if (N->getValueType(i) == MVT::Flag)
00622       return 0;   // Never CSE anything that produces a flag.
00623   
00624   if (N->getNumValues() == 1) {
00625     if (N->getNumOperands() == 1) {
00626       return &UnaryOps[std::make_pair(N->getOpcode(),
00627                                       std::make_pair(Ops[0],
00628                                                      N->getValueType(0)))];
00629     } else if (N->getNumOperands() == 2) {
00630       return &BinaryOps[std::make_pair(N->getOpcode(),
00631                                        std::make_pair(Ops[0], Ops[1]))];
00632     } else {
00633       return &OneResultNodes[std::make_pair(N->getOpcode(),
00634                                             std::make_pair(N->getValueType(0),
00635                                                            Ops))];
00636     }
00637   } else {  
00638     if (N->getOpcode() == ISD::LOAD) {
00639       return &Loads[std::make_pair(Ops[1],
00640                                    std::make_pair(Ops[0], N->getValueType(0)))];
00641     } else {
00642       std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end());
00643       return &ArbitraryNodes[std::make_pair(N->getOpcode(),
00644                                             std::make_pair(RV, Ops))];
00645     }
00646   }
00647   return 0;
00648 }
00649 
00650 
00651 SelectionDAG::~SelectionDAG() {
00652   while (!AllNodes.empty()) {
00653     SDNode *N = AllNodes.begin();
00654     delete [] N->OperandList;
00655     N->OperandList = 0;
00656     N->NumOperands = 0;
00657     AllNodes.pop_front();
00658   }
00659 }
00660 
00661 SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) {
00662   if (Op.getValueType() == VT) return Op;
00663   int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT));
00664   return getNode(ISD::AND, Op.getValueType(), Op,
00665                  getConstant(Imm, Op.getValueType()));
00666 }
00667 
00668 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) {
00669   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
00670   assert(!MVT::isVector(VT) && "Cannot create Vector ConstantSDNodes!");
00671   
00672   // Mask out any bits that are not valid for this constant.
00673   if (VT != MVT::i64)
00674     Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
00675 
00676   SDNode *&N = Constants[std::make_pair(Val, VT)];
00677   if (N) return SDOperand(N, 0);
00678   N = new ConstantSDNode(false, Val, VT);
00679   AllNodes.push_back(N);
00680   return SDOperand(N, 0);
00681 }
00682 
00683 SDOperand SelectionDAG::getString(const std::string &Val) {
00684   StringSDNode *&N = StringNodes[Val];
00685   if (!N) {
00686     N = new StringSDNode(Val);
00687     AllNodes.push_back(N);
00688   }
00689   return SDOperand(N, 0);
00690 }
00691 
00692 SDOperand SelectionDAG::getTargetConstant(uint64_t Val, MVT::ValueType VT) {
00693   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
00694   // Mask out any bits that are not valid for this constant.
00695   if (VT != MVT::i64)
00696     Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
00697   
00698   SDNode *&N = TargetConstants[std::make_pair(Val, VT)];
00699   if (N) return SDOperand(N, 0);
00700   N = new ConstantSDNode(true, Val, VT);
00701   AllNodes.push_back(N);
00702   return SDOperand(N, 0);
00703 }
00704 
00705 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) {
00706   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
00707   if (VT == MVT::f32)
00708     Val = (float)Val;  // Mask out extra precision.
00709 
00710   // Do the map lookup using the actual bit pattern for the floating point
00711   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
00712   // we don't have issues with SNANs.
00713   SDNode *&N = ConstantFPs[std::make_pair(DoubleToBits(Val), VT)];
00714   if (N) return SDOperand(N, 0);
00715   N = new ConstantFPSDNode(false, Val, VT);
00716   AllNodes.push_back(N);
00717   return SDOperand(N, 0);
00718 }
00719 
00720 SDOperand SelectionDAG::getTargetConstantFP(double Val, MVT::ValueType VT) {
00721   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
00722   if (VT == MVT::f32)
00723     Val = (float)Val;  // Mask out extra precision.
00724   
00725   // Do the map lookup using the actual bit pattern for the floating point
00726   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
00727   // we don't have issues with SNANs.
00728   SDNode *&N = TargetConstantFPs[std::make_pair(DoubleToBits(Val), VT)];
00729   if (N) return SDOperand(N, 0);
00730   N = new ConstantFPSDNode(true, Val, VT);
00731   AllNodes.push_back(N);
00732   return SDOperand(N, 0);
00733 }
00734 
00735 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
00736                                          MVT::ValueType VT, int offset) {
00737   SDNode *&N = GlobalValues[std::make_pair(GV, offset)];
00738   if (N) return SDOperand(N, 0);
00739   N = new GlobalAddressSDNode(false, GV, VT, offset);
00740   AllNodes.push_back(N);
00741   return SDOperand(N, 0);
00742 }
00743 
00744 SDOperand SelectionDAG::getTargetGlobalAddress(const GlobalValue *GV,
00745                                                MVT::ValueType VT, int offset) {
00746   SDNode *&N = TargetGlobalValues[std::make_pair(GV, offset)];
00747   if (N) return SDOperand(N, 0);
00748   N = new GlobalAddressSDNode(true, GV, VT, offset);
00749   AllNodes.push_back(N);
00750   return SDOperand(N, 0);
00751 }
00752 
00753 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) {
00754   SDNode *&N = FrameIndices[FI];
00755   if (N) return SDOperand(N, 0);
00756   N = new FrameIndexSDNode(FI, VT, false);
00757   AllNodes.push_back(N);
00758   return SDOperand(N, 0);
00759 }
00760 
00761 SDOperand SelectionDAG::getTargetFrameIndex(int FI, MVT::ValueType VT) {
00762   SDNode *&N = TargetFrameIndices[FI];
00763   if (N) return SDOperand(N, 0);
00764   N = new FrameIndexSDNode(FI, VT, true);
00765   AllNodes.push_back(N);
00766   return SDOperand(N, 0);
00767 }
00768 
00769 SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT) {
00770   SDNode *&N = JumpTableIndices[JTI];
00771   if (N) return SDOperand(N, 0);
00772   N = new JumpTableSDNode(JTI, VT, false);
00773   AllNodes.push_back(N);
00774   return SDOperand(N, 0);
00775 }
00776 
00777 SDOperand SelectionDAG::getTargetJumpTable(int JTI, MVT::ValueType VT) {
00778   SDNode *&N = TargetJumpTableIndices[JTI];
00779   if (N) return SDOperand(N, 0);
00780   N = new JumpTableSDNode(JTI, VT, true);
00781   AllNodes.push_back(N);
00782   return SDOperand(N, 0);
00783 }
00784 
00785 SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT,
00786                                         unsigned Alignment,  int Offset) {
00787   SDNode *&N = ConstantPoolIndices[std::make_pair(C,
00788                                             std::make_pair(Offset, Alignment))];
00789   if (N) return SDOperand(N, 0);
00790   N = new ConstantPoolSDNode(false, C, VT, Offset, Alignment);
00791   AllNodes.push_back(N);
00792   return SDOperand(N, 0);
00793 }
00794 
00795 SDOperand SelectionDAG::getTargetConstantPool(Constant *C, MVT::ValueType VT,
00796                                              unsigned Alignment,  int Offset) {
00797   SDNode *&N = TargetConstantPoolIndices[std::make_pair(C,
00798                                             std::make_pair(Offset, Alignment))];
00799   if (N) return SDOperand(N, 0);
00800   N = new ConstantPoolSDNode(true, C, VT, Offset, Alignment);
00801   AllNodes.push_back(N);
00802   return SDOperand(N, 0);
00803 }
00804 
00805 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
00806   SDNode *&N = BBNodes[MBB];
00807   if (N) return SDOperand(N, 0);
00808   N = new BasicBlockSDNode(MBB);
00809   AllNodes.push_back(N);
00810   return SDOperand(N, 0);
00811 }
00812 
00813 SDOperand SelectionDAG::getValueType(MVT::ValueType VT) {
00814   if ((unsigned)VT >= ValueTypeNodes.size())
00815     ValueTypeNodes.resize(VT+1);
00816   if (ValueTypeNodes[VT] == 0) {
00817     ValueTypeNodes[VT] = new VTSDNode(VT);
00818     AllNodes.push_back(ValueTypeNodes[VT]);
00819   }
00820 
00821   return SDOperand(ValueTypeNodes[VT], 0);
00822 }
00823 
00824 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
00825   SDNode *&N = ExternalSymbols[Sym];
00826   if (N) return SDOperand(N, 0);
00827   N = new ExternalSymbolSDNode(false, Sym, VT);
00828   AllNodes.push_back(N);
00829   return SDOperand(N, 0);
00830 }
00831 
00832 SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym,
00833                                                 MVT::ValueType VT) {
00834   SDNode *&N = TargetExternalSymbols[Sym];
00835   if (N) return SDOperand(N, 0);
00836   N = new ExternalSymbolSDNode(true, Sym, VT);
00837   AllNodes.push_back(N);
00838   return SDOperand(N, 0);
00839 }
00840 
00841 SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
00842   if ((unsigned)Cond >= CondCodeNodes.size())
00843     CondCodeNodes.resize(Cond+1);
00844   
00845   if (CondCodeNodes[Cond] == 0) {
00846     CondCodeNodes[Cond] = new CondCodeSDNode(Cond);
00847     AllNodes.push_back(CondCodeNodes[Cond]);
00848   }
00849   return SDOperand(CondCodeNodes[Cond], 0);
00850 }
00851 
00852 SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) {
00853   RegisterSDNode *&Reg = RegNodes[std::make_pair(RegNo, VT)];
00854   if (!Reg) {
00855     Reg = new RegisterSDNode(RegNo, VT);
00856     AllNodes.push_back(Reg);
00857   }
00858   return SDOperand(Reg, 0);
00859 }
00860 
00861 SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1,
00862                                       SDOperand N2, ISD::CondCode Cond) {
00863   // These setcc operations always fold.
00864   switch (Cond) {
00865   default: break;
00866   case ISD::SETFALSE:
00867   case ISD::SETFALSE2: return getConstant(0, VT);
00868   case ISD::SETTRUE:
00869   case ISD::SETTRUE2:  return getConstant(1, VT);
00870     
00871   case ISD::SETOEQ:
00872   case ISD::SETOGT:
00873   case ISD::SETOGE:
00874   case ISD::SETOLT:
00875   case ISD::SETOLE:
00876   case ISD::SETONE:
00877   case ISD::SETO:
00878   case ISD::SETUO:
00879   case ISD::SETUEQ:
00880   case ISD::SETUNE:
00881     assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!");
00882     break;
00883   }
00884 
00885   if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
00886     uint64_t C2 = N2C->getValue();
00887     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
00888       uint64_t C1 = N1C->getValue();
00889 
00890       // Sign extend the operands if required
00891       if (ISD::isSignedIntSetCC(Cond)) {
00892         C1 = N1C->getSignExtended();
00893         C2 = N2C->getSignExtended();
00894       }
00895 
00896       switch (Cond) {
00897       default: assert(0 && "Unknown integer setcc!");
00898       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
00899       case ISD::SETNE:  return getConstant(C1 != C2, VT);
00900       case ISD::SETULT: return getConstant(C1 <  C2, VT);
00901       case ISD::SETUGT: return getConstant(C1 >  C2, VT);
00902       case ISD::SETULE: return getConstant(C1 <= C2, VT);
00903       case ISD::SETUGE: return getConstant(C1 >= C2, VT);
00904       case ISD::SETLT:  return getConstant((int64_t)C1 <  (int64_t)C2, VT);
00905       case ISD::SETGT:  return getConstant((int64_t)C1 >  (int64_t)C2, VT);
00906       case ISD::SETLE:  return getConstant((int64_t)C1 <= (int64_t)C2, VT);
00907       case ISD::SETGE:  return getConstant((int64_t)C1 >= (int64_t)C2, VT);
00908       }
00909     } else {
00910       // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
00911       if (N1.getOpcode() == ISD::ZERO_EXTEND) {
00912         unsigned InSize = MVT::getSizeInBits(N1.getOperand(0).getValueType());
00913 
00914         // If the comparison constant has bits in the upper part, the
00915         // zero-extended value could never match.
00916         if (C2 & (~0ULL << InSize)) {
00917           unsigned VSize = MVT::getSizeInBits(N1.getValueType());
00918           switch (Cond) {
00919           case ISD::SETUGT:
00920           case ISD::SETUGE:
00921           case ISD::SETEQ: return getConstant(0, VT);
00922           case ISD::SETULT:
00923           case ISD::SETULE:
00924           case ISD::SETNE: return getConstant(1, VT);
00925           case ISD::SETGT:
00926           case ISD::SETGE:
00927             // True if the sign bit of C2 is set.
00928             return getConstant((C2 & (1ULL << VSize)) != 0, VT);
00929           case ISD::SETLT:
00930           case ISD::SETLE:
00931             // True if the sign bit of C2 isn't set.
00932             return getConstant((C2 & (1ULL << VSize)) == 0, VT);
00933           default:
00934             break;
00935           }
00936         }
00937 
00938         // Otherwise, we can perform the comparison with the low bits.
00939         switch (Cond) {
00940         case ISD::SETEQ:
00941         case ISD::SETNE:
00942         case ISD::SETUGT:
00943         case ISD::SETUGE:
00944         case ISD::SETULT:
00945         case ISD::SETULE:
00946           return getSetCC(VT, N1.getOperand(0),
00947                           getConstant(C2, N1.getOperand(0).getValueType()),
00948                           Cond);
00949         default:
00950           break;   // todo, be more careful with signed comparisons
00951         }
00952       } else if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG &&
00953                  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
00954         MVT::ValueType ExtSrcTy = cast<VTSDNode>(N1.getOperand(1))->getVT();
00955         unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy);
00956         MVT::ValueType ExtDstTy = N1.getValueType();
00957         unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy);
00958 
00959         // If the extended part has any inconsistent bits, it cannot ever
00960         // compare equal.  In other words, they have to be all ones or all
00961         // zeros.
00962         uint64_t ExtBits =
00963           (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
00964         if ((C2 & ExtBits) != 0 && (C2 & ExtBits) != ExtBits)
00965           return getConstant(Cond == ISD::SETNE, VT);
00966         
00967         // Otherwise, make this a use of a zext.
00968         return getSetCC(VT, getZeroExtendInReg(N1.getOperand(0), ExtSrcTy),
00969                         getConstant(C2 & (~0ULL>>(64-ExtSrcTyBits)), ExtDstTy),
00970                         Cond);
00971       }
00972 
00973       uint64_t MinVal, MaxVal;
00974       unsigned OperandBitSize = MVT::getSizeInBits(N2C->getValueType(0));
00975       if (ISD::isSignedIntSetCC(Cond)) {
00976         MinVal = 1ULL << (OperandBitSize-1);
00977         if (OperandBitSize != 1)   // Avoid X >> 64, which is undefined.
00978           MaxVal = ~0ULL >> (65-OperandBitSize);
00979         else
00980           MaxVal = 0;
00981       } else {
00982         MinVal = 0;
00983         MaxVal = ~0ULL >> (64-OperandBitSize);
00984       }
00985 
00986       // Canonicalize GE/LE comparisons to use GT/LT comparisons.
00987       if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
00988         if (C2 == MinVal) return getConstant(1, VT);   // X >= MIN --> true
00989         --C2;                                          // X >= C1 --> X > (C1-1)
00990         return getSetCC(VT, N1, getConstant(C2, N2.getValueType()),
00991                         (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
00992       }
00993 
00994       if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
00995         if (C2 == MaxVal) return getConstant(1, VT);   // X <= MAX --> true
00996         ++C2;                                          // X <= C1 --> X < (C1+1)
00997         return getSetCC(VT, N1, getConstant(C2, N2.getValueType()),
00998                         (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
00999       }
01000 
01001       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal)
01002         return getConstant(0, VT);      // X < MIN --> false
01003 
01004       // Canonicalize setgt X, Min --> setne X, Min
01005       if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MinVal)
01006         return getSetCC(VT, N1, N2, ISD::SETNE);
01007 
01008       // If we have setult X, 1, turn it into seteq X, 0
01009       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal+1)
01010         return getSetCC(VT, N1, getConstant(MinVal, N1.getValueType()),
01011                         ISD::SETEQ);
01012       // If we have setugt X, Max-1, turn it into seteq X, Max
01013       else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MaxVal-1)
01014         return getSetCC(VT, N1, getConstant(MaxVal, N1.getValueType()),
01015                         ISD::SETEQ);
01016 
01017       // If we have "setcc X, C1", check to see if we can shrink the immediate
01018       // by changing cc.
01019 
01020       // SETUGT X, SINTMAX  -> SETLT X, 0
01021       if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
01022           C2 == (~0ULL >> (65-OperandBitSize)))
01023         return getSetCC(VT, N1, getConstant(0, N2.getValueType()), ISD::SETLT);
01024 
01025       // FIXME: Implement the rest of these.
01026 
01027 
01028       // Fold bit comparisons when we can.
01029       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
01030           VT == N1.getValueType() && N1.getOpcode() == ISD::AND)
01031         if (ConstantSDNode *AndRHS =
01032                     dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
01033           if (Cond == ISD::SETNE && C2 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
01034             // Perform the xform if the AND RHS is a single bit.
01035             if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) {
01036               return getNode(ISD::SRL, VT, N1,
01037                              getConstant(Log2_64(AndRHS->getValue()),
01038                                                    TLI.getShiftAmountTy()));
01039             }
01040           } else if (Cond == ISD::SETEQ && C2 == AndRHS->getValue()) {
01041             // (X & 8) == 8  -->  (X & 8) >> 3
01042             // Perform the xform if C2 is a single bit.
01043             if ((C2 & (C2-1)) == 0) {
01044               return getNode(ISD::SRL, VT, N1,
01045                              getConstant(Log2_64(C2),TLI.getShiftAmountTy()));
01046             }
01047           }
01048         }
01049     }
01050   } else if (isa<ConstantSDNode>(N1.Val)) {
01051       // Ensure that the constant occurs on the RHS.
01052     return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
01053   }
01054 
01055   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
01056     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
01057       double C1 = N1C->getValue(), C2 = N2C->getValue();
01058 
01059       switch (Cond) {
01060       default: break; // FIXME: Implement the rest of these!
01061       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
01062       case ISD::SETNE:  return getConstant(C1 != C2, VT);
01063       case ISD::SETLT:  return getConstant(C1 < C2, VT);
01064       case ISD::SETGT:  return getConstant(C1 > C2, VT);
01065       case ISD::SETLE:  return getConstant(C1 <= C2, VT);
01066       case ISD::SETGE:  return getConstant(C1 >= C2, VT);
01067       }
01068     } else {
01069       // Ensure that the constant occurs on the RHS.
01070       return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
01071     }
01072 
01073   // Could not fold it.
01074   return SDOperand();
01075 }
01076 
01077 /// getNode - Gets or creates the specified node.
01078 ///
01079 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
01080   SDNode *&N = NullaryOps[std::make_pair(Opcode, VT)];
01081   if (!N) {
01082     N = new SDNode(Opcode, VT);
01083     AllNodes.push_back(N);
01084   }
01085   return SDOperand(N, 0);
01086 }
01087 
01088 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
01089                                 SDOperand Operand) {
01090   unsigned Tmp1;
01091   // Constant fold unary operations with an integer constant operand.
01092   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
01093     uint64_t Val = C->getValue();
01094     switch (Opcode) {
01095     default: break;
01096     case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
01097     case ISD::ANY_EXTEND:
01098     case ISD::ZERO_EXTEND: return getConstant(Val, VT);
01099     case ISD::TRUNCATE:    return getConstant(Val, VT);
01100     case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
01101     case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
01102     case ISD::BIT_CONVERT:
01103       if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
01104         return getConstantFP(BitsToFloat(Val), VT);
01105       else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
01106         return getConstantFP(BitsToDouble(Val), VT);
01107       break;
01108     case ISD::BSWAP:
01109       switch(VT) {
01110       default: assert(0 && "Invalid bswap!"); break;
01111       case MVT::i16: return getConstant(ByteSwap_16((unsigned short)Val), VT);
01112       case MVT::i32: return getConstant(ByteSwap_32((unsigned)Val), VT);
01113       case MVT::i64: return getConstant(ByteSwap_64(Val), VT);
01114       }
01115       break;
01116     case ISD::CTPOP:
01117       switch(VT) {
01118       default: assert(0 && "Invalid ctpop!"); break;
01119       case MVT::i1: return getConstant(Val != 0, VT);
01120       case MVT::i8: 
01121         Tmp1 = (unsigned)Val & 0xFF;
01122         return getConstant(CountPopulation_32(Tmp1), VT);
01123       case MVT::i16:
01124         Tmp1 = (unsigned)Val & 0xFFFF;
01125         return getConstant(CountPopulation_32(Tmp1), VT);
01126       case MVT::i32:
01127         return getConstant(CountPopulation_32((unsigned)Val), VT);
01128       case MVT::i64:
01129         return getConstant(CountPopulation_64(Val), VT);
01130       }
01131     case ISD::CTLZ:
01132       switch(VT) {
01133       default: assert(0 && "Invalid ctlz!"); break;
01134       case MVT::i1: return getConstant(Val == 0, VT);
01135       case MVT::i8: 
01136         Tmp1 = (unsigned)Val & 0xFF;
01137         return getConstant(CountLeadingZeros_32(Tmp1)-24, VT);
01138       case MVT::i16:
01139         Tmp1 = (unsigned)Val & 0xFFFF;
01140         return getConstant(CountLeadingZeros_32(Tmp1)-16, VT);
01141       case MVT::i32:
01142         return getConstant(CountLeadingZeros_32((unsigned)Val), VT);
01143       case MVT::i64:
01144         return getConstant(CountLeadingZeros_64(Val), VT);
01145       }
01146     case ISD::CTTZ:
01147       switch(VT) {
01148       default: assert(0 && "Invalid cttz!"); break;
01149       case MVT::i1: return getConstant(Val == 0, VT);
01150       case MVT::i8: 
01151         Tmp1 = (unsigned)Val | 0x100;
01152         return getConstant(CountTrailingZeros_32(Tmp1), VT);
01153       case MVT::i16:
01154         Tmp1 = (unsigned)Val | 0x10000;
01155         return getConstant(CountTrailingZeros_32(Tmp1), VT);
01156       case MVT::i32:
01157         return getConstant(CountTrailingZeros_32((unsigned)Val), VT);
01158       case MVT::i64:
01159         return getConstant(CountTrailingZeros_64(Val), VT);
01160       }
01161     }
01162   }
01163 
01164   // Constant fold unary operations with an floating point constant operand.
01165   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
01166     switch (Opcode) {
01167     case ISD::FNEG:
01168       return getConstantFP(-C->getValue(), VT);
01169     case ISD::FABS:
01170       return getConstantFP(fabs(C->getValue()), VT);
01171     case ISD::FP_ROUND:
01172     case ISD::FP_EXTEND:
01173       return getConstantFP(C->getValue(), VT);
01174     case ISD::FP_TO_SINT:
01175       return getConstant((int64_t)C->getValue(), VT);
01176     case ISD::FP_TO_UINT:
01177       return getConstant((uint64_t)C->getValue(), VT);
01178     case ISD::BIT_CONVERT:
01179       if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
01180         return getConstant(FloatToBits(C->getValue()), VT);
01181       else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
01182         return getConstant(DoubleToBits(C->getValue()), VT);
01183       break;
01184     }
01185 
01186   unsigned OpOpcode = Operand.Val->getOpcode();
01187   switch (Opcode) {
01188   case ISD::TokenFactor:
01189     return Operand;         // Factor of one node?  No factor.
01190   case ISD::SIGN_EXTEND:
01191     if (Operand.getValueType() == VT) return Operand;   // noop extension
01192     assert(Operand.getValueType() < VT && "Invalid sext node, dst < src!");
01193     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
01194       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
01195     break;
01196   case ISD::ZERO_EXTEND:
01197     if (Operand.getValueType() == VT) return Operand;   // noop extension
01198     assert(Operand.getValueType() < VT && "Invalid zext node, dst < src!");
01199     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
01200       return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
01201     break;
01202   case ISD::ANY_EXTEND:
01203     if (Operand.getValueType() == VT) return Operand;   // noop extension
01204     assert(Operand.getValueType() < VT && "Invalid anyext node, dst < src!");
01205     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND)
01206       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
01207       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
01208     break;
01209   case ISD::TRUNCATE:
01210     if (Operand.getValueType() == VT) return Operand;   // noop truncate
01211     assert(Operand.getValueType() > VT && "Invalid truncate node, src < dst!");
01212     if (OpOpcode == ISD::TRUNCATE)
01213       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
01214     else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
01215              OpOpcode == ISD::ANY_EXTEND) {
01216       // If the source is smaller than the dest, we still need an extend.
01217       if (Operand.Val->getOperand(0).getValueType() < VT)
01218         return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
01219       else if (Operand.Val->getOperand(0).getValueType() > VT)
01220         return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
01221       else
01222         return Operand.Val->getOperand(0);
01223     }
01224     break;
01225   case ISD::BIT_CONVERT:
01226     // Basic sanity checking.
01227     assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType())
01228            && "Cannot BIT_CONVERT between two different types!");
01229     if (VT == Operand.getValueType()) return Operand;  // noop conversion.
01230     if (OpOpcode == ISD::BIT_CONVERT)  // bitconv(bitconv(x)) -> bitconv(x)
01231       return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0));
01232     if (OpOpcode == ISD::UNDEF)
01233       return getNode(ISD::UNDEF, VT);
01234     break;
01235   case ISD::SCALAR_TO_VECTOR:
01236     assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) &&
01237            MVT::getVectorBaseType(VT) == Operand.getValueType() &&
01238            "Illegal SCALAR_TO_VECTOR node!");
01239     break;
01240   case ISD::FNEG:
01241     if (OpOpcode == ISD::FSUB)   // -(X-Y) -> (Y-X)
01242       return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1),
01243                      Operand.Val->getOperand(0));
01244     if (OpOpcode == ISD::FNEG)  // --X -> X
01245       return Operand.Val->getOperand(0);
01246     break;
01247   case ISD::FABS:
01248     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
01249       return getNode(ISD::FABS, VT, Operand.Val->getOperand(0));
01250     break;
01251   }
01252 
01253   SDNode *N;
01254   if (VT != MVT::Flag) { // Don't CSE flag producing nodes
01255     SDNode *&E = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))];
01256     if (E) return SDOperand(E, 0);
01257     E = N = new SDNode(Opcode, Operand);
01258   } else {
01259     N = new SDNode(Opcode, Operand);
01260   }
01261   N->setValueTypes(VT);
01262   AllNodes.push_back(N);
01263   return SDOperand(N, 0);
01264 }
01265 
01266 
01267 
01268 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
01269                                 SDOperand N1, SDOperand N2) {
01270 #ifndef NDEBUG
01271   switch (Opcode) {
01272   case ISD::TokenFactor:
01273     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
01274            N2.getValueType() == MVT::Other && "Invalid token factor!");
01275     break;
01276   case ISD::AND:
01277   case ISD::OR:
01278   case ISD::XOR:
01279   case ISD::UDIV:
01280   case ISD::UREM:
01281   case ISD::MULHU:
01282   case ISD::MULHS:
01283     assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
01284     // fall through
01285   case ISD::ADD:
01286   case ISD::SUB:
01287   case ISD::MUL:
01288   case ISD::SDIV:
01289   case ISD::SREM:
01290     assert(MVT::isInteger(N1.getValueType()) && "Should use F* for FP ops");
01291     // fall through.
01292   case ISD::FADD:
01293   case ISD::FSUB:
01294   case ISD::FMUL:
01295   case ISD::FDIV:
01296   case ISD::FREM:
01297     assert(N1.getValueType() == N2.getValueType() &&
01298            N1.getValueType() == VT && "Binary operator types must match!");
01299     break;
01300   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
01301     assert(N1.getValueType() == VT &&
01302            MVT::isFloatingPoint(N1.getValueType()) && 
01303            MVT::isFloatingPoint(N2.getValueType()) &&
01304            "Invalid FCOPYSIGN!");
01305     break;
01306   case ISD::SHL:
01307   case ISD::SRA:
01308   case ISD::SRL:
01309   case ISD::ROTL:
01310   case ISD::ROTR:
01311     assert(VT == N1.getValueType() &&
01312            "Shift operators return type must be the same as their first arg");
01313     assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
01314            VT != MVT::i1 && "Shifts only work on integers");
01315     break;
01316   case ISD::FP_ROUND_INREG: {
01317     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
01318     assert(VT == N1.getValueType() && "Not an inreg round!");
01319     assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
01320            "Cannot FP_ROUND_INREG integer types");
01321     assert(EVT <= VT && "Not rounding down!");
01322     break;
01323   }
01324   case ISD::AssertSext:
01325   case ISD::AssertZext:
01326   case ISD::SIGN_EXTEND_INREG: {
01327     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
01328     assert(VT == N1.getValueType() && "Not an inreg extend!");
01329     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
01330            "Cannot *_EXTEND_INREG FP types");
01331     assert(EVT <= VT && "Not extending!");
01332   }
01333 
01334   default: break;
01335   }
01336 #endif
01337 
01338   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
01339   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
01340   if (N1C) {
01341     if (Opcode == ISD::SIGN_EXTEND_INREG) {
01342       int64_t Val = N1C->getValue();
01343       unsigned FromBits = MVT::getSizeInBits(cast<VTSDNode>(N2)->getVT());
01344       Val <<= 64-FromBits;
01345       Val >>= 64-FromBits;
01346       return getConstant(Val, VT);
01347     }
01348     
01349     if (N2C) {
01350       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
01351       switch (Opcode) {
01352       case ISD::ADD: return getConstant(C1 + C2, VT);
01353       case ISD::SUB: return getConstant(C1 - C2, VT);
01354       case ISD::MUL: return getConstant(C1 * C2, VT);
01355       case ISD::UDIV:
01356         if (C2) return getConstant(C1 / C2, VT);
01357         break;
01358       case ISD::UREM :
01359         if (C2) return getConstant(C1 % C2, VT);
01360         break;
01361       case ISD::SDIV :
01362         if (C2) return getConstant(N1C->getSignExtended() /
01363                                    N2C->getSignExtended(), VT);
01364         break;
01365       case ISD::SREM :
01366         if (C2) return getConstant(N1C->getSignExtended() %
01367                                    N2C->getSignExtended(), VT);
01368         break;
01369       case ISD::AND  : return getConstant(C1 & C2, VT);
01370       case ISD::OR   : return getConstant(C1 | C2, VT);
01371       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
01372       case ISD::SHL  : return getConstant(C1 << C2, VT);
01373       case ISD::SRL  : return getConstant(C1 >> C2, VT);
01374       case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
01375       case ISD::ROTL : 
01376         return getConstant((C1 << C2) | (C1 >> (MVT::getSizeInBits(VT) - C2)),
01377                            VT);
01378       case ISD::ROTR : 
01379         return getConstant((C1 >> C2) | (C1 << (MVT::getSizeInBits(VT) - C2)), 
01380                            VT);
01381       default: break;
01382       }
01383     } else {      // Cannonicalize constant to RHS if commutative
01384       if (isCommutativeBinOp(Opcode)) {
01385         std::swap(N1C, N2C);
01386         std::swap(N1, N2);
01387       }
01388     }
01389   }
01390 
01391   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
01392   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
01393   if (N1CFP) {
01394     if (N2CFP) {
01395       double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
01396       switch (Opcode) {
01397       case ISD::FADD: return getConstantFP(C1 + C2, VT);
01398       case ISD::FSUB: return getConstantFP(C1 - C2, VT);
01399       case ISD::FMUL: return getConstantFP(C1 * C2, VT);
01400       case ISD::FDIV:
01401         if (C2) return getConstantFP(C1 / C2, VT);
01402         break;
01403       case ISD::FREM :
01404         if (C2) return getConstantFP(fmod(C1, C2), VT);
01405         break;
01406       case ISD::FCOPYSIGN: {
01407         union {
01408           double   F;
01409           uint64_t I;
01410         } u1;
01411         union {
01412           double  F;
01413           int64_t I;
01414         } u2;
01415         u1.F = C1;
01416         u2.F = C2;
01417         if (u2.I < 0)  // Sign bit of RHS set?
01418           u1.I |= 1ULL << 63;      // Set the sign bit of the LHS.
01419         else 
01420           u1.I &= (1ULL << 63)-1;  // Clear the sign bit of the LHS.
01421         return getConstantFP(u1.F, VT);
01422       }
01423       default: break;
01424       }
01425     } else {      // Cannonicalize constant to RHS if commutative
01426       if (isCommutativeBinOp(Opcode)) {
01427         std::swap(N1CFP, N2CFP);
01428         std::swap(N1, N2);
01429       }
01430     }
01431   }
01432   
01433   // Canonicalize an UNDEF to the RHS, even over a constant.
01434   if (N1.getOpcode() == ISD::UNDEF) {
01435     if (isCommutativeBinOp(Opcode)) {
01436       std::swap(N1, N2);
01437     } else {
01438       switch (Opcode) {
01439       case ISD::FP_ROUND_INREG:
01440       case ISD::SIGN_EXTEND_INREG:
01441       case ISD::SUB:
01442       case ISD::FSUB:
01443       case ISD::FDIV:
01444       case ISD::FREM:
01445       case ISD::SRA:
01446         return N1;     // fold op(undef, arg2) -> undef
01447       case ISD::UDIV:
01448       case ISD::SDIV:
01449       case ISD::UREM:
01450       case ISD::SREM:
01451       case ISD::SRL:
01452       case ISD::SHL:
01453         return getConstant(0, VT);    // fold op(undef, arg2) -> 0
01454       }
01455     }
01456   }
01457   
01458   // Fold a bunch of operators when the RHS is undef. 
01459   if (N2.getOpcode() == ISD::UNDEF) {
01460     switch (Opcode) {
01461     case ISD::ADD:
01462     case ISD::SUB:
01463     case ISD::FADD:
01464     case ISD::FSUB:
01465     case ISD::FMUL:
01466     case ISD::FDIV:
01467     case ISD::FREM:
01468     case ISD::UDIV:
01469     case ISD::SDIV:
01470     case ISD::UREM:
01471     case ISD::SREM:
01472     case ISD::XOR:
01473       return N2;       // fold op(arg1, undef) -> undef
01474     case ISD::MUL: 
01475     case ISD::AND:
01476     case ISD::SRL:
01477     case ISD::SHL:
01478       return getConstant(0, VT);  // fold op(arg1, undef) -> 0
01479     case ISD::OR:
01480       return getConstant(MVT::getIntVTBitMask(VT), VT);
01481     case ISD::SRA:
01482       return N1;
01483     }
01484   }
01485 
01486   // Finally, fold operations that do not require constants.
01487   switch (Opcode) {
01488   case ISD::FP_ROUND_INREG:
01489     if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
01490     break;
01491   case ISD::SIGN_EXTEND_INREG: {
01492     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
01493     if (EVT == VT) return N1;  // Not actually extending
01494     break;
01495   }
01496 
01497   // FIXME: figure out how to safely handle things like
01498   // int foo(int x) { return 1 << (x & 255); }
01499   // int bar() { return foo(256); }
01500 #if 0
01501   case ISD::SHL:
01502   case ISD::SRL:
01503   case ISD::SRA:
01504     if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG &&
01505         cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1)
01506       return getNode(Opcode, VT, N1, N2.getOperand(0));
01507     else if (N2.getOpcode() == ISD::AND)
01508       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) {
01509         // If the and is only masking out bits that cannot effect the shift,
01510         // eliminate the and.
01511         unsigned NumBits = MVT::getSizeInBits(VT);
01512         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
01513           return getNode(Opcode, VT, N1, N2.getOperand(0));
01514       }
01515     break;
01516 #endif
01517   }
01518 
01519   // Memoize this node if possible.
01520   SDNode *N;
01521   if (VT != MVT::Flag) {
01522     SDNode *&BON = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))];
01523     if (BON) return SDOperand(BON, 0);
01524 
01525     BON = N = new SDNode(Opcode, N1, N2);
01526   } else {
01527     N = new SDNode(Opcode, N1, N2);
01528   }
01529 
01530   N->setValueTypes(VT);
01531   AllNodes.push_back(N);
01532   return SDOperand(N, 0);
01533 }
01534 
01535 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
01536                                 SDOperand N1, SDOperand N2, SDOperand N3) {
01537   // Perform various simplifications.
01538   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
01539   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
01540   //ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
01541   switch (Opcode) {
01542   case ISD::SETCC: {
01543     // Use SimplifySetCC  to simplify SETCC's.
01544     SDOperand Simp = SimplifySetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get());
01545     if (Simp.Val) return Simp;
01546     break;
01547   }
01548   case ISD::SELECT:
01549     if (N1C)
01550       if (N1C->getValue())
01551         return N2;             // select true, X, Y -> X
01552       else
01553         return N3;             // select false, X, Y -> Y
01554 
01555     if (N2 == N3) return N2;   // select C, X, X -> X
01556     break;
01557   case ISD::BRCOND:
01558     if (N2C)
01559       if (N2C->getValue()) // Unconditional branch
01560         return getNode(ISD::BR, MVT::Other, N1, N3);
01561       else
01562         return N1;         // Never-taken branch
01563     break;
01564   case ISD::VECTOR_SHUFFLE:
01565     assert(VT == N1.getValueType() && VT == N2.getValueType() &&
01566            MVT::isVector(VT) && MVT::isVector(N3.getValueType()) &&
01567            N3.getOpcode() == ISD::BUILD_VECTOR &&
01568            MVT::getVectorNumElements(VT) == N3.getNumOperands() &&
01569            "Illegal VECTOR_SHUFFLE node!");
01570     break;
01571   }
01572 
01573   std::vector<SDOperand> Ops;
01574   Ops.reserve(3);
01575   Ops.push_back(N1);
01576   Ops.push_back(N2);
01577   Ops.push_back(N3);
01578 
01579   // Memoize node if it doesn't produce a flag.
01580   SDNode *N;
01581   if (VT != MVT::Flag) {
01582     SDNode *&E = OneResultNodes[std::make_pair(Opcode,std::make_pair(VT, Ops))];
01583     if (E) return SDOperand(E, 0);
01584     E = N = new SDNode(Opcode, N1, N2, N3);
01585   } else {
01586     N = new SDNode(Opcode, N1, N2, N3);
01587   }
01588   N->setValueTypes(VT);
01589   AllNodes.push_back(N);
01590   return SDOperand(N, 0);
01591 }
01592 
01593 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
01594                                 SDOperand N1, SDOperand N2, SDOperand N3,
01595                                 SDOperand N4) {
01596   std::vector<SDOperand> Ops;
01597   Ops.reserve(4);
01598   Ops.push_back(N1);
01599   Ops.push_back(N2);
01600   Ops.push_back(N3);
01601   Ops.push_back(N4);
01602   return getNode(Opcode, VT, Ops);
01603 }
01604 
01605 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
01606                                 SDOperand N1, SDOperand N2, SDOperand N3,
01607                                 SDOperand N4, SDOperand N5) {
01608   std::vector<SDOperand> Ops;
01609   Ops.reserve(5);
01610   Ops.push_back(N1);
01611   Ops.push_back(N2);
01612   Ops.push_back(N3);
01613   Ops.push_back(N4);
01614   Ops.push_back(N5);
01615   return getNode(Opcode, VT, Ops);
01616 }
01617 
01618 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
01619                                 SDOperand Chain, SDOperand Ptr,
01620                                 SDOperand SV) {
01621   SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))];
01622   if (N) return SDOperand(N, 0);
01623   N = new SDNode(ISD::LOAD, Chain, Ptr, SV);
01624 
01625   // Loads have a token chain.
01626   setNodeValueTypes(N, VT, MVT::Other);
01627   AllNodes.push_back(N);
01628   return SDOperand(N, 0);
01629 }
01630 
01631 SDOperand SelectionDAG::getVecLoad(unsigned Count, MVT::ValueType EVT,
01632                                    SDOperand Chain, SDOperand Ptr,
01633                                    SDOperand SV) {
01634   std::vector<SDOperand> Ops;
01635   Ops.reserve(5);
01636   Ops.push_back(Chain);
01637   Ops.push_back(Ptr);
01638   Ops.push_back(SV);
01639   Ops.push_back(getConstant(Count, MVT::i32));
01640   Ops.push_back(getValueType(EVT));
01641   std::vector<MVT::ValueType> VTs;
01642   VTs.reserve(2);
01643   VTs.push_back(MVT::Vector); VTs.push_back(MVT::Other);  // Add token chain.
01644   return getNode(ISD::VLOAD, VTs, Ops);
01645 }
01646 
01647 SDOperand SelectionDAG::getExtLoad(unsigned Opcode, MVT::ValueType VT,
01648                                    SDOperand Chain, SDOperand Ptr, SDOperand SV,
01649                                    MVT::ValueType EVT) {
01650   std::vector<SDOperand> Ops;
01651   Ops.reserve(4);
01652   Ops.push_back(Chain);
01653   Ops.push_back(Ptr);
01654   Ops.push_back(SV);
01655   Ops.push_back(getValueType(EVT));
01656   std::vector<MVT::ValueType> VTs;
01657   VTs.reserve(2);
01658   VTs.push_back(VT); VTs.push_back(MVT::Other);  // Add token chain.
01659   return getNode(Opcode, VTs, Ops);
01660 }
01661 
01662 SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) {
01663   assert((!V || isa<PointerType>(V->getType())) &&
01664          "SrcValue is not a pointer?");
01665   SDNode *&N = ValueNodes[std::make_pair(V, Offset)];
01666   if (N) return SDOperand(N, 0);
01667 
01668   N = new SrcValueSDNode(V, Offset);
01669   AllNodes.push_back(N);
01670   return SDOperand(N, 0);
01671 }
01672 
01673 SDOperand SelectionDAG::getVAArg(MVT::ValueType VT,
01674                                  SDOperand Chain, SDOperand Ptr,
01675                                  SDOperand SV) {
01676   std::vector<SDOperand> Ops;
01677   Ops.reserve(3);
01678   Ops.push_back(Chain);
01679   Ops.push_back(Ptr);
01680   Ops.push_back(SV);
01681   std::vector<MVT::ValueType> VTs;
01682   VTs.reserve(2);
01683   VTs.push_back(VT); VTs.push_back(MVT::Other);  // Add token chain.
01684   return getNode(ISD::VAARG, VTs, Ops);
01685 }
01686 
01687 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
01688                                 std::vector<SDOperand> &Ops) {
01689   switch (Ops.size()) {
01690   case 0: return getNode(Opcode, VT);
01691   case 1: return getNode(Opcode, VT, Ops[0]);
01692   case 2: return getNode(Opcode, VT, Ops[0], Ops[1]);
01693   case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
01694   default: break;
01695   }
01696   
01697   switch (Opcode) {
01698   default: break;
01699   case ISD::TRUNCSTORE: {
01700     assert(Ops.size() == 5 && "TRUNCSTORE takes 5 operands!");
01701     MVT::ValueType EVT = cast<VTSDNode>(Ops[4])->getVT();
01702 #if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store
01703     // If this is a truncating store of a constant, convert to the desired type
01704     // and store it instead.
01705     if (isa<Constant>(Ops[0])) {
01706       SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1);
01707       if (isa<Constant>(Op))
01708         N1 = Op;
01709     }
01710     // Also for ConstantFP?
01711 #endif
01712     if (Ops[0].getValueType() == EVT)       // Normal store?
01713       return getNode(ISD::STORE, VT, Ops[0], Ops[1], Ops[2], Ops[3]);
01714     assert(Ops[1].getValueType() > EVT && "Not a truncation?");
01715     assert(MVT::isInteger(Ops[1].getValueType()) == MVT::isInteger(EVT) &&
01716            "Can't do FP-INT conversion!");
01717     break;
01718   }
01719   case ISD::SELECT_CC: {
01720     assert(Ops.size() == 5 && "SELECT_CC takes 5 operands!");
01721     assert(Ops[0].getValueType() == Ops[1].getValueType() &&
01722            "LHS and RHS of condition must have same type!");
01723     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
01724            "True and False arms of SelectCC must have same type!");
01725     assert(Ops[2].getValueType() == VT &&
01726            "select_cc node must be of same type as true and false value!");
01727     break;
01728   }
01729   case ISD::BR_CC: {
01730     assert(Ops.size() == 5 && "BR_CC takes 5 operands!");
01731     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
01732            "LHS/RHS of comparison should match types!");
01733     break;
01734   }
01735   }
01736 
01737   // Memoize nodes.
01738   SDNode *N;
01739   if (VT != MVT::Flag) {
01740     SDNode *&E =
01741       OneResultNodes[std::make_pair(Opcode, std::make_pair(VT, Ops))];
01742     if (E) return SDOperand(E, 0);
01743     E = N = new SDNode(Opcode, Ops);
01744   } else {
01745     N = new SDNode(Opcode, Ops);
01746   }
01747   N->setValueTypes(VT);
01748   AllNodes.push_back(N);
01749   return SDOperand(N, 0);
01750 }
01751 
01752 SDOperand SelectionDAG::getNode(unsigned Opcode,
01753                                 std::vector<MVT::ValueType> &ResultTys,
01754                                 std::vector<SDOperand> &Ops) {
01755   if (ResultTys.size() == 1)
01756     return getNode(Opcode, ResultTys[0], Ops);
01757 
01758   switch (Opcode) {
01759   case ISD::EXTLOAD:
01760   case ISD::SEXTLOAD:
01761   case ISD::ZEXTLOAD: {
01762     MVT::ValueType EVT = cast<VTSDNode>(Ops[3])->getVT();
01763     assert(Ops.size() == 4 && ResultTys.size() == 2 && "Bad *EXTLOAD!");
01764     // If they are asking for an extending load from/to the same thing, return a
01765     // normal load.
01766     if (ResultTys[0] == EVT)
01767       return getLoad(ResultTys[0], Ops[0], Ops[1], Ops[2]);
01768     if (MVT::isVector(ResultTys[0])) {
01769       assert(EVT == MVT::getVectorBaseType(ResultTys[0]) &&
01770              "Invalid vector extload!");
01771     } else {
01772       assert(EVT < ResultTys[0] &&
01773              "Should only be an extending load, not truncating!");
01774     }
01775     assert((Opcode == ISD::EXTLOAD || MVT::isInteger(ResultTys[0])) &&
01776            "Cannot sign/zero extend a FP/Vector load!");
01777     assert(MVT::isInteger(ResultTys[0]) == MVT::isInteger(EVT) &&
01778            "Cannot convert from FP to Int or Int -> FP!");
01779     break;
01780   }
01781 
01782   // FIXME: figure out how to safely handle things like
01783   // int foo(int x) { return 1 << (x & 255); }
01784   // int bar() { return foo(256); }
01785 #if 0
01786   case ISD::SRA_PARTS:
01787   case ISD::SRL_PARTS:
01788   case ISD::SHL_PARTS:
01789     if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
01790         cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
01791       return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
01792     else if (N3.getOpcode() == ISD::AND)
01793       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
01794         // If the and is only masking out bits that cannot effect the shift,
01795         // eliminate the and.
01796         unsigned NumBits = MVT::getSizeInBits(VT)*2;
01797         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
01798           return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
01799       }
01800     break;
01801 #endif
01802   }
01803 
01804   // Memoize the node unless it returns a flag.
01805   SDNode *N;
01806   if (ResultTys.back() != MVT::Flag) {
01807     SDNode *&E =
01808       ArbitraryNodes[std::make_pair(Opcode, std::make_pair(ResultTys, Ops))];
01809     if (E) return SDOperand(E, 0);
01810     E = N = new SDNode(Opcode, Ops);
01811   } else {
01812     N = new SDNode(Opcode, Ops);
01813   }
01814   setNodeValueTypes(N, ResultTys);
01815   AllNodes.push_back(N);
01816   return SDOperand(N, 0);
01817 }
01818 
01819 void SelectionDAG::setNodeValueTypes(SDNode *N, 
01820                                      std::vector<MVT::ValueType> &RetVals) {
01821   switch (RetVals.size()) {
01822   case 0: return;
01823   case 1: N->setValueTypes(RetVals[0]); return;
01824   case 2: setNodeValueTypes(N, RetVals[0], RetVals[1]); return;
01825   default: break;
01826   }
01827   
01828   std::list<std::vector<MVT::ValueType> >::iterator I =
01829     std::find(VTList.begin(), VTList.end(), RetVals);
01830   if (I == VTList.end()) {
01831     VTList.push_front(RetVals);
01832     I = VTList.begin();
01833   }
01834 
01835   N->setValueTypes(&(*I)[0], I->size());
01836 }
01837 
01838 void SelectionDAG::setNodeValueTypes(SDNode *N, MVT::ValueType VT1, 
01839                                      MVT::ValueType VT2) {
01840   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
01841        E = VTList.end(); I != E; ++I) {
01842     if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2) {
01843       N->setValueTypes(&(*I)[0], 2);
01844       return;
01845     }
01846   }
01847   std::vector<MVT::ValueType> V;
01848   V.push_back(VT1);
01849   V.push_back(VT2);
01850   VTList.push_front(V);
01851   N->setValueTypes(&(*VTList.begin())[0], 2);
01852 }
01853 
01854 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
01855 /// specified operands.  If the resultant node already exists in the DAG,
01856 /// this does not modify the specified node, instead it returns the node that
01857 /// already exists.  If the resultant node does not exist in the DAG, the
01858 /// input node is returned.  As a degenerate case, if you specify the same
01859 /// input operands as the node already has, the input node is returned.
01860 SDOperand SelectionDAG::
01861 UpdateNodeOperands(SDOperand InN, SDOperand Op) {
01862   SDNode *N = InN.Val;
01863   assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
01864   
01865   // Check to see if there is no change.
01866   if (Op == N->getOperand(0)) return InN;
01867   
01868   // See if the modified node already exists.
01869   SDNode **NewSlot = FindModifiedNodeSlot(N, Op);
01870   if (NewSlot && *NewSlot)
01871     return SDOperand(*NewSlot, InN.ResNo);
01872   
01873   // Nope it doesn't.  Remove the node from it's current place in the maps.
01874   if (NewSlot)
01875     RemoveNodeFromCSEMaps(N);
01876   
01877   // Now we update the operands.
01878   N->OperandList[0].Val->removeUser(N);
01879   Op.Val->addUser(N);
01880   N->OperandList[0] = Op;
01881   
01882   // If this gets put into a CSE map, add it.
01883   if (NewSlot) *NewSlot = N;
01884   return InN;
01885 }
01886 
01887 SDOperand SelectionDAG::
01888 UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) {
01889   SDNode *N = InN.Val;
01890   assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
01891   
01892   // Check to see if there is no change.
01893   bool AnyChange = false;
01894   if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
01895     return InN;   // No operands changed, just return the input node.
01896   
01897   // See if the modified node already exists.
01898   SDNode **NewSlot = FindModifiedNodeSlot(N, Op1, Op2);
01899   if (NewSlot && *NewSlot)
01900     return SDOperand(*NewSlot, InN.ResNo);
01901   
01902   // Nope it doesn't.  Remove the node from it's current place in the maps.
01903   if (NewSlot)
01904     RemoveNodeFromCSEMaps(N);
01905   
01906   // Now we update the operands.
01907   if (N->OperandList[0] != Op1) {
01908     N->OperandList[0].Val->removeUser(N);
01909     Op1.Val->addUser(N);
01910     N->OperandList[0] = Op1;
01911   }
01912   if (N->OperandList[1] != Op2) {
01913     N->OperandList[1].Val->removeUser(N);
01914     Op2.Val->addUser(N);
01915     N->OperandList[1] = Op2;
01916   }
01917   
01918   // If this gets put into a CSE map, add it.
01919   if (NewSlot) *NewSlot = N;
01920   return InN;
01921 }
01922 
01923 SDOperand SelectionDAG::
01924 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) {
01925   std::vector<SDOperand> Ops;
01926   Ops.push_back(Op1);
01927   Ops.push_back(Op2);
01928   Ops.push_back(Op3);
01929   return UpdateNodeOperands(N, Ops);
01930 }
01931 
01932 SDOperand SelectionDAG::
01933 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 
01934                    SDOperand Op3, SDOperand Op4) {
01935   std::vector<SDOperand> Ops;
01936   Ops.push_back(Op1);
01937   Ops.push_back(Op2);
01938   Ops.push_back(Op3);
01939   Ops.push_back(Op4);
01940   return UpdateNodeOperands(N, Ops);
01941 }
01942 
01943 SDOperand SelectionDAG::
01944 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
01945                    SDOperand Op3, SDOperand Op4, SDOperand Op5) {
01946   std::vector<SDOperand> Ops;
01947   Ops.push_back(Op1);
01948   Ops.push_back(Op2);
01949   Ops.push_back(Op3);
01950   Ops.push_back(Op4);
01951   Ops.push_back(Op5);
01952   return UpdateNodeOperands(N, Ops);
01953 }
01954 
01955 
01956 SDOperand SelectionDAG::
01957 UpdateNodeOperands(SDOperand InN, const std::vector<SDOperand> &Ops) {
01958   SDNode *N = InN.Val;
01959   assert(N->getNumOperands() == Ops.size() &&
01960          "Update with wrong number of operands");
01961   
01962   // Check to see if there is no change.
01963   unsigned NumOps = Ops.size();
01964   bool AnyChange = false;
01965   for (unsigned i = 0; i != NumOps; ++i) {
01966     if (Ops[i] != N->getOperand(i)) {
01967       AnyChange = true;
01968       break;
01969     }
01970   }
01971   
01972   // No operands changed, just return the input node.
01973   if (!AnyChange) return InN;
01974   
01975   // See if the modified node already exists.
01976   SDNode **NewSlot = FindModifiedNodeSlot(N, Ops);
01977   if (NewSlot && *NewSlot)
01978     return SDOperand(*NewSlot, InN.ResNo);
01979   
01980   // Nope it doesn't.  Remove the node from it's current place in the maps.
01981   if (NewSlot)
01982     RemoveNodeFromCSEMaps(N);
01983   
01984   // Now we update the operands.
01985   for (unsigned i = 0; i != NumOps; ++i) {
01986     if (N->OperandList[i] != Ops[i]) {
01987       N->OperandList[i].Val->removeUser(N);
01988       Ops[i].Val->addUser(N);
01989       N->OperandList[i] = Ops[i];
01990     }
01991   }
01992 
01993   // If this gets put into a CSE map, add it.
01994   if (NewSlot) *NewSlot = N;
01995   return InN;
01996 }
01997 
01998 
01999 
02000 
02001 /// SelectNodeTo - These are used for target selectors to *mutate* the
02002 /// specified node to have the specified return type, Target opcode, and
02003 /// operands.  Note that target opcodes are stored as
02004 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.
02005 ///
02006 /// Note that SelectNodeTo returns the resultant node.  If there is already a
02007 /// node of the specified opcode and operands, it returns that node instead of
02008 /// the current one.
02009 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02010                                      MVT::ValueType VT) {
02011   // If an identical node already exists, use it.
02012   SDNode *&ON = NullaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, VT)];
02013   if (ON) return SDOperand(ON, 0);
02014   
02015   RemoveNodeFromCSEMaps(N);
02016   
02017   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02018   N->setValueTypes(VT);
02019 
02020   ON = N;   // Memoize the new node.
02021   return SDOperand(N, 0);
02022 }
02023 
02024 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02025                                      MVT::ValueType VT, SDOperand Op1) {
02026   // If an identical node already exists, use it.
02027   SDNode *&ON = UnaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02028                                         std::make_pair(Op1, VT))];
02029   if (ON) return SDOperand(ON, 0);
02030   
02031   RemoveNodeFromCSEMaps(N);
02032   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02033   N->setValueTypes(VT);
02034   N->setOperands(Op1);
02035   
02036   ON = N;   // Memoize the new node.
02037   return SDOperand(N, 0);
02038 }
02039 
02040 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02041                                      MVT::ValueType VT, SDOperand Op1,
02042                                      SDOperand Op2) {
02043   // If an identical node already exists, use it.
02044   SDNode *&ON = BinaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02045                                          std::make_pair(Op1, Op2))];
02046   if (ON) return SDOperand(ON, 0);
02047   
02048   RemoveNodeFromCSEMaps(N);
02049   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02050   N->setValueTypes(VT);
02051   N->setOperands(Op1, Op2);
02052   
02053   ON = N;   // Memoize the new node.
02054   return SDOperand(N, 0);
02055 }
02056 
02057 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02058                                      MVT::ValueType VT, SDOperand Op1,
02059                                      SDOperand Op2, SDOperand Op3) {
02060   // If an identical node already exists, use it.
02061   std::vector<SDOperand> OpList;
02062   OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3);
02063   SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02064                                               std::make_pair(VT, OpList))];
02065   if (ON) return SDOperand(ON, 0);
02066   
02067   RemoveNodeFromCSEMaps(N);
02068   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02069   N->setValueTypes(VT);
02070   N->setOperands(Op1, Op2, Op3);
02071 
02072   ON = N;   // Memoize the new node.
02073   return SDOperand(N, 0);
02074 }
02075 
02076 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02077                                      MVT::ValueType VT, SDOperand Op1,
02078                                      SDOperand Op2, SDOperand Op3,
02079                                      SDOperand Op4) {
02080   // If an identical node already exists, use it.
02081   std::vector<SDOperand> OpList;
02082   OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3);
02083   OpList.push_back(Op4);
02084   SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02085                                               std::make_pair(VT, OpList))];
02086   if (ON) return SDOperand(ON, 0);
02087   
02088   RemoveNodeFromCSEMaps(N);
02089   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02090   N->setValueTypes(VT);
02091   N->setOperands(Op1, Op2, Op3, Op4);
02092 
02093   ON = N;   // Memoize the new node.
02094   return SDOperand(N, 0);
02095 }
02096 
02097 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02098                                      MVT::ValueType VT, SDOperand Op1,
02099                                      SDOperand Op2, SDOperand Op3,SDOperand Op4,
02100                                      SDOperand Op5) {
02101   // If an identical node already exists, use it.
02102   std::vector<SDOperand> OpList;
02103   OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3);
02104   OpList.push_back(Op4); OpList.push_back(Op5);
02105   SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02106                                               std::make_pair(VT, OpList))];
02107   if (ON) return SDOperand(ON, 0);
02108   
02109   RemoveNodeFromCSEMaps(N);
02110   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02111   N->setValueTypes(VT);
02112   N->setOperands(Op1, Op2, Op3, Op4, Op5);
02113   
02114   ON = N;   // Memoize the new node.
02115   return SDOperand(N, 0);
02116 }
02117 
02118 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02119                                      MVT::ValueType VT, SDOperand Op1,
02120                                      SDOperand Op2, SDOperand Op3,SDOperand Op4,
02121                                      SDOperand Op5, SDOperand Op6) {
02122   // If an identical node already exists, use it.
02123   std::vector<SDOperand> OpList;
02124   OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3);
02125   OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6);
02126   SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02127                                               std::make_pair(VT, OpList))];
02128   if (ON) return SDOperand(ON, 0);
02129 
02130   RemoveNodeFromCSEMaps(N);
02131   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02132   N->setValueTypes(VT);
02133   N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6);
02134   
02135   ON = N;   // Memoize the new node.
02136   return SDOperand(N, 0);
02137 }
02138 
02139 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02140                                      MVT::ValueType VT, SDOperand Op1,
02141                                      SDOperand Op2, SDOperand Op3,SDOperand Op4,
02142                                      SDOperand Op5, SDOperand Op6,
02143              SDOperand Op7) {
02144   // If an identical node already exists, use it.
02145   std::vector<SDOperand> OpList;
02146   OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3);
02147   OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6);
02148   OpList.push_back(Op7);
02149   SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02150                                               std::make_pair(VT, OpList))];
02151   if (ON) return SDOperand(ON, 0);
02152 
02153   RemoveNodeFromCSEMaps(N);
02154   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02155   N->setValueTypes(VT);
02156   N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7);
02157   
02158   ON = N;   // Memoize the new node.
02159   return SDOperand(N, 0);
02160 }
02161 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02162                                      MVT::ValueType VT, SDOperand Op1,
02163                                      SDOperand Op2, SDOperand Op3,SDOperand Op4,
02164                                      SDOperand Op5, SDOperand Op6,
02165              SDOperand Op7, SDOperand Op8) {
02166   // If an identical node already exists, use it.
02167   std::vector<SDOperand> OpList;
02168   OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3);
02169   OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6);
02170   OpList.push_back(Op7); OpList.push_back(Op8);
02171   SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02172                                               std::make_pair(VT, OpList))];
02173   if (ON) return SDOperand(ON, 0);
02174 
02175   RemoveNodeFromCSEMaps(N);
02176   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02177   N->setValueTypes(VT);
02178   N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7, Op8);
02179   
02180   ON = N;   // Memoize the new node.
02181   return SDOperand(N, 0);
02182 }
02183 
02184 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 
02185                                      MVT::ValueType VT1, MVT::ValueType VT2,
02186                                      SDOperand Op1, SDOperand Op2) {
02187   // If an identical node already exists, use it.
02188   std::vector<SDOperand> OpList;
02189   OpList.push_back(Op1); OpList.push_back(Op2); 
02190   std::vector<MVT::ValueType> VTList;
02191   VTList.push_back(VT1); VTList.push_back(VT2);
02192   SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02193                                               std::make_pair(VTList, OpList))];
02194   if (ON) return SDOperand(ON, 0);
02195 
02196   RemoveNodeFromCSEMaps(N);
02197   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02198   setNodeValueTypes(N, VT1, VT2);
02199   N->setOperands(Op1, Op2);
02200   
02201   ON = N;   // Memoize the new node.
02202   return SDOperand(N, 0);
02203 }
02204 
02205 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02206                                      MVT::ValueType VT1, MVT::ValueType VT2,
02207                                      SDOperand Op1, SDOperand Op2, 
02208                                      SDOperand Op3) {
02209   // If an identical node already exists, use it.
02210   std::vector<SDOperand> OpList;
02211   OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3);
02212   std::vector<MVT::ValueType> VTList;
02213   VTList.push_back(VT1); VTList.push_back(VT2);
02214   SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02215                                               std::make_pair(VTList, OpList))];
02216   if (ON) return SDOperand(ON, 0);
02217 
02218   RemoveNodeFromCSEMaps(N);
02219   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02220   setNodeValueTypes(N, VT1, VT2);
02221   N->setOperands(Op1, Op2, Op3);
02222   
02223   ON = N;   // Memoize the new node.
02224   return SDOperand(N, 0);
02225 }
02226 
02227 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02228                                      MVT::ValueType VT1, MVT::ValueType VT2,
02229                                      SDOperand Op1, SDOperand Op2,
02230                                      SDOperand Op3, SDOperand Op4) {
02231   // If an identical node already exists, use it.
02232   std::vector<SDOperand> OpList;
02233   OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3);
02234   OpList.push_back(Op4);
02235   std::vector<MVT::ValueType> VTList;
02236   VTList.push_back(VT1); VTList.push_back(VT2);
02237   SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02238                                               std::make_pair(VTList, OpList))];
02239   if (ON) return SDOperand(ON, 0);
02240 
02241   RemoveNodeFromCSEMaps(N);
02242   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02243   setNodeValueTypes(N, VT1, VT2);
02244   N->setOperands(Op1, Op2, Op3, Op4);
02245 
02246   ON = N;   // Memoize the new node.
02247   return SDOperand(N, 0);
02248 }
02249 
02250 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
02251                                      MVT::ValueType VT1, MVT::ValueType VT2,
02252                                      SDOperand Op1, SDOperand Op2,
02253                                      SDOperand Op3, SDOperand Op4, 
02254                                      SDOperand Op5) {
02255   // If an identical node already exists, use it.
02256   std::vector<SDOperand> OpList;
02257   OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3);
02258   OpList.push_back(Op4); OpList.push_back(Op5);
02259   std::vector<MVT::ValueType> VTList;
02260   VTList.push_back(VT1); VTList.push_back(VT2);
02261   SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc,
02262                                               std::make_pair(VTList, OpList))];
02263   if (ON) return SDOperand(ON, 0);
02264 
02265   RemoveNodeFromCSEMaps(N);
02266   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
02267   setNodeValueTypes(N, VT1, VT2);
02268   N->setOperands(Op1, Op2, Op3, Op4, Op5);
02269   
02270   ON = N;   // Memoize the new node.
02271   return SDOperand(N, 0);
02272 }
02273 
02274 /// getTargetNode - These are used for target selectors to create a new node
02275 /// with specified return type(s), target opcode, and operands.
02276 ///
02277 /// Note that getTargetNode returns the resultant node.  If there is already a
02278 /// node of the specified opcode and operands, it returns that node instead of
02279 /// the current one.
02280 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) {
02281   return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val;
02282 }
02283 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
02284                                     SDOperand Op1) {
02285   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val;
02286 }
02287 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
02288                                     SDOperand Op1, SDOperand Op2) {
02289   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val;
02290 }
02291 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
02292                                     SDOperand Op1, SDOperand Op2, SDOperand Op3) {
02293   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val;
02294 }
02295 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
02296                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
02297                                     SDOperand Op4) {
02298   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4).Val;
02299 }
02300 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
02301                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
02302                                     SDOperand Op4, SDOperand Op5) {
02303   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4, Op5).Val;
02304 }
02305 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
02306                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
02307                                     SDOperand Op4, SDOperand Op5, SDOperand Op6) {
02308   std::vector<SDOperand> Ops;
02309   Ops.reserve(6);
02310   Ops.push_back(Op1);
02311   Ops.push_back(Op2);
02312   Ops.push_back(Op3);
02313   Ops.push_back(Op4);
02314   Ops.push_back(Op5);
02315   Ops.push_back(Op6);
02316   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val;
02317 }
02318 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
02319                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
02320                                     SDOperand Op4, SDOperand Op5, SDOperand Op6,
02321                                     SDOperand Op7) {
02322   std::vector<SDOperand> Ops;
02323   Ops.reserve(7);
02324   Ops.push_back(Op1);
02325   Ops.push_back(Op2);
02326   Ops.push_back(Op3);
02327   Ops.push_back(Op4);
02328   Ops.push_back(Op5);
02329   Ops.push_back(Op6);
02330   Ops.push_back(Op7);
02331   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val;
02332 }
02333 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
02334                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
02335                                     SDOperand Op4, SDOperand Op5, SDOperand Op6,
02336                                     SDOperand Op7, SDOperand Op8) {
02337   std::vector<SDOperand> Ops;
02338   Ops.reserve(8);
02339   Ops.push_back(Op1);
02340   Ops.push_back(Op2);
02341   Ops.push_back(Op3);
02342   Ops.push_back(Op4);
02343   Ops.push_back(Op5);
02344   Ops.push_back(Op6);
02345   Ops.push_back(Op7);
02346   Ops.push_back(Op8);
02347   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val;
02348 }
02349 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
02350                                     std::vector<SDOperand> &Ops) {
02351   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val;
02352 }
02353 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02354                                     MVT::ValueType VT2, SDOperand Op1) {
02355   std::vector<MVT::ValueType> ResultTys;
02356   ResultTys.push_back(VT1);
02357   ResultTys.push_back(VT2);
02358   std::vector<SDOperand> Ops;
02359   Ops.push_back(Op1);
02360   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02361 }
02362 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02363                                     MVT::ValueType VT2, SDOperand Op1, SDOperand Op2) {
02364   std::vector<MVT::ValueType> ResultTys;
02365   ResultTys.push_back(VT1);
02366   ResultTys.push_back(VT2);
02367   std::vector<SDOperand> Ops;
02368   Ops.push_back(Op1);
02369   Ops.push_back(Op2);
02370   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02371 }
02372 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02373                                     MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
02374                                     SDOperand Op3) {
02375   std::vector<MVT::ValueType> ResultTys;
02376   ResultTys.push_back(VT1);
02377   ResultTys.push_back(VT2);
02378   std::vector<SDOperand> Ops;
02379   Ops.push_back(Op1);
02380   Ops.push_back(Op2);
02381   Ops.push_back(Op3);
02382   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02383 }
02384 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02385                                     MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
02386                                     SDOperand Op3, SDOperand Op4) {
02387   std::vector<MVT::ValueType> ResultTys;
02388   ResultTys.push_back(VT1);
02389   ResultTys.push_back(VT2);
02390   std::vector<SDOperand> Ops;
02391   Ops.push_back(Op1);
02392   Ops.push_back(Op2);
02393   Ops.push_back(Op3);
02394   Ops.push_back(Op4);
02395   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02396 }
02397 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02398                                     MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
02399                                     SDOperand Op3, SDOperand Op4, SDOperand Op5) {
02400   std::vector<MVT::ValueType> ResultTys;
02401   ResultTys.push_back(VT1);
02402   ResultTys.push_back(VT2);
02403   std::vector<SDOperand> Ops;
02404   Ops.push_back(Op1);
02405   Ops.push_back(Op2);
02406   Ops.push_back(Op3);
02407   Ops.push_back(Op4);
02408   Ops.push_back(Op5);
02409   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02410 }
02411 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02412                                     MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
02413                                     SDOperand Op3, SDOperand Op4, SDOperand Op5,
02414                                     SDOperand Op6) {
02415   std::vector<MVT::ValueType> ResultTys;
02416   ResultTys.push_back(VT1);
02417   ResultTys.push_back(VT2);
02418   std::vector<SDOperand> Ops;
02419   Ops.push_back(Op1);
02420   Ops.push_back(Op2);
02421   Ops.push_back(Op3);
02422   Ops.push_back(Op4);
02423   Ops.push_back(Op5);
02424   Ops.push_back(Op6);
02425   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02426 }
02427 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02428                                     MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
02429                                     SDOperand Op3, SDOperand Op4, SDOperand Op5,
02430                                     SDOperand Op6, SDOperand Op7) {
02431   std::vector<MVT::ValueType> ResultTys;
02432   ResultTys.push_back(VT1);
02433   ResultTys.push_back(VT2);
02434   std::vector<SDOperand> Ops;
02435   Ops.push_back(Op1);
02436   Ops.push_back(Op2);
02437   Ops.push_back(Op3);
02438   Ops.push_back(Op4);
02439   Ops.push_back(Op5);
02440   Ops.push_back(Op6); 
02441   Ops.push_back(Op7);
02442   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02443 }
02444 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02445                                     MVT::ValueType VT2, MVT::ValueType VT3,
02446                                     SDOperand Op1, SDOperand Op2) {
02447   std::vector<MVT::ValueType> ResultTys;
02448   ResultTys.push_back(VT1);
02449   ResultTys.push_back(VT2);
02450   ResultTys.push_back(VT3);
02451   std::vector<SDOperand> Ops;
02452   Ops.push_back(Op1);
02453   Ops.push_back(Op2);
02454   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02455 }
02456 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02457                                     MVT::ValueType VT2, MVT::ValueType VT3,
02458                                     SDOperand Op1, SDOperand Op2,
02459                                     SDOperand Op3, SDOperand Op4, SDOperand Op5) {
02460   std::vector<MVT::ValueType> ResultTys;
02461   ResultTys.push_back(VT1);
02462   ResultTys.push_back(VT2);
02463   ResultTys.push_back(VT3);
02464   std::vector<SDOperand> Ops;
02465   Ops.push_back(Op1);
02466   Ops.push_back(Op2);
02467   Ops.push_back(Op3);
02468   Ops.push_back(Op4);
02469   Ops.push_back(Op5);
02470   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02471 }
02472 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02473                                     MVT::ValueType VT2, MVT::ValueType VT3,
02474                                     SDOperand Op1, SDOperand Op2,
02475                                     SDOperand Op3, SDOperand Op4, SDOperand Op5,
02476                                     SDOperand Op6) {
02477   std::vector<MVT::ValueType> ResultTys;
02478   ResultTys.push_back(VT1);
02479   ResultTys.push_back(VT2);
02480   ResultTys.push_back(VT3);
02481   std::vector<SDOperand> Ops;
02482   Ops.push_back(Op1);
02483   Ops.push_back(Op2);
02484   Ops.push_back(Op3);
02485   Ops.push_back(Op4);
02486   Ops.push_back(Op5);
02487   Ops.push_back(Op6);
02488   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02489 }
02490 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
02491                                     MVT::ValueType VT2, MVT::ValueType VT3,
02492                                     SDOperand Op1, SDOperand Op2,
02493                                     SDOperand Op3, SDOperand Op4, SDOperand Op5,
02494                                     SDOperand Op6, SDOperand Op7) {
02495   std::vector<MVT::ValueType> ResultTys;
02496   ResultTys.push_back(VT1);
02497   ResultTys.push_back(VT2);
02498   ResultTys.push_back(VT3);
02499   std::vector<SDOperand> Ops;
02500   Ops.push_back(Op1);
02501   Ops.push_back(Op2);
02502   Ops.push_back(Op3);
02503   Ops.push_back(Op4);
02504   Ops.push_back(Op5);
02505   Ops.push_back(Op6);
02506   Ops.push_back(Op7);
02507   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02508 }
02509 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 
02510                                     MVT::ValueType VT2, std::vector<SDOperand> &Ops) {
02511   std::vector<MVT::ValueType> ResultTys;
02512   ResultTys.push_back(VT1);
02513   ResultTys.push_back(VT2);
02514   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val;
02515 }
02516 
02517 // ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
02518 /// This can cause recursive merging of nodes in the DAG.
02519 ///
02520 /// This version assumes From/To have a single result value.
02521 ///
02522 void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand ToN,
02523                                       std::vector<SDNode*> *Deleted) {
02524   SDNode *From = FromN.Val, *To = ToN.Val;
02525   assert(From->getNumValues() == 1 && To->getNumValues() == 1 &&
02526          "Cannot replace with this method!");
02527   assert(From != To && "Cannot replace uses of with self");
02528   
02529   while (!From->use_empty()) {
02530     // Process users until they are all gone.
02531     SDNode *U = *From->use_begin();
02532     
02533     // This node is about to morph, remove its old self from the CSE maps.
02534     RemoveNodeFromCSEMaps(U);
02535     
02536     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
02537          I != E; ++I)
02538       if (I->Val == From) {
02539         From->removeUser(U);
02540         I->Val = To;
02541         To->addUser(U);
02542       }
02543 
02544     // Now that we have modified U, add it back to the CSE maps.  If it already
02545     // exists there, recursively merge the results together.
02546     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
02547       ReplaceAllUsesWith(U, Existing, Deleted);
02548       // U is now dead.
02549       if (Deleted) Deleted->push_back(U);
02550       DeleteNodeNotInCSEMaps(U);
02551     }
02552   }
02553 }
02554 
02555 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
02556 /// This can cause recursive merging of nodes in the DAG.
02557 ///
02558 /// This version assumes From/To have matching types and numbers of result
02559 /// values.
02560 ///
02561 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
02562                                       std::vector<SDNode*> *Deleted) {
02563   assert(From != To && "Cannot replace uses of with self");
02564   assert(From->getNumValues() == To->getNumValues() &&
02565          "Cannot use this version of ReplaceAllUsesWith!");
02566   if (From->getNumValues() == 1) {  // If possible, use the faster version.
02567     ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted);
02568     return;
02569   }
02570   
02571   while (!From->use_empty()) {
02572     // Process users until they are all gone.
02573     SDNode *U = *From->use_begin();
02574     
02575     // This node is about to morph, remove its old self from the CSE maps.
02576     RemoveNodeFromCSEMaps(U);
02577     
02578     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
02579          I != E; ++I)
02580       if (I->Val == From) {
02581         From->removeUser(U);
02582         I->Val = To;
02583         To->addUser(U);
02584       }
02585         
02586     // Now that we have modified U, add it back to the CSE maps.  If it already
02587     // exists there, recursively merge the results together.
02588     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
02589       ReplaceAllUsesWith(U, Existing, Deleted);
02590       // U is now dead.
02591       if (Deleted) Deleted->push_back(U);
02592       DeleteNodeNotInCSEMaps(U);
02593     }
02594   }
02595 }
02596 
02597 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
02598 /// This can cause recursive merging of nodes in the DAG.
02599 ///
02600 /// This version can replace From with any result values.  To must match the
02601 /// number and types of values returned by From.
02602 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
02603                                       const std::vector<SDOperand> &To,
02604                                       std::vector<SDNode*> *Deleted) {
02605   assert(From->getNumValues() == To.size() &&
02606          "Incorrect number of values to replace with!");
02607   if (To.size() == 1 && To[0].Val->getNumValues() == 1) {
02608     // Degenerate case handled above.
02609     ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted);
02610     return;
02611   }
02612 
02613   while (!From->use_empty()) {
02614     // Process users until they are all gone.
02615     SDNode *U = *From->use_begin();
02616     
02617     // This node is about to morph, remove its old self from the CSE maps.
02618     RemoveNodeFromCSEMaps(U);
02619     
02620     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
02621          I != E; ++I)
02622       if (I->Val == From) {
02623         const SDOperand &ToOp = To[I->ResNo];
02624         From->removeUser(U);
02625         *I = ToOp;
02626         ToOp.Val->addUser(U);
02627       }
02628         
02629     // Now that we have modified U, add it back to the CSE maps.  If it already
02630     // exists there, recursively merge the results together.
02631     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
02632       ReplaceAllUsesWith(U, Existing, Deleted);
02633       // U is now dead.
02634       if (Deleted) Deleted->push_back(U);
02635       DeleteNodeNotInCSEMaps(U);
02636     }
02637   }
02638 }
02639 
02640 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
02641 /// uses of other values produced by From.Val alone.  The Deleted vector is
02642 /// handled the same was as for ReplaceAllUsesWith.
02643 void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
02644                                              std::vector<SDNode*> &Deleted) {
02645   assert(From != To && "Cannot replace a value with itself");
02646   // Handle the simple, trivial, case efficiently.
02647   if (From.Val->getNumValues() == 1 && To.Val->getNumValues() == 1) {
02648     ReplaceAllUsesWith(From, To, &Deleted);
02649     return;
02650   }
02651   
02652   // Get all of the users in a nice, deterministically ordered, uniqued set.
02653   SetVector<SDNode*> Users(From.Val->use_begin(), From.Val->use_end());
02654 
02655   while (!Users.empty()) {
02656     // We know that this user uses some value of From.  If it is the right
02657     // value, update it.
02658     SDNode *User = Users.back();
02659     Users.pop_back();
02660     
02661     for (SDOperand *Op = User->OperandList,
02662          *E = User->OperandList+User->NumOperands; Op != E; ++Op) {
02663       if (*Op == From) {
02664         // Okay, we know this user needs to be updated.  Remove its old self
02665         // from the CSE maps.
02666         RemoveNodeFromCSEMaps(User);
02667         
02668         // Update all operands that match "From".
02669         for (; Op != E; ++Op) {
02670           if (*Op == From) {
02671             From.Val->removeUser(User);
02672             *Op = To;
02673             To.Val->addUser(User);
02674           }
02675         }
02676                    
02677         // Now that we have modified User, add it back to the CSE maps.  If it
02678         // already exists there, recursively merge the results together.
02679         if (SDNode *Existing = AddNonLeafNodeToCSEMaps(User)) {
02680           unsigned NumDeleted = Deleted.size();
02681           ReplaceAllUsesWith(User, Existing, &Deleted);
02682           
02683           // User is now dead.
02684           Deleted.push_back(User);
02685           DeleteNodeNotInCSEMaps(User);
02686           
02687           // We have to be careful here, because ReplaceAllUsesWith could have
02688           // deleted a user of From, which means there may be dangling pointers
02689           // in the "Users" setvector.  Scan over the deleted node pointers and
02690           // remove them from the setvector.
02691           for (unsigned i = NumDeleted, e = Deleted.size(); i != e; ++i)
02692             Users.remove(Deleted[i]);
02693         }
02694         break;   // Exit the operand scanning loop.
02695       }
02696     }
02697   }
02698 }
02699 
02700 
02701 //===----------------------------------------------------------------------===//
02702 //                              SDNode Class
02703 //===----------------------------------------------------------------------===//
02704 
02705 // Out-of-line virtual method to give class a home.
02706 void SDNode::ANCHOR() {
02707 }
02708 
02709 
02710 /// getValueTypeList - Return a pointer to the specified value type.
02711 ///
02712 MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) {
02713   static MVT::ValueType VTs[MVT::LAST_VALUETYPE];
02714   VTs[VT] = VT;
02715   return &VTs[VT];
02716 }
02717 
02718 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
02719 /// indicated value.  This method ignores uses of other values defined by this
02720 /// operation.
02721 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
02722   assert(Value < getNumValues() && "Bad value!");
02723 
02724   // If there is only one value, this is easy.
02725   if (getNumValues() == 1)
02726     return use_size() == NUses;
02727   if (Uses.size() < NUses) return false;
02728 
02729   SDOperand TheValue(const_cast<SDNode *>(this), Value);
02730 
02731   std::set<SDNode*> UsersHandled;
02732 
02733   for (std::vector<SDNode*>::const_iterator UI = Uses.begin(), E = Uses.end();
02734        UI != E; ++UI) {
02735     SDNode *User = *UI;
02736     if (User->getNumOperands() == 1 ||
02737         UsersHandled.insert(User).second)     // First time we've seen this?
02738       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
02739         if (User->getOperand(i) == TheValue) {
02740           if (NUses == 0)
02741             return false;   // too many uses
02742           --NUses;
02743         }
02744   }
02745 
02746   // Found exactly the right number of uses?
02747   return NUses == 0;
02748 }
02749 
02750 
02751 // isOnlyUse - Return true if this node is the only use of N.
02752 bool SDNode::isOnlyUse(SDNode *N) const {
02753   bool Seen = false;
02754   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
02755     SDNode *User = *I;
02756     if (User == this)
02757       Seen = true;
02758     else
02759       return false;
02760   }
02761 
02762   return Seen;
02763 }
02764 
02765 // isOperand - Return true if this node is an operand of N.
02766 bool SDOperand::isOperand(SDNode *N) const {
02767   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
02768     if (*this == N->getOperand(i))
02769       return true;
02770   return false;
02771 }
02772 
02773 bool SDNode::isOperand(SDNode *N) const {
02774   for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
02775     if (this == N->OperandList[i].Val)
02776       return true;
02777   return false;
02778 }
02779 
02780 const char *SDNode::getOperationName(const SelectionDAG *G) const {
02781   switch (getOpcode()) {
02782   default:
02783     if (getOpcode() < ISD::BUILTIN_OP_END)
02784       return "<<Unknown DAG Node>>";
02785     else {
02786       if (G) {
02787         if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
02788           if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes())
02789             return TII->getName(getOpcode()-ISD::BUILTIN_OP_END);
02790 
02791         TargetLowering &TLI = G->getTargetLoweringInfo();
02792         const char *Name =
02793           TLI.getTargetNodeName(getOpcode());
02794         if (Name) return Name;
02795       }
02796 
02797       return "<<Unknown Target Node>>";
02798     }
02799    
02800   case ISD::PCMARKER:      return "PCMarker";
02801   case ISD::READCYCLECOUNTER: return "ReadCycleCounter";
02802   case ISD::SRCVALUE:      return "SrcValue";
02803   case ISD::EntryToken:    return "EntryToken";
02804   case ISD::TokenFactor:   return "TokenFactor";
02805   case ISD::AssertSext:    return "AssertSext";
02806   case ISD::AssertZext:    return "AssertZext";
02807 
02808   case ISD::STRING:        return "String";
02809   case ISD::BasicBlock:    return "BasicBlock";
02810   case ISD::VALUETYPE:     return "ValueType";
02811   case ISD::Register:      return "Register";
02812 
02813   case ISD::Constant:      return "Constant";
02814   case ISD::ConstantFP:    return "ConstantFP";
02815   case ISD::GlobalAddress: return "GlobalAddress";
02816   case ISD::FrameIndex:    return "FrameIndex";
02817   case ISD::JumpTable:     return "JumpTable";
02818   case ISD::ConstantPool:  return "ConstantPool";
02819   case ISD::ExternalSymbol: return "ExternalSymbol";
02820   case ISD::INTRINSIC_WO_CHAIN: {
02821     unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue();
02822     return Intrinsic::getName((Intrinsic::ID)IID);
02823   }
02824   case ISD::INTRINSIC_VOID:
02825   case ISD::INTRINSIC_W_CHAIN: {
02826     unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue();
02827     return Intrinsic::getName((Intrinsic::ID)IID);
02828   }
02829 
02830   case ISD::BUILD_VECTOR:   return "BUILD_VECTOR";
02831   case ISD::TargetConstant: return "TargetConstant";
02832   case ISD::TargetConstantFP:return "TargetConstantFP";
02833   case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
02834   case ISD::TargetFrameIndex: return "TargetFrameIndex";
02835   case ISD::TargetJumpTable:  return "TargetJumpTable";
02836   case ISD::TargetConstantPool:  return "TargetConstantPool";
02837   case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
02838 
02839   case ISD::CopyToReg:     return "CopyToReg";
02840   case ISD::CopyFromReg:   return "CopyFromReg";
02841   case ISD::UNDEF:         return "undef";
02842   case ISD::MERGE_VALUES:  return "mergevalues";
02843   case ISD::INLINEASM:     return "inlineasm";
02844   case ISD::HANDLENODE:    return "handlenode";
02845   case ISD::FORMAL_ARGUMENTS: return "formal_arguments";
02846   case ISD::CALL:          return "call";
02847     
02848   // Unary operators
02849   case ISD::FABS:   return "fabs";
02850   case ISD::FNEG:   return "fneg";
02851   case ISD::FSQRT:  return "fsqrt";
02852   case ISD::FSIN:   return "fsin";
02853   case ISD::FCOS:   return "fcos";
02854 
02855   // Binary operators
02856   case ISD::ADD:    return "add";
02857   case ISD::SUB:    return "sub";
02858   case ISD::MUL:    return "mul";
02859   case ISD::MULHU:  return "mulhu";
02860   case ISD::MULHS:  return "mulhs";
02861   case ISD::SDIV:   return "sdiv";
02862   case ISD::UDIV:   return "udiv";
02863   case ISD::SREM:   return "srem";
02864   case ISD::UREM:   return "urem";
02865   case ISD::AND:    return "and";
02866   case ISD::OR:     return "or";
02867   case ISD::XOR:    return "xor";
02868   case ISD::SHL:    return "shl";
02869   case ISD::SRA:    return "sra";
02870   case ISD::SRL:    return "srl";
02871   case ISD::ROTL:   return "rotl";
02872   case ISD::ROTR:   return "rotr";
02873   case ISD::FADD:   return "fadd";
02874   case ISD::FSUB:   return "fsub";
02875   case ISD::FMUL:   return "fmul";
02876   case ISD::FDIV:   return "fdiv";
02877   case ISD::FREM:   return "frem";
02878   case ISD::FCOPYSIGN: return "fcopysign";
02879   case ISD::VADD:   return "vadd";
02880   case ISD::VSUB:   return "vsub";
02881   case ISD::VMUL:   return "vmul";
02882   case ISD::VSDIV:  return "vsdiv";
02883   case ISD::VUDIV:  return "vudiv";
02884   case ISD::VAND:   return "vand";
02885   case ISD::VOR:    return "vor";
02886   case ISD::VXOR:   return "vxor";
02887 
02888   case ISD::SETCC:       return "setcc";
02889   case ISD::SELECT:      return "select";
02890   case ISD::SELECT_CC:   return "select_cc";
02891   case ISD::VSELECT:     return "vselect";
02892   case ISD::INSERT_VECTOR_ELT:   return "insert_vector_elt";
02893   case ISD::VINSERT_VECTOR_ELT:  return "vinsert_vector_elt";
02894   case ISD::EXTRACT_VECTOR_ELT:  return "extract_vector_elt";
02895   case ISD::VEXTRACT_VECTOR_ELT: return "vextract_vector_elt";
02896   case ISD::SCALAR_TO_VECTOR:    return "scalar_to_vector";
02897   case ISD::VBUILD_VECTOR:       return "vbuild_vector";
02898   case ISD::VECTOR_SHUFFLE:      return "vector_shuffle";
02899   case ISD::VVECTOR_SHUFFLE:     return "vvector_shuffle";
02900   case ISD::VBIT_CONVERT:        return "vbit_convert";
02901   case ISD::ADDC:        return "addc";
02902   case ISD::ADDE:        return "adde";
02903   case ISD::SUBC:        return "subc";
02904   case ISD::SUBE:        return "sube";
02905   case ISD::SHL_PARTS:   return "shl_parts";
02906   case ISD::SRA_PARTS:   return "sra_parts";
02907   case ISD::SRL_PARTS:   return "srl_parts";
02908 
02909   // Conversion operators.
02910   case ISD::SIGN_EXTEND: return "sign_extend";
02911   case ISD::ZERO_EXTEND: return "zero_extend";
02912   case ISD::ANY_EXTEND:  return "any_extend";
02913   case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
02914   case ISD::TRUNCATE:    return "truncate";
02915   case ISD::FP_ROUND:    return "fp_round";
02916   case ISD::FP_ROUND_INREG: return "fp_round_inreg";
02917   case ISD::FP_EXTEND:   return "fp_extend";
02918 
02919   case ISD::SINT_TO_FP:  return "sint_to_fp";
02920   case ISD::UINT_TO_FP:  return "uint_to_fp";
02921   case ISD::FP_TO_SINT:  return "fp_to_sint";
02922   case ISD::FP_TO_UINT:  return "fp_to_uint";
02923   case ISD::BIT_CONVERT: return "bit_convert";
02924 
02925     // Control flow instructions
02926   case ISD::BR:      return "br";
02927   case ISD::BRIND:   return "brind";
02928   case ISD::BRCOND:  return "brcond";
02929   case ISD::BR_CC:   return "br_cc";
02930   case ISD::RET:     return "ret";
02931   case ISD::CALLSEQ_START:  return "callseq_start";
02932   case ISD::CALLSEQ_END:    return "callseq_end";
02933 
02934     // Other operators
02935   case ISD::LOAD:               return "load";
02936   case ISD::STORE:              return "store";
02937   case ISD::VLOAD:              return "vload";
02938   case ISD::EXTLOAD:            return "extload";
02939   case ISD::SEXTLOAD:           return "sextload";
02940   case ISD::ZEXTLOAD:           return "zextload";
02941   case ISD::TRUNCSTORE:         return "truncstore";
02942   case ISD::VAARG:              return "vaarg";
02943   case ISD::VACOPY:             return "vacopy";
02944   case ISD::VAEND:              return "vaend";
02945   case ISD::VASTART:            return "vastart";
02946   case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
02947   case ISD::EXTRACT_ELEMENT:    return "extract_element";
02948   case ISD::BUILD_PAIR:         return "build_pair";
02949   case ISD::STACKSAVE:          return "stacksave";
02950   case ISD::STACKRESTORE:       return "stackrestore";
02951     
02952   // Block memory operations.
02953   case ISD::MEMSET:  return "memset";
02954   case ISD::MEMCPY:  return "memcpy";
02955   case ISD::MEMMOVE: return "memmove";
02956 
02957   // Bit manipulation
02958   case ISD::BSWAP:   return "bswap";
02959   case ISD::CTPOP:   return "ctpop";
02960   case ISD::CTTZ:    return "cttz";
02961   case ISD::CTLZ:    return "ctlz";
02962 
02963   // Debug info
02964   case ISD::LOCATION: return "location";
02965   case ISD::DEBUG_LOC: return "debug_loc";
02966   case ISD::DEBUG_LABEL: return "debug_label";
02967 
02968   case ISD::CONDCODE:
02969     switch (cast<CondCodeSDNode>(this)->get()) {
02970     default: assert(0 && "Unknown setcc condition!");
02971     case ISD::SETOEQ:  return "setoeq";
02972     case ISD::SETOGT:  return "setogt";
02973     case ISD::SETOGE:  return "setoge";
02974     case ISD::SETOLT:  return "setolt";
02975     case ISD::SETOLE:  return "setole";
02976     case ISD::SETONE:  return "setone";
02977 
02978     case ISD::SETO:    return "seto";
02979     case ISD::SETUO:   return "setuo";
02980     case ISD::SETUEQ:  return "setue";
02981     case ISD::SETUGT:  return "setugt";
02982     case ISD::SETUGE:  return "setuge";
02983     case ISD::SETULT:  return "setult";
02984     case ISD::SETULE:  return "setule";
02985     case ISD::SETUNE:  return "setune";
02986 
02987     case ISD::SETEQ:   return "seteq";
02988     case ISD::SETGT:   return "setgt";
02989     case ISD::SETGE:   return "setge";
02990     case ISD::SETLT:   return "setlt";
02991     case ISD::SETLE:   return "setle";
02992     case ISD::SETNE:   return "setne";
02993     }
02994   }
02995 }
02996 
02997 void SDNode::dump() const { dump(0); }
02998 void SDNode::dump(const SelectionDAG *G) const {
02999   std::cerr << (void*)this << ": ";
03000 
03001   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
03002     if (i) std::cerr << ",";
03003     if (getValueType(i) == MVT::Other)
03004       std::cerr << "ch";
03005     else
03006       std::cerr << MVT::getValueTypeString(getValueType(i));
03007   }
03008   std::cerr << " = " << getOperationName(G);
03009 
03010   std::cerr << " ";
03011   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
03012     if (i) std::cerr << ", ";
03013     std::cerr << (void*)getOperand(i).Val;
03014     if (unsigned RN = getOperand(i).ResNo)
03015       std::cerr << ":" << RN;
03016   }
03017 
03018   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
03019     std::cerr << "<" << CSDN->getValue() << ">";
03020   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
03021     std::cerr << "<" << CSDN->getValue() << ">";
03022   } else if (const GlobalAddressSDNode *GADN =
03023              dyn_cast<GlobalAddressSDNode>(this)) {
03024     int offset = GADN->getOffset();
03025     std::cerr << "<";
03026     WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
03027     if (offset > 0)
03028       std::cerr << " + " << offset;
03029     else
03030       std::cerr << " " << offset;
03031   } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
03032     std::cerr << "<" << FIDN->getIndex() << ">";
03033   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
03034     int offset = CP->getOffset();
03035     std::cerr << "<" << *CP->get() << ">";
03036     if (offset > 0)
03037       std::cerr << " + " << offset;
03038     else
03039       std::cerr << " " << offset;
03040   } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
03041     std::cerr << "<";
03042     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
03043     if (LBB)
03044       std::cerr << LBB->getName() << " ";
03045     std::cerr << (const void*)BBDN->getBasicBlock() << ">";
03046   } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) {
03047     if (G && R->getReg() && MRegisterInfo::isPhysicalRegister(R->getReg())) {
03048       std::cerr << " " <<G->getTarget().getRegisterInfo()->getName(R->getReg());
03049     } else {
03050       std::cerr << " #" << R->getReg();
03051     }
03052   } else if (const ExternalSymbolSDNode *ES =
03053              dyn_cast<ExternalSymbolSDNode>(this)) {
03054     std::cerr << "'" << ES->getSymbol() << "'";
03055   } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
03056     if (M->getValue())
03057       std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">";
03058     else
03059       std::cerr << "<null:" << M->getOffset() << ">";
03060   } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
03061     std::cerr << ":" << getValueTypeString(N->getVT());
03062   }
03063 }
03064 
03065 static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
03066   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
03067     if (N->getOperand(i).Val->hasOneUse())
03068       DumpNodes(N->getOperand(i).Val, indent+2, G);
03069     else
03070       std::cerr << "\n" << std::string(indent+2, ' ')
03071                 << (void*)N->getOperand(i).Val << ": <multiple use>";
03072 
03073 
03074   std::cerr << "\n" << std::string(indent, ' ');
03075   N->dump(G);
03076 }
03077 
03078 void SelectionDAG::dump() const {
03079   std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
03080   std::vector<const SDNode*> Nodes;
03081   for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end();
03082        I != E; ++I)
03083     Nodes.push_back(I);
03084   
03085   std::sort(Nodes.begin(), Nodes.end());
03086 
03087   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
03088     if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
03089       DumpNodes(Nodes[i], 2, this);
03090   }
03091 
03092   DumpNodes(getRoot().Val, 2, this);
03093 
03094   std::cerr << "\n\n";
03095 }
03096 
03097 /// InsertISelMapEntry - A helper function to insert a key / element pair
03098 /// into a SDOperand to SDOperand map. This is added to avoid the map
03099 /// insertion operator from being inlined.
03100 void SelectionDAG::InsertISelMapEntry(std::map<SDOperand, SDOperand> &Map,
03101                                       SDNode *Key, unsigned KeyResNo,
03102                                       SDNode *Element, unsigned ElementResNo) {
03103   Map.insert(std::make_pair(SDOperand(Key, KeyResNo),
03104                             SDOperand(Element, ElementResNo)));
03105 }
03106 
03107 /// InsertInFlightSetEntry - A helper function to insert a SDNode* to a
03108 /// SDNode* set. This is added to avoid the set insertion operator from being
03109 /// inlined.
03110 void SelectionDAG::InsertInFlightSetEntry(std::set<SDNode*> &Set, SDNode *N) {
03111   Set.insert(N);
03112 }
03113 
03114 /// RemoveInFlightSetEntry - A helper function to remove a SDNode* from a
03115 /// SDNode* set. This is added to avoid the set removal operator from being
03116 /// inlined.
03117 void SelectionDAG::RemoveInFlightSetEntry(std::set<SDNode*> &Set, SDNode *N) {
03118   Set.erase(N);
03119 }