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