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(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   SDOperand ExpandLibCall(const char *Name, SDNode *Node,
 123                           SDOperand &Hi);
 124   SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy,
 125                           SDOperand Source);
 126   bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt,
 127                    SDOperand &Lo, SDOperand &Hi);
 128   void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt,
 129                         SDOperand &Lo, SDOperand &Hi);
 130   void ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS,
 131                      SDOperand &Lo, SDOperand &Hi);
 132
 133   SDOperand getIntPtrConstant(uint64_t Val) {
 134     return DAG.getConstant(Val, TLI.getPointerTy());
 135   }
 136 };
 137 }
 138
 139
 140 SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag)
 141   : TLI(dag.getTargetLoweringInfo()), DAG(dag),
 142     ValueTypeActions(TLI.getValueTypeActions()) {
 143   assert(MVT::LAST_VALUETYPE <= 16 &&
 144          "Too many value types for ValueTypeActions to hold!");
 145 }
 146
 147 void SelectionDAGLegalize::LegalizeDAG() {
 148   SDOperand OldRoot = DAG.getRoot();
 149   SDOperand NewRoot = LegalizeOp(OldRoot);
 150   DAG.setRoot(NewRoot);
 151
 152   ExpandedNodes.clear();
 153   LegalizedNodes.clear();
 154   PromotedNodes.clear();
 155
 156   // Remove dead nodes now.
 157   DAG.RemoveDeadNodes(OldRoot.Val);
 158 }
 159
 160 SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 161   assert(getTypeAction(Op.getValueType()) == Legal &&
 162          "Caller should expand or promote operands that are not legal!");
 163
 164   // If this operation defines any values that cannot be represented in a
 165   // register on this target, make sure to expand or promote them.
 166   if (Op.Val->getNumValues() > 1) {
 167     for (unsigned i = 0, e = Op.Val->getNumValues(); i != e; ++i)
 168       switch (getTypeAction(Op.Val->getValueType(i))) {
 169       case Legal: break;  // Nothing to do.
 170       case Expand: {
 171         SDOperand T1, T2;
 172         ExpandOp(Op.getValue(i), T1, T2);
 173         assert(LegalizedNodes.count(Op) &&
 174                "Expansion didn't add legal operands!");
 175         return LegalizedNodes[Op];
 176       }
 177       case Promote:
 178         PromoteOp(Op.getValue(i));
 179         assert(LegalizedNodes.count(Op) &&
 180                "Expansion didn't add legal operands!");
 181         return LegalizedNodes[Op];
 182       }
 183   }
 184
 185   std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
 186   if (I != LegalizedNodes.end()) return I->second;
 187
 188   SDOperand Tmp1, Tmp2, Tmp3;
 189
 190   SDOperand Result = Op;
 191   SDNode *Node = Op.Val;
 192
 193   switch (Node->getOpcode()) {
 194   default:
 195     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 196     assert(0 && "Do not know how to legalize this operator!");
 197     abort();
 198   case ISD::EntryToken:
 199   case ISD::FrameIndex:
 200   case ISD::GlobalAddress:
 201   case ISD::ExternalSymbol:
 202   case ISD::ConstantPool:           // Nothing to do.
 203     assert(getTypeAction(Node->getValueType(0)) == Legal &&
 204            "This must be legal!");
 205     break;
 206   case ISD::CopyFromReg:
 207     Tmp1 = LegalizeOp(Node->getOperand(0));
 208     if (Tmp1 != Node->getOperand(0))
 209       Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(),
 210                                   Node->getValueType(0), Tmp1);
 211     else
 212       Result = Op.getValue(0);
 213
 214     // Since CopyFromReg produces two values, make sure to remember that we
 215     // legalized both of them.
 216     AddLegalizedOperand(Op.getValue(0), Result);
 217     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
 218     return Result.getValue(Op.ResNo);
 219   case ISD::ImplicitDef:
 220     Tmp1 = LegalizeOp(Node->getOperand(0));
 221     if (Tmp1 != Node->getOperand(0))
 222       Result = DAG.getImplicitDef(Tmp1, cast<RegSDNode>(Node)->getReg());
 223     break;
 224   case ISD::UNDEF: {
 225     MVT::ValueType VT = Op.getValueType();
 226     switch (TLI.getOperationAction(ISD::UNDEF, VT)) {
 227     default: assert(0 && "This action is not supported yet!");
 228     case TargetLowering::Expand:
 229     case TargetLowering::Promote:
 230       if (MVT::isInteger(VT))
 231         Result = DAG.getConstant(0, VT);
 232       else if (MVT::isFloatingPoint(VT))
 233         Result = DAG.getConstantFP(0, VT);
 234       else
 235         assert(0 && "Unknown value type!");
 236       break;
 237     case TargetLowering::Legal:
 238       break;
 239     }
 240     break;
 241   }
 242   case ISD::Constant:
 243     // We know we don't need to expand constants here, constants only have one
 244     // value and we check that it is fine above.
 245
 246     // FIXME: Maybe we should handle things like targets that don't support full
 247     // 32-bit immediates?
 248     break;
 249   case ISD::ConstantFP: {
 250     // Spill FP immediates to the constant pool if the target cannot directly
 251     // codegen them.  Targets often have some immediate values that can be
 252     // efficiently generated into an FP register without a load.  We explicitly
 253     // leave these constants as ConstantFP nodes for the target to deal with.
 254
 255     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
 256
 257     // Check to see if this FP immediate is already legal.
 258     bool isLegal = false;
 259     for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
 260            E = TLI.legal_fpimm_end(); I != E; ++I)
 261       if (CFP->isExactlyValue(*I)) {
 262         isLegal = true;
 263         break;
 264       }
 265
 266     if (!isLegal) {
 267       // Otherwise we need to spill the constant to memory.
 268       MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
 269
 270       bool Extend = false;
 271
 272       // If a FP immediate is precise when represented as a float, we put it
 273       // into the constant pool as a float, even if it's is statically typed
 274       // as a double.
 275       MVT::ValueType VT = CFP->getValueType(0);
 276       bool isDouble = VT == MVT::f64;
 277       ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
 278                                              Type::FloatTy, CFP->getValue());
 279       if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) &&
 280           // Only do this if the target has a native EXTLOAD instruction from
 281           // f32.
 282           TLI.getOperationAction(ISD::EXTLOAD,
 283                                  MVT::f32) == TargetLowering::Legal) {
 284         LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
 285         VT = MVT::f32;
 286         Extend = true;
 287       }
 288
 289       SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC),
 290                                             TLI.getPointerTy());
 291       if (Extend) {
 292         Result = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), CPIdx,
 293                              MVT::f32);
 294       } else {
 295         Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx);
 296       }
 297     }
 298     break;
 299   }
 300   case ISD::TokenFactor: {
 301     std::vector<SDOperand> Ops;
 302     bool Changed = false;
 303     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
 304       SDOperand Op = Node->getOperand(i);
 305       // Fold single-use TokenFactor nodes into this token factor as we go.
 306       if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) {
 307         Changed = true;
 308         for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j)
 309           Ops.push_back(LegalizeOp(Op.getOperand(j)));
 310       } else {
 311         Ops.push_back(LegalizeOp(Op));  // Legalize the operands
 312         Changed |= Ops[i] != Op;
 313       }
 314     }
 315     if (Changed)
 316       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops);
 317     break;
 318   }
 319
 320   case ISD::ADJCALLSTACKDOWN:
 321   case ISD::ADJCALLSTACKUP:
 322     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 323     // There is no need to legalize the size argument (Operand #1)
 324     if (Tmp1 != Node->getOperand(0))
 325       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1,
 326                            Node->getOperand(1));
 327     break;
 328   case ISD::DYNAMIC_STACKALLOC:
 329     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 330     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
 331     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
 332     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 333         Tmp3 != Node->getOperand(2))
 334       Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0),
 335                            Tmp1, Tmp2, Tmp3);
 336     else
 337       Result = Op.getValue(0);
 338
 339     // Since this op produces two values, make sure to remember that we
 340     // legalized both of them.
 341     AddLegalizedOperand(SDOperand(Node, 0), Result);
 342     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 343     return Result.getValue(Op.ResNo);
 344
 345   case ISD::CALL: {
 346     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 347     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
 348
 349     bool Changed = false;
 350     std::vector<SDOperand> Ops;
 351     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
 352       Ops.push_back(LegalizeOp(Node->getOperand(i)));
 353       Changed |= Ops.back() != Node->getOperand(i);
 354     }
 355
 356     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Changed) {
 357       std::vector<MVT::ValueType> RetTyVTs;
 358       RetTyVTs.reserve(Node->getNumValues());
 359       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 360         RetTyVTs.push_back(Node->getValueType(i));
 361       Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops), 0);
 362     } else {
 363       Result = Result.getValue(0);
 364     }
 365     // Since calls produce multiple values, make sure to remember that we
 366     // legalized all of them.
 367     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 368       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
 369     return Result.getValue(Op.ResNo);
 370   }
 371   case ISD::BR:
 372     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 373     if (Tmp1 != Node->getOperand(0))
 374       Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1));
 375     break;
 376
 377   case ISD::BRCOND:
 378     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 379
 380     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 381     case Expand: assert(0 && "It's impossible to expand bools");
 382     case Legal:
 383       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
 384       break;
 385     case Promote:
 386       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
 387       break;
 388     }
 389     // Basic block destination (Op#2) is always legal.
 390     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 391       Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
 392                            Node->getOperand(2));
 393     break;
 394
 395   case ISD::LOAD:
 396     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 397     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 398     if (Tmp1 != Node->getOperand(0) ||
 399         Tmp2 != Node->getOperand(1))
 400       Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2);
 401     else
 402       Result = SDOperand(Node, 0);
 403
 404     // Since loads produce two values, make sure to remember that we legalized
 405     // both of them.
 406     AddLegalizedOperand(SDOperand(Node, 0), Result);
 407     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 408     return Result.getValue(Op.ResNo);
 409
 410   case ISD::EXTLOAD:
 411   case ISD::SEXTLOAD:
 412   case ISD::ZEXTLOAD:
 413     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 414     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 415     if (Tmp1 != Node->getOperand(0) ||
 416         Tmp2 != Node->getOperand(1))
 417       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, Tmp2,
 418                            cast<MVTSDNode>(Node)->getExtraValueType());
 419     else
 420       Result = SDOperand(Node, 0);
 421
 422     // Since loads produce two values, make sure to remember that we legalized
 423     // both of them.
 424     AddLegalizedOperand(SDOperand(Node, 0), Result);
 425     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 426     return Result.getValue(Op.ResNo);
 427
 428   case ISD::EXTRACT_ELEMENT:
 429     // Get both the low and high parts.
 430     ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 431     if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
 432       Result = Tmp2;  // 1 -> Hi
 433     else
 434       Result = Tmp1;  // 0 -> Lo
 435     break;
 436
 437   case ISD::CopyToReg:
 438     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 439
 440     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 441     case Legal:
 442       // Legalize the incoming value (must be legal).
 443       Tmp2 = LegalizeOp(Node->getOperand(1));
 444       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 445         Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
 446       break;
 447     case Promote:
 448       Tmp2 = PromoteOp(Node->getOperand(1));
 449       Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
 450       break;
 451     case Expand:
 452       SDOperand Lo, Hi;
 453       ExpandOp(Node->getOperand(1), Lo, Hi);
 454       unsigned Reg = cast<RegSDNode>(Node)->getReg();
 455       Lo = DAG.getCopyToReg(Tmp1, Lo, Reg);
 456       Hi = DAG.getCopyToReg(Tmp1, Hi, Reg+1);
 457       // Note that the copytoreg nodes are independent of each other.
 458       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
 459       assert(isTypeLegal(Result.getValueType()) &&
 460              "Cannot expand multiple times yet (i64 -> i16)");
 461       break;
 462     }
 463     break;
 464
 465   case ISD::RET:
 466     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 467     switch (Node->getNumOperands()) {
 468     case 2:  // ret val
 469       switch (getTypeAction(Node->getOperand(1).getValueType())) {
 470       case Legal:
 471         Tmp2 = LegalizeOp(Node->getOperand(1));
 472         if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 473           Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 474         break;
 475       case Expand: {
 476         SDOperand Lo, Hi;
 477         ExpandOp(Node->getOperand(1), Lo, Hi);
 478         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
 479         break;
 480       }
 481       case Promote:
 482         Tmp2 = PromoteOp(Node->getOperand(1));
 483         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 484         break;
 485       }
 486       break;
 487     case 1:  // ret void
 488       if (Tmp1 != Node->getOperand(0))
 489         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1);
 490       break;
 491     default: { // ret <values>
 492       std::vector<SDOperand> NewValues;
 493       NewValues.push_back(Tmp1);
 494       for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
 495         switch (getTypeAction(Node->getOperand(i).getValueType())) {
 496         case Legal:
 497           NewValues.push_back(LegalizeOp(Node->getOperand(i)));
 498           break;
 499         case Expand: {
 500           SDOperand Lo, Hi;
 501           ExpandOp(Node->getOperand(i), Lo, Hi);
 502           NewValues.push_back(Lo);
 503           NewValues.push_back(Hi);
 504           break;
 505         }
 506         case Promote:
 507           assert(0 && "Can't promote multiple return value yet!");
 508         }
 509       Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
 510       break;
 511     }
 512     }
 513     break;
 514   case ISD::STORE:
 515     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 516     Tmp2 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 517
 518     // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
 519     if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){
 520       if (CFP->getValueType(0) == MVT::f32) {
 521         union {
 522           unsigned I;
 523           float    F;
 524         } V;
 525         V.F = CFP->getValue();
 526         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 527                              DAG.getConstant(V.I, MVT::i32), Tmp2);
 528       } else {
 529         assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
 530         union {
 531           uint64_t I;
 532           double   F;
 533         } V;
 534         V.F = CFP->getValue();
 535         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 536                              DAG.getConstant(V.I, MVT::i64), Tmp2);
 537       }
 538       Node = Result.Val;
 539     }
 540
 541     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 542     case Legal: {
 543       SDOperand Val = LegalizeOp(Node->getOperand(1));
 544       if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) ||
 545           Tmp2 != Node->getOperand(2))
 546         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2);
 547       break;
 548     }
 549     case Promote:
 550       // Truncate the value and store the result.
 551       Tmp3 = PromoteOp(Node->getOperand(1));
 552       Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2,
 553                            Node->getOperand(1).getValueType());
 554       break;
 555
 556     case Expand:
 557       SDOperand Lo, Hi;
 558       ExpandOp(Node->getOperand(1), Lo, Hi);
 559
 560       if (!TLI.isLittleEndian())
 561         std::swap(Lo, Hi);
 562
 563       Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2);
 564
 565       unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8;
 566       Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
 567                          getIntPtrConstant(IncrementSize));
 568       assert(isTypeLegal(Tmp2.getValueType()) &&
 569              "Pointers must be legal!");
 570       Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2);
 571       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
 572       break;
 573     }
 574     break;
 575   case ISD::PCMARKER:
 576     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 577     if (Tmp1 != Node->getOperand(0))
 578       Result = DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp1,Node->getOperand(1));
 579     break;
 580   case ISD::TRUNCSTORE:
 581     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 582     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 583
 584     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 585     case Legal:
 586       Tmp2 = LegalizeOp(Node->getOperand(1));
 587       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 588           Tmp3 != Node->getOperand(2))
 589         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3,
 590                              cast<MVTSDNode>(Node)->getExtraValueType());
 591       break;
 592     case Promote:
 593     case Expand:
 594       assert(0 && "Cannot handle illegal TRUNCSTORE yet!");
 595     }
 596     break;
 597   case ISD::SELECT:
 598     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 599     case Expand: assert(0 && "It's impossible to expand bools");
 600     case Legal:
 601       Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
 602       break;
 603     case Promote:
 604       Tmp1 = PromoteOp(Node->getOperand(0));  // Promote the condition.
 605       break;
 606     }
 607     Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
 608     Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
 609
 610     switch (TLI.getOperationAction(Node->getOpcode(), Tmp2.getValueType())) {
 611     default: assert(0 && "This action is not supported yet!");
 612     case TargetLowering::Legal:
 613       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 614           Tmp3 != Node->getOperand(2))
 615         Result = DAG.getNode(ISD::SELECT, Node->getValueType(0),
 616                              Tmp1, Tmp2, Tmp3);
 617       break;
 618     case TargetLowering::Promote: {
 619       MVT::ValueType NVT =
 620         TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType());
 621       unsigned ExtOp, TruncOp;
 622       if (MVT::isInteger(Tmp2.getValueType())) {
 623         ExtOp = ISD::ZERO_EXTEND;
 624         TruncOp  = ISD::TRUNCATE;
 625       } else {
 626         ExtOp = ISD::FP_EXTEND;
 627         TruncOp  = ISD::FP_ROUND;
 628       }
 629       // Promote each of the values to the new type.
 630       Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2);
 631       Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3);
 632       // Perform the larger operation, then round down.
 633       Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3);
 634       Result = DAG.getNode(TruncOp, Node->getValueType(0), Result);
 635       break;
 636     }
 637     }
 638     break;
 639   case ISD::SETCC:
 640     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 641     case Legal:
 642       Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 643       Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 644       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 645         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 646                               Node->getValueType(0), Tmp1, Tmp2);
 647       break;
 648     case Promote:
 649       Tmp1 = PromoteOp(Node->getOperand(0));   // LHS
 650       Tmp2 = PromoteOp(Node->getOperand(1));   // RHS
 651
 652       // If this is an FP compare, the operands have already been extended.
 653       if (MVT::isInteger(Node->getOperand(0).getValueType())) {
 654         MVT::ValueType VT = Node->getOperand(0).getValueType();
 655         MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 656
 657         // Otherwise, we have to insert explicit sign or zero extends.  Note
 658         // that we could insert sign extends for ALL conditions, but zero extend
 659         // is cheaper on many machines (an AND instead of two shifts), so prefer
 660         // it.
 661         switch (cast<SetCCSDNode>(Node)->getCondition()) {
 662         default: assert(0 && "Unknown integer comparison!");
 663         case ISD::SETEQ:
 664         case ISD::SETNE:
 665         case ISD::SETUGE:
 666         case ISD::SETUGT:
 667         case ISD::SETULE:
 668         case ISD::SETULT:
 669           // ALL of these operations will work if we either sign or zero extend
 670           // the operands (including the unsigned comparisons!).  Zero extend is
 671           // usually a simpler/cheaper operation, so prefer it.
 672           Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
 673           Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT);
 674           break;
 675         case ISD::SETGE:
 676         case ISD::SETGT:
 677         case ISD::SETLT:
 678         case ISD::SETLE:
 679           Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
 680           Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT);
 681           break;
 682         }
 683
 684       }
 685       Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 686                             Node->getValueType(0), Tmp1, Tmp2);
 687       break;
 688     case Expand:
 689       SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
 690       ExpandOp(Node->getOperand(0), LHSLo, LHSHi);
 691       ExpandOp(Node->getOperand(1), RHSLo, RHSHi);
 692       switch (cast<SetCCSDNode>(Node)->getCondition()) {
 693       case ISD::SETEQ:
 694       case ISD::SETNE:
 695         Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
 696         Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
 697         Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
 698         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 699                               Node->getValueType(0), Tmp1,
 700                               DAG.getConstant(0, Tmp1.getValueType()));
 701         break;
 702       default:
 703         // FIXME: This generated code sucks.
 704         ISD::CondCode LowCC;
 705         switch (cast<SetCCSDNode>(Node)->getCondition()) {
 706         default: assert(0 && "Unknown integer setcc!");
 707         case ISD::SETLT:
 708         case ISD::SETULT: LowCC = ISD::SETULT; break;
 709         case ISD::SETGT:
 710         case ISD::SETUGT: LowCC = ISD::SETUGT; break;
 711         case ISD::SETLE:
 712         case ISD::SETULE: LowCC = ISD::SETULE; break;
 713         case ISD::SETGE:
 714         case ISD::SETUGE: LowCC = ISD::SETUGE; break;
 715         }
 716
 717         // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
 718         // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
 719         // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
 720
 721         // NOTE: on targets without efficient SELECT of bools, we can always use
 722         // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
 723         Tmp1 = DAG.getSetCC(LowCC, Node->getValueType(0), LHSLo, RHSLo);
 724         Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 725                             Node->getValueType(0), LHSHi, RHSHi);
 726         Result = DAG.getSetCC(ISD::SETEQ, Node->getValueType(0), LHSHi, RHSHi);
 727         Result = DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
 728                              Result, Tmp1, Tmp2);
 729         break;
 730       }
 731     }
 732     break;
 733
 734   case ISD::MEMSET:
 735   case ISD::MEMCPY:
 736   case ISD::MEMMOVE: {
 737     Tmp1 = LegalizeOp(Node->getOperand(0));      // Chain
 738     Tmp2 = LegalizeOp(Node->getOperand(1));      // Pointer
 739
 740     if (Node->getOpcode() == ISD::MEMSET) {      // memset = ubyte
 741       switch (getTypeAction(Node->getOperand(2).getValueType())) {
 742       case Expand: assert(0 && "Cannot expand a byte!");
 743       case Legal:
 744         Tmp3 = LegalizeOp(Node->getOperand(2));
 745         break;
 746       case Promote:
 747         Tmp3 = PromoteOp(Node->getOperand(2));
 748         break;
 749       }
 750     } else {
 751       Tmp3 = LegalizeOp(Node->getOperand(2));    // memcpy/move = pointer,
 752     }
 753
 754     SDOperand Tmp4;
 755     switch (getTypeAction(Node->getOperand(3).getValueType())) {
 756     case Expand: assert(0 && "Cannot expand this yet!");
 757     case Legal:
 758       Tmp4 = LegalizeOp(Node->getOperand(3));
 759       break;
 760     case Promote:
 761       Tmp4 = PromoteOp(Node->getOperand(3));
 762       break;
 763     }
 764
 765     SDOperand Tmp5;
 766     switch (getTypeAction(Node->getOperand(4).getValueType())) {  // uint
 767     case Expand: assert(0 && "Cannot expand this yet!");
 768     case Legal:
 769       Tmp5 = LegalizeOp(Node->getOperand(4));
 770       break;
 771     case Promote:
 772       Tmp5 = PromoteOp(Node->getOperand(4));
 773       break;
 774     }
 775
 776     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
 777     default: assert(0 && "This action not implemented for this operation!");
 778     case TargetLowering::Legal:
 779       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 780           Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) ||
 781           Tmp5 != Node->getOperand(4)) {
 782         std::vector<SDOperand> Ops;
 783         Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
 784         Ops.push_back(Tmp4); Ops.push_back(Tmp5);
 785         Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
 786       }
 787       break;
 788     case TargetLowering::Expand: {
 789       // Otherwise, the target does not support this operation.  Lower the
 790       // operation to an explicit libcall as appropriate.
 791       MVT::ValueType IntPtr = TLI.getPointerTy();
 792       const Type *IntPtrTy = TLI.getTargetData().getIntPtrType();
 793       std::vector<std::pair<SDOperand, const Type*> > Args;
 794
 795       const char *FnName = 0;
 796       if (Node->getOpcode() == ISD::MEMSET) {
 797         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
 798         // Extend the ubyte argument to be an int value for the call.
 799         Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
 800         Args.push_back(std::make_pair(Tmp3, Type::IntTy));
 801         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
 802
 803         FnName = "memset";
 804       } else if (Node->getOpcode() == ISD::MEMCPY ||
 805                  Node->getOpcode() == ISD::MEMMOVE) {
 806         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
 807         Args.push_back(std::make_pair(Tmp3, IntPtrTy));
 808         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
 809         FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
 810       } else {
 811         assert(0 && "Unknown op!");
 812       }
 813       std::pair<SDOperand,SDOperand> CallResult =
 814         TLI.LowerCallTo(Tmp1, Type::VoidTy, false,
 815                         DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
 816       Result = LegalizeOp(CallResult.second);
 817       break;
 818     }
 819     case TargetLowering::Custom:
 820       std::vector<SDOperand> Ops;
 821       Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
 822       Ops.push_back(Tmp4); Ops.push_back(Tmp5);
 823       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
 824       Result = TLI.LowerOperation(Result);
 825       Result = LegalizeOp(Result);
 826       break;
 827     }
 828     break;
 829   }
 830   case ISD::ADD_PARTS:
 831   case ISD::SUB_PARTS:
 832   case ISD::SHL_PARTS:
 833   case ISD::SRA_PARTS:
 834   case ISD::SRL_PARTS: {
 835     std::vector<SDOperand> Ops;
 836     bool Changed = false;
 837     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
 838       Ops.push_back(LegalizeOp(Node->getOperand(i)));
 839       Changed |= Ops.back() != Node->getOperand(i);
 840     }
 841     if (Changed)
 842       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops);
 843
 844     // Since these produce multiple values, make sure to remember that we
 845     // legalized all of them.
 846     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 847       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
 848     return Result.getValue(Op.ResNo);
 849   }
 850
 851     // Binary operators
 852   case ISD::ADD:
 853   case ISD::SUB:
 854   case ISD::MUL:
 855   case ISD::UDIV:
 856   case ISD::SDIV:
 857   case ISD::AND:
 858   case ISD::OR:
 859   case ISD::XOR:
 860   case ISD::SHL:
 861   case ISD::SRL:
 862   case ISD::SRA:
 863     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 864     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 865     if (Tmp1 != Node->getOperand(0) ||
 866         Tmp2 != Node->getOperand(1))
 867       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2);
 868     break;
 869
 870   case ISD::UREM:
 871   case ISD::SREM:
 872     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 873     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 874     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
 875     case TargetLowering::Legal:
 876       if (Tmp1 != Node->getOperand(0) ||
 877           Tmp2 != Node->getOperand(1))
 878         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
 879                              Tmp2);
 880       break;
 881     case TargetLowering::Promote:
 882     case TargetLowering::Custom:
 883       assert(0 && "Cannot promote/custom handle this yet!");
 884     case TargetLowering::Expand: {
 885       MVT::ValueType VT = Node->getValueType(0);
 886       unsigned Opc = (Node->getOpcode() == ISD::UREM) ? ISD::UDIV : ISD::SDIV;
 887       Result = DAG.getNode(Opc, VT, Tmp1, Tmp2);
 888       Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2);
 889       Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result);
 890       }
 891       break;
 892     }
 893     break;
 894
 895     // Unary operators
 896   case ISD::FABS:
 897   case ISD::FNEG:
 898     Tmp1 = LegalizeOp(Node->getOperand(0));
 899     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
 900     case TargetLowering::Legal:
 901       if (Tmp1 != Node->getOperand(0))
 902         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
 903       break;
 904     case TargetLowering::Promote:
 905     case TargetLowering::Custom:
 906       assert(0 && "Cannot promote/custom handle this yet!");
 907     case TargetLowering::Expand:
 908       if (Node->getOpcode() == ISD::FNEG) {
 909         // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
 910         Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0));
 911         Result = LegalizeOp(DAG.getNode(ISD::SUB, Node->getValueType(0),
 912                                         Tmp2, Tmp1));
 913       } else if (Node->getOpcode() == ISD::FABS) {
 914         // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
 915         MVT::ValueType VT = Node->getValueType(0);
 916         Tmp2 = DAG.getConstantFP(0.0, VT);
 917         Tmp2 = DAG.getSetCC(ISD::SETUGT, TLI.getSetCCResultTy(), Tmp1, Tmp2);
 918         Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1);
 919         Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3);
 920         Result = LegalizeOp(Result);
 921       } else {
 922         assert(0 && "Unreachable!");
 923       }
 924       break;
 925     }
 926     break;
 927
 928     // Conversion operators.  The source and destination have different types.
 929   case ISD::ZERO_EXTEND:
 930   case ISD::SIGN_EXTEND:
 931   case ISD::TRUNCATE:
 932   case ISD::FP_EXTEND:
 933   case ISD::FP_ROUND:
 934   case ISD::FP_TO_SINT:
 935   case ISD::FP_TO_UINT:
 936   case ISD::SINT_TO_FP:
 937   case ISD::UINT_TO_FP:
 938     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 939     case Legal:
 940       Tmp1 = LegalizeOp(Node->getOperand(0));
 941       if (Tmp1 != Node->getOperand(0))
 942         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
 943       break;
 944     case Expand:
 945       if (Node->getOpcode() == ISD::SINT_TO_FP ||
 946           Node->getOpcode() == ISD::UINT_TO_FP) {
 947         Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP,
 948                                Node->getValueType(0), Node->getOperand(0));
 949         Result = LegalizeOp(Result);
 950         break;
 951       } else if (Node->getOpcode() == ISD::TRUNCATE) {
 952         // In the expand case, we must be dealing with a truncate, because
 953         // otherwise the result would be larger than the source.
 954         ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 955
 956         // Since the result is legal, we should just be able to truncate the low
 957         // part of the source.
 958         Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
 959         break;
 960       }
 961       assert(0 && "Shouldn't need to expand other operators here!");
 962
 963     case Promote:
 964       switch (Node->getOpcode()) {
 965       case ISD::ZERO_EXTEND:
 966         Result = PromoteOp(Node->getOperand(0));
 967         // NOTE: Any extend would work here...
 968         Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
 969         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Op.getValueType(),
 970                              Result, Node->getOperand(0).getValueType());
 971         break;
 972       case ISD::SIGN_EXTEND:
 973         Result = PromoteOp(Node->getOperand(0));
 974         // NOTE: Any extend would work here...
 975         Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
 976         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
 977                              Result, Node->getOperand(0).getValueType());
 978         break;
 979       case ISD::TRUNCATE:
 980         Result = PromoteOp(Node->getOperand(0));
 981         Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
 982         break;
 983       case ISD::FP_EXTEND:
 984         Result = PromoteOp(Node->getOperand(0));
 985         if (Result.getValueType() != Op.getValueType())
 986           // Dynamically dead while we have only 2 FP types.
 987           Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
 988         break;
 989       case ISD::FP_ROUND:
 990       case ISD::FP_TO_SINT:
 991       case ISD::FP_TO_UINT:
 992         Result = PromoteOp(Node->getOperand(0));
 993         Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
 994         break;
 995       case ISD::SINT_TO_FP:
 996         Result = PromoteOp(Node->getOperand(0));
 997         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
 998                              Result, Node->getOperand(0).getValueType());
 999         Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result);
