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 ubyte argument to be an int value for the call.
1665         Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
1666         Args.push_back(std::make_pair(Tmp3, Type::IntTy));
1667         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
1668
1669         FnName = "memset";
1670       } else if (Node->getOpcode() == ISD::MEMCPY ||
1671                  Node->getOpcode() == ISD::MEMMOVE) {
1672         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
1673         Args.push_back(std::make_pair(Tmp3, IntPtrTy));
1674         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
1675         FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
1676       } else {
1677         assert(0 && "Unknown op!");
1678       }
1679
1680       std::pair<SDOperand,SDOperand> CallResult =
1681         TLI.LowerCallTo(Tmp1, Type::VoidTy, false, CallingConv::C, false,
1682                         DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
1683       Result = CallResult.second;
1684       break;
1685     }
1686     }
1687     break;
1688   }
1689
1690   case ISD::READPORT:
1691     Tmp1 = LegalizeOp(Node->getOperand(0));
1692     Tmp2 = LegalizeOp(Node->getOperand(1));
1693     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1694
1695     // Since these produce two values, make sure to remember that we legalized
1696     // both of them.
1697     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1698     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1699     return Result;
1700   case ISD::WRITEPORT:
1701     Tmp1 = LegalizeOp(Node->getOperand(0));
1702     Tmp2 = LegalizeOp(Node->getOperand(1));
1703     Tmp3 = LegalizeOp(Node->getOperand(2));
1704     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1705     break;
1706
1707   case ISD::READIO:
1708     Tmp1 = LegalizeOp(Node->getOperand(0));
1709     Tmp2 = LegalizeOp(Node->getOperand(1));
1710
1711     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1712     case TargetLowering::Custom:
1713     default: assert(0 && "This action not implemented for this operation!");
1714     case TargetLowering::Legal:
1715       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1716       break;
1717     case TargetLowering::Expand:
1718       // Replace this with a load from memory.
1719       Result = DAG.getLoad(Node->getValueType(0), Node->getOperand(0),
1720                            Node->getOperand(1), DAG.getSrcValue(NULL));
1721       Result = LegalizeOp(Result);
1722       break;
1723     }
1724
1725     // Since these produce two values, make sure to remember that we legalized
1726     // both of them.
1727     AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1728     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1729     return Result.getValue(Op.ResNo);
1730
1731   case ISD::WRITEIO:
1732     Tmp1 = LegalizeOp(Node->getOperand(0));
1733     Tmp2 = LegalizeOp(Node->getOperand(1));
1734     Tmp3 = LegalizeOp(Node->getOperand(2));
1735
1736     switch (TLI.getOperationAction(Node->getOpcode(),
1737                                    Node->getOperand(1).getValueType())) {
1738     case TargetLowering::Custom:
1739     default: assert(0 && "This action not implemented for this operation!");
1740     case TargetLowering::Legal:
1741       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1742       break;
1743     case TargetLowering::Expand:
1744       // Replace this with a store to memory.
1745       Result = DAG.getNode(ISD::STORE, MVT::Other, Node->getOperand(0),
1746                            Node->getOperand(1), Node->getOperand(2),
1747                            DAG.getSrcValue(NULL));
1748       break;
1749     }
1750     break;
1751
1752   case ISD::ADD_PARTS:
1753   case ISD::SUB_PARTS:
1754   case ISD::SHL_PARTS:
1755   case ISD::SRA_PARTS:
1756   case ISD::SRL_PARTS: {
1757     std::vector<SDOperand> Ops;
1758     bool Changed = false;
1759     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
1760       Ops.push_back(LegalizeOp(Node->getOperand(i)));
1761       Changed |= Ops.back() != Node->getOperand(i);
1762     }
1763     if (Changed)
1764       Result = DAG.UpdateNodeOperands(Result, Ops);
1765
1766     switch (TLI.getOperationAction(Node->getOpcode(),
1767                                    Node->getValueType(0))) {
1768     default: assert(0 && "This action is not supported yet!");
1769     case TargetLowering::Legal: break;
1770     case TargetLowering::Custom:
1771       Tmp1 = TLI.LowerOperation(Result, DAG);
1772       if (Tmp1.Val) {
1773         SDOperand Tmp2, RetVal(0, 0);
1774         for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) {
1775           Tmp2 = LegalizeOp(Tmp1.getValue(i));
1776           AddLegalizedOperand(SDOperand(Node, i), Tmp2);
1777           if (i == Op.ResNo)
1778             RetVal = Tmp2;
1779         }
1780         assert(RetVal.Val && "Illegal result number");
1781         return RetVal;
1782       }
1783       break;
1784     }
1785
1786     // Since these produce multiple values, make sure to remember that we
1787     // legalized all of them.
1788     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
1789       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
1790     return Result.getValue(Op.ResNo);
1791   }
1792
1793     // Binary operators
1794   case ISD::ADD:
1795   case ISD::SUB:
1796   case ISD::MUL:
1797   case ISD::MULHS:
1798   case ISD::MULHU:
1799   case ISD::UDIV:
1800   case ISD::SDIV:
1801   case ISD::AND:
1802   case ISD::OR:
1803   case ISD::XOR:
1804   case ISD::SHL:
1805   case ISD::SRL:
1806   case ISD::SRA:
1807   case ISD::FADD:
1808   case ISD::FSUB:
1809   case ISD::FMUL:
1810   case ISD::FDIV:
1811     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
1812     switch (getTypeAction(Node->getOperand(1).getValueType())) {
1813     case Expand: assert(0 && "Not possible");
1814     case Legal:
1815       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS.
1816       break;
1817     case Promote:
1818       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the RHS.
1819       break;
1820     }
1821
1822     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1823
1824     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1825     default: assert(0 && "Operation not supported");
1826     case TargetLowering::Legal: break;
1827     case TargetLowering::Custom:
1828       Tmp1 = TLI.LowerOperation(Result, DAG);
1829       if (Tmp1.Val) Result = Tmp1;
1830       break;
1831     }
1832     break;
1833
1834   case ISD::BUILD_PAIR: {
1835     MVT::ValueType PairTy = Node->getValueType(0);
1836     // TODO: handle the case where the Lo and Hi operands are not of legal type
1837     Tmp1 = LegalizeOp(Node->getOperand(0));   // Lo
1838     Tmp2 = LegalizeOp(Node->getOperand(1));   // Hi
1839     switch (TLI.getOperationAction(ISD::BUILD_PAIR, PairTy)) {
1840     case TargetLowering::Promote:
1841     case TargetLowering::Custom:
1842       assert(0 && "Cannot promote/custom this yet!");
1843     case TargetLowering::Legal:
1844       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
1845         Result = DAG.getNode(ISD::BUILD_PAIR, PairTy, Tmp1, Tmp2);
1846       break;
1847     case TargetLowering::Expand:
1848       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, PairTy, Tmp1);
1849       Tmp2 = DAG.getNode(ISD::ANY_EXTEND, PairTy, Tmp2);
1850       Tmp2 = DAG.getNode(ISD::SHL, PairTy, Tmp2,
1851                          DAG.getConstant(MVT::getSizeInBits(PairTy)/2,
1852                                          TLI.getShiftAmountTy()));
1853       Result = DAG.getNode(ISD::OR, PairTy, Tmp1, Tmp2);
1854       break;
1855     }
1856     break;
1857   }
1858
1859   case ISD::UREM:
1860   case ISD::SREM:
1861   case ISD::FREM:
1862     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
1863     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
1864
1865     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1866     case TargetLowering::Promote: assert(0 && "Cannot promote this yet!");
1867     case TargetLowering::Custom:
1868       isCustom = true;
1869       // FALLTHROUGH
1870     case TargetLowering::Legal:
1871       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1872       if (isCustom) {
1873         Tmp1 = TLI.LowerOperation(Result, DAG);
1874         if (Tmp1.Val) Result = Tmp1;
1875       }
1876       break;
1877     case TargetLowering::Expand:
1878       if (MVT::isInteger(Node->getValueType(0))) {
1879         // X % Y -> X-X/Y*Y
1880         MVT::ValueType VT = Node->getValueType(0);
1881         unsigned Opc = Node->getOpcode() == ISD::UREM ? ISD::UDIV : ISD::SDIV;
1882         Result = DAG.getNode(Opc, VT, Tmp1, Tmp2);
1883         Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2);
1884         Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result);
1885       } else {
1886         // Floating point mod -> fmod libcall.
1887         const char *FnName = Node->getValueType(0) == MVT::f32 ? "fmodf":"fmod";
1888         SDOperand Dummy;
1889         Result = ExpandLibCall(FnName, Node, Dummy);
1890       }
1891       break;
1892     }
1893     break;
1894   case ISD::VAARG: {
1895     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1896     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1897
1898     MVT::ValueType VT = Node->getValueType(0);
1899     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
1900     default: assert(0 && "This action is not supported yet!");
1901     case TargetLowering::Custom:
1902       isCustom = true;
1903       // FALLTHROUGH
1904     case TargetLowering::Legal:
1905       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1906       Result = Result.getValue(0);
1907       Tmp1 = Result.getValue(1);
1908
1909       if (isCustom) {
1910         Tmp2 = TLI.LowerOperation(Result, DAG);
1911         if (Tmp2.Val) {
1912           Result = LegalizeOp(Tmp2);
1913           Tmp1 = LegalizeOp(Tmp2.getValue(1));
1914         }
1915       }
1916       break;
1917     case TargetLowering::Expand: {
1918       SDOperand VAList = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp2,
1919                                      Node->getOperand(2));
1920       // Increment the pointer, VAList, to the next vaarg
1921       Tmp3 = DAG.getNode(ISD::ADD, TLI.getPointerTy(), VAList,
1922                          DAG.getConstant(MVT::getSizeInBits(VT)/8,
1923                                          TLI.getPointerTy()));
1924       // Store the incremented VAList to the legalized pointer
1925       Tmp3 = DAG.getNode(ISD::STORE, MVT::Other, VAList.getValue(1), Tmp3, Tmp2,
1926                          Node->getOperand(2));
1927       // Load the actual argument out of the pointer VAList
1928       Result = DAG.getLoad(VT, Tmp3, VAList, DAG.getSrcValue(0));
1929       Tmp1 = LegalizeOp(Result.getValue(1));
1930       Result = LegalizeOp(Result);
1931       break;
1932     }
1933     }
1934     // Since VAARG produces two values, make sure to remember that we
1935     // legalized both of them.
1936     AddLegalizedOperand(SDOperand(Node, 0), Result);
1937     AddLegalizedOperand(SDOperand(Node, 1), Tmp1);
1938     return Op.ResNo ? Tmp1 : Result;
1939   }
1940
1941   case ISD::VACOPY:
1942     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1943     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the dest pointer.
1944     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the source pointer.
1945
1946     switch (TLI.getOperationAction(ISD::VACOPY, MVT::Other)) {
1947     default: assert(0 && "This action is not supported yet!");
1948     case TargetLowering::Custom:
1949       isCustom = true;
1950       // FALLTHROUGH
1951     case TargetLowering::Legal:
1952       Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3,
1953                                       Node->getOperand(3), Node->getOperand(4));
1954       if (isCustom) {
1955         Tmp1 = TLI.LowerOperation(Result, DAG);
1956         if (Tmp1.Val) Result = Tmp1;
1957       }
1958       break;
1959     case TargetLowering::Expand:
1960       // This defaults to loading a pointer from the input and storing it to the
1961       // output, returning the chain.
1962       Tmp4 = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp3, Node->getOperand(3));
1963       Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp4.getValue(1), Tmp4, Tmp2,
1964                            Node->getOperand(4));
1965       break;
1966     }
1967     break;
1968
1969   case ISD::VAEND:
1970     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1971     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1972
1973     switch (TLI.getOperationAction(ISD::VAEND, 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, Node->getOperand(2));
1980       if (isCustom) {
1981         Tmp1 = TLI.LowerOperation(Tmp1, DAG);
1982         if (Tmp1.Val) Result = Tmp1;
1983       }
1984       break;
1985     case TargetLowering::Expand:
1986       Result = Tmp1; // Default to a no-op, return the chain
1987       break;
1988     }
1989     break;
1990
1991   case ISD::VASTART:
1992     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1993     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1994
1995     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1996
1997     switch (TLI.getOperationAction(ISD::VASTART, MVT::Other)) {
1998     default: assert(0 && "This action is not supported yet!");
1999     case TargetLowering::Legal: break;
2000     case TargetLowering::Custom:
2001       Tmp1 = TLI.LowerOperation(Result, DAG);
2002       if (Tmp1.Val) Result = Tmp1;
2003       break;
2004     }
2005     break;
2006
2007   case ISD::ROTL:
2008   case ISD::ROTR:
2009     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2010     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2011
2012     assert(TLI.isOperationLegal(Node->getOpcode(), Node->getValueType(0)) &&
2013            "Cannot handle this yet!");
2014     Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2015     break;
2016
2017   case ISD::BSWAP:
2018     Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
2019     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2020     case TargetLowering::Custom:
2021       assert(0 && "Cannot custom legalize this yet!");
2022     case TargetLowering::Legal:
2023       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2024       break;
2025     case TargetLowering::Promote: {
2026       MVT::ValueType OVT = Tmp1.getValueType();
2027       MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2028       unsigned DiffBits = getSizeInBits(NVT) - getSizeInBits(OVT);
2029
2030       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2031       Tmp1 = DAG.getNode(ISD::BSWAP, NVT, Tmp1);
2032       Result = DAG.getNode(ISD::SRL, NVT, Tmp1,
2033                            DAG.getConstant(DiffBits, TLI.getShiftAmountTy()));
2034       break;
2035     }
2036     case TargetLowering::Expand:
2037       Result = ExpandBSWAP(Tmp1);
2038       break;
2039     }
2040     break;
2041
2042   case ISD::CTPOP:
2043   case ISD::CTTZ:
2044   case ISD::CTLZ:
2045     Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
2046     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2047     case TargetLowering::Custom: assert(0 && "Cannot custom handle this yet!");
2048     case TargetLowering::Legal:
2049       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2050       break;
2051     case TargetLowering::Promote: {
2052       MVT::ValueType OVT = Tmp1.getValueType();
2053       MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2054
2055       // Zero extend the argument.
2056       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2057       // Perform the larger operation, then subtract if needed.
2058       Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
2059       switch (Node->getOpcode()) {
2060       case ISD::CTPOP:
2061         Result = Tmp1;
2062         break;
2063       case ISD::CTTZ:
2064         //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
2065         Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1,
2066                             DAG.getConstant(getSizeInBits(NVT), NVT),
2067                             ISD::SETEQ);
2068         Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
2069                            DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1);
2070         break;
2071       case ISD::CTLZ:
2072         // Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
2073         Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
2074                              DAG.getConstant(getSizeInBits(NVT) -
2075                                              getSizeInBits(OVT), NVT));
2076         break;
2077       }
2078       break;
2079     }
2080     case TargetLowering::Expand:
2081       Result = ExpandBitCount(Node->getOpcode(), Tmp1);
2082       break;
2083     }
2084     break;
2085
2086     // Unary operators
2087   case ISD::FABS:
2088   case ISD::FNEG:
2089   case ISD::FSQRT:
2090   case ISD::FSIN:
2091   case ISD::FCOS:
2092     Tmp1 = LegalizeOp(Node->getOperand(0));
2093     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2094     case TargetLowering::Promote:
2095     case TargetLowering::Custom:
2096      isCustom = true;
2097      // FALLTHROUGH
2098     case TargetLowering::Legal:
2099       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2100       if (isCustom) {
2101         Tmp1 = TLI.LowerOperation(Result, DAG);
2102         if (Tmp1.Val) Result = Tmp1;
2103       }
2104       break;
2105     case TargetLowering::Expand:
2106       switch (Node->getOpcode()) {
2107       default: assert(0 && "Unreachable!");
2108       case ISD::FNEG:
2109         // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
2110         Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0));
2111         Result = DAG.getNode(ISD::FSUB, Node->getValueType(0), Tmp2, Tmp1);
2112         break;
2113       case ISD::FABS: {
2114         // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
2115         MVT::ValueType VT = Node->getValueType(0);
2116         Tmp2 = DAG.getConstantFP(0.0, VT);
2117         Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, Tmp2, ISD::SETUGT);
2118         Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1);
2119         Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3);
2120         break;
2121       }
2122       case ISD::FSQRT:
2123       case ISD::FSIN:
2124       case ISD::FCOS: {
2125         MVT::ValueType VT = Node->getValueType(0);
2126         const char *FnName = 0;
2127         switch(Node->getOpcode()) {
2128         case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break;
2129         case ISD::FSIN:  FnName = VT == MVT::f32 ? "sinf"  : "sin"; break;
2130         case ISD::FCOS:  FnName = VT == MVT::f32 ? "cosf"  : "cos"; break;
2131         default: assert(0 && "Unreachable!");
2132         }
2133         SDOperand Dummy;
2134         Result = ExpandLibCall(FnName, Node, Dummy);
2135         break;
2136       }
2137       }
2138       break;
2139     }
2140     break;
2141
2142   case ISD::BIT_CONVERT:
2143     if (!isTypeLegal(Node->getOperand(0).getValueType())) {
2144       Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2145     } else {
2146       switch (TLI.getOperationAction(ISD::BIT_CONVERT,
2147                                      Node->getOperand(0).getValueType())) {
2148       default: assert(0 && "Unknown operation action!");
2149       case TargetLowering::Expand:
2150         Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2151         break;
2152       case TargetLowering::Legal:
2153         Tmp1 = LegalizeOp(Node->getOperand(0));
2154         Result = DAG.UpdateNodeOperands(Result, Tmp1);
2155         break;
2156       }
2157     }
2158     break;
2159     // Conversion operators.  The source and destination have different types.
2160   case ISD::SINT_TO_FP:
2161   case ISD::UINT_TO_FP: {
2162     bool isSigned = Node->getOpcode() == ISD::SINT_TO_FP;
2163     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2164     case Legal:
2165       switch (TLI.getOperationAction(Node->getOpcode(),
2166                                      Node->getOperand(0).getValueType())) {
2167       default: assert(0 && "Unknown operation action!");
2168       case TargetLowering::Custom:
2169         isCustom = true;
2170         // FALLTHROUGH
2171       case TargetLowering::Legal:
2172         Tmp1 = LegalizeOp(Node->getOperand(0));
2173         Result = DAG.UpdateNodeOperands(Result, Tmp1);
2174         if (isCustom) {
2175           Tmp1 = TLI.LowerOperation(Result, DAG);
2176           if (Tmp1.Val) Result = Tmp1;
2177         }
2178         break;
2179       case TargetLowering::Expand:
2180         Result = ExpandLegalINT_TO_FP(isSigned,
2181                                       LegalizeOp(Node->getOperand(0)),
2182                                       Node->getValueType(0));
2183         break;
2184       case TargetLowering::Promote:
2185         Result = PromoteLegalINT_TO_FP(LegalizeOp(Node->getOperand(0)),
2186                                        Node->getValueType(0),
2187                                        isSigned);
2188         break;
2189       }
2190       break;
2191     case Expand:
2192       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP,
2193                              Node->getValueType(0), Node->getOperand(0));
2194       break;
2195     case Promote:
2196       Tmp1 = PromoteOp(Node->getOperand(0));
2197       if (isSigned) {
2198         Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, Tmp1.getValueType(),
2199                  Tmp1, DAG.getValueType(Node->getOperand(0).getValueType()));
2200       } else {
2201         Tmp1 = DAG.getZeroExtendInReg(Tmp1,
2202                                       Node->getOperand(0).getValueType());
2203       }
2204       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2205       Result = LegalizeOp(Result);  // The 'op' is not necessarily legal!
2206       break;
2207     }
2208     break;
2209   }
2210   case ISD::TRUNCATE:
2211     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2212     case Legal:
2213       Tmp1 = LegalizeOp(Node->getOperand(0));
2214       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2215       break;
2216     case Expand:
2217       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
2218
2219       // Since the result is legal, we should just be able to truncate the low
2220       // part of the source.
2221       Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
2222       break;
2223     case Promote:
2224       Result = PromoteOp(Node->getOperand(0));
2225       Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
2226       break;
2227     }
2228     break;
2229
2230   case ISD::FP_TO_SINT:
2231   case ISD::FP_TO_UINT:
2232     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2233     case Legal:
2234       Tmp1 = LegalizeOp(Node->getOperand(0));
2235
2236       switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))){
2237       default: assert(0 && "Unknown operation action!");
2238       case TargetLowering::Custom:
2239         isCustom = true;
2240         // FALLTHROUGH
2241       case TargetLowering::Legal:
2242         Result = DAG.UpdateNodeOperands(Result, Tmp1);
2243         if (isCustom) {
2244           Tmp1 = TLI.LowerOperation(Result, DAG);
2245           if (Tmp1.Val) Result = Tmp1;
2246         }
2247         break;
2248       case TargetLowering::Promote:
2249         Result = PromoteLegalFP_TO_INT(Tmp1, Node->getValueType(0),
2250                                        Node->getOpcode() == ISD::FP_TO_SINT);
2251         break;
2252       case TargetLowering::Expand:
2253         if (Node->getOpcode() == ISD::FP_TO_UINT) {
2254           SDOperand True, False;
2255           MVT::ValueType VT =  Node->getOperand(0).getValueType();
2256           MVT::ValueType NVT = Node->getValueType(0);
2257           unsigned ShiftAmt = MVT::getSizeInBits(Node->getValueType(0))-1;
2258           Tmp2 = DAG.getConstantFP((double)(1ULL << ShiftAmt), VT);
2259           Tmp3 = DAG.getSetCC(TLI.getSetCCResultTy(),
2260                             Node->getOperand(0), Tmp2, ISD::SETLT);
2261           True = DAG.getNode(ISD::FP_TO_SINT, NVT, Node->getOperand(0));
2262           False = DAG.getNode(ISD::FP_TO_SINT, NVT,
2263                               DAG.getNode(ISD::FSUB, VT, Node->getOperand(0),
2264                                           Tmp2));
2265           False = DAG.getNode(ISD::XOR, NVT, False,
2266                               DAG.getConstant(1ULL << ShiftAmt, NVT));
2267           Result = DAG.getNode(ISD::SELECT, NVT, Tmp3, True, False);
2268           break;
2269         } else {
2270           assert(0 && "Do not know how to expand FP_TO_SINT yet!");
2271         }
2272         break;
2273       }
2274       break;
2275     case Expand:
2276       assert(0 && "Shouldn't need to expand other operators here!");
2277     case Promote:
2278       Tmp1 = PromoteOp(Node->getOperand(0));
2279       Result = DAG.UpdateNodeOperands(Result, LegalizeOp(Tmp1));
2280       Result = LegalizeOp(Result);
2281       break;
2282     }
2283     break;
2284
2285   case ISD::ANY_EXTEND:
2286   case ISD::ZERO_EXTEND:
2287   case ISD::SIGN_EXTEND:
2288   case ISD::FP_EXTEND:
2289   case ISD::FP_ROUND:
2290     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2291     case Expand: assert(0 && "Shouldn't need to expand other operators here!");
2292     case Legal:
2293       Tmp1 = LegalizeOp(Node->getOperand(0));
2294       Result = DAG.UpdateNodeOperands(Result, Tmp1);
2295       break;
2296     case Promote:
2297       switch (Node->getOpcode()) {
2298       case ISD::ANY_EXTEND:
2299         Tmp1 = PromoteOp(Node->getOperand(0));
2300         Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Tmp1);
2301         break;
2302       case ISD::ZERO_EXTEND:
2303         Result = PromoteOp(Node->getOperand(0));
2304         Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result);
2305         Result = DAG.getZeroExtendInReg(Result,
2306                                         Node->getOperand(0).getValueType());
2307         break;
2308       case ISD::SIGN_EXTEND:
2309         Result = PromoteOp(Node->getOperand(0));
2310         Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result);
2311         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
2312                              Result,
2313                           DAG.getValueType(Node->getOperand(0).getValueType()));
2314         break;
2315       case ISD::FP_EXTEND:
2316         Result = PromoteOp(Node->getOperand(0));
2317         if (Result.getValueType() != Op.getValueType())
2318           // Dynamically dead while we have only 2 FP types.
2319           Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
2320         break;
2321       case ISD::FP_ROUND:
2322         Result = PromoteOp(Node->getOperand(0));
2323         Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
2324         break;
2325       }
2326     }
2327     break;
2328   case ISD::FP_ROUND_INREG:
2329   case ISD::SIGN_EXTEND_INREG: {
2330     Tmp1 = LegalizeOp(Node->getOperand(0));
2331     MVT::ValueType ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
2332
2333     // If this operation is not supported, convert it to a shl/shr or load/store
2334     // pair.
2335     switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
2336     default: assert(0 && "This action not supported for this op yet!");
2337     case TargetLowering::Legal:
2338       Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
2339       break;
2340     case TargetLowering::Expand:
2341       // If this is an integer extend and shifts are supported, do that.
2342       if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
2343         // NOTE: we could fall back on load/store here too for targets without
2344         // SAR.  However, it is doubtful that any exist.
2345         unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
2346                             MVT::getSizeInBits(ExtraVT);
2347         SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy());
2348         Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
2349                              Node->getOperand(0), ShiftCst);
2350         Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
2351                              Result, ShiftCst);
2352       } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
2353         // The only way we can lower this is to turn it into a STORETRUNC,
2354         // EXTLOAD pair, targetting a temporary location (a stack slot).
2355
2356         // NOTE: there is a choice here between constantly creating new stack
2357         // slots and always reusing the same one.  We currently always create
2358         // new ones, as reuse may inhibit scheduling.
2359         const Type *Ty = MVT::getTypeForValueType(ExtraVT);
2360         unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty);
2361         unsigned Align  = TLI.getTargetData().getTypeAlignment(Ty);
2362         MachineFunction &MF = DAG.getMachineFunction();
2363         int SSFI =
2364           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
2365         SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
2366         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
2367                              Node->getOperand(0), StackSlot,
2368                              DAG.getSrcValue(NULL), DAG.getValueType(ExtraVT));
2369         Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
2370                                 Result, StackSlot, DAG.getSrcValue(NULL),
2371                                 ExtraVT);
2372       } else {
2373         assert(0 && "Unknown op");
2374       }
2375       break;
2376     }
2377     break;
2378   }
2379   }
2380
2381   // Make sure that the generated code is itself legal.
2382   if (Result != Op)
2383     Result = LegalizeOp(Result);
2384
2385   // Note that LegalizeOp may be reentered even from single-use nodes, which
2386   // means that we always must cache transformed nodes.
2387   AddLegalizedOperand(Op, Result);
2388   return Result;
2389 }
2390
2391 /// PromoteOp - Given an operation that produces a value in an invalid type,
2392 /// promote it to compute the value into a larger type.  The produced value will
2393 /// have the correct bits for the low portion of the register, but no guarantee
2394 /// is made about the top bits: it may be zero, sign-extended, or garbage.
2395 SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
2396   MVT::ValueType VT = Op.getValueType();
2397   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
2398   assert(getTypeAction(VT) == Promote &&
2399          "Caller should expand or legalize operands that are not promotable!");
2400   assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
2401          "Cannot promote to smaller type!");
2402
2403   SDOperand Tmp1, Tmp2, Tmp3;
2404   SDOperand Result;
2405   SDNode *Node = Op.Val;
2406
2407   std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
2408   if (I != PromotedNodes.end()) return I->second;
2409
2410   switch (Node->getOpcode()) {
2411   case ISD::CopyFromReg:
2412     assert(0 && "CopyFromReg must be legal!");
2413   default:
2414     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
2415     assert(0 && "Do not know how to promote this operator!");
2416     abort();
2417   case ISD::UNDEF:
2418     Result = DAG.getNode(ISD::UNDEF, NVT);
2419     break;
2420   case ISD::Constant:
2421     if (VT != MVT::i1)
2422       Result = DAG.getNode(ISD::SIGN_EXTEND, NVT, Op);
2423     else
2424       Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
2425     assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
2426     break;
2427   case ISD::ConstantFP:
2428     Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
2429     assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
2430     break;
2431
2432   case ISD::SETCC:
2433     assert(isTypeLegal(TLI.getSetCCResultTy()) && "SetCC type is not legal??");
2434     Result = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(),Node->getOperand(0),
2435                          Node->getOperand(1), Node->getOperand(2));
2436     break;
2437
2438   case ISD::TRUNCATE:
2439     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2440     case Legal:
2441       Result = LegalizeOp(Node->getOperand(0));
2442       assert(Result.getValueType() >= NVT &&
2443              "This truncation doesn't make sense!");
2444       if (Result.getValueType() > NVT)    // Truncate to NVT instead of VT
2445         Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
2446       break;
2447     case Promote:
2448       // The truncation is not required, because we don't guarantee anything
2449       // about high bits anyway.
2450       Result = PromoteOp(Node->getOperand(0));
2451       break;
2452     case Expand:
2453       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
2454       // Truncate the low part of the expanded value to the result type
2455       Result = DAG.getNode(ISD::TRUNCATE, NVT, Tmp1);
2456     }
2457     break;
2458   case ISD::SIGN_EXTEND:
2459   case ISD::ZERO_EXTEND:
2460   case ISD::ANY_EXTEND:
2461     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2462     case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
2463     case Legal:
2464       // Input is legal?  Just do extend all the way to the larger type.
2465       Result = DAG.getNode(Node->getOpcode(), NVT, Node->getOperand(0));
2466       break;
2467     case Promote:
2468       // Promote the reg if it's smaller.
2469       Result = PromoteOp(Node->getOperand(0));
2470       // The high bits are not guaranteed to be anything.  Insert an extend.
2471       if (Node->getOpcode() == ISD::SIGN_EXTEND)
2472         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
2473                          DAG.getValueType(Node->getOperand(0).getValueType()));
2474       else if (Node->getOpcode() == ISD::ZERO_EXTEND)
2475         Result = DAG.getZeroExtendInReg(Result,
2476                                         Node->getOperand(0).getValueType());
2477       break;
2478     }
2479     break;
2480   case ISD::BIT_CONVERT:
2481     Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2482     Result = PromoteOp(Result);
2483     break;
2484
2485   case ISD::FP_EXTEND:
2486     assert(0 && "Case not implemented.  Dynamically dead with 2 FP types!");
2487   case ISD::FP_ROUND:
2488     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2489     case Expand: assert(0 && "BUG: Cannot expand FP regs!");
2490     case Promote:  assert(0 && "Unreachable with 2 FP types!");
2491     case Legal:
2492       // Input is legal?  Do an FP_ROUND_INREG.
2493       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Node->getOperand(0),
2494                            DAG.getValueType(VT));
2495       break;
2496     }
2497     break;
2498
2499   case ISD::SINT_TO_FP:
2500   case ISD::UINT_TO_FP:
2501     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2502     case Legal:
2503       // No extra round required here.
2504       Result = DAG.getNode(Node->getOpcode(), NVT, Node->getOperand(0));
2505       break;
2506
2507     case Promote:
2508       Result = PromoteOp(Node->getOperand(0));
2509       if (Node->getOpcode() == ISD::SINT_TO_FP)
2510         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
2511                              Result,
2512                          DAG.getValueType(Node->getOperand(0).getValueType()));
2513       else
2514         Result = DAG.getZeroExtendInReg(Result,
2515                                         Node->getOperand(0).getValueType());
2516       // No extra round required here.
2517       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
2518       break;
2519     case Expand:
2520       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT,
2521                              Node->getOperand(0));
2522       // Round if we cannot tolerate excess precision.
2523       if (NoExcessFPPrecision)
2524         Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2525                              DAG.getValueType(VT));
2526       break;
2527     }
2528     break;
2529
2530   case ISD::SIGN_EXTEND_INREG:
2531     Result = PromoteOp(Node->getOperand(0));
2532     Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
2533                          Node->getOperand(1));
2534     break;
2535   case ISD::FP_TO_SINT:
2536   case ISD::FP_TO_UINT:
2537     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2538     case Legal:
2539       Tmp1 = Node->getOperand(0);
2540       break;
2541     case Promote:
2542       // The input result is prerounded, so we don't have to do anything
2543       // special.
2544       Tmp1 = PromoteOp(Node->getOperand(0));
2545       break;
2546     case Expand:
2547       assert(0 && "not implemented");
2548     }
2549     // If we're promoting a UINT to a larger size, check to see if the new node
2550     // will be legal.  If it isn't, check to see if FP_TO_SINT is legal, since
2551     // we can use that instead.  This allows us to generate better code for
2552     // FP_TO_UINT for small destination sizes on targets where FP_TO_UINT is not
2553     // legal, such as PowerPC.
2554     if (Node->getOpcode() == ISD::FP_TO_UINT &&
2555         !TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) &&
2556         (TLI.isOperationLegal(ISD::FP_TO_SINT, NVT) ||
2557          TLI.getOperationAction(ISD::FP_TO_SINT, NVT)==TargetLowering::Custom)){
2558       Result = DAG.getNode(ISD::FP_TO_SINT, NVT, Tmp1);
2559     } else {
2560       Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2561     }
2562     break;
2563
2564   case ISD::FABS:
2565   case ISD::FNEG:
2566     Tmp1 = PromoteOp(Node->getOperand(0));
2567     assert(Tmp1.getValueType() == NVT);
2568     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2569     // NOTE: we do not have to do any extra rounding here for
2570     // NoExcessFPPrecision, because we know the input will have the appropriate
2571     // precision, and these operations don't modify precision at all.
2572     break;
2573
2574   case ISD::FSQRT:
2575   case ISD::FSIN:
2576   case ISD::FCOS:
2577     Tmp1 = PromoteOp(Node->getOperand(0));
2578     assert(Tmp1.getValueType() == NVT);
2579     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2580     if (NoExcessFPPrecision)
2581       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2582                            DAG.getValueType(VT));
2583     break;
2584
2585   case ISD::AND:
2586   case ISD::OR:
2587   case ISD::XOR:
2588   case ISD::ADD:
2589   case ISD::SUB:
2590   case ISD::MUL:
2591     // The input may have strange things in the top bits of the registers, but
2592     // these operations don't care.  They may have weird bits going out, but
2593     // that too is okay if they are integer operations.
2594     Tmp1 = PromoteOp(Node->getOperand(0));
2595     Tmp2 = PromoteOp(Node->getOperand(1));
2596     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
2597     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2598     break;
2599   case ISD::FADD:
2600   case ISD::FSUB:
2601   case ISD::FMUL:
2602     Tmp1 = PromoteOp(Node->getOperand(0));
2603     Tmp2 = PromoteOp(Node->getOperand(1));
2604     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
2605     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2606
2607     // Floating point operations will give excess precision that we may not be
2608     // able to tolerate.  If we DO allow excess precision, just leave it,
2609     // otherwise excise it.
2610     // FIXME: Why would we need to round FP ops more than integer ones?
2611     //     Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
2612     if (NoExcessFPPrecision)
2613       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2614                            DAG.getValueType(VT));
2615     break;
2616
2617   case ISD::SDIV:
2618   case ISD::SREM:
2619     // These operators require that their input be sign extended.
2620     Tmp1 = PromoteOp(Node->getOperand(0));
2621     Tmp2 = PromoteOp(Node->getOperand(1));
2622     if (MVT::isInteger(NVT)) {
2623       Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
2624                          DAG.getValueType(VT));
2625       Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
2626                          DAG.getValueType(VT));
2627     }
2628     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2629
2630     // Perform FP_ROUND: this is probably overly pessimistic.
2631     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
2632       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2633                            DAG.getValueType(VT));
2634     break;
2635   case ISD::FDIV:
2636   case ISD::FREM:
2637     // These operators require that their input be fp extended.
2638     Tmp1 = PromoteOp(Node->getOperand(0));
2639     Tmp2 = PromoteOp(Node->getOperand(1));
2640     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2641
2642     // Perform FP_ROUND: this is probably overly pessimistic.
2643     if (NoExcessFPPrecision)
2644       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
2645                            DAG.getValueType(VT));
2646     break;
2647
2648   case ISD::UDIV:
2649   case ISD::UREM:
2650     // These operators require that their input be zero extended.
2651     Tmp1 = PromoteOp(Node->getOperand(0));
2652     Tmp2 = PromoteOp(Node->getOperand(1));
2653     assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
2654     Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
2655     Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
2656     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2657     break;
2658
2659   case ISD::SHL:
2660     Tmp1 = PromoteOp(Node->getOperand(0));
2661     Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Node->getOperand(1));
2662     break;
2663   case ISD::SRA:
2664     // The input value must be properly sign extended.
2665     Tmp1 = PromoteOp(Node->getOperand(0));
2666     Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
2667                        DAG.getValueType(VT));
2668     Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Node->getOperand(1));
2669     break;
2670   case ISD::SRL:
2671     // The input value must be properly zero extended.
2672     Tmp1 = PromoteOp(Node->getOperand(0));
2673     Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
2674     Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Node->getOperand(1));
2675     break;
2676
2677   case ISD::VAARG:
2678     Tmp1 = Node->getOperand(0);   // Get the chain.
2679     Tmp2 = Node->getOperand(1);   // Get the pointer.
2680     if (TLI.getOperationAction(ISD::VAARG, VT) == TargetLowering::Custom) {
2681       Tmp3 = DAG.getVAArg(VT, Tmp1, Tmp2, Node->getOperand(2));
2682       Result = TLI.CustomPromoteOperation(Tmp3, DAG);
2683     } else {
2684       SDOperand VAList = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp2,
2685                                      Node->getOperand(2));
2686       // Increment the pointer, VAList, to the next vaarg
2687       Tmp3 = DAG.getNode(ISD::ADD, TLI.getPointerTy(), VAList,
2688                          DAG.getConstant(MVT::getSizeInBits(VT)/8,
2689                                          TLI.getPointerTy()));
2690       // Store the incremented VAList to the legalized pointer
2691       Tmp3 = DAG.getNode(ISD::STORE, MVT::Other, VAList.getValue(1), Tmp3, Tmp2,
2692                          Node->getOperand(2));
2693       // Load the actual argument out of the pointer VAList
2694       Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Tmp3, VAList,
2695                               DAG.getSrcValue(0), VT);
2696     }
2697     // Remember that we legalized the chain.
2698     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
2699     break;
2700
2701   case ISD::LOAD:
2702     Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Node->getOperand(0),
2703                             Node->getOperand(1), Node->getOperand(2), VT);
2704     // Remember that we legalized the chain.
2705     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
2706     break;
2707   case ISD::SEXTLOAD:
2708   case ISD::ZEXTLOAD:
2709   case ISD::EXTLOAD:
2710     Result = DAG.getExtLoad(Node->getOpcode(), NVT, Node->getOperand(0),
2711                             Node->getOperand(1), Node->getOperand(2),
2712                             cast<VTSDNode>(Node->getOperand(3))->getVT());
2713     // Remember that we legalized the chain.
2714     AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
2715     break;
2716   case ISD::SELECT:
2717     Tmp2 = PromoteOp(Node->getOperand(1));   // Legalize the op0
2718     Tmp3 = PromoteOp(Node->getOperand(2));   // Legalize the op1
2719     Result = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), Tmp2, Tmp3);
2720     break;
2721   case ISD::SELECT_CC:
2722     Tmp2 = PromoteOp(Node->getOperand(2));   // True
2723     Tmp3 = PromoteOp(Node->getOperand(3));   // False
2724     Result = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
2725                          Node->getOperand(1), Tmp2, Tmp3, Node->getOperand(4));
2726     break;
2727   case ISD::BSWAP:
2728     Tmp1 = Node->getOperand(0);
2729     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2730     Tmp1 = DAG.getNode(ISD::BSWAP, NVT, Tmp1);
2731     Result = DAG.getNode(ISD::SRL, NVT, Tmp1,
2732                          DAG.getConstant(getSizeInBits(NVT) - getSizeInBits(VT),
2733                                          TLI.getShiftAmountTy()));
2734     break;
2735   case ISD::CTPOP:
2736   case ISD::CTTZ:
2737   case ISD::CTLZ:
2738     // Zero extend the argument
2739     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Node->getOperand(0));
2740     // Perform the larger operation, then subtract if needed.
2741     Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
2742     switch(Node->getOpcode()) {
2743     case ISD::CTPOP:
2744       Result = Tmp1;
2745       break;
2746     case ISD::CTTZ:
2747       // if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
2748       Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1,
2749                           DAG.getConstant(getSizeInBits(NVT), NVT), ISD::SETEQ);
2750       Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
2751                            DAG.getConstant(getSizeInBits(VT), NVT), Tmp1);
2752       break;
2753     case ISD::CTLZ:
2754       //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
2755       Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
2756                            DAG.getConstant(getSizeInBits(NVT) -
2757                                            getSizeInBits(VT), NVT));
2758       break;
2759     }
2760     break;
2761   }
2762
2763   assert(Result.Val && "Didn't set a result!");
2764
2765   // Make sure the result is itself legal.
2766   Result = LegalizeOp(Result);
2767
2768   // Remember that we promoted this!
2769   AddPromotedOperand(Op, Result);
2770   return Result;
2771 }
2772
2773 /// LegalizeSetCCOperands - Attempts to create a legal LHS and RHS for a SETCC
2774 /// with condition CC on the current target.  This usually involves legalizing
2775 /// or promoting the arguments.  In the case where LHS and RHS must be expanded,
2776 /// there may be no choice but to create a new SetCC node to represent the
2777 /// legalized value of setcc lhs, rhs.  In this case, the value is returned in
2778 /// LHS, and the SDOperand returned in RHS has a nil SDNode value.
2779 void SelectionDAGLegalize::LegalizeSetCCOperands(SDOperand &LHS,
2780                                                  SDOperand &RHS,
2781                                                  SDOperand &CC) {
2782   SDOperand Tmp1, Tmp2, Result;
2783
2784   switch (getTypeAction(LHS.getValueType())) {
2785   case Legal:
2786     Tmp1 = LegalizeOp(LHS);   // LHS
2787     Tmp2 = LegalizeOp(RHS);   // RHS
2788     break;
2789   case Promote:
2790     Tmp1 = PromoteOp(LHS);   // LHS
2791     Tmp2 = PromoteOp(RHS);   // RHS
2792
2793     // If this is an FP compare, the operands have already been extended.
2794     if (MVT::isInteger(LHS.getValueType())) {
2795       MVT::ValueType VT = LHS.getValueType();
2796       MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
2797
2798       // Otherwise, we have to insert explicit sign or zero extends.  Note
2799       // that we could insert sign extends for ALL conditions, but zero extend
2800       // is cheaper on many machines (an AND instead of two shifts), so prefer
2801       // it.
2802       switch (cast<CondCodeSDNode>(CC)->get()) {
2803       default: assert(0 && "Unknown integer comparison!");
2804       case ISD::SETEQ:
2805       case ISD::SETNE:
2806       case ISD::SETUGE:
2807       case ISD::SETUGT:
2808       case ISD::SETULE:
2809       case ISD::SETULT:
2810         // ALL of these operations will work if we either sign or zero extend
2811         // the operands (including the unsigned comparisons!).  Zero extend is
2812         // usually a simpler/cheaper operation, so prefer it.
2813         Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
2814         Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
2815         break;
2816       case ISD::SETGE:
2817       case ISD::SETGT:
2818       case ISD::SETLT:
2819       case ISD::SETLE:
2820         Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
2821                            DAG.getValueType(VT));
2822         Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
2823                            DAG.getValueType(VT));
2824         break;
2825       }
2826     }
2827     break;
2828   case Expand:
2829     SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
2830     ExpandOp(LHS, LHSLo, LHSHi);
2831     ExpandOp(RHS, RHSLo, RHSHi);
2832     switch (cast<CondCodeSDNode>(CC)->get()) {
2833     case ISD::SETEQ:
2834     case ISD::SETNE:
2835       if (RHSLo == RHSHi)
2836         if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
2837           if (RHSCST->isAllOnesValue()) {
2838             // Comparison to -1.
2839             Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
2840             Tmp2 = RHSLo;
2841             break;
2842           }
2843
2844       Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
2845       Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
2846       Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
2847       Tmp2 = DAG.getConstant(0, Tmp1.getValueType());
2848       break;
2849     default:
2850       // If this is a comparison of the sign bit, just look at the top part.
2851       // X > -1,  x < 0
2852       if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(RHS))
2853         if ((cast<CondCodeSDNode>(CC)->get() == ISD::SETLT &&
2854              CST->getValue() == 0) ||             // X < 0
2855             (cast<CondCodeSDNode>(CC)->get() == ISD::SETGT &&
2856              CST->isAllOnesValue())) {            // X > -1
2857           Tmp1 = LHSHi;
2858           Tmp2 = RHSHi;
2859           break;
2860         }
2861
2862       // FIXME: This generated code sucks.
2863       ISD::CondCode LowCC;
2864       switch (cast<CondCodeSDNode>(CC)->get()) {
2865       default: assert(0 && "Unknown integer setcc!");
2866       case ISD::SETLT:
2867       case ISD::SETULT: LowCC = ISD::SETULT; break;
2868       case ISD::SETGT:
2869       case ISD::SETUGT: LowCC = ISD::SETUGT; break;
2870       case ISD::SETLE:
2871       case ISD::SETULE: LowCC = ISD::SETULE; break;
2872       case ISD::SETGE:
2873       case ISD::SETUGE: LowCC = ISD::SETUGE; break;
2874       }
2875
2876       // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
2877       // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
2878       // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
2879
2880       // NOTE: on targets without efficient SELECT of bools, we can always use
2881       // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
2882       Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC);
2883       Tmp2 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), LHSHi, RHSHi, CC);
2884       Result = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ);
2885       Result = LegalizeOp(DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
2886                                       Result, Tmp1, Tmp2));
2887       Tmp1 = Result;
2888       Tmp2 = SDOperand();
2889     }
2890   }
2891   LHS = Tmp1;
2892   RHS = Tmp2;
2893 }
2894
2895 /// ExpandBIT_CONVERT - Expand a BIT_CONVERT node into a store/load combination.
2896 /// The resultant code need not be legal.  Note that SrcOp is the input operand
2897 /// to the BIT_CONVERT, not the BIT_CONVERT node itself.
2898 SDOperand SelectionDAGLegalize::ExpandBIT_CONVERT(MVT::ValueType DestVT,
2899                                                   SDOperand SrcOp) {
2900   // Create the stack frame object.
2901   MachineFrameInfo *FrameInfo = DAG.getMachineFunction().getFrameInfo();
2902   unsigned ByteSize = MVT::getSizeInBits(DestVT)/8;
2903   int FrameIdx = FrameInfo->CreateStackObject(ByteSize, ByteSize);
2904   SDOperand FIPtr = DAG.getFrameIndex(FrameIdx, TLI.getPointerTy());
2905
2906   // Emit a store to the stack slot.
2907   SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
2908                                 SrcOp, FIPtr, DAG.getSrcValue(NULL));
2909   // Result is a load from the stack slot.
2910   return DAG.getLoad(DestVT, Store, FIPtr, DAG.getSrcValue(0));
2911 }
2912
2913 void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp,
2914                                             SDOperand Op, SDOperand Amt,
2915                                             SDOperand &Lo, SDOperand &Hi) {
2916   // Expand the subcomponents.
2917   SDOperand LHSL, LHSH;
2918   ExpandOp(Op, LHSL, LHSH);
2919
2920   std::vector<SDOperand> Ops;
2921   Ops.push_back(LHSL);
2922   Ops.push_back(LHSH);
2923   Ops.push_back(Amt);
2924   std::vector<MVT::ValueType> VTs(2, LHSL.getValueType());
2925   Lo = DAG.getNode(NodeOp, VTs, Ops);
2926   Hi = Lo.getValue(1);
2927 }
2928
2929
2930 /// ExpandShift - Try to find a clever way to expand this shift operation out to
2931 /// smaller elements.  If we can't find a way that is more efficient than a
2932 /// libcall on this target, return false.  Otherwise, return true with the
2933 /// low-parts expanded into Lo and Hi.
2934 bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
2935                                        SDOperand &Lo, SDOperand &Hi) {
2936   assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
2937          "This is not a shift!");
2938
2939   MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
2940   SDOperand ShAmt = LegalizeOp(Amt);
2941   MVT::ValueType ShTy = ShAmt.getValueType();
2942   unsigned VTBits = MVT::getSizeInBits(Op.getValueType());
2943   unsigned NVTBits = MVT::getSizeInBits(NVT);
2944
2945   // Handle the case when Amt is an immediate.  Other cases are currently broken
2946   // and are disabled.
2947   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) {
2948     unsigned Cst = CN->getValue();
2949     // Expand the incoming operand to be shifted, so that we have its parts
2950     SDOperand InL, InH;
2951     ExpandOp(Op, InL, InH);
2952     switch(Opc) {
2953     case ISD::SHL:
2954       if (Cst > VTBits) {
2955         Lo = DAG.getConstant(0, NVT);
2956         Hi = DAG.getConstant(0, NVT);
2957       } else if (Cst > NVTBits) {
2958         Lo = DAG.getConstant(0, NVT);
2959         Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy));
2960       } else if (Cst == NVTBits) {
2961         Lo = DAG.getConstant(0, NVT);
2962         Hi = InL;
2963       } else {
2964         Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy));
2965         Hi = DAG.getNode(ISD::OR, NVT,
2966            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)),
2967            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy)));
2968       }
2969       return true;
2970     case ISD::SRL:
2971       if (Cst > VTBits) {
2972         Lo = DAG.getConstant(0, NVT);
2973         Hi = DAG.getConstant(0, NVT);
2974       } else if (Cst > NVTBits) {
2975         Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy));
2976         Hi = DAG.getConstant(0, NVT);
2977       } else if (Cst == NVTBits) {
2978         Lo = InH;
2979         Hi = DAG.getConstant(0, NVT);
2980       } else {
2981         Lo = DAG.getNode(ISD::OR, NVT,
2982            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
2983            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
2984         Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy));
2985       }
2986       return true;
2987     case ISD::SRA:
2988       if (Cst > VTBits) {
2989         Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
2990                               DAG.getConstant(NVTBits-1, ShTy));
2991       } else if (Cst > NVTBits) {
2992         Lo = DAG.getNode(ISD::SRA, NVT, InH,
2993                            DAG.getConstant(Cst-NVTBits, ShTy));
2994         Hi = DAG.getNode(ISD::SRA, NVT, InH,
2995                               DAG.getConstant(NVTBits-1, ShTy));
2996       } else if (Cst == NVTBits) {
2997         Lo = InH;
2998         Hi = DAG.getNode(ISD::SRA, NVT, InH,
2999                               DAG.getConstant(NVTBits-1, ShTy));
3000       } else {
3001         Lo = DAG.getNode(ISD::OR, NVT,
3002            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
3003            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
3004         Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy));
3005       }
3006       return true;
3007     }
3008   }
3009   return false;
3010 }
3011
3012
3013 // ExpandLibCall - Expand a node into a call to a libcall.  If the result value
3014 // does not fit into a register, return the lo part and set the hi part to the
3015 // by-reg argument.  If it does fit into a single register, return the result
3016 // and leave the Hi part unset.
3017 SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node,
3018                                               SDOperand &Hi) {
3019   assert(!IsLegalizingCall && "Cannot overlap legalization of calls!");
3020   // The input chain to this libcall is the entry node of the function.
3021   // Legalizing the call will automatically add the previous call to the
3022   // dependence.
3023   SDOperand InChain = DAG.getEntryNode();
3024
3025   TargetLowering::ArgListTy Args;
3026   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
3027     MVT::ValueType ArgVT = Node->getOperand(i).getValueType();
3028     const Type *ArgTy = MVT::getTypeForValueType(ArgVT);
3029     Args.push_back(std::make_pair(Node->getOperand(i), ArgTy));
3030   }
3031   SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy());
3032
3033   // Splice the libcall in wherever FindInputOutputChains tells us to.
3034   const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0));
3035   std::pair<SDOperand,SDOperand> CallInfo =
3036     TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, false,
3037                     Callee, Args, DAG);
3038
3039   // Legalize the call sequence, starting with the chain.  This will advance
3040   // the LastCALLSEQ_END to the legalized version of the CALLSEQ_END node that
3041   // was added by LowerCallTo (guaranteeing proper serialization of calls).
3042   LegalizeOp(CallInfo.second);
3043   SDOperand Result;
3044   switch (getTypeAction(CallInfo.first.getValueType())) {
3045   default: assert(0 && "Unknown thing");
3046   case Legal:
3047     Result = CallInfo.first;
3048     break;
3049   case Expand:
3050     ExpandOp(CallInfo.first, Result, Hi);
3051     break;
3052   }
3053   return Result;
3054 }
3055
3056
3057 /// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the
3058 /// destination type is legal.
3059 SDOperand SelectionDAGLegalize::
3060 ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) {
3061   assert(isTypeLegal(DestTy) && "Destination type is not legal!");
3062   assert(getTypeAction(Source.getValueType()) == Expand &&
3063          "This is not an expansion!");
3064   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
3065
3066   if (!isSigned) {
3067     assert(Source.getValueType() == MVT::i64 &&
3068            "This only works for 64-bit -> FP");
3069     // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
3070     // incoming integer is set.  To handle this, we dynamically test to see if
3071     // it is set, and, if so, add a fudge factor.
3072     SDOperand Lo, Hi;
3073     ExpandOp(Source, Lo, Hi);
3074
3075     // If this is unsigned, and not supported, first perform the conversion to
3076     // signed, then adjust the result if the sign bit is set.
3077     SDOperand SignedConv = ExpandIntToFP(true, DestTy,
3078                    DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), Lo, Hi));
3079
3080     SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi,
3081                                      DAG.getConstant(0, Hi.getValueType()),
3082                                      ISD::SETLT);
3083     SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
3084     SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
3085                                       SignSet, Four, Zero);
3086     uint64_t FF = 0x5f800000ULL;
3087     if (TLI.isLittleEndian()) FF <<= 32;
3088     static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
3089
3090     SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
3091     CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
3092     SDOperand FudgeInReg;
3093     if (DestTy == MVT::f32)
3094       FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
3095                                DAG.getSrcValue(NULL));
3096     else {
3097       assert(DestTy == MVT::f64 && "Unexpected conversion");
3098       FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
3099                                   CPIdx, DAG.getSrcValue(NULL), MVT::f32);
3100     }
3101     return DAG.getNode(ISD::FADD, DestTy, SignedConv, FudgeInReg);
3102   }
3103
3104   // Check to see if the target has a custom way to lower this.  If so, use it.
3105   switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) {
3106   default: assert(0 && "This action not implemented for this operation!");
3107   case TargetLowering::Legal:
3108   case TargetLowering::Expand:
3109     break;   // This case is handled below.
3110   case TargetLowering::Custom: {
3111     SDOperand NV = TLI.LowerOperation(DAG.getNode(ISD::SINT_TO_FP, DestTy,
3112                                                   Source), DAG);
3113     if (NV.Val)
3114       return LegalizeOp(NV);
3115     break;   // The target decided this was legal after all
3116   }
3117   }
3118
3119   // Expand the source, then glue it back together for the call.  We must expand
3120   // the source in case it is shared (this pass of legalize must traverse it).
3121   SDOperand SrcLo, SrcHi;
3122   ExpandOp(Source, SrcLo, SrcHi);
3123   Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi);
3124
3125   const char *FnName = 0;
3126   if (DestTy == MVT::f32)
3127     FnName = "__floatdisf";
3128   else {
3129     assert(DestTy == MVT::f64 && "Unknown fp value type!");
3130     FnName = "__floatdidf";
3131   }
3132
3133   Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source);
3134   SDOperand UnusedHiPart;
3135   return ExpandLibCall(FnName, Source.Val, UnusedHiPart);
3136 }
3137
3138 /// ExpandLegalINT_TO_FP - This function is responsible for legalizing a
3139 /// INT_TO_FP operation of the specified operand when the target requests that
3140 /// we expand it.  At this point, we know that the result and operand types are
3141 /// legal for the target.
3142 SDOperand SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned,
3143                                                      SDOperand Op0,
3144                                                      MVT::ValueType DestVT) {
3145   if (Op0.getValueType() == MVT::i32) {
3146     // simple 32-bit [signed|unsigned] integer to float/double expansion
3147
3148     // get the stack frame index of a 8 byte buffer
3149     MachineFunction &MF = DAG.getMachineFunction();
3150     int SSFI = MF.getFrameInfo()->CreateStackObject(8, 8);
3151     // get address of 8 byte buffer
3152     SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
3153     // word offset constant for Hi/Lo address computation
3154     SDOperand WordOff = DAG.getConstant(sizeof(int), TLI.getPointerTy());
3155     // set up Hi and Lo (into buffer) address based on endian
3156     SDOperand Hi, Lo;
3157     if (TLI.isLittleEndian()) {
3158       Hi = DAG.getNode(ISD::ADD, TLI.getPointerTy(), StackSlot, WordOff);
3159       Lo = StackSlot;
3160     } else {
3161       Hi = StackSlot;
3162       Lo = DAG.getNode(ISD::ADD, TLI.getPointerTy(), StackSlot, WordOff);
3163     }
3164     // if signed map to unsigned space
3165     SDOperand Op0Mapped;
3166     if (isSigned) {
3167       // constant used to invert sign bit (signed to unsigned mapping)
3168       SDOperand SignBit = DAG.getConstant(0x80000000u, MVT::i32);
3169       Op0Mapped = DAG.getNode(ISD::XOR, MVT::i32, Op0, SignBit);
3170     } else {
3171       Op0Mapped = Op0;
3172     }
3173     // store the lo of the constructed double - based on integer input
3174     SDOperand Store1 = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
3175                                    Op0Mapped, Lo, DAG.getSrcValue(NULL));
3176     // initial hi portion of constructed double
3177     SDOperand InitialHi = DAG.getConstant(0x43300000u, MVT::i32);
3178     // store the hi of the constructed double - biased exponent
3179     SDOperand Store2 = DAG.getNode(ISD::STORE, MVT::Other, Store1,
3180                                    InitialHi, Hi, DAG.getSrcValue(NULL));
3181     // load the constructed double
3182     SDOperand Load = DAG.getLoad(MVT::f64, Store2, StackSlot,
3183                                DAG.getSrcValue(NULL));
3184     // FP constant to bias correct the final result
3185     SDOperand Bias = DAG.getConstantFP(isSigned ?
3186                                             BitsToDouble(0x4330000080000000ULL)
3187                                           : BitsToDouble(0x4330000000000000ULL),
3188                                      MVT::f64);
3189     // subtract the bias
3190     SDOperand Sub = DAG.getNode(ISD::FSUB, MVT::f64, Load, Bias);
3191     // final result
3192     SDOperand Result;
3193     // handle final rounding
3194     if (DestVT == MVT::f64) {
3195       // do nothing
3196       Result = Sub;
3197     } else {
3198      // if f32 then cast to f32
3199       Result = DAG.getNode(ISD::FP_ROUND, MVT::f32, Sub);
3200     }
3201     return Result;
3202   }
3203   assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet");
3204   SDOperand Tmp1 = DAG.getNode(ISD::SINT_TO_FP, DestVT, Op0);
3205
3206   SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Op0,
3207                                    DAG.getConstant(0, Op0.getValueType()),
3208                                    ISD::SETLT);
3209   SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
3210   SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
3211                                     SignSet, Four, Zero);
3212
3213   // If the sign bit of the integer is set, the large number will be treated
3214   // as a negative number.  To counteract this, the dynamic code adds an
3215   // offset depending on the data type.
3216   uint64_t FF;
3217   switch (Op0.getValueType()) {
3218   default: assert(0 && "Unsupported integer type!");
3219   case MVT::i8 : FF = 0x43800000ULL; break;  // 2^8  (as a float)
3220   case MVT::i16: FF = 0x47800000ULL; break;  // 2^16 (as a float)
3221   case MVT::i32: FF = 0x4F800000ULL; break;  // 2^32 (as a float)
3222   case MVT::i64: FF = 0x5F800000ULL; break;  // 2^64 (as a float)
3223   }
3224   if (TLI.isLittleEndian()) FF <<= 32;
3225   static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
3226
3227   SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
3228   CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
3229   SDOperand FudgeInReg;
3230   if (DestVT == MVT::f32)
3231     FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
3232                              DAG.getSrcValue(NULL));
3233   else {
3234     assert(DestVT == MVT::f64 && "Unexpected conversion");
3235     FudgeInReg = LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, MVT::f64,
3236                                            DAG.getEntryNode(), CPIdx,
3237                                            DAG.getSrcValue(NULL), MVT::f32));
3238   }
3239
3240   return DAG.getNode(ISD::FADD, DestVT, Tmp1, FudgeInReg);
3241 }
3242
3243 /// PromoteLegalINT_TO_FP - This function is responsible for legalizing a
3244 /// *INT_TO_FP operation of the specified operand when the target requests that
3245 /// we promote it.  At this point, we know that the result and operand types are
3246 /// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP
3247 /// operation that takes a larger input.
3248 SDOperand SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDOperand LegalOp,
3249                                                       MVT::ValueType DestVT,
3250                                                       bool isSigned) {
3251   // First step, figure out the appropriate *INT_TO_FP operation to use.
3252   MVT::ValueType NewInTy = LegalOp.getValueType();
3253
3254   unsigned OpToUse = 0;
3255
3256   // Scan for the appropriate larger type to use.
3257   while (1) {
3258     NewInTy = (MVT::ValueType)(NewInTy+1);
3259     assert(MVT::isInteger(NewInTy) && "Ran out of possibilities!");
3260
3261     // If the target supports SINT_TO_FP of this type, use it.
3262     switch (TLI.getOperationAction(ISD::SINT_TO_FP, NewInTy)) {
3263       default: break;
3264       case TargetLowering::Legal:
3265         if (!TLI.isTypeLegal(NewInTy))
3266           break;  // Can't use this datatype.
3267         // FALL THROUGH.
3268       case TargetLowering::Custom:
3269         OpToUse = ISD::SINT_TO_FP;
3270         break;
3271     }
3272     if (OpToUse) break;
3273     if (isSigned) continue;
3274
3275     // If the target supports UINT_TO_FP of this type, use it.
3276     switch (TLI.getOperationAction(ISD::UINT_TO_FP, NewInTy)) {
3277       default: break;
3278       case TargetLowering::Legal:
3279         if (!TLI.isTypeLegal(NewInTy))
3280           break;  // Can't use this datatype.
3281         // FALL THROUGH.
3282       case TargetLowering::Custom:
3283         OpToUse = ISD::UINT_TO_FP;
3284         break;
3285     }
3286     if (OpToUse) break;
3287
3288     // Otherwise, try a larger type.
3289   }
3290
3291   // Okay, we found the operation and type to use.  Zero extend our input to the
3292   // desired type then run the operation on it.
3293   return DAG.getNode(OpToUse, DestVT,
3294                      DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND,
3295                                  NewInTy, LegalOp));
3296 }
3297
3298 /// PromoteLegalFP_TO_INT - This function is responsible for legalizing a
3299 /// FP_TO_*INT operation of the specified operand when the target requests that
3300 /// we promote it.  At this point, we know that the result and operand types are
3301 /// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT
3302 /// operation that returns a larger result.
3303 SDOperand SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDOperand LegalOp,
3304                                                       MVT::ValueType DestVT,
3305                                                       bool isSigned) {
3306   // First step, figure out the appropriate FP_TO*INT operation to use.
3307   MVT::ValueType NewOutTy = DestVT;
3308
3309   unsigned OpToUse = 0;
3310
3311   // Scan for the appropriate larger type to use.
3312   while (1) {
3313     NewOutTy = (MVT::ValueType)(NewOutTy+1);
3314     assert(MVT::isInteger(NewOutTy) && "Ran out of possibilities!");
3315
3316     // If the target supports FP_TO_SINT returning this type, use it.
3317     switch (TLI.getOperationAction(ISD::FP_TO_SINT, NewOutTy)) {
3318     default: break;
3319     case TargetLowering::Legal:
3320       if (!TLI.isTypeLegal(NewOutTy))
3321         break;  // Can't use this datatype.
3322       // FALL THROUGH.
3323     case TargetLowering::Custom:
3324       OpToUse = ISD::FP_TO_SINT;
3325       break;
3326     }
3327     if (OpToUse) break;
3328
3329     // If the target supports FP_TO_UINT of this type, use it.
3330     switch (TLI.getOperationAction(ISD::FP_TO_UINT, NewOutTy)) {
3331     default: break;
3332     case TargetLowering::Legal:
3333       if (!TLI.isTypeLegal(NewOutTy))
3334         break;  // Can't use this datatype.
3335       // FALL THROUGH.
3336     case TargetLowering::Custom:
3337       OpToUse = ISD::FP_TO_UINT;
3338       break;
3339     }
3340     if (OpToUse) break;
3341
3342     // Otherwise, try a larger type.
3343   }
3344
3345   // Okay, we found the operation and type to use.  Truncate the result of the
3346   // extended FP_TO_*INT operation to the desired size.
3347   return DAG.getNode(ISD::TRUNCATE, DestVT,
3348                      DAG.getNode(OpToUse, NewOutTy, LegalOp));
3349 }
3350
3351 /// ExpandBSWAP - Open code the operations for BSWAP of the specified operation.
3352 ///
3353 SDOperand SelectionDAGLegalize::ExpandBSWAP(SDOperand Op) {
3354   MVT::ValueType VT = Op.getValueType();
3355   MVT::ValueType SHVT = TLI.getShiftAmountTy();
3356   SDOperand Tmp1, Tmp2, Tmp3, Tmp4, Tmp5, Tmp6, Tmp7, Tmp8;
3357   switch (VT) {
3358   default: assert(0 && "Unhandled Expand type in BSWAP!"); abort();
3359   case MVT::i16:
3360     Tmp2 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
3361     Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
3362     return DAG.getNode(ISD::OR, VT, Tmp1, Tmp2);
3363   case MVT::i32:
3364     Tmp4 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(24, SHVT));
3365     Tmp3 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
3366     Tmp2 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
3367     Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(24, SHVT));
3368     Tmp3 = DAG.getNode(ISD::AND, VT, Tmp3, DAG.getConstant(0xFF0000, VT));
3369     Tmp2 = DAG.getNode(ISD::AND, VT, Tmp2, DAG.getConstant(0xFF00, VT));
3370     Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp3);
3371     Tmp2 = DAG.getNode(ISD::OR, VT, Tmp2, Tmp1);
3372     return DAG.getNode(ISD::OR, VT, Tmp4, Tmp2);
3373   case MVT::i64:
3374     Tmp8 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(56, SHVT));
3375     Tmp7 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(40, SHVT));
3376     Tmp6 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(24, SHVT));
3377     Tmp5 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
3378     Tmp4 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
3379     Tmp3 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(24, SHVT));
3380     Tmp2 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(40, SHVT));
3381     Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(56, SHVT));
3382     Tmp7 = DAG.getNode(ISD::AND, VT, Tmp7, DAG.getConstant(255ULL<<48, VT));
3383     Tmp6 = DAG.getNode(ISD::AND, VT, Tmp6, DAG.getConstant(255ULL<<40, VT));
3384     Tmp5 = DAG.getNode(ISD::AND, VT, Tmp5, DAG.getConstant(255ULL<<32, VT));
3385     Tmp4 = DAG.getNode(ISD::AND, VT, Tmp4, DAG.getConstant(255ULL<<24, VT));
3386     Tmp3 = DAG.getNode(ISD::AND, VT, Tmp3, DAG.getConstant(255ULL<<16, VT));
3387     Tmp2 = DAG.getNode(ISD::AND, VT, Tmp2, DAG.getConstant(255ULL<<8 , VT));
3388     Tmp8 = DAG.getNode(ISD::OR, VT, Tmp8, Tmp7);
3389     Tmp6 = DAG.getNode(ISD::OR, VT, Tmp6, Tmp5);
3390     Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp3);
3391     Tmp2 = DAG.getNode(ISD::OR, VT, Tmp2, Tmp1);
3392     Tmp8 = DAG.getNode(ISD::OR, VT, Tmp8, Tmp6);
3393     Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp2);
3394     return DAG.getNode(ISD::OR, VT, Tmp8, Tmp4);
3395   }
3396 }
3397
3398 /// ExpandBitCount - Expand the specified bitcount instruction into operations.
3399 ///
3400 SDOperand SelectionDAGLegalize::ExpandBitCount(unsigned Opc, SDOperand Op) {
3401   switch (Opc) {
3402   default: assert(0 && "Cannot expand this yet!");
3403   case ISD::CTPOP: {
3404     static const uint64_t mask[6] = {
3405       0x5555555555555555ULL, 0x3333333333333333ULL,
3406       0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
3407       0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
3408     };
3409     MVT::ValueType VT = Op.getValueType();
3410     MVT::ValueType ShVT = TLI.getShiftAmountTy();
3411     unsigned len = getSizeInBits(VT);
3412     for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
3413       //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
3414       SDOperand Tmp2 = DAG.getConstant(mask[i], VT);
3415       SDOperand Tmp3 = DAG.getConstant(1ULL << i, ShVT);
3416       Op = DAG.getNode(ISD::ADD, VT, DAG.getNode(ISD::AND, VT, Op, Tmp2),
3417                        DAG.getNode(ISD::AND, VT,
3418                                    DAG.getNode(ISD::SRL, VT, Op, Tmp3),Tmp2));
3419     }
3420     return Op;
3421   }
3422   case ISD::CTLZ: {
3423     // for now, we do this:
3424     // x = x | (x >> 1);
3425     // x = x | (x >> 2);
3426     // ...
3427     // x = x | (x >>16);
3428     // x = x | (x >>32); // for 64-bit input
3429     // return popcount(~x);
3430     //
3431     // but see also: http://www.hackersdelight.org/HDcode/nlz.cc
3432     MVT::ValueType VT = Op.getValueType();
3433     MVT::ValueType ShVT = TLI.getShiftAmountTy();
3434     unsigned len = getSizeInBits(VT);
3435     for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
3436       SDOperand Tmp3 = DAG.getConstant(1ULL << i, ShVT);
3437       Op = DAG.getNode(ISD::OR, VT, Op, DAG.getNode(ISD::SRL, VT, Op, Tmp3));
3438     }
3439     Op = DAG.getNode(ISD::XOR, VT, Op, DAG.getConstant(~0ULL, VT));
3440     return DAG.getNode(ISD::CTPOP, VT, Op);
3441   }
3442   case ISD::CTTZ: {
3443     // for now, we use: { return popcount(~x & (x - 1)); }
3444     // unless the target has ctlz but not ctpop, in which case we use:
3445     // { return 32 - nlz(~x & (x-1)); }
3446     // see also http://www.hackersdelight.org/HDcode/ntz.cc
3447     MVT::ValueType VT = Op.getValueType();
3448     SDOperand Tmp2 = DAG.getConstant(~0ULL, VT);
3449     SDOperand Tmp3 = DAG.getNode(ISD::AND, VT,
3450                        DAG.getNode(ISD::XOR, VT, Op, Tmp2),
3451                        DAG.getNode(ISD::SUB, VT, Op, DAG.getConstant(1, VT)));
3452     // If ISD::CTLZ is legal and CTPOP isn't, then do that instead.
3453     if (!TLI.isOperationLegal(ISD::CTPOP, VT) &&
3454         TLI.isOperationLegal(ISD::CTLZ, VT))
3455       return DAG.getNode(ISD::SUB, VT,
3456                          DAG.getConstant(getSizeInBits(VT), VT),
3457                          DAG.getNode(ISD::CTLZ, VT, Tmp3));
3458     return DAG.getNode(ISD::CTPOP, VT, Tmp3);
3459   }
3460   }
3461 }
3462
3463
3464 /// ExpandOp - Expand the specified SDOperand into its two component pieces
3465 /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
3466 /// LegalizeNodes map is filled in for any results that are not expanded, the
3467 /// ExpandedNodes map is filled in for any results that are expanded, and the
3468 /// Lo/Hi values are returned.
3469 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
3470   MVT::ValueType VT = Op.getValueType();
3471   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
3472   SDNode *Node = Op.Val;
3473   assert(getTypeAction(VT) == Expand && "Not an expanded type!");
3474   assert((MVT::isInteger(VT) || VT == MVT::Vector) &&
3475          "Cannot expand FP values!");
3476   assert(((MVT::isInteger(NVT) && NVT < VT) || VT == MVT::Vector) &&
3477          "Cannot expand to FP value or to larger int value!");
3478
3479   // See if we already expanded it.
3480   std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
3481     = ExpandedNodes.find(Op);
3482   if (I != ExpandedNodes.end()) {
3483     Lo = I->second.first;
3484     Hi = I->second.second;
3485     return;
3486   }
3487
3488   switch (Node->getOpcode()) {
3489   case ISD::CopyFromReg:
3490     assert(0 && "CopyFromReg must be legal!");
3491   default:
3492     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
3493     assert(0 && "Do not know how to expand this operator!");
3494     abort();
3495   case ISD::UNDEF:
3496     Lo = DAG.getNode(ISD::UNDEF, NVT);
3497     Hi = DAG.getNode(ISD::UNDEF, NVT);
3498     break;
3499   case ISD::Constant: {
3500     uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
3501     Lo = DAG.getConstant(Cst, NVT);
3502     Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
3503     break;
3504   }
3505   case ISD::ConstantVec: {
3506     unsigned NumElements = Node->getNumOperands();
3507     // If we only have two elements left in the constant vector, just break it
3508     // apart into the two scalar constants it contains.  Otherwise, bisect the
3509     // ConstantVec, and return each half as a new ConstantVec.
3510     // FIXME: this is hard coded as big endian, it may have to change to support
3511     // SSE and Alpha MVI
3512     if (NumElements == 2) {
3513       Hi = Node->getOperand(0);
3514       Lo = Node->getOperand(1);
3515     } else {
3516       NumElements /= 2;
3517       std::vector<SDOperand> LoOps, HiOps;
3518       for (unsigned I = 0, E = NumElements; I < E; ++I) {
3519         HiOps.push_back(Node->getOperand(I));
3520         LoOps.push_back(Node->getOperand(I+NumElements));
3521       }
3522       Lo = DAG.getNode(ISD::ConstantVec, MVT::Vector, LoOps);
3523       Hi = DAG.getNode(ISD::ConstantVec, MVT::Vector, HiOps);
3524     }
3525     break;
3526   }
3527
3528   case ISD::BUILD_PAIR:
3529     // Return the operands.
3530     Lo = Node->getOperand(0);
3531     Hi = Node->getOperand(1);
3532     break;
3533
3534   case ISD::SIGN_EXTEND_INREG:
3535     ExpandOp(Node->getOperand(0), Lo, Hi);
3536     // Sign extend the lo-part.
3537     Hi = DAG.getNode(ISD::SRA, NVT, Lo,
3538                      DAG.getConstant(MVT::getSizeInBits(NVT)-1,
3539                                      TLI.getShiftAmountTy()));
3540     // sext_inreg the low part if needed.
3541     Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Lo, Node->getOperand(1));
3542     break;
3543
3544   case ISD::BSWAP: {
3545     ExpandOp(Node->getOperand(0), Lo, Hi);
3546     SDOperand TempLo = DAG.getNode(ISD::BSWAP, NVT, Hi);
3547     Hi = DAG.getNode(ISD::BSWAP, NVT, Lo);
3548     Lo = TempLo;
3549     break;
3550   }
3551
3552   case ISD::CTPOP:
3553     ExpandOp(Node->getOperand(0), Lo, Hi);
3554     Lo = DAG.getNode(ISD::ADD, NVT,          // ctpop(HL) -> ctpop(H)+ctpop(L)
3555                      DAG.getNode(ISD::CTPOP, NVT, Lo),
3556                      DAG.getNode(ISD::CTPOP, NVT, Hi));
3557     Hi = DAG.getConstant(0, NVT);
3558     break;
3559
3560   case ISD::CTLZ: {
3561     // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32)
3562     ExpandOp(Node->getOperand(0), Lo, Hi);
3563     SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
3564     SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
3565     SDOperand TopNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), HLZ, BitsC,
3566                                         ISD::SETNE);
3567     SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo);
3568     LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC);
3569
3570     Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart);
3571     Hi = DAG.getConstant(0, NVT);
3572     break;
3573   }
3574
3575   case ISD::CTTZ: {
3576     // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32)
3577     ExpandOp(Node->getOperand(0), Lo, Hi);
3578     SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
3579     SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
3580     SDOperand BotNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), LTZ, BitsC,
3581                                         ISD::SETNE);
3582     SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi);
3583     HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC);
3584
3585     Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart);
3586     Hi = DAG.getConstant(0, NVT);
3587     break;
3588   }
3589
3590   case ISD::VAARG: {
3591     SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
3592     SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
3593     Lo = DAG.getVAArg(NVT, Ch, Ptr, Node->getOperand(2));
3594     Hi = DAG.getVAArg(NVT, Lo.getValue(1), Ptr, Node->getOperand(2));
3595
3596     // Remember that we legalized the chain.
3597     Hi = LegalizeOp(Hi);
3598     AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
3599     if (!TLI.isLittleEndian())
3600       std::swap(Lo, Hi);
3601     break;
3602   }
3603
3604   case ISD::LOAD: {
3605     SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
3606     SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
3607     Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
3608
3609     // Increment the pointer to the other half.
3610     unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
3611     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
3612                       getIntPtrConstant(IncrementSize));
3613     // FIXME: This creates a bogus srcvalue!
3614     Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
3615
3616     // Build a factor node to remember that this load is independent of the
3617     // other one.
3618     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
3619                                Hi.getValue(1));
3620
3621     // Remember that we legalized the chain.
3622     AddLegalizedOperand(Op.getValue(1), LegalizeOp(TF));
3623     if (!TLI.isLittleEndian())
3624       std::swap(Lo, Hi);
3625     break;
3626   }
3627   case ISD::VLOAD: {
3628     SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
3629     SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
3630     unsigned NumElements =cast<ConstantSDNode>(Node->getOperand(2))->getValue();
3631     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
3632
3633     // If we only have two elements, turn into a pair of scalar loads.
3634     // FIXME: handle case where a vector of two elements is fine, such as
3635     //   2 x double on SSE2.
3636     if (NumElements == 2) {
3637       Lo = DAG.getLoad(EVT, Ch, Ptr, Node->getOperand(4));
3638       // Increment the pointer to the other half.
3639       unsigned IncrementSize = MVT::getSizeInBits(EVT)/8;
3640       Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
3641                         getIntPtrConstant(IncrementSize));
3642       // FIXME: This creates a bogus srcvalue!
3643       Hi = DAG.getLoad(EVT, Ch, Ptr, Node->getOperand(4));
3644     } else {
3645       NumElements /= 2; // Split the vector in half
3646       Lo = DAG.getVecLoad(NumElements, EVT, Ch, Ptr, Node->getOperand(4));
3647       unsigned IncrementSize = NumElements * MVT::getSizeInBits(EVT)/8;
3648       Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
3649                         getIntPtrConstant(IncrementSize));
3650       // FIXME: This creates a bogus srcvalue!
3651       Hi = DAG.getVecLoad(NumElements, EVT, Ch, Ptr, Node->getOperand(4));
3652     }
3653
3654     // Build a factor node to remember that this load is independent of the
3655     // other one.
3656     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
3657                                Hi.getValue(1));
3658
3659     // Remember that we legalized the chain.
3660     AddLegalizedOperand(Op.getValue(1), LegalizeOp(TF));
3661     if (!TLI.isLittleEndian())
3662       std::swap(Lo, Hi);
3663     break;
3664   }
3665   case ISD::VADD:
3666   case ISD::VSUB:
3667   case ISD::VMUL: {
3668     unsigned NumElements =cast<ConstantSDNode>(Node->getOperand(2))->getValue();
3669     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
3670     SDOperand LL, LH, RL, RH;
3671
3672     ExpandOp(Node->getOperand(0), LL, LH);
3673     ExpandOp(Node->getOperand(1), RL, RH);
3674
3675     // If we only have two elements, turn into a pair of scalar loads.
3676     // FIXME: handle case where a vector of two elements is fine, such as
3677     //   2 x double on SSE2.
3678     if (NumElements == 2) {
3679       unsigned Opc = getScalarizedOpcode(Node->getOpcode(), EVT);
3680       Lo = DAG.getNode(Opc, EVT, LL, RL);
3681       Hi = DAG.getNode(Opc, EVT, LH, RH);
3682     } else {
3683       Lo = DAG.getNode(Node->getOpcode(), MVT::Vector, LL, RL, LL.getOperand(2),
3684                        LL.getOperand(3));
3685       Hi = DAG.getNode(Node->getOpcode(), MVT::Vector, LH, RH, LH.getOperand(2),
3686                        LH.getOperand(3));
3687     }
3688     break;
3689   }
3690   case ISD::AND:
3691   case ISD::OR:
3692   case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
3693     SDOperand LL, LH, RL, RH;
3694     ExpandOp(Node->getOperand(0), LL, LH);
3695     ExpandOp(Node->getOperand(1), RL, RH);
3696     Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
3697     Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
3698     break;
3699   }
3700   case ISD::SELECT: {
3701     SDOperand LL, LH, RL, RH;
3702     ExpandOp(Node->getOperand(1), LL, LH);
3703     ExpandOp(Node->getOperand(2), RL, RH);
3704     Lo = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), LL, RL);
3705     Hi = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), LH, RH);
3706     break;
3707   }
3708   case ISD::SELECT_CC: {
3709     SDOperand TL, TH, FL, FH;
3710     ExpandOp(Node->getOperand(2), TL, TH);
3711     ExpandOp(Node->getOperand(3), FL, FH);
3712     Lo = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
3713                      Node->getOperand(1), TL, FL, Node->getOperand(4));
3714     Hi = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
3715                      Node->getOperand(1), TH, FH, Node->getOperand(4));
3716     break;
3717   }
3718   case ISD::SEXTLOAD: {
3719     SDOperand Chain = Node->getOperand(0);
3720     SDOperand Ptr   = Node->getOperand(1);
3721     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
3722
3723     if (EVT == NVT)
3724       Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2));
3725     else
3726       Lo = DAG.getExtLoad(ISD::SEXTLOAD, NVT, Chain, Ptr, Node->getOperand(2),
3727                           EVT);
3728
3729     // Remember that we legalized the chain.
3730     AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
3731
3732     // The high part is obtained by SRA'ing all but one of the bits of the lo
3733     // part.
3734     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
3735     Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1,
3736                                                        TLI.getShiftAmountTy()));
3737     break;
3738   }
3739   case ISD::ZEXTLOAD: {
3740     SDOperand Chain = Node->getOperand(0);
3741     SDOperand Ptr   = Node->getOperand(1);
3742     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
3743
3744     if (EVT == NVT)
3745       Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2));
3746     else
3747       Lo = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Chain, Ptr, Node->getOperand(2),
3748                           EVT);
3749
3750     // Remember that we legalized the chain.
3751     AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
3752
3753     // The high part is just a zero.
3754     Hi = DAG.getConstant(0, NVT);
3755     break;
3756   }
3757   case ISD::EXTLOAD: {
3758     SDOperand Chain = Node->getOperand(0);
3759     SDOperand Ptr   = Node->getOperand(1);
3760     MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
3761
3762     if (EVT == NVT)
3763       Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2));
3764     else
3765       Lo = DAG.getExtLoad(ISD::EXTLOAD, NVT, Chain, Ptr, Node->getOperand(2),
3766                           EVT);
3767
3768     // Remember that we legalized the chain.
3769     AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
3770
3771     // The high part is undefined.
3772     Hi = DAG.getNode(ISD::UNDEF, NVT);
3773     break;
3774   }
3775   case ISD::ANY_EXTEND:
3776     // The low part is any extension of the input (which degenerates to a copy).
3777     Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, Node->getOperand(0));
3778     // The high part is undefined.
3779     Hi = DAG.getNode(ISD::UNDEF, NVT);
3780     break;
3781   case ISD::SIGN_EXTEND: {
3782     // The low part is just a sign extension of the input (which degenerates to
3783     // a copy).
3784     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, Node->getOperand(0));
3785
3786     // The high part is obtained by SRA'ing all but one of the bits of the lo
3787     // part.
3788     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
3789     Hi = DAG.getNode(ISD::SRA, NVT, Lo,
3790                      DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
3791     break;
3792   }
3793   case ISD::ZERO_EXTEND:
3794     // The low part is just a zero extension of the input (which degenerates to
3795     // a copy).
3796     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, Node->getOperand(0));
3797
3798     // The high part is just a zero.
3799     Hi = DAG.getConstant(0, NVT);
3800     break;
3801
3802   case ISD::BIT_CONVERT: {
3803     SDOperand Tmp = ExpandBIT_CONVERT(Node->getValueType(0),
3804                                       Node->getOperand(0));
3805     ExpandOp(Tmp, Lo, Hi);
3806     break;
3807   }
3808
3809   case ISD::READCYCLECOUNTER:
3810     assert(TLI.getOperationAction(ISD::READCYCLECOUNTER, VT) ==
3811                  TargetLowering::Custom &&
3812            "Must custom expand ReadCycleCounter");
3813     Lo = TLI.LowerOperation(Op, DAG);
3814     assert(Lo.Val && "Node must be custom expanded!");
3815     Hi = Lo.getValue(1);
3816     AddLegalizedOperand(SDOperand(Node, 1), // Remember we legalized the chain.
3817                         LegalizeOp(Lo.getValue(2)));
3818     break;
3819
3820     // These operators cannot be expanded directly, emit them as calls to
3821     // library functions.
3822   case ISD::FP_TO_SINT:
3823     if (TLI.getOperationAction(ISD::FP_TO_SINT, VT) == TargetLowering::Custom) {
3824       SDOperand Op;
3825       switch (getTypeAction(Node->getOperand(0).getValueType())) {
3826       case Expand: assert(0 && "cannot expand FP!");
3827       case Legal:   Op = LegalizeOp(Node->getOperand(0)); break;
3828       case Promote: Op = PromoteOp (Node->getOperand(0)); break;
3829       }
3830
3831       Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_SINT, VT, Op), DAG);
3832
3833       // Now that the custom expander is done, expand the result, which is still
3834       // VT.
3835       if (Op.Val) {
3836         ExpandOp(Op, Lo, Hi);
3837         break;
3838       }
3839     }
3840
3841     if (Node->getOperand(0).getValueType() == MVT::f32)
3842       Lo = ExpandLibCall("__fixsfdi", Node, Hi);
3843     else
3844       Lo = ExpandLibCall("__fixdfdi", Node, Hi);
3845     break;
3846
3847   case ISD::FP_TO_UINT:
3848     if (TLI.getOperationAction(ISD::FP_TO_UINT, VT) == TargetLowering::Custom) {
3849       SDOperand Op;
3850       switch (getTypeAction(Node->getOperand(0).getValueType())) {
3851         case Expand: assert(0 && "cannot expand FP!");
3852         case Legal:   Op = LegalizeOp(Node->getOperand(0)); break;
3853         case Promote: Op = PromoteOp (Node->getOperand(0)); break;
3854       }
3855
3856       Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_UINT, VT, Op), DAG);
3857
3858       // Now that the custom expander is done, expand the result.
3859       if (Op.Val) {
3860         ExpandOp(Op, Lo, Hi);
3861         break;
3862       }
3863     }
3864
3865     if (Node->getOperand(0).getValueType() == MVT::f32)
3866       Lo = ExpandLibCall("__fixunssfdi", Node, Hi);
3867     else
3868       Lo = ExpandLibCall("__fixunsdfdi", Node, Hi);
3869     break;
3870
3871   case ISD::SHL: {
3872     // If the target wants custom lowering, do so.
3873     SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
3874     if (TLI.getOperationAction(ISD::SHL, VT) == TargetLowering::Custom) {
3875       SDOperand Op = DAG.getNode(ISD::SHL, VT, Node->getOperand(0), ShiftAmt);
3876       Op = TLI.LowerOperation(Op, DAG);
3877       if (Op.Val) {
3878         // Now that the custom expander is done, expand the result, which is
3879         // still VT.
3880         ExpandOp(Op, Lo, Hi);
3881         break;
3882       }
3883     }
3884
3885     // If we can emit an efficient shift operation, do so now.
3886     if (ExpandShift(ISD::SHL, Node->getOperand(0), ShiftAmt, Lo, Hi))
3887       break;
3888
3889     // If this target supports SHL_PARTS, use it.
3890     TargetLowering::LegalizeAction Action =
3891       TLI.getOperationAction(ISD::SHL_PARTS, NVT);
3892     if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
3893         Action == TargetLowering::Custom) {
3894       ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
3895       break;
3896     }
3897
3898     // Otherwise, emit a libcall.
3899     Lo = ExpandLibCall("__ashldi3", Node, Hi);
3900     break;
3901   }
3902
3903   case ISD::SRA: {
3904     // If the target wants custom lowering, do so.
3905     SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
3906     if (TLI.getOperationAction(ISD::SRA, VT) == TargetLowering::Custom) {
3907       SDOperand Op = DAG.getNode(ISD::SRA, VT, Node->getOperand(0), ShiftAmt);
3908       Op = TLI.LowerOperation(Op, DAG);
3909       if (Op.Val) {
3910         // Now that the custom expander is done, expand the result, which is
3911         // still VT.
3912         ExpandOp(Op, Lo, Hi);
3913         break;
3914       }
3915     }
3916
3917     // If we can emit an efficient shift operation, do so now.
3918     if (ExpandShift(ISD::SRA, Node->getOperand(0), ShiftAmt, Lo, Hi))
3919       break;
3920
3921     // If this target supports SRA_PARTS, use it.
3922     TargetLowering::LegalizeAction Action =
3923       TLI.getOperationAction(ISD::SRA_PARTS, NVT);
3924     if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
3925         Action == TargetLowering::Custom) {
3926       ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
3927       break;
3928     }
3929
3930     // Otherwise, emit a libcall.
3931     Lo = ExpandLibCall("__ashrdi3", Node, Hi);
3932     break;
3933   }
3934
3935   case ISD::SRL: {
3936     // If the target wants custom lowering, do so.
3937     SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
3938     if (TLI.getOperationAction(ISD::SRL, VT) == TargetLowering::Custom) {
3939       SDOperand Op = DAG.getNode(ISD::SRL, VT, Node->getOperand(0), ShiftAmt);
3940       Op = TLI.LowerOperation(Op, DAG);
3941       if (Op.Val) {
3942         // Now that the custom expander is done, expand the result, which is
3943         // still VT.
3944         ExpandOp(Op, Lo, Hi);
3945         break;
3946       }
3947     }
3948
3949     // If we can emit an efficient shift operation, do so now.
3950     if (ExpandShift(ISD::SRL, Node->getOperand(0), ShiftAmt, Lo, Hi))
3951       break;
3952
3953     // If this target supports SRL_PARTS, use it.
3954     TargetLowering::LegalizeAction Action =
3955       TLI.getOperationAction(ISD::SRL_PARTS, NVT);
3956     if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
3957         Action == TargetLowering::Custom) {
3958       ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
3959       break;
3960     }
3961
3962     // Otherwise, emit a libcall.
3963     Lo = ExpandLibCall("__lshrdi3", Node, Hi);
3964     break;
3965   }
3966
3967   case ISD::ADD:
3968   case ISD::SUB: {
3969     // If the target wants to custom expand this, let them.
3970     if (TLI.getOperationAction(Node->getOpcode(), VT) ==
3971             TargetLowering::Custom) {
3972       Op = TLI.LowerOperation(Op, DAG);
3973       if (Op.Val) {
3974         ExpandOp(Op, Lo, Hi);
3975         break;
3976       }
3977     }
3978
3979     // Expand the subcomponents.
3980     SDOperand LHSL, LHSH, RHSL, RHSH;
3981     ExpandOp(Node->getOperand(0), LHSL, LHSH);
3982     ExpandOp(Node->getOperand(1), RHSL, RHSH);
3983
3984     std::vector<SDOperand> Ops;
3985     Ops.push_back(LHSL);
3986     Ops.push_back(LHSH);
3987     Ops.push_back(RHSL);
3988     Ops.push_back(RHSH);
3989     std::vector<MVT::ValueType> VTs(2, LHSL.getValueType());
3990     unsigned Opc =
3991       Node->getOpcode() == ISD::ADD ? ISD::ADD_PARTS : ISD::SUB_PARTS;
3992     Lo = DAG.getNode(Opc, VTs, Ops);
3993     Hi = Lo.getValue(1);
3994     break;
3995   }
3996   case ISD::MUL: {
3997     if (TLI.isOperationLegal(ISD::MULHU, NVT)) {
3998       SDOperand LL, LH, RL, RH;
3999       ExpandOp(Node->getOperand(0), LL, LH);
4000       ExpandOp(Node->getOperand(1), RL, RH);
4001       unsigned SH = MVT::getSizeInBits(RH.getValueType())-1;
4002       // MULHS implicitly sign extends its inputs.  Check to see if ExpandOp
4003       // extended the sign bit of the low half through the upper half, and if so
4004       // emit a MULHS instead of the alternate sequence that is valid for any
4005       // i64 x i64 multiply.
4006       if (TLI.isOperationLegal(ISD::MULHS, NVT) &&
4007           // is RH an extension of the sign bit of RL?
4008           RH.getOpcode() == ISD::SRA && RH.getOperand(0) == RL &&
4009           RH.getOperand(1).getOpcode() == ISD::Constant &&
4010           cast<ConstantSDNode>(RH.getOperand(1))->getValue() == SH &&
4011           // is LH an extension of the sign bit of LL?
4012           LH.getOpcode() == ISD::SRA && LH.getOperand(0) == LL &&
4013           LH.getOperand(1).getOpcode() == ISD::Constant &&
4014           cast<ConstantSDNode>(LH.getOperand(1))->getValue() == SH) {
4015         Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL);
4016       } else {
4017         Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
4018         RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
4019         LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
4020         Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
4021         Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
4022       }
4023       Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
4024     } else {
4025       Lo = ExpandLibCall("__muldi3" , Node, Hi);
4026     }
4027     break;
4028   }
4029   case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break;
4030   case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break;
4031   case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break;
4032   case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break;
4033   }
4034
4035   // Make sure the resultant values have been legalized themselves, unless this
4036   // is a type that requires multi-step expansion.
4037   if (getTypeAction(NVT) != Expand && NVT != MVT::isVoid) {
4038     Lo = LegalizeOp(Lo);
4039     Hi = LegalizeOp(Hi);
4040   }
4041
4042   // Remember in a map if the values will be reused later.
4043   bool isNew =
4044     ExpandedNodes.insert(std::make_pair(Op, std::make_pair(Lo, Hi))).second;
4045   assert(isNew && "Value already expanded?!?");
4046 }
4047
4048
4049 // SelectionDAG::Legalize - This is the entry point for the file.
4050 //
4051 void SelectionDAG::Legalize() {
4052   /// run - This is the main entry point to this class.
4053   ///
4054   SelectionDAGLegalize(*this).LegalizeDAG();
4055 }
4056