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