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   SDOperand getIntPtrConstant(uint64_t Val) {
 123     return DAG.getConstant(Val, TLI.getPointerTy());
 124   }
 125 };
 126 }
 127
 128
 129 SelectionDAGLegalize::SelectionDAGLegalize(TargetLowering &tli,
 130                                            SelectionDAG &dag)
 131   : TLI(tli), DAG(dag), ValueTypeActions(TLI.getValueTypeActions()) {
 132   assert(MVT::LAST_VALUETYPE <= 16 &&
 133          "Too many value types for ValueTypeActions to hold!");
 134 }
 135
 136 void SelectionDAGLegalize::LegalizeDAG() {
 137   SDOperand OldRoot = DAG.getRoot();
 138   SDOperand NewRoot = LegalizeOp(OldRoot);
 139   DAG.setRoot(NewRoot);
 140
 141   ExpandedNodes.clear();
 142   LegalizedNodes.clear();
 143   PromotedNodes.clear();
 144
 145   // Remove dead nodes now.
 146   DAG.RemoveDeadNodes(OldRoot.Val);
 147 }
 148
 149 SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 150   assert(getTypeAction(Op.getValueType()) == Legal &&
 151          "Caller should expand or promote operands that are not legal!");
 152
 153   // If this operation defines any values that cannot be represented in a
 154   // register on this target, make sure to expand or promote them.
 155   if (Op.Val->getNumValues() > 1) {
 156     for (unsigned i = 0, e = Op.Val->getNumValues(); i != e; ++i)
 157       switch (getTypeAction(Op.Val->getValueType(i))) {
 158       case Legal: break;  // Nothing to do.
 159       case Expand: {
 160         SDOperand T1, T2;
 161         ExpandOp(Op.getValue(i), T1, T2);
 162         assert(LegalizedNodes.count(Op) &&
 163                "Expansion didn't add legal operands!");
 164         return LegalizedNodes[Op];
 165       }
 166       case Promote:
 167         PromoteOp(Op.getValue(i));
 168         assert(LegalizedNodes.count(Op) &&
 169                "Expansion didn't add legal operands!");
 170         return LegalizedNodes[Op];
 171       }
 172   }
 173
 174   std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
 175   if (I != LegalizedNodes.end()) return I->second;
 176
 177   SDOperand Tmp1, Tmp2, Tmp3;
 178
 179   SDOperand Result = Op;
 180   SDNode *Node = Op.Val;
 181
 182   switch (Node->getOpcode()) {
 183   default:
 184     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 185     assert(0 && "Do not know how to legalize this operator!");
 186     abort();
 187   case ISD::EntryToken:
 188   case ISD::FrameIndex:
 189   case ISD::GlobalAddress:
 190   case ISD::ExternalSymbol:
 191   case ISD::ConstantPool:           // Nothing to do.
 192     assert(getTypeAction(Node->getValueType(0)) == Legal &&
 193            "This must be legal!");
 194     break;
 195   case ISD::CopyFromReg:
 196     Tmp1 = LegalizeOp(Node->getOperand(0));
 197     if (Tmp1 != Node->getOperand(0))
 198       Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(),
 199                                   Node->getValueType(0), Tmp1);
 200     break;
 201   case ISD::ImplicitDef:
 202     Tmp1 = LegalizeOp(Node->getOperand(0));
 203     if (Tmp1 != Node->getOperand(0))
 204       Result = DAG.getImplicitDef(Tmp1, cast<RegSDNode>(Node)->getReg());
 205     break;
 206   case ISD::Constant:
 207     // We know we don't need to expand constants here, constants only have one
 208     // value and we check that it is fine above.
 209
 210     // FIXME: Maybe we should handle things like targets that don't support full
 211     // 32-bit immediates?
 212     break;
 213   case ISD::ConstantFP: {
 214     // Spill FP immediates to the constant pool if the target cannot directly
 215     // codegen them.  Targets often have some immediate values that can be
 216     // efficiently generated into an FP register without a load.  We explicitly
 217     // leave these constants as ConstantFP nodes for the target to deal with.
 218
 219     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
 220
 221     // Check to see if this FP immediate is already legal.
 222     bool isLegal = false;
 223     for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
 224            E = TLI.legal_fpimm_end(); I != E; ++I)
 225       if (CFP->isExactlyValue(*I)) {
 226         isLegal = true;
 227         break;
 228       }
 229
 230     if (!isLegal) {
 231       // Otherwise we need to spill the constant to memory.
 232       MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
 233
 234       bool Extend = false;
 235
 236       // If a FP immediate is precise when represented as a float, we put it
 237       // into the constant pool as a float, even if it's is statically typed
 238       // as a double.
 239       MVT::ValueType VT = CFP->getValueType(0);
 240       bool isDouble = VT == MVT::f64;
 241       ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
 242                                              Type::FloatTy, CFP->getValue());
 243       if (isDouble && CFP->isExactlyValue((float)CFP->getValue())) {
 244         LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
 245         VT = MVT::f32;
 246         Extend = true;
 247       }
 248
 249       SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC),
 250                                             TLI.getPointerTy());
 251       Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx);
 252
 253       if (Extend) Result = DAG.getNode(ISD::FP_EXTEND, MVT::f64, Result);
 254     }
 255     break;
 256   }
 257   case ISD::TokenFactor: {
 258     std::vector<SDOperand> Ops;
 259     bool Changed = false;
 260     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
 261       Ops.push_back(LegalizeOp(Node->getOperand(i)));  // Legalize the operands
 262       Changed |= Ops[i] != Node->getOperand(i);
 263     }
 264     if (Changed)
 265       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops);
 266     break;
 267   }
 268
 269   case ISD::ADJCALLSTACKDOWN:
 270   case ISD::ADJCALLSTACKUP:
 271     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 272     // There is no need to legalize the size argument (Operand #1)
 273     if (Tmp1 != Node->getOperand(0))
 274       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1,
 275                            Node->getOperand(1));
 276     break;
 277   case ISD::DYNAMIC_STACKALLOC:
 278     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 279     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
 280     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
 281     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 282         Tmp3 != Node->getOperand(2))
 283       Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0),
 284                            Tmp1, Tmp2, Tmp3);
 285     else
 286       Result = Op.getValue(0);
 287
 288     // Since this op produces two values, make sure to remember that we
 289     // legalized both of them.
 290     AddLegalizedOperand(SDOperand(Node, 0), Result);
 291     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 292     return Result.getValue(Op.ResNo);
 293
 294   case ISD::CALL:
 295     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 296     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
 297     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
 298       std::vector<MVT::ValueType> RetTyVTs;
 299       RetTyVTs.reserve(Node->getNumValues());
 300       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 301         RetTyVTs.push_back(Node->getValueType(i));
 302       Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2), 0);
 303     } else {
 304       Result = Result.getValue(0);
 305     }
 306     // Since calls produce multiple values, make sure to remember that we
 307     // legalized all of them.
 308     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 309       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
 310     return Result.getValue(Op.ResNo);
 311
 312   case ISD::BR:
 313     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 314     if (Tmp1 != Node->getOperand(0))
 315       Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1));
 316     break;
 317
 318   case ISD::BRCOND:
 319     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 320     // FIXME: booleans might not be legal!
 321     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the condition.
 322     // Basic block destination (Op#2) is always legal.
 323     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 324       Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
 325                            Node->getOperand(2));
 326     break;
 327
 328   case ISD::LOAD:
 329     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 330     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 331     if (Tmp1 != Node->getOperand(0) ||
 332         Tmp2 != Node->getOperand(1))
 333       Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2);
 334     else
 335       Result = SDOperand(Node, 0);
 336
 337     // Since loads produce two values, make sure to remember that we legalized
 338     // both of them.
 339     AddLegalizedOperand(SDOperand(Node, 0), Result);
 340     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 341     return Result.getValue(Op.ResNo);
 342
 343   case ISD::EXTLOAD:
 344   case ISD::SEXTLOAD:
 345   case ISD::ZEXTLOAD:
 346     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 347     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 348     if (Tmp1 != Node->getOperand(0) ||
 349         Tmp2 != Node->getOperand(1))
 350       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, Tmp2,
 351                            cast<MVTSDNode>(Node)->getExtraValueType());
 352     else
 353       Result = SDOperand(Node, 0);
 354
 355     // Since loads produce two values, make sure to remember that we legalized
 356     // both of them.
 357     AddLegalizedOperand(SDOperand(Node, 0), Result);
 358     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 359     return Result.getValue(Op.ResNo);
 360
 361   case ISD::EXTRACT_ELEMENT:
 362     // Get both the low and high parts.
 363     ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 364     if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
 365       Result = Tmp2;  // 1 -> Hi
 366     else
 367       Result = Tmp1;  // 0 -> Lo
 368     break;
 369
 370   case ISD::CopyToReg:
 371     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 372
 373     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 374     case Legal:
 375       // Legalize the incoming value (must be legal).
 376       Tmp2 = LegalizeOp(Node->getOperand(1));
 377       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 378         Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
 379       break;
 380     case Expand: {
 381       SDOperand Lo, Hi;
 382       ExpandOp(Node->getOperand(1), Lo, Hi);
 383       unsigned Reg = cast<RegSDNode>(Node)->getReg();
 384       Result = DAG.getCopyToReg(Tmp1, Lo, Reg);
 385       Result = DAG.getCopyToReg(Result, Hi, Reg+1);
 386       assert(isTypeLegal(Result.getValueType()) &&
 387              "Cannot expand multiple times yet (i64 -> i16)");
 388       break;
 389     }
 390     case Promote:
 391       assert(0 && "Don't know what it means to promote this!");
 392       abort();
 393     }
 394     break;
 395
 396   case ISD::RET:
 397     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 398     switch (Node->getNumOperands()) {
 399     case 2:  // ret val
 400       switch (getTypeAction(Node->getOperand(1).getValueType())) {
 401       case Legal:
 402         Tmp2 = LegalizeOp(Node->getOperand(1));
 403         if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 404           Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 405         break;
 406       case Expand: {
 407         SDOperand Lo, Hi;
 408         ExpandOp(Node->getOperand(1), Lo, Hi);
 409         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
 410         break;
 411       }
 412       case Promote:
 413         Tmp2 = PromoteOp(Node->getOperand(1));
 414         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 415         break;
 416       }
 417       break;
 418     case 1:  // ret void
 419       if (Tmp1 != Node->getOperand(0))
 420         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1);
 421       break;
 422     default: { // ret <values>
 423       std::vector<SDOperand> NewValues;
 424       NewValues.push_back(Tmp1);
 425       for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
 426         switch (getTypeAction(Node->getOperand(i).getValueType())) {
 427         case Legal:
 428           NewValues.push_back(LegalizeOp(Node->getOperand(i)));
 429           break;
 430         case Expand: {
 431           SDOperand Lo, Hi;
 432           ExpandOp(Node->getOperand(i), Lo, Hi);
 433           NewValues.push_back(Lo);
 434           NewValues.push_back(Hi);
 435           break;
 436         }
 437         case Promote:
 438           assert(0 && "Can't promote multiple return value yet!");
 439         }
 440       Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
 441       break;
 442     }
 443     }
 444     break;
 445   case ISD::STORE:
 446     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 447     Tmp2 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 448
 449     // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
 450     if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){
 451       if (CFP->getValueType(0) == MVT::f32) {
 452         union {
 453           unsigned I;
 454           float    F;
 455         } V;
 456         V.F = CFP->getValue();
 457         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 458                              DAG.getConstant(V.I, MVT::i32), Tmp2);
 459       } else {
 460         assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
 461         union {
 462           uint64_t I;
 463           double   F;
 464         } V;
 465         V.F = CFP->getValue();
 466         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 467                              DAG.getConstant(V.I, MVT::i64), Tmp2);
 468       }
 469       Op = Result;
 470       Node = Op.Val;
 471     }
 472
 473     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 474     case Legal: {
 475       SDOperand Val = LegalizeOp(Node->getOperand(1));
 476       if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) ||
 477           Tmp2 != Node->getOperand(2))
 478         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2);
 479       break;
 480     }
 481     case Promote:
 482       // Truncate the value and store the result.
 483       Tmp3 = PromoteOp(Node->getOperand(1));
 484       Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2,
 485                            Node->getOperand(1).getValueType());
 486       break;
 487
 488     case Expand:
 489       SDOperand Lo, Hi;
 490       ExpandOp(Node->getOperand(1), Lo, Hi);
 491
 492       if (!TLI.isLittleEndian())
 493         std::swap(Lo, Hi);
 494
 495       // FIXME: These two stores are independent of each other!
 496       Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2);
 497
 498       unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
 499       Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
 500                          getIntPtrConstant(IncrementSize));
 501       assert(isTypeLegal(Tmp2.getValueType()) &&
 502              "Pointers must be legal!");
 503       Result = DAG.getNode(ISD::STORE, MVT::Other, Result, Hi, Tmp2);
 504     }
 505     break;
 506   case ISD::TRUNCSTORE:
 507     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 508     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 509
 510     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 511     case Legal:
 512       Tmp2 = LegalizeOp(Node->getOperand(1));
 513       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 514           Tmp3 != Node->getOperand(2))
 515         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3,
 516                              cast<MVTSDNode>(Node)->getExtraValueType());
 517       break;
 518     case Promote:
 519     case Expand:
 520       assert(0 && "Cannot handle illegal TRUNCSTORE yet!");
 521     }
 522     break;
 523   case ISD::SELECT:
 524     // FIXME: BOOLS MAY REQUIRE PROMOTION!
 525     Tmp1 = LegalizeOp(Node->getOperand(0));   // Cond
 526     Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
 527     Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
 528
 529     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 530         Tmp3 != Node->getOperand(2))
 531       Result = DAG.getNode(ISD::SELECT, Node->getValueType(0), Tmp1, Tmp2,Tmp3);
 532     break;
 533   case ISD::SETCC:
 534     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 535     case Legal:
 536       Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 537       Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 538       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 539         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 540                               Tmp1, Tmp2);
 541       break;
 542     case Promote:
 543       Tmp1 = PromoteOp(Node->getOperand(0));   // LHS
 544       Tmp2 = PromoteOp(Node->getOperand(1));   // RHS
 545
 546       // If this is an FP compare, the operands have already been extended.
 547       if (MVT::isInteger(Node->getOperand(0).getValueType())) {
 548         MVT::ValueType VT = Node->getOperand(0).getValueType();
 549         MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 550
 551         // Otherwise, we have to insert explicit sign or zero extends.  Note
 552         // that we could insert sign extends for ALL conditions, but zero extend
 553         // is cheaper on many machines (an AND instead of two shifts), so prefer
 554         // it.
 555         switch (cast<SetCCSDNode>(Node)->getCondition()) {
 556         default: assert(0 && "Unknown integer comparison!");
 557         case ISD::SETEQ:
 558         case ISD::SETNE:
 559         case ISD::SETUGE:
 560         case ISD::SETUGT:
 561         case ISD::SETULE:
 562         case ISD::SETULT:
 563           // ALL of these operations will work if we either sign or zero extend
 564           // the operands (including the unsigned comparisons!).  Zero extend is
 565           // usually a simpler/cheaper operation, so prefer it.
 566           Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
 567           Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT);
 568           break;
 569         case ISD::SETGE:
 570         case ISD::SETGT:
 571         case ISD::SETLT:
 572         case ISD::SETLE:
 573           Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
 574           Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT);
 575           break;
 576         }
 577
 578       }
 579       Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 580                             Tmp1, Tmp2);
 581       break;
 582     case Expand:
 583       SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
 584       ExpandOp(Node->getOperand(0), LHSLo, LHSHi);
 585       ExpandOp(Node->getOperand(1), RHSLo, RHSHi);
 586       switch (cast<SetCCSDNode>(Node)->getCondition()) {
 587       case ISD::SETEQ:
 588       case ISD::SETNE:
 589         Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
 590         Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
 591         Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
 592         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), Tmp1,
 593                               DAG.getConstant(0, Tmp1.getValueType()));
 594         break;
 595       default:
 596         // FIXME: This generated code sucks.
 597         ISD::CondCode LowCC;
 598         switch (cast<SetCCSDNode>(Node)->getCondition()) {
 599         default: assert(0 && "Unknown integer setcc!");
 600         case ISD::SETLT:
 601         case ISD::SETULT: LowCC = ISD::SETULT; break;
 602         case ISD::SETGT:
 603         case ISD::SETUGT: LowCC = ISD::SETUGT; break;
 604         case ISD::SETLE:
 605         case ISD::SETULE: LowCC = ISD::SETULE; break;
 606         case ISD::SETGE:
 607         case ISD::SETUGE: LowCC = ISD::SETUGE; break;
 608         }
 609
 610         // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
 611         // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
 612         // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
 613
 614         // NOTE: on targets without efficient SELECT of bools, we can always use
 615         // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
 616         Tmp1 = DAG.getSetCC(LowCC, LHSLo, RHSLo);
 617         Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 618                             LHSHi, RHSHi);
 619         Result = DAG.getSetCC(ISD::SETEQ, LHSHi, RHSHi);
 620         Result = DAG.getNode(ISD::SELECT, MVT::i1, Result, Tmp1, Tmp2);
 621         break;
 622       }
 623     }
 624     break;
 625
 626   case ISD::MEMSET:
 627   case ISD::MEMCPY:
 628   case ISD::MEMMOVE: {
 629     Tmp1 = LegalizeOp(Node->getOperand(0));
 630     Tmp2 = LegalizeOp(Node->getOperand(1));
 631     Tmp3 = LegalizeOp(Node->getOperand(2));
 632     SDOperand Tmp4 = LegalizeOp(Node->getOperand(3));
 633     SDOperand Tmp5 = LegalizeOp(Node->getOperand(4));
 634     if (TLI.isOperationSupported(Node->getOpcode(), MVT::Other)) {
 635       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 636           Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) ||
 637           Tmp5 != Node->getOperand(4)) {
 638         std::vector<SDOperand> Ops;
 639         Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
 640         Ops.push_back(Tmp4); Ops.push_back(Tmp5);
 641         Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
 642       }
 643     } else {
 644       // Otherwise, the target does not support this operation.  Lower the
 645       // operation to an explicit libcall as appropriate.
 646       MVT::ValueType IntPtr = TLI.getPointerTy();
 647       const Type *IntPtrTy = TLI.getTargetData().getIntPtrType();
 648       std::vector<std::pair<SDOperand, const Type*> > Args;
 649
 650       const char *FnName = 0;
 651       if (Node->getOpcode() == ISD::MEMSET) {
 652         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
 653         // Extend the ubyte argument to be an int value for the call.
 654         Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
 655         Args.push_back(std::make_pair(Tmp3, Type::IntTy));
 656         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
 657
 658         FnName = "memset";
 659       } else if (Node->getOpcode() == ISD::MEMCPY ||
 660                  Node->getOpcode() == ISD::MEMMOVE) {
 661         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
 662         Args.push_back(std::make_pair(Tmp3, IntPtrTy));
 663         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
 664         FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
 665       } else {
 666         assert(0 && "Unknown op!");
 667       }
 668       std::pair<SDOperand,SDOperand> CallResult =
 669         TLI.LowerCallTo(Tmp1, Type::VoidTy,
 670                         DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
 671       Result = LegalizeOp(CallResult.second);
 672     }
 673     break;
 674   }
 675   case ISD::ADD:
 676   case ISD::SUB:
 677   case ISD::MUL:
 678   case ISD::UDIV:
 679   case ISD::SDIV:
 680   case ISD::UREM:
 681   case ISD::SREM:
 682   case ISD::AND:
 683   case ISD::OR:
 684   case ISD::XOR:
 685   case ISD::SHL:
 686   case ISD::SRL:
 687   case ISD::SRA:
 688     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 689     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 690     if (Tmp1 != Node->getOperand(0) ||
 691         Tmp2 != Node->getOperand(1))
 692       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2);
 693     break;
 694   case ISD::ZERO_EXTEND:
 695   case ISD::SIGN_EXTEND:
 696   case ISD::TRUNCATE:
 697   case ISD::FP_EXTEND:
 698   case ISD::FP_ROUND:
 699   case ISD::FP_TO_SINT:
 700   case ISD::FP_TO_UINT:
 701   case ISD::SINT_TO_FP:
 702   case ISD::UINT_TO_FP:
 703     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 704     case Legal:
 705       Tmp1 = LegalizeOp(Node->getOperand(0));
 706       if (Tmp1 != Node->getOperand(0))
 707         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
 708       break;
 709     case Expand:
 710       assert(Node->getOpcode() != ISD::SINT_TO_FP &&
 711              Node->getOpcode() != ISD::UINT_TO_FP &&
 712              "Cannot lower Xint_to_fp to a call yet!");
 713
 714       // In the expand case, we must be dealing with a truncate, because
 715       // otherwise the result would be larger than the source.
 716       assert(Node->getOpcode() == ISD::TRUNCATE &&
 717              "Shouldn't need to expand other operators here!");
 718       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 719
 720       // Since the result is legal, we should just be able to truncate the low
 721       // part of the source.
 722       Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
 723       break;
 724
 725     case Promote:
 726       switch (Node->getOpcode()) {
 727       case ISD::ZERO_EXTEND:
 728         Result = PromoteOp(Node->getOperand(0));
 729         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(),
 730                              Result, Node->getOperand(0).getValueType());
 731         break;
 732       case ISD::SIGN_EXTEND:
 733         Result = PromoteOp(Node->getOperand(0));
 734         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
 735                              Result, Node->getOperand(0).getValueType());
 736         break;
 737       case ISD::TRUNCATE:
 738         Result = PromoteOp(Node->getOperand(0));
 739         Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
 740         break;
 741       case ISD::FP_EXTEND:
 742         Result = PromoteOp(Node->getOperand(0));
 743         if (Result.getValueType() != Op.getValueType())
 744           // Dynamically dead while we have only 2 FP types.
 745           Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
 746         break;
 747       case ISD::FP_ROUND:
 748         Result = PromoteOp(Node->getOperand(0));
 749         Result = DAG.getNode(ISD::FP_ROUND, Op.getValueType(), Result);
 750         break;
 751       case ISD::FP_TO_SINT:
 752       case ISD::FP_TO_UINT:
 753       case ISD::SINT_TO_FP:
 754       case ISD::UINT_TO_FP:
 755         Node->dump();
 756         assert(0 && "Do not know how to promote this yet!");
 757       }
 758     }
 759     break;
 760   case ISD::FP_ROUND_INREG:
 761   case ISD::SIGN_EXTEND_INREG:
 762   case ISD::ZERO_EXTEND_INREG: {
 763     Tmp1 = LegalizeOp(Node->getOperand(0));
 764     MVT::ValueType ExtraVT = cast<MVTSDNode>(Node)->getExtraValueType();
 765
 766     // If this operation is not supported, convert it to a shl/shr or load/store
 767     // pair.
 768     if (!TLI.isOperationSupported(Node->getOpcode(), ExtraVT)) {
 769       // If this is an integer extend and shifts are supported, do that.
 770       if (Node->getOpcode() == ISD::ZERO_EXTEND_INREG) {
 771         // NOTE: we could fall back on load/store here too for targets without
 772         // AND.  However, it is doubtful that any exist.
 773         // AND out the appropriate bits.
 774         SDOperand Mask =
 775           DAG.getConstant((1ULL << MVT::getSizeInBits(ExtraVT))-1,
 776                           Node->getValueType(0));
 777         Result = DAG.getNode(ISD::AND, Node->getValueType(0),
 778                              Node->getOperand(0), Mask);
 779       } else if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
 780         // NOTE: we could fall back on load/store here too for targets without
 781         // SAR.  However, it is doubtful that any exist.
 782         unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
 783                             MVT::getSizeInBits(ExtraVT);
 784         SDOperand ShiftCst = DAG.getConstant(BitsDiff, MVT::i8);
 785         Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
 786                              Node->getOperand(0), ShiftCst);
 787         Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
 788                              Result, ShiftCst);
 789       } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
 790         // The only way we can lower this is to turn it into a STORETRUNC,
 791         // EXTLOAD pair, targetting a temporary location (a stack slot).
 792
 793         // NOTE: there is a choice here between constantly creating new stack
 794         // slots and always reusing the same one.  We currently always create
 795         // new ones, as reuse may inhibit scheduling.
 796         const Type *Ty = MVT::getTypeForValueType(ExtraVT);
 797         unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty);
 798         unsigned Align  = TLI.getTargetData().getTypeAlignment(Ty);
 799         MachineFunction &MF = DAG.getMachineFunction();
 800         int SSFI =
 801           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
 802         SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
 803         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
 804                              Node->getOperand(0), StackSlot, ExtraVT);
 805         Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0),
 806                              Result, StackSlot, ExtraVT);
 807       } else {
 808         assert(0 && "Unknown op");
 809       }
 810       Result = LegalizeOp(Result);
 811     } else {
 812       if (Tmp1 != Node->getOperand(0))
 813         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
 814                              ExtraVT);
 815     }
 816     break;
 817   }
 818   }
 819
 820   if (!Op.Val->hasOneUse())
 821     AddLegalizedOperand(Op, Result);
 822
 823   return Result;
 824 }
 825
 826 /// PromoteOp - Given an operation that produces a value in an invalid type,
 827 /// promote it to compute the value into a larger type.  The produced value will
 828 /// have the correct bits for the low portion of the register, but no guarantee
 829 /// is made about the top bits: it may be zero, sign-extended, or garbage.
 830 SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
 831   MVT::ValueType VT = Op.getValueType();
 832   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 833   assert(getTypeAction(VT) == Promote &&
 834          "Caller should expand or legalize operands that are not promotable!");
 835   assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
 836          "Cannot promote to smaller type!");
 837
 838   std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
 839   if (I != PromotedNodes.end()) return I->second;
 840
 841   SDOperand Tmp1, Tmp2, Tmp3;
 842
 843   SDOperand Result;
 844   SDNode *Node = Op.Val;
 845
 846   // Promotion needs an optimization step to clean up after it, and is not
 847   // careful to avoid operations the target does not support.  Make sure that
 848   // all generated operations are legalized in the next iteration.
 849   NeedsAnotherIteration = true;
 850
 851   switch (Node->getOpcode()) {
 852   default:
 853     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 854     assert(0 && "Do not know how to promote this operator!");
 855     abort();
 856   case ISD::CALL:
 857     assert(0 && "Target's LowerCallTo implementation is buggy, returning value"
 858            " types that are not supported by the target!");
 859   case ISD::Constant:
 860     Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
 861     assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
 862     break;
 863   case ISD::ConstantFP:
 864     Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
 865     assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
 866     break;
 867
 868   case ISD::TRUNCATE:
 869     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 870     case Legal:
 871       Result = LegalizeOp(Node->getOperand(0));
 872       assert(Result.getValueType() >= NVT &&
 873              "This truncation doesn't make sense!");
 874       if (Result.getValueType() > NVT)    // Truncate to NVT instead of VT
 875         Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
 876       break;
 877     case Expand:
 878       assert(0 && "Cannot handle expand yet");
 879     case Promote:
 880       assert(0 && "Cannot handle promote-promote yet");
 881     }
 882     break;
 883   case ISD::SIGN_EXTEND:
 884   case ISD::ZERO_EXTEND:
 885     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 886     case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
 887     case Legal:
 888       // Input is legal?  Just do extend all the way to the larger type.
 889       Result = LegalizeOp(Node->getOperand(0));
 890       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
 891       break;
 892     case Promote:
 893       // Promote the reg if it's smaller.
 894       Result = PromoteOp(Node->getOperand(0));
 895       // The high bits are not guaranteed to be anything.  Insert an extend.
 896       if (Node->getOpcode() == ISD::SIGN_EXTEND)
 897         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result, VT);
 898       else
 899         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Result, VT);
 900       break;
 901     }
 902     break;
 903
 904   case ISD::FP_EXTEND:
 905     assert(0 && "Case not implemented.  Dynamically dead with 2 FP types!");
 906   case ISD::FP_ROUND:
 907     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 908     case Expand: assert(0 && "BUG: Cannot expand FP regs!");
 909     case Promote:  assert(0 && "Unreachable with 2 FP types!");
 910     case Legal:
 911       // Input is legal?  Do an FP_ROUND_INREG.
 912       Result = LegalizeOp(Node->getOperand(0));
 913       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
 914       break;
 915     }
 916     break;
 917
 918   case ISD::SINT_TO_FP:
 919   case ISD::UINT_TO_FP:
 920     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 921     case Legal:
 922       Result = LegalizeOp(Node->getOperand(0));
 923       break;
 924
 925     case Promote:
 926       Result = PromoteOp(Node->getOperand(0));
 927       if (Node->getOpcode() == ISD::SINT_TO_FP)
 928         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
 929                              Result, Node->getOperand(0).getValueType());
 930       else
 931         Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(),
 932                              Result, Node->getOperand(0).getValueType());
 933       break;
 934     case Expand:
 935       assert(0 && "Unimplemented");
 936     }
 937     // No extra round required here.
 938     Result = DAG.getNode(Node->getOpcode(), NVT, Result);
 939     break;
 940
 941   case ISD::FP_TO_SINT:
 942   case ISD::FP_TO_UINT:
 943     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 944     case Legal:
 945       Tmp1 = LegalizeOp(Node->getOperand(0));
 946       break;
 947     case Promote:
 948       // The input result is prerounded, so we don't have to do anything
 949       // special.
 950       Tmp1 = PromoteOp(Node->getOperand(0));
 951       break;
 952     case Expand:
 953       assert(0 && "not implemented");
 954     }
 955     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
 956     break;
 957
 958   case ISD::AND:
 959   case ISD::OR:
 960   case ISD::XOR:
 961   case ISD::ADD:
 962   case ISD::SUB:
 963   case ISD::MUL:
 964     // The input may have strange things in the top bits of the registers, but
 965     // these operations don't care.  They may have wierd bits going out, but
 966     // that too is okay if they are integer operations.
 967     Tmp1 = PromoteOp(Node->getOperand(0));
 968     Tmp2 = PromoteOp(Node->getOperand(1));
 969     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
 970     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
 971
 972     // However, if this is a floating point operation, they will give excess
 973     // precision that we may not be able to tolerate.  If we DO allow excess
 974     // precision, just leave it, otherwise excise it.
 975     // FIXME: Why would we need to round FP ops more than integer ones?
 976     //     Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
 977     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
 978       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
 979     break;
 980
 981   case ISD::SDIV:
 982   case ISD::SREM:
 983     // These operators require that their input be sign extended.
 984     Tmp1 = PromoteOp(Node->getOperand(0));
 985     Tmp2 = PromoteOp(Node->getOperand(1));
 986     if (MVT::isInteger(NVT)) {
 987       Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
 988       Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT);
 989     }
 990     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
 991
 992     // Perform FP_ROUND: this is probably overly pessimistic.
 993     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
 994       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
 995     break;
 996
 997   case ISD::UDIV:
 998   case ISD::UREM:
 999     // These operators require that their input be zero extended.
