lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

   1 //===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the SelectionDAG::Legalize method.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/SelectionDAG.h"
  15 #include "llvm/CodeGen/MachineFunction.h"
  16 #include "llvm/CodeGen/MachineFrameInfo.h"
  17 #include "llvm/Target/TargetLowering.h"
  18 #include "llvm/Target/TargetData.h"
  19 #include "llvm/Target/TargetOptions.h"
  20 #include "llvm/CallingConv.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/Support/MathExtras.h"
  23 #include "llvm/Support/CommandLine.h"
  24 #include <iostream>
  25 #include <map>
  26 using namespace llvm;
  27
  28 #ifndef NDEBUG
  29 static cl::opt<bool>
  30 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
  31                  cl::desc("Pop up a window to show dags before legalize"));
  32 #else
  33 static const bool ViewLegalizeDAGs = 0;
  34 #endif
  35
  36 //===----------------------------------------------------------------------===//
  37 /// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and
  38 /// hacks on it until the target machine can handle it.  This involves
  39 /// eliminating value sizes the machine cannot handle (promoting small sizes to
  40 /// large sizes or splitting up large values into small values) as well as
  41 /// eliminating operations the machine cannot handle.
  42 ///
  43 /// This code also does a small amount of optimization and recognition of idioms
  44 /// as part of its processing.  For example, if a target does not support a
  45 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
  46 /// will attempt merge setcc and brc instructions into brcc's.
  47 ///
  48 namespace {
  49 class SelectionDAGLegalize {
  50   TargetLowering &TLI;
  51   SelectionDAG &DAG;
  52
  53   // Libcall insertion helpers.
  54
  55   /// LastCALLSEQ_END - This keeps track of the CALLSEQ_END node that has been
  56   /// legalized.  We use this to ensure that calls are properly serialized
  57   /// against each other, including inserted libcalls.
  58   SDOperand LastCALLSEQ_END;
  59
  60   /// IsLegalizingCall - This member is used *only* for purposes of providing
  61   /// helpful assertions that a libcall isn't created while another call is
  62   /// being legalized (which could lead to non-serialized call sequences).
  63   bool IsLegalizingCall;
  64
  65   enum LegalizeAction {
  66     Legal,      // The target natively supports this operation.
  67     Promote,    // This operation should be executed in a larger type.
  68     Expand,     // Try to expand this to other ops, otherwise use a libcall.
  69   };
  70
  71   /// ValueTypeActions - This is a bitvector that contains two bits for each
  72   /// value type, where the two bits correspond to the LegalizeAction enum.
  73   /// This can be queried with "getTypeAction(VT)".
  74   TargetLowering::ValueTypeActionImpl ValueTypeActions;
  75
  76   /// LegalizedNodes - For nodes that are of legal width, and that have more
  77   /// than one use, this map indicates what regularized operand to use.  This
  78   /// allows us to avoid legalizing the same thing more than once.
  79   std::map<SDOperand, SDOperand> LegalizedNodes;
  80
  81   /// PromotedNodes - For nodes that are below legal width, and that have more
  82   /// than one use, this map indicates what promoted value to use.  This allows
  83   /// us to avoid promoting the same thing more than once.
  84   std::map<SDOperand, SDOperand> PromotedNodes;
  85
  86   /// ExpandedNodes - For nodes that need to be expanded this map indicates
  87   /// which which operands are the expanded version of the input.  This allows
  88   /// us to avoid expanding the same node more than once.
  89   std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
  90
  91   /// SplitNodes - For vector nodes that need to be split, this map indicates
  92   /// which which operands are the split version of the input.  This allows us
  93   /// to avoid splitting the same node more than once.
  94   std::map<SDOperand, std::pair<SDOperand, SDOperand> > SplitNodes;
  95
  96   /// PackedNodes - For nodes that need to be packed from MVT::Vector types to
  97   /// concrete packed types, this contains the mapping of ones we have already
  98   /// processed to the result.
  99   std::map<SDOperand, SDOperand> PackedNodes;
 100
 101   void AddLegalizedOperand(SDOperand From, SDOperand To) {
 102     LegalizedNodes.insert(std::make_pair(From, To));
 103     // If someone requests legalization of the new node, return itself.
 104     if (From != To)
 105       LegalizedNodes.insert(std::make_pair(To, To));
 106   }
 107   void AddPromotedOperand(SDOperand From, SDOperand To) {
 108     bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second;
 109     assert(isNew && "Got into the map somehow?");
 110     // If someone requests legalization of the new node, return itself.
 111     LegalizedNodes.insert(std::make_pair(To, To));
 112   }
 113
 114 public:
 115
 116   SelectionDAGLegalize(SelectionDAG &DAG);
 117
 118   /// getTypeAction - Return how we should legalize values of this type, either
 119   /// it is already legal or we need to expand it into multiple registers of
 120   /// smaller integer type, or we need to promote it to a larger type.
 121   LegalizeAction getTypeAction(MVT::ValueType VT) const {
 122     return (LegalizeAction)ValueTypeActions.getTypeAction(VT);
 123   }
 124
 125   /// isTypeLegal - Return true if this type is legal on this target.
 126   ///
 127   bool isTypeLegal(MVT::ValueType VT) const {
 128     return getTypeAction(VT) == Legal;
 129   }
 130
 131   void LegalizeDAG();
 132
 133 private:
 134   /// HandleOp - Legalize, Promote, Expand or Pack the specified operand as
 135   /// appropriate for its type.
 136   void HandleOp(SDOperand Op);
 137
 138   /// LegalizeOp - We know that the specified value has a legal type.
 139   /// Recursively ensure that the operands have legal types, then return the
 140   /// result.
 141   SDOperand LegalizeOp(SDOperand O);
 142
 143   /// PromoteOp - Given an operation that produces a value in an invalid type,
 144   /// promote it to compute the value into a larger type.  The produced value
 145   /// will have the correct bits for the low portion of the register, but no
 146   /// guarantee is made about the top bits: it may be zero, sign-extended, or
 147   /// garbage.
 148   SDOperand PromoteOp(SDOperand O);
 149
 150   /// ExpandOp - Expand the specified SDOperand into its two component pieces
 151   /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this,
 152   /// the LegalizeNodes map is filled in for any results that are not expanded,
 153   /// the ExpandedNodes map is filled in for any results that are expanded, and
 154   /// the Lo/Hi values are returned.   This applies to integer types and Vector
 155   /// types.
 156   void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
 157
 158   /// SplitVectorOp - Given an operand of MVT::Vector type, break it down into
 159   /// two smaller values of MVT::Vector type.
 160   void SplitVectorOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
 161
 162   /// PackVectorOp - Given an operand of MVT::Vector type, convert it into the
 163   /// equivalent operation that returns a packed value (e.g. MVT::V4F32).  When
 164   /// this is called, we know that PackedVT is the right type for the result and
 165   /// we know that this type is legal for the target.
 166   SDOperand PackVectorOp(SDOperand O, MVT::ValueType PackedVT);
 167
 168   bool LegalizeAllNodesNotLeadingTo(SDNode *N, SDNode *Dest);
 169
 170   void LegalizeSetCCOperands(SDOperand &LHS, SDOperand &RHS, SDOperand &CC);
 171
 172   SDOperand CreateStackTemporary(MVT::ValueType VT);
 173
 174   SDOperand ExpandLibCall(const char *Name, SDNode *Node,
 175                           SDOperand &Hi);
 176   SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy,
 177                           SDOperand Source);
 178
 179   SDOperand ExpandBIT_CONVERT(MVT::ValueType DestVT, SDOperand SrcOp);
 180   SDOperand ExpandBUILD_VECTOR(SDNode *Node);
 181   SDOperand ExpandLegalINT_TO_FP(bool isSigned,
 182                                  SDOperand LegalOp,
 183                                  MVT::ValueType DestVT);
 184   SDOperand PromoteLegalINT_TO_FP(SDOperand LegalOp, MVT::ValueType DestVT,
 185                                   bool isSigned);
 186   SDOperand PromoteLegalFP_TO_INT(SDOperand LegalOp, MVT::ValueType DestVT,
 187                                   bool isSigned);
 188
 189   SDOperand ExpandBSWAP(SDOperand Op);
 190   SDOperand ExpandBitCount(unsigned Opc, SDOperand Op);
 191   bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt,
 192                    SDOperand &Lo, SDOperand &Hi);
 193   void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt,
 194                         SDOperand &Lo, SDOperand &Hi);
 195
 196   SDOperand LowerVEXTRACT_VECTOR_ELT(SDOperand Op);
 197
 198   SDOperand getIntPtrConstant(uint64_t Val) {
 199     return DAG.getConstant(Val, TLI.getPointerTy());
 200   }
 201 };
 202 }
 203
 204 /// getScalarizedOpcode - Return the scalar opcode that corresponds to the
 205 /// specified vector opcode.
 206 static unsigned getScalarizedOpcode(unsigned VecOp, MVT::ValueType VT) {
 207   switch (VecOp) {
 208   default: assert(0 && "Don't know how to scalarize this opcode!");
 209   case ISD::VADD:  return MVT::isInteger(VT) ? ISD::ADD : ISD::FADD;
 210   case ISD::VSUB:  return MVT::isInteger(VT) ? ISD::SUB : ISD::FSUB;
 211   case ISD::VMUL:  return MVT::isInteger(VT) ? ISD::MUL : ISD::FMUL;
 212   case ISD::VSDIV: return MVT::isInteger(VT) ? ISD::SDIV: ISD::FDIV;
 213   case ISD::VUDIV: return MVT::isInteger(VT) ? ISD::UDIV: ISD::FDIV;
 214   case ISD::VAND:  return MVT::isInteger(VT) ? ISD::AND : 0;
 215   case ISD::VOR:   return MVT::isInteger(VT) ? ISD::OR  : 0;
 216   case ISD::VXOR:  return MVT::isInteger(VT) ? ISD::XOR : 0;
 217   }
 218 }
 219
 220 SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag)
 221   : TLI(dag.getTargetLoweringInfo()), DAG(dag),
 222     ValueTypeActions(TLI.getValueTypeActions()) {
 223   assert(MVT::LAST_VALUETYPE <= 32 &&
 224          "Too many value types for ValueTypeActions to hold!");
 225 }
 226
 227 /// ComputeTopDownOrdering - Add the specified node to the Order list if it has
 228 /// not been visited yet and if all of its operands have already been visited.
 229 static void ComputeTopDownOrdering(SDNode *N, std::vector<SDNode*> &Order,
 230                                    std::map<SDNode*, unsigned> &Visited) {
 231   if (++Visited[N] != N->getNumOperands())
 232     return;  // Haven't visited all operands yet
 233
 234   Order.push_back(N);
 235
 236   if (N->hasOneUse()) { // Tail recurse in common case.
 237     ComputeTopDownOrdering(*N->use_begin(), Order, Visited);
 238     return;
 239   }
 240
 241   // Now that we have N in, add anything that uses it if all of their operands
 242   // are now done.
 243   for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); UI != E;++UI)
 244     ComputeTopDownOrdering(*UI, Order, Visited);
 245 }
 246
 247
 248 void SelectionDAGLegalize::LegalizeDAG() {
 249   LastCALLSEQ_END = DAG.getEntryNode();
 250   IsLegalizingCall = false;
 251
 252   // The legalize process is inherently a bottom-up recursive process (users
 253   // legalize their uses before themselves).  Given infinite stack space, we
 254   // could just start legalizing on the root and traverse the whole graph.  In
 255   // practice however, this causes us to run out of stack space on large basic
 256   // blocks.  To avoid this problem, compute an ordering of the nodes where each
 257   // node is only legalized after all of its operands are legalized.
 258   std::map<SDNode*, unsigned> Visited;
 259   std::vector<SDNode*> Order;
 260
 261   // Compute ordering from all of the leaves in the graphs, those (like the
 262   // entry node) that have no operands.
 263   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 264        E = DAG.allnodes_end(); I != E; ++I) {
 265     if (I->getNumOperands() == 0) {
 266       Visited[I] = 0 - 1U;
 267       ComputeTopDownOrdering(I, Order, Visited);
 268     }
 269   }
 270
 271   assert(Order.size() == Visited.size() &&
 272          Order.size() ==
 273             (unsigned)std::distance(DAG.allnodes_begin(), DAG.allnodes_end()) &&
 274          "Error: DAG is cyclic!");
 275   Visited.clear();
 276
 277   for (unsigned i = 0, e = Order.size(); i != e; ++i)
 278     HandleOp(SDOperand(Order[i], 0));
 279
 280   // Finally, it's possible the root changed.  Get the new root.
 281   SDOperand OldRoot = DAG.getRoot();
 282   assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?");
 283   DAG.setRoot(LegalizedNodes[OldRoot]);
 284
 285   ExpandedNodes.clear();
 286   LegalizedNodes.clear();
 287   PromotedNodes.clear();
 288   SplitNodes.clear();
 289   PackedNodes.clear();
 290
 291   // Remove dead nodes now.
 292   DAG.RemoveDeadNodes(OldRoot.Val);
 293 }
 294
 295
 296 /// FindCallEndFromCallStart - Given a chained node that is part of a call
 297 /// sequence, find the CALLSEQ_END node that terminates the call sequence.
 298 static SDNode *FindCallEndFromCallStart(SDNode *Node) {
 299   if (Node->getOpcode() == ISD::CALLSEQ_END)
 300     return Node;
 301   if (Node->use_empty())
 302     return 0;   // No CallSeqEnd
 303
 304   // The chain is usually at the end.
 305   SDOperand TheChain(Node, Node->getNumValues()-1);
 306   if (TheChain.getValueType() != MVT::Other) {
 307     // Sometimes it's at the beginning.
 308     TheChain = SDOperand(Node, 0);
 309     if (TheChain.getValueType() != MVT::Other) {
 310       // Otherwise, hunt for it.
 311       for (unsigned i = 1, e = Node->getNumValues(); i != e; ++i)
 312         if (Node->getValueType(i) == MVT::Other) {
 313           TheChain = SDOperand(Node, i);
 314           break;
 315         }
 316
 317       // Otherwise, we walked into a node without a chain.
 318       if (TheChain.getValueType() != MVT::Other)
 319         return 0;
 320     }
 321   }
 322
 323   for (SDNode::use_iterator UI = Node->use_begin(),
 324        E = Node->use_end(); UI != E; ++UI) {
 325
 326     // Make sure to only follow users of our token chain.
 327     SDNode *User = *UI;
 328     for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
 329       if (User->getOperand(i) == TheChain)
 330         if (SDNode *Result = FindCallEndFromCallStart(User))
 331           return Result;
 332   }
 333   return 0;
 334 }
 335
 336 /// FindCallStartFromCallEnd - Given a chained node that is part of a call
 337 /// sequence, find the CALLSEQ_START node that initiates the call sequence.
 338 static SDNode *FindCallStartFromCallEnd(SDNode *Node) {
 339   assert(Node && "Didn't find callseq_start for a call??");
 340   if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
 341
 342   assert(Node->getOperand(0).getValueType() == MVT::Other &&
 343          "Node doesn't have a token chain argument!");
 344   return FindCallStartFromCallEnd(Node->getOperand(0).Val);
 345 }
 346
 347 /// LegalizeAllNodesNotLeadingTo - Recursively walk the uses of N, looking to
 348 /// see if any uses can reach Dest.  If no dest operands can get to dest,
 349 /// legalize them, legalize ourself, and return false, otherwise, return true.
 350 bool SelectionDAGLegalize::LegalizeAllNodesNotLeadingTo(SDNode *N,
 351                                                         SDNode *Dest) {
 352   if (N == Dest) return true;  // N certainly leads to Dest :)
 353
 354   // If the first result of this node has been already legalized, then it cannot
 355   // reach N.
 356   switch (getTypeAction(N->getValueType(0))) {
 357   case Legal:
 358     if (LegalizedNodes.count(SDOperand(N, 0))) return false;
 359     break;
 360   case Promote:
 361     if (PromotedNodes.count(SDOperand(N, 0))) return false;
 362     break;
 363   case Expand:
 364     if (ExpandedNodes.count(SDOperand(N, 0))) return false;
 365     break;
 366   }
 367
 368   // Okay, this node has not already been legalized.  Check and legalize all
 369   // operands.  If none lead to Dest, then we can legalize this node.
 370   bool OperandsLeadToDest = false;
 371   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 372     OperandsLeadToDest |=     // If an operand leads to Dest, so do we.
 373       LegalizeAllNodesNotLeadingTo(N->getOperand(i).Val, Dest);
 374
 375   if (OperandsLeadToDest) return true;
 376
 377   // Okay, this node looks safe, legalize it and return false.
 378   switch (getTypeAction(N->getValueType(0))) {
 379   case Legal:
 380     LegalizeOp(SDOperand(N, 0));
 381     break;
 382   case Promote:
 383     PromoteOp(SDOperand(N, 0));
 384     break;
 385   case Expand: {
 386     SDOperand X, Y;
 387     ExpandOp(SDOperand(N, 0), X, Y);
 388     break;
 389   }
 390   }
 391   return false;
 392 }
 393
 394 /// HandleOp - Legalize, Promote, Expand or Pack the specified operand as
 395 /// appropriate for its type.
 396 void SelectionDAGLegalize::HandleOp(SDOperand Op) {
 397   switch (getTypeAction(Op.getValueType())) {
 398   default: assert(0 && "Bad type action!");
 399   case Legal:   LegalizeOp(Op); break;
 400   case Promote: PromoteOp(Op);  break;
 401   case Expand:
 402     if (Op.getValueType() != MVT::Vector) {
 403       SDOperand X, Y;
 404       ExpandOp(Op, X, Y);
 405     } else {
 406       SDNode *N = Op.Val;
 407       unsigned NumOps = N->getNumOperands();
 408       unsigned NumElements =
 409         cast<ConstantSDNode>(N->getOperand(NumOps-2))->getValue();
 410       MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(NumOps-1))->getVT();
 411       MVT::ValueType PackedVT = getVectorType(EVT, NumElements);
 412       if (PackedVT != MVT::Other && TLI.isTypeLegal(PackedVT)) {
 413         // In the common case, this is a legal vector type, convert it to the
 414         // packed operation and type now.
 415         PackVectorOp(Op, PackedVT);
 416       } else if (NumElements == 1) {
 417         // Otherwise, if this is a single element vector, convert it to a
 418         // scalar operation.
 419         PackVectorOp(Op, EVT);
 420       } else {
 421         // Otherwise, this is a multiple element vector that isn't supported.
 422         // Split it in half and legalize both parts.
 423         SDOperand X, Y;
 424         SplitVectorOp(Op, X, Y);
 425       }
 426     }
 427     break;
 428   }
 429 }
 430
 431
 432 /// LegalizeOp - We know that the specified value has a legal type.
 433 /// Recursively ensure that the operands have legal types, then return the
 434 /// result.
 435 SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 436   assert(isTypeLegal(Op.getValueType()) &&
 437          "Caller should expand or promote operands that are not legal!");
 438   SDNode *Node = Op.Val;
 439
 440   // If this operation defines any values that cannot be represented in a
 441   // register on this target, make sure to expand or promote them.
 442   if (Node->getNumValues() > 1) {
 443     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 444       if (getTypeAction(Node->getValueType(i)) != Legal) {
 445         HandleOp(Op.getValue(i));
 446         assert(LegalizedNodes.count(Op) &&
 447                "Handling didn't add legal operands!");
 448         return LegalizedNodes[Op];
 449       }
 450   }
 451
 452   // Note that LegalizeOp may be reentered even from single-use nodes, which
 453   // means that we always must cache transformed nodes.
 454   std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
 455   if (I != LegalizedNodes.end()) return I->second;
 456
 457   SDOperand Tmp1, Tmp2, Tmp3, Tmp4;
 458   SDOperand Result = Op;
 459   bool isCustom = false;
 460
 461   switch (Node->getOpcode()) {
 462   case ISD::FrameIndex:
 463   case ISD::EntryToken:
 464   case ISD::Register:
 465   case ISD::BasicBlock:
 466   case ISD::TargetFrameIndex:
 467   case ISD::TargetConstant:
 468   case ISD::TargetConstantFP:
 469   case ISD::TargetConstantPool:
 470   case ISD::TargetGlobalAddress:
 471   case ISD::TargetExternalSymbol:
 472   case ISD::VALUETYPE:
 473   case ISD::SRCVALUE:
 474   case ISD::STRING:
 475   case ISD::CONDCODE:
 476     // Primitives must all be legal.
 477     assert(TLI.isOperationLegal(Node->getValueType(0), Node->getValueType(0)) &&
 478            "This must be legal!");
 479     break;
 480   default:
 481     if (Node->getOpcode() >= ISD::BUILTIN_OP_END) {
 482       // If this is a target node, legalize it by legalizing the operands then
 483       // passing it through.
 484       std::vector<SDOperand> Ops;
 485       bool Changed = false;
 486       for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
 487         Ops.push_back(LegalizeOp(Node->getOperand(i)));
 488         Changed = Changed || Node->getOperand(i) != Ops.back();
 489       }
 490       if (Changed)
 491         if (Node->getNumValues() == 1)
 492           Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops);
 493         else {
 494           std::vector<MVT::ValueType> VTs(Node->value_begin(),
 495                                           Node->value_end());
 496           Result = DAG.getNode(Node->getOpcode(), VTs, Ops);
 497         }
 498
 499       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 500         AddLegalizedOperand(Op.getValue(i), Result.getValue(i));
 501       return Result.getValue(Op.ResNo);
 502     }
 503     // Otherwise this is an unhandled builtin node.  splat.
 504     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 505     assert(0 && "Do not know how to legalize this operator!");
 506     abort();
 507   case ISD::GlobalAddress:
 508   case ISD::ExternalSymbol:
 509   case ISD::ConstantPool:           // Nothing to do.
 510     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
 511     default: assert(0 && "This action is not supported yet!");
 512     case TargetLowering::Custom:
 513       Tmp1 = TLI.LowerOperation(Op, DAG);
 514       if (Tmp1.Val) Result = Tmp1;
 515       // FALLTHROUGH if the target doesn't want to lower this op after all.
 516     case TargetLowering::Legal:
 517       break;
 518     }
 519     break;
 520   case ISD::AssertSext:
 521   case ISD::AssertZext:
 522     Tmp1 = LegalizeOp(Node->getOperand(0));
 523     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
 524     break;
 525   case ISD::MERGE_VALUES:
 526     // Legalize eliminates MERGE_VALUES nodes.
 527     Result = Node->getOperand(Op.ResNo);
 528     break;
 529   case ISD::CopyFromReg:
 530     Tmp1 = LegalizeOp(Node->getOperand(0));
 531     Result = Op.getValue(0);
 532     if (Node->getNumValues() == 2) {
 533       Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
 534     } else {
 535       assert(Node->getNumValues() == 3 && "Invalid copyfromreg!");
 536       if (Node->getNumOperands() == 3) {
 537         Tmp2 = LegalizeOp(Node->getOperand(2));
 538         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1),Tmp2);
 539       } else {
 540         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
 541       }
 542       AddLegalizedOperand(Op.getValue(2), Result.getValue(2));
 543     }
 544     // Since CopyFromReg produces two values, make sure to remember that we
 545     // legalized both of them.
 546     AddLegalizedOperand(Op.getValue(0), Result);
 547     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
 548     return Result.getValue(Op.ResNo);
 549   case ISD::UNDEF: {
 550     MVT::ValueType VT = Op.getValueType();
 551     switch (TLI.getOperationAction(ISD::UNDEF, VT)) {
 552     default: assert(0 && "This action is not supported yet!");
 553     case TargetLowering::Expand:
 554       if (MVT::isInteger(VT))
 555         Result = DAG.getConstant(0, VT);
 556       else if (MVT::isFloatingPoint(VT))
 557         Result = DAG.getConstantFP(0, VT);
 558       else
 559         assert(0 && "Unknown value type!");
 560       break;
 561     case TargetLowering::Legal:
 562       break;
 563     }
 564     break;
 565   }
 566
 567   case ISD::INTRINSIC_W_CHAIN:
 568   case ISD::INTRINSIC_WO_CHAIN:
 569   case ISD::INTRINSIC_VOID: {
 570     std::vector<SDOperand> Ops;
 571     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 572       Ops.push_back(LegalizeOp(Node->getOperand(i)));
 573     Result = DAG.UpdateNodeOperands(Result, Ops);
 574
 575     // Allow the target to custom lower its intrinsics if it wants to.
 576     if (TLI.getOperationAction(Node->getOpcode(), MVT::Other) ==
 577         TargetLowering::Custom) {
 578       Tmp3 = TLI.LowerOperation(Result, DAG);
 579       if (Tmp3.Val) Result = Tmp3;
 580     }
 581
 582     if (Result.Val->getNumValues() == 1) break;
 583
 584     // Must have return value and chain result.
 585     assert(Result.Val->getNumValues() == 2 &&
 586            "Cannot return more than two values!");
 587
 588     // Since loads produce two values, make sure to remember that we
 589     // legalized both of them.
 590     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
 591     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 592     return Result.getValue(Op.ResNo);
 593   }
 594
 595   case ISD::LOCATION:
 596     assert(Node->getNumOperands() == 5 && "Invalid LOCATION node!");
 597     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the input chain.
 598
 599     switch (TLI.getOperationAction(ISD::LOCATION, MVT::Other)) {
 600     case TargetLowering::Promote:
 601     default: assert(0 && "This action is not supported yet!");
 602     case TargetLowering::Expand: {
 603       MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo();
 604       bool useDEBUG_LOC = TLI.isOperationLegal(ISD::DEBUG_LOC, MVT::Other);
 605       bool useDEBUG_LABEL = TLI.isOperationLegal(ISD::DEBUG_LABEL, MVT::Other);
 606
 607       if (DebugInfo && (useDEBUG_LOC || useDEBUG_LABEL)) {
 608         const std::string &FName =
 609           cast<StringSDNode>(Node->getOperand(3))->getValue();
 610         const std::string &DirName =
 611           cast<StringSDNode>(Node->getOperand(4))->getValue();
 612         unsigned SrcFile = DebugInfo->RecordSource(DirName, FName);
 613
 614         std::vector<SDOperand> Ops;
 615         Ops.push_back(Tmp1);  // chain
 616         SDOperand LineOp = Node->getOperand(1);
 617         SDOperand ColOp = Node->getOperand(2);
 618
 619         if (useDEBUG_LOC) {
 620           Ops.push_back(LineOp);  // line #
 621           Ops.push_back(ColOp);  // col #
 622           Ops.push_back(DAG.getConstant(SrcFile, MVT::i32));  // source file id
 623           Result = DAG.getNode(ISD::DEBUG_LOC, MVT::Other, Ops);
 624         } else {
 625           unsigned Line = cast<ConstantSDNode>(LineOp)->getValue();
 626           unsigned Col = cast<ConstantSDNode>(ColOp)->getValue();
 627           unsigned ID = DebugInfo->RecordLabel(Line, Col, SrcFile);
 628           Ops.push_back(DAG.getConstant(ID, MVT::i32));
 629           Result = DAG.getNode(ISD::DEBUG_LABEL, MVT::Other, Ops);
 630         }
 631       } else {
 632         Result = Tmp1;  // chain
 633       }
 634       break;
 635     }
 636     case TargetLowering::Legal:
 637       if (Tmp1 != Node->getOperand(0) ||
 638           getTypeAction(Node->getOperand(1).getValueType()) == Promote) {
 639         std::vector<SDOperand> Ops;
 640         Ops.push_back(Tmp1);
 641         if (getTypeAction(Node->getOperand(1).getValueType()) == Legal) {
 642           Ops.push_back(Node->getOperand(1));  // line # must be legal.
 643           Ops.push_back(Node->getOperand(2));  // col # must be legal.
 644         } else {
 645           // Otherwise promote them.
 646           Ops.push_back(PromoteOp(Node->getOperand(1)));
 647           Ops.push_back(PromoteOp(Node->getOperand(2)));
 648         }
 649         Ops.push_back(Node->getOperand(3));  // filename must be legal.
 650         Ops.push_back(Node->getOperand(4));  // working dir # must be legal.
 651         Result = DAG.UpdateNodeOperands(Result, Ops);
 652       }
 653       break;
 654     }
 655     break;
 656
 657   case ISD::DEBUG_LOC:
 658     assert(Node->getNumOperands() == 4 && "Invalid DEBUG_LOC node!");
 659     switch (TLI.getOperationAction(ISD::DEBUG_LOC, MVT::Other)) {
 660     default: assert(0 && "This action is not supported yet!");
 661     case TargetLowering::Legal:
 662       Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 663       Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the line #.
 664       Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the col #.
 665       Tmp4 = LegalizeOp(Node->getOperand(3));  // Legalize the source file id.
 666       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4);
 667       break;
 668     }
 669     break;
 670
 671   case ISD::DEBUG_LABEL:
 672     assert(Node->getNumOperands() == 2 && "Invalid DEBUG_LABEL node!");
 673     switch (TLI.getOperationAction(ISD::DEBUG_LABEL, MVT::Other)) {
 674     default: assert(0 && "This action is not supported yet!");
 675     case TargetLowering::Legal:
 676       Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 677       Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the label id.
 678       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
 679       break;
 680     }
 681     break;
 682
 683   case ISD::Constant:
 684     // We know we don't need to expand constants here, constants only have one
 685     // value and we check that it is fine above.
 686
 687     // FIXME: Maybe we should handle things like targets that don't support full
 688     // 32-bit immediates?
 689     break;
 690   case ISD::ConstantFP: {
 691     // Spill FP immediates to the constant pool if the target cannot directly
 692     // codegen them.  Targets often have some immediate values that can be
 693     // efficiently generated into an FP register without a load.  We explicitly
 694     // leave these constants as ConstantFP nodes for the target to deal with.
 695     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
 696
 697     // Check to see if this FP immediate is already legal.
 698     bool isLegal = false;
 699     for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
 700            E = TLI.legal_fpimm_end(); I != E; ++I)
 701       if (CFP->isExactlyValue(*I)) {
 702         isLegal = true;
 703         break;
 704       }
 705
 706     // If this is a legal constant, turn it into a TargetConstantFP node.
 707     if (isLegal) {
 708       Result = DAG.getTargetConstantFP(CFP->getValue(), CFP->getValueType(0));
 709       break;
 710     }
 711
 712     switch (TLI.getOperationAction(ISD::ConstantFP, CFP->getValueType(0))) {
 713     default: assert(0 && "This action is not supported yet!");
 714     case TargetLowering::Custom:
 715       Tmp3 = TLI.LowerOperation(Result, DAG);
 716       if (Tmp3.Val) {
 717         Result = Tmp3;
 718         break;
 719       }
 720       // FALLTHROUGH
 721     case TargetLowering::Expand:
 722       // Otherwise we need to spill the constant to memory.
 723       bool Extend = false;
 724
 725       // If a FP immediate is precise when represented as a float and if the
 726       // target can do an extending load from float to double, we put it into
 727       // the constant pool as a float, even if it's is statically typed as a
 728       // double.
 729       MVT::ValueType VT = CFP->getValueType(0);
 730       bool isDouble = VT == MVT::f64;
 731       ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
 732                                              Type::FloatTy, CFP->getValue());
 733       if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) &&
 734           // Only do this if the target has a native EXTLOAD instruction from
 735           // f32.
 736           TLI.isOperationLegal(ISD::EXTLOAD, MVT::f32)) {
 737         LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
 738         VT = MVT::f32;
 739         Extend = true;
 740       }
 741
 742       SDOperand CPIdx = DAG.getConstantPool(LLVMC, TLI.getPointerTy());
 743       if (Extend) {
 744         Result = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
 745                                 CPIdx, DAG.getSrcValue(NULL), MVT::f32);
 746       } else {
 747         Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx,
 748                              DAG.getSrcValue(NULL));
 749       }
 750     }
 751     break;
 752   }
 753   case ISD::TokenFactor:
 754     if (Node->getNumOperands() == 2) {
 755       Tmp1 = LegalizeOp(Node->getOperand(0));
 756       Tmp2 = LegalizeOp(Node->getOperand(1));
 757       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
 758     } else if (Node->getNumOperands() == 3) {
 759       Tmp1 = LegalizeOp(Node->getOperand(0));
 760       Tmp2 = LegalizeOp(Node->getOperand(1));
 761       Tmp3 = LegalizeOp(Node->getOperand(2));
 762       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
 763     } else {
 764       std::vector<SDOperand> Ops;
 765       // Legalize the operands.
 766       for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 767         Ops.push_back(LegalizeOp(Node->getOperand(i)));
 768       Result = DAG.UpdateNodeOperands(Result, Ops);
 769     }
 770     break;
 771
 772   case ISD::BUILD_VECTOR:
 773     switch (TLI.getOperationAction(ISD::BUILD_VECTOR, Node->getValueType(0))) {
 774     default: assert(0 && "This action is not supported yet!");
 775     case TargetLowering::Custom:
 776       Tmp3 = TLI.LowerOperation(Result, DAG);
 777       if (Tmp3.Val) {
 778         Result = Tmp3;
 779         break;
 780       }
 781       // FALLTHROUGH
 782     case TargetLowering::Expand:
 783       Result = ExpandBUILD_VECTOR(Result.Val);
 784       break;
 785     }
 786     break;
 787   case ISD::INSERT_VECTOR_ELT:
 788     Tmp1 = LegalizeOp(Node->getOperand(0));  // InVec
 789     Tmp2 = LegalizeOp(Node->getOperand(1));  // InVal
 790     Tmp3 = LegalizeOp(Node->getOperand(2));  // InEltNo
 791     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
 792
 793     switch (TLI.getOperationAction(ISD::INSERT_VECTOR_ELT,
 794                                    Node->getValueType(0))) {
 795     default: assert(0 && "This action is not supported yet!");
 796     case TargetLowering::Legal:
 797       break;
 798     case TargetLowering::Custom:
 799       Tmp3 = TLI.LowerOperation(Result, DAG);
 800       if (Tmp3.Val) {
 801         Result = Tmp3;
 802         break;
 803       }
 804       // FALLTHROUGH
 805     case TargetLowering::Expand: {
 806       // If the target doesn't support this, we have to spill the input vector
 807       // to a temporary stack slot, update the element, then reload it.  This is
 808       // badness.  We could also load the value into a vector register (either
 809       // with a "move to register" or "extload into register" instruction, then
 810       // permute it into place, if the idx is a constant and if the idx is
 811       // supported by the target.
 812       SDOperand StackPtr = CreateStackTemporary(Tmp1.getValueType());
 813       // Store the vector.
 814       SDOperand Ch = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
 815                                  Tmp1, StackPtr, DAG.getSrcValue(NULL));
 816
 817       // Truncate or zero extend offset to target pointer type.
 818       MVT::ValueType IntPtr = TLI.getPointerTy();
 819       if (Tmp3.getValueType() > IntPtr)
 820         Tmp3 = DAG.getNode(ISD::TRUNCATE, IntPtr, Tmp3);
 821       else
 822         Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Tmp3);
 823
 824       // Add the offset to the index.
 825       unsigned EltSize = MVT::getSizeInBits(Result.getValueType())/8;
 826       Tmp3 = DAG.getNode(ISD::MUL, Tmp3.getValueType(), Tmp3,
 827                          DAG.getConstant(EltSize, Tmp3.getValueType()));
 828       SDOperand StackPtr2 =
 829         DAG.getNode(ISD::ADD, Tmp3.getValueType(), Tmp3, StackPtr);
 830       // Store the scalar value.
 831       Ch = DAG.getNode(ISD::STORE, MVT::Other, Ch,
 832                        Tmp2, StackPtr2, DAG.getSrcValue(NULL));
 833       // Load the updated vector.
 834       Result = DAG.getLoad(Result.getValueType(), Ch, StackPtr,
 835                            DAG.getSrcValue(NULL));
 836       break;
 837     }
 838     }
 839     break;
 840   case ISD::SCALAR_TO_VECTOR:
 841     Tmp1 = LegalizeOp(Node->getOperand(0));  // InVal
 842     Result = DAG.UpdateNodeOperands(Result, Tmp1);
 843     switch (TLI.getOperationAction(ISD::SCALAR_TO_VECTOR,
 844                                    Node->getValueType(0))) {
 845     default: assert(0 && "This action is not supported yet!");
 846     case TargetLowering::Legal:
 847       break;
 848     case TargetLowering::Custom:
 849       Tmp3 = TLI.LowerOperation(Result, DAG);
 850       if (Tmp3.Val) {
 851         Result = Tmp3;
 852         break;
 853       }
 854       // FALLTHROUGH
 855     case TargetLowering::Expand: {
 856       // If the target doesn't support this, store the value to a temporary
 857       // stack slot, then EXTLOAD the vector back out.
 858       // TODO: If a target doesn't support this, create a stack slot for the
 859       // whole vector, then store into it, then load the whole vector.
 860       SDOperand StackPtr =
 861         CreateStackTemporary(Node->getOperand(0).getValueType());
 862       SDOperand Ch = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
 863                                  Node->getOperand(0), StackPtr,
 864                                  DAG.getSrcValue(NULL));
 865       Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0), Ch, StackPtr,
 866                               DAG.getSrcValue(NULL),
 867                               Node->getOperand(0).getValueType());
 868       break;
 869     }
 870     }
 871     break;
 872   case ISD::VECTOR_SHUFFLE:
 873     assert(TLI.isShuffleLegal(Result.getValueType(), Node->getOperand(2)) &&
 874            "vector shuffle should not be created if not legal!");
 875     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the input vectors,
 876     Tmp2 = LegalizeOp(Node->getOperand(1));   // but not the shuffle mask.
 877     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
 878
 879     // Allow targets to custom lower the SHUFFLEs they support.
 880     if (TLI.getOperationAction(ISD::VECTOR_SHUFFLE, Result.getValueType())
 881         == TargetLowering::Custom) {
 882       Tmp1 = TLI.LowerOperation(Result, DAG);
 883       if (Tmp1.Val) Result = Tmp1;
 884     }
 885     break;
 886
 887   case ISD::EXTRACT_VECTOR_ELT:
 888     Tmp1 = LegalizeOp(Node->getOperand(0));
 889     Tmp2 = LegalizeOp(Node->getOperand(1));
 890     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
 891
 892     switch (TLI.getOperationAction(ISD::EXTRACT_VECTOR_ELT,
 893                                    Tmp1.getValueType())) {
 894     default: assert(0 && "This action is not supported yet!");
 895     case TargetLowering::Legal:
 896       break;
 897     case TargetLowering::Custom:
 898       Tmp3 = TLI.LowerOperation(Result, DAG);
 899       if (Tmp3.Val) {
 900         Result = Tmp3;
 901         break;
 902       }
 903       // FALLTHROUGH
 904     case TargetLowering::Expand: {
 905       // If the target doesn't support this, store the value to a temporary
 906       // stack slot, then LOAD the scalar element back out.
 907       SDOperand StackPtr = CreateStackTemporary(Tmp1.getValueType());
 908       SDOperand Ch = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
 909                                  Tmp1, StackPtr, DAG.getSrcValue(NULL));
 910
 911       // Add the offset to the index.
 912       unsigned EltSize = MVT::getSizeInBits(Result.getValueType())/8;
 913       Tmp2 = DAG.getNode(ISD::MUL, Tmp2.getValueType(), Tmp2,
 914                          DAG.getConstant(EltSize, Tmp2.getValueType()));
 915       StackPtr = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2, StackPtr);
 916
 917       Result = DAG.getLoad(Result.getValueType(), Ch, StackPtr,
 918                               DAG.getSrcValue(NULL));
 919       break;
 920     }
 921     }
 922     break;
 923
 924   case ISD::VEXTRACT_VECTOR_ELT:
 925     Result = LegalizeOp(LowerVEXTRACT_VECTOR_ELT(Op));
 926     break;
 927
 928   case ISD::CALLSEQ_START: {
 929     SDNode *CallEnd = FindCallEndFromCallStart(Node);
 930
 931     // Recursively Legalize all of the inputs of the call end that do not lead
 932     // to this call start.  This ensures that any libcalls that need be inserted
 933     // are inserted *before* the CALLSEQ_START.
 934     for (unsigned i = 0, e = CallEnd->getNumOperands(); i != e; ++i)
 935       LegalizeAllNodesNotLeadingTo(CallEnd->getOperand(i).Val, Node);
 936
 937     // Now that we legalized all of the inputs (which may have inserted
 938     // libcalls) create the new CALLSEQ_START node.
 939     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 940
 941     // Merge in the last call, to ensure that this call start after the last
 942     // call ended.
 943     Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
 944     Tmp1 = LegalizeOp(Tmp1);
 945
 946     // Do not try to legalize the target-specific arguments (#1+).
 947     if (Tmp1 != Node->getOperand(0)) {
 948       std::vector<SDOperand> Ops(Node->op_begin(), Node->op_end());
 949       Ops[0] = Tmp1;
 950       Result = DAG.UpdateNodeOperands(Result, Ops);
 951     }
 952
 953     // Remember that the CALLSEQ_START is legalized.
 954     AddLegalizedOperand(Op.getValue(0), Result);
 955     if (Node->getNumValues() == 2)    // If this has a flag result, remember it.
 956       AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
 957
 958     // Now that the callseq_start and all of the non-call nodes above this call
 959     // sequence have been legalized, legalize the call itself.  During this
 960     // process, no libcalls can/will be inserted, guaranteeing that no calls
 961     // can overlap.
 962     assert(!IsLegalizingCall && "Inconsistent sequentialization of calls!");
 963     SDOperand InCallSEQ = LastCALLSEQ_END;
 964     // Note that we are selecting this call!
 965     LastCALLSEQ_END = SDOperand(CallEnd, 0);
 966     IsLegalizingCall = true;
 967
 968     // Legalize the call, starting from the CALLSEQ_END.
 969     LegalizeOp(LastCALLSEQ_END);
 970     assert(!IsLegalizingCall && "CALLSEQ_END should have cleared this!");
 971     return Result;
 972   }
 973   case ISD::CALLSEQ_END:
 974     // If the CALLSEQ_START node hasn't been legalized first, legalize it.  This
 975     // will cause this node to be legalized as well as handling libcalls right.
 976     if (LastCALLSEQ_END.Val != Node) {
 977       LegalizeOp(SDOperand(FindCallStartFromCallEnd(Node), 0));
 978       std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
 979       assert(I != LegalizedNodes.end() &&
 980              "Legalizing the call start should have legalized this node!");
 981       return I->second;
 982     }
 983
 984     // Otherwise, the call start has been legalized and everything is going
 985     // according to plan.  Just legalize ourselves normally here.
 986     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 987     // Do not try to legalize the target-specific arguments (#1+), except for
 988     // an optional flag input.
 989     if (Node->getOperand(Node->getNumOperands()-1).getValueType() != MVT::Flag){
 990       if (Tmp1 != Node->getOperand(0)) {
 991         std::vector<SDOperand> Ops(Node->op_begin(), Node->op_end());
 992         Ops[0] = Tmp1;
 993         Result = DAG.UpdateNodeOperands(Result, Ops);
 994       }
 995     } else {
 996       Tmp2 = LegalizeOp(Node->getOperand(Node->getNumOperands()-1));
 997       if (Tmp1 != Node->getOperand(0) ||
 998           Tmp2 != Node->getOperand(Node->getNumOperands()-1)) {
 999         std::vector<SDOperand> Ops(Node->op_begin(), Node->op_end());
1000         Ops[0] = Tmp1;
1001         Ops.back() = Tmp2;
1002         Result = DAG.UpdateNodeOperands(Result, Ops);
1003       }
1004     }
1005     assert(IsLegalizingCall && "Call sequence imbalance between start/end?");
1006     // This finishes up call legalization.
1007     IsLegalizingCall = false;
1008
1009     // If the CALLSEQ_END node has a flag, remember that we legalized it.
1010     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1011     if (Node->getNumValues() == 2)
1012       AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1013     return Result.getValue(Op.ResNo);
1014   case ISD::DYNAMIC_STACKALLOC: {
1015     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1016     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
1017     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
1018     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1019
1020     Tmp1 = Result.getValue(0);
1021     Tmp2 = Result.getValue(1);
1022     switch (TLI.getOperationAction(Node->getOpcode(),
1023                                    Node->getValueType(0))) {
1024     default: assert(0 && "This action is not supported yet!");
1025     case TargetLowering::Expand: {
1026       unsigned SPReg = TLI.getStackPointerRegisterToSaveRestore();
1027       assert(SPReg && "Target cannot require DYNAMIC_STACKALLOC expansion and"
1028              " not tell us which reg is the stack pointer!");
1029       SDOperand Chain = Tmp1.getOperand(0);
1030       SDOperand Size  = Tmp2.getOperand(1);
1031       SDOperand SP = DAG.getCopyFromReg(Chain, SPReg, Node->getValueType(0));
1032       Tmp1 = DAG.getNode(ISD::SUB, Node->getValueType(0), SP, Size);    // Value
1033       Tmp2 = DAG.getCopyToReg(SP.getValue(1), SPReg, Tmp1);      // Output chain
1034       Tmp1 = LegalizeOp(Tmp1);
1035       Tmp2 = LegalizeOp(Tmp2);
1036       break;
1037     }
1038     case TargetLowering::Custom:
1039       Tmp3 = TLI.LowerOperation(Tmp1, DAG);
1040       if (Tmp3.Val) {
1041         Tmp1 = LegalizeOp(Tmp3);
1042         Tmp2 = LegalizeOp(Tmp3.getValue(1));
1043       }
1044       break;
1045     case TargetLowering::Legal:
1046       break;
1047     }
1048     // Since this op produce two values, make sure to remember that we
1049     // legalized both of them.
1050     AddLegalizedOperand(SDOperand(Node, 0), Tmp1);
1051     AddLegalizedOperand(SDOperand(Node, 1), Tmp2);
1052     return Op.ResNo ? Tmp2 : Tmp1;
1053   }
1054   case ISD::INLINEASM:
1055     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize Chain.
1056     Tmp2 = Node->getOperand(Node->getNumOperands()-1);
1057     if (Tmp2.getValueType() == MVT::Flag)     // Legalize Flag if it exists.
1058       Tmp2 = Tmp3 = SDOperand(0, 0);
1059     else
1060       Tmp3 = LegalizeOp(Tmp2);
1061
1062     if (Tmp1 != Node->getOperand(0) || Tmp2 != Tmp3) {
1063       std::vector<SDOperand> Ops(Node->op_begin(), Node->op_end());
1064       Ops[0] = Tmp1;
1065       if (Tmp3.Val) Ops.back() = Tmp3;
1066       Result = DAG.UpdateNodeOperands(Result, Ops);
1067     }
1068
1069     // INLINE asm returns a chain and flag, make sure to add both to the map.
1070     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1071     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1072     return Result.getValue(Op.ResNo);
1073   case ISD::BR:
1074     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1075     // Ensure that libcalls are emitted before a branch.
1076     Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1077     Tmp1 = LegalizeOp(Tmp1);
1078     LastCALLSEQ_END = DAG.getEntryNode();
1079
1080     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
1081     break;
1082
1083   case ISD::BRCOND:
1084     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1085     // Ensure that libcalls are emitted before a return.
1086     Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1087     Tmp1 = LegalizeOp(Tmp1);
1088     LastCALLSEQ_END = DAG.getEntryNode();
1089
1090     switch (getTypeAction(Node->getOperand(1).getValueType())) {
1091     case Expand: assert(0 && "It's impossible to expand bools");
1092     case Legal:
1093       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
1094       break;
1095     case Promote:
1096       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
1097       break;
1098     }
1099
1100     // Basic block destination (Op#2) is always legal.
1101     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1102
1103     switch (TLI.getOperationAction(ISD::BRCOND, MVT::Other)) {
1104     default: assert(0 && "This action is not supported yet!");
1105     case TargetLowering::Legal: break;
1106     case TargetLowering::Custom:
1107       Tmp1 = TLI.LowerOperation(Result, DAG);
1108       if (Tmp1.Val) Result = Tmp1;
1109       break;
1110     case TargetLowering::Expand:
1111       // Expand brcond's setcc into its constituent parts and create a BR_CC
1112       // Node.
1113       if (Tmp2.getOpcode() == ISD::SETCC) {
1114         Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Tmp2.getOperand(2),
1115                              Tmp2.getOperand(0), Tmp2.getOperand(1),
1116                              Node->getOperand(2));
1117       } else {
1118         // Make sure the condition is either zero or one.  It may have been
1119         // promoted from something else.
1120         unsigned NumBits = MVT::getSizeInBits(Tmp2.getValueType());
1121         if (!TLI.MaskedValueIsZero(Tmp2, (~0ULL >> (64-NumBits))^1))
1122           Tmp2 = DAG.getZeroExtendInReg(Tmp2, MVT::i1);
1123
1124         Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1,
1125                              DAG.getCondCode(ISD::SETNE), Tmp2,
1126                              DAG.getConstant(0, Tmp2.getValueType()),
1127                              Node->getOperand(2));
1128       }
1129       break;
1130     }
1131     break;
1132   case ISD::BR_CC:
1133     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1134     // Ensure that libcalls are emitted before a branch.
1135     Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1136     Tmp1 = LegalizeOp(Tmp1);
1137     LastCALLSEQ_END = DAG.getEntryNode();
1138
1139     Tmp2 = Node->getOperand(2);              // LHS
1140     Tmp3 = Node->getOperand(3);              // RHS
1141     Tmp4 = Node->getOperand(1);              // CC
1142
1143     LegalizeSetCCOperands(Tmp2, Tmp3, Tmp4);
1144
1145     // If we didn't get both a LHS and RHS back from LegalizeSetCCOperands,
1146     // the LHS is a legal SETCC itself.  In this case, we need to compare
1147     // the result against zero to select between true and false values.
1148     if (Tmp3.Val == 0) {
1149       Tmp3 = DAG.getConstant(0, Tmp2.getValueType());
1150       Tmp4 = DAG.getCondCode(ISD::SETNE);
1151     }
1152
1153     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp4, Tmp2, Tmp3,
1154                                     Node->getOperand(4));
1155
1156     switch (TLI.getOperationAction(ISD::BR_CC, Tmp3.getValueType())) {
1157     default: assert(0 && "Unexpected action for BR_CC!");
1158     case TargetLowering::Legal: break;
1159     case TargetLowering::Custom:
1160       Tmp4 = TLI.LowerOperation(Result, DAG);
1161       if (Tmp4.Val) Result = Tmp4;
1162       break;
1163     }
1164     break;
1165   case ISD::LOAD: {
1166     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1167     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1168
1169     MVT::ValueType VT = Node->getValueType(0);
1170     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1171     Tmp2 = Result.getValue(0);
1172     Tmp3 = Result.getValue(1);
1173
1174     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
1175     default: assert(0 && "This action is not supported yet!");
1176     case TargetLowering::Legal: break;
1177     case TargetLowering::Custom:
1178       Tmp1 = TLI.LowerOperation(Tmp2, DAG);
1179       if (Tmp1.Val) {
1180         Tmp2 = LegalizeOp(Tmp1);
1181         Tmp3 = LegalizeOp(Tmp1.getValue(1));
1182       }
1183       break;
1184     }
1185     // Since loads produce two values, make sure to remember that we
1186     // legalized both of them.
1187     AddLegalizedOperand(SDOperand(Node, 0), Tmp2);
1188     AddLegalizedOperand(SDOperand(Node, 1), Tmp3);
1189     return Op.ResNo ? Tmp3 : Tmp2;
1190   }
1191   case ISD::EXTLOAD:
1192   case ISD::SEXTLOAD:
1193   case ISD::ZEXTLOAD: {
1194     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1195     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1196
1197     MVT::ValueType SrcVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
1198     switch (TLI.getOperationAction(Node->getOpcode(), SrcVT)) {
1199     default: assert(0 && "This action is not supported yet!");
1200     case TargetLowering::Promote:
1201       assert(SrcVT == MVT::i1 && "Can only promote EXTLOAD from i1 -> i8!");
1202       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2),
1203                                       DAG.getValueType(MVT::i8));
1204       Tmp1 = Result.getValue(0);
1205       Tmp2 = Result.getValue(1);
1206       break;
1207     case TargetLowering::Custom:
1208       isCustom = true;
1209       // FALLTHROUGH
1210     case TargetLowering::Legal:
1211       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2),
1212                                       Node->getOperand(3));
1213       Tmp1 = Result.getValue(0);
1214       Tmp2 = Result.getValue(1);
1215
1216       if (isCustom) {
1217         Tmp3 = TLI.LowerOperation(Tmp3, DAG);
1218         if (Tmp3.Val) {
1219           Tmp1 = LegalizeOp(Tmp3);
1220           Tmp2 = LegalizeOp(Tmp3.getValue(1));
1221         }
1222       }
1223       break;
1224     case TargetLowering::Expand:
1225       // f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND
1226       if (SrcVT == MVT::f32 && Node->getValueType(0) == MVT::f64) {
1227         SDOperand Load = DAG.getLoad(SrcVT, Tmp1, Tmp2, Node->getOperand(2));
1228         Result = DAG.getNode(ISD::FP_EXTEND, Node->getValueType(0), Load);
1229         Tmp1 = LegalizeOp(Result);  // Relegalize new nodes.
1230         Tmp2 = LegalizeOp(Load.getValue(1));
1231         break;
1232       }
1233       assert(Node->getOpcode() != ISD::EXTLOAD &&
1234              "EXTLOAD should always be supported!");
1235       // Turn the unsupported load into an EXTLOAD followed by an explicit
1236       // zero/sign extend inreg.
1237       Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
1238                               Tmp1, Tmp2, Node->getOperand(2), SrcVT);
1239       SDOperand ValRes;
1240       if (Node->getOpcode() == ISD::SEXTLOAD)
1241         ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1242                              Result, DAG.getValueType(SrcVT));
1243       else
1244         ValRes = DAG.getZeroExtendInReg(Result, SrcVT);
1245       Tmp1 = LegalizeOp(ValRes);  // Relegalize new nodes.
1246       Tmp2 = LegalizeOp(Result.getValue(1));  // Relegalize new nodes.
1247       break;
1248     }
1249     // Since loads produce two values, make sure to remember that we legalized
1250     // both of them.
1251     AddLegalizedOperand(SDOperand(Node, 0), Tmp1);
1252     AddLegalizedOperand(SDOperand(Node, 1), Tmp2);
1253     return Op.ResNo ? Tmp2 : Tmp1;
1254   }
1255   case ISD::EXTRACT_ELEMENT: {
1256     MVT::ValueType OpTy = Node->getOperand(0).getValueType();
1257     switch (getTypeAction(OpTy)) {
1258     default: assert(0 && "EXTRACT_ELEMENT action for type unimplemented!");
1259     case Legal:
1260       if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) {
1261         // 1 -> Hi
1262         Result = DAG.getNode(ISD::SRL, OpTy, Node->getOperand(0),
1263                              DAG.getConstant(MVT::getSizeInBits(OpTy)/2,
1264                                              TLI.getShiftAmountTy()));
1265         Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Result);
1266       } else {
1267         // 0 -> Lo
1268         Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0),
1269                              Node->getOperand(0));
1270       }
1271       break;
1272     case Expand:
1273       // Get both the low and high parts.
1274       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
1275       if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
1276         Result = Tmp2;  // 1 -> Hi
1277       else
1278         Result = Tmp1;  // 0 -> Lo
1279       break;
1280     }
1281     break;
1282   }
1283
1284   case ISD::CopyToReg:
1285     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1286
1287     assert(isTypeLegal(Node->getOperand(2).getValueType()) &&
1288            "Register type must be legal!");
1289     // Legalize the incoming value (must be a legal type).
1290     Tmp2 = LegalizeOp(Node->getOperand(2));
1291     if (Node->getNumValues() == 1) {
1292       Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1), Tmp2);
1293     } else {
1294       assert(Node->getNumValues() == 2 && "Unknown CopyToReg");
1295       if (Node->getNumOperands() == 4) {
1296         Tmp3 = LegalizeOp(Node->getOperand(3));
1297         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1), Tmp2,
1298                                         Tmp3);
1299       } else {
1300         Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1),Tmp2);
1301       }
1302
1303       // Since this produces two values, make sure to remember that we legalized
1304       // both of them.
1305       AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1306       AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1307       return Result;
1308     }
1309     break;
1310
1311   case ISD::RET:
1312     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1313
1314     // Ensure that libcalls are emitted before a return.
1315     Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1316     Tmp1 = LegalizeOp(Tmp1);
1317     LastCALLSEQ_END = DAG.getEntryNode();
1318
1319     switch (Node->getNumOperands()) {
1320     case 2:  // ret val
1321       switch (getTypeAction(Node->getOperand(1).getValueType())) {
1322       case Legal:
1323         Tmp2 = LegalizeOp(Node->getOperand(1));
1324         Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1325         break;
1326       case Expand: {
1327         SDOperand Lo, Hi;
1328         ExpandOp(Node->getOperand(1), Lo, Hi);
1329         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
1330         break;
1331       }
1332       case Promote:
1333         Tmp2 = PromoteOp(Node->getOperand(1));
1334         Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1335         Result = LegalizeOp(Result);
1336         break;
1337       }
1338       break;
1339     case 1:  // ret void
1340       Result = DAG.UpdateNodeOperands(Result, Tmp1);
1341       break;
1342     default: { // ret <values>
1343       std::vector<SDOperand> NewValues;
1344       NewValues.push_back(Tmp1);
1345       for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
1346         switch (getTypeAction(Node->getOperand(i).getValueType())) {
1347         case Legal:
1348           NewValues.push_back(LegalizeOp(Node->getOperand(i)));
1349           break;
1350         case Expand: {
1351           SDOperand Lo, Hi;
1352           ExpandOp(Node->getOperand(i), Lo, Hi);
1353           NewValues.push_back(Lo);
1354           NewValues.push_back(Hi);
1355           break;
1356         }
1357         case Promote:
1358           assert(0 && "Can't promote multiple return value yet!");
1359         }
1360
1361       if (NewValues.size() == Node->getNumOperands())
1362         Result = DAG.UpdateNodeOperands(Result, NewValues);
1363       else
1364         Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
1365       break;
1366     }
1367     }
1368
1369     if (Result.getOpcode() == ISD::RET) {
1370       switch (TLI.getOperationAction(Result.getOpcode(), MVT::Other)) {
1371       default: assert(0 && "This action is not supported yet!");
1372       case TargetLowering::Legal: break;
1373       case TargetLowering::Custom:
1374         Tmp1 = TLI.LowerOperation(Result, DAG);
1375         if (Tmp1.Val) Result = Tmp1;
1376         break;
1377       }
1378     }
1379     break;
1380   case ISD::STORE: {
1381     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1382     Tmp2 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
1383
1384     // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
1385     // FIXME: We shouldn't do this for TargetConstantFP's.
1386     // FIXME: move this to the DAG Combiner!
1387     if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){
1388       if (CFP->getValueType(0) == MVT::f32) {
1389         Tmp3 = DAG.getConstant(FloatToBits(CFP->getValue()), MVT::i32);
1390       } else {
1391         assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
1392         Tmp3 = DAG.getConstant(DoubleToBits(CFP->getValue()), MVT::i64);
1393       }
1394       Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Tmp3, Tmp2,
1395                            Node->getOperand(3));
1396       break;
1397     }
1398
1399     switch (getTypeAction(Node->getOperand(1).getValueType())) {
1400     case Legal: {
1401       Tmp3 = LegalizeOp(Node->getOperand(1));
1402       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
1403                                       Node->getOperand(3));
1404
1405       MVT::ValueType VT = Tmp3.getValueType();
1406       switch (TLI.getOperationAction(ISD::STORE, VT)) {
1407       default: assert(0 && "This action is not supported yet!");
1408       case TargetLowering::Legal:  break;
1409       case TargetLowering::Custom:
1410         Tmp1 = TLI.LowerOperation(Result, DAG);
1411         if (Tmp1.Val) Result = Tmp1;
1412         break;
1413       }
1414       break;
1415     }
1416     case Promote:
1417       // Truncate the value and store the result.
1418       Tmp3 = PromoteOp(Node->getOperand(1));
1419       Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2,
1420                            Node->getOperand(3),
1421                           DAG.getValueType(Node->getOperand(1).getValueType()));
1422       break;
1423
1424     case Expand:
1425       unsigned IncrementSize = 0;
1426       SDOperand Lo, Hi;
1427
1428       // If this is a vector type, then we have to calculate the increment as
1429       // the product of the element size in bytes, and the number of elements
1430       // in the high half of the vector.
1431       if (Node->getOperand(1).getValueType() == MVT::Vector) {
1432         SDNode *InVal = Node->getOperand(1).Val;
1433         unsigned NumElems =
1434           cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
1435         MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
1436
1437         // Figure out if there is a Packed type corresponding to this Vector
1438         // type.  If so, convert to the packed type.
1439         MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
1440         if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
1441           // Turn this into a normal store of the packed type.
1442           Tmp3 = PackVectorOp(Node->getOperand(1), TVT);
1443           Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
1444                                           Node->getOperand(3));
1445           break;
1446         } else if (NumElems == 1) {
1447           // Turn this into a normal store of the scalar type.
1448           Tmp3 = PackVectorOp(Node->getOperand(1), EVT);
1449           Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
1450                                           Node->getOperand(3));
1451           // The scalarized value type may not be legal, e.g. it might require
1452           // promotion or expansion.  Relegalize the scalar store.
1453           Result = LegalizeOp(Result);
1454           break;
1455         } else {
1456           SplitVectorOp(Node->getOperand(1), Lo, Hi);
1457           IncrementSize = NumElems/2 * MVT::getSizeInBits(EVT)/8;
1458         }
1459       } else {
1460         ExpandOp(Node->getOperand(1), Lo, Hi);
1461         IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8;
1462
1463         if (!TLI.isLittleEndian())
1464           std::swap(Lo, Hi);
1465       }
1466
1467       Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2,
1468                        Node->getOperand(3));
1469       Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
1470                          getIntPtrConstant(IncrementSize));
1471       assert(isTypeLegal(Tmp2.getValueType()) &&
1472              "Pointers must be legal!");
1473       // FIXME: This sets the srcvalue of both halves to be the same, which is
1474       // wrong.
1475       Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2,
1476                        Node->getOperand(3));
1477       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1478       break;
1479     }
1480     break;
1481   }
1482   case ISD::PCMARKER:
1483     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1484     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
1485     break;
1486   case ISD::STACKSAVE:
1487     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1488     Result = DAG.UpdateNodeOperands(Result, Tmp1);
1489     Tmp1 = Result.getValue(0);
1490     Tmp2 = Result.getValue(1);
1491
1492     switch (TLI.getOperationAction(ISD::STACKSAVE, MVT::Other)) {
1493     default: assert(0 && "This action is not supported yet!");
1494     case TargetLowering::Legal: break;
1495     case TargetLowering::Custom:
1496       Tmp3 = TLI.LowerOperation(Result, DAG);
1497       if (Tmp3.Val) {
1498         Tmp1 = LegalizeOp(Tmp3);
1499         Tmp2 = LegalizeOp(Tmp3.getValue(1));
1500       }
1501       break;
1502     case TargetLowering::Expand:
1503       // Expand to CopyFromReg if the target set
1504       // StackPointerRegisterToSaveRestore.
1505       if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
1506         Tmp1 = DAG.getCopyFromReg(Result.getOperand(0), SP,
1507                                   Node->getValueType(0));
1508         Tmp2 = Tmp1.getValue(1);
1509       } else {
1510         Tmp1 = DAG.getNode(ISD::UNDEF, Node->getValueType(0));
1511         Tmp2 = Node->getOperand(0);
1512       }
1513       break;
1514     }
1515
1516     // Since stacksave produce two values, make sure to remember that we
1517     // legalized both of them.
1518     AddLegalizedOperand(SDOperand(Node, 0), Tmp1);
1519     AddLegalizedOperand(SDOperand(Node, 1), Tmp2);
1520     return Op.ResNo ? Tmp2 : Tmp1;
1521
1522   case ISD::STACKRESTORE:
1523     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1524     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1525     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1526
1527     switch (TLI.getOperationAction(ISD::STACKRESTORE, MVT::Other)) {
1528     default: assert(0 && "This action is not supported yet!");
1529     case TargetLowering::Legal: break;
1530     case TargetLowering::Custom:
1531       Tmp1 = TLI.LowerOperation(Result, DAG);
1532       if (Tmp1.Val) Result = Tmp1;
1533       break;
1534     case TargetLowering::Expand:
1535       // Expand to CopyToReg if the target set
1536       // StackPointerRegisterToSaveRestore.
1537       if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
1538         Result = DAG.getCopyToReg(Tmp1, SP, Tmp2);
1539       } else {
1540         Result = Tmp1;
1541       }
1542       break;
1543     }
1544     break;
1545
1546   case ISD::READCYCLECOUNTER:
1547     Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain
1548     Result = DAG.UpdateNodeOperands(Result, Tmp1);
1549
1550     // Since rdcc produce two values, make sure to remember that we legalized
1551     // both of them.
1552     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1553     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1554     return Result;
1555
1556   case ISD::TRUNCSTORE: {
1557     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1558     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
1559
1560     assert(isTypeLegal(Node->getOperand(1).getValueType()) &&
1561            "Cannot handle illegal TRUNCSTORE yet!");
1562     Tmp2 = LegalizeOp(Node->getOperand(1));
1563
1564     // The only promote case we handle is TRUNCSTORE:i1 X into
1565     //   -> TRUNCSTORE:i8 (and X, 1)
1566     if (cast<VTSDNode>(Node->getOperand(4))->getVT() == MVT::i1 &&
1567         TLI.getOperationAction(ISD::TRUNCSTORE, MVT::i1) ==
1568               TargetLowering::Promote) {
1569       // Promote the bool to a mask then store.
1570       Tmp2 = DAG.getNode(ISD::AND, Tmp2.getValueType(), Tmp2,
1571                          DAG.getConstant(1, Tmp2.getValueType()));
1572       Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3,
1573                            Node->getOperand(3), DAG.getValueType(MVT::i8));
1574
1575     } else if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1576                Tmp3 != Node->getOperand(2)) {
1577       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3,
1578                                       Node->getOperand(3), Node->getOperand(4));
1579     }
1580
1581     MVT::ValueType StVT = cast<VTSDNode>(Result.Val->getOperand(4))->getVT();
1582     switch (TLI.getOperationAction(Result.Val->getOpcode(), StVT)) {
1583     default: assert(0 && "This action is not supported yet!");
1584     case TargetLowering::Legal: break;
1585     case TargetLowering::Custom:
1586       Tmp1 = TLI.LowerOperation(Result, DAG);
1587       if (Tmp1.Val) Result = Tmp1;
1588       break;
1589     }
1590     break;
1591   }
1592   case ISD::SELECT:
1593     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1594     case Expand: assert(0 && "It's impossible to expand bools");
1595     case Legal:
1596       Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
1597       break;
1598     case Promote:
1599       Tmp1 = PromoteOp(Node->getOperand(0));  // Promote the condition.
1600       break;
1601     }
1602     Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
1603     Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
1604
1605     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1606
1607     switch (TLI.getOperationAction(ISD::SELECT, Tmp2.getValueType())) {
1608     default: assert(0 && "This action is not supported yet!");
1609     case TargetLowering::Legal: break;
1610     case TargetLowering::Custom: {
1611       Tmp1 = TLI.LowerOperation(Result, DAG);
1612       if (Tmp1.Val) Result = Tmp1;
1613       break;
1614     }
1615     case TargetLowering::Expand:
1616       if (Tmp1.getOpcode() == ISD::SETCC) {
1617         Result = DAG.getSelectCC(Tmp1.getOperand(0), Tmp1.getOperand(1),
1618                               Tmp2, Tmp3,
1619                               cast<CondCodeSDNode>(Tmp1.getOperand(2))->get());
1620       } else {
1621         // Make sure the condition is either zero or one.  It may have been
1622         // promoted from something else.
1623         unsigned NumBits = MVT::getSizeInBits(Tmp1.getValueType());
1624         if (!TLI.MaskedValueIsZero(Tmp1, (~0ULL >> (64-NumBits))^1))
1625           Tmp1 = DAG.getZeroExtendInReg(Tmp1, MVT::i1);
1626         Result = DAG.getSelectCC(Tmp1,
1627                                  DAG.getConstant(0, Tmp1.getValueType()),
1628                                  Tmp2, Tmp3, ISD::SETNE);
1629       }
1630       break;
1631     case TargetLowering::Promote: {
1632       MVT::ValueType NVT =
1633         TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType());
1634       unsigned ExtOp, TruncOp;
1635       if (MVT::isInteger(Tmp2.getValueType())) {
1636         ExtOp   = ISD::ANY_EXTEND;
1637         TruncOp = ISD::TRUNCATE;
1638       } else {
1639         ExtOp   = ISD::FP_EXTEND;
1640         TruncOp = ISD::FP_ROUND;
1641       }
1642       // Promote each of the values to the new type.
1643       Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2);
1644       Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3);
1645       // Perform the larger operation, then round down.
1646       Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3);
1647       Result = DAG.getNode(TruncOp, Node->getValueType(0), Result);
1648       break;
1649     }
1650     }
1651     break;
1652   case ISD::SELECT_CC: {
1653     Tmp1 = Node->getOperand(0);               // LHS
1654     Tmp2 = Node->getOperand(1);               // RHS
1655     Tmp3 = LegalizeOp(Node->getOperand(2));   // True
1656     Tmp4 = LegalizeOp(Node->getOperand(3));   // False
1657     SDOperand CC = Node->getOperand(4);
1658
1659     LegalizeSetCCOperands(Tmp1, Tmp2, CC);
1660
1661     // If we didn't get both a LHS and RHS back from LegalizeSetCCOperands,
1662     // the LHS is a legal SETCC itself.  In this case, we need to compare
1663     // the result against zero to select between true and false values.
1664     if (Tmp2.Val == 0) {
1665       Tmp2 = DAG.getConstant(0, Tmp1.getValueType());
1666       CC = DAG.getCondCode(ISD::SETNE);
1667     }
1668     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4, CC);
1669
1670     // Everything is legal, see if we should expand this op or something.
1671     switch (TLI.getOperationAction(ISD::SELECT_CC, Tmp3.getValueType())) {
1672     default: assert(0 && "This action is not supported yet!");
1673     case TargetLowering::Legal: break;
1674     case TargetLowering::Custom:
1675       Tmp1 = TLI.LowerOperation(Result, DAG);
1676       if (Tmp1.Val) Result = Tmp1;
1677       break;
1678     }
1679     break;
1680   }
1681   case ISD::SETCC:
1682     Tmp1 = Node->getOperand(0);
1683     Tmp2 = Node->getOperand(1);
1684     Tmp3 = Node->getOperand(2);
1685     LegalizeSetCCOperands(Tmp1, Tmp2, Tmp3);
1686
1687     // If we had to Expand the SetCC operands into a SELECT node, then it may
1688     // not always be possible to return a true LHS & RHS.  In this case, just
1689     // return the value we legalized, returned in the LHS
1690     if (Tmp2.Val == 0) {
1691       Result = Tmp1;
1692       break;
1693     }
1694
1695     switch (TLI.getOperationAction(ISD::SETCC, Tmp1.getValueType())) {
1696     default: assert(0 && "Cannot handle this action for SETCC yet!");
1697     case TargetLowering::Custom:
1698       isCustom = true;
1699       // FALLTHROUGH.
1700     case TargetLowering::Legal:
1701       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1702       if (isCustom) {
1703         Tmp3 = TLI.LowerOperation(Result, DAG);
1704         if (Tmp3.Val) Result = Tmp3;
1705       }
1706       break;
1707     case TargetLowering::Promote: {
1708       // First step, figure out the appropriate operation to use.
1709       // Allow SETCC to not be supported for all legal data types
1710       // Mostly this targets FP
1711       MVT::ValueType NewInTy = Node->getOperand(0).getValueType();
1712       MVT::ValueType OldVT = NewInTy;
1713
1714       // Scan for the appropriate larger type to use.
1715       while (1) {
1716         NewInTy = (MVT::ValueType)(NewInTy+1);
1717
1718         assert(MVT::isInteger(NewInTy) == MVT::isInteger(OldVT) &&
1719                "Fell off of the edge of the integer world");
1720         assert(MVT::isFloatingPoint(NewInTy) == MVT::isFloatingPoint(OldVT) &&
1721                "Fell off of the edge of the floating point world");
1722
1723         // If the target supports SETCC of this type, use it.
1724         if (TLI.isOperationLegal(ISD::SETCC, NewInTy))
1725           break;
1726       }
1727       if (MVT::isInteger(NewInTy))
1728         assert(0 && "Cannot promote Legal Integer SETCC yet");
1729       else {
1730         Tmp1 = DAG.getNode(ISD::FP_EXTEND, NewInTy, Tmp1);
1731         Tmp2 = DAG.getNode(ISD::FP_EXTEND, NewInTy, Tmp2);
1732       }
1733       Tmp1 = LegalizeOp(Tmp1);
1734       Tmp2 = LegalizeOp(Tmp2);
1735       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1736       Result = LegalizeOp(Result);
1737       break;
1738     }
1739     case TargetLowering::Expand:
1740       // Expand a setcc node into a select_cc of the same condition, lhs, and
1741       // rhs that selects between const 1 (true) and const 0 (false).
1742       MVT::ValueType VT = Node->getValueType(0);
1743       Result = DAG.getNode(ISD::SELECT_CC, VT, Tmp1, Tmp2,
1744                            DAG.getConstant(1, VT), DAG.getConstant(0, VT),
1745                            Node->getOperand(2));
1746       break;
1747     }
1748     break;
1749   case ISD::MEMSET:
1750   case ISD::MEMCPY:
1751   case ISD::MEMMOVE: {
1752     Tmp1 = LegalizeOp(Node->getOperand(0));      // Chain
1753     Tmp2 = LegalizeOp(Node->getOperand(1));      // Pointer
1754
1755     if (Node->getOpcode() == ISD::MEMSET) {      // memset = ubyte
1756       switch (getTypeAction(Node->getOperand(2).getValueType())) {
1757       case Expand: assert(0 && "Cannot expand a byte!");
1758       case Legal:
1759         Tmp3 = LegalizeOp(Node->getOperand(2));
1760         break;
1761       case Promote:
1762         Tmp3 = PromoteOp(Node->getOperand(2));
1763         break;
1764       }
1765     } else {
1766       Tmp3 = LegalizeOp(Node->getOperand(2));    // memcpy/move = pointer,
1767     }
1768
1769     SDOperand Tmp4;
1770     switch (getTypeAction(Node->getOperand(3).getValueType())) {
1771     case Expand: {
1772       // Length is too big, just take the lo-part of the length.
1773       SDOperand HiPart;
1774       ExpandOp(Node->getOperand(3), HiPart, Tmp4);
1775       break;
1776     }
1777     case Legal:
1778       Tmp4 = LegalizeOp(Node->getOperand(3));
1779       break;
1780     case Promote:
1781       Tmp4 = PromoteOp(Node->getOperand(3));
1782       break;
1783     }
1784
1785     SDOperand Tmp5;
1786     switch (getTypeAction(Node->getOperand(4).getValueType())) {  // uint
1787     case Expand: assert(0 && "Cannot expand this yet!");
1788     case Legal:
1789       Tmp5 = LegalizeOp(Node->getOperand(4));
1790       break;
1791     case Promote:
1792       Tmp5 = PromoteOp(Node->getOperand(4));
1793       break;
1794     }
1795
1796     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
1797     default: assert(0 && "This action not implemented for this operation!");
1798     case TargetLowering::Custom:
1799       isCustom = true;
1800       // FALLTHROUGH
1801     case TargetLowering::Legal:
1802       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4, Tmp5);
1803       if (isCustom) {
1804         Tmp1 = TLI.LowerOperation(Result, DAG);
1805         if (Tmp1.Val) Result = Tmp1;
1806       }
1807       break;
1808     case TargetLowering::Expand: {
1809       // Otherwise, the target does not support this operation.  Lower the
1810       // operation to an explicit libcall as appropriate.
1811       MVT::ValueType IntPtr = TLI.getPointerTy();
1812       const Type *IntPtrTy = TLI.getTargetData().getIntPtrType();
1813       std::vector<std::pair<SDOperand, const Type*> > Args;
1814
1815       const char *FnName = 0;
1816       if (Node->getOpcode() == ISD::MEMSET) {
1817         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
1818         // Extend the (previously legalized) ubyte argument to be an int value
1819         // for the call.
1820         if (Tmp3.getValueType() > MVT::i32)
1821           Tmp3 = DAG.getNode(ISD::TRUNCATE, MVT::i32, Tmp3);
1822         else
1823           Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
1824         Args.push_back(std::make_pair(Tmp3, Type::IntTy));
1825         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
1826
1827         FnName = "memset";
1828       } else if (Node->getOpcode() == ISD::MEMCPY ||
1829                  Node->getOpcode() == ISD::MEMMOVE) {
1830         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
1831         Args.push_back(std::make_pair(Tmp3, IntPtrTy));
1832         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
1833         FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
1834       } else {
1835         assert(0 && "Unknown op!");
1836       }
1837
1838       std::pair<SDOperand,SDOperand> CallResult =
1839         TLI.LowerCallTo(Tmp1, Type::VoidTy, false, CallingConv::C, false,
1840                         DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
1841       Result = CallResult.second;
1842       break;
1843     }
1844     }
1845     break;
1846   }
1847
1848   case ISD::SHL_PARTS:
1849   case ISD::SRA_PARTS:
1850   case ISD::SRL_PARTS: {
1851     std::vector<SDOperand> Ops;
1852     bool Changed = false;
1853     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
1854       Ops.push_back(LegalizeOp(Node->getOperand(i)));
1855       Changed |= Ops.back() != Node->getOperand(i);
1856     }
1857     if (Changed)
1858       Result = DAG.UpdateNodeOperands(Result, Ops);
1859
1860     switch (TLI.getOperationAction(Node->getOpcode(),
1861                                    Node->getValueType(0))) {
1862     default: assert(0 && "This action is not supported yet!");
1863     case TargetLowering::Legal: break;
1864     case TargetLowering::Custom:
1865       Tmp1 = TLI.LowerOperation(Result, DAG);
1866       if (Tmp1.Val) {
1867         SDOperand Tmp2, RetVal(0, 0);
1868         for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) {
1869           Tmp2 = LegalizeOp(Tmp1.getValue(i));
1870           AddLegalizedOperand(SDOperand(Node, i), Tmp2);
1871           if (i == Op.ResNo)
1872             RetVal = Tmp2;
1873         }
1874         assert(RetVal.Val && "Illegal result number");
1875         return RetVal;
1876       }
1877       break;
1878     }
1879
1880     // Since these produce multiple values, make sure to remember that we
1881     // legalized all of them.
1882     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
1883       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
1884     return Result.getValue(Op.ResNo);
1885   }
1886
1887     // Binary operators
1888   case ISD::ADD:
1889   case ISD::SUB:
1890   case ISD::MUL:
1891   case ISD::MULHS:
1892   case ISD::MULHU:
1893   case ISD::UDIV:
1894   case ISD::SDIV:
1895   case ISD::AND:
1896   case ISD::OR:
1897   case ISD::XOR:
1898   case ISD::SHL:
1899   case ISD::SRL:
1900   case ISD::SRA:
1901   case ISD::FADD:
1902   case ISD::FSUB:
1903   case ISD::FMUL:
1904   case ISD::FDIV:
1905     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
1906     switch (getTypeAction(Node->getOperand(1).getValueType())) {
1907     case Expand: assert(0 && "Not possible");
1908     case Legal:
1909       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS.
1910       break;
1911     case Promote:
1912       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the RHS.
1913       break;
1914     }
1915
1916     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1917
1918     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1919     default: assert(0 && "Operation not supported");
1920     case TargetLowering::Legal: break;
1921     case TargetLowering::Custom:
1922       Tmp1 = TLI.LowerOperation(Result, DAG);
1923       if (Tmp1.Val) Result = Tmp1;
1924       break;
1925     }
1926     break;
1927
1928   case ISD::FCOPYSIGN:  // FCOPYSIGN does not require LHS/RHS to match type!
1929     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
1930     switch (getTypeAction(Node->getOperand(1).getValueType())) {
1931       case Expand: assert(0 && "Not possible");
1932       case Legal:
1933         Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS.
1934         break;
1935       case Promote:
1936         Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the RHS.
1937         break;
1938     }
1939
1940     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1941
1942     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1943     default: assert(0 && "Operation not supported");
1944     case TargetLowering::Custom:
1945       Tmp1 = TLI.LowerOperation(Result, DAG);
1946       if (Tmp1.Val) Result = Tmp1;
1947       break;
1948     case TargetLowering::Legal: break;
1949     case TargetLowering::Expand:
1950       // If this target supports fabs/fneg natively, do this efficiently.
1951       if (TLI.isOperationLegal(ISD::FABS, Tmp1.getValueType()) &&
1952           TLI.isOperationLegal(ISD::FNEG, Tmp1.getValueType())) {
1953         // Get the sign bit of the RHS.
1954         MVT::ValueType IVT =
1955           Tmp2.getValueType() == MVT::f32 ? MVT::i32 : MVT::i64;
1956         SDOperand SignBit = DAG.getNode(ISD::BIT_CONVERT, IVT, Tmp2);
1957         SignBit = DAG.getSetCC(TLI.getSetCCResultTy(),
1958                                SignBit, DAG.getConstant(0, IVT), ISD::SETLT);
1959         // Get the absolute value of the result.
1960         SDOperand AbsVal = DAG.getNode(ISD::FABS, Tmp1.getValueType(), Tmp1);
1961         // Select between the nabs and abs value based on the sign bit of
1962         // the input.
1963         Result = DAG.getNode(ISD::SELECT, AbsVal.getValueType(), SignBit,
1964                              DAG.getNode(ISD::FNEG, AbsVal.getValueType(),
1965                                          AbsVal),
1966                              AbsVal);
1967         Result = LegalizeOp(Result);
1968         break;
1969       }
1970
1971       // Otherwise, do bitwise ops!
1972
1973       // copysign -> copysignf/copysign libcall.
1974       const char *FnName;
1975       if (Node->getValueType(0) == MVT::f32) {
1976         FnName = "copysignf";
1977         if (Tmp2.getValueType() != MVT::f32)  // Force operands to match type.
1978           Result = DAG.UpdateNodeOperands(Result, Tmp1,
1979                                     DAG.getNode(ISD::FP_ROUND, MVT::f32, Tmp2));
1980       } else {
1981         FnName = "copysign";
1982         if (Tmp2.getValueType() != MVT::f64)  // Force operands to match type.
1983           Result = DAG.UpdateNodeOperands(Result, Tmp1,
1984                                    DAG.getNode(ISD::FP_EXTEND, MVT::f64, Tmp2));
1985       }
1986       SDOperand Dummy;
1987       Result = ExpandLibCall(FnName, Node, Dummy);
1988       break;
1989     }
1990     break;
1991
1992   case ISD::ADDC:
1993   case ISD::SUBC:
1994     Tmp1 = LegalizeOp(Node->getOperand(0));
1995     Tmp2 = LegalizeOp(Node->getOperand(1));
1996     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1997     // Since this produces two values, make sure to remember that we legalized
1998     // both of them.
1999     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
2000     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
2001     return Result;
2002
2003   case ISD::ADDE:
2004   case ISD::SUBE:
2005     Tmp1 = LegalizeOp(Node->getOperand(0));
2006     Tmp2 = LegalizeOp(Node->getOperand(1));
2007     Tmp3 = LegalizeOp(Node->getOperand(2));
2008     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
2009     // Since this produces two values, make sure to remember that we legalized
2010     // both of them.
2011     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
2012     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
2013     return Result;
2014
2015   case ISD::BUILD_PAIR: {
2016     MVT::ValueType PairTy = Node->getValueType(0);
2017     // TODO: handle the case where the Lo and Hi operands are not of legal type
2018     Tmp1 = LegalizeOp(Node->getOperand(0));   // Lo
2019     Tmp2 = LegalizeOp(Node->getOperand(1));   // Hi
2020     switch (TLI.getOperationAction(ISD::BUILD_PAIR, PairTy)) {
2021     case TargetLowering::Promote:
2022     case TargetLowering::Custom:
2023       assert(0 && "Cannot promote/custom this yet!");
2024     case TargetLowering::Legal:
2025       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
2026         Result = DAG.getNode(ISD::BUILD_PAIR, PairTy, Tmp1, Tmp2);
2027       break;
2028     case TargetLowering::Expand:
2029       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, PairTy, Tmp1);
2030       Tmp2 = DAG.getNode(ISD::ANY_EXTEND, PairTy, Tmp2);
2031       Tmp2 = DAG.getNode(ISD::SHL, PairTy, Tmp2,
2032                          DAG.getConstant(MVT::getSizeInBits(PairTy)/2,
2033                                          TLI.getShiftAmountTy()));
2034       Result = DAG.getNode(ISD::OR, PairTy, Tmp1, Tmp2);
2035       break;
2036     }
2037     break;
2038   }
2039
2040   case ISD::UREM:
2041   case ISD::SREM:
2042   case ISD::FREM:
2043     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2044     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2045
2046     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2047     case TargetLowering::Promote: assert(0 && "Cannot promote this yet!");
2048     case TargetLowering::Custom:
2049       isCustom = true;
2050       // FALLTHROUGH
2051     case TargetLowering::Legal:
2052       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2053       if (isCustom) {
2054         Tmp1 = TLI.LowerOperation(Result, DAG);
2055         if (Tmp1.Val) Result = Tmp1;
2056       }
2057       break;
2058     case TargetLowering::Expand:
2059       if (MVT::isInteger(Node->getValueType(0))) {
2060         // X % Y -> X-X/Y*Y
2061         MVT::ValueType VT = Node->getValueType(0);
2062         unsigned Opc = Node->getOpcode() == ISD::UREM ? ISD::UDIV : ISD::SDIV;
2063         Result = DAG.getNode(Opc, VT, Tmp1, Tmp2);
2064         Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2);
2065         Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result);
2066       } else {
2067         // Floating point mod -> fmod libcall.
2068         const char *FnName = Node->getValueType(0) == MVT::f32 ? "fmodf":"fmod";
2069         SDOperand Dummy;
2070         Result = ExpandLibCall(FnName, Node, Dummy);
2071       }
2072       break;
2073     }
2074     break;
2075   case ISD::VAARG: {
2076     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2077     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2078
2079     MVT::ValueType VT = Node->getValueType(0);
2080     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
2081     default: assert(0 && "This action is not supported yet!");
2082     case TargetLowering::Custom:
2083       isCustom = true;
2084       // FALLTHROUGH
2085     case TargetLowering::Legal:
2086       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
2087       Result = Result.getValue(0);
2088       Tmp1 = Result.getValue(1);
2089
2090       if (isCustom) {
2091         Tmp2 = TLI.LowerOperation(Result, DAG);
2092         if (Tmp2.Val) {
2093           Result = LegalizeOp(Tmp2);
2094           Tmp1 = LegalizeOp(Tmp2.getValue(1));
2095         }
2096       }
2097       break;
2098     case TargetLowering::Expand: {
2099       SDOperand VAList = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp2,
2100                                      Node->getOperand(2));
2101       // Increment the pointer, VAList, to the next vaarg
2102       Tmp3 = DAG.getNode(ISD::ADD, TLI.getPointerTy(), VAList,
2103                          DAG.getConstant(MVT::getSizeInBits(VT)/8,
2104                                          TLI.getPointerTy()));
2105       // Store the incremented VAList to the legalized pointer
2106       Tmp3 = DAG.getNode(ISD::STORE, MVT::Other, VAList.getValue(1), Tmp3, Tmp2,
2107                          Node->getOperand(2));
2108       // Load the actual argument out of the pointer VAList
2109       Result = DAG.getLoad(VT, Tmp3, VAList, DAG.getSrcValue(0));
2110       Tmp1 = LegalizeOp(Result.getValue(1));
2111       Result = LegalizeOp(Result);
2112       break;
2113     }
2114     }
2115     // Since VAARG produces two values, make sure to remember that we
2116     // legalized both of them.
2117     AddLegalizedOperand(SDOperand(Node, 0), Result);
2118     AddLegalizedOperand(SDOperand(Node, 1), Tmp1);
2119     return Op.ResNo ? Tmp1 : Result;
2120   }
2121
2122   case ISD::VACOPY:
2123     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2124     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the dest pointer.
2125     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the source pointer.
2126
2127     switch (TLI.getOperationAction(ISD::VACOPY, MVT::Other)) {
2128     default: assert(0 && "This action is not supported yet!");
2129     case TargetLowering::Custom:
2130       isCustom = true;
2131       // FALLTHROUGH
2132     case TargetLowering::Legal:
2133       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3,
2134                                       Node->getOperand(3), Node->getOperand(4));
2135       if (isCustom) {
2136         Tmp1 = TLI.LowerOperation(Result, DAG);
2137         if (Tmp1.Val) Result = Tmp1;
2138       }
2139       break;
2140     case TargetLowering::Expand:
2141       // This defaults to loading a pointer from the input and storing it to the
2142       // output, returning the chain.
2143       Tmp4 = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp3, Node->getOperand(3));
2144       Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp4.getValue(1), Tmp4, Tmp2,
2145                            Node->getOperand(4));
2146       break;
2147     }
2148     break;
2149
2150   case ISD::VAEND:
2151     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2152     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2153
2154     switch (TLI.getOperationAction(ISD::VAEND, MVT::Other)) {
2155     default: assert(0 && "This action is not supported yet!");
2156     case TargetLowering::Custom:
2157       isCustom = true;
2158       // FALLTHROUGH
2159     case TargetLowering::Legal:
2160       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
2161       if (isCustom) {
2162         Tmp1 = TLI.LowerOperation(Tmp1, DAG);
2163         if (Tmp1.Val) Result = Tmp1;
2164       }
2165       break;
2166     case TargetLowering::Expand:
2167       Result = Tmp1; // Default to a no-op, return the chain
2168       break;
2169     }
2170     break;
2171
2172   case ISD::VASTART:
2173     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2174     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2175
2176     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
2177
2178     switch (TLI.getOperationAction(ISD::VASTART, MVT::Other)) {
2179     default: assert(0 && "This action is not supported yet!");
2180     case TargetLowering::Legal: break;
2181     case TargetLowering::Custom:
2182       Tmp1 = TLI.LowerOperation(Result, DAG);
2183       if (Tmp1.Val) Result = Tmp1;
2184       break;
2185     }
2186     break;
2187
2188   case ISD::ROTL:
2189   case ISD::ROTR:
2190     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2191     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2192
2193     assert(TLI.isOperationLegal(Node->getOpcode(), Node->getValueType(0)) &&
2194            "Cannot handle this yet!");
2195     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2196     break;
2197
2198   case ISD::BSWAP:
2199     Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
2200     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2201     case TargetLowering::Custom:
2202       assert(0 && "Cannot custom legalize this yet!");
2203     case TargetLowering::Legal:
2204       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2205       break;
2206     case TargetLowering::Promote: {
2207       MVT::ValueType OVT = Tmp1.getValueType();
2208       MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2209       unsigned DiffBits = getSizeInBits(NVT) - getSizeInBits(OVT);
2210
2211       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2212       Tmp1 = DAG.getNode(ISD::BSWAP, NVT, Tmp1);
2213       Result = DAG.getNode(ISD::SRL, NVT, Tmp1,
2214                            DAG.getConstant(DiffBits, TLI.getShiftAmountTy()));
2215       break;
2216     }
2217     case TargetLowering::Expand:
2218       Result = ExpandBSWAP(Tmp1);
2219       break;
2220     }
2221     break;
2222
2223   case ISD::CTPOP:
2224   case ISD::CTTZ:
2225   case ISD::CTLZ:
2226     Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
2227     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2228     case TargetLowering::Custom: assert(0 && "Cannot custom handle this yet!");
2229     case TargetLowering::Legal:
2230       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2231       break;
2232     case TargetLowering::Promote: {
2233       MVT::ValueType OVT = Tmp1.getValueType();
2234       MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2235
2236       // Zero extend the argument.
2237       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2238       // Perform the larger operation, then subtract if needed.
2239       Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
2240       switch (Node->getOpcode()) {
2241       case ISD::CTPOP:
2242         Result = Tmp1;
2243         break;
2244       case ISD::CTTZ:
2245         //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
2246         Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1,
2247                             DAG.getConstant(getSizeInBits(NVT), NVT),
2248                             ISD::SETEQ);
2249         Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
2250                            DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1);
2251         break;
2252       case ISD::CTLZ:
2253         // Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
2254         Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
2255                              DAG.getConstant(getSizeInBits(NVT) -
2256                                              getSizeInBits(OVT), NVT));
2257         break;
2258       }
2259       break;
2260     }
2261     case TargetLowering::Expand:
2262       Result = ExpandBitCount(Node->getOpcode(), Tmp1);
2263       break;
2264     }
2265     break;
2266
2267     // Unary operators
2268   case ISD::FABS:
2269   case ISD::FNEG:
2270   case ISD::FSQRT:
2271   case ISD::FSIN:
2272   case ISD::FCOS:
2273     Tmp1 = LegalizeOp(Node->getOperand(0));
2274     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2275     case TargetLowering::Promote:
2276     case TargetLowering::Custom:
2277      isCustom = true;
2278      // FALLTHROUGH
2279     case TargetLowering::Legal:
2280       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2281       if (isCustom) {
2282         Tmp1 = TLI.LowerOperation(Result, DAG);
2283         if (Tmp1.Val) Result = Tmp1;
2284       }
2285       break;
2286     case TargetLowering::Expand:
2287       switch (Node->getOpcode()) {
2288       default: assert(0 && "Unreachable!");
2289       case ISD::FNEG:
2290         // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
2291         Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0));
2292         Result = DAG.getNode(ISD::FSUB, Node->getValueType(0), Tmp2, Tmp1);
2293         break;
2294       case ISD::FABS: {
2295         // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
2296         MVT::ValueType VT = Node->getValueType(0);
2297         Tmp2 = DAG.getConstantFP(0.0, VT);
2298         Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, Tmp2, ISD::SETUGT);
2299         Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1);
2300         Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3);
2301         break;
2302       }
2303       case ISD::FSQRT:
2304       case ISD::FSIN:
2305       case ISD::FCOS: {
2306         MVT::ValueType VT = Node->getValueType(0);
2307         const char *FnName = 0;
2308         switch(Node->getOpcode()) {
2309         case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break;
2310         case ISD::FSIN:  FnName = VT == MVT::f32 ? "sinf"  : "sin"; break;
2311         case ISD::FCOS:  FnName = VT == MVT::f32 ? "cosf"  : "cos"; break;
2312         default: assert(0 && "Unreachable!");
2313         }
2314         SDOperand Dummy;
2315         Result = ExpandLibCall(FnName, Node, Dummy);
2316         break;
2317       }
2318       }
2319       break;
2320     }
2321     break;
2322
2323   case ISD::BIT_CONVERT:
2324     if (!isTypeLegal(Node->getOperand(0).getValueType())) {
2325       Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2326     } else {
2327       switch (TLI.getOperationAction(ISD::BIT_CONVERT,
2328                                      Node->getOperand(0).getValueType())) {
2329       default: assert(0 && "Unknown operation action!");
2330       case TargetLowering::Expand:
2331         Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2332         break;
2333       case TargetLowering::Legal:
2334         Tmp1 = LegalizeOp(Node->getOperand(0));
2335         Result = DAG.UpdateNodeOperands(Result, Tmp1);
2336         break;
2337       }
2338     }
2339     break;
2340   case ISD::VBIT_CONVERT: {
2341     assert(Op.getOperand(0).getValueType() == MVT::Vector &&
2342            "Can only have VBIT_CONVERT where input or output is MVT::Vector!");
2343
2344     // The input has to be a vector type, we have to either scalarize it, pack
2345     // it, or convert it based on whether the input vector type is legal.
2346     SDNode *InVal = Node->getOperand(0).Val;
2347     unsigned NumElems =
2348       cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
2349     MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
2350
2351     // Figure out if there is a Packed type corresponding to this Vector
2352     // type.  If so, convert to the packed type.
2353     MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
2354     if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
2355       // Turn this into a bit convert of the packed input.
2356       Result = DAG.getNode(ISD::BIT_CONVERT, Node->getValueType(0),
2357                            PackVectorOp(Node->getOperand(0), TVT));
2358       break;
2359     } else if (NumElems == 1) {
2360       // Turn this into a bit convert of the scalar input.
2361       Result = DAG.getNode(ISD::BIT_CONVERT, Node->getValueType(0),
2362                            PackVectorOp(Node->getOperand(0), EVT));
2363       break;
2364     } else {
2365       // FIXME: UNIMP!  Store then reload
2366       assert(0 && "Cast from unsupported vector type not implemented yet!");
2367     }
2368   }
2369
2370     // Conversion operators.  The source and destination have different types.
2371   case ISD::SINT_TO_FP:
2372   case ISD::UINT_TO_FP: {
2373     bool isSigned = Node->getOpcode() == ISD::SINT_TO_FP;
2374     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2375     case Legal:
2376       switch (TLI.getOperationAction(Node->getOpcode(),
2377                                      Node->getOperand(0).getValueType())) {
2378       default: assert(0 && "Unknown operation action!");
2379       case TargetLowering::Custom:
2380         isCustom = true;
2381         // FALLTHROUGH
2382       case TargetLowering::Legal:
2383         Tmp1 = LegalizeOp(Node->getOperand(0));
2384         Result = DAG.UpdateNodeOperands(Result, Tmp1);
2385         if (isCustom) {
2386           Tmp1 = TLI.LowerOperation(Result, DAG);
2387           if (Tmp1.Val) Result = Tmp1;
2388         }
2389         break;
2390       case TargetLowering::Expand:
2391         Result = ExpandLegalINT_TO_FP(isSigned,
2392                                       LegalizeOp(Node->getOperand(0)),
2393                                       Node->getValueType(0));
2394         break;
2395       case TargetLowering::Promote:
2396         Result = PromoteLegalINT_TO_FP(LegalizeOp(Node->getOperand(0)),
2397                                        Node->getValueType(0),
2398                                        isSigned);
2399         break;
2400       }
2401       break;
2402     case Expand:
2403       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP,
2404                              Node->getValueType(0), Node->getOperand(0));
2405       break;
2406     case Promote:
2407       Tmp1 = PromoteOp(Node->getOperand(0));
2408       if (isSigned) {
2409         Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, Tmp1.getValueType(),
2410                  Tmp1, DAG.getValueType(Node->getOperand(0).getValueType()));
2411       } else {
2412         Tmp1 = DAG.getZeroExtendInReg(Tmp1,
2413                                       Node->getOperand(0).getValueType());
2414       }
2415       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2416       Result = LegalizeOp(Result);  // The 'op' is not necessarily legal!
2417       break;
2418     }
2419     break;
2420   }
2421   case ISD::TRUNCATE:
2422     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2423     case Legal:
2424       Tmp1 = LegalizeOp(Node->getOperand(0));
2425       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2426       break;
2427     case Expand:
2428       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
2429
2430       // Since the result is legal, we should just be able to truncate the low
2431       // part of the source.
2432       Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
2433       break;
2434     case Promote:
2435       Result = PromoteOp(Node->getOperand(0));
2436       Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
2437       break;
2438     }
2439     break;
2440
2441   case ISD::FP_TO_SINT:
2442   case ISD::FP_TO_UINT:
2443     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2444     case Legal:
2445       Tmp1 = LegalizeOp(Node->getOperand(0));
2446
2447       switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))){
2448       default: assert(0 && "Unknown operation action!");
2449       case TargetLowering::Custom:
2450         isCustom = true;
2451         // FALLTHROUGH
2452       case TargetLowering::Legal:
2453         Result = DAG.UpdateNodeOperands(Result, Tmp1);
2454         if (isCustom) {
2455           Tmp1 = TLI.LowerOperation(Result, DAG);
2456           if (Tmp1.Val) Result = Tmp1;
2457         }
2458         break;
2459       case TargetLowering::Promote:
2460         Result = PromoteLegalFP_TO_INT(Tmp1, Node->getValueType(0),
2461                                        Node->getOpcode() == ISD::FP_TO_SINT);
2462         break;
2463       case TargetLowering::Expand:
2464         if (Node->getOpcode() == ISD::FP_TO_UINT) {
2465           SDOperand True, False;
2466           MVT::ValueType VT =  Node->getOperand(0).getValueType();
2467           MVT::ValueType NVT = Node->getValueType(0);
2468           unsigned ShiftAmt = MVT::getSizeInBits(Node->getValueType(0))-1;
2469           Tmp2 = DAG.getConstantFP((double)(1ULL << ShiftAmt), VT);
2470           Tmp3 = DAG.getSetCC(TLI.getSetCCResultTy(),
2471                             Node->getOperand(0), Tmp2, ISD::SETLT);
2472           True = DAG.getNode(ISD::FP_TO_SINT, NVT, Node->getOperand(0));
2473           False = DAG.getNode(ISD::FP_TO_SINT, NVT,
2474                               DAG.getNode(ISD::FSUB, VT, Node->getOperand(0),
2475                                           Tmp2));
2476           False = DAG.getNode(ISD::XOR, NVT, False,
2477                               DAG.getConstant(1ULL << ShiftAmt, NVT));
2478           Result = DAG.getNode(ISD::SELECT, NVT, Tmp3, True, False);
2479           break;
2480         } else {
2481           assert(0 && "Do not know how to expand FP_TO_SINT yet!");
2482         }
2483         break;
2484       }
2485       break;
2486     case Expand:
2487       assert(0 && "Shouldn't need to expand other operators here!");
2488     case Promote:
2489       Tmp1 = PromoteOp(Node->getOperand(0));
2490       Result = DAG.UpdateNodeOperands(Result, LegalizeOp(Tmp1));
2491       Result = LegalizeOp(Result);
2492       break;
2493     }
2494     break;
2495
2496   case ISD::ANY_EXTEND:
2497   case ISD::ZERO_EXTEND:
2498   case ISD::SIGN_EXTEND:
2499   case ISD::FP_EXTEND:
2500   case ISD::FP_ROUND:
2501     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2502     case Expand: assert(0 && "Shouldn't need to expand other operators here!");
2503     case Legal:
2504       Tmp1 = LegalizeOp(Node->getOperand(0));
2505       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2506       break;
2507     case Promote:
2508       switch (Node->getOpcode()) {
2509       case ISD::ANY_EXTEND:
2510         Tmp1 = PromoteOp(Node->getOperand(0));
2511         Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Tmp1);
2512         break;
2513       case ISD::ZERO_EXTEND:
2514         Result = PromoteOp(Node->getOperand(0));
2515         Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result);
2516         Result = DAG.getZeroExtendInReg(Result,
2517                                         Node->getOperand(0).getValueType());
2518         break;
2519       case ISD::SIGN_EXTEND:
2520         Result = PromoteOp(Node->getOperand(0));
2521         Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result);
2522         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
2523                              Result,
2524                           DAG.getValueType(Node->getOperand(0).getValueType()));
2525         break;
2526       case ISD::FP_EXTEND:
2527         Result = PromoteOp(Node->getOperand(0));
2528         if (Result.getValueType() != Op.getValueType())
2529           // Dynamically dead while we have only 2 FP types.
2530           Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
2531         break;
2532       case ISD::FP_ROUND:
2533         Result = PromoteOp(Node->getOperand(0));
2534         Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
2535         break;
2536       }
2537     }
2538     break;
2539   case ISD::FP_ROUND_INREG:
2540   case ISD::SIGN_EXTEND_INREG: {
2541     Tmp1 = LegalizeOp(Node->getOperand(0));
2542     MVT::ValueType ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
2543
2544     // If this operation is not supported, convert it to a shl/shr or load/store
2545     // pair.
2546     switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
2547     default: assert(0 && "This action not supported for this op yet!");
2548     case TargetLowering::Legal:
2549       Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
2550       break;
2551     case TargetLowering::Expand:
2552       // If this is an integer extend and shifts are supported, do that.
2553       if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
2554         // NOTE: we could fall back on load/store here too for targets without
2555         // SAR.  However, it is doubtful that any exist.
2556         unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
2557                             MVT::getSizeInBits(ExtraVT);
2558         SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy());
2559         Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
2560                              Node->getOperand(0), ShiftCst);
2561         Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
2562                              Result, ShiftCst);
2563       } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
2564         // The only way we can lower this is to turn it into a STORETRUNC,
2565         // EXTLOAD pair, targetting a temporary location (a stack slot).
2566
2567         // NOTE: there is a choice here between constantly creating new stack
2568         // slots and always reusing the same one.  We currently always create
2569         // new ones, as reuse may inhibit scheduling.
2570         const Type *Ty = MVT::getTypeForValueType(ExtraVT);
2571         unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty);
2572         unsigned Align  = TLI.getTargetData().getTypeAlignment(Ty);
2573         MachineFunction &MF = DAG.getMachineFunction();
2574         int SSFI =
2575           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
2576         SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
2577         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
2578                              Node->getOperand(0), StackSlot,
2579                              DAG.getSrcValue(NULL), DAG.getValueType(ExtraVT));
2580         Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
2581                                 Result, StackSlot, DAG.getSrcValue(NULL),
2582                                 ExtraVT);
2583       } else {
2584         assert(0 && "Unknown op");
2585       }
2586       break;
2587     }
2588     break;
2589   }
2590   }
2591
2592   // Make sure that the generated code is itself legal.
2593   if (Result != Op)
2594     Result = LegalizeOp(Result);
2595
2596   // Note that LegalizeOp may be reentered even from single-use nodes, which
2597   // means that we always must cache transformed nodes.
2598   AddLegalizedOperand(Op, Result);
2599   return Result;
2600 }
2601
2602 /// PromoteOp - Given an operation that produces a value in an invalid type,
2603 /// promote it to compute the value into a larger type.  The produced value will
2604 /// have the correct bits for the low portion of the register, but no guarantee
2605 /// is made about the top bits: it may be zero, sign-extended, or garbage.
2606 SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
2607   MVT::ValueType VT = Op.getValueType();
2608   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
2609   assert(getTypeAction(VT) == Promote &&
2610          "Caller should expand or legalize operands that are not promotable!");
2611   assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
2612          "Cannot promote to smaller type!");
2613
2614   SDOperand Tmp1, Tmp2, Tmp3;
2615   SDOperand Result;
2616   SDNode *Node = Op.Val;
2617
2618   std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
2619   if (I != PromotedNodes.end()) return I->second;
2620
2621   switch (Node->getOpcode()) {
2622   case ISD::CopyFromReg:
2623     assert(0 && "CopyFromReg must be legal!");
2624   default:
2625     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
2626     assert(0 && "Do not know how to promote this operator!");
2627     abort();
2628   case ISD::UNDEF:
2629     Result = DAG.getNode(ISD::UNDEF, NVT);
2630     break;
2631   case ISD::Constant:
2632     if (VT != MVT::i1)
2633       Result = DAG.getNode(ISD::SIGN_EXTEND, NVT, Op);
2634     else
2635       Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
2636     assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
2637     break;
2638   case ISD::ConstantFP:
2639     Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
2640     assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
2641     break;
2642
2643   case ISD::SETCC:
2644     assert(isTypeLegal(TLI.getSetCCResultTy()) && "SetCC type is not legal??");
2645     Result = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(),Node->getOperand(0),
2646                          Node->getOperand(1), Node->getOperand(2));
2647     break;
2648
2649   case ISD::TRUNCATE:
2650     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2651     case Legal:
2652       Result = LegalizeOp(Node->getOperand(0));
2653       assert(Result.getValueType() >= NVT &&
2654              "This truncation doesn't make sense!");
2655       if (Result.getValueType() > NVT)    // Truncate to NVT instead of VT
2656         Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
2657       break;
2658     case Promote:
2659       // The truncation is not required, because we don't guarantee anything
2660       // about high bits anyway.
2661       Result = PromoteOp(Node->getOperand(0));
2662       break;
2663     case Expand:
2664       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
2665       // Truncate the low part of the expanded value to the result type
2666       Result = DAG.getNode(ISD::TRUNCATE, NVT, Tmp1);
2667     }
2668     break;
2669   case ISD::SIGN_EXTEND:
2670   case ISD::ZERO_EXTEND:
2671   case ISD::ANY_EXTEND:
2672     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2673     case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
2674     case Legal:
2675       // Input is legal?  Just do extend all the way to the larger type.
2676       Result = DAG.getNode(Node->getOpcode(), NVT, Node->getOperand(0));
2677       break;
2678     case Promote:
2679       // Promote the reg if it's smaller.
2680       Result = PromoteOp(Node->getOperand(0));
2681       // The high bits are not guaranteed to be anything.  Insert an extend.
2682       if (Node->getOpcode() == ISD::SIGN_EXTEND)
2683         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
2684                          DAG.getValueType(Node->getOperand(0).getValueType()));
2685       else if (Node->getOpcode() == ISD::ZERO_EXTEND)
2686         Result = DAG.getZeroExtendInReg(Result,
2687                                         Node->getOperand(0).getValueType());
2688       break;
2689     }
2690     break;
2691   case ISD::BIT_CONVERT:
2692     Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2693     Result = PromoteOp(Result);
2694     break;
2695
2696   case ISD::FP_EXTEND:
2697     assert(0 && "Case not implemented.  Dynamically dead with 2 FP types!");
2698   case ISD::FP_ROUND:
2699     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2700     case Expand: assert(0 && "BUG: Cannot expand FP regs!");
2701     case Promote:  assert(0 && "Unreachable with 2 FP types!");
2702     case Legal:
2703       // Input is legal?  Do an FP_ROUND_INREG.
2704       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Node->getOperand(0),
2705                            DAG.getValueType(VT));
2706       break;
2707     }
2708     break;
2709
2710   case ISD::SINT_TO_FP:
2711   case ISD::UINT_TO_FP:
2712     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2713     case Legal:
2714       // No extra round required here.
2715       Result = DAG.getNode(Node->getOpcode(), NVT, Node->getOperand(0));
2716       break;
2717
2718     case Promote:
2719       Result = PromoteOp(Node->getOperand(0));
2720       if (Node->getOpcode() == ISD::SINT_TO_FP)
2721         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
2722                              Result,
2723                          DAG.getValueType(Node->getOperand(0).getValueType()));
2724       else
2725         Result = DAG.getZeroExtendInReg(Result,
2726                                         Node->getOperand(0).getValueType());
2727       // No extra round required here.
2728       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
2729       break;
2730     case Expand:
2731       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT,
2732                              Node->getOperand(0));
2733       // Round if we cannot tolerate excess precision.
2734       if (NoExcessFPPrecision)
2735         Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2736                              DAG.getValueType(VT));
2737       break;
2738     }
2739     break;
2740
2741   case ISD::SIGN_EXTEND_INREG:
2742     Result = PromoteOp(Node->getOperand(0));
2743     Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
2744                          Node->getOperand(1));
2745     break;
2746   case ISD::FP_TO_SINT:
2747   case ISD::FP_TO_UINT:
2748     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2749     case Legal:
2750       Tmp1 = Node->getOperand(0);
2751       break;
2752     case Promote:
2753       // The input result is prerounded, so we don't have to do anything
2754       // special.
2755       Tmp1 = PromoteOp(Node->getOperand(0));
2756       break;
2757     case Expand:
2758       assert(0 && "not implemented");
2759     }
2760     // If we're promoting a UINT to a larger size, check to see if the new node
2761     // will be legal.  If it isn't, check to see if FP_TO_SINT is legal, since
2762     // we can use that instead.  This allows us to generate better code for
2763     // FP_TO_UINT for small destination sizes on targets where FP_TO_UINT is not
2764     // legal, such as PowerPC.
2765     if (Node->getOpcode() == ISD::FP_TO_UINT &&
2766         !TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) &&
2767         (TLI.isOperationLegal(ISD::FP_TO_SINT, NVT) ||
2768          TLI.getOperationAction(ISD::FP_TO_SINT, NVT)==TargetLowering::Custom)){
2769       Result = DAG.getNode(ISD::FP_TO_SINT, NVT, Tmp1);
2770     } else {
2771       Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2772     }
2773     break;
2774
2775   case ISD::FABS:
2776   case ISD::FNEG:
2777     Tmp1 = PromoteOp(Node->getOperand(0));
2778     assert(Tmp1.getValueType() == NVT);
2779     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2780     // NOTE: we do not have to do any extra rounding here for
2781     // NoExcessFPPrecision, because we know the input will have the appropriate
2782     // precision, and these operations don't modify precision at all.
2783     break;
2784
2785   case ISD::FSQRT:
2786   case ISD::FSIN:
2787   case ISD::FCOS:
2788     Tmp1 = PromoteOp(Node->getOperand(0));
2789     assert(Tmp1.getValueType() == NVT);
2790     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2791     if (NoExcessFPPrecision)
2792       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2793                            DAG.getValueType(VT));
2794     break;
2795
2796   case ISD::AND:
2797   case ISD::OR:
2798   case ISD::XOR:
2799   case ISD::ADD:
2800   case ISD::SUB:
2801   case ISD::MUL:
2802     // The input may have strange things in the top bits of the registers, but
2803     // these operations don't care.  They may have weird bits going out, but
2804     // that too is okay if they are integer operations.
2805     Tmp1 = PromoteOp(Node->getOperand(0));
2806     Tmp2 = PromoteOp(Node->getOperand(1));
2807     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
2808     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2809     break;
2810   case ISD::FADD:
2811   case ISD::FSUB:
2812   case ISD::FMUL:
2813     Tmp1 = PromoteOp(Node->getOperand(0));
2814     Tmp2 = PromoteOp(Node->getOperand(1));
2815     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
2816     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2817
2818     // Floating point operations will give excess precision that we may not be
2819     // able to tolerate.  If we DO allow excess precision, just leave it,
2820     // otherwise excise it.
2821     // FIXME: Why would we need to round FP ops more than integer ones?
2822     //     Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
2823     if (NoExcessFPPrecision)
2824       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2825                            DAG.getValueType(VT));
2826     break;
2827
2828   case ISD::SDIV:
2829   case ISD::SREM:
2830     // These operators require that their input be sign extended.
2831     Tmp1 = PromoteOp(Node->getOperand(0));
2832     Tmp2 = PromoteOp(Node->getOperand(1));
2833     if (MVT::isInteger(NVT)) {
2834       Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
2835                          DAG.getValueType(VT));
2836       Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
2837                          DAG.getValueType(VT));
2838     }
2839     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2840
2841     // Perform FP_ROUND: this is probably overly pessimistic.
2842     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
2843       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2844                            DAG.getValueType(VT));
2845     break;
2846   case ISD::FDIV:
2847   case ISD::FREM:
2848   case ISD::FCOPYSIGN:
2849     // These operators require that their input be fp extended.
2850     Tmp1 = PromoteOp(Node->getOperand(0));
2851     Tmp2 = PromoteOp(Node->getOperand(1));
2852     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2853
2854     // Perform FP_ROUND: this is probably overly pessimistic.
2855     if (NoExcessFPPrecision && Node->getOpcode() != ISD::FCOPYSIGN)
2856       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2857                            DAG.getValueType(VT));
2858     break;
2859
2860   case ISD::UDIV:
2861   case ISD::UREM:
2862     // These operators require that their input be zero extended.
2863     Tmp1 = PromoteOp(Node->getOperand(0));
2864     Tmp2 = PromoteOp(Node->getOperand(1));
2865     assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
2866     Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
2867     Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
2868     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2869     break;
2870
2871   case ISD::SHL:
2872     Tmp1 = PromoteOp(Node->getOperand(0));
2873     Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Node->getOperand(1));
2874     break;
2875   case ISD::SRA:
2876     // The input value must be properly sign extended.
2877     Tmp1 = PromoteOp(Node->getOperand(0));
2878     Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
2879                        DAG.getValueType(VT));
2880     Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Node->getOperand(1));
2881     break;
2882   case ISD::SRL:
2883     // The input value must be properly zero extended.
2884     Tmp1 = PromoteOp(Node->getOperand(0));
2885     Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
2886     Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Node->getOperand(1));
2887     break;
2888
2889   case ISD::VAARG:
2890     Tmp1 = Node->getOperand(0);   // Get the chain.
2891     Tmp2 = Node->getOperand(1);   // Get the pointer.
2892     if (TLI.getOperationAction(ISD::VAARG, VT) == TargetLowering::Custom) {
2893       Tmp3 = DAG.getVAArg(VT, Tmp1, Tmp2, Node->getOperand(2));
2894       Result = TLI.CustomPromoteOperation(Tmp3, DAG);
2895     } else {
2896       SDOperand VAList = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp2,
2897                                      Node->getOperand(2));
2898       // Increment the pointer, VAList, to the next vaarg
2899       Tmp3 = DAG.getNode(ISD::ADD, TLI.getPointerTy(), VAList,
2900                          DAG.getConstant(MVT::getSizeInBits(VT)/8,
2901                                          TLI.getPointerTy()));
2902       // Store the incremented VAList to the legalized pointer
2903       Tmp3 = DAG.getNode(ISD::STORE, MVT::Other, VAList.getValue(1), Tmp3, Tmp2,
2904                          Node->getOperand(2));
2905       // Load the actual argument out of the pointer VAList
2906       Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Tmp3, VAList,
2907                               DAG.getSrcValue(0), VT);
2908     }
2909     // Remember that we legalized the chain.
2910     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
2911     break;
2912
2913   case ISD::LOAD:
2914     Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Node->getOperand(0),
2915                             Node->getOperand(1), Node->getOperand(2), VT);
2916     // Remember that we legalized the chain.
2917     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
2918     break;
2919   case ISD::SEXTLOAD:
2920   case ISD::ZEXTLOAD:
2921   case ISD::EXTLOAD:
2922     Result = DAG.getExtLoad(Node->getOpcode(), NVT, Node->getOperand(0),
2923                             Node->getOperand(1), Node->getOperand(2),
2924                             cast<VTSDNode>(Node->getOperand(3))->getVT());
2925     // Remember that we legalized the chain.
2926     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
2927     break;
2928   case ISD::SELECT:
2929     Tmp2 = PromoteOp(Node->getOperand(1));   // Legalize the op0
2930     Tmp3 = PromoteOp(Node->getOperand(2));   // Legalize the op1
2931     Result = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), Tmp2, Tmp3);
2932     break;
2933   case ISD::SELECT_CC:
2934     Tmp2 = PromoteOp(Node->getOperand(2));   // True
2935     Tmp3 = PromoteOp(Node->getOperand(3));   // False
2936     Result = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
2937                          Node->getOperand(1), Tmp2, Tmp3, Node->getOperand(4));
2938     break;
2939   case ISD::BSWAP:
2940     Tmp1 = Node->getOperand(0);
2941     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2942     Tmp1 = DAG.getNode(ISD::BSWAP, NVT, Tmp1);
2943     Result = DAG.getNode(ISD::SRL, NVT, Tmp1,
2944                          DAG.getConstant(getSizeInBits(NVT) - getSizeInBits(VT),
2945                                          TLI.getShiftAmountTy()));
2946     break;
2947   case ISD::CTPOP:
2948   case ISD::CTTZ:
2949   case ISD::CTLZ:
2950     // Zero extend the argument
2951     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Node->getOperand(0));
2952     // Perform the larger operation, then subtract if needed.
2953     Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2954     switch(Node->getOpcode()) {
2955     case ISD::CTPOP:
2956       Result = Tmp1;
2957       break;
2958     case ISD::CTTZ:
2959       // if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
2960       Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1,
2961                           DAG.getConstant(getSizeInBits(NVT), NVT), ISD::SETEQ);
2962       Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
2963                            DAG.getConstant(getSizeInBits(VT), NVT), Tmp1);
2964       break;
2965     case ISD::CTLZ:
2966       //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
2967       Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
2968                            DAG.getConstant(getSizeInBits(NVT) -
2969                                            getSizeInBits(VT), NVT));
2970       break;
2971     }
2972     break;
2973   case ISD::VEXTRACT_VECTOR_ELT:
2974     Result = PromoteOp(LowerVEXTRACT_VECTOR_ELT(Op));
2975     break;
2976   }
2977
2978   assert(Result.Val && "Didn't set a result!");
2979
2980   // Make sure the result is itself legal.
2981   Result = LegalizeOp(Result);
2982
2983   // Remember that we promoted this!
2984   AddPromotedOperand(Op, Result);
2985   return Result;
2986 }
2987
2988 /// LowerVEXTRACT_VECTOR_ELT - Lower a VEXTRACT_VECTOR_ELT operation into a
2989 /// EXTRACT_VECTOR_ELT operation, to memory operations, or to scalar code based
2990 /// on the vector type.  The return type of this matches the element type of the
2991 /// vector, which may not be legal for the target.
2992 SDOperand SelectionDAGLegalize::LowerVEXTRACT_VECTOR_ELT(SDOperand Op) {
2993   // We know that operand #0 is the Vec vector.  If the index is a constant
2994   // or if the invec is a supported hardware type, we can use it.  Otherwise,
2995   // lower to a store then an indexed load.
2996   SDOperand Vec = Op.getOperand(0);
2997   SDOperand Idx = LegalizeOp(Op.getOperand(1));
2998
2999   SDNode *InVal = Vec.Val;
3000   unsigned NumElems = cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
3001   MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
3002
3003   // Figure out if there is a Packed type corresponding to this Vector
3004   // type.  If so, convert to the packed type.
3005   MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
3006   if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
3007     // Turn this into a packed extract_vector_elt operation.
3008     Vec = PackVectorOp(Vec, TVT);
3009     return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, Op.getValueType(), Vec, Idx);
3010   } else if (NumElems == 1) {
3011     // This must be an access of the only element.  Return it.
3012     return PackVectorOp(Vec, EVT);
3013   } else if (ConstantSDNode *CIdx = dyn_cast<ConstantSDNode>(Idx)) {
3014     SDOperand Lo, Hi;
3015     SplitVectorOp(Vec, Lo, Hi);
3016     if (CIdx->getValue() < NumElems/2) {
3017       Vec = Lo;
3018     } else {
3019       Vec = Hi;
3020       Idx = DAG.getConstant(CIdx->getValue() - NumElems/2, Idx.getValueType());
3021     }
3022
3023     // It's now an extract from the appropriate high or low part.  Recurse.
3024     Op = DAG.UpdateNodeOperands(Op, Vec, Idx);
3025     return LowerVEXTRACT_VECTOR_ELT(Op);
3026   } else {
3027     // Variable index case for extract element.
3028     // FIXME: IMPLEMENT STORE/LOAD lowering.  Need alignment of stack slot!!
3029     assert(0 && "unimp!");
3030     return SDOperand();
3031   }
3032 }
3033
3034
3035 /// LegalizeSetCCOperands - Attempts to create a legal LHS and RHS for a SETCC
3036 /// with condition CC on the current target.  This usually involves legalizing
3037 /// or promoting the arguments.  In the case where LHS and RHS must be expanded,
3038 /// there may be no choice but to create a new SetCC node to represent the
3039 /// legalized value of setcc lhs, rhs.  In this case, the value is returned in
3040 /// LHS, and the SDOperand returned in RHS has a nil SDNode value.
3041 void SelectionDAGLegalize::LegalizeSetCCOperands(SDOperand &LHS,
3042                                                  SDOperand &RHS,
3043                                                  SDOperand &CC) {
3044   SDOperand Tmp1, Tmp2, Result;
3045
3046   switch (getTypeAction(LHS.getValueType())) {
3047   case Legal:
3048     Tmp1 = LegalizeOp(LHS);   // LHS
3049     Tmp2 = LegalizeOp(RHS);   // RHS
3050     break;
3051   case Promote:
3052     Tmp1 = PromoteOp(LHS);   // LHS
3053     Tmp2 = PromoteOp(RHS);   // RHS
3054
3055     // If this is an FP compare, the operands have already been extended.
3056     if (MVT::isInteger(LHS.getValueType())) {
3057       MVT::ValueType VT = LHS.getValueType();
3058       MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
3059
3060       // Otherwise, we have to insert explicit sign or zero extends.  Note
3061       // that we could insert sign extends for ALL conditions, but zero extend
3062       // is cheaper on many machines (an AND instead of two shifts), so prefer
3063       // it.
3064       switch (cast<CondCodeSDNode>(CC)->get()) {
3065       default: assert(0 && "Unknown integer comparison!");
3066       case ISD::SETEQ:
3067       case ISD::SETNE:
3068       case ISD::SETUGE:
3069       case ISD::SETUGT:
3070       case ISD::SETULE:
3071       case ISD::SETULT:
3072         // ALL of these operations will work if we either sign or zero extend
3073         // the operands (including the unsigned comparisons!).  Zero extend is
3074         // usually a simpler/cheaper operation, so prefer it.
3075         Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
3076         Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
3077         break;
3078       case ISD::SETGE:
3079       case ISD::SETGT:
3080       case ISD::SETLT:
3081       case ISD::SETLE:
3082         Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
3083                            DAG.getValueType(VT));
3084         Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
3085                            DAG.getValueType(VT));
3086         break;
3087       }
3088     }
3089     break;
3090   case Expand:
3091     SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
3092     ExpandOp(LHS, LHSLo, LHSHi);
3093     ExpandOp(RHS, RHSLo, RHSHi);
3094     switch (cast<CondCodeSDNode>(CC)->get()) {
3095     case ISD::SETEQ:
3096     case ISD::SETNE:
3097       if (RHSLo == RHSHi)
3098         if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
3099           if (RHSCST->isAllOnesValue()) {
3100             // Comparison to -1.
3101             Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
3102             Tmp2 = RHSLo;
3103             break;
3104           }
3105
3106       Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
3107       Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
3108       Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
3109       Tmp2 = DAG.getConstant(0, Tmp1.getValueType());
3110       break;
3111     default:
3112       // If this is a comparison of the sign bit, just look at the top part.
3113       // X > -1,  x < 0
3114       if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(RHS))
3115         if ((cast<CondCodeSDNode>(CC)->get() == ISD::SETLT &&
3116              CST->getValue() == 0) ||             // X < 0
3117             (cast<CondCodeSDNode>(CC)->get() == ISD::SETGT &&
3118              CST->isAllOnesValue())) {            // X > -1
3119           Tmp1 = LHSHi;
3120           Tmp2 = RHSHi;
3121           break;
3122         }
3123
3124       // FIXME: This generated code sucks.
3125       ISD::CondCode LowCC;
3126       switch (cast<CondCodeSDNode>(CC)->get()) {
3127       default: assert(0 && "Unknown integer setcc!");
3128       case ISD::SETLT:
3129       case ISD::SETULT: LowCC = ISD::SETULT; break;
3130       case ISD::SETGT:
3131       case ISD::SETUGT: LowCC = ISD::SETUGT; break;
3132       case ISD::SETLE:
3133       case ISD::SETULE: LowCC = ISD::SETULE; break;
3134       case ISD::SETGE:
3135       case ISD::SETUGE: LowCC = ISD::SETUGE; break;
3136       }
3137
3138       // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
3139       // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
3140       // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
3141
3142       // NOTE: on targets without efficient SELECT of bools, we can always use
3143       // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
3144       Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC);
3145       Tmp2 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), LHSHi, RHSHi, CC);
3146       Result = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ);
3147       Result = LegalizeOp(DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
3148                                       Result, Tmp1, Tmp2));
3149       Tmp1 = Result;
3150       Tmp2 = SDOperand();
3151     }
3152   }
3153   LHS = Tmp1;
3154   RHS = Tmp2;
3155 }
3156
3157 /// ExpandBIT_CONVERT - Expand a BIT_CONVERT node into a store/load combination.
3158 /// The resultant code need not be legal.  Note that SrcOp is the input operand
3159 /// to the BIT_CONVERT, not the BIT_CONVERT node itself.
3160 SDOperand SelectionDAGLegalize::ExpandBIT_CONVERT(MVT::ValueType DestVT,
3161                                                   SDOperand SrcOp) {
3162   // Create the stack frame object.
3163   SDOperand FIPtr = CreateStackTemporary(DestVT);
3164
3165   // Emit a store to the stack slot.
3166   SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
3167                                 SrcOp, FIPtr, DAG.getSrcValue(NULL));
3168   // Result is a load from the stack slot.
3169   return DAG.getLoad(DestVT, Store, FIPtr, DAG.getSrcValue(0));
3170 }
3171
3172 /// ExpandBUILD_VECTOR - Expand a BUILD_VECTOR node on targets that don't
3173 /// support the operation, but do support the resultant packed vector type.
3174 SDOperand SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
3175
3176   // If the only non-undef value is the low element, turn this into a
3177   // SCALAR_TO_VECTOR node.  If this is { X, X, X, X }, determine X.
3178   unsigned NumElems = Node->getNumOperands();
3179   bool isOnlyLowElement = true;
3180   SDOperand SplatValue = Node->getOperand(0);
3181   std::map<SDOperand, std::vector<unsigned> > Values;
3182   Values[SplatValue].push_back(0);
3183   bool isConstant = true;
3184   if (!isa<ConstantFPSDNode>(SplatValue) && !isa<ConstantSDNode>(SplatValue) &&
3185       SplatValue.getOpcode() != ISD::UNDEF)
3186     isConstant = false;
3187
3188   for (unsigned i = 1; i < NumElems; ++i) {
3189     SDOperand V = Node->getOperand(i);
3190     std::map<SDOperand, std::vector<unsigned> >::iterator I = Values.find(V);
3191     if (I != Values.end())
3192       I->second.push_back(i);
3193     else
3194       Values[V].push_back(i);
3195     if (V.getOpcode() != ISD::UNDEF)
3196       isOnlyLowElement = false;
3197     if (SplatValue != V)
3198       SplatValue = SDOperand(0,0);
3199
3200     // If this isn't a constant element or an undef, we can't use a constant
3201     // pool load.
3202     if (!isa<ConstantFPSDNode>(V) && !isa<ConstantSDNode>(V) &&
3203         V.getOpcode() != ISD::UNDEF)
3204       isConstant = false;
3205   }
3206
3207   if (isOnlyLowElement) {
3208     // If the low element is an undef too, then this whole things is an undef.
3209     if (Node->getOperand(0).getOpcode() == ISD::UNDEF)
3210       return DAG.getNode(ISD::UNDEF, Node->getValueType(0));
3211     // Otherwise, turn this into a scalar_to_vector node.
3212     return DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0),
3213                        Node->getOperand(0));
3214   }
3215
3216   // If all elements are constants, create a load from the constant pool.
3217   if (isConstant) {
3218     MVT::ValueType VT = Node->getValueType(0);
3219     const Type *OpNTy =
3220       MVT::getTypeForValueType(Node->getOperand(0).getValueType());
3221     std::vector<Constant*> CV;
3222     for (unsigned i = 0, e = NumElems; i != e; ++i) {
3223       if (ConstantFPSDNode *V =
3224           dyn_cast<ConstantFPSDNode>(Node->getOperand(i))) {
3225         CV.push_back(ConstantFP::get(OpNTy, V->getValue()));
3226       } else if (ConstantSDNode *V =
3227                  dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
3228         CV.push_back(ConstantUInt::get(OpNTy, V->getValue()));
3229       } else {
3230         assert(Node->getOperand(i).getOpcode() == ISD::UNDEF);
3231         CV.push_back(UndefValue::get(OpNTy));
3232       }
3233     }
3234     Constant *CP = ConstantPacked::get(CV);
3235     SDOperand CPIdx = DAG.getConstantPool(CP, TLI.getPointerTy());
3236     return DAG.getLoad(VT, DAG.getEntryNode(), CPIdx,
3237                        DAG.getSrcValue(NULL));
3238   }
3239
3240   if (SplatValue.Val) {   // Splat of one value?
3241     // Build the shuffle constant vector: <0, 0, 0, 0>
3242     MVT::ValueType MaskVT =
3243       MVT::getIntVectorWithNumElements(NumElems);
3244     SDOperand Zero = DAG.getConstant(0, MVT::getVectorBaseType(MaskVT));
3245     std::vector<SDOperand> ZeroVec(NumElems, Zero);
3246     SDOperand SplatMask = DAG.getNode(ISD::BUILD_VECTOR, MaskVT, ZeroVec);
3247
3248     // If the target supports VECTOR_SHUFFLE and this shuffle mask, use it.
3249     if (TLI.isShuffleLegal(Node->getValueType(0), SplatMask)) {
3250       // Get the splatted value into the low element of a vector register.
3251       SDOperand LowValVec =
3252         DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0), SplatValue);
3253
3254       // Return shuffle(LowValVec, undef, <0,0,0,0>)
3255       return DAG.getNode(ISD::VECTOR_SHUFFLE, Node->getValueType(0), LowValVec,
3256                          DAG.getNode(ISD::UNDEF, Node->getValueType(0)),
3257                          SplatMask);
3258     }
3259   }
3260
3261   // If there are only two unique elements, we may be able to turn this into a
3262   // vector shuffle.
3263   if (Values.size() == 2) {
3264     // Build the shuffle constant vector: e.g. <0, 4, 0, 4>
3265     MVT::ValueType MaskVT =
3266       MVT::getIntVectorWithNumElements(NumElems);
3267     std::vector<SDOperand> MaskVec(NumElems);
3268     unsigned i = 0;
3269     for (std::map<SDOperand,std::vector<unsigned> >::iterator I=Values.begin(),
3270            E = Values.end(); I != E; ++I) {
3271       for (std::vector<unsigned>::iterator II = I->second.begin(),
3272              EE = I->second.end(); II != EE; ++II)
3273         MaskVec[*II] = DAG.getConstant(i, MVT::getVectorBaseType(MaskVT));
3274       i += NumElems;
3275     }
3276     SDOperand ShuffleMask = DAG.getNode(ISD::BUILD_VECTOR, MaskVT, MaskVec);
3277
3278     // If the target supports VECTOR_SHUFFLE and this shuffle mask, use it.
3279     if (TLI.isShuffleLegal(Node->getValueType(0), ShuffleMask) &&
3280         TLI.isOperationLegal(ISD::SCALAR_TO_VECTOR, Node->getValueType(0))) {
3281       std::vector<SDOperand> Ops;
3282       for(std::map<SDOperand,std::vector<unsigned> >::iterator I=Values.begin(),
3283             E = Values.end(); I != E; ++I) {
3284         SDOperand Op = DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0),
3285                                    I->first);
3286         Ops.push_back(Op);
3287       }
3288       Ops.push_back(ShuffleMask);
3289
3290       // Return shuffle(LoValVec, HiValVec, <0,1,0,1>)
3291       return DAG.getNode(ISD::VECTOR_SHUFFLE, Node->getValueType(0), Ops);
3292     }
3293   }
3294
3295   // Otherwise, we can't handle this case efficiently.  Allocate a sufficiently
3296   // aligned object on the stack, store each element into it, then load
3297   // the result as a vector.
3298   MVT::ValueType VT = Node->getValueType(0);
3299   // Create the stack frame object.
3300   SDOperand FIPtr = CreateStackTemporary(VT);
3301
3302   // Emit a store of each element to the stack slot.
3303   std::vector<SDOperand> Stores;
3304   unsigned TypeByteSize =
3305     MVT::getSizeInBits(Node->getOperand(0).getValueType())/8;
3306   unsigned VectorSize = MVT::getSizeInBits(VT)/8;
3307   // Store (in the right endianness) the elements to memory.
3308   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
3309     // Ignore undef elements.
3310     if (Node->getOperand(i).getOpcode() == ISD::UNDEF) continue;
3311
3312     unsigned Offset = TypeByteSize*i;
3313
3314     SDOperand Idx = DAG.getConstant(Offset, FIPtr.getValueType());
3315     Idx = DAG.getNode(ISD::ADD, FIPtr.getValueType(), FIPtr, Idx);
3316
3317     Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
3318                                  Node->getOperand(i), Idx,
3319                                  DAG.getSrcValue(NULL)));
3320   }
3321
3322   SDOperand StoreChain;
3323   if (!Stores.empty())    // Not all undef elements?
3324     StoreChain = DAG.getNode(ISD::TokenFactor, MVT::Other, Stores);
3325   else
3326     StoreChain = DAG.getEntryNode();
3327
3328   // Result is a load from the stack slot.
3329   return DAG.getLoad(VT, StoreChain, FIPtr, DAG.getSrcValue(0));
3330 }
3331
3332 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
3333 /// specified value type.
3334 SDOperand SelectionDAGLegalize::CreateStackTemporary(MVT::ValueType VT) {
3335   MachineFrameInfo *FrameInfo = DAG.getMachineFunction().getFrameInfo();
3336   unsigned ByteSize = MVT::getSizeInBits(VT)/8;
3337   int FrameIdx = FrameInfo->CreateStackObject(ByteSize, ByteSize);
3338   return DAG.getFrameIndex(FrameIdx, TLI.getPointerTy());
3339 }
3340
3341 void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp,
3342                                             SDOperand Op, SDOperand Amt,
3343                                             SDOperand &Lo, SDOperand &Hi) {
3344   // Expand the subcomponents.
3345   SDOperand LHSL, LHSH;
3346   ExpandOp(Op, LHSL, LHSH);
3347
3348   std::vector<SDOperand> Ops;
3349   Ops.push_back(LHSL);
3350   Ops.push_back(LHSH);
3351   Ops.push_back(Amt);
3352   std::vector<MVT::ValueType> VTs(2, LHSL.getValueType());
3353   Lo = DAG.getNode(NodeOp, VTs, Ops);
3354   Hi = Lo.getValue(1);
3355 }
3356
3357
3358 /// ExpandShift - Try to find a clever way to expand this shift operation out to
3359 /// smaller elements.  If we can't find a way that is more efficient than a
3360 /// libcall on this target, return false.  Otherwise, return true with the
3361 /// low-parts expanded into Lo and Hi.
3362 bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
3363                                        SDOperand &Lo, SDOperand &Hi) {
3364   assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
3365          "This is not a shift!");
3366
3367   MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
3368   SDOperand ShAmt = LegalizeOp(Amt);
3369   MVT::ValueType ShTy = ShAmt.getValueType();
3370   unsigned VTBits = MVT::getSizeInBits(Op.getValueType());
3371   unsigned NVTBits = MVT::getSizeInBits(NVT);
3372
3373   // Handle the case when Amt is an immediate.  Other cases are currently broken
3374   // and are disabled.
3375   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) {
3376     unsigned Cst = CN->getValue();
3377     // Expand the incoming operand to be shifted, so that we have its parts
3378     SDOperand InL, InH;
3379     ExpandOp(Op, InL, InH);
3380     switch(Opc) {
3381     case ISD::SHL:
3382       if (Cst > VTBits) {
3383         Lo = DAG.getConstant(0, NVT);
3384         Hi = DAG.getConstant(0, NVT);
3385       } else if (Cst > NVTBits) {
3386         Lo = DAG.getConstant(0, NVT);
3387         Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy));
3388       } else if (Cst == NVTBits) {
3389         Lo = DAG.getConstant(0, NVT);
3390         Hi = InL;
3391       } else {
3392         Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy));
3393         Hi = DAG.getNode(ISD::OR, NVT,
3394            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)),
3395            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy)));
3396       }
3397       return true;
3398     case ISD::SRL:
3399       if (Cst > VTBits) {
3400         Lo = DAG.getConstant(0, NVT);
3401         Hi = DAG.getConstant(0, NVT);
3402       } else if (Cst > NVTBits) {
3403         Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy));
3404         Hi = DAG.getConstant(0, NVT);
3405       } else if (Cst == NVTBits) {
3406         Lo = InH;
3407         Hi = DAG.getConstant(0, NVT);
3408       } else {
3409         Lo = DAG.getNode(ISD::OR, NVT,
3410            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
3411            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
3412         Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy));
3413       }
3414       return true;
3415     case ISD::SRA:
3416       if (Cst > VTBits) {
3417         Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
3418                               DAG.getConstant(NVTBits-1, ShTy));
3419       } else if (Cst > NVTBits) {
3420         Lo = DAG.getNode(ISD::SRA, NVT, InH,
3421                            DAG.getConstant(Cst-NVTBits, ShTy));
3422         Hi = DAG.getNode(ISD::SRA, NVT, InH,
3423                               DAG.getConstant(NVTBits-1, ShTy));
3424       } else if (Cst == NVTBits) {
3425         Lo = InH;
3426         Hi = DAG.getNode(ISD::SRA, NVT, InH,
3427                               DAG.getConstant(NVTBits-1, ShTy));
3428       } else {
3429         Lo = DAG.getNode(ISD::OR, NVT,
3430            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
3431            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
3432         Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy));
3433       }
3434       return true;
3435     }
3436   }
3437   return false;
3438 }
3439
3440
3441 // ExpandLibCall - Expand a node into a call to a libcall.  If the result value
3442 // does not fit into a register, return the lo part and set the hi part to the
3443 // by-reg argument.  If it does fit into a single register, return the result
3444 // and leave the Hi part unset.
3445 SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node,
3446                                               SDOperand &Hi) {
3447   assert(!IsLegalizingCall && "Cannot overlap legalization of calls!");
3448   // The input chain to this libcall is the entry node of the function.
3449   // Legalizing the call will automatically add the previous call to the
3450   // dependence.
3451   SDOperand InChain = DAG.getEntryNode();
3452
3453   TargetLowering::ArgListTy Args;
3454   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
3455     MVT::ValueType ArgVT = Node->getOperand(i).getValueType();
3456     const Type *ArgTy = MVT::getTypeForValueType(ArgVT);
3457     Args.push_back(std::make_pair(Node->getOperand(i), ArgTy));
3458   }
3459   SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy());
3460
3461   // Splice the libcall in wherever FindInputOutputChains tells us to.
3462   const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0));
3463   std::pair<SDOperand,SDOperand> CallInfo =
3464     TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, false,
3465                     Callee, Args, DAG);
3466
3467   // Legalize the call sequence, starting with the chain.  This will advance
3468   // the LastCALLSEQ_END to the legalized version of the CALLSEQ_END node that
3469   // was added by LowerCallTo (guaranteeing proper serialization of calls).
3470   LegalizeOp(CallInfo.second);
3471   SDOperand Result;
3472   switch (getTypeAction(CallInfo.first.getValueType())) {
3473   default: assert(0 && "Unknown thing");
3474   case Legal:
3475     Result = CallInfo.first;
3476     break;
3477   case Expand:
3478     ExpandOp(CallInfo.first, Result, Hi);
3479     break;
3480   }
3481   return Result;
3482 }
3483
3484
3485 /// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the
3486 /// destination type is legal.
3487 SDOperand SelectionDAGLegalize::
3488 ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) {
3489   assert(isTypeLegal(DestTy) && "Destination type is not legal!");
3490   assert(getTypeAction(Source.getValueType()) == Expand &&
3491          "This is not an expansion!");
3492   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
3493
3494   if (!isSigned) {
3495     assert(Source.getValueType() == MVT::i64 &&
3496            "This only works for 64-bit -> FP");
3497     // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
3498     // incoming integer is set.  To handle this, we dynamically test to see if
3499     // it is set, and, if so, add a fudge factor.
3500     SDOperand Lo, Hi;
3501     ExpandOp(Source, Lo, Hi);
3502
3503     // If this is unsigned, and not supported, first perform the conversion to
3504     // signed, then adjust the result if the sign bit is set.
3505     SDOperand SignedConv = ExpandIntToFP(true, DestTy,
3506                    DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), Lo, Hi));
3507
3508     SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi,
3509                                      DAG.getConstant(0, Hi.getValueType()),
3510                                      ISD::SETLT);
3511     SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
3512     SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
3513                                       SignSet, Four, Zero);
3514     uint64_t FF = 0x5f800000ULL;
3515     if (TLI.isLittleEndian()) FF <<= 32;
3516     static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
3517
3518     SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
3519     CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
3520     SDOperand FudgeInReg;
3521     if (DestTy == MVT::f32)
3522       FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
3523                                DAG.getSrcValue(NULL));
3524     else {
3525       assert(DestTy == MVT::f64 && "Unexpected conversion");
3526       FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
3527                                   CPIdx, DAG.getSrcValue(NULL), MVT::f32);
3528     }
3529     return DAG.getNode(ISD::FADD, DestTy, SignedConv, FudgeInReg);
3530   }
3531
3532   // Check to see if the target has a custom way to lower this.  If so, use it.
3533   switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) {
3534   default: assert(0 && "This action not implemented for this operation!");
3535   case TargetLowering::Legal:
3536   case TargetLowering::Expand:
3537     break;   // This case is handled below.
3538   case TargetLowering::Custom: {
3539     SDOperand NV = TLI.LowerOperation(DAG.getNode(ISD::SINT_TO_FP, DestTy,
3540                                                   Source), DAG);
3541     if (NV.Val)
3542       return LegalizeOp(NV);
3543     break;   // The target decided this was legal after all
3544   }
3545   }
3546
3547   // Expand the source, then glue it back together for the call.  We must expand
3548   // the source in case it is shared (this pass of legalize must traverse it).
3549   SDOperand SrcLo, SrcHi;
3550   ExpandOp(Source, SrcLo, SrcHi);
3551   Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi);
3552
3553   const char *FnName = 0;
3554   if (DestTy == MVT::f32)
3555     FnName = "__floatdisf";
3556   else {
3557     assert(DestTy == MVT::f64 && "Unknown fp value type!");
3558     FnName = "__floatdidf";
3559   }
3560
3561   Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source);
3562   SDOperand UnusedHiPart;
3563   return ExpandLibCall(FnName, Source.Val, UnusedHiPart);
3564 }
3565
3566 /// ExpandLegalINT_TO_FP - This function is responsible for legalizing a
3567 /// INT_TO_FP operation of the specified operand when the target requests that
3568 /// we expand it.  At this point, we know that the result and operand types are
3569 /// legal for the target.
3570 SDOperand SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned,
3571                                                      SDOperand Op0,
3572                                                      MVT::ValueType DestVT) {
3573   if (Op0.getValueType() == MVT::i32) {
3574     // simple 32-bit [signed|unsigned] integer to float/double expansion
3575
3576     // get the stack frame index of a 8 byte buffer
3577     MachineFunction &MF = DAG.getMachineFunction();
3578     int SSFI = MF.getFrameInfo()->CreateStackObject(8, 8);
3579     // get address of 8 byte buffer
3580     SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
3581     // word offset constant for Hi/Lo address computation
3582     SDOperand WordOff = DAG.getConstant(sizeof(int), TLI.getPointerTy());
3583     // set up Hi and Lo (into buffer) address based on endian
3584     SDOperand Hi = StackSlot;
3585     SDOperand Lo = DAG.getNode(ISD::ADD, TLI.getPointerTy(), StackSlot,WordOff);
3586     if (TLI.isLittleEndian())
3587       std::swap(Hi, Lo);
3588
3589     // if signed map to unsigned space
3590     SDOperand Op0Mapped;
3591     if (isSigned) {
3592       // constant used to invert sign bit (signed to unsigned mapping)
3593       SDOperand SignBit = DAG.getConstant(0x80000000u, MVT::i32);
3594       Op0Mapped = DAG.getNode(ISD::XOR, MVT::i32, Op0, SignBit);
3595     } else {
3596       Op0Mapped = Op0;
3597     }
3598     // store the lo of the constructed double - based on integer input
3599     SDOperand Store1 = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
3600                                    Op0Mapped, Lo, DAG.getSrcValue(NULL));
3601     // initial hi portion of constructed double
3602     SDOperand InitialHi = DAG.getConstant(0x43300000u, MVT::i32);
3603     // store the hi of the constructed double - biased exponent
3604     SDOperand Store2 = DAG.getNode(ISD::STORE, MVT::Other, Store1,
3605                                    InitialHi, Hi, DAG.getSrcValue(NULL));
3606     // load the constructed double
3607     SDOperand Load = DAG.getLoad(MVT::f64, Store2, StackSlot,
3608                                DAG.getSrcValue(NULL));
3609     // FP constant to bias correct the final result
3610     SDOperand Bias = DAG.getConstantFP(isSigned ?
3611                                             BitsToDouble(0x4330000080000000ULL)
3612                                           : BitsToDouble(0x4330000000000000ULL),
3613                                      MVT::f64);
3614     // subtract the bias
3615     SDOperand Sub = DAG.getNode(ISD::FSUB, MVT::f64, Load, Bias);
3616     // final result
3617     SDOperand Result;
3618     // handle final rounding
3619     if (DestVT == MVT::f64) {
3620       // do nothing
3621       Result = Sub;
3622     } else {
3623      // if f32 then cast to f32
3624       Result = DAG.getNode(ISD::FP_ROUND, MVT::f32, Sub);
3625     }
3626     return Result;
3627   }
3628   assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet");
3629   SDOperand Tmp1 = DAG.getNode(ISD::SINT_TO_FP, DestVT, Op0);
3630
3631   SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Op0,
3632                                    DAG.getConstant(0, Op0.getValueType()),
3633                                    ISD::SETLT);
3634   SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
3635   SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
3636                                     SignSet, Four, Zero);
3637
3638   // If the sign bit of the integer is set, the large number will be treated
3639   // as a negative number.  To counteract this, the dynamic code adds an
3640   // offset depending on the data type.
3641   uint64_t FF;
3642   switch (Op0.getValueType()) {
3643   default: assert(0 && "Unsupported integer type!");
3644   case MVT::i8 : FF = 0x43800000ULL; break;  // 2^8  (as a float)
3645   case MVT::i16: FF = 0x47800000ULL; break;  // 2^16 (as a float)
3646   case MVT::i32: FF = 0x4F800000ULL; break;  // 2^32 (as a float)
3647   case MVT::i64: FF = 0x5F800000ULL; break;  // 2^64 (as a float)
3648   }
3649   if (TLI.isLittleEndian()) FF <<= 32;
3650   static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
3651
3652   SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
3653   CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
3654   SDOperand FudgeInReg;
3655   if (DestVT == MVT::f32)
3656     FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
3657                              DAG.getSrcValue(NULL));
3658   else {
3659     assert(DestVT == MVT::f64 && "Unexpected conversion");
3660     FudgeInReg = LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, MVT::f64,
3661                                            DAG.getEntryNode(), CPIdx,
3662                                            DAG.getSrcValue(NULL), MVT::f32));
3663   }
3664
3665   return DAG.getNode(ISD::FADD, DestVT, Tmp1, FudgeInReg);
3666 }
3667
3668 /// PromoteLegalINT_TO_FP - This function is responsible for legalizing a
3669 /// *INT_TO_FP operation of the specified operand when the target requests that
3670 /// we promote it.  At this point, we know that the result and operand types are
3671 /// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP
3672 /// operation that takes a larger input.
3673 SDOperand SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDOperand LegalOp,
3674                                                       MVT::ValueType DestVT,
3675                                                       bool isSigned) {
3676   // First step, figure out the appropriate *INT_TO_FP operation to use.
3677   MVT::ValueType NewInTy = LegalOp.getValueType();
3678
3679   unsigned OpToUse = 0;
3680
3681   // Scan for the appropriate larger type to use.
3682   while (1) {
3683     NewInTy = (MVT::ValueType)(NewInTy+1);
3684     assert(MVT::isInteger(NewInTy) && "Ran out of possibilities!");
3685
3686     // If the target supports SINT_TO_FP of this type, use it.
3687     switch (TLI.getOperationAction(ISD::SINT_TO_FP, NewInTy)) {
3688       default: break;
3689       case TargetLowering::Legal:
3690         if (!TLI.isTypeLegal(NewInTy))
3691           break;  // Can't use this datatype.
3692         // FALL THROUGH.
3693       case TargetLowering::Custom:
3694         OpToUse = ISD::SINT_TO_FP;
3695         break;
3696     }
3697     if (OpToUse) break;
3698     if (isSigned) continue;
3699
3700     // If the target supports UINT_TO_FP of this type, use it.
3701     switch (TLI.getOperationAction(ISD::UINT_TO_FP, NewInTy)) {
3702       default: break;
3703       case TargetLowering::Legal:
3704         if (!TLI.isTypeLegal(NewInTy))
3705           break;  // Can't use this datatype.
3706         // FALL THROUGH.
3707       case TargetLowering::Custom:
3708         OpToUse = ISD::UINT_TO_FP;
3709         break;
3710     }
3711     if (OpToUse) break;
3712
3713     // Otherwise, try a larger type.
3714   }
3715
3716   // Okay, we found the operation and type to use.  Zero extend our input to the
3717   // desired type then run the operation on it.
3718   return DAG.getNode(OpToUse, DestVT,
3719                      DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND,
3720                                  NewInTy, LegalOp));
3721 }
3722
3723 /// PromoteLegalFP_TO_INT - This function is responsible for legalizing a
3724 /// FP_TO_*INT operation of the specified operand when the target requests that
3725 /// we promote it.  At this point, we know that the result and operand types are
3726 /// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT
3727 /// operation that returns a larger result.
3728 SDOperand SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDOperand LegalOp,
3729                                                       MVT::ValueType DestVT,
3730                                                       bool isSigned) {
3731   // First step, figure out the appropriate FP_TO*INT operation to use.
3732   MVT::ValueType NewOutTy = DestVT;
3733
3734   unsigned OpToUse = 0;
3735
3736   // Scan for the appropriate larger type to use.
3737   while (1) {
3738     NewOutTy = (MVT::ValueType)(NewOutTy+1);
3739     assert(MVT::isInteger(NewOutTy) && "Ran out of possibilities!");
3740
3741     // If the target supports FP_TO_SINT returning this type, use it.
3742     switch (TLI.getOperationAction(ISD::FP_TO_SINT, NewOutTy)) {
3743     default: break;
3744     case TargetLowering::Legal:
3745       if (!TLI.isTypeLegal(NewOutTy))
3746         break;  // Can't use this datatype.
3747       // FALL THROUGH.
3748     case TargetLowering::Custom:
3749       OpToUse = ISD::FP_TO_SINT;
3750       break;
3751     }
3752     if (OpToUse) break;
3753
3754     // If the target supports FP_TO_UINT of this type, use it.
3755     switch (TLI.getOperationAction(ISD::FP_TO_UINT, NewOutTy)) {
3756     default: break;
3757     case TargetLowering::Legal:
3758       if (!TLI.isTypeLegal(NewOutTy))
3759         break;  // Can't use this datatype.
3760       // FALL THROUGH.
3761     case TargetLowering::Custom:
3762       OpToUse = ISD::FP_TO_UINT;
3763       break;
3764     }
3765     if (OpToUse) break;
3766
3767     // Otherwise, try a larger type.
3768   }
3769
3770   // Okay, we found the operation and type to use.  Truncate the result of the
3771   // extended FP_TO_*INT operation to the desired size.
3772   return DAG.getNode(ISD::TRUNCATE, DestVT,
3773                      DAG.getNode(OpToUse, NewOutTy, LegalOp));
3774 }
3775
3776 /// ExpandBSWAP - Open code the operations for BSWAP of the specified operation.
3777 ///
3778 SDOperand SelectionDAGLegalize::ExpandBSWAP(SDOperand Op) {
3779   MVT::ValueType VT = Op.getValueType();
3780   MVT::ValueType SHVT = TLI.getShiftAmountTy();
3781   SDOperand Tmp1, Tmp2, Tmp3, Tmp4, Tmp5, Tmp6, Tmp7, Tmp8;
3782   switch (VT) {
3783   default: assert(0 && "Unhandled Expand type in BSWAP!"); abort();
3784   case MVT::i16:
3785     Tmp2 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
3786     Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
3787     return DAG.getNode(ISD::OR, VT, Tmp1, Tmp2);
3788   case MVT::i32:
3789     Tmp4 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(24, SHVT));
3790     Tmp3 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
3791     Tmp2 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
3792     Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(24, SHVT));
3793     Tmp3 = DAG.getNode(ISD::AND, VT, Tmp3, DAG.getConstant(0xFF0000, VT));
3794     Tmp2 = DAG.getNode(ISD::AND, VT, Tmp2, DAG.getConstant(0xFF00, VT));
3795     Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp3);
3796     Tmp2 = DAG.getNode(ISD::OR, VT, Tmp2, Tmp1);
3797     return DAG.getNode(ISD::OR, VT, Tmp4, Tmp2);
3798   case MVT::i64:
3799     Tmp8 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(56, SHVT));
3800     Tmp7 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(40, SHVT));
3801     Tmp6 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(24, SHVT));
3802     Tmp5 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
3803     Tmp4 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
3804     Tmp3 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(24, SHVT));
3805     Tmp2 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(40, SHVT));
3806     Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(56, SHVT));
3807     Tmp7 = DAG.getNode(ISD::AND, VT, Tmp7, DAG.getConstant(255ULL<<48, VT));
3808     Tmp6 = DAG.getNode(ISD::AND, VT, Tmp6, DAG.getConstant(255ULL<<40, VT));
3809     Tmp5 = DAG.getNode(ISD::AND, VT, Tmp5, DAG.getConstant(255ULL<<32, VT));
3810     Tmp4 = DAG.getNode(ISD::AND, VT, Tmp4, DAG.getConstant(255ULL<<24, VT));
3811     Tmp3 = DAG.getNode(ISD::AND, VT, Tmp3, DAG.getConstant(255ULL<<16, VT));
3812     Tmp2 = DAG.getNode(ISD::AND, VT, Tmp2, DAG.getConstant(255ULL<<8 , VT));
3813     Tmp8 = DAG.getNode(ISD::OR, VT, Tmp8, Tmp7);
3814     Tmp6 = DAG.getNode(ISD::OR, VT, Tmp6, Tmp5);
3815     Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp3);
3816     Tmp2 = DAG.getNode(ISD::OR, VT, Tmp2, Tmp1);
3817     Tmp8 = DAG.getNode(ISD::OR, VT, Tmp8, Tmp6);
3818     Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp2);
3819     return DAG.getNode(ISD::OR, VT, Tmp8, Tmp4);
3820   }
3821 }
3822
3823 /// ExpandBitCount - Expand the specified bitcount instruction into operations.
3824 ///
3825 SDOperand SelectionDAGLegalize::ExpandBitCount(unsigned Opc, SDOperand Op) {
3826   switch (Opc) {
3827   default: assert(0 && "Cannot expand this yet!");
3828   case ISD::CTPOP: {
3829     static const uint64_t mask[6] = {
3830       0x5555555555555555ULL, 0x3333333333333333ULL,
3831       0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
3832       0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
3833     };
3834     MVT::ValueType VT = Op.getValueType();
3835     MVT::ValueType ShVT = TLI.getShiftAmountTy();
3836     unsigned len = getSizeInBits(VT);
3837     for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
3838       //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
3839       SDOperand Tmp2 = DAG.getConstant(mask[i], VT);
3840       SDOperand Tmp3 = DAG.getConstant(1ULL << i, ShVT);
3841       Op = DAG.getNode(ISD::ADD, VT, DAG.getNode(ISD::AND, VT, Op, Tmp2),
3842                        DAG.getNode(ISD::AND, VT,
3843                                    DAG.getNode(ISD::SRL, VT, Op, Tmp3),Tmp2));
3844     }
3845     return Op;
3846   }
3847   case ISD::CTLZ: {
3848     // for now, we do this:
3849     // x = x | (x >> 1);
3850     // x = x | (x >> 2);
3851     // ...
3852     // x = x | (x >>16);
3853     // x = x | (x >>32); // for 64-bit input
3854     // return popcount(~x);
3855     //
3856     // but see also: http://www.hackersdelight.org/HDcode/nlz.cc
3857     MVT::ValueType VT = Op.getValueType();
3858     MVT::ValueType ShVT = TLI.getShiftAmountTy();
3859     unsigned len = getSizeInBits(VT);
3860     for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
3861       SDOperand Tmp3 = DAG.getConstant(1ULL << i, ShVT);
3862       Op = DAG.getNode(ISD::OR, VT, Op, DAG.getNode(ISD::SRL, VT, Op, Tmp3));
3863     }
3864     Op = DAG.getNode(ISD::XOR, VT, Op, DAG.getConstant(~0ULL, VT));
3865     return DAG.getNode(ISD::CTPOP, VT, Op);
3866   }
3867   case ISD::CTTZ: {
3868     // for now, we use: { return popcount(~x & (x - 1)); }
3869     // unless the target has ctlz but not ctpop, in which case we use:
3870     // { return 32 - nlz(~x & (x-1)); }
3871     // see also http://www.hackersdelight.org/HDcode/ntz.cc
3872     MVT::ValueType VT = Op.getValueType();
3873     SDOperand Tmp2 = DAG.getConstant(~0ULL, VT);
3874     SDOperand Tmp3 = DAG.getNode(ISD::AND, VT,
3875                        DAG.getNode(ISD::XOR, VT, Op, Tmp2),
3876                        DAG.getNode(ISD::SUB, VT, Op, DAG.getConstant(1, VT)));
3877     // If ISD::CTLZ is legal and CTPOP isn't, then do that instead.
3878     if (!TLI.isOperationLegal(ISD::CTPOP, VT) &&
3879         TLI.isOperationLegal(ISD::CTLZ, VT))
3880       return DAG.getNode(ISD::SUB, VT,
3881                          DAG.getConstant(getSizeInBits(VT), VT),
3882                          DAG.getNode(ISD::CTLZ, VT, Tmp3));
3883     return DAG.getNode(ISD::CTPOP, VT, Tmp3);
3884   }
3885   }
3886 }
3887
3888
3889 /// ExpandOp - Expand the specified SDOperand into its two component pieces
3890 /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
3891 /// LegalizeNodes map is filled in for any results that are not expanded, the
3892 /// ExpandedNodes map is filled in for any results that are expanded, and the
3893 /// Lo/Hi values are returned.
3894 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
3895   MVT::ValueType VT = Op.getValueType();
3896   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
3897   SDNode *Node = Op.Val;
3898   assert(getTypeAction(VT) == Expand && "Not an expanded type!");
3899   assert((MVT::isInteger(VT) || VT == MVT::Vector) &&
3900          "Cannot expand FP values!");
3901   assert(((MVT::isInteger(NVT) && NVT < VT) || VT == MVT::Vector) &&
3902          "Cannot expand to FP value or to larger int value!");
3903
3904   // See if we already expanded it.
3905   std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
3906     = ExpandedNodes.find(Op);
3907   if (I != ExpandedNodes.end()) {
3908     Lo = I->second.first;
3909     Hi = I->second.second;
3910     return;
3911   }
3912
3913   switch (Node->getOpcode()) {
3914   case ISD::CopyFromReg:
3915     assert(0 && "CopyFromReg must be legal!");
3916   default:
3917     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
3918     assert(0 && "Do not know how to expand this operator!");
3919     abort();
3920   case ISD::UNDEF:
3921     Lo = DAG.getNode(ISD::UNDEF, NVT);
3922     Hi = DAG.getNode(ISD::UNDEF, NVT);
3923     break;
3924   case ISD::Constant: {
3925     uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
3926     Lo = DAG.getConstant(Cst, NVT);
3927     Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
3928     break;
3929   }
3930   case ISD::BUILD_PAIR:
3931     // Return the operands.
3932     Lo = Node->getOperand(0);
3933     Hi = Node->getOperand(1);
3934     break;
3935
3936   case ISD::SIGN_EXTEND_INREG:
3937     ExpandOp(Node->getOperand(0), Lo, Hi);
3938     // Sign extend the lo-part.
3939     Hi = DAG.getNode(ISD::SRA, NVT, Lo,
3940                      DAG.getConstant(MVT::getSizeInBits(NVT)-1,
3941                                      TLI.getShiftAmountTy()));
3942     // sext_inreg the low part if needed.
3943     Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Lo, Node->getOperand(1));
3944     break;
3945
3946   case ISD::BSWAP: {
3947     ExpandOp(Node->getOperand(0), Lo, Hi);
3948     SDOperand TempLo = DAG.getNode(ISD::BSWAP, NVT, Hi);
3949     Hi = DAG.getNode(ISD::BSWAP, NVT, Lo);
3950     Lo = TempLo;
3951     break;
3952   }
3953
3954   case ISD::CTPOP:
3955     ExpandOp(Node->getOperand(0), Lo, Hi);
3956     Lo = DAG.getNode(ISD::ADD, NVT,          // ctpop(HL) -> ctpop(H)+ctpop(L)
3957                      DAG.getNode(ISD::CTPOP, NVT, Lo),
3958                      DAG.getNode(ISD::CTPOP, NVT, Hi));
3959     Hi = DAG.getConstant(0, NVT);
3960     break;
3961
3962   case ISD::CTLZ: {
3963     // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32)
3964     ExpandOp(Node->getOperand(0), Lo, Hi);
3965     SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
3966     SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
3967     SDOperand TopNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), HLZ, BitsC,
3968                                         ISD::SETNE);
3969     SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo);
3970     LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC);
3971
3972     Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart);
3973     Hi = DAG.getConstant(0, NVT);
3974     break;
3975   }
3976
3977   case ISD::CTTZ: {
3978     // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32)
3979     ExpandOp(Node->getOperand(0), Lo, Hi);
3980     SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
3981     SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
3982     SDOperand BotNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), LTZ, BitsC,
3983                                         ISD::SETNE);
3984     SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi);
3985     HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC);
3986
3987     Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart);
3988     Hi = DAG.getConstant(0, NVT);
3989     break;
3990   }
3991
3992   case ISD::VAARG: {
3993     SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
3994     SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
3995     Lo = DAG.getVAArg(NVT, Ch, Ptr, Node->getOperand(2));
3996     Hi = DAG.getVAArg(NVT, Lo.getValue(1), Ptr, Node->getOperand(2));
3997
3998     // Remember that we legalized the chain.
3999     Hi = LegalizeOp(Hi);
4000     AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
4001     if (!TLI.isLittleEndian())
4002       std::swap(Lo, Hi);
4003     break;
4004   }
4005
4006   case ISD::LOAD: {
4007     SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
4008     SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
4009     Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
4010
4011     // Increment the pointer to the other half.
4012     unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
4013     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
4014                       getIntPtrConstant(IncrementSize));
4015     // FIXME: This creates a bogus srcvalue!
4016     Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
4017
4018     // Build a factor node to remember that this load is independent of the
4019     // other one.
4020     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
4021                                Hi.getValue(1));
4022
4023     // Remember that we legalized the chain.
4024     AddLegalizedOperand(Op.getValue(1), LegalizeOp(TF));
4025     if (!TLI.isLittleEndian())
4026       std::swap(Lo, Hi);
4027     break;
4028   }
4029   case ISD::AND:
4030   case ISD::OR:
4031   case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
4032     SDOperand LL, LH, RL, RH;
4033     ExpandOp(Node->getOperand(0), LL, LH);
4034     ExpandOp(Node->getOperand(1), RL, RH);
4035     Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
4036     Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
4037     break;
4038   }
4039   case ISD::SELECT: {
4040     SDOperand LL, LH, RL, RH;
4041     ExpandOp(Node->getOperand(1), LL, LH);
4042     ExpandOp(Node->getOperand(2), RL, RH);
4043     Lo = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), LL, RL);
4044     Hi = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), LH, RH);
4045     break;
4046   }
4047   case ISD::SELECT_CC: {
4048     SDOperand TL, TH, FL, FH;
4049     ExpandOp(Node->getOperand(2), TL, TH);
4050     ExpandOp(Node->getOperand(3), FL, FH);
4051     Lo = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
4052                      Node->getOperand(1), TL, FL, Node->getOperand(4));
4053     Hi = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
4054                      Node->getOperand(1), TH, FH, Node->getOperand(4));
4055     break;
4056   }
4057   case ISD::SEXTLOAD: {
4058     SDOperand Chain = Node->getOperand(0);
4059     SDOperand Ptr   = Node->getOperand(1);
4060     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
4061
4062     if (EVT == NVT)
4063       Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2));
4064     else
4065       Lo = DAG.getExtLoad(ISD::SEXTLOAD, NVT, Chain, Ptr, Node->getOperand(2),
4066                           EVT);
4067
4068     // Remember that we legalized the chain.
4069     AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
4070
4071     // The high part is obtained by SRA'ing all but one of the bits of the lo
4072     // part.
4073     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
4074     Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1,
4075                                                        TLI.getShiftAmountTy()));
4076     break;
4077   }
4078   case ISD::ZEXTLOAD: {
4079     SDOperand Chain = Node->getOperand(0);
4080     SDOperand Ptr   = Node->getOperand(1);
4081     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
4082
4083     if (EVT == NVT)
4084       Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2));
4085     else
4086       Lo = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Chain, Ptr, Node->getOperand(2),
4087                           EVT);
4088
4089     // Remember that we legalized the chain.
4090     AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
4091
4092     // The high part is just a zero.
4093     Hi = DAG.getConstant(0, NVT);
4094     break;
4095   }
4096   case ISD::EXTLOAD: {
4097     SDOperand Chain = Node->getOperand(0);
4098     SDOperand Ptr   = Node->getOperand(1);
4099     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
4100
4101     if (EVT == NVT)
4102       Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2));
4103     else
4104       Lo = DAG.getExtLoad(ISD::EXTLOAD, NVT, Chain, Ptr, Node->getOperand(2),
4105                           EVT);
4106
4107     // Remember that we legalized the chain.
4108     AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
4109
4110     // The high part is undefined.
4111     Hi = DAG.getNode(ISD::UNDEF, NVT);
4112     break;
4113   }
4114   case ISD::ANY_EXTEND:
4115     // The low part is any extension of the input (which degenerates to a copy).
4116     Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, Node->getOperand(0));
4117     // The high part is undefined.
4118     Hi = DAG.getNode(ISD::UNDEF, NVT);
4119     break;
4120   case ISD::SIGN_EXTEND: {
4121     // The low part is just a sign extension of the input (which degenerates to
4122     // a copy).
4123     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, Node->getOperand(0));
4124
4125     // The high part is obtained by SRA'ing all but one of the bits of the lo
4126     // part.
4127     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
4128     Hi = DAG.getNode(ISD::SRA, NVT, Lo,
4129                      DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
4130     break;
4131   }
4132   case ISD::ZERO_EXTEND:
4133     // The low part is just a zero extension of the input (which degenerates to
4134     // a copy).
4135     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, Node->getOperand(0));
4136
4137     // The high part is just a zero.
4138     Hi = DAG.getConstant(0, NVT);
4139     break;
4140
4141   case ISD::BIT_CONVERT: {
4142     SDOperand Tmp = ExpandBIT_CONVERT(Node->getValueType(0),
4143                                       Node->getOperand(0));
4144     ExpandOp(Tmp, Lo, Hi);
4145     break;
4146   }
4147
4148   case ISD::READCYCLECOUNTER:
4149     assert(TLI.getOperationAction(ISD::READCYCLECOUNTER, VT) ==
4150                  TargetLowering::Custom &&
4151            "Must custom expand ReadCycleCounter");
4152     Lo = TLI.LowerOperation(Op, DAG);
4153     assert(Lo.Val && "Node must be custom expanded!");
4154     Hi = Lo.getValue(1);
4155     AddLegalizedOperand(SDOperand(Node, 1), // Remember we legalized the chain.
4156                         LegalizeOp(Lo.getValue(2)));
4157     break;
4158
4159     // These operators cannot be expanded directly, emit them as calls to
4160     // library functions.
4161   case ISD::FP_TO_SINT:
4162     if (TLI.getOperationAction(ISD::FP_TO_SINT, VT) == TargetLowering::Custom) {
4163       SDOperand Op;
4164       switch (getTypeAction(Node->getOperand(0).getValueType())) {
4165       case Expand: assert(0 && "cannot expand FP!");
4166       case Legal:   Op = LegalizeOp(Node->getOperand(0)); break;
4167       case Promote: Op = PromoteOp (Node->getOperand(0)); break;
4168       }
4169
4170       Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_SINT, VT, Op), DAG);
4171
4172       // Now that the custom expander is done, expand the result, which is still
4173       // VT.
4174       if (Op.Val) {
4175         ExpandOp(Op, Lo, Hi);
4176         break;
4177       }
4178     }
4179
4180     if (Node->getOperand(0).getValueType() == MVT::f32)
4181       Lo = ExpandLibCall("__fixsfdi", Node, Hi);
4182     else
4183       Lo = ExpandLibCall("__fixdfdi", Node, Hi);
4184     break;
4185
4186   case ISD::FP_TO_UINT:
4187     if (TLI.getOperationAction(ISD::FP_TO_UINT, VT) == TargetLowering::Custom) {
4188       SDOperand Op;
4189       switch (getTypeAction(Node->getOperand(0).getValueType())) {
4190         case Expand: assert(0 && "cannot expand FP!");
4191         case Legal:   Op = LegalizeOp(Node->getOperand(0)); break;
4192         case Promote: Op = PromoteOp (Node->getOperand(0)); break;
4193       }
4194
4195       Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_UINT, VT, Op), DAG);
4196
4197       // Now that the custom expander is done, expand the result.
4198       if (Op.Val) {
4199         ExpandOp(Op, Lo, Hi);
4200         break;
4201       }
4202     }
4203
4204     if (Node->getOperand(0).getValueType() == MVT::f32)
4205       Lo = ExpandLibCall("__fixunssfdi", Node, Hi);
4206     else
4207       Lo = ExpandLibCall("__fixunsdfdi", Node, Hi);
4208     break;
4209
4210   case ISD::SHL: {
4211     // If the target wants custom lowering, do so.
4212     SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
4213     if (TLI.getOperationAction(ISD::SHL, VT) == TargetLowering::Custom) {
4214       SDOperand Op = DAG.getNode(ISD::SHL, VT, Node->getOperand(0), ShiftAmt);
4215       Op = TLI.LowerOperation(Op, DAG);
4216       if (Op.Val) {
4217         // Now that the custom expander is done, expand the result, which is
4218         // still VT.
4219         ExpandOp(Op, Lo, Hi);
4220         break;
4221       }
4222     }
4223
4224     // If we can emit an efficient shift operation, do so now.
4225     if (ExpandShift(ISD::SHL, Node->getOperand(0), ShiftAmt, Lo, Hi))
4226       break;
4227
4228     // If this target supports SHL_PARTS, use it.
4229     TargetLowering::LegalizeAction Action =
4230       TLI.getOperationAction(ISD::SHL_PARTS, NVT);
4231     if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
4232         Action == TargetLowering::Custom) {
4233       ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
4234       break;
4235     }
4236
4237     // Otherwise, emit a libcall.
4238     Lo = ExpandLibCall("__ashldi3", Node, Hi);
4239     break;
4240   }
4241
4242   case ISD::SRA: {
4243     // If the target wants custom lowering, do so.
4244     SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
4245     if (TLI.getOperationAction(ISD::SRA, VT) == TargetLowering::Custom) {
4246       SDOperand Op = DAG.getNode(ISD::SRA, VT, Node->getOperand(0), ShiftAmt);
4247       Op = TLI.LowerOperation(Op, DAG);
4248       if (Op.Val) {
4249         // Now that the custom expander is done, expand the result, which is
4250         // still VT.
4251         ExpandOp(Op, Lo, Hi);
4252         break;
4253       }
4254     }
4255
4256     // If we can emit an efficient shift operation, do so now.
4257     if (ExpandShift(ISD::SRA, Node->getOperand(0), ShiftAmt, Lo, Hi))
4258       break;
4259
4260     // If this target supports SRA_PARTS, use it.
4261     TargetLowering::LegalizeAction Action =
4262       TLI.getOperationAction(ISD::SRA_PARTS, NVT);
4263     if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
4264         Action == TargetLowering::Custom) {
4265       ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
4266       break;
4267     }
4268
4269     // Otherwise, emit a libcall.
4270     Lo = ExpandLibCall("__ashrdi3", Node, Hi);
4271     break;
4272   }
4273
4274   case ISD::SRL: {
4275     // If the target wants custom lowering, do so.
4276     SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
4277     if (TLI.getOperationAction(ISD::SRL, VT) == TargetLowering::Custom) {
4278       SDOperand Op = DAG.getNode(ISD::SRL, VT, Node->getOperand(0), ShiftAmt);
4279       Op = TLI.LowerOperation(Op, DAG);
4280       if (Op.Val) {
4281         // Now that the custom expander is done, expand the result, which is
4282         // still VT.
4283         ExpandOp(Op, Lo, Hi);
4284         break;
4285       }
4286     }
4287
4288     // If we can emit an efficient shift operation, do so now.
4289     if (ExpandShift(ISD::SRL, Node->getOperand(0), ShiftAmt, Lo, Hi))
4290       break;
4291
4292     // If this target supports SRL_PARTS, use it.
4293     TargetLowering::LegalizeAction Action =
4294       TLI.getOperationAction(ISD::SRL_PARTS, NVT);
4295     if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
4296         Action == TargetLowering::Custom) {
4297       ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
4298       break;
4299     }
4300
4301     // Otherwise, emit a libcall.
4302     Lo = ExpandLibCall("__lshrdi3", Node, Hi);
4303     break;
4304   }
4305
4306   case ISD::ADD:
4307   case ISD::SUB: {
4308     // If the target wants to custom expand this, let them.
4309     if (TLI.getOperationAction(Node->getOpcode(), VT) ==
4310             TargetLowering::Custom) {
4311       Op = TLI.LowerOperation(Op, DAG);
4312       if (Op.Val) {
4313         ExpandOp(Op, Lo, Hi);
4314         break;
4315       }
4316     }
4317
4318     // Expand the subcomponents.
4319     SDOperand LHSL, LHSH, RHSL, RHSH;
4320     ExpandOp(Node->getOperand(0), LHSL, LHSH);
4321     ExpandOp(Node->getOperand(1), RHSL, RHSH);
4322     std::vector<MVT::ValueType> VTs;
4323     std::vector<SDOperand> LoOps, HiOps;
4324     VTs.push_back(LHSL.getValueType());
4325     VTs.push_back(MVT::Flag);
4326     LoOps.push_back(LHSL);
4327     LoOps.push_back(RHSL);
4328     HiOps.push_back(LHSH);
4329     HiOps.push_back(RHSH);
4330     if (Node->getOpcode() == ISD::ADD) {
4331       Lo = DAG.getNode(ISD::ADDC, VTs, LoOps);
4332       HiOps.push_back(Lo.getValue(1));
4333       Hi = DAG.getNode(ISD::ADDE, VTs, HiOps);
4334     } else {
4335       Lo = DAG.getNode(ISD::SUBC, VTs, LoOps);
4336       HiOps.push_back(Lo.getValue(1));
4337       Hi = DAG.getNode(ISD::SUBE, VTs, HiOps);
4338     }
4339     break;
4340   }
4341   case ISD::MUL: {
4342     if (TLI.isOperationLegal(ISD::MULHU, NVT)) {
4343       SDOperand LL, LH, RL, RH;
4344       ExpandOp(Node->getOperand(0), LL, LH);
4345       ExpandOp(Node->getOperand(1), RL, RH);
4346       unsigned SH = MVT::getSizeInBits(RH.getValueType())-1;
4347       // MULHS implicitly sign extends its inputs.  Check to see if ExpandOp
4348       // extended the sign bit of the low half through the upper half, and if so
4349       // emit a MULHS instead of the alternate sequence that is valid for any
4350       // i64 x i64 multiply.
4351       if (TLI.isOperationLegal(ISD::MULHS, NVT) &&
4352           // is RH an extension of the sign bit of RL?
4353           RH.getOpcode() == ISD::SRA && RH.getOperand(0) == RL &&
4354           RH.getOperand(1).getOpcode() == ISD::Constant &&
4355           cast<ConstantSDNode>(RH.getOperand(1))->getValue() == SH &&
4356           // is LH an extension of the sign bit of LL?
4357           LH.getOpcode() == ISD::SRA && LH.getOperand(0) == LL &&
4358           LH.getOperand(1).getOpcode() == ISD::Constant &&
4359           cast<ConstantSDNode>(LH.getOperand(1))->getValue() == SH) {
4360         Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL);
4361       } else {
4362         Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
4363         RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
4364         LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
4365         Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
4366         Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
4367       }
4368       Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
4369     } else {
4370       Lo = ExpandLibCall("__muldi3" , Node, Hi);
4371     }
4372     break;
4373   }
4374   case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break;
4375   case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break;
4376   case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break;
4377   case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break;
4378   }
4379
4380   // Make sure the resultant values have been legalized themselves, unless this
4381   // is a type that requires multi-step expansion.
4382   if (getTypeAction(NVT) != Expand && NVT != MVT::isVoid) {
4383     Lo = LegalizeOp(Lo);
4384     Hi = LegalizeOp(Hi);
4385   }
4386
4387   // Remember in a map if the values will be reused later.
4388   bool isNew =
4389     ExpandedNodes.insert(std::make_pair(Op, std::make_pair(Lo, Hi))).second;
4390   assert(isNew && "Value already expanded?!?");
4391 }
4392
4393 /// SplitVectorOp - Given an operand of MVT::Vector type, break it down into
4394 /// two smaller values of MVT::Vector type.
4395 void SelectionDAGLegalize::SplitVectorOp(SDOperand Op, SDOperand &Lo,
4396                                          SDOperand &Hi) {
4397   assert(Op.getValueType() == MVT::Vector && "Cannot split non-vector type!");
4398   SDNode *Node = Op.Val;
4399   unsigned NumElements = cast<ConstantSDNode>(*(Node->op_end()-2))->getValue();
4400   assert(NumElements > 1 && "Cannot split a single element vector!");
4401   unsigned NewNumElts = NumElements/2;
4402   SDOperand NewNumEltsNode = DAG.getConstant(NewNumElts, MVT::i32);
4403   SDOperand TypeNode = *(Node->op_end()-1);
4404
4405   // See if we already split it.
4406   std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
4407     = SplitNodes.find(Op);
4408   if (I != SplitNodes.end()) {
4409     Lo = I->second.first;
4410     Hi = I->second.second;
4411     return;
4412   }
4413
4414   switch (Node->getOpcode()) {
4415   default: Node->dump(); assert(0 && "Unknown vector operation!");
4416   case ISD::VBUILD_VECTOR: {
4417     std::vector<SDOperand> LoOps(Node->op_begin(), Node->op_begin()+NewNumElts);
4418     LoOps.push_back(NewNumEltsNode);
4419     LoOps.push_back(TypeNode);
4420     Lo = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, LoOps);
4421
4422     std::vector<SDOperand> HiOps(Node->op_begin()+NewNumElts, Node->op_end()-2);
4423     HiOps.push_back(NewNumEltsNode);
4424     HiOps.push_back(TypeNode);
4425     Hi = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, HiOps);
4426     break;
4427   }
4428   case ISD::VADD:
4429   case ISD::VSUB:
4430   case ISD::VMUL:
4431   case ISD::VSDIV:
4432   case ISD::VUDIV:
4433   case ISD::VAND:
4434   case ISD::VOR:
4435   case ISD::VXOR: {
4436     SDOperand LL, LH, RL, RH;
4437     SplitVectorOp(Node->getOperand(0), LL, LH);
4438     SplitVectorOp(Node->getOperand(1), RL, RH);
4439
4440     Lo = DAG.getNode(Node->getOpcode(), MVT::Vector, LL, RL,
4441                      NewNumEltsNode, TypeNode);
4442     Hi = DAG.getNode(Node->getOpcode(), MVT::Vector, LH, RH,
4443                      NewNumEltsNode, TypeNode);
4444     break;
4445   }
4446   case ISD::VLOAD: {
4447     SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
4448     SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
4449     MVT::ValueType EVT = cast<VTSDNode>(TypeNode)->getVT();
4450
4451     Lo = DAG.getVecLoad(NewNumElts, EVT, Ch, Ptr, Node->getOperand(2));
4452     unsigned IncrementSize = NewNumElts * MVT::getSizeInBits(EVT)/8;
4453     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
4454                       getIntPtrConstant(IncrementSize));
4455     // FIXME: This creates a bogus srcvalue!
4456     Hi = DAG.getVecLoad(NewNumElts, EVT, Ch, Ptr, Node->getOperand(2));
4457
4458     // Build a factor node to remember that this load is independent of the
4459     // other one.
4460     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
4461                                Hi.getValue(1));
4462
4463     // Remember that we legalized the chain.
4464     AddLegalizedOperand(Op.getValue(1), LegalizeOp(TF));
4465     break;
4466   }
4467   case ISD::VBIT_CONVERT: {
4468     // We know the result is a vector.  The input may be either a vector or a
4469     // scalar value.
4470     if (Op.getOperand(0).getValueType() != MVT::Vector) {
4471       // Lower to a store/load.  FIXME: this could be improved probably.
4472       SDOperand Ptr = CreateStackTemporary(Op.getOperand(0).getValueType());
4473
4474       SDOperand St = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
4475                                  Op.getOperand(0), Ptr, DAG.getSrcValue(0));
4476       MVT::ValueType EVT = cast<VTSDNode>(TypeNode)->getVT();
4477       St = DAG.getVecLoad(NumElements, EVT, St, Ptr, DAG.getSrcValue(0));
4478       SplitVectorOp(St, Lo, Hi);
4479     } else {
4480       // If the input is a vector type, we have to either scalarize it, pack it
4481       // or convert it based on whether the input vector type is legal.
4482       SDNode *InVal = Node->getOperand(0).Val;
4483       unsigned NumElems =
4484         cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
4485       MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
4486
4487       // If the input is from a single element vector, scalarize the vector,
4488       // then treat like a scalar.
4489       if (NumElems == 1) {
4490         SDOperand Scalar = PackVectorOp(Op.getOperand(0), EVT);
4491         Scalar = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Scalar,
4492                              Op.getOperand(1), Op.getOperand(2));
4493         SplitVectorOp(Scalar, Lo, Hi);
4494       } else {
4495         // Split the input vector.
4496         SplitVectorOp(Op.getOperand(0), Lo, Hi);
4497
4498         // Convert each of the pieces now.
4499         Lo = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Lo,
4500                          NewNumEltsNode, TypeNode);
4501         Hi = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Hi,
4502                          NewNumEltsNode, TypeNode);
4503       }
4504       break;
4505     }
4506   }
4507   }
4508
4509   // Remember in a map if the values will be reused later.
4510   bool isNew =
4511     SplitNodes.insert(std::make_pair(Op, std::make_pair(Lo, Hi))).second;
4512   assert(isNew && "Value already expanded?!?");
4513 }
4514
4515
4516 /// PackVectorOp - Given an operand of MVT::Vector type, convert it into the
4517 /// equivalent operation that returns a scalar (e.g. F32) or packed value
4518 /// (e.g. MVT::V4F32).  When this is called, we know that PackedVT is the right
4519 /// type for the result.
4520 SDOperand SelectionDAGLegalize::PackVectorOp(SDOperand Op,
4521                                              MVT::ValueType NewVT) {
4522   assert(Op.getValueType() == MVT::Vector && "Bad PackVectorOp invocation!");
4523   SDNode *Node = Op.Val;
4524
4525   // See if we already packed it.
4526   std::map<SDOperand, SDOperand>::iterator I = PackedNodes.find(Op);
4527   if (I != PackedNodes.end()) return I->second;
4528
4529   SDOperand Result;
4530   switch (Node->getOpcode()) {
4531   default:
4532     Node->dump(); std::cerr << "\n";
4533     assert(0 && "Unknown vector operation in PackVectorOp!");
4534   case ISD::VADD:
4535   case ISD::VSUB:
4536   case ISD::VMUL:
4537   case ISD::VSDIV:
4538   case ISD::VUDIV:
4539   case ISD::VAND:
4540   case ISD::VOR:
4541   case ISD::VXOR:
4542     Result = DAG.getNode(getScalarizedOpcode(Node->getOpcode(), NewVT),
4543                          NewVT,
4544                          PackVectorOp(Node->getOperand(0), NewVT),
4545                          PackVectorOp(Node->getOperand(1), NewVT));
4546     break;
4547   case ISD::VLOAD: {
4548     SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
4549     SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
4550
4551     Result = DAG.getLoad(NewVT, Ch, Ptr, Node->getOperand(2));
4552
4553     // Remember that we legalized the chain.
4554     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
4555     break;
4556   }
4557   case ISD::VBUILD_VECTOR:
4558     if (Node->getOperand(0).getValueType() == NewVT) {
4559       // Returning a scalar?
4560       Result = Node->getOperand(0);
4561     } else {
4562       // Returning a BUILD_VECTOR?
4563       std::vector<SDOperand> Ops(Node->op_begin(), Node->op_end()-2);
4564       Result = DAG.getNode(ISD::BUILD_VECTOR, NewVT, Ops);
4565     }
4566     break;
4567   case ISD::VINSERT_VECTOR_ELT:
4568     if (!MVT::isVector(NewVT)) {
4569       // Returning a scalar?  Must be the inserted element.
4570       Result = Node->getOperand(1);
4571     } else {
4572       Result = DAG.getNode(ISD::INSERT_VECTOR_ELT, NewVT,
4573                            PackVectorOp(Node->getOperand(0), NewVT),
4574                            Node->getOperand(1), Node->getOperand(2));
4575     }
4576     break;
4577   case ISD::VVECTOR_SHUFFLE:
4578     if (!MVT::isVector(NewVT)) {
4579       // Returning a scalar?  Figure out if it is the LHS or RHS and return it.
4580       SDOperand EltNum = Node->getOperand(2).getOperand(0);
4581       if (cast<ConstantSDNode>(EltNum)->getValue())
4582         Result = PackVectorOp(Node->getOperand(1), NewVT);
4583       else
4584         Result = PackVectorOp(Node->getOperand(0), NewVT);
4585     } else {
4586       // Otherwise, return a VECTOR_SHUFFLE node.  First convert the index
4587       // vector from a VBUILD_VECTOR to a BUILD_VECTOR.
4588       std::vector<SDOperand> BuildVecIdx(Node->getOperand(2).Val->op_begin(),
4589                                          Node->getOperand(2).Val->op_end()-2);
4590       MVT::ValueType BVT = MVT::getIntVectorWithNumElements(BuildVecIdx.size());
4591       SDOperand BV = DAG.getNode(ISD::BUILD_VECTOR, BVT, BuildVecIdx);
4592
4593       Result = DAG.getNode(ISD::VECTOR_SHUFFLE, NewVT,
4594                            PackVectorOp(Node->getOperand(0), NewVT),
4595                            PackVectorOp(Node->getOperand(1), NewVT), BV);
4596     }
4597     break;
4598   case ISD::VBIT_CONVERT:
4599     if (Op.getOperand(0).getValueType() != MVT::Vector)
4600       Result = DAG.getNode(ISD::BIT_CONVERT, NewVT, Op.getOperand(0));
4601     else {
4602       // If the input is a vector type, we have to either scalarize it, pack it
4603       // or convert it based on whether the input vector type is legal.
4604       SDNode *InVal = Node->getOperand(0).Val;
4605       unsigned NumElems =
4606         cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
4607       MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
4608
4609       // Figure out if there is a Packed type corresponding to this Vector
4610       // type.  If so, convert to the packed type.
4611       MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
4612       if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
4613         // Turn this into a bit convert of the packed input.
4614         Result = DAG.getNode(ISD::BIT_CONVERT, NewVT,
4615                              PackVectorOp(Node->getOperand(0), TVT));
4616         break;
4617       } else if (NumElems == 1) {
4618         // Turn this into a bit convert of the scalar input.
4619         Result = DAG.getNode(ISD::BIT_CONVERT, NewVT,
4620                              PackVectorOp(Node->getOperand(0), EVT));
4621         break;
4622       } else {
4623         // FIXME: UNIMP!
4624         assert(0 && "Cast from unsupported vector type not implemented yet!");
4625       }
4626     }
4627   }
4628
4629   if (TLI.isTypeLegal(NewVT))
4630     Result = LegalizeOp(Result);
4631   bool isNew = PackedNodes.insert(std::make_pair(Op, Result)).second;
4632   assert(isNew && "Value already packed?");
4633   return Result;
4634 }
4635
4636
4637 // SelectionDAG::Legalize - This is the entry point for the file.
4638 //
4639 void SelectionDAG::Legalize() {
4640   if (ViewLegalizeDAGs) viewGraph();
4641
4642   /// run - This is the main entry point to this class.
4643   ///
4644   SelectionDAGLegalize(*this).LegalizeDAG();
4645 }
4646