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