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/MachineConstantPool.h"
  16 #include "llvm/CodeGen/MachineFunction.h"
  17 #include "llvm/CodeGen/MachineFrameInfo.h"
  18 #include "llvm/Target/TargetLowering.h"
  19 #include "llvm/Target/TargetData.h"
  20 #include "llvm/Target/TargetOptions.h"
  21 #include "llvm/Constants.h"
  22 #include <iostream>
  23 using namespace llvm;
  24
  25 //===----------------------------------------------------------------------===//
  26 /// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and
  27 /// hacks on it until the target machine can handle it.  This involves
  28 /// eliminating value sizes the machine cannot handle (promoting small sizes to
  29 /// large sizes or splitting up large values into small values) as well as
  30 /// eliminating operations the machine cannot handle.
  31 ///
  32 /// This code also does a small amount of optimization and recognition of idioms
  33 /// as part of its processing.  For example, if a target does not support a
  34 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
  35 /// will attempt merge setcc and brc instructions into brcc's.
  36 ///
  37 namespace {
  38 class SelectionDAGLegalize {
  39   TargetLowering &TLI;
  40   SelectionDAG &DAG;
  41
  42   /// LegalizeAction - This enum indicates what action we should take for each
  43   /// value type the can occur in the program.
  44   enum LegalizeAction {
  45     Legal,            // The target natively supports this value type.
  46     Promote,          // This should be promoted to the next larger type.
  47     Expand,           // This integer type should be broken into smaller pieces.
  48   };
  49
  50   /// ValueTypeActions - This is a bitvector that contains two bits for each
  51   /// value type, where the two bits correspond to the LegalizeAction enum.
  52   /// This can be queried with "getTypeAction(VT)".
  53   unsigned ValueTypeActions;
  54
  55   /// NeedsAnotherIteration - This is set when we expand a large integer
  56   /// operation into smaller integer operations, but the smaller operations are
  57   /// not set.  This occurs only rarely in practice, for targets that don't have
  58   /// 32-bit or larger integer registers.
  59   bool NeedsAnotherIteration;
  60
  61   /// LegalizedNodes - For nodes that are of legal width, and that have more
  62   /// than one use, this map indicates what regularized operand to use.  This
  63   /// allows us to avoid legalizing the same thing more than once.
  64   std::map<SDOperand, SDOperand> LegalizedNodes;
  65
  66   /// PromotedNodes - For nodes that are below legal width, and that have more
  67   /// than one use, this map indicates what promoted value to use.  This allows
  68   /// us to avoid promoting the same thing more than once.
  69   std::map<SDOperand, SDOperand> PromotedNodes;
  70
  71   /// ExpandedNodes - For nodes that need to be expanded, and which have more
  72   /// than one use, this map indicates which which operands are the expanded
  73   /// version of the input.  This allows us to avoid expanding the same node
  74   /// more than once.
  75   std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
  76
  77   void AddLegalizedOperand(SDOperand From, SDOperand To) {
  78     bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second;
  79     assert(isNew && "Got into the map somehow?");
  80   }
  81   void AddPromotedOperand(SDOperand From, SDOperand To) {
  82     bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second;
  83     assert(isNew && "Got into the map somehow?");
  84   }
  85
  86 public:
  87
  88   SelectionDAGLegalize(TargetLowering &TLI, SelectionDAG &DAG);
  89
  90   /// Run - While there is still lowering to do, perform a pass over the DAG.
  91   /// Most regularization can be done in a single pass, but targets that require
  92   /// large values to be split into registers multiple times (e.g. i64 -> 4x
  93   /// i16) require iteration for these values (the first iteration will demote
  94   /// to i32, the second will demote to i16).
  95   void Run() {
  96     do {
  97       NeedsAnotherIteration = false;
  98       LegalizeDAG();
  99     } while (NeedsAnotherIteration);
 100   }
 101
 102   /// getTypeAction - Return how we should legalize values of this type, either
 103   /// it is already legal or we need to expand it into multiple registers of
 104   /// smaller integer type, or we need to promote it to a larger type.
 105   LegalizeAction getTypeAction(MVT::ValueType VT) const {
 106     return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3);
 107   }
 108
 109   /// isTypeLegal - Return true if this type is legal on this target.
 110   ///
 111   bool isTypeLegal(MVT::ValueType VT) const {
 112     return getTypeAction(VT) == Legal;
 113   }
 114
 115 private:
 116   void LegalizeDAG();
 117
 118   SDOperand LegalizeOp(SDOperand O);
 119   void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
 120   SDOperand PromoteOp(SDOperand O);
 121
 122   bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt,
 123                    SDOperand &Lo, SDOperand &Hi);
 124   void ExpandAddSub(bool isAdd, SDOperand Op, SDOperand Amt,
 125                     SDOperand &Lo, SDOperand &Hi);
 126
 127   SDOperand getIntPtrConstant(uint64_t Val) {
 128     return DAG.getConstant(Val, TLI.getPointerTy());
 129   }
 130 };
 131 }
 132
 133
 134 SelectionDAGLegalize::SelectionDAGLegalize(TargetLowering &tli,
 135                                            SelectionDAG &dag)
 136   : TLI(tli), DAG(dag), ValueTypeActions(TLI.getValueTypeActions()) {
 137   assert(MVT::LAST_VALUETYPE <= 16 &&
 138          "Too many value types for ValueTypeActions to hold!");
 139 }
 140
 141 void SelectionDAGLegalize::LegalizeDAG() {
 142   SDOperand OldRoot = DAG.getRoot();
 143   SDOperand NewRoot = LegalizeOp(OldRoot);
 144   DAG.setRoot(NewRoot);
 145
 146   ExpandedNodes.clear();
 147   LegalizedNodes.clear();
 148   PromotedNodes.clear();
 149
 150   // Remove dead nodes now.
 151   DAG.RemoveDeadNodes(OldRoot.Val);
 152 }
 153
 154 SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 155   assert(getTypeAction(Op.getValueType()) == Legal &&
 156          "Caller should expand or promote operands that are not legal!");
 157
 158   // If this operation defines any values that cannot be represented in a
 159   // register on this target, make sure to expand or promote them.
 160   if (Op.Val->getNumValues() > 1) {
 161     for (unsigned i = 0, e = Op.Val->getNumValues(); i != e; ++i)
 162       switch (getTypeAction(Op.Val->getValueType(i))) {
 163       case Legal: break;  // Nothing to do.
 164       case Expand: {
 165         SDOperand T1, T2;
 166         ExpandOp(Op.getValue(i), T1, T2);
 167         assert(LegalizedNodes.count(Op) &&
 168                "Expansion didn't add legal operands!");
 169         return LegalizedNodes[Op];
 170       }
 171       case Promote:
 172         PromoteOp(Op.getValue(i));
 173         assert(LegalizedNodes.count(Op) &&
 174                "Expansion didn't add legal operands!");
 175         return LegalizedNodes[Op];
 176       }
 177   }
 178
 179   std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
 180   if (I != LegalizedNodes.end()) return I->second;
 181
 182   SDOperand Tmp1, Tmp2, Tmp3;
 183
 184   SDOperand Result = Op;
 185   SDNode *Node = Op.Val;
 186
 187   switch (Node->getOpcode()) {
 188   default:
 189     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 190     assert(0 && "Do not know how to legalize this operator!");
 191     abort();
 192   case ISD::EntryToken:
 193   case ISD::FrameIndex:
 194   case ISD::GlobalAddress:
 195   case ISD::ExternalSymbol:
 196   case ISD::ConstantPool:           // Nothing to do.
 197     assert(getTypeAction(Node->getValueType(0)) == Legal &&
 198            "This must be legal!");
 199     break;
 200   case ISD::CopyFromReg:
 201     Tmp1 = LegalizeOp(Node->getOperand(0));
 202     if (Tmp1 != Node->getOperand(0))
 203       Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(),
 204                                   Node->getValueType(0), Tmp1);
 205     break;
 206   case ISD::ImplicitDef:
 207     Tmp1 = LegalizeOp(Node->getOperand(0));
 208     if (Tmp1 != Node->getOperand(0))
 209       Result = DAG.getImplicitDef(Tmp1, cast<RegSDNode>(Node)->getReg());
 210     break;
 211   case ISD::Constant:
 212     // We know we don't need to expand constants here, constants only have one
 213     // value and we check that it is fine above.
 214
 215     // FIXME: Maybe we should handle things like targets that don't support full
 216     // 32-bit immediates?
 217     break;
 218   case ISD::ConstantFP: {
 219     // Spill FP immediates to the constant pool if the target cannot directly
 220     // codegen them.  Targets often have some immediate values that can be
 221     // efficiently generated into an FP register without a load.  We explicitly
 222     // leave these constants as ConstantFP nodes for the target to deal with.
 223
 224     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
 225
 226     // Check to see if this FP immediate is already legal.
 227     bool isLegal = false;
 228     for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
 229            E = TLI.legal_fpimm_end(); I != E; ++I)
 230       if (CFP->isExactlyValue(*I)) {
 231         isLegal = true;
 232         break;
 233       }
 234
 235     if (!isLegal) {
 236       // Otherwise we need to spill the constant to memory.
 237       MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
 238
 239       bool Extend = false;
 240
 241       // If a FP immediate is precise when represented as a float, we put it
 242       // into the constant pool as a float, even if it's is statically typed
 243       // as a double.
 244       MVT::ValueType VT = CFP->getValueType(0);
 245       bool isDouble = VT == MVT::f64;
 246       ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
 247                                              Type::FloatTy, CFP->getValue());
 248       if (isDouble && CFP->isExactlyValue((float)CFP->getValue())) {
 249         LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
 250         VT = MVT::f32;
 251         Extend = true;
 252       }
 253
 254       SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC),
 255                                             TLI.getPointerTy());
 256       if (Extend) {
 257         Result = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), CPIdx,
 258                              MVT::f32);
 259       } else {
 260         Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx);
 261       }
 262     }
 263     break;
 264   }
 265   case ISD::TokenFactor: {
 266     std::vector<SDOperand> Ops;
 267     bool Changed = false;
 268     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
 269       SDOperand Op = Node->getOperand(i);
 270       // Fold single-use TokenFactor nodes into this token factor as we go.
 271       if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) {
 272         Changed = true;
 273         for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j)
 274           Ops.push_back(LegalizeOp(Op.getOperand(j)));
 275       } else {
 276         Ops.push_back(LegalizeOp(Op));  // Legalize the operands
 277         Changed |= Ops[i] != Op;
 278       }
 279     }
 280     if (Changed)
 281       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops);
 282     break;
 283   }
 284
 285   case ISD::ADJCALLSTACKDOWN:
 286   case ISD::ADJCALLSTACKUP:
 287     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 288     // There is no need to legalize the size argument (Operand #1)
 289     if (Tmp1 != Node->getOperand(0))
 290       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1,
 291                            Node->getOperand(1));
 292     break;
 293   case ISD::DYNAMIC_STACKALLOC:
 294     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 295     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
 296     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
 297     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 298         Tmp3 != Node->getOperand(2))
 299       Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0),
 300                            Tmp1, Tmp2, Tmp3);
 301     else
 302       Result = Op.getValue(0);
 303
 304     // Since this op produces two values, make sure to remember that we
 305     // legalized both of them.
 306     AddLegalizedOperand(SDOperand(Node, 0), Result);
 307     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 308     return Result.getValue(Op.ResNo);
 309
 310   case ISD::CALL: {
 311     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 312     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
 313
 314     bool Changed = false;
 315     std::vector<SDOperand> Ops;
 316     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
 317       Ops.push_back(LegalizeOp(Node->getOperand(i)));
 318       Changed |= Ops.back() != Node->getOperand(i);
 319     }
 320
 321     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Changed) {
 322       std::vector<MVT::ValueType> RetTyVTs;
 323       RetTyVTs.reserve(Node->getNumValues());
 324       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 325         RetTyVTs.push_back(Node->getValueType(i));
 326       Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops), 0);
 327     } else {
 328       Result = Result.getValue(0);
 329     }
 330     // Since calls produce multiple values, make sure to remember that we
 331     // legalized all of them.
 332     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 333       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
 334     return Result.getValue(Op.ResNo);
 335   }
 336   case ISD::BR:
 337     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 338     if (Tmp1 != Node->getOperand(0))
 339       Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1));
 340     break;
 341
 342   case ISD::BRCOND:
 343     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 344
 345     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 346     case Expand: assert(0 && "It's impossible to expand bools");
 347     case Legal:
 348       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
 349       break;
 350     case Promote:
 351       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
 352       break;
 353     }
 354     // Basic block destination (Op#2) is always legal.
 355     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 356       Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
 357                            Node->getOperand(2));
 358     break;
 359
 360   case ISD::LOAD:
 361     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 362     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 363     if (Tmp1 != Node->getOperand(0) ||
 364         Tmp2 != Node->getOperand(1))
 365       Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2);
 366     else
 367       Result = SDOperand(Node, 0);
 368
 369     // Since loads produce two values, make sure to remember that we legalized
 370     // both of them.
 371     AddLegalizedOperand(SDOperand(Node, 0), Result);
 372     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 373     return Result.getValue(Op.ResNo);
 374
 375   case ISD::EXTLOAD:
 376   case ISD::SEXTLOAD:
 377   case ISD::ZEXTLOAD:
 378     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 379     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 380     if (Tmp1 != Node->getOperand(0) ||
 381         Tmp2 != Node->getOperand(1))
 382       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, Tmp2,
 383                            cast<MVTSDNode>(Node)->getExtraValueType());
 384     else
 385       Result = SDOperand(Node, 0);
 386
 387     // Since loads produce two values, make sure to remember that we legalized
 388     // both of them.
 389     AddLegalizedOperand(SDOperand(Node, 0), Result);
 390     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 391     return Result.getValue(Op.ResNo);
 392
 393   case ISD::EXTRACT_ELEMENT:
 394     // Get both the low and high parts.
 395     ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 396     if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
 397       Result = Tmp2;  // 1 -> Hi
 398     else
 399       Result = Tmp1;  // 0 -> Lo
 400     break;
 401
 402   case ISD::CopyToReg:
 403     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 404
 405     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 406     case Legal:
 407       // Legalize the incoming value (must be legal).
 408       Tmp2 = LegalizeOp(Node->getOperand(1));
 409       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 410         Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
 411       break;
 412     case Promote:
 413       Tmp2 = PromoteOp(Node->getOperand(1));
 414       Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
 415       break;
 416     case Expand:
 417       SDOperand Lo, Hi;
 418       ExpandOp(Node->getOperand(1), Lo, Hi);
 419       unsigned Reg = cast<RegSDNode>(Node)->getReg();
 420       Lo = DAG.getCopyToReg(Tmp1, Lo, Reg);
 421       Hi = DAG.getCopyToReg(Tmp1, Hi, Reg+1);
 422       // Note that the copytoreg nodes are independent of each other.
 423       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
 424       assert(isTypeLegal(Result.getValueType()) &&
 425              "Cannot expand multiple times yet (i64 -> i16)");
 426       break;
 427     }
 428     break;
 429
 430   case ISD::RET:
 431     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 432     switch (Node->getNumOperands()) {
 433     case 2:  // ret val
 434       switch (getTypeAction(Node->getOperand(1).getValueType())) {
 435       case Legal:
 436         Tmp2 = LegalizeOp(Node->getOperand(1));
 437         if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 438           Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 439         break;
 440       case Expand: {
 441         SDOperand Lo, Hi;
 442         ExpandOp(Node->getOperand(1), Lo, Hi);
 443         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
 444         break;
 445       }
 446       case Promote:
 447         Tmp2 = PromoteOp(Node->getOperand(1));
 448         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 449         break;
 450       }
 451       break;
 452     case 1:  // ret void
 453       if (Tmp1 != Node->getOperand(0))
 454         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1);
 455       break;
 456     default: { // ret <values>
 457       std::vector<SDOperand> NewValues;
 458       NewValues.push_back(Tmp1);
 459       for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
 460         switch (getTypeAction(Node->getOperand(i).getValueType())) {
 461         case Legal:
 462           NewValues.push_back(LegalizeOp(Node->getOperand(i)));
 463           break;
 464         case Expand: {
 465           SDOperand Lo, Hi;
 466           ExpandOp(Node->getOperand(i), Lo, Hi);
 467           NewValues.push_back(Lo);
 468           NewValues.push_back(Hi);
 469           break;
 470         }
 471         case Promote:
 472           assert(0 && "Can't promote multiple return value yet!");
 473         }
 474       Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
 475       break;
 476     }
 477     }
 478     break;
 479   case ISD::STORE:
 480     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 481     Tmp2 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 482
 483     // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
 484     if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){
 485       if (CFP->getValueType(0) == MVT::f32) {
 486         union {
 487           unsigned I;
 488           float    F;
 489         } V;
 490         V.F = CFP->getValue();
 491         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 492                              DAG.getConstant(V.I, MVT::i32), Tmp2);
 493       } else {
 494         assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
 495         union {
 496           uint64_t I;
 497           double   F;
 498         } V;
 499         V.F = CFP->getValue();
 500         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 501                              DAG.getConstant(V.I, MVT::i64), Tmp2);
 502       }
 503       Op = Result;
 504       Node = Op.Val;
 505     }
 506
 507     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 508     case Legal: {
 509       SDOperand Val = LegalizeOp(Node->getOperand(1));
 510       if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) ||
 511           Tmp2 != Node->getOperand(2))
 512         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2);
 513       break;
 514     }
 515     case Promote:
 516       // Truncate the value and store the result.
 517       Tmp3 = PromoteOp(Node->getOperand(1));
 518       Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2,
 519                            Node->getOperand(1).getValueType());
 520       break;
 521
 522     case Expand:
 523       SDOperand Lo, Hi;
 524       ExpandOp(Node->getOperand(1), Lo, Hi);
 525
 526       if (!TLI.isLittleEndian())
 527         std::swap(Lo, Hi);
 528
 529       Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2);
 530
 531       unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8;
 532       Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
 533                          getIntPtrConstant(IncrementSize));
 534       assert(isTypeLegal(Tmp2.getValueType()) &&
 535              "Pointers must be legal!");
 536       Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2);
 537       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
 538       break;
 539     }
 540     break;
 541   case ISD::TRUNCSTORE:
 542     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 543     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 544
 545     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 546     case Legal:
 547       Tmp2 = LegalizeOp(Node->getOperand(1));
 548       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 549           Tmp3 != Node->getOperand(2))
 550         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3,
 551                              cast<MVTSDNode>(Node)->getExtraValueType());
 552       break;
 553     case Promote:
 554     case Expand:
 555       assert(0 && "Cannot handle illegal TRUNCSTORE yet!");
 556     }
 557     break;
 558   case ISD::SELECT:
 559     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 560     case Expand: assert(0 && "It's impossible to expand bools");
 561     case Legal:
 562       Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
 563       break;
 564     case Promote:
 565       Tmp1 = PromoteOp(Node->getOperand(0));  // Promote the condition.
 566       break;
 567     }
 568     Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
 569     Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
 570
 571     switch (TLI.getOperationAction(Node->getOpcode(), Tmp2.getValueType())) {
 572     default: assert(0 && "This action is not supported yet!");
 573     case TargetLowering::Legal:
 574       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 575           Tmp3 != Node->getOperand(2))
 576         Result = DAG.getNode(ISD::SELECT, Node->getValueType(0),
 577                              Tmp1, Tmp2, Tmp3);
 578       break;
 579     case TargetLowering::Promote: {
 580       MVT::ValueType NVT =
 581         TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType());
 582       unsigned ExtOp, TruncOp;
 583       if (MVT::isInteger(Tmp2.getValueType())) {
 584         ExtOp = ISD::ZERO_EXTEND;
 585         TruncOp  = ISD::TRUNCATE;
 586       } else {
 587         ExtOp = ISD::FP_EXTEND;
 588         TruncOp  = ISD::FP_ROUND;
 589       }
 590       // Promote each of the values to the new type.
 591       Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2);
 592       Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3);
 593       // Perform the larger operation, then round down.
 594       Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3);
 595       Result = DAG.getNode(TruncOp, Node->getValueType(0), Result);
 596       break;
 597     }
 598     }
 599     break;
 600   case ISD::SETCC:
 601     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 602     case Legal:
 603       Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 604       Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 605       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 606         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 607                               Node->getValueType(0), Tmp1, Tmp2);
 608       break;
 609     case Promote:
 610       Tmp1 = PromoteOp(Node->getOperand(0));   // LHS
 611       Tmp2 = PromoteOp(Node->getOperand(1));   // RHS
 612
 613       // If this is an FP compare, the operands have already been extended.
 614       if (MVT::isInteger(Node->getOperand(0).getValueType())) {
 615         MVT::ValueType VT = Node->getOperand(0).getValueType();
 616         MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 617
 618         // Otherwise, we have to insert explicit sign or zero extends.  Note
 619         // that we could insert sign extends for ALL conditions, but zero extend
 620         // is cheaper on many machines (an AND instead of two shifts), so prefer
 621         // it.
 622         switch (cast<SetCCSDNode>(Node)->getCondition()) {
 623         default: assert(0 && "Unknown integer comparison!");
 624         case ISD::SETEQ:
 625         case ISD::SETNE:
 626         case ISD::SETUGE:
 627         case ISD::SETUGT:
 628         case ISD::SETULE:
 629         case ISD::SETULT:
 630           // ALL of these operations will work if we either sign or zero extend
 631           // the operands (including the unsigned comparisons!).  Zero extend is
 632           // usually a simpler/cheaper operation, so prefer it.
 633           Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
 634           Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT);
 635           break;
 636         case ISD::SETGE:
 637         case ISD::SETGT:
 638         case ISD::SETLT:
 639         case ISD::SETLE:
 640           Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
 641           Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT);
 642           break;
 643         }
 644
 645       }
 646       Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 647                             Node->getValueType(0), Tmp1, Tmp2);
 648       break;
 649     case Expand:
 650       SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
 651       ExpandOp(Node->getOperand(0), LHSLo, LHSHi);
 652       ExpandOp(Node->getOperand(1), RHSLo, RHSHi);
 653       switch (cast<SetCCSDNode>(Node)->getCondition()) {
 654       case ISD::SETEQ:
 655       case ISD::SETNE:
 656         Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
 657         Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
 658         Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
 659         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 660                               Node->getValueType(0), Tmp1,
 661                               DAG.getConstant(0, Tmp1.getValueType()));
 662         break;
 663       default:
 664         // FIXME: This generated code sucks.
 665         ISD::CondCode LowCC;
 666         switch (cast<SetCCSDNode>(Node)->getCondition()) {
 667         default: assert(0 && "Unknown integer setcc!");
 668         case ISD::SETLT:
 669         case ISD::SETULT: LowCC = ISD::SETULT; break;
 670         case ISD::SETGT:
 671         case ISD::SETUGT: LowCC = ISD::SETUGT; break;
 672         case ISD::SETLE:
 673         case ISD::SETULE: LowCC = ISD::SETULE; break;
 674         case ISD::SETGE:
 675         case ISD::SETUGE: LowCC = ISD::SETUGE; break;
 676         }
 677
 678         // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
 679         // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
 680         // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
 681
 682         // NOTE: on targets without efficient SELECT of bools, we can always use
 683         // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
 684         Tmp1 = DAG.getSetCC(LowCC, Node->getValueType(0), LHSLo, RHSLo);
 685         Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 686                             Node->getValueType(0), LHSHi, RHSHi);
 687         Result = DAG.getSetCC(ISD::SETEQ, Node->getValueType(0), LHSHi, RHSHi);
 688         Result = DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
 689                              Result, Tmp1, Tmp2);
 690         break;
 691       }
 692     }
 693     break;
 694
 695   case ISD::MEMSET:
 696   case ISD::MEMCPY:
 697   case ISD::MEMMOVE: {
 698     Tmp1 = LegalizeOp(Node->getOperand(0));
 699     Tmp2 = LegalizeOp(Node->getOperand(1));
 700     Tmp3 = LegalizeOp(Node->getOperand(2));
 701     SDOperand Tmp4 = LegalizeOp(Node->getOperand(3));
 702     SDOperand Tmp5 = LegalizeOp(Node->getOperand(4));
 703
 704     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
 705     default: assert(0 && "This action not implemented for this operation!");
 706     case TargetLowering::Legal:
 707       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 708           Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) ||
 709           Tmp5 != Node->getOperand(4)) {
 710         std::vector<SDOperand> Ops;
 711         Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
 712         Ops.push_back(Tmp4); Ops.push_back(Tmp5);
 713         Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
 714       }
 715       break;
 716     case TargetLowering::Expand: {
 717       // Otherwise, the target does not support this operation.  Lower the
 718       // operation to an explicit libcall as appropriate.
 719       MVT::ValueType IntPtr = TLI.getPointerTy();
 720       const Type *IntPtrTy = TLI.getTargetData().getIntPtrType();
 721       std::vector<std::pair<SDOperand, const Type*> > Args;
 722
 723       const char *FnName = 0;
 724       if (Node->getOpcode() == ISD::MEMSET) {
 725         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
 726         // Extend the ubyte argument to be an int value for the call.
 727         Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
 728         Args.push_back(std::make_pair(Tmp3, Type::IntTy));
 729         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
 730
 731         FnName = "memset";
 732       } else if (Node->getOpcode() == ISD::MEMCPY ||
 733                  Node->getOpcode() == ISD::MEMMOVE) {
 734         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
 735         Args.push_back(std::make_pair(Tmp3, IntPtrTy));
 736         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
 737         FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
 738       } else {
 739         assert(0 && "Unknown op!");
 740       }
 741       std::pair<SDOperand,SDOperand> CallResult =
 742         TLI.LowerCallTo(Tmp1, Type::VoidTy,
 743                         DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
 744       Result = LegalizeOp(CallResult.second);
 745       break;
 746     }
 747     case TargetLowering::Custom:
 748       std::vector<SDOperand> Ops;
 749       Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
 750       Ops.push_back(Tmp4); Ops.push_back(Tmp5);
 751       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
 752       Result = TLI.LowerOperation(Result);
 753       Result = LegalizeOp(Result);
 754       break;
 755     }
 756     break;
 757   }
 758   case ISD::ADD_PARTS:
 759   case ISD::SUB_PARTS: {
 760     std::vector<SDOperand> Ops;
 761     bool Changed = false;
 762     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
 763       Ops.push_back(LegalizeOp(Node->getOperand(i)));
 764       Changed |= Ops.back() != Node->getOperand(i);
 765     }
 766     if (Changed)
 767       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops);
 768     break;
 769   }
 770   case ISD::ADD:
 771   case ISD::SUB:
 772   case ISD::MUL:
 773   case ISD::UDIV:
 774   case ISD::SDIV:
 775   case ISD::UREM:
 776   case ISD::SREM:
 777   case ISD::AND:
 778   case ISD::OR:
 779   case ISD::XOR:
 780   case ISD::SHL:
 781   case ISD::SRL:
 782   case ISD::SRA:
 783     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 784     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 785     if (Tmp1 != Node->getOperand(0) ||
 786         Tmp2 != Node->getOperand(1))
 787       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2);
 788     break;
 789   case ISD::ZERO_EXTEND:
 790   case ISD::SIGN_EXTEND:
 791   case ISD::TRUNCATE:
 792   case ISD::FP_EXTEND:
 793   case ISD::FP_ROUND:
 794   case ISD::FP_TO_SINT:
 795   case ISD::FP_TO_UINT:
 796   case ISD::SINT_TO_FP:
 797   case ISD::UINT_TO_FP:
 798     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 799     case Legal:
 800       Tmp1 = LegalizeOp(Node->getOperand(0));
 801       if (Tmp1 != Node->getOperand(0))
 802         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
 803       break;
 804     case Expand:
 805       assert(Node->getOpcode() != ISD::SINT_TO_FP &&
 806              Node->getOpcode() != ISD::UINT_TO_FP &&
 807              "Cannot lower Xint_to_fp to a call yet!");
 808
 809       // In the expand case, we must be dealing with a truncate, because
 810       // otherwise the result would be larger than the source.
 811       assert(Node->getOpcode() == ISD::TRUNCATE &&
 812              "Shouldn't need to expand other operators here!");
 813       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 814
 815       // Since the result is legal, we should just be able to truncate the low
 816       // part of the source.
 817       Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
 818       break;
 819
 820     case Promote:
 821       switch (Node->getOpcode()) {
 822       case ISD::ZERO_EXTEND:
 823         Result = PromoteOp(Node->getOperand(0));
 824         // NOTE: Any extend would work here...
 825         Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
 826         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Op.getValueType(),
 827                              Result, Node->getOperand(0).getValueType());
 828         break;
 829       case ISD::SIGN_EXTEND:
 830         Result = PromoteOp(Node->getOperand(0));
 831         // NOTE: Any extend would work here...
 832         Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
 833         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
 834                              Result, Node->getOperand(0).getValueType());
 835         break;
 836       case ISD::TRUNCATE:
 837         Result = PromoteOp(Node->getOperand(0));
 838         Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
 839         break;
 840       case ISD::FP_EXTEND:
 841         Result = PromoteOp(Node->getOperand(0));
 842         if (Result.getValueType() != Op.getValueType())
 843           // Dynamically dead while we have only 2 FP types.
 844           Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
 845         break;
 846       case ISD::FP_ROUND:
 847       case ISD::FP_TO_SINT:
 848       case ISD::FP_TO_UINT:
 849         Result = PromoteOp(Node->getOperand(0));
 850         Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
 851         break;
 852       case ISD::SINT_TO_FP:
 853         Result = PromoteOp(Node->getOperand(0));
 854         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
 855                              Result, Node->getOperand(0).getValueType());
 856         Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result);
 857         break;
 858       case ISD::UINT_TO_FP:
 859         Result = PromoteOp(Node->getOperand(0));
 860         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(),
 861                              Result, Node->getOperand(0).getValueType());
 862         Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result);
 863         break;
 864       }
 865     }
 866     break;
 867   case ISD::FP_ROUND_INREG:
 868   case ISD::SIGN_EXTEND_INREG:
 869   case ISD::ZERO_EXTEND_INREG: {
 870     Tmp1 = LegalizeOp(Node->getOperand(0));
 871     MVT::ValueType ExtraVT = cast<MVTSDNode>(Node)->getExtraValueType();
 872
 873     // If this operation is not supported, convert it to a shl/shr or load/store
 874     // pair.
 875     switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
 876     default: assert(0 && "This action not supported for this op yet!");
 877     case TargetLowering::Legal:
 878       if (Tmp1 != Node->getOperand(0))
 879         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
 880                              ExtraVT);
 881       break;
 882     case TargetLowering::Expand:
 883       // If this is an integer extend and shifts are supported, do that.
 884       if (Node->getOpcode() == ISD::ZERO_EXTEND_INREG) {
 885         // NOTE: we could fall back on load/store here too for targets without
 886         // AND.  However, it is doubtful that any exist.
 887         // AND out the appropriate bits.
 888         SDOperand Mask =
 889           DAG.getConstant((1ULL << MVT::getSizeInBits(ExtraVT))-1,
 890                           Node->getValueType(0));
 891         Result = DAG.getNode(ISD::AND, Node->getValueType(0),
 892                              Node->getOperand(0), Mask);
 893       } else if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
 894         // NOTE: we could fall back on load/store here too for targets without
 895         // SAR.  However, it is doubtful that any exist.
 896         unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
 897                             MVT::getSizeInBits(ExtraVT);
 898         SDOperand ShiftCst = DAG.getConstant(BitsDiff, MVT::i8);
 899         Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
 900                              Node->getOperand(0), ShiftCst);
 901         Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
 902                              Result, ShiftCst);
 903       } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
 904         // The only way we can lower this is to turn it into a STORETRUNC,
 905         // EXTLOAD pair, targetting a temporary location (a stack slot).
 906
 907         // NOTE: there is a choice here between constantly creating new stack
 908         // slots and always reusing the same one.  We currently always create
 909         // new ones, as reuse may inhibit scheduling.
 910         const Type *Ty = MVT::getTypeForValueType(ExtraVT);
 911         unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty);
 912         unsigned Align  = TLI.getTargetData().getTypeAlignment(Ty);
 913         MachineFunction &MF = DAG.getMachineFunction();
 914         int SSFI =
 915           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
 916         SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
 917         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
 918                              Node->getOperand(0), StackSlot, ExtraVT);
 919         Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0),
 920                              Result, StackSlot, ExtraVT);
 921       } else {
 922         assert(0 && "Unknown op");
 923       }
 924       Result = LegalizeOp(Result);
 925       break;
 926     }
 927     break;
 928   }
 929   }
 930
 931   if (!Op.Val->hasOneUse())
 932     AddLegalizedOperand(Op, Result);
 933
 934   return Result;
 935 }
 936
 937 /// PromoteOp - Given an operation that produces a value in an invalid type,
 938 /// promote it to compute the value into a larger type.  The produced value will
 939 /// have the correct bits for the low portion of the register, but no guarantee
 940 /// is made about the top bits: it may be zero, sign-extended, or garbage.
 941 SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
 942   MVT::ValueType VT = Op.getValueType();
 943   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 944   assert(getTypeAction(VT) == Promote &&
 945          "Caller should expand or legalize operands that are not promotable!");
 946   assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
 947          "Cannot promote to smaller type!");
 948
 949   std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
 950   if (I != PromotedNodes.end()) return I->second;
 951
 952   SDOperand Tmp1, Tmp2, Tmp3;
 953
 954   SDOperand Result;
 955   SDNode *Node = Op.Val;
 956
 957   // Promotion needs an optimization step to clean up after it, and is not
 958   // careful to avoid operations the target does not support.  Make sure that
 959   // all generated operations are legalized in the next iteration.
 960   NeedsAnotherIteration = true;
 961
 962   switch (Node->getOpcode()) {
 963   default:
 964     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 965     assert(0 && "Do not know how to promote this operator!");
 966     abort();
 967   case ISD::Constant:
 968     Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
 969     assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
 970     break;
 971   case ISD::ConstantFP:
 972     Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
 973     assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
 974     break;
 975   case ISD::CopyFromReg:
 976     Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), NVT,
 977                                 Node->getOperand(0));
 978     // Remember that we legalized the chain.
 979     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
 980     break;
 981
 982   case ISD::SETCC:
 983     assert(getTypeAction(TLI.getSetCCResultTy()) == Legal &&
 984            "SetCC type is not legal??");
 985     Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 986                           TLI.getSetCCResultTy(), Node->getOperand(0),
 987                           Node->getOperand(1));
 988     Result = LegalizeOp(Result);
 989     break;
 990
 991   case ISD::TRUNCATE:
 992     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 993     case Legal:
 994       Result = LegalizeOp(Node->getOperand(0));
 995       assert(Result.getValueType() >= NVT &&
 996              "This truncation doesn't make sense!");
 997       if (Result.getValueType() > NVT)    // Truncate to NVT instead of VT
 998         Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
 999       break;
