lib/CodeGen/SelectionDAG/LegalizeDAGTypes.cpp

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