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