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