lib/CodeGen/SelectionDAG/LegalizeDAGTypes.cpp

   1 //===-- LegalizeDAGTypes.cpp - Implement SelectionDAG::LegalizeTypes ------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner 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::LegalizeTypes method.  It transforms
  11 // an arbitrary well-formed SelectionDAG to only consist of legal types.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "legalize-types"
  16 #include "llvm/CodeGen/SelectionDAG.h"
  17 #include "llvm/Constants.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/Target/TargetLowering.h"
  20 #include "llvm/ADT/DenseMap.h"
  21 #include "llvm/Support/Compiler.h"
  22 #include "llvm/Support/Debug.h"
  23 using namespace llvm;
  24
  25 //===----------------------------------------------------------------------===//
  26 /// DAGTypeLegalizer - 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 VISIBILITY_HIDDEN DAGTypeLegalizer {
  39   TargetLowering &TLI;
  40   SelectionDAG &DAG;
  41
  42   // NodeIDFlags - This pass uses the NodeID on the SDNodes to hold information
  43   // about the state of the node.  The enum has all the values.
  44   enum NodeIDFlags {
  45     /// ReadyToProcess - All operands have been processed, so this node is ready
  46     /// to be handled.
  47     ReadyToProcess = 0,
  48
  49     /// NewNode - This is a new node that was created in the process of
  50     /// legalizing some other node.
  51     NewNode = -1,
  52
  53     /// Processed - This is a node that has already been processed.
  54     Processed = -2
  55
  56     // 1+ - This is a node which has this many unlegalized operands.
  57   };
  58
  59   enum LegalizeAction {
  60     Legal,      // The target natively supports this type.
  61     Promote,    // This type should be executed in a larger type.
  62     Expand      // This type should be split into two types of half the size.
  63   };
  64
  65   /// ValueTypeActions - This is a bitvector that contains two bits for each
  66   /// simple value type, where the two bits correspond to the LegalizeAction
  67   /// enum.  This can be queried with "getTypeAction(VT)".
  68   TargetLowering::ValueTypeActionImpl ValueTypeActions;
  69
  70   /// getTypeAction - Return how we should legalize values of this type, either
  71   /// it is already legal or we need to expand it into multiple registers of
  72   /// smaller integer type, or we need to promote it to a larger type.
  73   LegalizeAction getTypeAction(MVT::ValueType VT) const {
  74     return (LegalizeAction)ValueTypeActions.getTypeAction(VT);
  75   }
  76
  77   /// isTypeLegal - Return true if this type is legal on this target.
  78   ///
  79   bool isTypeLegal(MVT::ValueType VT) const {
  80     return getTypeAction(VT) == Legal;
  81   }
  82
  83   SDOperand getIntPtrConstant(uint64_t Val) {
  84     return DAG.getConstant(Val, TLI.getPointerTy());
  85   }
  86
  87   /// PromotedNodes - For nodes that are below legal width, and that have more
  88   /// than one use, this map indicates what promoted value to use.
  89   DenseMap<SDOperand, SDOperand> PromotedNodes;
  90
  91   /// ExpandedNodes - For nodes that need to be expanded this map indicates
  92   /// which operands are the expanded version of the input.
  93   DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
  94
  95   /// Worklist - This defines a worklist of nodes to process.  In order to be
  96   /// pushed onto this worklist, all operands of a node must have already been
  97   /// processed.
  98   SmallVector<SDNode*, 128> Worklist;
  99
 100 public:
 101   DAGTypeLegalizer(SelectionDAG &dag)
 102     : TLI(dag.getTargetLoweringInfo()), DAG(dag),
 103     ValueTypeActions(TLI.getValueTypeActions()) {
 104     assert(MVT::LAST_VALUETYPE <= 32 &&
 105            "Too many value types for ValueTypeActions to hold!");
 106   }
 107
 108   void run();
 109
 110 private:
 111   void MarkNewNodes(SDNode *N);
 112
 113   void ReplaceLegalValueWith(SDOperand From, SDOperand To);
 114
 115   SDOperand GetPromotedOp(SDOperand Op) {
 116     Op = PromotedNodes[Op];
 117     assert(Op.Val && "Operand wasn't promoted?");
 118     return Op;
 119   }
 120   void SetPromotedOp(SDOperand Op, SDOperand Result);
 121
 122   /// GetPromotedZExtOp - Get a promoted operand and zero extend it to the final
 123   /// size.
 124   SDOperand GetPromotedZExtOp(SDOperand Op) {
 125     MVT::ValueType OldVT = Op.getValueType();
 126     Op = GetPromotedOp(Op);
 127     return DAG.getZeroExtendInReg(Op, OldVT);
 128   }
 129
 130   void GetExpandedOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi);
 131   void SetExpandedOp(SDOperand Op, SDOperand Lo, SDOperand Hi);
 132
 133   // Common routines.
 134   SDOperand CreateStackStoreLoad(SDOperand Op, MVT::ValueType DestVT);
 135   SDOperand HandleMemIntrinsic(SDNode *N);
 136
 137   // Result Promotion.
 138   void PromoteResult(SDNode *N, unsigned ResNo);
 139   SDOperand PromoteResult_UNDEF(SDNode *N);
 140   SDOperand PromoteResult_Constant(SDNode *N);
 141   SDOperand PromoteResult_TRUNCATE(SDNode *N);
 142   SDOperand PromoteResult_INT_EXTEND(SDNode *N);
 143   SDOperand PromoteResult_FP_ROUND(SDNode *N);
 144   SDOperand PromoteResult_FP_TO_XINT(SDNode *N);
 145   SDOperand PromoteResult_SETCC(SDNode *N);
 146   SDOperand PromoteResult_LOAD(LoadSDNode *N);
 147   SDOperand PromoteResult_SimpleIntBinOp(SDNode *N);
 148   SDOperand PromoteResult_SHL(SDNode *N);
 149   SDOperand PromoteResult_SRA(SDNode *N);
 150   SDOperand PromoteResult_SRL(SDNode *N);
 151   SDOperand PromoteResult_SELECT   (SDNode *N);
 152   SDOperand PromoteResult_SELECT_CC(SDNode *N);
 153
 154   // Result Expansion.
 155   void ExpandResult(SDNode *N, unsigned ResNo);
 156   void ExpandResult_UNDEF      (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 157   void ExpandResult_Constant   (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 158   void ExpandResult_BUILD_PAIR (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 159   void ExpandResult_ANY_EXTEND (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 160   void ExpandResult_ZERO_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi);
 161   void ExpandResult_SIGN_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi);
 162   void ExpandResult_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi);
 163   void ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi);
 164   void ExpandResult_LOAD       (LoadSDNode *N, SDOperand &Lo, SDOperand &Hi);
 165
 166   void ExpandResult_Logical    (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 167   void ExpandResult_BSWAP      (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 168   void ExpandResult_ADDSUB     (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 169   void ExpandResult_ADDSUBC    (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 170   void ExpandResult_ADDSUBE    (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 171   void ExpandResult_SELECT     (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 172   void ExpandResult_SELECT_CC  (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 173   void ExpandResult_MUL        (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 174   void ExpandResult_Shift      (SDNode *N, SDOperand &Lo, SDOperand &Hi);
 175
 176   void ExpandShiftByConstant(SDNode *N, unsigned Amt,
 177                              SDOperand &Lo, SDOperand &Hi);
 178   bool ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi);
 179
 180   // Operand Promotion.
 181   bool PromoteOperand(SDNode *N, unsigned OperandNo);
 182   SDOperand PromoteOperand_ANY_EXTEND(SDNode *N);
 183   SDOperand PromoteOperand_ZERO_EXTEND(SDNode *N);
 184   SDOperand PromoteOperand_SIGN_EXTEND(SDNode *N);
 185   SDOperand PromoteOperand_TRUNCATE(SDNode *N);
 186   SDOperand PromoteOperand_FP_EXTEND(SDNode *N);
 187   SDOperand PromoteOperand_FP_ROUND(SDNode *N);
 188   SDOperand PromoteOperand_INT_TO_FP(SDNode *N);
 189   SDOperand PromoteOperand_SELECT(SDNode *N, unsigned OpNo);
 190   SDOperand PromoteOperand_BRCOND(SDNode *N, unsigned OpNo);
 191   SDOperand PromoteOperand_BR_CC(SDNode *N, unsigned OpNo);
 192   SDOperand PromoteOperand_STORE(StoreSDNode *N, unsigned OpNo);
 193
 194   void PromoteSetCCOperands(SDOperand &LHS,SDOperand &RHS, ISD::CondCode Code);
 195
 196   // Operand Expansion.
 197   bool ExpandOperand(SDNode *N, unsigned OperandNo);
 198   SDOperand ExpandOperand_TRUNCATE(SDNode *N);
 199   SDOperand ExpandOperand_BIT_CONVERT(SDNode *N);
 200   SDOperand ExpandOperand_UINT_TO_FP(SDOperand Source, MVT::ValueType DestTy);
 201   SDOperand ExpandOperand_SINT_TO_FP(SDOperand Source, MVT::ValueType DestTy);
 202   SDOperand ExpandOperand_EXTRACT_ELEMENT(SDNode *N);
 203   SDOperand ExpandOperand_SETCC(SDNode *N);
 204   SDOperand ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo);
 205
 206   void ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS,
 207                            ISD::CondCode &CCCode);
 208 };
 209 }  // end anonymous namespace
 210
 211
 212
 213 /// run - This is the main entry point for the type legalizer.  This does a
 214 /// top-down traversal of the dag, legalizing types as it goes.
 215 void DAGTypeLegalizer::run() {
 216   // Create a dummy node (which is not added to allnodes), that adds a reference
 217   // to the root node, preventing it from being deleted, and tracking any
 218   // changes of the root.
 219   HandleSDNode Dummy(DAG.getRoot());
 220
 221   // The root of the dag may dangle to deleted nodes until the type legalizer is
 222   // done.  Set it to null to avoid confusion.
 223   DAG.setRoot(SDOperand());
 224
 225   // Walk all nodes in the graph, assigning them a NodeID of 'ReadyToProcess'
 226   // (and remembering them) if they are leaves and assigning 'NewNode' if
 227   // non-leaves.
 228   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 229        E = DAG.allnodes_end(); I != E; ++I) {
 230     if (I->getNumOperands() == 0) {
 231       I->setNodeId(ReadyToProcess);
 232       Worklist.push_back(I);
 233     } else {
 234       I->setNodeId(NewNode);
 235     }
 236   }
 237
 238   // Now that we have a set of nodes to process, handle them all.
 239   while (!Worklist.empty()) {
 240     SDNode *N = Worklist.back();
 241     Worklist.pop_back();
 242     assert(N->getNodeId() == ReadyToProcess &&
 243            "Node should be ready if on worklist!");
 244
 245     // Scan the values produced by the node, checking to see if any result
 246     // types are illegal.
 247     unsigned i = 0;
 248     unsigned NumResults = N->getNumValues();
 249     do {
 250       LegalizeAction Action = getTypeAction(N->getValueType(i));
 251       if (Action == Promote) {
 252         PromoteResult(N, i);
 253         goto NodeDone;
 254       } else if (Action == Expand) {
 255         ExpandResult(N, i);
 256         goto NodeDone;
 257       } else {
 258         assert(Action == Legal && "Unknown action!");
 259       }
 260     } while (++i < NumResults);
 261
 262     // Scan the operand list for the node, handling any nodes with operands that
 263     // are illegal.
 264     {
 265     unsigned NumOperands = N->getNumOperands();
 266     bool NeedsRevisit = false;
 267     for (i = 0; i != NumOperands; ++i) {
 268       LegalizeAction Action = getTypeAction(N->getOperand(i).getValueType());
 269       if (Action == Promote) {
 270         NeedsRevisit = PromoteOperand(N, i);
 271         break;
 272       } else if (Action == Expand) {
 273         NeedsRevisit = ExpandOperand(N, i);
 274         break;
 275       } else {
 276         assert(Action == Legal && "Unknown action!");
 277       }
 278     }
 279
 280     // If the node needs revisiting, don't add all users to the worklist etc.
 281     if (NeedsRevisit)
 282       continue;
 283
 284     if (i == NumOperands)
 285       DEBUG(cerr << "Legally typed node: "; N->dump(&DAG); cerr << "\n");
 286     }
 287 NodeDone:
 288
 289     // If we reach here, the node was processed, potentially creating new nodes.
 290     // Mark it as processed and add its users to the worklist as appropriate.
 291     N->setNodeId(Processed);
 292
 293     for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
 294          UI != E; ++UI) {
 295       SDNode *User = *UI;
 296       int NodeID = User->getNodeId();
 297       assert(NodeID != ReadyToProcess && NodeID != Processed &&
 298              "Invalid node id for user of unprocessed node!");
 299
 300       // This node has two options: it can either be a new node or its Node ID
 301       // may be a count of the number of operands it has that are not ready.
 302       if (NodeID > 0) {
 303         User->setNodeId(NodeID-1);
 304
 305         // If this was the last use it was waiting on, add it to the ready list.
 306         if (NodeID-1 == ReadyToProcess)
 307           Worklist.push_back(User);
 308         continue;
 309       }
 310
 311       // Otherwise, this node is new: this is the first operand of it that
 312       // became ready.  Its new NodeID is the number of operands it has minus 1
 313       // (as this node is now processed).
 314       assert(NodeID == NewNode && "Unknown node ID!");
 315       User->setNodeId(User->getNumOperands()-1);
 316
 317       // If the node only has a single operand, it is now ready.
 318       if (User->getNumOperands() == 1)
 319         Worklist.push_back(User);
 320     }
 321   }
 322
 323   // If the root changed (e.g. it was a dead load, update the root).
 324   DAG.setRoot(Dummy.getValue());
 325
 326   //DAG.viewGraph();
 327
 328   // Remove dead nodes.  This is important to do for cleanliness but also before
 329   // the checking loop below.  Implicit folding by the DAG.getNode operators can
 330   // cause unreachable nodes to be around with their flags set to new.
 331   DAG.RemoveDeadNodes();
 332
 333   // In a debug build, scan all the nodes to make sure we found them all.  This
 334   // ensures that there are no cycles and that everything got processed.
 335 #ifndef NDEBUG
 336   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 337        E = DAG.allnodes_end(); I != E; ++I) {
 338     if (I->getNodeId() == Processed)
 339       continue;
 340     cerr << "Unprocessed node: ";
 341     I->dump(&DAG); cerr << "\n";
 342
 343     if (I->getNodeId() == NewNode)
 344       cerr << "New node not 'noticed'?\n";
 345     else if (I->getNodeId() > 0)
 346       cerr << "Operand not processed?\n";
 347     else if (I->getNodeId() == ReadyToProcess)
 348       cerr << "Not added to worklist?\n";
 349     abort();
 350   }
 351 #endif
 352 }
 353
 354 /// MarkNewNodes - The specified node is the root of a subtree of potentially
 355 /// new nodes.  Add the correct NodeId to mark it.
 356 void DAGTypeLegalizer::MarkNewNodes(SDNode *N) {
 357   // If this was an existing node that is already done, we're done.
 358   if (N->getNodeId() != NewNode)
 359     return;
 360
 361   // Okay, we know that this node is new.  Recursively walk all of its operands
 362   // to see if they are new also.  The depth of this walk is bounded by the size
 363   // of the new tree that was constructed (usually 2-3 nodes), so we don't worry
 364   // about revisiting of nodes.
 365   //
 366   // As we walk the operands, keep track of the number of nodes that are
 367   // processed.  If non-zero, this will become the new nodeid of this node.
 368   unsigned NumProcessed = 0;
 369   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
 370     int OpId = N->getOperand(i).Val->getNodeId();
 371     if (OpId == NewNode)
 372       MarkNewNodes(N->getOperand(i).Val);
 373     else if (OpId == Processed)
 374       ++NumProcessed;
 375   }
 376
 377   N->setNodeId(N->getNumOperands()-NumProcessed);
 378   if (N->getNodeId() == ReadyToProcess)
 379     Worklist.push_back(N);
 380 }
 381
 382 /// ReplaceLegalValueWith - The specified value with a legal type was legalized
 383 /// to the specified other value.  If they are different, update the DAG and
 384 /// NodeIDs replacing any uses of From to use To instead.
 385 void DAGTypeLegalizer::ReplaceLegalValueWith(SDOperand From, SDOperand To) {
 386   if (From == To) return;
 387
 388   // If expansion produced new nodes, make sure they are properly marked.
 389   if (To.Val->getNodeId() == NewNode)
 390     MarkNewNodes(To.Val);
 391
 392   // Anything that used the old node should now use the new one.  Note that this
 393   // can potentially cause recursive merging.
 394   DAG.ReplaceAllUsesOfValueWith(From, To);
 395
 396   // Since we just made an unstructured update to the DAG, which could wreak
 397   // general havoc on anything that once used N and now uses Res, walk all users
 398   // of the result, updating their flags.
 399   for (SDNode::use_iterator I = To.Val->use_begin(), E = To.Val->use_end();
 400        I != E; ++I) {
 401     SDNode *User = *I;
 402     // If the node isn't already processed or in the worklist, mark it as new,
 403     // then use MarkNewNodes to recompute its ID.
 404     int NodeId = User->getNodeId();
 405     if (NodeId != ReadyToProcess && NodeId != Processed) {
 406       User->setNodeId(NewNode);
 407       MarkNewNodes(User);
 408     }
 409   }
 410 }
 411
 412 void DAGTypeLegalizer::SetPromotedOp(SDOperand Op, SDOperand Result) {
 413   if (Result.Val->getNodeId() == NewNode)
 414     MarkNewNodes(Result.Val);
 415
 416   SDOperand &OpEntry = PromotedNodes[Op];
 417   assert(OpEntry.Val == 0 && "Node is already promoted!");
 418   OpEntry = Result;
 419 }
 420
 421 void DAGTypeLegalizer::GetExpandedOp(SDOperand Op, SDOperand &Lo,
 422                                      SDOperand &Hi) {
 423   std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op];
 424   assert(Entry.first.Val && "Operand isn't expanded");
 425   Lo = Entry.first;
 426   Hi = Entry.second;
 427 }
 428
 429 void DAGTypeLegalizer::SetExpandedOp(SDOperand Op, SDOperand Lo,
 430                                      SDOperand Hi) {
 431   // Remember that this is the result of the node.
 432   std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op];
 433   assert(Entry.first.Val == 0 && "Node already expanded");
 434   Entry.first = Lo;
 435   Entry.second = Hi;
 436
 437   // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
 438   if (Lo.Val->getNodeId() == NewNode)
 439     MarkNewNodes(Lo.Val);
 440   if (Hi.Val->getNodeId() == NewNode)
 441     MarkNewNodes(Hi.Val);
 442 }
 443
 444 SDOperand DAGTypeLegalizer::CreateStackStoreLoad(SDOperand Op,
 445                                                  MVT::ValueType DestVT) {
 446   // Create the stack frame object.
 447   SDOperand FIPtr = DAG.CreateStackTemporary(DestVT);
 448
 449   // Emit a store to the stack slot.
 450   SDOperand Store = DAG.getStore(DAG.getEntryNode(), Op, FIPtr, NULL, 0);
 451   // Result is a load from the stack slot.
 452   return DAG.getLoad(DestVT, Store, FIPtr, NULL, 0);
 453 }
 454
 455
 456 /// HandleMemIntrinsic - This handles memcpy/memset/memmove with invalid
 457 /// operands.  This promotes or expands the operands as required.
 458 SDOperand DAGTypeLegalizer::HandleMemIntrinsic(SDNode *N) {
 459   // The chain and pointer [operands #0 and #1] are always valid types.
 460   SDOperand Chain = N->getOperand(0);
 461   SDOperand Ptr   = N->getOperand(1);
 462   SDOperand Op2   = N->getOperand(2);
 463
 464   // Op #2 is either a value (memset) or a pointer.  Promote it if required.
 465   switch (getTypeAction(Op2.getValueType())) {
 466   default: assert(0 && "Unknown action for pointer/value operand");
 467   case Legal: break;
 468   case Promote: Op2 = GetPromotedOp(Op2); break;
 469   }
 470
 471   // The length could have any action required.
 472   SDOperand Length = N->getOperand(3);
 473   switch (getTypeAction(Length.getValueType())) {
 474   default: assert(0 && "Unknown action for memop operand");
 475   case Legal: break;
 476   case Promote: Length = GetPromotedZExtOp(Length); break;
 477   case Expand:
 478     SDOperand Dummy;  // discard the high part.
 479     GetExpandedOp(Length, Length, Dummy);
 480     break;
 481   }
 482
 483   SDOperand Align = N->getOperand(4);
 484   switch (getTypeAction(Align.getValueType())) {
 485   default: assert(0 && "Unknown action for memop operand");
 486   case Legal: break;
 487   case Promote: Align = GetPromotedZExtOp(Align); break;
 488   }
 489
 490   SDOperand AlwaysInline = N->getOperand(5);
 491   switch (getTypeAction(AlwaysInline.getValueType())) {
 492   default: assert(0 && "Unknown action for memop operand");
 493   case Legal: break;
 494   case Promote: AlwaysInline = GetPromotedZExtOp(AlwaysInline); break;
 495   }
 496
 497   SDOperand Ops[] = { Chain, Ptr, Op2, Length, Align, AlwaysInline };
 498   return DAG.UpdateNodeOperands(SDOperand(N, 0), Ops, 6);
 499 }
 500
 501 //===----------------------------------------------------------------------===//
 502 //  Result Promotion
 503 //===----------------------------------------------------------------------===//
 504
 505 /// PromoteResult - This method is called when a result of a node is found to be
 506 /// in need of promotion to a larger type.  At this point, the node may also
 507 /// have invalid operands or may have other results that need expansion, we just
 508 /// know that (at least) one result needs promotion.
 509 void DAGTypeLegalizer::PromoteResult(SDNode *N, unsigned ResNo) {
 510   DEBUG(cerr << "Promote node result: "; N->dump(&DAG); cerr << "\n");
 511   SDOperand Result = SDOperand();
 512
 513   switch (N->getOpcode()) {
 514   default:
 515 #ifndef NDEBUG
 516     cerr << "PromoteResult #" << ResNo << ": ";
 517     N->dump(&DAG); cerr << "\n";
 518 #endif
 519     assert(0 && "Do not know how to promote this operator!");
 520     abort();
 521   case ISD::UNDEF:    Result = PromoteResult_UNDEF(N); break;
 522   case ISD::Constant: Result = PromoteResult_Constant(N); break;
 523
 524   case ISD::TRUNCATE:    Result = PromoteResult_TRUNCATE(N); break;
 525   case ISD::SIGN_EXTEND:
 526   case ISD::ZERO_EXTEND:
 527   case ISD::ANY_EXTEND:  Result = PromoteResult_INT_EXTEND(N); break;
 528   case ISD::FP_ROUND:    Result = PromoteResult_FP_ROUND(N); break;
 529   case ISD::FP_TO_SINT:
 530   case ISD::FP_TO_UINT:  Result = PromoteResult_FP_TO_XINT(N); break;
 531   case ISD::SETCC:    Result = PromoteResult_SETCC(N); break;
 532   case ISD::LOAD:     Result = PromoteResult_LOAD(cast<LoadSDNode>(N)); break;
 533
 534   case ISD::AND:
 535   case ISD::OR:
 536   case ISD::XOR:
 537   case ISD::ADD:
 538   case ISD::SUB:
 539   case ISD::MUL:      Result = PromoteResult_SimpleIntBinOp(N); break;
 540
 541   case ISD::SHL:      Result = PromoteResult_SHL(N); break;
 542   case ISD::SRA:      Result = PromoteResult_SRA(N); break;
 543   case ISD::SRL:      Result = PromoteResult_SRL(N); break;
 544
 545   case ISD::SELECT:    Result = PromoteResult_SELECT(N); break;
 546   case ISD::SELECT_CC: Result = PromoteResult_SELECT_CC(N); break;
 547
 548   }
 549
 550   // If Result is null, the sub-method took care of registering the result.
 551   if (Result.Val)
 552     SetPromotedOp(SDOperand(N, ResNo), Result);
 553 }
 554
 555 SDOperand DAGTypeLegalizer::PromoteResult_UNDEF(SDNode *N) {
 556   return DAG.getNode(ISD::UNDEF, TLI.getTypeToTransformTo(N->getValueType(0)));
 557 }
 558
 559 SDOperand DAGTypeLegalizer::PromoteResult_Constant(SDNode *N) {
 560   MVT::ValueType VT = N->getValueType(0);
 561   // Zero extend things like i1, sign extend everything else.  It shouldn't
 562   // matter in theory which one we pick, but this tends to give better code?
 563   unsigned Opc = VT != MVT::i1 ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
 564   SDOperand Result = DAG.getNode(Opc, TLI.getTypeToTransformTo(VT),
 565                                  SDOperand(N, 0));
 566   assert(isa<ConstantSDNode>(Result) && "Didn't constant fold ext?");
 567   return Result;
 568 }
 569
 570 SDOperand DAGTypeLegalizer::PromoteResult_TRUNCATE(SDNode *N) {
 571   SDOperand Res;
 572
 573   switch (getTypeAction(N->getOperand(0).getValueType())) {
 574   default: assert(0 && "Unknown type action!");
 575   case Legal:
 576   case Expand:
 577     Res = N->getOperand(0);
 578     break;
 579   case Promote:
 580     Res = GetPromotedOp(N->getOperand(0));
 581     break;
 582   }
 583
 584   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 585   assert(MVT::getSizeInBits(Res.getValueType()) >= MVT::getSizeInBits(NVT) &&
 586          "Truncation doesn't make sense!");
 587   if (Res.getValueType() == NVT)
 588     return Res;
 589
 590   // Truncate to NVT instead of VT
 591   return DAG.getNode(ISD::TRUNCATE, NVT, Res);
 592 }
 593
 594 SDOperand DAGTypeLegalizer::PromoteResult_INT_EXTEND(SDNode *N) {
 595   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 596
 597   if (getTypeAction(N->getOperand(0).getValueType()) == Promote) {
 598     SDOperand Res = GetPromotedOp(N->getOperand(0));
 599     assert(MVT::getSizeInBits(Res.getValueType()) <= MVT::getSizeInBits(NVT) &&
 600            "Extension doesn't make sense!");
 601
 602     // If the result and operand types are the same after promotion, simplify
 603     // to an in-register extension.
 604     if (NVT == Res.getValueType()) {
 605       // The high bits are not guaranteed to be anything.  Insert an extend.
 606       if (N->getOpcode() == ISD::SIGN_EXTEND)
 607         return DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Res,
 608                            DAG.getValueType(N->getOperand(0).getValueType()));
 609       if (N->getOpcode() == ISD::ZERO_EXTEND)
 610         return DAG.getZeroExtendInReg(Res, N->getOperand(0).getValueType());
 611       assert(N->getOpcode() == ISD::ANY_EXTEND && "Unknown integer extension!");
 612       return Res;
 613     }
 614   }
 615
 616   // Otherwise, just extend the original operand all the way to the larger type.
 617   return DAG.getNode(N->getOpcode(), NVT, N->getOperand(0));
 618 }
 619
 620 SDOperand DAGTypeLegalizer::PromoteResult_FP_ROUND(SDNode *N) {
 621   // NOTE: Assumes input is legal.
 622   return DAG.getNode(ISD::FP_ROUND_INREG, N->getOperand(0).getValueType(),
 623                      N->getOperand(0), DAG.getValueType(N->getValueType(0)));
 624 }
 625
 626 SDOperand DAGTypeLegalizer::PromoteResult_FP_TO_XINT(SDNode *N) {
 627   SDOperand Op = N->getOperand(0);
 628   // If the operand needed to be promoted, do so now.
 629   if (getTypeAction(Op.getValueType()) == Promote)
 630     // The input result is prerounded, so we don't have to do anything special.
 631     Op = GetPromotedOp(Op);
 632
 633   unsigned NewOpc = N->getOpcode();
 634   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 635
 636   // If we're promoting a UINT to a larger size, check to see if the new node
 637   // will be legal.  If it isn't, check to see if FP_TO_SINT is legal, since
 638   // we can use that instead.  This allows us to generate better code for
 639   // FP_TO_UINT for small destination sizes on targets where FP_TO_UINT is not
 640   // legal, such as PowerPC.
 641   if (N->getOpcode() == ISD::FP_TO_UINT) {
 642     if (!TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) &&
 643         (TLI.isOperationLegal(ISD::FP_TO_SINT, NVT) ||
 644          TLI.getOperationAction(ISD::FP_TO_SINT, NVT)==TargetLowering::Custom))
 645       NewOpc = ISD::FP_TO_SINT;
 646   }
 647
 648   return DAG.getNode(NewOpc, NVT, Op);
 649 }
 650
 651
 652 SDOperand DAGTypeLegalizer::PromoteResult_SETCC(SDNode *N) {
 653   assert(isTypeLegal(TLI.getSetCCResultTy()) && "SetCC type is not legal??");
 654   return DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), N->getOperand(0),
 655                      N->getOperand(1), N->getOperand(2));
 656 }
 657
 658 SDOperand DAGTypeLegalizer::PromoteResult_LOAD(LoadSDNode *N) {
 659   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 660   ISD::LoadExtType ExtType =
 661     ISD::isNON_EXTLoad(N) ? ISD::EXTLOAD : N->getExtensionType();
 662   SDOperand Res = DAG.getExtLoad(ExtType, NVT, N->getChain(), N->getBasePtr(),
 663                                  N->getSrcValue(), N->getSrcValueOffset(),
 664                                  N->getLoadedVT(), N->isVolatile(),
 665                                  N->getAlignment());
 666
 667   // Legalized the chain result - switch anything that used the old chain to
 668   // use the new one.
 669   ReplaceLegalValueWith(SDOperand(N, 1), Res.getValue(1));
 670   return Res;
 671 }
 672
 673 SDOperand DAGTypeLegalizer::PromoteResult_SimpleIntBinOp(SDNode *N) {
 674   // The input may have strange things in the top bits of the registers, but
 675   // these operations don't care.  They may have weird bits going out, but
 676   // that too is okay if they are integer operations.
 677   SDOperand LHS = GetPromotedOp(N->getOperand(0));
 678   SDOperand RHS = GetPromotedOp(N->getOperand(1));
 679   return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS);
 680 }
 681
 682 SDOperand DAGTypeLegalizer::PromoteResult_SHL(SDNode *N) {
 683   return DAG.getNode(ISD::SHL, TLI.getTypeToTransformTo(N->getValueType(0)),
 684                      GetPromotedOp(N->getOperand(0)), N->getOperand(1));
 685 }
 686
 687 SDOperand DAGTypeLegalizer::PromoteResult_SRA(SDNode *N) {
 688   // The input value must be properly sign extended.
 689   MVT::ValueType VT = N->getValueType(0);
 690   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 691   SDOperand Res = GetPromotedOp(N->getOperand(0));
 692   Res = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Res, DAG.getValueType(VT));
 693   return DAG.getNode(ISD::SRA, NVT, Res, N->getOperand(1));
 694 }
 695
 696 SDOperand DAGTypeLegalizer::PromoteResult_SRL(SDNode *N) {
 697   // The input value must be properly zero extended.
 698   MVT::ValueType VT = N->getValueType(0);
 699   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 700   SDOperand Res = GetPromotedZExtOp(N->getOperand(0));
 701   return DAG.getNode(ISD::SRL, NVT, Res, N->getOperand(1));
 702 }
 703
 704 SDOperand DAGTypeLegalizer::PromoteResult_SELECT(SDNode *N) {
 705   SDOperand LHS = GetPromotedOp(N->getOperand(1));
 706   SDOperand RHS = GetPromotedOp(N->getOperand(2));
 707   return DAG.getNode(ISD::SELECT, LHS.getValueType(), N->getOperand(0),LHS,RHS);
 708 }
 709
 710 SDOperand DAGTypeLegalizer::PromoteResult_SELECT_CC(SDNode *N) {
 711   SDOperand LHS = GetPromotedOp(N->getOperand(2));
 712   SDOperand RHS = GetPromotedOp(N->getOperand(3));
 713   return DAG.getNode(ISD::SELECT_CC, LHS.getValueType(), N->getOperand(0),
 714                      N->getOperand(1), LHS, RHS, N->getOperand(4));
 715 }
 716
 717 //===----------------------------------------------------------------------===//
 718 //  Result Expansion
 719 //===----------------------------------------------------------------------===//
 720
 721 /// ExpandResult - This method is called when the specified result of the
 722 /// specified node is found to need expansion.  At this point, the node may also
 723 /// have invalid operands or may have other results that need promotion, we just
 724 /// know that (at least) one result needs expansion.
 725 void DAGTypeLegalizer::ExpandResult(SDNode *N, unsigned ResNo) {
 726   DEBUG(cerr << "Expand node result: "; N->dump(&DAG); cerr << "\n");
 727   SDOperand Lo, Hi;
 728   Lo = Hi = SDOperand();
 729
 730   // If this is a single-result node, see if the target wants to custom expand
 731   // it.
 732   if (N->getNumValues() == 1 &&
 733       TLI.getOperationAction(N->getOpcode(),
 734                              N->getValueType(0)) == TargetLowering::Custom) {
 735     // If the target wants to, allow it to lower this itself.
 736     std::pair<SDOperand,SDOperand> P = TLI.ExpandOperationResult(N, DAG);
 737     if (P.first.Val) {
 738       Lo = P.first;
 739       Hi = P.second;
 740       return;
 741     }
 742   }
 743
 744   switch (N->getOpcode()) {
 745   default:
 746 #ifndef NDEBUG
 747     cerr << "ExpandResult #" << ResNo << ": ";
 748     N->dump(&DAG); cerr << "\n";
 749 #endif
 750     assert(0 && "Do not know how to expand this operator!");
 751     abort();
 752
 753   case ISD::UNDEF:       ExpandResult_UNDEF(N, Lo, Hi); break;
 754   case ISD::Constant:    ExpandResult_Constant(N, Lo, Hi); break;
 755   case ISD::BUILD_PAIR:  ExpandResult_BUILD_PAIR(N, Lo, Hi); break;
 756   case ISD::ANY_EXTEND:  ExpandResult_ANY_EXTEND(N, Lo, Hi); break;
 757   case ISD::ZERO_EXTEND: ExpandResult_ZERO_EXTEND(N, Lo, Hi); break;
 758   case ISD::SIGN_EXTEND: ExpandResult_SIGN_EXTEND(N, Lo, Hi); break;
 759   case ISD::BIT_CONVERT: ExpandResult_BIT_CONVERT(N, Lo, Hi); break;
 760   case ISD::SIGN_EXTEND_INREG: ExpandResult_SIGN_EXTEND_INREG(N, Lo, Hi); break;
 761   case ISD::LOAD:        ExpandResult_LOAD(cast<LoadSDNode>(N), Lo, Hi); break;
 762
 763   case ISD::AND:
 764   case ISD::OR:
 765   case ISD::XOR:         ExpandResult_Logical(N, Lo, Hi); break;
 766   case ISD::BSWAP:       ExpandResult_BSWAP(N, Lo, Hi); break;
 767   case ISD::ADD:
 768   case ISD::SUB:         ExpandResult_ADDSUB(N, Lo, Hi); break;
 769   case ISD::ADDC:
 770   case ISD::SUBC:        ExpandResult_ADDSUBC(N, Lo, Hi); break;
 771   case ISD::ADDE:
 772   case ISD::SUBE:        ExpandResult_ADDSUBE(N, Lo, Hi); break;
 773   case ISD::SELECT:      ExpandResult_SELECT(N, Lo, Hi); break;
 774   case ISD::SELECT_CC:   ExpandResult_SELECT_CC(N, Lo, Hi); break;
 775   case ISD::MUL:         ExpandResult_MUL(N, Lo, Hi); break;
 776   case ISD::SHL:
 777   case ISD::SRA:
 778   case ISD::SRL:         ExpandResult_Shift(N, Lo, Hi); break;
 779
 780   }
 781
 782   // If Lo/Hi is null, the sub-method took care of registering results etc.
 783   if (Lo.Val)
 784     SetExpandedOp(SDOperand(N, ResNo), Lo, Hi);
 785 }
 786
 787 void DAGTypeLegalizer::ExpandResult_UNDEF(SDNode *N,
 788                                           SDOperand &Lo, SDOperand &Hi) {
 789   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 790   Lo = Hi = DAG.getNode(ISD::UNDEF, NVT);
 791 }
 792
 793 void DAGTypeLegalizer::ExpandResult_Constant(SDNode *N,
 794                                              SDOperand &Lo, SDOperand &Hi) {
 795   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 796   uint64_t Cst = cast<ConstantSDNode>(N)->getValue();
 797   Lo = DAG.getConstant(Cst, NVT);
 798   Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
 799 }
 800
 801 void DAGTypeLegalizer::ExpandResult_BUILD_PAIR(SDNode *N,
 802                                                SDOperand &Lo, SDOperand &Hi) {
 803   // Return the operands.
 804   Lo = N->getOperand(0);
 805   Hi = N->getOperand(1);
 806 }
 807
 808 void DAGTypeLegalizer::ExpandResult_ANY_EXTEND(SDNode *N,
 809                                                SDOperand &Lo, SDOperand &Hi) {
 810
 811   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 812   // The low part is any extension of the input (which degenerates to a copy).
 813   Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, N->getOperand(0));
 814   Hi = DAG.getNode(ISD::UNDEF, NVT);   // The high part is undefined.
 815 }
 816
 817 void DAGTypeLegalizer::ExpandResult_ZERO_EXTEND(SDNode *N,
 818                                                 SDOperand &Lo, SDOperand &Hi) {
 819   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 820   // The low part is zero extension of the input (which degenerates to a copy).
 821   Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, N->getOperand(0));
 822   Hi = DAG.getConstant(0, NVT);   // The high part is just a zero.
 823 }
 824
 825 void DAGTypeLegalizer::ExpandResult_SIGN_EXTEND(SDNode *N,
 826                                                 SDOperand &Lo, SDOperand &Hi) {
 827   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 828   // The low part is sign extension of the input (which degenerates to a copy).
 829   Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, N->getOperand(0));
 830
 831   // The high part is obtained by SRA'ing all but one of the bits of low part.
 832   unsigned LoSize = MVT::getSizeInBits(NVT);
 833   Hi = DAG.getNode(ISD::SRA, NVT, Lo,
 834                    DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
 835 }
 836
 837 void DAGTypeLegalizer::ExpandResult_BIT_CONVERT(SDNode *N,
 838                                                 SDOperand &Lo, SDOperand &Hi) {
 839   // Lower the bit-convert to a store/load from the stack, then expand the load.
 840   SDOperand Op = CreateStackStoreLoad(N->getOperand(0), N->getValueType(0));
 841   ExpandResult_LOAD(cast<LoadSDNode>(Op.Val), Lo, Hi);
 842 }
 843
 844 void DAGTypeLegalizer::
 845 ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
 846   GetExpandedOp(N->getOperand(0), Lo, Hi);
 847
 848   // sext_inreg the low part if needed.
 849   Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, Lo.getValueType(), Lo,
 850                    N->getOperand(1));
 851
 852   // The high part gets the sign extension from the lo-part.  This handles
 853   // things like sextinreg V:i64 from i8.
 854   Hi = DAG.getNode(ISD::SRA, Hi.getValueType(), Lo,
 855                    DAG.getConstant(MVT::getSizeInBits(Hi.getValueType())-1,
 856                                    TLI.getShiftAmountTy()));
 857 }
 858
 859
 860 void DAGTypeLegalizer::ExpandResult_LOAD(LoadSDNode *N,
 861                                          SDOperand &Lo, SDOperand &Hi) {
 862   MVT::ValueType VT = N->getValueType(0);
 863   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 864   SDOperand Ch  = N->getChain();    // Legalize the chain.
 865   SDOperand Ptr = N->getBasePtr();  // Legalize the pointer.
 866   ISD::LoadExtType ExtType = N->getExtensionType();
 867   int SVOffset = N->getSrcValueOffset();
 868   unsigned Alignment = N->getAlignment();
 869   bool isVolatile = N->isVolatile();
 870
 871   if (ExtType == ISD::NON_EXTLOAD) {
 872     Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
 873                      isVolatile, Alignment);
 874     // Increment the pointer to the other half.
 875     unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
 876     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
 877                       getIntPtrConstant(IncrementSize));
 878     Hi = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset+IncrementSize,
 879                      isVolatile, std::max(Alignment, IncrementSize));
 880
 881     // Build a factor node to remember that this load is independent of the
 882     // other one.
 883     Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
 884                      Hi.getValue(1));
 885
 886     // Handle endianness of the load.
 887     if (!TLI.isLittleEndian())
 888       std::swap(Lo, Hi);
 889   } else {
 890     MVT::ValueType EVT = N->getLoadedVT();
 891
 892     if (EVT == NVT)
 893       Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(),
 894                        SVOffset, isVolatile, Alignment);
 895     else
 896       Lo = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(),
 897                           SVOffset, EVT, isVolatile,
 898                           Alignment);
 899     // Remember the chain.
 900     Ch = Lo.getValue(1);
 901
 902     if (ExtType == ISD::SEXTLOAD) {
 903       // The high part is obtained by SRA'ing all but one of the bits of the
 904       // lo part.
 905       unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
 906       Hi = DAG.getNode(ISD::SRA, NVT, Lo,
 907                        DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
 908     } else if (ExtType == ISD::ZEXTLOAD) {
 909       // The high part is just a zero.
 910       Hi = DAG.getConstant(0, NVT);
 911     } else {
 912       assert(ExtType == ISD::EXTLOAD && "Unknown extload!");
 913       // The high part is undefined.
 914       Hi = DAG.getNode(ISD::UNDEF, NVT);
 915     }
 916   }
 917
 918   // Legalized the chain result - switch anything that used the old chain to
 919   // use the new one.
 920   ReplaceLegalValueWith(SDOperand(N, 1), Ch);
 921 }
 922
 923
 924 void DAGTypeLegalizer::ExpandResult_Logical(SDNode *N,
 925                                             SDOperand &Lo, SDOperand &Hi) {
 926   SDOperand LL, LH, RL, RH;
 927   GetExpandedOp(N->getOperand(0), LL, LH);
 928   GetExpandedOp(N->getOperand(1), RL, RH);
 929   Lo = DAG.getNode(N->getOpcode(), LL.getValueType(), LL, RL);
 930   Hi = DAG.getNode(N->getOpcode(), LL.getValueType(), LH, RH);
 931 }
 932
 933 void DAGTypeLegalizer::ExpandResult_BSWAP(SDNode *N,
 934                                           SDOperand &Lo, SDOperand &Hi) {
 935   GetExpandedOp(N->getOperand(0), Hi, Lo);  // Note swapped operands.
 936   Lo = DAG.getNode(ISD::BSWAP, Lo.getValueType(), Lo);
 937   Hi = DAG.getNode(ISD::BSWAP, Hi.getValueType(), Hi);
 938 }
 939
 940
 941 void DAGTypeLegalizer::ExpandResult_SELECT(SDNode *N,
 942                                            SDOperand &Lo, SDOperand &Hi) {
 943   SDOperand LL, LH, RL, RH;
 944   GetExpandedOp(N->getOperand(1), LL, LH);
 945   GetExpandedOp(N->getOperand(2), RL, RH);
 946   Lo = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LL, RL);
 947
 948   assert(N->getOperand(0).getValueType() != MVT::f32 &&
 949          "FIXME: softfp shouldn't use expand!");
 950   Hi = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LH, RH);
 951 }
 952
 953 void DAGTypeLegalizer::ExpandResult_SELECT_CC(SDNode *N,
 954                                               SDOperand &Lo, SDOperand &Hi) {
 955   SDOperand LL, LH, RL, RH;
 956   GetExpandedOp(N->getOperand(2), LL, LH);
 957   GetExpandedOp(N->getOperand(3), RL, RH);
 958   Lo = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0),
 959                    N->getOperand(1), LL, RL, N->getOperand(4));
 960
 961   assert(N->getOperand(0).getValueType() != MVT::f32 &&
 962          "FIXME: softfp shouldn't use expand!");
 963   Hi = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0),
 964                    N->getOperand(1), LH, RH, N->getOperand(4));
 965 }
 966
 967 void DAGTypeLegalizer::ExpandResult_ADDSUB(SDNode *N,
 968                                            SDOperand &Lo, SDOperand &Hi) {
 969   // Expand the subcomponents.
 970   SDOperand LHSL, LHSH, RHSL, RHSH;
 971   GetExpandedOp(N->getOperand(0), LHSL, LHSH);
 972   GetExpandedOp(N->getOperand(1), RHSL, RHSH);
 973   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
 974   SDOperand LoOps[2] = { LHSL, RHSL };
 975   SDOperand HiOps[3] = { LHSH, RHSH };
 976
 977   if (N->getOpcode() == ISD::ADD) {
 978     Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
 979     HiOps[2] = Lo.getValue(1);
 980     Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
 981   } else {
 982     Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
 983     HiOps[2] = Lo.getValue(1);
 984     Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
 985   }
 986 }
 987
 988 void DAGTypeLegalizer::ExpandResult_ADDSUBC(SDNode *N,
 989                                             SDOperand &Lo, SDOperand &Hi) {
 990   // Expand the subcomponents.
 991   SDOperand LHSL, LHSH, RHSL, RHSH;
 992   GetExpandedOp(N->getOperand(0), LHSL, LHSH);
 993   GetExpandedOp(N->getOperand(1), RHSL, RHSH);
 994   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
 995   SDOperand LoOps[2] = { LHSL, RHSL };
 996   SDOperand HiOps[3] = { LHSH, RHSH };
 997
 998   if (N->getOpcode() == ISD::ADDC) {
 999     Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
1000     HiOps[2] = Lo.getValue(1);
1001     Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
1002   } else {
1003     Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
1004     HiOps[2] = Lo.getValue(1);
1005     Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
1006   }
1007
1008   // Legalized the flag result - switch anything that used the old flag to
1009   // use the new one.
1010   ReplaceLegalValueWith(SDOperand(N, 1), Hi.getValue(1));
1011 }
1012
1013 void DAGTypeLegalizer::ExpandResult_ADDSUBE(SDNode *N,
1014                                             SDOperand &Lo, SDOperand &Hi) {
1015   // Expand the subcomponents.
1016   SDOperand LHSL, LHSH, RHSL, RHSH;
1017   GetExpandedOp(N->getOperand(0), LHSL, LHSH);
1018   GetExpandedOp(N->getOperand(1), RHSL, RHSH);
1019   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
1020   SDOperand LoOps[3] = { LHSL, RHSL, N->getOperand(2) };
1021   SDOperand HiOps[3] = { LHSH, RHSH };
1022
1023   Lo = DAG.getNode(N->getOpcode(), VTList, LoOps, 3);
1024   HiOps[2] = Lo.getValue(1);
1025   Hi = DAG.getNode(N->getOpcode(), VTList, HiOps, 3);
1026
1027   // Legalized the flag result - switch anything that used the old flag to
1028   // use the new one.
1029   ReplaceLegalValueWith(SDOperand(N, 1), Hi.getValue(1));
1030 }
1031
1032 void DAGTypeLegalizer::ExpandResult_MUL(SDNode *N,
1033                                         SDOperand &Lo, SDOperand &Hi) {
1034   MVT::ValueType VT = N->getValueType(0);
1035   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1036
1037   bool HasMULHS = TLI.isOperationLegal(ISD::MULHS, NVT);
1038   bool HasMULHU = TLI.isOperationLegal(ISD::MULHU, NVT);
1039   bool HasSMUL_LOHI = TLI.isOperationLegal(ISD::SMUL_LOHI, NVT);
1040   bool HasUMUL_LOHI = TLI.isOperationLegal(ISD::UMUL_LOHI, NVT);
1041   if (HasMULHU || HasMULHS || HasUMUL_LOHI || HasSMUL_LOHI) {
1042     SDOperand LL, LH, RL, RH;
1043     GetExpandedOp(N->getOperand(0), LL, LH);
1044     GetExpandedOp(N->getOperand(1), RL, RH);
1045     unsigned BitSize = MVT::getSizeInBits(RH.getValueType());
1046     unsigned LHSSB = DAG.ComputeNumSignBits(N->getOperand(0));
1047     unsigned RHSSB = DAG.ComputeNumSignBits(N->getOperand(1));
1048
1049     // FIXME: generalize this to handle other bit sizes
1050     if (LHSSB == 32 && RHSSB == 32 &&
1051         DAG.MaskedValueIsZero(N->getOperand(0), 0xFFFFFFFF00000000ULL) &&
1052         DAG.MaskedValueIsZero(N->getOperand(1), 0xFFFFFFFF00000000ULL)) {
1053       // The inputs are both zero-extended.
1054       if (HasUMUL_LOHI) {
1055         // We can emit a umul_lohi.
1056         Lo = DAG.getNode(ISD::UMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL);
1057         Hi = SDOperand(Lo.Val, 1);
1058         return;
1059       }
1060       if (HasMULHU) {
1061         // We can emit a mulhu+mul.
1062         Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
1063         Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
1064         return;
1065       }
1066     }
1067     if (LHSSB > BitSize && RHSSB > BitSize) {
1068       // The input values are both sign-extended.
1069       if (HasSMUL_LOHI) {
1070         // We can emit a smul_lohi.
1071         Lo = DAG.getNode(ISD::SMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL);
1072         Hi = SDOperand(Lo.Val, 1);
1073         return;
1074       }
1075       if (HasMULHS) {
1076         // We can emit a mulhs+mul.
1077         Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
1078         Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL);
1079         return;
1080       }
1081     }
1082     if (HasUMUL_LOHI) {
1083       // Lo,Hi = umul LHS, RHS.
1084       SDOperand UMulLOHI = DAG.getNode(ISD::UMUL_LOHI,
1085                                        DAG.getVTList(NVT, NVT), LL, RL);
1086       Lo = UMulLOHI;
1087       Hi = UMulLOHI.getValue(1);
1088       RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
1089       LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
1090       Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
1091       Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
1092       return;
1093     }
1094   }
1095
1096   abort();
1097 #if 0 // FIXME!
1098   // If nothing else, we can make a libcall.
1099   Lo = ExpandLibCall(TLI.getLibcallName(RTLIB::MUL_I64), N,
1100                      false/*sign irrelevant*/, Hi);
1101 #endif
1102 }
1103
1104
1105 void DAGTypeLegalizer::ExpandResult_Shift(SDNode *N,
1106                                           SDOperand &Lo, SDOperand &Hi) {
1107   MVT::ValueType VT = N->getValueType(0);
1108
1109   // If we can emit an efficient shift operation, do so now.  Check to see if
1110   // the RHS is a constant.
1111   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1)))
1112     return ExpandShiftByConstant(N, CN->getValue(), Lo, Hi);
1113
1114   // If we can determine that the high bit of the shift is zero or one, even if
1115   // the low bits are variable, emit this shift in an optimized form.
1116   if (ExpandShiftWithKnownAmountBit(N, Lo, Hi))
1117     return;
1118
1119   // If this target supports shift_PARTS, use it.  First, map to the _PARTS opc.
1120   unsigned PartsOpc;
1121   if (N->getOpcode() == ISD::SHL)
1122     PartsOpc = ISD::SHL_PARTS;
1123   else if (N->getOpcode() == ISD::SRL)
1124     PartsOpc = ISD::SRL_PARTS;
1125   else {
1126     assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
1127     PartsOpc = ISD::SRA_PARTS;
1128   }
1129
1130   // Next check to see if the target supports this SHL_PARTS operation or if it
1131   // will custom expand it.
1132   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1133   TargetLowering::LegalizeAction Action = TLI.getOperationAction(PartsOpc, NVT);
1134   if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
1135       Action == TargetLowering::Custom) {
1136     // Expand the subcomponents.
1137     SDOperand LHSL, LHSH;
1138     GetExpandedOp(N->getOperand(0), LHSL, LHSH);
1139
1140     SDOperand Ops[] = { LHSL, LHSH, N->getOperand(1) };
1141     MVT::ValueType VT = LHSL.getValueType();
1142     Lo = DAG.getNode(PartsOpc, DAG.getNodeValueTypes(VT, VT), 2, Ops, 3);
1143     Hi = Lo.getValue(1);
1144     return;
1145   }
1146
1147   abort();
1148 #if 0 // FIXME!
1149   // Otherwise, emit a libcall.
1150   unsigned RuntimeCode = ; // SRL -> SRL_I64 etc.
1151   bool Signed = ;
1152   Lo = ExpandLibCall(TLI.getLibcallName(RTLIB::SRL_I64), N,
1153                      false/*lshr is unsigned*/, Hi);
1154 #endif
1155 }
1156
1157
1158 /// ExpandShiftByConstant - N is a shift by a value that needs to be expanded,
1159 /// and the shift amount is a constant 'Amt'.  Expand the operation.
1160 void DAGTypeLegalizer::ExpandShiftByConstant(SDNode *N, unsigned Amt,
1161                                              SDOperand &Lo, SDOperand &Hi) {
1162   // Expand the incoming operand to be shifted, so that we have its parts
1163   SDOperand InL, InH;
1164   GetExpandedOp(N->getOperand(0), InL, InH);
1165
1166   MVT::ValueType NVT = InL.getValueType();
1167   unsigned VTBits = MVT::getSizeInBits(N->getValueType(0));
1168   unsigned NVTBits = MVT::getSizeInBits(NVT);
1169   MVT::ValueType ShTy = N->getOperand(1).getValueType();
1170
1171   if (N->getOpcode() == ISD::SHL) {
1172     if (Amt > VTBits) {
1173       Lo = Hi = DAG.getConstant(0, NVT);
1174     } else if (Amt > NVTBits) {
1175       Lo = DAG.getConstant(0, NVT);
1176       Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt-NVTBits,ShTy));
1177     } else if (Amt == NVTBits) {
1178       Lo = DAG.getConstant(0, NVT);
1179       Hi = InL;
1180     } else {
1181       Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt, ShTy));
1182       Hi = DAG.getNode(ISD::OR, NVT,
1183                        DAG.getNode(ISD::SHL, NVT, InH,
1184                                    DAG.getConstant(Amt, ShTy)),
1185                        DAG.getNode(ISD::SRL, NVT, InL,
1186                                    DAG.getConstant(NVTBits-Amt, ShTy)));
1187     }
1188     return;
1189   }
1190
1191   if (N->getOpcode() == ISD::SRL) {
1192     if (Amt > VTBits) {
1193       Lo = DAG.getConstant(0, NVT);
1194       Hi = DAG.getConstant(0, NVT);
1195     } else if (Amt > NVTBits) {
1196       Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Amt-NVTBits,ShTy));
1197       Hi = DAG.getConstant(0, NVT);
1198     } else if (Amt == NVTBits) {
1199       Lo = InH;
1200       Hi = DAG.getConstant(0, NVT);
1201     } else {
1202       Lo = DAG.getNode(ISD::OR, NVT,
1203                        DAG.getNode(ISD::SRL, NVT, InL,
1204                                    DAG.getConstant(Amt, ShTy)),
1205                        DAG.getNode(ISD::SHL, NVT, InH,
1206                                    DAG.getConstant(NVTBits-Amt, ShTy)));
1207       Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Amt, ShTy));
1208     }
1209     return;
1210   }
1211
1212   assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
1213   if (Amt > VTBits) {
1214     Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
1215                           DAG.getConstant(NVTBits-1, ShTy));
1216   } else if (Amt > NVTBits) {
1217     Lo = DAG.getNode(ISD::SRA, NVT, InH,
1218                      DAG.getConstant(Amt-NVTBits, ShTy));
1219     Hi = DAG.getNode(ISD::SRA, NVT, InH,
1220                      DAG.getConstant(NVTBits-1, ShTy));
1221   } else if (Amt == NVTBits) {
1222     Lo = InH;
1223     Hi = DAG.getNode(ISD::SRA, NVT, InH,
1224                      DAG.getConstant(NVTBits-1, ShTy));
1225   } else {
1226     Lo = DAG.getNode(ISD::OR, NVT,
1227                      DAG.getNode(ISD::SRL, NVT, InL,
1228                                  DAG.getConstant(Amt, ShTy)),
1229                      DAG.getNode(ISD::SHL, NVT, InH,
1230                                  DAG.getConstant(NVTBits-Amt, ShTy)));
1231     Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Amt, ShTy));
1232   }
1233 }
1234
1235 /// ExpandShiftWithKnownAmountBit - Try to determine whether we can simplify
1236 /// this shift based on knowledge of the high bit of the shift amount.  If we
1237 /// can tell this, we know that it is >= 32 or < 32, without knowing the actual
1238 /// shift amount.
1239 bool DAGTypeLegalizer::
1240 ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
1241   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
1242   unsigned NVTBits = MVT::getSizeInBits(NVT);
1243
1244   uint64_t HighBitMask = NVTBits, KnownZero, KnownOne;
1245   DAG.ComputeMaskedBits(N->getOperand(1), HighBitMask, KnownZero, KnownOne);
1246
1247   // If we don't know anything about the high bit, exit.
1248   if (((KnownZero|KnownOne) & HighBitMask) == 0)
1249     return false;
1250
1251   // Get the incoming operand to be shifted.
1252   SDOperand InL, InH;
1253   GetExpandedOp(N->getOperand(0), InL, InH);
1254   SDOperand Amt = N->getOperand(1);
1255
1256   // If we know that the high bit of the shift amount is one, then we can do
1257   // this as a couple of simple shifts.
1258   if (KnownOne & HighBitMask) {
1259     // Mask out the high bit, which we know is set.
1260     Amt = DAG.getNode(ISD::AND, Amt.getValueType(), Amt,
1261                       DAG.getConstant(NVTBits-1, Amt.getValueType()));
1262
1263     switch (N->getOpcode()) {
1264     default: assert(0 && "Unknown shift");
1265     case ISD::SHL:
1266       Lo = DAG.getConstant(0, NVT);              // Low part is zero.
1267       Hi = DAG.getNode(ISD::SHL, NVT, InL, Amt); // High part from Lo part.
1268       return true;
1269     case ISD::SRL:
1270       Hi = DAG.getConstant(0, NVT);              // Hi part is zero.
1271       Lo = DAG.getNode(ISD::SRL, NVT, InH, Amt); // Lo part from Hi part.
1272       return true;
1273     case ISD::SRA:
1274       Hi = DAG.getNode(ISD::SRA, NVT, InH,       // Sign extend high part.
1275                        DAG.getConstant(NVTBits-1, Amt.getValueType()));
1276       Lo = DAG.getNode(ISD::SRA, NVT, InH, Amt); // Lo part from Hi part.
1277       return true;
1278     }
1279   }
1280
1281   // If we know that the high bit of the shift amount is zero, then we can do
1282   // this as a couple of simple shifts.
1283   assert((KnownZero & HighBitMask) && "Bad mask computation above");
1284
1285   // Compute 32-amt.
1286   SDOperand Amt2 = DAG.getNode(ISD::SUB, Amt.getValueType(),
1287                                DAG.getConstant(NVTBits, Amt.getValueType()),
1288                                Amt);
1289   unsigned Op1, Op2;
1290   switch (N->getOpcode()) {
1291   default: assert(0 && "Unknown shift");
1292   case ISD::SHL:  Op1 = ISD::SHL; Op2 = ISD::SRL; break;
1293   case ISD::SRL:
1294   case ISD::SRA:  Op1 = ISD::SRL; Op2 = ISD::SHL; break;
1295   }
1296
1297   Lo = DAG.getNode(N->getOpcode(), NVT, InL, Amt);
1298   Hi = DAG.getNode(ISD::OR, NVT,
1299                    DAG.getNode(Op1, NVT, InH, Amt),
1300                    DAG.getNode(Op2, NVT, InL, Amt2));
1301   return true;
1302 }
1303
1304 //===----------------------------------------------------------------------===//
1305 //  Operand Promotion
1306 //===----------------------------------------------------------------------===//
1307
1308 /// PromoteOperand - This method is called when the specified operand of the
1309 /// specified node is found to need promotion.  At this point, all of the result
1310 /// types of the node are known to be legal, but other operands of the node may
1311 /// need promotion or expansion as well as the specified one.
1312 bool DAGTypeLegalizer::PromoteOperand(SDNode *N, unsigned OpNo) {
1313   DEBUG(cerr << "Promote node operand: "; N->dump(&DAG); cerr << "\n");
1314   SDOperand Res;
1315   switch (N->getOpcode()) {
1316     default:
1317 #ifndef NDEBUG
1318     cerr << "PromoteOperand Op #" << OpNo << ": ";
1319     N->dump(&DAG); cerr << "\n";
1320 #endif
1321     assert(0 && "Do not know how to promote this operator's operand!");
1322     abort();
1323
1324   case ISD::ANY_EXTEND:  Res = PromoteOperand_ANY_EXTEND(N); break;
1325   case ISD::ZERO_EXTEND: Res = PromoteOperand_ZERO_EXTEND(N); break;
1326   case ISD::SIGN_EXTEND: Res = PromoteOperand_SIGN_EXTEND(N); break;
1327   case ISD::TRUNCATE:    Res = PromoteOperand_TRUNCATE(N); break;
1328   case ISD::FP_EXTEND:   Res = PromoteOperand_FP_EXTEND(N); break;
1329   case ISD::FP_ROUND:    Res = PromoteOperand_FP_ROUND(N); break;
1330   case ISD::SINT_TO_FP:
1331   case ISD::UINT_TO_FP:  Res = PromoteOperand_INT_TO_FP(N); break;
1332
1333   case ISD::SELECT:      Res = PromoteOperand_SELECT(N, OpNo); break;
1334   case ISD::BRCOND:      Res = PromoteOperand_BRCOND(N, OpNo); break;
1335   case ISD::BR_CC:       Res = PromoteOperand_BR_CC(N, OpNo); break;
1336
1337   case ISD::STORE:       Res = PromoteOperand_STORE(cast<StoreSDNode>(N),
1338                                                     OpNo); break;
1339   case ISD::MEMSET:
1340   case ISD::MEMCPY:
1341   case ISD::MEMMOVE:     Res = HandleMemIntrinsic(N); break;
1342   }
1343
1344   // If the result is null, the sub-method took care of registering results etc.
1345   if (!Res.Val) return false;
1346   // If the result is N, the sub-method updated N in place.
1347   if (Res.Val == N) {
1348     // Mark N as new and remark N and its operands.  This allows us to correctly
1349     // revisit N if it needs another step of promotion and allows us to visit
1350     // any new operands to N.
1351     N->setNodeId(NewNode);
1352     MarkNewNodes(N);
1353     return true;
1354   }
1355
1356   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
1357          "Invalid operand expansion");
1358
1359   ReplaceLegalValueWith(SDOperand(N, 0), Res);
1360   return false;
1361 }
1362
1363 SDOperand DAGTypeLegalizer::PromoteOperand_ANY_EXTEND(SDNode *N) {
1364   SDOperand Op = GetPromotedOp(N->getOperand(0));
1365   return DAG.getNode(ISD::ANY_EXTEND, N->getValueType(0), Op);
1366 }
1367
1368 SDOperand DAGTypeLegalizer::PromoteOperand_ZERO_EXTEND(SDNode *N) {
1369   SDOperand Op = GetPromotedOp(N->getOperand(0));
1370   Op = DAG.getNode(ISD::ANY_EXTEND, N->getValueType(0), Op);
1371   return DAG.getZeroExtendInReg(Op, N->getOperand(0).getValueType());
1372 }
1373
1374 SDOperand DAGTypeLegalizer::PromoteOperand_SIGN_EXTEND(SDNode *N) {
1375   SDOperand Op = GetPromotedOp(N->getOperand(0));
1376   Op = DAG.getNode(ISD::ANY_EXTEND, N->getValueType(0), Op);
1377   return DAG.getNode(ISD::SIGN_EXTEND_INREG, Op.getValueType(),
1378                      Op, DAG.getValueType(N->getOperand(0).getValueType()));
1379 }
1380
1381 SDOperand DAGTypeLegalizer::PromoteOperand_TRUNCATE(SDNode *N) {
1382   SDOperand Op = GetPromotedOp(N->getOperand(0));
1383   return DAG.getNode(ISD::TRUNCATE, N->getValueType(0), Op);
1384 }
1385
1386 SDOperand DAGTypeLegalizer::PromoteOperand_FP_EXTEND(SDNode *N) {
1387   SDOperand Op = GetPromotedOp(N->getOperand(0));
1388   return DAG.getNode(ISD::FP_EXTEND, N->getValueType(0), Op);
1389 }
1390
1391 SDOperand DAGTypeLegalizer::PromoteOperand_FP_ROUND(SDNode *N) {
1392   SDOperand Op = GetPromotedOp(N->getOperand(0));
1393   return DAG.getNode(ISD::FP_ROUND, N->getValueType(0), Op);
1394 }
1395
1396 SDOperand DAGTypeLegalizer::PromoteOperand_INT_TO_FP(SDNode *N) {
1397   SDOperand In = GetPromotedOp(N->getOperand(0));
1398   MVT::ValueType OpVT = N->getOperand(0).getValueType();
1399   if (N->getOpcode() == ISD::UINT_TO_FP)
1400     In = DAG.getZeroExtendInReg(In, OpVT);
1401   else
1402     In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(),
1403                      In, DAG.getValueType(OpVT));
1404
1405   return DAG.UpdateNodeOperands(SDOperand(N, 0), In);
1406 }
1407
1408
1409 SDOperand DAGTypeLegalizer::PromoteOperand_SELECT(SDNode *N, unsigned OpNo) {
1410   assert(OpNo == 0 && "Only know how to promote condition");
1411   SDOperand Cond = GetPromotedOp(N->getOperand(0));  // Promote the condition.
1412
1413   // The top bits of the promoted condition are not necessarily zero, ensure
1414   // that the value is properly zero extended.
1415   if (!DAG.MaskedValueIsZero(Cond,
1416                              MVT::getIntVTBitMask(Cond.getValueType())^1)) {
1417     Cond = DAG.getZeroExtendInReg(Cond, MVT::i1);
1418     MarkNewNodes(Cond.Val);
1419   }
1420
1421   // The chain (Op#0) and basic block destination (Op#2) are always legal types.
1422   return DAG.UpdateNodeOperands(SDOperand(N, 0), Cond, N->getOperand(1),
1423                                 N->getOperand(2));
1424 }
1425
1426
1427 SDOperand DAGTypeLegalizer::PromoteOperand_BRCOND(SDNode *N, unsigned OpNo) {
1428   assert(OpNo == 1 && "only know how to promote condition");
1429   SDOperand Cond = GetPromotedOp(N->getOperand(1));  // Promote the condition.
1430
1431   // The top bits of the promoted condition are not necessarily zero, ensure
1432   // that the value is properly zero extended.
1433   if (!DAG.MaskedValueIsZero(Cond,
1434                              MVT::getIntVTBitMask(Cond.getValueType())^1)) {
1435     Cond = DAG.getZeroExtendInReg(Cond, MVT::i1);
1436     MarkNewNodes(Cond.Val);
1437   }
1438
1439   // The chain (Op#0) and basic block destination (Op#2) are always legal types.
1440   return DAG.UpdateNodeOperands(SDOperand(N, 0), N->getOperand(0), Cond,
1441                                 N->getOperand(2));
1442 }
1443
1444 SDOperand DAGTypeLegalizer::PromoteOperand_BR_CC(SDNode *N, unsigned OpNo) {
1445   assert(OpNo == 2 && "Don't know how to promote this operand");
1446
1447   SDOperand LHS = N->getOperand(2);
1448   SDOperand RHS = N->getOperand(3);
1449   PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(1))->get());
1450
1451   // The chain (Op#0), CC (#1) and basic block destination (Op#4) are always
1452   // legal types.
1453   return DAG.UpdateNodeOperands(SDOperand(N, 0), N->getOperand(0),
1454                                 N->getOperand(1), LHS, RHS, N->getOperand(4));
1455 }
1456
1457 /// PromoteSetCCOperands - Promote the operands of a comparison.  This code is
1458 /// shared among BR_CC, SELECT_CC, and SETCC handlers.
1459 void DAGTypeLegalizer::PromoteSetCCOperands(SDOperand &NewLHS,SDOperand &NewRHS,
1460                                             ISD::CondCode CCCode) {
1461   MVT::ValueType VT = NewLHS.getValueType();
1462
1463   // Get the promoted values.
1464   NewLHS = GetPromotedOp(NewLHS);
1465   NewRHS = GetPromotedOp(NewRHS);
1466
1467   // If this is an FP compare, the operands have already been extended.
1468   if (!MVT::isInteger(NewLHS.getValueType()))
1469     return;
1470
1471   // Otherwise, we have to insert explicit sign or zero extends.  Note
1472   // that we could insert sign extends for ALL conditions, but zero extend
1473   // is cheaper on many machines (an AND instead of two shifts), so prefer
1474   // it.
1475   switch (CCCode) {
1476   default: assert(0 && "Unknown integer comparison!");
1477   case ISD::SETEQ:
1478   case ISD::SETNE:
1479   case ISD::SETUGE:
1480   case ISD::SETUGT:
1481   case ISD::SETULE:
1482   case ISD::SETULT:
1483     // ALL of these operations will work if we either sign or zero extend
1484     // the operands (including the unsigned comparisons!).  Zero extend is
1485     // usually a simpler/cheaper operation, so prefer it.
1486     NewLHS = DAG.getZeroExtendInReg(NewLHS, VT);
1487     NewRHS = DAG.getZeroExtendInReg(NewRHS, VT);
1488     return;
1489   case ISD::SETGE:
1490   case ISD::SETGT:
1491   case ISD::SETLT:
1492   case ISD::SETLE:
1493     NewLHS = DAG.getNode(ISD::SIGN_EXTEND_INREG, NewLHS.getValueType(), NewLHS,
1494                          DAG.getValueType(VT));
1495     NewRHS = DAG.getNode(ISD::SIGN_EXTEND_INREG, NewRHS.getValueType(), NewRHS,
1496                          DAG.getValueType(VT));
1497     return;
1498   }
1499 }
1500
1501
1502 SDOperand DAGTypeLegalizer::PromoteOperand_STORE(StoreSDNode *N, unsigned OpNo){
1503   SDOperand Ch = N->getChain(), Ptr = N->getBasePtr();
1504   int SVOffset = N->getSrcValueOffset();
1505   unsigned Alignment = N->getAlignment();
1506   bool isVolatile = N->isVolatile();
1507
1508   SDOperand Val = GetPromotedOp(N->getValue());  // Get promoted value.
1509
1510   assert(!N->isTruncatingStore() && "Cannot promote this store operand!");
1511
1512   // Truncate the value and store the result.
1513   return DAG.getTruncStore(Ch, Val, Ptr, N->getSrcValue(),
1514                            SVOffset, N->getStoredVT(),
1515                            isVolatile, Alignment);
1516 }
1517
1518
1519 //===----------------------------------------------------------------------===//
1520 //  Operand Expansion
1521 //===----------------------------------------------------------------------===//
1522
1523 /// ExpandOperand - This method is called when the specified operand of the
1524 /// specified node is found to need expansion.  At this point, all of the result
1525 /// types of the node are known to be legal, but other operands of the node may
1526 /// need promotion or expansion as well as the specified one.
1527 bool DAGTypeLegalizer::ExpandOperand(SDNode *N, unsigned OpNo) {
1528   DEBUG(cerr << "Expand node operand: "; N->dump(&DAG); cerr << "\n");
1529   SDOperand Res;
1530   switch (N->getOpcode()) {
1531   default:
1532 #ifndef NDEBUG
1533     cerr << "ExpandOperand Op #" << OpNo << ": ";
1534     N->dump(&DAG); cerr << "\n";
1535 #endif
1536     assert(0 && "Do not know how to expand this operator's operand!");
1537     abort();
1538
1539   case ISD::TRUNCATE:        Res = ExpandOperand_TRUNCATE(N); break;
1540   case ISD::BIT_CONVERT:     Res = ExpandOperand_BIT_CONVERT(N); break;
1541
1542   case ISD::SINT_TO_FP:
1543     Res = ExpandOperand_SINT_TO_FP(N->getOperand(0), N->getValueType(0));
1544     break;
1545   case ISD::UINT_TO_FP:
1546     Res = ExpandOperand_UINT_TO_FP(N->getOperand(0), N->getValueType(0));
1547     break;
1548   case ISD::EXTRACT_ELEMENT: Res = ExpandOperand_EXTRACT_ELEMENT(N); break;
1549   case ISD::SETCC:           Res = ExpandOperand_SETCC(N); break;
1550
1551   case ISD::STORE: Res = ExpandOperand_STORE(cast<StoreSDNode>(N), OpNo); break;
1552   case ISD::MEMSET:
1553   case ISD::MEMCPY:
1554   case ISD::MEMMOVE:     Res = HandleMemIntrinsic(N); break;
1555   }
1556
1557   // If the result is null, the sub-method took care of registering results etc.
1558   if (!Res.Val) return false;
1559   // If the result is N, the sub-method updated N in place.  Check to see if any
1560   // operands are new, and if so, mark them.
1561   if (Res.Val == N) {
1562     // Mark N as new and remark N and its operands.  This allows us to correctly
1563     // revisit N if it needs another step of promotion and allows us to visit
1564     // any new operands to N.
1565     N->setNodeId(NewNode);
1566     MarkNewNodes(N);
1567     return true;
1568   }
1569
1570   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
1571          "Invalid operand expansion");
1572
1573   ReplaceLegalValueWith(SDOperand(N, 0), Res);
1574   return false;
1575 }
1576
1577 SDOperand DAGTypeLegalizer::ExpandOperand_TRUNCATE(SDNode *N) {
1578   SDOperand InL, InH;
1579   GetExpandedOp(N->getOperand(0), InL, InH);
1580   // Just truncate the low part of the source.
1581   return DAG.getNode(ISD::TRUNCATE, N->getValueType(0), InL);
1582 }
1583
1584 SDOperand DAGTypeLegalizer::ExpandOperand_BIT_CONVERT(SDNode *N) {
1585   return CreateStackStoreLoad(N->getOperand(0), N->getValueType(0));
1586 }
1587
1588 SDOperand DAGTypeLegalizer::ExpandOperand_SINT_TO_FP(SDOperand Source,
1589                                                      MVT::ValueType DestTy) {
1590   // We know the destination is legal, but that the input needs to be expanded.
1591   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
1592
1593   // Check to see if the target has a custom way to lower this.  If so, use it.
1594   switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) {
1595   default: assert(0 && "This action not implemented for this operation!");
1596   case TargetLowering::Legal:
1597   case TargetLowering::Expand:
1598     break;   // This case is handled below.
1599   case TargetLowering::Custom:
1600     SDOperand NV = TLI.LowerOperation(DAG.getNode(ISD::SINT_TO_FP, DestTy,
1601                                                   Source), DAG);
1602     if (NV.Val) return NV;
1603     break;   // The target lowered this.
1604   }
1605
1606   RTLIB::Libcall LC;
1607   if (DestTy == MVT::f32)
1608     LC = RTLIB::SINTTOFP_I64_F32;
1609   else {
1610     assert(DestTy == MVT::f64 && "Unknown fp value type!");
1611     LC = RTLIB::SINTTOFP_I64_F64;
1612   }
1613
1614   assert(0 && "FIXME: no libcalls yet!");
1615   abort();
1616 #if 0
1617   assert(TLI.getLibcallName(LC) && "Don't know how to expand this SINT_TO_FP!");
1618   Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source);
1619   SDOperand UnusedHiPart;
1620   return ExpandLibCall(TLI.getLibcallName(LC), Source.Val, true, UnusedHiPart);
1621 #endif
1622 }
1623
1624 SDOperand DAGTypeLegalizer::ExpandOperand_UINT_TO_FP(SDOperand Source,
1625                                                      MVT::ValueType DestTy) {
1626   // We know the destination is legal, but that the input needs to be expanded.
1627   assert(getTypeAction(Source.getValueType()) == Expand &&
1628          "This is not an expansion!");
1629   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
1630
1631   // If this is unsigned, and not supported, first perform the conversion to
1632   // signed, then adjust the result if the sign bit is set.
1633   SDOperand SignedConv = ExpandOperand_SINT_TO_FP(Source, DestTy);
1634
1635   // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
1636   // incoming integer is set.  To handle this, we dynamically test to see if
1637   // it is set, and, if so, add a fudge factor.
1638   SDOperand Lo, Hi;
1639   GetExpandedOp(Source, Lo, Hi);
1640
1641   SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi,
1642                                    DAG.getConstant(0, Hi.getValueType()),
1643                                    ISD::SETLT);
1644   SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
1645   SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
1646                                     SignSet, Four, Zero);
1647   uint64_t FF = 0x5f800000ULL;
1648   if (TLI.isLittleEndian()) FF <<= 32;
1649   Constant *FudgeFactor = ConstantInt::get(Type::Int64Ty, FF);
1650
1651   SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
1652   CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
1653   SDOperand FudgeInReg;
1654   if (DestTy == MVT::f32)
1655     FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, NULL, 0);
1656   else if (MVT::getSizeInBits(DestTy) > MVT::getSizeInBits(MVT::f32))
1657     // FIXME: Avoid the extend by construction the right constantpool?
1658     FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, DestTy, DAG.getEntryNode(),
1659                                 CPIdx, NULL, 0, MVT::f32);
1660   else
1661     assert(0 && "Unexpected conversion");
1662
1663   return DAG.getNode(ISD::FADD, DestTy, SignedConv, FudgeInReg);
1664 }
1665
1666
1667 SDOperand DAGTypeLegalizer::ExpandOperand_EXTRACT_ELEMENT(SDNode *N) {
1668   SDOperand Lo, Hi;
1669   GetExpandedOp(N->getOperand(0), Lo, Hi);
1670   return cast<ConstantSDNode>(N->getOperand(1))->getValue() ? Hi : Lo;
1671 }
1672
1673 SDOperand DAGTypeLegalizer::ExpandOperand_SETCC(SDNode *N) {
1674   SDOperand NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
1675   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(2))->get();
1676   ExpandSetCCOperands(NewLHS, NewRHS, CCCode);
1677
1678   // If ExpandSetCCOperands returned a scalar, use it.
1679   if (NewRHS.Val == 0) return NewLHS;
1680
1681   // Otherwise, update N to have the operands specified.
1682   return DAG.UpdateNodeOperands(SDOperand(N, 0), NewLHS, NewRHS,
1683                                 DAG.getCondCode(CCCode));
1684 }
1685
1686 /// ExpandSetCCOperands - Expand the operands of a comparison.  This code is
1687 /// shared among BR_CC, SELECT_CC, and SETCC handlers.
1688 void DAGTypeLegalizer::ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS,
1689                                            ISD::CondCode &CCCode) {
1690   SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
1691   GetExpandedOp(NewLHS, LHSLo, LHSHi);
1692   GetExpandedOp(NewRHS, RHSLo, RHSHi);
1693
1694   MVT::ValueType VT = NewLHS.getValueType();
1695   if (VT == MVT::f32 || VT == MVT::f64) {
1696     assert(0 && "FIXME: softfp not implemented yet! should be promote not exp");
1697   }
1698
1699   if (VT == MVT::ppcf128) {
1700     // FIXME:  This generated code sucks.  We want to generate
1701     //         FCMP crN, hi1, hi2
1702     //         BNE crN, L:
1703     //         FCMP crN, lo1, lo2
1704     // The following can be improved, but not that much.
1705     SDOperand Tmp1, Tmp2, Tmp3;
1706     Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ);
1707     Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, CCCode);
1708     Tmp3 = DAG.getNode(ISD::AND, Tmp1.getValueType(), Tmp1, Tmp2);
1709     Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETNE);
1710     Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, CCCode);
1711     Tmp1 = DAG.getNode(ISD::AND, Tmp1.getValueType(), Tmp1, Tmp2);
1712     NewLHS = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp3);
1713     NewRHS = SDOperand();   // LHS is the result, not a compare.
1714     return;
1715   }
1716
1717
1718   if (CCCode == ISD::SETEQ || CCCode == ISD::SETNE) {
1719     if (RHSLo == RHSHi)
1720       if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
1721         if (RHSCST->isAllOnesValue()) {
1722           // Equality comparison to -1.
1723           NewLHS = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
1724           NewRHS = RHSLo;
1725           return;
1726         }
1727
1728     NewLHS = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
1729     NewRHS = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
1730     NewLHS = DAG.getNode(ISD::OR, NewLHS.getValueType(), NewLHS, NewRHS);
1731     NewRHS = DAG.getConstant(0, NewLHS.getValueType());
1732     return;
1733   }
1734
1735   // If this is a comparison of the sign bit, just look at the top part.
1736   // X > -1,  x < 0
1737   if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(NewRHS))
1738     if ((CCCode == ISD::SETLT && CST->getValue() == 0) ||   // X < 0
1739         (CCCode == ISD::SETGT && CST->isAllOnesValue())) {  // X > -1
1740       NewLHS = LHSHi;
1741       NewRHS = RHSHi;
1742       return;
1743     }
1744
1745   // FIXME: This generated code sucks.
1746   ISD::CondCode LowCC;
1747   switch (CCCode) {
1748   default: assert(0 && "Unknown integer setcc!");
1749   case ISD::SETLT:
1750   case ISD::SETULT: LowCC = ISD::SETULT; break;
1751   case ISD::SETGT:
1752   case ISD::SETUGT: LowCC = ISD::SETUGT; break;
1753   case ISD::SETLE:
1754   case ISD::SETULE: LowCC = ISD::SETULE; break;
1755   case ISD::SETGE:
1756   case ISD::SETUGE: LowCC = ISD::SETUGE; break;
1757   }
1758
1759   // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
1760   // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
1761   // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
1762
1763   // NOTE: on targets without efficient SELECT of bools, we can always use
1764   // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
1765   TargetLowering::DAGCombinerInfo DagCombineInfo(DAG, false, true, NULL);
1766   SDOperand Tmp1, Tmp2;
1767   Tmp1 = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC,
1768                            false, DagCombineInfo);
1769   if (!Tmp1.Val)
1770     Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC);
1771   Tmp2 = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi,
1772                            CCCode, false, DagCombineInfo);
1773   if (!Tmp2.Val)
1774     Tmp2 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), LHSHi, RHSHi,
1775                        DAG.getCondCode(CCCode));
1776
1777   ConstantSDNode *Tmp1C = dyn_cast<ConstantSDNode>(Tmp1.Val);
1778   ConstantSDNode *Tmp2C = dyn_cast<ConstantSDNode>(Tmp2.Val);
1779   if ((Tmp1C && Tmp1C->getValue() == 0) ||
1780       (Tmp2C && Tmp2C->getValue() == 0 &&
1781        (CCCode == ISD::SETLE || CCCode == ISD::SETGE ||
1782         CCCode == ISD::SETUGE || CCCode == ISD::SETULE)) ||
1783       (Tmp2C && Tmp2C->getValue() == 1 &&
1784        (CCCode == ISD::SETLT || CCCode == ISD::SETGT ||
1785         CCCode == ISD::SETUGT || CCCode == ISD::SETULT))) {
1786     // low part is known false, returns high part.
1787     // For LE / GE, if high part is known false, ignore the low part.
1788     // For LT / GT, if high part is known true, ignore the low part.
1789     NewLHS = Tmp2;
1790     NewRHS = SDOperand();
1791     return;
1792   }
1793
1794   NewLHS = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi,
1795                              ISD::SETEQ, false, DagCombineInfo);
1796   if (!NewLHS.Val)
1797     NewLHS = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ);
1798   NewLHS = DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
1799                        NewLHS, Tmp1, Tmp2);
1800   NewRHS = SDOperand();
1801 }
1802
1803
1804 SDOperand DAGTypeLegalizer::ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo) {
1805   assert(OpNo == 1 && "Can only expand the stored value so far");
1806   assert(!N->isTruncatingStore() && "Can't expand truncstore!");
1807
1808   unsigned IncrementSize = 0;
1809   SDOperand Lo, Hi;
1810
1811   // If this is a vector type, then we have to calculate the increment as
1812   // the product of the element size in bytes, and the number of elements
1813   // in the high half of the vector.
1814   if (MVT::isVector(N->getValue().getValueType())) {
1815     assert(0 && "Vectors not supported yet");
1816 #if 0
1817     SDNode *InVal = ST->getValue().Val;
1818     unsigned NumElems = MVT::getVectorNumElements(InVal->getValueType(0));
1819     MVT::ValueType EVT = MVT::getVectorElementType(InVal->getValueType(0));
1820
1821     // Figure out if there is a simple type corresponding to this Vector
1822     // type.  If so, convert to the vector type.
1823     MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
1824     if (TLI.isTypeLegal(TVT)) {
1825       // Turn this into a normal store of the vector type.
1826       Tmp3 = LegalizeOp(Node->getOperand(1));
1827       Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1828                             SVOffset, isVolatile, Alignment);
1829       Result = LegalizeOp(Result);
1830       break;
1831     } else if (NumElems == 1) {
1832       // Turn this into a normal store of the scalar type.
1833       Tmp3 = ScalarizeVectorOp(Node->getOperand(1));
1834       Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1835                             SVOffset, isVolatile, Alignment);
1836       // The scalarized value type may not be legal, e.g. it might require
1837       // promotion or expansion.  Relegalize the scalar store.
1838       return LegalizeOp(Result);
1839     } else {
1840       SplitVectorOp(Node->getOperand(1), Lo, Hi);
1841       IncrementSize = NumElems/2 * MVT::getSizeInBits(EVT)/8;
1842     }
1843 #endif
1844   } else {
1845     GetExpandedOp(N->getValue(), Lo, Hi);
1846     IncrementSize = Hi.Val ? MVT::getSizeInBits(Hi.getValueType())/8 : 0;
1847
1848     if (!TLI.isLittleEndian())
1849       std::swap(Lo, Hi);
1850   }
1851
1852   SDOperand Chain    = N->getChain();
1853   SDOperand Ptr      = N->getBasePtr();
1854   int SVOffset       = N->getSrcValueOffset();
1855   unsigned Alignment = N->getAlignment();
1856   bool isVolatile    = N->isVolatile();
1857
1858   Lo = DAG.getStore(Chain, Lo, Ptr, N->getSrcValue(),
1859                     SVOffset, isVolatile, Alignment);
1860
1861   assert(Hi.Val && "FIXME: int <-> float should be handled with promote!");
1862 #if 0
1863   if (Hi.Val == NULL) {
1864     // Must be int <-> float one-to-one expansion.
1865     return Lo;
1866   }
1867 #endif
1868
1869   Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1870                     getIntPtrConstant(IncrementSize));
1871   assert(isTypeLegal(Ptr.getValueType()) && "Pointers must be legal!");
1872   Hi = DAG.getStore(Chain, Hi, Ptr, N->getSrcValue(), SVOffset+IncrementSize,
1873                     isVolatile, std::max(Alignment, IncrementSize));
1874   return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1875 }
1876
1877 //===----------------------------------------------------------------------===//
1878 //  Entry Point
1879 //===----------------------------------------------------------------------===//
1880
1881 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
1882 /// only uses types natively supported by the target.
1883 ///
1884 /// Note that this is an involved process that may invalidate pointers into
1885 /// the graph.
1886 void SelectionDAG::LegalizeTypes() {
1887   DAGTypeLegalizer(*this).run();
1888 }
1889