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::ConstantPool:
 228   case ISD::CopyFromReg:            // Nothing to do.
 229     assert(getTypeAction(Node->getValueType(0)) == Legal &&
 230            "This must be legal!");
 231     break;
 232   case ISD::Constant:
 233     // We know we don't need to expand constants here, constants only have one
 234     // value and we check that it is fine above.
 235
 236     // FIXME: Maybe we should handle things like targets that don't support full
 237     // 32-bit immediates?
 238     break;
 239   case ISD::ConstantFP: {
 240     // Spill FP immediates to the constant pool if the target cannot directly
 241     // codegen them.  Targets often have some immediate values that can be
 242     // efficiently generated into an FP register without a load.  We explicitly
 243     // leave these constants as ConstantFP nodes for the target to deal with.
 244
 245     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
 246
 247     // Check to see if this FP immediate is already legal.
 248     bool isLegal = false;
 249     for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
 250            E = TLI.legal_fpimm_end(); I != E; ++I)
 251       if (CFP->isExactlyValue(*I)) {
 252         isLegal = true;
 253         break;
 254       }
 255
 256     if (!isLegal) {
 257       // Otherwise we need to spill the constant to memory.
 258       MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
 259
 260       bool Extend = false;
 261
 262       // If a FP immediate is precise when represented as a float, we put it
 263       // into the constant pool as a float, even if it's is statically typed
 264       // as a double.
 265       MVT::ValueType VT = CFP->getValueType(0);
 266       bool isDouble = VT == MVT::f64;
 267       ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
 268                                              Type::FloatTy, CFP->getValue());
 269       if (isDouble && CFP->isExactlyValue((float)CFP->getValue())) {
 270         LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
 271         VT = MVT::f32;
 272         Extend = true;
 273       }
 274
 275       SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC),
 276                                             TLI.getPointerTy());
 277       Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx);
 278
 279       if (Extend) Result = DAG.getNode(ISD::FP_EXTEND, MVT::f64, Result);
 280     }
 281     break;
 282   }
 283   case ISD::ADJCALLSTACKDOWN:
 284   case ISD::ADJCALLSTACKUP:
 285     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 286     // There is no need to legalize the size argument (Operand #1)
 287     if (Tmp1 != Node->getOperand(0))
 288       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1,
 289                            Node->getOperand(1));
 290     break;
 291   case ISD::CALL:
 292     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 293     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
 294     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
 295       std::vector<MVT::ValueType> RetTyVTs;
 296       RetTyVTs.reserve(Node->getNumValues());
 297       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 298         RetTyVTs.push_back(Node->getValueType(i));
 299       Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2), Op.ResNo);
 300     }
 301     break;
 302
 303   case ISD::BRCOND:
 304     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 305     // FIXME: booleans might not be legal!
 306     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the condition.
 307     // Basic block destination (Op#2) is always legal.
 308     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 309       Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
 310                            Node->getOperand(2));
 311     break;
 312
 313   case ISD::LOAD:
 314     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 315     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 316     if (Tmp1 != Node->getOperand(0) ||
 317         Tmp2 != Node->getOperand(1))
 318       Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2);
 319     break;
 320
 321   case ISD::EXTRACT_ELEMENT:
 322     // Get both the low and high parts.
 323     ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 324     if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
 325       Result = Tmp2;  // 1 -> Hi
 326     else
 327       Result = Tmp1;  // 0 -> Lo
 328     break;
 329
 330   case ISD::CopyToReg:
 331     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 332
 333     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 334     case Legal:
 335       // Legalize the incoming value (must be legal).
 336       Tmp2 = LegalizeOp(Node->getOperand(1));
 337       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 338         Result = DAG.getCopyToReg(Tmp1, Tmp2,
 339                                   cast<CopyRegSDNode>(Node)->getReg());
 340       break;
 341     case Expand: {
 342       SDOperand Lo, Hi;
 343       ExpandOp(Node->getOperand(1), Lo, Hi);
 344       unsigned Reg = cast<CopyRegSDNode>(Node)->getReg();
 345       Result = DAG.getCopyToReg(Tmp1, Lo, Reg);
 346       Result = DAG.getCopyToReg(Result, Hi, Reg+1);
 347       assert(isTypeLegal(Result.getValueType()) &&
 348              "Cannot expand multiple times yet (i64 -> i16)");
 349       break;
 350     }
 351     case Promote:
 352       assert(0 && "Don't know what it means to promote this!");
 353       abort();
 354     }
 355     break;
 356
 357   case ISD::RET:
 358     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 359     switch (Node->getNumOperands()) {
 360     case 2:  // ret val
 361       switch (getTypeAction(Node->getOperand(1).getValueType())) {
 362       case Legal:
 363         Tmp2 = LegalizeOp(Node->getOperand(1));
 364         if (Tmp2 != Node->getOperand(1))
 365           Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 366         break;
 367       case Expand: {
 368         SDOperand Lo, Hi;
 369         ExpandOp(Node->getOperand(1), Lo, Hi);
 370         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
 371         break;
 372       }
 373       case Promote:
 374         assert(0 && "Can't promote return value!");
 375       }
 376       break;
 377     case 1:  // ret void
 378       if (Tmp1 != Node->getOperand(0))
 379         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1);
 380       break;
 381     default: { // ret <values>
 382       std::vector<SDOperand> NewValues;
 383       NewValues.push_back(Tmp1);
 384       for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
 385         switch (getTypeAction(Node->getOperand(i).getValueType())) {
 386         case Legal:
 387           NewValues.push_back(LegalizeOp(Node->getOperand(1)));
 388           break;
 389         case Expand: {
 390           SDOperand Lo, Hi;
 391           ExpandOp(Node->getOperand(i), Lo, Hi);
 392           NewValues.push_back(Lo);
 393           NewValues.push_back(Hi);
 394           break;
 395         }
 396         case Promote:
 397           assert(0 && "Can't promote return value!");
 398         }
 399       Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
 400       break;
 401     }
 402     }
 403     break;
 404   case ISD::STORE:
 405     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 406     Tmp2 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 407
 408     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 409     case Legal: {
 410       SDOperand Val = LegalizeOp(Node->getOperand(1));
 411       if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) ||
 412           Tmp2 != Node->getOperand(2))
 413         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2);
 414       break;
 415     }
 416     case Promote:
 417       assert(0 && "FIXME: promote for stores not implemented!");
 418     case Expand:
 419       SDOperand Lo, Hi;
 420       ExpandOp(Node->getOperand(1), Lo, Hi);
 421
 422       if (!TLI.isLittleEndian())
 423         std::swap(Lo, Hi);
 424
 425       // FIXME: These two stores are independent of each other!
 426       Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2);
 427
 428       unsigned IncrementSize;
 429       switch (Lo.getValueType()) {
 430       default: assert(0 && "Unknown ValueType to expand to!");
 431       case MVT::i32: IncrementSize = 4; break;
 432       case MVT::i16: IncrementSize = 2; break;
 433       case MVT::i8:  IncrementSize = 1; break;
 434       }
 435       Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
 436                          getIntPtrConstant(IncrementSize));
 437       assert(isTypeLegal(Tmp2.getValueType()) &&
 438              "Pointers must be legal!");
 439       Result = DAG.getNode(ISD::STORE, MVT::Other, Result, Hi, Tmp2);
 440     }
 441     break;
 442   case ISD::SELECT: {
 443     // FIXME: BOOLS MAY REQUIRE PROMOTION!
 444     Tmp1 = LegalizeOp(Node->getOperand(0));   // Cond
 445     Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
 446     SDOperand Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
 447
 448     if (Tmp1 != Node->getOperand(0) ||
 449         Tmp2 != Node->getOperand(1) ||
 450         Tmp3 != Node->getOperand(2))
 451       Result = DAG.getNode(ISD::SELECT, Node->getValueType(0), Tmp1, Tmp2,Tmp3);
 452     break;
 453   }
 454   case ISD::SETCC:
 455     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 456     case Legal:
 457       Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 458       Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 459       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 460         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 461                               Tmp1, Tmp2);
 462       break;
 463     case Promote:
 464       assert(0 && "Can't promote setcc operands yet!");
 465       break;
 466     case Expand:
 467       SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
 468       ExpandOp(Node->getOperand(0), LHSLo, LHSHi);
 469       ExpandOp(Node->getOperand(1), RHSLo, RHSHi);
 470       switch (cast<SetCCSDNode>(Node)->getCondition()) {
 471       case ISD::SETEQ:
 472       case ISD::SETNE:
 473         Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
 474         Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
 475         Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
 476         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), Tmp1,
 477                               DAG.getConstant(0, Tmp1.getValueType()));
 478         break;
 479       default:
 480         // FIXME: This generated code sucks.
 481         ISD::CondCode LowCC;
 482         switch (cast<SetCCSDNode>(Node)->getCondition()) {
 483         default: assert(0 && "Unknown integer setcc!");
 484         case ISD::SETLT:
 485         case ISD::SETULT: LowCC = ISD::SETULT; break;
 486         case ISD::SETGT:
 487         case ISD::SETUGT: LowCC = ISD::SETUGT; break;
 488         case ISD::SETLE:
 489         case ISD::SETULE: LowCC = ISD::SETULE; break;
 490         case ISD::SETGE:
 491         case ISD::SETUGE: LowCC = ISD::SETUGE; break;
 492         }
 493
 494         // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
 495         // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
 496         // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
 497
 498         // NOTE: on targets without efficient SELECT of bools, we can always use
 499         // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
 500         Tmp1 = DAG.getSetCC(LowCC, LHSLo, RHSLo);
 501         Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 502                             LHSHi, RHSHi);
 503         Result = DAG.getSetCC(ISD::SETEQ, LHSHi, RHSHi);
 504         Result = DAG.getNode(ISD::SELECT, MVT::i1, Result, Tmp1, Tmp2);
 505         break;
 506       }
 507     }
 508     break;
 509
 510   case ISD::ADD:
 511   case ISD::SUB:
 512   case ISD::MUL:
 513   case ISD::UDIV:
 514   case ISD::SDIV:
 515   case ISD::UREM:
 516   case ISD::SREM:
 517   case ISD::AND:
 518   case ISD::OR:
 519   case ISD::XOR:
 520     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 521     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 522     if (Tmp1 != Node->getOperand(0) ||
 523         Tmp2 != Node->getOperand(1))
 524       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2);
 525     break;
 526   case ISD::ZERO_EXTEND:
 527   case ISD::SIGN_EXTEND:
 528     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 529     case Legal:
 530       Tmp1 = LegalizeOp(Node->getOperand(0));
 531       if (Tmp1 != Node->getOperand(0))
 532         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
 533       break;
 534     default:
 535       assert(0 && "Do not know how to expand or promote this yet!");
 536     }
 537     break;
 538   }
 539
 540   if (!Op.Val->hasOneUse()) {
 541     bool isNew = LegalizedNodes.insert(std::make_pair(Op, Result)).second;
 542     assert(isNew && "Got into the map somehow?");
 543   }
 544
 545   return Result;
 546 }
 547
 548
 549 /// ExpandOp - Expand the specified SDOperand into its two component pieces
 550 /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
 551 /// LegalizeNodes map is filled in for any results that are not expanded, the
 552 /// ExpandedNodes map is filled in for any results that are expanded, and the
 553 /// Lo/Hi values are returned.
 554 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
 555   MVT::ValueType VT = Op.getValueType();
 556   MVT::ValueType NVT = TransformToType[VT];
 557   SDNode *Node = Op.Val;
 558   assert(getTypeAction(VT) == Expand && "Not an expanded type!");
 559   assert(MVT::isInteger(VT) && "Cannot expand FP values!");
 560   assert(MVT::isInteger(NVT) && NVT < VT &&
 561          "Cannot expand to FP value or to larger int value!");
 562
 563   // If there is more than one use of this, see if we already expanded it.
 564   // There is no use remembering values that only have a single use, as the map
 565   // entries will never be reused.
 566   if (!Node->hasOneUse()) {
 567     std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
 568       = ExpandedNodes.find(Op);
 569     if (I != ExpandedNodes.end()) {
 570       Lo = I->second.first;
 571       Hi = I->second.second;
 572       return;
 573     }
 574   }
 575
 576   // If we are lowering to a type that the target doesn't support, we will have
 577   // to iterate lowering.
 578   if (!isTypeLegal(NVT))
 579     NeedsAnotherIteration = true;
 580
 581   LegalizeAction Action;
 582   switch (Node->getOpcode()) {
 583   default:
 584     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 585     assert(0 && "Do not know how to expand this operator!");
 586     abort();
 587   case ISD::Constant: {
 588     uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
 589     Lo = DAG.getConstant(Cst, NVT);
 590     Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
 591     break;
 592   }
 593
 594   case ISD::CopyFromReg: {
 595     unsigned Reg = cast<CopyRegSDNode>(Node)->getReg();
 596     // Aggregate register values are always in consequtive pairs.
 597     Lo = DAG.getCopyFromReg(Reg, NVT);
 598     Hi = DAG.getCopyFromReg(Reg+1, NVT);
 599     assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
 600     break;
 601   }
 602
 603   case ISD::LOAD: {
 604     SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
 605     SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 606     Lo = DAG.getLoad(NVT, Ch, Ptr);
 607
 608     // Increment the pointer to the other half.
 609     unsigned IncrementSize;
 610     switch (Lo.getValueType()) {
 611     default: assert(0 && "Unknown ValueType to expand to!");
 612     case MVT::i32: IncrementSize = 4; break;
 613     case MVT::i16: IncrementSize = 2; break;
 614     case MVT::i8:  IncrementSize = 1; break;
 615     }
 616     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
 617                       getIntPtrConstant(IncrementSize));
 618     // FIXME: This load is independent of the first one.
 619     Hi = DAG.getLoad(NVT, Lo.getValue(1), Ptr);
 620
 621     // Remember that we legalized the chain.
 622     bool isNew = LegalizedNodes.insert(std::make_pair(Op.getValue(1),
 623                                                       Hi.getValue(1))).second;
 624     assert(isNew && "This node was already legalized!");
 625     if (!TLI.isLittleEndian())
 626       std::swap(Lo, Hi);
 627     break;
 628   }
 629   case ISD::CALL: {
 630     SDOperand Chain  = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 631     SDOperand Callee = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
 632
 633     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
 634            "Can only expand a call once so far, not i64 -> i16!");
 635
 636     std::vector<MVT::ValueType> RetTyVTs;
 637     RetTyVTs.reserve(3);
 638     RetTyVTs.push_back(NVT);
 639     RetTyVTs.push_back(NVT);
 640     RetTyVTs.push_back(MVT::Other);
 641     SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee);
 642     Lo = SDOperand(NC, 0);
 643     Hi = SDOperand(NC, 1);
 644
 645     // Insert the new chain mapping.
 646     bool isNew = LegalizedNodes.insert(std::make_pair(Op.getValue(1),
 647                                                       Hi.getValue(2))).second;
 648     assert(isNew && "This node was already legalized!");
 649     break;
 650   }
 651   case ISD::AND:
 652   case ISD::OR:
 653   case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
 654     SDOperand LL, LH, RL, RH;
 655     ExpandOp(Node->getOperand(0), LL, LH);
 656     ExpandOp(Node->getOperand(1), RL, RH);
 657     Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
 658     Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
 659     break;
 660   }
 661   case ISD::SELECT: {
 662     SDOperand C, LL, LH, RL, RH;
 663     // FIXME: BOOLS MAY REQUIRE PROMOTION!
 664     C = LegalizeOp(Node->getOperand(0));
 665     ExpandOp(Node->getOperand(1), LL, LH);
 666     ExpandOp(Node->getOperand(2), RL, RH);
 667     Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL);
 668     Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH);
 669     break;
 670   }
 671   case ISD::SIGN_EXTEND: {
 672     // The low part is just a sign extension of the input (which degenerates to
 673     // a copy).
 674     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
 675
 676     // The high part is obtained by SRA'ing all but one of the bits of the lo
 677     // part.
 678     unsigned SrcSize = MVT::getSizeInBits(Node->getOperand(0).getValueType());
 679     Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(SrcSize-1, MVT::i8));
 680     break;
 681   }
 682   case ISD::ZERO_EXTEND:
 683     // The low part is just a zero extension of the input (which degenerates to
 684     // a copy).
 685     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
 686
 687     // The high part is just a zero.
 688     Hi = DAG.getConstant(0, NVT);
 689     break;
 690   }
 691
 692   // Remember in a map if the values will be reused later.
 693   if (!Node->hasOneUse()) {
 694     bool isNew = ExpandedNodes.insert(std::make_pair(Op,
 695                                             std::make_pair(Lo, Hi))).second;
 696     assert(isNew && "Value already expanded?!?");
 697   }
 698 }
 699
 700
 701 // SelectionDAG::Legalize - This is the entry point for the file.
 702 //
 703 void SelectionDAG::Legalize(TargetLowering &TLI) {
 704   /// run - This is the main entry point to this class.
 705   ///
 706   SelectionDAGLegalize(TLI, *this).Run();
 707 }
 708