1000     case Expand:
1001       assert(0 && "Cannot handle expand yet");
1002     case Promote:
1003       assert(0 && "Cannot handle promote-promote yet");
1004     }
1005     break;
1006   case ISD::SIGN_EXTEND:
1007   case ISD::ZERO_EXTEND:
1008     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1009     case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
1010     case Legal:
1011       // Input is legal?  Just do extend all the way to the larger type.
1012       Result = LegalizeOp(Node->getOperand(0));
1013       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1014       break;
1015     case Promote:
1016       // Promote the reg if it's smaller.
1017       Result = PromoteOp(Node->getOperand(0));
1018       // The high bits are not guaranteed to be anything.  Insert an extend.
1019       if (Node->getOpcode() == ISD::SIGN_EXTEND)
1020         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result, VT);
1021       else
1022         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Result, VT);
1023       break;
1024     }
1025     break;
1026
1027   case ISD::FP_EXTEND:
1028     assert(0 && "Case not implemented.  Dynamically dead with 2 FP types!");
1029   case ISD::FP_ROUND:
1030     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1031     case Expand: assert(0 && "BUG: Cannot expand FP regs!");
1032     case Promote:  assert(0 && "Unreachable with 2 FP types!");
1033     case Legal:
1034       // Input is legal?  Do an FP_ROUND_INREG.
1035       Result = LegalizeOp(Node->getOperand(0));
1036       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1037       break;
1038     }
1039     break;
1040
1041   case ISD::SINT_TO_FP:
1042   case ISD::UINT_TO_FP:
1043     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1044     case Legal:
1045       Result = LegalizeOp(Node->getOperand(0));
1046       break;
1047
1048     case Promote:
1049       Result = PromoteOp(Node->getOperand(0));
1050       if (Node->getOpcode() == ISD::SINT_TO_FP)
1051         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1052                              Result, Node->getOperand(0).getValueType());
1053       else
1054         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(),
1055                              Result, Node->getOperand(0).getValueType());
1056       break;
1057     case Expand:
1058       assert(0 && "Unimplemented");
1059     }
1060     // No extra round required here.
1061     Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1062     break;
1063
1064   case ISD::FP_TO_SINT:
1065   case ISD::FP_TO_UINT:
1066     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1067     case Legal:
1068       Tmp1 = LegalizeOp(Node->getOperand(0));
1069       break;
1070     case Promote:
1071       // The input result is prerounded, so we don't have to do anything
1072       // special.
1073       Tmp1 = PromoteOp(Node->getOperand(0));
1074       break;
1075     case Expand:
1076       assert(0 && "not implemented");
1077     }
1078     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1079     break;
1080
1081   case ISD::AND:
1082   case ISD::OR:
1083   case ISD::XOR:
1084   case ISD::ADD:
1085   case ISD::SUB:
1086   case ISD::MUL:
1087     // The input may have strange things in the top bits of the registers, but
1088     // these operations don't care.  They may have wierd bits going out, but
1089     // that too is okay if they are integer operations.
1090     Tmp1 = PromoteOp(Node->getOperand(0));
1091     Tmp2 = PromoteOp(Node->getOperand(1));
1092     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
1093     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1094
1095     // However, if this is a floating point operation, they will give excess
1096     // precision that we may not be able to tolerate.  If we DO allow excess
1097     // precision, just leave it, otherwise excise it.
1098     // FIXME: Why would we need to round FP ops more than integer ones?
1099     //     Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
1100     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
1101       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1102     break;
1103
1104   case ISD::SDIV:
1105   case ISD::SREM:
1106     // These operators require that their input be sign extended.
1107     Tmp1 = PromoteOp(Node->getOperand(0));
1108     Tmp2 = PromoteOp(Node->getOperand(1));
1109     if (MVT::isInteger(NVT)) {
1110       Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
1111       Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT);
1112     }
1113     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1114
1115     // Perform FP_ROUND: this is probably overly pessimistic.
1116     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
1117       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1118     break;
1119
1120   case ISD::UDIV:
1121   case ISD::UREM:
1122     // These operators require that their input be zero extended.
1123     Tmp1 = PromoteOp(Node->getOperand(0));
1124     Tmp2 = PromoteOp(Node->getOperand(1));
1125     assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
1126     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
1127     Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT);
1128     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1129     break;
1130
1131   case ISD::SHL:
1132     Tmp1 = PromoteOp(Node->getOperand(0));
1133     Tmp2 = LegalizeOp(Node->getOperand(1));
1134     Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2);
1135     break;
1136   case ISD::SRA:
1137     // The input value must be properly sign extended.
1138     Tmp1 = PromoteOp(Node->getOperand(0));
1139     Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
1140     Tmp2 = LegalizeOp(Node->getOperand(1));
1141     Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2);
1142     break;
1143   case ISD::SRL:
1144     // The input value must be properly zero extended.
1145     Tmp1 = PromoteOp(Node->getOperand(0));
1146     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
1147     Tmp2 = LegalizeOp(Node->getOperand(1));
1148     Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2);
1149     break;
1150   case ISD::LOAD:
1151     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
1152     Tmp2 = LegalizeOp(Node->getOperand(1));   // Legalize the pointer.
1153     Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, VT);
1154
1155     // Remember that we legalized the chain.
1156     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1157     break;
1158   case ISD::SELECT:
1159     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1160     case Expand: assert(0 && "It's impossible to expand bools");
1161     case Legal:
1162       Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition.
1163       break;
1164     case Promote:
1165       Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition.
1166       break;
1167     }
1168     Tmp2 = PromoteOp(Node->getOperand(1));   // Legalize the op0
1169     Tmp3 = PromoteOp(Node->getOperand(2));   // Legalize the op1
1170     Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3);
1171     break;
1172   case ISD::CALL: {
1173     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1174     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
1175
1176     std::vector<SDOperand> Ops;
1177     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i)
1178       Ops.push_back(LegalizeOp(Node->getOperand(i)));
1179
1180     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
1181            "Can only promote single result calls");
1182     std::vector<MVT::ValueType> RetTyVTs;
1183     RetTyVTs.reserve(2);
1184     RetTyVTs.push_back(NVT);
1185     RetTyVTs.push_back(MVT::Other);
1186     SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops);
1187     Result = SDOperand(NC, 0);
1188
1189     // Insert the new chain mapping.
1190     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1191     break;
1192   }
1193   }
1194
1195   assert(Result.Val && "Didn't set a result!");
1196   AddPromotedOperand(Op, Result);
1197   return Result;
1198 }
1199
1200 /// ExpandAddSub - Find a clever way to expand this add operation into
1201 /// subcomponents.
1202 void SelectionDAGLegalize::ExpandAddSub(bool isAdd, SDOperand LHS,SDOperand RHS,
1203                                         SDOperand &Lo, SDOperand &Hi) {
1204   // Expand the subcomponents.
1205   SDOperand LHSL, LHSH, RHSL, RHSH;
1206   ExpandOp(LHS, LHSL, LHSH);
1207   ExpandOp(RHS, RHSL, RHSH);
1208
1209   // Convert this add to the appropriate ADDC pair.  The low part has no carry
1210   // in.
1211   unsigned Opc = isAdd ? ISD::ADD_PARTS : ISD::SUB_PARTS;
1212   std::vector<SDOperand> Ops;
1213   Ops.push_back(LHSL);
1214   Ops.push_back(LHSH);
1215   Ops.push_back(RHSL);
1216   Ops.push_back(RHSH);
1217   Lo = DAG.getNode(Opc, LHSL.getValueType(), Ops);
1218   Hi = Lo.getValue(1);
1219 }
1220
1221 /// ExpandShift - Try to find a clever way to expand this shift operation out to
1222 /// smaller elements.  If we can't find a way that is more efficient than a
1223 /// libcall on this target, return false.  Otherwise, return true with the
1224 /// low-parts expanded into Lo and Hi.
1225 bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
1226                                        SDOperand &Lo, SDOperand &Hi) {
1227   assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
1228          "This is not a shift!");
1229   MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
1230
1231   // If we have an efficient select operation (or if the selects will all fold
1232   // away), lower to some complex code, otherwise just emit the libcall.
1233   if (TLI.getOperationAction(ISD::SELECT, NVT) != TargetLowering::Legal &&
1234       !isa<ConstantSDNode>(Amt))
1235     return false;
1236
1237   SDOperand InL, InH;
1238   ExpandOp(Op, InL, InH);
1239   SDOperand ShAmt = LegalizeOp(Amt);
1240   SDOperand OShAmt = ShAmt;  // Unmasked shift amount.
1241   MVT::ValueType ShTy = ShAmt.getValueType();
1242
1243   unsigned NVTBits = MVT::getSizeInBits(NVT);
1244   SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy,           // NAmt = 32-ShAmt
1245                                DAG.getConstant(NVTBits, ShTy), ShAmt);
1246
1247   if (TLI.getShiftAmountFlavor() != TargetLowering::Mask) {
1248     ShAmt = DAG.getNode(ISD::AND, ShTy, ShAmt,             // ShAmt &= 31
1249                         DAG.getConstant(NVTBits-1, ShTy));
1250     NAmt  = DAG.getNode(ISD::AND, ShTy, NAmt,              // NAmt &= 31
1251                         DAG.getConstant(NVTBits-1, ShTy));
1252   }
1253
1254   if (Opc == ISD::SHL) {
1255     SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << Amt) | (Lo >> NAmt)
1256                                DAG.getNode(ISD::SHL, NVT, InH, ShAmt),
1257                                DAG.getNode(ISD::SRL, NVT, InL, NAmt));
1258     SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt
1259
1260     SDOperand Cond = DAG.getSetCC(ISD::SETGE, TLI.getSetCCResultTy(), OShAmt,
1261                                   DAG.getConstant(NVTBits, ShTy));
1262     Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
1263     Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2);
1264   } else {
1265     SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << NAmt) | (Lo >> Amt)
1266                                DAG.getNode(ISD::SHL, NVT, InH, NAmt),
1267                                DAG.getNode(ISD::SRL, NVT, InL, ShAmt));
1268     bool isSign = Opc == ISD::SRA;
1269     SDOperand T2 = DAG.getNode(Opc, NVT, InH, ShAmt);
1270
1271     SDOperand HiPart;
1272     if (isSign)
1273       HiPart = DAG.getNode(Opc, NVT, InH, DAG.getConstant(NVTBits-1, ShTy));
1274     else
1275       HiPart = DAG.getConstant(0, NVT);
1276     SDOperand Cond = DAG.getSetCC(ISD::SETGE, TLI.getSetCCResultTy(), OShAmt,
1277                                   DAG.getConstant(NVTBits, ShTy));
1278     Lo = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
1279     Hi = DAG.getNode(ISD::SELECT, NVT, Cond, HiPart,T2);
1280   }
1281   return true;
1282 }
1283
1284
1285
1286 /// ExpandOp - Expand the specified SDOperand into its two component pieces
1287 /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
1288 /// LegalizeNodes map is filled in for any results that are not expanded, the
1289 /// ExpandedNodes map is filled in for any results that are expanded, and the
1290 /// Lo/Hi values are returned.
1291 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
1292   MVT::ValueType VT = Op.getValueType();
1293   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1294   SDNode *Node = Op.Val;
1295   assert(getTypeAction(VT) == Expand && "Not an expanded type!");
1296   assert(MVT::isInteger(VT) && "Cannot expand FP values!");
1297   assert(MVT::isInteger(NVT) && NVT < VT &&
1298          "Cannot expand to FP value or to larger int value!");
1299
1300   // If there is more than one use of this, see if we already expanded it.
1301   // There is no use remembering values that only have a single use, as the map
1302   // entries will never be reused.
1303   if (!Node->hasOneUse()) {
1304     std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
1305       = ExpandedNodes.find(Op);
1306     if (I != ExpandedNodes.end()) {
1307       Lo = I->second.first;
1308       Hi = I->second.second;
1309       return;
1310     }
1311   }
1312
1313   // Expanding to multiple registers needs to perform an optimization step, and
1314   // is not careful to avoid operations the target does not support.  Make sure
1315   // that all generated operations are legalized in the next iteration.
1316   NeedsAnotherIteration = true;
1317   const char *LibCallName = 0;
1318
1319   switch (Node->getOpcode()) {
1320   default:
1321     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
1322     assert(0 && "Do not know how to expand this operator!");
1323     abort();
1324   case ISD::Constant: {
1325     uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
1326     Lo = DAG.getConstant(Cst, NVT);
1327     Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
1328     break;
1329   }
1330
1331   case ISD::CopyFromReg: {
1332     unsigned Reg = cast<RegSDNode>(Node)->getReg();
1333     // Aggregate register values are always in consequtive pairs.
1334     Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0));
1335     Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1));
1336
1337     // Remember that we legalized the chain.
1338     AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
1339
1340     assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
1341     break;
1342   }
1343
1344   case ISD::LOAD: {
1345     SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
1346     SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1347     Lo = DAG.getLoad(NVT, Ch, Ptr);
1348
1349     // Increment the pointer to the other half.
1350     unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
1351     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1352                       getIntPtrConstant(IncrementSize));
1353     Hi = DAG.getLoad(NVT, Ch, Ptr);
1354
1355     // Build a factor node to remember that this load is independent of the
1356     // other one.
1357     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
1358                                Hi.getValue(1));
1359
1360     // Remember that we legalized the chain.
1361     AddLegalizedOperand(Op.getValue(1), TF);
1362     if (!TLI.isLittleEndian())
1363       std::swap(Lo, Hi);
1364     break;
1365   }
1366   case ISD::CALL: {
1367     SDOperand Chain  = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1368     SDOperand Callee = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
1369
1370     bool Changed = false;
1371     std::vector<SDOperand> Ops;
1372     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
1373       Ops.push_back(LegalizeOp(Node->getOperand(i)));
1374       Changed |= Ops.back() != Node->getOperand(i);
1375     }
1376
1377     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
1378            "Can only expand a call once so far, not i64 -> i16!");
1379
1380     std::vector<MVT::ValueType> RetTyVTs;
1381     RetTyVTs.reserve(3);
1382     RetTyVTs.push_back(NVT);
1383     RetTyVTs.push_back(NVT);
1384     RetTyVTs.push_back(MVT::Other);
1385     SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee, Ops);
1386     Lo = SDOperand(NC, 0);
1387     Hi = SDOperand(NC, 1);
1388
1389     // Insert the new chain mapping.
1390     AddLegalizedOperand(Op.getValue(1), Hi.getValue(2));
1391     break;
1392   }
1393   case ISD::AND:
1394   case ISD::OR:
1395   case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
1396     SDOperand LL, LH, RL, RH;
1397     ExpandOp(Node->getOperand(0), LL, LH);
1398     ExpandOp(Node->getOperand(1), RL, RH);
1399     Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
1400     Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
1401     break;
1402   }
1403   case ISD::SELECT: {
1404     SDOperand C, LL, LH, RL, RH;
1405
1406     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1407     case Expand: assert(0 && "It's impossible to expand bools");
1408     case Legal:
1409       C = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
1410       break;
1411     case Promote:
1412       C = PromoteOp(Node->getOperand(0));  // Promote the condition.
1413       break;
1414     }
1415     ExpandOp(Node->getOperand(1), LL, LH);
1416     ExpandOp(Node->getOperand(2), RL, RH);
1417     Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL);
1418     Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH);
1419     break;
1420   }
1421   case ISD::SIGN_EXTEND: {
1422     // The low part is just a sign extension of the input (which degenerates to
1423     // a copy).
1424     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
1425
1426     // The high part is obtained by SRA'ing all but one of the bits of the lo
1427     // part.
1428     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
1429     Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, MVT::i8));
1430     break;
1431   }
1432   case ISD::ZERO_EXTEND:
1433     // The low part is just a zero extension of the input (which degenerates to
1434     // a copy).
1435     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
1436
1437     // The high part is just a zero.
1438     Hi = DAG.getConstant(0, NVT);
1439     break;
1440
1441     // These operators cannot be expanded directly, emit them as calls to
1442     // library functions.
1443   case ISD::FP_TO_SINT:
1444     if (Node->getOperand(0).getValueType() == MVT::f32)
1445       LibCallName = "__fixsfdi";
1446     else
1447       LibCallName = "__fixdfdi";
1448     break;
1449   case ISD::FP_TO_UINT:
1450     if (Node->getOperand(0).getValueType() == MVT::f32)
1451       LibCallName = "__fixunssfdi";
1452     else
1453       LibCallName = "__fixunsdfdi";
1454     break;
1455
1456   case ISD::SHL:
1457     // If we can emit an efficient shift operation, do so now.
1458     if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1),
1459                     Lo, Hi))
1460       break;
1461     // Otherwise, emit a libcall.
1462     LibCallName = "__ashldi3";
1463     break;
1464
1465   case ISD::SRA:
1466     // If we can emit an efficient shift operation, do so now.
1467     if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1),
1468                     Lo, Hi))
1469       break;
1470     // Otherwise, emit a libcall.
1471     LibCallName = "__ashrdi3";
1472     break;
1473   case ISD::SRL:
1474     // If we can emit an efficient shift operation, do so now.
1475     if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1),
1476                     Lo, Hi))
1477       break;
1478     // Otherwise, emit a libcall.
1479     LibCallName = "__lshrdi3";
1480     break;
1481
1482   case ISD::ADD:
1483     ExpandAddSub(true, Node->getOperand(0), Node->getOperand(1), Lo, Hi);
1484     break;
1485   case ISD::SUB:
1486     ExpandAddSub(false, Node->getOperand(0), Node->getOperand(1), Lo, Hi);
1487     break;
1488   case ISD::MUL:  LibCallName = "__muldi3"; break;
1489   case ISD::SDIV: LibCallName = "__divdi3"; break;
1490   case ISD::UDIV: LibCallName = "__udivdi3"; break;
1491   case ISD::SREM: LibCallName = "__moddi3"; break;
1492   case ISD::UREM: LibCallName = "__umoddi3"; break;
1493   }
1494
1495   // Int2FP -> __floatdisf/__floatdidf
1496
1497   // If this is to be expanded into a libcall... do so now.
1498   if (LibCallName) {
1499     TargetLowering::ArgListTy Args;
1500     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1501       Args.push_back(std::make_pair(Node->getOperand(i),
1502                  MVT::getTypeForValueType(Node->getOperand(i).getValueType())));
1503     SDOperand Callee = DAG.getExternalSymbol(LibCallName, TLI.getPointerTy());
1504
1505     // We don't care about token chains for libcalls.  We just use the entry
1506     // node as our input and ignore the output chain.  This allows us to place
1507     // calls wherever we need them to satisfy data dependences.
1508     SDOperand Result = TLI.LowerCallTo(DAG.getEntryNode(),
1509                            MVT::getTypeForValueType(Op.getValueType()), Callee,
1510                                        Args, DAG).first;
1511     ExpandOp(Result, Lo, Hi);
1512   }
1513
1514   // Remember in a map if the values will be reused later.
1515   if (!Node->hasOneUse()) {
1516     bool isNew = ExpandedNodes.insert(std::make_pair(Op,
1517                                             std::make_pair(Lo, Hi))).second;
1518     assert(isNew && "Value already expanded?!?");
1519   }
1520 }
1521
1522
1523 // SelectionDAG::Legalize - This is the entry point for the file.
1524 //
1525 void SelectionDAG::Legalize(TargetLowering &TLI) {
1526   /// run - This is the main entry point to this class.
1527   ///
1528   SelectionDAGLegalize(TLI, *this).Run();
1529 }
1530