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/MachineConstantPool.h"
  16 #include "llvm/CodeGen/MachineFunction.h"
  17 #include "llvm/CodeGen/MachineFrameInfo.h"
  18 #include "llvm/Support/MathExtras.h"
  19 #include "llvm/Target/TargetLowering.h"
  20 #include "llvm/Target/TargetData.h"
  21 #include "llvm/Target/TargetOptions.h"
  22 #include "llvm/CallingConv.h"
  23 #include "llvm/Constants.h"
  24 #include <iostream>
  25 #include <set>
  26 using namespace llvm;
  27
  28 //===----------------------------------------------------------------------===//
  29 /// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and
  30 /// hacks on it until the target machine can handle it.  This involves
  31 /// eliminating value sizes the machine cannot handle (promoting small sizes to
  32 /// large sizes or splitting up large values into small values) as well as
  33 /// eliminating operations the machine cannot handle.
  34 ///
  35 /// This code also does a small amount of optimization and recognition of idioms
  36 /// as part of its processing.  For example, if a target does not support a
  37 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
  38 /// will attempt merge setcc and brc instructions into brcc's.
  39 ///
  40 namespace {
  41 class SelectionDAGLegalize {
  42   TargetLowering &TLI;
  43   SelectionDAG &DAG;
  44
  45   /// LegalizeAction - This enum indicates what action we should take for each
  46   /// value type the can occur in the program.
  47   enum LegalizeAction {
  48     Legal,            // The target natively supports this value type.
  49     Promote,          // This should be promoted to the next larger type.
  50     Expand,           // This integer type should be broken into smaller pieces.
  51   };
  52
  53   /// ValueTypeActions - This is a bitvector that contains two bits for each
  54   /// value type, where the two bits correspond to the LegalizeAction enum.
  55   /// This can be queried with "getTypeAction(VT)".
  56   unsigned ValueTypeActions;
  57
  58   /// NeedsAnotherIteration - This is set when we expand a large integer
  59   /// operation into smaller integer operations, but the smaller operations are
  60   /// not set.  This occurs only rarely in practice, for targets that don't have
  61   /// 32-bit or larger integer registers.
  62   bool NeedsAnotherIteration;
  63
  64   /// LegalizedNodes - For nodes that are of legal width, and that have more
  65   /// than one use, this map indicates what regularized operand to use.  This
  66   /// allows us to avoid legalizing the same thing more than once.
  67   std::map<SDOperand, SDOperand> LegalizedNodes;
  68
  69   /// PromotedNodes - For nodes that are below legal width, and that have more
  70   /// than one use, this map indicates what promoted value to use.  This allows
  71   /// us to avoid promoting the same thing more than once.
  72   std::map<SDOperand, SDOperand> PromotedNodes;
  73
  74   /// ExpandedNodes - For nodes that need to be expanded, and which have more
  75   /// than one use, this map indicates which which operands are the expanded
  76   /// version of the input.  This allows us to avoid expanding the same node
  77   /// more than once.
  78   std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
  79
  80   void AddLegalizedOperand(SDOperand From, SDOperand To) {
  81     bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second;
  82     assert(isNew && "Got into the map somehow?");
  83   }
  84   void AddPromotedOperand(SDOperand From, SDOperand To) {
  85     bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second;
  86     assert(isNew && "Got into the map somehow?");
  87   }
  88
  89 public:
  90
  91   SelectionDAGLegalize(SelectionDAG &DAG);
  92
  93   /// Run - While there is still lowering to do, perform a pass over the DAG.
  94   /// Most regularization can be done in a single pass, but targets that require
  95   /// large values to be split into registers multiple times (e.g. i64 -> 4x
  96   /// i16) require iteration for these values (the first iteration will demote
  97   /// to i32, the second will demote to i16).
  98   void Run() {
  99     do {
 100       NeedsAnotherIteration = false;
 101       LegalizeDAG();
 102     } while (NeedsAnotherIteration);
 103   }
 104
 105   /// getTypeAction - Return how we should legalize values of this type, either
 106   /// it is already legal or we need to expand it into multiple registers of
 107   /// smaller integer type, or we need to promote it to a larger type.
 108   LegalizeAction getTypeAction(MVT::ValueType VT) const {
 109     return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3);
 110   }
 111
 112   /// isTypeLegal - Return true if this type is legal on this target.
 113   ///
 114   bool isTypeLegal(MVT::ValueType VT) const {
 115     return getTypeAction(VT) == Legal;
 116   }
 117
 118 private:
 119   void LegalizeDAG();
 120
 121   SDOperand LegalizeOp(SDOperand O);
 122   void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
 123   SDOperand PromoteOp(SDOperand O);
 124
 125   SDOperand ExpandLibCall(const char *Name, SDNode *Node,
 126                           SDOperand &Hi);
 127   SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy,
 128                           SDOperand Source);
 129
 130   SDOperand ExpandLegalINT_TO_FP(bool isSigned,
 131                                  SDOperand LegalOp,
 132                                  MVT::ValueType DestVT);
 133   SDOperand PromoteLegalINT_TO_FP(SDOperand LegalOp, MVT::ValueType DestVT,
 134                                   bool isSigned);
 135   SDOperand PromoteLegalFP_TO_INT(SDOperand LegalOp, MVT::ValueType DestVT,
 136                                   bool isSigned);
 137
 138   bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt,
 139                    SDOperand &Lo, SDOperand &Hi);
 140   void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt,
 141                         SDOperand &Lo, SDOperand &Hi);
 142   void ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS,
 143                      SDOperand &Lo, SDOperand &Hi);
 144
 145   void SpliceCallInto(const SDOperand &CallResult, SDNode *OutChain);
 146
 147   SDOperand getIntPtrConstant(uint64_t Val) {
 148     return DAG.getConstant(Val, TLI.getPointerTy());
 149   }
 150 };
 151 }
 152
 153
 154 SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag)
 155   : TLI(dag.getTargetLoweringInfo()), DAG(dag),
 156     ValueTypeActions(TLI.getValueTypeActions()) {
 157   assert(MVT::LAST_VALUETYPE <= 16 &&
 158          "Too many value types for ValueTypeActions to hold!");
 159 }
 160
 161 /// ExpandLegalINT_TO_FP - This function is responsible for legalizing a
 162 /// INT_TO_FP operation of the specified operand when the target requests that
 163 /// we expand it.  At this point, we know that the result and operand types are
 164 /// legal for the target.
 165 SDOperand SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned,
 166                                                      SDOperand Op0,
 167                                                      MVT::ValueType DestVT) {
 168   if (Op0.getValueType() == MVT::i32) {
 169     // simple 32-bit [signed|unsigned] integer to float/double expansion
 170
 171     // get the stack frame index of a 8 byte buffer
 172     MachineFunction &MF = DAG.getMachineFunction();
 173     int SSFI = MF.getFrameInfo()->CreateStackObject(8, 8);
 174     // get address of 8 byte buffer
 175     SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
 176     // word offset constant for Hi/Lo address computation
 177     SDOperand WordOff = DAG.getConstant(sizeof(int), TLI.getPointerTy());
 178     // set up Hi and Lo (into buffer) address based on endian
 179     SDOperand Hi, Lo;
 180     if (TLI.isLittleEndian()) {
 181       Hi = DAG.getNode(ISD::ADD, TLI.getPointerTy(), StackSlot, WordOff);
 182       Lo = StackSlot;
 183     } else {
 184       Hi = StackSlot;
 185       Lo = DAG.getNode(ISD::ADD, TLI.getPointerTy(), StackSlot, WordOff);
 186     }
 187     // if signed map to unsigned space
 188     SDOperand Op0Mapped;
 189     if (isSigned) {
 190       // constant used to invert sign bit (signed to unsigned mapping)
 191       SDOperand SignBit = DAG.getConstant(0x80000000u, MVT::i32);
 192       Op0Mapped = DAG.getNode(ISD::XOR, MVT::i32, Op0, SignBit);
 193     } else {
 194       Op0Mapped = Op0;
 195     }
 196     // store the lo of the constructed double - based on integer input
 197     SDOperand Store1 = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
 198                                    Op0Mapped, Lo, DAG.getSrcValue(NULL));
 199     // initial hi portion of constructed double
 200     SDOperand InitialHi = DAG.getConstant(0x43300000u, MVT::i32);
 201     // store the hi of the constructed double - biased exponent
 202     SDOperand Store2 = DAG.getNode(ISD::STORE, MVT::Other, Store1,
 203                                    InitialHi, Hi, DAG.getSrcValue(NULL));
 204     // load the constructed double
 205     SDOperand Load = DAG.getLoad(MVT::f64, Store2, StackSlot,
 206                                DAG.getSrcValue(NULL));
 207     // FP constant to bias correct the final result
 208     SDOperand Bias = DAG.getConstantFP(isSigned ?
 209                                             BitsToDouble(0x4330000080000000ULL)
 210                                           : BitsToDouble(0x4330000000000000ULL),
 211                                      MVT::f64);
 212     // subtract the bias
 213     SDOperand Sub = DAG.getNode(ISD::SUB, MVT::f64, Load, Bias);
 214     // final result
 215     SDOperand Result;
 216     // handle final rounding
 217     if (DestVT == MVT::f64) {
 218       // do nothing
 219       Result = Sub;
 220     } else {
 221      // if f32 then cast to f32
 222       Result = DAG.getNode(ISD::FP_ROUND, MVT::f32, Sub);
 223     }
 224     NeedsAnotherIteration = true;
 225     return Result;
 226   }
 227   assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet");
 228   SDOperand Tmp1 = DAG.getNode(ISD::SINT_TO_FP, DestVT, Op0);
 229
 230   SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Op0,
 231                                    DAG.getConstant(0, Op0.getValueType()),
 232                                    ISD::SETLT);
 233   SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
 234   SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
 235                                     SignSet, Four, Zero);
 236
 237   // If the sign bit of the integer is set, the large number will be treated
 238   // as a negative number.  To counteract this, the dynamic code adds an
 239   // offset depending on the data type.
 240   uint64_t FF;
 241   switch (Op0.getValueType()) {
 242   default: assert(0 && "Unsupported integer type!");
 243   case MVT::i8 : FF = 0x43800000ULL; break;  // 2^8  (as a float)
 244   case MVT::i16: FF = 0x47800000ULL; break;  // 2^16 (as a float)
 245   case MVT::i32: FF = 0x4F800000ULL; break;  // 2^32 (as a float)
 246   case MVT::i64: FF = 0x5F800000ULL; break;  // 2^64 (as a float)
 247   }
 248   if (TLI.isLittleEndian()) FF <<= 32;
 249   static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
 250
 251   MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
 252   SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(FudgeFactor),
 253                                         TLI.getPointerTy());
 254   CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
 255   SDOperand FudgeInReg;
 256   if (DestVT == MVT::f32)
 257     FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
 258                              DAG.getSrcValue(NULL));
 259   else {
 260     assert(DestVT == MVT::f64 && "Unexpected conversion");
 261     FudgeInReg = LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, MVT::f64,
 262                                            DAG.getEntryNode(), CPIdx,
 263                                            DAG.getSrcValue(NULL), MVT::f32));
 264   }
 265
 266   NeedsAnotherIteration = true;
 267   return DAG.getNode(ISD::ADD, DestVT, Tmp1, FudgeInReg);
 268 }
 269
 270 /// PromoteLegalINT_TO_FP - This function is responsible for legalizing a
 271 /// *INT_TO_FP operation of the specified operand when the target requests that
 272 /// we promote it.  At this point, we know that the result and operand types are
 273 /// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP
 274 /// operation that takes a larger input.
 275 SDOperand SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDOperand LegalOp,
 276                                                       MVT::ValueType DestVT,
 277                                                       bool isSigned) {
 278   // First step, figure out the appropriate *INT_TO_FP operation to use.
 279   MVT::ValueType NewInTy = LegalOp.getValueType();
 280
 281   unsigned OpToUse = 0;
 282
 283   // Scan for the appropriate larger type to use.
 284   while (1) {
 285     NewInTy = (MVT::ValueType)(NewInTy+1);
 286     assert(MVT::isInteger(NewInTy) && "Ran out of possibilities!");
 287
 288     // If the target supports SINT_TO_FP of this type, use it.
 289     switch (TLI.getOperationAction(ISD::SINT_TO_FP, NewInTy)) {
 290       default: break;
 291       case TargetLowering::Legal:
 292         if (!TLI.hasNativeSupportFor(NewInTy))
 293           break;  // Can't use this datatype.
 294         // FALL THROUGH.
 295       case TargetLowering::Custom:
 296         OpToUse = ISD::SINT_TO_FP;
 297         break;
 298     }
 299     if (OpToUse) break;
 300     if (isSigned) continue;
 301
 302     // If the target supports UINT_TO_FP of this type, use it.
 303     switch (TLI.getOperationAction(ISD::UINT_TO_FP, NewInTy)) {
 304       default: break;
 305       case TargetLowering::Legal:
 306         if (!TLI.hasNativeSupportFor(NewInTy))
 307           break;  // Can't use this datatype.
 308         // FALL THROUGH.
 309       case TargetLowering::Custom:
 310         OpToUse = ISD::UINT_TO_FP;
 311         break;
 312     }
 313     if (OpToUse) break;
 314
 315     // Otherwise, try a larger type.
 316   }
 317
 318   // Make sure to legalize any nodes we create here in the next pass.
 319   NeedsAnotherIteration = true;
 320
 321   // Okay, we found the operation and type to use.  Zero extend our input to the
 322   // desired type then run the operation on it.
 323   return DAG.getNode(OpToUse, DestVT,
 324                      DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND,
 325                                  NewInTy, LegalOp));
 326 }
 327
 328 /// PromoteLegalFP_TO_INT - This function is responsible for legalizing a
 329 /// FP_TO_*INT operation of the specified operand when the target requests that
 330 /// we promote it.  At this point, we know that the result and operand types are
 331 /// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT
 332 /// operation that returns a larger result.
 333 SDOperand SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDOperand LegalOp,
 334                                                       MVT::ValueType DestVT,
 335                                                       bool isSigned) {
 336   // First step, figure out the appropriate FP_TO*INT operation to use.
 337   MVT::ValueType NewOutTy = DestVT;
 338
 339   unsigned OpToUse = 0;
 340
 341   // Scan for the appropriate larger type to use.
 342   while (1) {
 343     NewOutTy = (MVT::ValueType)(NewOutTy+1);
 344     assert(MVT::isInteger(NewOutTy) && "Ran out of possibilities!");
 345
 346     // If the target supports FP_TO_SINT returning this type, use it.
 347     switch (TLI.getOperationAction(ISD::FP_TO_SINT, NewOutTy)) {
 348     default: break;
 349     case TargetLowering::Legal:
 350       if (!TLI.hasNativeSupportFor(NewOutTy))
 351         break;  // Can't use this datatype.
 352       // FALL THROUGH.
 353     case TargetLowering::Custom:
 354       OpToUse = ISD::FP_TO_SINT;
 355       break;
 356     }
 357     if (OpToUse) break;
 358
 359     // If the target supports FP_TO_UINT of this type, use it.
 360     switch (TLI.getOperationAction(ISD::FP_TO_UINT, NewOutTy)) {
 361     default: break;
 362     case TargetLowering::Legal:
 363       if (!TLI.hasNativeSupportFor(NewOutTy))
 364         break;  // Can't use this datatype.
 365       // FALL THROUGH.
 366     case TargetLowering::Custom:
 367       OpToUse = ISD::FP_TO_UINT;
 368       break;
 369     }
 370     if (OpToUse) break;
 371
 372     // Otherwise, try a larger type.
 373   }
 374
 375   // Make sure to legalize any nodes we create here in the next pass.
 376   NeedsAnotherIteration = true;
 377
 378   // Okay, we found the operation and type to use.  Truncate the result of the
 379   // extended FP_TO_*INT operation to the desired size.
 380   return DAG.getNode(ISD::TRUNCATE, DestVT,
 381                      DAG.getNode(OpToUse, NewOutTy, LegalOp));
 382 }
 383
 384
 385 void SelectionDAGLegalize::LegalizeDAG() {
 386   SDOperand OldRoot = DAG.getRoot();
 387   SDOperand NewRoot = LegalizeOp(OldRoot);
 388   DAG.setRoot(NewRoot);
 389
 390   ExpandedNodes.clear();
 391   LegalizedNodes.clear();
 392   PromotedNodes.clear();
 393
 394   // Remove dead nodes now.
 395   DAG.RemoveDeadNodes(OldRoot.Val);
 396 }
 397
 398 SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 399   assert(getTypeAction(Op.getValueType()) == Legal &&
 400          "Caller should expand or promote operands that are not legal!");
 401   SDNode *Node = Op.Val;
 402
 403   // If this operation defines any values that cannot be represented in a
 404   // register on this target, make sure to expand or promote them.
 405   if (Node->getNumValues() > 1) {
 406     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 407       switch (getTypeAction(Node->getValueType(i))) {
 408       case Legal: break;  // Nothing to do.
 409       case Expand: {
 410         SDOperand T1, T2;
 411         ExpandOp(Op.getValue(i), T1, T2);
 412         assert(LegalizedNodes.count(Op) &&
 413                "Expansion didn't add legal operands!");
 414         return LegalizedNodes[Op];
 415       }
 416       case Promote:
 417         PromoteOp(Op.getValue(i));
 418         assert(LegalizedNodes.count(Op) &&
 419                "Expansion didn't add legal operands!");
 420         return LegalizedNodes[Op];
 421       }
 422   }
 423
 424   // Note that LegalizeOp may be reentered even from single-use nodes, which
 425   // means that we always must cache transformed nodes.
 426   std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
 427   if (I != LegalizedNodes.end()) return I->second;
 428
 429   SDOperand Tmp1, Tmp2, Tmp3, Tmp4;
 430
 431   SDOperand Result = Op;
 432
 433   switch (Node->getOpcode()) {
 434   default:
 435     if (Node->getOpcode() >= ISD::BUILTIN_OP_END) {
 436       // If this is a target node, legalize it by legalizing the operands then
 437       // passing it through.
 438       std::vector<SDOperand> Ops;
 439       bool Changed = false;
 440       for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
 441         Ops.push_back(LegalizeOp(Node->getOperand(i)));
 442         Changed = Changed || Node->getOperand(i) != Ops.back();
 443       }
 444       if (Changed)
 445         if (Node->getNumValues() == 1)
 446           Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops);
 447         else {
 448           std::vector<MVT::ValueType> VTs(Node->value_begin(),
 449                                           Node->value_end());
 450           Result = DAG.getNode(Node->getOpcode(), VTs, Ops);
 451         }
 452
 453       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 454         AddLegalizedOperand(Op.getValue(i), Result.getValue(i));
 455       return Result.getValue(Op.ResNo);
 456     }
 457     // Otherwise this is an unhandled builtin node.  splat.
 458     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 459     assert(0 && "Do not know how to legalize this operator!");
 460     abort();
 461   case ISD::EntryToken:
 462   case ISD::FrameIndex:
 463   case ISD::GlobalAddress:
 464   case ISD::ExternalSymbol:
 465   case ISD::ConstantPool:           // Nothing to do.
 466     assert(getTypeAction(Node->getValueType(0)) == Legal &&
 467            "This must be legal!");
 468     break;
 469   case ISD::CopyFromReg:
 470     Tmp1 = LegalizeOp(Node->getOperand(0));
 471     if (Tmp1 != Node->getOperand(0))
 472       Result = DAG.getCopyFromReg(Tmp1,
 473                             cast<RegisterSDNode>(Node->getOperand(1))->getReg(),
 474                                   Node->getValueType(0));
 475     else
 476       Result = Op.getValue(0);
 477
 478     // Since CopyFromReg produces two values, make sure to remember that we
 479     // legalized both of them.
 480     AddLegalizedOperand(Op.getValue(0), Result);
 481     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
 482     return Result.getValue(Op.ResNo);
 483   case ISD::ImplicitDef:
 484     Tmp1 = LegalizeOp(Node->getOperand(0));
 485     if (Tmp1 != Node->getOperand(0))
 486       Result = DAG.getNode(ISD::ImplicitDef, MVT::Other,
 487                            Tmp1, Node->getOperand(1));
 488     break;
 489   case ISD::UNDEF: {
 490     MVT::ValueType VT = Op.getValueType();
 491     switch (TLI.getOperationAction(ISD::UNDEF, VT)) {
 492     default: assert(0 && "This action is not supported yet!");
 493     case TargetLowering::Expand:
 494     case TargetLowering::Promote:
 495       if (MVT::isInteger(VT))
 496         Result = DAG.getConstant(0, VT);
 497       else if (MVT::isFloatingPoint(VT))
 498         Result = DAG.getConstantFP(0, VT);
 499       else
 500         assert(0 && "Unknown value type!");
 501       break;
 502     case TargetLowering::Legal:
 503       break;
 504     }
 505     break;
 506   }
 507   case ISD::Constant:
 508     // We know we don't need to expand constants here, constants only have one
 509     // value and we check that it is fine above.
 510
 511     // FIXME: Maybe we should handle things like targets that don't support full
 512     // 32-bit immediates?
 513     break;
 514   case ISD::ConstantFP: {
 515     // Spill FP immediates to the constant pool if the target cannot directly
 516     // codegen them.  Targets often have some immediate values that can be
 517     // efficiently generated into an FP register without a load.  We explicitly
 518     // leave these constants as ConstantFP nodes for the target to deal with.
 519
 520     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
 521
 522     // Check to see if this FP immediate is already legal.
 523     bool isLegal = false;
 524     for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
 525            E = TLI.legal_fpimm_end(); I != E; ++I)
 526       if (CFP->isExactlyValue(*I)) {
 527         isLegal = true;
 528         break;
 529       }
 530
 531     if (!isLegal) {
 532       // Otherwise we need to spill the constant to memory.
 533       MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
 534
 535       bool Extend = false;
 536
 537       // If a FP immediate is precise when represented as a float, we put it
 538       // into the constant pool as a float, even if it's is statically typed
 539       // as a double.
 540       MVT::ValueType VT = CFP->getValueType(0);
 541       bool isDouble = VT == MVT::f64;
 542       ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
 543                                              Type::FloatTy, CFP->getValue());
 544       if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) &&
 545           // Only do this if the target has a native EXTLOAD instruction from
 546           // f32.
 547           TLI.getOperationAction(ISD::EXTLOAD,
 548                                  MVT::f32) == TargetLowering::Legal) {
 549         LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
 550         VT = MVT::f32;
 551         Extend = true;
 552       }
 553
 554       SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC),
 555                                             TLI.getPointerTy());
 556       if (Extend) {
 557         Result = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
 558                                 CPIdx, DAG.getSrcValue(NULL), MVT::f32);
 559       } else {
 560         Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx,
 561                              DAG.getSrcValue(NULL));
 562       }
 563     }
 564     break;
 565   }
 566   case ISD::TokenFactor: {
 567     std::vector<SDOperand> Ops;
 568     bool Changed = false;
 569     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
 570       SDOperand Op = Node->getOperand(i);
 571       // Fold single-use TokenFactor nodes into this token factor as we go.
 572       // FIXME: This is something that the DAGCombiner should do!!
 573       if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) {
 574         Changed = true;
 575         for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j)
 576           Ops.push_back(LegalizeOp(Op.getOperand(j)));
 577       } else {
 578         Ops.push_back(LegalizeOp(Op));  // Legalize the operands
 579         Changed |= Ops[i] != Op;
 580       }
 581     }
 582     if (Changed)
 583       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops);
 584     break;
 585   }
 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+)
 591     Tmp2 = Node->getOperand(0);
 592     if (Tmp1 != Tmp2) {
 593       Node->setAdjCallChain(Tmp1);
 594
 595       // If moving the operand from pointing to Tmp2 dropped its use count to 1,
 596       // this will cause the maps used to memoize results to get confused.
 597       // Create and add a dummy use, just to increase its use count.  This will
 598       // be removed at the end of legalize when dead nodes are removed.
 599       if (Tmp2.Val->hasOneUse())
 600         DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp2,
 601                     DAG.getConstant(0, MVT::i32));
 602     }
 603     // Note that we do not create new CALLSEQ_DOWN/UP nodes here.  These
 604     // nodes are treated specially and are mutated in place.  This makes the dag
 605     // legalization process more efficient and also makes libcall insertion
 606     // easier.
 607     break;
 608   case ISD::DYNAMIC_STACKALLOC:
 609     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 610     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
 611     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
 612     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 613         Tmp3 != Node->getOperand(2)) {
 614       std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end());
 615       std::vector<SDOperand> Ops;
 616       Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
 617       Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, Ops);
 618     } else
 619       Result = Op.getValue(0);
 620
 621     // Since this op produces two values, make sure to remember that we
 622     // legalized both of them.
 623     AddLegalizedOperand(SDOperand(Node, 0), Result);
 624     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 625     return Result.getValue(Op.ResNo);
 626
 627   case ISD::TAILCALL:
 628   case ISD::CALL: {
 629     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 630     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
 631
 632     bool Changed = false;
 633     std::vector<SDOperand> Ops;
 634     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
 635       Ops.push_back(LegalizeOp(Node->getOperand(i)));
 636       Changed |= Ops.back() != Node->getOperand(i);
 637     }
 638
 639     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Changed) {
 640       std::vector<MVT::ValueType> RetTyVTs;
 641       RetTyVTs.reserve(Node->getNumValues());
 642       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 643         RetTyVTs.push_back(Node->getValueType(i));
 644       Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops,
 645                                      Node->getOpcode() == ISD::TAILCALL), 0);
 646     } else {
 647       Result = Result.getValue(0);
 648     }
 649     // Since calls produce multiple values, make sure to remember that we
 650     // legalized all of them.
 651     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 652       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
 653     return Result.getValue(Op.ResNo);
 654   }
 655   case ISD::BR:
 656     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 657     if (Tmp1 != Node->getOperand(0))
 658       Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1));
 659     break;
 660
 661   case ISD::BRCOND:
 662     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 663
 664     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 665     case Expand: assert(0 && "It's impossible to expand bools");
 666     case Legal:
 667       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
 668       break;
 669     case Promote:
 670       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
 671       break;
 672     }
 673
 674     switch (TLI.getOperationAction(ISD::BRCOND, MVT::Other)) {
 675     default: assert(0 && "This action is not supported yet!");
 676     case TargetLowering::Expand:
 677       // Expand brcond's setcc into its constituent parts and create a BR_CC
 678       // Node.
 679       if (Tmp2.getOpcode() == ISD::SETCC) {
 680         Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Tmp2.getOperand(2),
 681                              Tmp2.getOperand(0), Tmp2.getOperand(1),
 682                              Node->getOperand(2));
 683       } else {
 684         // Make sure the condition is either zero or one.  It may have been
 685         // promoted from something else.
 686         Tmp2 = DAG.getZeroExtendInReg(Tmp2, MVT::i1);
 687
 688         Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1,
 689                              DAG.getCondCode(ISD::SETNE), Tmp2,
 690                              DAG.getConstant(0, Tmp2.getValueType()),
 691                              Node->getOperand(2));
 692       }
 693       break;
 694     case TargetLowering::Legal:
 695       // Basic block destination (Op#2) is always legal.
 696       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 697         Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
 698                              Node->getOperand(2));
 699         break;
 700     }
 701     break;
 702   case ISD::BR_CC:
 703     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 704
 705     if (getTypeAction(Node->getOperand(2).getValueType()) == Legal) {
 706       Tmp2 = LegalizeOp(Node->getOperand(2));   // LHS
 707       Tmp3 = LegalizeOp(Node->getOperand(3));   // RHS
 708       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2) ||
 709           Tmp3 != Node->getOperand(3)) {
 710         Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Node->getOperand(1),
 711                              Tmp2, Tmp3, Node->getOperand(4));
 712       }
 713       break;
 714     } else {
 715       Tmp2 = LegalizeOp(DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(),
 716                                     Node->getOperand(2),  // LHS
 717                                     Node->getOperand(3),  // RHS
 718                                     Node->getOperand(1)));
 719       // If we get a SETCC back from legalizing the SETCC node we just
 720       // created, then use its LHS, RHS, and CC directly in creating a new
 721       // node.  Otherwise, select between the true and false value based on
 722       // comparing the result of the legalized with zero.
 723       if (Tmp2.getOpcode() == ISD::SETCC) {
 724         Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Tmp2.getOperand(2),
 725                              Tmp2.getOperand(0), Tmp2.getOperand(1),
 726                              Node->getOperand(4));
 727       } else {
 728         Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1,
 729                              DAG.getCondCode(ISD::SETNE),
 730                              Tmp2, DAG.getConstant(0, Tmp2.getValueType()),
 731                              Node->getOperand(4));
 732       }
 733     }
 734     break;
 735   case ISD::BRCONDTWOWAY:
 736     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 737     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 738     case Expand: assert(0 && "It's impossible to expand bools");
 739     case Legal:
 740       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
 741       break;
 742     case Promote:
 743       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
 744       break;
 745     }
 746     // If this target does not support BRCONDTWOWAY, lower it to a BRCOND/BR
 747     // pair.
 748     switch (TLI.getOperationAction(ISD::BRCONDTWOWAY, MVT::Other)) {
 749     case TargetLowering::Promote:
 750     default: assert(0 && "This action is not supported yet!");
 751     case TargetLowering::Legal:
 752       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
 753         std::vector<SDOperand> Ops;
 754         Ops.push_back(Tmp1);
 755         Ops.push_back(Tmp2);
 756         Ops.push_back(Node->getOperand(2));
 757         Ops.push_back(Node->getOperand(3));
 758         Result = DAG.getNode(ISD::BRCONDTWOWAY, MVT::Other, Ops);
 759       }
 760       break;
 761     case TargetLowering::Expand:
 762       // If BRTWOWAY_CC is legal for this target, then simply expand this node
 763       // to that.  Otherwise, skip BRTWOWAY_CC and expand directly to a
 764       // BRCOND/BR pair.
 765       if (TLI.getOperationAction(ISD::BRTWOWAY_CC, MVT::Other) ==
 766           TargetLowering::Legal) {
 767         if (Tmp2.getOpcode() == ISD::SETCC) {
 768           Result = DAG.getBR2Way_CC(Tmp1, Tmp2.getOperand(2),
 769                                     Tmp2.getOperand(0), Tmp2.getOperand(1),
 770                                     Node->getOperand(2), Node->getOperand(3));
 771         } else {
 772           Result = DAG.getBR2Way_CC(Tmp1, DAG.getCondCode(ISD::SETNE), Tmp2,
 773                                     DAG.getConstant(0, Tmp2.getValueType()),
 774                                     Node->getOperand(2), Node->getOperand(3));
 775         }
 776       } else {
 777         Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
 778                            Node->getOperand(2));
 779         Result = DAG.getNode(ISD::BR, MVT::Other, Result, Node->getOperand(3));
 780       }
 781       break;
 782     }
 783     break;
 784   case ISD::BRTWOWAY_CC:
 785     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 786     if (getTypeAction(Node->getOperand(2).getValueType()) == Legal) {
 787       Tmp2 = LegalizeOp(Node->getOperand(2));   // LHS
 788       Tmp3 = LegalizeOp(Node->getOperand(3));   // RHS
 789       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2) ||
 790           Tmp3 != Node->getOperand(3)) {
 791         Result = DAG.getBR2Way_CC(Tmp1, Node->getOperand(1), Tmp2, Tmp3,
 792                                   Node->getOperand(4), Node->getOperand(5));
 793       }
 794       break;
 795     } else {
 796       Tmp2 = LegalizeOp(DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(),
 797                                     Node->getOperand(2),  // LHS
 798                                     Node->getOperand(3),  // RHS
 799                                     Node->getOperand(1)));
 800       // If this target does not support BRTWOWAY_CC, lower it to a BRCOND/BR
 801       // pair.
 802       switch (TLI.getOperationAction(ISD::BRTWOWAY_CC, MVT::Other)) {
 803       default: assert(0 && "This action is not supported yet!");
 804       case TargetLowering::Legal:
 805         // If we get a SETCC back from legalizing the SETCC node we just
 806         // created, then use its LHS, RHS, and CC directly in creating a new
 807         // node.  Otherwise, select between the true and false value based on
 808         // comparing the result of the legalized with zero.
 809         if (Tmp2.getOpcode() == ISD::SETCC) {
 810           Result = DAG.getBR2Way_CC(Tmp1, Tmp2.getOperand(2),
 811                                     Tmp2.getOperand(0), Tmp2.getOperand(1),
 812                                     Node->getOperand(4), Node->getOperand(5));
 813         } else {
 814           Result = DAG.getBR2Way_CC(Tmp1, DAG.getCondCode(ISD::SETNE), Tmp2,
 815                                     DAG.getConstant(0, Tmp2.getValueType()),
 816                                     Node->getOperand(4), Node->getOperand(5));
 817         }
 818         break;
 819       case TargetLowering::Expand:
 820         Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
 821                              Node->getOperand(4));
 822         Result = DAG.getNode(ISD::BR, MVT::Other, Result, Node->getOperand(5));
 823         break;
 824       }
 825     }
 826     break;
 827   case ISD::LOAD:
 828     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 829     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 830
 831     if (Tmp1 != Node->getOperand(0) ||
 832         Tmp2 != Node->getOperand(1))
 833       Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2,
 834                            Node->getOperand(2));
 835     else
 836       Result = SDOperand(Node, 0);
 837
 838     // Since loads produce two values, make sure to remember that we legalized
 839     // both of them.
 840     AddLegalizedOperand(SDOperand(Node, 0), Result);
 841     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 842     return Result.getValue(Op.ResNo);
 843
 844   case ISD::EXTLOAD:
 845   case ISD::SEXTLOAD:
 846   case ISD::ZEXTLOAD: {
 847     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 848     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 849
 850     MVT::ValueType SrcVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
 851     switch (TLI.getOperationAction(Node->getOpcode(), SrcVT)) {
 852     default: assert(0 && "This action is not supported yet!");
 853     case TargetLowering::Promote:
 854       assert(SrcVT == MVT::i1 && "Can only promote EXTLOAD from i1 -> i8!");
 855       Result = DAG.getExtLoad(Node->getOpcode(), Node->getValueType(0),
 856                               Tmp1, Tmp2, Node->getOperand(2), MVT::i8);
 857       // Since loads produce two values, make sure to remember that we legalized
 858       // both of them.
 859       AddLegalizedOperand(SDOperand(Node, 0), Result);
 860       AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 861       return Result.getValue(Op.ResNo);
 862
 863     case TargetLowering::Legal:
 864       if (Tmp1 != Node->getOperand(0) ||
 865           Tmp2 != Node->getOperand(1))
 866         Result = DAG.getExtLoad(Node->getOpcode(), Node->getValueType(0),
 867                                 Tmp1, Tmp2, Node->getOperand(2), SrcVT);
 868       else
 869         Result = SDOperand(Node, 0);
 870
 871       // Since loads produce two values, make sure to remember that we legalized
 872       // both of them.
 873       AddLegalizedOperand(SDOperand(Node, 0), Result);
 874       AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 875       return Result.getValue(Op.ResNo);
 876     case TargetLowering::Expand:
 877       //f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND
 878       if (SrcVT == MVT::f32 && Node->getValueType(0) == MVT::f64) {
 879         SDOperand Load = DAG.getLoad(SrcVT, Tmp1, Tmp2, Node->getOperand(2));
 880         Result = DAG.getNode(ISD::FP_EXTEND, Node->getValueType(0), Load);
 881         if (Op.ResNo)
 882           return Load.getValue(1);
 883         return Result;
 884       }
 885       assert(Node->getOpcode() != ISD::EXTLOAD &&
 886              "EXTLOAD should always be supported!");
 887       // Turn the unsupported load into an EXTLOAD followed by an explicit
 888       // zero/sign extend inreg.
 889       Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
 890                               Tmp1, Tmp2, Node->getOperand(2), SrcVT);
 891       SDOperand ValRes;
 892       if (Node->getOpcode() == ISD::SEXTLOAD)
 893         ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
 894                              Result, DAG.getValueType(SrcVT));
 895       else
 896         ValRes = DAG.getZeroExtendInReg(Result, SrcVT);
 897       AddLegalizedOperand(SDOperand(Node, 0), ValRes);
 898       AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 899       if (Op.ResNo)
 900         return Result.getValue(1);
 901       return ValRes;
 902     }
 903     assert(0 && "Unreachable");
 904   }
 905   case ISD::EXTRACT_ELEMENT:
 906     // Get both the low and high parts.
 907     ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 908     if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
 909       Result = Tmp2;  // 1 -> Hi
 910     else
 911       Result = Tmp1;  // 0 -> Lo
 912     break;
 913
 914   case ISD::CopyToReg:
 915     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 916
 917     assert(getTypeAction(Node->getOperand(2).getValueType()) == Legal &&
 918            "Register type must be legal!");
 919     // Legalize the incoming value (must be legal).
 920     Tmp2 = LegalizeOp(Node->getOperand(2));
 921     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2))
 922       Result = DAG.getNode(ISD::CopyToReg, MVT::Other, Tmp1,
 923                            Node->getOperand(1), Tmp2);
 924     break;
 925
 926   case ISD::RET:
 927     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 928     switch (Node->getNumOperands()) {
 929     case 2:  // ret val
 930       switch (getTypeAction(Node->getOperand(1).getValueType())) {
 931       case Legal:
 932         Tmp2 = LegalizeOp(Node->getOperand(1));
 933         if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 934           Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 935         break;
 936       case Expand: {
 937         SDOperand Lo, Hi;
 938         ExpandOp(Node->getOperand(1), Lo, Hi);
 939         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
 940         break;
 941       }
 942       case Promote:
 943         Tmp2 = PromoteOp(Node->getOperand(1));
 944         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 945         break;
 946       }
 947       break;
 948     case 1:  // ret void
 949       if (Tmp1 != Node->getOperand(0))
 950         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1);
 951       break;
 952     default: { // ret <values>
 953       std::vector<SDOperand> NewValues;
 954       NewValues.push_back(Tmp1);
 955       for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
 956         switch (getTypeAction(Node->getOperand(i).getValueType())) {
 957         case Legal:
 958           NewValues.push_back(LegalizeOp(Node->getOperand(i)));
 959           break;
 960         case Expand: {
 961           SDOperand Lo, Hi;
 962           ExpandOp(Node->getOperand(i), Lo, Hi);
 963           NewValues.push_back(Lo);
 964           NewValues.push_back(Hi);
 965           break;
 966         }
 967         case Promote:
 968           assert(0 && "Can't promote multiple return value yet!");
 969         }
 970       Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
 971       break;
 972     }
 973     }
 974     break;
 975   case ISD::STORE:
 976     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 977     Tmp2 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 978
 979     // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
 980     if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){
 981       if (CFP->getValueType(0) == MVT::f32) {
 982         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 983                              DAG.getConstant(FloatToBits(CFP->getValue()),
 984                                              MVT::i32),
 985                              Tmp2,
 986                              Node->getOperand(3));
 987       } else {
 988         assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
 989         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 990                              DAG.getConstant(DoubleToBits(CFP->getValue()),
 991                                              MVT::i64),
 992                              Tmp2,
 993                              Node->getOperand(3));
 994       }
 995       Node = Result.Val;
 996     }
 997
 998     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 999     case Legal: {
1000       SDOperand Val = LegalizeOp(Node->getOperand(1));
1001       if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) ||
1002           Tmp2 != Node->getOperand(2))
1003         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2,
1004                              Node->getOperand(3));
1005       break;
1006     }
1007     case Promote:
1008       // Truncate the value and store the result.
1009       Tmp3 = PromoteOp(Node->getOperand(1));
1010       Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2,
1011                            Node->getOperand(3),
1012                           DAG.getValueType(Node->getOperand(1).getValueType()));
1013       break;
1014
1015     case Expand:
1016       SDOperand Lo, Hi;
1017       ExpandOp(Node->getOperand(1), Lo, Hi);
1018
1019       if (!TLI.isLittleEndian())
1020         std::swap(Lo, Hi);
1021
1022       Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2,
1023                        Node->getOperand(3));
1024       unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8;
1025       Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
1026                          getIntPtrConstant(IncrementSize));
1027       assert(isTypeLegal(Tmp2.getValueType()) &&
1028              "Pointers must be legal!");
1029       //Again, claiming both parts of the store came form the same Instr
1030       Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2,
1031                        Node->getOperand(3));
1032       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1033       break;
1034     }
1035     break;
1036   case ISD::PCMARKER:
1037     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1038     if (Tmp1 != Node->getOperand(0))
1039       Result = DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp1,Node->getOperand(1));
1040     break;
1041   case ISD::TRUNCSTORE:
1042     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1043     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
1044
1045     switch (getTypeAction(Node->getOperand(1).getValueType())) {
1046     case Legal:
1047       Tmp2 = LegalizeOp(Node->getOperand(1));
1048       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1049           Tmp3 != Node->getOperand(2))
1050         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3,
1051                              Node->getOperand(3), Node->getOperand(4));
1052       break;
1053     case Promote:
1054     case Expand:
1055       assert(0 && "Cannot handle illegal TRUNCSTORE yet!");
1056     }
1057     break;
1058   case ISD::SELECT:
1059     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1060     case Expand: assert(0 && "It's impossible to expand bools");
1061     case Legal:
1062       Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
1063       break;
1064     case Promote:
1065       Tmp1 = PromoteOp(Node->getOperand(0));  // Promote the condition.
1066       break;
1067     }
1068     Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
1069     Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
1070
1071     switch (TLI.getOperationAction(Node->getOpcode(), Tmp2.getValueType())) {
1072     default: assert(0 && "This action is not supported yet!");
1073     case TargetLowering::Expand:
1074       if (Tmp1.getOpcode() == ISD::SETCC) {
1075         Result = DAG.getSelectCC(Tmp1.getOperand(0), Tmp1.getOperand(1),
1076                               Tmp2, Tmp3,
1077                               cast<CondCodeSDNode>(Tmp1.getOperand(2))->get());
1078       } else {
1079         // Make sure the condition is either zero or one.  It may have been
1080         // promoted from something else.
1081         Tmp1 = DAG.getZeroExtendInReg(Tmp1, MVT::i1);
1082         Result = DAG.getSelectCC(Tmp1,
1083                                  DAG.getConstant(0, Tmp1.getValueType()),
1084                                  Tmp2, Tmp3, ISD::SETNE);
1085       }
1086       break;
1087     case TargetLowering::Legal:
1088       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1089           Tmp3 != Node->getOperand(2))
1090         Result = DAG.getNode(ISD::SELECT, Node->getValueType(0),
1091                              Tmp1, Tmp2, Tmp3);
1092       break;
1093     case TargetLowering::Promote: {
1094       MVT::ValueType NVT =
1095         TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType());
1096       unsigned ExtOp, TruncOp;
1097       if (MVT::isInteger(Tmp2.getValueType())) {
1098         ExtOp = ISD::ZERO_EXTEND;
1099         TruncOp  = ISD::TRUNCATE;
1100       } else {
1101         ExtOp = ISD::FP_EXTEND;
1102         TruncOp  = ISD::FP_ROUND;
1103       }
1104       // Promote each of the values to the new type.
1105       Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2);
1106       Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3);
1107       // Perform the larger operation, then round down.
1108       Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3);
1109       Result = DAG.getNode(TruncOp, Node->getValueType(0), Result);
1110       break;
1111     }
1112     }
1113     break;
1114   case ISD::SELECT_CC:
1115     Tmp3 = LegalizeOp(Node->getOperand(2));   // True
1116     Tmp4 = LegalizeOp(Node->getOperand(3));   // False
1117
1118     if (getTypeAction(Node->getOperand(0).getValueType()) == Legal) {
1119       Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
1120       Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
1121       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1122           Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3)) {
1123         Result = DAG.getNode(ISD::SELECT_CC, Node->getValueType(0), Tmp1, Tmp2,
1124                              Tmp3, Tmp4, Node->getOperand(4));
1125       }
1126       break;
1127     } else {
1128       Tmp1 = LegalizeOp(DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(),
1129                                     Node->getOperand(0),  // LHS
1130                                     Node->getOperand(1),  // RHS
1131                                     Node->getOperand(4)));
1132       // If we get a SETCC back from legalizing the SETCC node we just
1133       // created, then use its LHS, RHS, and CC directly in creating a new
1134       // node.  Otherwise, select between the true and false value based on
1135       // comparing the result of the legalized with zero.
1136       if (Tmp1.getOpcode() == ISD::SETCC) {
1137         Result = DAG.getNode(ISD::SELECT_CC, Tmp3.getValueType(),
1138                              Tmp1.getOperand(0), Tmp1.getOperand(1),
1139                              Tmp3, Tmp4, Tmp1.getOperand(2));
1140       } else {
1141         Result = DAG.getSelectCC(Tmp1,
1142                                  DAG.getConstant(0, Tmp1.getValueType()),
1143                                  Tmp3, Tmp4, ISD::SETNE);
1144       }
1145     }
1146     break;
1147   case ISD::SETCC:
1148     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1149     case Legal:
1150       Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
1151       Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
1152       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
1153         Result = DAG.getNode(ISD::SETCC, Node->getValueType(0), Tmp1, Tmp2,
1154                              Node->getOperand(2));
1155       break;
1156     case Promote:
1157       Tmp1 = PromoteOp(Node->getOperand(0));   // LHS
1158       Tmp2 = PromoteOp(Node->getOperand(1));   // RHS
1159
1160       // If this is an FP compare, the operands have already been extended.
1161       if (MVT::isInteger(Node->getOperand(0).getValueType())) {
1162         MVT::ValueType VT = Node->getOperand(0).getValueType();
1163         MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1164
1165         // Otherwise, we have to insert explicit sign or zero extends.  Note
1166         // that we could insert sign extends for ALL conditions, but zero extend
1167         // is cheaper on many machines (an AND instead of two shifts), so prefer
1168         // it.
1169         switch (cast<CondCodeSDNode>(Node->getOperand(2))->get()) {
1170         default: assert(0 && "Unknown integer comparison!");
1171         case ISD::SETEQ:
1172         case ISD::SETNE:
1173         case ISD::SETUGE:
1174         case ISD::SETUGT:
1175         case ISD::SETULE:
1176         case ISD::SETULT:
1177           // ALL of these operations will work if we either sign or zero extend
1178           // the operands (including the unsigned comparisons!).  Zero extend is
1179           // usually a simpler/cheaper operation, so prefer it.
1180           Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
1181           Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
1182           break;
1183         case ISD::SETGE:
1184         case ISD::SETGT:
1185         case ISD::SETLT:
1186         case ISD::SETLE:
1187           Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
1188                              DAG.getValueType(VT));
1189           Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
1190                              DAG.getValueType(VT));
1191           break;
1192         }
1193
1194       }
1195       Result = DAG.getNode(ISD::SETCC, Node->getValueType(0), Tmp1, Tmp2,
1196                            Node->getOperand(2));
1197       break;
1198     case Expand:
1199       SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
1200       ExpandOp(Node->getOperand(0), LHSLo, LHSHi);
1201       ExpandOp(Node->getOperand(1), RHSLo, RHSHi);
1202       switch (cast<CondCodeSDNode>(Node->getOperand(2))->get()) {
1203       case ISD::SETEQ:
1204       case ISD::SETNE:
1205         if (RHSLo == RHSHi)
1206           if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
1207             if (RHSCST->isAllOnesValue()) {
1208               // Comparison to -1.
1209               Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
1210               Result = DAG.getNode(ISD::SETCC, Node->getValueType(0), Tmp1,
1211                                    RHSLo, Node->getOperand(2));
1212               break;
1213             }
1214
1215         Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
1216         Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
1217         Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
1218         Result = DAG.getNode(ISD::SETCC, Node->getValueType(0), Tmp1,
1219                              DAG.getConstant(0, Tmp1.getValueType()),
1220                              Node->getOperand(2));
1221         break;
1222       default:
1223         // If this is a comparison of the sign bit, just look at the top part.
1224         // X > -1,  x < 0
1225         if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(Node->getOperand(1)))
1226           if ((cast<CondCodeSDNode>(Node->getOperand(2))->get() == ISD::SETLT &&
1227                CST->getValue() == 0) ||              // X < 0
1228               (cast<CondCodeSDNode>(Node->getOperand(2))->get() == ISD::SETGT &&
1229                (CST->isAllOnesValue())))             // X > -1
1230             return DAG.getNode(ISD::SETCC, Node->getValueType(0), LHSHi, RHSHi,
1231                                Node->getOperand(2));
1232
1233         // FIXME: This generated code sucks.
1234         ISD::CondCode LowCC;
1235         switch (cast<CondCodeSDNode>(Node->getOperand(2))->get()) {
1236         default: assert(0 && "Unknown integer setcc!");
1237         case ISD::SETLT:
1238         case ISD::SETULT: LowCC = ISD::SETULT; break;
1239         case ISD::SETGT:
1240         case ISD::SETUGT: LowCC = ISD::SETUGT; break;
1241         case ISD::SETLE:
1242         case ISD::SETULE: LowCC = ISD::SETULE; break;
1243         case ISD::SETGE:
1244         case ISD::SETUGE: LowCC = ISD::SETUGE; break;
1245         }
1246
1247         // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
1248         // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
1249         // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
1250
1251         // NOTE: on targets without efficient SELECT of bools, we can always use
1252         // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
1253         Tmp1 = DAG.getSetCC(Node->getValueType(0), LHSLo, RHSLo, LowCC);
1254         Tmp2 = DAG.getNode(ISD::SETCC, Node->getValueType(0), LHSHi, RHSHi,
1255                            Node->getOperand(2));
1256         Result = DAG.getSetCC(Node->getValueType(0), LHSHi, RHSHi, ISD::SETEQ);
1257         Result = DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
1258                              Result, Tmp1, Tmp2);
1259         break;
1260       }
1261     }
1262     break;
1263
1264   case ISD::MEMSET:
1265   case ISD::MEMCPY:
1266   case ISD::MEMMOVE: {
1267     Tmp1 = LegalizeOp(Node->getOperand(0));      // Chain
1268     Tmp2 = LegalizeOp(Node->getOperand(1));      // Pointer
1269
1270     if (Node->getOpcode() == ISD::MEMSET) {      // memset = ubyte
1271       switch (getTypeAction(Node->getOperand(2).getValueType())) {
1272       case Expand: assert(0 && "Cannot expand a byte!");
1273       case Legal:
1274         Tmp3 = LegalizeOp(Node->getOperand(2));
1275         break;
1276       case Promote:
1277         Tmp3 = PromoteOp(Node->getOperand(2));
1278         break;
1279       }
1280     } else {
1281       Tmp3 = LegalizeOp(Node->getOperand(2));    // memcpy/move = pointer,
1282     }
1283
1284     SDOperand Tmp4;
1285     switch (getTypeAction(Node->getOperand(3).getValueType())) {
1286     case Expand: {
1287       // Length is too big, just take the lo-part of the length.
1288       SDOperand HiPart;
1289       ExpandOp(Node->getOperand(3), HiPart, Tmp4);
1290       break;
1291     }
1292     case Legal:
1293       Tmp4 = LegalizeOp(Node->getOperand(3));
1294       break;
1295     case Promote:
1296       Tmp4 = PromoteOp(Node->getOperand(3));
1297       break;
1298     }
1299
1300     SDOperand Tmp5;
1301     switch (getTypeAction(Node->getOperand(4).getValueType())) {  // uint
1302     case Expand: assert(0 && "Cannot expand this yet!");
1303     case Legal:
1304       Tmp5 = LegalizeOp(Node->getOperand(4));
1305       break;
1306     case Promote:
1307       Tmp5 = PromoteOp(Node->getOperand(4));
1308       break;
1309     }
1310
1311     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
1312     default: assert(0 && "This action not implemented for this operation!");
1313     case TargetLowering::Legal:
1314       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1315           Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) ||
1316           Tmp5 != Node->getOperand(4)) {
1317         std::vector<SDOperand> Ops;
1318         Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
1319         Ops.push_back(Tmp4); Ops.push_back(Tmp5);
1320         Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
1321       }
1322       break;
1323     case TargetLowering::Expand: {
1324       // Otherwise, the target does not support this operation.  Lower the
1325       // operation to an explicit libcall as appropriate.
1326       MVT::ValueType IntPtr = TLI.getPointerTy();
1327       const Type *IntPtrTy = TLI.getTargetData().getIntPtrType();
1328       std::vector<std::pair<SDOperand, const Type*> > Args;
1329
1330       const char *FnName = 0;
1331       if (Node->getOpcode() == ISD::MEMSET) {
1332         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
1333         // Extend the ubyte argument to be an int value for the call.
1334         Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
1335         Args.push_back(std::make_pair(Tmp3, Type::IntTy));
1336         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
1337
1338         FnName = "memset";
1339       } else if (Node->getOpcode() == ISD::MEMCPY ||
1340                  Node->getOpcode() == ISD::MEMMOVE) {
1341         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
1342         Args.push_back(std::make_pair(Tmp3, IntPtrTy));
1343         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
1344         FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
1345       } else {
1346         assert(0 && "Unknown op!");
1347       }
1348
1349       std::pair<SDOperand,SDOperand> CallResult =
1350         TLI.LowerCallTo(Tmp1, Type::VoidTy, false, CallingConv::C, false,
1351                         DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
1352       Result = CallResult.second;
1353       NeedsAnotherIteration = true;
1354       break;
1355     }
1356     case TargetLowering::Custom:
1357       std::vector<SDOperand> Ops;
1358       Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
1359       Ops.push_back(Tmp4); Ops.push_back(Tmp5);
1360       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
1361       Result = TLI.LowerOperation(Result, DAG);
1362       Result = LegalizeOp(Result);
1363       break;
1364     }
1365     break;
1366   }
1367
1368   case ISD::READPORT:
1369     Tmp1 = LegalizeOp(Node->getOperand(0));
1370     Tmp2 = LegalizeOp(Node->getOperand(1));
1371
1372     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
1373       std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end());
1374       std::vector<SDOperand> Ops;
1375       Ops.push_back(Tmp1);
1376       Ops.push_back(Tmp2);
1377       Result = DAG.getNode(ISD::READPORT, VTs, Ops);
1378     } else
1379       Result = SDOperand(Node, 0);
1380     // Since these produce two values, make sure to remember that we legalized
1381     // both of them.
1382     AddLegalizedOperand(SDOperand(Node, 0), Result);
1383     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1384     return Result.getValue(Op.ResNo);
1385   case ISD::WRITEPORT:
1386     Tmp1 = LegalizeOp(Node->getOperand(0));
1387     Tmp2 = LegalizeOp(Node->getOperand(1));
1388     Tmp3 = LegalizeOp(Node->getOperand(2));
1389     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1390         Tmp3 != Node->getOperand(2))
1391       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3);
1392     break;
1393
1394   case ISD::READIO:
1395     Tmp1 = LegalizeOp(Node->getOperand(0));
1396     Tmp2 = LegalizeOp(Node->getOperand(1));
1397
1398     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1399     case TargetLowering::Custom:
1400     default: assert(0 && "This action not implemented for this operation!");
1401     case TargetLowering::Legal:
1402       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
1403         std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end());
1404         std::vector<SDOperand> Ops;
1405         Ops.push_back(Tmp1);
1406         Ops.push_back(Tmp2);
1407         Result = DAG.getNode(ISD::READPORT, VTs, Ops);
1408       } else
1409         Result = SDOperand(Node, 0);
1410       break;
1411     case TargetLowering::Expand:
1412       // Replace this with a load from memory.
1413       Result = DAG.getLoad(Node->getValueType(0), Node->getOperand(0),
1414                            Node->getOperand(1), DAG.getSrcValue(NULL));
1415       Result = LegalizeOp(Result);
1416       break;
1417     }
1418
1419     // Since these produce two values, make sure to remember that we legalized
1420     // both of them.
1421     AddLegalizedOperand(SDOperand(Node, 0), Result);
1422     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1423     return Result.getValue(Op.ResNo);
1424
1425   case ISD::WRITEIO:
1426     Tmp1 = LegalizeOp(Node->getOperand(0));
1427     Tmp2 = LegalizeOp(Node->getOperand(1));
1428     Tmp3 = LegalizeOp(Node->getOperand(2));
1429
1430     switch (TLI.getOperationAction(Node->getOpcode(),
1431                                    Node->getOperand(1).getValueType())) {
1432     case TargetLowering::Custom:
1433     default: assert(0 && "This action not implemented for this operation!");
1434     case TargetLowering::Legal:
1435       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1436           Tmp3 != Node->getOperand(2))
1437         Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3);
1438       break;
1439     case TargetLowering::Expand:
1440       // Replace this with a store to memory.
1441       Result = DAG.getNode(ISD::STORE, MVT::Other, Node->getOperand(0),
1442                            Node->getOperand(1), Node->getOperand(2),
1443                            DAG.getSrcValue(NULL));
1444       Result = LegalizeOp(Result);
1445       break;
1446     }
1447     break;
1448
1449   case ISD::ADD_PARTS:
1450   case ISD::SUB_PARTS:
1451   case ISD::SHL_PARTS:
1452   case ISD::SRA_PARTS:
1453   case ISD::SRL_PARTS: {
1454     std::vector<SDOperand> Ops;
1455     bool Changed = false;
1456     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
1457       Ops.push_back(LegalizeOp(Node->getOperand(i)));
1458       Changed |= Ops.back() != Node->getOperand(i);
1459     }
1460     if (Changed) {
1461       std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end());
1462       Result = DAG.getNode(Node->getOpcode(), VTs, Ops);
1463     }
1464
1465     // Since these produce multiple values, make sure to remember that we
1466     // legalized all of them.
1467     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
1468       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
1469     return Result.getValue(Op.ResNo);
1470   }
1471
1472     // Binary operators
1473   case ISD::ADD:
1474   case ISD::SUB:
1475   case ISD::MUL:
1476   case ISD::MULHS:
1477   case ISD::MULHU:
1478   case ISD::UDIV:
1479   case ISD::SDIV:
1480   case ISD::AND:
1481   case ISD::OR:
1482   case ISD::XOR:
1483   case ISD::SHL:
1484   case ISD::SRL:
1485   case ISD::SRA:
1486     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
1487     switch (getTypeAction(Node->getOperand(1).getValueType())) {
1488     case Expand: assert(0 && "Not possible");
1489     case Legal:
1490       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS.
1491       break;
1492     case Promote:
1493       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the RHS.
1494       break;
1495     }
1496     if (Tmp1 != Node->getOperand(0) ||
1497         Tmp2 != Node->getOperand(1))
1498       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2);
1499     break;
1500
1501   case ISD::UREM:
1502   case ISD::SREM:
1503     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
1504     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
1505     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1506     case TargetLowering::Legal:
1507       if (Tmp1 != Node->getOperand(0) ||
1508           Tmp2 != Node->getOperand(1))
1509         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
1510                              Tmp2);
1511       break;
1512     case TargetLowering::Promote:
1513     case TargetLowering::Custom:
1514       assert(0 && "Cannot promote/custom handle this yet!");
1515     case TargetLowering::Expand:
1516       if (MVT::isInteger(Node->getValueType(0))) {
1517         MVT::ValueType VT = Node->getValueType(0);
1518         unsigned Opc = (Node->getOpcode() == ISD::UREM) ? ISD::UDIV : ISD::SDIV;
1519         Result = DAG.getNode(Opc, VT, Tmp1, Tmp2);
1520         Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2);
1521         Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result);
1522       } else {
1523         // Floating point mod -> fmod libcall.
1524         const char *FnName = Node->getValueType(0) == MVT::f32 ? "fmodf":"fmod";
1525         SDOperand Dummy;
1526         Result = ExpandLibCall(FnName, Node, Dummy);
1527       }
1528       break;
1529     }
1530     break;
1531
1532   case ISD::CTPOP:
1533   case ISD::CTTZ:
1534   case ISD::CTLZ:
1535     Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
1536     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1537     case TargetLowering::Legal:
1538       if (Tmp1 != Node->getOperand(0))
1539         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1540       break;
1541     case TargetLowering::Promote: {
1542       MVT::ValueType OVT = Tmp1.getValueType();
1543       MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
1544
1545       // Zero extend the argument.
1546       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
1547       // Perform the larger operation, then subtract if needed.
1548       Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1549       switch(Node->getOpcode())
1550       {
1551       case ISD::CTPOP:
1552         Result = Tmp1;
1553         break;
1554       case ISD::CTTZ:
1555         //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
1556         Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1,
1557                             DAG.getConstant(getSizeInBits(NVT), NVT),
1558                             ISD::SETEQ);
1559         Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
1560                            DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1);
1561         break;
1562       case ISD::CTLZ:
1563         //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
1564         Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
1565                              DAG.getConstant(getSizeInBits(NVT) -
1566                                              getSizeInBits(OVT), NVT));
1567         break;
1568       }
1569       break;
1570     }
1571     case TargetLowering::Custom:
1572       assert(0 && "Cannot custom handle this yet!");
1573     case TargetLowering::Expand:
1574       switch(Node->getOpcode())
1575       {
1576       case ISD::CTPOP: {
1577         static const uint64_t mask[6] = {
1578           0x5555555555555555ULL, 0x3333333333333333ULL,
1579           0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
1580           0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
1581         };
1582         MVT::ValueType VT = Tmp1.getValueType();
1583         MVT::ValueType ShVT = TLI.getShiftAmountTy();
1584         unsigned len = getSizeInBits(VT);
1585         for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
1586           //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
1587           Tmp2 = DAG.getConstant(mask[i], VT);
1588           Tmp3 = DAG.getConstant(1ULL << i, ShVT);
1589           Tmp1 = DAG.getNode(ISD::ADD, VT,
1590                              DAG.getNode(ISD::AND, VT, Tmp1, Tmp2),
1591                              DAG.getNode(ISD::AND, VT,
1592                                          DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3),
1593                                          Tmp2));
1594         }
1595         Result = Tmp1;
1596         break;
1597       }
1598       case ISD::CTLZ: {
1599         /* for now, we do this:
1600            x = x | (x >> 1);
1601            x = x | (x >> 2);
1602            ...
1603            x = x | (x >>16);
1604            x = x | (x >>32); // for 64-bit input
1605            return popcount(~x);
1606
1607            but see also: http://www.hackersdelight.org/HDcode/nlz.cc */
1608         MVT::ValueType VT = Tmp1.getValueType();
1609         MVT::ValueType ShVT = TLI.getShiftAmountTy();
1610         unsigned len = getSizeInBits(VT);
1611         for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
1612           Tmp3 = DAG.getConstant(1ULL << i, ShVT);
1613           Tmp1 = DAG.getNode(ISD::OR, VT, Tmp1,
1614                              DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3));
1615         }
1616         Tmp3 = DAG.getNode(ISD::XOR, VT, Tmp1, DAG.getConstant(~0ULL, VT));
1617         Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3));
1618         break;
1619       }
1620       case ISD::CTTZ: {
1621         // for now, we use: { return popcount(~x & (x - 1)); }
1622         // unless the target has ctlz but not ctpop, in which case we use:
1623         // { return 32 - nlz(~x & (x-1)); }
1624         // see also http://www.hackersdelight.org/HDcode/ntz.cc
1625         MVT::ValueType VT = Tmp1.getValueType();
1626         Tmp2 = DAG.getConstant(~0ULL, VT);
1627         Tmp3 = DAG.getNode(ISD::AND, VT,
1628                            DAG.getNode(ISD::XOR, VT, Tmp1, Tmp2),
1629                            DAG.getNode(ISD::SUB, VT, Tmp1,
1630                                        DAG.getConstant(1, VT)));
1631         // If ISD::CTLZ is legal and CTPOP isn't, then do that instead
1632         if (TLI.getOperationAction(ISD::CTPOP, VT) != TargetLowering::Legal &&
1633             TLI.getOperationAction(ISD::CTLZ, VT) == TargetLowering::Legal) {
1634           Result = LegalizeOp(DAG.getNode(ISD::SUB, VT,
1635                                         DAG.getConstant(getSizeInBits(VT), VT),
1636                                         DAG.getNode(ISD::CTLZ, VT, Tmp3)));
1637         } else {
1638           Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3));
1639         }
1640         break;
1641       }
1642       default:
1643         assert(0 && "Cannot expand this yet!");
1644         break;
1645       }
1646       break;
1647     }
1648     break;
1649
1650     // Unary operators
1651   case ISD::FABS:
1652   case ISD::FNEG:
1653   case ISD::FSQRT:
1654   case ISD::FSIN:
1655   case ISD::FCOS:
1656     Tmp1 = LegalizeOp(Node->getOperand(0));
1657     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1658     case TargetLowering::Legal:
1659       if (Tmp1 != Node->getOperand(0))
1660         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1661       break;
1662     case TargetLowering::Promote:
1663     case TargetLowering::Custom:
1664       assert(0 && "Cannot promote/custom handle this yet!");
1665     case TargetLowering::Expand:
1666       switch(Node->getOpcode()) {
1667       case ISD::FNEG: {
1668         // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
1669         Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0));
1670         Result = LegalizeOp(DAG.getNode(ISD::SUB, Node->getValueType(0),
1671                                         Tmp2, Tmp1));
1672         break;
1673       }
1674       case ISD::FABS: {
1675         // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
1676         MVT::ValueType VT = Node->getValueType(0);
1677         Tmp2 = DAG.getConstantFP(0.0, VT);
1678         Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, Tmp2, ISD::SETUGT);
1679         Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1);
1680         Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3);
1681         Result = LegalizeOp(Result);
1682         break;
1683       }
1684       case ISD::FSQRT:
1685       case ISD::FSIN:
1686       case ISD::FCOS: {
1687         MVT::ValueType VT = Node->getValueType(0);
1688         const char *FnName = 0;
1689         switch(Node->getOpcode()) {
1690         case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break;
1691         case ISD::FSIN:  FnName = VT == MVT::f32 ? "sinf"  : "sin"; break;
1692         case ISD::FCOS:  FnName = VT == MVT::f32 ? "cosf"  : "cos"; break;
1693         default: assert(0 && "Unreachable!");
1694         }
1695         SDOperand Dummy;
1696         Result = ExpandLibCall(FnName, Node, Dummy);
1697         break;
1698       }
1699       default:
1700         assert(0 && "Unreachable!");
1701       }
1702       break;
1703     }
1704     break;
1705
1706     // Conversion operators.  The source and destination have different types.
1707   case ISD::SINT_TO_FP:
1708   case ISD::UINT_TO_FP: {
1709     bool isSigned = Node->getOpcode() == ISD::SINT_TO_FP;
1710     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1711     case Legal:
1712       switch (TLI.getOperationAction(Node->getOpcode(),
1713                                      Node->getOperand(0).getValueType())) {
1714       default: assert(0 && "Unknown operation action!");
1715       case TargetLowering::Expand:
1716         Result = ExpandLegalINT_TO_FP(isSigned,
1717                                       LegalizeOp(Node->getOperand(0)),
1718                                       Node->getValueType(0));
1719         AddLegalizedOperand(Op, Result);
1720         return Result;
1721       case TargetLowering::Promote:
1722         Result = PromoteLegalINT_TO_FP(LegalizeOp(Node->getOperand(0)),
1723                                        Node->getValueType(0),
1724                                        isSigned);
1725         AddLegalizedOperand(Op, Result);
1726         return Result;
1727       case TargetLowering::Legal:
1728         break;
1729       }
1730
1731       Tmp1 = LegalizeOp(Node->getOperand(0));
1732       if (Tmp1 != Node->getOperand(0))
1733         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1734       break;
1735     case Expand:
1736       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP,
1737                              Node->getValueType(0), Node->getOperand(0));
1738       break;
1739     case Promote:
1740       if (isSigned) {
1741         Result = PromoteOp(Node->getOperand(0));
1742         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1743                  Result, DAG.getValueType(Node->getOperand(0).getValueType()));
1744         Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result);
1745       } else {
1746         Result = PromoteOp(Node->getOperand(0));
1747         Result = DAG.getZeroExtendInReg(Result,
1748                                         Node->getOperand(0).getValueType());
1749         Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result);
1750       }
1751       break;
1752     }
1753     break;
1754   }
1755   case ISD::TRUNCATE:
1756     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1757     case Legal:
1758       Tmp1 = LegalizeOp(Node->getOperand(0));
1759       if (Tmp1 != Node->getOperand(0))
1760         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1761       break;
1762     case Expand:
1763       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
1764
1765       // Since the result is legal, we should just be able to truncate the low
1766       // part of the source.
1767       Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
1768       break;
1769     case Promote:
1770       Result = PromoteOp(Node->getOperand(0));
1771       Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
1772       break;
1773     }
1774     break;
1775
1776   case ISD::FP_TO_SINT:
1777   case ISD::FP_TO_UINT:
1778     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1779     case Legal:
1780       Tmp1 = LegalizeOp(Node->getOperand(0));
1781
1782       switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))){
1783       default: assert(0 && "Unknown operation action!");
1784       case TargetLowering::Expand:
1785         if (Node->getOpcode() == ISD::FP_TO_UINT) {
1786           SDOperand True, False;
1787           MVT::ValueType VT =  Node->getOperand(0).getValueType();
1788           MVT::ValueType NVT = Node->getValueType(0);
1789           unsigned ShiftAmt = MVT::getSizeInBits(Node->getValueType(0))-1;
1790           Tmp2 = DAG.getConstantFP((double)(1ULL << ShiftAmt), VT);
1791           Tmp3 = DAG.getSetCC(TLI.getSetCCResultTy(),
1792                             Node->getOperand(0), Tmp2, ISD::SETLT);
1793           True = DAG.getNode(ISD::FP_TO_SINT, NVT, Node->getOperand(0));
1794           False = DAG.getNode(ISD::FP_TO_SINT, NVT,
1795                               DAG.getNode(ISD::SUB, VT, Node->getOperand(0),
1796                                           Tmp2));
1797           False = DAG.getNode(ISD::XOR, NVT, False,
1798                               DAG.getConstant(1ULL << ShiftAmt, NVT));
1799           Result = LegalizeOp(DAG.getNode(ISD::SELECT, NVT, Tmp3, True, False));
1800           return Result;
1801         } else {
1802           assert(0 && "Do not know how to expand FP_TO_SINT yet!");
1803         }
1804         break;
1805       case TargetLowering::Promote:
1806         Result = PromoteLegalFP_TO_INT(Tmp1, Node->getValueType(0),
1807                                        Node->getOpcode() == ISD::FP_TO_SINT);
1808         AddLegalizedOperand(Op, Result);
1809         return Result;
1810       case TargetLowering::Legal:
1811         break;
1812       case TargetLowering::Custom:
1813         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1814         Result = TLI.LowerOperation(Result, DAG);
1815         AddLegalizedOperand(Op, Result);
1816         NeedsAnotherIteration = true;
1817         return Result;
1818       }
1819
1820       if (Tmp1 != Node->getOperand(0))
1821         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1822       break;
1823     case Expand:
1824       assert(0 && "Shouldn't need to expand other operators here!");
1825     case Promote:
1826       Result = PromoteOp(Node->getOperand(0));
1827       Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
1828       break;
1829     }
1830     break;
1831
1832   case ISD::ZERO_EXTEND:
1833   case ISD::SIGN_EXTEND:
1834   case ISD::FP_EXTEND:
1835   case ISD::FP_ROUND:
1836     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1837     case Legal:
1838       Tmp1 = LegalizeOp(Node->getOperand(0));
1839       if (Tmp1 != Node->getOperand(0))
1840         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1841       break;
1842     case Expand:
1843       assert(0 && "Shouldn't need to expand other operators here!");
1844
1845     case Promote:
1846       switch (Node->getOpcode()) {
1847       case ISD::ZERO_EXTEND:
1848         Result = PromoteOp(Node->getOperand(0));
1849         // NOTE: Any extend would work here...
1850         Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
1851         Result = DAG.getZeroExtendInReg(Result,
1852                                         Node->getOperand(0).getValueType());
1853         break;
1854       case ISD::SIGN_EXTEND:
1855         Result = PromoteOp(Node->getOperand(0));
1856         // NOTE: Any extend would work here...
1857         Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
1858         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1859                              Result,
1860                           DAG.getValueType(Node->getOperand(0).getValueType()));
1861         break;
1862       case ISD::FP_EXTEND:
1863         Result = PromoteOp(Node->getOperand(0));
1864         if (Result.getValueType() != Op.getValueType())
1865           // Dynamically dead while we have only 2 FP types.
1866           Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
1867         break;
1868       case ISD::FP_ROUND:
1869         Result = PromoteOp(Node->getOperand(0));
1870         Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
1871         break;
1872       }
1873     }
1874     break;
1875   case ISD::FP_ROUND_INREG:
1876   case ISD::SIGN_EXTEND_INREG: {
1877     Tmp1 = LegalizeOp(Node->getOperand(0));
1878     MVT::ValueType ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
1879
1880     // If this operation is not supported, convert it to a shl/shr or load/store
1881     // pair.
1882     switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
1883     default: assert(0 && "This action not supported for this op yet!");
1884     case TargetLowering::Legal:
1885       if (Tmp1 != Node->getOperand(0))
1886         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
1887                              DAG.getValueType(ExtraVT));
1888       break;
1889     case TargetLowering::Expand:
1890       // If this is an integer extend and shifts are supported, do that.
1891       if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
1892         // NOTE: we could fall back on load/store here too for targets without
1893         // SAR.  However, it is doubtful that any exist.
1894         unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
1895                             MVT::getSizeInBits(ExtraVT);
1896         SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy());
1897         Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
1898                              Node->getOperand(0), ShiftCst);
1899         Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
1900                              Result, ShiftCst);
1901       } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
1902         // The only way we can lower this is to turn it into a STORETRUNC,
1903         // EXTLOAD pair, targetting a temporary location (a stack slot).
1904
1905         // NOTE: there is a choice here between constantly creating new stack
1906         // slots and always reusing the same one.  We currently always create
1907         // new ones, as reuse may inhibit scheduling.
1908         const Type *Ty = MVT::getTypeForValueType(ExtraVT);
1909         unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty);
1910         unsigned Align  = TLI.getTargetData().getTypeAlignment(Ty);
1911         MachineFunction &MF = DAG.getMachineFunction();
1912         int SSFI =
1913           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
1914         SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
1915         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
1916                              Node->getOperand(0), StackSlot,
1917                              DAG.getSrcValue(NULL), DAG.getValueType(ExtraVT));
1918         Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
1919                                 Result, StackSlot, DAG.getSrcValue(NULL),
1920                                 ExtraVT);
1921       } else {
1922         assert(0 && "Unknown op");
1923       }
1924       Result = LegalizeOp(Result);
1925       break;
1926     }
1927     break;
1928   }
1929   }
1930
1931   // Note that LegalizeOp may be reentered even from single-use nodes, which
1932   // means that we always must cache transformed nodes.
1933   AddLegalizedOperand(Op, Result);
1934   return Result;
1935 }
1936
1937 /// PromoteOp - Given an operation that produces a value in an invalid type,
1938 /// promote it to compute the value into a larger type.  The produced value will
1939 /// have the correct bits for the low portion of the register, but no guarantee
1940 /// is made about the top bits: it may be zero, sign-extended, or garbage.
1941 SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
1942   MVT::ValueType VT = Op.getValueType();
1943   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1944   assert(getTypeAction(VT) == Promote &&
1945          "Caller should expand or legalize operands that are not promotable!");
1946   assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
1947          "Cannot promote to smaller type!");
1948
1949   SDOperand Tmp1, Tmp2, Tmp3;
1950
1951   SDOperand Result;
1952   SDNode *Node = Op.Val;
1953
1954   if (!Node->hasOneUse()) {
1955     std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
1956     if (I != PromotedNodes.end()) return I->second;
1957   } else {
1958     assert(!PromotedNodes.count(Op) && "Repromoted this node??");
1959   }
1960
1961   // Promotion needs an optimization step to clean up after it, and is not
1962   // careful to avoid operations the target does not support.  Make sure that
1963   // all generated operations are legalized in the next iteration.
1964   NeedsAnotherIteration = true;
1965
1966   switch (Node->getOpcode()) {
1967   case ISD::CopyFromReg:
1968     assert(0 && "CopyFromReg must be legal!");
1969   default:
1970     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
1971     assert(0 && "Do not know how to promote this operator!");
1972     abort();
1973   case ISD::UNDEF:
1974     Result = DAG.getNode(ISD::UNDEF, NVT);
1975     break;
1976   case ISD::Constant:
1977     Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
1978     assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
1979     break;
1980   case ISD::ConstantFP:
1981     Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
1982     assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
1983     break;
1984
1985   case ISD::SETCC:
1986     assert(getTypeAction(TLI.getSetCCResultTy()) == Legal &&
1987            "SetCC type is not legal??");
1988     Result = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(),Node->getOperand(0),
1989                          Node->getOperand(1), Node->getOperand(2));
1990     Result = LegalizeOp(Result);
1991     break;
1992
1993   case ISD::TRUNCATE:
1994     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1995     case Legal:
1996       Result = LegalizeOp(Node->getOperand(0));
1997       assert(Result.getValueType() >= NVT &&
1998              "This truncation doesn't make sense!");
1999       if (Result.getValueType() > NVT)    // Truncate to NVT instead of VT
2000         Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
2001       break;
2002     case Promote:
2003       // The truncation is not required, because we don't guarantee anything
2004       // about high bits anyway.
2005       Result = PromoteOp(Node->getOperand(0));
2006       break;
2007     case Expand:
2008       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
2009       // Truncate the low part of the expanded value to the result type
2010       Result = DAG.getNode(ISD::TRUNCATE, NVT, Tmp1);
2011     }
2012     break;
2013   case ISD::SIGN_EXTEND:
2014   case ISD::ZERO_EXTEND:
2015     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2016     case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
2017     case Legal:
2018       // Input is legal?  Just do extend all the way to the larger type.
2019       Result = LegalizeOp(Node->getOperand(0));
2020       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
2021       break;
2022     case Promote:
2023       // Promote the reg if it's smaller.
2024       Result = PromoteOp(Node->getOperand(0));
2025       // The high bits are not guaranteed to be anything.  Insert an extend.
2026       if (Node->getOpcode() == ISD::SIGN_EXTEND)
2027         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
2028                          DAG.getValueType(Node->getOperand(0).getValueType()));
2029       else
2030         Result = DAG.getZeroExtendInReg(Result,
2031                                         Node->getOperand(0).getValueType());
2032       break;
2033     }
2034     break;
2035
2036   case ISD::FP_EXTEND:
2037     assert(0 && "Case not implemented.  Dynamically dead with 2 FP types!");
2038   case ISD::FP_ROUND:
2039     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2040     case Expand: assert(0 && "BUG: Cannot expand FP regs!");
2041     case Promote:  assert(0 && "Unreachable with 2 FP types!");
2042     case Legal:
2043       // Input is legal?  Do an FP_ROUND_INREG.
2044       Result = LegalizeOp(Node->getOperand(0));
2045       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2046                            DAG.getValueType(VT));
2047       break;
2048     }
2049     break;
2050
2051   case ISD::SINT_TO_FP:
2052   case ISD::UINT_TO_FP:
2053     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2054     case Legal:
2055       Result = LegalizeOp(Node->getOperand(0));
2056       // No extra round required here.
2057       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
2058       break;
2059
2060     case Promote:
2061       Result = PromoteOp(Node->getOperand(0));
2062       if (Node->getOpcode() == ISD::SINT_TO_FP)
2063         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
2064                              Result,
2065                          DAG.getValueType(Node->getOperand(0).getValueType()));
2066       else
2067         Result = DAG.getZeroExtendInReg(Result,
2068                                         Node->getOperand(0).getValueType());
2069       // No extra round required here.
2070       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
2071       break;
2072     case Expand:
2073       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT,
2074                              Node->getOperand(0));
2075       // Round if we cannot tolerate excess precision.
2076       if (NoExcessFPPrecision)
2077         Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2078                              DAG.getValueType(VT));
2079       break;
2080     }
2081     break;
2082
2083   case ISD::FP_TO_SINT:
2084   case ISD::FP_TO_UINT:
2085     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2086     case Legal:
2087       Tmp1 = LegalizeOp(Node->getOperand(0));
2088       break;
2089     case Promote:
2090       // The input result is prerounded, so we don't have to do anything
2091       // special.
2092       Tmp1 = PromoteOp(Node->getOperand(0));
2093       break;
2094     case Expand:
2095       assert(0 && "not implemented");
2096     }
2097     // If we're promoting a UINT to a larger size, check to see if the new node
2098     // will be legal.  If it isn't, check to see if FP_TO_SINT is legal, since
2099     // we can use that instead.  This allows us to generate better code for
2100     // FP_TO_UINT for small destination sizes on targets where FP_TO_UINT is not
2101     // legal, such as PowerPC.
2102     if (Node->getOpcode() == ISD::FP_TO_UINT &&
2103         TargetLowering::Legal != TLI.getOperationAction(ISD::FP_TO_UINT, NVT) &&
2104         TargetLowering::Legal == TLI.getOperationAction(ISD::FP_TO_SINT, NVT)) {
2105       Result = DAG.getNode(ISD::FP_TO_SINT, NVT, Tmp1);
2106     } else {
2107       Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2108     }
2109     break;
2110
2111   case ISD::FABS:
2112   case ISD::FNEG:
2113     Tmp1 = PromoteOp(Node->getOperand(0));
2114     assert(Tmp1.getValueType() == NVT);
2115     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2116     // NOTE: we do not have to do any extra rounding here for
2117     // NoExcessFPPrecision, because we know the input will have the appropriate
2118     // precision, and these operations don't modify precision at all.
2119     break;
2120
2121   case ISD::FSQRT:
2122   case ISD::FSIN:
2123   case ISD::FCOS:
2124     Tmp1 = PromoteOp(Node->getOperand(0));
2125     assert(Tmp1.getValueType() == NVT);
2126     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2127     if(NoExcessFPPrecision)
2128       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2129                            DAG.getValueType(VT));
2130     break;
2131
2132   case ISD::AND:
2133   case ISD::OR:
2134   case ISD::XOR:
2135   case ISD::ADD:
2136   case ISD::SUB:
2137   case ISD::MUL:
2138     // The input may have strange things in the top bits of the registers, but
2139     // these operations don't care.  They may have wierd bits going out, but
2140     // that too is okay if they are integer operations.
2141     Tmp1 = PromoteOp(Node->getOperand(0));
2142     Tmp2 = PromoteOp(Node->getOperand(1));
2143     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
2144     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2145
2146     // However, if this is a floating point operation, they will give excess
2147     // precision that we may not be able to tolerate.  If we DO allow excess
2148     // precision, just leave it, otherwise excise it.
2149     // FIXME: Why would we need to round FP ops more than integer ones?
2150     //     Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
2151     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
2152       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2153                            DAG.getValueType(VT));
2154     break;
2155
2156   case ISD::SDIV:
2157   case ISD::SREM:
2158     // These operators require that their input be sign extended.
2159     Tmp1 = PromoteOp(Node->getOperand(0));
2160     Tmp2 = PromoteOp(Node->getOperand(1));
2161     if (MVT::isInteger(NVT)) {
2162       Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
2163                          DAG.getValueType(VT));
2164       Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
2165                          DAG.getValueType(VT));
2166     }
2167     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2168
2169     // Perform FP_ROUND: this is probably overly pessimistic.
2170     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
2171       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2172                            DAG.getValueType(VT));
2173     break;
2174
2175   case ISD::UDIV:
2176   case ISD::UREM:
2177     // These operators require that their input be zero extended.
2178     Tmp1 = PromoteOp(Node->getOperand(0));
2179     Tmp2 = PromoteOp(Node->getOperand(1));
2180     assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
2181     Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
2182     Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
2183     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2184     break;
2185
2186   case ISD::SHL:
2187     Tmp1 = PromoteOp(Node->getOperand(0));
2188     Tmp2 = LegalizeOp(Node->getOperand(1));
2189     Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2);
2190     break;
2191   case ISD::SRA:
2192     // The input value must be properly sign extended.
2193     Tmp1 = PromoteOp(Node->getOperand(0));
2194     Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
2195                        DAG.getValueType(VT));
2196     Tmp2 = LegalizeOp(Node->getOperand(1));
2197     Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2);
2198     break;
2199   case ISD::SRL:
2200     // The input value must be properly zero extended.
2201     Tmp1 = PromoteOp(Node->getOperand(0));
2202     Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
2203     Tmp2 = LegalizeOp(Node->getOperand(1));
2204     Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2);
2205     break;
2206   case ISD::LOAD:
2207     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
2208     Tmp2 = LegalizeOp(Node->getOperand(1));   // Legalize the pointer.
2209     // FIXME: When the DAG combiner exists, change this to use EXTLOAD!
2210     if (MVT::isInteger(NVT))
2211       Result = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Tmp1, Tmp2,
2212                               Node->getOperand(2), VT);
2213     else
2214       Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Tmp1, Tmp2,
2215                               Node->getOperand(2), VT);
2216
2217     // Remember that we legalized the chain.
2218     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
2219     break;
2220   case ISD::SELECT:
2221     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2222     case Expand: assert(0 && "It's impossible to expand bools");
2223     case Legal:
2224       Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition.
2225       break;
2226     case Promote:
2227       Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition.
2228       break;
2229     }
2230     Tmp2 = PromoteOp(Node->getOperand(1));   // Legalize the op0
2231     Tmp3 = PromoteOp(Node->getOperand(2));   // Legalize the op1
2232     Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3);
2233     break;
2234   case ISD::SELECT_CC:
2235     Tmp2 = PromoteOp(Node->getOperand(2));   // True
2236     Tmp3 = PromoteOp(Node->getOperand(3));   // False
2237     Result = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
2238                          Node->getOperand(1), Tmp2, Tmp3,
2239                          Node->getOperand(4));
2240     break;
2241   case ISD::TAILCALL:
2242   case ISD::CALL: {
2243     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2244     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
2245
2246     std::vector<SDOperand> Ops;
2247     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i)
2248       Ops.push_back(LegalizeOp(Node->getOperand(i)));
2249
2250     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
2251            "Can only promote single result calls");
2252     std::vector<MVT::ValueType> RetTyVTs;
2253     RetTyVTs.reserve(2);
2254     RetTyVTs.push_back(NVT);
2255     RetTyVTs.push_back(MVT::Other);
2256     SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops,
2257                              Node->getOpcode() == ISD::TAILCALL);
2258     Result = SDOperand(NC, 0);
2259
2260     // Insert the new chain mapping.
2261     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
2262     break;
2263   }
2264   case ISD::CTPOP:
2265   case ISD::CTTZ:
2266   case ISD::CTLZ:
2267     Tmp1 = Node->getOperand(0);
2268     //Zero extend the argument
2269     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2270     // Perform the larger operation, then subtract if needed.
2271     Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2272     switch(Node->getOpcode())
2273     {
2274     case ISD::CTPOP:
2275       Result = Tmp1;
2276       break;
2277     case ISD::CTTZ:
2278       //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
2279       Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1,
2280                           DAG.getConstant(getSizeInBits(NVT), NVT), ISD::SETEQ);
2281       Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
2282                            DAG.getConstant(getSizeInBits(VT),NVT), Tmp1);
2283       break;
2284     case ISD::CTLZ:
2285       //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
2286       Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
2287                            DAG.getConstant(getSizeInBits(NVT) -
2288                                            getSizeInBits(VT), NVT));
2289       break;
2290     }
2291     break;
2292   }
2293
2294   assert(Result.Val && "Didn't set a result!");
2295   AddPromotedOperand(Op, Result);
2296   return Result;
2297 }
2298
2299 /// ExpandAddSub - Find a clever way to expand this add operation into
2300 /// subcomponents.
2301 void SelectionDAGLegalize::
2302 ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS,
2303               SDOperand &Lo, SDOperand &Hi) {
2304   // Expand the subcomponents.
2305   SDOperand LHSL, LHSH, RHSL, RHSH;
2306   ExpandOp(LHS, LHSL, LHSH);
2307   ExpandOp(RHS, RHSL, RHSH);
2308
2309   // FIXME: this should be moved to the dag combiner someday.
2310   assert(NodeOp == ISD::ADD_PARTS || NodeOp == ISD::SUB_PARTS);
2311   if (LHSL.getValueType() == MVT::i32) {
2312     SDOperand LowEl;
2313     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(LHSL))
2314       if (C->getValue() == 0)
2315         LowEl = RHSL;
2316     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(RHSL))
2317       if (C->getValue() == 0)
2318         LowEl = LHSL;
2319     if (LowEl.Val) {
2320       // Turn this into an add/sub of the high part only.
2321       SDOperand HiEl =
2322         DAG.getNode(NodeOp == ISD::ADD_PARTS ? ISD::ADD : ISD::SUB,
2323                     LowEl.getValueType(), LHSH, RHSH);
2324       Lo = LowEl;
2325       Hi = HiEl;
2326       return;
2327     }
2328   }
2329
2330   std::vector<SDOperand> Ops;
2331   Ops.push_back(LHSL);
2332   Ops.push_back(LHSH);
2333   Ops.push_back(RHSL);
2334   Ops.push_back(RHSH);
2335
2336   std::vector<MVT::ValueType> VTs(2, LHSL.getValueType());
2337   Lo = DAG.getNode(NodeOp, VTs, Ops);
2338   Hi = Lo.getValue(1);
2339 }
2340
2341 void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp,
2342                                             SDOperand Op, SDOperand Amt,
2343                                             SDOperand &Lo, SDOperand &Hi) {
2344   // Expand the subcomponents.
2345   SDOperand LHSL, LHSH;
2346   ExpandOp(Op, LHSL, LHSH);
2347
2348   std::vector<SDOperand> Ops;
2349   Ops.push_back(LHSL);
2350   Ops.push_back(LHSH);
2351   Ops.push_back(Amt);
2352   std::vector<MVT::ValueType> VTs;
2353   VTs.push_back(LHSL.getValueType());
2354   VTs.push_back(LHSH.getValueType());
2355   VTs.push_back(Amt.getValueType());
2356   Lo = DAG.getNode(NodeOp, VTs, Ops);
2357   Hi = Lo.getValue(1);
2358 }
2359
2360
2361 /// ExpandShift - Try to find a clever way to expand this shift operation out to
2362 /// smaller elements.  If we can't find a way that is more efficient than a
2363 /// libcall on this target, return false.  Otherwise, return true with the
2364 /// low-parts expanded into Lo and Hi.
2365 bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
2366                                        SDOperand &Lo, SDOperand &Hi) {
2367   assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
2368          "This is not a shift!");
2369
2370   MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
2371   SDOperand ShAmt = LegalizeOp(Amt);
2372   MVT::ValueType ShTy = ShAmt.getValueType();
2373   unsigned VTBits = MVT::getSizeInBits(Op.getValueType());
2374   unsigned NVTBits = MVT::getSizeInBits(NVT);
2375
2376   // Handle the case when Amt is an immediate.  Other cases are currently broken
2377   // and are disabled.
2378   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) {
2379     unsigned Cst = CN->getValue();
2380     // Expand the incoming operand to be shifted, so that we have its parts
2381     SDOperand InL, InH;
2382     ExpandOp(Op, InL, InH);
2383     switch(Opc) {
2384     case ISD::SHL:
2385       if (Cst > VTBits) {
2386         Lo = DAG.getConstant(0, NVT);
2387         Hi = DAG.getConstant(0, NVT);
2388       } else if (Cst > NVTBits) {
2389         Lo = DAG.getConstant(0, NVT);
2390         Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy));
2391       } else if (Cst == NVTBits) {
2392         Lo = DAG.getConstant(0, NVT);
2393         Hi = InL;
2394       } else {
2395         Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy));
2396         Hi = DAG.getNode(ISD::OR, NVT,
2397            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)),
2398            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy)));
2399       }
2400       return true;
2401     case ISD::SRL:
2402       if (Cst > VTBits) {
2403         Lo = DAG.getConstant(0, NVT);
2404         Hi = DAG.getConstant(0, NVT);
2405       } else if (Cst > NVTBits) {
2406         Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy));
2407         Hi = DAG.getConstant(0, NVT);
2408       } else if (Cst == NVTBits) {
2409         Lo = InH;
2410         Hi = DAG.getConstant(0, NVT);
2411       } else {
2412         Lo = DAG.getNode(ISD::OR, NVT,
2413            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
2414            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
2415         Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy));
2416       }
2417       return true;
2418     case ISD::SRA:
2419       if (Cst > VTBits) {
2420         Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
2421                               DAG.getConstant(NVTBits-1, ShTy));
2422       } else if (Cst > NVTBits) {
2423         Lo = DAG.getNode(ISD::SRA, NVT, InH,
2424                            DAG.getConstant(Cst-NVTBits, ShTy));
2425         Hi = DAG.getNode(ISD::SRA, NVT, InH,
2426                               DAG.getConstant(NVTBits-1, ShTy));
2427       } else if (Cst == NVTBits) {
2428         Lo = InH;
2429         Hi = DAG.getNode(ISD::SRA, NVT, InH,
2430                               DAG.getConstant(NVTBits-1, ShTy));
2431       } else {
2432         Lo = DAG.getNode(ISD::OR, NVT,
2433            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
2434            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
2435         Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy));
2436       }
2437       return true;
2438     }
2439   }
2440   // FIXME: The following code for expanding shifts using ISD::SELECT is buggy,
2441   // so disable it for now.  Currently targets are handling this via SHL_PARTS
2442   // and friends.
2443   return false;
2444
2445   // If we have an efficient select operation (or if the selects will all fold
2446   // away), lower to some complex code, otherwise just emit the libcall.
2447   if (TLI.getOperationAction(ISD::SELECT, NVT) != TargetLowering::Legal &&
2448       !isa<ConstantSDNode>(Amt))
2449     return false;
2450
2451   SDOperand InL, InH;
2452   ExpandOp(Op, InL, InH);
2453   SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy,           // NAmt = 32-ShAmt
2454                                DAG.getConstant(NVTBits, ShTy), ShAmt);
2455
2456   // Compare the unmasked shift amount against 32.
2457   SDOperand Cond = DAG.getSetCC(TLI.getSetCCResultTy(), ShAmt,
2458                                 DAG.getConstant(NVTBits, ShTy), ISD::SETGE);
2459
2460   if (TLI.getShiftAmountFlavor() != TargetLowering::Mask) {
2461     ShAmt = DAG.getNode(ISD::AND, ShTy, ShAmt,             // ShAmt &= 31
2462                         DAG.getConstant(NVTBits-1, ShTy));
2463     NAmt  = DAG.getNode(ISD::AND, ShTy, NAmt,              // NAmt &= 31
2464                         DAG.getConstant(NVTBits-1, ShTy));
2465   }
2466
2467   if (Opc == ISD::SHL) {
2468     SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << Amt) | (Lo >> NAmt)
2469                                DAG.getNode(ISD::SHL, NVT, InH, ShAmt),
2470                                DAG.getNode(ISD::SRL, NVT, InL, NAmt));
2471     SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31
2472
2473     Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
2474     Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2);
2475   } else {
2476     SDOperand HiLoPart = DAG.getNode(ISD::SELECT, NVT,
2477                                      DAG.getSetCC(TLI.getSetCCResultTy(), NAmt,
2478                                                   DAG.getConstant(32, ShTy),
2479                                                   ISD::SETEQ),
2480                                      DAG.getConstant(0, NVT),
2481                                      DAG.getNode(ISD::SHL, NVT, InH, NAmt));
2482     SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << NAmt) | (Lo >> Amt)
2483                                HiLoPart,
2484                                DAG.getNode(ISD::SRL, NVT, InL, ShAmt));
2485     SDOperand T2 = DAG.getNode(Opc, NVT, InH, ShAmt);  // T2 = InH >> ShAmt&31
2486
2487     SDOperand HiPart;
2488     if (Opc == ISD::SRA)
2489       HiPart = DAG.getNode(ISD::SRA, NVT, InH,
2490                            DAG.getConstant(NVTBits-1, ShTy));
2491     else
2492       HiPart = DAG.getConstant(0, NVT);
2493     Lo = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
2494     Hi = DAG.getNode(ISD::SELECT, NVT, Cond, HiPart, T2);
2495   }
2496   return true;
2497 }
2498
2499 /// FindLatestCallSeqStart - Scan up the dag to find the latest (highest
2500 /// NodeDepth) node that is an CallSeqStart operation and occurs later than
2501 /// Found.
2502 static void FindLatestCallSeqStart(SDNode *Node, SDNode *&Found) {
2503   if (Node->getNodeDepth() <= Found->getNodeDepth()) return;
2504
2505   // If we found an CALLSEQ_START, we already know this node occurs later
2506   // than the Found node. Just remember this node and return.
2507   if (Node->getOpcode() == ISD::CALLSEQ_START) {
2508     Found = Node;
2509     return;
2510   }
2511
2512   // Otherwise, scan the operands of Node to see if any of them is a call.
2513   assert(Node->getNumOperands() != 0 &&
2514          "All leaves should have depth equal to the entry node!");
2515   for (unsigned i = 0, e = Node->getNumOperands()-1; i != e; ++i)
2516     FindLatestCallSeqStart(Node->getOperand(i).Val, Found);
2517
2518   // Tail recurse for the last iteration.
2519   FindLatestCallSeqStart(Node->getOperand(Node->getNumOperands()-1).Val,
2520                              Found);
2521 }
2522
2523
2524 /// FindEarliestCallSeqEnd - Scan down the dag to find the earliest (lowest
2525 /// NodeDepth) node that is an CallSeqEnd operation and occurs more recent
2526 /// than Found.
2527 static void FindEarliestCallSeqEnd(SDNode *Node, SDNode *&Found,
2528                                    std::set<SDNode*> &Visited) {
2529   if ((Found && Node->getNodeDepth() >= Found->getNodeDepth()) ||
2530       !Visited.insert(Node).second) return;
2531
2532   // If we found an CALLSEQ_END, we already know this node occurs earlier
2533   // than the Found node. Just remember this node and return.
2534   if (Node->getOpcode() == ISD::CALLSEQ_END) {
2535     Found = Node;
2536     return;
2537   }
2538
2539   // Otherwise, scan the operands of Node to see if any of them is a call.
2540   SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
2541   if (UI == E) return;
2542   for (--E; UI != E; ++UI)
2543     FindEarliestCallSeqEnd(*UI, Found, Visited);
2544
2545   // Tail recurse for the last iteration.
2546   FindEarliestCallSeqEnd(*UI, Found, Visited);
2547 }
2548
2549 /// FindCallSeqEnd - Given a chained node that is part of a call sequence,
2550 /// find the CALLSEQ_END node that terminates the call sequence.
2551 static SDNode *FindCallSeqEnd(SDNode *Node) {
2552   if (Node->getOpcode() == ISD::CALLSEQ_END)
2553     return Node;
2554   if (Node->use_empty())
2555     return 0;   // No CallSeqEnd
2556
2557   if (Node->hasOneUse())  // Simple case, only has one user to check.
2558     return FindCallSeqEnd(*Node->use_begin());
2559
2560   SDOperand TheChain(Node, Node->getNumValues()-1);
2561   if (TheChain.getValueType() != MVT::Other)
2562     TheChain = SDOperand(Node, 0);
2563   assert(TheChain.getValueType() == MVT::Other && "Is not a token chain!");
2564
2565   for (SDNode::use_iterator UI = Node->use_begin(),
2566          E = Node->use_end(); UI != E; ++UI) {
2567
2568     // Make sure to only follow users of our token chain.
2569     SDNode *User = *UI;
2570     for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
2571       if (User->getOperand(i) == TheChain)
2572         if (SDNode *Result = FindCallSeqEnd(User))
2573           return Result;
2574   }
2575   return 0;
2576 }
2577
2578 /// FindCallSeqStart - Given a chained node that is part of a call sequence,
2579 /// find the CALLSEQ_START node that initiates the call sequence.
2580 static SDNode *FindCallSeqStart(SDNode *Node) {
2581   assert(Node && "Didn't find callseq_start for a call??");
2582   if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
2583
2584   assert(Node->getOperand(0).getValueType() == MVT::Other &&
2585          "Node doesn't have a token chain argument!");
2586   return FindCallSeqStart(Node->getOperand(0).Val);
2587 }
2588
2589
2590 /// FindInputOutputChains - If we are replacing an operation with a call we need
2591 /// to find the call that occurs before and the call that occurs after it to
2592 /// properly serialize the calls in the block.  The returned operand is the
2593 /// input chain value for the new call (e.g. the entry node or the previous
2594 /// call), and OutChain is set to be the chain node to update to point to the
2595 /// end of the call chain.
2596 static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain,
2597                                        SDOperand Entry) {
2598   SDNode *LatestCallSeqStart = Entry.Val;
2599   SDNode *LatestCallSeqEnd = 0;
2600   FindLatestCallSeqStart(OpNode, LatestCallSeqStart);
2601   //std::cerr<<"Found node: "; LatestCallSeqStart->dump(); std::cerr <<"\n";
2602
2603   // It is possible that no ISD::CALLSEQ_START was found because there is no
2604   // previous call in the function.  LatestCallStackDown may in that case be
2605   // the entry node itself.  Do not attempt to find a matching CALLSEQ_END
2606   // unless LatestCallStackDown is an CALLSEQ_START.
2607   if (LatestCallSeqStart->getOpcode() == ISD::CALLSEQ_START)
2608     LatestCallSeqEnd = FindCallSeqEnd(LatestCallSeqStart);
2609   else
2610     LatestCallSeqEnd = Entry.Val;
2611   assert(LatestCallSeqEnd && "NULL return from FindCallSeqEnd");
2612
2613   // Finally, find the first call that this must come before, first we find the
2614   // CallSeqEnd that ends the call.
2615   OutChain = 0;
2616   std::set<SDNode*> Visited;
2617   FindEarliestCallSeqEnd(OpNode, OutChain, Visited);
2618
2619   // If we found one, translate from the adj up to the callseq_start.
2620   if (OutChain)
2621     OutChain = FindCallSeqStart(OutChain);
2622
2623   return SDOperand(LatestCallSeqEnd, 0);
2624 }
2625
2626 /// SpliceCallInto - Given the result chain of a libcall (CallResult), and a
2627 void SelectionDAGLegalize::SpliceCallInto(const SDOperand &CallResult,
2628                                           SDNode *OutChain) {
2629   // Nothing to splice it into?
2630   if (OutChain == 0) return;
2631
2632   assert(OutChain->getOperand(0).getValueType() == MVT::Other);
2633   //OutChain->dump();
2634
2635   // Form a token factor node merging the old inval and the new inval.
2636   SDOperand InToken = DAG.getNode(ISD::TokenFactor, MVT::Other, CallResult,
2637                                   OutChain->getOperand(0));
2638   // Change the node to refer to the new token.
2639   OutChain->setAdjCallChain(InToken);
2640 }
2641
2642
2643 // ExpandLibCall - Expand a node into a call to a libcall.  If the result value
2644 // does not fit into a register, return the lo part and set the hi part to the
2645 // by-reg argument.  If it does fit into a single register, return the result
2646 // and leave the Hi part unset.
2647 SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node,
2648                                               SDOperand &Hi) {
2649   SDNode *OutChain;
2650   SDOperand InChain = FindInputOutputChains(Node, OutChain,
2651                                             DAG.getEntryNode());
2652   if (InChain.Val == 0)
2653     InChain = DAG.getEntryNode();
2654
2655   TargetLowering::ArgListTy Args;
2656   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
2657     MVT::ValueType ArgVT = Node->getOperand(i).getValueType();
2658     const Type *ArgTy = MVT::getTypeForValueType(ArgVT);
2659     Args.push_back(std::make_pair(Node->getOperand(i), ArgTy));
2660   }
2661   SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy());
2662
2663   // Splice the libcall in wherever FindInputOutputChains tells us to.
2664   const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0));
2665   std::pair<SDOperand,SDOperand> CallInfo =
2666     TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, false,
2667                     Callee, Args, DAG);
2668   SpliceCallInto(CallInfo.second, OutChain);
2669
2670   NeedsAnotherIteration = true;
2671
2672   switch (getTypeAction(CallInfo.first.getValueType())) {
2673   default: assert(0 && "Unknown thing");
2674   case Legal:
2675     return CallInfo.first;
2676   case Promote:
2677     assert(0 && "Cannot promote this yet!");
2678   case Expand:
2679     SDOperand Lo;
2680     ExpandOp(CallInfo.first, Lo, Hi);
2681     return Lo;
2682   }
2683 }
2684
2685
2686 /// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the
2687 /// destination type is legal.
2688 SDOperand SelectionDAGLegalize::
2689 ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) {
2690   assert(getTypeAction(DestTy) == Legal && "Destination type is not legal!");
2691   assert(getTypeAction(Source.getValueType()) == Expand &&
2692          "This is not an expansion!");
2693   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
2694
2695   if (!isSigned) {
2696     assert(Source.getValueType() == MVT::i64 &&
2697            "This only works for 64-bit -> FP");
2698     // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
2699     // incoming integer is set.  To handle this, we dynamically test to see if
2700     // it is set, and, if so, add a fudge factor.
2701     SDOperand Lo, Hi;
2702     ExpandOp(Source, Lo, Hi);
2703
2704     // If this is unsigned, and not supported, first perform the conversion to
2705     // signed, then adjust the result if the sign bit is set.
2706     SDOperand SignedConv = ExpandIntToFP(true, DestTy,
2707                    DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), Lo, Hi));
2708
2709     SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi,
2710                                      DAG.getConstant(0, Hi.getValueType()),
2711                                      ISD::SETLT);
2712     SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
2713     SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
2714                                       SignSet, Four, Zero);
2715     uint64_t FF = 0x5f800000ULL;
2716     if (TLI.isLittleEndian()) FF <<= 32;
2717     static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
2718
2719     MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
2720     SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(FudgeFactor),
2721                                           TLI.getPointerTy());
2722     CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
2723     SDOperand FudgeInReg;
2724     if (DestTy == MVT::f32)
2725       FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
2726                                DAG.getSrcValue(NULL));
2727     else {
2728       assert(DestTy == MVT::f64 && "Unexpected conversion");
2729       FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
2730                                   CPIdx, DAG.getSrcValue(NULL), MVT::f32);
2731     }
2732     return DAG.getNode(ISD::ADD, DestTy, SignedConv, FudgeInReg);
2733   }
2734
2735   // Check to see if the target has a custom way to lower this.  If so, use it.
2736   switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) {
2737   default: assert(0 && "This action not implemented for this operation!");
2738   case TargetLowering::Legal:
2739   case TargetLowering::Expand:
2740     break;   // This case is handled below.
2741   case TargetLowering::Custom:
2742     Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source);
2743     return LegalizeOp(TLI.LowerOperation(Source, DAG));
2744   }
2745
2746   // Expand the source, then glue it back together for the call.  We must expand
2747   // the source in case it is shared (this pass of legalize must traverse it).
2748   SDOperand SrcLo, SrcHi;
2749   ExpandOp(Source, SrcLo, SrcHi);
2750   Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi);
2751
2752   SDNode *OutChain = 0;
2753   SDOperand InChain = FindInputOutputChains(Source.Val, OutChain,
2754                                             DAG.getEntryNode());
2755   const char *FnName = 0;
2756   if (DestTy == MVT::f32)
2757     FnName = "__floatdisf";
2758   else {
2759     assert(DestTy == MVT::f64 && "Unknown fp value type!");
2760     FnName = "__floatdidf";
2761   }
2762
2763   SDOperand Callee = DAG.getExternalSymbol(FnName, TLI.getPointerTy());
2764
2765   TargetLowering::ArgListTy Args;
2766   const Type *ArgTy = MVT::getTypeForValueType(Source.getValueType());
2767
2768   Args.push_back(std::make_pair(Source, ArgTy));
2769
2770   // We don't care about token chains for libcalls.  We just use the entry
2771   // node as our input and ignore the output chain.  This allows us to place
2772   // calls wherever we need them to satisfy data dependences.
2773   const Type *RetTy = MVT::getTypeForValueType(DestTy);
2774
2775   std::pair<SDOperand,SDOperand> CallResult =
2776     TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, true,
2777                     Callee, Args, DAG);
2778
2779   SpliceCallInto(CallResult.second, OutChain);
2780   return CallResult.first;
2781 }
2782
2783
2784
2785 /// ExpandOp - Expand the specified SDOperand into its two component pieces
2786 /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
2787 /// LegalizeNodes map is filled in for any results that are not expanded, the
2788 /// ExpandedNodes map is filled in for any results that are expanded, and the
2789 /// Lo/Hi values are returned.
2790 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
2791   MVT::ValueType VT = Op.getValueType();
2792   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
2793   SDNode *Node = Op.Val;
2794   assert(getTypeAction(VT) == Expand && "Not an expanded type!");
2795   assert(MVT::isInteger(VT) && "Cannot expand FP values!");
2796   assert(MVT::isInteger(NVT) && NVT < VT &&
2797          "Cannot expand to FP value or to larger int value!");
2798
2799   // If there is more than one use of this, see if we already expanded it.
2800   // There is no use remembering values that only have a single use, as the map
2801   // entries will never be reused.
2802   if (!Node->hasOneUse()) {
2803     std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
2804       = ExpandedNodes.find(Op);
2805     if (I != ExpandedNodes.end()) {
2806       Lo = I->second.first;
2807       Hi = I->second.second;
2808       return;
2809     }
2810   } else {
2811     assert(!ExpandedNodes.count(Op) && "Re-expanding a node!");
2812   }
2813
2814   // Expanding to multiple registers needs to perform an optimization step, and
2815   // is not careful to avoid operations the target does not support.  Make sure
2816   // that all generated operations are legalized in the next iteration.
2817   NeedsAnotherIteration = true;
2818
2819   switch (Node->getOpcode()) {
2820    case ISD::CopyFromReg:
2821       assert(0 && "CopyFromReg must be legal!");
2822    default:
2823     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
2824     assert(0 && "Do not know how to expand this operator!");
2825     abort();
2826   case ISD::UNDEF:
2827     Lo = DAG.getNode(ISD::UNDEF, NVT);
2828     Hi = DAG.getNode(ISD::UNDEF, NVT);
2829     break;
2830   case ISD::Constant: {
2831     uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
2832     Lo = DAG.getConstant(Cst, NVT);
2833     Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
2834     break;
2835   }
2836
2837   case ISD::BUILD_PAIR:
2838     // Legalize both operands.  FIXME: in the future we should handle the case
2839     // where the two elements are not legal.
2840     assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
2841     Lo = LegalizeOp(Node->getOperand(0));
2842     Hi = LegalizeOp(Node->getOperand(1));
2843     break;
2844
2845   case ISD::CTPOP:
2846     ExpandOp(Node->getOperand(0), Lo, Hi);
2847     Lo = DAG.getNode(ISD::ADD, NVT,          // ctpop(HL) -> ctpop(H)+ctpop(L)
2848                      DAG.getNode(ISD::CTPOP, NVT, Lo),
2849                      DAG.getNode(ISD::CTPOP, NVT, Hi));
2850     Hi = DAG.getConstant(0, NVT);
2851     break;
2852
2853   case ISD::CTLZ: {
2854     // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32)
2855     ExpandOp(Node->getOperand(0), Lo, Hi);
2856     SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
2857     SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
2858     SDOperand TopNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), HLZ, BitsC,
2859                                         ISD::SETNE);
2860     SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo);
2861     LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC);
2862
2863     Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart);
2864     Hi = DAG.getConstant(0, NVT);
2865     break;
2866   }
2867
2868   case ISD::CTTZ: {
2869     // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32)
2870     ExpandOp(Node->getOperand(0), Lo, Hi);
2871     SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
2872     SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
2873     SDOperand BotNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), LTZ, BitsC,
2874                                         ISD::SETNE);
2875     SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi);
2876     HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC);
2877
2878     Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart);
2879     Hi = DAG.getConstant(0, NVT);
2880     break;
2881   }
2882
2883   case ISD::LOAD: {
2884     SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
2885     SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2886     Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
2887
2888     // Increment the pointer to the other half.
2889     unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
2890     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
2891                       getIntPtrConstant(IncrementSize));
2892     //Is this safe?  declaring that the two parts of the split load
2893     //are from the same instruction?
2894     Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
2895
2896     // Build a factor node to remember that this load is independent of the
2897     // other one.
2898     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
2899                                Hi.getValue(1));
2900
2901     // Remember that we legalized the chain.
2902     AddLegalizedOperand(Op.getValue(1), TF);
2903     if (!TLI.isLittleEndian())
2904       std::swap(Lo, Hi);
2905     break;
2906   }
2907   case ISD::TAILCALL:
2908   case ISD::CALL: {
2909     SDOperand Chain  = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2910     SDOperand Callee = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
2911
2912     bool Changed = false;
2913     std::vector<SDOperand> Ops;
2914     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
2915       Ops.push_back(LegalizeOp(Node->getOperand(i)));
2916       Changed |= Ops.back() != Node->getOperand(i);
2917     }
2918
2919     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
2920            "Can only expand a call once so far, not i64 -> i16!");
2921
2922     std::vector<MVT::ValueType> RetTyVTs;
2923     RetTyVTs.reserve(3);
2924     RetTyVTs.push_back(NVT);
2925     RetTyVTs.push_back(NVT);
2926     RetTyVTs.push_back(MVT::Other);
2927     SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee, Ops,
2928                              Node->getOpcode() == ISD::TAILCALL);
2929     Lo = SDOperand(NC, 0);
2930     Hi = SDOperand(NC, 1);
2931
2932     // Insert the new chain mapping.
2933     AddLegalizedOperand(Op.getValue(1), Hi.getValue(2));
2934     break;
2935   }
2936   case ISD::AND:
2937   case ISD::OR:
2938   case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
2939     SDOperand LL, LH, RL, RH;
2940     ExpandOp(Node->getOperand(0), LL, LH);
2941     ExpandOp(Node->getOperand(1), RL, RH);
2942     Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
2943     Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
2944     break;
2945   }
2946   case ISD::SELECT: {
2947     SDOperand C, LL, LH, RL, RH;
2948
2949     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2950     case Expand: assert(0 && "It's impossible to expand bools");
2951     case Legal:
2952       C = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
2953       break;
2954     case Promote:
2955       C = PromoteOp(Node->getOperand(0));  // Promote the condition.
2956       break;
2957     }
2958     ExpandOp(Node->getOperand(1), LL, LH);
2959     ExpandOp(Node->getOperand(2), RL, RH);
2960     Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL);
2961     Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH);
2962     break;
2963   }
2964   case ISD::SELECT_CC: {
2965     SDOperand TL, TH, FL, FH;
2966     ExpandOp(Node->getOperand(2), TL, TH);
2967     ExpandOp(Node->getOperand(3), FL, FH);
2968     Lo = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
2969                      Node->getOperand(1), TL, FL, Node->getOperand(4));
2970     Hi = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
2971                      Node->getOperand(1), TH, FH, Node->getOperand(4));
2972     Lo = LegalizeOp(Lo);
2973     Hi = LegalizeOp(Hi);
2974     break;
2975   }
2976   case ISD::SIGN_EXTEND: {
2977     SDOperand In;
2978     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2979     case Expand: assert(0 && "expand-expand not implemented yet!");
2980     case Legal: In = LegalizeOp(Node->getOperand(0)); break;
2981     case Promote:
2982       In = PromoteOp(Node->getOperand(0));
2983       // Emit the appropriate sign_extend_inreg to get the value we want.
2984       In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(), In,
2985                        DAG.getValueType(Node->getOperand(0).getValueType()));
2986       break;
2987     }
2988
2989     // The low part is just a sign extension of the input (which degenerates to
2990     // a copy).
2991     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, In);
2992
2993     // The high part is obtained by SRA'ing all but one of the bits of the lo
2994     // part.
2995     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
2996     Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1,
2997                                                        TLI.getShiftAmountTy()));
2998     break;
2999   }
3000   case ISD::ZERO_EXTEND: {
3001     SDOperand In;
3002     switch (getTypeAction(Node->getOperand(0).getValueType())) {
3003     case Expand: assert(0 && "expand-expand not implemented yet!");
3004     case Legal: In = LegalizeOp(Node->getOperand(0)); break;
3005     case Promote:
3006       In = PromoteOp(Node->getOperand(0));
3007       // Emit the appropriate zero_extend_inreg to get the value we want.
3008       In = DAG.getZeroExtendInReg(In, Node->getOperand(0).getValueType());
3009       break;
3010     }
3011
3012     // The low part is just a zero extension of the input (which degenerates to
3013     // a copy).
3014     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, In);
3015
3016     // The high part is just a zero.
3017     Hi = DAG.getConstant(0, NVT);
3018     break;
3019   }
3020     // These operators cannot be expanded directly, emit them as calls to
3021     // library functions.
3022   case ISD::FP_TO_SINT:
3023     if (TLI.getOperationAction(ISD::FP_TO_SINT, VT) == TargetLowering::Custom) {
3024       SDOperand Op;
3025       switch (getTypeAction(Node->getOperand(0).getValueType())) {
3026       case Expand: assert(0 && "cannot expand FP!");
3027       case Legal: Op = LegalizeOp(Node->getOperand(0)); break;
3028       case Promote: Op = PromoteOp(Node->getOperand(0)); break;
3029       }
3030
3031       Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_SINT, VT, Op), DAG);
3032
3033       // Now that the custom expander is done, expand the result, which is still
3034       // VT.
3035       ExpandOp(Op, Lo, Hi);
3036       break;
3037     }
3038
3039     if (Node->getOperand(0).getValueType() == MVT::f32)
3040       Lo = ExpandLibCall("__fixsfdi", Node, Hi);
3041     else
3042       Lo = ExpandLibCall("__fixdfdi", Node, Hi);
3043     break;
3044
3045   case ISD::FP_TO_UINT:
3046     if (TLI.getOperationAction(ISD::FP_TO_UINT, VT) == TargetLowering::Custom) {
3047       SDOperand Op = DAG.getNode(ISD::FP_TO_UINT, VT,
3048                                  LegalizeOp(Node->getOperand(0)));
3049       // Now that the custom expander is done, expand the result, which is still
3050       // VT.
3051       ExpandOp(TLI.LowerOperation(Op, DAG), Lo, Hi);
3052       break;
3053     }
3054
3055     if (Node->getOperand(0).getValueType() == MVT::f32)
3056       Lo = ExpandLibCall("__fixunssfdi", Node, Hi);
3057     else
3058       Lo = ExpandLibCall("__fixunsdfdi", Node, Hi);
3059     break;
3060
3061   case ISD::SHL:
3062     // If we can emit an efficient shift operation, do so now.
3063     if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
3064       break;
3065
3066     // If this target supports SHL_PARTS, use it.
3067     if (TLI.getOperationAction(ISD::SHL_PARTS, NVT) == TargetLowering::Legal) {
3068       ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), Node->getOperand(1),
3069                        Lo, Hi);
3070       break;
3071     }
3072
3073     // Otherwise, emit a libcall.
3074     Lo = ExpandLibCall("__ashldi3", Node, Hi);
3075     break;
3076
3077   case ISD::SRA:
3078     // If we can emit an efficient shift operation, do so now.
3079     if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
3080       break;
3081
3082     // If this target supports SRA_PARTS, use it.
3083     if (TLI.getOperationAction(ISD::SRA_PARTS, NVT) == TargetLowering::Legal) {
3084       ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), Node->getOperand(1),
3085                        Lo, Hi);
3086       break;
3087     }
3088
3089     // Otherwise, emit a libcall.
3090     Lo = ExpandLibCall("__ashrdi3", Node, Hi);
3091     break;
3092   case ISD::SRL:
3093     // If we can emit an efficient shift operation, do so now.
3094     if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
3095       break;
3096
3097     // If this target supports SRL_PARTS, use it.
3098     if (TLI.getOperationAction(ISD::SRL_PARTS, NVT) == TargetLowering::Legal) {
3099       ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), Node->getOperand(1),
3100                        Lo, Hi);
3101       break;
3102     }
3103
3104     // Otherwise, emit a libcall.
3105     Lo = ExpandLibCall("__lshrdi3", Node, Hi);
3106     break;
3107
3108   case ISD::ADD:
3109     ExpandByParts(ISD::ADD_PARTS, Node->getOperand(0), Node->getOperand(1),
3110                   Lo, Hi);
3111     break;
3112   case ISD::SUB:
3113     ExpandByParts(ISD::SUB_PARTS, Node->getOperand(0), Node->getOperand(1),
3114                   Lo, Hi);
3115     break;
3116   case ISD::MUL: {
3117     if (TLI.getOperationAction(ISD::MULHU, NVT) == TargetLowering::Legal) {
3118       SDOperand LL, LH, RL, RH;
3119       ExpandOp(Node->getOperand(0), LL, LH);
3120       ExpandOp(Node->getOperand(1), RL, RH);
3121       Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
3122       RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
3123       LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
3124       Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
3125       Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
3126       Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
3127     } else {
3128       Lo = ExpandLibCall("__muldi3" , Node, Hi); break;
3129     }
3130     break;
3131   }
3132   case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break;
3133   case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break;
3134   case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break;
3135   case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break;
3136   }
3137
3138   // Remember in a map if the values will be reused later.
3139   if (!Node->hasOneUse()) {
3140     bool isNew = ExpandedNodes.insert(std::make_pair(Op,
3141                                             std::make_pair(Lo, Hi))).second;
3142     assert(isNew && "Value already expanded?!?");
3143   }
3144 }
3145
3146
3147 // SelectionDAG::Legalize - This is the entry point for the file.
3148 //
3149 void SelectionDAG::Legalize() {
3150   /// run - This is the main entry point to this class.
3151   ///
3152   SelectionDAGLegalize(*this).Run();
3153 }
3154