lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

   1 //===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the SelectionDAG::Legalize method.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/SelectionDAG.h"
  15 #include "llvm/CodeGen/MachineConstantPool.h"
  16 #include "llvm/CodeGen/MachineFunction.h"
  17 #include "llvm/CodeGen/MachineFrameInfo.h"
  18 #include "llvm/Target/TargetLowering.h"
  19 #include "llvm/Target/TargetData.h"
  20 #include "llvm/Target/TargetOptions.h"
  21 #include "llvm/Constants.h"
  22 #include <iostream>
  23 using namespace llvm;
  24
  25 //===----------------------------------------------------------------------===//
  26 /// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and
  27 /// hacks on it until the target machine can handle it.  This involves
  28 /// eliminating value sizes the machine cannot handle (promoting small sizes to
  29 /// large sizes or splitting up large values into small values) as well as
  30 /// eliminating operations the machine cannot handle.
  31 ///
  32 /// This code also does a small amount of optimization and recognition of idioms
  33 /// as part of its processing.  For example, if a target does not support a
  34 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
  35 /// will attempt merge setcc and brc instructions into brcc's.
  36 ///
  37 namespace {
  38 class SelectionDAGLegalize {
  39   TargetLowering &TLI;
  40   SelectionDAG &DAG;
  41
  42   /// LegalizeAction - This enum indicates what action we should take for each
  43   /// value type the can occur in the program.
  44   enum LegalizeAction {
  45     Legal,            // The target natively supports this value type.
  46     Promote,          // This should be promoted to the next larger type.
  47     Expand,           // This integer type should be broken into smaller pieces.
  48   };
  49
  50   /// ValueTypeActions - This is a bitvector that contains two bits for each
  51   /// value type, where the two bits correspond to the LegalizeAction enum.
  52   /// This can be queried with "getTypeAction(VT)".
  53   unsigned ValueTypeActions;
  54
  55   /// NeedsAnotherIteration - This is set when we expand a large integer
  56   /// operation into smaller integer operations, but the smaller operations are
  57   /// not set.  This occurs only rarely in practice, for targets that don't have
  58   /// 32-bit or larger integer registers.
  59   bool NeedsAnotherIteration;
  60
  61   /// LegalizedNodes - For nodes that are of legal width, and that have more
  62   /// than one use, this map indicates what regularized operand to use.  This
  63   /// allows us to avoid legalizing the same thing more than once.
  64   std::map<SDOperand, SDOperand> LegalizedNodes;
  65
  66   /// PromotedNodes - For nodes that are below legal width, and that have more
  67   /// than one use, this map indicates what promoted value to use.  This allows
  68   /// us to avoid promoting the same thing more than once.
  69   std::map<SDOperand, SDOperand> PromotedNodes;
  70
  71   /// ExpandedNodes - For nodes that need to be expanded, and which have more
  72   /// than one use, this map indicates which which operands are the expanded
  73   /// version of the input.  This allows us to avoid expanding the same node
  74   /// more than once.
  75   std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
  76
  77   void AddLegalizedOperand(SDOperand From, SDOperand To) {
  78     bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second;
  79     assert(isNew && "Got into the map somehow?");
  80   }
  81   void AddPromotedOperand(SDOperand From, SDOperand To) {
  82     bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second;
  83     assert(isNew && "Got into the map somehow?");
  84   }
  85
  86 public:
  87
  88   SelectionDAGLegalize(SelectionDAG &DAG);
  89
  90   /// Run - While there is still lowering to do, perform a pass over the DAG.
  91   /// Most regularization can be done in a single pass, but targets that require
  92   /// large values to be split into registers multiple times (e.g. i64 -> 4x
  93   /// i16) require iteration for these values (the first iteration will demote
  94   /// to i32, the second will demote to i16).
  95   void Run() {
  96     do {
  97       NeedsAnotherIteration = false;
  98       LegalizeDAG();
  99     } while (NeedsAnotherIteration);
 100   }
 101
 102   /// getTypeAction - Return how we should legalize values of this type, either
 103   /// it is already legal or we need to expand it into multiple registers of
 104   /// smaller integer type, or we need to promote it to a larger type.
 105   LegalizeAction getTypeAction(MVT::ValueType VT) const {
 106     return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3);
 107   }
 108
 109   /// isTypeLegal - Return true if this type is legal on this target.
 110   ///
 111   bool isTypeLegal(MVT::ValueType VT) const {
 112     return getTypeAction(VT) == Legal;
 113   }
 114
 115 private:
 116   void LegalizeDAG();
 117
 118   SDOperand LegalizeOp(SDOperand O);
 119   void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
 120   SDOperand PromoteOp(SDOperand O);
 121
 122   SDOperand ExpandLibCall(const char *Name, SDNode *Node,
 123                           SDOperand &Hi);
 124   SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy,
 125                           SDOperand Source);
 126   bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt,
 127                    SDOperand &Lo, SDOperand &Hi);
 128   void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt,
 129                         SDOperand &Lo, SDOperand &Hi);
 130   void ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS,
 131                      SDOperand &Lo, SDOperand &Hi);
 132
 133   void SpliceCallInto(const SDOperand &CallResult, SDNode *OutChain);
 134
 135   SDOperand getIntPtrConstant(uint64_t Val) {
 136     return DAG.getConstant(Val, TLI.getPointerTy());
 137   }
 138 };
 139 }
 140
 141
 142 SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag)
 143   : TLI(dag.getTargetLoweringInfo()), DAG(dag),
 144     ValueTypeActions(TLI.getValueTypeActions()) {
 145   assert(MVT::LAST_VALUETYPE <= 16 &&
 146          "Too many value types for ValueTypeActions to hold!");
 147 }
 148
 149 void SelectionDAGLegalize::LegalizeDAG() {
 150   SDOperand OldRoot = DAG.getRoot();
 151   SDOperand NewRoot = LegalizeOp(OldRoot);
 152   DAG.setRoot(NewRoot);
 153
 154   ExpandedNodes.clear();
 155   LegalizedNodes.clear();
 156   PromotedNodes.clear();
 157
 158   // Remove dead nodes now.
 159   DAG.RemoveDeadNodes(OldRoot.Val);
 160 }
 161
 162 SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 163   assert(getTypeAction(Op.getValueType()) == Legal &&
 164          "Caller should expand or promote operands that are not legal!");
 165   SDNode *Node = Op.Val;
 166
 167   // If this operation defines any values that cannot be represented in a
 168   // register on this target, make sure to expand or promote them.
 169   if (Node->getNumValues() > 1) {
 170     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 171       switch (getTypeAction(Node->getValueType(i))) {
 172       case Legal: break;  // Nothing to do.
 173       case Expand: {
 174         SDOperand T1, T2;
 175         ExpandOp(Op.getValue(i), T1, T2);
 176         assert(LegalizedNodes.count(Op) &&
 177                "Expansion didn't add legal operands!");
 178         return LegalizedNodes[Op];
 179       }
 180       case Promote:
 181         PromoteOp(Op.getValue(i));
 182         assert(LegalizedNodes.count(Op) &&
 183                "Expansion didn't add legal operands!");
 184         return LegalizedNodes[Op];
 185       }
 186   }
 187
 188   // Note that LegalizeOp may be reentered even from single-use nodes, which
 189   // means that we always must cache transformed nodes.
 190   std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
 191   if (I != LegalizedNodes.end()) return I->second;
 192
 193   SDOperand Tmp1, Tmp2, Tmp3;
 194
 195   SDOperand Result = Op;
 196
 197   switch (Node->getOpcode()) {
 198   default:
 199     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
 200     assert(0 && "Do not know how to legalize this operator!");
 201     abort();
 202   case ISD::EntryToken:
 203   case ISD::FrameIndex:
 204   case ISD::GlobalAddress:
 205   case ISD::ExternalSymbol:
 206   case ISD::ConstantPool:           // Nothing to do.
 207     assert(getTypeAction(Node->getValueType(0)) == Legal &&
 208            "This must be legal!");
 209     break;
 210   case ISD::CopyFromReg:
 211     Tmp1 = LegalizeOp(Node->getOperand(0));
 212     if (Tmp1 != Node->getOperand(0))
 213       Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(),
 214                                   Node->getValueType(0), Tmp1);
 215     else
 216       Result = Op.getValue(0);
 217
 218     // Since CopyFromReg produces two values, make sure to remember that we
 219     // legalized both of them.
 220     AddLegalizedOperand(Op.getValue(0), Result);
 221     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
 222     return Result.getValue(Op.ResNo);
 223   case ISD::ImplicitDef:
 224     Tmp1 = LegalizeOp(Node->getOperand(0));
 225     if (Tmp1 != Node->getOperand(0))
 226       Result = DAG.getImplicitDef(Tmp1, cast<RegSDNode>(Node)->getReg());
 227     break;
 228   case ISD::UNDEF: {
 229     MVT::ValueType VT = Op.getValueType();
 230     switch (TLI.getOperationAction(ISD::UNDEF, VT)) {
 231     default: assert(0 && "This action is not supported yet!");
 232     case TargetLowering::Expand:
 233     case TargetLowering::Promote:
 234       if (MVT::isInteger(VT))
 235         Result = DAG.getConstant(0, VT);
 236       else if (MVT::isFloatingPoint(VT))
 237         Result = DAG.getConstantFP(0, VT);
 238       else
 239         assert(0 && "Unknown value type!");
 240       break;
 241     case TargetLowering::Legal:
 242       break;
 243     }
 244     break;
 245   }
 246   case ISD::Constant:
 247     // We know we don't need to expand constants here, constants only have one
 248     // value and we check that it is fine above.
 249
 250     // FIXME: Maybe we should handle things like targets that don't support full
 251     // 32-bit immediates?
 252     break;
 253   case ISD::ConstantFP: {
 254     // Spill FP immediates to the constant pool if the target cannot directly
 255     // codegen them.  Targets often have some immediate values that can be
 256     // efficiently generated into an FP register without a load.  We explicitly
 257     // leave these constants as ConstantFP nodes for the target to deal with.
 258
 259     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
 260
 261     // Check to see if this FP immediate is already legal.
 262     bool isLegal = false;
 263     for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
 264            E = TLI.legal_fpimm_end(); I != E; ++I)
 265       if (CFP->isExactlyValue(*I)) {
 266         isLegal = true;
 267         break;
 268       }
 269
 270     if (!isLegal) {
 271       // Otherwise we need to spill the constant to memory.
 272       MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
 273
 274       bool Extend = false;
 275
 276       // If a FP immediate is precise when represented as a float, we put it
 277       // into the constant pool as a float, even if it's is statically typed
 278       // as a double.
 279       MVT::ValueType VT = CFP->getValueType(0);
 280       bool isDouble = VT == MVT::f64;
 281       ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
 282                                              Type::FloatTy, CFP->getValue());
 283       if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) &&
 284           // Only do this if the target has a native EXTLOAD instruction from
 285           // f32.
 286           TLI.getOperationAction(ISD::EXTLOAD,
 287                                  MVT::f32) == TargetLowering::Legal) {
 288         LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
 289         VT = MVT::f32;
 290         Extend = true;
 291       }
 292
 293       SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC),
 294                                             TLI.getPointerTy());
 295       if (Extend) {
 296         Result = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), CPIdx,
 297                              DAG.getSrcValue(NULL), MVT::f32);
 298       } else {
 299         Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx,
 300                              DAG.getSrcValue(NULL));
 301       }
 302     }
 303     break;
 304   }
 305   case ISD::TokenFactor: {
 306     std::vector<SDOperand> Ops;
 307     bool Changed = false;
 308     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
 309       SDOperand Op = Node->getOperand(i);
 310       // Fold single-use TokenFactor nodes into this token factor as we go.
 311       // FIXME: This is something that the DAGCombiner should do!!
 312       if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) {
 313         Changed = true;
 314         for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j)
 315           Ops.push_back(LegalizeOp(Op.getOperand(j)));
 316       } else {
 317         Ops.push_back(LegalizeOp(Op));  // Legalize the operands
 318         Changed |= Ops[i] != Op;
 319       }
 320     }
 321     if (Changed)
 322       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops);
 323     break;
 324   }
 325
 326   case ISD::CALLSEQ_START:
 327   case ISD::CALLSEQ_END:
 328     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 329     // Do not try to legalize the target-specific arguments (#1+)
 330     Tmp2 = Node->getOperand(0);
 331     if (Tmp1 != Tmp2) {
 332       Node->setAdjCallChain(Tmp1);
 333
 334       // If moving the operand from pointing to Tmp2 dropped its use count to 1,
 335       // this will cause the maps used to memoize results to get confused.
 336       // Create and add a dummy use, just to increase its use count.  This will
 337       // be removed at the end of legalize when dead nodes are removed.
 338       if (Tmp2.Val->hasOneUse())
 339         DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp2,
 340                     DAG.getConstant(0, MVT::i32));
 341     }
 342     // Note that we do not create new CALLSEQ_DOWN/UP nodes here.  These
 343     // nodes are treated specially and are mutated in place.  This makes the dag
 344     // legalization process more efficient and also makes libcall insertion
 345     // easier.
 346     break;
 347   case ISD::DYNAMIC_STACKALLOC:
 348     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 349     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
 350     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
 351     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 352         Tmp3 != Node->getOperand(2))
 353       Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0),
 354                            Tmp1, Tmp2, Tmp3);
 355     else
 356       Result = Op.getValue(0);
 357
 358     // Since this op produces two values, make sure to remember that we
 359     // legalized both of them.
 360     AddLegalizedOperand(SDOperand(Node, 0), Result);
 361     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 362     return Result.getValue(Op.ResNo);
 363
 364   case ISD::CALL: {
 365     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 366     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
 367
 368     bool Changed = false;
 369     std::vector<SDOperand> Ops;
 370     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
 371       Ops.push_back(LegalizeOp(Node->getOperand(i)));
 372       Changed |= Ops.back() != Node->getOperand(i);
 373     }
 374
 375     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Changed) {
 376       std::vector<MVT::ValueType> RetTyVTs;
 377       RetTyVTs.reserve(Node->getNumValues());
 378       for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 379         RetTyVTs.push_back(Node->getValueType(i));
 380       Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops), 0);
 381     } else {
 382       Result = Result.getValue(0);
 383     }
 384     // Since calls produce multiple values, make sure to remember that we
 385     // legalized all of them.
 386     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
 387       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
 388     return Result.getValue(Op.ResNo);
 389   }
 390   case ISD::BR:
 391     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 392     if (Tmp1 != Node->getOperand(0))
 393       Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1));
 394     break;
 395
 396   case ISD::BRCOND:
 397     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 398
 399     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 400     case Expand: assert(0 && "It's impossible to expand bools");
 401     case Legal:
 402       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
 403       break;
 404     case Promote:
 405       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
 406       break;
 407     }
 408     // Basic block destination (Op#2) is always legal.
 409     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 410       Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
 411                            Node->getOperand(2));
 412     break;
 413   case ISD::BRCONDTWOWAY:
 414     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 415     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 416     case Expand: assert(0 && "It's impossible to expand bools");
 417     case Legal:
 418       Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
 419       break;
 420     case Promote:
 421       Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
 422       break;
 423     }
 424     // If this target does not support BRCONDTWOWAY, lower it to a BRCOND/BR
 425     // pair.
 426     switch (TLI.getOperationAction(ISD::BRCONDTWOWAY, MVT::Other)) {
 427     case TargetLowering::Promote:
 428     default: assert(0 && "This action is not supported yet!");
 429     case TargetLowering::Legal:
 430       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
 431         std::vector<SDOperand> Ops;
 432         Ops.push_back(Tmp1);
 433         Ops.push_back(Tmp2);
 434         Ops.push_back(Node->getOperand(2));
 435         Ops.push_back(Node->getOperand(3));
 436         Result = DAG.getNode(ISD::BRCONDTWOWAY, MVT::Other, Ops);
 437       }
 438       break;
 439     case TargetLowering::Expand:
 440       Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
 441                            Node->getOperand(2));
 442       Result = DAG.getNode(ISD::BR, MVT::Other, Result, Node->getOperand(3));
 443       break;
 444     }
 445     break;
 446
 447   case ISD::LOAD:
 448     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 449     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 450
 451     if (Tmp1 != Node->getOperand(0) ||
 452         Tmp2 != Node->getOperand(1))
 453       Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2,
 454                            Node->getOperand(2));
 455     else
 456       Result = SDOperand(Node, 0);
 457
 458     // Since loads produce two values, make sure to remember that we legalized
 459     // both of them.
 460     AddLegalizedOperand(SDOperand(Node, 0), Result);
 461     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 462     return Result.getValue(Op.ResNo);
 463
 464   case ISD::EXTLOAD:
 465   case ISD::SEXTLOAD:
 466   case ISD::ZEXTLOAD: {
 467     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 468     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
 469
 470     MVT::ValueType SrcVT = cast<MVTSDNode>(Node)->getExtraValueType();
 471     switch (TLI.getOperationAction(Node->getOpcode(), SrcVT)) {
 472     default: assert(0 && "This action is not supported yet!");
 473     case TargetLowering::Promote:
 474       assert(SrcVT == MVT::i1 && "Can only promote EXTLOAD from i1 -> i8!");
 475       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0),
 476                            Tmp1, Tmp2, Node->getOperand(2), MVT::i8);
 477       // Since loads produce two values, make sure to remember that we legalized
 478       // both of them.
 479       AddLegalizedOperand(SDOperand(Node, 0), Result);
 480       AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 481       return Result.getValue(Op.ResNo);
 482
 483     case TargetLowering::Legal:
 484       if (Tmp1 != Node->getOperand(0) ||
 485           Tmp2 != Node->getOperand(1))
 486         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0),
 487                              Tmp1, Tmp2, Node->getOperand(2), SrcVT);
 488       else
 489         Result = SDOperand(Node, 0);
 490
 491       // Since loads produce two values, make sure to remember that we legalized
 492       // both of them.
 493       AddLegalizedOperand(SDOperand(Node, 0), Result);
 494       AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 495       return Result.getValue(Op.ResNo);
 496     case TargetLowering::Expand:
 497       assert(Node->getOpcode() != ISD::EXTLOAD &&
 498              "EXTLOAD should always be supported!");
 499       // Turn the unsupported load into an EXTLOAD followed by an explicit
 500       // zero/sign extend inreg.
 501       Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0),
 502                            Tmp1, Tmp2, Node->getOperand(2), SrcVT);
 503       SDOperand ValRes;
 504       if (Node->getOpcode() == ISD::SEXTLOAD)
 505         ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
 506                              Result, SrcVT);
 507       else
 508         ValRes = DAG.getZeroExtendInReg(Result, SrcVT);
 509       AddLegalizedOperand(SDOperand(Node, 0), ValRes);
 510       AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 511       if (Op.ResNo)
 512         return Result.getValue(1);
 513       return ValRes;
 514     }
 515     assert(0 && "Unreachable");
 516   }
 517   case ISD::EXTRACT_ELEMENT:
 518     // Get both the low and high parts.
 519     ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
 520     if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
 521       Result = Tmp2;  // 1 -> Hi
 522     else
 523       Result = Tmp1;  // 0 -> Lo
 524     break;
 525
 526   case ISD::CopyToReg:
 527     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 528
 529     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 530     case Legal:
 531       // Legalize the incoming value (must be legal).
 532       Tmp2 = LegalizeOp(Node->getOperand(1));
 533       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 534         Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
 535       break;
 536     case Promote:
 537       Tmp2 = PromoteOp(Node->getOperand(1));
 538       Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
 539       break;
 540     case Expand:
 541       SDOperand Lo, Hi;
 542       ExpandOp(Node->getOperand(1), Lo, Hi);
 543       unsigned Reg = cast<RegSDNode>(Node)->getReg();
 544       Lo = DAG.getCopyToReg(Tmp1, Lo, Reg);
 545       Hi = DAG.getCopyToReg(Tmp1, Hi, Reg+1);
 546       // Note that the copytoreg nodes are independent of each other.
 547       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
 548       assert(isTypeLegal(Result.getValueType()) &&
 549              "Cannot expand multiple times yet (i64 -> i16)");
 550       break;
 551     }
 552     break;
 553
 554   case ISD::RET:
 555     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 556     switch (Node->getNumOperands()) {
 557     case 2:  // ret val
 558       switch (getTypeAction(Node->getOperand(1).getValueType())) {
 559       case Legal:
 560         Tmp2 = LegalizeOp(Node->getOperand(1));
 561         if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 562           Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 563         break;
 564       case Expand: {
 565         SDOperand Lo, Hi;
 566         ExpandOp(Node->getOperand(1), Lo, Hi);
 567         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
 568         break;
 569       }
 570       case Promote:
 571         Tmp2 = PromoteOp(Node->getOperand(1));
 572         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
 573         break;
 574       }
 575       break;
 576     case 1:  // ret void
 577       if (Tmp1 != Node->getOperand(0))
 578         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1);
 579       break;
 580     default: { // ret <values>
 581       std::vector<SDOperand> NewValues;
 582       NewValues.push_back(Tmp1);
 583       for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
 584         switch (getTypeAction(Node->getOperand(i).getValueType())) {
 585         case Legal:
 586           NewValues.push_back(LegalizeOp(Node->getOperand(i)));
 587           break;
 588         case Expand: {
 589           SDOperand Lo, Hi;
 590           ExpandOp(Node->getOperand(i), Lo, Hi);
 591           NewValues.push_back(Lo);
 592           NewValues.push_back(Hi);
 593           break;
 594         }
 595         case Promote:
 596           assert(0 && "Can't promote multiple return value yet!");
 597         }
 598       Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
 599       break;
 600     }
 601     }
 602     break;
 603   case ISD::STORE:
 604     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 605     Tmp2 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 606
 607     // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
 608     if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){
 609       if (CFP->getValueType(0) == MVT::f32) {
 610         union {
 611           unsigned I;
 612           float    F;
 613         } V;
 614         V.F = CFP->getValue();
 615         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 616                              DAG.getConstant(V.I, MVT::i32), Tmp2,
 617                              Node->getOperand(3));
 618       } else {
 619         assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
 620         union {
 621           uint64_t I;
 622           double   F;
 623         } V;
 624         V.F = CFP->getValue();
 625         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
 626                              DAG.getConstant(V.I, MVT::i64), Tmp2,
 627                              Node->getOperand(3));
 628       }
 629       Node = Result.Val;
 630     }
 631
 632     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 633     case Legal: {
 634       SDOperand Val = LegalizeOp(Node->getOperand(1));
 635       if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) ||
 636           Tmp2 != Node->getOperand(2))
 637         Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2,
 638                              Node->getOperand(3));
 639       break;
 640     }
 641     case Promote:
 642       // Truncate the value and store the result.
 643       Tmp3 = PromoteOp(Node->getOperand(1));
 644       Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2,
 645                            Node->getOperand(3),
 646                            Node->getOperand(1).getValueType());
 647       break;
 648
 649     case Expand:
 650       SDOperand Lo, Hi;
 651       ExpandOp(Node->getOperand(1), Lo, Hi);
 652
 653       if (!TLI.isLittleEndian())
 654         std::swap(Lo, Hi);
 655
 656       Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2,
 657                        Node->getOperand(3));
 658       unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8;
 659       Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
 660                          getIntPtrConstant(IncrementSize));
 661       assert(isTypeLegal(Tmp2.getValueType()) &&
 662              "Pointers must be legal!");
 663       //Again, claiming both parts of the store came form the same Instr
 664       Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2,
 665                        Node->getOperand(3));
 666       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
 667       break;
 668     }
 669     break;
 670   case ISD::PCMARKER:
 671     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 672     if (Tmp1 != Node->getOperand(0))
 673       Result = DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp1,Node->getOperand(1));
 674     break;
 675   case ISD::TRUNCSTORE:
 676     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
 677     Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
 678
 679     switch (getTypeAction(Node->getOperand(1).getValueType())) {
 680     case Legal:
 681       Tmp2 = LegalizeOp(Node->getOperand(1));
 682       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 683           Tmp3 != Node->getOperand(2))
 684         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3,
 685                              Node->getOperand(3),
 686                              cast<MVTSDNode>(Node)->getExtraValueType());
 687       break;
 688     case Promote:
 689     case Expand:
 690       assert(0 && "Cannot handle illegal TRUNCSTORE yet!");
 691     }
 692     break;
 693   case ISD::SELECT:
 694     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 695     case Expand: assert(0 && "It's impossible to expand bools");
 696     case Legal:
 697       Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
 698       break;
 699     case Promote:
 700       Tmp1 = PromoteOp(Node->getOperand(0));  // Promote the condition.
 701       break;
 702     }
 703     Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
 704     Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
 705
 706     switch (TLI.getOperationAction(Node->getOpcode(), Tmp2.getValueType())) {
 707     default: assert(0 && "This action is not supported yet!");
 708     case TargetLowering::Legal:
 709       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 710           Tmp3 != Node->getOperand(2))
 711         Result = DAG.getNode(ISD::SELECT, Node->getValueType(0),
 712                              Tmp1, Tmp2, Tmp3);
 713       break;
 714     case TargetLowering::Promote: {
 715       MVT::ValueType NVT =
 716         TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType());
 717       unsigned ExtOp, TruncOp;
 718       if (MVT::isInteger(Tmp2.getValueType())) {
 719         ExtOp = ISD::ZERO_EXTEND;
 720         TruncOp  = ISD::TRUNCATE;
 721       } else {
 722         ExtOp = ISD::FP_EXTEND;
 723         TruncOp  = ISD::FP_ROUND;
 724       }
 725       // Promote each of the values to the new type.
 726       Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2);
 727       Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3);
 728       // Perform the larger operation, then round down.
 729       Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3);
 730       Result = DAG.getNode(TruncOp, Node->getValueType(0), Result);
 731       break;
 732     }
 733     }
 734     break;
 735   case ISD::SETCC:
 736     switch (getTypeAction(Node->getOperand(0).getValueType())) {
 737     case Legal:
 738       Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
 739       Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
 740       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 741         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 742                               Node->getValueType(0), Tmp1, Tmp2);
 743       break;
 744     case Promote:
 745       Tmp1 = PromoteOp(Node->getOperand(0));   // LHS
 746       Tmp2 = PromoteOp(Node->getOperand(1));   // RHS
 747
 748       // If this is an FP compare, the operands have already been extended.
 749       if (MVT::isInteger(Node->getOperand(0).getValueType())) {
 750         MVT::ValueType VT = Node->getOperand(0).getValueType();
 751         MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 752
 753         // Otherwise, we have to insert explicit sign or zero extends.  Note
 754         // that we could insert sign extends for ALL conditions, but zero extend
 755         // is cheaper on many machines (an AND instead of two shifts), so prefer
 756         // it.
 757         switch (cast<SetCCSDNode>(Node)->getCondition()) {
 758         default: assert(0 && "Unknown integer comparison!");
 759         case ISD::SETEQ:
 760         case ISD::SETNE:
 761         case ISD::SETUGE:
 762         case ISD::SETUGT:
 763         case ISD::SETULE:
 764         case ISD::SETULT:
 765           // ALL of these operations will work if we either sign or zero extend
 766           // the operands (including the unsigned comparisons!).  Zero extend is
 767           // usually a simpler/cheaper operation, so prefer it.
 768           Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
 769           Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
 770           break;
 771         case ISD::SETGE:
 772         case ISD::SETGT:
 773         case ISD::SETLT:
 774         case ISD::SETLE:
 775           Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
 776           Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT);
 777           break;
 778         }
 779
 780       }
 781       Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 782                             Node->getValueType(0), Tmp1, Tmp2);
 783       break;
 784     case Expand:
 785       SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
 786       ExpandOp(Node->getOperand(0), LHSLo, LHSHi);
 787       ExpandOp(Node->getOperand(1), RHSLo, RHSHi);
 788       switch (cast<SetCCSDNode>(Node)->getCondition()) {
 789       case ISD::SETEQ:
 790       case ISD::SETNE:
 791         if (RHSLo == RHSHi)
 792           if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
 793             if (RHSCST->isAllOnesValue()) {
 794               // Comparison to -1.
 795               Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
 796               Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 797                                     Node->getValueType(0), Tmp1, RHSLo);
 798               break;
 799             }
 800
 801         Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
 802         Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
 803         Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
 804         Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 805                               Node->getValueType(0), Tmp1,
 806                               DAG.getConstant(0, Tmp1.getValueType()));
 807         break;
 808       default:
 809         // If this is a comparison of the sign bit, just look at the top part.
 810         // X > -1,  x < 0
 811         if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(Node->getOperand(1)))
 812           if ((cast<SetCCSDNode>(Node)->getCondition() == ISD::SETLT &&
 813                CST->getValue() == 0) ||              // X < 0
 814               (cast<SetCCSDNode>(Node)->getCondition() == ISD::SETGT &&
 815                (CST->isAllOnesValue())))             // X > -1
 816             return DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 817                                 Node->getValueType(0), LHSHi, RHSHi);
 818
 819         // FIXME: This generated code sucks.
 820         ISD::CondCode LowCC;
 821         switch (cast<SetCCSDNode>(Node)->getCondition()) {
 822         default: assert(0 && "Unknown integer setcc!");
 823         case ISD::SETLT:
 824         case ISD::SETULT: LowCC = ISD::SETULT; break;
 825         case ISD::SETGT:
 826         case ISD::SETUGT: LowCC = ISD::SETUGT; break;
 827         case ISD::SETLE:
 828         case ISD::SETULE: LowCC = ISD::SETULE; break;
 829         case ISD::SETGE:
 830         case ISD::SETUGE: LowCC = ISD::SETUGE; break;
 831         }
 832
 833         // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
 834         // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
 835         // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
 836
 837         // NOTE: on targets without efficient SELECT of bools, we can always use
 838         // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
 839         Tmp1 = DAG.getSetCC(LowCC, Node->getValueType(0), LHSLo, RHSLo);
 840         Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
 841                             Node->getValueType(0), LHSHi, RHSHi);
 842         Result = DAG.getSetCC(ISD::SETEQ, Node->getValueType(0), LHSHi, RHSHi);
 843         Result = DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
 844                              Result, Tmp1, Tmp2);
 845         break;
 846       }
 847     }
 848     break;
 849
 850   case ISD::MEMSET:
 851   case ISD::MEMCPY:
 852   case ISD::MEMMOVE: {
 853     Tmp1 = LegalizeOp(Node->getOperand(0));      // Chain
 854     Tmp2 = LegalizeOp(Node->getOperand(1));      // Pointer
 855
 856     if (Node->getOpcode() == ISD::MEMSET) {      // memset = ubyte
 857       switch (getTypeAction(Node->getOperand(2).getValueType())) {
 858       case Expand: assert(0 && "Cannot expand a byte!");
 859       case Legal:
 860         Tmp3 = LegalizeOp(Node->getOperand(2));
 861         break;
 862       case Promote:
 863         Tmp3 = PromoteOp(Node->getOperand(2));
 864         break;
 865       }
 866     } else {
 867       Tmp3 = LegalizeOp(Node->getOperand(2));    // memcpy/move = pointer,
 868     }
 869
 870     SDOperand Tmp4;
 871     switch (getTypeAction(Node->getOperand(3).getValueType())) {
 872     case Expand: assert(0 && "Cannot expand this yet!");
 873     case Legal:
 874       Tmp4 = LegalizeOp(Node->getOperand(3));
 875       break;
 876     case Promote:
 877       Tmp4 = PromoteOp(Node->getOperand(3));
 878       break;
 879     }
 880
 881     SDOperand Tmp5;
 882     switch (getTypeAction(Node->getOperand(4).getValueType())) {  // uint
 883     case Expand: assert(0 && "Cannot expand this yet!");
 884     case Legal:
 885       Tmp5 = LegalizeOp(Node->getOperand(4));
 886       break;
 887     case Promote:
 888       Tmp5 = PromoteOp(Node->getOperand(4));
 889       break;
 890     }
 891
 892     switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
 893     default: assert(0 && "This action not implemented for this operation!");
 894     case TargetLowering::Legal:
 895       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 896           Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) ||
 897           Tmp5 != Node->getOperand(4)) {
 898         std::vector<SDOperand> Ops;
 899         Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
 900         Ops.push_back(Tmp4); Ops.push_back(Tmp5);
 901         Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
 902       }
 903       break;
 904     case TargetLowering::Expand: {
 905       // Otherwise, the target does not support this operation.  Lower the
 906       // operation to an explicit libcall as appropriate.
 907       MVT::ValueType IntPtr = TLI.getPointerTy();
 908       const Type *IntPtrTy = TLI.getTargetData().getIntPtrType();
 909       std::vector<std::pair<SDOperand, const Type*> > Args;
 910
 911       const char *FnName = 0;
 912       if (Node->getOpcode() == ISD::MEMSET) {
 913         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
 914         // Extend the ubyte argument to be an int value for the call.
 915         Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
 916         Args.push_back(std::make_pair(Tmp3, Type::IntTy));
 917         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
 918
 919         FnName = "memset";
 920       } else if (Node->getOpcode() == ISD::MEMCPY ||
 921                  Node->getOpcode() == ISD::MEMMOVE) {
 922         Args.push_back(std::make_pair(Tmp2, IntPtrTy));
 923         Args.push_back(std::make_pair(Tmp3, IntPtrTy));
 924         Args.push_back(std::make_pair(Tmp4, IntPtrTy));
 925         FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
 926       } else {
 927         assert(0 && "Unknown op!");
 928       }
 929
 930       std::pair<SDOperand,SDOperand> CallResult =
 931         TLI.LowerCallTo(Tmp1, Type::VoidTy, false, 0,
 932                         DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
 933       Result = LegalizeOp(CallResult.second);
 934       break;
 935     }
 936     case TargetLowering::Custom:
 937       std::vector<SDOperand> Ops;
 938       Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
 939       Ops.push_back(Tmp4); Ops.push_back(Tmp5);
 940       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
 941       Result = TLI.LowerOperation(Result);
 942       Result = LegalizeOp(Result);
 943       break;
 944     }
 945     break;
 946   }
 947
 948   case ISD::READPORT:
 949     Tmp1 = LegalizeOp(Node->getOperand(0));
 950     Tmp2 = LegalizeOp(Node->getOperand(1));
 951
 952     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 953       Result = DAG.getNode(ISD::READPORT, Node->getValueType(0), Tmp1, Tmp2);
 954     else
 955       Result = SDOperand(Node, 0);
 956     // Since these produce two values, make sure to remember that we legalized
 957     // both of them.
 958     AddLegalizedOperand(SDOperand(Node, 0), Result);
 959     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 960     return Result.getValue(Op.ResNo);
 961   case ISD::WRITEPORT:
 962     Tmp1 = LegalizeOp(Node->getOperand(0));
 963     Tmp2 = LegalizeOp(Node->getOperand(1));
 964     Tmp3 = LegalizeOp(Node->getOperand(2));
 965     if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
 966         Tmp3 != Node->getOperand(2))
 967       Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3);
 968     break;
 969
 970   case ISD::READIO:
 971     Tmp1 = LegalizeOp(Node->getOperand(0));
 972     Tmp2 = LegalizeOp(Node->getOperand(1));
 973
 974     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
 975     case TargetLowering::Custom:
 976     default: assert(0 && "This action not implemented for this operation!");
 977     case TargetLowering::Legal:
 978       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
 979         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0),
 980                              Tmp1, Tmp2);
 981       else
 982         Result = SDOperand(Node, 0);
 983       break;
 984     case TargetLowering::Expand:
 985       // Replace this with a load from memory.
 986       Result = DAG.getLoad(Node->getValueType(0), Node->getOperand(0),
 987                            Node->getOperand(1), DAG.getSrcValue(NULL));
 988       Result = LegalizeOp(Result);
 989       break;
 990     }
 991
 992     // Since these produce two values, make sure to remember that we legalized
 993     // both of them.
 994     AddLegalizedOperand(SDOperand(Node, 0), Result);
 995     AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
 996     return Result.getValue(Op.ResNo);
 997
 998   case ISD::WRITEIO:
 999     Tmp1 = LegalizeOp(Node->getOperand(0));
