lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

   1 //===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/ADT/DenseMap.h"
  16 #include "llvm/ADT/SmallPtrSet.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/CallingConv.h"
  19 #include "llvm/CodeGen/Analysis.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  22 #include "llvm/Constants.h"
  23 #include "llvm/DataLayout.h"
  24 #include "llvm/DebugInfo.h"
  25 #include "llvm/DerivedTypes.h"
  26 #include "llvm/LLVMContext.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/MathExtras.h"
  30 #include "llvm/Support/raw_ostream.h"
  31 #include "llvm/Target/TargetFrameLowering.h"
  32 #include "llvm/Target/TargetLowering.h"
  33 #include "llvm/Target/TargetMachine.h"
  34 using namespace llvm;
  35
  36 //===----------------------------------------------------------------------===//
  37 /// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and
  38 /// hacks on it until the target machine can handle it.  This involves
  39 /// eliminating value sizes the machine cannot handle (promoting small sizes to
  40 /// large sizes or splitting up large values into small values) as well as
  41 /// eliminating operations the machine cannot handle.
  42 ///
  43 /// This code also does a small amount of optimization and recognition of idioms
  44 /// as part of its processing.  For example, if a target does not support a
  45 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
  46 /// will attempt merge setcc and brc instructions into brcc's.
  47 ///
  48 namespace {
  49 class SelectionDAGLegalize : public SelectionDAG::DAGUpdateListener {
  50   const TargetMachine &TM;
  51   const TargetLowering &TLI;
  52   SelectionDAG &DAG;
  53
  54   /// LegalizePosition - The iterator for walking through the node list.
  55   SelectionDAG::allnodes_iterator LegalizePosition;
  56
  57   /// LegalizedNodes - The set of nodes which have already been legalized.
  58   SmallPtrSet<SDNode *, 16> LegalizedNodes;
  59
  60   // Libcall insertion helpers.
  61
  62 public:
  63   explicit SelectionDAGLegalize(SelectionDAG &DAG);
  64
  65   void LegalizeDAG();
  66
  67 private:
  68   /// LegalizeOp - Legalizes the given operation.
  69   void LegalizeOp(SDNode *Node);
  70
  71   SDValue OptimizeFloatStore(StoreSDNode *ST);
  72
  73   void LegalizeLoadOps(SDNode *Node);
  74   void LegalizeStoreOps(SDNode *Node);
  75
  76   /// PerformInsertVectorEltInMemory - Some target cannot handle a variable
  77   /// insertion index for the INSERT_VECTOR_ELT instruction.  In this case, it
  78   /// is necessary to spill the vector being inserted into to memory, perform
  79   /// the insert there, and then read the result back.
  80   SDValue PerformInsertVectorEltInMemory(SDValue Vec, SDValue Val,
  81                                          SDValue Idx, DebugLoc dl);
  82   SDValue ExpandINSERT_VECTOR_ELT(SDValue Vec, SDValue Val,
  83                                   SDValue Idx, DebugLoc dl);
  84
  85   /// ShuffleWithNarrowerEltType - Return a vector shuffle operation which
  86   /// performs the same shuffe in terms of order or result bytes, but on a type
  87   /// whose vector element type is narrower than the original shuffle type.
  88   /// e.g. <v4i32> <0, 1, 0, 1> -> v8i16 <0, 1, 2, 3, 0, 1, 2, 3>
  89   SDValue ShuffleWithNarrowerEltType(EVT NVT, EVT VT, DebugLoc dl,
  90                                      SDValue N1, SDValue N2,
  91                                      ArrayRef<int> Mask) const;
  92
  93   void LegalizeSetCCCondCode(EVT VT, SDValue &LHS, SDValue &RHS, SDValue &CC,
  94                              DebugLoc dl);
  95
  96   SDValue ExpandLibCall(RTLIB::Libcall LC, SDNode *Node, bool isSigned);
  97   SDValue ExpandLibCall(RTLIB::Libcall LC, EVT RetVT, const SDValue *Ops,
  98                         unsigned NumOps, bool isSigned, DebugLoc dl);
  99
 100   std::pair<SDValue, SDValue> ExpandChainLibCall(RTLIB::Libcall LC,
 101                                                  SDNode *Node, bool isSigned);
 102   SDValue ExpandFPLibCall(SDNode *Node, RTLIB::Libcall Call_F32,
 103                           RTLIB::Libcall Call_F64, RTLIB::Libcall Call_F80,
 104                           RTLIB::Libcall Call_PPCF128);
 105   SDValue ExpandIntLibCall(SDNode *Node, bool isSigned,
 106                            RTLIB::Libcall Call_I8,
 107                            RTLIB::Libcall Call_I16,
 108                            RTLIB::Libcall Call_I32,
 109                            RTLIB::Libcall Call_I64,
 110                            RTLIB::Libcall Call_I128);
 111   void ExpandDivRemLibCall(SDNode *Node, SmallVectorImpl<SDValue> &Results);
 112
 113   SDValue EmitStackConvert(SDValue SrcOp, EVT SlotVT, EVT DestVT, DebugLoc dl);
 114   SDValue ExpandBUILD_VECTOR(SDNode *Node);
 115   SDValue ExpandSCALAR_TO_VECTOR(SDNode *Node);
 116   void ExpandDYNAMIC_STACKALLOC(SDNode *Node,
 117                                 SmallVectorImpl<SDValue> &Results);
 118   SDValue ExpandFCOPYSIGN(SDNode *Node);
 119   SDValue ExpandLegalINT_TO_FP(bool isSigned, SDValue LegalOp, EVT DestVT,
 120                                DebugLoc dl);
 121   SDValue PromoteLegalINT_TO_FP(SDValue LegalOp, EVT DestVT, bool isSigned,
 122                                 DebugLoc dl);
 123   SDValue PromoteLegalFP_TO_INT(SDValue LegalOp, EVT DestVT, bool isSigned,
 124                                 DebugLoc dl);
 125
 126   SDValue ExpandBSWAP(SDValue Op, DebugLoc dl);
 127   SDValue ExpandBitCount(unsigned Opc, SDValue Op, DebugLoc dl);
 128
 129   SDValue ExpandExtractFromVectorThroughStack(SDValue Op);
 130   SDValue ExpandInsertToVectorThroughStack(SDValue Op);
 131   SDValue ExpandVectorBuildThroughStack(SDNode* Node);
 132
 133   SDValue ExpandConstantFP(ConstantFPSDNode *CFP, bool UseCP);
 134
 135   std::pair<SDValue, SDValue> ExpandAtomic(SDNode *Node);
 136
 137   void ExpandNode(SDNode *Node);
 138   void PromoteNode(SDNode *Node);
 139
 140   void ForgetNode(SDNode *N) {
 141     LegalizedNodes.erase(N);
 142     if (LegalizePosition == SelectionDAG::allnodes_iterator(N))
 143       ++LegalizePosition;
 144   }
 145
 146 public:
 147   // DAGUpdateListener implementation.
 148   virtual void NodeDeleted(SDNode *N, SDNode *E) {
 149     ForgetNode(N);
 150   }
 151   virtual void NodeUpdated(SDNode *N) {}
 152
 153   // Node replacement helpers
 154   void ReplacedNode(SDNode *N) {
 155     if (N->use_empty()) {
 156       DAG.RemoveDeadNode(N);
 157     } else {
 158       ForgetNode(N);
 159     }
 160   }
 161   void ReplaceNode(SDNode *Old, SDNode *New) {
 162     DAG.ReplaceAllUsesWith(Old, New);
 163     ReplacedNode(Old);
 164   }
 165   void ReplaceNode(SDValue Old, SDValue New) {
 166     DAG.ReplaceAllUsesWith(Old, New);
 167     ReplacedNode(Old.getNode());
 168   }
 169   void ReplaceNode(SDNode *Old, const SDValue *New) {
 170     DAG.ReplaceAllUsesWith(Old, New);
 171     ReplacedNode(Old);
 172   }
 173 };
 174 }
 175
 176 /// ShuffleWithNarrowerEltType - Return a vector shuffle operation which
 177 /// performs the same shuffe in terms of order or result bytes, but on a type
 178 /// whose vector element type is narrower than the original shuffle type.
 179 /// e.g. <v4i32> <0, 1, 0, 1> -> v8i16 <0, 1, 2, 3, 0, 1, 2, 3>
 180 SDValue
 181 SelectionDAGLegalize::ShuffleWithNarrowerEltType(EVT NVT, EVT VT,  DebugLoc dl,
 182                                                  SDValue N1, SDValue N2,
 183                                                  ArrayRef<int> Mask) const {
 184   unsigned NumMaskElts = VT.getVectorNumElements();
 185   unsigned NumDestElts = NVT.getVectorNumElements();
 186   unsigned NumEltsGrowth = NumDestElts / NumMaskElts;
 187
 188   assert(NumEltsGrowth && "Cannot promote to vector type with fewer elts!");
 189
 190   if (NumEltsGrowth == 1)
 191     return DAG.getVectorShuffle(NVT, dl, N1, N2, &Mask[0]);
 192
 193   SmallVector<int, 8> NewMask;
 194   for (unsigned i = 0; i != NumMaskElts; ++i) {
 195     int Idx = Mask[i];
 196     for (unsigned j = 0; j != NumEltsGrowth; ++j) {
 197       if (Idx < 0)
 198         NewMask.push_back(-1);
 199       else
 200         NewMask.push_back(Idx * NumEltsGrowth + j);
 201     }
 202   }
 203   assert(NewMask.size() == NumDestElts && "Non-integer NumEltsGrowth?");
 204   assert(TLI.isShuffleMaskLegal(NewMask, NVT) && "Shuffle not legal?");
 205   return DAG.getVectorShuffle(NVT, dl, N1, N2, &NewMask[0]);
 206 }
 207
 208 SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag)
 209   : SelectionDAG::DAGUpdateListener(dag),
 210     TM(dag.getTarget()), TLI(dag.getTargetLoweringInfo()),
 211     DAG(dag) {
 212 }
 213
 214 void SelectionDAGLegalize::LegalizeDAG() {
 215   DAG.AssignTopologicalOrder();
 216
 217   // Visit all the nodes. We start in topological order, so that we see
 218   // nodes with their original operands intact. Legalization can produce
 219   // new nodes which may themselves need to be legalized. Iterate until all
 220   // nodes have been legalized.
 221   for (;;) {
 222     bool AnyLegalized = false;
 223     for (LegalizePosition = DAG.allnodes_end();
 224          LegalizePosition != DAG.allnodes_begin(); ) {
 225       --LegalizePosition;
 226
 227       SDNode *N = LegalizePosition;
 228       if (LegalizedNodes.insert(N)) {
 229         AnyLegalized = true;
 230         LegalizeOp(N);
 231       }
 232     }
 233     if (!AnyLegalized)
 234       break;
 235
 236   }
 237
 238   // Remove dead nodes now.
 239   DAG.RemoveDeadNodes();
 240 }
 241
 242 /// ExpandConstantFP - Expands the ConstantFP node to an integer constant or
 243 /// a load from the constant pool.
 244 SDValue
 245 SelectionDAGLegalize::ExpandConstantFP(ConstantFPSDNode *CFP, bool UseCP) {
 246   bool Extend = false;
 247   DebugLoc dl = CFP->getDebugLoc();
 248
 249   // If a FP immediate is precise when represented as a float and if the
 250   // target can do an extending load from float to double, we put it into
 251   // the constant pool as a float, even if it's is statically typed as a
 252   // double.  This shrinks FP constants and canonicalizes them for targets where
 253   // an FP extending load is the same cost as a normal load (such as on the x87
 254   // fp stack or PPC FP unit).
 255   EVT VT = CFP->getValueType(0);
 256   ConstantFP *LLVMC = const_cast<ConstantFP*>(CFP->getConstantFPValue());
 257   if (!UseCP) {
 258     assert((VT == MVT::f64 || VT == MVT::f32) && "Invalid type expansion");
 259     return DAG.getConstant(LLVMC->getValueAPF().bitcastToAPInt(),
 260                            (VT == MVT::f64) ? MVT::i64 : MVT::i32);
 261   }
 262
 263   EVT OrigVT = VT;
 264   EVT SVT = VT;
 265   while (SVT != MVT::f32) {
 266     SVT = (MVT::SimpleValueType)(SVT.getSimpleVT().SimpleTy - 1);
 267     if (ConstantFPSDNode::isValueValidForType(SVT, CFP->getValueAPF()) &&
 268         // Only do this if the target has a native EXTLOAD instruction from
 269         // smaller type.
 270         TLI.isLoadExtLegal(ISD::EXTLOAD, SVT) &&
 271         TLI.ShouldShrinkFPConstant(OrigVT)) {
 272       Type *SType = SVT.getTypeForEVT(*DAG.getContext());
 273       LLVMC = cast<ConstantFP>(ConstantExpr::getFPTrunc(LLVMC, SType));
 274       VT = SVT;
 275       Extend = true;
 276     }
 277   }
 278
 279   SDValue CPIdx = DAG.getConstantPool(LLVMC, TLI.getPointerTy());
 280   unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment();
 281   if (Extend) {
 282     SDValue Result =
 283       DAG.getExtLoad(ISD::EXTLOAD, dl, OrigVT,
 284                      DAG.getEntryNode(),
 285                      CPIdx, MachinePointerInfo::getConstantPool(),
 286                      VT, false, false, Alignment);
 287     return Result;
 288   }
 289   SDValue Result =
 290     DAG.getLoad(OrigVT, dl, DAG.getEntryNode(), CPIdx,
 291                 MachinePointerInfo::getConstantPool(), false, false, false,
 292                 Alignment);
 293   return Result;
 294 }
 295
 296 /// ExpandUnalignedStore - Expands an unaligned store to 2 half-size stores.
 297 static void ExpandUnalignedStore(StoreSDNode *ST, SelectionDAG &DAG,
 298                                  const TargetLowering &TLI,
 299                                  SelectionDAGLegalize *DAGLegalize) {
 300   assert(ST->getAddressingMode() == ISD::UNINDEXED &&
 301          "unaligned indexed stores not implemented!");
 302   SDValue Chain = ST->getChain();
 303   SDValue Ptr = ST->getBasePtr();
 304   SDValue Val = ST->getValue();
 305   EVT VT = Val.getValueType();
 306   int Alignment = ST->getAlignment();
 307   DebugLoc dl = ST->getDebugLoc();
 308   if (ST->getMemoryVT().isFloatingPoint() ||
 309       ST->getMemoryVT().isVector()) {
 310     EVT intVT = EVT::getIntegerVT(*DAG.getContext(), VT.getSizeInBits());
 311     if (TLI.isTypeLegal(intVT)) {
 312       // Expand to a bitconvert of the value to the integer type of the
 313       // same size, then a (misaligned) int store.
 314       // FIXME: Does not handle truncating floating point stores!
 315       SDValue Result = DAG.getNode(ISD::BITCAST, dl, intVT, Val);
 316       Result = DAG.getStore(Chain, dl, Result, Ptr, ST->getPointerInfo(),
 317                            ST->isVolatile(), ST->isNonTemporal(), Alignment);
 318       DAGLegalize->ReplaceNode(SDValue(ST, 0), Result);
 319       return;
 320     }
 321     // Do a (aligned) store to a stack slot, then copy from the stack slot
 322     // to the final destination using (unaligned) integer loads and stores.
 323     EVT StoredVT = ST->getMemoryVT();
 324     MVT RegVT =
 325       TLI.getRegisterType(*DAG.getContext(),
 326                           EVT::getIntegerVT(*DAG.getContext(),
 327                                             StoredVT.getSizeInBits()));
 328     unsigned StoredBytes = StoredVT.getSizeInBits() / 8;
 329     unsigned RegBytes = RegVT.getSizeInBits() / 8;
 330     unsigned NumRegs = (StoredBytes + RegBytes - 1) / RegBytes;
 331
 332     // Make sure the stack slot is also aligned for the register type.
 333     SDValue StackPtr = DAG.CreateStackTemporary(StoredVT, RegVT);
 334
 335     // Perform the original store, only redirected to the stack slot.
 336     SDValue Store = DAG.getTruncStore(Chain, dl,
 337                                       Val, StackPtr, MachinePointerInfo(),
 338                                       StoredVT, false, false, 0);
 339     SDValue Increment = DAG.getConstant(RegBytes, TLI.getPointerTy());
 340     SmallVector<SDValue, 8> Stores;
 341     unsigned Offset = 0;
 342
 343     // Do all but one copies using the full register width.
 344     for (unsigned i = 1; i < NumRegs; i++) {
 345       // Load one integer register's worth from the stack slot.
 346       SDValue Load = DAG.getLoad(RegVT, dl, Store, StackPtr,
 347                                  MachinePointerInfo(),
 348                                  false, false, false, 0);
 349       // Store it to the final location.  Remember the store.
 350       Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, Ptr,
 351                                   ST->getPointerInfo().getWithOffset(Offset),
 352                                     ST->isVolatile(), ST->isNonTemporal(),
 353                                     MinAlign(ST->getAlignment(), Offset)));
 354       // Increment the pointers.
 355       Offset += RegBytes;
 356       StackPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr,
 357                              Increment);
 358       Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr, Increment);
 359     }
 360
 361     // The last store may be partial.  Do a truncating store.  On big-endian
 362     // machines this requires an extending load from the stack slot to ensure
 363     // that the bits are in the right place.
 364     EVT MemVT = EVT::getIntegerVT(*DAG.getContext(),
 365                                   8 * (StoredBytes - Offset));
 366
 367     // Load from the stack slot.
 368     SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Store, StackPtr,
 369                                   MachinePointerInfo(),
 370                                   MemVT, false, false, 0);
 371
 372     Stores.push_back(DAG.getTruncStore(Load.getValue(1), dl, Load, Ptr,
 373                                        ST->getPointerInfo()
 374                                          .getWithOffset(Offset),
 375                                        MemVT, ST->isVolatile(),
 376                                        ST->isNonTemporal(),
 377                                        MinAlign(ST->getAlignment(), Offset)));
 378     // The order of the stores doesn't matter - say it with a TokenFactor.
 379     SDValue Result =
 380       DAG.getNode(ISD::TokenFactor, dl, MVT::Other, &Stores[0],
 381                   Stores.size());
 382     DAGLegalize->ReplaceNode(SDValue(ST, 0), Result);
 383     return;
 384   }
 385   assert(ST->getMemoryVT().isInteger() &&
 386          !ST->getMemoryVT().isVector() &&
 387          "Unaligned store of unknown type.");
 388   // Get the half-size VT
 389   EVT NewStoredVT = ST->getMemoryVT().getHalfSizedIntegerVT(*DAG.getContext());
 390   int NumBits = NewStoredVT.getSizeInBits();
 391   int IncrementSize = NumBits / 8;
 392
 393   // Divide the stored value in two parts.
 394   SDValue ShiftAmount = DAG.getConstant(NumBits,
 395                                       TLI.getShiftAmountTy(Val.getValueType()));
 396   SDValue Lo = Val;
 397   SDValue Hi = DAG.getNode(ISD::SRL, dl, VT, Val, ShiftAmount);
 398
 399   // Store the two parts
 400   SDValue Store1, Store2;
 401   Store1 = DAG.getTruncStore(Chain, dl, TLI.isLittleEndian()?Lo:Hi, Ptr,
 402                              ST->getPointerInfo(), NewStoredVT,
 403                              ST->isVolatile(), ST->isNonTemporal(), Alignment);
 404   Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 405                     DAG.getConstant(IncrementSize, TLI.getPointerTy()));
 406   Alignment = MinAlign(Alignment, IncrementSize);
 407   Store2 = DAG.getTruncStore(Chain, dl, TLI.isLittleEndian()?Hi:Lo, Ptr,
 408                              ST->getPointerInfo().getWithOffset(IncrementSize),
 409                              NewStoredVT, ST->isVolatile(), ST->isNonTemporal(),
 410                              Alignment);
 411
 412   SDValue Result =
 413     DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Store1, Store2);
 414   DAGLegalize->ReplaceNode(SDValue(ST, 0), Result);
 415 }
 416
 417 /// ExpandUnalignedLoad - Expands an unaligned load to 2 half-size loads.
 418 static void
 419 ExpandUnalignedLoad(LoadSDNode *LD, SelectionDAG &DAG,
 420                     const TargetLowering &TLI,
 421                     SDValue &ValResult, SDValue &ChainResult) {
 422   assert(LD->getAddressingMode() == ISD::UNINDEXED &&
 423          "unaligned indexed loads not implemented!");
 424   SDValue Chain = LD->getChain();
 425   SDValue Ptr = LD->getBasePtr();
 426   EVT VT = LD->getValueType(0);
 427   EVT LoadedVT = LD->getMemoryVT();
 428   DebugLoc dl = LD->getDebugLoc();
 429   if (VT.isFloatingPoint() || VT.isVector()) {
 430     EVT intVT = EVT::getIntegerVT(*DAG.getContext(), LoadedVT.getSizeInBits());
 431     if (TLI.isTypeLegal(intVT) && TLI.isTypeLegal(LoadedVT)) {
 432       // Expand to a (misaligned) integer load of the same size,
 433       // then bitconvert to floating point or vector.
 434       SDValue newLoad = DAG.getLoad(intVT, dl, Chain, Ptr, LD->getPointerInfo(),
 435                                     LD->isVolatile(),
 436                                     LD->isNonTemporal(),
 437                                     LD->isInvariant(), LD->getAlignment());
 438       SDValue Result = DAG.getNode(ISD::BITCAST, dl, LoadedVT, newLoad);
 439       if (LoadedVT != VT)
 440         Result = DAG.getNode(VT.isFloatingPoint() ? ISD::FP_EXTEND :
 441                              ISD::ANY_EXTEND, dl, VT, Result);
 442
 443       ValResult = Result;
 444       ChainResult = Chain;
 445       return;
 446     }
 447
 448     // Copy the value to a (aligned) stack slot using (unaligned) integer
 449     // loads and stores, then do a (aligned) load from the stack slot.
 450     MVT RegVT = TLI.getRegisterType(*DAG.getContext(), intVT);
 451     unsigned LoadedBytes = LoadedVT.getSizeInBits() / 8;
 452     unsigned RegBytes = RegVT.getSizeInBits() / 8;
 453     unsigned NumRegs = (LoadedBytes + RegBytes - 1) / RegBytes;
 454
 455     // Make sure the stack slot is also aligned for the register type.
 456     SDValue StackBase = DAG.CreateStackTemporary(LoadedVT, RegVT);
 457
 458     SDValue Increment = DAG.getConstant(RegBytes, TLI.getPointerTy());
 459     SmallVector<SDValue, 8> Stores;
 460     SDValue StackPtr = StackBase;
 461     unsigned Offset = 0;
 462
 463     // Do all but one copies using the full register width.
 464     for (unsigned i = 1; i < NumRegs; i++) {
 465       // Load one integer register's worth from the original location.
 466       SDValue Load = DAG.getLoad(RegVT, dl, Chain, Ptr,
 467                                  LD->getPointerInfo().getWithOffset(Offset),
 468                                  LD->isVolatile(), LD->isNonTemporal(),
 469                                  LD->isInvariant(),
 470                                  MinAlign(LD->getAlignment(), Offset));
 471       // Follow the load with a store to the stack slot.  Remember the store.
 472       Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, StackPtr,
 473                                     MachinePointerInfo(), false, false, 0));
 474       // Increment the pointers.
 475       Offset += RegBytes;
 476       Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr, Increment);
 477       StackPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr,
 478                              Increment);
 479     }
 480
 481     // The last copy may be partial.  Do an extending load.
 482     EVT MemVT = EVT::getIntegerVT(*DAG.getContext(),
 483                                   8 * (LoadedBytes - Offset));
 484     SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Chain, Ptr,
 485                                   LD->getPointerInfo().getWithOffset(Offset),
 486                                   MemVT, LD->isVolatile(),
 487                                   LD->isNonTemporal(),
 488                                   MinAlign(LD->getAlignment(), Offset));
 489     // Follow the load with a store to the stack slot.  Remember the store.
 490     // On big-endian machines this requires a truncating store to ensure
 491     // that the bits end up in the right place.
 492     Stores.push_back(DAG.getTruncStore(Load.getValue(1), dl, Load, StackPtr,
 493                                        MachinePointerInfo(), MemVT,
 494                                        false, false, 0));
 495
 496     // The order of the stores doesn't matter - say it with a TokenFactor.
 497     SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, &Stores[0],
 498                              Stores.size());
 499
 500     // Finally, perform the original load only redirected to the stack slot.
 501     Load = DAG.getExtLoad(LD->getExtensionType(), dl, VT, TF, StackBase,
 502                           MachinePointerInfo(), LoadedVT, false, false, 0);
 503
 504     // Callers expect a MERGE_VALUES node.
 505     ValResult = Load;
 506     ChainResult = TF;
 507     return;
 508   }
 509   assert(LoadedVT.isInteger() && !LoadedVT.isVector() &&
 510          "Unaligned load of unsupported type.");
 511
 512   // Compute the new VT that is half the size of the old one.  This is an
 513   // integer MVT.
 514   unsigned NumBits = LoadedVT.getSizeInBits();
 515   EVT NewLoadedVT;
 516   NewLoadedVT = EVT::getIntegerVT(*DAG.getContext(), NumBits/2);
 517   NumBits >>= 1;
 518
 519   unsigned Alignment = LD->getAlignment();
 520   unsigned IncrementSize = NumBits / 8;
 521   ISD::LoadExtType HiExtType = LD->getExtensionType();
 522
 523   // If the original load is NON_EXTLOAD, the hi part load must be ZEXTLOAD.
 524   if (HiExtType == ISD::NON_EXTLOAD)
 525     HiExtType = ISD::ZEXTLOAD;
 526
 527   // Load the value in two parts
 528   SDValue Lo, Hi;
 529   if (TLI.isLittleEndian()) {
 530     Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr, LD->getPointerInfo(),
 531                         NewLoadedVT, LD->isVolatile(),
 532                         LD->isNonTemporal(), Alignment);
 533     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 534                       DAG.getConstant(IncrementSize, TLI.getPointerTy()));
 535     Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr,
 536                         LD->getPointerInfo().getWithOffset(IncrementSize),
 537                         NewLoadedVT, LD->isVolatile(),
 538                         LD->isNonTemporal(), MinAlign(Alignment,IncrementSize));
 539   } else {
 540     Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr, LD->getPointerInfo(),
 541                         NewLoadedVT, LD->isVolatile(),
 542                         LD->isNonTemporal(), Alignment);
 543     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 544                       DAG.getConstant(IncrementSize, TLI.getPointerTy()));
 545     Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr,
 546                         LD->getPointerInfo().getWithOffset(IncrementSize),
 547                         NewLoadedVT, LD->isVolatile(),
 548                         LD->isNonTemporal(), MinAlign(Alignment,IncrementSize));
 549   }
 550
 551   // aggregate the two parts
 552   SDValue ShiftAmount = DAG.getConstant(NumBits,
 553                                        TLI.getShiftAmountTy(Hi.getValueType()));
 554   SDValue Result = DAG.getNode(ISD::SHL, dl, VT, Hi, ShiftAmount);
 555   Result = DAG.getNode(ISD::OR, dl, VT, Result, Lo);
 556
 557   SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
 558                              Hi.getValue(1));
 559
 560   ValResult = Result;
 561   ChainResult = TF;
 562 }
 563
 564 /// PerformInsertVectorEltInMemory - Some target cannot handle a variable
 565 /// insertion index for the INSERT_VECTOR_ELT instruction.  In this case, it
 566 /// is necessary to spill the vector being inserted into to memory, perform
 567 /// the insert there, and then read the result back.
 568 SDValue SelectionDAGLegalize::
 569 PerformInsertVectorEltInMemory(SDValue Vec, SDValue Val, SDValue Idx,
 570                                DebugLoc dl) {
 571   SDValue Tmp1 = Vec;
 572   SDValue Tmp2 = Val;
 573   SDValue Tmp3 = Idx;
 574
 575   // If the target doesn't support this, we have to spill the input vector
 576   // to a temporary stack slot, update the element, then reload it.  This is
 577   // badness.  We could also load the value into a vector register (either
 578   // with a "move to register" or "extload into register" instruction, then
 579   // permute it into place, if the idx is a constant and if the idx is
 580   // supported by the target.
 581   EVT VT    = Tmp1.getValueType();
 582   EVT EltVT = VT.getVectorElementType();
 583   EVT IdxVT = Tmp3.getValueType();
 584   EVT PtrVT = TLI.getPointerTy();
 585   SDValue StackPtr = DAG.CreateStackTemporary(VT);
 586
 587   int SPFI = cast<FrameIndexSDNode>(StackPtr.getNode())->getIndex();
 588
 589   // Store the vector.
 590   SDValue Ch = DAG.getStore(DAG.getEntryNode(), dl, Tmp1, StackPtr,
 591                             MachinePointerInfo::getFixedStack(SPFI),
 592                             false, false, 0);
 593
 594   // Truncate or zero extend offset to target pointer type.
 595   unsigned CastOpc = IdxVT.bitsGT(PtrVT) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
 596   Tmp3 = DAG.getNode(CastOpc, dl, PtrVT, Tmp3);
 597   // Add the offset to the index.
 598   unsigned EltSize = EltVT.getSizeInBits()/8;
 599   Tmp3 = DAG.getNode(ISD::MUL, dl, IdxVT, Tmp3,DAG.getConstant(EltSize, IdxVT));
 600   SDValue StackPtr2 = DAG.getNode(ISD::ADD, dl, IdxVT, Tmp3, StackPtr);
 601   // Store the scalar value.
 602   Ch = DAG.getTruncStore(Ch, dl, Tmp2, StackPtr2, MachinePointerInfo(), EltVT,
 603                          false, false, 0);
 604   // Load the updated vector.
 605   return DAG.getLoad(VT, dl, Ch, StackPtr,
 606                      MachinePointerInfo::getFixedStack(SPFI), false, false,
 607                      false, 0);
 608 }
 609
 610
 611 SDValue SelectionDAGLegalize::
 612 ExpandINSERT_VECTOR_ELT(SDValue Vec, SDValue Val, SDValue Idx, DebugLoc dl) {
 613   if (ConstantSDNode *InsertPos = dyn_cast<ConstantSDNode>(Idx)) {
 614     // SCALAR_TO_VECTOR requires that the type of the value being inserted
 615     // match the element type of the vector being created, except for
 616     // integers in which case the inserted value can be over width.
 617     EVT EltVT = Vec.getValueType().getVectorElementType();
 618     if (Val.getValueType() == EltVT ||
 619         (EltVT.isInteger() && Val.getValueType().bitsGE(EltVT))) {
 620       SDValue ScVec = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl,
 621                                   Vec.getValueType(), Val);
 622
 623       unsigned NumElts = Vec.getValueType().getVectorNumElements();
 624       // We generate a shuffle of InVec and ScVec, so the shuffle mask
 625       // should be 0,1,2,3,4,5... with the appropriate element replaced with
 626       // elt 0 of the RHS.
 627       SmallVector<int, 8> ShufOps;
 628       for (unsigned i = 0; i != NumElts; ++i)
 629         ShufOps.push_back(i != InsertPos->getZExtValue() ? i : NumElts);
 630
 631       return DAG.getVectorShuffle(Vec.getValueType(), dl, Vec, ScVec,
 632                                   &ShufOps[0]);
 633     }
 634   }
 635   return PerformInsertVectorEltInMemory(Vec, Val, Idx, dl);
 636 }
 637
 638 SDValue SelectionDAGLegalize::OptimizeFloatStore(StoreSDNode* ST) {
 639   // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
 640   // FIXME: We shouldn't do this for TargetConstantFP's.
 641   // FIXME: move this to the DAG Combiner!  Note that we can't regress due
 642   // to phase ordering between legalized code and the dag combiner.  This
 643   // probably means that we need to integrate dag combiner and legalizer
 644   // together.
 645   // We generally can't do this one for long doubles.
 646   SDValue Chain = ST->getChain();
 647   SDValue Ptr = ST->getBasePtr();
 648   unsigned Alignment = ST->getAlignment();
 649   bool isVolatile = ST->isVolatile();
 650   bool isNonTemporal = ST->isNonTemporal();
 651   DebugLoc dl = ST->getDebugLoc();
 652   if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(ST->getValue())) {
 653     if (CFP->getValueType(0) == MVT::f32 &&
 654         TLI.isTypeLegal(MVT::i32)) {
 655       SDValue Con = DAG.getConstant(CFP->getValueAPF().
 656                                       bitcastToAPInt().zextOrTrunc(32),
 657                               MVT::i32);
 658       return DAG.getStore(Chain, dl, Con, Ptr, ST->getPointerInfo(),
 659                           isVolatile, isNonTemporal, Alignment);
 660     }
 661
 662     if (CFP->getValueType(0) == MVT::f64) {
 663       // If this target supports 64-bit registers, do a single 64-bit store.
 664       if (TLI.isTypeLegal(MVT::i64)) {
 665         SDValue Con = DAG.getConstant(CFP->getValueAPF().bitcastToAPInt().
 666                                   zextOrTrunc(64), MVT::i64);
 667         return DAG.getStore(Chain, dl, Con, Ptr, ST->getPointerInfo(),
 668                             isVolatile, isNonTemporal, Alignment);
 669       }
 670
 671       if (TLI.isTypeLegal(MVT::i32) && !ST->isVolatile()) {
 672         // Otherwise, if the target supports 32-bit registers, use 2 32-bit
 673         // stores.  If the target supports neither 32- nor 64-bits, this
 674         // xform is certainly not worth it.
 675         const APInt &IntVal =CFP->getValueAPF().bitcastToAPInt();
 676         SDValue Lo = DAG.getConstant(IntVal.trunc(32), MVT::i32);
 677         SDValue Hi = DAG.getConstant(IntVal.lshr(32).trunc(32), MVT::i32);
 678         if (TLI.isBigEndian()) std::swap(Lo, Hi);
 679
 680         Lo = DAG.getStore(Chain, dl, Lo, Ptr, ST->getPointerInfo(), isVolatile,
 681                           isNonTemporal, Alignment);
 682         Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 683                             DAG.getIntPtrConstant(4));
 684         Hi = DAG.getStore(Chain, dl, Hi, Ptr,
 685                           ST->getPointerInfo().getWithOffset(4),
 686                           isVolatile, isNonTemporal, MinAlign(Alignment, 4U));
 687
 688         return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
 689       }
 690     }
 691   }
 692   return SDValue(0, 0);
 693 }
 694
 695 void SelectionDAGLegalize::LegalizeStoreOps(SDNode *Node) {
 696     StoreSDNode *ST = cast<StoreSDNode>(Node);
 697     SDValue Chain = ST->getChain();
 698     SDValue Ptr = ST->getBasePtr();
 699     DebugLoc dl = Node->getDebugLoc();
 700
 701     unsigned Alignment = ST->getAlignment();
 702     bool isVolatile = ST->isVolatile();
 703     bool isNonTemporal = ST->isNonTemporal();
 704
 705     if (!ST->isTruncatingStore()) {
 706       if (SDNode *OptStore = OptimizeFloatStore(ST).getNode()) {
 707         ReplaceNode(ST, OptStore);
 708         return;
 709       }
 710
 711       {
 712         SDValue Value = ST->getValue();
 713         MVT VT = Value.getSimpleValueType();
 714         switch (TLI.getOperationAction(ISD::STORE, VT)) {
 715         default: llvm_unreachable("This action is not supported yet!");
 716         case TargetLowering::Legal:
 717           // If this is an unaligned store and the target doesn't support it,
 718           // expand it.
 719           if (!TLI.allowsUnalignedMemoryAccesses(ST->getMemoryVT())) {
 720             Type *Ty = ST->getMemoryVT().getTypeForEVT(*DAG.getContext());
 721             unsigned ABIAlignment= TLI.getDataLayout()->getABITypeAlignment(Ty);
 722             if (ST->getAlignment() < ABIAlignment)
 723               ExpandUnalignedStore(cast<StoreSDNode>(Node),
 724                                    DAG, TLI, this);
 725           }
 726           break;
 727         case TargetLowering::Custom: {
 728           SDValue Res = TLI.LowerOperation(SDValue(Node, 0), DAG);
 729           if (Res.getNode())
 730             ReplaceNode(SDValue(Node, 0), Res);
 731           return;
 732         }
 733         case TargetLowering::Promote: {
 734           MVT NVT = TLI.getTypeToPromoteTo(ISD::STORE, VT);
 735           assert(NVT.getSizeInBits() == VT.getSizeInBits() &&
 736                  "Can only promote stores to same size type");
 737           Value = DAG.getNode(ISD::BITCAST, dl, NVT, Value);
 738           SDValue Result =
 739             DAG.getStore(Chain, dl, Value, Ptr,
 740                          ST->getPointerInfo(), isVolatile,
 741                          isNonTemporal, Alignment);
 742           ReplaceNode(SDValue(Node, 0), Result);
 743           break;
 744         }
 745         }
 746         return;
 747       }
 748     } else {
 749       SDValue Value = ST->getValue();
 750
 751       EVT StVT = ST->getMemoryVT();
 752       unsigned StWidth = StVT.getSizeInBits();
 753
 754       if (StWidth != StVT.getStoreSizeInBits()) {
 755         // Promote to a byte-sized store with upper bits zero if not
 756         // storing an integral number of bytes.  For example, promote
 757         // TRUNCSTORE:i1 X -> TRUNCSTORE:i8 (and X, 1)
 758         EVT NVT = EVT::getIntegerVT(*DAG.getContext(),
 759                                     StVT.getStoreSizeInBits());
 760         Value = DAG.getZeroExtendInReg(Value, dl, StVT);
 761         SDValue Result =
 762           DAG.getTruncStore(Chain, dl, Value, Ptr, ST->getPointerInfo(),
 763                             NVT, isVolatile, isNonTemporal, Alignment);
 764         ReplaceNode(SDValue(Node, 0), Result);
 765       } else if (StWidth & (StWidth - 1)) {
 766         // If not storing a power-of-2 number of bits, expand as two stores.
 767         assert(!StVT.isVector() && "Unsupported truncstore!");
 768         unsigned RoundWidth = 1 << Log2_32(StWidth);
 769         assert(RoundWidth < StWidth);
 770         unsigned ExtraWidth = StWidth - RoundWidth;
 771         assert(ExtraWidth < RoundWidth);
 772         assert(!(RoundWidth % 8) && !(ExtraWidth % 8) &&
 773                "Store size not an integral number of bytes!");
 774         EVT RoundVT = EVT::getIntegerVT(*DAG.getContext(), RoundWidth);
 775         EVT ExtraVT = EVT::getIntegerVT(*DAG.getContext(), ExtraWidth);
 776         SDValue Lo, Hi;
 777         unsigned IncrementSize;
 778
 779         if (TLI.isLittleEndian()) {
 780           // TRUNCSTORE:i24 X -> TRUNCSTORE:i16 X, TRUNCSTORE@+2:i8 (srl X, 16)
 781           // Store the bottom RoundWidth bits.
 782           Lo = DAG.getTruncStore(Chain, dl, Value, Ptr, ST->getPointerInfo(),
 783                                  RoundVT,
 784                                  isVolatile, isNonTemporal, Alignment);
 785
 786           // Store the remaining ExtraWidth bits.
 787           IncrementSize = RoundWidth / 8;
 788           Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 789                              DAG.getIntPtrConstant(IncrementSize));
 790           Hi = DAG.getNode(ISD::SRL, dl, Value.getValueType(), Value,
 791                            DAG.getConstant(RoundWidth,
 792                                     TLI.getShiftAmountTy(Value.getValueType())));
 793           Hi = DAG.getTruncStore(Chain, dl, Hi, Ptr,
 794                              ST->getPointerInfo().getWithOffset(IncrementSize),
 795                                  ExtraVT, isVolatile, isNonTemporal,
 796                                  MinAlign(Alignment, IncrementSize));
 797         } else {
 798           // Big endian - avoid unaligned stores.
 799           // TRUNCSTORE:i24 X -> TRUNCSTORE:i16 (srl X, 8), TRUNCSTORE@+2:i8 X
 800           // Store the top RoundWidth bits.
 801           Hi = DAG.getNode(ISD::SRL, dl, Value.getValueType(), Value,
 802                            DAG.getConstant(ExtraWidth,
 803                                     TLI.getShiftAmountTy(Value.getValueType())));
 804           Hi = DAG.getTruncStore(Chain, dl, Hi, Ptr, ST->getPointerInfo(),
 805                                  RoundVT, isVolatile, isNonTemporal, Alignment);
 806
 807           // Store the remaining ExtraWidth bits.
 808           IncrementSize = RoundWidth / 8;
 809           Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 810                              DAG.getIntPtrConstant(IncrementSize));
 811           Lo = DAG.getTruncStore(Chain, dl, Value, Ptr,
 812                               ST->getPointerInfo().getWithOffset(IncrementSize),
 813                                  ExtraVT, isVolatile, isNonTemporal,
 814                                  MinAlign(Alignment, IncrementSize));
 815         }
 816
 817         // The order of the stores doesn't matter.
 818         SDValue Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
 819         ReplaceNode(SDValue(Node, 0), Result);
 820       } else {
 821         switch (TLI.getTruncStoreAction(ST->getValue().getSimpleValueType(),
 822                                         StVT.getSimpleVT())) {
 823         default: llvm_unreachable("This action is not supported yet!");
 824         case TargetLowering::Legal:
 825           // If this is an unaligned store and the target doesn't support it,
 826           // expand it.
 827           if (!TLI.allowsUnalignedMemoryAccesses(ST->getMemoryVT())) {
 828             Type *Ty = ST->getMemoryVT().getTypeForEVT(*DAG.getContext());
 829             unsigned ABIAlignment= TLI.getDataLayout()->getABITypeAlignment(Ty);
 830             if (ST->getAlignment() < ABIAlignment)
 831               ExpandUnalignedStore(cast<StoreSDNode>(Node), DAG, TLI, this);
 832           }
 833           break;
 834         case TargetLowering::Custom: {
 835           SDValue Res = TLI.LowerOperation(SDValue(Node, 0), DAG);
 836           if (Res.getNode())
 837             ReplaceNode(SDValue(Node, 0), Res);
 838           return;
 839         }
 840         case TargetLowering::Expand:
 841           assert(!StVT.isVector() &&
 842                  "Vector Stores are handled in LegalizeVectorOps");
 843
 844           // TRUNCSTORE:i16 i32 -> STORE i16
 845           assert(TLI.isTypeLegal(StVT) &&
 846                  "Do not know how to expand this store!");
 847           Value = DAG.getNode(ISD::TRUNCATE, dl, StVT, Value);
 848           SDValue Result =
 849             DAG.getStore(Chain, dl, Value, Ptr, ST->getPointerInfo(),
 850                          isVolatile, isNonTemporal, Alignment);
 851           ReplaceNode(SDValue(Node, 0), Result);
 852           break;
 853         }
 854       }
 855     }
 856 }
 857
 858 void SelectionDAGLegalize::LegalizeLoadOps(SDNode *Node) {
 859   LoadSDNode *LD = cast<LoadSDNode>(Node);
 860   SDValue Chain = LD->getChain();  // The chain.
 861   SDValue Ptr = LD->getBasePtr();  // The base pointer.
 862   SDValue Value;                   // The value returned by the load op.
 863   DebugLoc dl = Node->getDebugLoc();
 864
 865   ISD::LoadExtType ExtType = LD->getExtensionType();
 866   if (ExtType == ISD::NON_EXTLOAD) {
 867     MVT VT = Node->getSimpleValueType(0);
 868     SDValue RVal = SDValue(Node, 0);
 869     SDValue RChain = SDValue(Node, 1);
 870
 871     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
 872     default: llvm_unreachable("This action is not supported yet!");
 873     case TargetLowering::Legal:
 874       // If this is an unaligned load and the target doesn't support it,
 875       // expand it.
 876       if (!TLI.allowsUnalignedMemoryAccesses(LD->getMemoryVT())) {
 877         Type *Ty = LD->getMemoryVT().getTypeForEVT(*DAG.getContext());
 878         unsigned ABIAlignment =
 879           TLI.getDataLayout()->getABITypeAlignment(Ty);
 880         if (LD->getAlignment() < ABIAlignment){
 881           ExpandUnalignedLoad(cast<LoadSDNode>(Node), DAG, TLI, RVal, RChain);
 882         }
 883       }
 884       break;
 885     case TargetLowering::Custom: {
 886       SDValue Res = TLI.LowerOperation(RVal, DAG);
 887       if (Res.getNode()) {
 888         RVal = Res;
 889         RChain = Res.getValue(1);
 890       }
 891       break;
 892     }
 893     case TargetLowering::Promote: {
 894       MVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), VT);
 895       assert(NVT.getSizeInBits() == VT.getSizeInBits() &&
 896              "Can only promote loads to same size type");
 897
 898       SDValue Res = DAG.getLoad(NVT, dl, Chain, Ptr, LD->getPointerInfo(),
 899                          LD->isVolatile(), LD->isNonTemporal(),
 900                          LD->isInvariant(), LD->getAlignment());
 901       RVal = DAG.getNode(ISD::BITCAST, dl, VT, Res);
 902       RChain = Res.getValue(1);
 903       break;
 904     }
 905     }
 906     if (RChain.getNode() != Node) {
 907       assert(RVal.getNode() != Node && "Load must be completely replaced");
 908       DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 0), RVal);
 909       DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 1), RChain);
 910       ReplacedNode(Node);
 911     }
 912     return;
 913   }
 914
 915   EVT SrcVT = LD->getMemoryVT();
 916   unsigned SrcWidth = SrcVT.getSizeInBits();
 917   unsigned Alignment = LD->getAlignment();
 918   bool isVolatile = LD->isVolatile();
 919   bool isNonTemporal = LD->isNonTemporal();
 920
 921   if (SrcWidth != SrcVT.getStoreSizeInBits() &&
 922       // Some targets pretend to have an i1 loading operation, and actually
 923       // load an i8.  This trick is correct for ZEXTLOAD because the top 7
 924       // bits are guaranteed to be zero; it helps the optimizers understand
 925       // that these bits are zero.  It is also useful for EXTLOAD, since it
 926       // tells the optimizers that those bits are undefined.  It would be
 927       // nice to have an effective generic way of getting these benefits...
 928       // Until such a way is found, don't insist on promoting i1 here.
 929       (SrcVT != MVT::i1 ||
 930        TLI.getLoadExtAction(ExtType, MVT::i1) == TargetLowering::Promote)) {
 931     // Promote to a byte-sized load if not loading an integral number of
 932     // bytes.  For example, promote EXTLOAD:i20 -> EXTLOAD:i24.
 933     unsigned NewWidth = SrcVT.getStoreSizeInBits();
 934     EVT NVT = EVT::getIntegerVT(*DAG.getContext(), NewWidth);
 935     SDValue Ch;
 936
 937     // The extra bits are guaranteed to be zero, since we stored them that
 938     // way.  A zext load from NVT thus automatically gives zext from SrcVT.
 939
 940     ISD::LoadExtType NewExtType =
 941       ExtType == ISD::ZEXTLOAD ? ISD::ZEXTLOAD : ISD::EXTLOAD;
 942
 943     SDValue Result =
 944       DAG.getExtLoad(NewExtType, dl, Node->getValueType(0),
 945                      Chain, Ptr, LD->getPointerInfo(),
 946                      NVT, isVolatile, isNonTemporal, Alignment);
 947
 948     Ch = Result.getValue(1); // The chain.
 949
 950     if (ExtType == ISD::SEXTLOAD)
 951       // Having the top bits zero doesn't help when sign extending.
 952       Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl,
 953                            Result.getValueType(),
 954                            Result, DAG.getValueType(SrcVT));
 955     else if (ExtType == ISD::ZEXTLOAD || NVT == Result.getValueType())
 956       // All the top bits are guaranteed to be zero - inform the optimizers.
 957       Result = DAG.getNode(ISD::AssertZext, dl,
 958                            Result.getValueType(), Result,
 959                            DAG.getValueType(SrcVT));
 960
 961     Value = Result;
 962     Chain = Ch;
 963   } else if (SrcWidth & (SrcWidth - 1)) {
 964     // If not loading a power-of-2 number of bits, expand as two loads.
 965     assert(!SrcVT.isVector() && "Unsupported extload!");
 966     unsigned RoundWidth = 1 << Log2_32(SrcWidth);
 967     assert(RoundWidth < SrcWidth);
 968     unsigned ExtraWidth = SrcWidth - RoundWidth;
 969     assert(ExtraWidth < RoundWidth);
 970     assert(!(RoundWidth % 8) && !(ExtraWidth % 8) &&
 971            "Load size not an integral number of bytes!");
 972     EVT RoundVT = EVT::getIntegerVT(*DAG.getContext(), RoundWidth);
 973     EVT ExtraVT = EVT::getIntegerVT(*DAG.getContext(), ExtraWidth);
 974     SDValue Lo, Hi, Ch;
 975     unsigned IncrementSize;
 976
 977     if (TLI.isLittleEndian()) {
 978       // EXTLOAD:i24 -> ZEXTLOAD:i16 | (shl EXTLOAD@+2:i8, 16)
 979       // Load the bottom RoundWidth bits.
 980       Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, Node->getValueType(0),
 981                           Chain, Ptr,
 982                           LD->getPointerInfo(), RoundVT, isVolatile,
 983                           isNonTemporal, Alignment);
 984
 985       // Load the remaining ExtraWidth bits.
 986       IncrementSize = RoundWidth / 8;
 987       Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 988                          DAG.getIntPtrConstant(IncrementSize));
 989       Hi = DAG.getExtLoad(ExtType, dl, Node->getValueType(0), Chain, Ptr,
 990                           LD->getPointerInfo().getWithOffset(IncrementSize),
 991                           ExtraVT, isVolatile, isNonTemporal,
 992                           MinAlign(Alignment, IncrementSize));
 993
 994       // Build a factor node to remember that this load is independent of
 995       // the other one.
 996       Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
 997                        Hi.getValue(1));
 998
 999       // Move the top bits to the right place.
