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