1000         break;
1001       case ISD::UINT_TO_FP:
1002         Result = PromoteOp(Node->getOperand(0));
1003         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(),
1004                              Result, Node->getOperand(0).getValueType());
1005         Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result);
1006         break;
1007       }
1008     }
1009     break;
1010   case ISD::FP_ROUND_INREG:
1011   case ISD::SIGN_EXTEND_INREG:
1012   case ISD::ZERO_EXTEND_INREG: {
1013     Tmp1 = LegalizeOp(Node->getOperand(0));
1014     MVT::ValueType ExtraVT = cast<MVTSDNode>(Node)->getExtraValueType();
1015
1016     // If this operation is not supported, convert it to a shl/shr or load/store
1017     // pair.
1018     switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
1019     default: assert(0 && "This action not supported for this op yet!");
1020     case TargetLowering::Legal:
1021       if (Tmp1 != Node->getOperand(0))
1022         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
1023                              ExtraVT);
1024       break;
1025     case TargetLowering::Expand:
1026       // If this is an integer extend and shifts are supported, do that.
1027       if (Node->getOpcode() == ISD::ZERO_EXTEND_INREG) {
1028         // NOTE: we could fall back on load/store here too for targets without
1029         // AND.  However, it is doubtful that any exist.
1030         // AND out the appropriate bits.
1031         SDOperand Mask =
1032           DAG.getConstant((1ULL << MVT::getSizeInBits(ExtraVT))-1,
1033                           Node->getValueType(0));
1034         Result = DAG.getNode(ISD::AND, Node->getValueType(0),
1035                              Node->getOperand(0), Mask);
1036       } else if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
1037         // NOTE: we could fall back on load/store here too for targets without
1038         // SAR.  However, it is doubtful that any exist.
1039         unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
1040                             MVT::getSizeInBits(ExtraVT);
1041         SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy());
1042         Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
1043                              Node->getOperand(0), ShiftCst);
1044         Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
1045                              Result, ShiftCst);
1046       } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
1047         // The only way we can lower this is to turn it into a STORETRUNC,
1048         // EXTLOAD pair, targetting a temporary location (a stack slot).
1049
1050         // NOTE: there is a choice here between constantly creating new stack
1051         // slots and always reusing the same one.  We currently always create
1052         // new ones, as reuse may inhibit scheduling.
1053         const Type *Ty = MVT::getTypeForValueType(ExtraVT);
1054         unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty);
1055         unsigned Align  = TLI.getTargetData().getTypeAlignment(Ty);
1056         MachineFunction &MF = DAG.getMachineFunction();
1057         int SSFI =
1058           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
1059         SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
1060         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
1061                              Node->getOperand(0), StackSlot, ExtraVT);
1062         Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0),
1063                              Result, StackSlot, ExtraVT);
1064       } else {
1065         assert(0 && "Unknown op");
1066       }
1067       Result = LegalizeOp(Result);
1068       break;
1069     }
1070     break;
1071   }
1072   }
1073
1074   if (!Op.Val->hasOneUse())
1075     AddLegalizedOperand(Op, Result);
1076
1077   return Result;
1078 }
1079
1080 /// PromoteOp - Given an operation that produces a value in an invalid type,
1081 /// promote it to compute the value into a larger type.  The produced value will
1082 /// have the correct bits for the low portion of the register, but no guarantee
1083 /// is made about the top bits: it may be zero, sign-extended, or garbage.
1084 SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
1085   MVT::ValueType VT = Op.getValueType();
1086   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1087   assert(getTypeAction(VT) == Promote &&
1088          "Caller should expand or legalize operands that are not promotable!");
1089   assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
1090          "Cannot promote to smaller type!");
1091
1092   std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
1093   if (I != PromotedNodes.end()) return I->second;
1094
1095   SDOperand Tmp1, Tmp2, Tmp3;
1096
1097   SDOperand Result;
1098   SDNode *Node = Op.Val;
1099
1100   // Promotion needs an optimization step to clean up after it, and is not
1101   // careful to avoid operations the target does not support.  Make sure that
1102   // all generated operations are legalized in the next iteration.
1103   NeedsAnotherIteration = true;
1104
1105   switch (Node->getOpcode()) {
1106   default:
1107     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
1108     assert(0 && "Do not know how to promote this operator!");
1109     abort();
1110   case ISD::UNDEF:
1111     Result = DAG.getNode(ISD::UNDEF, NVT);
1112     break;
1113   case ISD::Constant:
1114     Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
1115     assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
1116     break;
1117   case ISD::ConstantFP:
1118     Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
1119     assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
1120     break;
1121   case ISD::CopyFromReg:
1122     Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), NVT,
1123                                 Node->getOperand(0));
1124     // Remember that we legalized the chain.
1125     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1126     break;
1127
1128   case ISD::SETCC:
1129     assert(getTypeAction(TLI.getSetCCResultTy()) == Legal &&
1130            "SetCC type is not legal??");
1131     Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
1132                           TLI.getSetCCResultTy(), Node->getOperand(0),
1133                           Node->getOperand(1));
1134     Result = LegalizeOp(Result);
1135     break;
1136
1137   case ISD::TRUNCATE:
1138     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1139     case Legal:
1140       Result = LegalizeOp(Node->getOperand(0));
1141       assert(Result.getValueType() >= NVT &&
1142              "This truncation doesn't make sense!");
1143       if (Result.getValueType() > NVT)    // Truncate to NVT instead of VT
1144         Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
1145       break;
1146     case Promote:
1147       // The truncation is not required, because we don't guarantee anything
1148       // about high bits anyway.
1149       Result = PromoteOp(Node->getOperand(0));
1150       break;
1151     case Expand:
1152       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
1153       // Truncate the low part of the expanded value to the result type
1154       Result = DAG.getNode(ISD::TRUNCATE, VT, Tmp1);
1155     }
1156     break;
1157   case ISD::SIGN_EXTEND:
1158   case ISD::ZERO_EXTEND:
1159     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1160     case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
1161     case Legal:
1162       // Input is legal?  Just do extend all the way to the larger type.
1163       Result = LegalizeOp(Node->getOperand(0));
1164       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1165       break;
1166     case Promote:
1167       // Promote the reg if it's smaller.
1168       Result = PromoteOp(Node->getOperand(0));
1169       // The high bits are not guaranteed to be anything.  Insert an extend.
1170       if (Node->getOpcode() == ISD::SIGN_EXTEND)
1171         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
1172                              Node->getOperand(0).getValueType());
1173       else
1174         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Result,
1175                              Node->getOperand(0).getValueType());
1176       break;
1177     }
1178     break;
1179
1180   case ISD::FP_EXTEND:
1181     assert(0 && "Case not implemented.  Dynamically dead with 2 FP types!");
1182   case ISD::FP_ROUND:
1183     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1184     case Expand: assert(0 && "BUG: Cannot expand FP regs!");
1185     case Promote:  assert(0 && "Unreachable with 2 FP types!");
1186     case Legal:
1187       // Input is legal?  Do an FP_ROUND_INREG.
1188       Result = LegalizeOp(Node->getOperand(0));
1189       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1190       break;
1191     }
1192     break;
1193
1194   case ISD::SINT_TO_FP:
1195   case ISD::UINT_TO_FP:
1196     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1197     case Legal:
1198       Result = LegalizeOp(Node->getOperand(0));
1199       // No extra round required here.
1200       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1201       break;
1202
1203     case Promote:
1204       Result = PromoteOp(Node->getOperand(0));
1205       if (Node->getOpcode() == ISD::SINT_TO_FP)
1206         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1207                              Result, Node->getOperand(0).getValueType());
1208       else
1209         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(),
1210                              Result, Node->getOperand(0).getValueType());
1211       // No extra round required here.
1212       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1213       break;
1214     case Expand:
1215       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT,
1216                              Node->getOperand(0));
1217       Result = LegalizeOp(Result);
1218
1219       // Round if we cannot tolerate excess precision.
1220       if (NoExcessFPPrecision)
1221         Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1222       break;
1223     }
1224     break;
1225
1226   case ISD::FP_TO_SINT:
1227   case ISD::FP_TO_UINT:
1228     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1229     case Legal:
1230       Tmp1 = LegalizeOp(Node->getOperand(0));
1231       break;
1232     case Promote:
1233       // The input result is prerounded, so we don't have to do anything
1234       // special.
1235       Tmp1 = PromoteOp(Node->getOperand(0));
1236       break;
1237     case Expand:
1238       assert(0 && "not implemented");
1239     }
1240     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1241     break;
1242
1243   case ISD::FABS:
1244   case ISD::FNEG:
1245     Tmp1 = PromoteOp(Node->getOperand(0));
1246     assert(Tmp1.getValueType() == NVT);
1247     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1248     // NOTE: we do not have to do any extra rounding here for
1249     // NoExcessFPPrecision, because we know the input will have the appropriate
1250     // precision, and these operations don't modify precision at all.
1251     break;
1252
1253   case ISD::AND:
1254   case ISD::OR:
1255   case ISD::XOR:
1256   case ISD::ADD:
1257   case ISD::SUB:
1258   case ISD::MUL:
1259     // The input may have strange things in the top bits of the registers, but
1260     // these operations don't care.  They may have wierd bits going out, but
1261     // that too is okay if they are integer operations.
1262     Tmp1 = PromoteOp(Node->getOperand(0));
1263     Tmp2 = PromoteOp(Node->getOperand(1));
1264     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
1265     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1266
1267     // However, if this is a floating point operation, they will give excess
1268     // precision that we may not be able to tolerate.  If we DO allow excess
1269     // precision, just leave it, otherwise excise it.
1270     // FIXME: Why would we need to round FP ops more than integer ones?
1271     //     Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
1272     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
1273       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1274     break;
1275
1276   case ISD::SDIV:
1277   case ISD::SREM:
1278     // These operators require that their input be sign extended.
1279     Tmp1 = PromoteOp(Node->getOperand(0));
1280     Tmp2 = PromoteOp(Node->getOperand(1));
1281     if (MVT::isInteger(NVT)) {
1282       Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
1283       Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT);
1284     }
1285     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1286
1287     // Perform FP_ROUND: this is probably overly pessimistic.
1288     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
1289       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1290     break;
1291
1292   case ISD::UDIV:
1293   case ISD::UREM:
1294     // These operators require that their input be zero extended.
1295     Tmp1 = PromoteOp(Node->getOperand(0));
1296     Tmp2 = PromoteOp(Node->getOperand(1));
1297     assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
1298     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
1299     Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT);
1300     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1301     break;
1302
1303   case ISD::SHL:
1304     Tmp1 = PromoteOp(Node->getOperand(0));
1305     Tmp2 = LegalizeOp(Node->getOperand(1));
1306     Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2);
1307     break;
1308   case ISD::SRA:
1309     // The input value must be properly sign extended.
1310     Tmp1 = PromoteOp(Node->getOperand(0));
1311     Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
1312     Tmp2 = LegalizeOp(Node->getOperand(1));
1313     Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2);
1314     break;
1315   case ISD::SRL:
1316     // The input value must be properly zero extended.
1317     Tmp1 = PromoteOp(Node->getOperand(0));
1318     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
1319     Tmp2 = LegalizeOp(Node->getOperand(1));
1320     Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2);
1321     break;
1322   case ISD::LOAD:
1323     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
1324     Tmp2 = LegalizeOp(Node->getOperand(1));   // Legalize the pointer.
1325     Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, VT);
1326
1327     // Remember that we legalized the chain.
1328     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1329     break;
1330   case ISD::SELECT:
1331     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1332     case Expand: assert(0 && "It's impossible to expand bools");
1333     case Legal:
1334       Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition.
1335       break;
1336     case Promote:
1337       Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition.
1338       break;
1339     }
1340     Tmp2 = PromoteOp(Node->getOperand(1));   // Legalize the op0
1341     Tmp3 = PromoteOp(Node->getOperand(2));   // Legalize the op1
1342     Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3);
1343     break;
1344   case ISD::CALL: {
1345     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1346     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
1347
1348     std::vector<SDOperand> Ops;
1349     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i)
1350       Ops.push_back(LegalizeOp(Node->getOperand(i)));
1351
1352     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
1353            "Can only promote single result calls");
1354     std::vector<MVT::ValueType> RetTyVTs;
1355     RetTyVTs.reserve(2);
1356     RetTyVTs.push_back(NVT);
1357     RetTyVTs.push_back(MVT::Other);
1358     SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops);
1359     Result = SDOperand(NC, 0);
1360
1361     // Insert the new chain mapping.
1362     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1363     break;
1364   }
1365   }
1366
1367   assert(Result.Val && "Didn't set a result!");
1368   AddPromotedOperand(Op, Result);
1369   return Result;
1370 }
1371
1372 /// ExpandAddSub - Find a clever way to expand this add operation into
1373 /// subcomponents.
1374 void SelectionDAGLegalize::
1375 ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS,
1376               SDOperand &Lo, SDOperand &Hi) {
1377   // Expand the subcomponents.
1378   SDOperand LHSL, LHSH, RHSL, RHSH;
1379   ExpandOp(LHS, LHSL, LHSH);
1380   ExpandOp(RHS, RHSL, RHSH);
1381
1382   // Convert this add to the appropriate ADDC pair.  The low part has no carry
1383   // in.
1384   std::vector<SDOperand> Ops;
1385   Ops.push_back(LHSL);
1386   Ops.push_back(LHSH);
1387   Ops.push_back(RHSL);
1388   Ops.push_back(RHSH);
1389   Lo = DAG.getNode(NodeOp, LHSL.getValueType(), Ops);
1390   Hi = Lo.getValue(1);
1391 }
1392
1393 void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp,
1394                                             SDOperand Op, SDOperand Amt,
1395                                             SDOperand &Lo, SDOperand &Hi) {
1396   // Expand the subcomponents.
1397   SDOperand LHSL, LHSH;
1398   ExpandOp(Op, LHSL, LHSH);
1399
1400   std::vector<SDOperand> Ops;
1401   Ops.push_back(LHSL);
1402   Ops.push_back(LHSH);
1403   Ops.push_back(Amt);
1404   Lo = DAG.getNode(NodeOp, LHSL.getValueType(), Ops);
1405   Hi = Lo.getValue(1);
1406 }
1407
1408
1409 /// ExpandShift - Try to find a clever way to expand this shift operation out to
1410 /// smaller elements.  If we can't find a way that is more efficient than a
1411 /// libcall on this target, return false.  Otherwise, return true with the
1412 /// low-parts expanded into Lo and Hi.
1413 bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
1414                                        SDOperand &Lo, SDOperand &Hi) {
1415   // FIXME: This code is buggy, disable it for now.  Note that we should at
1416   // least handle the case when Amt is an immediate here.
1417   return false;
1418
1419   assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
1420          "This is not a shift!");
1421   MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
1422
1423   // If we have an efficient select operation (or if the selects will all fold
1424   // away), lower to some complex code, otherwise just emit the libcall.
1425   if (TLI.getOperationAction(ISD::SELECT, NVT) != TargetLowering::Legal &&
1426       !isa<ConstantSDNode>(Amt))
1427     return false;
1428
1429   SDOperand InL, InH;
1430   ExpandOp(Op, InL, InH);
1431   SDOperand ShAmt = LegalizeOp(Amt);
1432   MVT::ValueType ShTy = ShAmt.getValueType();
1433
1434   unsigned NVTBits = MVT::getSizeInBits(NVT);
1435   SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy,           // NAmt = 32-ShAmt
1436                                DAG.getConstant(NVTBits, ShTy), ShAmt);
1437
1438   // Compare the unmasked shift amount against 32.
1439   SDOperand Cond = DAG.getSetCC(ISD::SETGE, TLI.getSetCCResultTy(), ShAmt,
1440                                 DAG.getConstant(NVTBits, ShTy));
1441
1442   if (TLI.getShiftAmountFlavor() != TargetLowering::Mask) {
1443     ShAmt = DAG.getNode(ISD::AND, ShTy, ShAmt,             // ShAmt &= 31
1444                         DAG.getConstant(NVTBits-1, ShTy));
1445     NAmt  = DAG.getNode(ISD::AND, ShTy, NAmt,              // NAmt &= 31
1446                         DAG.getConstant(NVTBits-1, ShTy));
1447   }
1448
1449   if (Opc == ISD::SHL) {
1450     SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << Amt) | (Lo >> NAmt)
1451                                DAG.getNode(ISD::SHL, NVT, InH, ShAmt),
1452                                DAG.getNode(ISD::SRL, NVT, InL, NAmt));
1453     SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31
1454
1455     Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
1456     Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2);
1457   } else {
1458     SDOperand HiLoPart = DAG.getNode(ISD::SELECT, NVT,
1459                                      DAG.getSetCC(ISD::SETEQ,
1460                                                   TLI.getSetCCResultTy(), NAmt,
1461                                                   DAG.getConstant(32, ShTy)),
1462                                      DAG.getConstant(0, NVT),
1463                                      DAG.getNode(ISD::SHL, NVT, InH, NAmt));
1464     SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << NAmt) | (Lo >> Amt)
1465                                HiLoPart,
1466                                DAG.getNode(ISD::SRL, NVT, InL, ShAmt));
1467     SDOperand T2 = DAG.getNode(Opc, NVT, InH, ShAmt);  // T2 = InH >> ShAmt&31
1468
1469     SDOperand HiPart;
1470     if (Opc == ISD::SRA)
1471       HiPart = DAG.getNode(ISD::SRA, NVT, InH,
1472                            DAG.getConstant(NVTBits-1, ShTy));
1473     else
1474       HiPart = DAG.getConstant(0, NVT);
1475     Lo = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
1476     Hi = DAG.getNode(ISD::SELECT, NVT, Cond, HiPart, T2);
1477   }
1478   return true;
1479 }
1480
1481 /// FindLatestAdjCallStackDown - Scan up the dag to find the latest (highest
1482 /// NodeDepth) node that is an AdjCallStackDown operation and occurs later than
1483 /// Found.
1484 static void FindLatestAdjCallStackDown(SDNode *Node, SDNode *&Found) {
1485   if (Node->getNodeDepth() <= Found->getNodeDepth()) return;
1486
1487   // If we found an ADJCALLSTACKDOWN, we already know this node occurs later
1488   // than the Found node. Just remember this node and return.
1489   if (Node->getOpcode() == ISD::ADJCALLSTACKDOWN) {
1490     Found = Node;
1491     return;
1492   }
1493
1494   // Otherwise, scan the operands of Node to see if any of them is a call.
1495   assert(Node->getNumOperands() != 0 &&
1496          "All leaves should have depth equal to the entry node!");
1497   for (unsigned i = 0, e = Node->getNumOperands()-1; i != e; ++i)
1498     FindLatestAdjCallStackDown(Node->getOperand(i).Val, Found);
1499
1500   // Tail recurse for the last iteration.
1501   FindLatestAdjCallStackDown(Node->getOperand(Node->getNumOperands()-1).Val,
1502                              Found);
1503 }
1504
1505
1506 /// FindEarliestAdjCallStackUp - Scan down the dag to find the earliest (lowest
1507 /// NodeDepth) node that is an AdjCallStackUp operation and occurs more recent
1508 /// than Found.
1509 static void FindEarliestAdjCallStackUp(SDNode *Node, SDNode *&Found) {
1510   if (Found && Node->getNodeDepth() >= Found->getNodeDepth()) return;
1511
1512   // If we found an ADJCALLSTACKUP, we already know this node occurs earlier
1513   // than the Found node. Just remember this node and return.
1514   if (Node->getOpcode() == ISD::ADJCALLSTACKUP) {
1515     Found = Node;
1516     return;
1517   }
1518
1519   // Otherwise, scan the operands of Node to see if any of them is a call.
1520   SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
1521   if (UI == E) return;
1522   for (--E; UI != E; ++UI)
1523     FindEarliestAdjCallStackUp(*UI, Found);
1524
1525   // Tail recurse for the last iteration.
1526   FindEarliestAdjCallStackUp(*UI, Found);
1527 }
1528
1529 /// FindAdjCallStackUp - Given a chained node that is part of a call sequence,
1530 /// find the ADJCALLSTACKUP node that terminates the call sequence.
1531 static SDNode *FindAdjCallStackUp(SDNode *Node) {
1532   if (Node->getOpcode() == ISD::ADJCALLSTACKUP)
1533     return Node;
1534   if (Node->use_empty())
1535     return 0;   // No adjcallstackup
1536
1537   if (Node->hasOneUse())  // Simple case, only has one user to check.
1538     return FindAdjCallStackUp(*Node->use_begin());
1539
1540   SDOperand TheChain(Node, Node->getNumValues()-1);
1541   assert(TheChain.getValueType() == MVT::Other && "Is not a token chain!");
1542
1543   for (SDNode::use_iterator UI = Node->use_begin(),
1544          E = Node->use_end(); ; ++UI) {
1545     assert(UI != E && "Didn't find a user of the tokchain, no ADJCALLSTACKUP!");
1546
1547     // Make sure to only follow users of our token chain.
1548     SDNode *User = *UI;
1549     for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
1550       if (User->getOperand(i) == TheChain)
1551         return FindAdjCallStackUp(User);
1552   }
1553   assert(0 && "Unreachable");
1554   abort();
1555 }
1556
1557 /// FindInputOutputChains - If we are replacing an operation with a call we need
1558 /// to find the call that occurs before and the call that occurs after it to
1559 /// properly serialize the calls in the block.
1560 static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain,
1561                                        SDOperand Entry) {
1562   SDNode *LatestAdjCallStackDown = Entry.Val;
1563   FindLatestAdjCallStackDown(OpNode, LatestAdjCallStackDown);
1564   //std::cerr << "Found node: "; LatestAdjCallStackDown->dump(); std::cerr <<"\n";
1565
1566   SDNode *LatestAdjCallStackUp = FindAdjCallStackUp(LatestAdjCallStackDown);
1567
1568
1569   SDNode *EarliestAdjCallStackUp = 0;
1570   FindEarliestAdjCallStackUp(OpNode, EarliestAdjCallStackUp);
1571
1572   if (EarliestAdjCallStackUp) {
1573     //std::cerr << "Found node: ";
1574     //EarliestAdjCallStackUp->dump(); std::cerr <<"\n";
1575   }
1576
1577   return SDOperand(LatestAdjCallStackUp, 0);
1578 }
1579
1580
1581
1582 // ExpandLibCall - Expand a node into a call to a libcall.  If the result value
1583 // does not fit into a register, return the lo part and set the hi part to the
1584 // by-reg argument.  If it does fit into a single register, return the result
1585 // and leave the Hi part unset.
1586 SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node,
1587                                               SDOperand &Hi) {
1588   SDNode *OutChain;
1589   SDOperand InChain = FindInputOutputChains(Node, OutChain,
1590                                             DAG.getEntryNode());
1591   if (InChain.Val == 0)
1592     InChain = DAG.getEntryNode();
1593
1594   TargetLowering::ArgListTy Args;
1595   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
1596     MVT::ValueType ArgVT = Node->getOperand(i).getValueType();
1597     const Type *ArgTy = MVT::getTypeForValueType(ArgVT);
1598     Args.push_back(std::make_pair(Node->getOperand(i), ArgTy));
1599   }
1600   SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy());
1601
1602   // We don't care about token chains for libcalls.  We just use the entry
1603   // node as our input and ignore the output chain.  This allows us to place
1604   // calls wherever we need them to satisfy data dependences.
1605   const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0));
1606   SDOperand Result = TLI.LowerCallTo(InChain, RetTy, false, Callee,
1607                                      Args, DAG).first;
1608   switch (getTypeAction(Result.getValueType())) {
1609   default: assert(0 && "Unknown thing");
1610   case Legal:
1611     return Result;
1612   case Promote:
1613     assert(0 && "Cannot promote this yet!");
1614   case Expand:
1615     SDOperand Lo;
1616     ExpandOp(Result, Lo, Hi);
1617     return Lo;
1618   }
1619 }
1620
1621
1622 /// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the
1623 /// destination type is legal.
1624 SDOperand SelectionDAGLegalize::
1625 ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) {
1626   assert(getTypeAction(DestTy) == Legal && "Destination type is not legal!");
1627   assert(getTypeAction(Source.getValueType()) == Expand &&
1628          "This is not an expansion!");
1629   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
1630
1631   SDNode *OutChain;
1632   SDOperand InChain = FindInputOutputChains(Source.Val, OutChain,
1633                                             DAG.getEntryNode());
1634
1635   const char *FnName = 0;
1636   if (isSigned) {
1637     if (DestTy == MVT::f32)
1638       FnName = "__floatdisf";
1639     else {
1640       assert(DestTy == MVT::f64 && "Unknown fp value type!");
1641       FnName = "__floatdidf";
1642     }
1643   } else {
1644     // If this is unsigned, and not supported, first perform the conversion to
1645     // signed, then adjust the result if the sign bit is set.
1646     SDOperand SignedConv = ExpandIntToFP(false, DestTy, Source);
1647
1648     assert(0 && "Unsigned casts not supported yet!");
1649   }
1650   SDOperand Callee = DAG.getExternalSymbol(FnName, TLI.getPointerTy());
1651
1652   TargetLowering::ArgListTy Args;
1653   const Type *ArgTy = MVT::getTypeForValueType(Source.getValueType());
1654   Args.push_back(std::make_pair(Source, ArgTy));
1655
1656   // We don't care about token chains for libcalls.  We just use the entry
1657   // node as our input and ignore the output chain.  This allows us to place
1658   // calls wherever we need them to satisfy data dependences.
1659   const Type *RetTy = MVT::getTypeForValueType(DestTy);
1660   return TLI.LowerCallTo(InChain, RetTy, false, Callee, Args, DAG).first;
1661
1662 }
1663
1664
1665
1666 /// ExpandOp - Expand the specified SDOperand into its two component pieces
1667 /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
1668 /// LegalizeNodes map is filled in for any results that are not expanded, the
1669 /// ExpandedNodes map is filled in for any results that are expanded, and the
1670 /// Lo/Hi values are returned.
1671 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
1672   MVT::ValueType VT = Op.getValueType();
1673   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1674   SDNode *Node = Op.Val;
1675   assert(getTypeAction(VT) == Expand && "Not an expanded type!");
1676   assert(MVT::isInteger(VT) && "Cannot expand FP values!");
1677   assert(MVT::isInteger(NVT) && NVT < VT &&
1678          "Cannot expand to FP value or to larger int value!");
1679
1680   // If there is more than one use of this, see if we already expanded it.
1681   // There is no use remembering values that only have a single use, as the map
1682   // entries will never be reused.
1683   if (!Node->hasOneUse()) {
1684     std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
1685       = ExpandedNodes.find(Op);
1686     if (I != ExpandedNodes.end()) {
1687       Lo = I->second.first;
1688       Hi = I->second.second;
1689       return;
1690     }
1691   }
1692
1693   // Expanding to multiple registers needs to perform an optimization step, and
1694   // is not careful to avoid operations the target does not support.  Make sure
1695   // that all generated operations are legalized in the next iteration.
1696   NeedsAnotherIteration = true;
1697
1698   switch (Node->getOpcode()) {
1699   default:
1700     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
1701     assert(0 && "Do not know how to expand this operator!");
1702     abort();
1703   case ISD::UNDEF:
1704     Lo = DAG.getNode(ISD::UNDEF, NVT);
1705     Hi = DAG.getNode(ISD::UNDEF, NVT);
1706     break;
1707   case ISD::Constant: {
1708     uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
1709     Lo = DAG.getConstant(Cst, NVT);
1710     Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
1711     break;
1712   }
1713
1714   case ISD::CopyFromReg: {
1715     unsigned Reg = cast<RegSDNode>(Node)->getReg();
1716     // Aggregate register values are always in consequtive pairs.
1717     Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0));
1718     Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1));
1719
1720     // Remember that we legalized the chain.
1721     AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
1722
1723     assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
1724     break;
1725   }
1726
1727   case ISD::BUILD_PAIR:
1728     // Legalize both operands.  FIXME: in the future we should handle the case
1729     // where the two elements are not legal.
1730     assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
1731     Lo = LegalizeOp(Node->getOperand(0));
1732     Hi = LegalizeOp(Node->getOperand(1));
1733     break;
1734
1735   case ISD::LOAD: {
1736     SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
1737     SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1738     Lo = DAG.getLoad(NVT, Ch, Ptr);
1739
1740     // Increment the pointer to the other half.
1741     unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
1742     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1743                       getIntPtrConstant(IncrementSize));
1744     Hi = DAG.getLoad(NVT, Ch, Ptr);
1745
1746     // Build a factor node to remember that this load is independent of the
1747     // other one.
1748     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
1749                                Hi.getValue(1));
1750
1751     // Remember that we legalized the chain.
1752     AddLegalizedOperand(Op.getValue(1), TF);
1753     if (!TLI.isLittleEndian())
1754       std::swap(Lo, Hi);
1755     break;
1756   }
1757   case ISD::CALL: {
1758     SDOperand Chain  = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1759     SDOperand Callee = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
1760
1761     bool Changed = false;
1762     std::vector<SDOperand> Ops;
1763     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
1764       Ops.push_back(LegalizeOp(Node->getOperand(i)));
1765       Changed |= Ops.back() != Node->getOperand(i);
1766     }
1767
1768     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
1769            "Can only expand a call once so far, not i64 -> i16!");
1770
1771     std::vector<MVT::ValueType> RetTyVTs;
1772     RetTyVTs.reserve(3);
1773     RetTyVTs.push_back(NVT);
1774     RetTyVTs.push_back(NVT);
1775     RetTyVTs.push_back(MVT::Other);
1776     SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee, Ops);
1777     Lo = SDOperand(NC, 0);
1778     Hi = SDOperand(NC, 1);
1779
1780     // Insert the new chain mapping.
1781     AddLegalizedOperand(Op.getValue(1), Hi.getValue(2));
1782     break;
1783   }
1784   case ISD::AND:
1785   case ISD::OR:
1786   case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
1787     SDOperand LL, LH, RL, RH;
1788     ExpandOp(Node->getOperand(0), LL, LH);
1789     ExpandOp(Node->getOperand(1), RL, RH);
1790     Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
1791     Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
1792     break;
1793   }
1794   case ISD::SELECT: {
1795     SDOperand C, LL, LH, RL, RH;
1796
1797     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1798     case Expand: assert(0 && "It's impossible to expand bools");
1799     case Legal:
1800       C = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
1801       break;
1802     case Promote:
1803       C = PromoteOp(Node->getOperand(0));  // Promote the condition.
1804       break;
1805     }
1806     ExpandOp(Node->getOperand(1), LL, LH);
1807     ExpandOp(Node->getOperand(2), RL, RH);
1808     Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL);
1809     Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH);
1810     break;
1811   }
1812   case ISD::SIGN_EXTEND: {
1813     SDOperand In;
1814     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1815     case Expand: assert(0 && "expand-expand not implemented yet!");
1816     case Legal: In = LegalizeOp(Node->getOperand(0)); break;
1817     case Promote:
1818       In = PromoteOp(Node->getOperand(0));
1819       // Emit the appropriate sign_extend_inreg to get the value we want.
1820       In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(), In,
1821                        Node->getOperand(0).getValueType());
1822       break;
1823     }
1824
1825     // The low part is just a sign extension of the input (which degenerates to
1826     // a copy).
1827     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, In);
1828
1829     // The high part is obtained by SRA'ing all but one of the bits of the lo
1830     // part.
1831     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
1832     Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1,
1833                                                        TLI.getShiftAmountTy()));
1834     break;
1835   }
1836   case ISD::ZERO_EXTEND: {
1837     SDOperand In;
1838     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1839     case Expand: assert(0 && "expand-expand not implemented yet!");
1840     case Legal: In = LegalizeOp(Node->getOperand(0)); break;
1841     case Promote:
1842       In = PromoteOp(Node->getOperand(0));
1843       // Emit the appropriate zero_extend_inreg to get the value we want.
1844       In = DAG.getNode(ISD::ZERO_EXTEND_INREG, In.getValueType(), In,
1845                        Node->getOperand(0).getValueType());
1846       break;
1847     }
1848
1849     // The low part is just a zero extension of the input (which degenerates to
1850     // a copy).
1851     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
1852
1853     // The high part is just a zero.
1854     Hi = DAG.getConstant(0, NVT);
1855     break;
1856   }
1857     // These operators cannot be expanded directly, emit them as calls to
1858     // library functions.
1859   case ISD::FP_TO_SINT:
1860     if (Node->getOperand(0).getValueType() == MVT::f32)
1861       Lo = ExpandLibCall("__fixsfdi", Node, Hi);
1862     else
1863       Lo = ExpandLibCall("__fixdfdi", Node, Hi);
1864     break;
1865   case ISD::FP_TO_UINT:
1866     if (Node->getOperand(0).getValueType() == MVT::f32)
1867       Lo = ExpandLibCall("__fixunssfdi", Node, Hi);
1868     else
1869       Lo = ExpandLibCall("__fixunsdfdi", Node, Hi);
1870     break;
1871
1872   case ISD::SHL:
1873     // If we can emit an efficient shift operation, do so now.
1874     if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
1875       break;
1876
1877     // If this target supports SHL_PARTS, use it.
1878     if (TLI.getOperationAction(ISD::SHL_PARTS, NVT) == TargetLowering::Legal) {
1879       ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), Node->getOperand(1),
1880                        Lo, Hi);
1881       break;
1882     }
1883
1884     // Otherwise, emit a libcall.
1885     Lo = ExpandLibCall("__ashldi3", Node, Hi);
1886     break;
1887
1888   case ISD::SRA:
1889     // If we can emit an efficient shift operation, do so now.
1890     if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
1891       break;
1892
1893     // If this target supports SRA_PARTS, use it.
1894     if (TLI.getOperationAction(ISD::SRA_PARTS, NVT) == TargetLowering::Legal) {
1895       ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), Node->getOperand(1),
1896                        Lo, Hi);
1897       break;
1898     }
1899
1900     // Otherwise, emit a libcall.
1901     Lo = ExpandLibCall("__ashrdi3", Node, Hi);
1902     break;
1903   case ISD::SRL:
1904     // If we can emit an efficient shift operation, do so now.
1905     if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
1906       break;
1907
1908     // If this target supports SRL_PARTS, use it.
1909     if (TLI.getOperationAction(ISD::SRL_PARTS, NVT) == TargetLowering::Legal) {
1910       ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), Node->getOperand(1),
1911                        Lo, Hi);
1912       break;
1913     }
1914
1915     // Otherwise, emit a libcall.
1916     Lo = ExpandLibCall("__lshrdi3", Node, Hi);
1917     break;
1918
1919   case ISD::ADD:
1920     ExpandByParts(ISD::ADD_PARTS, Node->getOperand(0), Node->getOperand(1),
1921                   Lo, Hi);
1922     break;
1923   case ISD::SUB:
1924     ExpandByParts(ISD::SUB_PARTS, Node->getOperand(0), Node->getOperand(1),
1925                   Lo, Hi);
1926     break;
1927   case ISD::MUL:  Lo = ExpandLibCall("__muldi3" , Node, Hi); break;
1928   case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break;
1929   case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break;
1930   case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break;
1931   case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break;
1932   }
1933
1934   // Remember in a map if the values will be reused later.
1935   if (!Node->hasOneUse()) {
1936     bool isNew = ExpandedNodes.insert(std::make_pair(Op,
1937                                             std::make_pair(Lo, Hi))).second;
1938     assert(isNew && "Value already expanded?!?");
1939   }
1940 }
1941
1942
1943 // SelectionDAG::Legalize - This is the entry point for the file.
1944 //
1945 void SelectionDAG::Legalize() {
1946   /// run - This is the main entry point to this class.
1947   ///
1948   SelectionDAGLegalize(*this).Run();
1949 }
1950