1000     Tmp1 = PromoteOp(Node->getOperand(0));
1001     Tmp2 = PromoteOp(Node->getOperand(1));
1002     assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
1003     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
1004     Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT);
1005     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1006     break;
1007
1008   case ISD::SHL:
1009     Tmp1 = PromoteOp(Node->getOperand(0));
1010     Tmp2 = LegalizeOp(Node->getOperand(1));
1011     Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2);
1012     break;
1013   case ISD::SRA:
1014     // The input value must be properly sign extended.
1015     Tmp1 = PromoteOp(Node->getOperand(0));
1016     Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
1017     Tmp2 = LegalizeOp(Node->getOperand(1));
1018     Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2);
1019     break;
1020   case ISD::SRL:
1021     // The input value must be properly zero extended.
1022     Tmp1 = PromoteOp(Node->getOperand(0));
1023     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
1024     Tmp2 = LegalizeOp(Node->getOperand(1));
1025     Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2);
1026     break;
1027   case ISD::LOAD:
1028     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
1029     Tmp2 = LegalizeOp(Node->getOperand(1));   // Legalize the pointer.
1030     Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, VT);
1031
1032     // Remember that we legalized the chain.
1033     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1034     break;
1035   case ISD::SELECT:
1036     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the condition
1037     Tmp2 = PromoteOp(Node->getOperand(1));   // Legalize the op0
1038     Tmp3 = PromoteOp(Node->getOperand(2));   // Legalize the op1
1039     Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3);
1040     break;
1041   }
1042
1043   assert(Result.Val && "Didn't set a result!");
1044   AddPromotedOperand(Op, Result);
1045   return Result;
1046 }
1047
1048 /// ExpandOp - Expand the specified SDOperand into its two component pieces
1049 /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
1050 /// LegalizeNodes map is filled in for any results that are not expanded, the
1051 /// ExpandedNodes map is filled in for any results that are expanded, and the
1052 /// Lo/Hi values are returned.
1053 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
1054   MVT::ValueType VT = Op.getValueType();
1055   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1056   SDNode *Node = Op.Val;
1057   assert(getTypeAction(VT) == Expand && "Not an expanded type!");
1058   assert(MVT::isInteger(VT) && "Cannot expand FP values!");
1059   assert(MVT::isInteger(NVT) && NVT < VT &&
1060          "Cannot expand to FP value or to larger int value!");
1061
1062   // If there is more than one use of this, see if we already expanded it.
1063   // There is no use remembering values that only have a single use, as the map
1064   // entries will never be reused.
1065   if (!Node->hasOneUse()) {
1066     std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
1067       = ExpandedNodes.find(Op);
1068     if (I != ExpandedNodes.end()) {
1069       Lo = I->second.first;
1070       Hi = I->second.second;
1071       return;
1072     }
1073   }
1074
1075   // Expanding to multiple registers needs to perform an optimization step, and
1076   // is not careful to avoid operations the target does not support.  Make sure
1077   // that all generated operations are legalized in the next iteration.
1078   NeedsAnotherIteration = true;
1079   const char *LibCallName = 0;
1080
1081   switch (Node->getOpcode()) {
1082   default:
1083     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
1084     assert(0 && "Do not know how to expand this operator!");
1085     abort();
1086   case ISD::Constant: {
1087     uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
1088     Lo = DAG.getConstant(Cst, NVT);
1089     Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
1090     break;
1091   }
1092
1093   case ISD::CopyFromReg: {
1094     unsigned Reg = cast<RegSDNode>(Node)->getReg();
1095     // Aggregate register values are always in consequtive pairs.
1096     Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0));
1097     Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1));
1098
1099     // Remember that we legalized the chain.
1100     AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
1101
1102     assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
1103     break;
1104   }
1105
1106   case ISD::LOAD: {
1107     SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
1108     SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1109     Lo = DAG.getLoad(NVT, Ch, Ptr);
1110
1111     // Increment the pointer to the other half.
1112     unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
1113     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1114                       getIntPtrConstant(IncrementSize));
1115     // FIXME: This load is independent of the first one.
1116     Hi = DAG.getLoad(NVT, Lo.getValue(1), Ptr);
1117
1118     // Remember that we legalized the chain.
1119     AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
1120     if (!TLI.isLittleEndian())
1121       std::swap(Lo, Hi);
1122     break;
1123   }
1124   case ISD::CALL: {
1125     SDOperand Chain  = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1126     SDOperand Callee = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
1127
1128     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
1129            "Can only expand a call once so far, not i64 -> i16!");
1130
1131     std::vector<MVT::ValueType> RetTyVTs;
1132     RetTyVTs.reserve(3);
1133     RetTyVTs.push_back(NVT);
1134     RetTyVTs.push_back(NVT);
1135     RetTyVTs.push_back(MVT::Other);
1136     SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee);
1137     Lo = SDOperand(NC, 0);
1138     Hi = SDOperand(NC, 1);
1139
1140     // Insert the new chain mapping.
1141     AddLegalizedOperand(Op.getValue(1), Hi.getValue(2));
1142     break;
1143   }
1144   case ISD::AND:
1145   case ISD::OR:
1146   case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
1147     SDOperand LL, LH, RL, RH;
1148     ExpandOp(Node->getOperand(0), LL, LH);
1149     ExpandOp(Node->getOperand(1), RL, RH);
1150     Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
1151     Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
1152     break;
1153   }
1154   case ISD::SELECT: {
1155     SDOperand C, LL, LH, RL, RH;
1156     // FIXME: BOOLS MAY REQUIRE PROMOTION!
1157     C = LegalizeOp(Node->getOperand(0));
1158     ExpandOp(Node->getOperand(1), LL, LH);
1159     ExpandOp(Node->getOperand(2), RL, RH);
1160     Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL);
1161     Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH);
1162     break;
1163   }
1164   case ISD::SIGN_EXTEND: {
1165     // The low part is just a sign extension of the input (which degenerates to
1166     // a copy).
1167     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
1168
1169     // The high part is obtained by SRA'ing all but one of the bits of the lo
1170     // part.
1171     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
1172     Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, MVT::i8));
1173     break;
1174   }
1175   case ISD::ZERO_EXTEND:
1176     // The low part is just a zero extension of the input (which degenerates to
1177     // a copy).
1178     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
1179
1180     // The high part is just a zero.
1181     Hi = DAG.getConstant(0, NVT);
1182     break;
1183
1184     // These operators cannot be expanded directly, emit them as calls to
1185     // library functions.
1186   case ISD::FP_TO_SINT:
1187     if (Node->getOperand(0).getValueType() == MVT::f32)
1188       LibCallName = "__fixsfdi";
1189     else
1190       LibCallName = "__fixdfdi";
1191     break;
1192   case ISD::FP_TO_UINT:
1193     if (Node->getOperand(0).getValueType() == MVT::f32)
1194       LibCallName = "__fixunssfdi";
1195     else
1196       LibCallName = "__fixunsdfdi";
1197     break;
1198
1199   case ISD::ADD:  LibCallName = "__adddi3"; break;
1200   case ISD::SUB:  LibCallName = "__subdi3"; break;
1201   case ISD::MUL:  LibCallName = "__muldi3"; break;
1202   case ISD::SDIV: LibCallName = "__divdi3"; break;
1203   case ISD::UDIV: LibCallName = "__udivdi3"; break;
1204   case ISD::SREM: LibCallName = "__moddi3"; break;
1205   case ISD::UREM: LibCallName = "__umoddi3"; break;
1206   case ISD::SHL:  LibCallName = "__ashldi3"; break;
1207   case ISD::SRA:  LibCallName = "__ashrdi3"; break;
1208   case ISD::SRL:  LibCallName = "__lshrdi3"; break;
1209   }
1210
1211   // Int2FP -> __floatdisf/__floatdidf
1212
1213   // If this is to be expanded into a libcall... do so now.
1214   if (LibCallName) {
1215     TargetLowering::ArgListTy Args;
1216     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1217       Args.push_back(std::make_pair(Node->getOperand(i),
1218                  MVT::getTypeForValueType(Node->getOperand(i).getValueType())));
1219     SDOperand Callee = DAG.getExternalSymbol(LibCallName, TLI.getPointerTy());
1220
1221     // We don't care about token chains for libcalls.  We just use the entry
1222     // node as our input and ignore the output chain.  This allows us to place
1223     // calls wherever we need them to satisfy data dependences.
1224     SDOperand Result = TLI.LowerCallTo(DAG.getEntryNode(),
1225                            MVT::getTypeForValueType(Op.getValueType()), Callee,
1226                                        Args, DAG).first;
1227     ExpandOp(Result, Lo, Hi);
1228   }
1229
1230   // Remember in a map if the values will be reused later.
1231   if (!Node->hasOneUse()) {
1232     bool isNew = ExpandedNodes.insert(std::make_pair(Op,
1233                                             std::make_pair(Lo, Hi))).second;
1234     assert(isNew && "Value already expanded?!?");
1235   }
1236 }
1237
1238
1239 // SelectionDAG::Legalize - This is the entry point for the file.
1240 //
1241 void SelectionDAG::Legalize(TargetLowering &TLI) {
1242   /// run - This is the main entry point to this class.
1243   ///
1244   SelectionDAGLegalize(TLI, *this).Run();
1245 }
1246