1000     Tmp2 = LegalizeOp(Node->getOperand(1));
1001     Tmp3 = LegalizeOp(Node->getOperand(2));
1002
1003     switch (TLI.getOperationAction(Node->getOpcode(),
1004                                    Node->getOperand(1).getValueType())) {
1005     case TargetLowering::Custom:
1006     default: assert(0 && "This action not implemented for this operation!");
1007     case TargetLowering::Legal:
1008       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1009           Tmp3 != Node->getOperand(2))
1010         Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3);
1011       break;
1012     case TargetLowering::Expand:
1013       // Replace this with a store to memory.
1014       Result = DAG.getNode(ISD::STORE, MVT::Other, Node->getOperand(0),
1015                            Node->getOperand(1), Node->getOperand(2),
1016                            DAG.getSrcValue(NULL));
1017       Result = LegalizeOp(Result);
1018       break;
1019     }
1020     break;
1021
1022   case ISD::ADD_PARTS:
1023   case ISD::SUB_PARTS:
1024   case ISD::SHL_PARTS:
1025   case ISD::SRA_PARTS:
1026   case ISD::SRL_PARTS: {
1027     std::vector<SDOperand> Ops;
1028     bool Changed = false;
1029     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
1030       Ops.push_back(LegalizeOp(Node->getOperand(i)));
1031       Changed |= Ops.back() != Node->getOperand(i);
1032     }
1033     if (Changed)
1034       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops);
1035
1036     // Since these produce multiple values, make sure to remember that we
1037     // legalized all of them.
1038     for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
1039       AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
1040     return Result.getValue(Op.ResNo);
1041   }
1042
1043     // Binary operators
1044   case ISD::ADD:
1045   case ISD::SUB:
1046   case ISD::MUL:
1047   case ISD::MULHS:
1048   case ISD::MULHU:
1049   case ISD::UDIV:
1050   case ISD::SDIV:
1051   case ISD::AND:
1052   case ISD::OR:
1053   case ISD::XOR:
1054   case ISD::SHL:
1055   case ISD::SRL:
1056   case ISD::SRA:
1057     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
1058     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
1059     if (Tmp1 != Node->getOperand(0) ||
1060         Tmp2 != Node->getOperand(1))
1061       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2);
1062     break;
1063
1064   case ISD::UREM:
1065   case ISD::SREM:
1066     Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
1067     Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
1068     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1069     case TargetLowering::Legal:
1070       if (Tmp1 != Node->getOperand(0) ||
1071           Tmp2 != Node->getOperand(1))
1072         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
1073                              Tmp2);
1074       break;
1075     case TargetLowering::Promote:
1076     case TargetLowering::Custom:
1077       assert(0 && "Cannot promote/custom handle this yet!");
1078     case TargetLowering::Expand: {
1079       MVT::ValueType VT = Node->getValueType(0);
1080       unsigned Opc = (Node->getOpcode() == ISD::UREM) ? ISD::UDIV : ISD::SDIV;
1081       Result = DAG.getNode(Opc, VT, Tmp1, Tmp2);
1082       Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2);
1083       Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result);
1084       }
1085       break;
1086     }
1087     break;
1088
1089   case ISD::CTPOP:
1090   case ISD::CTTZ:
1091   case ISD::CTLZ:
1092     Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
1093     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1094     case TargetLowering::Legal:
1095       if (Tmp1 != Node->getOperand(0))
1096         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1097       break;
1098     case TargetLowering::Promote: {
1099       MVT::ValueType OVT = Tmp1.getValueType();
1100       MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
1101
1102       // Zero extend the argument.
1103       Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
1104       // Perform the larger operation, then subtract if needed.
1105       Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1106       switch(Node->getOpcode())
1107       {
1108       case ISD::CTPOP:
1109         Result = Tmp1;
1110         break;
1111       case ISD::CTTZ:
1112         //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
1113         Tmp2 = DAG.getSetCC(ISD::SETEQ, TLI.getSetCCResultTy(), Tmp1,
1114                             DAG.getConstant(getSizeInBits(NVT), NVT));
1115         Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
1116                            DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1);
1117         break;
1118       case ISD::CTLZ:
1119         //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
1120         Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
1121                              DAG.getConstant(getSizeInBits(NVT) -
1122                                              getSizeInBits(OVT), NVT));
1123         break;
1124       }
1125       break;
1126     }
1127     case TargetLowering::Custom:
1128       assert(0 && "Cannot custom handle this yet!");
1129     case TargetLowering::Expand:
1130       switch(Node->getOpcode())
1131       {
1132       case ISD::CTPOP: {
1133         static const uint64_t mask[6] = {
1134           0x5555555555555555ULL, 0x3333333333333333ULL,
1135           0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
1136           0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
1137         };
1138         MVT::ValueType VT = Tmp1.getValueType();
1139         MVT::ValueType ShVT = TLI.getShiftAmountTy();
1140         unsigned len = getSizeInBits(VT);
1141         for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
1142           //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
1143           Tmp2 = DAG.getConstant(mask[i], VT);
1144           Tmp3 = DAG.getConstant(1ULL << i, ShVT);
1145           Tmp1 = DAG.getNode(ISD::ADD, VT,
1146                              DAG.getNode(ISD::AND, VT, Tmp1, Tmp2),
1147                              DAG.getNode(ISD::AND, VT,
1148                                          DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3),
1149                                          Tmp2));
1150         }
1151         Result = Tmp1;
1152         break;
1153       }
1154       case ISD::CTLZ: {
1155         /* for now, we do this:
1156            x = x | (x >> 1);
1157            x = x | (x >> 2);
1158            ...
1159            x = x | (x >>16);
1160            x = x | (x >>32); // for 64-bit input
1161            return popcount(~x);
1162
1163            but see also: http://www.hackersdelight.org/HDcode/nlz.cc */
1164         MVT::ValueType VT = Tmp1.getValueType();
1165         MVT::ValueType ShVT = TLI.getShiftAmountTy();
1166         unsigned len = getSizeInBits(VT);
1167         for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
1168           Tmp3 = DAG.getConstant(1ULL << i, ShVT);
1169           Tmp1 = DAG.getNode(ISD::OR, VT, Tmp1,
1170                              DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3));
1171         }
1172         Tmp3 = DAG.getNode(ISD::XOR, VT, Tmp1, DAG.getConstant(~0ULL, VT));
1173         Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3));
1174         break;
1175       }
1176       case ISD::CTTZ: {
1177         // for now, we use: { return popcount(~x & (x - 1)); }
1178         // unless the target has ctlz but not ctpop, in which case we use:
1179         // { return 32 - nlz(~x & (x-1)); }
1180         // see also http://www.hackersdelight.org/HDcode/ntz.cc
1181         MVT::ValueType VT = Tmp1.getValueType();
1182         Tmp2 = DAG.getConstant(~0ULL, VT);
1183         Tmp3 = DAG.getNode(ISD::AND, VT,
1184                            DAG.getNode(ISD::XOR, VT, Tmp1, Tmp2),
1185                            DAG.getNode(ISD::SUB, VT, Tmp1,
1186                                        DAG.getConstant(1, VT)));
1187         // If ISD::CTLZ is legal and CTPOP isn't, then do that instead
1188         if (TLI.getOperationAction(ISD::CTPOP, VT) != TargetLowering::Legal &&
1189             TLI.getOperationAction(ISD::CTLZ, VT) == TargetLowering::Legal) {
1190           Result = LegalizeOp(DAG.getNode(ISD::SUB, VT,
1191                                         DAG.getConstant(getSizeInBits(VT), VT),
1192                                         DAG.getNode(ISD::CTLZ, VT, Tmp3)));
1193         } else {
1194           Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3));
1195         }
1196         break;
1197       }
1198       default:
1199         assert(0 && "Cannot expand this yet!");
1200         break;
1201       }
1202       break;
1203     }
1204     break;
1205
1206     // Unary operators
1207   case ISD::FABS:
1208   case ISD::FNEG:
1209   case ISD::FSQRT:
1210   case ISD::FSIN:
1211   case ISD::FCOS:
1212     Tmp1 = LegalizeOp(Node->getOperand(0));
1213     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1214     case TargetLowering::Legal:
1215       if (Tmp1 != Node->getOperand(0))
1216         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1217       break;
1218     case TargetLowering::Promote:
1219     case TargetLowering::Custom:
1220       assert(0 && "Cannot promote/custom handle this yet!");
1221     case TargetLowering::Expand:
1222       switch(Node->getOpcode()) {
1223       case ISD::FNEG: {
1224         // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
1225         Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0));
1226         Result = LegalizeOp(DAG.getNode(ISD::SUB, Node->getValueType(0),
1227                                         Tmp2, Tmp1));
1228         break;
1229       }
1230       case ISD::FABS: {
1231         // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
1232         MVT::ValueType VT = Node->getValueType(0);
1233         Tmp2 = DAG.getConstantFP(0.0, VT);
1234         Tmp2 = DAG.getSetCC(ISD::SETUGT, TLI.getSetCCResultTy(), Tmp1, Tmp2);
1235         Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1);
1236         Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3);
1237         Result = LegalizeOp(Result);
1238         break;
1239       }
1240       case ISD::FSQRT:
1241       case ISD::FSIN:
1242       case ISD::FCOS: {
1243         MVT::ValueType VT = Node->getValueType(0);
1244         Type *T = VT == MVT::f32 ? Type::FloatTy : Type::DoubleTy;
1245         const char *FnName = 0;
1246         switch(Node->getOpcode()) {
1247         case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break;
1248         case ISD::FSIN:  FnName = VT == MVT::f32 ? "sinf"  : "sin"; break;
1249         case ISD::FCOS:  FnName = VT == MVT::f32 ? "cosf"  : "cos"; break;
1250         default: assert(0 && "Unreachable!");
1251         }
1252         std::vector<std::pair<SDOperand, const Type*> > Args;
1253         Args.push_back(std::make_pair(Tmp1, T));
1254         // FIXME: should use ExpandLibCall!
1255         std::pair<SDOperand,SDOperand> CallResult =
1256           TLI.LowerCallTo(DAG.getEntryNode(), T, false, 0,
1257                           DAG.getExternalSymbol(FnName, VT), Args, DAG);
1258         Result = LegalizeOp(CallResult.first);
1259         break;
1260       }
1261       default:
1262         assert(0 && "Unreachable!");
1263       }
1264       break;
1265     }
1266     break;
1267
1268     // Conversion operators.  The source and destination have different types.
1269   case ISD::ZERO_EXTEND:
1270   case ISD::SIGN_EXTEND:
1271   case ISD::TRUNCATE:
1272   case ISD::FP_EXTEND:
1273   case ISD::FP_ROUND:
1274   case ISD::FP_TO_SINT:
1275   case ISD::FP_TO_UINT:
1276   case ISD::SINT_TO_FP:
1277   case ISD::UINT_TO_FP:
1278     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1279     case Legal:
1280       Tmp1 = LegalizeOp(Node->getOperand(0));
1281       if (Tmp1 != Node->getOperand(0))
1282         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1283       break;
1284     case Expand:
1285       if (Node->getOpcode() == ISD::SINT_TO_FP ||
1286           Node->getOpcode() == ISD::UINT_TO_FP) {
1287         Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP,
1288                                Node->getValueType(0), Node->getOperand(0));
1289         break;
1290       } else if (Node->getOpcode() == ISD::TRUNCATE) {
1291         // In the expand case, we must be dealing with a truncate, because
1292         // otherwise the result would be larger than the source.
1293         ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
1294
1295         // Since the result is legal, we should just be able to truncate the low
1296         // part of the source.
1297         Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
1298         break;
1299       }
1300       assert(0 && "Shouldn't need to expand other operators here!");
1301
1302     case Promote:
1303       switch (Node->getOpcode()) {
1304       case ISD::ZERO_EXTEND:
1305         Result = PromoteOp(Node->getOperand(0));
1306         // NOTE: Any extend would work here...
1307         Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
1308         Result = DAG.getZeroExtendInReg(Result,
1309                                         Node->getOperand(0).getValueType());
1310         break;
1311       case ISD::SIGN_EXTEND:
1312         Result = PromoteOp(Node->getOperand(0));
1313         // NOTE: Any extend would work here...
1314         Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
1315         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1316                              Result, Node->getOperand(0).getValueType());
1317         break;
1318       case ISD::TRUNCATE:
1319         Result = PromoteOp(Node->getOperand(0));
1320         Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
1321         break;
1322       case ISD::FP_EXTEND:
1323         Result = PromoteOp(Node->getOperand(0));
1324         if (Result.getValueType() != Op.getValueType())
1325           // Dynamically dead while we have only 2 FP types.
1326           Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
1327         break;
1328       case ISD::FP_ROUND:
1329       case ISD::FP_TO_SINT:
1330       case ISD::FP_TO_UINT:
1331         Result = PromoteOp(Node->getOperand(0));
1332         Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
1333         break;
1334       case ISD::SINT_TO_FP:
1335         Result = PromoteOp(Node->getOperand(0));
1336         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1337                              Result, Node->getOperand(0).getValueType());
1338         Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result);
1339         break;
1340       case ISD::UINT_TO_FP:
1341         Result = PromoteOp(Node->getOperand(0));
1342         Result = DAG.getZeroExtendInReg(Result,
1343                                         Node->getOperand(0).getValueType());
1344         Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result);
1345         break;
1346       }
1347     }
1348     break;
1349   case ISD::FP_ROUND_INREG:
1350   case ISD::SIGN_EXTEND_INREG: {
1351     Tmp1 = LegalizeOp(Node->getOperand(0));
1352     MVT::ValueType ExtraVT = cast<MVTSDNode>(Node)->getExtraValueType();
1353
1354     // If this operation is not supported, convert it to a shl/shr or load/store
1355     // pair.
1356     switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
1357     default: assert(0 && "This action not supported for this op yet!");
1358     case TargetLowering::Legal:
1359       if (Tmp1 != Node->getOperand(0))
1360         Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
1361                              ExtraVT);
1362       break;
1363     case TargetLowering::Expand:
1364       // If this is an integer extend and shifts are supported, do that.
1365       if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
1366         // NOTE: we could fall back on load/store here too for targets without
1367         // SAR.  However, it is doubtful that any exist.
1368         unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
1369                             MVT::getSizeInBits(ExtraVT);
1370         SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy());
1371         Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
1372                              Node->getOperand(0), ShiftCst);
1373         Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
1374                              Result, ShiftCst);
1375       } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
1376         // The only way we can lower this is to turn it into a STORETRUNC,
1377         // EXTLOAD pair, targetting a temporary location (a stack slot).
1378
1379         // NOTE: there is a choice here between constantly creating new stack
1380         // slots and always reusing the same one.  We currently always create
1381         // new ones, as reuse may inhibit scheduling.
1382         const Type *Ty = MVT::getTypeForValueType(ExtraVT);
1383         unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty);
1384         unsigned Align  = TLI.getTargetData().getTypeAlignment(Ty);
1385         MachineFunction &MF = DAG.getMachineFunction();
1386         int SSFI =
1387           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
1388         SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
1389         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
1390                              Node->getOperand(0), StackSlot,
1391                              DAG.getSrcValue(NULL), ExtraVT);
1392         Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0),
1393                              Result, StackSlot, DAG.getSrcValue(NULL), ExtraVT);
1394       } else {
1395         assert(0 && "Unknown op");
1396       }
1397       Result = LegalizeOp(Result);
1398       break;
1399     }
1400     break;
1401   }
1402   }
1403
1404   // Note that LegalizeOp may be reentered even from single-use nodes, which
1405   // means that we always must cache transformed nodes.
1406   AddLegalizedOperand(Op, Result);
1407   return Result;
1408 }
1409
1410 /// PromoteOp - Given an operation that produces a value in an invalid type,
1411 /// promote it to compute the value into a larger type.  The produced value will
1412 /// have the correct bits for the low portion of the register, but no guarantee
1413 /// is made about the top bits: it may be zero, sign-extended, or garbage.
1414 SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
1415   MVT::ValueType VT = Op.getValueType();
1416   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1417   assert(getTypeAction(VT) == Promote &&
1418          "Caller should expand or legalize operands that are not promotable!");
1419   assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
1420          "Cannot promote to smaller type!");
1421
1422   SDOperand Tmp1, Tmp2, Tmp3;
1423
1424   SDOperand Result;
1425   SDNode *Node = Op.Val;
1426
1427   if (!Node->hasOneUse()) {
1428     std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
1429     if (I != PromotedNodes.end()) return I->second;
1430   } else {
1431     assert(!PromotedNodes.count(Op) && "Repromoted this node??");
1432   }
1433
1434   // Promotion needs an optimization step to clean up after it, and is not
1435   // careful to avoid operations the target does not support.  Make sure that
1436   // all generated operations are legalized in the next iteration.
1437   NeedsAnotherIteration = true;
1438
1439   switch (Node->getOpcode()) {
1440   default:
1441     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
1442     assert(0 && "Do not know how to promote this operator!");
1443     abort();
1444   case ISD::UNDEF:
1445     Result = DAG.getNode(ISD::UNDEF, NVT);
1446     break;
1447   case ISD::Constant:
1448     Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
1449     assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
1450     break;
1451   case ISD::ConstantFP:
1452     Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
1453     assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
1454     break;
1455   case ISD::CopyFromReg:
1456     Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), NVT,
1457                                 Node->getOperand(0));
1458     // Remember that we legalized the chain.
1459     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1460     break;
1461
1462   case ISD::SETCC:
1463     assert(getTypeAction(TLI.getSetCCResultTy()) == Legal &&
1464            "SetCC type is not legal??");
1465     Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
1466                           TLI.getSetCCResultTy(), Node->getOperand(0),
1467                           Node->getOperand(1));
1468     Result = LegalizeOp(Result);
1469     break;
1470
1471   case ISD::TRUNCATE:
1472     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1473     case Legal:
1474       Result = LegalizeOp(Node->getOperand(0));
1475       assert(Result.getValueType() >= NVT &&
1476              "This truncation doesn't make sense!");
1477       if (Result.getValueType() > NVT)    // Truncate to NVT instead of VT
1478         Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
1479       break;
1480     case Promote:
1481       // The truncation is not required, because we don't guarantee anything
1482       // about high bits anyway.
1483       Result = PromoteOp(Node->getOperand(0));
1484       break;
1485     case Expand:
1486       ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
1487       // Truncate the low part of the expanded value to the result type
1488       Result = DAG.getNode(ISD::TRUNCATE, VT, Tmp1);
1489     }
1490     break;
1491   case ISD::SIGN_EXTEND:
1492   case ISD::ZERO_EXTEND:
1493     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1494     case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
1495     case Legal:
1496       // Input is legal?  Just do extend all the way to the larger type.
1497       Result = LegalizeOp(Node->getOperand(0));
1498       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1499       break;
1500     case Promote:
1501       // Promote the reg if it's smaller.
1502       Result = PromoteOp(Node->getOperand(0));
1503       // The high bits are not guaranteed to be anything.  Insert an extend.
1504       if (Node->getOpcode() == ISD::SIGN_EXTEND)
1505         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
1506                              Node->getOperand(0).getValueType());
1507       else
1508         Result = DAG.getZeroExtendInReg(Result,
1509                                         Node->getOperand(0).getValueType());
1510       break;
1511     }
1512     break;
1513
1514   case ISD::FP_EXTEND:
1515     assert(0 && "Case not implemented.  Dynamically dead with 2 FP types!");
1516   case ISD::FP_ROUND:
1517     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1518     case Expand: assert(0 && "BUG: Cannot expand FP regs!");
1519     case Promote:  assert(0 && "Unreachable with 2 FP types!");
1520     case Legal:
1521       // Input is legal?  Do an FP_ROUND_INREG.
1522       Result = LegalizeOp(Node->getOperand(0));
1523       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1524       break;
1525     }
1526     break;
1527
1528   case ISD::SINT_TO_FP:
1529   case ISD::UINT_TO_FP:
1530     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1531     case Legal:
1532       Result = LegalizeOp(Node->getOperand(0));
1533       // No extra round required here.
1534       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1535       break;
1536
1537     case Promote:
1538       Result = PromoteOp(Node->getOperand(0));
1539       if (Node->getOpcode() == ISD::SINT_TO_FP)
1540         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1541                              Result, Node->getOperand(0).getValueType());
1542       else
1543         Result = DAG.getZeroExtendInReg(Result,
1544                                         Node->getOperand(0).getValueType());
1545       // No extra round required here.
1546       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1547       break;
1548     case Expand:
1549       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT,
1550                              Node->getOperand(0));
1551       // Round if we cannot tolerate excess precision.
1552       if (NoExcessFPPrecision)
1553         Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1554       break;
1555     }
1556     break;
1557
1558   case ISD::FP_TO_SINT:
1559   case ISD::FP_TO_UINT:
1560     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1561     case Legal:
1562       Tmp1 = LegalizeOp(Node->getOperand(0));
1563       break;
1564     case Promote:
1565       // The input result is prerounded, so we don't have to do anything
1566       // special.
1567       Tmp1 = PromoteOp(Node->getOperand(0));
1568       break;
1569     case Expand:
1570       assert(0 && "not implemented");
1571     }
1572     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1573     break;
1574
1575   case ISD::FABS:
1576   case ISD::FNEG:
1577     Tmp1 = PromoteOp(Node->getOperand(0));
1578     assert(Tmp1.getValueType() == NVT);
1579     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1580     // NOTE: we do not have to do any extra rounding here for
1581     // NoExcessFPPrecision, because we know the input will have the appropriate
1582     // precision, and these operations don't modify precision at all.
1583     break;
1584
1585   case ISD::FSQRT:
1586   case ISD::FSIN:
1587   case ISD::FCOS:
1588     Tmp1 = PromoteOp(Node->getOperand(0));
1589     assert(Tmp1.getValueType() == NVT);
1590     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1591     if(NoExcessFPPrecision)
1592       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1593     break;
1594
1595   case ISD::AND:
1596   case ISD::OR:
1597   case ISD::XOR:
1598   case ISD::ADD:
1599   case ISD::SUB:
1600   case ISD::MUL:
1601     // The input may have strange things in the top bits of the registers, but
1602     // these operations don't care.  They may have wierd bits going out, but
1603     // that too is okay if they are integer operations.
1604     Tmp1 = PromoteOp(Node->getOperand(0));
1605     Tmp2 = PromoteOp(Node->getOperand(1));
1606     assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
1607     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1608
1609     // However, if this is a floating point operation, they will give excess
1610     // precision that we may not be able to tolerate.  If we DO allow excess
1611     // precision, just leave it, otherwise excise it.
1612     // FIXME: Why would we need to round FP ops more than integer ones?
1613     //     Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
1614     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
1615       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1616     break;
1617
1618   case ISD::SDIV:
1619   case ISD::SREM:
1620     // These operators require that their input be sign extended.
1621     Tmp1 = PromoteOp(Node->getOperand(0));
1622     Tmp2 = PromoteOp(Node->getOperand(1));
1623     if (MVT::isInteger(NVT)) {
1624       Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
1625       Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT);
1626     }
1627     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1628
1629     // Perform FP_ROUND: this is probably overly pessimistic.
1630     if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
1631       Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1632     break;
1633
1634   case ISD::UDIV:
1635   case ISD::UREM:
1636     // These operators require that their input be zero extended.
1637     Tmp1 = PromoteOp(Node->getOperand(0));
1638     Tmp2 = PromoteOp(Node->getOperand(1));
1639     assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
1640     Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
1641     Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
1642     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1643     break;
1644
1645   case ISD::SHL:
1646     Tmp1 = PromoteOp(Node->getOperand(0));
1647     Tmp2 = LegalizeOp(Node->getOperand(1));
1648     Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2);
1649     break;
1650   case ISD::SRA:
1651     // The input value must be properly sign extended.
1652     Tmp1 = PromoteOp(Node->getOperand(0));
1653     Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
1654     Tmp2 = LegalizeOp(Node->getOperand(1));
1655     Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2);
1656     break;
1657   case ISD::SRL:
1658     // The input value must be properly zero extended.
1659     Tmp1 = PromoteOp(Node->getOperand(0));
1660     Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
1661     Tmp2 = LegalizeOp(Node->getOperand(1));
1662     Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2);
1663     break;
1664   case ISD::LOAD:
1665     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
1666     Tmp2 = LegalizeOp(Node->getOperand(1));   // Legalize the pointer.
1667     // FIXME: When the DAG combiner exists, change this to use EXTLOAD!
1668     if (MVT::isInteger(NVT))
1669       Result = DAG.getNode(ISD::ZEXTLOAD, NVT, Tmp1, Tmp2, Node->getOperand(2),
1670                            VT);
1671     else
1672       Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, Node->getOperand(2),
1673                            VT);
1674
1675     // Remember that we legalized the chain.
1676     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1677     break;
1678   case ISD::SELECT:
1679     switch (getTypeAction(Node->getOperand(0).getValueType())) {
1680     case Expand: assert(0 && "It's impossible to expand bools");
1681     case Legal:
1682       Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition.
1683       break;
1684     case Promote:
1685       Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition.
1686       break;
1687     }
1688     Tmp2 = PromoteOp(Node->getOperand(1));   // Legalize the op0
1689     Tmp3 = PromoteOp(Node->getOperand(2));   // Legalize the op1
1690     Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3);
1691     break;
1692   case ISD::CALL: {
1693     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1694     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
1695
1696     std::vector<SDOperand> Ops;
1697     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i)
1698       Ops.push_back(LegalizeOp(Node->getOperand(i)));
1699
1700     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
1701            "Can only promote single result calls");
1702     std::vector<MVT::ValueType> RetTyVTs;
1703     RetTyVTs.reserve(2);
1704     RetTyVTs.push_back(NVT);
1705     RetTyVTs.push_back(MVT::Other);
1706     SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops);
1707     Result = SDOperand(NC, 0);
1708
1709     // Insert the new chain mapping.
1710     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1711     break;
1712   }
1713   case ISD::CTPOP:
1714   case ISD::CTTZ:
1715   case ISD::CTLZ:
1716     Tmp1 = Node->getOperand(0);
1717     //Zero extend the argument
1718     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
1719     // Perform the larger operation, then subtract if needed.
1720     Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1721     switch(Node->getOpcode())
1722     {
1723     case ISD::CTPOP:
1724       Result = Tmp1;
1725       break;
1726     case ISD::CTTZ:
1727       //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
1728       Tmp2 = DAG.getSetCC(ISD::SETEQ, MVT::i1, Tmp1,
1729                           DAG.getConstant(getSizeInBits(NVT), NVT));
1730       Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
1731                            DAG.getConstant(getSizeInBits(VT),NVT), Tmp1);
1732       break;
1733     case ISD::CTLZ:
1734       //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
1735       Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
1736                            DAG.getConstant(getSizeInBits(NVT) -
1737                                            getSizeInBits(VT), NVT));
1738       break;
1739     }
1740     break;
1741   }
1742
1743   assert(Result.Val && "Didn't set a result!");
1744   AddPromotedOperand(Op, Result);
1745   return Result;
1746 }
1747
1748 /// ExpandAddSub - Find a clever way to expand this add operation into
1749 /// subcomponents.
1750 void SelectionDAGLegalize::
1751 ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS,
1752               SDOperand &Lo, SDOperand &Hi) {
1753   // Expand the subcomponents.
1754   SDOperand LHSL, LHSH, RHSL, RHSH;
1755   ExpandOp(LHS, LHSL, LHSH);
1756   ExpandOp(RHS, RHSL, RHSH);
1757
1758   // FIXME: this should be moved to the dag combiner someday.
1759   if (NodeOp == ISD::ADD_PARTS || NodeOp == ISD::SUB_PARTS)
1760     if (LHSL.getValueType() == MVT::i32) {
1761       SDOperand LowEl;
1762       if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(LHSL))
1763         if (C->getValue() == 0)
1764           LowEl = RHSL;
1765       if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(RHSL))
1766         if (C->getValue() == 0)
1767           LowEl = LHSL;
1768       if (LowEl.Val) {
1769         // Turn this into an add/sub of the high part only.
1770         SDOperand HiEl =
1771           DAG.getNode(NodeOp == ISD::ADD_PARTS ? ISD::ADD : ISD::SUB,
1772                       LowEl.getValueType(), LHSH, RHSH);
1773         Lo = LowEl;
1774         Hi = HiEl;
1775         return;
1776       }
1777     }
1778
1779   std::vector<SDOperand> Ops;
1780   Ops.push_back(LHSL);
1781   Ops.push_back(LHSH);
1782   Ops.push_back(RHSL);
1783   Ops.push_back(RHSH);
1784   Lo = DAG.getNode(NodeOp, LHSL.getValueType(), Ops);
1785   Hi = Lo.getValue(1);
1786 }
1787
1788 void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp,
1789                                             SDOperand Op, SDOperand Amt,
1790                                             SDOperand &Lo, SDOperand &Hi) {
1791   // Expand the subcomponents.
1792   SDOperand LHSL, LHSH;
1793   ExpandOp(Op, LHSL, LHSH);
1794
1795   std::vector<SDOperand> Ops;
1796   Ops.push_back(LHSL);
1797   Ops.push_back(LHSH);
1798   Ops.push_back(Amt);
1799   Lo = DAG.getNode(NodeOp, LHSL.getValueType(), Ops);
1800   Hi = Lo.getValue(1);
1801 }
1802
1803
1804 /// ExpandShift - Try to find a clever way to expand this shift operation out to
1805 /// smaller elements.  If we can't find a way that is more efficient than a
1806 /// libcall on this target, return false.  Otherwise, return true with the
1807 /// low-parts expanded into Lo and Hi.
1808 bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
1809                                        SDOperand &Lo, SDOperand &Hi) {
1810   assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
1811          "This is not a shift!");
1812
1813   MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
1814   SDOperand ShAmt = LegalizeOp(Amt);
1815   MVT::ValueType ShTy = ShAmt.getValueType();
1816   unsigned VTBits = MVT::getSizeInBits(Op.getValueType());
1817   unsigned NVTBits = MVT::getSizeInBits(NVT);
1818
1819   // Handle the case when Amt is an immediate.  Other cases are currently broken
1820   // and are disabled.
1821   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) {
1822     unsigned Cst = CN->getValue();
1823     // Expand the incoming operand to be shifted, so that we have its parts
1824     SDOperand InL, InH;
1825     ExpandOp(Op, InL, InH);
1826     switch(Opc) {
1827     case ISD::SHL:
1828       if (Cst > VTBits) {
1829         Lo = DAG.getConstant(0, NVT);
1830         Hi = DAG.getConstant(0, NVT);
1831       } else if (Cst > NVTBits) {
1832         Lo = DAG.getConstant(0, NVT);
1833         Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy));
1834       } else if (Cst == NVTBits) {
1835         Lo = DAG.getConstant(0, NVT);
1836         Hi = InL;
1837       } else {
1838         Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy));
1839         Hi = DAG.getNode(ISD::OR, NVT,
1840            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)),
1841            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy)));
1842       }
1843       return true;
1844     case ISD::SRL:
1845       if (Cst > VTBits) {
1846         Lo = DAG.getConstant(0, NVT);
1847         Hi = DAG.getConstant(0, NVT);
1848       } else if (Cst > NVTBits) {
1849         Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy));
1850         Hi = DAG.getConstant(0, NVT);
1851       } else if (Cst == NVTBits) {
1852         Lo = InH;
1853         Hi = DAG.getConstant(0, NVT);
1854       } else {
1855         Lo = DAG.getNode(ISD::OR, NVT,
1856            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
1857            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
1858         Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy));
1859       }
1860       return true;
1861     case ISD::SRA:
1862       if (Cst > VTBits) {
1863         Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
1864                               DAG.getConstant(NVTBits-1, ShTy));
1865       } else if (Cst > NVTBits) {
1866         Lo = DAG.getNode(ISD::SRA, NVT, InH,
1867                            DAG.getConstant(Cst-NVTBits, ShTy));
1868         Hi = DAG.getNode(ISD::SRA, NVT, InH,
1869                               DAG.getConstant(NVTBits-1, ShTy));
1870       } else if (Cst == NVTBits) {
1871         Lo = InH;
1872         Hi = DAG.getNode(ISD::SRA, NVT, InH,
1873                               DAG.getConstant(NVTBits-1, ShTy));
1874       } else {
1875         Lo = DAG.getNode(ISD::OR, NVT,
1876            DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
1877            DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
1878         Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy));
1879       }
1880       return true;
1881     }
1882   }
1883   // FIXME: The following code for expanding shifts using ISD::SELECT is buggy,
1884   // so disable it for now.  Currently targets are handling this via SHL_PARTS
1885   // and friends.
1886   return false;
1887
1888   // If we have an efficient select operation (or if the selects will all fold
1889   // away), lower to some complex code, otherwise just emit the libcall.
1890   if (TLI.getOperationAction(ISD::SELECT, NVT) != TargetLowering::Legal &&
1891       !isa<ConstantSDNode>(Amt))
1892     return false;
1893
1894   SDOperand InL, InH;
1895   ExpandOp(Op, InL, InH);
1896   SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy,           // NAmt = 32-ShAmt
1897                                DAG.getConstant(NVTBits, ShTy), ShAmt);
1898
1899   // Compare the unmasked shift amount against 32.
1900   SDOperand Cond = DAG.getSetCC(ISD::SETGE, TLI.getSetCCResultTy(), ShAmt,
1901                                 DAG.getConstant(NVTBits, ShTy));
1902
1903   if (TLI.getShiftAmountFlavor() != TargetLowering::Mask) {
1904     ShAmt = DAG.getNode(ISD::AND, ShTy, ShAmt,             // ShAmt &= 31
1905                         DAG.getConstant(NVTBits-1, ShTy));
1906     NAmt  = DAG.getNode(ISD::AND, ShTy, NAmt,              // NAmt &= 31
1907                         DAG.getConstant(NVTBits-1, ShTy));
1908   }
1909
1910   if (Opc == ISD::SHL) {
1911     SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << Amt) | (Lo >> NAmt)
1912                                DAG.getNode(ISD::SHL, NVT, InH, ShAmt),
1913                                DAG.getNode(ISD::SRL, NVT, InL, NAmt));
1914     SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31
1915
1916     Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
1917     Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2);
1918   } else {
1919     SDOperand HiLoPart = DAG.getNode(ISD::SELECT, NVT,
1920                                      DAG.getSetCC(ISD::SETEQ,
1921                                                   TLI.getSetCCResultTy(), NAmt,
1922                                                   DAG.getConstant(32, ShTy)),
1923                                      DAG.getConstant(0, NVT),
1924                                      DAG.getNode(ISD::SHL, NVT, InH, NAmt));
1925     SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << NAmt) | (Lo >> Amt)
1926                                HiLoPart,
1927                                DAG.getNode(ISD::SRL, NVT, InL, ShAmt));
1928     SDOperand T2 = DAG.getNode(Opc, NVT, InH, ShAmt);  // T2 = InH >> ShAmt&31
1929
1930     SDOperand HiPart;
1931     if (Opc == ISD::SRA)
1932       HiPart = DAG.getNode(ISD::SRA, NVT, InH,
1933                            DAG.getConstant(NVTBits-1, ShTy));
1934     else
1935       HiPart = DAG.getConstant(0, NVT);
1936     Lo = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
1937     Hi = DAG.getNode(ISD::SELECT, NVT, Cond, HiPart, T2);
1938   }
1939   return true;
1940 }
1941
1942 /// FindLatestAdjCallStackDown - Scan up the dag to find the latest (highest
1943 /// NodeDepth) node that is an AdjCallStackDown operation and occurs later than
1944 /// Found.
1945 static void FindLatestAdjCallStackDown(SDNode *Node, SDNode *&Found) {
1946   if (Node->getNodeDepth() <= Found->getNodeDepth()) return;
1947
1948   // If we found an CALLSEQ_START, we already know this node occurs later
1949   // than the Found node. Just remember this node and return.
1950   if (Node->getOpcode() == ISD::CALLSEQ_START) {
1951     Found = Node;
1952     return;
1953   }
1954
1955   // Otherwise, scan the operands of Node to see if any of them is a call.
1956   assert(Node->getNumOperands() != 0 &&
1957          "All leaves should have depth equal to the entry node!");
1958   for (unsigned i = 0, e = Node->getNumOperands()-1; i != e; ++i)
1959     FindLatestAdjCallStackDown(Node->getOperand(i).Val, Found);
1960
1961   // Tail recurse for the last iteration.
1962   FindLatestAdjCallStackDown(Node->getOperand(Node->getNumOperands()-1).Val,
1963                              Found);
1964 }
1965
1966
1967 /// FindEarliestAdjCallStackUp - Scan down the dag to find the earliest (lowest
1968 /// NodeDepth) node that is an AdjCallStackUp operation and occurs more recent
1969 /// than Found.
1970 static void FindEarliestAdjCallStackUp(SDNode *Node, SDNode *&Found) {
1971   if (Found && Node->getNodeDepth() >= Found->getNodeDepth()) return;
1972
1973   // If we found an CALLSEQ_END, we already know this node occurs earlier
1974   // than the Found node. Just remember this node and return.
1975   if (Node->getOpcode() == ISD::CALLSEQ_END) {
1976     Found = Node;
1977     return;
1978   }
1979
1980   // Otherwise, scan the operands of Node to see if any of them is a call.
1981   SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
1982   if (UI == E) return;
1983   for (--E; UI != E; ++UI)
1984     FindEarliestAdjCallStackUp(*UI, Found);
1985
1986   // Tail recurse for the last iteration.
1987   FindEarliestAdjCallStackUp(*UI, Found);
1988 }
1989
1990 /// FindAdjCallStackUp - Given a chained node that is part of a call sequence,
1991 /// find the CALLSEQ_END node that terminates the call sequence.
1992 static SDNode *FindAdjCallStackUp(SDNode *Node) {
1993   if (Node->getOpcode() == ISD::CALLSEQ_END)
1994     return Node;
1995   if (Node->use_empty())
1996     return 0;   // No adjcallstackup
1997
1998   if (Node->hasOneUse())  // Simple case, only has one user to check.
1999     return FindAdjCallStackUp(*Node->use_begin());
2000
2001   SDOperand TheChain(Node, Node->getNumValues()-1);
2002   assert(TheChain.getValueType() == MVT::Other && "Is not a token chain!");
2003
2004   for (SDNode::use_iterator UI = Node->use_begin(),
2005          E = Node->use_end(); ; ++UI) {
2006     assert(UI != E && "Didn't find a user of the tokchain, no CALLSEQ_END!");
2007
2008     // Make sure to only follow users of our token chain.
2009     SDNode *User = *UI;
2010     for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
2011       if (User->getOperand(i) == TheChain)
2012         return FindAdjCallStackUp(User);
2013   }
2014   assert(0 && "Unreachable");
2015   abort();
2016 }
2017
2018 /// FindAdjCallStackDown - Given a chained node that is part of a call sequence,
2019 /// find the CALLSEQ_START node that initiates the call sequence.
2020 static SDNode *FindAdjCallStackDown(SDNode *Node) {
2021   assert(Node && "Didn't find adjcallstackdown for a call??");
2022   if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
2023
2024   assert(Node->getOperand(0).getValueType() == MVT::Other &&
2025          "Node doesn't have a token chain argument!");
2026   return FindAdjCallStackDown(Node->getOperand(0).Val);
2027 }
2028
2029
2030 /// FindInputOutputChains - If we are replacing an operation with a call we need
2031 /// to find the call that occurs before and the call that occurs after it to
2032 /// properly serialize the calls in the block.  The returned operand is the
2033 /// input chain value for the new call (e.g. the entry node or the previous
2034 /// call), and OutChain is set to be the chain node to update to point to the
2035 /// end of the call chain.
2036 static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain,
2037                                        SDOperand Entry) {
2038   SDNode *LatestAdjCallStackDown = Entry.Val;
2039   SDNode *LatestAdjCallStackUp = 0;
2040   FindLatestAdjCallStackDown(OpNode, LatestAdjCallStackDown);
2041   //std::cerr<<"Found node: "; LatestAdjCallStackDown->dump(); std::cerr <<"\n";
2042
2043   // It is possible that no ISD::CALLSEQ_START was found because there is no
2044   // previous call in the function.  LatestCallStackDown may in that case be
2045   // the entry node itself.  Do not attempt to find a matching CALLSEQ_END
2046   // unless LatestCallStackDown is an CALLSEQ_START.
2047   if (LatestAdjCallStackDown->getOpcode() == ISD::CALLSEQ_START)
2048     LatestAdjCallStackUp = FindAdjCallStackUp(LatestAdjCallStackDown);
2049   else
2050     LatestAdjCallStackUp = Entry.Val;
2051   assert(LatestAdjCallStackUp && "NULL return from FindAdjCallStackUp");
2052
2053   // Finally, find the first call that this must come before, first we find the
2054   // adjcallstackup that ends the call.
2055   OutChain = 0;
2056   FindEarliestAdjCallStackUp(OpNode, OutChain);
2057
2058   // If we found one, translate from the adj up to the adjdown.
2059   if (OutChain)
2060     OutChain = FindAdjCallStackDown(OutChain);
2061
2062   return SDOperand(LatestAdjCallStackUp, 0);
2063 }
2064
2065 /// SpliceCallInto - Given the result chain of a libcall (CallResult), and a
2066 void SelectionDAGLegalize::SpliceCallInto(const SDOperand &CallResult,
2067                                           SDNode *OutChain) {
2068   // Nothing to splice it into?
2069   if (OutChain == 0) return;
2070
2071   assert(OutChain->getOperand(0).getValueType() == MVT::Other);
2072   //OutChain->dump();
2073
2074   // Form a token factor node merging the old inval and the new inval.
2075   SDOperand InToken = DAG.getNode(ISD::TokenFactor, MVT::Other, CallResult,
2076                                   OutChain->getOperand(0));
2077   // Change the node to refer to the new token.
2078   OutChain->setAdjCallChain(InToken);
2079 }
2080
2081
2082 // ExpandLibCall - Expand a node into a call to a libcall.  If the result value
2083 // does not fit into a register, return the lo part and set the hi part to the
2084 // by-reg argument.  If it does fit into a single register, return the result
2085 // and leave the Hi part unset.
2086 SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node,
2087                                               SDOperand &Hi) {
2088   SDNode *OutChain;
2089   SDOperand InChain = FindInputOutputChains(Node, OutChain,
2090                                             DAG.getEntryNode());
2091   if (InChain.Val == 0)
2092     InChain = DAG.getEntryNode();
2093
2094   TargetLowering::ArgListTy Args;
2095   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
2096     MVT::ValueType ArgVT = Node->getOperand(i).getValueType();
2097     const Type *ArgTy = MVT::getTypeForValueType(ArgVT);
2098     Args.push_back(std::make_pair(Node->getOperand(i), ArgTy));
2099   }
2100   SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy());
2101
2102   // Splice the libcall in wherever FindInputOutputChains tells us to.
2103   const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0));
2104   std::pair<SDOperand,SDOperand> CallInfo =
2105     TLI.LowerCallTo(InChain, RetTy, false, 0, Callee, Args, DAG);
2106   SpliceCallInto(CallInfo.second, OutChain);
2107
2108   NeedsAnotherIteration = true;
2109
2110   switch (getTypeAction(CallInfo.first.getValueType())) {
2111   default: assert(0 && "Unknown thing");
2112   case Legal:
2113     return CallInfo.first;
2114   case Promote:
2115     assert(0 && "Cannot promote this yet!");
2116   case Expand:
2117     SDOperand Lo;
2118     ExpandOp(CallInfo.first, Lo, Hi);
2119     return Lo;
2120   }
2121 }
2122
2123
2124 /// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the
2125 /// destination type is legal.
2126 SDOperand SelectionDAGLegalize::
2127 ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) {
2128   assert(getTypeAction(DestTy) == Legal && "Destination type is not legal!");
2129   assert(getTypeAction(Source.getValueType()) == Expand &&
2130          "This is not an expansion!");
2131   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
2132
2133   if (!isSigned) {
2134     // If this is unsigned, and not supported, first perform the conversion to
2135     // signed, then adjust the result if the sign bit is set.
2136     SDOperand SignedConv = ExpandIntToFP(true, DestTy, Source);
2137
2138     assert(Source.getValueType() == MVT::i64 &&
2139            "This only works for 64-bit -> FP");
2140     // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
2141     // incoming integer is set.  To handle this, we dynamically test to see if
2142     // it is set, and, if so, add a fudge factor.
2143     SDOperand Lo, Hi;
2144     ExpandOp(Source, Lo, Hi);
2145
2146     SDOperand SignSet = DAG.getSetCC(ISD::SETLT, TLI.getSetCCResultTy(), Hi,
2147                                      DAG.getConstant(0, Hi.getValueType()));
2148     SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
2149     SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
2150                                       SignSet, Four, Zero);
2151     uint64_t FF = 0x5f800000ULL;
2152     if (TLI.isLittleEndian()) FF <<= 32;
2153     static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
2154
2155     MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
2156     SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(FudgeFactor),
2157                                           TLI.getPointerTy());
2158     CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
2159     SDOperand FudgeInReg;
2160     if (DestTy == MVT::f32)
2161       FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
2162                                DAG.getSrcValue(NULL));
2163     else {
2164       assert(DestTy == MVT::f64 && "Unexpected conversion");
2165       FudgeInReg = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
2166                                CPIdx, DAG.getSrcValue(NULL), MVT::f32);
2167     }
2168     return DAG.getNode(ISD::ADD, DestTy, SignedConv, FudgeInReg);
2169   }
2170
2171   // Expand the source, then glue it back together for the call.  We must expand
2172   // the source in case it is shared (this pass of legalize must traverse it).
2173   SDOperand SrcLo, SrcHi;
2174   ExpandOp(Source, SrcLo, SrcHi);
2175   Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi);
2176
2177   SDNode *OutChain = 0;
2178   SDOperand InChain = FindInputOutputChains(Source.Val, OutChain,
2179                                             DAG.getEntryNode());
2180   const char *FnName = 0;
2181   if (DestTy == MVT::f32)
2182     FnName = "__floatdisf";
2183   else {
2184     assert(DestTy == MVT::f64 && "Unknown fp value type!");
2185     FnName = "__floatdidf";
2186   }
2187
2188   SDOperand Callee = DAG.getExternalSymbol(FnName, TLI.getPointerTy());
2189
2190   TargetLowering::ArgListTy Args;
2191   const Type *ArgTy = MVT::getTypeForValueType(Source.getValueType());
2192
2193   Args.push_back(std::make_pair(Source, ArgTy));
2194
2195   // We don't care about token chains for libcalls.  We just use the entry
2196   // node as our input and ignore the output chain.  This allows us to place
2197   // calls wherever we need them to satisfy data dependences.
2198   const Type *RetTy = MVT::getTypeForValueType(DestTy);
2199
2200   std::pair<SDOperand,SDOperand> CallResult =
2201     TLI.LowerCallTo(InChain, RetTy, false, 0, Callee, Args, DAG);
2202
2203   SpliceCallInto(CallResult.second, OutChain);
2204   return CallResult.first;
2205 }
2206
2207
2208
2209 /// ExpandOp - Expand the specified SDOperand into its two component pieces
2210 /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
2211 /// LegalizeNodes map is filled in for any results that are not expanded, the
2212 /// ExpandedNodes map is filled in for any results that are expanded, and the
2213 /// Lo/Hi values are returned.
2214 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
2215   MVT::ValueType VT = Op.getValueType();
2216   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
2217   SDNode *Node = Op.Val;
2218   assert(getTypeAction(VT) == Expand && "Not an expanded type!");
2219   assert(MVT::isInteger(VT) && "Cannot expand FP values!");
2220   assert(MVT::isInteger(NVT) && NVT < VT &&
2221          "Cannot expand to FP value or to larger int value!");
2222
2223   // If there is more than one use of this, see if we already expanded it.
2224   // There is no use remembering values that only have a single use, as the map
2225   // entries will never be reused.
2226   if (!Node->hasOneUse()) {
2227     std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
2228       = ExpandedNodes.find(Op);
2229     if (I != ExpandedNodes.end()) {
2230       Lo = I->second.first;
2231       Hi = I->second.second;
2232       return;
2233     }
2234   } else {
2235     assert(!ExpandedNodes.count(Op) && "Re-expanding a node!");
2236   }
2237
2238   // Expanding to multiple registers needs to perform an optimization step, and
2239   // is not careful to avoid operations the target does not support.  Make sure
2240   // that all generated operations are legalized in the next iteration.
2241   NeedsAnotherIteration = true;
2242
2243   switch (Node->getOpcode()) {
2244   default:
2245     std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
2246     assert(0 && "Do not know how to expand this operator!");
2247     abort();
2248   case ISD::UNDEF:
2249     Lo = DAG.getNode(ISD::UNDEF, NVT);
2250     Hi = DAG.getNode(ISD::UNDEF, NVT);
2251     break;
2252   case ISD::Constant: {
2253     uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
2254     Lo = DAG.getConstant(Cst, NVT);
2255     Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
2256     break;
2257   }
2258
2259   case ISD::CopyFromReg: {
2260     unsigned Reg = cast<RegSDNode>(Node)->getReg();
2261     // Aggregate register values are always in consequtive pairs.
2262     Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0));
2263     Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1));
2264
2265     // Remember that we legalized the chain.
2266     AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
2267
2268     assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
2269     break;
2270   }
2271
2272   case ISD::BUILD_PAIR:
2273     // Legalize both operands.  FIXME: in the future we should handle the case
2274     // where the two elements are not legal.
2275     assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
2276     Lo = LegalizeOp(Node->getOperand(0));
2277     Hi = LegalizeOp(Node->getOperand(1));
2278     break;
2279
2280   case ISD::CTPOP:
2281     ExpandOp(Node->getOperand(0), Lo, Hi);
2282     Lo = DAG.getNode(ISD::ADD, NVT,          // ctpop(HL) -> ctpop(H)+ctpop(L)
2283                      DAG.getNode(ISD::CTPOP, NVT, Lo),
2284                      DAG.getNode(ISD::CTPOP, NVT, Hi));
2285     Hi = DAG.getConstant(0, NVT);
2286     break;
2287
2288   case ISD::CTLZ: {
2289     // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32)
2290     ExpandOp(Node->getOperand(0), Lo, Hi);
2291     SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
2292     SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
2293     SDOperand TopNotZero = DAG.getSetCC(ISD::SETNE, TLI.getSetCCResultTy(),
2294                                         HLZ, BitsC);
2295     SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo);
2296     LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC);
2297
2298     Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart);
2299     Hi = DAG.getConstant(0, NVT);
2300     break;
2301   }
2302
2303   case ISD::CTTZ: {
2304     // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32)
2305     ExpandOp(Node->getOperand(0), Lo, Hi);
2306     SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
2307     SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
2308     SDOperand BotNotZero = DAG.getSetCC(ISD::SETNE, TLI.getSetCCResultTy(),
2309                                         LTZ, BitsC);
2310     SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi);
2311     HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC);
2312
2313     Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart);
2314     Hi = DAG.getConstant(0, NVT);
2315     break;
2316   }
2317
2318   case ISD::LOAD: {
2319     SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
2320     SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2321     Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
2322
2323     // Increment the pointer to the other half.
2324     unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
2325     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
2326                       getIntPtrConstant(IncrementSize));
2327     //Is this safe?  declaring that the two parts of the split load
2328     //are from the same instruction?
2329     Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
2330
2331     // Build a factor node to remember that this load is independent of the
2332     // other one.
2333     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
2334                                Hi.getValue(1));
2335
2336     // Remember that we legalized the chain.
2337     AddLegalizedOperand(Op.getValue(1), TF);
2338     if (!TLI.isLittleEndian())
2339       std::swap(Lo, Hi);
2340     break;
2341   }
2342   case ISD::CALL: {
2343     SDOperand Chain  = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2344     SDOperand Callee = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
2345
2346     bool Changed = false;
2347     std::vector<SDOperand> Ops;
2348     for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
2349       Ops.push_back(LegalizeOp(Node->getOperand(i)));
2350       Changed |= Ops.back() != Node->getOperand(i);
2351     }
2352
2353     assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
2354            "Can only expand a call once so far, not i64 -> i16!");
2355
2356     std::vector<MVT::ValueType> RetTyVTs;
2357     RetTyVTs.reserve(3);
2358     RetTyVTs.push_back(NVT);
2359     RetTyVTs.push_back(NVT);
2360     RetTyVTs.push_back(MVT::Other);
2361     SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee, Ops);
2362     Lo = SDOperand(NC, 0);
2363     Hi = SDOperand(NC, 1);
2364
2365     // Insert the new chain mapping.
2366     AddLegalizedOperand(Op.getValue(1), Hi.getValue(2));
2367     break;
2368   }
2369   case ISD::AND:
2370   case ISD::OR:
2371   case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
2372     SDOperand LL, LH, RL, RH;
2373     ExpandOp(Node->getOperand(0), LL, LH);
2374     ExpandOp(Node->getOperand(1), RL, RH);
2375     Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
2376     Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
2377     break;
2378   }
2379   case ISD::SELECT: {
2380     SDOperand C, LL, LH, RL, RH;
2381
2382     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2383     case Expand: assert(0 && "It's impossible to expand bools");
2384     case Legal:
2385       C = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
2386       break;
2387     case Promote:
2388       C = PromoteOp(Node->getOperand(0));  // Promote the condition.
2389       break;
2390     }
2391     ExpandOp(Node->getOperand(1), LL, LH);
2392     ExpandOp(Node->getOperand(2), RL, RH);
2393     Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL);
2394     Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH);
2395     break;
2396   }
2397   case ISD::SIGN_EXTEND: {
2398     SDOperand In;
2399     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2400     case Expand: assert(0 && "expand-expand not implemented yet!");
2401     case Legal: In = LegalizeOp(Node->getOperand(0)); break;
2402     case Promote:
2403       In = PromoteOp(Node->getOperand(0));
2404       // Emit the appropriate sign_extend_inreg to get the value we want.
2405       In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(), In,
2406                        Node->getOperand(0).getValueType());
2407       break;
2408     }
2409
2410     // The low part is just a sign extension of the input (which degenerates to
2411     // a copy).
2412     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, In);
2413
2414     // The high part is obtained by SRA'ing all but one of the bits of the lo
2415     // part.
2416     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
2417     Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1,
2418                                                        TLI.getShiftAmountTy()));
2419     break;
2420   }
2421   case ISD::ZERO_EXTEND: {
2422     SDOperand In;
2423     switch (getTypeAction(Node->getOperand(0).getValueType())) {
2424     case Expand: assert(0 && "expand-expand not implemented yet!");
2425     case Legal: In = LegalizeOp(Node->getOperand(0)); break;
2426     case Promote:
2427       In = PromoteOp(Node->getOperand(0));
2428       // Emit the appropriate zero_extend_inreg to get the value we want.
2429       In = DAG.getZeroExtendInReg(In, Node->getOperand(0).getValueType());
2430       break;
2431     }
2432
2433     // The low part is just a zero extension of the input (which degenerates to
2434     // a copy).
2435     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, In);
2436
2437     // The high part is just a zero.
2438     Hi = DAG.getConstant(0, NVT);
2439     break;
2440   }
2441     // These operators cannot be expanded directly, emit them as calls to
2442     // library functions.
2443   case ISD::FP_TO_SINT:
2444     if (Node->getOperand(0).getValueType() == MVT::f32)
2445       Lo = ExpandLibCall("__fixsfdi", Node, Hi);
2446     else
2447       Lo = ExpandLibCall("__fixdfdi", Node, Hi);
2448     break;
2449   case ISD::FP_TO_UINT:
2450     if (Node->getOperand(0).getValueType() == MVT::f32)
2451       Lo = ExpandLibCall("__fixunssfdi", Node, Hi);
2452     else
2453       Lo = ExpandLibCall("__fixunsdfdi", Node, Hi);
2454     break;
2455
2456   case ISD::SHL:
2457     // If we can emit an efficient shift operation, do so now.
2458     if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
2459       break;
2460
2461     // If this target supports SHL_PARTS, use it.
2462     if (TLI.getOperationAction(ISD::SHL_PARTS, NVT) == TargetLowering::Legal) {
2463       ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), Node->getOperand(1),
2464                        Lo, Hi);
2465       break;
2466     }
2467
2468     // Otherwise, emit a libcall.
2469     Lo = ExpandLibCall("__ashldi3", Node, Hi);
2470     break;
2471
2472   case ISD::SRA:
2473     // If we can emit an efficient shift operation, do so now.
2474     if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
2475       break;
2476
2477     // If this target supports SRA_PARTS, use it.
2478     if (TLI.getOperationAction(ISD::SRA_PARTS, NVT) == TargetLowering::Legal) {
2479       ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), Node->getOperand(1),
2480                        Lo, Hi);
2481       break;
2482     }
2483
2484     // Otherwise, emit a libcall.
2485     Lo = ExpandLibCall("__ashrdi3", Node, Hi);
2486     break;
2487   case ISD::SRL:
2488     // If we can emit an efficient shift operation, do so now.
2489     if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
2490       break;
2491
2492     // If this target supports SRL_PARTS, use it.
2493     if (TLI.getOperationAction(ISD::SRL_PARTS, NVT) == TargetLowering::Legal) {
2494       ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), Node->getOperand(1),
2495                        Lo, Hi);
2496       break;
2497     }
2498
2499     // Otherwise, emit a libcall.
2500     Lo = ExpandLibCall("__lshrdi3", Node, Hi);
2501     break;
2502
2503   case ISD::ADD:
2504     ExpandByParts(ISD::ADD_PARTS, Node->getOperand(0), Node->getOperand(1),
2505                   Lo, Hi);
2506     break;
2507   case ISD::SUB:
2508     ExpandByParts(ISD::SUB_PARTS, Node->getOperand(0), Node->getOperand(1),
2509                   Lo, Hi);
2510     break;
2511   case ISD::MUL: {
2512     if (TLI.getOperationAction(ISD::MULHU, NVT) == TargetLowering::Legal) {
2513       SDOperand LL, LH, RL, RH;
2514       ExpandOp(Node->getOperand(0), LL, LH);
2515       ExpandOp(Node->getOperand(1), RL, RH);
2516       Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
2517       RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
2518       LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
2519       Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
2520       Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
2521       Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
2522     } else {
2523       Lo = ExpandLibCall("__muldi3" , Node, Hi); break;
2524     }
2525     break;
2526   }
2527   case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break;
2528   case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break;
2529   case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break;
2530   case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break;
2531   }
2532
2533   // Remember in a map if the values will be reused later.
2534   if (!Node->hasOneUse()) {
2535     bool isNew = ExpandedNodes.insert(std::make_pair(Op,
2536                                             std::make_pair(Lo, Hi))).second;
2537     assert(isNew && "Value already expanded?!?");
2538   }
2539 }
2540
2541
2542 // SelectionDAG::Legalize - This is the entry point for the file.
2543 //
2544 void SelectionDAG::Legalize() {
2545   /// run - This is the main entry point to this class.
2546   ///
2547   SelectionDAGLegalize(*this).Run();
2548 }
2549