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/Target/TargetLowering.h"
  18 #include "llvm/Constants.h"
  19 #include <iostream>
  20 using namespace llvm;
  21
  22 static const Type *getTypeFor(MVT::ValueType VT) {
  23   switch (VT) {
  24   default: assert(0 && "Unknown MVT!");
  25   case MVT::i1: return Type::BoolTy;
  26   case MVT::i8: return Type::UByteTy;
  27   case MVT::i16: return Type::UShortTy;
  28   case MVT::i32: return Type::UIntTy;
  29   case MVT::i64: return Type::ULongTy;
  30   case MVT::f32: return Type::FloatTy;
  31   case MVT::f64: return Type::DoubleTy;
  32   }
  33 }
  34
  35
  36 //===----------------------------------------------------------------------===//
  37 /// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and
  38 /// hacks on it until the target machine can handle it.  This involves
  39 /// eliminating value sizes the machine cannot handle (promoting small sizes to
  40 /// large sizes or splitting up large values into small values) as well as
  41 /// eliminating operations the machine cannot handle.
  42 ///
  43 /// This code also does a small amount of optimization and recognition of idioms
  44 /// as part of its processing.  For example, if a target does not support a
  45 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
  46 /// will attempt merge setcc and brc instructions into brcc's.
  47 ///
  48 namespace {
  49 class SelectionDAGLegalize {
  50   TargetLowering &TLI;
  51   SelectionDAG &DAG;
  52
  53   /// LegalizeAction - This enum indicates what action we should take for each
  54   /// value type the can occur in the program.
  55   enum LegalizeAction {
  56     Legal,            // The target natively supports this value type.
  57     Promote,          // This should be promoted to the next larger type.
  58     Expand,           // This integer type should be broken into smaller pieces.
  59   };
  60
  61   /// TransformToType - For any value types we are promoting or expanding, this
  62   /// contains the value type that we are changing to.  For Expanded types, this
  63   /// contains one step of the expand (e.g. i64 -> i32), even if there are
  64   /// multiple steps required (e.g. i64 -> i16)
  65   MVT::ValueType TransformToType[MVT::LAST_VALUETYPE];
  66
  67   /// ValueTypeActions - This is a bitvector that contains two bits for each
  68   /// value type, where the two bits correspond to the LegalizeAction enum.
  69   /// This can be queried with "getTypeAction(VT)".
  70   unsigned ValueTypeActions;
  71
  72   /// NeedsAnotherIteration - This is set when we expand a large integer
  73   /// operation into smaller integer operations, but the smaller operations are
  74   /// not set.  This occurs only rarely in practice, for targets that don't have
  75   /// 32-bit or larger integer registers.
  76   bool NeedsAnotherIteration;
  77
  78   /// LegalizedNodes - For nodes that are of legal width, and that have more
  79   /// than one use, this map indicates what regularized operand to use.  This
  80   /// allows us to avoid legalizing the same thing more than once.
  81   std::map<SDOperand, SDOperand> LegalizedNodes;
  82
  83   /// ExpandedNodes - For nodes that need to be expanded, and which have more
  84   /// than one use, this map indicates which which operands are the expanded
  85   /// version of the input.  This allows us to avoid expanding the same node
  86   /// more than once.
  87   std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
  88
  89   void AddLegalizedOperand(SDOperand From, SDOperand To) {
  90     bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second;
  91     assert(isNew && "Got into the map somehow?");
  92   }
  93
  94   /// setValueTypeAction - Set the action for a particular value type.  This
  95   /// assumes an action has not already been set for this value type.
  96   void setValueTypeAction(MVT::ValueType VT, LegalizeAction A) {
  97     ValueTypeActions |= A << (VT*2);
  98     if (A == Promote) {
  99       MVT::ValueType PromoteTo;
 100       if (VT == MVT::f32)
 101         PromoteTo = MVT::f64;
 102       else {
 103         unsigned LargerReg = VT+1;
 104         while (!TLI.hasNativeSupportFor((MVT::ValueType)LargerReg)) {
 105           ++LargerReg;
 106           assert(MVT::isInteger((MVT::ValueType)LargerReg) &&
 107                  "Nothing to promote to??");
 108         }
 109         PromoteTo = (MVT::ValueType)LargerReg;
 110       }
 111
 112       assert(MVT::isInteger(VT) == MVT::isInteger(PromoteTo) &&
 113              MVT::isFloatingPoint(VT) == MVT::isFloatingPoint(PromoteTo) &&
 114              "Can only promote from int->int or fp->fp!");
 115       assert(VT < PromoteTo && "Must promote to a larger type!");
 116       TransformToType[VT] = PromoteTo;
 117     } else if (A == Expand) {
 118       assert(MVT::isInteger(VT) && VT > MVT::i8 &&
 119              "Cannot expand this type: target must support SOME integer reg!");
 120       // Expand to the next smaller integer type!
 121       TransformToType[VT] = (MVT::ValueType)(VT-1);
 122     }
 123   }
 124
 125 public:
 126
 127   SelectionDAGLegalize(TargetLowering &TLI, SelectionDAG &DAG);
 128
 129   /// Run - While there is still lowering to do, perform a pass over the DAG.
 130   /// Most regularization can be done in a single pass, but targets that require
 131   /// large values to be split into registers multiple times (e.g. i64 -> 4x
 132   /// i16) require iteration for these values (the first iteration will demote
 133   /// to i32, the second will demote to i16).
 134   void Run() {
 135     do {
 136       NeedsAnotherIteration = false;
 137       LegalizeDAG();
 138     } while (NeedsAnotherIteration);
 139   }
 140
 141   /// getTypeAction - Return how we should legalize values of this type, either
 142   /// it is already legal or we need to expand it into multiple registers of
 143   /// smaller integer type, or we need to promote it to a larger type.
 144   LegalizeAction getTypeAction(MVT::ValueType VT) const {
 145     return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3);
 146   }
 147
 148   /// isTypeLegal - Return true if this type is legal on this target.
 149   ///
 150   bool isTypeLegal(MVT::ValueType VT) const {
 151     return getTypeAction(VT) == Legal;
 152   }
 153
 154 private:
 155   void LegalizeDAG();
 156
 157   SDOperand LegalizeOp(SDOperand O);
 158   void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
 159
 160   SDOperand getIntPtrConstant(uint64_t Val) {
 161     return DAG.getConstant(Val, TLI.getPointerTy());
 162   }
 163 };
 164 }
 165
 166
 167 SelectionDAGLegalize::SelectionDAGLegalize(TargetLowering &tli,
 168                                            SelectionDAG &dag)
 169   : TLI(tli), DAG(dag), ValueTypeActions(0) {
 170
 171   assert(MVT::LAST_VALUETYPE <= 16 &&
 172          "Too many value types for ValueTypeActions to hold!");
 173
 174   // Inspect all of the ValueType's possible, deciding how to process them.
 175   for (unsigned IntReg = MVT::i1; IntReg <= MVT::i128; ++IntReg)
 176     // If TLI says we are expanding this type, expand it!
 177     if (TLI.getNumElements((MVT::ValueType)IntReg) != 1)
 178       setValueTypeAction((MVT::ValueType)IntReg, Expand);
 179     else if (!TLI.hasNativeSupportFor((MVT::ValueType)IntReg))
 180       // Otherwise, if we don't have native support, we must promote to a
 181       // larger type.
 182       setValueTypeAction((MVT::ValueType)IntReg, Promote);
 183
 184   // If the target does not have native support for F32, promote it to F64.
 185   if (!TLI.hasNativeSupportFor(MVT::f32))
 186     setValueTypeAction(MVT::f32, Promote);
 187 }
 188
 189 void SelectionDAGLegalize::LegalizeDAG() {
 190   SDOperand OldRoot = DAG.getRoot();
 191   SDOperand NewRoot = LegalizeOp(OldRoot);
 192   DAG.setRoot(NewRoot);
 193
 194   ExpandedNodes.clear();
 195   LegalizedNodes.clear();
 196
 197   // Remove dead nodes now.
 198   DAG.RemoveDeadNodes(OldRoot.Val);
 199 }
 200
 201 SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 202   assert(getTypeAction(Op.getValueType()) == Legal &&
 203          "Caller should expand or promote operands that are not legal!");
 204
 205   // If this operation defines any values that cannot be represented in a
 206   // register on this target, make sure to expand or promote them.
 207   if (Op.Val->getNumValues() > 1) {
 208     for (unsigned i = 0, e = Op.Val->getNumValues(); i != e; ++i)
 209       switch (getTypeAction(Op.Val->getValueType(i))) {
 210       case Legal: break;  // Nothing to do.
 211       case Expand: {
 212         SDOperand T1, T2;
 213         ExpandOp(Op.getValue(i), T1, T2);
 214         assert(LegalizedNodes.count(Op) &&
 215                "Expansion didn't add legal operands!");
 216         return LegalizedNodes[Op];
 217       }
 218       case Promote:
 219         // FIXME: Implement promotion!
 220         assert(0 && "Promotion not implemented at all yet!");
 221       }
 222   }
 223
 224   // If there is more than one use of this, see if we already legalized it.
 225   // There is no use remembering values that only have a single use, as the map
 226   // entries will never be reused.
 227   if (!Op.Val->hasOneUse()) {
 228     std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
 229     if (I != LegalizedNodes.end()) return I->second;
 230   }
 231
 232   SDOperand Tmp1, Tmp2, Tmp3;
 233
 234   SDOperand Result = Op;
 235   SDNode *Node = Op.Val;
 236
 237   switch (Node->getOpcode()) {
 238   default:
 239     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 240     assert(0 && "Do not know how to legalize this operator!");
 241     abort();
 242   case ISD::EntryToken:
 243   case ISD::FrameIndex:
 244   case ISD::GlobalAddress:
 245   case ISD::ExternalSymbol:
 246   case ISD::ConstantPool:
 247   case ISD::CopyFromReg:            // Nothing to do.
 248     assert(getTypeAction(Node->getValueType(0)) == Legal &&
 249            "This must be legal!");
 250     break;
 251   case ISD::Constant:
 252     // We know we don't need to expand constants here, constants only have one
 253     // value and we check that it is fine above.
 254
 255     // FIXME: Maybe we should handle things like targets that don't support full
 256     // 32-bit immediates?
 257     break;
 258   case ISD::ConstantFP: {
 259     // Spill FP immediates to the constant pool if the target cannot directly
 260     // codegen them.  Targets often have some immediate values that can be
 261     // efficiently generated into an FP register without a load.  We explicitly
 262     // leave these constants as ConstantFP nodes for the target to deal with.
 263
 264     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
 265
 266     // Check to see if this FP immediate is already legal.
 267     bool isLegal = false;
 268     for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
 269            E = TLI.legal_fpimm_end(); I != E; ++I)
 270       if (CFP->isExactlyValue(*I)) {
 271         isLegal = true;
 272         break;
 273       }
 274
 275     if (!isLegal) {
 276       // Otherwise we need to spill the constant to memory.
 277       MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
 278
 279       bool Extend = false;
 280
 281       // If a FP immediate is precise when represented as a float, we put it
 282       // into the constant pool as a float, even if it's is statically typed
 283       // as a double.
 284       MVT::ValueType VT = CFP->getValueType(0);
 285       bool isDouble = VT == MVT::f64;
 286       ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
 287                                              Type::FloatTy, CFP->getValue());
 288       if (isDouble && CFP->isExactlyValue((float)CFP->getValue())) {
 289         LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
 290         VT = MVT::f32;
 291         Extend = true;
 292       }
 293
 294       SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC),
 295                                             TLI.getPointerTy());
 296       Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx);
 297
 298       if (Extend) Result = DAG.getNode(ISD::FP_EXTEND, MVT::f64, Result);
 299     }
 300     break;
 301   }
 302   case ISD::ADJCALLSTACKDOWN:
 303   case ISD::ADJCALLSTACKUP:
 304     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 305     // There is no need to legalize the size argument (Operand #1)
 306     if (Tmp1 != Node->getOperand(0))
 307       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1,
 308                            Node->getOperand(1));
 309     break;
 310   case ISD::DYNAMIC_STACKALLOC:
 311     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 312     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
 313     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
 314     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 315         Tmp3 != Node->getOperand(2))
 316       Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0),
 317                            Tmp1, Tmp2, Tmp3);
 318     else
 319       Result = Op.getValue(0);
 320
 321     // Since this op produces two values, make sure to remember that we
 322     // legalized both of them.
 323     AddLegalizedOperand(SDOperand(Node, 0), Result);
 324     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 325     return Result.getValue(Op.ResNo);
 326
 327   case ISD::CALL:
 328     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 329     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
 330     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
 331       std::vector<MVT::ValueType> RetTyVTs;
 332       RetTyVTs.reserve(Node->getNumValues());
 333       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 334         RetTyVTs.push_back(Node->getValueType(i));
 335       Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2), Op.ResNo);
 336     }
 337     break;
 338
 339   case ISD::BR:
 340     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 341     if (Tmp1 != Node->getOperand(0))
 342       Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1));
 343     break;
 344
 345   case ISD::BRCOND:
 346     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 347     // FIXME: booleans might not be legal!
 348     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the condition.
 349     // Basic block destination (Op#2) is always legal.
 350     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 351       Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
 352                            Node->getOperand(2));
 353     break;
 354
 355   case ISD::LOAD:
 356     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 357     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 358     if (Tmp1 != Node->getOperand(0) ||
 359         Tmp2 != Node->getOperand(1))
 360       Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2);
 361     else
 362       Result = SDOperand(Node, 0);
 363
 364     // Since loads produce two values, make sure to remember that we legalized
 365     // both of them.
 366     AddLegalizedOperand(SDOperand(Node, 0), Result);
 367     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 368     return Result.getValue(Op.ResNo);
 369
 370   case ISD::EXTRACT_ELEMENT:
 371     // Get both the low and high parts.
 372     ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 373     if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
 374       Result = Tmp2;  // 1 -> Hi
 375     else
 376       Result = Tmp1;  // 0 -> Lo
 377     break;
 378
 379   case ISD::CopyToReg:
 380     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 381
 382     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 383     case Legal:
 384       // Legalize the incoming value (must be legal).
 385       Tmp2 = LegalizeOp(Node->getOperand(1));
 386       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 387         Result = DAG.getCopyToReg(Tmp1, Tmp2,
 388                                   cast<CopyRegSDNode>(Node)->getReg());
 389       break;
 390     case Expand: {
 391       SDOperand Lo, Hi;
 392       ExpandOp(Node->getOperand(1), Lo, Hi);
 393       unsigned Reg = cast<CopyRegSDNode>(Node)->getReg();
 394       Result = DAG.getCopyToReg(Tmp1, Lo, Reg);
 395       Result = DAG.getCopyToReg(Result, Hi, Reg+1);
 396       assert(isTypeLegal(Result.getValueType()) &&
 397              "Cannot expand multiple times yet (i64 -> i16)");
 398       break;
 399     }
 400     case Promote:
 401       assert(0 && "Don't know what it means to promote this!");
 402       abort();
 403     }
 404     break;
 405
 406   case ISD::RET:
 407     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 408     switch (Node->getNumOperands()) {
 409     case 2:  // ret val
 410       switch (getTypeAction(Node->getOperand(1).getValueType())) {
 411       case Legal:
 412         Tmp2 = LegalizeOp(Node->getOperand(1));
 413         if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 414           Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 415         break;
 416       case Expand: {
 417         SDOperand Lo, Hi;
 418         ExpandOp(Node->getOperand(1), Lo, Hi);
 419         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
 420         break;
 421       }
 422       case Promote:
 423         assert(0 && "Can't promote return value!");
 424       }
 425       break;
 426     case 1:  // ret void
 427       if (Tmp1 != Node->getOperand(0))
 428         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1);
 429       break;
 430     default: { // ret <values>
 431       std::vector<SDOperand> NewValues;
 432       NewValues.push_back(Tmp1);
 433       for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
 434         switch (getTypeAction(Node->getOperand(i).getValueType())) {
 435         case Legal:
 436           NewValues.push_back(LegalizeOp(Node->getOperand(i)));
 437           break;
 438         case Expand: {
 439           SDOperand Lo, Hi;
 440           ExpandOp(Node->getOperand(i), Lo, Hi);
 441           NewValues.push_back(Lo);
 442           NewValues.push_back(Hi);
 443           break;
 444         }
 445         case Promote:
 446           assert(0 && "Can't promote return value!");
 447         }
 448       Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
 449       break;
 450     }
 451     }
 452     break;
 453   case ISD::STORE:
 454     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 455     Tmp2 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 456
 457     // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
 458     if (ConstantFPSDNode *CFP =
 459         dyn_cast<ConstantFPSDNode>(Node->getOperand(1))) {
 460       if (CFP->getValueType(0) == MVT::f32) {
 461         union {
 462           unsigned I;
 463           float    F;
 464         } V;
 465         V.F = CFP->getValue();
 466         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 467                              DAG.getConstant(V.I, MVT::i32), Tmp2);
 468       } else {
 469         assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
 470         union {
 471           uint64_t I;
 472           double   F;
 473         } V;
 474         V.F = CFP->getValue();
 475         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 476                              DAG.getConstant(V.I, MVT::i64), Tmp2);
 477       }
 478       Op = Result;
 479       Node = Op.Val;
 480     }
 481
 482     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 483     case Legal: {
 484       SDOperand Val = LegalizeOp(Node->getOperand(1));
 485       if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) ||
 486           Tmp2 != Node->getOperand(2))
 487         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2);
 488       break;
 489     }
 490     case Promote:
 491       assert(0 && "FIXME: promote for stores not implemented!");
 492     case Expand:
 493       SDOperand Lo, Hi;
 494       ExpandOp(Node->getOperand(1), Lo, Hi);
 495
 496       if (!TLI.isLittleEndian())
 497         std::swap(Lo, Hi);
 498
 499       // FIXME: These two stores are independent of each other!
 500       Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2);
 501
 502       unsigned IncrementSize;
 503       switch (Lo.getValueType()) {
 504       default: assert(0 && "Unknown ValueType to expand to!");
 505       case MVT::i32: IncrementSize = 4; break;
 506       case MVT::i16: IncrementSize = 2; break;
 507       case MVT::i8:  IncrementSize = 1; break;
 508       }
 509       Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
 510                          getIntPtrConstant(IncrementSize));
 511       assert(isTypeLegal(Tmp2.getValueType()) &&
 512              "Pointers must be legal!");
 513       Result = DAG.getNode(ISD::STORE, MVT::Other, Result, Hi, Tmp2);
 514     }
 515     break;
 516   case ISD::SELECT: {
 517     // FIXME: BOOLS MAY REQUIRE PROMOTION!
 518     Tmp1 = LegalizeOp(Node->getOperand(0));   // Cond
 519     Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
 520     SDOperand Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
 521
 522     if (Tmp1 != Node->getOperand(0) ||
 523         Tmp2 != Node->getOperand(1) ||
 524         Tmp3 != Node->getOperand(2))
 525       Result = DAG.getNode(ISD::SELECT, Node->getValueType(0), Tmp1, Tmp2,Tmp3);
 526     break;
 527   }
 528   case ISD::SETCC:
 529     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 530     case Legal:
 531       Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 532       Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 533       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 534         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 535                               Tmp1, Tmp2);
 536       break;
 537     case Promote:
 538       assert(0 && "Can't promote setcc operands yet!");
 539       break;
 540     case Expand:
 541       SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
 542       ExpandOp(Node->getOperand(0), LHSLo, LHSHi);
 543       ExpandOp(Node->getOperand(1), RHSLo, RHSHi);
 544       switch (cast<SetCCSDNode>(Node)->getCondition()) {
 545       case ISD::SETEQ:
 546       case ISD::SETNE:
 547         Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
 548         Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
 549         Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
 550         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), Tmp1,
 551                               DAG.getConstant(0, Tmp1.getValueType()));
 552         break;
 553       default:
 554         // FIXME: This generated code sucks.
 555         ISD::CondCode LowCC;
 556         switch (cast<SetCCSDNode>(Node)->getCondition()) {
 557         default: assert(0 && "Unknown integer setcc!");
 558         case ISD::SETLT:
 559         case ISD::SETULT: LowCC = ISD::SETULT; break;
 560         case ISD::SETGT:
 561         case ISD::SETUGT: LowCC = ISD::SETUGT; break;
 562         case ISD::SETLE:
 563         case ISD::SETULE: LowCC = ISD::SETULE; break;
 564         case ISD::SETGE:
 565         case ISD::SETUGE: LowCC = ISD::SETUGE; break;
 566         }
 567
 568         // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
 569         // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
 570         // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
 571
 572         // NOTE: on targets without efficient SELECT of bools, we can always use
 573         // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
 574         Tmp1 = DAG.getSetCC(LowCC, LHSLo, RHSLo);
 575         Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 576                             LHSHi, RHSHi);
 577         Result = DAG.getSetCC(ISD::SETEQ, LHSHi, RHSHi);
 578         Result = DAG.getNode(ISD::SELECT, MVT::i1, Result, Tmp1, Tmp2);
 579         break;
 580       }
 581     }
 582     break;
 583
 584   case ISD::ADD:
 585   case ISD::SUB:
 586   case ISD::MUL:
 587   case ISD::UDIV:
 588   case ISD::SDIV:
 589   case ISD::UREM:
 590   case ISD::SREM:
 591   case ISD::AND:
 592   case ISD::OR:
 593   case ISD::XOR:
 594   case ISD::SHL:
 595   case ISD::SRL:
 596   case ISD::SRA:
 597     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 598     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 599     if (Tmp1 != Node->getOperand(0) ||
 600         Tmp2 != Node->getOperand(1))
 601       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2);
 602     break;
 603   case ISD::ZERO_EXTEND:
 604   case ISD::SIGN_EXTEND:
 605   case ISD::TRUNCATE:
 606   case ISD::FP_EXTEND:
 607   case ISD::FP_ROUND:
 608   case ISD::FP_TO_SINT:
 609   case ISD::FP_TO_UINT:
 610   case ISD::SINT_TO_FP:
 611   case ISD::UINT_TO_FP:
 612
 613     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 614     case Legal:
 615       Tmp1 = LegalizeOp(Node->getOperand(0));
 616       if (Tmp1 != Node->getOperand(0))
 617         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
 618       break;
 619     case Expand:
 620       // In the expand case, we must be dealing with a truncate, because
 621       // otherwise the result would be larger than the source.
 622       assert(Node->getOpcode() == ISD::TRUNCATE &&
 623              "Shouldn't need to expand other operators here!");
 624       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 625
 626       // Since the result is legal, we should just be able to truncate the low
 627       // part of the source.
 628       Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
 629       break;
 630
 631     default:
 632       assert(0 && "Do not know how to promote this yet!");
 633     }
 634     break;
 635   }
 636
 637   if (!Op.Val->hasOneUse())
 638     AddLegalizedOperand(Op, Result);
 639
 640   return Result;
 641 }
 642
 643
 644 /// ExpandOp - Expand the specified SDOperand into its two component pieces
 645 /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
 646 /// LegalizeNodes map is filled in for any results that are not expanded, the
 647 /// ExpandedNodes map is filled in for any results that are expanded, and the
 648 /// Lo/Hi values are returned.
 649 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
 650   MVT::ValueType VT = Op.getValueType();
 651   MVT::ValueType NVT = TransformToType[VT];
 652   SDNode *Node = Op.Val;
 653   assert(getTypeAction(VT) == Expand && "Not an expanded type!");
 654   assert(MVT::isInteger(VT) && "Cannot expand FP values!");
 655   assert(MVT::isInteger(NVT) && NVT < VT &&
 656          "Cannot expand to FP value or to larger int value!");
 657
 658   // If there is more than one use of this, see if we already expanded it.
 659   // There is no use remembering values that only have a single use, as the map
 660   // entries will never be reused.
 661   if (!Node->hasOneUse()) {
 662     std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
 663       = ExpandedNodes.find(Op);
 664     if (I != ExpandedNodes.end()) {
 665       Lo = I->second.first;
 666       Hi = I->second.second;
 667       return;
 668     }
 669   }
 670
 671   // Expanding to multiple registers needs to perform an optimization step, and
 672   // is not careful to avoid operations the target does not support.  Make sure
 673   // that all generated operations are legalized in the next iteration.
 674   NeedsAnotherIteration = true;
 675   const char *LibCallName = 0;
 676
 677   switch (Node->getOpcode()) {
 678   default:
 679     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 680     assert(0 && "Do not know how to expand this operator!");
 681     abort();
 682   case ISD::Constant: {
 683     uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
 684     Lo = DAG.getConstant(Cst, NVT);
 685     Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
 686     break;
 687   }
 688
 689   case ISD::CopyFromReg: {
 690     unsigned Reg = cast<CopyRegSDNode>(Node)->getReg();
 691     // Aggregate register values are always in consequtive pairs.
 692     Lo = DAG.getCopyFromReg(Reg, NVT);
 693     Hi = DAG.getCopyFromReg(Reg+1, NVT);
 694     assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
 695     break;
 696   }
 697
 698   case ISD::LOAD: {
 699     SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
 700     SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 701     Lo = DAG.getLoad(NVT, Ch, Ptr);
 702
 703     // Increment the pointer to the other half.
 704     unsigned IncrementSize;
 705     switch (Lo.getValueType()) {
 706     default: assert(0 && "Unknown ValueType to expand to!");
 707     case MVT::i32: IncrementSize = 4; break;
 708     case MVT::i16: IncrementSize = 2; break;
 709     case MVT::i8:  IncrementSize = 1; break;
 710     }
 711     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
 712                       getIntPtrConstant(IncrementSize));
 713     // FIXME: This load is independent of the first one.
 714     Hi = DAG.getLoad(NVT, Lo.getValue(1), Ptr);
 715
 716     // Remember that we legalized the chain.
 717     AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
 718     if (!TLI.isLittleEndian())
 719       std::swap(Lo, Hi);
 720     break;
 721   }
 722   case ISD::CALL: {
 723     SDOperand Chain  = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 724     SDOperand Callee = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
 725
 726     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
 727            "Can only expand a call once so far, not i64 -> i16!");
 728
 729     std::vector<MVT::ValueType> RetTyVTs;
 730     RetTyVTs.reserve(3);
 731     RetTyVTs.push_back(NVT);
 732     RetTyVTs.push_back(NVT);
 733     RetTyVTs.push_back(MVT::Other);
 734     SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee);
 735     Lo = SDOperand(NC, 0);
 736     Hi = SDOperand(NC, 1);
 737
 738     // Insert the new chain mapping.
 739     AddLegalizedOperand(Op.getValue(1), Hi.getValue(2));
 740     break;
 741   }
 742   case ISD::AND:
 743   case ISD::OR:
 744   case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
 745     SDOperand LL, LH, RL, RH;
 746     ExpandOp(Node->getOperand(0), LL, LH);
 747     ExpandOp(Node->getOperand(1), RL, RH);
 748     Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
 749     Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
 750     break;
 751   }
 752   case ISD::SELECT: {
 753     SDOperand C, LL, LH, RL, RH;
 754     // FIXME: BOOLS MAY REQUIRE PROMOTION!
 755     C = LegalizeOp(Node->getOperand(0));
 756     ExpandOp(Node->getOperand(1), LL, LH);
 757     ExpandOp(Node->getOperand(2), RL, RH);
 758     Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL);
 759     Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH);
 760     break;
 761   }
 762   case ISD::SIGN_EXTEND: {
 763     // The low part is just a sign extension of the input (which degenerates to
 764     // a copy).
 765     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
 766
 767     // The high part is obtained by SRA'ing all but one of the bits of the lo
 768     // part.
 769     unsigned SrcSize = MVT::getSizeInBits(Node->getOperand(0).getValueType());
 770     Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(SrcSize-1, MVT::i8));
 771     break;
 772   }
 773   case ISD::ZERO_EXTEND:
 774     // The low part is just a zero extension of the input (which degenerates to
 775     // a copy).
 776     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
 777
 778     // The high part is just a zero.
 779     Hi = DAG.getConstant(0, NVT);
 780     break;
 781
 782     // These operators cannot be expanded directly, emit them as calls to
 783     // library functions.
 784   case ISD::FP_TO_SINT:
 785     if (Node->getOperand(0).getValueType() == MVT::f32)
 786       LibCallName = "__fixsfdi";
 787     else
 788       LibCallName = "__fixdfdi";
 789     break;
 790   case ISD::FP_TO_UINT:
 791     if (Node->getOperand(0).getValueType() == MVT::f32)
 792       LibCallName = "__fixunssfdi";
 793     else
 794       LibCallName = "__fixunsdfdi";
 795     break;
 796
 797   case ISD::ADD:  LibCallName = "__adddi3"; break;
 798   case ISD::SUB:  LibCallName = "__subdi3"; break;
 799   case ISD::MUL:  LibCallName = "__muldi3"; break;
 800   case ISD::SDIV: LibCallName = "__divdi3"; break;
 801   case ISD::UDIV: LibCallName = "__udivdi3"; break;
 802   case ISD::SREM: LibCallName = "__moddi3"; break;
 803   case ISD::UREM: LibCallName = "__umoddi3"; break;
 804   case ISD::SHL:  LibCallName = "__lshrdi3"; break;
 805   case ISD::SRA:  LibCallName = "__ashrdi3"; break;
 806   case ISD::SRL:  LibCallName = "__ashldi3"; break;
 807   }
 808
 809   // Int2FP -> __floatdisf/__floatdidf
 810
 811   // If this is to be expanded into a libcall... do so now.
 812   if (LibCallName) {
 813     TargetLowering::ArgListTy Args;
 814     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 815       Args.push_back(std::make_pair(Node->getOperand(i),
 816                                getTypeFor(Node->getOperand(i).getValueType())));
 817     SDOperand Callee = DAG.getExternalSymbol(LibCallName, TLI.getPointerTy());
 818
 819     // We don't care about token chains for libcalls.  We just use the entry
 820     // node as our input and ignore the output chain.  This allows us to place
 821     // calls wherever we need them to satisfy data dependences.
 822     SDOperand Result = TLI.LowerCallTo(DAG.getEntryNode(),
 823                                        getTypeFor(Op.getValueType()), Callee,
 824                                        Args, DAG).first;
 825     ExpandOp(Result, Lo, Hi);
 826   }
 827
 828   // Remember in a map if the values will be reused later.
 829   if (!Node->hasOneUse()) {
 830     bool isNew = ExpandedNodes.insert(std::make_pair(Op,
 831                                             std::make_pair(Lo, Hi))).second;
 832     assert(isNew && "Value already expanded?!?");
 833   }
 834 }
 835
 836
 837 // SelectionDAG::Legalize - This is the entry point for the file.
 838 //
 839 void SelectionDAG::Legalize(TargetLowering &TLI) {
 840   /// run - This is the main entry point to this class.
 841   ///
 842   SelectionDAGLegalize(TLI, *this).Run();
 843 }
 844