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 LegalizeINT_TO_FP(SDValue Result, bool isSigned, MVT DestTy,
 161                             SDValue Op, DebugLoc dl);
 162   SDValue ExpandLegalINT_TO_FP(bool isSigned, SDValue LegalOp, MVT DestVT,
 163                                DebugLoc dl);
 164   SDValue PromoteLegalINT_TO_FP(SDValue LegalOp, MVT DestVT, bool isSigned,
 165                                 DebugLoc dl);
 166   SDValue PromoteLegalFP_TO_INT(SDValue LegalOp, MVT DestVT, bool isSigned,
 167                                 DebugLoc dl);
 168
 169   SDValue ExpandBSWAP(SDValue Op, DebugLoc dl);
 170   SDValue ExpandBitCount(unsigned Opc, SDValue Op, DebugLoc dl);
 171
 172   SDValue ExpandEXTRACT_VECTOR_ELT(SDValue Op);
 173   SDValue ExpandExtractFromVectorThroughStack(SDValue Op);
 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   switch (Node->getOpcode()) {
 716   case ISD::FrameIndex:
 717   case ISD::EntryToken:
 718   case ISD::Register:
 719   case ISD::BasicBlock:
 720   case ISD::TargetFrameIndex:
 721   case ISD::TargetJumpTable:
 722   case ISD::TargetConstant:
 723   case ISD::TargetConstantFP:
 724   case ISD::TargetConstantPool:
 725   case ISD::TargetGlobalAddress:
 726   case ISD::TargetGlobalTLSAddress:
 727   case ISD::TargetExternalSymbol:
 728   case ISD::VALUETYPE:
 729   case ISD::SRCVALUE:
 730   case ISD::MEMOPERAND:
 731   case ISD::CONDCODE:
 732   case ISD::ARG_FLAGS:
 733     // Primitives must all be legal.
 734     assert(TLI.isOperationLegal(Node->getOpcode(), Node->getValueType(0)) &&
 735            "This must be legal!");
 736     break;
 737   default:
 738     if (Node->getOpcode() >= ISD::BUILTIN_OP_END) {
 739       // If this is a target node, legalize it by legalizing the operands then
 740       // passing it through.
 741       SmallVector<SDValue, 8> Ops;
 742       for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 743         Ops.push_back(LegalizeOp(Node->getOperand(i)));
 744
 745       Result = DAG.UpdateNodeOperands(Result.getValue(0), Ops.data(), Ops.size());
 746
 747       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 748         AddLegalizedOperand(Op.getValue(i), Result.getValue(i));
 749       return Result.getValue(Op.getResNo());
 750     }
 751     // Otherwise this is an unhandled builtin node.  splat.
 752 #ifndef NDEBUG
 753     cerr << "NODE: "; Node->dump(&DAG); cerr << "\n";
 754 #endif
 755     assert(0 && "Do not know how to legalize this operator!");
 756     abort();
 757   case ISD::GLOBAL_OFFSET_TABLE:
 758   case ISD::GlobalAddress:
 759   case ISD::GlobalTLSAddress:
 760   case ISD::ExternalSymbol:
 761   case ISD::ConstantPool:
 762   case ISD::JumpTable: // Nothing to do.
 763     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
 764     default: assert(0 && "This action is not supported yet!");
 765     case TargetLowering::Custom:
 766       Tmp1 = TLI.LowerOperation(Op, DAG);
 767       if (Tmp1.getNode()) Result = Tmp1;
 768       // FALLTHROUGH if the target doesn't want to lower this op after all.
 769     case TargetLowering::Legal:
 770       break;
 771     }
 772     break;
 773   case ISD::FRAMEADDR:
 774   case ISD::RETURNADDR:
 775     // The only option for these nodes is to custom lower them.  If the target
 776     // does not custom lower them, then return zero.
 777     Tmp1 = TLI.LowerOperation(Op, DAG);
 778     if (Tmp1.getNode())
 779       Result = Tmp1;
 780     else
 781       Result = DAG.getConstant(0, TLI.getPointerTy());
 782     break;
 783   case ISD::FRAME_TO_ARGS_OFFSET: {
 784     MVT VT = Node->getValueType(0);
 785     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
 786     default: assert(0 && "This action is not supported yet!");
 787     case TargetLowering::Custom:
 788       Result = TLI.LowerOperation(Op, DAG);
 789       if (Result.getNode()) break;
 790       // Fall Thru
 791     case TargetLowering::Legal:
 792       Result = DAG.getConstant(0, VT);
 793       break;
 794     }
 795     }
 796     break;
 797   case ISD::EXCEPTIONADDR: {
 798     Tmp1 = LegalizeOp(Node->getOperand(0));
 799     MVT VT = Node->getValueType(0);
 800     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
 801     default: assert(0 && "This action is not supported yet!");
 802     case TargetLowering::Expand: {
 803         unsigned Reg = TLI.getExceptionAddressRegister();
 804         Result = DAG.getCopyFromReg(Tmp1, dl, Reg, VT);
 805       }
 806       break;
 807     case TargetLowering::Custom:
 808       Result = TLI.LowerOperation(Op, DAG);
 809       if (Result.getNode()) break;
 810       // Fall Thru
 811     case TargetLowering::Legal: {
 812       SDValue Ops[] = { DAG.getConstant(0, VT), Tmp1 };
 813       Result = DAG.getMergeValues(Ops, 2, dl);
 814       break;
 815     }
 816     }
 817     }
 818     if (Result.getNode()->getNumValues() == 1) break;
 819
 820     assert(Result.getNode()->getNumValues() == 2 &&
 821            "Cannot return more than two values!");
 822
 823     // Since we produced two values, make sure to remember that we
 824     // legalized both of them.
 825     Tmp1 = LegalizeOp(Result);
 826     Tmp2 = LegalizeOp(Result.getValue(1));
 827     AddLegalizedOperand(Op.getValue(0), Tmp1);
 828     AddLegalizedOperand(Op.getValue(1), Tmp2);
 829     return Op.getResNo() ? Tmp2 : Tmp1;
 830   case ISD::EHSELECTION: {
 831     Tmp1 = LegalizeOp(Node->getOperand(0));
 832     Tmp2 = LegalizeOp(Node->getOperand(1));
 833     MVT VT = Node->getValueType(0);
 834     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
 835     default: assert(0 && "This action is not supported yet!");
 836     case TargetLowering::Expand: {
 837         unsigned Reg = TLI.getExceptionSelectorRegister();
 838         Result = DAG.getCopyFromReg(Tmp2, dl, Reg, VT);
 839       }
 840       break;
 841     case TargetLowering::Custom:
 842       Result = TLI.LowerOperation(Op, DAG);
 843       if (Result.getNode()) break;
 844       // Fall Thru
 845     case TargetLowering::Legal: {
 846       SDValue Ops[] = { DAG.getConstant(0, VT), Tmp2 };
 847       Result = DAG.getMergeValues(Ops, 2, dl);
 848       break;
 849     }
 850     }
 851     }
 852     if (Result.getNode()->getNumValues() == 1) break;
 853
 854     assert(Result.getNode()->getNumValues() == 2 &&
 855            "Cannot return more than two values!");
 856
 857     // Since we produced two values, make sure to remember that we
 858     // legalized both of them.
 859     Tmp1 = LegalizeOp(Result);
 860     Tmp2 = LegalizeOp(Result.getValue(1));
 861     AddLegalizedOperand(Op.getValue(0), Tmp1);
 862     AddLegalizedOperand(Op.getValue(1), Tmp2);
 863     return Op.getResNo() ? Tmp2 : Tmp1;
 864   case ISD::EH_RETURN: {
 865     MVT VT = Node->getValueType(0);
 866     // The only "good" option for this node is to custom lower it.
 867     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
 868     default: assert(0 && "This action is not supported at all!");
 869     case TargetLowering::Custom:
 870       Result = TLI.LowerOperation(Op, DAG);
 871       if (Result.getNode()) break;
 872       // Fall Thru
 873     case TargetLowering::Legal:
 874       // Target does not know, how to lower this, lower to noop
 875       Result = LegalizeOp(Node->getOperand(0));
 876       break;
 877     }
 878     }
 879     break;
 880   case ISD::AssertSext:
 881   case ISD::AssertZext:
 882     Tmp1 = LegalizeOp(Node->getOperand(0));
 883     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
 884     break;
 885   case ISD::MERGE_VALUES:
 886     // Legalize eliminates MERGE_VALUES nodes.
 887     Result = Node->getOperand(Op.getResNo());
 888     break;
 889   case ISD::CopyFromReg:
 890     Tmp1 = LegalizeOp(Node->getOperand(0));
 891     Result = Op.getValue(0);
 892     if (Node->getNumValues() == 2) {
 893       Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
 894     } else {
 895       assert(Node->getNumValues() == 3 && "Invalid copyfromreg!");
 896       if (Node->getNumOperands() == 3) {
 897         Tmp2 = LegalizeOp(Node->getOperand(2));
 898         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1),Tmp2);
 899       } else {
 900         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
 901       }
 902       AddLegalizedOperand(Op.getValue(2), Result.getValue(2));
 903     }
 904     // Since CopyFromReg produces two values, make sure to remember that we
 905     // legalized both of them.
 906     AddLegalizedOperand(Op.getValue(0), Result);
 907     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
 908     return Result.getValue(Op.getResNo());
 909   case ISD::UNDEF: {
 910     MVT VT = Op.getValueType();
 911     switch (TLI.getOperationAction(ISD::UNDEF, VT)) {
 912     default: assert(0 && "This action is not supported yet!");
 913     case TargetLowering::Expand:
 914       if (VT.isInteger())
 915         Result = DAG.getConstant(0, VT);
 916       else if (VT.isFloatingPoint())
 917         Result = DAG.getConstantFP(APFloat(APInt(VT.getSizeInBits(), 0)),
 918                                    VT);
 919       else
 920         assert(0 && "Unknown value type!");
 921       break;
 922     case TargetLowering::Legal:
 923       break;
 924     }
 925     break;
 926   }
 927
 928   case ISD::INTRINSIC_W_CHAIN:
 929   case ISD::INTRINSIC_WO_CHAIN:
 930   case ISD::INTRINSIC_VOID: {
 931     SmallVector<SDValue, 8> Ops;
 932     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 933       Ops.push_back(LegalizeOp(Node->getOperand(i)));
 934     Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
 935
 936     // Allow the target to custom lower its intrinsics if it wants to.
 937     if (TLI.getOperationAction(Node->getOpcode(), MVT::Other) ==
 938         TargetLowering::Custom) {
 939       Tmp3 = TLI.LowerOperation(Result, DAG);
 940       if (Tmp3.getNode()) Result = Tmp3;
 941     }
 942
 943     if (Result.getNode()->getNumValues() == 1) break;
 944
 945     // Must have return value and chain result.
 946     assert(Result.getNode()->getNumValues() == 2 &&
 947            "Cannot return more than two values!");
 948
 949     // Since loads produce two values, make sure to remember that we
 950     // legalized both of them.
 951     AddLegalizedOperand(SDValue(Node, 0), Result.getValue(0));
 952     AddLegalizedOperand(SDValue(Node, 1), Result.getValue(1));
 953     return Result.getValue(Op.getResNo());
 954   }
 955
 956   case ISD::DBG_STOPPOINT:
 957     assert(Node->getNumOperands() == 1 && "Invalid DBG_STOPPOINT node!");
 958     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the input chain.
 959
 960     switch (TLI.getOperationAction(ISD::DBG_STOPPOINT, MVT::Other)) {
 961     case TargetLowering::Promote:
 962     default: assert(0 && "This action is not supported yet!");
 963     case TargetLowering::Expand: {
 964       DwarfWriter *DW = DAG.getDwarfWriter();
 965       bool useDEBUG_LOC = TLI.isOperationLegalOrCustom(ISD::DEBUG_LOC,
 966                                                        MVT::Other);
 967       bool useLABEL = TLI.isOperationLegalOrCustom(ISD::DBG_LABEL, MVT::Other);
 968
 969       const DbgStopPointSDNode *DSP = cast<DbgStopPointSDNode>(Node);
 970       GlobalVariable *CU_GV = cast<GlobalVariable>(DSP->getCompileUnit());
 971       if (DW && (useDEBUG_LOC || useLABEL) && !CU_GV->isDeclaration()) {
 972         DICompileUnit CU(cast<GlobalVariable>(DSP->getCompileUnit()));
 973
 974         unsigned Line = DSP->getLine();
 975         unsigned Col = DSP->getColumn();
 976
 977         if (OptLevel == CodeGenOpt::None) {
 978           // A bit self-referential to have DebugLoc on Debug_Loc nodes, but it
 979           // won't hurt anything.
 980           if (useDEBUG_LOC) {
 981             SDValue Ops[] = { Tmp1, DAG.getConstant(Line, MVT::i32),
 982                               DAG.getConstant(Col, MVT::i32),
 983                               DAG.getSrcValue(CU.getGV()) };
 984             Result = DAG.getNode(ISD::DEBUG_LOC, dl, MVT::Other, Ops, 4);
 985           } else {
 986             unsigned ID = DW->RecordSourceLine(Line, Col, CU);
 987             Result = DAG.getLabel(ISD::DBG_LABEL, dl, Tmp1, ID);
 988           }
 989         } else {
 990           Result = Tmp1;  // chain
 991         }
 992       } else {
 993         Result = Tmp1;  // chain
 994       }
 995       break;
 996     }
 997    case TargetLowering::Custom:
 998       Result = TLI.LowerOperation(Op, DAG);
 999       if (Result.getNode())
1000         break;
1001     case TargetLowering::Legal: {
1002       if (Tmp1 == Node->getOperand(0))
1003         break;
1004
1005       SmallVector<SDValue, 8> Ops;
1006       Ops.push_back(Tmp1);
1007       Ops.push_back(Node->getOperand(1));  // line # must be legal.
1008       Ops.push_back(Node->getOperand(2));  // col # must be legal.
1009       Ops.push_back(Node->getOperand(3));  // filename must be legal.
1010       Ops.push_back(Node->getOperand(4));  // working dir # must be legal.
1011       Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1012       break;
1013     }
1014     }
1015     break;
1016
1017   case ISD::DECLARE:
1018     assert(Node->getNumOperands() == 3 && "Invalid DECLARE node!");
1019     switch (TLI.getOperationAction(ISD::DECLARE, MVT::Other)) {
1020     default: assert(0 && "This action is not supported yet!");
1021     case TargetLowering::Legal:
1022       Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1023       Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the address.
1024       Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the variable.
1025       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1026       break;
1027     case TargetLowering::Expand:
1028       Result = LegalizeOp(Node->getOperand(0));
1029       break;
1030     }
1031     break;
1032
1033   case ISD::DEBUG_LOC:
1034     assert(Node->getNumOperands() == 4 && "Invalid DEBUG_LOC node!");
1035     switch (TLI.getOperationAction(ISD::DEBUG_LOC, MVT::Other)) {
1036     default: assert(0 && "This action is not supported yet!");
1037     case TargetLowering::Legal: {
1038       Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1039       if (Tmp1 == Node->getOperand(0))
1040         break;
1041       Tmp2 = Node->getOperand(1);
1042       Tmp3 = Node->getOperand(2);
1043       Tmp4 = Node->getOperand(3);
1044       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4);
1045       break;
1046     }
1047     }
1048     break;
1049
1050   case ISD::DBG_LABEL:
1051   case ISD::EH_LABEL:
1052     assert(Node->getNumOperands() == 1 && "Invalid LABEL node!");
1053     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
1054     default: assert(0 && "This action is not supported yet!");
1055     case TargetLowering::Legal:
1056       Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1057       Result = DAG.UpdateNodeOperands(Result, Tmp1);
1058       break;
1059     case TargetLowering::Expand:
1060       Result = LegalizeOp(Node->getOperand(0));
1061       break;
1062     }
1063     break;
1064
1065   case ISD::PREFETCH:
1066     assert(Node->getNumOperands() == 4 && "Invalid Prefetch node!");
1067     switch (TLI.getOperationAction(ISD::PREFETCH, MVT::Other)) {
1068     default: assert(0 && "This action is not supported yet!");
1069     case TargetLowering::Legal:
1070       Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1071       Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the address.
1072       Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the rw specifier.
1073       Tmp4 = LegalizeOp(Node->getOperand(3));  // Legalize locality specifier.
1074       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4);
1075       break;
1076     case TargetLowering::Expand:
1077       // It's a noop.
1078       Result = LegalizeOp(Node->getOperand(0));
1079       break;
1080     }
1081     break;
1082
1083   case ISD::MEMBARRIER: {
1084     assert(Node->getNumOperands() == 6 && "Invalid MemBarrier node!");
1085     switch (TLI.getOperationAction(ISD::MEMBARRIER, MVT::Other)) {
1086     default: assert(0 && "This action is not supported yet!");
1087     case TargetLowering::Legal: {
1088       SDValue Ops[6];
1089       Ops[0] = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1090       for (int x = 1; x < 6; ++x) {
1091         Ops[x] = Node->getOperand(x);
1092       }
1093       Result = DAG.UpdateNodeOperands(Result, &Ops[0], 6);
1094       break;
1095     }
1096     case TargetLowering::Expand:
1097       //There is no libgcc call for this op
1098       Result = Node->getOperand(0);  // Noop
1099     break;
1100     }
1101     break;
1102   }
1103
1104   case ISD::ATOMIC_CMP_SWAP: {
1105     unsigned int num_operands = 4;
1106     assert(Node->getNumOperands() == num_operands && "Invalid Atomic node!");
1107     SDValue Ops[4];
1108     for (unsigned int x = 0; x < num_operands; ++x)
1109       Ops[x] = LegalizeOp(Node->getOperand(x));
1110     Result = DAG.UpdateNodeOperands(Result, &Ops[0], num_operands);
1111
1112     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1113       default: assert(0 && "This action is not supported yet!");
1114       case TargetLowering::Custom:
1115         Result = TLI.LowerOperation(Result, DAG);
1116         break;
1117       case TargetLowering::Legal:
1118         break;
1119     }
1120     AddLegalizedOperand(SDValue(Node, 0), Result.getValue(0));
1121     AddLegalizedOperand(SDValue(Node, 1), Result.getValue(1));
1122     return Result.getValue(Op.getResNo());
1123   }
1124   case ISD::ATOMIC_LOAD_ADD:
1125   case ISD::ATOMIC_LOAD_SUB:
1126   case ISD::ATOMIC_LOAD_AND:
1127   case ISD::ATOMIC_LOAD_OR:
1128   case ISD::ATOMIC_LOAD_XOR:
1129   case ISD::ATOMIC_LOAD_NAND:
1130   case ISD::ATOMIC_LOAD_MIN:
1131   case ISD::ATOMIC_LOAD_MAX:
1132   case ISD::ATOMIC_LOAD_UMIN:
1133   case ISD::ATOMIC_LOAD_UMAX:
1134   case ISD::ATOMIC_SWAP: {
1135     unsigned int num_operands = 3;
1136     assert(Node->getNumOperands() == num_operands && "Invalid Atomic node!");
1137     SDValue Ops[3];
1138     for (unsigned int x = 0; x < num_operands; ++x)
1139       Ops[x] = LegalizeOp(Node->getOperand(x));
1140     Result = DAG.UpdateNodeOperands(Result, &Ops[0], num_operands);
1141
1142     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1143     default: assert(0 && "This action is not supported yet!");
1144     case TargetLowering::Custom:
1145       Result = TLI.LowerOperation(Result, DAG);
1146       break;
1147     case TargetLowering::Legal:
1148       break;
1149     }
1150     AddLegalizedOperand(SDValue(Node, 0), Result.getValue(0));
1151     AddLegalizedOperand(SDValue(Node, 1), Result.getValue(1));
1152     return Result.getValue(Op.getResNo());
1153   }
1154   case ISD::Constant: {
1155     ConstantSDNode *CN = cast<ConstantSDNode>(Node);
1156     unsigned opAction =
1157       TLI.getOperationAction(ISD::Constant, CN->getValueType(0));
1158
1159     // We know we don't need to expand constants here, constants only have one
1160     // value and we check that it is fine above.
1161
1162     if (opAction == TargetLowering::Custom) {
1163       Tmp1 = TLI.LowerOperation(Result, DAG);
1164       if (Tmp1.getNode())
1165         Result = Tmp1;
1166     }
1167     break;
1168   }
1169   case ISD::ConstantFP: {
1170     // Spill FP immediates to the constant pool if the target cannot directly
1171     // codegen them.  Targets often have some immediate values that can be
1172     // efficiently generated into an FP register without a load.  We explicitly
1173     // leave these constants as ConstantFP nodes for the target to deal with.
1174     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
1175
1176     switch (TLI.getOperationAction(ISD::ConstantFP, CFP->getValueType(0))) {
1177     default: assert(0 && "This action is not supported yet!");
1178     case TargetLowering::Legal:
1179       break;
1180     case TargetLowering::Custom:
1181       Tmp3 = TLI.LowerOperation(Result, DAG);
1182       if (Tmp3.getNode()) {
1183         Result = Tmp3;
1184         break;
1185       }
1186       // FALLTHROUGH
1187     case TargetLowering::Expand: {
1188       // Check to see if this FP immediate is already legal.
1189       bool isLegal = false;
1190       for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
1191              E = TLI.legal_fpimm_end(); I != E; ++I) {
1192         if (CFP->isExactlyValue(*I)) {
1193           isLegal = true;
1194           break;
1195         }
1196       }
1197       // If this is a legal constant, turn it into a TargetConstantFP node.
1198       if (isLegal)
1199         break;
1200       Result = ExpandConstantFP(CFP, true, DAG, TLI);
1201     }
1202     }
1203     break;
1204   }
1205   case ISD::TokenFactor:
1206     if (Node->getNumOperands() == 2) {
1207       Tmp1 = LegalizeOp(Node->getOperand(0));
1208       Tmp2 = LegalizeOp(Node->getOperand(1));
1209       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1210     } else if (Node->getNumOperands() == 3) {
1211       Tmp1 = LegalizeOp(Node->getOperand(0));
1212       Tmp2 = LegalizeOp(Node->getOperand(1));
1213       Tmp3 = LegalizeOp(Node->getOperand(2));
1214       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1215     } else {
1216       SmallVector<SDValue, 8> Ops;
1217       // Legalize the operands.
1218       for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1219         Ops.push_back(LegalizeOp(Node->getOperand(i)));
1220       Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1221     }
1222     break;
1223
1224   case ISD::FORMAL_ARGUMENTS:
1225   case ISD::CALL:
1226     // The only option for this is to custom lower it.
1227     Tmp3 = TLI.LowerOperation(Result.getValue(0), DAG);
1228     assert(Tmp3.getNode() && "Target didn't custom lower this node!");
1229     // A call within a calling sequence must be legalized to something
1230     // other than the normal CALLSEQ_END.  Violating this gets Legalize
1231     // into an infinite loop.
1232     assert ((!IsLegalizingCall ||
1233              Node->getOpcode() != ISD::CALL ||
1234              Tmp3.getNode()->getOpcode() != ISD::CALLSEQ_END) &&
1235             "Nested CALLSEQ_START..CALLSEQ_END not supported.");
1236
1237     // The number of incoming and outgoing values should match; unless the final
1238     // outgoing value is a flag.
1239     assert((Tmp3.getNode()->getNumValues() == Result.getNode()->getNumValues() ||
1240             (Tmp3.getNode()->getNumValues() == Result.getNode()->getNumValues() + 1 &&
1241              Tmp3.getNode()->getValueType(Tmp3.getNode()->getNumValues() - 1) ==
1242                MVT::Flag)) &&
1243            "Lowering call/formal_arguments produced unexpected # results!");
1244
1245     // Since CALL/FORMAL_ARGUMENTS nodes produce multiple values, make sure to
1246     // remember that we legalized all of them, so it doesn't get relegalized.
1247     for (unsigned i = 0, e = Tmp3.getNode()->getNumValues(); i != e; ++i) {
1248       if (Tmp3.getNode()->getValueType(i) == MVT::Flag)
1249         continue;
1250       Tmp1 = LegalizeOp(Tmp3.getValue(i));
1251       if (Op.getResNo() == i)
1252         Tmp2 = Tmp1;
1253       AddLegalizedOperand(SDValue(Node, i), Tmp1);
1254     }
1255     return Tmp2;
1256   case ISD::BUILD_VECTOR:
1257     switch (TLI.getOperationAction(ISD::BUILD_VECTOR, Node->getValueType(0))) {
1258     default: assert(0 && "This action is not supported yet!");
1259     case TargetLowering::Custom:
1260       Tmp3 = TLI.LowerOperation(Result, DAG);
1261       if (Tmp3.getNode()) {
1262         Result = Tmp3;
1263         break;
1264       }
1265       // FALLTHROUGH
1266     case TargetLowering::Expand:
1267       Result = ExpandBUILD_VECTOR(Result.getNode());
1268       break;
1269     }
1270     break;
1271   case ISD::INSERT_VECTOR_ELT:
1272     Tmp1 = LegalizeOp(Node->getOperand(0));  // InVec
1273     Tmp3 = LegalizeOp(Node->getOperand(2));  // InEltNo
1274
1275     // The type of the value to insert may not be legal, even though the vector
1276     // type is legal.  Legalize/Promote accordingly.  We do not handle Expand
1277     // here.
1278     Tmp2 = LegalizeOp(Node->getOperand(1));
1279     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1280
1281     switch (TLI.getOperationAction(ISD::INSERT_VECTOR_ELT,
1282                                    Node->getValueType(0))) {
1283     default: assert(0 && "This action is not supported yet!");
1284     case TargetLowering::Legal:
1285       break;
1286     case TargetLowering::Custom:
1287       Tmp4 = TLI.LowerOperation(Result, DAG);
1288       if (Tmp4.getNode()) {
1289         Result = Tmp4;
1290         break;
1291       }
1292       // FALLTHROUGH
1293     case TargetLowering::Promote:
1294       // Fall thru for vector case
1295     case TargetLowering::Expand: {
1296       // If the insert index is a constant, codegen this as a scalar_to_vector,
1297       // then a shuffle that inserts it into the right position in the vector.
1298       if (ConstantSDNode *InsertPos = dyn_cast<ConstantSDNode>(Tmp3)) {
1299         // SCALAR_TO_VECTOR requires that the type of the value being inserted
1300         // match the element type of the vector being created, except for
1301         // integers in which case the inserted value can be over width.
1302         MVT EltVT = Op.getValueType().getVectorElementType();
1303         if (Tmp2.getValueType() == EltVT ||
1304             (EltVT.isInteger() && Tmp2.getValueType().bitsGE(EltVT))) {
1305           SDValue ScVec = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl,
1306                                       Tmp1.getValueType(), Tmp2);
1307
1308           unsigned NumElts = Tmp1.getValueType().getVectorNumElements();
1309           // We generate a shuffle of InVec and ScVec, so the shuffle mask
1310           // should be 0,1,2,3,4,5... with the appropriate element replaced with
1311           // elt 0 of the RHS.
1312           SmallVector<int, 8> ShufOps;
1313           for (unsigned i = 0; i != NumElts; ++i)
1314             ShufOps.push_back(i != InsertPos->getZExtValue() ? i : NumElts);
1315
1316           Result = DAG.getVectorShuffle(Tmp1.getValueType(), dl, Tmp1, ScVec,
1317                                         &ShufOps[0]);
1318           Result = LegalizeOp(Result);
1319           break;
1320         }
1321       }
1322       Result = PerformInsertVectorEltInMemory(Tmp1, Tmp2, Tmp3, dl);
1323       break;
1324     }
1325     }
1326     break;
1327   case ISD::SCALAR_TO_VECTOR:
1328     Tmp1 = LegalizeOp(Node->getOperand(0));  // InVal
1329     Result = DAG.UpdateNodeOperands(Result, Tmp1);
1330     switch (TLI.getOperationAction(ISD::SCALAR_TO_VECTOR,
1331                                    Node->getValueType(0))) {
1332     default: assert(0 && "This action is not supported yet!");
1333     case TargetLowering::Legal:
1334       break;
1335     case TargetLowering::Custom:
1336       Tmp3 = TLI.LowerOperation(Result, DAG);
1337       if (Tmp3.getNode()) {
1338         Result = Tmp3;
1339         break;
1340       }
1341       // FALLTHROUGH
1342     case TargetLowering::Expand:
1343       Result = LegalizeOp(ExpandSCALAR_TO_VECTOR(Node));
1344       break;
1345     }
1346     break;
1347   case ISD::VECTOR_SHUFFLE: {
1348     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the input vectors,
1349     Tmp2 = LegalizeOp(Node->getOperand(1));   // but not the shuffle mask.
1350     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1351     MVT VT = Result.getValueType();
1352
1353     // Copy the Mask to a local SmallVector for use with isShuffleMaskLegal.
1354     SmallVector<int, 8> Mask;
1355     cast<ShuffleVectorSDNode>(Result)->getMask(Mask);
1356
1357     // Allow targets to custom lower the SHUFFLEs they support.
1358     switch (TLI.getOperationAction(ISD::VECTOR_SHUFFLE, VT)) {
1359     default: assert(0 && "Unknown operation action!");
1360     case TargetLowering::Legal:
1361       assert(TLI.isShuffleMaskLegal(Mask, VT) &&
1362              "vector shuffle should not be created if not legal!");
1363       break;
1364     case TargetLowering::Custom:
1365       Tmp3 = TLI.LowerOperation(Result, DAG);
1366       if (Tmp3.getNode()) {
1367         Result = Tmp3;
1368         break;
1369       }
1370       // FALLTHROUGH
1371     case TargetLowering::Expand: {
1372       MVT EltVT = VT.getVectorElementType();
1373       unsigned NumElems = VT.getVectorNumElements();
1374       SmallVector<SDValue, 8> Ops;
1375       for (unsigned i = 0; i != NumElems; ++i) {
1376         if (Mask[i] < 0) {
1377           Ops.push_back(DAG.getUNDEF(EltVT));
1378           continue;
1379         }
1380         unsigned Idx = Mask[i];
1381         if (Idx < NumElems)
1382           Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Tmp1,
1383                                     DAG.getIntPtrConstant(Idx)));
1384         else
1385           Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Tmp2,
1386                                     DAG.getIntPtrConstant(Idx - NumElems)));
1387       }
1388       Result = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], Ops.size());
1389       break;
1390     }
1391     case TargetLowering::Promote: {
1392       // Change base type to a different vector type.
1393       MVT OVT = Node->getValueType(0);
1394       MVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
1395
1396       // Cast the two input vectors.
1397       Tmp1 = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Tmp1);
1398       Tmp2 = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Tmp2);
1399
1400       // Convert the shuffle mask to the right # elements.
1401       Result = ShuffleWithNarrowerEltType(NVT, OVT, dl, Tmp1, Tmp2, Mask);
1402       Result = DAG.getNode(ISD::BIT_CONVERT, dl, OVT, Result);
1403       break;
1404     }
1405     }
1406     break;
1407   }
1408   case ISD::EXTRACT_VECTOR_ELT:
1409     Tmp1 = Node->getOperand(0);
1410     Tmp2 = LegalizeOp(Node->getOperand(1));
1411     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1412     Result = ExpandEXTRACT_VECTOR_ELT(Result);
1413     break;
1414
1415   case ISD::EXTRACT_SUBVECTOR:
1416     Tmp1 = LegalizeOp(Node->getOperand(0));
1417     Tmp2 = LegalizeOp(Node->getOperand(1));
1418     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1419
1420     switch (TLI.getOperationAction(ISD::EXTRACT_SUBVECTOR,
1421                                    Node->getValueType(0))) {
1422     default: assert(0 && "Unknown operation action!");
1423     case TargetLowering::Legal:
1424       break;
1425     case TargetLowering::Custom:
1426       Tmp3 = TLI.LowerOperation(Result, DAG);
1427       if (Tmp3.getNode()) {
1428         Result = Tmp3;
1429         break;
1430       }
1431       // FALLTHROUGH
1432     case TargetLowering::Expand: {
1433       Result = ExpandExtractFromVectorThroughStack(Result);
1434       break;
1435     }
1436     }
1437     break;
1438
1439   case ISD::CONCAT_VECTORS: {
1440     // Legalize the operands.
1441     SmallVector<SDValue, 8> Ops;
1442     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1443       Ops.push_back(LegalizeOp(Node->getOperand(i)));
1444     Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1445
1446     switch (TLI.getOperationAction(ISD::CONCAT_VECTORS,
1447                                    Node->getValueType(0))) {
1448     default: assert(0 && "Unknown operation action!");
1449     case TargetLowering::Legal:
1450       break;
1451     case TargetLowering::Custom:
1452       Tmp3 = TLI.LowerOperation(Result, DAG);
1453       if (Tmp3.getNode()) {
1454         Result = Tmp3;
1455         break;
1456       }
1457       // FALLTHROUGH
1458     case TargetLowering::Expand: {
1459       // Use extract/insert/build vector for now. We might try to be
1460       // more clever later.
1461       MVT PtrVT = TLI.getPointerTy();
1462       SmallVector<SDValue, 8> Ops;
1463       unsigned NumOperands = Node->getNumOperands();
1464       for (unsigned i=0; i < NumOperands; ++i) {
1465         SDValue SubOp = Node->getOperand(i);
1466         MVT VVT = SubOp.getNode()->getValueType(0);
1467         MVT EltVT = VVT.getVectorElementType();
1468         unsigned NumSubElem = VVT.getVectorNumElements();
1469         for (unsigned j=0; j < NumSubElem; ++j) {
1470           Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, SubOp,
1471                                     DAG.getConstant(j, PtrVT)));
1472         }
1473       }
1474       return LegalizeOp(DAG.getNode(ISD::BUILD_VECTOR, dl,
1475                                     Node->getValueType(0),
1476                                     &Ops[0], Ops.size()));
1477     }
1478     }
1479     break;
1480   }
1481
1482   case ISD::CALLSEQ_START: {
1483     SDNode *CallEnd = FindCallEndFromCallStart(Node);
1484
1485     // Recursively Legalize all of the inputs of the call end that do not lead
1486     // to this call start.  This ensures that any libcalls that need be inserted
1487     // are inserted *before* the CALLSEQ_START.
1488     {SmallPtrSet<SDNode*, 32> NodesLeadingTo;
1489     for (unsigned i = 0, e = CallEnd->getNumOperands(); i != e; ++i)
1490       LegalizeAllNodesNotLeadingTo(CallEnd->getOperand(i).getNode(), Node,
1491                                    NodesLeadingTo);
1492     }
1493
1494     // Now that we legalized all of the inputs (which may have inserted
1495     // libcalls) create the new CALLSEQ_START node.
1496     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1497
1498     // Merge in the last call, to ensure that this call start after the last
1499     // call ended.
1500     if (LastCALLSEQ_END.getOpcode() != ISD::EntryToken) {
1501       Tmp1 = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
1502                          Tmp1, LastCALLSEQ_END);
1503       Tmp1 = LegalizeOp(Tmp1);
1504     }
1505
1506     // Do not try to legalize the target-specific arguments (#1+).
1507     if (Tmp1 != Node->getOperand(0)) {
1508       SmallVector<SDValue, 8> Ops(Node->op_begin(), Node->op_end());
1509       Ops[0] = Tmp1;
1510       Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1511     }
1512
1513     // Remember that the CALLSEQ_START is legalized.
1514     AddLegalizedOperand(Op.getValue(0), Result);
1515     if (Node->getNumValues() == 2)    // If this has a flag result, remember it.
1516       AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1517
1518     // Now that the callseq_start and all of the non-call nodes above this call
1519     // sequence have been legalized, legalize the call itself.  During this
1520     // process, no libcalls can/will be inserted, guaranteeing that no calls
1521     // can overlap.
1522     assert(!IsLegalizingCall && "Inconsistent sequentialization of calls!");
1523     // Note that we are selecting this call!
1524     LastCALLSEQ_END = SDValue(CallEnd, 0);
1525     IsLegalizingCall = true;
1526
1527     // Legalize the call, starting from the CALLSEQ_END.
1528     LegalizeOp(LastCALLSEQ_END);
1529     assert(!IsLegalizingCall && "CALLSEQ_END should have cleared this!");
1530     return Result;
1531   }
1532   case ISD::CALLSEQ_END:
1533     // If the CALLSEQ_START node hasn't been legalized first, legalize it.  This
1534     // will cause this node to be legalized as well as handling libcalls right.
1535     if (LastCALLSEQ_END.getNode() != Node) {
1536       LegalizeOp(SDValue(FindCallStartFromCallEnd(Node), 0));
1537       DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op);
1538       assert(I != LegalizedNodes.end() &&
1539              "Legalizing the call start should have legalized this node!");
1540       return I->second;
1541     }
1542
1543     // Otherwise, the call start has been legalized and everything is going
1544     // according to plan.  Just legalize ourselves normally here.
1545     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1546     // Do not try to legalize the target-specific arguments (#1+), except for
1547     // an optional flag input.
1548     if (Node->getOperand(Node->getNumOperands()-1).getValueType() != MVT::Flag){
1549       if (Tmp1 != Node->getOperand(0)) {
1550         SmallVector<SDValue, 8> Ops(Node->op_begin(), Node->op_end());
1551         Ops[0] = Tmp1;
1552         Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1553       }
1554     } else {
1555       Tmp2 = LegalizeOp(Node->getOperand(Node->getNumOperands()-1));
1556       if (Tmp1 != Node->getOperand(0) ||
1557           Tmp2 != Node->getOperand(Node->getNumOperands()-1)) {
1558         SmallVector<SDValue, 8> Ops(Node->op_begin(), Node->op_end());
1559         Ops[0] = Tmp1;
1560         Ops.back() = Tmp2;
1561         Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1562       }
1563     }
1564     assert(IsLegalizingCall && "Call sequence imbalance between start/end?");
1565     // This finishes up call legalization.
1566     IsLegalizingCall = false;
1567
1568     // If the CALLSEQ_END node has a flag, remember that we legalized it.
1569     AddLegalizedOperand(SDValue(Node, 0), Result.getValue(0));
1570     if (Node->getNumValues() == 2)
1571       AddLegalizedOperand(SDValue(Node, 1), Result.getValue(1));
1572     return Result.getValue(Op.getResNo());
1573   case ISD::DYNAMIC_STACKALLOC: {
1574     MVT VT = Node->getValueType(0);
1575     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1576     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
1577     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
1578     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1579
1580     Tmp1 = Result.getValue(0);
1581     Tmp2 = Result.getValue(1);
1582     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
1583     default: assert(0 && "This action is not supported yet!");
1584     case TargetLowering::Expand: {
1585       unsigned SPReg = TLI.getStackPointerRegisterToSaveRestore();
1586       assert(SPReg && "Target cannot require DYNAMIC_STACKALLOC expansion and"
1587              " not tell us which reg is the stack pointer!");
1588       SDValue Chain = Tmp1.getOperand(0);
1589
1590       // Chain the dynamic stack allocation so that it doesn't modify the stack
1591       // pointer when other instructions are using the stack.
1592       Chain = DAG.getCALLSEQ_START(Chain, DAG.getIntPtrConstant(0, true));
1593
1594       SDValue Size  = Tmp2.getOperand(1);
1595       SDValue SP = DAG.getCopyFromReg(Chain, dl, SPReg, VT);
1596       Chain = SP.getValue(1);
1597       unsigned Align = cast<ConstantSDNode>(Tmp3)->getZExtValue();
1598       unsigned StackAlign =
1599         TLI.getTargetMachine().getFrameInfo()->getStackAlignment();
1600       if (Align > StackAlign)
1601         SP = DAG.getNode(ISD::AND, dl, VT, SP,
1602                          DAG.getConstant(-(uint64_t)Align, VT));
1603       Tmp1 = DAG.getNode(ISD::SUB, dl, VT, SP, Size);       // Value
1604       Chain = DAG.getCopyToReg(Chain, dl, SPReg, Tmp1);     // Output chain
1605
1606       Tmp2 = DAG.getCALLSEQ_END(Chain,  DAG.getIntPtrConstant(0, true),
1607                                 DAG.getIntPtrConstant(0, true), SDValue());
1608
1609       Tmp1 = LegalizeOp(Tmp1);
1610       Tmp2 = LegalizeOp(Tmp2);
1611       break;
1612     }
1613     case TargetLowering::Custom:
1614       Tmp3 = TLI.LowerOperation(Tmp1, DAG);
1615       if (Tmp3.getNode()) {
1616         Tmp1 = LegalizeOp(Tmp3);
1617         Tmp2 = LegalizeOp(Tmp3.getValue(1));
1618       }
1619       break;
1620     case TargetLowering::Legal:
1621       break;
1622     }
1623     // Since this op produce two values, make sure to remember that we
1624     // legalized both of them.
1625     AddLegalizedOperand(SDValue(Node, 0), Tmp1);
1626     AddLegalizedOperand(SDValue(Node, 1), Tmp2);
1627     return Op.getResNo() ? Tmp2 : Tmp1;
1628   }
1629   case ISD::INLINEASM: {
1630     SmallVector<SDValue, 8> Ops(Node->op_begin(), Node->op_end());
1631     bool Changed = false;
1632     // Legalize all of the operands of the inline asm, in case they are nodes
1633     // that need to be expanded or something.  Note we skip the asm string and
1634     // all of the TargetConstant flags.
1635     SDValue Op = LegalizeOp(Ops[0]);
1636     Changed = Op != Ops[0];
1637     Ops[0] = Op;
1638
1639     bool HasInFlag = Ops.back().getValueType() == MVT::Flag;
1640     for (unsigned i = 2, e = Ops.size()-HasInFlag; i < e; ) {
1641       unsigned NumVals = InlineAsm::
1642         getNumOperandRegisters(cast<ConstantSDNode>(Ops[i])->getZExtValue());
1643       for (++i; NumVals; ++i, --NumVals) {
1644         SDValue Op = LegalizeOp(Ops[i]);
1645         if (Op != Ops[i]) {
1646           Changed = true;
1647           Ops[i] = Op;
1648         }
1649       }
1650     }
1651
1652     if (HasInFlag) {
1653       Op = LegalizeOp(Ops.back());
1654       Changed |= Op != Ops.back();
1655       Ops.back() = Op;
1656     }
1657
1658     if (Changed)
1659       Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1660
1661     // INLINE asm returns a chain and flag, make sure to add both to the map.
1662     AddLegalizedOperand(SDValue(Node, 0), Result.getValue(0));
1663     AddLegalizedOperand(SDValue(Node, 1), Result.getValue(1));
1664     return Result.getValue(Op.getResNo());
1665   }
1666   case ISD::BR:
1667     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1668     // Ensure that libcalls are emitted before a branch.
1669     Tmp1 = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Tmp1, LastCALLSEQ_END);
1670     Tmp1 = LegalizeOp(Tmp1);
1671     LastCALLSEQ_END = DAG.getEntryNode();
1672
1673     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
1674     break;
1675   case ISD::BRIND:
1676     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1677     // Ensure that libcalls are emitted before a branch.
1678     Tmp1 = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Tmp1, LastCALLSEQ_END);
1679     Tmp1 = LegalizeOp(Tmp1);
1680     LastCALLSEQ_END = DAG.getEntryNode();
1681
1682     Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
1683     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1684     break;
1685   case ISD::BR_JT:
1686     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1687     // Ensure that libcalls are emitted before a branch.
1688     Tmp1 = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Tmp1, LastCALLSEQ_END);
1689     Tmp1 = LegalizeOp(Tmp1);
1690     LastCALLSEQ_END = DAG.getEntryNode();
1691
1692     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the jumptable node.
1693     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1694
1695     switch (TLI.getOperationAction(ISD::BR_JT, MVT::Other)) {
1696     default: assert(0 && "This action is not supported yet!");
1697     case TargetLowering::Legal: break;
1698     case TargetLowering::Custom:
1699       Tmp1 = TLI.LowerOperation(Result, DAG);
1700       if (Tmp1.getNode()) Result = Tmp1;
1701       break;
1702     case TargetLowering::Expand: {
1703       SDValue Chain = Result.getOperand(0);
1704       SDValue Table = Result.getOperand(1);
1705       SDValue Index = Result.getOperand(2);
1706
1707       MVT PTy = TLI.getPointerTy();
1708       MachineFunction &MF = DAG.getMachineFunction();
1709       unsigned EntrySize = MF.getJumpTableInfo()->getEntrySize();
1710       Index= DAG.getNode(ISD::MUL, dl, PTy,
1711                          Index, DAG.getConstant(EntrySize, PTy));
1712       SDValue Addr = DAG.getNode(ISD::ADD, dl, PTy, Index, Table);
1713
1714       MVT MemVT = MVT::getIntegerVT(EntrySize * 8);
1715       SDValue LD = DAG.getExtLoad(ISD::SEXTLOAD, dl, PTy, Chain, Addr,
1716                                   PseudoSourceValue::getJumpTable(), 0, MemVT);
1717       Addr = LD;
1718       if (TLI.getTargetMachine().getRelocationModel() == Reloc::PIC_) {
1719         // For PIC, the sequence is:
1720         // BRIND(load(Jumptable + index) + RelocBase)
1721         // RelocBase can be JumpTable, GOT or some sort of global base.
1722         Addr = DAG.getNode(ISD::ADD, dl, PTy, Addr,
1723                            TLI.getPICJumpTableRelocBase(Table, DAG));
1724       }
1725       Result = DAG.getNode(ISD::BRIND, dl, MVT::Other, LD.getValue(1), Addr);
1726     }
1727     }
1728     break;
1729   case ISD::BRCOND:
1730     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1731     // Ensure that libcalls are emitted before a return.
1732     Tmp1 = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Tmp1, LastCALLSEQ_END);
1733     Tmp1 = LegalizeOp(Tmp1);
1734     LastCALLSEQ_END = DAG.getEntryNode();
1735
1736     Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
1737
1738     // Basic block destination (Op#2) is always legal.
1739     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1740
1741     switch (TLI.getOperationAction(ISD::BRCOND, MVT::Other)) {
1742     default: assert(0 && "This action is not supported yet!");
1743     case TargetLowering::Legal: break;
1744     case TargetLowering::Custom:
1745       Tmp1 = TLI.LowerOperation(Result, DAG);
1746       if (Tmp1.getNode()) Result = Tmp1;
1747       break;
1748     case TargetLowering::Expand:
1749       // Expand brcond's setcc into its constituent parts and create a BR_CC
1750       // Node.
1751       if (Tmp2.getOpcode() == ISD::SETCC) {
1752         Result = DAG.getNode(ISD::BR_CC, dl, MVT::Other,
1753                              Tmp1, Tmp2.getOperand(2),
1754                              Tmp2.getOperand(0), Tmp2.getOperand(1),
1755                              Node->getOperand(2));
1756       } else {
1757         Result = DAG.getNode(ISD::BR_CC, dl, MVT::Other, Tmp1,
1758                              DAG.getCondCode(ISD::SETNE), Tmp2,
1759                              DAG.getConstant(0, Tmp2.getValueType()),
1760                              Node->getOperand(2));
1761       }
1762       break;
1763     }
1764     break;
1765   case ISD::BR_CC:
1766     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1767     // Ensure that libcalls are emitted before a branch.
1768     Tmp1 = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Tmp1, LastCALLSEQ_END);
1769     Tmp1 = LegalizeOp(Tmp1);
1770     Tmp2 = Node->getOperand(2);              // LHS
1771     Tmp3 = Node->getOperand(3);              // RHS
1772     Tmp4 = Node->getOperand(1);              // CC
1773
1774     LegalizeSetCC(TLI.getSetCCResultType(Tmp2.getValueType()),
1775                   Tmp2, Tmp3, Tmp4, dl);
1776     LastCALLSEQ_END = DAG.getEntryNode();
1777
1778     // If we didn't get both a LHS and RHS back from LegalizeSetCC,
1779     // the LHS is a legal SETCC itself.  In this case, we need to compare
1780     // the result against zero to select between true and false values.
1781     if (Tmp3.getNode() == 0) {
1782       Tmp3 = DAG.getConstant(0, Tmp2.getValueType());
1783       Tmp4 = DAG.getCondCode(ISD::SETNE);
1784     }
1785
1786     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp4, Tmp2, Tmp3,
1787                                     Node->getOperand(4));
1788
1789     switch (TLI.getOperationAction(ISD::BR_CC, Tmp3.getValueType())) {
1790     default: assert(0 && "Unexpected action for BR_CC!");
1791     case TargetLowering::Legal: break;
1792     case TargetLowering::Custom:
1793       Tmp4 = TLI.LowerOperation(Result, DAG);
1794       if (Tmp4.getNode()) Result = Tmp4;
1795       break;
1796     }
1797     break;
1798   case ISD::LOAD: {
1799     LoadSDNode *LD = cast<LoadSDNode>(Node);
1800     Tmp1 = LegalizeOp(LD->getChain());   // Legalize the chain.
1801     Tmp2 = LegalizeOp(LD->getBasePtr()); // Legalize the base pointer.
1802
1803     ISD::LoadExtType ExtType = LD->getExtensionType();
1804     if (ExtType == ISD::NON_EXTLOAD) {
1805       MVT VT = Node->getValueType(0);
1806       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, LD->getOffset());
1807       Tmp3 = Result.getValue(0);
1808       Tmp4 = Result.getValue(1);
1809
1810       switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
1811       default: assert(0 && "This action is not supported yet!");
1812       case TargetLowering::Legal:
1813         // If this is an unaligned load and the target doesn't support it,
1814         // expand it.
1815         if (!TLI.allowsUnalignedMemoryAccesses()) {
1816           unsigned ABIAlignment = TLI.getTargetData()->
1817             getABITypeAlignment(LD->getMemoryVT().getTypeForMVT());
1818           if (LD->getAlignment() < ABIAlignment){
1819             Result = ExpandUnalignedLoad(cast<LoadSDNode>(Result.getNode()), DAG,
1820                                          TLI);
1821             Tmp3 = Result.getOperand(0);
1822             Tmp4 = Result.getOperand(1);
1823             Tmp3 = LegalizeOp(Tmp3);
1824             Tmp4 = LegalizeOp(Tmp4);
1825           }
1826         }
1827         break;
1828       case TargetLowering::Custom:
1829         Tmp1 = TLI.LowerOperation(Tmp3, DAG);
1830         if (Tmp1.getNode()) {
1831           Tmp3 = LegalizeOp(Tmp1);
1832           Tmp4 = LegalizeOp(Tmp1.getValue(1));
1833         }
1834         break;
1835       case TargetLowering::Promote: {
1836         // Only promote a load of vector type to another.
1837         assert(VT.isVector() && "Cannot promote this load!");
1838         // Change base type to a different vector type.
1839         MVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), VT);
1840
1841         Tmp1 = DAG.getLoad(NVT, dl, Tmp1, Tmp2, LD->getSrcValue(),
1842                            LD->getSrcValueOffset(),
1843                            LD->isVolatile(), LD->getAlignment());
1844         Tmp3 = LegalizeOp(DAG.getNode(ISD::BIT_CONVERT, dl, VT, Tmp1));
1845         Tmp4 = LegalizeOp(Tmp1.getValue(1));
1846         break;
1847       }
1848       }
1849       // Since loads produce two values, make sure to remember that we
1850       // legalized both of them.
1851       AddLegalizedOperand(SDValue(Node, 0), Tmp3);
1852       AddLegalizedOperand(SDValue(Node, 1), Tmp4);
1853       return Op.getResNo() ? Tmp4 : Tmp3;
1854     } else {
1855       MVT SrcVT = LD->getMemoryVT();
1856       unsigned SrcWidth = SrcVT.getSizeInBits();
1857       int SVOffset = LD->getSrcValueOffset();
1858       unsigned Alignment = LD->getAlignment();
1859       bool isVolatile = LD->isVolatile();
1860
1861       if (SrcWidth != SrcVT.getStoreSizeInBits() &&
1862           // Some targets pretend to have an i1 loading operation, and actually
1863           // load an i8.  This trick is correct for ZEXTLOAD because the top 7
1864           // bits are guaranteed to be zero; it helps the optimizers understand
1865           // that these bits are zero.  It is also useful for EXTLOAD, since it
1866           // tells the optimizers that those bits are undefined.  It would be
1867           // nice to have an effective generic way of getting these benefits...
1868           // Until such a way is found, don't insist on promoting i1 here.
1869           (SrcVT != MVT::i1 ||
1870            TLI.getLoadExtAction(ExtType, MVT::i1) == TargetLowering::Promote)) {
1871         // Promote to a byte-sized load if not loading an integral number of
1872         // bytes.  For example, promote EXTLOAD:i20 -> EXTLOAD:i24.
1873         unsigned NewWidth = SrcVT.getStoreSizeInBits();
1874         MVT NVT = MVT::getIntegerVT(NewWidth);
1875         SDValue Ch;
1876
1877         // The extra bits are guaranteed to be zero, since we stored them that
1878         // way.  A zext load from NVT thus automatically gives zext from SrcVT.
1879
1880         ISD::LoadExtType NewExtType =
1881           ExtType == ISD::ZEXTLOAD ? ISD::ZEXTLOAD : ISD::EXTLOAD;
1882
1883         Result = DAG.getExtLoad(NewExtType, dl, Node->getValueType(0),
1884                                 Tmp1, Tmp2, LD->getSrcValue(), SVOffset,
1885                                 NVT, isVolatile, Alignment);
1886
1887         Ch = Result.getValue(1); // The chain.
1888
1889         if (ExtType == ISD::SEXTLOAD)
1890           // Having the top bits zero doesn't help when sign extending.
1891           Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl,
1892                                Result.getValueType(),
1893                                Result, DAG.getValueType(SrcVT));
1894         else if (ExtType == ISD::ZEXTLOAD || NVT == Result.getValueType())
1895           // All the top bits are guaranteed to be zero - inform the optimizers.
1896           Result = DAG.getNode(ISD::AssertZext, dl,
1897                                Result.getValueType(), Result,
1898                                DAG.getValueType(SrcVT));
1899
1900         Tmp1 = LegalizeOp(Result);
1901         Tmp2 = LegalizeOp(Ch);
1902       } else if (SrcWidth & (SrcWidth - 1)) {
1903         // If not loading a power-of-2 number of bits, expand as two loads.
1904         assert(SrcVT.isExtended() && !SrcVT.isVector() &&
1905                "Unsupported extload!");
1906         unsigned RoundWidth = 1 << Log2_32(SrcWidth);
1907         assert(RoundWidth < SrcWidth);
1908         unsigned ExtraWidth = SrcWidth - RoundWidth;
1909         assert(ExtraWidth < RoundWidth);
1910         assert(!(RoundWidth % 8) && !(ExtraWidth % 8) &&
1911                "Load size not an integral number of bytes!");
1912         MVT RoundVT = MVT::getIntegerVT(RoundWidth);
1913         MVT ExtraVT = MVT::getIntegerVT(ExtraWidth);
1914         SDValue Lo, Hi, Ch;
1915         unsigned IncrementSize;
1916
1917         if (TLI.isLittleEndian()) {
1918           // EXTLOAD:i24 -> ZEXTLOAD:i16 | (shl EXTLOAD@+2:i8, 16)
1919           // Load the bottom RoundWidth bits.
1920           Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl,
1921                               Node->getValueType(0), Tmp1, Tmp2,
1922                               LD->getSrcValue(), SVOffset, RoundVT, isVolatile,
1923                               Alignment);
1924
1925           // Load the remaining ExtraWidth bits.
1926           IncrementSize = RoundWidth / 8;
1927           Tmp2 = DAG.getNode(ISD::ADD, dl, Tmp2.getValueType(), Tmp2,
1928                              DAG.getIntPtrConstant(IncrementSize));
1929           Hi = DAG.getExtLoad(ExtType, dl, Node->getValueType(0), Tmp1, Tmp2,
1930                               LD->getSrcValue(), SVOffset + IncrementSize,
1931                               ExtraVT, isVolatile,
1932                               MinAlign(Alignment, IncrementSize));
1933
1934           // Build a factor node to remember that this load is independent of the
1935           // other one.
1936           Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1937                            Hi.getValue(1));
1938
1939           // Move the top bits to the right place.
1940           Hi = DAG.getNode(ISD::SHL, dl, Hi.getValueType(), Hi,
1941                            DAG.getConstant(RoundWidth, TLI.getShiftAmountTy()));
1942
1943           // Join the hi and lo parts.
1944           Result = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi);
1945         } else {
1946           // Big endian - avoid unaligned loads.
1947           // EXTLOAD:i24 -> (shl EXTLOAD:i16, 8) | ZEXTLOAD@+2:i8
1948           // Load the top RoundWidth bits.
1949           Hi = DAG.getExtLoad(ExtType, dl, Node->getValueType(0), Tmp1, Tmp2,
1950                               LD->getSrcValue(), SVOffset, RoundVT, isVolatile,
1951                               Alignment);
1952
1953           // Load the remaining ExtraWidth bits.
1954           IncrementSize = RoundWidth / 8;
1955           Tmp2 = DAG.getNode(ISD::ADD, dl, Tmp2.getValueType(), Tmp2,
1956                              DAG.getIntPtrConstant(IncrementSize));
1957           Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl,
1958                               Node->getValueType(0), Tmp1, Tmp2,
1959                               LD->getSrcValue(), SVOffset + IncrementSize,
1960                               ExtraVT, isVolatile,
1961                               MinAlign(Alignment, IncrementSize));
1962
1963           // Build a factor node to remember that this load is independent of the
1964           // other one.
1965           Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1966                            Hi.getValue(1));
1967
1968           // Move the top bits to the right place.
1969           Hi = DAG.getNode(ISD::SHL, dl, Hi.getValueType(), Hi,
1970                            DAG.getConstant(ExtraWidth, TLI.getShiftAmountTy()));
1971
1972           // Join the hi and lo parts.
1973           Result = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi);
1974         }
1975
1976         Tmp1 = LegalizeOp(Result);
1977         Tmp2 = LegalizeOp(Ch);
1978       } else {
1979         switch (TLI.getLoadExtAction(ExtType, SrcVT)) {
1980         default: assert(0 && "This action is not supported yet!");
1981         case TargetLowering::Custom:
1982           isCustom = true;
1983           // FALLTHROUGH
1984         case TargetLowering::Legal:
1985           Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, LD->getOffset());
1986           Tmp1 = Result.getValue(0);
1987           Tmp2 = Result.getValue(1);
1988
1989           if (isCustom) {
1990             Tmp3 = TLI.LowerOperation(Result, DAG);
1991             if (Tmp3.getNode()) {
1992               Tmp1 = LegalizeOp(Tmp3);
1993               Tmp2 = LegalizeOp(Tmp3.getValue(1));
1994             }
1995           } else {
1996             // If this is an unaligned load and the target doesn't support it,
1997             // expand it.
1998             if (!TLI.allowsUnalignedMemoryAccesses()) {
1999               unsigned ABIAlignment = TLI.getTargetData()->
2000                 getABITypeAlignment(LD->getMemoryVT().getTypeForMVT());
2001               if (LD->getAlignment() < ABIAlignment){
2002                 Result = ExpandUnalignedLoad(cast<LoadSDNode>(Result.getNode()), DAG,
2003                                              TLI);
2004                 Tmp1 = Result.getOperand(0);
2005                 Tmp2 = Result.getOperand(1);
2006                 Tmp1 = LegalizeOp(Tmp1);
2007                 Tmp2 = LegalizeOp(Tmp2);
2008               }
2009             }
2010           }
2011           break;
2012         case TargetLowering::Expand:
2013           // f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND
2014           if (SrcVT == MVT::f32 && Node->getValueType(0) == MVT::f64) {
2015             SDValue Load = DAG.getLoad(SrcVT, dl, Tmp1, Tmp2, LD->getSrcValue(),
2016                                          LD->getSrcValueOffset(),
2017                                          LD->isVolatile(), LD->getAlignment());
2018             Result = DAG.getNode(ISD::FP_EXTEND, dl,
2019                                  Node->getValueType(0), Load);
2020             Tmp1 = LegalizeOp(Result);  // Relegalize new nodes.
2021             Tmp2 = LegalizeOp(Load.getValue(1));
2022             break;
2023           }
2024           assert(ExtType != ISD::EXTLOAD &&"EXTLOAD should always be supported!");
2025           // Turn the unsupported load into an EXTLOAD followed by an explicit
2026           // zero/sign extend inreg.
2027           Result = DAG.getExtLoad(ISD::EXTLOAD, dl, Node->getValueType(0),
2028                                   Tmp1, Tmp2, LD->getSrcValue(),
2029                                   LD->getSrcValueOffset(), SrcVT,
2030                                   LD->isVolatile(), LD->getAlignment());
2031           SDValue ValRes;
2032           if (ExtType == ISD::SEXTLOAD)
2033             ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl,
2034                                  Result.getValueType(),
2035                                  Result, DAG.getValueType(SrcVT));
2036           else
2037             ValRes = DAG.getZeroExtendInReg(Result, dl, SrcVT);
2038           Tmp1 = LegalizeOp(ValRes);  // Relegalize new nodes.
2039           Tmp2 = LegalizeOp(Result.getValue(1));  // Relegalize new nodes.
2040           break;
2041         }
2042       }
2043
2044       // Since loads produce two values, make sure to remember that we legalized
2045       // both of them.
2046       AddLegalizedOperand(SDValue(Node, 0), Tmp1);
2047       AddLegalizedOperand(SDValue(Node, 1), Tmp2);
2048       return Op.getResNo() ? Tmp2 : Tmp1;
2049     }
2050   }
2051   case ISD::EXTRACT_ELEMENT: {
2052     MVT OpTy = Node->getOperand(0).getValueType();
2053     if (cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue()) {
2054       // 1 -> Hi
2055       Result = DAG.getNode(ISD::SRL, dl, OpTy, Node->getOperand(0),
2056                            DAG.getConstant(OpTy.getSizeInBits()/2,
2057                                            TLI.getShiftAmountTy()));
2058       Result = DAG.getNode(ISD::TRUNCATE, dl, Node->getValueType(0), Result);
2059     } else {
2060       // 0 -> Lo
2061       Result = DAG.getNode(ISD::TRUNCATE, dl, Node->getValueType(0),
2062                            Node->getOperand(0));
2063     }
2064     break;
2065   }
2066
2067   case ISD::CopyToReg:
2068     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2069
2070     // Legalize the incoming value (must be a legal type).
2071     Tmp2 = LegalizeOp(Node->getOperand(2));
2072     if (Node->getNumValues() == 1) {
2073       Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1), Tmp2);
2074     } else {
2075       assert(Node->getNumValues() == 2 && "Unknown CopyToReg");
2076       if (Node->getNumOperands() == 4) {
2077         Tmp3 = LegalizeOp(Node->getOperand(3));
2078         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1), Tmp2,
2079                                         Tmp3);
2080       } else {
2081         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1),Tmp2);
2082       }
2083
2084       // Since this produces two values, make sure to remember that we legalized
2085       // both of them.
2086       AddLegalizedOperand(SDValue(Node, 0), Result.getValue(0));
2087       AddLegalizedOperand(SDValue(Node, 1), Result.getValue(1));
2088       return Result;
2089     }
2090     break;
2091
2092   case ISD::RET:
2093     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2094
2095     // Ensure that libcalls are emitted before a return.
2096     Tmp1 = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Tmp1, LastCALLSEQ_END);
2097     Tmp1 = LegalizeOp(Tmp1);
2098     LastCALLSEQ_END = DAG.getEntryNode();
2099
2100     switch (Node->getNumOperands()) {
2101     case 3:  // ret val
2102       Tmp2 = Node->getOperand(1);
2103       Tmp3 = Node->getOperand(2);  // Signness
2104       Result = DAG.UpdateNodeOperands(Result, Tmp1, LegalizeOp(Tmp2), Tmp3);
2105       break;
2106     case 1:  // ret void
2107       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2108       break;
2109     default: { // ret <values>
2110       SmallVector<SDValue, 8> NewValues;
2111       NewValues.push_back(Tmp1);
2112       for (unsigned i = 1, e = Node->getNumOperands(); i < e; i += 2) {
2113         NewValues.push_back(LegalizeOp(Node->getOperand(i)));
2114         NewValues.push_back(Node->getOperand(i+1));
2115       }
2116       Result = DAG.UpdateNodeOperands(Result, &NewValues[0],NewValues.size());
2117       break;
2118     }
2119     }
2120
2121     switch (TLI.getOperationAction(Result.getOpcode(), MVT::Other)) {
2122     default: assert(0 && "This action is not supported yet!");
2123     case TargetLowering::Legal: break;
2124     case TargetLowering::Custom:
2125       Tmp1 = TLI.LowerOperation(Result, DAG);
2126       if (Tmp1.getNode()) Result = Tmp1;
2127       break;
2128     }
2129     break;
2130   case ISD::STORE: {
2131     StoreSDNode *ST = cast<StoreSDNode>(Node);
2132     Tmp1 = LegalizeOp(ST->getChain());    // Legalize the chain.
2133     Tmp2 = LegalizeOp(ST->getBasePtr());  // Legalize the pointer.
2134     int SVOffset = ST->getSrcValueOffset();
2135     unsigned Alignment = ST->getAlignment();
2136     bool isVolatile = ST->isVolatile();
2137
2138     if (!ST->isTruncatingStore()) {
2139       // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
2140       // FIXME: We shouldn't do this for TargetConstantFP's.
2141       // FIXME: move this to the DAG Combiner!  Note that we can't regress due
2142       // to phase ordering between legalized code and the dag combiner.  This
2143       // probably means that we need to integrate dag combiner and legalizer
2144       // together.
2145       // We generally can't do this one for long doubles.
2146       if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(ST->getValue())) {
2147         if (CFP->getValueType(0) == MVT::f32 &&
2148             getTypeAction(MVT::i32) == Legal) {
2149           Tmp3 = DAG.getConstant(CFP->getValueAPF().
2150                                           bitcastToAPInt().zextOrTrunc(32),
2151                                   MVT::i32);
2152           Result = DAG.getStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(),
2153                                 SVOffset, isVolatile, Alignment);
2154           break;
2155         } else if (CFP->getValueType(0) == MVT::f64) {
2156           // If this target supports 64-bit registers, do a single 64-bit store.
2157           if (getTypeAction(MVT::i64) == Legal) {
2158             Tmp3 = DAG.getConstant(CFP->getValueAPF().bitcastToAPInt().
2159                                      zextOrTrunc(64), MVT::i64);
2160             Result = DAG.getStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(),
2161                                   SVOffset, isVolatile, Alignment);
2162             break;
2163           } else if (getTypeAction(MVT::i32) == Legal && !ST->isVolatile()) {
2164             // Otherwise, if the target supports 32-bit registers, use 2 32-bit
2165             // stores.  If the target supports neither 32- nor 64-bits, this
2166             // xform is certainly not worth it.
2167             const APInt &IntVal =CFP->getValueAPF().bitcastToAPInt();
2168             SDValue Lo = DAG.getConstant(APInt(IntVal).trunc(32), MVT::i32);
2169             SDValue Hi = DAG.getConstant(IntVal.lshr(32).trunc(32), MVT::i32);
2170             if (TLI.isBigEndian()) std::swap(Lo, Hi);
2171
2172             Lo = DAG.getStore(Tmp1, dl, Lo, Tmp2, ST->getSrcValue(),
2173                               SVOffset, isVolatile, Alignment);
2174             Tmp2 = DAG.getNode(ISD::ADD, dl, Tmp2.getValueType(), Tmp2,
2175                                DAG.getIntPtrConstant(4));
2176             Hi = DAG.getStore(Tmp1, dl, Hi, Tmp2, ST->getSrcValue(), SVOffset+4,
2177                               isVolatile, MinAlign(Alignment, 4U));
2178
2179             Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
2180             break;
2181           }
2182         }
2183       }
2184
2185       {
2186         Tmp3 = LegalizeOp(ST->getValue());
2187         Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
2188                                         ST->getOffset());
2189
2190         MVT VT = Tmp3.getValueType();
2191         switch (TLI.getOperationAction(ISD::STORE, VT)) {
2192         default: assert(0 && "This action is not supported yet!");
2193         case TargetLowering::Legal:
2194           // If this is an unaligned store and the target doesn't support it,
2195           // expand it.
2196           if (!TLI.allowsUnalignedMemoryAccesses()) {
2197             unsigned ABIAlignment = TLI.getTargetData()->
2198               getABITypeAlignment(ST->getMemoryVT().getTypeForMVT());
2199             if (ST->getAlignment() < ABIAlignment)
2200               Result = ExpandUnalignedStore(cast<StoreSDNode>(Result.getNode()), DAG,
2201                                             TLI);
2202           }
2203           break;
2204         case TargetLowering::Custom:
2205           Tmp1 = TLI.LowerOperation(Result, DAG);
2206           if (Tmp1.getNode()) Result = Tmp1;
2207           break;
2208         case TargetLowering::Promote:
2209           assert(VT.isVector() && "Unknown legal promote case!");
2210           Tmp3 = DAG.getNode(ISD::BIT_CONVERT, dl,
2211                              TLI.getTypeToPromoteTo(ISD::STORE, VT), Tmp3);
2212           Result = DAG.getStore(Tmp1, dl, Tmp3, Tmp2,
2213                                 ST->getSrcValue(), SVOffset, isVolatile,
2214                                 Alignment);
2215           break;
2216         }
2217         break;
2218       }
2219     } else {
2220       Tmp3 = LegalizeOp(ST->getValue());
2221
2222       MVT StVT = ST->getMemoryVT();
2223       unsigned StWidth = StVT.getSizeInBits();
2224
2225       if (StWidth != StVT.getStoreSizeInBits()) {
2226         // Promote to a byte-sized store with upper bits zero if not
2227         // storing an integral number of bytes.  For example, promote
2228         // TRUNCSTORE:i1 X -> TRUNCSTORE:i8 (and X, 1)
2229         MVT NVT = MVT::getIntegerVT(StVT.getStoreSizeInBits());
2230         Tmp3 = DAG.getZeroExtendInReg(Tmp3, dl, StVT);
2231         Result = DAG.getTruncStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(),
2232                                    SVOffset, NVT, isVolatile, Alignment);
2233       } else if (StWidth & (StWidth - 1)) {
2234         // If not storing a power-of-2 number of bits, expand as two stores.
2235         assert(StVT.isExtended() && !StVT.isVector() &&
2236                "Unsupported truncstore!");
2237         unsigned RoundWidth = 1 << Log2_32(StWidth);
2238         assert(RoundWidth < StWidth);
2239         unsigned ExtraWidth = StWidth - RoundWidth;
2240         assert(ExtraWidth < RoundWidth);
2241         assert(!(RoundWidth % 8) && !(ExtraWidth % 8) &&
2242                "Store size not an integral number of bytes!");
2243         MVT RoundVT = MVT::getIntegerVT(RoundWidth);
2244         MVT ExtraVT = MVT::getIntegerVT(ExtraWidth);
2245         SDValue Lo, Hi;
2246         unsigned IncrementSize;
2247
2248         if (TLI.isLittleEndian()) {
2249           // TRUNCSTORE:i24 X -> TRUNCSTORE:i16 X, TRUNCSTORE@+2:i8 (srl X, 16)
2250           // Store the bottom RoundWidth bits.
2251           Lo = DAG.getTruncStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(),
2252                                  SVOffset, RoundVT,
2253                                  isVolatile, Alignment);
2254
2255           // Store the remaining ExtraWidth bits.
2256           IncrementSize = RoundWidth / 8;
2257           Tmp2 = DAG.getNode(ISD::ADD, dl, Tmp2.getValueType(), Tmp2,
2258                              DAG.getIntPtrConstant(IncrementSize));
2259           Hi = DAG.getNode(ISD::SRL, dl, Tmp3.getValueType(), Tmp3,
2260                            DAG.getConstant(RoundWidth, TLI.getShiftAmountTy()));
2261           Hi = DAG.getTruncStore(Tmp1, dl, Hi, Tmp2, ST->getSrcValue(),
2262                                  SVOffset + IncrementSize, ExtraVT, isVolatile,
2263                                  MinAlign(Alignment, IncrementSize));
2264         } else {
2265           // Big endian - avoid unaligned stores.
2266           // TRUNCSTORE:i24 X -> TRUNCSTORE:i16 (srl X, 8), TRUNCSTORE@+2:i8 X
2267           // Store the top RoundWidth bits.
2268           Hi = DAG.getNode(ISD::SRL, dl, Tmp3.getValueType(), Tmp3,
2269                            DAG.getConstant(ExtraWidth, TLI.getShiftAmountTy()));
2270           Hi = DAG.getTruncStore(Tmp1, dl, Hi, Tmp2, ST->getSrcValue(),
2271                                  SVOffset, RoundVT, isVolatile, Alignment);
2272
2273           // Store the remaining ExtraWidth bits.
2274           IncrementSize = RoundWidth / 8;
2275           Tmp2 = DAG.getNode(ISD::ADD, dl, Tmp2.getValueType(), Tmp2,
2276                              DAG.getIntPtrConstant(IncrementSize));
2277           Lo = DAG.getTruncStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(),
2278                                  SVOffset + IncrementSize, ExtraVT, isVolatile,
2279                                  MinAlign(Alignment, IncrementSize));
2280         }
2281
2282         // The order of the stores doesn't matter.
2283         Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
2284       } else {
2285         if (Tmp1 != ST->getChain() || Tmp3 != ST->getValue() ||
2286             Tmp2 != ST->getBasePtr())
2287           Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
2288                                           ST->getOffset());
2289
2290         switch (TLI.getTruncStoreAction(ST->getValue().getValueType(), StVT)) {
2291         default: assert(0 && "This action is not supported yet!");
2292         case TargetLowering::Legal:
2293           // If this is an unaligned store and the target doesn't support it,
2294           // expand it.
2295           if (!TLI.allowsUnalignedMemoryAccesses()) {
2296             unsigned ABIAlignment = TLI.getTargetData()->
2297               getABITypeAlignment(ST->getMemoryVT().getTypeForMVT());
2298             if (ST->getAlignment() < ABIAlignment)
2299               Result = ExpandUnalignedStore(cast<StoreSDNode>(Result.getNode()), DAG,
2300                                             TLI);
2301           }
2302           break;
2303         case TargetLowering::Custom:
2304           Result = TLI.LowerOperation(Result, DAG);
2305           break;
2306         case Expand:
2307           // TRUNCSTORE:i16 i32 -> STORE i16
2308           assert(isTypeLegal(StVT) && "Do not know how to expand this store!");
2309           Tmp3 = DAG.getNode(ISD::TRUNCATE, dl, StVT, Tmp3);
2310           Result = DAG.getStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(),
2311                                 SVOffset, isVolatile, Alignment);
2312           break;
2313         }
2314       }
2315     }
2316     break;
2317   }
2318   case ISD::PCMARKER:
2319     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2320     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
2321     break;
2322   case ISD::STACKSAVE:
2323     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2324     Result = DAG.UpdateNodeOperands(Result, Tmp1);
2325     Tmp1 = Result.getValue(0);
2326     Tmp2 = Result.getValue(1);
2327
2328     switch (TLI.getOperationAction(ISD::STACKSAVE, MVT::Other)) {
2329     default: assert(0 && "This action is not supported yet!");
2330     case TargetLowering::Legal: break;
2331     case TargetLowering::Custom:
2332       Tmp3 = TLI.LowerOperation(Result, DAG);
2333       if (Tmp3.getNode()) {
2334         Tmp1 = LegalizeOp(Tmp3);
2335         Tmp2 = LegalizeOp(Tmp3.getValue(1));
2336       }
2337       break;
2338     case TargetLowering::Expand:
2339       // Expand to CopyFromReg if the target set
2340       // StackPointerRegisterToSaveRestore.
2341       if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
2342         Tmp1 = DAG.getCopyFromReg(Result.getOperand(0), dl, SP,
2343                                   Node->getValueType(0));
2344         Tmp2 = Tmp1.getValue(1);
2345       } else {
2346         Tmp1 = DAG.getUNDEF(Node->getValueType(0));
2347         Tmp2 = Node->getOperand(0);
2348       }
2349       break;
2350     }
2351
2352     // Since stacksave produce two values, make sure to remember that we
2353     // legalized both of them.
2354     AddLegalizedOperand(SDValue(Node, 0), Tmp1);
2355     AddLegalizedOperand(SDValue(Node, 1), Tmp2);
2356     return Op.getResNo() ? Tmp2 : Tmp1;
2357
2358   case ISD::STACKRESTORE:
2359     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2360     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2361     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2362
2363     switch (TLI.getOperationAction(ISD::STACKRESTORE, MVT::Other)) {
2364     default: assert(0 && "This action is not supported yet!");
2365     case TargetLowering::Legal: break;
2366     case TargetLowering::Custom:
2367       Tmp1 = TLI.LowerOperation(Result, DAG);
2368       if (Tmp1.getNode()) Result = Tmp1;
2369       break;
2370     case TargetLowering::Expand:
2371       // Expand to CopyToReg if the target set
2372       // StackPointerRegisterToSaveRestore.
2373       if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
2374         Result = DAG.getCopyToReg(Tmp1, dl, SP, Tmp2);
2375       } else {
2376         Result = Tmp1;
2377       }
2378       break;
2379     }
2380     break;
2381
2382   case ISD::READCYCLECOUNTER:
2383     Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain
2384     Result = DAG.UpdateNodeOperands(Result, Tmp1);
2385     switch (TLI.getOperationAction(ISD::READCYCLECOUNTER,
2386                                    Node->getValueType(0))) {
2387     default: assert(0 && "This action is not supported yet!");
2388     case TargetLowering::Legal:
2389       Tmp1 = Result.getValue(0);
2390       Tmp2 = Result.getValue(1);
2391       break;
2392     case TargetLowering::Custom:
2393       Result = TLI.LowerOperation(Result, DAG);
2394       Tmp1 = LegalizeOp(Result.getValue(0));
2395       Tmp2 = LegalizeOp(Result.getValue(1));
2396       break;
2397     }
2398
2399     // Since rdcc produce two values, make sure to remember that we legalized
2400     // both of them.
2401     AddLegalizedOperand(SDValue(Node, 0), Tmp1);
2402     AddLegalizedOperand(SDValue(Node, 1), Tmp2);
2403     return Result;
2404
2405   case ISD::SELECT:
2406     Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
2407     Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
2408     Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
2409
2410     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
2411
2412     switch (TLI.getOperationAction(ISD::SELECT, Tmp2.getValueType())) {
2413     default: assert(0 && "This action is not supported yet!");
2414     case TargetLowering::Legal: break;
2415     case TargetLowering::Custom: {
2416       Tmp1 = TLI.LowerOperation(Result, DAG);
2417       if (Tmp1.getNode()) Result = Tmp1;
2418       break;
2419     }
2420     case TargetLowering::Expand:
2421       if (Tmp1.getOpcode() == ISD::SETCC) {
2422         Result = DAG.getSelectCC(dl, Tmp1.getOperand(0), Tmp1.getOperand(1),
2423                               Tmp2, Tmp3,
2424                               cast<CondCodeSDNode>(Tmp1.getOperand(2))->get());
2425       } else {
2426         Result = DAG.getSelectCC(dl, Tmp1,
2427                                  DAG.getConstant(0, Tmp1.getValueType()),
2428                                  Tmp2, Tmp3, ISD::SETNE);
2429       }
2430       break;
2431     case TargetLowering::Promote: {
2432       MVT NVT =
2433         TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType());
2434       unsigned ExtOp, TruncOp;
2435       if (Tmp2.getValueType().isVector()) {
2436         ExtOp   = ISD::BIT_CONVERT;
2437         TruncOp = ISD::BIT_CONVERT;
2438       } else if (Tmp2.getValueType().isInteger()) {
2439         ExtOp   = ISD::ANY_EXTEND;
2440         TruncOp = ISD::TRUNCATE;
2441       } else {
2442         ExtOp   = ISD::FP_EXTEND;
2443         TruncOp = ISD::FP_ROUND;
2444       }
2445       // Promote each of the values to the new type.
2446       Tmp2 = DAG.getNode(ExtOp, dl, NVT, Tmp2);
2447       Tmp3 = DAG.getNode(ExtOp, dl, NVT, Tmp3);
2448       // Perform the larger operation, then round down.
2449       Result = DAG.getNode(ISD::SELECT, dl, NVT, Tmp1, Tmp2, Tmp3);
2450       if (TruncOp != ISD::FP_ROUND)
2451         Result = DAG.getNode(TruncOp, dl, Node->getValueType(0), Result);
2452       else
2453         Result = DAG.getNode(TruncOp, dl, Node->getValueType(0), Result,
2454                              DAG.getIntPtrConstant(0));
2455       break;
2456     }
2457     }
2458     break;
2459   case ISD::SELECT_CC: {
2460     Tmp1 = Node->getOperand(0);               // LHS
2461     Tmp2 = Node->getOperand(1);               // RHS
2462     Tmp3 = LegalizeOp(Node->getOperand(2));   // True
2463     Tmp4 = LegalizeOp(Node->getOperand(3));   // False
2464     SDValue CC = Node->getOperand(4);
2465
2466     LegalizeSetCC(TLI.getSetCCResultType(Tmp1.getValueType()),
2467                   Tmp1, Tmp2, CC, dl);
2468
2469     // If we didn't get both a LHS and RHS back from LegalizeSetCC,
2470     // the LHS is a legal SETCC itself.  In this case, we need to compare
2471     // the result against zero to select between true and false values.
2472     if (Tmp2.getNode() == 0) {
2473       Tmp2 = DAG.getConstant(0, Tmp1.getValueType());
2474       CC = DAG.getCondCode(ISD::SETNE);
2475     }
2476     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4, CC);
2477
2478     // Everything is legal, see if we should expand this op or something.
2479     switch (TLI.getOperationAction(ISD::SELECT_CC, Tmp3.getValueType())) {
2480     default: assert(0 && "This action is not supported yet!");
2481     case TargetLowering::Legal: break;
2482     case TargetLowering::Custom:
2483       Tmp1 = TLI.LowerOperation(Result, DAG);
2484       if (Tmp1.getNode()) Result = Tmp1;
2485       break;
2486     }
2487     break;
2488   }
2489   case ISD::SETCC:
2490     Tmp1 = Node->getOperand(0);
2491     Tmp2 = Node->getOperand(1);
2492     Tmp3 = Node->getOperand(2);
2493     LegalizeSetCC(Node->getValueType(0), Tmp1, Tmp2, Tmp3, dl);
2494
2495     // If we had to Expand the SetCC operands into a SELECT node, then it may
2496     // not always be possible to return a true LHS & RHS.  In this case, just
2497     // return the value we legalized, returned in the LHS
2498     if (Tmp2.getNode() == 0) {
2499       Result = Tmp1;
2500       break;
2501     }
2502
2503     switch (TLI.getOperationAction(ISD::SETCC, Tmp1.getValueType())) {
2504     default: assert(0 && "Cannot handle this action for SETCC yet!");
2505     case TargetLowering::Custom:
2506       isCustom = true;
2507       // FALLTHROUGH.
2508     case TargetLowering::Legal:
2509       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
2510       if (isCustom) {
2511         Tmp4 = TLI.LowerOperation(Result, DAG);
2512         if (Tmp4.getNode()) Result = Tmp4;
2513       }
2514       break;
2515     case TargetLowering::Promote: {
2516       // First step, figure out the appropriate operation to use.
2517       // Allow SETCC to not be supported for all legal data types
2518       // Mostly this targets FP
2519       MVT NewInTy = Node->getOperand(0).getValueType();
2520       MVT OldVT = NewInTy; OldVT = OldVT;
2521
2522       // Scan for the appropriate larger type to use.
2523       while (1) {
2524         NewInTy = (MVT::SimpleValueType)(NewInTy.getSimpleVT()+1);
2525
2526         assert(NewInTy.isInteger() == OldVT.isInteger() &&
2527                "Fell off of the edge of the integer world");
2528         assert(NewInTy.isFloatingPoint() == OldVT.isFloatingPoint() &&
2529                "Fell off of the edge of the floating point world");
2530
2531         // If the target supports SETCC of this type, use it.
2532         if (TLI.isOperationLegalOrCustom(ISD::SETCC, NewInTy))
2533           break;
2534       }
2535       if (NewInTy.isInteger())
2536         assert(0 && "Cannot promote Legal Integer SETCC yet");
2537       else {
2538         Tmp1 = DAG.getNode(ISD::FP_EXTEND, dl, NewInTy, Tmp1);
2539         Tmp2 = DAG.getNode(ISD::FP_EXTEND, dl, NewInTy, Tmp2);
2540       }
2541       Tmp1 = LegalizeOp(Tmp1);
2542       Tmp2 = LegalizeOp(Tmp2);
2543       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
2544       Result = LegalizeOp(Result);
2545       break;
2546     }
2547     case TargetLowering::Expand:
2548       // Expand a setcc node into a select_cc of the same condition, lhs, and
2549       // rhs that selects between const 1 (true) and const 0 (false).
2550       MVT VT = Node->getValueType(0);
2551       Result = DAG.getNode(ISD::SELECT_CC, dl, VT, Tmp1, Tmp2,
2552                            DAG.getConstant(1, VT), DAG.getConstant(0, VT),
2553                            Tmp3);
2554       break;
2555     }
2556     break;
2557   case ISD::VSETCC: {
2558     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2559     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2560     SDValue CC = Node->getOperand(2);
2561
2562     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, CC);
2563
2564     // Everything is legal, see if we should expand this op or something.
2565     switch (TLI.getOperationAction(ISD::VSETCC, Tmp1.getValueType())) {
2566     default: assert(0 && "This action is not supported yet!");
2567     case TargetLowering::Legal: break;
2568     case TargetLowering::Custom:
2569       Tmp1 = TLI.LowerOperation(Result, DAG);
2570       if (Tmp1.getNode()) Result = Tmp1;
2571       break;
2572     case TargetLowering::Expand: {
2573       // Unroll into a nasty set of scalar code for now.
2574       MVT VT = Node->getValueType(0);
2575       unsigned NumElems = VT.getVectorNumElements();
2576       MVT EltVT = VT.getVectorElementType();
2577       MVT TmpEltVT = Tmp1.getValueType().getVectorElementType();
2578       SmallVector<SDValue, 8> Ops(NumElems);
2579       for (unsigned i = 0; i < NumElems; ++i) {
2580         SDValue In1 = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT,
2581                                   Tmp1, DAG.getIntPtrConstant(i));
2582         Ops[i] = DAG.getNode(ISD::SETCC, dl, TLI.getSetCCResultType(TmpEltVT),
2583                              In1, DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
2584                                               TmpEltVT, Tmp2,
2585                                               DAG.getIntPtrConstant(i)),
2586                              CC);
2587         Ops[i] = DAG.getNode(ISD::SELECT, dl, EltVT, Ops[i],
2588                              DAG.getConstant(APInt::getAllOnesValue
2589                                              (EltVT.getSizeInBits()), EltVT),
2590                              DAG.getConstant(0, EltVT));
2591       }
2592       Result = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], NumElems);
2593       break;
2594     }
2595     }
2596     break;
2597   }
2598
2599   case ISD::SHL_PARTS:
2600   case ISD::SRA_PARTS:
2601   case ISD::SRL_PARTS: {
2602     SmallVector<SDValue, 8> Ops;
2603     bool Changed = false;
2604     unsigned N = Node->getNumOperands();
2605     for (unsigned i = 0; i + 1 < N; ++i) {
2606       Ops.push_back(LegalizeOp(Node->getOperand(i)));
2607       Changed |= Ops.back() != Node->getOperand(i);
2608     }
2609     Ops.push_back(LegalizeOp(DAG.getShiftAmountOperand(Node->getOperand(N-1))));
2610     Changed |= Ops.back() != Node->getOperand(N-1);
2611     if (Changed)
2612       Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
2613
2614     switch (TLI.getOperationAction(Node->getOpcode(),
2615                                    Node->getValueType(0))) {
2616     default: assert(0 && "This action is not supported yet!");
2617     case TargetLowering::Legal: break;
2618     case TargetLowering::Custom:
2619       Tmp1 = TLI.LowerOperation(Result, DAG);
2620       if (Tmp1.getNode()) {
2621         SDValue Tmp2, RetVal(0, 0);
2622         for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) {
2623           Tmp2 = LegalizeOp(Tmp1.getValue(i));
2624           AddLegalizedOperand(SDValue(Node, i), Tmp2);
2625           if (i == Op.getResNo())
2626             RetVal = Tmp2;
2627         }
2628         assert(RetVal.getNode() && "Illegal result number");
2629         return RetVal;
2630       }
2631       break;
2632     }
2633
2634     // Since these produce multiple values, make sure to remember that we
2635     // legalized all of them.
2636     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
2637       AddLegalizedOperand(SDValue(Node, i), Result.getValue(i));
2638     return Result.getValue(Op.getResNo());
2639   }
2640
2641     // Binary operators
2642   case ISD::ADD:
2643   case ISD::SUB:
2644   case ISD::MUL:
2645   case ISD::MULHS:
2646   case ISD::MULHU:
2647   case ISD::UDIV:
2648   case ISD::SDIV:
2649   case ISD::AND:
2650   case ISD::OR:
2651   case ISD::XOR:
2652   case ISD::SHL:
2653   case ISD::SRL:
2654   case ISD::SRA:
2655   case ISD::FADD:
2656   case ISD::FSUB:
2657   case ISD::FMUL:
2658   case ISD::FDIV:
2659   case ISD::FPOW:
2660     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2661     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2662
2663     if ((Node->getOpcode() == ISD::SHL ||
2664          Node->getOpcode() == ISD::SRL ||
2665          Node->getOpcode() == ISD::SRA) &&
2666         !Node->getValueType(0).isVector())
2667       Tmp2 = DAG.getShiftAmountOperand(Tmp2);
2668
2669     Tmp2 = LegalizeOp(Tmp2); // Legalize the RHS.
2670
2671     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2672
2673     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2674     default: assert(0 && "BinOp legalize operation not supported");
2675     case TargetLowering::Legal: break;
2676     case TargetLowering::Custom:
2677       Tmp1 = TLI.LowerOperation(Result, DAG);
2678       if (Tmp1.getNode()) {
2679         Result = Tmp1;
2680         break;
2681       }
2682       // Fall through if the custom lower can't deal with the operation
2683     case TargetLowering::Expand: {
2684       MVT VT = Op.getValueType();
2685
2686       // See if multiply or divide can be lowered using two-result operations.
2687       SDVTList VTs = DAG.getVTList(VT, VT);
2688       if (Node->getOpcode() == ISD::MUL) {
2689         // We just need the low half of the multiply; try both the signed
2690         // and unsigned forms. If the target supports both SMUL_LOHI and
2691         // UMUL_LOHI, form a preference by checking which forms of plain
2692         // MULH it supports.
2693         bool HasSMUL_LOHI = TLI.isOperationLegalOrCustom(ISD::SMUL_LOHI, VT);
2694         bool HasUMUL_LOHI = TLI.isOperationLegalOrCustom(ISD::UMUL_LOHI, VT);
2695         bool HasMULHS = TLI.isOperationLegalOrCustom(ISD::MULHS, VT);
2696         bool HasMULHU = TLI.isOperationLegalOrCustom(ISD::MULHU, VT);
2697         unsigned OpToUse = 0;
2698         if (HasSMUL_LOHI && !HasMULHS) {
2699           OpToUse = ISD::SMUL_LOHI;
2700         } else if (HasUMUL_LOHI && !HasMULHU) {
2701           OpToUse = ISD::UMUL_LOHI;
2702         } else if (HasSMUL_LOHI) {
2703           OpToUse = ISD::SMUL_LOHI;
2704         } else if (HasUMUL_LOHI) {
2705           OpToUse = ISD::UMUL_LOHI;
2706         }
2707         if (OpToUse) {
2708           Result = DAG.getNode(OpToUse, dl, VTs, Tmp1, Tmp2);
2709           break;
2710         }
2711       }
2712       if (Node->getOpcode() == ISD::MULHS &&
2713           TLI.isOperationLegalOrCustom(ISD::SMUL_LOHI, VT)) {
2714         Result = SDValue(DAG.getNode(ISD::SMUL_LOHI, dl,
2715                                      VTs, Tmp1, Tmp2).getNode(),
2716                          1);
2717         break;
2718       }
2719       if (Node->getOpcode() == ISD::MULHU &&
2720           TLI.isOperationLegalOrCustom(ISD::UMUL_LOHI, VT)) {
2721         Result = SDValue(DAG.getNode(ISD::UMUL_LOHI, dl,
2722                                      VTs, Tmp1, Tmp2).getNode(),
2723                          1);
2724         break;
2725       }
2726       if (Node->getOpcode() == ISD::SDIV &&
2727           TLI.isOperationLegalOrCustom(ISD::SDIVREM, VT)) {
2728         Result = DAG.getNode(ISD::SDIVREM, dl, VTs, Tmp1, Tmp2);
2729         break;
2730       }
2731       if (Node->getOpcode() == ISD::UDIV &&
2732           TLI.isOperationLegalOrCustom(ISD::UDIVREM, VT)) {
2733         Result = DAG.getNode(ISD::UDIVREM, dl, VTs, Tmp1, Tmp2);
2734         break;
2735       }
2736       if (Node->getOpcode() == ISD::SUB &&
2737           TLI.isOperationLegalOrCustom(ISD::ADD, VT) &&
2738           TLI.isOperationLegalOrCustom(ISD::XOR, VT)) {
2739         Tmp2 = DAG.getNode(ISD::XOR, dl, VT, Tmp2,
2740                DAG.getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT));
2741         Tmp2 = DAG.getNode(ISD::ADD, dl, VT, Tmp2, DAG.getConstant(1, VT));
2742         Result = DAG.getNode(ISD::ADD, dl, VT, Tmp1, Tmp2);
2743         break;
2744       }
2745
2746       // Check to see if we have a libcall for this operator.
2747       RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2748       bool isSigned = false;
2749       switch (Node->getOpcode()) {
2750       case ISD::UDIV:
2751       case ISD::SDIV:
2752        isSigned = Node->getOpcode() == ISD::SDIV;
2753        if (VT == MVT::i16)
2754          LC = (isSigned ? RTLIB::SDIV_I16  : RTLIB::UDIV_I16);
2755        else if (VT == MVT::i32)
2756          LC = (isSigned ? RTLIB::SDIV_I32  : RTLIB::UDIV_I32);
2757        else if (VT == MVT::i64)
2758          LC = (isSigned ? RTLIB::SDIV_I64  : RTLIB::UDIV_I64);
2759        else if (VT == MVT::i128)
2760          LC = (isSigned ? RTLIB::SDIV_I128 : RTLIB::UDIV_I128);
2761        break;
2762       case ISD::MUL:
2763         if (VT == MVT::i16)
2764           LC = RTLIB::MUL_I16;
2765         else if (VT == MVT::i32)
2766           LC = RTLIB::MUL_I32;
2767         else if (VT == MVT::i64)
2768           LC = RTLIB::MUL_I64;
2769         else if (VT == MVT::i128)
2770           LC = RTLIB::MUL_I128;
2771         break;
2772       case ISD::FPOW:
2773         LC = GetFPLibCall(VT, RTLIB::POW_F32, RTLIB::POW_F64, RTLIB::POW_F80,
2774                           RTLIB::POW_PPCF128);
2775         break;
2776       case ISD::FDIV:
2777         LC = GetFPLibCall(VT, RTLIB::DIV_F32, RTLIB::DIV_F64, RTLIB::DIV_F80,
2778                           RTLIB::DIV_PPCF128);
2779         break;
2780       default: break;
2781       }
2782       if (LC != RTLIB::UNKNOWN_LIBCALL) {
2783         SDValue Dummy;
2784         Result = ExpandLibCall(LC, Node, isSigned, Dummy);
2785         break;
2786       }
2787
2788       assert(0 && "Cannot expand this binary operator!");
2789       break;
2790     }
2791     case TargetLowering::Promote: {
2792       switch (Node->getOpcode()) {
2793       default:  assert(0 && "Do not know how to promote this BinOp!");
2794       case ISD::AND:
2795       case ISD::OR:
2796       case ISD::XOR: {
2797         MVT OVT = Node->getValueType(0);
2798         MVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2799         assert(OVT.isVector() && "Cannot promote this BinOp!");
2800         // Bit convert each of the values to the new type.
2801         Tmp1 = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Tmp1);
2802         Tmp2 = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Tmp2);
2803         Result = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1, Tmp2);
2804         // Bit convert the result back the original type.
2805         Result = DAG.getNode(ISD::BIT_CONVERT, dl, OVT, Result);
2806         break;
2807       }
2808       }
2809     }
2810     }
2811     break;
2812
2813   case ISD::SMUL_LOHI:
2814   case ISD::UMUL_LOHI:
2815   case ISD::SDIVREM:
2816   case ISD::UDIVREM:
2817     // These nodes will only be produced by target-specific lowering, so
2818     // they shouldn't be here if they aren't legal.
2819     assert(TLI.isOperationLegal(Node->getOpcode(), Node->getValueType(0)) &&
2820            "This must be legal!");
2821
2822     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2823     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2824     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2825     break;
2826
2827   case ISD::FCOPYSIGN:  // FCOPYSIGN does not require LHS/RHS to match type!
2828     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2829     Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS.
2830
2831     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2832
2833     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2834     default: assert(0 && "Operation not supported");
2835     case TargetLowering::Custom:
2836       Tmp1 = TLI.LowerOperation(Result, DAG);
2837       if (Tmp1.getNode()) Result = Tmp1;
2838       break;
2839     case TargetLowering::Legal: break;
2840     case TargetLowering::Expand: {
2841       assert((Tmp2.getValueType() == MVT::f32 ||
2842               Tmp2.getValueType() == MVT::f64) &&
2843               "Ugly special-cased code!");
2844       // Get the sign bit of the RHS.
2845       SDValue SignBit;
2846       MVT IVT = Tmp2.getValueType() == MVT::f64 ? MVT::i64 : MVT::i32;
2847       if (isTypeLegal(IVT)) {
2848         SignBit = DAG.getNode(ISD::BIT_CONVERT, dl, IVT, Tmp2);
2849       } else {
2850         assert(isTypeLegal(TLI.getPointerTy()) &&
2851                (TLI.getPointerTy() == MVT::i32 ||
2852                 TLI.getPointerTy() == MVT::i64) &&
2853                "Legal type for load?!");
2854         SDValue StackPtr = DAG.CreateStackTemporary(Tmp2.getValueType());
2855         SDValue StorePtr = StackPtr, LoadPtr = StackPtr;
2856         SDValue Ch =
2857             DAG.getStore(DAG.getEntryNode(), dl, Tmp2, StorePtr, NULL, 0);
2858         if (Tmp2.getValueType() == MVT::f64 && TLI.isLittleEndian())
2859           LoadPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(),
2860                                 LoadPtr, DAG.getIntPtrConstant(4));
2861         SignBit = DAG.getExtLoad(ISD::SEXTLOAD, dl, TLI.getPointerTy(),
2862                                  Ch, LoadPtr, NULL, 0, MVT::i32);
2863       }
2864       SignBit =
2865           DAG.getSetCC(dl, TLI.getSetCCResultType(SignBit.getValueType()),
2866                        SignBit, DAG.getConstant(0, SignBit.getValueType()),
2867                        ISD::SETLT);
2868       // Get the absolute value of the result.
2869       SDValue AbsVal = DAG.getNode(ISD::FABS, dl, Tmp1.getValueType(), Tmp1);
2870       // Select between the nabs and abs value based on the sign bit of
2871       // the input.
2872       Result = DAG.getNode(ISD::SELECT, dl, AbsVal.getValueType(), SignBit,
2873                            DAG.getNode(ISD::FNEG, dl, AbsVal.getValueType(),
2874                                        AbsVal),
2875                            AbsVal);
2876       Result = LegalizeOp(Result);
2877       break;
2878     }
2879     }
2880     break;
2881
2882   case ISD::ADDC:
2883   case ISD::SUBC:
2884     Tmp1 = LegalizeOp(Node->getOperand(0));
2885     Tmp2 = LegalizeOp(Node->getOperand(1));
2886     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2887     Tmp3 = Result.getValue(0);
2888     Tmp4 = Result.getValue(1);
2889
2890     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2891     default: assert(0 && "This action is not supported yet!");
2892     case TargetLowering::Legal:
2893       break;
2894     case TargetLowering::Custom:
2895       Tmp1 = TLI.LowerOperation(Tmp3, DAG);
2896       if (Tmp1.getNode() != NULL) {
2897         Tmp3 = LegalizeOp(Tmp1);
2898         Tmp4 = LegalizeOp(Tmp1.getValue(1));
2899       }
2900       break;
2901     }
2902     // Since this produces two values, make sure to remember that we legalized
2903     // both of them.
2904     AddLegalizedOperand(SDValue(Node, 0), Tmp3);
2905     AddLegalizedOperand(SDValue(Node, 1), Tmp4);
2906     return Op.getResNo() ? Tmp4 : Tmp3;
2907
2908   case ISD::ADDE:
2909   case ISD::SUBE:
2910     Tmp1 = LegalizeOp(Node->getOperand(0));
2911     Tmp2 = LegalizeOp(Node->getOperand(1));
2912     Tmp3 = LegalizeOp(Node->getOperand(2));
2913     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
2914     Tmp3 = Result.getValue(0);
2915     Tmp4 = Result.getValue(1);
2916
2917     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2918     default: assert(0 && "This action is not supported yet!");
2919     case TargetLowering::Legal:
2920       break;
2921     case TargetLowering::Custom:
2922       Tmp1 = TLI.LowerOperation(Tmp3, DAG);
2923       if (Tmp1.getNode() != NULL) {
2924         Tmp3 = LegalizeOp(Tmp1);
2925         Tmp4 = LegalizeOp(Tmp1.getValue(1));
2926       }
2927       break;
2928     }
2929     // Since this produces two values, make sure to remember that we legalized
2930     // both of them.
2931     AddLegalizedOperand(SDValue(Node, 0), Tmp3);
2932     AddLegalizedOperand(SDValue(Node, 1), Tmp4);
2933     return Op.getResNo() ? Tmp4 : Tmp3;
2934
2935   case ISD::BUILD_PAIR: {
2936     MVT PairTy = Node->getValueType(0);
2937     // TODO: handle the case where the Lo and Hi operands are not of legal type
2938     Tmp1 = LegalizeOp(Node->getOperand(0));   // Lo
2939     Tmp2 = LegalizeOp(Node->getOperand(1));   // Hi
2940     switch (TLI.getOperationAction(ISD::BUILD_PAIR, PairTy)) {
2941     case TargetLowering::Promote:
2942     case TargetLowering::Custom:
2943       assert(0 && "Cannot promote/custom this yet!");
2944     case TargetLowering::Legal:
2945       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
2946         Result = DAG.getNode(ISD::BUILD_PAIR, dl, PairTy, Tmp1, Tmp2);
2947       break;
2948     case TargetLowering::Expand:
2949       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, PairTy, Tmp1);
2950       Tmp2 = DAG.getNode(ISD::ANY_EXTEND, dl, PairTy, Tmp2);
2951       Tmp2 = DAG.getNode(ISD::SHL, dl, PairTy, Tmp2,
2952                          DAG.getConstant(PairTy.getSizeInBits()/2,
2953                                          TLI.getShiftAmountTy()));
2954       Result = DAG.getNode(ISD::OR, dl, PairTy, Tmp1, Tmp2);
2955       break;
2956     }
2957     break;
2958   }
2959
2960   case ISD::UREM:
2961   case ISD::SREM:
2962   case ISD::FREM:
2963     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2964     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2965
2966     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2967     case TargetLowering::Promote: assert(0 && "Cannot promote this yet!");
2968     case TargetLowering::Custom:
2969       isCustom = true;
2970       // FALLTHROUGH
2971     case TargetLowering::Legal:
2972       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2973       if (isCustom) {
2974         Tmp1 = TLI.LowerOperation(Result, DAG);
2975         if (Tmp1.getNode()) Result = Tmp1;
2976       }
2977       break;
2978     case TargetLowering::Expand: {
2979       unsigned DivOpc= (Node->getOpcode() == ISD::UREM) ? ISD::UDIV : ISD::SDIV;
2980       bool isSigned = DivOpc == ISD::SDIV;
2981       MVT VT = Node->getValueType(0);
2982
2983       // See if remainder can be lowered using two-result operations.
2984       SDVTList VTs = DAG.getVTList(VT, VT);
2985       if (Node->getOpcode() == ISD::SREM &&
2986           TLI.isOperationLegalOrCustom(ISD::SDIVREM, VT)) {
2987         Result = SDValue(DAG.getNode(ISD::SDIVREM, dl,
2988                                      VTs, Tmp1, Tmp2).getNode(), 1);
2989         break;
2990       }
2991       if (Node->getOpcode() == ISD::UREM &&
2992           TLI.isOperationLegalOrCustom(ISD::UDIVREM, VT)) {
2993         Result = SDValue(DAG.getNode(ISD::UDIVREM, dl,
2994                                      VTs, Tmp1, Tmp2).getNode(), 1);
2995         break;
2996       }
2997
2998       if (VT.isInteger() &&
2999           TLI.getOperationAction(DivOpc, VT) == TargetLowering::Legal) {
3000         // X % Y -> X-X/Y*Y
3001         Result = DAG.getNode(DivOpc, dl, VT, Tmp1, Tmp2);
3002         Result = DAG.getNode(ISD::MUL, dl, VT, Result, Tmp2);
3003         Result = DAG.getNode(ISD::SUB, dl, VT, Tmp1, Result);
3004         break;
3005       }
3006
3007       // Check to see if we have a libcall for this operator.
3008       RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
3009       switch (Node->getOpcode()) {
3010       default: break;
3011       case ISD::UREM:
3012       case ISD::SREM:
3013        if (VT == MVT::i16)
3014          LC = (isSigned ? RTLIB::SREM_I16  : RTLIB::UREM_I16);
3015        else if (VT == MVT::i32)
3016          LC = (isSigned ? RTLIB::SREM_I32  : RTLIB::UREM_I32);
3017        else if (VT == MVT::i64)
3018          LC = (isSigned ? RTLIB::SREM_I64  : RTLIB::UREM_I64);
3019        else if (VT == MVT::i128)
3020          LC = (isSigned ? RTLIB::SREM_I128 : RTLIB::UREM_I128);
3021        break;
3022        case ISD::FREM:
3023         // Floating point mod -> fmod libcall.
3024         LC = GetFPLibCall(VT, RTLIB::REM_F32, RTLIB::REM_F64,
3025                           RTLIB::REM_F80, RTLIB::REM_PPCF128);
3026         break;
3027       }
3028
3029       if (LC != RTLIB::UNKNOWN_LIBCALL) {
3030         SDValue Dummy;
3031         Result = ExpandLibCall(LC, Node, isSigned, Dummy);
3032         break;
3033       }
3034
3035       assert(0 && "Cannot expand this binary operator!");
3036       break;
3037     }
3038     }
3039     break;
3040   case ISD::VAARG: {
3041     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
3042     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
3043
3044     MVT VT = Node->getValueType(0);
3045     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
3046     default: assert(0 && "This action is not supported yet!");
3047     case TargetLowering::Custom:
3048       isCustom = true;
3049       // FALLTHROUGH
3050     case TargetLowering::Legal:
3051       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
3052       Result = Result.getValue(0);
3053       Tmp1 = Result.getValue(1);
3054
3055       if (isCustom) {
3056         Tmp2 = TLI.LowerOperation(Result, DAG);
3057         if (Tmp2.getNode()) {
3058           Result = LegalizeOp(Tmp2);
3059           Tmp1 = LegalizeOp(Tmp2.getValue(1));
3060         }
3061       }
3062       break;
3063     case TargetLowering::Expand: {
3064       const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
3065       SDValue VAList = DAG.getLoad(TLI.getPointerTy(), dl, Tmp1, Tmp2, V, 0);
3066       // Increment the pointer, VAList, to the next vaarg
3067       Tmp3 = DAG.getNode(ISD::ADD, dl, TLI.getPointerTy(), VAList,
3068                          DAG.getConstant(TLI.getTargetData()->
3069                                          getTypeAllocSize(VT.getTypeForMVT()),
3070                                          TLI.getPointerTy()));
3071       // Store the incremented VAList to the legalized pointer
3072       Tmp3 = DAG.getStore(VAList.getValue(1), dl, Tmp3, Tmp2, V, 0);
3073       // Load the actual argument out of the pointer VAList
3074       Result = DAG.getLoad(VT, dl, Tmp3, VAList, NULL, 0);
3075       Tmp1 = LegalizeOp(Result.getValue(1));
3076       Result = LegalizeOp(Result);
3077       break;
3078     }
3079     }
3080     // Since VAARG produces two values, make sure to remember that we
3081     // legalized both of them.
3082     AddLegalizedOperand(SDValue(Node, 0), Result);
3083     AddLegalizedOperand(SDValue(Node, 1), Tmp1);
3084     return Op.getResNo() ? Tmp1 : Result;
3085   }
3086
3087   case ISD::VACOPY:
3088     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
3089     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the dest pointer.
3090     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the source pointer.
3091
3092     switch (TLI.getOperationAction(ISD::VACOPY, MVT::Other)) {
3093     default: assert(0 && "This action is not supported yet!");
3094     case TargetLowering::Custom:
3095       isCustom = true;
3096       // FALLTHROUGH
3097     case TargetLowering::Legal:
3098       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3,
3099                                       Node->getOperand(3), Node->getOperand(4));
3100       if (isCustom) {
3101         Tmp1 = TLI.LowerOperation(Result, DAG);
3102         if (Tmp1.getNode()) Result = Tmp1;
3103       }
3104       break;
3105     case TargetLowering::Expand:
3106       // This defaults to loading a pointer from the input and storing it to the
3107       // output, returning the chain.
3108       const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
3109       const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
3110       Tmp4 = DAG.getLoad(TLI.getPointerTy(), dl, Tmp1, Tmp3, VS, 0);
3111       Result = DAG.getStore(Tmp4.getValue(1), dl, Tmp4, Tmp2, VD, 0);
3112       break;
3113     }
3114     break;
3115
3116   case ISD::VAEND:
3117     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
3118     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
3119
3120     switch (TLI.getOperationAction(ISD::VAEND, MVT::Other)) {
3121     default: assert(0 && "This action is not supported yet!");
3122     case TargetLowering::Custom:
3123       isCustom = true;
3124       // FALLTHROUGH
3125     case TargetLowering::Legal:
3126       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
3127       if (isCustom) {
3128         Tmp1 = TLI.LowerOperation(Tmp1, DAG);
3129         if (Tmp1.getNode()) Result = Tmp1;
3130       }
3131       break;
3132     case TargetLowering::Expand:
3133       Result = Tmp1; // Default to a no-op, return the chain
3134       break;
3135     }
3136     break;
3137
3138   case ISD::VASTART:
3139     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
3140     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
3141
3142     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
3143
3144     switch (TLI.getOperationAction(ISD::VASTART, MVT::Other)) {
3145     default: assert(0 && "This action is not supported yet!");
3146     case TargetLowering::Legal: break;
3147     case TargetLowering::Custom:
3148       Tmp1 = TLI.LowerOperation(Result, DAG);
3149       if (Tmp1.getNode()) Result = Tmp1;
3150       break;
3151     }
3152     break;
3153
3154   case ISD::ROTL:
3155   case ISD::ROTR:
3156     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
3157     Tmp2 = LegalizeOp(DAG.getShiftAmountOperand(Node->getOperand(1)));   // RHS
3158     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
3159     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
3160     default:
3161       assert(0 && "ROTL/ROTR legalize operation not supported");
3162       break;
3163     case TargetLowering::Legal:
3164       break;
3165     case TargetLowering::Custom:
3166       Tmp1 = TLI.LowerOperation(Result, DAG);
3167       if (Tmp1.getNode()) Result = Tmp1;
3168       break;
3169     case TargetLowering::Promote:
3170       assert(0 && "Do not know how to promote ROTL/ROTR");
3171       break;
3172     case TargetLowering::Expand:
3173       assert(0 && "Do not know how to expand ROTL/ROTR");
3174       break;
3175     }
3176     break;
3177
3178   case ISD::BSWAP:
3179     Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
3180     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
3181     case TargetLowering::Custom:
3182       assert(0 && "Cannot custom legalize this yet!");
3183     case TargetLowering::Legal:
3184       Result = DAG.UpdateNodeOperands(Result, Tmp1);
3185       break;
3186     case TargetLowering::Promote: {
3187       MVT OVT = Tmp1.getValueType();
3188       MVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
3189       unsigned DiffBits = NVT.getSizeInBits() - OVT.getSizeInBits();
3190
3191       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Tmp1);
3192       Tmp1 = DAG.getNode(ISD::BSWAP, dl, NVT, Tmp1);
3193       Result = DAG.getNode(ISD::SRL, dl, NVT, Tmp1,
3194                            DAG.getConstant(DiffBits, TLI.getShiftAmountTy()));
3195       break;
3196     }
3197     case TargetLowering::Expand:
3198       Result = ExpandBSWAP(Tmp1, dl);
3199       break;
3200     }
3201     break;
3202
3203   case ISD::CTPOP:
3204   case ISD::CTTZ:
3205   case ISD::CTLZ:
3206     Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
3207     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
3208     case TargetLowering::Custom:
3209     case TargetLowering::Legal:
3210       Result = DAG.UpdateNodeOperands(Result, Tmp1);
3211       if (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0)) ==
3212           TargetLowering::Custom) {
3213         Tmp1 = TLI.LowerOperation(Result, DAG);
3214         if (Tmp1.getNode()) {
3215           Result = Tmp1;
3216         }
3217       }
3218       break;
3219     case TargetLowering::Promote: {
3220       MVT OVT = Tmp1.getValueType();
3221       MVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
3222
3223       // Zero extend the argument.
3224       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Tmp1);
3225       // Perform the larger operation, then subtract if needed.
3226       Tmp1 = DAG.getNode(Node->getOpcode(), dl, Node->getValueType(0), Tmp1);
3227       switch (Node->getOpcode()) {
3228       case ISD::CTPOP:
3229         Result = Tmp1;
3230         break;
3231       case ISD::CTTZ:
3232         //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
3233         Tmp2 = DAG.getSetCC(dl, TLI.getSetCCResultType(Tmp1.getValueType()),
3234                             Tmp1, DAG.getConstant(NVT.getSizeInBits(), NVT),
3235                             ISD::SETEQ);
3236         Result = DAG.getNode(ISD::SELECT, dl, NVT, Tmp2,
3237                              DAG.getConstant(OVT.getSizeInBits(), NVT), Tmp1);
3238         break;
3239       case ISD::CTLZ:
3240         // Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
3241         Result = DAG.getNode(ISD::SUB, dl, NVT, Tmp1,
3242                              DAG.getConstant(NVT.getSizeInBits() -
3243                                              OVT.getSizeInBits(), NVT));
3244         break;
3245       }
3246       break;
3247     }
3248     case TargetLowering::Expand:
3249       Result = ExpandBitCount(Node->getOpcode(), Tmp1, dl);
3250       break;
3251     }
3252     break;
3253
3254     // Unary operators
3255   case ISD::FABS:
3256   case ISD::FNEG:
3257   case ISD::FSQRT:
3258   case ISD::FSIN:
3259   case ISD::FCOS:
3260   case ISD::FLOG:
3261   case ISD::FLOG2:
3262   case ISD::FLOG10:
3263   case ISD::FEXP:
3264   case ISD::FEXP2:
3265   case ISD::FTRUNC:
3266   case ISD::FFLOOR:
3267   case ISD::FCEIL:
3268   case ISD::FRINT:
3269   case ISD::FNEARBYINT:
3270     Tmp1 = LegalizeOp(Node->getOperand(0));
3271     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
3272     case TargetLowering::Promote:
3273     case TargetLowering::Custom:
3274      isCustom = true;
3275      // FALLTHROUGH
3276     case TargetLowering::Legal:
3277       Result = DAG.UpdateNodeOperands(Result, Tmp1);
3278       if (isCustom) {
3279         Tmp1 = TLI.LowerOperation(Result, DAG);
3280         if (Tmp1.getNode()) Result = Tmp1;
3281       }
3282       break;
3283     case TargetLowering::Expand:
3284       switch (Node->getOpcode()) {
3285       default: assert(0 && "Unreachable!");
3286       case ISD::FNEG:
3287         // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
3288         Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0));
3289         Result = DAG.getNode(ISD::FSUB, dl, Node->getValueType(0), Tmp2, Tmp1);
3290         break;
3291       case ISD::FABS: {
3292         // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
3293         MVT VT = Node->getValueType(0);
3294         Tmp2 = DAG.getConstantFP(0.0, VT);
3295         Tmp2 = DAG.getSetCC(dl, TLI.getSetCCResultType(Tmp1.getValueType()),
3296                             Tmp1, Tmp2, ISD::SETUGT);
3297         Tmp3 = DAG.getNode(ISD::FNEG, dl, VT, Tmp1);
3298         Result = DAG.getNode(ISD::SELECT, dl, VT, Tmp2, Tmp1, Tmp3);
3299         break;
3300       }
3301       case ISD::FSQRT:
3302       case ISD::FSIN:
3303       case ISD::FCOS:
3304       case ISD::FLOG:
3305       case ISD::FLOG2:
3306       case ISD::FLOG10:
3307       case ISD::FEXP:
3308       case ISD::FEXP2:
3309       case ISD::FTRUNC:
3310       case ISD::FFLOOR:
3311       case ISD::FCEIL:
3312       case ISD::FRINT:
3313       case ISD::FNEARBYINT: {
3314         MVT VT = Node->getValueType(0);
3315
3316         assert(!VT.isVector() && "Vector shouldn't get here!");
3317
3318         RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
3319         switch(Node->getOpcode()) {
3320         case ISD::FSQRT:
3321           LC = GetFPLibCall(VT, RTLIB::SQRT_F32, RTLIB::SQRT_F64,
3322                             RTLIB::SQRT_F80, RTLIB::SQRT_PPCF128);
3323           break;
3324         case ISD::FSIN:
3325           LC = GetFPLibCall(VT, RTLIB::SIN_F32, RTLIB::SIN_F64,
3326                             RTLIB::SIN_F80, RTLIB::SIN_PPCF128);
3327           break;
3328         case ISD::FCOS:
3329           LC = GetFPLibCall(VT, RTLIB::COS_F32, RTLIB::COS_F64,
3330                             RTLIB::COS_F80, RTLIB::COS_PPCF128);
3331           break;
3332         case ISD::FLOG:
3333           LC = GetFPLibCall(VT, RTLIB::LOG_F32, RTLIB::LOG_F64,
3334                             RTLIB::LOG_F80, RTLIB::LOG_PPCF128);
3335           break;
3336         case ISD::FLOG2:
3337           LC = GetFPLibCall(VT, RTLIB::LOG2_F32, RTLIB::LOG2_F64,
3338                             RTLIB::LOG2_F80, RTLIB::LOG2_PPCF128);
3339           break;
3340         case ISD::FLOG10:
3341           LC = GetFPLibCall(VT, RTLIB::LOG10_F32, RTLIB::LOG10_F64,
3342                             RTLIB::LOG10_F80, RTLIB::LOG10_PPCF128);
3343           break;
3344         case ISD::FEXP:
3345           LC = GetFPLibCall(VT, RTLIB::EXP_F32, RTLIB::EXP_F64,
3346                             RTLIB::EXP_F80, RTLIB::EXP_PPCF128);
3347           break;
3348         case ISD::FEXP2:
3349           LC = GetFPLibCall(VT, RTLIB::EXP2_F32, RTLIB::EXP2_F64,
3350                             RTLIB::EXP2_F80, RTLIB::EXP2_PPCF128);
3351           break;
3352         case ISD::FTRUNC:
3353           LC = GetFPLibCall(VT, RTLIB::TRUNC_F32, RTLIB::TRUNC_F64,
3354                             RTLIB::TRUNC_F80, RTLIB::TRUNC_PPCF128);
3355           break;
3356         case ISD::FFLOOR:
3357           LC = GetFPLibCall(VT, RTLIB::FLOOR_F32, RTLIB::FLOOR_F64,
3358                             RTLIB::FLOOR_F80, RTLIB::FLOOR_PPCF128);
3359           break;
3360         case ISD::FCEIL:
3361           LC = GetFPLibCall(VT, RTLIB::CEIL_F32, RTLIB::CEIL_F64,
3362                             RTLIB::CEIL_F80, RTLIB::CEIL_PPCF128);
3363           break;
3364         case ISD::FRINT:
3365           LC = GetFPLibCall(VT, RTLIB::RINT_F32, RTLIB::RINT_F64,
3366                             RTLIB::RINT_F80, RTLIB::RINT_PPCF128);
3367           break;
3368         case ISD::FNEARBYINT:
3369           LC = GetFPLibCall(VT, RTLIB::NEARBYINT_F32, RTLIB::NEARBYINT_F64,
3370                             RTLIB::NEARBYINT_F80, RTLIB::NEARBYINT_PPCF128);
3371           break;
3372       break;
3373         default: assert(0 && "Unreachable!");
3374         }
3375         SDValue Dummy;
3376         Result = ExpandLibCall(LC, Node, false/*sign irrelevant*/, Dummy);
3377         break;
3378       }
3379       }
3380       break;
3381     }
3382     break;
3383   case ISD::FPOWI: {
3384     MVT VT = Node->getValueType(0);
3385
3386     // Expand unsupported unary vector operators by unrolling them.
3387     assert(!VT.isVector() && "Vector shouldn't get here!");
3388
3389     // We always lower FPOWI into a libcall.  No target support for it yet.
3390     RTLIB::Libcall LC = GetFPLibCall(VT, RTLIB::POWI_F32, RTLIB::POWI_F64,
3391                                      RTLIB::POWI_F80, RTLIB::POWI_PPCF128);
3392     SDValue Dummy;
3393     Result = ExpandLibCall(LC, Node, false/*sign irrelevant*/, Dummy);
3394     break;
3395   }
3396   case ISD::BIT_CONVERT:
3397     switch (TLI.getOperationAction(ISD::BIT_CONVERT,
3398                                    Node->getOperand(0).getValueType())) {
3399     default: assert(0 && "Unknown operation action!");
3400     case TargetLowering::Expand:
3401       Result = EmitStackConvert(Node->getOperand(0), Node->getValueType(0),
3402                                 Node->getValueType(0), dl);
3403       break;
3404     case TargetLowering::Legal:
3405       Tmp1 = LegalizeOp(Node->getOperand(0));
3406       Result = DAG.UpdateNodeOperands(Result, Tmp1);
3407       break;
3408     }
3409     break;
3410   case ISD::CONVERT_RNDSAT: {
3411     ISD::CvtCode CvtCode = cast<CvtRndSatSDNode>(Node)->getCvtCode();
3412     switch (CvtCode) {
3413     default: assert(0 && "Unknown cvt code!");
3414     case ISD::CVT_SF:
3415     case ISD::CVT_UF:
3416     case ISD::CVT_FF:
3417       break;
3418     case ISD::CVT_FS:
3419     case ISD::CVT_FU:
3420     case ISD::CVT_SS:
3421     case ISD::CVT_SU:
3422     case ISD::CVT_US:
3423     case ISD::CVT_UU: {
3424       SDValue DTyOp = Node->getOperand(1);
3425       SDValue STyOp = Node->getOperand(2);
3426       SDValue RndOp = Node->getOperand(3);
3427       SDValue SatOp = Node->getOperand(4);
3428       Tmp1 = LegalizeOp(Node->getOperand(0));
3429       Result = DAG.UpdateNodeOperands(Result, Tmp1, DTyOp, STyOp,
3430                                       RndOp, SatOp);
3431       if (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0)) ==
3432           TargetLowering::Custom) {
3433         Tmp1 = TLI.LowerOperation(Result, DAG);
3434         if (Tmp1.getNode()) Result = Tmp1;
3435       }
3436       break;
3437     }
3438     } // end switch CvtCode
3439     break;
3440   }
3441     // Conversion operators.  The source and destination have different types.
3442   case ISD::SINT_TO_FP:
3443   case ISD::UINT_TO_FP: {
3444     bool isSigned = Node->getOpcode() == ISD::SINT_TO_FP;
3445     Result = LegalizeINT_TO_FP(Result, isSigned,
3446                                Node->getValueType(0), Node->getOperand(0), dl);
3447     break;
3448   }
3449   case ISD::TRUNCATE:
3450     Tmp1 = LegalizeOp(Node->getOperand(0));
3451     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
3452     default: assert(0 && "Unknown TRUNCATE legalization operation action!");
3453     case TargetLowering::Custom:
3454       isCustom = true;
3455       // FALLTHROUGH
3456     case TargetLowering::Legal:
3457       Result = DAG.UpdateNodeOperands(Result, Tmp1);
3458       if (isCustom) {
3459         Tmp1 = TLI.LowerOperation(Result, DAG);
3460         if (Tmp1.getNode()) Result = Tmp1;
3461       }
3462       break;
3463     }
3464     break;
3465
3466   case ISD::FP_TO_SINT:
3467   case ISD::FP_TO_UINT:
3468     Tmp1 = LegalizeOp(Node->getOperand(0));
3469
3470     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))){
3471     default: assert(0 && "Unknown operation action!");
3472     case TargetLowering::Custom:
3473       isCustom = true;
3474       // FALLTHROUGH
3475     case TargetLowering::Legal:
3476       Result = DAG.UpdateNodeOperands(Result, Tmp1);
3477       if (isCustom) {
3478         Tmp1 = TLI.LowerOperation(Result, DAG);
3479         if (Tmp1.getNode()) Result = Tmp1;
3480       }
3481       break;
3482     case TargetLowering::Promote:
3483       Result = PromoteLegalFP_TO_INT(Tmp1, Node->getValueType(0),
3484                                      Node->getOpcode() == ISD::FP_TO_SINT,
3485                                      dl);
3486       break;
3487     case TargetLowering::Expand:
3488       if (Node->getOpcode() == ISD::FP_TO_UINT) {
3489         SDValue True, False;
3490         MVT VT =  Node->getOperand(0).getValueType();
3491         MVT NVT = Node->getValueType(0);
3492         const uint64_t zero[] = {0, 0};
3493         APFloat apf = APFloat(APInt(VT.getSizeInBits(), 2, zero));
3494         APInt x = APInt::getSignBit(NVT.getSizeInBits());
3495         (void)apf.convertFromAPInt(x, false, APFloat::rmNearestTiesToEven);
3496         Tmp2 = DAG.getConstantFP(apf, VT);
3497         Tmp3 = DAG.getSetCC(dl, TLI.getSetCCResultType(VT),
3498                             Node->getOperand(0),
3499                             Tmp2, ISD::SETLT);
3500         True = DAG.getNode(ISD::FP_TO_SINT, dl, NVT, Node->getOperand(0));
3501         False = DAG.getNode(ISD::FP_TO_SINT, dl, NVT,
3502                             DAG.getNode(ISD::FSUB, dl, VT,
3503                                         Node->getOperand(0), Tmp2));
3504         False = DAG.getNode(ISD::XOR, dl, NVT, False,
3505                             DAG.getConstant(x, NVT));
3506         Result = DAG.getNode(ISD::SELECT, dl, NVT, Tmp3, True, False);
3507       } else {
3508         assert(0 && "Do not know how to expand FP_TO_SINT yet!");
3509       }
3510       break;
3511     }
3512     break;
3513
3514   case ISD::FP_EXTEND: {
3515     MVT DstVT = Op.getValueType();
3516     MVT SrcVT = Op.getOperand(0).getValueType();
3517     if (TLI.getConvertAction(SrcVT, DstVT) == TargetLowering::Expand) {
3518       // The only other way we can lower this is to turn it into a STORE,
3519       // LOAD pair, targetting a temporary location (a stack slot).
3520       Result = EmitStackConvert(Node->getOperand(0), SrcVT, DstVT, dl);
3521       break;
3522     }
3523     Tmp1 = LegalizeOp(Node->getOperand(0));
3524     Result = DAG.UpdateNodeOperands(Result, Tmp1);
3525     break;
3526   }
3527   case ISD::FP_ROUND: {
3528     MVT DstVT = Op.getValueType();
3529     MVT SrcVT = Op.getOperand(0).getValueType();
3530     if (TLI.getConvertAction(SrcVT, DstVT) == TargetLowering::Expand) {
3531       if (SrcVT == MVT::ppcf128) {
3532         // FIXME: Figure out how to extract the double without
3533         // help from type legalization
3534       }
3535       // The only other way we can lower this is to turn it into a STORE,
3536       // LOAD pair, targetting a temporary location (a stack slot).
3537       Result = EmitStackConvert(Node->getOperand(0), DstVT, DstVT, dl);
3538       break;
3539     }
3540     Tmp1 = LegalizeOp(Node->getOperand(0));
3541     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
3542     break;
3543   }
3544   case ISD::ANY_EXTEND:
3545   case ISD::ZERO_EXTEND:
3546   case ISD::SIGN_EXTEND:
3547     Tmp1 = LegalizeOp(Node->getOperand(0));
3548     Result = DAG.UpdateNodeOperands(Result, Tmp1);
3549     if (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0)) ==
3550         TargetLowering::Custom) {
3551       Tmp1 = TLI.LowerOperation(Result, DAG);
3552       if (Tmp1.getNode()) Result = Tmp1;
3553     }
3554     break;
3555   case ISD::FP_ROUND_INREG:
3556   case ISD::SIGN_EXTEND_INREG: {
3557     Tmp1 = LegalizeOp(Node->getOperand(0));
3558     MVT ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
3559
3560     // If this operation is not supported, convert it to a shl/shr or load/store
3561     // pair.
3562     switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
3563     default: assert(0 && "This action not supported for this op yet!");
3564     case TargetLowering::Legal:
3565       Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
3566       break;
3567     case TargetLowering::Expand:
3568       // If this is an integer extend and shifts are supported, do that.
3569       if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
3570         // NOTE: we could fall back on load/store here too for targets without
3571         // SAR.  However, it is doubtful that any exist.
3572         unsigned BitsDiff = Node->getValueType(0).getSizeInBits() -
3573                             ExtraVT.getSizeInBits();
3574         SDValue ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy());
3575         Result = DAG.getNode(ISD::SHL, dl, Node->getValueType(0),
3576                              Node->getOperand(0), ShiftCst);
3577         Result = DAG.getNode(ISD::SRA, dl, Node->getValueType(0),
3578                              Result, ShiftCst);
3579       } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
3580         // The only way we can lower this is to turn it into a TRUNCSTORE,
3581         // EXTLOAD pair, targetting a temporary location (a stack slot).
3582
3583         // NOTE: there is a choice here between constantly creating new stack
3584         // slots and always reusing the same one.  We currently always create
3585         // new ones, as reuse may inhibit scheduling.
3586         Result = EmitStackConvert(Node->getOperand(0), ExtraVT,
3587                                   Node->getValueType(0), dl);
3588       } else {
3589         assert(0 && "Unknown op");
3590       }
3591       break;
3592     }
3593     break;
3594   }
3595   case ISD::TRAMPOLINE: {
3596     SDValue Ops[6];
3597     for (unsigned i = 0; i != 6; ++i)
3598       Ops[i] = LegalizeOp(Node->getOperand(i));
3599     Result = DAG.UpdateNodeOperands(Result, Ops, 6);
3600     // The only option for this node is to custom lower it.
3601     Result = TLI.LowerOperation(Result, DAG);
3602     assert(Result.getNode() && "Should always custom lower!");
3603
3604     // Since trampoline produces two values, make sure to remember that we
3605     // legalized both of them.
3606     Tmp1 = LegalizeOp(Result.getValue(1));
3607     Result = LegalizeOp(Result);
3608     AddLegalizedOperand(SDValue(Node, 0), Result);
3609     AddLegalizedOperand(SDValue(Node, 1), Tmp1);
3610     return Op.getResNo() ? Tmp1 : Result;
3611   }
3612   case ISD::FLT_ROUNDS_: {
3613     MVT VT = Node->getValueType(0);
3614     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
3615     default: assert(0 && "This action not supported for this op yet!");
3616     case TargetLowering::Custom:
3617       Result = TLI.LowerOperation(Op, DAG);
3618       if (Result.getNode()) break;
3619       // Fall Thru
3620     case TargetLowering::Legal:
3621       // If this operation is not supported, lower it to constant 1
3622       Result = DAG.getConstant(1, VT);
3623       break;
3624     }
3625     break;
3626   }
3627   case ISD::TRAP: {
3628     MVT VT = Node->getValueType(0);
3629     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
3630     default: assert(0 && "This action not supported for this op yet!");
3631     case TargetLowering::Legal:
3632       Tmp1 = LegalizeOp(Node->getOperand(0));
3633       Result = DAG.UpdateNodeOperands(Result, Tmp1);
3634       break;
3635     case TargetLowering::Custom:
3636       Result = TLI.LowerOperation(Op, DAG);
3637       if (Result.getNode()) break;
3638       // Fall Thru
3639     case TargetLowering::Expand:
3640       // If this operation is not supported, lower it to 'abort()' call
3641       Tmp1 = LegalizeOp(Node->getOperand(0));
3642       TargetLowering::ArgListTy Args;
3643       std::pair<SDValue, SDValue> CallResult =
3644         TLI.LowerCallTo(Tmp1, Type::VoidTy,
3645                         false, false, false, false, CallingConv::C, false,
3646                         DAG.getExternalSymbol("abort", TLI.getPointerTy()),
3647                         Args, DAG, dl);
3648       Result = CallResult.second;
3649       break;
3650     }
3651     break;
3652   }
3653
3654   case ISD::SADDO:
3655   case ISD::SSUBO: {
3656     MVT VT = Node->getValueType(0);
3657     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
3658     default: assert(0 && "This action not supported for this op yet!");
3659     case TargetLowering::Custom:
3660       Result = TLI.LowerOperation(Op, DAG);
3661       if (Result.getNode()) break;
3662       // FALLTHROUGH
3663     case TargetLowering::Legal: {
3664       SDValue LHS = LegalizeOp(Node->getOperand(0));
3665       SDValue RHS = LegalizeOp(Node->getOperand(1));
3666
3667       SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::SADDO ?
3668                                 ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
3669                                 LHS, RHS);
3670       MVT OType = Node->getValueType(1);
3671
3672       SDValue Zero = DAG.getConstant(0, LHS.getValueType());
3673
3674       //   LHSSign -> LHS >= 0
3675       //   RHSSign -> RHS >= 0
3676       //   SumSign -> Sum >= 0
3677       //
3678       //   Add:
3679       //   Overflow -> (LHSSign == RHSSign) && (LHSSign != SumSign)
3680       //   Sub:
3681       //   Overflow -> (LHSSign != RHSSign) && (LHSSign != SumSign)
3682       //
3683       SDValue LHSSign = DAG.getSetCC(dl, OType, LHS, Zero, ISD::SETGE);
3684       SDValue RHSSign = DAG.getSetCC(dl, OType, RHS, Zero, ISD::SETGE);
3685       SDValue SignsMatch = DAG.getSetCC(dl, OType, LHSSign, RHSSign,
3686                                         Node->getOpcode() == ISD::SADDO ?
3687                                         ISD::SETEQ : ISD::SETNE);
3688
3689       SDValue SumSign = DAG.getSetCC(dl, OType, Sum, Zero, ISD::SETGE);
3690       SDValue SumSignNE = DAG.getSetCC(dl, OType, LHSSign, SumSign, ISD::SETNE);
3691
3692       SDValue Cmp = DAG.getNode(ISD::AND, dl, OType, SignsMatch, SumSignNE);
3693
3694       MVT ValueVTs[] = { LHS.getValueType(), OType };
3695       SDValue Ops[] = { Sum, Cmp };
3696
3697       Result = DAG.getNode(ISD::MERGE_VALUES, dl,
3698                            DAG.getVTList(&ValueVTs[0], 2),
3699                            &Ops[0], 2);
3700       SDNode *RNode = Result.getNode();
3701       DAG.ReplaceAllUsesWith(Node, RNode);
3702       break;
3703     }
3704     }
3705
3706     break;
3707   }
3708   case ISD::UADDO:
3709   case ISD::USUBO: {
3710     MVT VT = Node->getValueType(0);
3711     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
3712     default: assert(0 && "This action not supported for this op yet!");
3713     case TargetLowering::Custom:
3714       Result = TLI.LowerOperation(Op, DAG);
3715       if (Result.getNode()) break;
3716       // FALLTHROUGH
3717     case TargetLowering::Legal: {
3718       SDValue LHS = LegalizeOp(Node->getOperand(0));
3719       SDValue RHS = LegalizeOp(Node->getOperand(1));
3720
3721       SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::UADDO ?
3722                                 ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
3723                                 LHS, RHS);
3724       MVT OType = Node->getValueType(1);
3725       SDValue Cmp = DAG.getSetCC(dl, OType, Sum, LHS,
3726                                  Node->getOpcode () == ISD::UADDO ?
3727                                  ISD::SETULT : ISD::SETUGT);
3728
3729       MVT ValueVTs[] = { LHS.getValueType(), OType };
3730       SDValue Ops[] = { Sum, Cmp };
3731
3732       Result = DAG.getNode(ISD::MERGE_VALUES, dl,
3733                            DAG.getVTList(&ValueVTs[0], 2),
3734                            &Ops[0], 2);
3735       SDNode *RNode = Result.getNode();
3736       DAG.ReplaceAllUsesWith(Node, RNode);
3737       break;
3738     }
3739     }
3740
3741     break;
3742   }
3743   case ISD::SMULO:
3744   case ISD::UMULO: {
3745     MVT VT = Node->getValueType(0);
3746     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
3747     default: assert(0 && "This action is not supported at all!");
3748     case TargetLowering::Custom:
3749       Result = TLI.LowerOperation(Op, DAG);
3750       if (Result.getNode()) break;
3751       // Fall Thru
3752     case TargetLowering::Legal:
3753       // FIXME: According to Hacker's Delight, this can be implemented in
3754       // target independent lowering, but it would be inefficient, since it
3755       // requires a division + a branch.
3756       assert(0 && "Target independent lowering is not supported for SMULO/UMULO!");
3757     break;
3758     }
3759     break;
3760   }
3761
3762   }
3763
3764   assert(Result.getValueType() == Op.getValueType() &&
3765          "Bad legalization!");
3766
3767   // Make sure that the generated code is itself legal.
3768   if (Result != Op)
3769     Result = LegalizeOp(Result);
3770
3771   // Note that LegalizeOp may be reentered even from single-use nodes, which
3772   // means that we always must cache transformed nodes.
3773   AddLegalizedOperand(Op, Result);
3774   return Result;
3775 }
3776
3777 /// ExpandEXTRACT_VECTOR_ELT - Expand an EXTRACT_VECTOR_ELT operation into
3778 /// a legal EXTRACT_VECTOR_ELT operation, scalar code, or memory traffic,
3779 /// based on the vector type. The return type of this matches the element type
3780 /// of the vector, which may not be legal for the target.
3781 SDValue SelectionDAGLegalize::ExpandEXTRACT_VECTOR_ELT(SDValue Op) {
3782   // We know that operand #0 is the Vec vector.  If the index is a constant
3783   // or if the invec is a supported hardware type, we can use it.  Otherwise,
3784   // lower to a store then an indexed load.
3785   SDValue Vec = Op.getOperand(0);
3786   SDValue Idx = Op.getOperand(1);
3787   DebugLoc dl = Op.getDebugLoc();
3788
3789   MVT TVT = Vec.getValueType();
3790   unsigned NumElems = TVT.getVectorNumElements();
3791
3792   switch (TLI.getOperationAction(ISD::EXTRACT_VECTOR_ELT, TVT)) {
3793   default: assert(0 && "This action is not supported yet!");
3794   case TargetLowering::Custom: {
3795     Vec = LegalizeOp(Vec);
3796     Op = DAG.UpdateNodeOperands(Op, Vec, Idx);
3797     SDValue Tmp3 = TLI.LowerOperation(Op, DAG);
3798     if (Tmp3.getNode())
3799       return Tmp3;
3800     break;
3801   }
3802   case TargetLowering::Legal:
3803     if (isTypeLegal(TVT)) {
3804       Vec = LegalizeOp(Vec);
3805       Op = DAG.UpdateNodeOperands(Op, Vec, Idx);
3806       return Op;
3807     }
3808     break;
3809   case TargetLowering::Promote:
3810     assert(TVT.isVector() && "not vector type");
3811     // fall thru to expand since vectors are by default are promote
3812   case TargetLowering::Expand:
3813     break;
3814   }
3815
3816   if (NumElems == 1)
3817     // This must be an access of the only element.  Return it.
3818     return DAG.getNode(ISD::BIT_CONVERT, dl, Op.getValueType(), Vec);
3819   else
3820     return ExpandExtractFromVectorThroughStack(Op);
3821 }
3822
3823 SDValue SelectionDAGLegalize::ExpandExtractFromVectorThroughStack(SDValue Op) {
3824   SDValue Vec = Op.getOperand(0);
3825   SDValue Idx = Op.getOperand(1);
3826   DebugLoc dl = Op.getDebugLoc();
3827   // Store the value to a temporary stack slot, then LOAD the returned part.
3828   SDValue StackPtr = DAG.CreateStackTemporary(Vec.getValueType());
3829   SDValue Ch = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr, NULL, 0);
3830
3831   // Add the offset to the index.
3832   unsigned EltSize =
3833       Vec.getValueType().getVectorElementType().getSizeInBits()/8;
3834   Idx = DAG.getNode(ISD::MUL, dl, Idx.getValueType(), Idx,
3835                     DAG.getConstant(EltSize, Idx.getValueType()));
3836
3837   if (Idx.getValueType().bitsGT(TLI.getPointerTy()))
3838     Idx = DAG.getNode(ISD::TRUNCATE, dl, TLI.getPointerTy(), Idx);
3839   else
3840     Idx = DAG.getNode(ISD::ZERO_EXTEND, dl, TLI.getPointerTy(), Idx);
3841
3842   StackPtr = DAG.getNode(ISD::ADD, dl, Idx.getValueType(), Idx, StackPtr);
3843
3844   return DAG.getLoad(Op.getValueType(), dl, Ch, StackPtr, NULL, 0);
3845 }
3846
3847 /// LegalizeSetCCOperands - Attempts to create a legal LHS and RHS for a SETCC
3848 /// with condition CC on the current target.  This usually involves legalizing
3849 /// or promoting the arguments.  In the case where LHS and RHS must be expanded,
3850 /// there may be no choice but to create a new SetCC node to represent the
3851 /// legalized value of setcc lhs, rhs.  In this case, the value is returned in
3852 /// LHS, and the SDValue returned in RHS has a nil SDNode value.
3853 void SelectionDAGLegalize::LegalizeSetCCOperands(SDValue &LHS,
3854                                                  SDValue &RHS,
3855                                                  SDValue &CC,
3856                                                  DebugLoc dl) {
3857   LHS = LegalizeOp(LHS);
3858   RHS = LegalizeOp(RHS);
3859 }
3860
3861 /// LegalizeSetCCCondCode - Legalize a SETCC with given LHS and RHS and
3862 /// condition code CC on the current target. This routine assumes LHS and rHS
3863 /// have already been legalized by LegalizeSetCCOperands. It expands SETCC with
3864 /// illegal condition code into AND / OR of multiple SETCC values.
3865 void SelectionDAGLegalize::LegalizeSetCCCondCode(MVT VT,
3866                                                  SDValue &LHS, SDValue &RHS,
3867                                                  SDValue &CC,
3868                                                  DebugLoc dl) {
3869   MVT OpVT = LHS.getValueType();
3870   ISD::CondCode CCCode = cast<CondCodeSDNode>(CC)->get();
3871   switch (TLI.getCondCodeAction(CCCode, OpVT)) {
3872   default: assert(0 && "Unknown condition code action!");
3873   case TargetLowering::Legal:
3874     // Nothing to do.
3875     break;
3876   case TargetLowering::Expand: {
3877     ISD::CondCode CC1 = ISD::SETCC_INVALID, CC2 = ISD::SETCC_INVALID;
3878     unsigned Opc = 0;
3879     switch (CCCode) {
3880     default: assert(0 && "Don't know how to expand this condition!"); abort();
3881     case ISD::SETOEQ: CC1 = ISD::SETEQ; CC2 = ISD::SETO;  Opc = ISD::AND; break;
3882     case ISD::SETOGT: CC1 = ISD::SETGT; CC2 = ISD::SETO;  Opc = ISD::AND; break;
3883     case ISD::SETOGE: CC1 = ISD::SETGE; CC2 = ISD::SETO;  Opc = ISD::AND; break;
3884     case ISD::SETOLT: CC1 = ISD::SETLT; CC2 = ISD::SETO;  Opc = ISD::AND; break;
3885     case ISD::SETOLE: CC1 = ISD::SETLE; CC2 = ISD::SETO;  Opc = ISD::AND; break;
3886     case ISD::SETONE: CC1 = ISD::SETNE; CC2 = ISD::SETO;  Opc = ISD::AND; break;
3887     case ISD::SETUEQ: CC1 = ISD::SETEQ; CC2 = ISD::SETUO; Opc = ISD::OR;  break;
3888     case ISD::SETUGT: CC1 = ISD::SETGT; CC2 = ISD::SETUO; Opc = ISD::OR;  break;
3889     case ISD::SETUGE: CC1 = ISD::SETGE; CC2 = ISD::SETUO; Opc = ISD::OR;  break;
3890     case ISD::SETULT: CC1 = ISD::SETLT; CC2 = ISD::SETUO; Opc = ISD::OR;  break;
3891     case ISD::SETULE: CC1 = ISD::SETLE; CC2 = ISD::SETUO; Opc = ISD::OR;  break;
3892     case ISD::SETUNE: CC1 = ISD::SETNE; CC2 = ISD::SETUO; Opc = ISD::OR;  break;
3893     // FIXME: Implement more expansions.
3894     }
3895
3896     SDValue SetCC1 = DAG.getSetCC(dl, VT, LHS, RHS, CC1);
3897     SDValue SetCC2 = DAG.getSetCC(dl, VT, LHS, RHS, CC2);
3898     LHS = DAG.getNode(Opc, dl, VT, SetCC1, SetCC2);
3899     RHS = SDValue();
3900     CC  = SDValue();
3901     break;
3902   }
3903   }
3904 }
3905
3906 /// EmitStackConvert - Emit a store/load combination to the stack.  This stores
3907 /// SrcOp to a stack slot of type SlotVT, truncating it if needed.  It then does
3908 /// a load from the stack slot to DestVT, extending it if needed.
3909 /// The resultant code need not be legal.
3910 SDValue SelectionDAGLegalize::EmitStackConvert(SDValue SrcOp,
3911                                                MVT SlotVT,
3912                                                MVT DestVT,
3913                                                DebugLoc dl) {
3914   // Create the stack frame object.
3915   unsigned SrcAlign =
3916     TLI.getTargetData()->getPrefTypeAlignment(SrcOp.getValueType().
3917                                               getTypeForMVT());
3918   SDValue FIPtr = DAG.CreateStackTemporary(SlotVT, SrcAlign);
3919
3920   FrameIndexSDNode *StackPtrFI = cast<FrameIndexSDNode>(FIPtr);
3921   int SPFI = StackPtrFI->getIndex();
3922   const Value *SV = PseudoSourceValue::getFixedStack(SPFI);
3923
3924   unsigned SrcSize = SrcOp.getValueType().getSizeInBits();
3925   unsigned SlotSize = SlotVT.getSizeInBits();
3926   unsigned DestSize = DestVT.getSizeInBits();
3927   unsigned DestAlign =
3928     TLI.getTargetData()->getPrefTypeAlignment(DestVT.getTypeForMVT());
3929
3930   // Emit a store to the stack slot.  Use a truncstore if the input value is
3931   // later than DestVT.
3932   SDValue Store;
3933
3934   if (SrcSize > SlotSize)
3935     Store = DAG.getTruncStore(DAG.getEntryNode(), dl, SrcOp, FIPtr,
3936                               SV, 0, SlotVT, false, SrcAlign);
3937   else {
3938     assert(SrcSize == SlotSize && "Invalid store");
3939     Store = DAG.getStore(DAG.getEntryNode(), dl, SrcOp, FIPtr,
3940                          SV, 0, false, SrcAlign);
3941   }
3942
3943   // Result is a load from the stack slot.
3944   if (SlotSize == DestSize)
3945     return DAG.getLoad(DestVT, dl, Store, FIPtr, SV, 0, false, DestAlign);
3946
3947   assert(SlotSize < DestSize && "Unknown extension!");
3948   return DAG.getExtLoad(ISD::EXTLOAD, dl, DestVT, Store, FIPtr, SV, 0, SlotVT,
3949                         false, DestAlign);
3950 }
3951
3952 SDValue SelectionDAGLegalize::ExpandSCALAR_TO_VECTOR(SDNode *Node) {
3953   DebugLoc dl = Node->getDebugLoc();
3954   // Create a vector sized/aligned stack slot, store the value to element #0,
3955   // then load the whole vector back out.
3956   SDValue StackPtr = DAG.CreateStackTemporary(Node->getValueType(0));
3957
3958   FrameIndexSDNode *StackPtrFI = cast<FrameIndexSDNode>(StackPtr);
3959   int SPFI = StackPtrFI->getIndex();
3960
3961   SDValue Ch = DAG.getTruncStore(DAG.getEntryNode(), dl, Node->getOperand(0),
3962                                  StackPtr,
3963                                  PseudoSourceValue::getFixedStack(SPFI), 0,
3964                                  Node->getValueType(0).getVectorElementType());
3965   return DAG.getLoad(Node->getValueType(0), dl, Ch, StackPtr,
3966                      PseudoSourceValue::getFixedStack(SPFI), 0);
3967 }
3968
3969
3970 /// ExpandBUILD_VECTOR - Expand a BUILD_VECTOR node on targets that don't
3971 /// support the operation, but do support the resultant vector type.
3972 SDValue SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
3973   unsigned NumElems = Node->getNumOperands();
3974   SDValue SplatValue = Node->getOperand(0);
3975   DebugLoc dl = Node->getDebugLoc();
3976   MVT VT = Node->getValueType(0);
3977   MVT OpVT = SplatValue.getValueType();
3978   MVT EltVT = VT.getVectorElementType();
3979
3980   // If the only non-undef value is the low element, turn this into a
3981   // SCALAR_TO_VECTOR node.  If this is { X, X, X, X }, determine X.
3982   bool isOnlyLowElement = true;
3983
3984   // FIXME: it would be far nicer to change this into map<SDValue,uint64_t>
3985   // and use a bitmask instead of a list of elements.
3986   // FIXME: this doesn't treat <0, u, 0, u> for example, as a splat.
3987   std::map<SDValue, std::vector<unsigned> > Values;
3988   Values[SplatValue].push_back(0);
3989   bool isConstant = true;
3990   if (!isa<ConstantFPSDNode>(SplatValue) && !isa<ConstantSDNode>(SplatValue) &&
3991       SplatValue.getOpcode() != ISD::UNDEF)
3992     isConstant = false;
3993
3994   for (unsigned i = 1; i < NumElems; ++i) {
3995     SDValue V = Node->getOperand(i);
3996     Values[V].push_back(i);
3997     if (V.getOpcode() != ISD::UNDEF)
3998       isOnlyLowElement = false;
3999     if (SplatValue != V)
4000       SplatValue = SDValue(0, 0);
4001
4002     // If this isn't a constant element or an undef, we can't use a constant
4003     // pool load.
4004     if (!isa<ConstantFPSDNode>(V) && !isa<ConstantSDNode>(V) &&
4005         V.getOpcode() != ISD::UNDEF)
4006       isConstant = false;
4007   }
4008
4009   if (isOnlyLowElement) {
4010     // If the low element is an undef too, then this whole things is an undef.
4011     if (Node->getOperand(0).getOpcode() == ISD::UNDEF)
4012       return DAG.getUNDEF(VT);
4013     // Otherwise, turn this into a scalar_to_vector node.
4014     return DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Node->getOperand(0));
4015   }
4016
4017   // If all elements are constants, create a load from the constant pool.
4018   if (isConstant) {
4019     std::vector<Constant*> CV;
4020     for (unsigned i = 0, e = NumElems; i != e; ++i) {
4021       if (ConstantFPSDNode *V =
4022           dyn_cast<ConstantFPSDNode>(Node->getOperand(i))) {
4023         CV.push_back(const_cast<ConstantFP *>(V->getConstantFPValue()));
4024       } else if (ConstantSDNode *V =
4025                  dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
4026         CV.push_back(const_cast<ConstantInt *>(V->getConstantIntValue()));
4027       } else {
4028         assert(Node->getOperand(i).getOpcode() == ISD::UNDEF);
4029         const Type *OpNTy = OpVT.getTypeForMVT();
4030         CV.push_back(UndefValue::get(OpNTy));
4031       }
4032     }
4033     Constant *CP = ConstantVector::get(CV);
4034     SDValue CPIdx = DAG.getConstantPool(CP, TLI.getPointerTy());
4035     unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment();
4036     return DAG.getLoad(VT, dl, DAG.getEntryNode(), CPIdx,
4037                        PseudoSourceValue::getConstantPool(), 0,
4038                        false, Alignment);
4039   }
4040
4041   if (SplatValue.getNode()) {   // Splat of one value?
4042     // Build the shuffle constant vector: <0, 0, 0, 0>
4043     SmallVector<int, 8> ZeroVec(NumElems, 0);
4044
4045     // If the target supports VECTOR_SHUFFLE and this shuffle mask, use it.
4046     if (TLI.isShuffleMaskLegal(ZeroVec, Node->getValueType(0))) {
4047       // Get the splatted value into the low element of a vector register.
4048       SDValue LowValVec =
4049         DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, SplatValue);
4050
4051       // Return shuffle(LowValVec, undef, <0,0,0,0>)
4052       return DAG.getVectorShuffle(VT, dl, LowValVec, DAG.getUNDEF(VT),
4053                                   &ZeroVec[0]);
4054     }
4055   }
4056
4057   // If there are only two unique elements, we may be able to turn this into a
4058   // vector shuffle.
4059   if (Values.size() == 2) {
4060     // Get the two values in deterministic order.
4061     SDValue Val1 = Node->getOperand(1);
4062     SDValue Val2;
4063     std::map<SDValue, std::vector<unsigned> >::iterator MI = Values.begin();
4064     if (MI->first != Val1)
4065       Val2 = MI->first;
4066     else
4067       Val2 = (++MI)->first;
4068
4069     // If Val1 is an undef, make sure it ends up as Val2, to ensure that our
4070     // vector shuffle has the undef vector on the RHS.
4071     if (Val1.getOpcode() == ISD::UNDEF)
4072       std::swap(Val1, Val2);
4073
4074     // Build the shuffle constant vector: e.g. <0, 4, 0, 4>
4075     SmallVector<int, 8> ShuffleMask(NumElems, -1);
4076
4077     // Set elements of the shuffle mask for Val1.
4078     std::vector<unsigned> &Val1Elts = Values[Val1];
4079     for (unsigned i = 0, e = Val1Elts.size(); i != e; ++i)
4080       ShuffleMask[Val1Elts[i]] = 0;
4081
4082     // Set elements of the shuffle mask for Val2.
4083     std::vector<unsigned> &Val2Elts = Values[Val2];
4084     for (unsigned i = 0, e = Val2Elts.size(); i != e; ++i)
4085       if (Val2.getOpcode() != ISD::UNDEF)
4086         ShuffleMask[Val2Elts[i]] = NumElems;
4087
4088     // If the target supports SCALAR_TO_VECTOR and this shuffle mask, use it.
4089     if (TLI.isOperationLegalOrCustom(ISD::SCALAR_TO_VECTOR, VT) &&
4090         TLI.isShuffleMaskLegal(ShuffleMask, VT)) {
4091       Val1 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Val1);
4092       Val2 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Val2);
4093       return DAG.getVectorShuffle(VT, dl, Val1, Val2, &ShuffleMask[0]);
4094     }
4095   }
4096
4097   // Otherwise, we can't handle this case efficiently.  Allocate a sufficiently
4098   // aligned object on the stack, store each element into it, then load
4099   // the result as a vector.
4100   // Create the stack frame object.
4101   SDValue FIPtr = DAG.CreateStackTemporary(VT);
4102   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
4103   const Value *SV = PseudoSourceValue::getFixedStack(FI);
4104
4105   // Emit a store of each element to the stack slot.
4106   SmallVector<SDValue, 8> Stores;
4107   unsigned TypeByteSize = OpVT.getSizeInBits() / 8;
4108   // Store (in the right endianness) the elements to memory.
4109   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
4110     // Ignore undef elements.
4111     if (Node->getOperand(i).getOpcode() == ISD::UNDEF) continue;
4112
4113     unsigned Offset = TypeByteSize*i;
4114
4115     SDValue Idx = DAG.getConstant(Offset, FIPtr.getValueType());
4116     Idx = DAG.getNode(ISD::ADD, dl, FIPtr.getValueType(), FIPtr, Idx);
4117
4118     Stores.push_back(DAG.getStore(DAG.getEntryNode(), dl, Node->getOperand(i),
4119                                   Idx, SV, Offset));
4120   }
4121
4122   SDValue StoreChain;
4123   if (!Stores.empty())    // Not all undef elements?
4124     StoreChain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
4125                              &Stores[0], Stores.size());
4126   else
4127     StoreChain = DAG.getEntryNode();
4128
4129   // Result is a load from the stack slot.
4130   return DAG.getLoad(VT, dl, StoreChain, FIPtr, SV, 0);
4131 }
4132
4133 // ExpandLibCall - Expand a node into a call to a libcall.  If the result value
4134 // does not fit into a register, return the lo part and set the hi part to the
4135 // by-reg argument.  If it does fit into a single register, return the result
4136 // and leave the Hi part unset.
4137 SDValue SelectionDAGLegalize::ExpandLibCall(RTLIB::Libcall LC, SDNode *Node,
4138                                             bool isSigned, SDValue &Hi) {
4139   assert(!IsLegalizingCall && "Cannot overlap legalization of calls!");
4140   // The input chain to this libcall is the entry node of the function.
4141   // Legalizing the call will automatically add the previous call to the
4142   // dependence.
4143   SDValue InChain = DAG.getEntryNode();
4144
4145   TargetLowering::ArgListTy Args;
4146   TargetLowering::ArgListEntry Entry;
4147   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
4148     MVT ArgVT = Node->getOperand(i).getValueType();
4149     const Type *ArgTy = ArgVT.getTypeForMVT();
4150     Entry.Node = Node->getOperand(i); Entry.Ty = ArgTy;
4151     Entry.isSExt = isSigned;
4152     Entry.isZExt = !isSigned;
4153     Args.push_back(Entry);
4154   }
4155   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
4156                                          TLI.getPointerTy());
4157
4158   // Splice the libcall in wherever FindInputOutputChains tells us to.
4159   const Type *RetTy = Node->getValueType(0).getTypeForMVT();
4160   std::pair<SDValue, SDValue> CallInfo =
4161     TLI.LowerCallTo(InChain, RetTy, isSigned, !isSigned, false, false,
4162                     CallingConv::C, false, Callee, Args, DAG,
4163                     Node->getDebugLoc());
4164
4165   // Legalize the call sequence, starting with the chain.  This will advance
4166   // the LastCALLSEQ_END to the legalized version of the CALLSEQ_END node that
4167   // was added by LowerCallTo (guaranteeing proper serialization of calls).
4168   LegalizeOp(CallInfo.second);
4169   return CallInfo.first;
4170 }
4171
4172 /// LegalizeINT_TO_FP - Legalize a [US]INT_TO_FP operation.
4173 ///
4174 SDValue SelectionDAGLegalize::
4175 LegalizeINT_TO_FP(SDValue Result, bool isSigned, MVT DestTy, SDValue Op,
4176                   DebugLoc dl) {
4177   bool isCustom = false;
4178   SDValue Tmp1;
4179   switch (TLI.getOperationAction(isSigned ? ISD::SINT_TO_FP : ISD::UINT_TO_FP,
4180                                  Op.getValueType())) {
4181   default: assert(0 && "Unknown operation action!");
4182   case TargetLowering::Custom:
4183     isCustom = true;
4184     // FALLTHROUGH
4185   case TargetLowering::Legal:
4186     Tmp1 = LegalizeOp(Op);
4187     if (Result.getNode())
4188       Result = DAG.UpdateNodeOperands(Result, Tmp1);
4189     else
4190       Result = DAG.getNode(isSigned ? ISD::SINT_TO_FP : ISD::UINT_TO_FP, dl,
4191                            DestTy, Tmp1);
4192     if (isCustom) {
4193       Tmp1 = TLI.LowerOperation(Result, DAG);
4194       if (Tmp1.getNode()) Result = Tmp1;
4195     }
4196     break;
4197   case TargetLowering::Expand:
4198     Result = ExpandLegalINT_TO_FP(isSigned, LegalizeOp(Op), DestTy, dl);
4199     break;
4200   case TargetLowering::Promote:
4201     Result = PromoteLegalINT_TO_FP(LegalizeOp(Op), DestTy, isSigned, dl);
4202     break;
4203   }
4204   return Result;
4205 }
4206
4207 /// ExpandLegalINT_TO_FP - This function is responsible for legalizing a
4208 /// INT_TO_FP operation of the specified operand when the target requests that
4209 /// we expand it.  At this point, we know that the result and operand types are
4210 /// legal for the target.
4211 SDValue SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned,
4212                                                    SDValue Op0,
4213                                                    MVT DestVT,
4214                                                    DebugLoc dl) {
4215   if (Op0.getValueType() == MVT::i32) {
4216     // simple 32-bit [signed|unsigned] integer to float/double expansion
4217
4218     // Get the stack frame index of a 8 byte buffer.
4219     SDValue StackSlot = DAG.CreateStackTemporary(MVT::f64);
4220
4221     // word offset constant for Hi/Lo address computation
4222     SDValue WordOff = DAG.getConstant(sizeof(int), TLI.getPointerTy());
4223     // set up Hi and Lo (into buffer) address based on endian
4224     SDValue Hi = StackSlot;
4225     SDValue Lo = DAG.getNode(ISD::ADD, dl,
4226                              TLI.getPointerTy(), StackSlot, WordOff);
4227     if (TLI.isLittleEndian())
4228       std::swap(Hi, Lo);
4229
4230     // if signed map to unsigned space
4231     SDValue Op0Mapped;
4232     if (isSigned) {
4233       // constant used to invert sign bit (signed to unsigned mapping)
4234       SDValue SignBit = DAG.getConstant(0x80000000u, MVT::i32);
4235       Op0Mapped = DAG.getNode(ISD::XOR, dl, MVT::i32, Op0, SignBit);
4236     } else {
4237       Op0Mapped = Op0;
4238     }
4239     // store the lo of the constructed double - based on integer input
4240     SDValue Store1 = DAG.getStore(DAG.getEntryNode(), dl,
4241                                   Op0Mapped, Lo, NULL, 0);
4242     // initial hi portion of constructed double
4243     SDValue InitialHi = DAG.getConstant(0x43300000u, MVT::i32);
4244     // store the hi of the constructed double - biased exponent
4245     SDValue Store2=DAG.getStore(Store1, dl, InitialHi, Hi, NULL, 0);
4246     // load the constructed double
4247     SDValue Load = DAG.getLoad(MVT::f64, dl, Store2, StackSlot, NULL, 0);
4248     // FP constant to bias correct the final result
4249     SDValue Bias = DAG.getConstantFP(isSigned ?
4250                                      BitsToDouble(0x4330000080000000ULL) :
4251                                      BitsToDouble(0x4330000000000000ULL),
4252                                      MVT::f64);
4253     // subtract the bias
4254     SDValue Sub = DAG.getNode(ISD::FSUB, dl, MVT::f64, Load, Bias);
4255     // final result
4256     SDValue Result;
4257     // handle final rounding
4258     if (DestVT == MVT::f64) {
4259       // do nothing
4260       Result = Sub;
4261     } else if (DestVT.bitsLT(MVT::f64)) {
4262       Result = DAG.getNode(ISD::FP_ROUND, dl, DestVT, Sub,
4263                            DAG.getIntPtrConstant(0));
4264     } else if (DestVT.bitsGT(MVT::f64)) {
4265       Result = DAG.getNode(ISD::FP_EXTEND, dl, DestVT, Sub);
4266     }
4267     return Result;
4268   }
4269   assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet");
4270   SDValue Tmp1 = DAG.getNode(ISD::SINT_TO_FP, dl, DestVT, Op0);
4271
4272   SDValue SignSet = DAG.getSetCC(dl, TLI.getSetCCResultType(Op0.getValueType()),
4273                                  Op0, DAG.getConstant(0, Op0.getValueType()),
4274                                  ISD::SETLT);
4275   SDValue Zero = DAG.getIntPtrConstant(0), Four = DAG.getIntPtrConstant(4);
4276   SDValue CstOffset = DAG.getNode(ISD::SELECT, dl, Zero.getValueType(),
4277                                     SignSet, Four, Zero);
4278
4279   // If the sign bit of the integer is set, the large number will be treated
4280   // as a negative number.  To counteract this, the dynamic code adds an
4281   // offset depending on the data type.
4282   uint64_t FF;
4283   switch (Op0.getValueType().getSimpleVT()) {
4284   default: assert(0 && "Unsupported integer type!");
4285   case MVT::i8 : FF = 0x43800000ULL; break;  // 2^8  (as a float)
4286   case MVT::i16: FF = 0x47800000ULL; break;  // 2^16 (as a float)
4287   case MVT::i32: FF = 0x4F800000ULL; break;  // 2^32 (as a float)
4288   case MVT::i64: FF = 0x5F800000ULL; break;  // 2^64 (as a float)
4289   }
4290   if (TLI.isLittleEndian()) FF <<= 32;
4291   Constant *FudgeFactor = ConstantInt::get(Type::Int64Ty, FF);
4292
4293   SDValue CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
4294   unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment();
4295   CPIdx = DAG.getNode(ISD::ADD, dl, TLI.getPointerTy(), CPIdx, CstOffset);
4296   Alignment = std::min(Alignment, 4u);
4297   SDValue FudgeInReg;
4298   if (DestVT == MVT::f32)
4299     FudgeInReg = DAG.getLoad(MVT::f32, dl, DAG.getEntryNode(), CPIdx,
4300                              PseudoSourceValue::getConstantPool(), 0,
4301                              false, Alignment);
4302   else {
4303     FudgeInReg =
4304       LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, dl, DestVT,
4305                                 DAG.getEntryNode(), CPIdx,
4306                                 PseudoSourceValue::getConstantPool(), 0,
4307                                 MVT::f32, false, Alignment));
4308   }
4309
4310   return DAG.getNode(ISD::FADD, dl, DestVT, Tmp1, FudgeInReg);
4311 }
4312
4313 /// PromoteLegalINT_TO_FP - This function is responsible for legalizing a
4314 /// *INT_TO_FP operation of the specified operand when the target requests that
4315 /// we promote it.  At this point, we know that the result and operand types are
4316 /// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP
4317 /// operation that takes a larger input.
4318 SDValue SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDValue LegalOp,
4319                                                     MVT DestVT,
4320                                                     bool isSigned,
4321                                                     DebugLoc dl) {
4322   // First step, figure out the appropriate *INT_TO_FP operation to use.
4323   MVT NewInTy = LegalOp.getValueType();
4324
4325   unsigned OpToUse = 0;
4326
4327   // Scan for the appropriate larger type to use.
4328   while (1) {
4329     NewInTy = (MVT::SimpleValueType)(NewInTy.getSimpleVT()+1);
4330     assert(NewInTy.isInteger() && "Ran out of possibilities!");
4331
4332     // If the target supports SINT_TO_FP of this type, use it.
4333     switch (TLI.getOperationAction(ISD::SINT_TO_FP, NewInTy)) {
4334       default: break;
4335       case TargetLowering::Legal:
4336         if (!TLI.isTypeLegal(NewInTy))
4337           break;  // Can't use this datatype.
4338         // FALL THROUGH.
4339       case TargetLowering::Custom:
4340         OpToUse = ISD::SINT_TO_FP;
4341         break;
4342     }
4343     if (OpToUse) break;
4344     if (isSigned) continue;
4345
4346     // If the target supports UINT_TO_FP of this type, use it.
4347     switch (TLI.getOperationAction(ISD::UINT_TO_FP, NewInTy)) {
4348       default: break;
4349       case TargetLowering::Legal:
4350         if (!TLI.isTypeLegal(NewInTy))
4351           break;  // Can't use this datatype.
4352         // FALL THROUGH.
4353       case TargetLowering::Custom:
4354         OpToUse = ISD::UINT_TO_FP;
4355         break;
4356     }
4357     if (OpToUse) break;
4358
4359     // Otherwise, try a larger type.
4360   }
4361
4362   // Okay, we found the operation and type to use.  Zero extend our input to the
4363   // desired type then run the operation on it.
4364   return DAG.getNode(OpToUse, dl, DestVT,
4365                      DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND,
4366                                  dl, NewInTy, LegalOp));
4367 }
4368
4369 /// PromoteLegalFP_TO_INT - This function is responsible for legalizing a
4370 /// FP_TO_*INT operation of the specified operand when the target requests that
4371 /// we promote it.  At this point, we know that the result and operand types are
4372 /// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT
4373 /// operation that returns a larger result.
4374 SDValue SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDValue LegalOp,
4375                                                     MVT DestVT,
4376                                                     bool isSigned,
4377                                                     DebugLoc dl) {
4378   // First step, figure out the appropriate FP_TO*INT operation to use.
4379   MVT NewOutTy = DestVT;
4380
4381   unsigned OpToUse = 0;
4382
4383   // Scan for the appropriate larger type to use.
4384   while (1) {
4385     NewOutTy = (MVT::SimpleValueType)(NewOutTy.getSimpleVT()+1);
4386     assert(NewOutTy.isInteger() && "Ran out of possibilities!");
4387
4388     // If the target supports FP_TO_SINT returning this type, use it.
4389     switch (TLI.getOperationAction(ISD::FP_TO_SINT, NewOutTy)) {
4390     default: break;
4391     case TargetLowering::Legal:
4392       if (!TLI.isTypeLegal(NewOutTy))
4393         break;  // Can't use this datatype.
4394       // FALL THROUGH.
4395     case TargetLowering::Custom:
4396       OpToUse = ISD::FP_TO_SINT;
4397       break;
4398     }
4399     if (OpToUse) break;
4400
4401     // If the target supports FP_TO_UINT of this type, use it.
4402     switch (TLI.getOperationAction(ISD::FP_TO_UINT, NewOutTy)) {
4403     default: break;
4404     case TargetLowering::Legal:
4405       if (!TLI.isTypeLegal(NewOutTy))
4406         break;  // Can't use this datatype.
4407       // FALL THROUGH.
4408     case TargetLowering::Custom:
4409       OpToUse = ISD::FP_TO_UINT;
4410       break;
4411     }
4412     if (OpToUse) break;
4413
4414     // Otherwise, try a larger type.
4415   }
4416
4417
4418   // Okay, we found the operation and type to use.
4419   SDValue Operation = DAG.getNode(OpToUse, dl, NewOutTy, LegalOp);
4420
4421   // If the operation produces an invalid type, it must be custom lowered.  Use
4422   // the target lowering hooks to expand it.  Just keep the low part of the
4423   // expanded operation, we know that we're truncating anyway.
4424   if (getTypeAction(NewOutTy) == Expand) {
4425     SmallVector<SDValue, 2> Results;
4426     TLI.ReplaceNodeResults(Operation.getNode(), Results, DAG);
4427     assert(Results.size() == 1 && "Incorrect FP_TO_XINT lowering!");
4428     Operation = Results[0];
4429   }
4430
4431   // Truncate the result of the extended FP_TO_*INT operation to the desired
4432   // size.
4433   return DAG.getNode(ISD::TRUNCATE, dl, DestVT, Operation);
4434 }
4435
4436 /// ExpandBSWAP - Open code the operations for BSWAP of the specified operation.
4437 ///
4438 SDValue SelectionDAGLegalize::ExpandBSWAP(SDValue Op, DebugLoc dl) {
4439   MVT VT = Op.getValueType();
4440   MVT SHVT = TLI.getShiftAmountTy();
4441   SDValue Tmp1, Tmp2, Tmp3, Tmp4, Tmp5, Tmp6, Tmp7, Tmp8;
4442   switch (VT.getSimpleVT()) {
4443   default: assert(0 && "Unhandled Expand type in BSWAP!"); abort();
4444   case MVT::i16:
4445     Tmp2 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, SHVT));
4446     Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, SHVT));
4447     return DAG.getNode(ISD::OR, dl, VT, Tmp1, Tmp2);
4448   case MVT::i32:
4449     Tmp4 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(24, SHVT));
4450     Tmp3 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, SHVT));
4451     Tmp2 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, SHVT));
4452     Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(24, SHVT));
4453     Tmp3 = DAG.getNode(ISD::AND, dl, VT, Tmp3, DAG.getConstant(0xFF0000, VT));
4454     Tmp2 = DAG.getNode(ISD::AND, dl, VT, Tmp2, DAG.getConstant(0xFF00, VT));
4455     Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp3);
4456     Tmp2 = DAG.getNode(ISD::OR, dl, VT, Tmp2, Tmp1);
4457     return DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp2);
4458   case MVT::i64:
4459     Tmp8 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(56, SHVT));
4460     Tmp7 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(40, SHVT));
4461     Tmp6 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(24, SHVT));
4462     Tmp5 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, SHVT));
4463     Tmp4 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, SHVT));
4464     Tmp3 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(24, SHVT));
4465     Tmp2 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(40, SHVT));
4466     Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(56, SHVT));
4467     Tmp7 = DAG.getNode(ISD::AND, dl, VT, Tmp7, DAG.getConstant(255ULL<<48, VT));
4468     Tmp6 = DAG.getNode(ISD::AND, dl, VT, Tmp6, DAG.getConstant(255ULL<<40, VT));
4469     Tmp5 = DAG.getNode(ISD::AND, dl, VT, Tmp5, DAG.getConstant(255ULL<<32, VT));
4470     Tmp4 = DAG.getNode(ISD::AND, dl, VT, Tmp4, DAG.getConstant(255ULL<<24, VT));
4471     Tmp3 = DAG.getNode(ISD::AND, dl, VT, Tmp3, DAG.getConstant(255ULL<<16, VT));
4472     Tmp2 = DAG.getNode(ISD::AND, dl, VT, Tmp2, DAG.getConstant(255ULL<<8 , VT));
4473     Tmp8 = DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp7);
4474     Tmp6 = DAG.getNode(ISD::OR, dl, VT, Tmp6, Tmp5);
4475     Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp3);
4476     Tmp2 = DAG.getNode(ISD::OR, dl, VT, Tmp2, Tmp1);
4477     Tmp8 = DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp6);
4478     Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp2);
4479     return DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp4);
4480   }
4481 }
4482
4483 /// ExpandBitCount - Expand the specified bitcount instruction into operations.
4484 ///
4485 SDValue SelectionDAGLegalize::ExpandBitCount(unsigned Opc, SDValue Op,
4486                                              DebugLoc dl) {
4487   switch (Opc) {
4488   default: assert(0 && "Cannot expand this yet!");
4489   case ISD::CTPOP: {
4490     static const uint64_t mask[6] = {
4491       0x5555555555555555ULL, 0x3333333333333333ULL,
4492       0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
4493       0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
4494     };
4495     MVT VT = Op.getValueType();
4496     MVT ShVT = TLI.getShiftAmountTy();
4497     unsigned len = VT.getSizeInBits();
4498     for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
4499       //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
4500       unsigned EltSize = VT.isVector() ?
4501         VT.getVectorElementType().getSizeInBits() : len;
4502       SDValue Tmp2 = DAG.getConstant(APInt(EltSize, mask[i]), VT);
4503       SDValue Tmp3 = DAG.getConstant(1ULL << i, ShVT);
4504       Op = DAG.getNode(ISD::ADD, dl, VT,
4505                        DAG.getNode(ISD::AND, dl, VT, Op, Tmp2),
4506                        DAG.getNode(ISD::AND, dl, VT,
4507                                    DAG.getNode(ISD::SRL, dl, VT, Op, Tmp3),
4508                                    Tmp2));
4509     }
4510     return Op;
4511   }
4512   case ISD::CTLZ: {
4513     // for now, we do this:
4514     // x = x | (x >> 1);
4515     // x = x | (x >> 2);
4516     // ...
4517     // x = x | (x >>16);
4518     // x = x | (x >>32); // for 64-bit input
4519     // return popcount(~x);
4520     //
4521     // but see also: http://www.hackersdelight.org/HDcode/nlz.cc
4522     MVT VT = Op.getValueType();
4523     MVT ShVT = TLI.getShiftAmountTy();
4524     unsigned len = VT.getSizeInBits();
4525     for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
4526       SDValue Tmp3 = DAG.getConstant(1ULL << i, ShVT);
4527       Op = DAG.getNode(ISD::OR, dl, VT, Op,
4528                        DAG.getNode(ISD::SRL, dl, VT, Op, Tmp3));
4529     }
4530     Op = DAG.getNOT(dl, Op, VT);
4531     return DAG.getNode(ISD::CTPOP, dl, VT, Op);
4532   }
4533   case ISD::CTTZ: {
4534     // for now, we use: { return popcount(~x & (x - 1)); }
4535     // unless the target has ctlz but not ctpop, in which case we use:
4536     // { return 32 - nlz(~x & (x-1)); }
4537     // see also http://www.hackersdelight.org/HDcode/ntz.cc
4538     MVT VT = Op.getValueType();
4539     SDValue Tmp3 = DAG.getNode(ISD::AND, dl, VT,
4540                                DAG.getNOT(dl, Op, VT),
4541                                DAG.getNode(ISD::SUB, dl, VT, Op,
4542                                            DAG.getConstant(1, VT)));
4543     // If ISD::CTLZ is legal and CTPOP isn't, then do that instead.
4544     if (!TLI.isOperationLegalOrCustom(ISD::CTPOP, VT) &&
4545         TLI.isOperationLegalOrCustom(ISD::CTLZ, VT))
4546       return DAG.getNode(ISD::SUB, dl, VT,
4547                          DAG.getConstant(VT.getSizeInBits(), VT),
4548                          DAG.getNode(ISD::CTLZ, dl, VT, Tmp3));
4549     return DAG.getNode(ISD::CTPOP, dl, VT, Tmp3);
4550   }
4551   }
4552 }
4553
4554 // SelectionDAG::Legalize - This is the entry point for the file.
4555 //
4556 void SelectionDAG::Legalize(bool TypesNeedLegalizing,
4557                             CodeGenOpt::Level OptLevel) {
4558   /// run - This is the main entry point to this class.
4559   ///
4560   SelectionDAGLegalize(*this, OptLevel).LegalizeDAG();
4561 }
4562