1000       Hi = DAG.getNode(ISD::SHL, dl, Hi.getValueType(), Hi,
1001                        DAG.getConstant(RoundWidth,
1002                                        TLI.getShiftAmountTy(Hi.getValueType())));
1003
1004       // Join the hi and lo parts.
1005       Value = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi);
1006     } else {
1007       // Big endian - avoid unaligned loads.
1008       // EXTLOAD:i24 -> (shl EXTLOAD:i16, 8) | ZEXTLOAD@+2:i8
1009       // Load the top RoundWidth bits.
1010       Hi = DAG.getExtLoad(ExtType, dl, Node->getValueType(0), Chain, Ptr,
1011                           LD->getPointerInfo(), RoundVT, isVolatile,
1012                           isNonTemporal, Alignment);
1013
1014       // Load the remaining ExtraWidth bits.
1015       IncrementSize = RoundWidth / 8;
1016       Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
1017                          DAG.getIntPtrConstant(IncrementSize));
1018       Lo = DAG.getExtLoad(ISD::ZEXTLOAD,
1019                           dl, Node->getValueType(0), Chain, Ptr,
1020                           LD->getPointerInfo().getWithOffset(IncrementSize),
1021                           ExtraVT, isVolatile, isNonTemporal,
1022                           MinAlign(Alignment, IncrementSize));
1023
1024       // Build a factor node to remember that this load is independent of
1025       // the other one.
1026       Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1027                        Hi.getValue(1));
1028
1029       // Move the top bits to the right place.
1030       Hi = DAG.getNode(ISD::SHL, dl, Hi.getValueType(), Hi,
1031                        DAG.getConstant(ExtraWidth,
1032                                        TLI.getShiftAmountTy(Hi.getValueType())));
1033
1034       // Join the hi and lo parts.
1035       Value = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi);
1036     }
1037
1038     Chain = Ch;
1039   } else {
1040     bool isCustom = false;
1041     switch (TLI.getLoadExtAction(ExtType, SrcVT.getSimpleVT())) {
1042     default: llvm_unreachable("This action is not supported yet!");
1043     case TargetLowering::Custom:
1044              isCustom = true;
1045              // FALLTHROUGH
1046     case TargetLowering::Legal: {
1047              Value = SDValue(Node, 0);
1048              Chain = SDValue(Node, 1);
1049
1050              if (isCustom) {
1051                SDValue Res = TLI.LowerOperation(SDValue(Node, 0), DAG);
1052                if (Res.getNode()) {
1053                  Value = Res;
1054                  Chain = Res.getValue(1);
1055                }
1056              } else {
1057                // If this is an unaligned load and the target doesn't support it,
1058                // expand it.
1059                if (!TLI.allowsUnalignedMemoryAccesses(LD->getMemoryVT())) {
1060                  Type *Ty =
1061                    LD->getMemoryVT().getTypeForEVT(*DAG.getContext());
1062                  unsigned ABIAlignment =
1063                    TLI.getDataLayout()->getABITypeAlignment(Ty);
1064                  if (LD->getAlignment() < ABIAlignment){
1065                    ExpandUnalignedLoad(cast<LoadSDNode>(Node),
1066                                        DAG, TLI, Value, Chain);
1067                  }
1068                }
1069              }
1070              break;
1071     }
1072     case TargetLowering::Expand:
1073              if (!TLI.isLoadExtLegal(ISD::EXTLOAD, SrcVT) && TLI.isTypeLegal(SrcVT)) {
1074                SDValue Load = DAG.getLoad(SrcVT, dl, Chain, Ptr,
1075                                           LD->getPointerInfo(),
1076                                           LD->isVolatile(), LD->isNonTemporal(),
1077                                           LD->isInvariant(), LD->getAlignment());
1078                unsigned ExtendOp;
1079                switch (ExtType) {
1080                case ISD::EXTLOAD:
1081                  ExtendOp = (SrcVT.isFloatingPoint() ?
1082                              ISD::FP_EXTEND : ISD::ANY_EXTEND);
1083                  break;
1084                case ISD::SEXTLOAD: ExtendOp = ISD::SIGN_EXTEND; break;
1085                case ISD::ZEXTLOAD: ExtendOp = ISD::ZERO_EXTEND; break;
1086                default: llvm_unreachable("Unexpected extend load type!");
1087                }
1088                Value = DAG.getNode(ExtendOp, dl, Node->getValueType(0), Load);
1089                Chain = Load.getValue(1);
1090                break;
1091              }
1092
1093              assert(!SrcVT.isVector() &&
1094                     "Vector Loads are handled in LegalizeVectorOps");
1095
1096              // FIXME: This does not work for vectors on most targets.  Sign- and
1097              // zero-extend operations are currently folded into extending loads,
1098              // whether they are legal or not, and then we end up here without any
1099              // support for legalizing them.
1100              assert(ExtType != ISD::EXTLOAD &&
1101                     "EXTLOAD should always be supported!");
1102              // Turn the unsupported load into an EXTLOAD followed by an explicit
1103              // zero/sign extend inreg.
1104              SDValue Result = DAG.getExtLoad(ISD::EXTLOAD, dl, Node->getValueType(0),
1105                                              Chain, Ptr, LD->getPointerInfo(), SrcVT,
1106                                              LD->isVolatile(), LD->isNonTemporal(),
1107                                              LD->getAlignment());
1108              SDValue ValRes;
1109              if (ExtType == ISD::SEXTLOAD)
1110                ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl,
1111                                     Result.getValueType(),
1112                                     Result, DAG.getValueType(SrcVT));
1113              else
1114                ValRes = DAG.getZeroExtendInReg(Result, dl, SrcVT.getScalarType());
1115              Value = ValRes;
1116              Chain = Result.getValue(1);
1117              break;
1118     }
1119   }
1120
1121   // Since loads produce two values, make sure to remember that we legalized
1122   // both of them.
1123   if (Chain.getNode() != Node) {
1124     assert(Value.getNode() != Node && "Load must be completely replaced");
1125     DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 0), Value);
1126     DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 1), Chain);
1127     ReplacedNode(Node);
1128   }
1129 }
1130
1131 /// LegalizeOp - Return a legal replacement for the given operation, with
1132 /// all legal operands.
1133 void SelectionDAGLegalize::LegalizeOp(SDNode *Node) {
1134   if (Node->getOpcode() == ISD::TargetConstant) // Allow illegal target nodes.
1135     return;
1136
1137   for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
1138     assert(TLI.getTypeAction(*DAG.getContext(), Node->getValueType(i)) ==
1139              TargetLowering::TypeLegal &&
1140            "Unexpected illegal type!");
1141
1142   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1143     assert((TLI.getTypeAction(*DAG.getContext(),
1144                               Node->getOperand(i).getValueType()) ==
1145               TargetLowering::TypeLegal ||
1146             Node->getOperand(i).getOpcode() == ISD::TargetConstant) &&
1147            "Unexpected illegal type!");
1148
1149   // Figure out the correct action; the way to query this varies by opcode
1150   TargetLowering::LegalizeAction Action = TargetLowering::Legal;
1151   bool SimpleFinishLegalizing = true;
1152   switch (Node->getOpcode()) {
1153   case ISD::INTRINSIC_W_CHAIN:
1154   case ISD::INTRINSIC_WO_CHAIN:
1155   case ISD::INTRINSIC_VOID:
1156   case ISD::STACKSAVE:
1157     Action = TLI.getOperationAction(Node->getOpcode(), MVT::Other);
1158     break;
1159   case ISD::VAARG:
1160     Action = TLI.getOperationAction(Node->getOpcode(),
1161                                     Node->getValueType(0));
1162     if (Action != TargetLowering::Promote)
1163       Action = TLI.getOperationAction(Node->getOpcode(), MVT::Other);
1164     break;
1165   case ISD::SINT_TO_FP:
1166   case ISD::UINT_TO_FP:
1167   case ISD::EXTRACT_VECTOR_ELT:
1168     Action = TLI.getOperationAction(Node->getOpcode(),
1169                                     Node->getOperand(0).getValueType());
1170     break;
1171   case ISD::FP_ROUND_INREG:
1172   case ISD::SIGN_EXTEND_INREG: {
1173     EVT InnerType = cast<VTSDNode>(Node->getOperand(1))->getVT();
1174     Action = TLI.getOperationAction(Node->getOpcode(), InnerType);
1175     break;
1176   }
1177   case ISD::ATOMIC_STORE: {
1178     Action = TLI.getOperationAction(Node->getOpcode(),
1179                                     Node->getOperand(2).getValueType());
1180     break;
1181   }
1182   case ISD::SELECT_CC:
1183   case ISD::SETCC:
1184   case ISD::BR_CC: {
1185     unsigned CCOperand = Node->getOpcode() == ISD::SELECT_CC ? 4 :
1186                          Node->getOpcode() == ISD::SETCC ? 2 : 1;
1187     unsigned CompareOperand = Node->getOpcode() == ISD::BR_CC ? 2 : 0;
1188     MVT OpVT = Node->getOperand(CompareOperand).getSimpleValueType();
1189     ISD::CondCode CCCode =
1190         cast<CondCodeSDNode>(Node->getOperand(CCOperand))->get();
1191     Action = TLI.getCondCodeAction(CCCode, OpVT);
1192     if (Action == TargetLowering::Legal) {
1193       if (Node->getOpcode() == ISD::SELECT_CC)
1194         Action = TLI.getOperationAction(Node->getOpcode(),
1195                                         Node->getValueType(0));
1196       else
1197         Action = TLI.getOperationAction(Node->getOpcode(), OpVT);
1198     }
1199     break;
1200   }
1201   case ISD::LOAD:
1202   case ISD::STORE:
1203     // FIXME: Model these properly.  LOAD and STORE are complicated, and
1204     // STORE expects the unlegalized operand in some cases.
1205     SimpleFinishLegalizing = false;
1206     break;
1207   case ISD::CALLSEQ_START:
1208   case ISD::CALLSEQ_END:
1209     // FIXME: This shouldn't be necessary.  These nodes have special properties
1210     // dealing with the recursive nature of legalization.  Removing this
1211     // special case should be done as part of making LegalizeDAG non-recursive.
1212     SimpleFinishLegalizing = false;
1213     break;
1214   case ISD::EXTRACT_ELEMENT:
1215   case ISD::FLT_ROUNDS_:
1216   case ISD::SADDO:
1217   case ISD::SSUBO:
1218   case ISD::UADDO:
1219   case ISD::USUBO:
1220   case ISD::SMULO:
1221   case ISD::UMULO:
1222   case ISD::FPOWI:
1223   case ISD::MERGE_VALUES:
1224   case ISD::EH_RETURN:
1225   case ISD::FRAME_TO_ARGS_OFFSET:
1226   case ISD::EH_SJLJ_SETJMP:
1227   case ISD::EH_SJLJ_LONGJMP:
1228     // These operations lie about being legal: when they claim to be legal,
1229     // they should actually be expanded.
1230     Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
1231     if (Action == TargetLowering::Legal)
1232       Action = TargetLowering::Expand;
1233     break;
1234   case ISD::INIT_TRAMPOLINE:
1235   case ISD::ADJUST_TRAMPOLINE:
1236   case ISD::FRAMEADDR:
1237   case ISD::RETURNADDR:
1238     // These operations lie about being legal: when they claim to be legal,
1239     // they should actually be custom-lowered.
1240     Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
1241     if (Action == TargetLowering::Legal)
1242       Action = TargetLowering::Custom;
1243     break;
1244   case ISD::DEBUGTRAP:
1245     Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
1246     if (Action == TargetLowering::Expand) {
1247       // replace ISD::DEBUGTRAP with ISD::TRAP
1248       SDValue NewVal;
1249       NewVal = DAG.getNode(ISD::TRAP, Node->getDebugLoc(), Node->getVTList(),
1250                            Node->getOperand(0));
1251       ReplaceNode(Node, NewVal.getNode());
1252       LegalizeOp(NewVal.getNode());
1253       return;
1254     }
1255     break;
1256
1257   default:
1258     if (Node->getOpcode() >= ISD::BUILTIN_OP_END) {
1259       Action = TargetLowering::Legal;
1260     } else {
1261       Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
1262     }
1263     break;
1264   }
1265
1266   if (SimpleFinishLegalizing) {
1267     SDNode *NewNode = Node;
1268     switch (Node->getOpcode()) {
1269     default: break;
1270     case ISD::SHL:
1271     case ISD::SRL:
1272     case ISD::SRA:
1273     case ISD::ROTL:
1274     case ISD::ROTR:
1275       // Legalizing shifts/rotates requires adjusting the shift amount
1276       // to the appropriate width.
1277       if (!Node->getOperand(1).getValueType().isVector()) {
1278         SDValue SAO =
1279           DAG.getShiftAmountOperand(Node->getOperand(0).getValueType(),
1280                                     Node->getOperand(1));
1281         HandleSDNode Handle(SAO);
1282         LegalizeOp(SAO.getNode());
1283         NewNode = DAG.UpdateNodeOperands(Node, Node->getOperand(0),
1284                                          Handle.getValue());
1285       }
1286       break;
1287     case ISD::SRL_PARTS:
1288     case ISD::SRA_PARTS:
1289     case ISD::SHL_PARTS:
1290       // Legalizing shifts/rotates requires adjusting the shift amount
1291       // to the appropriate width.
1292       if (!Node->getOperand(2).getValueType().isVector()) {
1293         SDValue SAO =
1294           DAG.getShiftAmountOperand(Node->getOperand(0).getValueType(),
1295                                     Node->getOperand(2));
1296         HandleSDNode Handle(SAO);
1297         LegalizeOp(SAO.getNode());
1298         NewNode = DAG.UpdateNodeOperands(Node, Node->getOperand(0),
1299                                          Node->getOperand(1),
1300                                          Handle.getValue());
1301       }
1302       break;
1303     }
1304
1305     if (NewNode != Node) {
1306       DAG.ReplaceAllUsesWith(Node, NewNode);
1307       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
1308         DAG.TransferDbgValues(SDValue(Node, i), SDValue(NewNode, i));
1309       ReplacedNode(Node);
1310       Node = NewNode;
1311     }
1312     switch (Action) {
1313     case TargetLowering::Legal:
1314       return;
1315     case TargetLowering::Custom: {
1316       // FIXME: The handling for custom lowering with multiple results is
1317       // a complete mess.
1318       SDValue Res = TLI.LowerOperation(SDValue(Node, 0), DAG);
1319       if (Res.getNode()) {
1320         SmallVector<SDValue, 8> ResultVals;
1321         for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) {
1322           if (e == 1)
1323             ResultVals.push_back(Res);
1324           else
1325             ResultVals.push_back(Res.getValue(i));
1326         }
1327         if (Res.getNode() != Node || Res.getResNo() != 0) {
1328           DAG.ReplaceAllUsesWith(Node, ResultVals.data());
1329           for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
1330             DAG.TransferDbgValues(SDValue(Node, i), ResultVals[i]);
1331           ReplacedNode(Node);
1332         }
1333         return;
1334       }
1335     }
1336       // FALL THROUGH
1337     case TargetLowering::Expand:
1338       ExpandNode(Node);
1339       return;
1340     case TargetLowering::Promote:
1341       PromoteNode(Node);
1342       return;
1343     }
1344   }
1345
1346   switch (Node->getOpcode()) {
1347   default:
1348 #ifndef NDEBUG
1349     dbgs() << "NODE: ";
1350     Node->dump( &DAG);
1351     dbgs() << "\n";
1352 #endif
1353     llvm_unreachable("Do not know how to legalize this operator!");
1354
1355   case ISD::CALLSEQ_START:
1356   case ISD::CALLSEQ_END:
1357     break;
1358   case ISD::LOAD: {
1359     return LegalizeLoadOps(Node);
1360   }
1361   case ISD::STORE: {
1362     return LegalizeStoreOps(Node);
1363   }
1364   }
1365 }
1366
1367 SDValue SelectionDAGLegalize::ExpandExtractFromVectorThroughStack(SDValue Op) {
1368   SDValue Vec = Op.getOperand(0);
1369   SDValue Idx = Op.getOperand(1);
1370   DebugLoc dl = Op.getDebugLoc();
1371   // Store the value to a temporary stack slot, then LOAD the returned part.
1372   SDValue StackPtr = DAG.CreateStackTemporary(Vec.getValueType());
1373   SDValue Ch = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr,
1374                             MachinePointerInfo(), false, false, 0);
1375
1376   // Add the offset to the index.
1377   unsigned EltSize =
1378       Vec.getValueType().getVectorElementType().getSizeInBits()/8;
1379   Idx = DAG.getNode(ISD::MUL, dl, Idx.getValueType(), Idx,
1380                     DAG.getConstant(EltSize, Idx.getValueType()));
1381
1382   if (Idx.getValueType().bitsGT(TLI.getPointerTy()))
1383     Idx = DAG.getNode(ISD::TRUNCATE, dl, TLI.getPointerTy(), Idx);
1384   else
1385     Idx = DAG.getNode(ISD::ZERO_EXTEND, dl, TLI.getPointerTy(), Idx);
1386
1387   StackPtr = DAG.getNode(ISD::ADD, dl, Idx.getValueType(), Idx, StackPtr);
1388
1389   if (Op.getValueType().isVector())
1390     return DAG.getLoad(Op.getValueType(), dl, Ch, StackPtr,MachinePointerInfo(),
1391                        false, false, false, 0);
1392   return DAG.getExtLoad(ISD::EXTLOAD, dl, Op.getValueType(), Ch, StackPtr,
1393                         MachinePointerInfo(),
1394                         Vec.getValueType().getVectorElementType(),
1395                         false, false, 0);
1396 }
1397
1398 SDValue SelectionDAGLegalize::ExpandInsertToVectorThroughStack(SDValue Op) {
1399   assert(Op.getValueType().isVector() && "Non-vector insert subvector!");
1400
1401   SDValue Vec  = Op.getOperand(0);
1402   SDValue Part = Op.getOperand(1);
1403   SDValue Idx  = Op.getOperand(2);
1404   DebugLoc dl  = Op.getDebugLoc();
1405
1406   // Store the value to a temporary stack slot, then LOAD the returned part.
1407
1408   SDValue StackPtr = DAG.CreateStackTemporary(Vec.getValueType());
1409   int FI = cast<FrameIndexSDNode>(StackPtr.getNode())->getIndex();
1410   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(FI);
1411
1412   // First store the whole vector.
1413   SDValue Ch = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr, PtrInfo,
1414                             false, false, 0);
1415
1416   // Then store the inserted part.
1417
1418   // Add the offset to the index.
1419   unsigned EltSize =
1420       Vec.getValueType().getVectorElementType().getSizeInBits()/8;
1421
1422   Idx = DAG.getNode(ISD::MUL, dl, Idx.getValueType(), Idx,
1423                     DAG.getConstant(EltSize, Idx.getValueType()));
1424
1425   if (Idx.getValueType().bitsGT(TLI.getPointerTy()))
1426     Idx = DAG.getNode(ISD::TRUNCATE, dl, TLI.getPointerTy(), Idx);
1427   else
1428     Idx = DAG.getNode(ISD::ZERO_EXTEND, dl, TLI.getPointerTy(), Idx);
1429
1430   SDValue SubStackPtr = DAG.getNode(ISD::ADD, dl, Idx.getValueType(), Idx,
1431                                     StackPtr);
1432
1433   // Store the subvector.
1434   Ch = DAG.getStore(DAG.getEntryNode(), dl, Part, SubStackPtr,
1435                     MachinePointerInfo(), false, false, 0);
1436
1437   // Finally, load the updated vector.
1438   return DAG.getLoad(Op.getValueType(), dl, Ch, StackPtr, PtrInfo,
1439                      false, false, false, 0);
1440 }
1441
1442 SDValue SelectionDAGLegalize::ExpandVectorBuildThroughStack(SDNode* Node) {
1443   // We can't handle this case efficiently.  Allocate a sufficiently
1444   // aligned object on the stack, store each element into it, then load
1445   // the result as a vector.
1446   // Create the stack frame object.
1447   EVT VT = Node->getValueType(0);
1448   EVT EltVT = VT.getVectorElementType();
1449   DebugLoc dl = Node->getDebugLoc();
1450   SDValue FIPtr = DAG.CreateStackTemporary(VT);
1451   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
1452   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(FI);
1453
1454   // Emit a store of each element to the stack slot.
1455   SmallVector<SDValue, 8> Stores;
1456   unsigned TypeByteSize = EltVT.getSizeInBits() / 8;
1457   // Store (in the right endianness) the elements to memory.
1458   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
1459     // Ignore undef elements.
1460     if (Node->getOperand(i).getOpcode() == ISD::UNDEF) continue;
1461
1462     unsigned Offset = TypeByteSize*i;
1463
1464     SDValue Idx = DAG.getConstant(Offset, FIPtr.getValueType());
1465     Idx = DAG.getNode(ISD::ADD, dl, FIPtr.getValueType(), FIPtr, Idx);
1466
1467     // If the destination vector element type is narrower than the source
1468     // element type, only store the bits necessary.
1469     if (EltVT.bitsLT(Node->getOperand(i).getValueType().getScalarType())) {
1470       Stores.push_back(DAG.getTruncStore(DAG.getEntryNode(), dl,
1471                                          Node->getOperand(i), Idx,
1472                                          PtrInfo.getWithOffset(Offset),
1473                                          EltVT, false, false, 0));
1474     } else
1475       Stores.push_back(DAG.getStore(DAG.getEntryNode(), dl,
1476                                     Node->getOperand(i), Idx,
1477                                     PtrInfo.getWithOffset(Offset),
1478                                     false, false, 0));
1479   }
1480
1481   SDValue StoreChain;
1482   if (!Stores.empty())    // Not all undef elements?
1483     StoreChain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
1484                              &Stores[0], Stores.size());
1485   else
1486     StoreChain = DAG.getEntryNode();
1487
1488   // Result is a load from the stack slot.
1489   return DAG.getLoad(VT, dl, StoreChain, FIPtr, PtrInfo,
1490                      false, false, false, 0);
1491 }
1492
1493 SDValue SelectionDAGLegalize::ExpandFCOPYSIGN(SDNode* Node) {
1494   DebugLoc dl = Node->getDebugLoc();
1495   SDValue Tmp1 = Node->getOperand(0);
1496   SDValue Tmp2 = Node->getOperand(1);
1497
1498   // Get the sign bit of the RHS.  First obtain a value that has the same
1499   // sign as the sign bit, i.e. negative if and only if the sign bit is 1.
1500   SDValue SignBit;
1501   EVT FloatVT = Tmp2.getValueType();
1502   EVT IVT = EVT::getIntegerVT(*DAG.getContext(), FloatVT.getSizeInBits());
1503   if (TLI.isTypeLegal(IVT)) {
1504     // Convert to an integer with the same sign bit.
1505     SignBit = DAG.getNode(ISD::BITCAST, dl, IVT, Tmp2);
1506   } else {
1507     // Store the float to memory, then load the sign part out as an integer.
1508     MVT LoadTy = TLI.getPointerTy();
1509     // First create a temporary that is aligned for both the load and store.
1510     SDValue StackPtr = DAG.CreateStackTemporary(FloatVT, LoadTy);
1511     // Then store the float to it.
1512     SDValue Ch =
1513       DAG.getStore(DAG.getEntryNode(), dl, Tmp2, StackPtr, MachinePointerInfo(),
1514                    false, false, 0);
1515     if (TLI.isBigEndian()) {
1516       assert(FloatVT.isByteSized() && "Unsupported floating point type!");
1517       // Load out a legal integer with the same sign bit as the float.
1518       SignBit = DAG.getLoad(LoadTy, dl, Ch, StackPtr, MachinePointerInfo(),
1519                             false, false, false, 0);
1520     } else { // Little endian
1521       SDValue LoadPtr = StackPtr;
1522       // The float may be wider than the integer we are going to load.  Advance
1523       // the pointer so that the loaded integer will contain the sign bit.
1524       unsigned Strides = (FloatVT.getSizeInBits()-1)/LoadTy.getSizeInBits();
1525       unsigned ByteOffset = (Strides * LoadTy.getSizeInBits()) / 8;
1526       LoadPtr = DAG.getNode(ISD::ADD, dl, LoadPtr.getValueType(),
1527                             LoadPtr, DAG.getIntPtrConstant(ByteOffset));
1528       // Load a legal integer containing the sign bit.
1529       SignBit = DAG.getLoad(LoadTy, dl, Ch, LoadPtr, MachinePointerInfo(),
1530                             false, false, false, 0);
1531       // Move the sign bit to the top bit of the loaded integer.
1532       unsigned BitShift = LoadTy.getSizeInBits() -
1533         (FloatVT.getSizeInBits() - 8 * ByteOffset);
1534       assert(BitShift < LoadTy.getSizeInBits() && "Pointer advanced wrong?");
1535       if (BitShift)
1536         SignBit = DAG.getNode(ISD::SHL, dl, LoadTy, SignBit,
1537                               DAG.getConstant(BitShift,
1538                                  TLI.getShiftAmountTy(SignBit.getValueType())));
1539     }
1540   }
1541   // Now get the sign bit proper, by seeing whether the value is negative.
1542   SignBit = DAG.getSetCC(dl, TLI.getSetCCResultType(SignBit.getValueType()),
1543                          SignBit, DAG.getConstant(0, SignBit.getValueType()),
1544                          ISD::SETLT);
1545   // Get the absolute value of the result.
1546   SDValue AbsVal = DAG.getNode(ISD::FABS, dl, Tmp1.getValueType(), Tmp1);
1547   // Select between the nabs and abs value based on the sign bit of
1548   // the input.
1549   return DAG.getNode(ISD::SELECT, dl, AbsVal.getValueType(), SignBit,
1550                      DAG.getNode(ISD::FNEG, dl, AbsVal.getValueType(), AbsVal),
1551                      AbsVal);
1552 }
1553
1554 void SelectionDAGLegalize::ExpandDYNAMIC_STACKALLOC(SDNode* Node,
1555                                            SmallVectorImpl<SDValue> &Results) {
1556   unsigned SPReg = TLI.getStackPointerRegisterToSaveRestore();
1557   assert(SPReg && "Target cannot require DYNAMIC_STACKALLOC expansion and"
1558           " not tell us which reg is the stack pointer!");
1559   DebugLoc dl = Node->getDebugLoc();
1560   EVT VT = Node->getValueType(0);
1561   SDValue Tmp1 = SDValue(Node, 0);
1562   SDValue Tmp2 = SDValue(Node, 1);
1563   SDValue Tmp3 = Node->getOperand(2);
1564   SDValue Chain = Tmp1.getOperand(0);
1565
1566   // Chain the dynamic stack allocation so that it doesn't modify the stack
1567   // pointer when other instructions are using the stack.
1568   Chain = DAG.getCALLSEQ_START(Chain, DAG.getIntPtrConstant(0, true));
1569
1570   SDValue Size  = Tmp2.getOperand(1);
1571   SDValue SP = DAG.getCopyFromReg(Chain, dl, SPReg, VT);
1572   Chain = SP.getValue(1);
1573   unsigned Align = cast<ConstantSDNode>(Tmp3)->getZExtValue();
1574   unsigned StackAlign = TM.getFrameLowering()->getStackAlignment();
1575   if (Align > StackAlign)
1576     SP = DAG.getNode(ISD::AND, dl, VT, SP,
1577                       DAG.getConstant(-(uint64_t)Align, VT));
1578   Tmp1 = DAG.getNode(ISD::SUB, dl, VT, SP, Size);       // Value
1579   Chain = DAG.getCopyToReg(Chain, dl, SPReg, Tmp1);     // Output chain
1580
1581   Tmp2 = DAG.getCALLSEQ_END(Chain,  DAG.getIntPtrConstant(0, true),
1582                             DAG.getIntPtrConstant(0, true), SDValue());
1583
1584   Results.push_back(Tmp1);
1585   Results.push_back(Tmp2);
1586 }
1587
1588 /// LegalizeSetCCCondCode - Legalize a SETCC with given LHS and RHS and
1589 /// condition code CC on the current target. This routine expands SETCC with
1590 /// illegal condition code into AND / OR of multiple SETCC values.
1591 void SelectionDAGLegalize::LegalizeSetCCCondCode(EVT VT,
1592                                                  SDValue &LHS, SDValue &RHS,
1593                                                  SDValue &CC,
1594                                                  DebugLoc dl) {
1595   MVT OpVT = LHS.getSimpleValueType();
1596   ISD::CondCode CCCode = cast<CondCodeSDNode>(CC)->get();
1597   switch (TLI.getCondCodeAction(CCCode, OpVT)) {
1598   default: llvm_unreachable("Unknown condition code action!");
1599   case TargetLowering::Legal:
1600     // Nothing to do.
1601     break;
1602   case TargetLowering::Expand: {
1603     ISD::CondCode CC1 = ISD::SETCC_INVALID, CC2 = ISD::SETCC_INVALID;
1604     ISD::CondCode InvCC = ISD::SETCC_INVALID;
1605     unsigned Opc = 0;
1606     switch (CCCode) {
1607     default: llvm_unreachable("Don't know how to expand this condition!");
1608     case ISD::SETO:
1609         assert(TLI.getCondCodeAction(ISD::SETOEQ, OpVT)
1610             == TargetLowering::Legal
1611             && "If SETO is expanded, SETOEQ must be legal!");
1612         CC1 = ISD::SETOEQ; CC2 = ISD::SETOEQ; Opc = ISD::AND; break;
1613     case ISD::SETUO:
1614         assert(TLI.getCondCodeAction(ISD::SETUNE, OpVT)
1615             == TargetLowering::Legal
1616             && "If SETUO is expanded, SETUNE must be legal!");
1617         CC1 = ISD::SETUNE; CC2 = ISD::SETUNE; Opc = ISD::OR;  break;
1618     case ISD::SETOEQ:
1619     case ISD::SETOGT:
1620     case ISD::SETOGE:
1621     case ISD::SETOLT:
1622     case ISD::SETOLE:
1623     case ISD::SETONE:
1624     case ISD::SETUEQ:
1625     case ISD::SETUNE:
1626     case ISD::SETUGT:
1627     case ISD::SETUGE:
1628     case ISD::SETULT:
1629     case ISD::SETULE:
1630         // If we are floating point, assign and break, otherwise fall through.
1631         if (!OpVT.isInteger()) {
1632           // We can use the 4th bit to tell if we are the unordered
1633           // or ordered version of the opcode.
1634           CC2 = ((unsigned)CCCode & 0x8U) ? ISD::SETUO : ISD::SETO;
1635           Opc = ((unsigned)CCCode & 0x8U) ? ISD::OR : ISD::AND;
1636           CC1 = (ISD::CondCode)(((int)CCCode & 0x7) | 0x10);
1637           break;
1638         }
1639         // Fallthrough if we are unsigned integer.
1640     case ISD::SETLE:
1641     case ISD::SETGT:
1642     case ISD::SETGE:
1643     case ISD::SETLT:
1644     case ISD::SETNE:
1645     case ISD::SETEQ:
1646       InvCC = ISD::getSetCCSwappedOperands(CCCode);
1647       if (TLI.getCondCodeAction(InvCC, OpVT) == TargetLowering::Expand) {
1648         // We only support using the inverted operation and not a
1649         // different manner of supporting expanding these cases.
1650         llvm_unreachable("Don't know how to expand this condition!");
1651       }
1652       LHS = DAG.getSetCC(dl, VT, RHS, LHS, InvCC);
1653       RHS = SDValue();
1654       CC = SDValue();
1655       return;
1656     }
1657
1658     SDValue SetCC1, SetCC2;
1659     if (CCCode != ISD::SETO && CCCode != ISD::SETUO) {
1660       // If we aren't the ordered or unorder operation,
1661       // then the pattern is (LHS CC1 RHS) Opc (LHS CC2 RHS).
1662       SetCC1 = DAG.getSetCC(dl, VT, LHS, RHS, CC1);
1663       SetCC2 = DAG.getSetCC(dl, VT, LHS, RHS, CC2);
1664     } else {
1665       // Otherwise, the pattern is (LHS CC1 LHS) Opc (RHS CC2 RHS)
1666       SetCC1 = DAG.getSetCC(dl, VT, LHS, LHS, CC1);
1667       SetCC2 = DAG.getSetCC(dl, VT, RHS, RHS, CC2);
1668     }
1669     LHS = DAG.getNode(Opc, dl, VT, SetCC1, SetCC2);
1670     RHS = SDValue();
1671     CC  = SDValue();
1672     break;
1673   }
1674   }
1675 }
1676
1677 /// EmitStackConvert - Emit a store/load combination to the stack.  This stores
1678 /// SrcOp to a stack slot of type SlotVT, truncating it if needed.  It then does
1679 /// a load from the stack slot to DestVT, extending it if needed.
1680 /// The resultant code need not be legal.
1681 SDValue SelectionDAGLegalize::EmitStackConvert(SDValue SrcOp,
1682                                                EVT SlotVT,
1683                                                EVT DestVT,
1684                                                DebugLoc dl) {
1685   // Create the stack frame object.
1686   unsigned SrcAlign =
1687     TLI.getDataLayout()->getPrefTypeAlignment(SrcOp.getValueType().
1688                                               getTypeForEVT(*DAG.getContext()));
1689   SDValue FIPtr = DAG.CreateStackTemporary(SlotVT, SrcAlign);
1690
1691   FrameIndexSDNode *StackPtrFI = cast<FrameIndexSDNode>(FIPtr);
1692   int SPFI = StackPtrFI->getIndex();
1693   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(SPFI);
1694
1695   unsigned SrcSize = SrcOp.getValueType().getSizeInBits();
1696   unsigned SlotSize = SlotVT.getSizeInBits();
1697   unsigned DestSize = DestVT.getSizeInBits();
1698   Type *DestType = DestVT.getTypeForEVT(*DAG.getContext());
1699   unsigned DestAlign = TLI.getDataLayout()->getPrefTypeAlignment(DestType);
1700
1701   // Emit a store to the stack slot.  Use a truncstore if the input value is
1702   // later than DestVT.
1703   SDValue Store;
1704
1705   if (SrcSize > SlotSize)
1706     Store = DAG.getTruncStore(DAG.getEntryNode(), dl, SrcOp, FIPtr,
1707                               PtrInfo, SlotVT, false, false, SrcAlign);
1708   else {
1709     assert(SrcSize == SlotSize && "Invalid store");
1710     Store = DAG.getStore(DAG.getEntryNode(), dl, SrcOp, FIPtr,
1711                          PtrInfo, false, false, SrcAlign);
1712   }
1713
1714   // Result is a load from the stack slot.
1715   if (SlotSize == DestSize)
1716     return DAG.getLoad(DestVT, dl, Store, FIPtr, PtrInfo,
1717                        false, false, false, DestAlign);
1718
1719   assert(SlotSize < DestSize && "Unknown extension!");
1720   return DAG.getExtLoad(ISD::EXTLOAD, dl, DestVT, Store, FIPtr,
1721                         PtrInfo, SlotVT, false, false, DestAlign);
1722 }
1723
1724 SDValue SelectionDAGLegalize::ExpandSCALAR_TO_VECTOR(SDNode *Node) {
1725   DebugLoc dl = Node->getDebugLoc();
1726   // Create a vector sized/aligned stack slot, store the value to element #0,
1727   // then load the whole vector back out.
1728   SDValue StackPtr = DAG.CreateStackTemporary(Node->getValueType(0));
1729
1730   FrameIndexSDNode *StackPtrFI = cast<FrameIndexSDNode>(StackPtr);
1731   int SPFI = StackPtrFI->getIndex();
1732
1733   SDValue Ch = DAG.getTruncStore(DAG.getEntryNode(), dl, Node->getOperand(0),
1734                                  StackPtr,
1735                                  MachinePointerInfo::getFixedStack(SPFI),
1736                                  Node->getValueType(0).getVectorElementType(),
1737                                  false, false, 0);
1738   return DAG.getLoad(Node->getValueType(0), dl, Ch, StackPtr,
1739                      MachinePointerInfo::getFixedStack(SPFI),
1740                      false, false, false, 0);
1741 }
1742
1743
1744 /// ExpandBUILD_VECTOR - Expand a BUILD_VECTOR node on targets that don't
1745 /// support the operation, but do support the resultant vector type.
1746 SDValue SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
1747   unsigned NumElems = Node->getNumOperands();
1748   SDValue Value1, Value2;
1749   DebugLoc dl = Node->getDebugLoc();
1750   EVT VT = Node->getValueType(0);
1751   EVT OpVT = Node->getOperand(0).getValueType();
1752   EVT EltVT = VT.getVectorElementType();
1753
1754   // If the only non-undef value is the low element, turn this into a
1755   // SCALAR_TO_VECTOR node.  If this is { X, X, X, X }, determine X.
1756   bool isOnlyLowElement = true;
1757   bool MoreThanTwoValues = false;
1758   bool isConstant = true;
1759   for (unsigned i = 0; i < NumElems; ++i) {
1760     SDValue V = Node->getOperand(i);
1761     if (V.getOpcode() == ISD::UNDEF)
1762       continue;
1763     if (i > 0)
1764       isOnlyLowElement = false;
1765     if (!isa<ConstantFPSDNode>(V) && !isa<ConstantSDNode>(V))
1766       isConstant = false;
1767
1768     if (!Value1.getNode()) {
1769       Value1 = V;
1770     } else if (!Value2.getNode()) {
1771       if (V != Value1)
1772         Value2 = V;
1773     } else if (V != Value1 && V != Value2) {
1774       MoreThanTwoValues = true;
1775     }
1776   }
1777
1778   if (!Value1.getNode())
1779     return DAG.getUNDEF(VT);
1780
1781   if (isOnlyLowElement)
1782     return DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Node->getOperand(0));
1783
1784   // If all elements are constants, create a load from the constant pool.
1785   if (isConstant) {
1786     SmallVector<Constant*, 16> CV;
1787     for (unsigned i = 0, e = NumElems; i != e; ++i) {
1788       if (ConstantFPSDNode *V =
1789           dyn_cast<ConstantFPSDNode>(Node->getOperand(i))) {
1790         CV.push_back(const_cast<ConstantFP *>(V->getConstantFPValue()));
1791       } else if (ConstantSDNode *V =
1792                  dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
1793         if (OpVT==EltVT)
1794           CV.push_back(const_cast<ConstantInt *>(V->getConstantIntValue()));
1795         else {
1796           // If OpVT and EltVT don't match, EltVT is not legal and the
1797           // element values have been promoted/truncated earlier.  Undo this;
1798           // we don't want a v16i8 to become a v16i32 for example.
1799           const ConstantInt *CI = V->getConstantIntValue();
1800           CV.push_back(ConstantInt::get(EltVT.getTypeForEVT(*DAG.getContext()),
1801                                         CI->getZExtValue()));
1802         }
1803       } else {
1804         assert(Node->getOperand(i).getOpcode() == ISD::UNDEF);
1805         Type *OpNTy = EltVT.getTypeForEVT(*DAG.getContext());
1806         CV.push_back(UndefValue::get(OpNTy));
1807       }
1808     }
1809     Constant *CP = ConstantVector::get(CV);
1810     SDValue CPIdx = DAG.getConstantPool(CP, TLI.getPointerTy());
1811     unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment();
1812     return DAG.getLoad(VT, dl, DAG.getEntryNode(), CPIdx,
1813                        MachinePointerInfo::getConstantPool(),
1814                        false, false, false, Alignment);
1815   }
1816
1817   if (!MoreThanTwoValues) {
1818     SmallVector<int, 8> ShuffleVec(NumElems, -1);
1819     for (unsigned i = 0; i < NumElems; ++i) {
1820       SDValue V = Node->getOperand(i);
1821       if (V.getOpcode() == ISD::UNDEF)
1822         continue;
1823       ShuffleVec[i] = V == Value1 ? 0 : NumElems;
1824     }
1825     if (TLI.isShuffleMaskLegal(ShuffleVec, Node->getValueType(0))) {
1826       // Get the splatted value into the low element of a vector register.
1827       SDValue Vec1 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Value1);
1828       SDValue Vec2;
1829       if (Value2.getNode())
1830         Vec2 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Value2);
1831       else
1832         Vec2 = DAG.getUNDEF(VT);
1833
1834       // Return shuffle(LowValVec, undef, <0,0,0,0>)
1835       return DAG.getVectorShuffle(VT, dl, Vec1, Vec2, ShuffleVec.data());
1836     }
1837   }
1838
1839   // Otherwise, we can't handle this case efficiently.
1840   return ExpandVectorBuildThroughStack(Node);
1841 }
1842
1843 // ExpandLibCall - Expand a node into a call to a libcall.  If the result value
1844 // does not fit into a register, return the lo part and set the hi part to the
1845 // by-reg argument.  If it does fit into a single register, return the result
1846 // and leave the Hi part unset.
1847 SDValue SelectionDAGLegalize::ExpandLibCall(RTLIB::Libcall LC, SDNode *Node,
1848                                             bool isSigned) {
1849   TargetLowering::ArgListTy Args;
1850   TargetLowering::ArgListEntry Entry;
1851   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
1852     EVT ArgVT = Node->getOperand(i).getValueType();
1853     Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
1854     Entry.Node = Node->getOperand(i); Entry.Ty = ArgTy;
1855     Entry.isSExt = isSigned;
1856     Entry.isZExt = !isSigned;
1857     Args.push_back(Entry);
1858   }
1859   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
1860                                          TLI.getPointerTy());
1861
1862   Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext());
1863
1864   // By default, the input chain to this libcall is the entry node of the
1865   // function. If the libcall is going to be emitted as a tail call then
1866   // TLI.isUsedByReturnOnly will change it to the right chain if the return
1867   // node which is being folded has a non-entry input chain.
1868   SDValue InChain = DAG.getEntryNode();
1869
1870   // isTailCall may be true since the callee does not reference caller stack
1871   // frame. Check if it's in the right position.
1872   SDValue TCChain = InChain;
1873   bool isTailCall = isInTailCallPosition(DAG, Node, TCChain, TLI);
1874   if (isTailCall)
1875     InChain = TCChain;
1876
1877   TargetLowering::
1878   CallLoweringInfo CLI(InChain, RetTy, isSigned, !isSigned, false, false,
1879                     0, TLI.getLibcallCallingConv(LC), isTailCall,
1880                     /*doesNotReturn=*/false, /*isReturnValueUsed=*/true,
1881                     Callee, Args, DAG, Node->getDebugLoc());
1882   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
1883
1884
1885   if (!CallInfo.second.getNode())
1886     // It's a tailcall, return the chain (which is the DAG root).
1887     return DAG.getRoot();
1888
1889   return CallInfo.first;
1890 }
1891
1892 /// ExpandLibCall - Generate a libcall taking the given operands as arguments
1893 /// and returning a result of type RetVT.
1894 SDValue SelectionDAGLegalize::ExpandLibCall(RTLIB::Libcall LC, EVT RetVT,
1895                                             const SDValue *Ops, unsigned NumOps,
1896                                             bool isSigned, DebugLoc dl) {
1897   TargetLowering::ArgListTy Args;
1898   Args.reserve(NumOps);
1899
1900   TargetLowering::ArgListEntry Entry;
1901   for (unsigned i = 0; i != NumOps; ++i) {
1902     Entry.Node = Ops[i];
1903     Entry.Ty = Entry.Node.getValueType().getTypeForEVT(*DAG.getContext());
1904     Entry.isSExt = isSigned;
1905     Entry.isZExt = !isSigned;
1906     Args.push_back(Entry);
1907   }
1908   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
1909                                          TLI.getPointerTy());
1910
1911   Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
1912   TargetLowering::
1913   CallLoweringInfo CLI(DAG.getEntryNode(), RetTy, isSigned, !isSigned, false,
1914                        false, 0, TLI.getLibcallCallingConv(LC),
1915                        /*isTailCall=*/false,
1916                   /*doesNotReturn=*/false, /*isReturnValueUsed=*/true,
1917                   Callee, Args, DAG, dl);
1918   std::pair<SDValue,SDValue> CallInfo = TLI.LowerCallTo(CLI);
1919
1920   return CallInfo.first;
1921 }
1922
1923 // ExpandChainLibCall - Expand a node into a call to a libcall. Similar to
1924 // ExpandLibCall except that the first operand is the in-chain.
1925 std::pair<SDValue, SDValue>
1926 SelectionDAGLegalize::ExpandChainLibCall(RTLIB::Libcall LC,
1927                                          SDNode *Node,
1928                                          bool isSigned) {
1929   SDValue InChain = Node->getOperand(0);
1930
1931   TargetLowering::ArgListTy Args;
1932   TargetLowering::ArgListEntry Entry;
1933   for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) {
1934     EVT ArgVT = Node->getOperand(i).getValueType();
1935     Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
1936     Entry.Node = Node->getOperand(i);
1937     Entry.Ty = ArgTy;
1938     Entry.isSExt = isSigned;
1939     Entry.isZExt = !isSigned;
1940     Args.push_back(Entry);
1941   }
1942   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
1943                                          TLI.getPointerTy());
1944
1945   Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext());
1946   TargetLowering::
1947   CallLoweringInfo CLI(InChain, RetTy, isSigned, !isSigned, false, false,
1948                     0, TLI.getLibcallCallingConv(LC), /*isTailCall=*/false,
1949                     /*doesNotReturn=*/false, /*isReturnValueUsed=*/true,
1950                     Callee, Args, DAG, Node->getDebugLoc());
1951   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
1952
1953   return CallInfo;
1954 }
1955
1956 SDValue SelectionDAGLegalize::ExpandFPLibCall(SDNode* Node,
1957                                               RTLIB::Libcall Call_F32,
1958                                               RTLIB::Libcall Call_F64,
1959                                               RTLIB::Libcall Call_F80,
1960                                               RTLIB::Libcall Call_PPCF128) {
1961   RTLIB::Libcall LC;
1962   switch (Node->getValueType(0).getSimpleVT().SimpleTy) {
1963   default: llvm_unreachable("Unexpected request for libcall!");
1964   case MVT::f32: LC = Call_F32; break;
1965   case MVT::f64: LC = Call_F64; break;
1966   case MVT::f80: LC = Call_F80; break;
1967   case MVT::ppcf128: LC = Call_PPCF128; break;
1968   }
1969   return ExpandLibCall(LC, Node, false);
1970 }
1971
1972 SDValue SelectionDAGLegalize::ExpandIntLibCall(SDNode* Node, bool isSigned,
1973                                                RTLIB::Libcall Call_I8,
1974                                                RTLIB::Libcall Call_I16,
1975                                                RTLIB::Libcall Call_I32,
1976                                                RTLIB::Libcall Call_I64,
1977                                                RTLIB::Libcall Call_I128) {
1978   RTLIB::Libcall LC;
1979   switch (Node->getValueType(0).getSimpleVT().SimpleTy) {
1980   default: llvm_unreachable("Unexpected request for libcall!");
1981   case MVT::i8:   LC = Call_I8; break;
1982   case MVT::i16:  LC = Call_I16; break;
1983   case MVT::i32:  LC = Call_I32; break;
1984   case MVT::i64:  LC = Call_I64; break;
1985   case MVT::i128: LC = Call_I128; break;
1986   }
1987   return ExpandLibCall(LC, Node, isSigned);
1988 }
1989
1990 /// isDivRemLibcallAvailable - Return true if divmod libcall is available.
1991 static bool isDivRemLibcallAvailable(SDNode *Node, bool isSigned,
1992                                      const TargetLowering &TLI) {
1993   RTLIB::Libcall LC;
1994   switch (Node->getValueType(0).getSimpleVT().SimpleTy) {
1995   default: llvm_unreachable("Unexpected request for libcall!");
1996   case MVT::i8:   LC= isSigned ? RTLIB::SDIVREM_I8  : RTLIB::UDIVREM_I8;  break;
1997   case MVT::i16:  LC= isSigned ? RTLIB::SDIVREM_I16 : RTLIB::UDIVREM_I16; break;
1998   case MVT::i32:  LC= isSigned ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32; break;
1999   case MVT::i64:  LC= isSigned ? RTLIB::SDIVREM_I64 : RTLIB::UDIVREM_I64; break;
2000   case MVT::i128: LC= isSigned ? RTLIB::SDIVREM_I128:RTLIB::UDIVREM_I128; break;
2001   }
2002
2003   return TLI.getLibcallName(LC) != 0;
2004 }
2005
2006 /// useDivRem - Only issue divrem libcall if both quotient and remainder are
2007 /// needed.
2008 static bool useDivRem(SDNode *Node, bool isSigned, bool isDIV) {
2009   // The other use might have been replaced with a divrem already.
2010   unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM;
2011   unsigned OtherOpcode = 0;
2012   if (isSigned)
2013     OtherOpcode = isDIV ? ISD::SREM : ISD::SDIV;
2014   else
2015     OtherOpcode = isDIV ? ISD::UREM : ISD::UDIV;
2016
2017   SDValue Op0 = Node->getOperand(0);
2018   SDValue Op1 = Node->getOperand(1);
2019   for (SDNode::use_iterator UI = Op0.getNode()->use_begin(),
2020          UE = Op0.getNode()->use_end(); UI != UE; ++UI) {
2021     SDNode *User = *UI;
2022     if (User == Node)
2023       continue;
2024     if ((User->getOpcode() == OtherOpcode || User->getOpcode() == DivRemOpc) &&
2025         User->getOperand(0) == Op0 &&
2026         User->getOperand(1) == Op1)
2027       return true;
2028   }
2029   return false;
2030 }
2031
2032 /// ExpandDivRemLibCall - Issue libcalls to __{u}divmod to compute div / rem
2033 /// pairs.
2034 void
2035 SelectionDAGLegalize::ExpandDivRemLibCall(SDNode *Node,
2036                                           SmallVectorImpl<SDValue> &Results) {
2037   unsigned Opcode = Node->getOpcode();
2038   bool isSigned = Opcode == ISD::SDIVREM;
2039
2040   RTLIB::Libcall LC;
2041   switch (Node->getValueType(0).getSimpleVT().SimpleTy) {
2042   default: llvm_unreachable("Unexpected request for libcall!");
2043   case MVT::i8:   LC= isSigned ? RTLIB::SDIVREM_I8  : RTLIB::UDIVREM_I8;  break;
2044   case MVT::i16:  LC= isSigned ? RTLIB::SDIVREM_I16 : RTLIB::UDIVREM_I16; break;
2045   case MVT::i32:  LC= isSigned ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32; break;
2046   case MVT::i64:  LC= isSigned ? RTLIB::SDIVREM_I64 : RTLIB::UDIVREM_I64; break;
2047   case MVT::i128: LC= isSigned ? RTLIB::SDIVREM_I128:RTLIB::UDIVREM_I128; break;
2048   }
2049
2050   // The input chain to this libcall is the entry node of the function.
2051   // Legalizing the call will automatically add the previous call to the
2052   // dependence.
2053   SDValue InChain = DAG.getEntryNode();
2054
2055   EVT RetVT = Node->getValueType(0);
2056   Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
2057
2058   TargetLowering::ArgListTy Args;
2059   TargetLowering::ArgListEntry Entry;
2060   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
2061     EVT ArgVT = Node->getOperand(i).getValueType();
2062     Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
2063     Entry.Node = Node->getOperand(i); Entry.Ty = ArgTy;
2064     Entry.isSExt = isSigned;
2065     Entry.isZExt = !isSigned;
2066     Args.push_back(Entry);
2067   }
2068
2069   // Also pass the return address of the remainder.
2070   SDValue FIPtr = DAG.CreateStackTemporary(RetVT);
2071   Entry.Node = FIPtr;
2072   Entry.Ty = RetTy->getPointerTo();
2073   Entry.isSExt = isSigned;
2074   Entry.isZExt = !isSigned;
2075   Args.push_back(Entry);
2076
2077   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
2078                                          TLI.getPointerTy());
2079
2080   DebugLoc dl = Node->getDebugLoc();
2081   TargetLowering::
2082   CallLoweringInfo CLI(InChain, RetTy, isSigned, !isSigned, false, false,
2083                     0, TLI.getLibcallCallingConv(LC), /*isTailCall=*/false,
2084                     /*doesNotReturn=*/false, /*isReturnValueUsed=*/true,
2085                     Callee, Args, DAG, dl);
2086   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
2087
2088   // Remainder is loaded back from the stack frame.
2089   SDValue Rem = DAG.getLoad(RetVT, dl, CallInfo.second, FIPtr,
2090                             MachinePointerInfo(), false, false, false, 0);
2091   Results.push_back(CallInfo.first);
2092   Results.push_back(Rem);
2093 }
2094
2095 /// ExpandLegalINT_TO_FP - This function is responsible for legalizing a
2096 /// INT_TO_FP operation of the specified operand when the target requests that
2097 /// we expand it.  At this point, we know that the result and operand types are
2098 /// legal for the target.
2099 SDValue SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned,
2100                                                    SDValue Op0,
2101                                                    EVT DestVT,
2102                                                    DebugLoc dl) {
2103   if (Op0.getValueType() == MVT::i32 && TLI.isTypeLegal(MVT::f64)) {
2104     // simple 32-bit [signed|unsigned] integer to float/double expansion
2105
2106     // Get the stack frame index of a 8 byte buffer.
2107     SDValue StackSlot = DAG.CreateStackTemporary(MVT::f64);
2108
2109     // word offset constant for Hi/Lo address computation
2110     SDValue WordOff = DAG.getConstant(sizeof(int), TLI.getPointerTy());
2111     // set up Hi and Lo (into buffer) address based on endian
2112     SDValue Hi = StackSlot;
2113     SDValue Lo = DAG.getNode(ISD::ADD, dl,
2114                              TLI.getPointerTy(), StackSlot, WordOff);
2115     if (TLI.isLittleEndian())
2116       std::swap(Hi, Lo);
2117
2118     // if signed map to unsigned space
2119     SDValue Op0Mapped;
2120     if (isSigned) {
2121       // constant used to invert sign bit (signed to unsigned mapping)
2122       SDValue SignBit = DAG.getConstant(0x80000000u, MVT::i32);
2123       Op0Mapped = DAG.getNode(ISD::XOR, dl, MVT::i32, Op0, SignBit);
2124     } else {
2125       Op0Mapped = Op0;
2126     }
2127     // store the lo of the constructed double - based on integer input
2128     SDValue Store1 = DAG.getStore(DAG.getEntryNode(), dl,
2129                                   Op0Mapped, Lo, MachinePointerInfo(),
2130                                   false, false, 0);
2131     // initial hi portion of constructed double
2132     SDValue InitialHi = DAG.getConstant(0x43300000u, MVT::i32);
2133     // store the hi of the constructed double - biased exponent
2134     SDValue Store2 = DAG.getStore(Store1, dl, InitialHi, Hi,
2135                                   MachinePointerInfo(),
2136                                   false, false, 0);
2137     // load the constructed double
2138     SDValue Load = DAG.getLoad(MVT::f64, dl, Store2, StackSlot,
2139                                MachinePointerInfo(), false, false, false, 0);
2140     // FP constant to bias correct the final result
2141     SDValue Bias = DAG.getConstantFP(isSigned ?
2142                                      BitsToDouble(0x4330000080000000ULL) :
2143                                      BitsToDouble(0x4330000000000000ULL),
2144                                      MVT::f64);
2145     // subtract the bias
2146     SDValue Sub = DAG.getNode(ISD::FSUB, dl, MVT::f64, Load, Bias);
2147     // final result
2148     SDValue Result;
2149     // handle final rounding
2150     if (DestVT == MVT::f64) {
2151       // do nothing
2152       Result = Sub;
2153     } else if (DestVT.bitsLT(MVT::f64)) {
2154       Result = DAG.getNode(ISD::FP_ROUND, dl, DestVT, Sub,
2155                            DAG.getIntPtrConstant(0));
2156     } else if (DestVT.bitsGT(MVT::f64)) {
2157       Result = DAG.getNode(ISD::FP_EXTEND, dl, DestVT, Sub);
2158     }
2159     return Result;
2160   }
2161   assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet");
2162   // Code below here assumes !isSigned without checking again.
2163
2164   // Implementation of unsigned i64 to f64 following the algorithm in
2165   // __floatundidf in compiler_rt. This implementation has the advantage
2166   // of performing rounding correctly, both in the default rounding mode
2167   // and in all alternate rounding modes.
2168   // TODO: Generalize this for use with other types.
2169   if (Op0.getValueType() == MVT::i64 && DestVT == MVT::f64) {
2170     SDValue TwoP52 =
2171       DAG.getConstant(UINT64_C(0x4330000000000000), MVT::i64);
2172     SDValue TwoP84PlusTwoP52 =
2173       DAG.getConstantFP(BitsToDouble(UINT64_C(0x4530000000100000)), MVT::f64);
2174     SDValue TwoP84 =
2175       DAG.getConstant(UINT64_C(0x4530000000000000), MVT::i64);
2176
2177     SDValue Lo = DAG.getZeroExtendInReg(Op0, dl, MVT::i32);
2178     SDValue Hi = DAG.getNode(ISD::SRL, dl, MVT::i64, Op0,
2179                              DAG.getConstant(32, MVT::i64));
2180     SDValue LoOr = DAG.getNode(ISD::OR, dl, MVT::i64, Lo, TwoP52);
2181     SDValue HiOr = DAG.getNode(ISD::OR, dl, MVT::i64, Hi, TwoP84);
2182     SDValue LoFlt = DAG.getNode(ISD::BITCAST, dl, MVT::f64, LoOr);
2183     SDValue HiFlt = DAG.getNode(ISD::BITCAST, dl, MVT::f64, HiOr);
2184     SDValue HiSub = DAG.getNode(ISD::FSUB, dl, MVT::f64, HiFlt,
2185                                 TwoP84PlusTwoP52);
2186     return DAG.getNode(ISD::FADD, dl, MVT::f64, LoFlt, HiSub);
2187   }
2188
2189   // Implementation of unsigned i64 to f32.
2190   // TODO: Generalize this for use with other types.
2191   if (Op0.getValueType() == MVT::i64 && DestVT == MVT::f32) {
2192     // For unsigned conversions, convert them to signed conversions using the
2193     // algorithm from the x86_64 __floatundidf in compiler_rt.
2194     if (!isSigned) {
2195       SDValue Fast = DAG.getNode(ISD::SINT_TO_FP, dl, MVT::f32, Op0);
2196
2197       SDValue ShiftConst =
2198           DAG.getConstant(1, TLI.getShiftAmountTy(Op0.getValueType()));
2199       SDValue Shr = DAG.getNode(ISD::SRL, dl, MVT::i64, Op0, ShiftConst);
2200       SDValue AndConst = DAG.getConstant(1, MVT::i64);
2201       SDValue And = DAG.getNode(ISD::AND, dl, MVT::i64, Op0, AndConst);
2202       SDValue Or = DAG.getNode(ISD::OR, dl, MVT::i64, And, Shr);
2203
2204       SDValue SignCvt = DAG.getNode(ISD::SINT_TO_FP, dl, MVT::f32, Or);
2205       SDValue Slow = DAG.getNode(ISD::FADD, dl, MVT::f32, SignCvt, SignCvt);
2206
2207       // TODO: This really should be implemented using a branch rather than a
2208       // select.  We happen to get lucky and machinesink does the right
2209       // thing most of the time.  This would be a good candidate for a
2210       //pseudo-op, or, even better, for whole-function isel.
2211       SDValue SignBitTest = DAG.getSetCC(dl, TLI.getSetCCResultType(MVT::i64),
2212         Op0, DAG.getConstant(0, MVT::i64), ISD::SETLT);
2213       return DAG.getNode(ISD::SELECT, dl, MVT::f32, SignBitTest, Slow, Fast);
2214     }
2215
2216     // Otherwise, implement the fully general conversion.
2217
2218     SDValue And = DAG.getNode(ISD::AND, dl, MVT::i64, Op0,
2219          DAG.getConstant(UINT64_C(0xfffffffffffff800), MVT::i64));
2220     SDValue Or = DAG.getNode(ISD::OR, dl, MVT::i64, And,
2221          DAG.getConstant(UINT64_C(0x800), MVT::i64));
2222     SDValue And2 = DAG.getNode(ISD::AND, dl, MVT::i64, Op0,
2223          DAG.getConstant(UINT64_C(0x7ff), MVT::i64));
2224     SDValue Ne = DAG.getSetCC(dl, TLI.getSetCCResultType(MVT::i64),
2225                    And2, DAG.getConstant(UINT64_C(0), MVT::i64), ISD::SETNE);
2226     SDValue Sel = DAG.getNode(ISD::SELECT, dl, MVT::i64, Ne, Or, Op0);
2227     SDValue Ge = DAG.getSetCC(dl, TLI.getSetCCResultType(MVT::i64),
2228                    Op0, DAG.getConstant(UINT64_C(0x0020000000000000), MVT::i64),
2229                    ISD::SETUGE);
2230     SDValue Sel2 = DAG.getNode(ISD::SELECT, dl, MVT::i64, Ge, Sel, Op0);
2231     EVT SHVT = TLI.getShiftAmountTy(Sel2.getValueType());
2232
2233     SDValue Sh = DAG.getNode(ISD::SRL, dl, MVT::i64, Sel2,
2234                              DAG.getConstant(32, SHVT));
2235     SDValue Trunc = DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Sh);
2236     SDValue Fcvt = DAG.getNode(ISD::UINT_TO_FP, dl, MVT::f64, Trunc);
2237     SDValue TwoP32 =
2238       DAG.getConstantFP(BitsToDouble(UINT64_C(0x41f0000000000000)), MVT::f64);
2239     SDValue Fmul = DAG.getNode(ISD::FMUL, dl, MVT::f64, TwoP32, Fcvt);
2240     SDValue Lo = DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Sel2);
2241     SDValue Fcvt2 = DAG.getNode(ISD::UINT_TO_FP, dl, MVT::f64, Lo);
2242     SDValue Fadd = DAG.getNode(ISD::FADD, dl, MVT::f64, Fmul, Fcvt2);
2243     return DAG.getNode(ISD::FP_ROUND, dl, MVT::f32, Fadd,
2244                        DAG.getIntPtrConstant(0));
2245   }
2246
2247   SDValue Tmp1 = DAG.getNode(ISD::SINT_TO_FP, dl, DestVT, Op0);
2248
2249   SDValue SignSet = DAG.getSetCC(dl, TLI.getSetCCResultType(Op0.getValueType()),
2250                                  Op0, DAG.getConstant(0, Op0.getValueType()),
2251                                  ISD::SETLT);
2252   SDValue Zero = DAG.getIntPtrConstant(0), Four = DAG.getIntPtrConstant(4);
2253   SDValue CstOffset = DAG.getNode(ISD::SELECT, dl, Zero.getValueType(),
2254                                     SignSet, Four, Zero);
2255
2256   // If the sign bit of the integer is set, the large number will be treated
2257   // as a negative number.  To counteract this, the dynamic code adds an
2258   // offset depending on the data type.
2259   uint64_t FF;
2260   switch (Op0.getValueType().getSimpleVT().SimpleTy) {
2261   default: llvm_unreachable("Unsupported integer type!");
2262   case MVT::i8 : FF = 0x43800000ULL; break;  // 2^8  (as a float)
2263   case MVT::i16: FF = 0x47800000ULL; break;  // 2^16 (as a float)
2264   case MVT::i32: FF = 0x4F800000ULL; break;  // 2^32 (as a float)
2265   case MVT::i64: FF = 0x5F800000ULL; break;  // 2^64 (as a float)
2266   }
2267   if (TLI.isLittleEndian()) FF <<= 32;
2268   Constant *FudgeFactor = ConstantInt::get(
2269                                        Type::getInt64Ty(*DAG.getContext()), FF);
2270
2271   SDValue CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
2272   unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment();
2273   CPIdx = DAG.getNode(ISD::ADD, dl, TLI.getPointerTy(), CPIdx, CstOffset);
2274   Alignment = std::min(Alignment, 4u);
2275   SDValue FudgeInReg;
2276   if (DestVT == MVT::f32)
2277     FudgeInReg = DAG.getLoad(MVT::f32, dl, DAG.getEntryNode(), CPIdx,
2278                              MachinePointerInfo::getConstantPool(),
2279                              false, false, false, Alignment);
2280   else {
2281     SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, DestVT,
2282                                   DAG.getEntryNode(), CPIdx,
2283                                   MachinePointerInfo::getConstantPool(),
2284                                   MVT::f32, false, false, Alignment);
2285     HandleSDNode Handle(Load);
2286     LegalizeOp(Load.getNode());
2287     FudgeInReg = Handle.getValue();
2288   }
2289
2290   return DAG.getNode(ISD::FADD, dl, DestVT, Tmp1, FudgeInReg);
2291 }
2292
2293 /// PromoteLegalINT_TO_FP - This function is responsible for legalizing a
2294 /// *INT_TO_FP operation of the specified operand when the target requests that
2295 /// we promote it.  At this point, we know that the result and operand types are
2296 /// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP
2297 /// operation that takes a larger input.
2298 SDValue SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDValue LegalOp,
2299                                                     EVT DestVT,
2300                                                     bool isSigned,
2301                                                     DebugLoc dl) {
2302   // First step, figure out the appropriate *INT_TO_FP operation to use.
2303   EVT NewInTy = LegalOp.getValueType();
2304
2305   unsigned OpToUse = 0;
2306
2307   // Scan for the appropriate larger type to use.
2308   while (1) {
2309     NewInTy = (MVT::SimpleValueType)(NewInTy.getSimpleVT().SimpleTy+1);
2310     assert(NewInTy.isInteger() && "Ran out of possibilities!");
2311
2312     // If the target supports SINT_TO_FP of this type, use it.
2313     if (TLI.isOperationLegalOrCustom(ISD::SINT_TO_FP, NewInTy)) {
2314       OpToUse = ISD::SINT_TO_FP;
2315       break;
2316     }
2317     if (isSigned) continue;
2318
2319     // If the target supports UINT_TO_FP of this type, use it.
2320     if (TLI.isOperationLegalOrCustom(ISD::UINT_TO_FP, NewInTy)) {
2321       OpToUse = ISD::UINT_TO_FP;
2322       break;
2323     }
2324
2325     // Otherwise, try a larger type.
2326   }
2327
2328   // Okay, we found the operation and type to use.  Zero extend our input to the
2329   // desired type then run the operation on it.
2330   return DAG.getNode(OpToUse, dl, DestVT,
2331                      DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND,
2332                                  dl, NewInTy, LegalOp));
2333 }
2334
2335 /// PromoteLegalFP_TO_INT - This function is responsible for legalizing a
2336 /// FP_TO_*INT operation of the specified operand when the target requests that
2337 /// we promote it.  At this point, we know that the result and operand types are
2338 /// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT
2339 /// operation that returns a larger result.
2340 SDValue SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDValue LegalOp,
2341                                                     EVT DestVT,
2342                                                     bool isSigned,
2343                                                     DebugLoc dl) {
2344   // First step, figure out the appropriate FP_TO*INT operation to use.
2345   EVT NewOutTy = DestVT;
2346
2347   unsigned OpToUse = 0;
2348
2349   // Scan for the appropriate larger type to use.
2350   while (1) {
2351     NewOutTy = (MVT::SimpleValueType)(NewOutTy.getSimpleVT().SimpleTy+1);
2352     assert(NewOutTy.isInteger() && "Ran out of possibilities!");
2353
2354     if (TLI.isOperationLegalOrCustom(ISD::FP_TO_SINT, NewOutTy)) {
2355       OpToUse = ISD::FP_TO_SINT;
2356       break;
2357     }
2358
2359     if (TLI.isOperationLegalOrCustom(ISD::FP_TO_UINT, NewOutTy)) {
2360       OpToUse = ISD::FP_TO_UINT;
2361       break;
2362     }
2363
2364     // Otherwise, try a larger type.
2365   }
2366
2367
2368   // Okay, we found the operation and type to use.
2369   SDValue Operation = DAG.getNode(OpToUse, dl, NewOutTy, LegalOp);
2370
2371   // Truncate the result of the extended FP_TO_*INT operation to the desired
2372   // size.
2373   return DAG.getNode(ISD::TRUNCATE, dl, DestVT, Operation);
2374 }
2375
2376 /// ExpandBSWAP - Open code the operations for BSWAP of the specified operation.
2377 ///
2378 SDValue SelectionDAGLegalize::ExpandBSWAP(SDValue Op, DebugLoc dl) {
2379   EVT VT = Op.getValueType();
2380   EVT SHVT = TLI.getShiftAmountTy(VT);
2381   SDValue Tmp1, Tmp2, Tmp3, Tmp4, Tmp5, Tmp6, Tmp7, Tmp8;
2382   switch (VT.getSimpleVT().SimpleTy) {
2383   default: llvm_unreachable("Unhandled Expand type in BSWAP!");
2384   case MVT::i16:
2385     Tmp2 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, SHVT));
2386     Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, SHVT));
2387     return DAG.getNode(ISD::OR, dl, VT, Tmp1, Tmp2);
2388   case MVT::i32:
2389     Tmp4 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(24, SHVT));
2390     Tmp3 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, SHVT));
2391     Tmp2 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, SHVT));
2392     Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(24, SHVT));
2393     Tmp3 = DAG.getNode(ISD::AND, dl, VT, Tmp3, DAG.getConstant(0xFF0000, VT));
2394     Tmp2 = DAG.getNode(ISD::AND, dl, VT, Tmp2, DAG.getConstant(0xFF00, VT));
2395     Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp3);
2396     Tmp2 = DAG.getNode(ISD::OR, dl, VT, Tmp2, Tmp1);
2397     return DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp2);
2398   case MVT::i64:
2399     Tmp8 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(56, SHVT));
2400     Tmp7 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(40, SHVT));
2401     Tmp6 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(24, SHVT));
2402     Tmp5 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, SHVT));
2403     Tmp4 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, SHVT));
2404     Tmp3 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(24, SHVT));
2405     Tmp2 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(40, SHVT));
2406     Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(56, SHVT));
2407     Tmp7 = DAG.getNode(ISD::AND, dl, VT, Tmp7, DAG.getConstant(255ULL<<48, VT));
2408     Tmp6 = DAG.getNode(ISD::AND, dl, VT, Tmp6, DAG.getConstant(255ULL<<40, VT));
2409     Tmp5 = DAG.getNode(ISD::AND, dl, VT, Tmp5, DAG.getConstant(255ULL<<32, VT));
2410     Tmp4 = DAG.getNode(ISD::AND, dl, VT, Tmp4, DAG.getConstant(255ULL<<24, VT));
2411     Tmp3 = DAG.getNode(ISD::AND, dl, VT, Tmp3, DAG.getConstant(255ULL<<16, VT));
2412     Tmp2 = DAG.getNode(ISD::AND, dl, VT, Tmp2, DAG.getConstant(255ULL<<8 , VT));
2413     Tmp8 = DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp7);
2414     Tmp6 = DAG.getNode(ISD::OR, dl, VT, Tmp6, Tmp5);
2415     Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp3);
2416     Tmp2 = DAG.getNode(ISD::OR, dl, VT, Tmp2, Tmp1);
2417     Tmp8 = DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp6);
2418     Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp2);
2419     return DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp4);
2420   }
2421 }
2422
2423 /// SplatByte - Distribute ByteVal over NumBits bits.
2424 // FIXME: Move this helper to a common place.
2425 static APInt SplatByte(unsigned NumBits, uint8_t ByteVal) {
2426   APInt Val = APInt(NumBits, ByteVal);
2427   unsigned Shift = 8;
2428   for (unsigned i = NumBits; i > 8; i >>= 1) {
2429     Val = (Val << Shift) | Val;
2430     Shift <<= 1;
2431   }
2432   return Val;
2433 }
2434
2435 /// ExpandBitCount - Expand the specified bitcount instruction into operations.
2436 ///
2437 SDValue SelectionDAGLegalize::ExpandBitCount(unsigned Opc, SDValue Op,
2438                                              DebugLoc dl) {
2439   switch (Opc) {
2440   default: llvm_unreachable("Cannot expand this yet!");
2441   case ISD::CTPOP: {
2442     EVT VT = Op.getValueType();
2443     EVT ShVT = TLI.getShiftAmountTy(VT);
2444     unsigned Len = VT.getSizeInBits();
2445
2446     assert(VT.isInteger() && Len <= 128 && Len % 8 == 0 &&
2447            "CTPOP not implemented for this type.");
2448
2449     // This is the "best" algorithm from
2450     // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
2451
2452     SDValue Mask55 = DAG.getConstant(SplatByte(Len, 0x55), VT);
2453     SDValue Mask33 = DAG.getConstant(SplatByte(Len, 0x33), VT);
2454     SDValue Mask0F = DAG.getConstant(SplatByte(Len, 0x0F), VT);
2455     SDValue Mask01 = DAG.getConstant(SplatByte(Len, 0x01), VT);
2456
2457     // v = v - ((v >> 1) & 0x55555555...)
2458     Op = DAG.getNode(ISD::SUB, dl, VT, Op,
2459                      DAG.getNode(ISD::AND, dl, VT,
2460                                  DAG.getNode(ISD::SRL, dl, VT, Op,
2461                                              DAG.getConstant(1, ShVT)),
2462                                  Mask55));
2463     // v = (v & 0x33333333...) + ((v >> 2) & 0x33333333...)
2464     Op = DAG.getNode(ISD::ADD, dl, VT,
2465                      DAG.getNode(ISD::AND, dl, VT, Op, Mask33),
2466                      DAG.getNode(ISD::AND, dl, VT,
2467                                  DAG.getNode(ISD::SRL, dl, VT, Op,
2468                                              DAG.getConstant(2, ShVT)),
2469                                  Mask33));
2470     // v = (v + (v >> 4)) & 0x0F0F0F0F...
2471     Op = DAG.getNode(ISD::AND, dl, VT,
2472                      DAG.getNode(ISD::ADD, dl, VT, Op,
2473                                  DAG.getNode(ISD::SRL, dl, VT, Op,
2474                                              DAG.getConstant(4, ShVT))),
2475                      Mask0F);
2476     // v = (v * 0x01010101...) >> (Len - 8)
2477     Op = DAG.getNode(ISD::SRL, dl, VT,
2478                      DAG.getNode(ISD::MUL, dl, VT, Op, Mask01),
2479                      DAG.getConstant(Len - 8, ShVT));
2480
2481     return Op;
2482   }
2483   case ISD::CTLZ_ZERO_UNDEF:
2484     // This trivially expands to CTLZ.
2485     return DAG.getNode(ISD::CTLZ, dl, Op.getValueType(), Op);
2486   case ISD::CTLZ: {
2487     // for now, we do this:
2488     // x = x | (x >> 1);
2489     // x = x | (x >> 2);
2490     // ...
2491     // x = x | (x >>16);
2492     // x = x | (x >>32); // for 64-bit input
2493     // return popcount(~x);
2494     //
2495     // but see also: http://www.hackersdelight.org/HDcode/nlz.cc
2496     EVT VT = Op.getValueType();
2497     EVT ShVT = TLI.getShiftAmountTy(VT);
2498     unsigned len = VT.getSizeInBits();
2499     for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
2500       SDValue Tmp3 = DAG.getConstant(1ULL << i, ShVT);
2501       Op = DAG.getNode(ISD::OR, dl, VT, Op,
2502                        DAG.getNode(ISD::SRL, dl, VT, Op, Tmp3));
2503     }
2504     Op = DAG.getNOT(dl, Op, VT);
2505     return DAG.getNode(ISD::CTPOP, dl, VT, Op);
2506   }
2507   case ISD::CTTZ_ZERO_UNDEF:
2508     // This trivially expands to CTTZ.
2509     return DAG.getNode(ISD::CTTZ, dl, Op.getValueType(), Op);
2510   case ISD::CTTZ: {
2511     // for now, we use: { return popcount(~x & (x - 1)); }
2512     // unless the target has ctlz but not ctpop, in which case we use:
2513     // { return 32 - nlz(~x & (x-1)); }
2514     // see also http://www.hackersdelight.org/HDcode/ntz.cc
2515     EVT VT = Op.getValueType();
2516     SDValue Tmp3 = DAG.getNode(ISD::AND, dl, VT,
2517                                DAG.getNOT(dl, Op, VT),
2518                                DAG.getNode(ISD::SUB, dl, VT, Op,
2519                                            DAG.getConstant(1, VT)));
2520     // If ISD::CTLZ is legal and CTPOP isn't, then do that instead.
2521     if (!TLI.isOperationLegalOrCustom(ISD::CTPOP, VT) &&
2522         TLI.isOperationLegalOrCustom(ISD::CTLZ, VT))
2523       return DAG.getNode(ISD::SUB, dl, VT,
2524                          DAG.getConstant(VT.getSizeInBits(), VT),
2525                          DAG.getNode(ISD::CTLZ, dl, VT, Tmp3));
2526     return DAG.getNode(ISD::CTPOP, dl, VT, Tmp3);
2527   }
2528   }
2529 }
2530
2531 std::pair <SDValue, SDValue> SelectionDAGLegalize::ExpandAtomic(SDNode *Node) {
2532   unsigned Opc = Node->getOpcode();
2533   MVT VT = cast<AtomicSDNode>(Node)->getMemoryVT().getSimpleVT();
2534   RTLIB::Libcall LC;
2535
2536   switch (Opc) {
2537   default:
2538     llvm_unreachable("Unhandled atomic intrinsic Expand!");
2539   case ISD::ATOMIC_SWAP:
2540     switch (VT.SimpleTy) {
2541     default: llvm_unreachable("Unexpected value type for atomic!");
2542     case MVT::i8:  LC = RTLIB::SYNC_LOCK_TEST_AND_SET_1; break;
2543     case MVT::i16: LC = RTLIB::SYNC_LOCK_TEST_AND_SET_2; break;
2544     case MVT::i32: LC = RTLIB::SYNC_LOCK_TEST_AND_SET_4; break;
2545     case MVT::i64: LC = RTLIB::SYNC_LOCK_TEST_AND_SET_8; break;
2546     }
2547     break;
2548   case ISD::ATOMIC_CMP_SWAP:
2549     switch (VT.SimpleTy) {
2550     default: llvm_unreachable("Unexpected value type for atomic!");
2551     case MVT::i8:  LC = RTLIB::SYNC_VAL_COMPARE_AND_SWAP_1; break;
2552     case MVT::i16: LC = RTLIB::SYNC_VAL_COMPARE_AND_SWAP_2; break;
2553     case MVT::i32: LC = RTLIB::SYNC_VAL_COMPARE_AND_SWAP_4; break;
2554     case MVT::i64: LC = RTLIB::SYNC_VAL_COMPARE_AND_SWAP_8; break;
2555     }
2556     break;
2557   case ISD::ATOMIC_LOAD_ADD:
2558     switch (VT.SimpleTy) {
2559     default: llvm_unreachable("Unexpected value type for atomic!");
2560     case MVT::i8:  LC = RTLIB::SYNC_FETCH_AND_ADD_1; break;
2561     case MVT::i16: LC = RTLIB::SYNC_FETCH_AND_ADD_2; break;
2562     case MVT::i32: LC = RTLIB::SYNC_FETCH_AND_ADD_4; break;
2563     case MVT::i64: LC = RTLIB::SYNC_FETCH_AND_ADD_8; break;
2564     }
2565     break;
2566   case ISD::ATOMIC_LOAD_SUB:
2567     switch (VT.SimpleTy) {
2568     default: llvm_unreachable("Unexpected value type for atomic!");
2569     case MVT::i8:  LC = RTLIB::SYNC_FETCH_AND_SUB_1; break;
2570     case MVT::i16: LC = RTLIB::SYNC_FETCH_AND_SUB_2; break;
2571     case MVT::i32: LC = RTLIB::SYNC_FETCH_AND_SUB_4; break;
2572     case MVT::i64: LC = RTLIB::SYNC_FETCH_AND_SUB_8; break;
2573     }
2574     break;
2575   case ISD::ATOMIC_LOAD_AND:
2576     switch (VT.SimpleTy) {
2577     default: llvm_unreachable("Unexpected value type for atomic!");
2578     case MVT::i8:  LC = RTLIB::SYNC_FETCH_AND_AND_1; break;
2579     case MVT::i16: LC = RTLIB::SYNC_FETCH_AND_AND_2; break;
2580     case MVT::i32: LC = RTLIB::SYNC_FETCH_AND_AND_4; break;
2581     case MVT::i64: LC = RTLIB::SYNC_FETCH_AND_AND_8; break;
2582     }
2583     break;
2584   case ISD::ATOMIC_LOAD_OR:
2585     switch (VT.SimpleTy) {
2586     default: llvm_unreachable("Unexpected value type for atomic!");
2587     case MVT::i8:  LC = RTLIB::SYNC_FETCH_AND_OR_1; break;
2588     case MVT::i16: LC = RTLIB::SYNC_FETCH_AND_OR_2; break;
2589     case MVT::i32: LC = RTLIB::SYNC_FETCH_AND_OR_4; break;
2590     case MVT::i64: LC = RTLIB::SYNC_FETCH_AND_OR_8; break;
2591     }
2592     break;
2593   case ISD::ATOMIC_LOAD_XOR:
2594     switch (VT.SimpleTy) {
2595     default: llvm_unreachable("Unexpected value type for atomic!");
2596     case MVT::i8:  LC = RTLIB::SYNC_FETCH_AND_XOR_1; break;
2597     case MVT::i16: LC = RTLIB::SYNC_FETCH_AND_XOR_2; break;
2598     case MVT::i32: LC = RTLIB::SYNC_FETCH_AND_XOR_4; break;
2599     case MVT::i64: LC = RTLIB::SYNC_FETCH_AND_XOR_8; break;
2600     }
2601     break;
2602   case ISD::ATOMIC_LOAD_NAND:
2603     switch (VT.SimpleTy) {
2604     default: llvm_unreachable("Unexpected value type for atomic!");
2605     case MVT::i8:  LC = RTLIB::SYNC_FETCH_AND_NAND_1; break;
2606     case MVT::i16: LC = RTLIB::SYNC_FETCH_AND_NAND_2; break;
2607     case MVT::i32: LC = RTLIB::SYNC_FETCH_AND_NAND_4; break;
2608     case MVT::i64: LC = RTLIB::SYNC_FETCH_AND_NAND_8; break;
2609     }
2610     break;
2611   }
2612
2613   return ExpandChainLibCall(LC, Node, false);
2614 }
2615
2616 void SelectionDAGLegalize::ExpandNode(SDNode *Node) {
2617   SmallVector<SDValue, 8> Results;
2618   DebugLoc dl = Node->getDebugLoc();
2619   SDValue Tmp1, Tmp2, Tmp3, Tmp4;
2620   switch (Node->getOpcode()) {
2621   case ISD::CTPOP:
2622   case ISD::CTLZ:
2623   case ISD::CTLZ_ZERO_UNDEF:
2624   case ISD::CTTZ:
2625   case ISD::CTTZ_ZERO_UNDEF:
2626     Tmp1 = ExpandBitCount(Node->getOpcode(), Node->getOperand(0), dl);
2627     Results.push_back(Tmp1);
2628     break;
2629   case ISD::BSWAP:
2630     Results.push_back(ExpandBSWAP(Node->getOperand(0), dl));
2631     break;
2632   case ISD::FRAMEADDR:
2633   case ISD::RETURNADDR:
2634   case ISD::FRAME_TO_ARGS_OFFSET:
2635     Results.push_back(DAG.getConstant(0, Node->getValueType(0)));
2636     break;
2637   case ISD::FLT_ROUNDS_:
2638     Results.push_back(DAG.getConstant(1, Node->getValueType(0)));
2639     break;
2640   case ISD::EH_RETURN:
2641   case ISD::EH_LABEL:
2642   case ISD::PREFETCH:
2643   case ISD::VAEND:
2644   case ISD::EH_SJLJ_LONGJMP:
2645     // If the target didn't expand these, there's nothing to do, so just
2646     // preserve the chain and be done.
2647     Results.push_back(Node->getOperand(0));
2648     break;
2649   case ISD::EH_SJLJ_SETJMP:
2650     // If the target didn't expand this, just return 'zero' and preserve the
2651     // chain.
2652     Results.push_back(DAG.getConstant(0, MVT::i32));
2653     Results.push_back(Node->getOperand(0));
2654     break;
2655   case ISD::ATOMIC_FENCE:
2656   case ISD::MEMBARRIER: {
2657     // If the target didn't lower this, lower it to '__sync_synchronize()' call
2658     // FIXME: handle "fence singlethread" more efficiently.
2659     TargetLowering::ArgListTy Args;
2660     TargetLowering::
2661     CallLoweringInfo CLI(Node->getOperand(0),
2662                          Type::getVoidTy(*DAG.getContext()),
2663                       false, false, false, false, 0, CallingConv::C,
2664                       /*isTailCall=*/false,
2665                       /*doesNotReturn=*/false, /*isReturnValueUsed=*/true,
2666                       DAG.getExternalSymbol("__sync_synchronize",
2667                                             TLI.getPointerTy()),
2668                       Args, DAG, dl);
2669     std::pair<SDValue, SDValue> CallResult = TLI.LowerCallTo(CLI);
2670
2671     Results.push_back(CallResult.second);
2672     break;
2673   }
2674   case ISD::ATOMIC_LOAD: {
2675     // There is no libcall for atomic load; fake it with ATOMIC_CMP_SWAP.
2676     SDValue Zero = DAG.getConstant(0, Node->getValueType(0));
2677     SDValue Swap = DAG.getAtomic(ISD::ATOMIC_CMP_SWAP, dl,
2678                                  cast<AtomicSDNode>(Node)->getMemoryVT(),
2679                                  Node->getOperand(0),
2680                                  Node->getOperand(1), Zero, Zero,
2681                                  cast<AtomicSDNode>(Node)->getMemOperand(),
2682                                  cast<AtomicSDNode>(Node)->getOrdering(),
2683                                  cast<AtomicSDNode>(Node)->getSynchScope());
2684     Results.push_back(Swap.getValue(0));
2685     Results.push_back(Swap.getValue(1));
2686     break;
2687   }
2688   case ISD::ATOMIC_STORE: {
2689     // There is no libcall for atomic store; fake it with ATOMIC_SWAP.
2690     SDValue Swap = DAG.getAtomic(ISD::ATOMIC_SWAP, dl,
2691                                  cast<AtomicSDNode>(Node)->getMemoryVT(),
2692                                  Node->getOperand(0),
2693                                  Node->getOperand(1), Node->getOperand(2),
2694                                  cast<AtomicSDNode>(Node)->getMemOperand(),
2695                                  cast<AtomicSDNode>(Node)->getOrdering(),
2696                                  cast<AtomicSDNode>(Node)->getSynchScope());
2697     Results.push_back(Swap.getValue(1));
2698     break;
2699   }
2700   // By default, atomic intrinsics are marked Legal and lowered. Targets
2701   // which don't support them directly, however, may want libcalls, in which
2702   // case they mark them Expand, and we get here.
2703   case ISD::ATOMIC_SWAP:
2704   case ISD::ATOMIC_LOAD_ADD:
2705   case ISD::ATOMIC_LOAD_SUB:
2706   case ISD::ATOMIC_LOAD_AND:
2707   case ISD::ATOMIC_LOAD_OR:
2708   case ISD::ATOMIC_LOAD_XOR:
2709   case ISD::ATOMIC_LOAD_NAND:
2710   case ISD::ATOMIC_LOAD_MIN:
2711   case ISD::ATOMIC_LOAD_MAX:
2712   case ISD::ATOMIC_LOAD_UMIN:
2713   case ISD::ATOMIC_LOAD_UMAX:
2714   case ISD::ATOMIC_CMP_SWAP: {
2715     std::pair<SDValue, SDValue> Tmp = ExpandAtomic(Node);
2716     Results.push_back(Tmp.first);
2717     Results.push_back(Tmp.second);
2718     break;
2719   }
2720   case ISD::DYNAMIC_STACKALLOC:
2721     ExpandDYNAMIC_STACKALLOC(Node, Results);
2722     break;
2723   case ISD::MERGE_VALUES:
2724     for (unsigned i = 0; i < Node->getNumValues(); i++)
2725       Results.push_back(Node->getOperand(i));
2726     break;
2727   case ISD::UNDEF: {
2728     EVT VT = Node->getValueType(0);
2729     if (VT.isInteger())
2730       Results.push_back(DAG.getConstant(0, VT));
2731     else {
2732       assert(VT.isFloatingPoint() && "Unknown value type!");
2733       Results.push_back(DAG.getConstantFP(0, VT));
2734     }
2735     break;
2736   }
2737   case ISD::TRAP: {
2738     // If this operation is not supported, lower it to 'abort()' call
2739     TargetLowering::ArgListTy Args;
2740     TargetLowering::
2741     CallLoweringInfo CLI(Node->getOperand(0),
2742                          Type::getVoidTy(*DAG.getContext()),
2743                       false, false, false, false, 0, CallingConv::C,
2744                       /*isTailCall=*/false,
2745                       /*doesNotReturn=*/false, /*isReturnValueUsed=*/true,
2746                       DAG.getExternalSymbol("abort", TLI.getPointerTy()),
2747                       Args, DAG, dl);
2748     std::pair<SDValue, SDValue> CallResult = TLI.LowerCallTo(CLI);
2749
2750     Results.push_back(CallResult.second);
2751     break;
2752   }
2753   case ISD::FP_ROUND:
2754   case ISD::BITCAST:
2755     Tmp1 = EmitStackConvert(Node->getOperand(0), Node->getValueType(0),
2756                             Node->getValueType(0), dl);
2757     Results.push_back(Tmp1);
2758     break;
2759   case ISD::FP_EXTEND:
2760     Tmp1 = EmitStackConvert(Node->getOperand(0),
2761                             Node->getOperand(0).getValueType(),
2762                             Node->getValueType(0), dl);
2763     Results.push_back(Tmp1);
2764     break;
2765   case ISD::SIGN_EXTEND_INREG: {
2766     // NOTE: we could fall back on load/store here too for targets without
2767     // SAR.  However, it is doubtful that any exist.
2768     EVT ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
2769     EVT VT = Node->getValueType(0);
2770     EVT ShiftAmountTy = TLI.getShiftAmountTy(VT);
2771     if (VT.isVector())
2772       ShiftAmountTy = VT;
2773     unsigned BitsDiff = VT.getScalarType().getSizeInBits() -
2774                         ExtraVT.getScalarType().getSizeInBits();
2775     SDValue ShiftCst = DAG.getConstant(BitsDiff, ShiftAmountTy);
2776     Tmp1 = DAG.getNode(ISD::SHL, dl, Node->getValueType(0),
2777                        Node->getOperand(0), ShiftCst);
2778     Tmp1 = DAG.getNode(ISD::SRA, dl, Node->getValueType(0), Tmp1, ShiftCst);
2779     Results.push_back(Tmp1);
2780     break;
2781   }
2782   case ISD::FP_ROUND_INREG: {
2783     // The only way we can lower this is to turn it into a TRUNCSTORE,
2784     // EXTLOAD pair, targeting a temporary location (a stack slot).
2785
2786     // NOTE: there is a choice here between constantly creating new stack
2787     // slots and always reusing the same one.  We currently always create
2788     // new ones, as reuse may inhibit scheduling.
2789     EVT ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
2790     Tmp1 = EmitStackConvert(Node->getOperand(0), ExtraVT,
2791                             Node->getValueType(0), dl);
2792     Results.push_back(Tmp1);
2793     break;
2794   }
2795   case ISD::SINT_TO_FP:
2796   case ISD::UINT_TO_FP:
2797     Tmp1 = ExpandLegalINT_TO_FP(Node->getOpcode() == ISD::SINT_TO_FP,
2798                                 Node->getOperand(0), Node->getValueType(0), dl);
2799     Results.push_back(Tmp1);
2800     break;
2801   case ISD::FP_TO_UINT: {
2802     SDValue True, False;
2803     EVT VT =  Node->getOperand(0).getValueType();
2804     EVT NVT = Node->getValueType(0);
2805     APFloat apf(APInt::getNullValue(VT.getSizeInBits()));
2806     APInt x = APInt::getSignBit(NVT.getSizeInBits());
2807     (void)apf.convertFromAPInt(x, false, APFloat::rmNearestTiesToEven);
2808     Tmp1 = DAG.getConstantFP(apf, VT);
2809     Tmp2 = DAG.getSetCC(dl, TLI.getSetCCResultType(VT),
2810                         Node->getOperand(0),
2811                         Tmp1, ISD::SETLT);
2812     True = DAG.getNode(ISD::FP_TO_SINT, dl, NVT, Node->getOperand(0));
2813     False = DAG.getNode(ISD::FP_TO_SINT, dl, NVT,
2814                         DAG.getNode(ISD::FSUB, dl, VT,
2815                                     Node->getOperand(0), Tmp1));
2816     False = DAG.getNode(ISD::XOR, dl, NVT, False,
2817                         DAG.getConstant(x, NVT));
2818     Tmp1 = DAG.getNode(ISD::SELECT, dl, NVT, Tmp2, True, False);
2819     Results.push_back(Tmp1);
2820     break;
2821   }
2822   case ISD::VAARG: {
2823     const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
2824     EVT VT = Node->getValueType(0);
2825     Tmp1 = Node->getOperand(0);
2826     Tmp2 = Node->getOperand(1);
2827     unsigned Align = Node->getConstantOperandVal(3);
2828
2829     SDValue VAListLoad = DAG.getLoad(TLI.getPointerTy(), dl, Tmp1, Tmp2,
2830                                      MachinePointerInfo(V),
2831                                      false, false, false, 0);
2832     SDValue VAList = VAListLoad;
2833
2834     if (Align > TLI.getMinStackArgumentAlignment()) {
2835       assert(((Align & (Align-1)) == 0) && "Expected Align to be a power of 2");
2836
2837       VAList = DAG.getNode(ISD::ADD, dl, TLI.getPointerTy(), VAList,
2838                            DAG.getConstant(Align - 1,
2839                                            TLI.getPointerTy()));
2840
2841       VAList = DAG.getNode(ISD::AND, dl, TLI.getPointerTy(), VAList,
2842                            DAG.getConstant(-(int64_t)Align,
2843                                            TLI.getPointerTy()));
2844     }
2845
2846     // Increment the pointer, VAList, to the next vaarg
2847     Tmp3 = DAG.getNode(ISD::ADD, dl, TLI.getPointerTy(), VAList,
2848                        DAG.getConstant(TLI.getDataLayout()->
2849                           getTypeAllocSize(VT.getTypeForEVT(*DAG.getContext())),
2850                                        TLI.getPointerTy()));
2851     // Store the incremented VAList to the legalized pointer
2852     Tmp3 = DAG.getStore(VAListLoad.getValue(1), dl, Tmp3, Tmp2,
2853                         MachinePointerInfo(V), false, false, 0);
2854     // Load the actual argument out of the pointer VAList
2855     Results.push_back(DAG.getLoad(VT, dl, Tmp3, VAList, MachinePointerInfo(),
2856                                   false, false, false, 0));
2857     Results.push_back(Results[0].getValue(1));
2858     break;
2859   }
2860   case ISD::VACOPY: {
2861     // This defaults to loading a pointer from the input and storing it to the
2862     // output, returning the chain.
2863     const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
2864     const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
2865     Tmp1 = DAG.getLoad(TLI.getPointerTy(), dl, Node->getOperand(0),
2866                        Node->getOperand(2), MachinePointerInfo(VS),
2867                        false, false, false, 0);
2868     Tmp1 = DAG.getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
2869                         MachinePointerInfo(VD), false, false, 0);
2870     Results.push_back(Tmp1);
2871     break;
2872   }
2873   case ISD::EXTRACT_VECTOR_ELT:
2874     if (Node->getOperand(0).getValueType().getVectorNumElements() == 1)
2875       // This must be an access of the only element.  Return it.
2876       Tmp1 = DAG.getNode(ISD::BITCAST, dl, Node->getValueType(0),
2877                          Node->getOperand(0));
2878     else
2879       Tmp1 = ExpandExtractFromVectorThroughStack(SDValue(Node, 0));
2880     Results.push_back(Tmp1);
2881     break;
2882   case ISD::EXTRACT_SUBVECTOR:
2883     Results.push_back(ExpandExtractFromVectorThroughStack(SDValue(Node, 0)));
2884     break;
2885   case ISD::INSERT_SUBVECTOR:
2886     Results.push_back(ExpandInsertToVectorThroughStack(SDValue(Node, 0)));
2887     break;
2888   case ISD::CONCAT_VECTORS: {
2889     Results.push_back(ExpandVectorBuildThroughStack(Node));
2890     break;
2891   }
2892   case ISD::SCALAR_TO_VECTOR:
2893     Results.push_back(ExpandSCALAR_TO_VECTOR(Node));
2894     break;
2895   case ISD::INSERT_VECTOR_ELT:
2896     Results.push_back(ExpandINSERT_VECTOR_ELT(Node->getOperand(0),
2897                                               Node->getOperand(1),
2898                                               Node->getOperand(2), dl));
2899     break;
2900   case ISD::VECTOR_SHUFFLE: {
2901     SmallVector<int, 32> NewMask;
2902     ArrayRef<int> Mask = cast<ShuffleVectorSDNode>(Node)->getMask();
2903
2904     EVT VT = Node->getValueType(0);
2905     EVT EltVT = VT.getVectorElementType();
2906     SDValue Op0 = Node->getOperand(0);
2907     SDValue Op1 = Node->getOperand(1);
2908     if (!TLI.isTypeLegal(EltVT)) {
2909
2910       EVT NewEltVT = TLI.getTypeToTransformTo(*DAG.getContext(), EltVT);
2911
2912       // BUILD_VECTOR operands are allowed to be wider than the element type.
2913       // But if NewEltVT is smaller that EltVT the BUILD_VECTOR does not accept it
2914       if (NewEltVT.bitsLT(EltVT)) {
2915
2916         // Convert shuffle node.
2917         // If original node was v4i64 and the new EltVT is i32,
2918         // cast operands to v8i32 and re-build the mask.
2919
2920         // Calculate new VT, the size of the new VT should be equal to original.
2921         EVT NewVT = EVT::getVectorVT(*DAG.getContext(), NewEltVT,
2922                                       VT.getSizeInBits()/NewEltVT.getSizeInBits());
2923         assert(NewVT.bitsEq(VT));
2924
2925         // cast operands to new VT
2926         Op0 = DAG.getNode(ISD::BITCAST, dl, NewVT, Op0);
2927         Op1 = DAG.getNode(ISD::BITCAST, dl, NewVT, Op1);
2928
2929         // Convert the shuffle mask
2930         unsigned int factor = NewVT.getVectorNumElements()/VT.getVectorNumElements();
2931
2932         // EltVT gets smaller
2933         assert(factor > 0);
2934
2935         for (unsigned i = 0; i < VT.getVectorNumElements(); ++i) {
2936           if (Mask[i] < 0) {
2937             for (unsigned fi = 0; fi < factor; ++fi)
2938               NewMask.push_back(Mask[i]);
2939           }
2940           else {
2941             for (unsigned fi = 0; fi < factor; ++fi)
2942               NewMask.push_back(Mask[i]*factor+fi);
2943           }
2944         }
2945         Mask = NewMask;
2946         VT = NewVT;
2947       }
2948       EltVT = NewEltVT;
2949     }
2950     unsigned NumElems = VT.getVectorNumElements();
2951     SmallVector<SDValue, 16> Ops;
2952     for (unsigned i = 0; i != NumElems; ++i) {
2953       if (Mask[i] < 0) {
2954         Ops.push_back(DAG.getUNDEF(EltVT));
2955         continue;
2956       }
2957       unsigned Idx = Mask[i];
2958       if (Idx < NumElems)
2959         Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT,
2960                                   Op0,
2961                                   DAG.getIntPtrConstant(Idx)));
2962       else
2963         Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT,
2964                                   Op1,
2965                                   DAG.getIntPtrConstant(Idx - NumElems)));
2966     }
2967
2968     Tmp1 = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], Ops.size());
2969     // We may have changed the BUILD_VECTOR type. Cast it back to the Node type.
2970     Tmp1 = DAG.getNode(ISD::BITCAST, dl, Node->getValueType(0), Tmp1);
2971     Results.push_back(Tmp1);
2972     break;
2973   }
2974   case ISD::EXTRACT_ELEMENT: {
2975     EVT OpTy = Node->getOperand(0).getValueType();
2976     if (cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue()) {
2977       // 1 -> Hi
2978       Tmp1 = DAG.getNode(ISD::SRL, dl, OpTy, Node->getOperand(0),
2979                          DAG.getConstant(OpTy.getSizeInBits()/2,
2980                     TLI.getShiftAmountTy(Node->getOperand(0).getValueType())));
2981       Tmp1 = DAG.getNode(ISD::TRUNCATE, dl, Node->getValueType(0), Tmp1);
2982     } else {
2983       // 0 -> Lo
2984       Tmp1 = DAG.getNode(ISD::TRUNCATE, dl, Node->getValueType(0),
2985                          Node->getOperand(0));
2986     }
2987     Results.push_back(Tmp1);
2988     break;
2989   }
2990   case ISD::STACKSAVE:
2991     // Expand to CopyFromReg if the target set
2992     // StackPointerRegisterToSaveRestore.
2993     if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
2994       Results.push_back(DAG.getCopyFromReg(Node->getOperand(0), dl, SP,
2995                                            Node->getValueType(0)));
2996       Results.push_back(Results[0].getValue(1));
2997     } else {
2998       Results.push_back(DAG.getUNDEF(Node->getValueType(0)));
2999       Results.push_back(Node->getOperand(0));
3000     }
3001     break;
3002   case ISD::STACKRESTORE:
3003     // Expand to CopyToReg if the target set
3004     // StackPointerRegisterToSaveRestore.
3005     if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
3006       Results.push_back(DAG.getCopyToReg(Node->getOperand(0), dl, SP,
3007                                          Node->getOperand(1)));
3008     } else {
3009       Results.push_back(Node->getOperand(0));
3010     }
3011     break;
3012   case ISD::FCOPYSIGN:
3013     Results.push_back(ExpandFCOPYSIGN(Node));
3014     break;
3015   case ISD::FNEG:
3016     // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
3017     Tmp1 = DAG.getConstantFP(-0.0, Node->getValueType(0));
3018     Tmp1 = DAG.getNode(ISD::FSUB, dl, Node->getValueType(0), Tmp1,
3019                        Node->getOperand(0));
3020     Results.push_back(Tmp1);
3021     break;
3022   case ISD::FABS: {
3023     // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
3024     EVT VT = Node->getValueType(0);
3025     Tmp1 = Node->getOperand(0);
3026     Tmp2 = DAG.getConstantFP(0.0, VT);
3027     Tmp2 = DAG.getSetCC(dl, TLI.getSetCCResultType(Tmp1.getValueType()),
3028                         Tmp1, Tmp2, ISD::SETUGT);
3029     Tmp3 = DAG.getNode(ISD::FNEG, dl, VT, Tmp1);
3030     Tmp1 = DAG.getNode(ISD::SELECT, dl, VT, Tmp2, Tmp1, Tmp3);
3031     Results.push_back(Tmp1);
3032     break;
3033   }
3034   case ISD::FSQRT:
3035     Results.push_back(ExpandFPLibCall(Node, RTLIB::SQRT_F32, RTLIB::SQRT_F64,
3036                                       RTLIB::SQRT_F80, RTLIB::SQRT_PPCF128));
3037     break;
3038   case ISD::FSIN:
3039     Results.push_back(ExpandFPLibCall(Node, RTLIB::SIN_F32, RTLIB::SIN_F64,
3040                                       RTLIB::SIN_F80, RTLIB::SIN_PPCF128));
3041     break;
3042   case ISD::FCOS:
3043     Results.push_back(ExpandFPLibCall(Node, RTLIB::COS_F32, RTLIB::COS_F64,
3044                                       RTLIB::COS_F80, RTLIB::COS_PPCF128));
3045     break;
3046   case ISD::FLOG:
3047     Results.push_back(ExpandFPLibCall(Node, RTLIB::LOG_F32, RTLIB::LOG_F64,
3048                                       RTLIB::LOG_F80, RTLIB::LOG_PPCF128));
3049     break;
3050   case ISD::FLOG2:
3051     Results.push_back(ExpandFPLibCall(Node, RTLIB::LOG2_F32, RTLIB::LOG2_F64,
3052                                       RTLIB::LOG2_F80, RTLIB::LOG2_PPCF128));
3053     break;
3054   case ISD::FLOG10:
3055     Results.push_back(ExpandFPLibCall(Node, RTLIB::LOG10_F32, RTLIB::LOG10_F64,
3056                                       RTLIB::LOG10_F80, RTLIB::LOG10_PPCF128));
3057     break;
3058   case ISD::FEXP:
3059     Results.push_back(ExpandFPLibCall(Node, RTLIB::EXP_F32, RTLIB::EXP_F64,
3060                                       RTLIB::EXP_F80, RTLIB::EXP_PPCF128));
3061     break;
3062   case ISD::FEXP2:
3063     Results.push_back(ExpandFPLibCall(Node, RTLIB::EXP2_F32, RTLIB::EXP2_F64,
3064                                       RTLIB::EXP2_F80, RTLIB::EXP2_PPCF128));
3065     break;
3066   case ISD::FTRUNC:
3067     Results.push_back(ExpandFPLibCall(Node, RTLIB::TRUNC_F32, RTLIB::TRUNC_F64,
3068                                       RTLIB::TRUNC_F80, RTLIB::TRUNC_PPCF128));
3069     break;
3070   case ISD::FFLOOR:
3071     Results.push_back(ExpandFPLibCall(Node, RTLIB::FLOOR_F32, RTLIB::FLOOR_F64,
3072                                       RTLIB::FLOOR_F80, RTLIB::FLOOR_PPCF128));
3073     break;
3074   case ISD::FCEIL:
3075     Results.push_back(ExpandFPLibCall(Node, RTLIB::CEIL_F32, RTLIB::CEIL_F64,
3076                                       RTLIB::CEIL_F80, RTLIB::CEIL_PPCF128));
3077     break;
3078   case ISD::FRINT:
3079     Results.push_back(ExpandFPLibCall(Node, RTLIB::RINT_F32, RTLIB::RINT_F64,
3080                                       RTLIB::RINT_F80, RTLIB::RINT_PPCF128));
3081     break;
3082   case ISD::FNEARBYINT:
3083     Results.push_back(ExpandFPLibCall(Node, RTLIB::NEARBYINT_F32,
3084                                       RTLIB::NEARBYINT_F64,
3085                                       RTLIB::NEARBYINT_F80,
3086                                       RTLIB::NEARBYINT_PPCF128));
3087     break;
3088   case ISD::FPOWI:
3089     Results.push_back(ExpandFPLibCall(Node, RTLIB::POWI_F32, RTLIB::POWI_F64,
3090                                       RTLIB::POWI_F80, RTLIB::POWI_PPCF128));
3091     break;
3092   case ISD::FPOW:
3093     Results.push_back(ExpandFPLibCall(Node, RTLIB::POW_F32, RTLIB::POW_F64,
3094                                       RTLIB::POW_F80, RTLIB::POW_PPCF128));
3095     break;
3096   case ISD::FDIV:
3097     Results.push_back(ExpandFPLibCall(Node, RTLIB::DIV_F32, RTLIB::DIV_F64,
3098                                       RTLIB::DIV_F80, RTLIB::DIV_PPCF128));
3099     break;
3100   case ISD::FREM:
3101     Results.push_back(ExpandFPLibCall(Node, RTLIB::REM_F32, RTLIB::REM_F64,
3102                                       RTLIB::REM_F80, RTLIB::REM_PPCF128));
3103     break;
3104   case ISD::FMA:
3105     Results.push_back(ExpandFPLibCall(Node, RTLIB::FMA_F32, RTLIB::FMA_F64,
3106                                       RTLIB::FMA_F80, RTLIB::FMA_PPCF128));
3107     break;
3108   case ISD::FP16_TO_FP32:
3109     Results.push_back(ExpandLibCall(RTLIB::FPEXT_F16_F32, Node, false));
3110     break;
3111   case ISD::FP32_TO_FP16:
3112     Results.push_back(ExpandLibCall(RTLIB::FPROUND_F32_F16, Node, false));
3113     break;
3114   case ISD::ConstantFP: {
3115     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
3116     // Check to see if this FP immediate is already legal.
3117     // If this is a legal constant, turn it into a TargetConstantFP node.
3118     if (!TLI.isFPImmLegal(CFP->getValueAPF(), Node->getValueType(0)))
3119       Results.push_back(ExpandConstantFP(CFP, true));
3120     break;
3121   }
3122   case ISD::EHSELECTION: {
3123     unsigned Reg = TLI.getExceptionSelectorRegister();
3124     assert(Reg && "Can't expand to unknown register!");
3125     Results.push_back(DAG.getCopyFromReg(Node->getOperand(1), dl, Reg,
3126                                          Node->getValueType(0)));
3127     Results.push_back(Results[0].getValue(1));
3128     break;
3129   }
3130   case ISD::EXCEPTIONADDR: {
3131     unsigned Reg = TLI.getExceptionPointerRegister();
3132     assert(Reg && "Can't expand to unknown register!");
3133     Results.push_back(DAG.getCopyFromReg(Node->getOperand(0), dl, Reg,
3134                                          Node->getValueType(0)));
3135     Results.push_back(Results[0].getValue(1));
3136     break;
3137   }
3138   case ISD::FSUB: {
3139     EVT VT = Node->getValueType(0);
3140     assert(TLI.isOperationLegalOrCustom(ISD::FADD, VT) &&
3141            TLI.isOperationLegalOrCustom(ISD::FNEG, VT) &&
3142            "Don't know how to expand this FP subtraction!");
3143     Tmp1 = DAG.getNode(ISD::FNEG, dl, VT, Node->getOperand(1));
3144     Tmp1 = DAG.getNode(ISD::FADD, dl, VT, Node->getOperand(0), Tmp1);
3145     Results.push_back(Tmp1);
3146     break;
3147   }
3148   case ISD::SUB: {
3149     EVT VT = Node->getValueType(0);
3150     assert(TLI.isOperationLegalOrCustom(ISD::ADD, VT) &&
3151            TLI.isOperationLegalOrCustom(ISD::XOR, VT) &&
3152            "Don't know how to expand this subtraction!");
3153     Tmp1 = DAG.getNode(ISD::XOR, dl, VT, Node->getOperand(1),
3154                DAG.getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT));
3155     Tmp1 = DAG.getNode(ISD::ADD, dl, VT, Tmp1, DAG.getConstant(1, VT));
3156     Results.push_back(DAG.getNode(ISD::ADD, dl, VT, Node->getOperand(0), Tmp1));
3157     break;
3158   }
3159   case ISD::UREM:
3160   case ISD::SREM: {
3161     EVT VT = Node->getValueType(0);
3162     SDVTList VTs = DAG.getVTList(VT, VT);
3163     bool isSigned = Node->getOpcode() == ISD::SREM;
3164     unsigned DivOpc = isSigned ? ISD::SDIV : ISD::UDIV;
3165     unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM;
3166     Tmp2 = Node->getOperand(0);
3167     Tmp3 = Node->getOperand(1);
3168     if (TLI.isOperationLegalOrCustom(DivRemOpc, VT) ||
3169         (isDivRemLibcallAvailable(Node, isSigned, TLI) &&
3170          // If div is legal, it's better to do the normal expansion
3171          !TLI.isOperationLegalOrCustom(DivOpc, Node->getValueType(0)) &&
3172          useDivRem(Node, isSigned, false))) {
3173       Tmp1 = DAG.getNode(DivRemOpc, dl, VTs, Tmp2, Tmp3).getValue(1);
3174     } else if (TLI.isOperationLegalOrCustom(DivOpc, VT)) {
3175       // X % Y -> X-X/Y*Y
3176       Tmp1 = DAG.getNode(DivOpc, dl, VT, Tmp2, Tmp3);
3177       Tmp1 = DAG.getNode(ISD::MUL, dl, VT, Tmp1, Tmp3);
3178       Tmp1 = DAG.getNode(ISD::SUB, dl, VT, Tmp2, Tmp1);
3179     } else if (isSigned)
3180       Tmp1 = ExpandIntLibCall(Node, true,
3181                               RTLIB::SREM_I8,
3182                               RTLIB::SREM_I16, RTLIB::SREM_I32,
3183                               RTLIB::SREM_I64, RTLIB::SREM_I128);
3184     else
3185       Tmp1 = ExpandIntLibCall(Node, false,
3186                               RTLIB::UREM_I8,
3187                               RTLIB::UREM_I16, RTLIB::UREM_I32,
3188                               RTLIB::UREM_I64, RTLIB::UREM_I128);
3189     Results.push_back(Tmp1);
3190     break;
3191   }
3192   case ISD::UDIV:
3193   case ISD::SDIV: {
3194     bool isSigned = Node->getOpcode() == ISD::SDIV;
3195     unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM;
3196     EVT VT = Node->getValueType(0);
3197     SDVTList VTs = DAG.getVTList(VT, VT);
3198     if (TLI.isOperationLegalOrCustom(DivRemOpc, VT) ||
3199         (isDivRemLibcallAvailable(Node, isSigned, TLI) &&
3200          useDivRem(Node, isSigned, true)))
3201       Tmp1 = DAG.getNode(DivRemOpc, dl, VTs, Node->getOperand(0),
3202                          Node->getOperand(1));
3203     else if (isSigned)
3204       Tmp1 = ExpandIntLibCall(Node, true,
3205                               RTLIB::SDIV_I8,
3206                               RTLIB::SDIV_I16, RTLIB::SDIV_I32,
3207                               RTLIB::SDIV_I64, RTLIB::SDIV_I128);
3208     else
3209       Tmp1 = ExpandIntLibCall(Node, false,
3210                               RTLIB::UDIV_I8,
3211                               RTLIB::UDIV_I16, RTLIB::UDIV_I32,
3212                               RTLIB::UDIV_I64, RTLIB::UDIV_I128);
3213     Results.push_back(Tmp1);
3214     break;
3215   }
3216   case ISD::MULHU:
3217   case ISD::MULHS: {
3218     unsigned ExpandOpcode = Node->getOpcode() == ISD::MULHU ? ISD::UMUL_LOHI :
3219                                                               ISD::SMUL_LOHI;
3220     EVT VT = Node->getValueType(0);
3221     SDVTList VTs = DAG.getVTList(VT, VT);
3222     assert(TLI.isOperationLegalOrCustom(ExpandOpcode, VT) &&
3223            "If this wasn't legal, it shouldn't have been created!");
3224     Tmp1 = DAG.getNode(ExpandOpcode, dl, VTs, Node->getOperand(0),
3225                        Node->getOperand(1));
3226     Results.push_back(Tmp1.getValue(1));
3227     break;
3228   }
3229   case ISD::SDIVREM:
3230   case ISD::UDIVREM:
3231     // Expand into divrem libcall
3232     ExpandDivRemLibCall(Node, Results);
3233     break;
3234   case ISD::MUL: {
3235     EVT VT = Node->getValueType(0);
3236     SDVTList VTs = DAG.getVTList(VT, VT);
3237     // See if multiply or divide can be lowered using two-result operations.
3238     // We just need the low half of the multiply; try both the signed
3239     // and unsigned forms. If the target supports both SMUL_LOHI and
3240     // UMUL_LOHI, form a preference by checking which forms of plain
3241     // MULH it supports.
3242     bool HasSMUL_LOHI = TLI.isOperationLegalOrCustom(ISD::SMUL_LOHI, VT);
3243     bool HasUMUL_LOHI = TLI.isOperationLegalOrCustom(ISD::UMUL_LOHI, VT);
3244     bool HasMULHS = TLI.isOperationLegalOrCustom(ISD::MULHS, VT);
3245     bool HasMULHU = TLI.isOperationLegalOrCustom(ISD::MULHU, VT);
3246     unsigned OpToUse = 0;
3247     if (HasSMUL_LOHI && !HasMULHS) {
3248       OpToUse = ISD::SMUL_LOHI;
3249     } else if (HasUMUL_LOHI && !HasMULHU) {
3250       OpToUse = ISD::UMUL_LOHI;
3251     } else if (HasSMUL_LOHI) {
3252       OpToUse = ISD::SMUL_LOHI;
3253     } else if (HasUMUL_LOHI) {
3254       OpToUse = ISD::UMUL_LOHI;
3255     }
3256     if (OpToUse) {
3257       Results.push_back(DAG.getNode(OpToUse, dl, VTs, Node->getOperand(0),
3258                                     Node->getOperand(1)));
3259       break;
3260     }
3261     Tmp1 = ExpandIntLibCall(Node, false,
3262                             RTLIB::MUL_I8,
3263                             RTLIB::MUL_I16, RTLIB::MUL_I32,
3264                             RTLIB::MUL_I64, RTLIB::MUL_I128);
3265     Results.push_back(Tmp1);
3266     break;
3267   }
3268   case ISD::SADDO:
3269   case ISD::SSUBO: {
3270     SDValue LHS = Node->getOperand(0);
3271     SDValue RHS = Node->getOperand(1);
3272     SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::SADDO ?
3273                               ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
3274                               LHS, RHS);
3275     Results.push_back(Sum);
3276     EVT OType = Node->getValueType(1);
3277
3278     SDValue Zero = DAG.getConstant(0, LHS.getValueType());
3279
3280     //   LHSSign -> LHS >= 0
3281     //   RHSSign -> RHS >= 0
3282     //   SumSign -> Sum >= 0
3283     //
3284     //   Add:
3285     //   Overflow -> (LHSSign == RHSSign) && (LHSSign != SumSign)
3286     //   Sub:
3287     //   Overflow -> (LHSSign != RHSSign) && (LHSSign != SumSign)
3288     //
3289     SDValue LHSSign = DAG.getSetCC(dl, OType, LHS, Zero, ISD::SETGE);
3290     SDValue RHSSign = DAG.getSetCC(dl, OType, RHS, Zero, ISD::SETGE);
3291     SDValue SignsMatch = DAG.getSetCC(dl, OType, LHSSign, RHSSign,
3292                                       Node->getOpcode() == ISD::SADDO ?
3293                                       ISD::SETEQ : ISD::SETNE);
3294
3295     SDValue SumSign = DAG.getSetCC(dl, OType, Sum, Zero, ISD::SETGE);
3296     SDValue SumSignNE = DAG.getSetCC(dl, OType, LHSSign, SumSign, ISD::SETNE);
3297
3298     SDValue Cmp = DAG.getNode(ISD::AND, dl, OType, SignsMatch, SumSignNE);
3299     Results.push_back(Cmp);
3300     break;
3301   }
3302   case ISD::UADDO:
3303   case ISD::USUBO: {
3304     SDValue LHS = Node->getOperand(0);
3305     SDValue RHS = Node->getOperand(1);
3306     SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::UADDO ?
3307                               ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
3308                               LHS, RHS);
3309     Results.push_back(Sum);
3310     Results.push_back(DAG.getSetCC(dl, Node->getValueType(1), Sum, LHS,
3311                                    Node->getOpcode () == ISD::UADDO ?
3312                                    ISD::SETULT : ISD::SETUGT));
3313     break;
3314   }
3315   case ISD::UMULO:
3316   case ISD::SMULO: {
3317     EVT VT = Node->getValueType(0);
3318     EVT WideVT = EVT::getIntegerVT(*DAG.getContext(), VT.getSizeInBits() * 2);
3319     SDValue LHS = Node->getOperand(0);
3320     SDValue RHS = Node->getOperand(1);
3321     SDValue BottomHalf;
3322     SDValue TopHalf;
3323     static const unsigned Ops[2][3] =
3324         { { ISD::MULHU, ISD::UMUL_LOHI, ISD::ZERO_EXTEND },
3325           { ISD::MULHS, ISD::SMUL_LOHI, ISD::SIGN_EXTEND }};
3326     bool isSigned = Node->getOpcode() == ISD::SMULO;
3327     if (TLI.isOperationLegalOrCustom(Ops[isSigned][0], VT)) {
3328       BottomHalf = DAG.getNode(ISD::MUL, dl, VT, LHS, RHS);
3329       TopHalf = DAG.getNode(Ops[isSigned][0], dl, VT, LHS, RHS);
3330     } else if (TLI.isOperationLegalOrCustom(Ops[isSigned][1], VT)) {
3331       BottomHalf = DAG.getNode(Ops[isSigned][1], dl, DAG.getVTList(VT, VT), LHS,
3332                                RHS);
3333       TopHalf = BottomHalf.getValue(1);
3334     } else if (TLI.isTypeLegal(EVT::getIntegerVT(*DAG.getContext(),
3335                                                  VT.getSizeInBits() * 2))) {
3336       LHS = DAG.getNode(Ops[isSigned][2], dl, WideVT, LHS);
3337       RHS = DAG.getNode(Ops[isSigned][2], dl, WideVT, RHS);
3338       Tmp1 = DAG.getNode(ISD::MUL, dl, WideVT, LHS, RHS);
3339       BottomHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Tmp1,
3340                                DAG.getIntPtrConstant(0));
3341       TopHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Tmp1,
3342                             DAG.getIntPtrConstant(1));
3343     } else {
3344       // We can fall back to a libcall with an illegal type for the MUL if we
3345       // have a libcall big enough.
3346       // Also, we can fall back to a division in some cases, but that's a big
3347       // performance hit in the general case.
3348       RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
3349       if (WideVT == MVT::i16)
3350         LC = RTLIB::MUL_I16;
3351       else if (WideVT == MVT::i32)
3352         LC = RTLIB::MUL_I32;
3353       else if (WideVT == MVT::i64)
3354         LC = RTLIB::MUL_I64;
3355       else if (WideVT == MVT::i128)
3356         LC = RTLIB::MUL_I128;
3357       assert(LC != RTLIB::UNKNOWN_LIBCALL && "Cannot expand this operation!");
3358
3359       // The high part is obtained by SRA'ing all but one of the bits of low
3360       // part.
3361       unsigned LoSize = VT.getSizeInBits();
3362       SDValue HiLHS = DAG.getNode(ISD::SRA, dl, VT, RHS,
3363                                 DAG.getConstant(LoSize-1, TLI.getPointerTy()));
3364       SDValue HiRHS = DAG.getNode(ISD::SRA, dl, VT, LHS,
3365                                 DAG.getConstant(LoSize-1, TLI.getPointerTy()));
3366
3367       // Here we're passing the 2 arguments explicitly as 4 arguments that are
3368       // pre-lowered to the correct types. This all depends upon WideVT not
3369       // being a legal type for the architecture and thus has to be split to
3370       // two arguments.
3371       SDValue Args[] = { LHS, HiLHS, RHS, HiRHS };
3372       SDValue Ret = ExpandLibCall(LC, WideVT, Args, 4, isSigned, dl);
3373       BottomHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Ret,
3374                                DAG.getIntPtrConstant(0));
3375       TopHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Ret,
3376                             DAG.getIntPtrConstant(1));
3377       // Ret is a node with an illegal type. Because such things are not
3378       // generally permitted during this phase of legalization, delete the
3379       // node. The above EXTRACT_ELEMENT nodes should have been folded.
3380       DAG.DeleteNode(Ret.getNode());
3381     }
3382
3383     if (isSigned) {
3384       Tmp1 = DAG.getConstant(VT.getSizeInBits() - 1,
3385                              TLI.getShiftAmountTy(BottomHalf.getValueType()));
3386       Tmp1 = DAG.getNode(ISD::SRA, dl, VT, BottomHalf, Tmp1);
3387       TopHalf = DAG.getSetCC(dl, TLI.getSetCCResultType(VT), TopHalf, Tmp1,
3388                              ISD::SETNE);
3389     } else {
3390       TopHalf = DAG.getSetCC(dl, TLI.getSetCCResultType(VT), TopHalf,
3391                              DAG.getConstant(0, VT), ISD::SETNE);
3392     }
3393     Results.push_back(BottomHalf);
3394     Results.push_back(TopHalf);
3395     break;
3396   }
3397   case ISD::BUILD_PAIR: {
3398     EVT PairTy = Node->getValueType(0);
3399     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, PairTy, Node->getOperand(0));
3400     Tmp2 = DAG.getNode(ISD::ANY_EXTEND, dl, PairTy, Node->getOperand(1));
3401     Tmp2 = DAG.getNode(ISD::SHL, dl, PairTy, Tmp2,
3402                        DAG.getConstant(PairTy.getSizeInBits()/2,
3403                                        TLI.getShiftAmountTy(PairTy)));
3404     Results.push_back(DAG.getNode(ISD::OR, dl, PairTy, Tmp1, Tmp2));
3405     break;
3406   }
3407   case ISD::SELECT:
3408     Tmp1 = Node->getOperand(0);
3409     Tmp2 = Node->getOperand(1);
3410     Tmp3 = Node->getOperand(2);
3411     if (Tmp1.getOpcode() == ISD::SETCC) {
3412       Tmp1 = DAG.getSelectCC(dl, Tmp1.getOperand(0), Tmp1.getOperand(1),
3413                              Tmp2, Tmp3,
3414                              cast<CondCodeSDNode>(Tmp1.getOperand(2))->get());
3415     } else {
3416       Tmp1 = DAG.getSelectCC(dl, Tmp1,
3417                              DAG.getConstant(0, Tmp1.getValueType()),
3418                              Tmp2, Tmp3, ISD::SETNE);
3419     }
3420     Results.push_back(Tmp1);
3421     break;
3422   case ISD::BR_JT: {
3423     SDValue Chain = Node->getOperand(0);
3424     SDValue Table = Node->getOperand(1);
3425     SDValue Index = Node->getOperand(2);
3426
3427     EVT PTy = TLI.getPointerTy();
3428
3429     const DataLayout &TD = *TLI.getDataLayout();
3430     unsigned EntrySize =
3431       DAG.getMachineFunction().getJumpTableInfo()->getEntrySize(TD);
3432
3433     Index = DAG.getNode(ISD::MUL, dl, PTy,
3434                         Index, DAG.getConstant(EntrySize, PTy));
3435     SDValue Addr = DAG.getNode(ISD::ADD, dl, PTy, Index, Table);
3436
3437     EVT MemVT = EVT::getIntegerVT(*DAG.getContext(), EntrySize * 8);
3438     SDValue LD = DAG.getExtLoad(ISD::SEXTLOAD, dl, PTy, Chain, Addr,
3439                                 MachinePointerInfo::getJumpTable(), MemVT,
3440                                 false, false, 0);
3441     Addr = LD;
3442     if (TM.getRelocationModel() == Reloc::PIC_) {
3443       // For PIC, the sequence is:
3444       // BRIND(load(Jumptable + index) + RelocBase)
3445       // RelocBase can be JumpTable, GOT or some sort of global base.
3446       Addr = DAG.getNode(ISD::ADD, dl, PTy, Addr,
3447                           TLI.getPICJumpTableRelocBase(Table, DAG));
3448     }
3449     Tmp1 = DAG.getNode(ISD::BRIND, dl, MVT::Other, LD.getValue(1), Addr);
3450     Results.push_back(Tmp1);
3451     break;
3452   }
3453   case ISD::BRCOND:
3454     // Expand brcond's setcc into its constituent parts and create a BR_CC
3455     // Node.
3456     Tmp1 = Node->getOperand(0);
3457     Tmp2 = Node->getOperand(1);
3458     if (Tmp2.getOpcode() == ISD::SETCC) {
3459       Tmp1 = DAG.getNode(ISD::BR_CC, dl, MVT::Other,
3460                          Tmp1, Tmp2.getOperand(2),
3461                          Tmp2.getOperand(0), Tmp2.getOperand(1),
3462                          Node->getOperand(2));
3463     } else {
3464       // We test only the i1 bit.  Skip the AND if UNDEF.
3465       Tmp3 = (Tmp2.getOpcode() == ISD::UNDEF) ? Tmp2 :
3466         DAG.getNode(ISD::AND, dl, Tmp2.getValueType(), Tmp2,
3467                     DAG.getConstant(1, Tmp2.getValueType()));
3468       Tmp1 = DAG.getNode(ISD::BR_CC, dl, MVT::Other, Tmp1,
3469                          DAG.getCondCode(ISD::SETNE), Tmp3,
3470                          DAG.getConstant(0, Tmp3.getValueType()),
3471                          Node->getOperand(2));
3472     }
3473     Results.push_back(Tmp1);
3474     break;
3475   case ISD::SETCC: {
3476     Tmp1 = Node->getOperand(0);
3477     Tmp2 = Node->getOperand(1);
3478     Tmp3 = Node->getOperand(2);
3479     LegalizeSetCCCondCode(Node->getValueType(0), Tmp1, Tmp2, Tmp3, dl);
3480
3481     // If we expanded the SETCC into an AND/OR, return the new node
3482     if (Tmp2.getNode() == 0) {
3483       Results.push_back(Tmp1);
3484       break;
3485     }
3486
3487     // Otherwise, SETCC for the given comparison type must be completely
3488     // illegal; expand it into a SELECT_CC.
3489     EVT VT = Node->getValueType(0);
3490     Tmp1 = DAG.getNode(ISD::SELECT_CC, dl, VT, Tmp1, Tmp2,
3491                        DAG.getConstant(1, VT), DAG.getConstant(0, VT), Tmp3);
3492     Results.push_back(Tmp1);
3493     break;
3494   }
3495   case ISD::SELECT_CC: {
3496     Tmp1 = Node->getOperand(0);   // LHS
3497     Tmp2 = Node->getOperand(1);   // RHS
3498     Tmp3 = Node->getOperand(2);   // True
3499     Tmp4 = Node->getOperand(3);   // False
3500     SDValue CC = Node->getOperand(4);
3501
3502     LegalizeSetCCCondCode(TLI.getSetCCResultType(Tmp1.getValueType()),
3503                           Tmp1, Tmp2, CC, dl);
3504
3505     assert(!Tmp2.getNode() && "Can't legalize SELECT_CC with legal condition!");
3506     Tmp2 = DAG.getConstant(0, Tmp1.getValueType());
3507     CC = DAG.getCondCode(ISD::SETNE);
3508     Tmp1 = DAG.getNode(ISD::SELECT_CC, dl, Node->getValueType(0), Tmp1, Tmp2,
3509                        Tmp3, Tmp4, CC);
3510     Results.push_back(Tmp1);
3511     break;
3512   }
3513   case ISD::BR_CC: {
3514     Tmp1 = Node->getOperand(0);              // Chain
3515     Tmp2 = Node->getOperand(2);              // LHS
3516     Tmp3 = Node->getOperand(3);              // RHS
3517     Tmp4 = Node->getOperand(1);              // CC
3518
3519     LegalizeSetCCCondCode(TLI.getSetCCResultType(Tmp2.getValueType()),
3520                           Tmp2, Tmp3, Tmp4, dl);
3521
3522     assert(!Tmp3.getNode() && "Can't legalize BR_CC with legal condition!");
3523     Tmp3 = DAG.getConstant(0, Tmp2.getValueType());
3524     Tmp4 = DAG.getCondCode(ISD::SETNE);
3525     Tmp1 = DAG.getNode(ISD::BR_CC, dl, Node->getValueType(0), Tmp1, Tmp4, Tmp2,
3526                        Tmp3, Node->getOperand(4));
3527     Results.push_back(Tmp1);
3528     break;
3529   }
3530   case ISD::BUILD_VECTOR:
3531     Results.push_back(ExpandBUILD_VECTOR(Node));
3532     break;
3533   case ISD::SRA:
3534   case ISD::SRL:
3535   case ISD::SHL: {
3536     // Scalarize vector SRA/SRL/SHL.
3537     EVT VT = Node->getValueType(0);
3538     assert(VT.isVector() && "Unable to legalize non-vector shift");
3539     assert(TLI.isTypeLegal(VT.getScalarType())&& "Element type must be legal");
3540     unsigned NumElem = VT.getVectorNumElements();
3541
3542     SmallVector<SDValue, 8> Scalars;
3543     for (unsigned Idx = 0; Idx < NumElem; Idx++) {
3544       SDValue Ex = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
3545                                VT.getScalarType(),
3546                                Node->getOperand(0), DAG.getIntPtrConstant(Idx));
3547       SDValue Sh = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
3548                                VT.getScalarType(),
3549                                Node->getOperand(1), DAG.getIntPtrConstant(Idx));
3550       Scalars.push_back(DAG.getNode(Node->getOpcode(), dl,
3551                                     VT.getScalarType(), Ex, Sh));
3552     }
3553     SDValue Result =
3554       DAG.getNode(ISD::BUILD_VECTOR, dl, Node->getValueType(0),
3555                   &Scalars[0], Scalars.size());
3556     ReplaceNode(SDValue(Node, 0), Result);
3557     break;
3558   }
3559   case ISD::GLOBAL_OFFSET_TABLE:
3560   case ISD::GlobalAddress:
3561   case ISD::GlobalTLSAddress:
3562   case ISD::ExternalSymbol:
3563   case ISD::ConstantPool:
3564   case ISD::JumpTable:
3565   case ISD::INTRINSIC_W_CHAIN:
3566   case ISD::INTRINSIC_WO_CHAIN:
3567   case ISD::INTRINSIC_VOID:
3568     // FIXME: Custom lowering for these operations shouldn't return null!
3569     break;
3570   }
3571
3572   // Replace the original node with the legalized result.
3573   if (!Results.empty())
3574     ReplaceNode(Node, Results.data());
3575 }
3576
3577 void SelectionDAGLegalize::PromoteNode(SDNode *Node) {
3578   SmallVector<SDValue, 8> Results;
3579   MVT OVT = Node->getSimpleValueType(0);
3580   if (Node->getOpcode() == ISD::UINT_TO_FP ||
3581       Node->getOpcode() == ISD::SINT_TO_FP ||
3582       Node->getOpcode() == ISD::SETCC) {
3583     OVT = Node->getOperand(0).getSimpleValueType();
3584   }
3585   MVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
3586   DebugLoc dl = Node->getDebugLoc();
3587   SDValue Tmp1, Tmp2, Tmp3;
3588   switch (Node->getOpcode()) {
3589   case ISD::CTTZ:
3590   case ISD::CTTZ_ZERO_UNDEF:
3591   case ISD::CTLZ:
3592   case ISD::CTLZ_ZERO_UNDEF:
3593   case ISD::CTPOP:
3594     // Zero extend the argument.
3595     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Node->getOperand(0));
3596     // Perform the larger operation. For CTPOP and CTTZ_ZERO_UNDEF, this is
3597     // already the correct result.
3598     Tmp1 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1);
3599     if (Node->getOpcode() == ISD::CTTZ) {
3600       // FIXME: This should set a bit in the zero extended value instead.
3601       Tmp2 = DAG.getSetCC(dl, TLI.getSetCCResultType(NVT),
3602                           Tmp1, DAG.getConstant(NVT.getSizeInBits(), NVT),
3603                           ISD::SETEQ);
3604       Tmp1 = DAG.getNode(ISD::SELECT, dl, NVT, Tmp2,
3605                           DAG.getConstant(OVT.getSizeInBits(), NVT), Tmp1);
3606     } else if (Node->getOpcode() == ISD::CTLZ ||
3607                Node->getOpcode() == ISD::CTLZ_ZERO_UNDEF) {
3608       // Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
3609       Tmp1 = DAG.getNode(ISD::SUB, dl, NVT, Tmp1,
3610                           DAG.getConstant(NVT.getSizeInBits() -
3611                                           OVT.getSizeInBits(), NVT));
3612     }
3613     Results.push_back(DAG.getNode(ISD::TRUNCATE, dl, OVT, Tmp1));
3614     break;
3615   case ISD::BSWAP: {
3616     unsigned DiffBits = NVT.getSizeInBits() - OVT.getSizeInBits();
3617     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Node->getOperand(0));
3618     Tmp1 = DAG.getNode(ISD::BSWAP, dl, NVT, Tmp1);
3619     Tmp1 = DAG.getNode(ISD::SRL, dl, NVT, Tmp1,
3620                           DAG.getConstant(DiffBits, TLI.getShiftAmountTy(NVT)));
3621     Results.push_back(Tmp1);
3622     break;
3623   }
3624   case ISD::FP_TO_UINT:
3625   case ISD::FP_TO_SINT:
3626     Tmp1 = PromoteLegalFP_TO_INT(Node->getOperand(0), Node->getValueType(0),
3627                                  Node->getOpcode() == ISD::FP_TO_SINT, dl);
3628     Results.push_back(Tmp1);
3629     break;
3630   case ISD::UINT_TO_FP:
3631   case ISD::SINT_TO_FP:
3632     Tmp1 = PromoteLegalINT_TO_FP(Node->getOperand(0), Node->getValueType(0),
3633                                  Node->getOpcode() == ISD::SINT_TO_FP, dl);
3634     Results.push_back(Tmp1);
3635     break;
3636   case ISD::VAARG: {
3637     SDValue Chain = Node->getOperand(0); // Get the chain.
3638     SDValue Ptr = Node->getOperand(1); // Get the pointer.
3639
3640     unsigned TruncOp;
3641     if (OVT.isVector()) {
3642       TruncOp = ISD::BITCAST;
3643     } else {
3644       assert(OVT.isInteger()
3645         && "VAARG promotion is supported only for vectors or integer types");
3646       TruncOp = ISD::TRUNCATE;
3647     }
3648
3649     // Perform the larger operation, then convert back
3650     Tmp1 = DAG.getVAArg(NVT, dl, Chain, Ptr, Node->getOperand(2),
3651              Node->getConstantOperandVal(3));
3652     Chain = Tmp1.getValue(1);
3653
3654     Tmp2 = DAG.getNode(TruncOp, dl, OVT, Tmp1);
3655
3656     // Modified the chain result - switch anything that used the old chain to
3657     // use the new one.
3658     DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 0), Tmp2);
3659     DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 1), Chain);
3660     ReplacedNode(Node);
3661     break;
3662   }
3663   case ISD::AND:
3664   case ISD::OR:
3665   case ISD::XOR: {
3666     unsigned ExtOp, TruncOp;
3667     if (OVT.isVector()) {
3668       ExtOp   = ISD::BITCAST;
3669       TruncOp = ISD::BITCAST;
3670     } else {
3671       assert(OVT.isInteger() && "Cannot promote logic operation");
3672       ExtOp   = ISD::ANY_EXTEND;
3673       TruncOp = ISD::TRUNCATE;
3674     }
3675     // Promote each of the values to the new type.
3676     Tmp1 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(0));
3677     Tmp2 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(1));
3678     // Perform the larger operation, then convert back
3679     Tmp1 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1, Tmp2);
3680     Results.push_back(DAG.getNode(TruncOp, dl, OVT, Tmp1));
3681     break;
3682   }
3683   case ISD::SELECT: {
3684     unsigned ExtOp, TruncOp;
3685     if (Node->getValueType(0).isVector()) {
3686       ExtOp   = ISD::BITCAST;
3687       TruncOp = ISD::BITCAST;
3688     } else if (Node->getValueType(0).isInteger()) {
3689       ExtOp   = ISD::ANY_EXTEND;
3690       TruncOp = ISD::TRUNCATE;
3691     } else {
3692       ExtOp   = ISD::FP_EXTEND;
3693       TruncOp = ISD::FP_ROUND;
3694     }
3695     Tmp1 = Node->getOperand(0);
3696     // Promote each of the values to the new type.
3697     Tmp2 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(1));
3698     Tmp3 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(2));
3699     // Perform the larger operation, then round down.
3700     Tmp1 = DAG.getNode(ISD::SELECT, dl, NVT, Tmp1, Tmp2, Tmp3);
3701     if (TruncOp != ISD::FP_ROUND)
3702       Tmp1 = DAG.getNode(TruncOp, dl, Node->getValueType(0), Tmp1);
3703     else
3704       Tmp1 = DAG.getNode(TruncOp, dl, Node->getValueType(0), Tmp1,
3705                          DAG.getIntPtrConstant(0));
3706     Results.push_back(Tmp1);
3707     break;
3708   }
3709   case ISD::VECTOR_SHUFFLE: {
3710     ArrayRef<int> Mask = cast<ShuffleVectorSDNode>(Node)->getMask();
3711
3712     // Cast the two input vectors.
3713     Tmp1 = DAG.getNode(ISD::BITCAST, dl, NVT, Node->getOperand(0));
3714     Tmp2 = DAG.getNode(ISD::BITCAST, dl, NVT, Node->getOperand(1));
3715
3716     // Convert the shuffle mask to the right # elements.
3717     Tmp1 = ShuffleWithNarrowerEltType(NVT, OVT, dl, Tmp1, Tmp2, Mask);
3718     Tmp1 = DAG.getNode(ISD::BITCAST, dl, OVT, Tmp1);
3719     Results.push_back(Tmp1);
3720     break;
3721   }
3722   case ISD::SETCC: {
3723     unsigned ExtOp = ISD::FP_EXTEND;
3724     if (NVT.isInteger()) {
3725       ISD::CondCode CCCode =
3726         cast<CondCodeSDNode>(Node->getOperand(2))->get();
3727       ExtOp = isSignedIntSetCC(CCCode) ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
3728     }
3729     Tmp1 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(0));
3730     Tmp2 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(1));
3731     Results.push_back(DAG.getNode(ISD::SETCC, dl, Node->getValueType(0),
3732                                   Tmp1, Tmp2, Node->getOperand(2)));
3733     break;
3734   }
3735   case ISD::FDIV:
3736   case ISD::FREM:
3737   case ISD::FPOW: {
3738     Tmp1 = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Node->getOperand(0));
3739     Tmp2 = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Node->getOperand(1));
3740     Tmp3 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1, Tmp2);
3741     Results.push_back(DAG.getNode(ISD::FP_ROUND, dl, OVT,
3742                                   Tmp3, DAG.getIntPtrConstant(0)));
3743     break;
3744   }
3745   case ISD::FLOG2:
3746   case ISD::FEXP2:
3747   case ISD::FLOG:
3748   case ISD::FEXP: {
3749     Tmp1 = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Node->getOperand(0));
3750     Tmp2 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1);
3751     Results.push_back(DAG.getNode(ISD::FP_ROUND, dl, OVT,
3752                                   Tmp2, DAG.getIntPtrConstant(0)));
3753     break;
3754   }
3755   }
3756
3757   // Replace the original node with the legalized result.
3758   if (!Results.empty())
3759     ReplaceNode(Node, Results.data());
3760 }
3761
3762 // SelectionDAG::Legalize - This is the entry point for the file.
3763 //
3764 void SelectionDAG::Legalize() {
3765   /// run - This is the main entry point to this class.
3766   ///
3767   SelectionDAGLegalize(*this).LegalizeDAG();
3768 }