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