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