lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

   1 //===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the SelectionDAG::Legalize method.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/SelectionDAG.h"
  15 #include "llvm/CodeGen/MachineFunction.h"
  16 #include "llvm/CodeGen/MachineFrameInfo.h"
  17 #include "llvm/Target/TargetLowering.h"
  18 #include "llvm/Target/TargetData.h"
  19 #include "llvm/Target/TargetOptions.h"
  20 #include "llvm/CallingConv.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/Support/MathExtras.h"
  23 #include "llvm/Support/CommandLine.h"
  24 #include "llvm/Support/Visibility.h"
  25 #include <iostream>
  26 #include <map>
  27 using namespace llvm;
  28
  29 #ifndef NDEBUG
  30 static cl::opt<bool>
  31 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
  32                  cl::desc("Pop up a window to show dags before legalize"));
  33 #else
  34 static const bool ViewLegalizeDAGs = 0;
  35 #endif
  36
  37 //===----------------------------------------------------------------------===//
  38 /// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and
  39 /// hacks on it until the target machine can handle it.  This involves
  40 /// eliminating value sizes the machine cannot handle (promoting small sizes to
  41 /// large sizes or splitting up large values into small values) as well as
  42 /// eliminating operations the machine cannot handle.
  43 ///
  44 /// This code also does a small amount of optimization and recognition of idioms
  45 /// as part of its processing.  For example, if a target does not support a
  46 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
  47 /// will attempt merge setcc and brc instructions into brcc's.
  48 ///
  49 namespace {
  50 class VISIBILITY_HIDDEN SelectionDAGLegalize {
  51   TargetLowering &TLI;
  52   SelectionDAG &DAG;
  53
  54   // Libcall insertion helpers.
  55
  56   /// LastCALLSEQ_END - This keeps track of the CALLSEQ_END node that has been
  57   /// legalized.  We use this to ensure that calls are properly serialized
  58   /// against each other, including inserted libcalls.
  59   SDOperand LastCALLSEQ_END;
  60
  61   /// IsLegalizingCall - This member is used *only* for purposes of providing
  62   /// helpful assertions that a libcall isn't created while another call is
  63   /// being legalized (which could lead to non-serialized call sequences).
  64   bool IsLegalizingCall;
  65
  66   enum LegalizeAction {
  67     Legal,      // The target natively supports this operation.
  68     Promote,    // This operation should be executed in a larger type.
  69     Expand      // Try to expand this to other ops, otherwise use a libcall.
  70   };
  71
  72   /// ValueTypeActions - This is a bitvector that contains two bits for each
  73   /// value type, where the two bits correspond to the LegalizeAction enum.
  74   /// This can be queried with "getTypeAction(VT)".
  75   TargetLowering::ValueTypeActionImpl ValueTypeActions;
  76
  77   /// LegalizedNodes - For nodes that are of legal width, and that have more
  78   /// than one use, this map indicates what regularized operand to use.  This
  79   /// allows us to avoid legalizing the same thing more than once.
  80   std::map<SDOperand, SDOperand> LegalizedNodes;
  81
  82   /// PromotedNodes - For nodes that are below legal width, and that have more
  83   /// than one use, this map indicates what promoted value to use.  This allows
  84   /// us to avoid promoting the same thing more than once.
  85   std::map<SDOperand, SDOperand> PromotedNodes;
  86
  87   /// ExpandedNodes - For nodes that need to be expanded this map indicates
  88   /// which which operands are the expanded version of the input.  This allows
  89   /// us to avoid expanding the same node more than once.
  90   std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
  91
  92   /// SplitNodes - For vector nodes that need to be split, this map indicates
  93   /// which which operands are the split version of the input.  This allows us
  94   /// to avoid splitting the same node more than once.
  95   std::map<SDOperand, std::pair<SDOperand, SDOperand> > SplitNodes;
  96
  97   /// PackedNodes - For nodes that need to be packed from MVT::Vector types to
  98   /// concrete packed types, this contains the mapping of ones we have already
  99   /// processed to the result.
 100   std::map<SDOperand, SDOperand> PackedNodes;
 101
 102   void AddLegalizedOperand(SDOperand From, SDOperand To) {
 103     LegalizedNodes.insert(std::make_pair(From, To));
 104     // If someone requests legalization of the new node, return itself.
 105     if (From != To)
 106       LegalizedNodes.insert(std::make_pair(To, To));
 107   }
 108   void AddPromotedOperand(SDOperand From, SDOperand To) {
 109     bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second;
 110     assert(isNew && "Got into the map somehow?");
 111     // If someone requests legalization of the new node, return itself.
 112     LegalizedNodes.insert(std::make_pair(To, To));
 113   }
 114
 115 public:
 116
 117   SelectionDAGLegalize(SelectionDAG &DAG);
 118
 119   /// getTypeAction - Return how we should legalize values of this type, either
 120   /// it is already legal or we need to expand it into multiple registers of
 121   /// smaller integer type, or we need to promote it to a larger type.
 122   LegalizeAction getTypeAction(MVT::ValueType VT) const {
 123     return (LegalizeAction)ValueTypeActions.getTypeAction(VT);
 124   }
 125
 126   /// isTypeLegal - Return true if this type is legal on this target.
 127   ///
 128   bool isTypeLegal(MVT::ValueType VT) const {
 129     return getTypeAction(VT) == Legal;
 130   }
 131
 132   void LegalizeDAG();
 133
 134 private:
 135   /// HandleOp - Legalize, Promote, Expand or Pack the specified operand as
 136   /// appropriate for its type.
 137   void HandleOp(SDOperand Op);
 138
 139   /// LegalizeOp - We know that the specified value has a legal type.
 140   /// Recursively ensure that the operands have legal types, then return the
 141   /// result.
 142   SDOperand LegalizeOp(SDOperand O);
 143
 144   /// PromoteOp - Given an operation that produces a value in an invalid type,
 145   /// promote it to compute the value into a larger type.  The produced value
 146   /// will have the correct bits for the low portion of the register, but no
 147   /// guarantee is made about the top bits: it may be zero, sign-extended, or
 148   /// garbage.
 149   SDOperand PromoteOp(SDOperand O);
 150
 151   /// ExpandOp - Expand the specified SDOperand into its two component pieces
 152   /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this,
 153   /// the LegalizeNodes map is filled in for any results that are not expanded,
 154   /// the ExpandedNodes map is filled in for any results that are expanded, and
 155   /// the Lo/Hi values are returned.   This applies to integer types and Vector
 156   /// types.
 157   void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
 158
 159   /// SplitVectorOp - Given an operand of MVT::Vector type, break it down into
 160   /// two smaller values of MVT::Vector type.
 161   void SplitVectorOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
 162
 163   /// PackVectorOp - Given an operand of MVT::Vector type, convert it into the
 164   /// equivalent operation that returns a packed value (e.g. MVT::V4F32).  When
 165   /// this is called, we know that PackedVT is the right type for the result and
 166   /// we know that this type is legal for the target.
 167   SDOperand PackVectorOp(SDOperand O, MVT::ValueType PackedVT);
 168
 169   /// isShuffleLegal - Return true if a vector shuffle is legal with the
 170   /// specified mask and type.  Targets can specify exactly which masks they
 171   /// support and the code generator is tasked with not creating illegal masks.
 172   ///
 173   /// Note that this will also return true for shuffles that are promoted to a
 174   /// different type.
 175   ///
 176   /// If this is a legal shuffle, this method returns the (possibly promoted)
 177   /// build_vector Mask.  If it's not a legal shuffle, it returns null.
 178   SDNode *isShuffleLegal(MVT::ValueType VT, SDOperand Mask) const;
 179
 180   bool LegalizeAllNodesNotLeadingTo(SDNode *N, SDNode *Dest);
 181
 182   void LegalizeSetCCOperands(SDOperand &LHS, SDOperand &RHS, SDOperand &CC);
 183
 184   SDOperand CreateStackTemporary(MVT::ValueType VT);
 185
 186   SDOperand ExpandLibCall(const char *Name, SDNode *Node,
 187                           SDOperand &Hi);
 188   SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy,
 189                           SDOperand Source);
 190
 191   SDOperand ExpandBIT_CONVERT(MVT::ValueType DestVT, SDOperand SrcOp);
 192   SDOperand ExpandBUILD_VECTOR(SDNode *Node);
 193   SDOperand ExpandSCALAR_TO_VECTOR(SDNode *Node);
 194   SDOperand ExpandLegalINT_TO_FP(bool isSigned,
 195                                  SDOperand LegalOp,
 196                                  MVT::ValueType DestVT);
 197   SDOperand PromoteLegalINT_TO_FP(SDOperand LegalOp, MVT::ValueType DestVT,
 198                                   bool isSigned);
 199   SDOperand PromoteLegalFP_TO_INT(SDOperand LegalOp, MVT::ValueType DestVT,
 200                                   bool isSigned);
 201
 202   SDOperand ExpandBSWAP(SDOperand Op);
 203   SDOperand ExpandBitCount(unsigned Opc, SDOperand Op);
 204   bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt,
 205                    SDOperand &Lo, SDOperand &Hi);
 206   void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt,
 207                         SDOperand &Lo, SDOperand &Hi);
 208
 209   SDOperand LowerVEXTRACT_VECTOR_ELT(SDOperand Op);
 210   SDOperand ExpandEXTRACT_VECTOR_ELT(SDOperand Op);
 211
 212   SDOperand getIntPtrConstant(uint64_t Val) {
 213     return DAG.getConstant(Val, TLI.getPointerTy());
 214   }
 215 };
 216 }
 217
 218 /// isVectorShuffleLegal - Return true if a vector shuffle is legal with the
 219 /// specified mask and type.  Targets can specify exactly which masks they
 220 /// support and the code generator is tasked with not creating illegal masks.
 221 ///
 222 /// Note that this will also return true for shuffles that are promoted to a
 223 /// different type.
 224 SDNode *SelectionDAGLegalize::isShuffleLegal(MVT::ValueType VT,
 225                                              SDOperand Mask) const {
 226   switch (TLI.getOperationAction(ISD::VECTOR_SHUFFLE, VT)) {
 227   default: return 0;
 228   case TargetLowering::Legal:
 229   case TargetLowering::Custom:
 230     break;
 231   case TargetLowering::Promote: {
 232     // If this is promoted to a different type, convert the shuffle mask and
 233     // ask if it is legal in the promoted type!
 234     MVT::ValueType NVT = TLI.getTypeToPromoteTo(ISD::VECTOR_SHUFFLE, VT);
 235
 236     // If we changed # elements, change the shuffle mask.
 237     unsigned NumEltsGrowth =
 238       MVT::getVectorNumElements(NVT) / MVT::getVectorNumElements(VT);
 239     assert(NumEltsGrowth && "Cannot promote to vector type with fewer elts!");
 240     if (NumEltsGrowth > 1) {
 241       // Renumber the elements.
 242       std::vector<SDOperand> Ops;
 243       for (unsigned i = 0, e = Mask.getNumOperands(); i != e; ++i) {
 244         SDOperand InOp = Mask.getOperand(i);
 245         for (unsigned j = 0; j != NumEltsGrowth; ++j) {
 246           if (InOp.getOpcode() == ISD::UNDEF)
 247             Ops.push_back(DAG.getNode(ISD::UNDEF, MVT::i32));
 248           else {
 249             unsigned InEltNo = cast<ConstantSDNode>(InOp)->getValue();
 250             Ops.push_back(DAG.getConstant(InEltNo*NumEltsGrowth+j, MVT::i32));
 251           }
 252         }
 253       }
 254       Mask = DAG.getNode(ISD::BUILD_VECTOR, NVT, Ops);
 255     }
 256     VT = NVT;
 257     break;
 258   }
 259   }
 260   return TLI.isShuffleMaskLegal(Mask, VT) ? Mask.Val : 0;
 261 }
 262
 263 /// getScalarizedOpcode - Return the scalar opcode that corresponds to the
 264 /// specified vector opcode.
 265 static unsigned getScalarizedOpcode(unsigned VecOp, MVT::ValueType VT) {
 266   switch (VecOp) {
 267   default: assert(0 && "Don't know how to scalarize this opcode!");
 268   case ISD::VADD:  return MVT::isInteger(VT) ? ISD::ADD : ISD::FADD;
 269   case ISD::VSUB:  return MVT::isInteger(VT) ? ISD::SUB : ISD::FSUB;
 270   case ISD::VMUL:  return MVT::isInteger(VT) ? ISD::MUL : ISD::FMUL;
 271   case ISD::VSDIV: return MVT::isInteger(VT) ? ISD::SDIV: ISD::FDIV;
 272   case ISD::VUDIV: return MVT::isInteger(VT) ? ISD::UDIV: ISD::FDIV;
 273   case ISD::VAND:  return MVT::isInteger(VT) ? ISD::AND : 0;
 274   case ISD::VOR:   return MVT::isInteger(VT) ? ISD::OR  : 0;
 275   case ISD::VXOR:  return MVT::isInteger(VT) ? ISD::XOR : 0;
 276   }
 277 }
 278
 279 SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag)
 280   : TLI(dag.getTargetLoweringInfo()), DAG(dag),
 281     ValueTypeActions(TLI.getValueTypeActions()) {
 282   assert(MVT::LAST_VALUETYPE <= 32 &&
 283          "Too many value types for ValueTypeActions to hold!");
 284 }
 285
 286 /// ComputeTopDownOrdering - Add the specified node to the Order list if it has
 287 /// not been visited yet and if all of its operands have already been visited.
 288 static void ComputeTopDownOrdering(SDNode *N, std::vector<SDNode*> &Order,
 289                                    std::map<SDNode*, unsigned> &Visited) {
 290   if (++Visited[N] != N->getNumOperands())
 291     return;  // Haven't visited all operands yet
 292
 293   Order.push_back(N);
 294
 295   if (N->hasOneUse()) { // Tail recurse in common case.
 296     ComputeTopDownOrdering(*N->use_begin(), Order, Visited);
 297     return;
 298   }
 299
 300   // Now that we have N in, add anything that uses it if all of their operands
 301   // are now done.
 302   for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); UI != E;++UI)
 303     ComputeTopDownOrdering(*UI, Order, Visited);
 304 }
 305
 306
 307 void SelectionDAGLegalize::LegalizeDAG() {
 308   LastCALLSEQ_END = DAG.getEntryNode();
 309   IsLegalizingCall = false;
 310
 311   // The legalize process is inherently a bottom-up recursive process (users
 312   // legalize their uses before themselves).  Given infinite stack space, we
 313   // could just start legalizing on the root and traverse the whole graph.  In
 314   // practice however, this causes us to run out of stack space on large basic
 315   // blocks.  To avoid this problem, compute an ordering of the nodes where each
 316   // node is only legalized after all of its operands are legalized.
 317   std::map<SDNode*, unsigned> Visited;
 318   std::vector<SDNode*> Order;
 319
 320   // Compute ordering from all of the leaves in the graphs, those (like the
 321   // entry node) that have no operands.
 322   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 323        E = DAG.allnodes_end(); I != E; ++I) {
 324     if (I->getNumOperands() == 0) {
 325       Visited[I] = 0 - 1U;
 326       ComputeTopDownOrdering(I, Order, Visited);
 327     }
 328   }
 329
 330   assert(Order.size() == Visited.size() &&
 331          Order.size() ==
 332             (unsigned)std::distance(DAG.allnodes_begin(), DAG.allnodes_end()) &&
 333          "Error: DAG is cyclic!");
 334   Visited.clear();
 335
 336   for (unsigned i = 0, e = Order.size(); i != e; ++i)
 337     HandleOp(SDOperand(Order[i], 0));
 338
 339   // Finally, it's possible the root changed.  Get the new root.
 340   SDOperand OldRoot = DAG.getRoot();
 341   assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?");
 342   DAG.setRoot(LegalizedNodes[OldRoot]);
 343
 344   ExpandedNodes.clear();
 345   LegalizedNodes.clear();
 346   PromotedNodes.clear();
 347   SplitNodes.clear();
 348   PackedNodes.clear();
 349
 350   // Remove dead nodes now.
 351   DAG.RemoveDeadNodes(OldRoot.Val);
 352 }
 353
 354
 355 /// FindCallEndFromCallStart - Given a chained node that is part of a call
 356 /// sequence, find the CALLSEQ_END node that terminates the call sequence.
 357 static SDNode *FindCallEndFromCallStart(SDNode *Node) {
 358   if (Node->getOpcode() == ISD::CALLSEQ_END)
 359     return Node;
 360   if (Node->use_empty())
 361     return 0;   // No CallSeqEnd
 362
 363   // The chain is usually at the end.
 364   SDOperand TheChain(Node, Node->getNumValues()-1);
 365   if (TheChain.getValueType() != MVT::Other) {
 366     // Sometimes it's at the beginning.
 367     TheChain = SDOperand(Node, 0);
 368     if (TheChain.getValueType() != MVT::Other) {
 369       // Otherwise, hunt for it.
 370       for (unsigned i = 1, e = Node->getNumValues(); i != e; ++i)
 371         if (Node->getValueType(i) == MVT::Other) {
 372           TheChain = SDOperand(Node, i);
 373           break;
 374         }
 375
 376       // Otherwise, we walked into a node without a chain.
 377       if (TheChain.getValueType() != MVT::Other)
 378         return 0;
 379     }
 380   }
 381
 382   for (SDNode::use_iterator UI = Node->use_begin(),
 383        E = Node->use_end(); UI != E; ++UI) {
 384
 385     // Make sure to only follow users of our token chain.
 386     SDNode *User = *UI;
 387     for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
 388       if (User->getOperand(i) == TheChain)
 389         if (SDNode *Result = FindCallEndFromCallStart(User))
 390           return Result;
 391   }
 392   return 0;
 393 }
 394
 395 /// FindCallStartFromCallEnd - Given a chained node that is part of a call
 396 /// sequence, find the CALLSEQ_START node that initiates the call sequence.
 397 static SDNode *FindCallStartFromCallEnd(SDNode *Node) {
 398   assert(Node && "Didn't find callseq_start for a call??");
 399   if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
 400
 401   assert(Node->getOperand(0).getValueType() == MVT::Other &&
 402          "Node doesn't have a token chain argument!");
 403   return FindCallStartFromCallEnd(Node->getOperand(0).Val);
 404 }
 405
 406 /// LegalizeAllNodesNotLeadingTo - Recursively walk the uses of N, looking to
 407 /// see if any uses can reach Dest.  If no dest operands can get to dest,
 408 /// legalize them, legalize ourself, and return false, otherwise, return true.
 409 bool SelectionDAGLegalize::LegalizeAllNodesNotLeadingTo(SDNode *N,
 410                                                         SDNode *Dest) {
 411   if (N == Dest) return true;  // N certainly leads to Dest :)
 412
 413   // If the first result of this node has been already legalized, then it cannot
 414   // reach N.
 415   switch (getTypeAction(N->getValueType(0))) {
 416   case Legal:
 417     if (LegalizedNodes.count(SDOperand(N, 0))) return false;
 418     break;
 419   case Promote:
 420     if (PromotedNodes.count(SDOperand(N, 0))) return false;
 421     break;
 422   case Expand:
 423     if (ExpandedNodes.count(SDOperand(N, 0))) return false;
 424     break;
 425   }
 426
 427   // Okay, this node has not already been legalized.  Check and legalize all
 428   // operands.  If none lead to Dest, then we can legalize this node.
 429   bool OperandsLeadToDest = false;
 430   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 431     OperandsLeadToDest |=     // If an operand leads to Dest, so do we.
 432       LegalizeAllNodesNotLeadingTo(N->getOperand(i).Val, Dest);
 433
 434   if (OperandsLeadToDest) return true;
 435
 436   // Okay, this node looks safe, legalize it and return false.
 437   HandleOp(SDOperand(N, 0));
 438   return false;
 439 }
 440
 441 /// HandleOp - Legalize, Promote, Expand or Pack the specified operand as
 442 /// appropriate for its type.
 443 void SelectionDAGLegalize::HandleOp(SDOperand Op) {
 444   switch (getTypeAction(Op.getValueType())) {
 445   default: assert(0 && "Bad type action!");
 446   case Legal:   LegalizeOp(Op); break;
 447   case Promote: PromoteOp(Op);  break;
 448   case Expand:
 449     if (Op.getValueType() != MVT::Vector) {
 450       SDOperand X, Y;
 451       ExpandOp(Op, X, Y);
 452     } else {
 453       SDNode *N = Op.Val;
 454       unsigned NumOps = N->getNumOperands();
 455       unsigned NumElements =
 456         cast<ConstantSDNode>(N->getOperand(NumOps-2))->getValue();
 457       MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(NumOps-1))->getVT();
 458       MVT::ValueType PackedVT = getVectorType(EVT, NumElements);
 459       if (PackedVT != MVT::Other && TLI.isTypeLegal(PackedVT)) {
 460         // In the common case, this is a legal vector type, convert it to the
 461         // packed operation and type now.
 462         PackVectorOp(Op, PackedVT);
 463       } else if (NumElements == 1) {
 464         // Otherwise, if this is a single element vector, convert it to a
 465         // scalar operation.
 466         PackVectorOp(Op, EVT);
 467       } else {
 468         // Otherwise, this is a multiple element vector that isn't supported.
 469         // Split it in half and legalize both parts.
 470         SDOperand X, Y;
 471         SplitVectorOp(Op, X, Y);
 472       }
 473     }
 474     break;
 475   }
 476 }
 477
 478
 479 /// LegalizeOp - We know that the specified value has a legal type.
 480 /// Recursively ensure that the operands have legal types, then return the
 481 /// result.
 482 SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 483   assert(isTypeLegal(Op.getValueType()) &&
 484          "Caller should expand or promote operands that are not legal!");
 485   SDNode *Node = Op.Val;
 486
 487   // If this operation defines any values that cannot be represented in a
 488   // register on this target, make sure to expand or promote them.
 489   if (Node->getNumValues() > 1) {
 490     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 491       if (getTypeAction(Node->getValueType(i)) != Legal) {
 492         HandleOp(Op.getValue(i));
 493         assert(LegalizedNodes.count(Op) &&
 494                "Handling didn't add legal operands!");
 495         return LegalizedNodes[Op];
 496       }
 497   }
 498
 499   // Note that LegalizeOp may be reentered even from single-use nodes, which
 500   // means that we always must cache transformed nodes.
 501   std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
 502   if (I != LegalizedNodes.end()) return I->second;
 503
 504   SDOperand Tmp1, Tmp2, Tmp3, Tmp4;
 505   SDOperand Result = Op;
 506   bool isCustom = false;
 507
 508   switch (Node->getOpcode()) {
 509   case ISD::FrameIndex:
 510   case ISD::EntryToken:
 511   case ISD::Register:
 512   case ISD::BasicBlock:
 513   case ISD::TargetFrameIndex:
 514   case ISD::TargetJumpTable:
 515   case ISD::TargetConstant:
 516   case ISD::TargetConstantFP:
 517   case ISD::TargetConstantPool:
 518   case ISD::TargetGlobalAddress:
 519   case ISD::TargetExternalSymbol:
 520   case ISD::VALUETYPE:
 521   case ISD::SRCVALUE:
 522   case ISD::STRING:
 523   case ISD::CONDCODE:
 524     // Primitives must all be legal.
 525     assert(TLI.isOperationLegal(Node->getValueType(0), Node->getValueType(0)) &&
 526            "This must be legal!");
 527     break;
 528   default:
 529     if (Node->getOpcode() >= ISD::BUILTIN_OP_END) {
 530       // If this is a target node, legalize it by legalizing the operands then
 531       // passing it through.
 532       std::vector<SDOperand> Ops;
 533       for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 534         Ops.push_back(LegalizeOp(Node->getOperand(i)));
 535
 536       Result = DAG.UpdateNodeOperands(Result.getValue(0), Ops);
 537
 538       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 539         AddLegalizedOperand(Op.getValue(i), Result.getValue(i));
 540       return Result.getValue(Op.ResNo);
 541     }
 542     // Otherwise this is an unhandled builtin node.  splat.
 543     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 544     assert(0 && "Do not know how to legalize this operator!");
 545     abort();
 546   case ISD::GlobalAddress:
 547   case ISD::ExternalSymbol:
 548   case ISD::ConstantPool:
 549   case ISD::JumpTable: // Nothing to do.
 550     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
 551     default: assert(0 && "This action is not supported yet!");
 552     case TargetLowering::Custom:
 553       Tmp1 = TLI.LowerOperation(Op, DAG);
 554       if (Tmp1.Val) Result = Tmp1;
 555       // FALLTHROUGH if the target doesn't want to lower this op after all.
 556     case TargetLowering::Legal:
 557       break;
 558     }
 559     break;
 560   case ISD::AssertSext:
 561   case ISD::AssertZext:
 562     Tmp1 = LegalizeOp(Node->getOperand(0));
 563     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
 564     break;
 565   case ISD::MERGE_VALUES:
 566     // Legalize eliminates MERGE_VALUES nodes.
 567     Result = Node->getOperand(Op.ResNo);
 568     break;
 569   case ISD::CopyFromReg:
 570     Tmp1 = LegalizeOp(Node->getOperand(0));
 571     Result = Op.getValue(0);
 572     if (Node->getNumValues() == 2) {
 573       Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
 574     } else {
 575       assert(Node->getNumValues() == 3 && "Invalid copyfromreg!");
 576       if (Node->getNumOperands() == 3) {
 577         Tmp2 = LegalizeOp(Node->getOperand(2));
 578         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1),Tmp2);
 579       } else {
 580         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
 581       }
 582       AddLegalizedOperand(Op.getValue(2), Result.getValue(2));
 583     }
 584     // Since CopyFromReg produces two values, make sure to remember that we
 585     // legalized both of them.
 586     AddLegalizedOperand(Op.getValue(0), Result);
 587     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
 588     return Result.getValue(Op.ResNo);
 589   case ISD::UNDEF: {
 590     MVT::ValueType VT = Op.getValueType();
 591     switch (TLI.getOperationAction(ISD::UNDEF, VT)) {
 592     default: assert(0 && "This action is not supported yet!");
 593     case TargetLowering::Expand:
 594       if (MVT::isInteger(VT))
 595         Result = DAG.getConstant(0, VT);
 596       else if (MVT::isFloatingPoint(VT))
 597         Result = DAG.getConstantFP(0, VT);
 598       else
 599         assert(0 && "Unknown value type!");
 600       break;
 601     case TargetLowering::Legal:
 602       break;
 603     }
 604     break;
 605   }
 606
 607   case ISD::INTRINSIC_W_CHAIN:
 608   case ISD::INTRINSIC_WO_CHAIN:
 609   case ISD::INTRINSIC_VOID: {
 610     std::vector<SDOperand> Ops;
 611     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 612       Ops.push_back(LegalizeOp(Node->getOperand(i)));
 613     Result = DAG.UpdateNodeOperands(Result, Ops);
 614
 615     // Allow the target to custom lower its intrinsics if it wants to.
 616     if (TLI.getOperationAction(Node->getOpcode(), MVT::Other) ==
 617         TargetLowering::Custom) {
 618       Tmp3 = TLI.LowerOperation(Result, DAG);
 619       if (Tmp3.Val) Result = Tmp3;
 620     }
 621
 622     if (Result.Val->getNumValues() == 1) break;
 623
 624     // Must have return value and chain result.
 625     assert(Result.Val->getNumValues() == 2 &&
 626            "Cannot return more than two values!");
 627
 628     // Since loads produce two values, make sure to remember that we
 629     // legalized both of them.
 630     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
 631     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 632     return Result.getValue(Op.ResNo);
 633   }
 634
 635   case ISD::LOCATION:
 636     assert(Node->getNumOperands() == 5 && "Invalid LOCATION node!");
 637     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the input chain.
 638
 639     switch (TLI.getOperationAction(ISD::LOCATION, MVT::Other)) {
 640     case TargetLowering::Promote:
 641     default: assert(0 && "This action is not supported yet!");
 642     case TargetLowering::Expand: {
 643       MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo();
 644       bool useDEBUG_LOC = TLI.isOperationLegal(ISD::DEBUG_LOC, MVT::Other);
 645       bool useDEBUG_LABEL = TLI.isOperationLegal(ISD::DEBUG_LABEL, MVT::Other);
 646
 647       if (DebugInfo && (useDEBUG_LOC || useDEBUG_LABEL)) {
 648         const std::string &FName =
 649           cast<StringSDNode>(Node->getOperand(3))->getValue();
 650         const std::string &DirName =
 651           cast<StringSDNode>(Node->getOperand(4))->getValue();
 652         unsigned SrcFile = DebugInfo->RecordSource(DirName, FName);
 653
 654         std::vector<SDOperand> Ops;
 655         Ops.push_back(Tmp1);  // chain
 656         SDOperand LineOp = Node->getOperand(1);
 657         SDOperand ColOp = Node->getOperand(2);
 658
 659         if (useDEBUG_LOC) {
 660           Ops.push_back(LineOp);  // line #
 661           Ops.push_back(ColOp);  // col #
 662           Ops.push_back(DAG.getConstant(SrcFile, MVT::i32));  // source file id
 663           Result = DAG.getNode(ISD::DEBUG_LOC, MVT::Other, Ops);
 664         } else {
 665           unsigned Line = cast<ConstantSDNode>(LineOp)->getValue();
 666           unsigned Col = cast<ConstantSDNode>(ColOp)->getValue();
 667           unsigned ID = DebugInfo->RecordLabel(Line, Col, SrcFile);
 668           Ops.push_back(DAG.getConstant(ID, MVT::i32));
 669           Result = DAG.getNode(ISD::DEBUG_LABEL, MVT::Other, Ops);
 670         }
 671       } else {
 672         Result = Tmp1;  // chain
 673       }
 674       break;
 675     }
 676     case TargetLowering::Legal:
 677       if (Tmp1 != Node->getOperand(0) ||
 678           getTypeAction(Node->getOperand(1).getValueType()) == Promote) {
 679         std::vector<SDOperand> Ops;
 680         Ops.push_back(Tmp1);
 681         if (getTypeAction(Node->getOperand(1).getValueType()) == Legal) {
 682           Ops.push_back(Node->getOperand(1));  // line # must be legal.
 683           Ops.push_back(Node->getOperand(2));  // col # must be legal.
 684         } else {
 685           // Otherwise promote them.
 686           Ops.push_back(PromoteOp(Node->getOperand(1)));
 687           Ops.push_back(PromoteOp(Node->getOperand(2)));
 688         }
 689         Ops.push_back(Node->getOperand(3));  // filename must be legal.
 690         Ops.push_back(Node->getOperand(4));  // working dir # must be legal.
 691         Result = DAG.UpdateNodeOperands(Result, Ops);
 692       }
 693       break;
 694     }
 695     break;
 696
 697   case ISD::DEBUG_LOC:
 698     assert(Node->getNumOperands() == 4 && "Invalid DEBUG_LOC node!");
 699     switch (TLI.getOperationAction(ISD::DEBUG_LOC, MVT::Other)) {
 700     default: assert(0 && "This action is not supported yet!");
 701     case TargetLowering::Legal:
 702       Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 703       Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the line #.
 704       Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the col #.
 705       Tmp4 = LegalizeOp(Node->getOperand(3));  // Legalize the source file id.
 706       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4);
 707       break;
 708     }
 709     break;
 710
 711   case ISD::DEBUG_LABEL:
 712     assert(Node->getNumOperands() == 2 && "Invalid DEBUG_LABEL node!");
 713     switch (TLI.getOperationAction(ISD::DEBUG_LABEL, MVT::Other)) {
 714     default: assert(0 && "This action is not supported yet!");
 715     case TargetLowering::Legal:
 716       Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 717       Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the label id.
 718       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
 719       break;
 720     }
 721     break;
 722
 723   case ISD::Constant:
 724     // We know we don't need to expand constants here, constants only have one
 725     // value and we check that it is fine above.
 726
 727     // FIXME: Maybe we should handle things like targets that don't support full
 728     // 32-bit immediates?
 729     break;
 730   case ISD::ConstantFP: {
 731     // Spill FP immediates to the constant pool if the target cannot directly
 732     // codegen them.  Targets often have some immediate values that can be
 733     // efficiently generated into an FP register without a load.  We explicitly
 734     // leave these constants as ConstantFP nodes for the target to deal with.
 735     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
 736
 737     // Check to see if this FP immediate is already legal.
 738     bool isLegal = false;
 739     for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
 740            E = TLI.legal_fpimm_end(); I != E; ++I)
 741       if (CFP->isExactlyValue(*I)) {
 742         isLegal = true;
 743         break;
 744       }
 745
 746     // If this is a legal constant, turn it into a TargetConstantFP node.
 747     if (isLegal) {
 748       Result = DAG.getTargetConstantFP(CFP->getValue(), CFP->getValueType(0));
 749       break;
 750     }
 751
 752     switch (TLI.getOperationAction(ISD::ConstantFP, CFP->getValueType(0))) {
 753     default: assert(0 && "This action is not supported yet!");
 754     case TargetLowering::Custom:
 755       Tmp3 = TLI.LowerOperation(Result, DAG);
 756       if (Tmp3.Val) {
 757         Result = Tmp3;
 758         break;
 759       }
 760       // FALLTHROUGH
 761     case TargetLowering::Expand:
 762       // Otherwise we need to spill the constant to memory.
 763       bool Extend = false;
 764
 765       // If a FP immediate is precise when represented as a float and if the
 766       // target can do an extending load from float to double, we put it into
 767       // the constant pool as a float, even if it's is statically typed as a
 768       // double.
 769       MVT::ValueType VT = CFP->getValueType(0);
 770       bool isDouble = VT == MVT::f64;
 771       ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
 772                                              Type::FloatTy, CFP->getValue());
 773       if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) &&
 774           // Only do this if the target has a native EXTLOAD instruction from
 775           // f32.
 776           TLI.isOperationLegal(ISD::EXTLOAD, MVT::f32)) {
 777         LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
 778         VT = MVT::f32;
 779         Extend = true;
 780       }
 781
 782       SDOperand CPIdx = DAG.getConstantPool(LLVMC, TLI.getPointerTy());
 783       if (Extend) {
 784         Result = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
 785                                 CPIdx, DAG.getSrcValue(NULL), MVT::f32);
 786       } else {
 787         Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx,
 788                              DAG.getSrcValue(NULL));
 789       }
 790     }
 791     break;
 792   }
 793   case ISD::TokenFactor:
 794     if (Node->getNumOperands() == 2) {
 795       Tmp1 = LegalizeOp(Node->getOperand(0));
 796       Tmp2 = LegalizeOp(Node->getOperand(1));
 797       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
 798     } else if (Node->getNumOperands() == 3) {
 799       Tmp1 = LegalizeOp(Node->getOperand(0));
 800       Tmp2 = LegalizeOp(Node->getOperand(1));
 801       Tmp3 = LegalizeOp(Node->getOperand(2));
 802       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
 803     } else {
 804       std::vector<SDOperand> Ops;
 805       // Legalize the operands.
 806       for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 807         Ops.push_back(LegalizeOp(Node->getOperand(i)));
 808       Result = DAG.UpdateNodeOperands(Result, Ops);
 809     }
 810     break;
 811
 812   case ISD::FORMAL_ARGUMENTS:
 813   case ISD::CALL:
 814     // The only option for this is to custom lower it.
 815     Tmp3 = TLI.LowerOperation(Result.getValue(0), DAG);
 816     assert(Tmp3.Val && "Target didn't custom lower this node!");
 817     assert(Tmp3.Val->getNumValues() == Result.Val->getNumValues() &&
 818            "Lowering call/formal_arguments produced unexpected # results!");
 819
 820     // Since CALL/FORMAL_ARGUMENTS nodes produce multiple values, make sure to
 821     // remember that we legalized all of them, so it doesn't get relegalized.
 822     for (unsigned i = 0, e = Tmp3.Val->getNumValues(); i != e; ++i) {
 823       Tmp1 = LegalizeOp(Tmp3.getValue(i));
 824       if (Op.ResNo == i)
 825         Tmp2 = Tmp1;
 826       AddLegalizedOperand(SDOperand(Node, i), Tmp1);
 827     }
 828     return Tmp2;
 829
 830   case ISD::BUILD_VECTOR:
 831     switch (TLI.getOperationAction(ISD::BUILD_VECTOR, Node->getValueType(0))) {
 832     default: assert(0 && "This action is not supported yet!");
 833     case TargetLowering::Custom:
 834       Tmp3 = TLI.LowerOperation(Result, DAG);
 835       if (Tmp3.Val) {
 836         Result = Tmp3;
 837         break;
 838       }
 839       // FALLTHROUGH
 840     case TargetLowering::Expand:
 841       Result = ExpandBUILD_VECTOR(Result.Val);
 842       break;
 843     }
 844     break;
 845   case ISD::INSERT_VECTOR_ELT:
 846     Tmp1 = LegalizeOp(Node->getOperand(0));  // InVec
 847     Tmp2 = LegalizeOp(Node->getOperand(1));  // InVal
 848     Tmp3 = LegalizeOp(Node->getOperand(2));  // InEltNo
 849     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
 850
 851     switch (TLI.getOperationAction(ISD::INSERT_VECTOR_ELT,
 852                                    Node->getValueType(0))) {
 853     default: assert(0 && "This action is not supported yet!");
 854     case TargetLowering::Legal:
 855       break;
 856     case TargetLowering::Custom:
 857       Tmp3 = TLI.LowerOperation(Result, DAG);
 858       if (Tmp3.Val) {
 859         Result = Tmp3;
 860         break;
 861       }
 862       // FALLTHROUGH
 863     case TargetLowering::Expand: {
 864       // If the insert index is a constant, codegen this as a scalar_to_vector,
 865       // then a shuffle that inserts it into the right position in the vector.
 866       if (ConstantSDNode *InsertPos = dyn_cast<ConstantSDNode>(Tmp3)) {
 867         SDOperand ScVec = DAG.getNode(ISD::SCALAR_TO_VECTOR,
 868                                       Tmp1.getValueType(), Tmp2);
 869
 870         unsigned NumElts = MVT::getVectorNumElements(Tmp1.getValueType());
 871         MVT::ValueType ShufMaskVT = MVT::getIntVectorWithNumElements(NumElts);
 872         MVT::ValueType ShufMaskEltVT = MVT::getVectorBaseType(ShufMaskVT);
 873
 874         // We generate a shuffle of InVec and ScVec, so the shuffle mask should
 875         // be 0,1,2,3,4,5... with the appropriate element replaced with elt 0 of
 876         // the RHS.
 877         std::vector<SDOperand> ShufOps;
 878         for (unsigned i = 0; i != NumElts; ++i) {
 879           if (i != InsertPos->getValue())
 880             ShufOps.push_back(DAG.getConstant(i, ShufMaskEltVT));
 881           else
 882             ShufOps.push_back(DAG.getConstant(NumElts, ShufMaskEltVT));
 883         }
 884         SDOperand ShufMask = DAG.getNode(ISD::BUILD_VECTOR, ShufMaskVT,ShufOps);
 885
 886         Result = DAG.getNode(ISD::VECTOR_SHUFFLE, Tmp1.getValueType(),
 887                              Tmp1, ScVec, ShufMask);
 888         Result = LegalizeOp(Result);
 889         break;
 890       }
 891
 892       // If the target doesn't support this, we have to spill the input vector
 893       // to a temporary stack slot, update the element, then reload it.  This is
 894       // badness.  We could also load the value into a vector register (either
 895       // with a "move to register" or "extload into register" instruction, then
 896       // permute it into place, if the idx is a constant and if the idx is
 897       // supported by the target.
 898       MVT::ValueType VT    = Tmp1.getValueType();
 899       MVT::ValueType EltVT = Tmp2.getValueType();
 900       MVT::ValueType IdxVT = Tmp3.getValueType();
 901       MVT::ValueType PtrVT = TLI.getPointerTy();
 902       SDOperand StackPtr = CreateStackTemporary(VT);
 903       // Store the vector.
 904       SDOperand Ch = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
 905                                  Tmp1, StackPtr, DAG.getSrcValue(NULL));
 906
 907       // Truncate or zero extend offset to target pointer type.
 908       unsigned CastOpc = (IdxVT > PtrVT) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
 909       Tmp3 = DAG.getNode(CastOpc, PtrVT, Tmp3);
 910       // Add the offset to the index.
 911       unsigned EltSize = MVT::getSizeInBits(EltVT)/8;
 912       Tmp3 = DAG.getNode(ISD::MUL, IdxVT, Tmp3,DAG.getConstant(EltSize, IdxVT));
 913       SDOperand StackPtr2 = DAG.getNode(ISD::ADD, IdxVT, Tmp3, StackPtr);
 914       // Store the scalar value.
 915       Ch = DAG.getNode(ISD::STORE, MVT::Other, Ch,
 916                        Tmp2, StackPtr2, DAG.getSrcValue(NULL));
 917       // Load the updated vector.
 918       Result = DAG.getLoad(VT, Ch, StackPtr, DAG.getSrcValue(NULL));
 919       break;
 920     }
 921     }
 922     break;
 923   case ISD::SCALAR_TO_VECTOR:
 924     if (!TLI.isTypeLegal(Node->getOperand(0).getValueType())) {
 925       Result = LegalizeOp(ExpandSCALAR_TO_VECTOR(Node));
 926       break;
 927     }
 928
 929     Tmp1 = LegalizeOp(Node->getOperand(0));  // InVal
 930     Result = DAG.UpdateNodeOperands(Result, Tmp1);
 931     switch (TLI.getOperationAction(ISD::SCALAR_TO_VECTOR,
 932                                    Node->getValueType(0))) {
 933     default: assert(0 && "This action is not supported yet!");
 934     case TargetLowering::Legal:
 935       break;
 936     case TargetLowering::Custom:
 937       Tmp3 = TLI.LowerOperation(Result, DAG);
 938       if (Tmp3.Val) {
 939         Result = Tmp3;
 940         break;
 941       }
 942       // FALLTHROUGH
 943     case TargetLowering::Expand:
 944       Result = LegalizeOp(ExpandSCALAR_TO_VECTOR(Node));
 945       break;
 946     }
 947     break;
 948   case ISD::VECTOR_SHUFFLE:
 949     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the input vectors,
 950     Tmp2 = LegalizeOp(Node->getOperand(1));   // but not the shuffle mask.
 951     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
 952
 953     // Allow targets to custom lower the SHUFFLEs they support.
 954     switch (TLI.getOperationAction(ISD::VECTOR_SHUFFLE,Result.getValueType())) {
 955     default: assert(0 && "Unknown operation action!");
 956     case TargetLowering::Legal:
 957       assert(isShuffleLegal(Result.getValueType(), Node->getOperand(2)) &&
 958              "vector shuffle should not be created if not legal!");
 959       break;
 960     case TargetLowering::Custom:
 961       Tmp3 = TLI.LowerOperation(Result, DAG);
 962       if (Tmp3.Val) {
 963         Result = Tmp3;
 964         break;
 965       }
 966       // FALLTHROUGH
 967     case TargetLowering::Expand: {
 968       MVT::ValueType VT = Node->getValueType(0);
 969       MVT::ValueType EltVT = MVT::getVectorBaseType(VT);
 970       MVT::ValueType PtrVT = TLI.getPointerTy();
 971       SDOperand Mask = Node->getOperand(2);
 972       unsigned NumElems = Mask.getNumOperands();
 973       std::vector<SDOperand> Ops;
 974       for (unsigned i = 0; i != NumElems; ++i) {
 975         SDOperand Arg = Mask.getOperand(i);
 976         if (Arg.getOpcode() == ISD::UNDEF) {
 977           Ops.push_back(DAG.getNode(ISD::UNDEF, EltVT));
 978         } else {
 979           assert(isa<ConstantSDNode>(Arg) && "Invalid VECTOR_SHUFFLE mask!");
 980           unsigned Idx = cast<ConstantSDNode>(Arg)->getValue();
 981           if (Idx < NumElems)
 982             Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, Tmp1,
 983                                       DAG.getConstant(Idx, PtrVT)));
 984           else
 985             Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, Tmp2,
 986                                       DAG.getConstant(Idx - NumElems, PtrVT)));
 987         }
 988       }
 989       Result = DAG.getNode(ISD::BUILD_VECTOR, VT, Ops);
 990       break;
 991     }
 992     case TargetLowering::Promote: {
 993       // Change base type to a different vector type.
 994       MVT::ValueType OVT = Node->getValueType(0);
 995       MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
 996
 997       // Cast the two input vectors.
 998       Tmp1 = DAG.getNode(ISD::BIT_CONVERT, NVT, Tmp1);
 999       Tmp2 = DAG.getNode(ISD::BIT_CONVERT, NVT, Tmp2);
1000
1001       // Convert the shuffle mask to the right # elements.
1002       Tmp3 = SDOperand(isShuffleLegal(OVT, Node->getOperand(2)), 0);
1003       assert(Tmp3.Val && "Shuffle not legal?");
1004       Result = DAG.getNode(ISD::VECTOR_SHUFFLE, NVT, Tmp1, Tmp2, Tmp3);
1005       Result = DAG.getNode(ISD::BIT_CONVERT, OVT, Result);
1006       break;
1007     }
1008     }
1009     break;
1010
1011   case ISD::EXTRACT_VECTOR_ELT:
1012     Tmp1 = LegalizeOp(Node->getOperand(0));
1013     Tmp2 = LegalizeOp(Node->getOperand(1));
1014     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1015
1016     switch (TLI.getOperationAction(ISD::EXTRACT_VECTOR_ELT,
1017                                    Tmp1.getValueType())) {
1018     default: assert(0 && "This action is not supported yet!");
1019     case TargetLowering::Legal:
1020       break;
1021     case TargetLowering::Custom:
1022       Tmp3 = TLI.LowerOperation(Result, DAG);
1023       if (Tmp3.Val) {
1024         Result = Tmp3;
1025         break;
1026       }
1027       // FALLTHROUGH
1028     case TargetLowering::Expand:
1029       Result = ExpandEXTRACT_VECTOR_ELT(Result);
1030       break;
1031     }
1032     break;
1033
1034   case ISD::VEXTRACT_VECTOR_ELT:
1035     Result = LegalizeOp(LowerVEXTRACT_VECTOR_ELT(Op));
1036     break;
1037
1038   case ISD::CALLSEQ_START: {
1039     SDNode *CallEnd = FindCallEndFromCallStart(Node);
1040
1041     // Recursively Legalize all of the inputs of the call end that do not lead
1042     // to this call start.  This ensures that any libcalls that need be inserted
1043     // are inserted *before* the CALLSEQ_START.
1044     for (unsigned i = 0, e = CallEnd->getNumOperands(); i != e; ++i)
1045       LegalizeAllNodesNotLeadingTo(CallEnd->getOperand(i).Val, Node);
1046
1047     // Now that we legalized all of the inputs (which may have inserted
1048     // libcalls) create the new CALLSEQ_START node.
1049     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1050
1051     // Merge in the last call, to ensure that this call start after the last
1052     // call ended.
1053     if (LastCALLSEQ_END.getOpcode() != ISD::EntryToken) {
1054       Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1055       Tmp1 = LegalizeOp(Tmp1);
1056     }
1057
1058     // Do not try to legalize the target-specific arguments (#1+).
1059     if (Tmp1 != Node->getOperand(0)) {
1060       std::vector<SDOperand> Ops(Node->op_begin(), Node->op_end());
1061       Ops[0] = Tmp1;
1062       Result = DAG.UpdateNodeOperands(Result, Ops);
1063     }
1064
1065     // Remember that the CALLSEQ_START is legalized.
1066     AddLegalizedOperand(Op.getValue(0), Result);
1067     if (Node->getNumValues() == 2)    // If this has a flag result, remember it.
1068       AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1069
1070     // Now that the callseq_start and all of the non-call nodes above this call
1071     // sequence have been legalized, legalize the call itself.  During this
1072     // process, no libcalls can/will be inserted, guaranteeing that no calls
1073     // can overlap.
1074     assert(!IsLegalizingCall && "Inconsistent sequentialization of calls!");
1075     SDOperand InCallSEQ = LastCALLSEQ_END;
1076     // Note that we are selecting this call!
1077     LastCALLSEQ_END = SDOperand(CallEnd, 0);
1078     IsLegalizingCall = true;
1079
1080     // Legalize the call, starting from the CALLSEQ_END.
1081     LegalizeOp(LastCALLSEQ_END);
1082     assert(!IsLegalizingCall && "CALLSEQ_END should have cleared this!");
1083     return Result;
1084   }
1085   case ISD::CALLSEQ_END:
1086     // If the CALLSEQ_START node hasn't been legalized first, legalize it.  This
1087     // will cause this node to be legalized as well as handling libcalls right.
1088     if (LastCALLSEQ_END.Val != Node) {
1089       LegalizeOp(SDOperand(FindCallStartFromCallEnd(Node), 0));
1090       std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
1091       assert(I != LegalizedNodes.end() &&
1092              "Legalizing the call start should have legalized this node!");
1093       return I->second;
1094     }
1095
1096     // Otherwise, the call start has been legalized and everything is going
1097     // according to plan.  Just legalize ourselves normally here.
1098     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1099     // Do not try to legalize the target-specific arguments (#1+), except for
1100     // an optional flag input.
1101     if (Node->getOperand(Node->getNumOperands()-1).getValueType() != MVT::Flag){
1102       if (Tmp1 != Node->getOperand(0)) {
1103         std::vector<SDOperand> Ops(Node->op_begin(), Node->op_end());
1104         Ops[0] = Tmp1;
1105         Result = DAG.UpdateNodeOperands(Result, Ops);
1106       }
1107     } else {
1108       Tmp2 = LegalizeOp(Node->getOperand(Node->getNumOperands()-1));
1109       if (Tmp1 != Node->getOperand(0) ||
1110           Tmp2 != Node->getOperand(Node->getNumOperands()-1)) {
1111         std::vector<SDOperand> Ops(Node->op_begin(), Node->op_end());
1112         Ops[0] = Tmp1;
1113         Ops.back() = Tmp2;
1114         Result = DAG.UpdateNodeOperands(Result, Ops);
1115       }
1116     }
1117     assert(IsLegalizingCall && "Call sequence imbalance between start/end?");
1118     // This finishes up call legalization.
1119     IsLegalizingCall = false;
1120
1121     // If the CALLSEQ_END node has a flag, remember that we legalized it.
1122     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1123     if (Node->getNumValues() == 2)
1124       AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1125     return Result.getValue(Op.ResNo);
1126   case ISD::DYNAMIC_STACKALLOC: {
1127     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1128     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
1129     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
1130     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1131
1132     Tmp1 = Result.getValue(0);
1133     Tmp2 = Result.getValue(1);
1134     switch (TLI.getOperationAction(Node->getOpcode(),
1135                                    Node->getValueType(0))) {
1136     default: assert(0 && "This action is not supported yet!");
1137     case TargetLowering::Expand: {
1138       unsigned SPReg = TLI.getStackPointerRegisterToSaveRestore();
1139       assert(SPReg && "Target cannot require DYNAMIC_STACKALLOC expansion and"
1140              " not tell us which reg is the stack pointer!");
1141       SDOperand Chain = Tmp1.getOperand(0);
1142       SDOperand Size  = Tmp2.getOperand(1);
1143       SDOperand SP = DAG.getCopyFromReg(Chain, SPReg, Node->getValueType(0));
1144       Tmp1 = DAG.getNode(ISD::SUB, Node->getValueType(0), SP, Size);    // Value
1145       Tmp2 = DAG.getCopyToReg(SP.getValue(1), SPReg, Tmp1);      // Output chain
1146       Tmp1 = LegalizeOp(Tmp1);
1147       Tmp2 = LegalizeOp(Tmp2);
1148       break;
1149     }
1150     case TargetLowering::Custom:
1151       Tmp3 = TLI.LowerOperation(Tmp1, DAG);
1152       if (Tmp3.Val) {
1153         Tmp1 = LegalizeOp(Tmp3);
1154         Tmp2 = LegalizeOp(Tmp3.getValue(1));
1155       }
1156       break;
1157     case TargetLowering::Legal:
1158       break;
1159     }
1160     // Since this op produce two values, make sure to remember that we
1161     // legalized both of them.
1162     AddLegalizedOperand(SDOperand(Node, 0), Tmp1);
1163     AddLegalizedOperand(SDOperand(Node, 1), Tmp2);
1164     return Op.ResNo ? Tmp2 : Tmp1;
1165   }
1166   case ISD::INLINEASM:
1167     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize Chain.
1168     Tmp2 = Node->getOperand(Node->getNumOperands()-1);
1169     if (Tmp2.getValueType() == MVT::Flag)     // Legalize Flag if it exists.
1170       Tmp2 = Tmp3 = SDOperand(0, 0);
1171     else
1172       Tmp3 = LegalizeOp(Tmp2);
1173
1174     if (Tmp1 != Node->getOperand(0) || Tmp2 != Tmp3) {
1175       std::vector<SDOperand> Ops(Node->op_begin(), Node->op_end());
1176       Ops[0] = Tmp1;
1177       if (Tmp3.Val) Ops.back() = Tmp3;
1178       Result = DAG.UpdateNodeOperands(Result, Ops);
1179     }
1180
1181     // INLINE asm returns a chain and flag, make sure to add both to the map.
1182     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1183     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1184     return Result.getValue(Op.ResNo);
1185   case ISD::BR:
1186     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1187     // Ensure that libcalls are emitted before a branch.
1188     Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1189     Tmp1 = LegalizeOp(Tmp1);
1190     LastCALLSEQ_END = DAG.getEntryNode();
1191
1192     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
1193     break;
1194   case ISD::BRIND:
1195     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1196     // Ensure that libcalls are emitted before a branch.
1197     Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1198     Tmp1 = LegalizeOp(Tmp1);
1199     LastCALLSEQ_END = DAG.getEntryNode();
1200
1201     switch (getTypeAction(Node->getOperand(1).getValueType())) {
1202     default: assert(0 && "Indirect target must be legal type (pointer)!");
1203     case Legal:
1204       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
1205       break;
1206     }
1207     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1208     break;
1209   case ISD::BRCOND:
1210     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1211     // Ensure that libcalls are emitted before a return.
1212     Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1213     Tmp1 = LegalizeOp(Tmp1);
1214     LastCALLSEQ_END = DAG.getEntryNode();
1215
1216     switch (getTypeAction(Node->getOperand(1).getValueType())) {
1217     case Expand: assert(0 && "It's impossible to expand bools");
1218     case Legal:
1219       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
1220       break;
1221     case Promote:
1222       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
1223       break;
1224     }
1225
1226     // Basic block destination (Op#2) is always legal.
1227     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1228
1229     switch (TLI.getOperationAction(ISD::BRCOND, MVT::Other)) {
1230     default: assert(0 && "This action is not supported yet!");
1231     case TargetLowering::Legal: break;
1232     case TargetLowering::Custom:
1233       Tmp1 = TLI.LowerOperation(Result, DAG);
1234       if (Tmp1.Val) Result = Tmp1;
1235       break;
1236     case TargetLowering::Expand:
1237       // Expand brcond's setcc into its constituent parts and create a BR_CC
1238       // Node.
1239       if (Tmp2.getOpcode() == ISD::SETCC) {
1240         Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Tmp2.getOperand(2),
1241                              Tmp2.getOperand(0), Tmp2.getOperand(1),
1242                              Node->getOperand(2));
1243       } else {
1244         // Make sure the condition is either zero or one.  It may have been
1245         // promoted from something else.
1246         unsigned NumBits = MVT::getSizeInBits(Tmp2.getValueType());
1247         if (!TLI.MaskedValueIsZero(Tmp2, (~0ULL >> (64-NumBits))^1))
1248           Tmp2 = DAG.getZeroExtendInReg(Tmp2, MVT::i1);
1249
1250         Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1,
1251                              DAG.getCondCode(ISD::SETNE), Tmp2,
1252                              DAG.getConstant(0, Tmp2.getValueType()),
1253                              Node->getOperand(2));
1254       }
1255       break;
1256     }
1257     break;
1258   case ISD::BR_CC:
1259     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1260     // Ensure that libcalls are emitted before a branch.
1261     Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1262     Tmp1 = LegalizeOp(Tmp1);
1263     LastCALLSEQ_END = DAG.getEntryNode();
1264
1265     Tmp2 = Node->getOperand(2);              // LHS
1266     Tmp3 = Node->getOperand(3);              // RHS
1267     Tmp4 = Node->getOperand(1);              // CC
1268
1269     LegalizeSetCCOperands(Tmp2, Tmp3, Tmp4);
1270
1271     // If we didn't get both a LHS and RHS back from LegalizeSetCCOperands,
1272     // the LHS is a legal SETCC itself.  In this case, we need to compare
1273     // the result against zero to select between true and false values.
1274     if (Tmp3.Val == 0) {
1275       Tmp3 = DAG.getConstant(0, Tmp2.getValueType());
1276       Tmp4 = DAG.getCondCode(ISD::SETNE);
1277     }
1278
1279     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp4, Tmp2, Tmp3,
1280                                     Node->getOperand(4));
1281
1282     switch (TLI.getOperationAction(ISD::BR_CC, Tmp3.getValueType())) {
1283     default: assert(0 && "Unexpected action for BR_CC!");
1284     case TargetLowering::Legal: break;
1285     case TargetLowering::Custom:
1286       Tmp4 = TLI.LowerOperation(Result, DAG);
1287       if (Tmp4.Val) Result = Tmp4;
1288       break;
1289     }
1290     break;
1291   case ISD::LOAD: {
1292     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1293     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1294
1295     MVT::ValueType VT = Node->getValueType(0);
1296     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1297     Tmp3 = Result.getValue(0);
1298     Tmp4 = Result.getValue(1);
1299
1300     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
1301     default: assert(0 && "This action is not supported yet!");
1302     case TargetLowering::Legal: break;
1303     case TargetLowering::Custom:
1304       Tmp1 = TLI.LowerOperation(Tmp3, DAG);
1305       if (Tmp1.Val) {
1306         Tmp3 = LegalizeOp(Tmp1);
1307         Tmp4 = LegalizeOp(Tmp1.getValue(1));
1308       }
1309       break;
1310     case TargetLowering::Promote: {
1311       // Only promote a load of vector type to another.
1312       assert(MVT::isVector(VT) && "Cannot promote this load!");
1313       // Change base type to a different vector type.
1314       MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), VT);
1315
1316       Tmp1 = DAG.getLoad(NVT, Tmp1, Tmp2, Node->getOperand(2));
1317       Tmp3 = LegalizeOp(DAG.getNode(ISD::BIT_CONVERT, VT, Tmp1));
1318       Tmp4 = LegalizeOp(Tmp1.getValue(1));
1319       break;
1320     }
1321     }
1322     // Since loads produce two values, make sure to remember that we
1323     // legalized both of them.
1324     AddLegalizedOperand(SDOperand(Node, 0), Tmp3);
1325     AddLegalizedOperand(SDOperand(Node, 1), Tmp4);
1326     return Op.ResNo ? Tmp4 : Tmp3;
1327   }
1328   case ISD::EXTLOAD:
1329   case ISD::SEXTLOAD:
1330   case ISD::ZEXTLOAD: {
1331     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1332     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1333
1334     MVT::ValueType SrcVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
1335     switch (TLI.getOperationAction(Node->getOpcode(), SrcVT)) {
1336     default: assert(0 && "This action is not supported yet!");
1337     case TargetLowering::Promote:
1338       assert(SrcVT == MVT::i1 && "Can only promote EXTLOAD from i1 -> i8!");
1339       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2),
1340                                       DAG.getValueType(MVT::i8));
1341       Tmp1 = Result.getValue(0);
1342       Tmp2 = Result.getValue(1);
1343       break;
1344     case TargetLowering::Custom:
1345       isCustom = true;
1346       // FALLTHROUGH
1347     case TargetLowering::Legal:
1348       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2),
1349                                       Node->getOperand(3));
1350       Tmp1 = Result.getValue(0);
1351       Tmp2 = Result.getValue(1);
1352
1353       if (isCustom) {
1354         Tmp3 = TLI.LowerOperation(Tmp3, DAG);
1355         if (Tmp3.Val) {
1356           Tmp1 = LegalizeOp(Tmp3);
1357           Tmp2 = LegalizeOp(Tmp3.getValue(1));
1358         }
1359       }
1360       break;
1361     case TargetLowering::Expand:
1362       // f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND
1363       if (SrcVT == MVT::f32 && Node->getValueType(0) == MVT::f64) {
1364         SDOperand Load = DAG.getLoad(SrcVT, Tmp1, Tmp2, Node->getOperand(2));
1365         Result = DAG.getNode(ISD::FP_EXTEND, Node->getValueType(0), Load);
1366         Tmp1 = LegalizeOp(Result);  // Relegalize new nodes.
1367         Tmp2 = LegalizeOp(Load.getValue(1));
1368         break;
1369       }
1370       assert(Node->getOpcode() != ISD::EXTLOAD &&
1371              "EXTLOAD should always be supported!");
1372       // Turn the unsupported load into an EXTLOAD followed by an explicit
1373       // zero/sign extend inreg.
1374       Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
1375                               Tmp1, Tmp2, Node->getOperand(2), SrcVT);
1376       SDOperand ValRes;
1377       if (Node->getOpcode() == ISD::SEXTLOAD)
1378         ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1379                              Result, DAG.getValueType(SrcVT));
1380       else
1381         ValRes = DAG.getZeroExtendInReg(Result, SrcVT);
1382       Tmp1 = LegalizeOp(ValRes);  // Relegalize new nodes.
1383       Tmp2 = LegalizeOp(Result.getValue(1));  // Relegalize new nodes.
1384       break;
1385     }
1386     // Since loads produce two values, make sure to remember that we legalized
1387     // both of them.
1388     AddLegalizedOperand(SDOperand(Node, 0), Tmp1);
1389     AddLegalizedOperand(SDOperand(Node, 1), Tmp2);
1390     return Op.ResNo ? Tmp2 : Tmp1;
1391   }
1392   case ISD::EXTRACT_ELEMENT: {
1393     MVT::ValueType OpTy = Node->getOperand(0).getValueType();
1394     switch (getTypeAction(OpTy)) {
1395     default: assert(0 && "EXTRACT_ELEMENT action for type unimplemented!");
1396     case Legal:
1397       if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) {
1398         // 1 -> Hi
1399         Result = DAG.getNode(ISD::SRL, OpTy, Node->getOperand(0),
1400                              DAG.getConstant(MVT::getSizeInBits(OpTy)/2,
1401                                              TLI.getShiftAmountTy()));
1402         Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Result);
1403       } else {
1404         // 0 -> Lo
1405         Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0),
1406                              Node->getOperand(0));
1407       }
1408       break;
1409     case Expand:
1410       // Get both the low and high parts.
1411       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
1412       if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
1413         Result = Tmp2;  // 1 -> Hi
1414       else
1415         Result = Tmp1;  // 0 -> Lo
1416       break;
1417     }
1418     break;
1419   }
1420
1421   case ISD::CopyToReg:
1422     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1423
1424     assert(isTypeLegal(Node->getOperand(2).getValueType()) &&
1425            "Register type must be legal!");
1426     // Legalize the incoming value (must be a legal type).
1427     Tmp2 = LegalizeOp(Node->getOperand(2));
1428     if (Node->getNumValues() == 1) {
1429       Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1), Tmp2);
1430     } else {
1431       assert(Node->getNumValues() == 2 && "Unknown CopyToReg");
1432       if (Node->getNumOperands() == 4) {
1433         Tmp3 = LegalizeOp(Node->getOperand(3));
1434         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1), Tmp2,
1435                                         Tmp3);
1436       } else {
1437         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1),Tmp2);
1438       }
1439
1440       // Since this produces two values, make sure to remember that we legalized
1441       // both of them.
1442       AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1443       AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1444       return Result;
1445     }
1446     break;
1447
1448   case ISD::RET:
1449     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1450
1451     // Ensure that libcalls are emitted before a return.
1452     Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1453     Tmp1 = LegalizeOp(Tmp1);
1454     LastCALLSEQ_END = DAG.getEntryNode();
1455
1456     switch (Node->getNumOperands()) {
1457     case 3:  // ret val
1458       Tmp2 = Node->getOperand(1);
1459       Tmp3 = Node->getOperand(2);  // Signness
1460       switch (getTypeAction(Tmp2.getValueType())) {
1461       case Legal:
1462         Result = DAG.UpdateNodeOperands(Result, Tmp1, LegalizeOp(Tmp2), Tmp3);
1463         break;
1464       case Expand:
1465         if (Tmp2.getValueType() != MVT::Vector) {
1466           SDOperand Lo, Hi;
1467           ExpandOp(Tmp2, Lo, Hi);
1468           Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Tmp3, Hi, Tmp3);
1469         } else {
1470           SDNode *InVal = Tmp2.Val;
1471           unsigned NumElems =
1472             cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
1473           MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
1474
1475           // Figure out if there is a Packed type corresponding to this Vector
1476           // type.  If so, convert to the packed type.
1477           MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
1478           if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
1479             // Turn this into a return of the packed type.
1480             Tmp2 = PackVectorOp(Tmp2, TVT);
1481             Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1482           } else if (NumElems == 1) {
1483             // Turn this into a return of the scalar type.
1484             Tmp2 = PackVectorOp(Tmp2, EVT);
1485             Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1486
1487             // FIXME: Returns of gcc generic vectors smaller than a legal type
1488             // should be returned in integer registers!
1489
1490             // The scalarized value type may not be legal, e.g. it might require
1491             // promotion or expansion.  Relegalize the return.
1492             Result = LegalizeOp(Result);
1493           } else {
1494             // FIXME: Returns of gcc generic vectors larger than a legal vector
1495             // type should be returned by reference!
1496             SDOperand Lo, Hi;
1497             SplitVectorOp(Tmp2, Lo, Hi);
1498             Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Tmp3, Hi, Tmp3);
1499             Result = LegalizeOp(Result);
1500           }
1501         }
1502         break;
1503       case Promote:
1504         Tmp2 = PromoteOp(Node->getOperand(1));
1505         Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1506         Result = LegalizeOp(Result);
1507         break;
1508       }
1509       break;
1510     case 1:  // ret void
1511       Result = DAG.UpdateNodeOperands(Result, Tmp1);
1512       break;
1513     default: { // ret <values>
1514       std::vector<SDOperand> NewValues;
1515       NewValues.push_back(Tmp1);
1516       for (unsigned i = 1, e = Node->getNumOperands(); i < e; i += 2)
1517         switch (getTypeAction(Node->getOperand(i).getValueType())) {
1518         case Legal:
1519           NewValues.push_back(LegalizeOp(Node->getOperand(i)));
1520           NewValues.push_back(Node->getOperand(i+1));
1521           break;
1522         case Expand: {
1523           SDOperand Lo, Hi;
1524           assert(Node->getOperand(i).getValueType() != MVT::Vector &&
1525                  "FIXME: TODO: implement returning non-legal vector types!");
1526           ExpandOp(Node->getOperand(i), Lo, Hi);
1527           NewValues.push_back(Lo);
1528           NewValues.push_back(Node->getOperand(i+1));
1529           NewValues.push_back(Hi);
1530           NewValues.push_back(Node->getOperand(i+1));
1531           break;
1532         }
1533         case Promote:
1534           assert(0 && "Can't promote multiple return value yet!");
1535         }
1536
1537       if (NewValues.size() == Node->getNumOperands())
1538         Result = DAG.UpdateNodeOperands(Result, NewValues);
1539       else
1540         Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
1541       break;
1542     }
1543     }
1544
1545     if (Result.getOpcode() == ISD::RET) {
1546       switch (TLI.getOperationAction(Result.getOpcode(), MVT::Other)) {
1547       default: assert(0 && "This action is not supported yet!");
1548       case TargetLowering::Legal: break;
1549       case TargetLowering::Custom:
1550         Tmp1 = TLI.LowerOperation(Result, DAG);
1551         if (Tmp1.Val) Result = Tmp1;
1552         break;
1553       }
1554     }
1555     break;
1556   case ISD::STORE: {
1557     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1558     Tmp2 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
1559
1560     // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
1561     // FIXME: We shouldn't do this for TargetConstantFP's.
1562     // FIXME: move this to the DAG Combiner!
1563     if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){
1564       if (CFP->getValueType(0) == MVT::f32) {
1565         Tmp3 = DAG.getConstant(FloatToBits(CFP->getValue()), MVT::i32);
1566       } else {
1567         assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
1568         Tmp3 = DAG.getConstant(DoubleToBits(CFP->getValue()), MVT::i64);
1569       }
1570       Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Tmp3, Tmp2,
1571                            Node->getOperand(3));
1572       break;
1573     }
1574
1575     switch (getTypeAction(Node->getOperand(1).getValueType())) {
1576     case Legal: {
1577       Tmp3 = LegalizeOp(Node->getOperand(1));
1578       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
1579                                       Node->getOperand(3));
1580
1581       MVT::ValueType VT = Tmp3.getValueType();
1582       switch (TLI.getOperationAction(ISD::STORE, VT)) {
1583       default: assert(0 && "This action is not supported yet!");
1584       case TargetLowering::Legal:  break;
1585       case TargetLowering::Custom:
1586         Tmp1 = TLI.LowerOperation(Result, DAG);
1587         if (Tmp1.Val) Result = Tmp1;
1588         break;
1589       case TargetLowering::Promote:
1590         assert(MVT::isVector(VT) && "Unknown legal promote case!");
1591         Tmp3 = DAG.getNode(ISD::BIT_CONVERT,
1592                            TLI.getTypeToPromoteTo(ISD::STORE, VT), Tmp3);
1593         Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
1594                                         Node->getOperand(3));
1595         break;
1596       }
1597       break;
1598     }
1599     case Promote:
1600       // Truncate the value and store the result.
1601       Tmp3 = PromoteOp(Node->getOperand(1));
1602       Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2,
1603                            Node->getOperand(3),
1604                           DAG.getValueType(Node->getOperand(1).getValueType()));
1605       break;
1606
1607     case Expand:
1608       unsigned IncrementSize = 0;
1609       SDOperand Lo, Hi;
1610
1611       // If this is a vector type, then we have to calculate the increment as
1612       // the product of the element size in bytes, and the number of elements
1613       // in the high half of the vector.
1614       if (Node->getOperand(1).getValueType() == MVT::Vector) {
1615         SDNode *InVal = Node->getOperand(1).Val;
1616         unsigned NumElems =
1617           cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
1618         MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
1619
1620         // Figure out if there is a Packed type corresponding to this Vector
1621         // type.  If so, convert to the packed type.
1622         MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
1623         if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
1624           // Turn this into a normal store of the packed type.
1625           Tmp3 = PackVectorOp(Node->getOperand(1), TVT);
1626           Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
1627                                           Node->getOperand(3));
1628           Result = LegalizeOp(Result);
1629           break;
1630         } else if (NumElems == 1) {
1631           // Turn this into a normal store of the scalar type.
1632           Tmp3 = PackVectorOp(Node->getOperand(1), EVT);
1633           Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
1634                                           Node->getOperand(3));
1635           // The scalarized value type may not be legal, e.g. it might require
1636           // promotion or expansion.  Relegalize the scalar store.
1637           Result = LegalizeOp(Result);
1638           break;
1639         } else {
1640           SplitVectorOp(Node->getOperand(1), Lo, Hi);
1641           IncrementSize = NumElems/2 * MVT::getSizeInBits(EVT)/8;
1642         }
1643       } else {
1644         ExpandOp(Node->getOperand(1), Lo, Hi);
1645         IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8;
1646
1647         if (!TLI.isLittleEndian())
1648           std::swap(Lo, Hi);
1649       }
1650
1651       Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2,
1652                        Node->getOperand(3));
1653       Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
1654                          getIntPtrConstant(IncrementSize));
1655       assert(isTypeLegal(Tmp2.getValueType()) &&
1656              "Pointers must be legal!");
1657       // FIXME: This sets the srcvalue of both halves to be the same, which is
1658       // wrong.
1659       Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2,
1660                        Node->getOperand(3));
1661       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1662       break;
1663     }
1664     break;
1665   }
1666   case ISD::PCMARKER:
1667     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1668     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
1669     break;
1670   case ISD::STACKSAVE:
1671     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1672     Result = DAG.UpdateNodeOperands(Result, Tmp1);
1673     Tmp1 = Result.getValue(0);
1674     Tmp2 = Result.getValue(1);
1675
1676     switch (TLI.getOperationAction(ISD::STACKSAVE, MVT::Other)) {
1677     default: assert(0 && "This action is not supported yet!");
1678     case TargetLowering::Legal: break;
1679     case TargetLowering::Custom:
1680       Tmp3 = TLI.LowerOperation(Result, DAG);
1681       if (Tmp3.Val) {
1682         Tmp1 = LegalizeOp(Tmp3);
1683         Tmp2 = LegalizeOp(Tmp3.getValue(1));
1684       }
1685       break;
1686     case TargetLowering::Expand:
1687       // Expand to CopyFromReg if the target set
1688       // StackPointerRegisterToSaveRestore.
1689       if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
1690         Tmp1 = DAG.getCopyFromReg(Result.getOperand(0), SP,
1691                                   Node->getValueType(0));
1692         Tmp2 = Tmp1.getValue(1);
1693       } else {
1694         Tmp1 = DAG.getNode(ISD::UNDEF, Node->getValueType(0));
1695         Tmp2 = Node->getOperand(0);
1696       }
1697       break;
1698     }
1699
1700     // Since stacksave produce two values, make sure to remember that we
1701     // legalized both of them.
1702     AddLegalizedOperand(SDOperand(Node, 0), Tmp1);
1703     AddLegalizedOperand(SDOperand(Node, 1), Tmp2);
1704     return Op.ResNo ? Tmp2 : Tmp1;
1705
1706   case ISD::STACKRESTORE:
1707     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1708     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1709     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1710
1711     switch (TLI.getOperationAction(ISD::STACKRESTORE, MVT::Other)) {
1712     default: assert(0 && "This action is not supported yet!");
1713     case TargetLowering::Legal: break;
1714     case TargetLowering::Custom:
1715       Tmp1 = TLI.LowerOperation(Result, DAG);
1716       if (Tmp1.Val) Result = Tmp1;
1717       break;
1718     case TargetLowering::Expand:
1719       // Expand to CopyToReg if the target set
1720       // StackPointerRegisterToSaveRestore.
1721       if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
1722         Result = DAG.getCopyToReg(Tmp1, SP, Tmp2);
1723       } else {
1724         Result = Tmp1;
1725       }
1726       break;
1727     }
1728     break;
1729
1730   case ISD::READCYCLECOUNTER:
1731     Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain
1732     Result = DAG.UpdateNodeOperands(Result, Tmp1);
1733
1734     // Since rdcc produce two values, make sure to remember that we legalized
1735     // both of them.
1736     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1737     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1738     return Result;
1739
1740   case ISD::TRUNCSTORE: {
1741     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1742     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
1743
1744     assert(isTypeLegal(Node->getOperand(1).getValueType()) &&
1745            "Cannot handle illegal TRUNCSTORE yet!");
1746     Tmp2 = LegalizeOp(Node->getOperand(1));
1747
1748     // The only promote case we handle is TRUNCSTORE:i1 X into
1749     //   -> TRUNCSTORE:i8 (and X, 1)
1750     if (cast<VTSDNode>(Node->getOperand(4))->getVT() == MVT::i1 &&
1751         TLI.getOperationAction(ISD::TRUNCSTORE, MVT::i1) ==
1752               TargetLowering::Promote) {
1753       // Promote the bool to a mask then store.
1754       Tmp2 = DAG.getNode(ISD::AND, Tmp2.getValueType(), Tmp2,
1755                          DAG.getConstant(1, Tmp2.getValueType()));
1756       Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3,
1757                            Node->getOperand(3), DAG.getValueType(MVT::i8));
1758
1759     } else if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1760                Tmp3 != Node->getOperand(2)) {
1761       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3,
1762                                       Node->getOperand(3), Node->getOperand(4));
1763     }
1764
1765     MVT::ValueType StVT = cast<VTSDNode>(Result.Val->getOperand(4))->getVT();
1766     switch (TLI.getOperationAction(Result.Val->getOpcode(), StVT)) {
1767     default: assert(0 && "This action is not supported yet!");
1768     case TargetLowering::Legal: break;
1769     case TargetLowering::Custom:
1770       Tmp1 = TLI.LowerOperation(Result, DAG);
1771       if (Tmp1.Val) Result = Tmp1;
1772       break;
1773     }
1774     break;
1775   }
1776   case ISD::SELECT:
1777     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1778     case Expand: assert(0 && "It's impossible to expand bools");
1779     case Legal:
1780       Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
1781       break;
1782     case Promote:
1783       Tmp1 = PromoteOp(Node->getOperand(0));  // Promote the condition.
1784       break;
1785     }
1786     Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
1787     Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
1788
1789     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1790
1791     switch (TLI.getOperationAction(ISD::SELECT, Tmp2.getValueType())) {
1792     default: assert(0 && "This action is not supported yet!");
1793     case TargetLowering::Legal: break;
1794     case TargetLowering::Custom: {
1795       Tmp1 = TLI.LowerOperation(Result, DAG);
1796       if (Tmp1.Val) Result = Tmp1;
1797       break;
1798     }
1799     case TargetLowering::Expand:
1800       if (Tmp1.getOpcode() == ISD::SETCC) {
1801         Result = DAG.getSelectCC(Tmp1.getOperand(0), Tmp1.getOperand(1),
1802                               Tmp2, Tmp3,
1803                               cast<CondCodeSDNode>(Tmp1.getOperand(2))->get());
1804       } else {
1805         // Make sure the condition is either zero or one.  It may have been
1806         // promoted from something else.
1807         unsigned NumBits = MVT::getSizeInBits(Tmp1.getValueType());
1808         if (!TLI.MaskedValueIsZero(Tmp1, (~0ULL >> (64-NumBits))^1))
1809           Tmp1 = DAG.getZeroExtendInReg(Tmp1, MVT::i1);
1810         Result = DAG.getSelectCC(Tmp1,
1811                                  DAG.getConstant(0, Tmp1.getValueType()),
1812                                  Tmp2, Tmp3, ISD::SETNE);
1813       }
1814       break;
1815     case TargetLowering::Promote: {
1816       MVT::ValueType NVT =
1817         TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType());
1818       unsigned ExtOp, TruncOp;
1819       if (MVT::isVector(Tmp2.getValueType())) {
1820         ExtOp   = ISD::BIT_CONVERT;
1821         TruncOp = ISD::BIT_CONVERT;
1822       } else if (MVT::isInteger(Tmp2.getValueType())) {
1823         ExtOp   = ISD::ANY_EXTEND;
1824         TruncOp = ISD::TRUNCATE;
1825       } else {
1826         ExtOp   = ISD::FP_EXTEND;
1827         TruncOp = ISD::FP_ROUND;
1828       }
1829       // Promote each of the values to the new type.
1830       Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2);
1831       Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3);
1832       // Perform the larger operation, then round down.
1833       Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3);
1834       Result = DAG.getNode(TruncOp, Node->getValueType(0), Result);
1835       break;
1836     }
1837     }
1838     break;
1839   case ISD::SELECT_CC: {
1840     Tmp1 = Node->getOperand(0);               // LHS
1841     Tmp2 = Node->getOperand(1);               // RHS
1842     Tmp3 = LegalizeOp(Node->getOperand(2));   // True
1843     Tmp4 = LegalizeOp(Node->getOperand(3));   // False
1844     SDOperand CC = Node->getOperand(4);
1845
1846     LegalizeSetCCOperands(Tmp1, Tmp2, CC);
1847
1848     // If we didn't get both a LHS and RHS back from LegalizeSetCCOperands,
1849     // the LHS is a legal SETCC itself.  In this case, we need to compare
1850     // the result against zero to select between true and false values.
1851     if (Tmp2.Val == 0) {
1852       Tmp2 = DAG.getConstant(0, Tmp1.getValueType());
1853       CC = DAG.getCondCode(ISD::SETNE);
1854     }
1855     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4, CC);
1856
1857     // Everything is legal, see if we should expand this op or something.
1858     switch (TLI.getOperationAction(ISD::SELECT_CC, Tmp3.getValueType())) {
1859     default: assert(0 && "This action is not supported yet!");
1860     case TargetLowering::Legal: break;
1861     case TargetLowering::Custom:
1862       Tmp1 = TLI.LowerOperation(Result, DAG);
1863       if (Tmp1.Val) Result = Tmp1;
1864       break;
1865     }
1866     break;
1867   }
1868   case ISD::SETCC:
1869     Tmp1 = Node->getOperand(0);
1870     Tmp2 = Node->getOperand(1);
1871     Tmp3 = Node->getOperand(2);
1872     LegalizeSetCCOperands(Tmp1, Tmp2, Tmp3);
1873
1874     // If we had to Expand the SetCC operands into a SELECT node, then it may
1875     // not always be possible to return a true LHS & RHS.  In this case, just
1876     // return the value we legalized, returned in the LHS
1877     if (Tmp2.Val == 0) {
1878       Result = Tmp1;
1879       break;
1880     }
1881
1882     switch (TLI.getOperationAction(ISD::SETCC, Tmp1.getValueType())) {
1883     default: assert(0 && "Cannot handle this action for SETCC yet!");
1884     case TargetLowering::Custom:
1885       isCustom = true;
1886       // FALLTHROUGH.
1887     case TargetLowering::Legal:
1888       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1889       if (isCustom) {
1890         Tmp3 = TLI.LowerOperation(Result, DAG);
1891         if (Tmp3.Val) Result = Tmp3;
1892       }
1893       break;
1894     case TargetLowering::Promote: {
1895       // First step, figure out the appropriate operation to use.
1896       // Allow SETCC to not be supported for all legal data types
1897       // Mostly this targets FP
1898       MVT::ValueType NewInTy = Node->getOperand(0).getValueType();
1899       MVT::ValueType OldVT = NewInTy;
1900
1901       // Scan for the appropriate larger type to use.
1902       while (1) {
1903         NewInTy = (MVT::ValueType)(NewInTy+1);
1904
1905         assert(MVT::isInteger(NewInTy) == MVT::isInteger(OldVT) &&
1906                "Fell off of the edge of the integer world");
1907         assert(MVT::isFloatingPoint(NewInTy) == MVT::isFloatingPoint(OldVT) &&
1908                "Fell off of the edge of the floating point world");
1909
1910         // If the target supports SETCC of this type, use it.
1911         if (TLI.isOperationLegal(ISD::SETCC, NewInTy))
1912           break;
1913       }
1914       if (MVT::isInteger(NewInTy))
1915         assert(0 && "Cannot promote Legal Integer SETCC yet");
1916       else {
1917         Tmp1 = DAG.getNode(ISD::FP_EXTEND, NewInTy, Tmp1);
1918         Tmp2 = DAG.getNode(ISD::FP_EXTEND, NewInTy, Tmp2);
1919       }
1920       Tmp1 = LegalizeOp(Tmp1);
1921       Tmp2 = LegalizeOp(Tmp2);
1922       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1923       Result = LegalizeOp(Result);
1924       break;
1925     }
1926     case TargetLowering::Expand:
1927       // Expand a setcc node into a select_cc of the same condition, lhs, and
1928       // rhs that selects between const 1 (true) and const 0 (false).
1929       MVT::ValueType VT = Node->getValueType(0);
1930       Result = DAG.getNode(ISD::SELECT_CC, VT, Tmp1, Tmp2,
1931                            DAG.getConstant(1, VT), DAG.getConstant(0, VT),
1932                            Node->getOperand(2));
1933       break;
1934     }
1935     break;
1936   case ISD::MEMSET:
1937   case ISD::MEMCPY:
1938   case ISD::MEMMOVE: {
1939     Tmp1 = LegalizeOp(Node->getOperand(0));      // Chain
1940     Tmp2 = LegalizeOp(Node->getOperand(1));      // Pointer
1941
1942     if (Node->getOpcode() == ISD::MEMSET) {      // memset = ubyte
1943       switch (getTypeAction(Node->getOperand(2).getValueType())) {
1944       case Expand: assert(0 && "Cannot expand a byte!");
1945       case Legal:
1946         Tmp3 = LegalizeOp(Node->getOperand(2));
1947         break;
1948       case Promote:
1949         Tmp3 = PromoteOp(Node->getOperand(2));
1950         break;
1951       }
1952     } else {
1953       Tmp3 = LegalizeOp(Node->getOperand(2));    // memcpy/move = pointer,
1954     }
1955
1956     SDOperand Tmp4;
1957     switch (getTypeAction(Node->getOperand(3).getValueType())) {
1958     case Expand: {
1959       // Length is too big, just take the lo-part of the length.
1960       SDOperand HiPart;
1961       ExpandOp(Node->getOperand(3), HiPart, Tmp4);
1962       break;
1963     }
1964     case Legal:
1965       Tmp4 = LegalizeOp(Node->getOperand(3));
1966       break;
1967     case Promote:
1968       Tmp4 = PromoteOp(Node->getOperand(3));
1969       break;
1970     }
1971
1972     SDOperand Tmp5;
1973     switch (getTypeAction(Node->getOperand(4).getValueType())) {  // uint
1974     case Expand: assert(0 && "Cannot expand this yet!");
1975     case Legal:
1976       Tmp5 = LegalizeOp(Node->getOperand(4));
1977       break;
1978     case Promote:
1979       Tmp5 = PromoteOp(Node->getOperand(4));
1980       break;
1981     }
1982
1983     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
1984     default: assert(0 && "This action not implemented for this operation!");
1985     case TargetLowering::Custom:
1986       isCustom = true;
1987       // FALLTHROUGH
1988     case TargetLowering::Legal:
1989       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4, Tmp5);
1990       if (isCustom) {
1991         Tmp1 = TLI.LowerOperation(Result, DAG);
1992         if (Tmp1.Val) Result = Tmp1;
1993       }
1994       break;
1995     case TargetLowering::Expand: {
1996       // Otherwise, the target does not support this operation.  Lower the
1997       // operation to an explicit libcall as appropriate.
1998       MVT::ValueType IntPtr = TLI.getPointerTy();
1999       const Type *IntPtrTy = TLI.getTargetData()->getIntPtrType();
2000       std::vector<std::pair<SDOperand, const Type*> > Args;
2001
2002       const char *FnName = 0;
2003       if (Node->getOpcode() == ISD::MEMSET) {
2004         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
2005         // Extend the (previously legalized) ubyte argument to be an int value
2006         // for the call.
2007         if (Tmp3.getValueType() > MVT::i32)
2008           Tmp3 = DAG.getNode(ISD::TRUNCATE, MVT::i32, Tmp3);
2009         else
2010           Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
2011         Args.push_back(std::make_pair(Tmp3, Type::IntTy));
2012         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
2013
2014         FnName = "memset";
2015       } else if (Node->getOpcode() == ISD::MEMCPY ||
2016                  Node->getOpcode() == ISD::MEMMOVE) {
2017         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
2018         Args.push_back(std::make_pair(Tmp3, IntPtrTy));
2019         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
2020         FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
2021       } else {
2022         assert(0 && "Unknown op!");
2023       }
2024
2025       std::pair<SDOperand,SDOperand> CallResult =
2026         TLI.LowerCallTo(Tmp1, Type::VoidTy, false, CallingConv::C, false,
2027                         DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
2028       Result = CallResult.second;
2029       break;
2030     }
2031     }
2032     break;
2033   }
2034
2035   case ISD::SHL_PARTS:
2036   case ISD::SRA_PARTS:
2037   case ISD::SRL_PARTS: {
2038     std::vector<SDOperand> Ops;
2039     bool Changed = false;
2040     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
2041       Ops.push_back(LegalizeOp(Node->getOperand(i)));
2042       Changed |= Ops.back() != Node->getOperand(i);
2043     }
2044     if (Changed)
2045       Result = DAG.UpdateNodeOperands(Result, Ops);
2046
2047     switch (TLI.getOperationAction(Node->getOpcode(),
2048                                    Node->getValueType(0))) {
2049     default: assert(0 && "This action is not supported yet!");
2050     case TargetLowering::Legal: break;
2051     case TargetLowering::Custom:
2052       Tmp1 = TLI.LowerOperation(Result, DAG);
2053       if (Tmp1.Val) {
2054         SDOperand Tmp2, RetVal(0, 0);
2055         for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) {
2056           Tmp2 = LegalizeOp(Tmp1.getValue(i));
2057           AddLegalizedOperand(SDOperand(Node, i), Tmp2);
2058           if (i == Op.ResNo)
2059             RetVal = Tmp2;
2060         }
2061         assert(RetVal.Val && "Illegal result number");
2062         return RetVal;
2063       }
2064       break;
2065     }
2066
2067     // Since these produce multiple values, make sure to remember that we
2068     // legalized all of them.
2069     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
2070       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
2071     return Result.getValue(Op.ResNo);
2072   }
2073
2074     // Binary operators
2075   case ISD::ADD:
2076   case ISD::SUB:
2077   case ISD::MUL:
2078   case ISD::MULHS:
2079   case ISD::MULHU:
2080   case ISD::UDIV:
2081   case ISD::SDIV:
2082   case ISD::AND:
2083   case ISD::OR:
2084   case ISD::XOR:
2085   case ISD::SHL:
2086   case ISD::SRL:
2087   case ISD::SRA:
2088   case ISD::FADD:
2089   case ISD::FSUB:
2090   case ISD::FMUL:
2091   case ISD::FDIV:
2092     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2093     switch (getTypeAction(Node->getOperand(1).getValueType())) {
2094     case Expand: assert(0 && "Not possible");
2095     case Legal:
2096       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS.
2097       break;
2098     case Promote:
2099       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the RHS.
2100       break;
2101     }
2102
2103     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2104
2105     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2106     default: assert(0 && "BinOp legalize operation not supported");
2107     case TargetLowering::Legal: break;
2108     case TargetLowering::Custom:
2109       Tmp1 = TLI.LowerOperation(Result, DAG);
2110       if (Tmp1.Val) Result = Tmp1;
2111       break;
2112     case TargetLowering::Expand: {
2113       assert(MVT::isVector(Node->getValueType(0)) &&
2114              "Cannot expand this binary operator!");
2115       // Expand the operation into a bunch of nasty scalar code.
2116       std::vector<SDOperand> Ops;
2117       MVT::ValueType EltVT = MVT::getVectorBaseType(Node->getValueType(0));
2118       MVT::ValueType PtrVT = TLI.getPointerTy();
2119       for (unsigned i = 0, e = MVT::getVectorNumElements(Node->getValueType(0));
2120            i != e; ++i) {
2121         SDOperand Idx = DAG.getConstant(i, PtrVT);
2122         SDOperand LHS = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, Tmp1, Idx);
2123         SDOperand RHS = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, Tmp2, Idx);
2124         Ops.push_back(DAG.getNode(Node->getOpcode(), EltVT, LHS, RHS));
2125       }
2126       Result = DAG.getNode(ISD::BUILD_VECTOR, Node->getValueType(0), Ops);
2127       break;
2128     }
2129     case TargetLowering::Promote: {
2130       switch (Node->getOpcode()) {
2131       default:  assert(0 && "Do not know how to promote this BinOp!");
2132       case ISD::AND:
2133       case ISD::OR:
2134       case ISD::XOR: {
2135         MVT::ValueType OVT = Node->getValueType(0);
2136         MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2137         assert(MVT::isVector(OVT) && "Cannot promote this BinOp!");
2138         // Bit convert each of the values to the new type.
2139         Tmp1 = DAG.getNode(ISD::BIT_CONVERT, NVT, Tmp1);
2140         Tmp2 = DAG.getNode(ISD::BIT_CONVERT, NVT, Tmp2);
2141         Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2142         // Bit convert the result back the original type.
2143         Result = DAG.getNode(ISD::BIT_CONVERT, OVT, Result);
2144         break;
2145       }
2146       }
2147     }
2148     }
2149     break;
2150
2151   case ISD::FCOPYSIGN:  // FCOPYSIGN does not require LHS/RHS to match type!
2152     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2153     switch (getTypeAction(Node->getOperand(1).getValueType())) {
2154       case Expand: assert(0 && "Not possible");
2155       case Legal:
2156         Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS.
2157         break;
2158       case Promote:
2159         Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the RHS.
2160         break;
2161     }
2162
2163     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2164
2165     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2166     default: assert(0 && "Operation not supported");
2167     case TargetLowering::Custom:
2168       Tmp1 = TLI.LowerOperation(Result, DAG);
2169       if (Tmp1.Val) Result = Tmp1;
2170       break;
2171     case TargetLowering::Legal: break;
2172     case TargetLowering::Expand:
2173       // If this target supports fabs/fneg natively, do this efficiently.
2174       if (TLI.isOperationLegal(ISD::FABS, Tmp1.getValueType()) &&
2175           TLI.isOperationLegal(ISD::FNEG, Tmp1.getValueType())) {
2176         // Get the sign bit of the RHS.
2177         MVT::ValueType IVT =
2178           Tmp2.getValueType() == MVT::f32 ? MVT::i32 : MVT::i64;
2179         SDOperand SignBit = DAG.getNode(ISD::BIT_CONVERT, IVT, Tmp2);
2180         SignBit = DAG.getSetCC(TLI.getSetCCResultTy(),
2181                                SignBit, DAG.getConstant(0, IVT), ISD::SETLT);
2182         // Get the absolute value of the result.
2183         SDOperand AbsVal = DAG.getNode(ISD::FABS, Tmp1.getValueType(), Tmp1);
2184         // Select between the nabs and abs value based on the sign bit of
2185         // the input.
2186         Result = DAG.getNode(ISD::SELECT, AbsVal.getValueType(), SignBit,
2187                              DAG.getNode(ISD::FNEG, AbsVal.getValueType(),
2188                                          AbsVal),
2189                              AbsVal);
2190         Result = LegalizeOp(Result);
2191         break;
2192       }
2193
2194       // Otherwise, do bitwise ops!
2195
2196       // copysign -> copysignf/copysign libcall.
2197       const char *FnName;
2198       if (Node->getValueType(0) == MVT::f32) {
2199         FnName = "copysignf";
2200         if (Tmp2.getValueType() != MVT::f32)  // Force operands to match type.
2201           Result = DAG.UpdateNodeOperands(Result, Tmp1,
2202                                     DAG.getNode(ISD::FP_ROUND, MVT::f32, Tmp2));
2203       } else {
2204         FnName = "copysign";
2205         if (Tmp2.getValueType() != MVT::f64)  // Force operands to match type.
2206           Result = DAG.UpdateNodeOperands(Result, Tmp1,
2207                                    DAG.getNode(ISD::FP_EXTEND, MVT::f64, Tmp2));
2208       }
2209       SDOperand Dummy;
2210       Result = ExpandLibCall(FnName, Node, Dummy);
2211       break;
2212     }
2213     break;
2214
2215   case ISD::ADDC:
2216   case ISD::SUBC:
2217     Tmp1 = LegalizeOp(Node->getOperand(0));
2218     Tmp2 = LegalizeOp(Node->getOperand(1));
2219     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2220     // Since this produces two values, make sure to remember that we legalized
2221     // both of them.
2222     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
2223     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
2224     return Result;
2225
2226   case ISD::ADDE:
2227   case ISD::SUBE:
2228     Tmp1 = LegalizeOp(Node->getOperand(0));
2229     Tmp2 = LegalizeOp(Node->getOperand(1));
2230     Tmp3 = LegalizeOp(Node->getOperand(2));
2231     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
2232     // Since this produces two values, make sure to remember that we legalized
2233     // both of them.
2234     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
2235     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
2236     return Result;
2237
2238   case ISD::BUILD_PAIR: {
2239     MVT::ValueType PairTy = Node->getValueType(0);
2240     // TODO: handle the case where the Lo and Hi operands are not of legal type
2241     Tmp1 = LegalizeOp(Node->getOperand(0));   // Lo
2242     Tmp2 = LegalizeOp(Node->getOperand(1));   // Hi
2243     switch (TLI.getOperationAction(ISD::BUILD_PAIR, PairTy)) {
2244     case TargetLowering::Promote:
2245     case TargetLowering::Custom:
2246       assert(0 && "Cannot promote/custom this yet!");
2247     case TargetLowering::Legal:
2248       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
2249         Result = DAG.getNode(ISD::BUILD_PAIR, PairTy, Tmp1, Tmp2);
2250       break;
2251     case TargetLowering::Expand:
2252       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, PairTy, Tmp1);
2253       Tmp2 = DAG.getNode(ISD::ANY_EXTEND, PairTy, Tmp2);
2254       Tmp2 = DAG.getNode(ISD::SHL, PairTy, Tmp2,
2255                          DAG.getConstant(MVT::getSizeInBits(PairTy)/2,
2256                                          TLI.getShiftAmountTy()));
2257       Result = DAG.getNode(ISD::OR, PairTy, Tmp1, Tmp2);
2258       break;
2259     }
2260     break;
2261   }
2262
2263   case ISD::UREM:
2264   case ISD::SREM:
2265   case ISD::FREM:
2266     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2267     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2268
2269     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2270     case TargetLowering::Promote: assert(0 && "Cannot promote this yet!");
2271     case TargetLowering::Custom:
2272       isCustom = true;
2273       // FALLTHROUGH
2274     case TargetLowering::Legal:
2275       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2276       if (isCustom) {
2277         Tmp1 = TLI.LowerOperation(Result, DAG);
2278         if (Tmp1.Val) Result = Tmp1;
2279       }
2280       break;
2281     case TargetLowering::Expand:
2282       if (MVT::isInteger(Node->getValueType(0))) {
2283         // X % Y -> X-X/Y*Y
2284         MVT::ValueType VT = Node->getValueType(0);
2285         unsigned Opc = Node->getOpcode() == ISD::UREM ? ISD::UDIV : ISD::SDIV;
2286         Result = DAG.getNode(Opc, VT, Tmp1, Tmp2);
2287         Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2);
2288         Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result);
2289       } else {
2290         // Floating point mod -> fmod libcall.
2291         const char *FnName = Node->getValueType(0) == MVT::f32 ? "fmodf":"fmod";
2292         SDOperand Dummy;
2293         Result = ExpandLibCall(FnName, Node, Dummy);
2294       }
2295       break;
2296     }
2297     break;
2298   case ISD::VAARG: {
2299     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2300     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2301
2302     MVT::ValueType VT = Node->getValueType(0);
2303     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
2304     default: assert(0 && "This action is not supported yet!");
2305     case TargetLowering::Custom:
2306       isCustom = true;
2307       // FALLTHROUGH
2308     case TargetLowering::Legal:
2309       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
2310       Result = Result.getValue(0);
2311       Tmp1 = Result.getValue(1);
2312
2313       if (isCustom) {
2314         Tmp2 = TLI.LowerOperation(Result, DAG);
2315         if (Tmp2.Val) {
2316           Result = LegalizeOp(Tmp2);
2317           Tmp1 = LegalizeOp(Tmp2.getValue(1));
2318         }
2319       }
2320       break;
2321     case TargetLowering::Expand: {
2322       SDOperand VAList = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp2,
2323                                      Node->getOperand(2));
2324       // Increment the pointer, VAList, to the next vaarg
2325       Tmp3 = DAG.getNode(ISD::ADD, TLI.getPointerTy(), VAList,
2326                          DAG.getConstant(MVT::getSizeInBits(VT)/8,
2327                                          TLI.getPointerTy()));
2328       // Store the incremented VAList to the legalized pointer
2329       Tmp3 = DAG.getNode(ISD::STORE, MVT::Other, VAList.getValue(1), Tmp3, Tmp2,
2330                          Node->getOperand(2));
2331       // Load the actual argument out of the pointer VAList
2332       Result = DAG.getLoad(VT, Tmp3, VAList, DAG.getSrcValue(0));
2333       Tmp1 = LegalizeOp(Result.getValue(1));
2334       Result = LegalizeOp(Result);
2335       break;
2336     }
2337     }
2338     // Since VAARG produces two values, make sure to remember that we
2339     // legalized both of them.
2340     AddLegalizedOperand(SDOperand(Node, 0), Result);
2341     AddLegalizedOperand(SDOperand(Node, 1), Tmp1);
2342     return Op.ResNo ? Tmp1 : Result;
2343   }
2344
2345   case ISD::VACOPY:
2346     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2347     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the dest pointer.
2348     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the source pointer.
2349
2350     switch (TLI.getOperationAction(ISD::VACOPY, MVT::Other)) {
2351     default: assert(0 && "This action is not supported yet!");
2352     case TargetLowering::Custom:
2353       isCustom = true;
2354       // FALLTHROUGH
2355     case TargetLowering::Legal:
2356       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3,
2357                                       Node->getOperand(3), Node->getOperand(4));
2358       if (isCustom) {
2359         Tmp1 = TLI.LowerOperation(Result, DAG);
2360         if (Tmp1.Val) Result = Tmp1;
2361       }
2362       break;
2363     case TargetLowering::Expand:
2364       // This defaults to loading a pointer from the input and storing it to the
2365       // output, returning the chain.
2366       Tmp4 = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp3, Node->getOperand(3));
2367       Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp4.getValue(1), Tmp4, Tmp2,
2368                            Node->getOperand(4));
2369       break;
2370     }
2371     break;
2372
2373   case ISD::VAEND:
2374     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2375     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2376
2377     switch (TLI.getOperationAction(ISD::VAEND, MVT::Other)) {
2378     default: assert(0 && "This action is not supported yet!");
2379     case TargetLowering::Custom:
2380       isCustom = true;
2381       // FALLTHROUGH
2382     case TargetLowering::Legal:
2383       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
2384       if (isCustom) {
2385         Tmp1 = TLI.LowerOperation(Tmp1, DAG);
2386         if (Tmp1.Val) Result = Tmp1;
2387       }
2388       break;
2389     case TargetLowering::Expand:
2390       Result = Tmp1; // Default to a no-op, return the chain
2391       break;
2392     }
2393     break;
2394
2395   case ISD::VASTART:
2396     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2397     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2398
2399     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
2400
2401     switch (TLI.getOperationAction(ISD::VASTART, MVT::Other)) {
2402     default: assert(0 && "This action is not supported yet!");
2403     case TargetLowering::Legal: break;
2404     case TargetLowering::Custom:
2405       Tmp1 = TLI.LowerOperation(Result, DAG);
2406       if (Tmp1.Val) Result = Tmp1;
2407       break;
2408     }
2409     break;
2410
2411   case ISD::ROTL:
2412   case ISD::ROTR:
2413     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2414     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2415
2416     assert(TLI.isOperationLegal(Node->getOpcode(), Node->getValueType(0)) &&
2417            "Cannot handle this yet!");
2418     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2419     break;
2420
2421   case ISD::BSWAP:
2422     Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
2423     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2424     case TargetLowering::Custom:
2425       assert(0 && "Cannot custom legalize this yet!");
2426     case TargetLowering::Legal:
2427       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2428       break;
2429     case TargetLowering::Promote: {
2430       MVT::ValueType OVT = Tmp1.getValueType();
2431       MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2432       unsigned DiffBits = getSizeInBits(NVT) - getSizeInBits(OVT);
2433
2434       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2435       Tmp1 = DAG.getNode(ISD::BSWAP, NVT, Tmp1);
2436       Result = DAG.getNode(ISD::SRL, NVT, Tmp1,
2437                            DAG.getConstant(DiffBits, TLI.getShiftAmountTy()));
2438       break;
2439     }
2440     case TargetLowering::Expand:
2441       Result = ExpandBSWAP(Tmp1);
2442       break;
2443     }
2444     break;
2445
2446   case ISD::CTPOP:
2447   case ISD::CTTZ:
2448   case ISD::CTLZ:
2449     Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
2450     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2451     case TargetLowering::Custom: assert(0 && "Cannot custom handle this yet!");
2452     case TargetLowering::Legal:
2453       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2454       break;
2455     case TargetLowering::Promote: {
2456       MVT::ValueType OVT = Tmp1.getValueType();
2457       MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2458
2459       // Zero extend the argument.
2460       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2461       // Perform the larger operation, then subtract if needed.
2462       Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
2463       switch (Node->getOpcode()) {
2464       case ISD::CTPOP:
2465         Result = Tmp1;
2466         break;
2467       case ISD::CTTZ:
2468         //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
2469         Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1,
2470                             DAG.getConstant(getSizeInBits(NVT), NVT),
2471                             ISD::SETEQ);
2472         Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
2473                            DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1);
2474         break;
2475       case ISD::CTLZ:
2476         // Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
2477         Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
2478                              DAG.getConstant(getSizeInBits(NVT) -
2479                                              getSizeInBits(OVT), NVT));
2480         break;
2481       }
2482       break;
2483     }
2484     case TargetLowering::Expand:
2485       Result = ExpandBitCount(Node->getOpcode(), Tmp1);
2486       break;
2487     }
2488     break;
2489
2490     // Unary operators
2491   case ISD::FABS:
2492   case ISD::FNEG:
2493   case ISD::FSQRT:
2494   case ISD::FSIN:
2495   case ISD::FCOS:
2496     Tmp1 = LegalizeOp(Node->getOperand(0));
2497     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2498     case TargetLowering::Promote:
2499     case TargetLowering::Custom:
2500      isCustom = true;
2501      // FALLTHROUGH
2502     case TargetLowering::Legal:
2503       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2504       if (isCustom) {
2505         Tmp1 = TLI.LowerOperation(Result, DAG);
2506         if (Tmp1.Val) Result = Tmp1;
2507       }
2508       break;
2509     case TargetLowering::Expand:
2510       switch (Node->getOpcode()) {
2511       default: assert(0 && "Unreachable!");
2512       case ISD::FNEG:
2513         // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
2514         Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0));
2515         Result = DAG.getNode(ISD::FSUB, Node->getValueType(0), Tmp2, Tmp1);
2516         break;
2517       case ISD::FABS: {
2518         // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
2519         MVT::ValueType VT = Node->getValueType(0);
2520         Tmp2 = DAG.getConstantFP(0.0, VT);
2521         Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, Tmp2, ISD::SETUGT);
2522         Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1);
2523         Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3);
2524         break;
2525       }
2526       case ISD::FSQRT:
2527       case ISD::FSIN:
2528       case ISD::FCOS: {
2529         MVT::ValueType VT = Node->getValueType(0);
2530         const char *FnName = 0;
2531         switch(Node->getOpcode()) {
2532         case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break;
2533         case ISD::FSIN:  FnName = VT == MVT::f32 ? "sinf"  : "sin"; break;
2534         case ISD::FCOS:  FnName = VT == MVT::f32 ? "cosf"  : "cos"; break;
2535         default: assert(0 && "Unreachable!");
2536         }
2537         SDOperand Dummy;
2538         Result = ExpandLibCall(FnName, Node, Dummy);
2539         break;
2540       }
2541       }
2542       break;
2543     }
2544     break;
2545
2546   case ISD::BIT_CONVERT:
2547     if (!isTypeLegal(Node->getOperand(0).getValueType())) {
2548       Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2549     } else {
2550       switch (TLI.getOperationAction(ISD::BIT_CONVERT,
2551                                      Node->getOperand(0).getValueType())) {
2552       default: assert(0 && "Unknown operation action!");
2553       case TargetLowering::Expand:
2554         Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2555         break;
2556       case TargetLowering::Legal:
2557         Tmp1 = LegalizeOp(Node->getOperand(0));
2558         Result = DAG.UpdateNodeOperands(Result, Tmp1);
2559         break;
2560       }
2561     }
2562     break;
2563   case ISD::VBIT_CONVERT: {
2564     assert(Op.getOperand(0).getValueType() == MVT::Vector &&
2565            "Can only have VBIT_CONVERT where input or output is MVT::Vector!");
2566
2567     // The input has to be a vector type, we have to either scalarize it, pack
2568     // it, or convert it based on whether the input vector type is legal.
2569     SDNode *InVal = Node->getOperand(0).Val;
2570     unsigned NumElems =
2571       cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
2572     MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
2573
2574     // Figure out if there is a Packed type corresponding to this Vector
2575     // type.  If so, convert to the packed type.
2576     MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
2577     if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
2578       // Turn this into a bit convert of the packed input.
2579       Result = DAG.getNode(ISD::BIT_CONVERT, Node->getValueType(0),
2580                            PackVectorOp(Node->getOperand(0), TVT));
2581       break;
2582     } else if (NumElems == 1) {
2583       // Turn this into a bit convert of the scalar input.
2584       Result = DAG.getNode(ISD::BIT_CONVERT, Node->getValueType(0),
2585                            PackVectorOp(Node->getOperand(0), EVT));
2586       break;
2587     } else {
2588       // FIXME: UNIMP!  Store then reload
2589       assert(0 && "Cast from unsupported vector type not implemented yet!");
2590     }
2591   }
2592
2593     // Conversion operators.  The source and destination have different types.
2594   case ISD::SINT_TO_FP:
2595   case ISD::UINT_TO_FP: {
2596     bool isSigned = Node->getOpcode() == ISD::SINT_TO_FP;
2597     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2598     case Legal:
2599       switch (TLI.getOperationAction(Node->getOpcode(),
2600                                      Node->getOperand(0).getValueType())) {
2601       default: assert(0 && "Unknown operation action!");
2602       case TargetLowering::Custom:
2603         isCustom = true;
2604         // FALLTHROUGH
2605       case TargetLowering::Legal:
2606         Tmp1 = LegalizeOp(Node->getOperand(0));
2607         Result = DAG.UpdateNodeOperands(Result, Tmp1);
2608         if (isCustom) {
2609           Tmp1 = TLI.LowerOperation(Result, DAG);
2610           if (Tmp1.Val) Result = Tmp1;
2611         }
2612         break;
2613       case TargetLowering::Expand:
2614         Result = ExpandLegalINT_TO_FP(isSigned,
2615                                       LegalizeOp(Node->getOperand(0)),
2616                                       Node->getValueType(0));
2617         break;
2618       case TargetLowering::Promote:
2619         Result = PromoteLegalINT_TO_FP(LegalizeOp(Node->getOperand(0)),
2620                                        Node->getValueType(0),
2621                                        isSigned);
2622         break;
2623       }
2624       break;
2625     case Expand:
2626       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP,
2627                              Node->getValueType(0), Node->getOperand(0));
2628       break;
2629     case Promote:
2630       Tmp1 = PromoteOp(Node->getOperand(0));
2631       if (isSigned) {
2632         Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, Tmp1.getValueType(),
2633                  Tmp1, DAG.getValueType(Node->getOperand(0).getValueType()));
2634       } else {
2635         Tmp1 = DAG.getZeroExtendInReg(Tmp1,
2636                                       Node->getOperand(0).getValueType());
2637       }
2638       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2639       Result = LegalizeOp(Result);  // The 'op' is not necessarily legal!
2640       break;
2641     }
2642     break;
2643   }
2644   case ISD::TRUNCATE:
2645     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2646     case Legal:
2647       Tmp1 = LegalizeOp(Node->getOperand(0));
2648       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2649       break;
2650     case Expand:
2651       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
2652
2653       // Since the result is legal, we should just be able to truncate the low
2654       // part of the source.
2655       Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
2656       break;
2657     case Promote:
2658       Result = PromoteOp(Node->getOperand(0));
2659       Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
2660       break;
2661     }
2662     break;
2663
2664   case ISD::FP_TO_SINT:
2665   case ISD::FP_TO_UINT:
2666     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2667     case Legal:
2668       Tmp1 = LegalizeOp(Node->getOperand(0));
2669
2670       switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))){
2671       default: assert(0 && "Unknown operation action!");
2672       case TargetLowering::Custom:
2673         isCustom = true;
2674         // FALLTHROUGH
2675       case TargetLowering::Legal:
2676         Result = DAG.UpdateNodeOperands(Result, Tmp1);
2677         if (isCustom) {
2678           Tmp1 = TLI.LowerOperation(Result, DAG);
2679           if (Tmp1.Val) Result = Tmp1;
2680         }
2681         break;
2682       case TargetLowering::Promote:
2683         Result = PromoteLegalFP_TO_INT(Tmp1, Node->getValueType(0),
2684                                        Node->getOpcode() == ISD::FP_TO_SINT);
2685         break;
2686       case TargetLowering::Expand:
2687         if (Node->getOpcode() == ISD::FP_TO_UINT) {
2688           SDOperand True, False;
2689           MVT::ValueType VT =  Node->getOperand(0).getValueType();
2690           MVT::ValueType NVT = Node->getValueType(0);
2691           unsigned ShiftAmt = MVT::getSizeInBits(Node->getValueType(0))-1;
2692           Tmp2 = DAG.getConstantFP((double)(1ULL << ShiftAmt), VT);
2693           Tmp3 = DAG.getSetCC(TLI.getSetCCResultTy(),
2694                             Node->getOperand(0), Tmp2, ISD::SETLT);
2695           True = DAG.getNode(ISD::FP_TO_SINT, NVT, Node->getOperand(0));
2696           False = DAG.getNode(ISD::FP_TO_SINT, NVT,
2697                               DAG.getNode(ISD::FSUB, VT, Node->getOperand(0),
2698                                           Tmp2));
2699           False = DAG.getNode(ISD::XOR, NVT, False,
2700                               DAG.getConstant(1ULL << ShiftAmt, NVT));
2701           Result = DAG.getNode(ISD::SELECT, NVT, Tmp3, True, False);
2702           break;
2703         } else {
2704           assert(0 && "Do not know how to expand FP_TO_SINT yet!");
2705         }
2706         break;
2707       }
2708       break;
2709     case Expand:
2710       assert(0 && "Shouldn't need to expand other operators here!");
2711     case Promote:
2712       Tmp1 = PromoteOp(Node->getOperand(0));
2713       Result = DAG.UpdateNodeOperands(Result, LegalizeOp(Tmp1));
2714       Result = LegalizeOp(Result);
2715       break;
2716     }
2717     break;
2718
2719   case ISD::ANY_EXTEND:
2720   case ISD::ZERO_EXTEND:
2721   case ISD::SIGN_EXTEND:
2722   case ISD::FP_EXTEND:
2723   case ISD::FP_ROUND:
2724     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2725     case Expand: assert(0 && "Shouldn't need to expand other operators here!");
2726     case Legal:
2727       Tmp1 = LegalizeOp(Node->getOperand(0));
2728       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2729       break;
2730     case Promote:
2731       switch (Node->getOpcode()) {
2732       case ISD::ANY_EXTEND:
2733         Tmp1 = PromoteOp(Node->getOperand(0));
2734         Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Tmp1);
2735         break;
2736       case ISD::ZERO_EXTEND:
2737         Result = PromoteOp(Node->getOperand(0));
2738         Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result);
2739         Result = DAG.getZeroExtendInReg(Result,
2740                                         Node->getOperand(0).getValueType());
2741         break;
2742       case ISD::SIGN_EXTEND:
2743         Result = PromoteOp(Node->getOperand(0));
2744         Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result);
2745         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
2746                              Result,
2747                           DAG.getValueType(Node->getOperand(0).getValueType()));
2748         break;
2749       case ISD::FP_EXTEND:
2750         Result = PromoteOp(Node->getOperand(0));
2751         if (Result.getValueType() != Op.getValueType())
2752           // Dynamically dead while we have only 2 FP types.
2753           Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
2754         break;
2755       case ISD::FP_ROUND:
2756         Result = PromoteOp(Node->getOperand(0));
2757         Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
2758         break;
2759       }
2760     }
2761     break;
2762   case ISD::FP_ROUND_INREG:
2763   case ISD::SIGN_EXTEND_INREG: {
2764     Tmp1 = LegalizeOp(Node->getOperand(0));
2765     MVT::ValueType ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
2766
2767     // If this operation is not supported, convert it to a shl/shr or load/store
2768     // pair.
2769     switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
2770     default: assert(0 && "This action not supported for this op yet!");
2771     case TargetLowering::Legal:
2772       Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
2773       break;
2774     case TargetLowering::Expand:
2775       // If this is an integer extend and shifts are supported, do that.
2776       if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
2777         // NOTE: we could fall back on load/store here too for targets without
2778         // SAR.  However, it is doubtful that any exist.
2779         unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
2780                             MVT::getSizeInBits(ExtraVT);
2781         SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy());
2782         Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
2783                              Node->getOperand(0), ShiftCst);
2784         Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
2785                              Result, ShiftCst);
2786       } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
2787         // The only way we can lower this is to turn it into a STORETRUNC,
2788         // EXTLOAD pair, targetting a temporary location (a stack slot).
2789
2790         // NOTE: there is a choice here between constantly creating new stack
2791         // slots and always reusing the same one.  We currently always create
2792         // new ones, as reuse may inhibit scheduling.
2793         const Type *Ty = MVT::getTypeForValueType(ExtraVT);
2794         unsigned TySize = (unsigned)TLI.getTargetData()->getTypeSize(Ty);
2795         unsigned Align  = TLI.getTargetData()->getTypeAlignment(Ty);
2796         MachineFunction &MF = DAG.getMachineFunction();
2797         int SSFI =
2798           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
2799         SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
2800         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
2801                              Node->getOperand(0), StackSlot,
2802                              DAG.getSrcValue(NULL), DAG.getValueType(ExtraVT));
2803         Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
2804                                 Result, StackSlot, DAG.getSrcValue(NULL),
2805                                 ExtraVT);
2806       } else {
2807         assert(0 && "Unknown op");
2808       }
2809       break;
2810     }
2811     break;
2812   }
2813   }
2814
2815   assert(Result.getValueType() == Op.getValueType() &&
2816          "Bad legalization!");
2817
2818   // Make sure that the generated code is itself legal.
2819   if (Result != Op)
2820     Result = LegalizeOp(Result);
2821
2822   // Note that LegalizeOp may be reentered even from single-use nodes, which
2823   // means that we always must cache transformed nodes.
2824   AddLegalizedOperand(Op, Result);
2825   return Result;
2826 }
2827
2828 /// PromoteOp - Given an operation that produces a value in an invalid type,
2829 /// promote it to compute the value into a larger type.  The produced value will
2830 /// have the correct bits for the low portion of the register, but no guarantee
2831 /// is made about the top bits: it may be zero, sign-extended, or garbage.
2832 SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
2833   MVT::ValueType VT = Op.getValueType();
2834   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
2835   assert(getTypeAction(VT) == Promote &&
2836          "Caller should expand or legalize operands that are not promotable!");
2837   assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
2838          "Cannot promote to smaller type!");
2839
2840   SDOperand Tmp1, Tmp2, Tmp3;
2841   SDOperand Result;
2842   SDNode *Node = Op.Val;
2843
2844   std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
2845   if (I != PromotedNodes.end()) return I->second;
2846
2847   switch (Node->getOpcode()) {
2848   case ISD::CopyFromReg:
2849     assert(0 && "CopyFromReg must be legal!");
2850   default:
2851     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
2852     assert(0 && "Do not know how to promote this operator!");
2853     abort();
2854   case ISD::UNDEF:
2855     Result = DAG.getNode(ISD::UNDEF, NVT);
2856     break;
2857   case ISD::Constant:
2858     if (VT != MVT::i1)
2859       Result = DAG.getNode(ISD::SIGN_EXTEND, NVT, Op);
2860     else
2861       Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
2862     assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
2863     break;
2864   case ISD::ConstantFP:
2865     Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
2866     assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
2867     break;
2868
2869   case ISD::SETCC:
2870     assert(isTypeLegal(TLI.getSetCCResultTy()) && "SetCC type is not legal??");
2871     Result = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(),Node->getOperand(0),
2872                          Node->getOperand(1), Node->getOperand(2));
2873     break;
2874
2875   case ISD::TRUNCATE:
2876     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2877     case Legal:
2878       Result = LegalizeOp(Node->getOperand(0));
2879       assert(Result.getValueType() >= NVT &&
2880              "This truncation doesn't make sense!");
2881       if (Result.getValueType() > NVT)    // Truncate to NVT instead of VT
2882         Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
2883       break;
2884     case Promote:
2885       // The truncation is not required, because we don't guarantee anything
2886       // about high bits anyway.
2887       Result = PromoteOp(Node->getOperand(0));
2888       break;
2889     case Expand:
2890       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
2891       // Truncate the low part of the expanded value to the result type
2892       Result = DAG.getNode(ISD::TRUNCATE, NVT, Tmp1);
2893     }
2894     break;
2895   case ISD::SIGN_EXTEND:
2896   case ISD::ZERO_EXTEND:
2897   case ISD::ANY_EXTEND:
2898     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2899     case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
2900     case Legal:
2901       // Input is legal?  Just do extend all the way to the larger type.
2902       Result = DAG.getNode(Node->getOpcode(), NVT, Node->getOperand(0));
2903       break;
2904     case Promote:
2905       // Promote the reg if it's smaller.
2906       Result = PromoteOp(Node->getOperand(0));
2907       // The high bits are not guaranteed to be anything.  Insert an extend.
2908       if (Node->getOpcode() == ISD::SIGN_EXTEND)
2909         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
2910                          DAG.getValueType(Node->getOperand(0).getValueType()));
2911       else if (Node->getOpcode() == ISD::ZERO_EXTEND)
2912         Result = DAG.getZeroExtendInReg(Result,
2913                                         Node->getOperand(0).getValueType());
2914       break;
2915     }
2916     break;
2917   case ISD::BIT_CONVERT:
2918     Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2919     Result = PromoteOp(Result);
2920     break;
2921
2922   case ISD::FP_EXTEND:
2923     assert(0 && "Case not implemented.  Dynamically dead with 2 FP types!");
2924   case ISD::FP_ROUND:
2925     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2926     case Expand: assert(0 && "BUG: Cannot expand FP regs!");
2927     case Promote:  assert(0 && "Unreachable with 2 FP types!");
2928     case Legal:
2929       // Input is legal?  Do an FP_ROUND_INREG.
2930       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Node->getOperand(0),
2931                            DAG.getValueType(VT));
2932       break;
2933     }
2934     break;
2935
2936   case ISD::SINT_TO_FP:
2937   case ISD::UINT_TO_FP:
2938     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2939     case Legal:
2940       // No extra round required here.
2941       Result = DAG.getNode(Node->getOpcode(), NVT, Node->getOperand(0));
2942       break;
2943
2944     case Promote:
2945       Result = PromoteOp(Node->getOperand(0));
2946       if (Node->getOpcode() == ISD::SINT_TO_FP)
2947         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
2948                              Result,
2949                          DAG.getValueType(Node->getOperand(0).getValueType()));
2950       else
2951         Result = DAG.getZeroExtendInReg(Result,
2952                                         Node->getOperand(0).getValueType());
2953       // No extra round required here.
2954       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
2955       break;
2956     case Expand:
2957       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT,
2958                              Node->getOperand(0));
2959       // Round if we cannot tolerate excess precision.
2960       if (NoExcessFPPrecision)
2961         Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2962                              DAG.getValueType(VT));
2963       break;
2964     }
2965     break;
2966
2967   case ISD::SIGN_EXTEND_INREG:
2968     Result = PromoteOp(Node->getOperand(0));
2969     Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
2970                          Node->getOperand(1));
2971     break;
2972   case ISD::FP_TO_SINT:
2973   case ISD::FP_TO_UINT:
2974     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2975     case Legal:
2976       Tmp1 = Node->getOperand(0);
2977       break;
2978     case Promote:
2979       // The input result is prerounded, so we don't have to do anything
2980       // special.
2981       Tmp1 = PromoteOp(Node->getOperand(0));
2982       break;
2983     case Expand:
2984       assert(0 && "not implemented");
2985     }
2986     // If we're promoting a UINT to a larger size, check to see if the new node
2987     // will be legal.  If it isn't, check to see if FP_TO_SINT is legal, since
2988     // we can use that instead.  This allows us to generate better code for
2989     // FP_TO_UINT for small destination sizes on targets where FP_TO_UINT is not
2990     // legal, such as PowerPC.
2991     if (Node->getOpcode() == ISD::FP_TO_UINT &&
2992         !TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) &&
2993         (TLI.isOperationLegal(ISD::FP_TO_SINT, NVT) ||
2994          TLI.getOperationAction(ISD::FP_TO_SINT, NVT)==TargetLowering::Custom)){
2995       Result = DAG.getNode(ISD::FP_TO_SINT, NVT, Tmp1);
2996     } else {
2997       Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2998     }
2999     break;
3000
3001   case ISD::FABS:
3002   case ISD::FNEG:
3003     Tmp1 = PromoteOp(Node->getOperand(0));
3004     assert(Tmp1.getValueType() == NVT);
3005     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
3006     // NOTE: we do not have to do any extra rounding here for
3007     // NoExcessFPPrecision, because we know the input will have the appropriate
3008     // precision, and these operations don't modify precision at all.
3009     break;
3010
3011   case ISD::FSQRT:
3012   case ISD::FSIN:
3013   case ISD::FCOS:
3014     Tmp1 = PromoteOp(Node->getOperand(0));
3015     assert(Tmp1.getValueType() == NVT);
3016     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
3017     if (NoExcessFPPrecision)
3018       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
3019                            DAG.getValueType(VT));
3020     break;
3021
3022   case ISD::AND:
3023   case ISD::OR:
3024   case ISD::XOR:
3025   case ISD::ADD:
3026   case ISD::SUB:
3027   case ISD::MUL:
3028     // The input may have strange things in the top bits of the registers, but
3029     // these operations don't care.  They may have weird bits going out, but
3030     // that too is okay if they are integer operations.
3031     Tmp1 = PromoteOp(Node->getOperand(0));
3032     Tmp2 = PromoteOp(Node->getOperand(1));
3033     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
3034     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
3035     break;
3036   case ISD::FADD:
3037   case ISD::FSUB:
3038   case ISD::FMUL:
3039     Tmp1 = PromoteOp(Node->getOperand(0));
3040     Tmp2 = PromoteOp(Node->getOperand(1));
3041     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
3042     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
3043
3044     // Floating point operations will give excess precision that we may not be
3045     // able to tolerate.  If we DO allow excess precision, just leave it,
3046     // otherwise excise it.
3047     // FIXME: Why would we need to round FP ops more than integer ones?
3048     //     Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
3049     if (NoExcessFPPrecision)
3050       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
3051                            DAG.getValueType(VT));
3052     break;
3053
3054   case ISD::SDIV:
3055   case ISD::SREM:
3056     // These operators require that their input be sign extended.
3057     Tmp1 = PromoteOp(Node->getOperand(0));
3058     Tmp2 = PromoteOp(Node->getOperand(1));
3059     if (MVT::isInteger(NVT)) {
3060       Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
3061                          DAG.getValueType(VT));
3062       Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
3063                          DAG.getValueType(VT));
3064     }
3065     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
3066
3067     // Perform FP_ROUND: this is probably overly pessimistic.
3068     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
3069       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
3070                            DAG.getValueType(VT));
3071     break;
3072   case ISD::FDIV:
3073   case ISD::FREM:
3074   case ISD::FCOPYSIGN:
3075     // These operators require that their input be fp extended.
3076     switch (getTypeAction(Node->getOperand(0).getValueType())) {
3077       case Legal:
3078         Tmp1 = LegalizeOp(Node->getOperand(0));
3079         break;
3080       case Promote:
3081         Tmp1 = PromoteOp(Node->getOperand(0));
3082         break;
3083       case Expand:
3084         assert(0 && "not implemented");
3085     }
3086     switch (getTypeAction(Node->getOperand(1).getValueType())) {
3087       case Legal:
3088         Tmp2 = LegalizeOp(Node->getOperand(1));
3089         break;
3090       case Promote:
3091         Tmp2 = PromoteOp(Node->getOperand(1));
3092         break;
3093       case Expand:
3094         assert(0 && "not implemented");
3095     }
3096     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
3097
3098     // Perform FP_ROUND: this is probably overly pessimistic.
3099     if (NoExcessFPPrecision && Node->getOpcode() != ISD::FCOPYSIGN)
3100       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
3101                            DAG.getValueType(VT));
3102     break;
3103
3104   case ISD::UDIV:
3105   case ISD::UREM:
3106     // These operators require that their input be zero extended.
3107     Tmp1 = PromoteOp(Node->getOperand(0));
3108     Tmp2 = PromoteOp(Node->getOperand(1));
3109     assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
3110     Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
3111     Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
3112     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
3113     break;
3114
3115   case ISD::SHL:
3116     Tmp1 = PromoteOp(Node->getOperand(0));
3117     Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Node->getOperand(1));
3118     break;
3119   case ISD::SRA:
3120     // The input value must be properly sign extended.
3121     Tmp1 = PromoteOp(Node->getOperand(0));
3122     Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
3123                        DAG.getValueType(VT));
3124     Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Node->getOperand(1));
3125     break;
3126   case ISD::SRL:
3127     // The input value must be properly zero extended.
3128     Tmp1 = PromoteOp(Node->getOperand(0));
3129     Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
3130     Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Node->getOperand(1));
3131     break;
3132
3133   case ISD::VAARG:
3134     Tmp1 = Node->getOperand(0);   // Get the chain.
3135     Tmp2 = Node->getOperand(1);   // Get the pointer.
3136     if (TLI.getOperationAction(ISD::VAARG, VT) == TargetLowering::Custom) {
3137       Tmp3 = DAG.getVAArg(VT, Tmp1, Tmp2, Node->getOperand(2));
3138       Result = TLI.CustomPromoteOperation(Tmp3, DAG);
3139     } else {
3140       SDOperand VAList = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp2,
3141                                      Node->getOperand(2));
3142       // Increment the pointer, VAList, to the next vaarg
3143       Tmp3 = DAG.getNode(ISD::ADD, TLI.getPointerTy(), VAList,
3144                          DAG.getConstant(MVT::getSizeInBits(VT)/8,
3145                                          TLI.getPointerTy()));
3146       // Store the incremented VAList to the legalized pointer
3147       Tmp3 = DAG.getNode(ISD::STORE, MVT::Other, VAList.getValue(1), Tmp3, Tmp2,
3148                          Node->getOperand(2));
3149       // Load the actual argument out of the pointer VAList
3150       Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Tmp3, VAList,
3151                               DAG.getSrcValue(0), VT);
3152     }
3153     // Remember that we legalized the chain.
3154     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
3155     break;
3156
3157   case ISD::LOAD:
3158     Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Node->getOperand(0),
3159                             Node->getOperand(1), Node->getOperand(2), VT);
3160     // Remember that we legalized the chain.
3161     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
3162     break;
3163   case ISD::SEXTLOAD:
3164   case ISD::ZEXTLOAD:
3165   case ISD::EXTLOAD:
3166     Result = DAG.getExtLoad(Node->getOpcode(), NVT, Node->getOperand(0),
3167                             Node->getOperand(1), Node->getOperand(2),
3168                             cast<VTSDNode>(Node->getOperand(3))->getVT());
3169     // Remember that we legalized the chain.
3170     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
3171     break;
3172   case ISD::SELECT:
3173     Tmp2 = PromoteOp(Node->getOperand(1));   // Legalize the op0
3174     Tmp3 = PromoteOp(Node->getOperand(2));   // Legalize the op1
3175     Result = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), Tmp2, Tmp3);
3176     break;
3177   case ISD::SELECT_CC:
3178     Tmp2 = PromoteOp(Node->getOperand(2));   // True
3179     Tmp3 = PromoteOp(Node->getOperand(3));   // False
3180     Result = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
3181                          Node->getOperand(1), Tmp2, Tmp3, Node->getOperand(4));
3182     break;
3183   case ISD::BSWAP:
3184     Tmp1 = Node->getOperand(0);
3185     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
3186     Tmp1 = DAG.getNode(ISD::BSWAP, NVT, Tmp1);
3187     Result = DAG.getNode(ISD::SRL, NVT, Tmp1,
3188                          DAG.getConstant(getSizeInBits(NVT) - getSizeInBits(VT),
3189                                          TLI.getShiftAmountTy()));
3190     break;
3191   case ISD::CTPOP:
3192   case ISD::CTTZ:
3193   case ISD::CTLZ:
3194     // Zero extend the argument
3195     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Node->getOperand(0));
3196     // Perform the larger operation, then subtract if needed.
3197     Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
3198     switch(Node->getOpcode()) {
3199     case ISD::CTPOP:
3200       Result = Tmp1;
3201       break;
3202     case ISD::CTTZ:
3203       // if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
3204       Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1,
3205                           DAG.getConstant(getSizeInBits(NVT), NVT), ISD::SETEQ);
3206       Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
3207                            DAG.getConstant(getSizeInBits(VT), NVT), Tmp1);
3208       break;
3209     case ISD::CTLZ:
3210       //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
3211       Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
3212                            DAG.getConstant(getSizeInBits(NVT) -
3213                                            getSizeInBits(VT), NVT));
3214       break;
3215     }
3216     break;
3217   case ISD::VEXTRACT_VECTOR_ELT:
3218     Result = PromoteOp(LowerVEXTRACT_VECTOR_ELT(Op));
3219     break;
3220   case ISD::EXTRACT_VECTOR_ELT:
3221     Result = PromoteOp(ExpandEXTRACT_VECTOR_ELT(Op));
3222     break;
3223   }
3224
3225   assert(Result.Val && "Didn't set a result!");
3226
3227   // Make sure the result is itself legal.
3228   Result = LegalizeOp(Result);
3229
3230   // Remember that we promoted this!
3231   AddPromotedOperand(Op, Result);
3232   return Result;
3233 }
3234
3235 /// LowerVEXTRACT_VECTOR_ELT - Lower a VEXTRACT_VECTOR_ELT operation into a
3236 /// EXTRACT_VECTOR_ELT operation, to memory operations, or to scalar code based
3237 /// on the vector type.  The return type of this matches the element type of the
3238 /// vector, which may not be legal for the target.
3239 SDOperand SelectionDAGLegalize::LowerVEXTRACT_VECTOR_ELT(SDOperand Op) {
3240   // We know that operand #0 is the Vec vector.  If the index is a constant
3241   // or if the invec is a supported hardware type, we can use it.  Otherwise,
3242   // lower to a store then an indexed load.
3243   SDOperand Vec = Op.getOperand(0);
3244   SDOperand Idx = LegalizeOp(Op.getOperand(1));
3245
3246   SDNode *InVal = Vec.Val;
3247   unsigned NumElems = cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
3248   MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
3249
3250   // Figure out if there is a Packed type corresponding to this Vector
3251   // type.  If so, convert to the packed type.
3252   MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
3253   if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
3254     // Turn this into a packed extract_vector_elt operation.
3255     Vec = PackVectorOp(Vec, TVT);
3256     return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, Op.getValueType(), Vec, Idx);
3257   } else if (NumElems == 1) {
3258     // This must be an access of the only element.  Return it.
3259     return PackVectorOp(Vec, EVT);
3260   } else if (ConstantSDNode *CIdx = dyn_cast<ConstantSDNode>(Idx)) {
3261     SDOperand Lo, Hi;
3262     SplitVectorOp(Vec, Lo, Hi);
3263     if (CIdx->getValue() < NumElems/2) {
3264       Vec = Lo;
3265     } else {
3266       Vec = Hi;
3267       Idx = DAG.getConstant(CIdx->getValue() - NumElems/2, Idx.getValueType());
3268     }
3269
3270     // It's now an extract from the appropriate high or low part.  Recurse.
3271     Op = DAG.UpdateNodeOperands(Op, Vec, Idx);
3272     return LowerVEXTRACT_VECTOR_ELT(Op);
3273   } else {
3274     // Variable index case for extract element.
3275     // FIXME: IMPLEMENT STORE/LOAD lowering.  Need alignment of stack slot!!
3276     assert(0 && "unimp!");
3277     return SDOperand();
3278   }
3279 }
3280
3281 /// ExpandEXTRACT_VECTOR_ELT - Expand an EXTRACT_VECTOR_ELT operation into
3282 /// memory traffic.
3283 SDOperand SelectionDAGLegalize::ExpandEXTRACT_VECTOR_ELT(SDOperand Op) {
3284   SDOperand Vector = Op.getOperand(0);
3285   SDOperand Idx    = Op.getOperand(1);
3286
3287   // If the target doesn't support this, store the value to a temporary
3288   // stack slot, then LOAD the scalar element back out.
3289   SDOperand StackPtr = CreateStackTemporary(Vector.getValueType());
3290   SDOperand Ch = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
3291                              Vector, StackPtr, DAG.getSrcValue(NULL));
3292
3293   // Add the offset to the index.
3294   unsigned EltSize = MVT::getSizeInBits(Op.getValueType())/8;
3295   Idx = DAG.getNode(ISD::MUL, Idx.getValueType(), Idx,
3296                     DAG.getConstant(EltSize, Idx.getValueType()));
3297   StackPtr = DAG.getNode(ISD::ADD, Idx.getValueType(), Idx, StackPtr);
3298
3299   return DAG.getLoad(Op.getValueType(), Ch, StackPtr, DAG.getSrcValue(NULL));
3300 }
3301
3302
3303 /// LegalizeSetCCOperands - Attempts to create a legal LHS and RHS for a SETCC
3304 /// with condition CC on the current target.  This usually involves legalizing
3305 /// or promoting the arguments.  In the case where LHS and RHS must be expanded,
3306 /// there may be no choice but to create a new SetCC node to represent the
3307 /// legalized value of setcc lhs, rhs.  In this case, the value is returned in
3308 /// LHS, and the SDOperand returned in RHS has a nil SDNode value.
3309 void SelectionDAGLegalize::LegalizeSetCCOperands(SDOperand &LHS,
3310                                                  SDOperand &RHS,
3311                                                  SDOperand &CC) {
3312   SDOperand Tmp1, Tmp2, Result;
3313
3314   switch (getTypeAction(LHS.getValueType())) {
3315   case Legal:
3316     Tmp1 = LegalizeOp(LHS);   // LHS
3317     Tmp2 = LegalizeOp(RHS);   // RHS
3318     break;
3319   case Promote:
3320     Tmp1 = PromoteOp(LHS);   // LHS
3321     Tmp2 = PromoteOp(RHS);   // RHS
3322
3323     // If this is an FP compare, the operands have already been extended.
3324     if (MVT::isInteger(LHS.getValueType())) {
3325       MVT::ValueType VT = LHS.getValueType();
3326       MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
3327
3328       // Otherwise, we have to insert explicit sign or zero extends.  Note
3329       // that we could insert sign extends for ALL conditions, but zero extend
3330       // is cheaper on many machines (an AND instead of two shifts), so prefer
3331       // it.
3332       switch (cast<CondCodeSDNode>(CC)->get()) {
3333       default: assert(0 && "Unknown integer comparison!");
3334       case ISD::SETEQ:
3335       case ISD::SETNE:
3336       case ISD::SETUGE:
3337       case ISD::SETUGT:
3338       case ISD::SETULE:
3339       case ISD::SETULT:
3340         // ALL of these operations will work if we either sign or zero extend
3341         // the operands (including the unsigned comparisons!).  Zero extend is
3342         // usually a simpler/cheaper operation, so prefer it.
3343         Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
3344         Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
3345         break;
3346       case ISD::SETGE:
3347       case ISD::SETGT:
3348       case ISD::SETLT:
3349       case ISD::SETLE:
3350         Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
3351                            DAG.getValueType(VT));
3352         Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
3353                            DAG.getValueType(VT));
3354         break;
3355       }
3356     }
3357     break;
3358   case Expand:
3359     SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
3360     ExpandOp(LHS, LHSLo, LHSHi);
3361     ExpandOp(RHS, RHSLo, RHSHi);
3362     switch (cast<CondCodeSDNode>(CC)->get()) {
3363     case ISD::SETEQ:
3364     case ISD::SETNE:
3365       if (RHSLo == RHSHi)
3366         if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
3367           if (RHSCST->isAllOnesValue()) {
3368             // Comparison to -1.
3369             Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
3370             Tmp2 = RHSLo;
3371             break;
3372           }
3373
3374       Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
3375       Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
3376       Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
3377       Tmp2 = DAG.getConstant(0, Tmp1.getValueType());
3378       break;
3379     default:
3380       // If this is a comparison of the sign bit, just look at the top part.
3381       // X > -1,  x < 0
3382       if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(RHS))
3383         if ((cast<CondCodeSDNode>(CC)->get() == ISD::SETLT &&
3384              CST->getValue() == 0) ||             // X < 0
3385             (cast<CondCodeSDNode>(CC)->get() == ISD::SETGT &&
3386              CST->isAllOnesValue())) {            // X > -1
3387           Tmp1 = LHSHi;
3388           Tmp2 = RHSHi;
3389           break;
3390         }
3391
3392       // FIXME: This generated code sucks.
3393       ISD::CondCode LowCC;
3394       switch (cast<CondCodeSDNode>(CC)->get()) {
3395       default: assert(0 && "Unknown integer setcc!");
3396       case ISD::SETLT:
3397       case ISD::SETULT: LowCC = ISD::SETULT; break;
3398       case ISD::SETGT:
3399       case ISD::SETUGT: LowCC = ISD::SETUGT; break;
3400       case ISD::SETLE:
3401       case ISD::SETULE: LowCC = ISD::SETULE; break;
3402       case ISD::SETGE:
3403       case ISD::SETUGE: LowCC = ISD::SETUGE; break;
3404       }
3405
3406       // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
3407       // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
3408       // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
3409
3410       // NOTE: on targets without efficient SELECT of bools, we can always use
3411       // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
3412       Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC);
3413       Tmp2 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), LHSHi, RHSHi, CC);
3414       Result = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ);
3415       Result = LegalizeOp(DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
3416                                       Result, Tmp1, Tmp2));
3417       Tmp1 = Result;
3418       Tmp2 = SDOperand();
3419     }
3420   }
3421   LHS = Tmp1;
3422   RHS = Tmp2;
3423 }
3424
3425 /// ExpandBIT_CONVERT - Expand a BIT_CONVERT node into a store/load combination.
3426 /// The resultant code need not be legal.  Note that SrcOp is the input operand
3427 /// to the BIT_CONVERT, not the BIT_CONVERT node itself.
3428 SDOperand SelectionDAGLegalize::ExpandBIT_CONVERT(MVT::ValueType DestVT,
3429                                                   SDOperand SrcOp) {
3430   // Create the stack frame object.
3431   SDOperand FIPtr = CreateStackTemporary(DestVT);
3432
3433   // Emit a store to the stack slot.
3434   SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
3435                                 SrcOp, FIPtr, DAG.getSrcValue(NULL));
3436   // Result is a load from the stack slot.
3437   return DAG.getLoad(DestVT, Store, FIPtr, DAG.getSrcValue(0));
3438 }
3439
3440 SDOperand SelectionDAGLegalize::ExpandSCALAR_TO_VECTOR(SDNode *Node) {
3441   // Create a vector sized/aligned stack slot, store the value to element #0,
3442   // then load the whole vector back out.
3443   SDOperand StackPtr = CreateStackTemporary(Node->getValueType(0));
3444   SDOperand Ch = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
3445                              Node->getOperand(0), StackPtr,
3446                              DAG.getSrcValue(NULL));
3447   return DAG.getLoad(Node->getValueType(0), Ch, StackPtr,DAG.getSrcValue(NULL));
3448 }
3449
3450
3451 /// ExpandBUILD_VECTOR - Expand a BUILD_VECTOR node on targets that don't
3452 /// support the operation, but do support the resultant packed vector type.
3453 SDOperand SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
3454
3455   // If the only non-undef value is the low element, turn this into a
3456   // SCALAR_TO_VECTOR node.  If this is { X, X, X, X }, determine X.
3457   unsigned NumElems = Node->getNumOperands();
3458   bool isOnlyLowElement = true;
3459   SDOperand SplatValue = Node->getOperand(0);
3460   std::map<SDOperand, std::vector<unsigned> > Values;
3461   Values[SplatValue].push_back(0);
3462   bool isConstant = true;
3463   if (!isa<ConstantFPSDNode>(SplatValue) && !isa<ConstantSDNode>(SplatValue) &&
3464       SplatValue.getOpcode() != ISD::UNDEF)
3465     isConstant = false;
3466
3467   for (unsigned i = 1; i < NumElems; ++i) {
3468     SDOperand V = Node->getOperand(i);
3469     Values[V].push_back(i);
3470     if (V.getOpcode() != ISD::UNDEF)
3471       isOnlyLowElement = false;
3472     if (SplatValue != V)
3473       SplatValue = SDOperand(0,0);
3474
3475     // If this isn't a constant element or an undef, we can't use a constant
3476     // pool load.
3477     if (!isa<ConstantFPSDNode>(V) && !isa<ConstantSDNode>(V) &&
3478         V.getOpcode() != ISD::UNDEF)
3479       isConstant = false;
3480   }
3481
3482   if (isOnlyLowElement) {
3483     // If the low element is an undef too, then this whole things is an undef.
3484     if (Node->getOperand(0).getOpcode() == ISD::UNDEF)
3485       return DAG.getNode(ISD::UNDEF, Node->getValueType(0));
3486     // Otherwise, turn this into a scalar_to_vector node.
3487     return DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0),
3488                        Node->getOperand(0));
3489   }
3490
3491   // If all elements are constants, create a load from the constant pool.
3492   if (isConstant) {
3493     MVT::ValueType VT = Node->getValueType(0);
3494     const Type *OpNTy =
3495       MVT::getTypeForValueType(Node->getOperand(0).getValueType());
3496     std::vector<Constant*> CV;
3497     for (unsigned i = 0, e = NumElems; i != e; ++i) {
3498       if (ConstantFPSDNode *V =
3499           dyn_cast<ConstantFPSDNode>(Node->getOperand(i))) {
3500         CV.push_back(ConstantFP::get(OpNTy, V->getValue()));
3501       } else if (ConstantSDNode *V =
3502                  dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
3503         CV.push_back(ConstantUInt::get(OpNTy, V->getValue()));
3504       } else {
3505         assert(Node->getOperand(i).getOpcode() == ISD::UNDEF);
3506         CV.push_back(UndefValue::get(OpNTy));
3507       }
3508     }
3509     Constant *CP = ConstantPacked::get(CV);
3510     SDOperand CPIdx = DAG.getConstantPool(CP, TLI.getPointerTy());
3511     return DAG.getLoad(VT, DAG.getEntryNode(), CPIdx,
3512                        DAG.getSrcValue(NULL));
3513   }
3514
3515   if (SplatValue.Val) {   // Splat of one value?
3516     // Build the shuffle constant vector: <0, 0, 0, 0>
3517     MVT::ValueType MaskVT =
3518       MVT::getIntVectorWithNumElements(NumElems);
3519     SDOperand Zero = DAG.getConstant(0, MVT::getVectorBaseType(MaskVT));
3520     std::vector<SDOperand> ZeroVec(NumElems, Zero);
3521     SDOperand SplatMask = DAG.getNode(ISD::BUILD_VECTOR, MaskVT, ZeroVec);
3522
3523     // If the target supports VECTOR_SHUFFLE and this shuffle mask, use it.
3524     if (isShuffleLegal(Node->getValueType(0), SplatMask)) {
3525       // Get the splatted value into the low element of a vector register.
3526       SDOperand LowValVec =
3527         DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0), SplatValue);
3528
3529       // Return shuffle(LowValVec, undef, <0,0,0,0>)
3530       return DAG.getNode(ISD::VECTOR_SHUFFLE, Node->getValueType(0), LowValVec,
3531                          DAG.getNode(ISD::UNDEF, Node->getValueType(0)),
3532                          SplatMask);
3533     }
3534   }
3535
3536   // If there are only two unique elements, we may be able to turn this into a
3537   // vector shuffle.
3538   if (Values.size() == 2) {
3539     // Build the shuffle constant vector: e.g. <0, 4, 0, 4>
3540     MVT::ValueType MaskVT =
3541       MVT::getIntVectorWithNumElements(NumElems);
3542     std::vector<SDOperand> MaskVec(NumElems);
3543     unsigned i = 0;
3544     for (std::map<SDOperand,std::vector<unsigned> >::iterator I=Values.begin(),
3545            E = Values.end(); I != E; ++I) {
3546       for (std::vector<unsigned>::iterator II = I->second.begin(),
3547              EE = I->second.end(); II != EE; ++II)
3548         MaskVec[*II] = DAG.getConstant(i, MVT::getVectorBaseType(MaskVT));
3549       i += NumElems;
3550     }
3551     SDOperand ShuffleMask = DAG.getNode(ISD::BUILD_VECTOR, MaskVT, MaskVec);
3552
3553     // If the target supports VECTOR_SHUFFLE and this shuffle mask, use it.
3554     if (TLI.isOperationLegal(ISD::SCALAR_TO_VECTOR, Node->getValueType(0)) &&
3555         isShuffleLegal(Node->getValueType(0), ShuffleMask)) {
3556       std::vector<SDOperand> Ops;
3557       for(std::map<SDOperand,std::vector<unsigned> >::iterator I=Values.begin(),
3558             E = Values.end(); I != E; ++I) {
3559         SDOperand Op = DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0),
3560                                    I->first);
3561         Ops.push_back(Op);
3562       }
3563       Ops.push_back(ShuffleMask);
3564
3565       // Return shuffle(LoValVec, HiValVec, <0,1,0,1>)
3566       return DAG.getNode(ISD::VECTOR_SHUFFLE, Node->getValueType(0), Ops);
3567     }
3568   }
3569
3570   // Otherwise, we can't handle this case efficiently.  Allocate a sufficiently
3571   // aligned object on the stack, store each element into it, then load
3572   // the result as a vector.
3573   MVT::ValueType VT = Node->getValueType(0);
3574   // Create the stack frame object.
3575   SDOperand FIPtr = CreateStackTemporary(VT);
3576
3577   // Emit a store of each element to the stack slot.
3578   std::vector<SDOperand> Stores;
3579   unsigned TypeByteSize =
3580     MVT::getSizeInBits(Node->getOperand(0).getValueType())/8;
3581   unsigned VectorSize = MVT::getSizeInBits(VT)/8;
3582   // Store (in the right endianness) the elements to memory.
3583   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
3584     // Ignore undef elements.
3585     if (Node->getOperand(i).getOpcode() == ISD::UNDEF) continue;
3586
3587     unsigned Offset = TypeByteSize*i;
3588
3589     SDOperand Idx = DAG.getConstant(Offset, FIPtr.getValueType());
3590     Idx = DAG.getNode(ISD::ADD, FIPtr.getValueType(), FIPtr, Idx);
3591
3592     Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
3593                                  Node->getOperand(i), Idx,
3594                                  DAG.getSrcValue(NULL)));
3595   }
3596
3597   SDOperand StoreChain;
3598   if (!Stores.empty())    // Not all undef elements?
3599     StoreChain = DAG.getNode(ISD::TokenFactor, MVT::Other, Stores);
3600   else
3601     StoreChain = DAG.getEntryNode();
3602
3603   // Result is a load from the stack slot.
3604   return DAG.getLoad(VT, StoreChain, FIPtr, DAG.getSrcValue(0));
3605 }
3606
3607 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
3608 /// specified value type.
3609 SDOperand SelectionDAGLegalize::CreateStackTemporary(MVT::ValueType VT) {
3610   MachineFrameInfo *FrameInfo = DAG.getMachineFunction().getFrameInfo();
3611   unsigned ByteSize = MVT::getSizeInBits(VT)/8;
3612   int FrameIdx = FrameInfo->CreateStackObject(ByteSize, ByteSize);
3613   return DAG.getFrameIndex(FrameIdx, TLI.getPointerTy());
3614 }
3615
3616 void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp,
3617                                             SDOperand Op, SDOperand Amt,
3618                                             SDOperand &Lo, SDOperand &Hi) {
3619   // Expand the subcomponents.
3620   SDOperand LHSL, LHSH;
3621   ExpandOp(Op, LHSL, LHSH);
3622
3623   std::vector<SDOperand> Ops;
3624   Ops.push_back(LHSL);
3625   Ops.push_back(LHSH);
3626   Ops.push_back(Amt);
3627   std::vector<MVT::ValueType> VTs(2, LHSL.getValueType());
3628   Lo = DAG.getNode(NodeOp, VTs, Ops);
3629   Hi = Lo.getValue(1);
3630 }
3631
3632
3633 /// ExpandShift - Try to find a clever way to expand this shift operation out to
3634 /// smaller elements.  If we can't find a way that is more efficient than a
3635 /// libcall on this target, return false.  Otherwise, return true with the
3636 /// low-parts expanded into Lo and Hi.
3637 bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
3638                                        SDOperand &Lo, SDOperand &Hi) {
3639   assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
3640          "This is not a shift!");
3641
3642   MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
3643   SDOperand ShAmt = LegalizeOp(Amt);
3644   MVT::ValueType ShTy = ShAmt.getValueType();
3645   unsigned VTBits = MVT::getSizeInBits(Op.getValueType());
3646   unsigned NVTBits = MVT::getSizeInBits(NVT);
3647
3648   // Handle the case when Amt is an immediate.  Other cases are currently broken
3649   // and are disabled.
3650   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) {
3651     unsigned Cst = CN->getValue();
3652     // Expand the incoming operand to be shifted, so that we have its parts
3653     SDOperand InL, InH;
3654     ExpandOp(Op, InL, InH);
3655     switch(Opc) {
3656     case ISD::SHL:
3657       if (Cst > VTBits) {
3658         Lo = DAG.getConstant(0, NVT);
3659         Hi = DAG.getConstant(0, NVT);
3660       } else if (Cst > NVTBits) {
3661         Lo = DAG.getConstant(0, NVT);
3662         Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy));
3663       } else if (Cst == NVTBits) {
3664         Lo = DAG.getConstant(0, NVT);
3665         Hi = InL;
3666       } else {
3667         Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy));
3668         Hi = DAG.getNode(ISD::OR, NVT,
3669            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)),
3670            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy)));
3671       }
3672       return true;
3673     case ISD::SRL:
3674       if (Cst > VTBits) {
3675         Lo = DAG.getConstant(0, NVT);
3676         Hi = DAG.getConstant(0, NVT);
3677       } else if (Cst > NVTBits) {
3678         Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy));
3679         Hi = DAG.getConstant(0, NVT);
3680       } else if (Cst == NVTBits) {
3681         Lo = InH;
3682         Hi = DAG.getConstant(0, NVT);
3683       } else {
3684         Lo = DAG.getNode(ISD::OR, NVT,
3685            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
3686            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
3687         Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy));
3688       }
3689       return true;
3690     case ISD::SRA:
3691       if (Cst > VTBits) {
3692         Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
3693                               DAG.getConstant(NVTBits-1, ShTy));
3694       } else if (Cst > NVTBits) {
3695         Lo = DAG.getNode(ISD::SRA, NVT, InH,
3696                            DAG.getConstant(Cst-NVTBits, ShTy));
3697         Hi = DAG.getNode(ISD::SRA, NVT, InH,
3698                               DAG.getConstant(NVTBits-1, ShTy));
3699       } else if (Cst == NVTBits) {
3700         Lo = InH;
3701         Hi = DAG.getNode(ISD::SRA, NVT, InH,
3702                               DAG.getConstant(NVTBits-1, ShTy));
3703       } else {
3704         Lo = DAG.getNode(ISD::OR, NVT,
3705            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
3706            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
3707         Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy));
3708       }
3709       return true;
3710     }
3711   }
3712   return false;
3713 }
3714
3715
3716 // ExpandLibCall - Expand a node into a call to a libcall.  If the result value
3717 // does not fit into a register, return the lo part and set the hi part to the
3718 // by-reg argument.  If it does fit into a single register, return the result
3719 // and leave the Hi part unset.
3720 SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node,
3721                                               SDOperand &Hi) {
3722   assert(!IsLegalizingCall && "Cannot overlap legalization of calls!");
3723   // The input chain to this libcall is the entry node of the function.
3724   // Legalizing the call will automatically add the previous call to the
3725   // dependence.
3726   SDOperand InChain = DAG.getEntryNode();
3727
3728   TargetLowering::ArgListTy Args;
3729   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
3730     MVT::ValueType ArgVT = Node->getOperand(i).getValueType();
3731     const Type *ArgTy = MVT::getTypeForValueType(ArgVT);
3732     Args.push_back(std::make_pair(Node->getOperand(i), ArgTy));
3733   }
3734   SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy());
3735
3736   // Splice the libcall in wherever FindInputOutputChains tells us to.
3737   const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0));
3738   std::pair<SDOperand,SDOperand> CallInfo =
3739     TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, false,
3740                     Callee, Args, DAG);
3741
3742   // Legalize the call sequence, starting with the chain.  This will advance
3743   // the LastCALLSEQ_END to the legalized version of the CALLSEQ_END node that
3744   // was added by LowerCallTo (guaranteeing proper serialization of calls).
3745   LegalizeOp(CallInfo.second);
3746   SDOperand Result;
3747   switch (getTypeAction(CallInfo.first.getValueType())) {
3748   default: assert(0 && "Unknown thing");
3749   case Legal:
3750     Result = CallInfo.first;
3751     break;
3752   case Expand:
3753     ExpandOp(CallInfo.first, Result, Hi);
3754     break;
3755   }
3756   return Result;
3757 }
3758
3759
3760 /// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the
3761 /// destination type is legal.
3762 SDOperand SelectionDAGLegalize::
3763 ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) {
3764   assert(isTypeLegal(DestTy) && "Destination type is not legal!");
3765   assert(getTypeAction(Source.getValueType()) == Expand &&
3766          "This is not an expansion!");
3767   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
3768
3769   if (!isSigned) {
3770     assert(Source.getValueType() == MVT::i64 &&
3771            "This only works for 64-bit -> FP");
3772     // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
3773     // incoming integer is set.  To handle this, we dynamically test to see if
3774     // it is set, and, if so, add a fudge factor.
3775     SDOperand Lo, Hi;
3776     ExpandOp(Source, Lo, Hi);
3777
3778     // If this is unsigned, and not supported, first perform the conversion to
3779     // signed, then adjust the result if the sign bit is set.
3780     SDOperand SignedConv = ExpandIntToFP(true, DestTy,
3781                    DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), Lo, Hi));
3782
3783     SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi,
3784                                      DAG.getConstant(0, Hi.getValueType()),
3785                                      ISD::SETLT);
3786     SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
3787     SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
3788                                       SignSet, Four, Zero);
3789     uint64_t FF = 0x5f800000ULL;
3790     if (TLI.isLittleEndian()) FF <<= 32;
3791     static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
3792
3793     SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
3794     CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
3795     SDOperand FudgeInReg;
3796     if (DestTy == MVT::f32)
3797       FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
3798                                DAG.getSrcValue(NULL));
3799     else {
3800       assert(DestTy == MVT::f64 && "Unexpected conversion");
3801       FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
3802                                   CPIdx, DAG.getSrcValue(NULL), MVT::f32);
3803     }
3804     return DAG.getNode(ISD::FADD, DestTy, SignedConv, FudgeInReg);
3805   }
3806
3807   // Check to see if the target has a custom way to lower this.  If so, use it.
3808   switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) {
3809   default: assert(0 && "This action not implemented for this operation!");
3810   case TargetLowering::Legal:
3811   case TargetLowering::Expand:
3812     break;   // This case is handled below.
3813   case TargetLowering::Custom: {
3814     SDOperand NV = TLI.LowerOperation(DAG.getNode(ISD::SINT_TO_FP, DestTy,
3815                                                   Source), DAG);
3816     if (NV.Val)
3817       return LegalizeOp(NV);
3818     break;   // The target decided this was legal after all
3819   }
3820   }
3821
3822   // Expand the source, then glue it back together for the call.  We must expand
3823   // the source in case it is shared (this pass of legalize must traverse it).
3824   SDOperand SrcLo, SrcHi;
3825   ExpandOp(Source, SrcLo, SrcHi);
3826   Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi);
3827
3828   const char *FnName = 0;
3829   if (DestTy == MVT::f32)
3830     FnName = "__floatdisf";
3831   else {
3832     assert(DestTy == MVT::f64 && "Unknown fp value type!");
3833     FnName = "__floatdidf";
3834   }
3835
3836   Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source);
3837   SDOperand UnusedHiPart;
3838   return ExpandLibCall(FnName, Source.Val, UnusedHiPart);
3839 }
3840
3841 /// ExpandLegalINT_TO_FP - This function is responsible for legalizing a
3842 /// INT_TO_FP operation of the specified operand when the target requests that
3843 /// we expand it.  At this point, we know that the result and operand types are
3844 /// legal for the target.
3845 SDOperand SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned,
3846                                                      SDOperand Op0,
3847                                                      MVT::ValueType DestVT) {
3848   if (Op0.getValueType() == MVT::i32) {
3849     // simple 32-bit [signed|unsigned] integer to float/double expansion
3850
3851     // get the stack frame index of a 8 byte buffer
3852     MachineFunction &MF = DAG.getMachineFunction();
3853     int SSFI = MF.getFrameInfo()->CreateStackObject(8, 8);
3854     // get address of 8 byte buffer
3855     SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
3856     // word offset constant for Hi/Lo address computation
3857     SDOperand WordOff = DAG.getConstant(sizeof(int), TLI.getPointerTy());
3858     // set up Hi and Lo (into buffer) address based on endian
3859     SDOperand Hi = StackSlot;
3860     SDOperand Lo = DAG.getNode(ISD::ADD, TLI.getPointerTy(), StackSlot,WordOff);
3861     if (TLI.isLittleEndian())
3862       std::swap(Hi, Lo);
3863
3864     // if signed map to unsigned space
3865     SDOperand Op0Mapped;
3866     if (isSigned) {
3867       // constant used to invert sign bit (signed to unsigned mapping)
3868       SDOperand SignBit = DAG.getConstant(0x80000000u, MVT::i32);
3869       Op0Mapped = DAG.getNode(ISD::XOR, MVT::i32, Op0, SignBit);
3870     } else {
3871       Op0Mapped = Op0;
3872     }
3873     // store the lo of the constructed double - based on integer input
3874     SDOperand Store1 = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
3875                                    Op0Mapped, Lo, DAG.getSrcValue(NULL));
3876     // initial hi portion of constructed double
3877     SDOperand InitialHi = DAG.getConstant(0x43300000u, MVT::i32);
3878     // store the hi of the constructed double - biased exponent
3879     SDOperand Store2 = DAG.getNode(ISD::STORE, MVT::Other, Store1,
3880                                    InitialHi, Hi, DAG.getSrcValue(NULL));
3881     // load the constructed double
3882     SDOperand Load = DAG.getLoad(MVT::f64, Store2, StackSlot,
3883                                DAG.getSrcValue(NULL));
3884     // FP constant to bias correct the final result
3885     SDOperand Bias = DAG.getConstantFP(isSigned ?
3886                                             BitsToDouble(0x4330000080000000ULL)
3887                                           : BitsToDouble(0x4330000000000000ULL),
3888                                      MVT::f64);
3889     // subtract the bias
3890     SDOperand Sub = DAG.getNode(ISD::FSUB, MVT::f64, Load, Bias);
3891     // final result
3892     SDOperand Result;
3893     // handle final rounding
3894     if (DestVT == MVT::f64) {
3895       // do nothing
3896       Result = Sub;
3897     } else {
3898      // if f32 then cast to f32
3899       Result = DAG.getNode(ISD::FP_ROUND, MVT::f32, Sub);
3900     }
3901     return Result;
3902   }
3903   assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet");
3904   SDOperand Tmp1 = DAG.getNode(ISD::SINT_TO_FP, DestVT, Op0);
3905
3906   SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Op0,
3907                                    DAG.getConstant(0, Op0.getValueType()),
3908                                    ISD::SETLT);
3909   SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
3910   SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
3911                                     SignSet, Four, Zero);
3912
3913   // If the sign bit of the integer is set, the large number will be treated
3914   // as a negative number.  To counteract this, the dynamic code adds an
3915   // offset depending on the data type.
3916   uint64_t FF;
3917   switch (Op0.getValueType()) {
3918   default: assert(0 && "Unsupported integer type!");
3919   case MVT::i8 : FF = 0x43800000ULL; break;  // 2^8  (as a float)
3920   case MVT::i16: FF = 0x47800000ULL; break;  // 2^16 (as a float)
3921   case MVT::i32: FF = 0x4F800000ULL; break;  // 2^32 (as a float)
3922   case MVT::i64: FF = 0x5F800000ULL; break;  // 2^64 (as a float)
3923   }
3924   if (TLI.isLittleEndian()) FF <<= 32;
3925   static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
3926
3927   SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
3928   CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
3929   SDOperand FudgeInReg;
3930   if (DestVT == MVT::f32)
3931     FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
3932                              DAG.getSrcValue(NULL));
3933   else {
3934     assert(DestVT == MVT::f64 && "Unexpected conversion");
3935     FudgeInReg = LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, MVT::f64,
3936                                            DAG.getEntryNode(), CPIdx,
3937                                            DAG.getSrcValue(NULL), MVT::f32));
3938   }
3939
3940   return DAG.getNode(ISD::FADD, DestVT, Tmp1, FudgeInReg);
3941 }
3942
3943 /// PromoteLegalINT_TO_FP - This function is responsible for legalizing a
3944 /// *INT_TO_FP operation of the specified operand when the target requests that
3945 /// we promote it.  At this point, we know that the result and operand types are
3946 /// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP
3947 /// operation that takes a larger input.
3948 SDOperand SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDOperand LegalOp,
3949                                                       MVT::ValueType DestVT,
3950                                                       bool isSigned) {
3951   // First step, figure out the appropriate *INT_TO_FP operation to use.
3952   MVT::ValueType NewInTy = LegalOp.getValueType();
3953
3954   unsigned OpToUse = 0;
3955
3956   // Scan for the appropriate larger type to use.
3957   while (1) {
3958     NewInTy = (MVT::ValueType)(NewInTy+1);
3959     assert(MVT::isInteger(NewInTy) && "Ran out of possibilities!");
3960
3961     // If the target supports SINT_TO_FP of this type, use it.
3962     switch (TLI.getOperationAction(ISD::SINT_TO_FP, NewInTy)) {
3963       default: break;
3964       case TargetLowering::Legal:
3965         if (!TLI.isTypeLegal(NewInTy))
3966           break;  // Can't use this datatype.
3967         // FALL THROUGH.
3968       case TargetLowering::Custom:
3969         OpToUse = ISD::SINT_TO_FP;
3970         break;
3971     }
3972     if (OpToUse) break;
3973     if (isSigned) continue;
3974
3975     // If the target supports UINT_TO_FP of this type, use it.
3976     switch (TLI.getOperationAction(ISD::UINT_TO_FP, NewInTy)) {
3977       default: break;
3978       case TargetLowering::Legal:
3979         if (!TLI.isTypeLegal(NewInTy))
3980           break;  // Can't use this datatype.
3981         // FALL THROUGH.
3982       case TargetLowering::Custom:
3983         OpToUse = ISD::UINT_TO_FP;
3984         break;
3985     }
3986     if (OpToUse) break;
3987
3988     // Otherwise, try a larger type.
3989   }
3990
3991   // Okay, we found the operation and type to use.  Zero extend our input to the
3992   // desired type then run the operation on it.
3993   return DAG.getNode(OpToUse, DestVT,
3994                      DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND,
3995                                  NewInTy, LegalOp));
3996 }
3997
3998 /// PromoteLegalFP_TO_INT - This function is responsible for legalizing a
3999 /// FP_TO_*INT operation of the specified operand when the target requests that
4000 /// we promote it.  At this point, we know that the result and operand types are
4001 /// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT
4002 /// operation that returns a larger result.
4003 SDOperand SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDOperand LegalOp,
4004                                                       MVT::ValueType DestVT,
4005                                                       bool isSigned) {
4006   // First step, figure out the appropriate FP_TO*INT operation to use.
4007   MVT::ValueType NewOutTy = DestVT;
4008
4009   unsigned OpToUse = 0;
4010
4011   // Scan for the appropriate larger type to use.
4012   while (1) {
4013     NewOutTy = (MVT::ValueType)(NewOutTy+1);
4014     assert(MVT::isInteger(NewOutTy) && "Ran out of possibilities!");
4015
4016     // If the target supports FP_TO_SINT returning this type, use it.
4017     switch (TLI.getOperationAction(ISD::FP_TO_SINT, NewOutTy)) {
4018     default: break;
4019     case TargetLowering::Legal:
4020       if (!TLI.isTypeLegal(NewOutTy))
4021         break;  // Can't use this datatype.
4022       // FALL THROUGH.
4023     case TargetLowering::Custom:
4024       OpToUse = ISD::FP_TO_SINT;
4025       break;
4026     }
4027     if (OpToUse) break;
4028
4029     // If the target supports FP_TO_UINT of this type, use it.
4030     switch (TLI.getOperationAction(ISD::FP_TO_UINT, NewOutTy)) {
4031     default: break;
4032     case TargetLowering::Legal:
4033       if (!TLI.isTypeLegal(NewOutTy))
4034         break;  // Can't use this datatype.
4035       // FALL THROUGH.
4036     case TargetLowering::Custom:
4037       OpToUse = ISD::FP_TO_UINT;
4038       break;
4039     }
4040     if (OpToUse) break;
4041
4042     // Otherwise, try a larger type.
4043   }
4044
4045   // Okay, we found the operation and type to use.  Truncate the result of the
4046   // extended FP_TO_*INT operation to the desired size.
4047   return DAG.getNode(ISD::TRUNCATE, DestVT,
4048                      DAG.getNode(OpToUse, NewOutTy, LegalOp));
4049 }
4050
4051 /// ExpandBSWAP - Open code the operations for BSWAP of the specified operation.
4052 ///
4053 SDOperand SelectionDAGLegalize::ExpandBSWAP(SDOperand Op) {
4054   MVT::ValueType VT = Op.getValueType();
4055   MVT::ValueType SHVT = TLI.getShiftAmountTy();
4056   SDOperand Tmp1, Tmp2, Tmp3, Tmp4, Tmp5, Tmp6, Tmp7, Tmp8;
4057   switch (VT) {
4058   default: assert(0 && "Unhandled Expand type in BSWAP!"); abort();
4059   case MVT::i16:
4060     Tmp2 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
4061     Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
4062     return DAG.getNode(ISD::OR, VT, Tmp1, Tmp2);
4063   case MVT::i32:
4064     Tmp4 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(24, SHVT));
4065     Tmp3 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
4066     Tmp2 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
4067     Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(24, SHVT));
4068     Tmp3 = DAG.getNode(ISD::AND, VT, Tmp3, DAG.getConstant(0xFF0000, VT));
4069     Tmp2 = DAG.getNode(ISD::AND, VT, Tmp2, DAG.getConstant(0xFF00, VT));
4070     Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp3);
4071     Tmp2 = DAG.getNode(ISD::OR, VT, Tmp2, Tmp1);
4072     return DAG.getNode(ISD::OR, VT, Tmp4, Tmp2);
4073   case MVT::i64:
4074     Tmp8 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(56, SHVT));
4075     Tmp7 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(40, SHVT));
4076     Tmp6 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(24, SHVT));
4077     Tmp5 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
4078     Tmp4 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
4079     Tmp3 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(24, SHVT));
4080     Tmp2 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(40, SHVT));
4081     Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(56, SHVT));
4082     Tmp7 = DAG.getNode(ISD::AND, VT, Tmp7, DAG.getConstant(255ULL<<48, VT));
4083     Tmp6 = DAG.getNode(ISD::AND, VT, Tmp6, DAG.getConstant(255ULL<<40, VT));
4084     Tmp5 = DAG.getNode(ISD::AND, VT, Tmp5, DAG.getConstant(255ULL<<32, VT));
4085     Tmp4 = DAG.getNode(ISD::AND, VT, Tmp4, DAG.getConstant(255ULL<<24, VT));
4086     Tmp3 = DAG.getNode(ISD::AND, VT, Tmp3, DAG.getConstant(255ULL<<16, VT));
4087     Tmp2 = DAG.getNode(ISD::AND, VT, Tmp2, DAG.getConstant(255ULL<<8 , VT));
4088     Tmp8 = DAG.getNode(ISD::OR, VT, Tmp8, Tmp7);
4089     Tmp6 = DAG.getNode(ISD::OR, VT, Tmp6, Tmp5);
4090     Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp3);
4091     Tmp2 = DAG.getNode(ISD::OR, VT, Tmp2, Tmp1);
4092     Tmp8 = DAG.getNode(ISD::OR, VT, Tmp8, Tmp6);
4093     Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp2);
4094     return DAG.getNode(ISD::OR, VT, Tmp8, Tmp4);
4095   }
4096 }
4097
4098 /// ExpandBitCount - Expand the specified bitcount instruction into operations.
4099 ///
4100 SDOperand SelectionDAGLegalize::ExpandBitCount(unsigned Opc, SDOperand Op) {
4101   switch (Opc) {
4102   default: assert(0 && "Cannot expand this yet!");
4103   case ISD::CTPOP: {
4104     static const uint64_t mask[6] = {
4105       0x5555555555555555ULL, 0x3333333333333333ULL,
4106       0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
4107       0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
4108     };
4109     MVT::ValueType VT = Op.getValueType();
4110     MVT::ValueType ShVT = TLI.getShiftAmountTy();
4111     unsigned len = getSizeInBits(VT);
4112     for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
4113       //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
4114       SDOperand Tmp2 = DAG.getConstant(mask[i], VT);
4115       SDOperand Tmp3 = DAG.getConstant(1ULL << i, ShVT);
4116       Op = DAG.getNode(ISD::ADD, VT, DAG.getNode(ISD::AND, VT, Op, Tmp2),
4117                        DAG.getNode(ISD::AND, VT,
4118                                    DAG.getNode(ISD::SRL, VT, Op, Tmp3),Tmp2));
4119     }
4120     return Op;
4121   }
4122   case ISD::CTLZ: {
4123     // for now, we do this:
4124     // x = x | (x >> 1);
4125     // x = x | (x >> 2);
4126     // ...
4127     // x = x | (x >>16);
4128     // x = x | (x >>32); // for 64-bit input
4129     // return popcount(~x);
4130     //
4131     // but see also: http://www.hackersdelight.org/HDcode/nlz.cc
4132     MVT::ValueType VT = Op.getValueType();
4133     MVT::ValueType ShVT = TLI.getShiftAmountTy();
4134     unsigned len = getSizeInBits(VT);
4135     for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
4136       SDOperand Tmp3 = DAG.getConstant(1ULL << i, ShVT);
4137       Op = DAG.getNode(ISD::OR, VT, Op, DAG.getNode(ISD::SRL, VT, Op, Tmp3));
4138     }
4139     Op = DAG.getNode(ISD::XOR, VT, Op, DAG.getConstant(~0ULL, VT));
4140     return DAG.getNode(ISD::CTPOP, VT, Op);
4141   }
4142   case ISD::CTTZ: {
4143     // for now, we use: { return popcount(~x & (x - 1)); }
4144     // unless the target has ctlz but not ctpop, in which case we use:
4145     // { return 32 - nlz(~x & (x-1)); }
4146     // see also http://www.hackersdelight.org/HDcode/ntz.cc
4147     MVT::ValueType VT = Op.getValueType();
4148     SDOperand Tmp2 = DAG.getConstant(~0ULL, VT);
4149     SDOperand Tmp3 = DAG.getNode(ISD::AND, VT,
4150                        DAG.getNode(ISD::XOR, VT, Op, Tmp2),
4151                        DAG.getNode(ISD::SUB, VT, Op, DAG.getConstant(1, VT)));
4152     // If ISD::CTLZ is legal and CTPOP isn't, then do that instead.
4153     if (!TLI.isOperationLegal(ISD::CTPOP, VT) &&
4154         TLI.isOperationLegal(ISD::CTLZ, VT))
4155       return DAG.getNode(ISD::SUB, VT,
4156                          DAG.getConstant(getSizeInBits(VT), VT),
4157                          DAG.getNode(ISD::CTLZ, VT, Tmp3));
4158     return DAG.getNode(ISD::CTPOP, VT, Tmp3);
4159   }
4160   }
4161 }
4162
4163 /// ExpandOp - Expand the specified SDOperand into its two component pieces
4164 /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
4165 /// LegalizeNodes map is filled in for any results that are not expanded, the
4166 /// ExpandedNodes map is filled in for any results that are expanded, and the
4167 /// Lo/Hi values are returned.
4168 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
4169   MVT::ValueType VT = Op.getValueType();
4170   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
4171   SDNode *Node = Op.Val;
4172   assert(getTypeAction(VT) == Expand && "Not an expanded type!");
4173   assert((MVT::isInteger(VT) || VT == MVT::Vector) &&
4174          "Cannot expand FP values!");
4175   assert(((MVT::isInteger(NVT) && NVT < VT) || VT == MVT::Vector) &&
4176          "Cannot expand to FP value or to larger int value!");
4177
4178   // See if we already expanded it.
4179   std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
4180     = ExpandedNodes.find(Op);
4181   if (I != ExpandedNodes.end()) {
4182     Lo = I->second.first;
4183     Hi = I->second.second;
4184     return;
4185   }
4186
4187   switch (Node->getOpcode()) {
4188   case ISD::CopyFromReg:
4189     assert(0 && "CopyFromReg must be legal!");
4190   default:
4191     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
4192     assert(0 && "Do not know how to expand this operator!");
4193     abort();
4194   case ISD::UNDEF:
4195     Lo = DAG.getNode(ISD::UNDEF, NVT);
4196     Hi = DAG.getNode(ISD::UNDEF, NVT);
4197     break;
4198   case ISD::Constant: {
4199     uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
4200     Lo = DAG.getConstant(Cst, NVT);
4201     Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
4202     break;
4203   }
4204   case ISD::BUILD_PAIR:
4205     // Return the operands.
4206     Lo = Node->getOperand(0);
4207     Hi = Node->getOperand(1);
4208     break;
4209
4210   case ISD::SIGN_EXTEND_INREG:
4211     ExpandOp(Node->getOperand(0), Lo, Hi);
4212     // Sign extend the lo-part.
4213     Hi = DAG.getNode(ISD::SRA, NVT, Lo,
4214                      DAG.getConstant(MVT::getSizeInBits(NVT)-1,
4215                                      TLI.getShiftAmountTy()));
4216     // sext_inreg the low part if needed.
4217     Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Lo, Node->getOperand(1));
4218     break;
4219
4220   case ISD::BSWAP: {
4221     ExpandOp(Node->getOperand(0), Lo, Hi);
4222     SDOperand TempLo = DAG.getNode(ISD::BSWAP, NVT, Hi);
4223     Hi = DAG.getNode(ISD::BSWAP, NVT, Lo);
4224     Lo = TempLo;
4225     break;
4226   }
4227
4228   case ISD::CTPOP:
4229     ExpandOp(Node->getOperand(0), Lo, Hi);
4230     Lo = DAG.getNode(ISD::ADD, NVT,          // ctpop(HL) -> ctpop(H)+ctpop(L)
4231                      DAG.getNode(ISD::CTPOP, NVT, Lo),
4232                      DAG.getNode(ISD::CTPOP, NVT, Hi));
4233     Hi = DAG.getConstant(0, NVT);
4234     break;
4235
4236   case ISD::CTLZ: {
4237     // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32)
4238     ExpandOp(Node->getOperand(0), Lo, Hi);
4239     SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
4240     SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
4241     SDOperand TopNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), HLZ, BitsC,
4242                                         ISD::SETNE);
4243     SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo);
4244     LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC);
4245
4246     Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart);
4247     Hi = DAG.getConstant(0, NVT);
4248     break;
4249   }
4250
4251   case ISD::CTTZ: {
4252     // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32)
4253     ExpandOp(Node->getOperand(0), Lo, Hi);
4254     SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
4255     SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
4256     SDOperand BotNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), LTZ, BitsC,
4257                                         ISD::SETNE);
4258     SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi);
4259     HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC);
4260
4261     Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart);
4262     Hi = DAG.getConstant(0, NVT);
4263     break;
4264   }
4265
4266   case ISD::VAARG: {
4267     SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
4268     SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
4269     Lo = DAG.getVAArg(NVT, Ch, Ptr, Node->getOperand(2));
4270     Hi = DAG.getVAArg(NVT, Lo.getValue(1), Ptr, Node->getOperand(2));
4271
4272     // Remember that we legalized the chain.
4273     Hi = LegalizeOp(Hi);
4274     AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
4275     if (!TLI.isLittleEndian())
4276       std::swap(Lo, Hi);
4277     break;
4278   }
4279
4280   case ISD::LOAD: {
4281     SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
4282     SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
4283     Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
4284
4285     // Increment the pointer to the other half.
4286     unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
4287     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
4288                       getIntPtrConstant(IncrementSize));
4289     // FIXME: This creates a bogus srcvalue!
4290     Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
4291
4292     // Build a factor node to remember that this load is independent of the
4293     // other one.
4294     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
4295                                Hi.getValue(1));
4296
4297     // Remember that we legalized the chain.
4298     AddLegalizedOperand(Op.getValue(1), LegalizeOp(TF));
4299     if (!TLI.isLittleEndian())
4300       std::swap(Lo, Hi);
4301     break;
4302   }
4303   case ISD::AND:
4304   case ISD::OR:
4305   case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
4306     SDOperand LL, LH, RL, RH;
4307     ExpandOp(Node->getOperand(0), LL, LH);
4308     ExpandOp(Node->getOperand(1), RL, RH);
4309     Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
4310     Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
4311     break;
4312   }
4313   case ISD::SELECT: {
4314     SDOperand LL, LH, RL, RH;
4315     ExpandOp(Node->getOperand(1), LL, LH);
4316     ExpandOp(Node->getOperand(2), RL, RH);
4317     Lo = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), LL, RL);
4318     Hi = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), LH, RH);
4319     break;
4320   }
4321   case ISD::SELECT_CC: {
4322     SDOperand TL, TH, FL, FH;
4323     ExpandOp(Node->getOperand(2), TL, TH);
4324     ExpandOp(Node->getOperand(3), FL, FH);
4325     Lo = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
4326                      Node->getOperand(1), TL, FL, Node->getOperand(4));
4327     Hi = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
4328                      Node->getOperand(1), TH, FH, Node->getOperand(4));
4329     break;
4330   }
4331   case ISD::SEXTLOAD: {
4332     SDOperand Chain = Node->getOperand(0);
4333     SDOperand Ptr   = Node->getOperand(1);
4334     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
4335
4336     if (EVT == NVT)
4337       Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2));
4338     else
4339       Lo = DAG.getExtLoad(ISD::SEXTLOAD, NVT, Chain, Ptr, Node->getOperand(2),
4340                           EVT);
4341
4342     // Remember that we legalized the chain.
4343     AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
4344
4345     // The high part is obtained by SRA'ing all but one of the bits of the lo
4346     // part.
4347     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
4348     Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1,
4349                                                        TLI.getShiftAmountTy()));
4350     break;
4351   }
4352   case ISD::ZEXTLOAD: {
4353     SDOperand Chain = Node->getOperand(0);
4354     SDOperand Ptr   = Node->getOperand(1);
4355     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
4356
4357     if (EVT == NVT)
4358       Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2));
4359     else
4360       Lo = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Chain, Ptr, Node->getOperand(2),
4361                           EVT);
4362
4363     // Remember that we legalized the chain.
4364     AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
4365
4366     // The high part is just a zero.
4367     Hi = DAG.getConstant(0, NVT);
4368     break;
4369   }
4370   case ISD::EXTLOAD: {
4371     SDOperand Chain = Node->getOperand(0);
4372     SDOperand Ptr   = Node->getOperand(1);
4373     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
4374
4375     if (EVT == NVT)
4376       Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2));
4377     else
4378       Lo = DAG.getExtLoad(ISD::EXTLOAD, NVT, Chain, Ptr, Node->getOperand(2),
4379                           EVT);
4380
4381     // Remember that we legalized the chain.
4382     AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
4383
4384     // The high part is undefined.
4385     Hi = DAG.getNode(ISD::UNDEF, NVT);
4386     break;
4387   }
4388   case ISD::ANY_EXTEND:
4389     // The low part is any extension of the input (which degenerates to a copy).
4390     Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, Node->getOperand(0));
4391     // The high part is undefined.
4392     Hi = DAG.getNode(ISD::UNDEF, NVT);
4393     break;
4394   case ISD::SIGN_EXTEND: {
4395     // The low part is just a sign extension of the input (which degenerates to
4396     // a copy).
4397     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, Node->getOperand(0));
4398
4399     // The high part is obtained by SRA'ing all but one of the bits of the lo
4400     // part.
4401     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
4402     Hi = DAG.getNode(ISD::SRA, NVT, Lo,
4403                      DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
4404     break;
4405   }
4406   case ISD::ZERO_EXTEND:
4407     // The low part is just a zero extension of the input (which degenerates to
4408     // a copy).
4409     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, Node->getOperand(0));
4410
4411     // The high part is just a zero.
4412     Hi = DAG.getConstant(0, NVT);
4413     break;
4414
4415   case ISD::BIT_CONVERT: {
4416     SDOperand Tmp = ExpandBIT_CONVERT(Node->getValueType(0),
4417                                       Node->getOperand(0));
4418     ExpandOp(Tmp, Lo, Hi);
4419     break;
4420   }
4421
4422   case ISD::READCYCLECOUNTER:
4423     assert(TLI.getOperationAction(ISD::READCYCLECOUNTER, VT) ==
4424                  TargetLowering::Custom &&
4425            "Must custom expand ReadCycleCounter");
4426     Lo = TLI.LowerOperation(Op, DAG);
4427     assert(Lo.Val && "Node must be custom expanded!");
4428     Hi = Lo.getValue(1);
4429     AddLegalizedOperand(SDOperand(Node, 1), // Remember we legalized the chain.
4430                         LegalizeOp(Lo.getValue(2)));
4431     break;
4432
4433     // These operators cannot be expanded directly, emit them as calls to
4434     // library functions.
4435   case ISD::FP_TO_SINT:
4436     if (TLI.getOperationAction(ISD::FP_TO_SINT, VT) == TargetLowering::Custom) {
4437       SDOperand Op;
4438       switch (getTypeAction(Node->getOperand(0).getValueType())) {
4439       case Expand: assert(0 && "cannot expand FP!");
4440       case Legal:   Op = LegalizeOp(Node->getOperand(0)); break;
4441       case Promote: Op = PromoteOp (Node->getOperand(0)); break;
4442       }
4443
4444       Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_SINT, VT, Op), DAG);
4445
4446       // Now that the custom expander is done, expand the result, which is still
4447       // VT.
4448       if (Op.Val) {
4449         ExpandOp(Op, Lo, Hi);
4450         break;
4451       }
4452     }
4453
4454     if (Node->getOperand(0).getValueType() == MVT::f32)
4455       Lo = ExpandLibCall("__fixsfdi", Node, Hi);
4456     else
4457       Lo = ExpandLibCall("__fixdfdi", Node, Hi);
4458     break;
4459
4460   case ISD::FP_TO_UINT:
4461     if (TLI.getOperationAction(ISD::FP_TO_UINT, VT) == TargetLowering::Custom) {
4462       SDOperand Op;
4463       switch (getTypeAction(Node->getOperand(0).getValueType())) {
4464         case Expand: assert(0 && "cannot expand FP!");
4465         case Legal:   Op = LegalizeOp(Node->getOperand(0)); break;
4466         case Promote: Op = PromoteOp (Node->getOperand(0)); break;
4467       }
4468
4469       Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_UINT, VT, Op), DAG);
4470
4471       // Now that the custom expander is done, expand the result.
4472       if (Op.Val) {
4473         ExpandOp(Op, Lo, Hi);
4474         break;
4475       }
4476     }
4477
4478     if (Node->getOperand(0).getValueType() == MVT::f32)
4479       Lo = ExpandLibCall("__fixunssfdi", Node, Hi);
4480     else
4481       Lo = ExpandLibCall("__fixunsdfdi", Node, Hi);
4482     break;
4483
4484   case ISD::SHL: {
4485     // If the target wants custom lowering, do so.
4486     SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
4487     if (TLI.getOperationAction(ISD::SHL, VT) == TargetLowering::Custom) {
4488       SDOperand Op = DAG.getNode(ISD::SHL, VT, Node->getOperand(0), ShiftAmt);
4489       Op = TLI.LowerOperation(Op, DAG);
4490       if (Op.Val) {
4491         // Now that the custom expander is done, expand the result, which is
4492         // still VT.
4493         ExpandOp(Op, Lo, Hi);
4494         break;
4495       }
4496     }
4497
4498     // If we can emit an efficient shift operation, do so now.
4499     if (ExpandShift(ISD::SHL, Node->getOperand(0), ShiftAmt, Lo, Hi))
4500       break;
4501
4502     // If this target supports SHL_PARTS, use it.
4503     TargetLowering::LegalizeAction Action =
4504       TLI.getOperationAction(ISD::SHL_PARTS, NVT);
4505     if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
4506         Action == TargetLowering::Custom) {
4507       ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
4508       break;
4509     }
4510
4511     // Otherwise, emit a libcall.
4512     Lo = ExpandLibCall("__ashldi3", Node, Hi);
4513     break;
4514   }
4515
4516   case ISD::SRA: {
4517     // If the target wants custom lowering, do so.
4518     SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
4519     if (TLI.getOperationAction(ISD::SRA, VT) == TargetLowering::Custom) {
4520       SDOperand Op = DAG.getNode(ISD::SRA, VT, Node->getOperand(0), ShiftAmt);
4521       Op = TLI.LowerOperation(Op, DAG);
4522       if (Op.Val) {
4523         // Now that the custom expander is done, expand the result, which is
4524         // still VT.
4525         ExpandOp(Op, Lo, Hi);
4526         break;
4527       }
4528     }
4529
4530     // If we can emit an efficient shift operation, do so now.
4531     if (ExpandShift(ISD::SRA, Node->getOperand(0), ShiftAmt, Lo, Hi))
4532       break;
4533
4534     // If this target supports SRA_PARTS, use it.
4535     TargetLowering::LegalizeAction Action =
4536       TLI.getOperationAction(ISD::SRA_PARTS, NVT);
4537     if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
4538         Action == TargetLowering::Custom) {
4539       ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
4540       break;
4541     }
4542
4543     // Otherwise, emit a libcall.
4544     Lo = ExpandLibCall("__ashrdi3", Node, Hi);
4545     break;
4546   }
4547
4548   case ISD::SRL: {
4549     // If the target wants custom lowering, do so.
4550     SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
4551     if (TLI.getOperationAction(ISD::SRL, VT) == TargetLowering::Custom) {
4552       SDOperand Op = DAG.getNode(ISD::SRL, VT, Node->getOperand(0), ShiftAmt);
4553       Op = TLI.LowerOperation(Op, DAG);
4554       if (Op.Val) {
4555         // Now that the custom expander is done, expand the result, which is
4556         // still VT.
4557         ExpandOp(Op, Lo, Hi);
4558         break;
4559       }
4560     }
4561
4562     // If we can emit an efficient shift operation, do so now.
4563     if (ExpandShift(ISD::SRL, Node->getOperand(0), ShiftAmt, Lo, Hi))
4564       break;
4565
4566     // If this target supports SRL_PARTS, use it.
4567     TargetLowering::LegalizeAction Action =
4568       TLI.getOperationAction(ISD::SRL_PARTS, NVT);
4569     if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
4570         Action == TargetLowering::Custom) {
4571       ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
4572       break;
4573     }
4574
4575     // Otherwise, emit a libcall.
4576     Lo = ExpandLibCall("__lshrdi3", Node, Hi);
4577     break;
4578   }
4579
4580   case ISD::ADD:
4581   case ISD::SUB: {
4582     // If the target wants to custom expand this, let them.
4583     if (TLI.getOperationAction(Node->getOpcode(), VT) ==
4584             TargetLowering::Custom) {
4585       Op = TLI.LowerOperation(Op, DAG);
4586       if (Op.Val) {
4587         ExpandOp(Op, Lo, Hi);
4588         break;
4589       }
4590     }
4591
4592     // Expand the subcomponents.
4593     SDOperand LHSL, LHSH, RHSL, RHSH;
4594     ExpandOp(Node->getOperand(0), LHSL, LHSH);
4595     ExpandOp(Node->getOperand(1), RHSL, RHSH);
4596     std::vector<MVT::ValueType> VTs;
4597     std::vector<SDOperand> LoOps, HiOps;
4598     VTs.push_back(LHSL.getValueType());
4599     VTs.push_back(MVT::Flag);
4600     LoOps.push_back(LHSL);
4601     LoOps.push_back(RHSL);
4602     HiOps.push_back(LHSH);
4603     HiOps.push_back(RHSH);
4604     if (Node->getOpcode() == ISD::ADD) {
4605       Lo = DAG.getNode(ISD::ADDC, VTs, LoOps);
4606       HiOps.push_back(Lo.getValue(1));
4607       Hi = DAG.getNode(ISD::ADDE, VTs, HiOps);
4608     } else {
4609       Lo = DAG.getNode(ISD::SUBC, VTs, LoOps);
4610       HiOps.push_back(Lo.getValue(1));
4611       Hi = DAG.getNode(ISD::SUBE, VTs, HiOps);
4612     }
4613     break;
4614   }
4615   case ISD::MUL: {
4616     if (TLI.isOperationLegal(ISD::MULHU, NVT)) {
4617       SDOperand LL, LH, RL, RH;
4618       ExpandOp(Node->getOperand(0), LL, LH);
4619       ExpandOp(Node->getOperand(1), RL, RH);
4620       unsigned SH = MVT::getSizeInBits(RH.getValueType())-1;
4621       // MULHS implicitly sign extends its inputs.  Check to see if ExpandOp
4622       // extended the sign bit of the low half through the upper half, and if so
4623       // emit a MULHS instead of the alternate sequence that is valid for any
4624       // i64 x i64 multiply.
4625       if (TLI.isOperationLegal(ISD::MULHS, NVT) &&
4626           // is RH an extension of the sign bit of RL?
4627           RH.getOpcode() == ISD::SRA && RH.getOperand(0) == RL &&
4628           RH.getOperand(1).getOpcode() == ISD::Constant &&
4629           cast<ConstantSDNode>(RH.getOperand(1))->getValue() == SH &&
4630           // is LH an extension of the sign bit of LL?
4631           LH.getOpcode() == ISD::SRA && LH.getOperand(0) == LL &&
4632           LH.getOperand(1).getOpcode() == ISD::Constant &&
4633           cast<ConstantSDNode>(LH.getOperand(1))->getValue() == SH) {
4634         Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL);
4635       } else {
4636         Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
4637         RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
4638         LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
4639         Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
4640         Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
4641       }
4642       Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
4643     } else {
4644       Lo = ExpandLibCall("__muldi3" , Node, Hi);
4645     }
4646     break;
4647   }
4648   case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break;
4649   case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break;
4650   case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break;
4651   case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break;
4652   }
4653
4654   // Make sure the resultant values have been legalized themselves, unless this
4655   // is a type that requires multi-step expansion.
4656   if (getTypeAction(NVT) != Expand && NVT != MVT::isVoid) {
4657     Lo = LegalizeOp(Lo);
4658     Hi = LegalizeOp(Hi);
4659   }
4660
4661   // Remember in a map if the values will be reused later.
4662   bool isNew =
4663     ExpandedNodes.insert(std::make_pair(Op, std::make_pair(Lo, Hi))).second;
4664   assert(isNew && "Value already expanded?!?");
4665 }
4666
4667 /// SplitVectorOp - Given an operand of MVT::Vector type, break it down into
4668 /// two smaller values of MVT::Vector type.
4669 void SelectionDAGLegalize::SplitVectorOp(SDOperand Op, SDOperand &Lo,
4670                                          SDOperand &Hi) {
4671   assert(Op.getValueType() == MVT::Vector && "Cannot split non-vector type!");
4672   SDNode *Node = Op.Val;
4673   unsigned NumElements = cast<ConstantSDNode>(*(Node->op_end()-2))->getValue();
4674   assert(NumElements > 1 && "Cannot split a single element vector!");
4675   unsigned NewNumElts = NumElements/2;
4676   SDOperand NewNumEltsNode = DAG.getConstant(NewNumElts, MVT::i32);
4677   SDOperand TypeNode = *(Node->op_end()-1);
4678
4679   // See if we already split it.
4680   std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
4681     = SplitNodes.find(Op);
4682   if (I != SplitNodes.end()) {
4683     Lo = I->second.first;
4684     Hi = I->second.second;
4685     return;
4686   }
4687
4688   switch (Node->getOpcode()) {
4689   default: Node->dump(); assert(0 && "Unhandled operation in SplitVectorOp!");
4690   case ISD::VBUILD_VECTOR: {
4691     std::vector<SDOperand> LoOps(Node->op_begin(), Node->op_begin()+NewNumElts);
4692     LoOps.push_back(NewNumEltsNode);
4693     LoOps.push_back(TypeNode);
4694     Lo = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, LoOps);
4695
4696     std::vector<SDOperand> HiOps(Node->op_begin()+NewNumElts, Node->op_end()-2);
4697     HiOps.push_back(NewNumEltsNode);
4698     HiOps.push_back(TypeNode);
4699     Hi = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, HiOps);
4700     break;
4701   }
4702   case ISD::VADD:
4703   case ISD::VSUB:
4704   case ISD::VMUL:
4705   case ISD::VSDIV:
4706   case ISD::VUDIV:
4707   case ISD::VAND:
4708   case ISD::VOR:
4709   case ISD::VXOR: {
4710     SDOperand LL, LH, RL, RH;
4711     SplitVectorOp(Node->getOperand(0), LL, LH);
4712     SplitVectorOp(Node->getOperand(1), RL, RH);
4713
4714     Lo = DAG.getNode(Node->getOpcode(), MVT::Vector, LL, RL,
4715                      NewNumEltsNode, TypeNode);
4716     Hi = DAG.getNode(Node->getOpcode(), MVT::Vector, LH, RH,
4717                      NewNumEltsNode, TypeNode);
4718     break;
4719   }
4720   case ISD::VLOAD: {
4721     SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
4722     SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
4723     MVT::ValueType EVT = cast<VTSDNode>(TypeNode)->getVT();
4724
4725     Lo = DAG.getVecLoad(NewNumElts, EVT, Ch, Ptr, Node->getOperand(2));
4726     unsigned IncrementSize = NewNumElts * MVT::getSizeInBits(EVT)/8;
4727     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
4728                       getIntPtrConstant(IncrementSize));
4729     // FIXME: This creates a bogus srcvalue!
4730     Hi = DAG.getVecLoad(NewNumElts, EVT, Ch, Ptr, Node->getOperand(2));
4731
4732     // Build a factor node to remember that this load is independent of the
4733     // other one.
4734     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
4735                                Hi.getValue(1));
4736
4737     // Remember that we legalized the chain.
4738     AddLegalizedOperand(Op.getValue(1), LegalizeOp(TF));
4739     break;
4740   }
4741   case ISD::VBIT_CONVERT: {
4742     // We know the result is a vector.  The input may be either a vector or a
4743     // scalar value.
4744     if (Op.getOperand(0).getValueType() != MVT::Vector) {
4745       // Lower to a store/load.  FIXME: this could be improved probably.
4746       SDOperand Ptr = CreateStackTemporary(Op.getOperand(0).getValueType());
4747
4748       SDOperand St = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
4749                                  Op.getOperand(0), Ptr, DAG.getSrcValue(0));
4750       MVT::ValueType EVT = cast<VTSDNode>(TypeNode)->getVT();
4751       St = DAG.getVecLoad(NumElements, EVT, St, Ptr, DAG.getSrcValue(0));
4752       SplitVectorOp(St, Lo, Hi);
4753     } else {
4754       // If the input is a vector type, we have to either scalarize it, pack it
4755       // or convert it based on whether the input vector type is legal.
4756       SDNode *InVal = Node->getOperand(0).Val;
4757       unsigned NumElems =
4758         cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
4759       MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
4760
4761       // If the input is from a single element vector, scalarize the vector,
4762       // then treat like a scalar.
4763       if (NumElems == 1) {
4764         SDOperand Scalar = PackVectorOp(Op.getOperand(0), EVT);
4765         Scalar = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Scalar,
4766                              Op.getOperand(1), Op.getOperand(2));
4767         SplitVectorOp(Scalar, Lo, Hi);
4768       } else {
4769         // Split the input vector.
4770         SplitVectorOp(Op.getOperand(0), Lo, Hi);
4771
4772         // Convert each of the pieces now.
4773         Lo = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Lo,
4774                          NewNumEltsNode, TypeNode);
4775         Hi = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Hi,
4776                          NewNumEltsNode, TypeNode);
4777       }
4778       break;
4779     }
4780   }
4781   }
4782
4783   // Remember in a map if the values will be reused later.
4784   bool isNew =
4785     SplitNodes.insert(std::make_pair(Op, std::make_pair(Lo, Hi))).second;
4786   assert(isNew && "Value already expanded?!?");
4787 }
4788
4789
4790 /// PackVectorOp - Given an operand of MVT::Vector type, convert it into the
4791 /// equivalent operation that returns a scalar (e.g. F32) or packed value
4792 /// (e.g. MVT::V4F32).  When this is called, we know that PackedVT is the right
4793 /// type for the result.
4794 SDOperand SelectionDAGLegalize::PackVectorOp(SDOperand Op,
4795                                              MVT::ValueType NewVT) {
4796   assert(Op.getValueType() == MVT::Vector && "Bad PackVectorOp invocation!");
4797   SDNode *Node = Op.Val;
4798
4799   // See if we already packed it.
4800   std::map<SDOperand, SDOperand>::iterator I = PackedNodes.find(Op);
4801   if (I != PackedNodes.end()) return I->second;
4802
4803   SDOperand Result;
4804   switch (Node->getOpcode()) {
4805   default:
4806     Node->dump(); std::cerr << "\n";
4807     assert(0 && "Unknown vector operation in PackVectorOp!");
4808   case ISD::VADD:
4809   case ISD::VSUB:
4810   case ISD::VMUL:
4811   case ISD::VSDIV:
4812   case ISD::VUDIV:
4813   case ISD::VAND:
4814   case ISD::VOR:
4815   case ISD::VXOR:
4816     Result = DAG.getNode(getScalarizedOpcode(Node->getOpcode(), NewVT),
4817                          NewVT,
4818                          PackVectorOp(Node->getOperand(0), NewVT),
4819                          PackVectorOp(Node->getOperand(1), NewVT));
4820     break;
4821   case ISD::VLOAD: {
4822     SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
4823     SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
4824
4825     Result = DAG.getLoad(NewVT, Ch, Ptr, Node->getOperand(2));
4826
4827     // Remember that we legalized the chain.
4828     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
4829     break;
4830   }
4831   case ISD::VBUILD_VECTOR:
4832     if (Node->getOperand(0).getValueType() == NewVT) {
4833       // Returning a scalar?
4834       Result = Node->getOperand(0);
4835     } else {
4836       // Returning a BUILD_VECTOR?
4837
4838       // If all elements of the build_vector are undefs, return an undef.
4839       bool AllUndef = true;
4840       for (unsigned i = 0, e = Node->getNumOperands()-2; i != e; ++i)
4841         if (Node->getOperand(i).getOpcode() != ISD::UNDEF) {
4842           AllUndef = false;
4843           break;
4844         }
4845       if (AllUndef) {
4846         Result = DAG.getNode(ISD::UNDEF, NewVT);
4847       } else {
4848         std::vector<SDOperand> Ops(Node->op_begin(), Node->op_end()-2);
4849         Result = DAG.getNode(ISD::BUILD_VECTOR, NewVT, Ops);
4850       }
4851     }
4852     break;
4853   case ISD::VINSERT_VECTOR_ELT:
4854     if (!MVT::isVector(NewVT)) {
4855       // Returning a scalar?  Must be the inserted element.
4856       Result = Node->getOperand(1);
4857     } else {
4858       Result = DAG.getNode(ISD::INSERT_VECTOR_ELT, NewVT,
4859                            PackVectorOp(Node->getOperand(0), NewVT),
4860                            Node->getOperand(1), Node->getOperand(2));
4861     }
4862     break;
4863   case ISD::VVECTOR_SHUFFLE:
4864     if (!MVT::isVector(NewVT)) {
4865       // Returning a scalar?  Figure out if it is the LHS or RHS and return it.
4866       SDOperand EltNum = Node->getOperand(2).getOperand(0);
4867       if (cast<ConstantSDNode>(EltNum)->getValue())
4868         Result = PackVectorOp(Node->getOperand(1), NewVT);
4869       else
4870         Result = PackVectorOp(Node->getOperand(0), NewVT);
4871     } else {
4872       // Otherwise, return a VECTOR_SHUFFLE node.  First convert the index
4873       // vector from a VBUILD_VECTOR to a BUILD_VECTOR.
4874       std::vector<SDOperand> BuildVecIdx(Node->getOperand(2).Val->op_begin(),
4875                                          Node->getOperand(2).Val->op_end()-2);
4876       MVT::ValueType BVT = MVT::getIntVectorWithNumElements(BuildVecIdx.size());
4877       SDOperand BV = DAG.getNode(ISD::BUILD_VECTOR, BVT, BuildVecIdx);
4878
4879       Result = DAG.getNode(ISD::VECTOR_SHUFFLE, NewVT,
4880                            PackVectorOp(Node->getOperand(0), NewVT),
4881                            PackVectorOp(Node->getOperand(1), NewVT), BV);
4882     }
4883     break;
4884   case ISD::VBIT_CONVERT:
4885     if (Op.getOperand(0).getValueType() != MVT::Vector)
4886       Result = DAG.getNode(ISD::BIT_CONVERT, NewVT, Op.getOperand(0));
4887     else {
4888       // If the input is a vector type, we have to either scalarize it, pack it
4889       // or convert it based on whether the input vector type is legal.
4890       SDNode *InVal = Node->getOperand(0).Val;
4891       unsigned NumElems =
4892         cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
4893       MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
4894
4895       // Figure out if there is a Packed type corresponding to this Vector
4896       // type.  If so, convert to the packed type.
4897       MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
4898       if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
4899         // Turn this into a bit convert of the packed input.
4900         Result = DAG.getNode(ISD::BIT_CONVERT, NewVT,
4901                              PackVectorOp(Node->getOperand(0), TVT));
4902         break;
4903       } else if (NumElems == 1) {
4904         // Turn this into a bit convert of the scalar input.
4905         Result = DAG.getNode(ISD::BIT_CONVERT, NewVT,
4906                              PackVectorOp(Node->getOperand(0), EVT));
4907         break;
4908       } else {
4909         // FIXME: UNIMP!
4910         assert(0 && "Cast from unsupported vector type not implemented yet!");
4911       }
4912     }
4913     break;
4914   case ISD::VSELECT:
4915     Result = DAG.getNode(ISD::SELECT, NewVT, Op.getOperand(0),
4916                          PackVectorOp(Op.getOperand(1), NewVT),
4917                          PackVectorOp(Op.getOperand(2), NewVT));
4918     break;
4919   }
4920
4921   if (TLI.isTypeLegal(NewVT))
4922     Result = LegalizeOp(Result);
4923   bool isNew = PackedNodes.insert(std::make_pair(Op, Result)).second;
4924   assert(isNew && "Value already packed?");
4925   return Result;
4926 }
4927
4928
4929 // SelectionDAG::Legalize - This is the entry point for the file.
4930 //
4931 void SelectionDAG::Legalize() {
4932   if (ViewLegalizeDAGs) viewGraph();
4933
4934   /// run - This is the main entry point to this class.
4935   ///
4936   SelectionDAGLegalize(*this).LegalizeDAG();
4937 }
4938