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