lib/CodeGen/SelectionDAG/LegalizeTypesExpand.cpp

   1 //===-- LegalizeTypesExpand.cpp - Expansion for 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 expansion support for LegalizeTypes.  Expansion is the
  11 // act of changing a computation in an invalid type to be a computation in
  12 // multiple registers of a smaller type.  For example, implementing i64
  13 // arithmetic in two i32 registers (as is often needed on 32-bit targets, for
  14 // example).
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "LegalizeTypes.h"
  19 #include "llvm/Constants.h"
  20 using namespace llvm;
  21
  22 //===----------------------------------------------------------------------===//
  23 //  Result Expansion
  24 //===----------------------------------------------------------------------===//
  25
  26 /// ExpandResult - This method is called when the specified result of the
  27 /// specified node is found to need expansion.  At this point, the node may also
  28 /// have invalid operands or may have other results that need promotion, we just
  29 /// know that (at least) one result needs expansion.
  30 void DAGTypeLegalizer::ExpandResult(SDNode *N, unsigned ResNo) {
  31   DEBUG(cerr << "Expand node result: "; N->dump(&DAG); cerr << "\n");
  32   SDOperand Lo, Hi;
  33   Lo = Hi = SDOperand();
  34
  35   // See if the target wants to custom expand this node.
  36   if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) ==
  37           TargetLowering::Custom) {
  38     // If the target wants to, allow it to lower this itself.
  39     if (SDNode *P = TLI.ExpandOperationResult(N, DAG)) {
  40       // Everything that once used N now uses P.  We are guaranteed that the
  41       // result value types of N and the result value types of P match.
  42       ReplaceNodeWith(N, P);
  43       return;
  44     }
  45   }
  46
  47   switch (N->getOpcode()) {
  48   default:
  49 #ifndef NDEBUG
  50     cerr << "ExpandResult #" << ResNo << ": ";
  51     N->dump(&DAG); cerr << "\n";
  52 #endif
  53     assert(0 && "Do not know how to expand the result of this operator!");
  54     abort();
  55
  56   case ISD::UNDEF:       ExpandResult_UNDEF(N, Lo, Hi); break;
  57   case ISD::Constant:    ExpandResult_Constant(N, Lo, Hi); break;
  58   case ISD::BUILD_PAIR:  ExpandResult_BUILD_PAIR(N, Lo, Hi); break;
  59   case ISD::MERGE_VALUES: ExpandResult_MERGE_VALUES(N, Lo, Hi); break;
  60   case ISD::ANY_EXTEND:  ExpandResult_ANY_EXTEND(N, Lo, Hi); break;
  61   case ISD::ZERO_EXTEND: ExpandResult_ZERO_EXTEND(N, Lo, Hi); break;
  62   case ISD::SIGN_EXTEND: ExpandResult_SIGN_EXTEND(N, Lo, Hi); break;
  63   case ISD::BIT_CONVERT: ExpandResult_BIT_CONVERT(N, Lo, Hi); break;
  64   case ISD::SIGN_EXTEND_INREG: ExpandResult_SIGN_EXTEND_INREG(N, Lo, Hi); break;
  65   case ISD::LOAD:        ExpandResult_LOAD(cast<LoadSDNode>(N), Lo, Hi); break;
  66
  67   case ISD::AND:
  68   case ISD::OR:
  69   case ISD::XOR:         ExpandResult_Logical(N, Lo, Hi); break;
  70   case ISD::BSWAP:       ExpandResult_BSWAP(N, Lo, Hi); break;
  71   case ISD::ADD:
  72   case ISD::SUB:         ExpandResult_ADDSUB(N, Lo, Hi); break;
  73   case ISD::ADDC:
  74   case ISD::SUBC:        ExpandResult_ADDSUBC(N, Lo, Hi); break;
  75   case ISD::ADDE:
  76   case ISD::SUBE:        ExpandResult_ADDSUBE(N, Lo, Hi); break;
  77   case ISD::SELECT:      ExpandResult_SELECT(N, Lo, Hi); break;
  78   case ISD::SELECT_CC:   ExpandResult_SELECT_CC(N, Lo, Hi); break;
  79   case ISD::MUL:         ExpandResult_MUL(N, Lo, Hi); break;
  80   case ISD::SHL:
  81   case ISD::SRA:
  82   case ISD::SRL:         ExpandResult_Shift(N, Lo, Hi); break;
  83   }
  84
  85   // If Lo/Hi is null, the sub-method took care of registering results etc.
  86   if (Lo.Val)
  87     SetExpandedOp(SDOperand(N, ResNo), Lo, Hi);
  88 }
  89
  90 void DAGTypeLegalizer::ExpandResult_UNDEF(SDNode *N,
  91                                           SDOperand &Lo, SDOperand &Hi) {
  92   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
  93   Lo = Hi = DAG.getNode(ISD::UNDEF, NVT);
  94 }
  95
  96 void DAGTypeLegalizer::ExpandResult_Constant(SDNode *N,
  97                                              SDOperand &Lo, SDOperand &Hi) {
  98   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
  99   uint64_t Cst = cast<ConstantSDNode>(N)->getValue();
 100   Lo = DAG.getConstant(Cst, NVT);
 101   Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
 102 }
 103
 104 void DAGTypeLegalizer::ExpandResult_BUILD_PAIR(SDNode *N,
 105                                                SDOperand &Lo, SDOperand &Hi) {
 106   // Return the operands.
 107   Lo = N->getOperand(0);
 108   Hi = N->getOperand(1);
 109 }
 110
 111 void DAGTypeLegalizer::ExpandResult_MERGE_VALUES(SDNode *N,
 112                                                  SDOperand &Lo, SDOperand &Hi) {
 113   // A MERGE_VALUES node can produce any number of values.  We know that the
 114   // first illegal one needs to be expanded into Lo/Hi.
 115   unsigned i;
 116
 117   // The string of legal results gets turns into the input operands, which have
 118   // the same type.
 119   for (i = 0; isTypeLegal(N->getValueType(i)); ++i)
 120     ReplaceValueWith(SDOperand(N, i), SDOperand(N->getOperand(i)));
 121
 122   // The first illegal result must be the one that needs to be expanded.
 123   GetExpandedOp(N->getOperand(i), Lo, Hi);
 124
 125   // Legalize the rest of the results into the input operands whether they are
 126   // legal or not.
 127   unsigned e = N->getNumValues();
 128   for (++i; i != e; ++i)
 129     ReplaceValueWith(SDOperand(N, i), SDOperand(N->getOperand(i)));
 130 }
 131
 132 void DAGTypeLegalizer::ExpandResult_ANY_EXTEND(SDNode *N,
 133                                                SDOperand &Lo, SDOperand &Hi) {
 134   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 135   SDOperand Op = N->getOperand(0);
 136   if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) {
 137     // The low part is any extension of the input (which degenerates to a copy).
 138     Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, Op);
 139     Hi = DAG.getNode(ISD::UNDEF, NVT);   // The high part is undefined.
 140   } else {
 141     // For example, extension of an i48 to an i64.  The operand type necessarily
 142     // promotes to the result type, so will end up being expanded too.
 143     assert(getTypeAction(Op.getValueType()) == Promote &&
 144            "Don't know how to expand this result!");
 145     SDOperand Res = GetPromotedOp(Op);
 146     assert(Res.getValueType() == N->getValueType(0) &&
 147            "Operand over promoted?");
 148     // Split the promoted operand.  This will simplify when it is expanded.
 149     SplitOp(Res, Lo, Hi);
 150   }
 151 }
 152
 153 void DAGTypeLegalizer::ExpandResult_ZERO_EXTEND(SDNode *N,
 154                                                 SDOperand &Lo, SDOperand &Hi) {
 155   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 156   SDOperand Op = N->getOperand(0);
 157   if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) {
 158     // The low part is zero extension of the input (which degenerates to a copy).
 159     Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, N->getOperand(0));
 160     Hi = DAG.getConstant(0, NVT);   // The high part is just a zero.
 161   } else {
 162     // For example, extension of an i48 to an i64.  The operand type necessarily
 163     // promotes to the result type, so will end up being expanded too.
 164     assert(getTypeAction(Op.getValueType()) == Promote &&
 165            "Don't know how to expand this result!");
 166     SDOperand Res = GetPromotedOp(Op);
 167     assert(Res.getValueType() == N->getValueType(0) &&
 168            "Operand over promoted?");
 169     // Split the promoted operand.  This will simplify when it is expanded.
 170     SplitOp(Res, Lo, Hi);
 171     unsigned ExcessBits =
 172       MVT::getSizeInBits(Op.getValueType()) - MVT::getSizeInBits(NVT);
 173     Hi = DAG.getZeroExtendInReg(Hi, MVT::getIntegerType(ExcessBits));
 174   }
 175 }
 176
 177 void DAGTypeLegalizer::ExpandResult_SIGN_EXTEND(SDNode *N,
 178                                                 SDOperand &Lo, SDOperand &Hi) {
 179   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 180   SDOperand Op = N->getOperand(0);
 181   if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) {
 182     // The low part is sign extension of the input (which degenerates to a copy).
 183     Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, N->getOperand(0));
 184     // The high part is obtained by SRA'ing all but one of the bits of low part.
 185     unsigned LoSize = MVT::getSizeInBits(NVT);
 186     Hi = DAG.getNode(ISD::SRA, NVT, Lo,
 187                      DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
 188   } else {
 189     // For example, extension of an i48 to an i64.  The operand type necessarily
 190     // promotes to the result type, so will end up being expanded too.
 191     assert(getTypeAction(Op.getValueType()) == Promote &&
 192            "Don't know how to expand this result!");
 193     SDOperand Res = GetPromotedOp(Op);
 194     assert(Res.getValueType() == N->getValueType(0) &&
 195            "Operand over promoted?");
 196     // Split the promoted operand.  This will simplify when it is expanded.
 197     SplitOp(Res, Lo, Hi);
 198     unsigned ExcessBits =
 199       MVT::getSizeInBits(Op.getValueType()) - MVT::getSizeInBits(NVT);
 200     Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, Hi.getValueType(), Hi,
 201                      DAG.getValueType(MVT::getIntegerType(ExcessBits)));
 202   }
 203 }
 204
 205 void DAGTypeLegalizer::ExpandResult_BIT_CONVERT(SDNode *N,
 206                                                 SDOperand &Lo, SDOperand &Hi) {
 207   // Lower the bit-convert to a store/load from the stack, then expand the load.
 208   SDOperand Op = CreateStackStoreLoad(N->getOperand(0), N->getValueType(0));
 209   ExpandResult_LOAD(cast<LoadSDNode>(Op.Val), Lo, Hi);
 210 }
 211
 212 void DAGTypeLegalizer::
 213 ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
 214   GetExpandedOp(N->getOperand(0), Lo, Hi);
 215   MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
 216
 217   if (MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(Lo.getValueType())) {
 218     // sext_inreg the low part if needed.
 219     Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, Lo.getValueType(), Lo,
 220                      N->getOperand(1));
 221
 222     // The high part gets the sign extension from the lo-part.  This handles
 223     // things like sextinreg V:i64 from i8.
 224     Hi = DAG.getNode(ISD::SRA, Hi.getValueType(), Lo,
 225                      DAG.getConstant(MVT::getSizeInBits(Hi.getValueType())-1,
 226                                      TLI.getShiftAmountTy()));
 227   } else {
 228     // For example, extension of an i48 to an i64.  Leave the low part alone,
 229     // sext_inreg the high part.
 230     unsigned ExcessBits =
 231       MVT::getSizeInBits(EVT) - MVT::getSizeInBits(Lo.getValueType());
 232     Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, Hi.getValueType(), Hi,
 233                      DAG.getValueType(MVT::getIntegerType(ExcessBits)));
 234   }
 235 }
 236
 237 void DAGTypeLegalizer::ExpandResult_LOAD(LoadSDNode *N,
 238                                          SDOperand &Lo, SDOperand &Hi) {
 239   MVT::ValueType VT = N->getValueType(0);
 240   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 241   SDOperand Ch  = N->getChain();    // Legalize the chain.
 242   SDOperand Ptr = N->getBasePtr();  // Legalize the pointer.
 243   ISD::LoadExtType ExtType = N->getExtensionType();
 244   int SVOffset = N->getSrcValueOffset();
 245   unsigned Alignment = N->getAlignment();
 246   bool isVolatile = N->isVolatile();
 247
 248   assert(!(MVT::getSizeInBits(NVT) & 7) && "Expanded type not byte sized!");
 249
 250   if (ExtType == ISD::NON_EXTLOAD) {
 251     Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
 252                      isVolatile, Alignment);
 253     // Increment the pointer to the other half.
 254     unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
 255     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
 256                       getIntPtrConstant(IncrementSize));
 257     Hi = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset+IncrementSize,
 258                      isVolatile, MinAlign(Alignment, IncrementSize));
 259
 260     // Build a factor node to remember that this load is independent of the
 261     // other one.
 262     Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
 263                      Hi.getValue(1));
 264
 265     // Handle endianness of the load.
 266     if (!TLI.isLittleEndian())
 267       std::swap(Lo, Hi);
 268   } else if (MVT::getSizeInBits(N->getLoadedVT()) <= MVT::getSizeInBits(NVT)) {
 269     MVT::ValueType EVT = N->getLoadedVT();
 270
 271     Lo = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(), SVOffset, EVT,
 272                         isVolatile, Alignment);
 273
 274     // Remember the chain.
 275     Ch = Lo.getValue(1);
 276
 277     if (ExtType == ISD::SEXTLOAD) {
 278       // The high part is obtained by SRA'ing all but one of the bits of the
 279       // lo part.
 280       unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
 281       Hi = DAG.getNode(ISD::SRA, NVT, Lo,
 282                        DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
 283     } else if (ExtType == ISD::ZEXTLOAD) {
 284       // The high part is just a zero.
 285       Hi = DAG.getConstant(0, NVT);
 286     } else {
 287       assert(ExtType == ISD::EXTLOAD && "Unknown extload!");
 288       // The high part is undefined.
 289       Hi = DAG.getNode(ISD::UNDEF, NVT);
 290     }
 291   } else if (TLI.isLittleEndian()) {
 292     // Little-endian - low bits are at low addresses.
 293     Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
 294                      isVolatile, Alignment);
 295
 296     unsigned ExcessBits =
 297       MVT::getSizeInBits(N->getLoadedVT()) - MVT::getSizeInBits(NVT);
 298     MVT::ValueType NEVT = MVT::getIntegerType(ExcessBits);
 299
 300     // Increment the pointer to the other half.
 301     unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
 302     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
 303                       getIntPtrConstant(IncrementSize));
 304     Hi = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(),
 305                         SVOffset+IncrementSize, NEVT,
 306                         isVolatile, MinAlign(Alignment, IncrementSize));
 307
 308     // Build a factor node to remember that this load is independent of the
 309     // other one.
 310     Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
 311                      Hi.getValue(1));
 312   } else {
 313     // Big-endian - high bits are at low addresses.  Favor aligned loads at
 314     // the cost of some bit-fiddling.
 315     MVT::ValueType EVT = N->getLoadedVT();
 316     unsigned EBytes = MVT::getStoreSizeInBits(EVT)/8;
 317     unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
 318     unsigned ExcessBits = (EBytes - IncrementSize)*8;
 319
 320     // Load both the high bits and maybe some of the low bits.
 321     Hi = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
 322                         MVT::getIntegerType(MVT::getSizeInBits(EVT)-ExcessBits),
 323                         isVolatile, Alignment);
 324
 325     // Increment the pointer to the other half.
 326     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
 327                       getIntPtrConstant(IncrementSize));
 328     // Load the rest of the low bits.
 329     Lo = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Ch, Ptr, N->getSrcValue(),
 330                         SVOffset+IncrementSize, MVT::getIntegerType(ExcessBits),
 331                         isVolatile, MinAlign(Alignment, IncrementSize));
 332
 333     // Build a factor node to remember that this load is independent of the
 334     // other one.
 335     Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
 336                      Hi.getValue(1));
 337
 338     if (ExcessBits < MVT::getSizeInBits(NVT)) {
 339       // Transfer low bits from the bottom of Hi to the top of Lo.
 340       Lo = DAG.getNode(ISD::OR, NVT, Lo,
 341                        DAG.getNode(ISD::SHL, NVT, Hi,
 342                                    DAG.getConstant(ExcessBits,
 343                                                    TLI.getShiftAmountTy())));
 344       // Move high bits to the right position in Hi.
 345       Hi = DAG.getNode(ExtType == ISD::SEXTLOAD ? ISD::SRA : ISD::SRL, NVT, Hi,
 346                        DAG.getConstant(MVT::getSizeInBits(NVT) - ExcessBits,
 347                                        TLI.getShiftAmountTy()));
 348     }
 349   }
 350
 351   // Legalized the chain result - switch anything that used the old chain to
 352   // use the new one.
 353   ReplaceValueWith(SDOperand(N, 1), Ch);
 354 }
 355
 356 void DAGTypeLegalizer::ExpandResult_Logical(SDNode *N,
 357                                             SDOperand &Lo, SDOperand &Hi) {
 358   SDOperand LL, LH, RL, RH;
 359   GetExpandedOp(N->getOperand(0), LL, LH);
 360   GetExpandedOp(N->getOperand(1), RL, RH);
 361   Lo = DAG.getNode(N->getOpcode(), LL.getValueType(), LL, RL);
 362   Hi = DAG.getNode(N->getOpcode(), LL.getValueType(), LH, RH);
 363 }
 364
 365 void DAGTypeLegalizer::ExpandResult_BSWAP(SDNode *N,
 366                                           SDOperand &Lo, SDOperand &Hi) {
 367   GetExpandedOp(N->getOperand(0), Hi, Lo);  // Note swapped operands.
 368   Lo = DAG.getNode(ISD::BSWAP, Lo.getValueType(), Lo);
 369   Hi = DAG.getNode(ISD::BSWAP, Hi.getValueType(), Hi);
 370 }
 371
 372 void DAGTypeLegalizer::ExpandResult_SELECT(SDNode *N,
 373                                            SDOperand &Lo, SDOperand &Hi) {
 374   SDOperand LL, LH, RL, RH;
 375   GetExpandedOp(N->getOperand(1), LL, LH);
 376   GetExpandedOp(N->getOperand(2), RL, RH);
 377   Lo = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LL, RL);
 378
 379   assert(N->getOperand(0).getValueType() != MVT::f32 &&
 380          "FIXME: softfp shouldn't use expand!");
 381   Hi = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LH, RH);
 382 }
 383
 384 void DAGTypeLegalizer::ExpandResult_SELECT_CC(SDNode *N,
 385                                               SDOperand &Lo, SDOperand &Hi) {
 386   SDOperand LL, LH, RL, RH;
 387   GetExpandedOp(N->getOperand(2), LL, LH);
 388   GetExpandedOp(N->getOperand(3), RL, RH);
 389   Lo = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0),
 390                    N->getOperand(1), LL, RL, N->getOperand(4));
 391
 392   assert(N->getOperand(0).getValueType() != MVT::f32 &&
 393          "FIXME: softfp shouldn't use expand!");
 394   Hi = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0),
 395                    N->getOperand(1), LH, RH, N->getOperand(4));
 396 }
 397
 398 void DAGTypeLegalizer::ExpandResult_ADDSUB(SDNode *N,
 399                                            SDOperand &Lo, SDOperand &Hi) {
 400   // Expand the subcomponents.
 401   SDOperand LHSL, LHSH, RHSL, RHSH;
 402   GetExpandedOp(N->getOperand(0), LHSL, LHSH);
 403   GetExpandedOp(N->getOperand(1), RHSL, RHSH);
 404   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
 405   SDOperand LoOps[2] = { LHSL, RHSL };
 406   SDOperand HiOps[3] = { LHSH, RHSH };
 407
 408   if (N->getOpcode() == ISD::ADD) {
 409     Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
 410     HiOps[2] = Lo.getValue(1);
 411     Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
 412   } else {
 413     Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
 414     HiOps[2] = Lo.getValue(1);
 415     Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
 416   }
 417 }
 418
 419 void DAGTypeLegalizer::ExpandResult_ADDSUBC(SDNode *N,
 420                                             SDOperand &Lo, SDOperand &Hi) {
 421   // Expand the subcomponents.
 422   SDOperand LHSL, LHSH, RHSL, RHSH;
 423   GetExpandedOp(N->getOperand(0), LHSL, LHSH);
 424   GetExpandedOp(N->getOperand(1), RHSL, RHSH);
 425   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
 426   SDOperand LoOps[2] = { LHSL, RHSL };
 427   SDOperand HiOps[3] = { LHSH, RHSH };
 428
 429   if (N->getOpcode() == ISD::ADDC) {
 430     Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
 431     HiOps[2] = Lo.getValue(1);
 432     Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
 433   } else {
 434     Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
 435     HiOps[2] = Lo.getValue(1);
 436     Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
 437   }
 438
 439   // Legalized the flag result - switch anything that used the old flag to
 440   // use the new one.
 441   ReplaceValueWith(SDOperand(N, 1), Hi.getValue(1));
 442 }
 443
 444 void DAGTypeLegalizer::ExpandResult_ADDSUBE(SDNode *N,
 445                                             SDOperand &Lo, SDOperand &Hi) {
 446   // Expand the subcomponents.
 447   SDOperand LHSL, LHSH, RHSL, RHSH;
 448   GetExpandedOp(N->getOperand(0), LHSL, LHSH);
 449   GetExpandedOp(N->getOperand(1), RHSL, RHSH);
 450   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
 451   SDOperand LoOps[3] = { LHSL, RHSL, N->getOperand(2) };
 452   SDOperand HiOps[3] = { LHSH, RHSH };
 453
 454   Lo = DAG.getNode(N->getOpcode(), VTList, LoOps, 3);
 455   HiOps[2] = Lo.getValue(1);
 456   Hi = DAG.getNode(N->getOpcode(), VTList, HiOps, 3);
 457
 458   // Legalized the flag result - switch anything that used the old flag to
 459   // use the new one.
 460   ReplaceValueWith(SDOperand(N, 1), Hi.getValue(1));
 461 }
 462
 463 void DAGTypeLegalizer::ExpandResult_MUL(SDNode *N,
 464                                         SDOperand &Lo, SDOperand &Hi) {
 465   MVT::ValueType VT = N->getValueType(0);
 466   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 467
 468   bool HasMULHS = TLI.isOperationLegal(ISD::MULHS, NVT);
 469   bool HasMULHU = TLI.isOperationLegal(ISD::MULHU, NVT);
 470   bool HasSMUL_LOHI = TLI.isOperationLegal(ISD::SMUL_LOHI, NVT);
 471   bool HasUMUL_LOHI = TLI.isOperationLegal(ISD::UMUL_LOHI, NVT);
 472   if (HasMULHU || HasMULHS || HasUMUL_LOHI || HasSMUL_LOHI) {
 473     SDOperand LL, LH, RL, RH;
 474     GetExpandedOp(N->getOperand(0), LL, LH);
 475     GetExpandedOp(N->getOperand(1), RL, RH);
 476     unsigned BitSize = MVT::getSizeInBits(NVT);
 477     unsigned LHSSB = DAG.ComputeNumSignBits(N->getOperand(0));
 478     unsigned RHSSB = DAG.ComputeNumSignBits(N->getOperand(1));
 479
 480     // FIXME: generalize this to handle other bit sizes
 481     if (LHSSB == 32 && RHSSB == 32 &&
 482         DAG.MaskedValueIsZero(N->getOperand(0), 0xFFFFFFFF00000000ULL) &&
 483         DAG.MaskedValueIsZero(N->getOperand(1), 0xFFFFFFFF00000000ULL)) {
 484       // The inputs are both zero-extended.
 485       if (HasUMUL_LOHI) {
 486         // We can emit a umul_lohi.
 487         Lo = DAG.getNode(ISD::UMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL);
 488         Hi = SDOperand(Lo.Val, 1);
 489         return;
 490       }
 491       if (HasMULHU) {
 492         // We can emit a mulhu+mul.
 493         Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
 494         Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
 495         return;
 496       }
 497     }
 498     if (LHSSB > BitSize && RHSSB > BitSize) {
 499       // The input values are both sign-extended.
 500       if (HasSMUL_LOHI) {
 501         // We can emit a smul_lohi.
 502         Lo = DAG.getNode(ISD::SMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL);
 503         Hi = SDOperand(Lo.Val, 1);
 504         return;
 505       }
 506       if (HasMULHS) {
 507         // We can emit a mulhs+mul.
 508         Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
 509         Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL);
 510         return;
 511       }
 512     }
 513     if (HasUMUL_LOHI) {
 514       // Lo,Hi = umul LHS, RHS.
 515       SDOperand UMulLOHI = DAG.getNode(ISD::UMUL_LOHI,
 516                                        DAG.getVTList(NVT, NVT), LL, RL);
 517       Lo = UMulLOHI;
 518       Hi = UMulLOHI.getValue(1);
 519       RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
 520       LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
 521       Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
 522       Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
 523       return;
 524     }
 525   }
 526
 527   abort();
 528 #if 0 // FIXME!
 529   // If nothing else, we can make a libcall.
 530   Lo = ExpandLibCall(TLI.getLibcallName(RTLIB::MUL_I64), N,
 531                      false/*sign irrelevant*/, Hi);
 532 #endif
 533 }
 534
 535
 536 void DAGTypeLegalizer::ExpandResult_Shift(SDNode *N,
 537                                           SDOperand &Lo, SDOperand &Hi) {
 538   MVT::ValueType VT = N->getValueType(0);
 539
 540   // If we can emit an efficient shift operation, do so now.  Check to see if
 541   // the RHS is a constant.
 542   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1)))
 543     return ExpandShiftByConstant(N, CN->getValue(), Lo, Hi);
 544
 545   // If we can determine that the high bit of the shift is zero or one, even if
 546   // the low bits are variable, emit this shift in an optimized form.
 547   if (ExpandShiftWithKnownAmountBit(N, Lo, Hi))
 548     return;
 549
 550   // If this target supports shift_PARTS, use it.  First, map to the _PARTS opc.
 551   unsigned PartsOpc;
 552   if (N->getOpcode() == ISD::SHL)
 553     PartsOpc = ISD::SHL_PARTS;
 554   else if (N->getOpcode() == ISD::SRL)
 555     PartsOpc = ISD::SRL_PARTS;
 556   else {
 557     assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
 558     PartsOpc = ISD::SRA_PARTS;
 559   }
 560
 561   // Next check to see if the target supports this SHL_PARTS operation or if it
 562   // will custom expand it.
 563   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
 564   TargetLowering::LegalizeAction Action = TLI.getOperationAction(PartsOpc, NVT);
 565   if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
 566       Action == TargetLowering::Custom) {
 567     // Expand the subcomponents.
 568     SDOperand LHSL, LHSH;
 569     GetExpandedOp(N->getOperand(0), LHSL, LHSH);
 570
 571     SDOperand Ops[] = { LHSL, LHSH, N->getOperand(1) };
 572     MVT::ValueType VT = LHSL.getValueType();
 573     Lo = DAG.getNode(PartsOpc, DAG.getNodeValueTypes(VT, VT), 2, Ops, 3);
 574     Hi = Lo.getValue(1);
 575     return;
 576   }
 577
 578   abort();
 579 #if 0 // FIXME!
 580   // Otherwise, emit a libcall.
 581   unsigned RuntimeCode = ; // SRL -> SRL_I64 etc.
 582   bool Signed = ;
 583   Lo = ExpandLibCall(TLI.getLibcallName(RTLIB::SRL_I64), N,
 584                      false/*lshr is unsigned*/, Hi);
 585 #endif
 586 }
 587
 588
 589 /// ExpandShiftByConstant - N is a shift by a value that needs to be expanded,
 590 /// and the shift amount is a constant 'Amt'.  Expand the operation.
 591 void DAGTypeLegalizer::ExpandShiftByConstant(SDNode *N, unsigned Amt,
 592                                              SDOperand &Lo, SDOperand &Hi) {
 593   // Expand the incoming operand to be shifted, so that we have its parts
 594   SDOperand InL, InH;
 595   GetExpandedOp(N->getOperand(0), InL, InH);
 596
 597   MVT::ValueType NVT = InL.getValueType();
 598   unsigned VTBits = MVT::getSizeInBits(N->getValueType(0));
 599   unsigned NVTBits = MVT::getSizeInBits(NVT);
 600   MVT::ValueType ShTy = N->getOperand(1).getValueType();
 601
 602   if (N->getOpcode() == ISD::SHL) {
 603     if (Amt > VTBits) {
 604       Lo = Hi = DAG.getConstant(0, NVT);
 605     } else if (Amt > NVTBits) {
 606       Lo = DAG.getConstant(0, NVT);
 607       Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt-NVTBits,ShTy));
 608     } else if (Amt == NVTBits) {
 609       Lo = DAG.getConstant(0, NVT);
 610       Hi = InL;
 611     } else {
 612       Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt, ShTy));
 613       Hi = DAG.getNode(ISD::OR, NVT,
 614                        DAG.getNode(ISD::SHL, NVT, InH,
 615                                    DAG.getConstant(Amt, ShTy)),
 616                        DAG.getNode(ISD::SRL, NVT, InL,
 617                                    DAG.getConstant(NVTBits-Amt, ShTy)));
 618     }
 619     return;
 620   }
 621
 622   if (N->getOpcode() == ISD::SRL) {
 623     if (Amt > VTBits) {
 624       Lo = DAG.getConstant(0, NVT);
 625       Hi = DAG.getConstant(0, NVT);
 626     } else if (Amt > NVTBits) {
 627       Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Amt-NVTBits,ShTy));
 628       Hi = DAG.getConstant(0, NVT);
 629     } else if (Amt == NVTBits) {
 630       Lo = InH;
 631       Hi = DAG.getConstant(0, NVT);
 632     } else {
 633       Lo = DAG.getNode(ISD::OR, NVT,
 634                        DAG.getNode(ISD::SRL, NVT, InL,
 635                                    DAG.getConstant(Amt, ShTy)),
 636                        DAG.getNode(ISD::SHL, NVT, InH,
 637                                    DAG.getConstant(NVTBits-Amt, ShTy)));
 638       Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Amt, ShTy));
 639     }
 640     return;
 641   }
 642
 643   assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
 644   if (Amt > VTBits) {
 645     Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
 646                           DAG.getConstant(NVTBits-1, ShTy));
 647   } else if (Amt > NVTBits) {
 648     Lo = DAG.getNode(ISD::SRA, NVT, InH,
 649                      DAG.getConstant(Amt-NVTBits, ShTy));
 650     Hi = DAG.getNode(ISD::SRA, NVT, InH,
 651                      DAG.getConstant(NVTBits-1, ShTy));
 652   } else if (Amt == NVTBits) {
 653     Lo = InH;
 654     Hi = DAG.getNode(ISD::SRA, NVT, InH,
 655                      DAG.getConstant(NVTBits-1, ShTy));
 656   } else {
 657     Lo = DAG.getNode(ISD::OR, NVT,
 658                      DAG.getNode(ISD::SRL, NVT, InL,
 659                                  DAG.getConstant(Amt, ShTy)),
 660                      DAG.getNode(ISD::SHL, NVT, InH,
 661                                  DAG.getConstant(NVTBits-Amt, ShTy)));
 662     Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Amt, ShTy));
 663   }
 664 }
 665
 666 /// ExpandShiftWithKnownAmountBit - Try to determine whether we can simplify
 667 /// this shift based on knowledge of the high bit of the shift amount.  If we
 668 /// can tell this, we know that it is >= 32 or < 32, without knowing the actual
 669 /// shift amount.
 670 bool DAGTypeLegalizer::
 671 ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
 672   MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
 673   unsigned NVTBits = MVT::getSizeInBits(NVT);
 674   assert(!(NVTBits & (NVTBits - 1)) &&
 675          "Expanded integer type size not a power of two!");
 676
 677   uint64_t HighBitMask = NVTBits, KnownZero, KnownOne;
 678   DAG.ComputeMaskedBits(N->getOperand(1), HighBitMask, KnownZero, KnownOne);
 679
 680   // If we don't know anything about the high bit, exit.
 681   if (((KnownZero|KnownOne) & HighBitMask) == 0)
 682     return false;
 683
 684   // Get the incoming operand to be shifted.
 685   SDOperand InL, InH;
 686   GetExpandedOp(N->getOperand(0), InL, InH);
 687   SDOperand Amt = N->getOperand(1);
 688
 689   // If we know that the high bit of the shift amount is one, then we can do
 690   // this as a couple of simple shifts.
 691   if (KnownOne & HighBitMask) {
 692     // Mask out the high bit, which we know is set.
 693     Amt = DAG.getNode(ISD::AND, Amt.getValueType(), Amt,
 694                       DAG.getConstant(NVTBits-1, Amt.getValueType()));
 695
 696     switch (N->getOpcode()) {
 697     default: assert(0 && "Unknown shift");
 698     case ISD::SHL:
 699       Lo = DAG.getConstant(0, NVT);              // Low part is zero.
 700       Hi = DAG.getNode(ISD::SHL, NVT, InL, Amt); // High part from Lo part.
 701       return true;
 702     case ISD::SRL:
 703       Hi = DAG.getConstant(0, NVT);              // Hi part is zero.
 704       Lo = DAG.getNode(ISD::SRL, NVT, InH, Amt); // Lo part from Hi part.
 705       return true;
 706     case ISD::SRA:
 707       Hi = DAG.getNode(ISD::SRA, NVT, InH,       // Sign extend high part.
 708                        DAG.getConstant(NVTBits-1, Amt.getValueType()));
 709       Lo = DAG.getNode(ISD::SRA, NVT, InH, Amt); // Lo part from Hi part.
 710       return true;
 711     }
 712   }
 713
 714   // If we know that the high bit of the shift amount is zero, then we can do
 715   // this as a couple of simple shifts.
 716   assert((KnownZero & HighBitMask) && "Bad mask computation above");
 717
 718   // Compute 32-amt.
 719   SDOperand Amt2 = DAG.getNode(ISD::SUB, Amt.getValueType(),
 720                                DAG.getConstant(NVTBits, Amt.getValueType()),
 721                                Amt);
 722   unsigned Op1, Op2;
 723   switch (N->getOpcode()) {
 724   default: assert(0 && "Unknown shift");
 725   case ISD::SHL:  Op1 = ISD::SHL; Op2 = ISD::SRL; break;
 726   case ISD::SRL:
 727   case ISD::SRA:  Op1 = ISD::SRL; Op2 = ISD::SHL; break;
 728   }
 729
 730   Lo = DAG.getNode(N->getOpcode(), NVT, InL, Amt);
 731   Hi = DAG.getNode(ISD::OR, NVT,
 732                    DAG.getNode(Op1, NVT, InH, Amt),
 733                    DAG.getNode(Op2, NVT, InL, Amt2));
 734   return true;
 735 }
 736
 737
 738 //===----------------------------------------------------------------------===//
 739 //  Operand Expansion
 740 //===----------------------------------------------------------------------===//
 741
 742 /// ExpandOperand - This method is called when the specified operand of the
 743 /// specified node is found to need expansion.  At this point, all of the result
 744 /// types of the node are known to be legal, but other operands of the node may
 745 /// need promotion or expansion as well as the specified one.
 746 bool DAGTypeLegalizer::ExpandOperand(SDNode *N, unsigned OpNo) {
 747   DEBUG(cerr << "Expand node operand: "; N->dump(&DAG); cerr << "\n");
 748   SDOperand Res(0, 0);
 749
 750   if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) ==
 751       TargetLowering::Custom)
 752     Res = TLI.LowerOperation(SDOperand(N, 0), DAG);
 753
 754   if (Res.Val == 0) {
 755     switch (N->getOpcode()) {
 756     default:
 757   #ifndef NDEBUG
 758       cerr << "ExpandOperand Op #" << OpNo << ": ";
 759       N->dump(&DAG); cerr << "\n";
 760   #endif
 761       assert(0 && "Do not know how to expand this operator's operand!");
 762       abort();
 763
 764     case ISD::TRUNCATE:        Res = ExpandOperand_TRUNCATE(N); break;
 765     case ISD::BIT_CONVERT:     Res = ExpandOperand_BIT_CONVERT(N); break;
 766
 767     case ISD::SINT_TO_FP:
 768       Res = ExpandOperand_SINT_TO_FP(N->getOperand(0), N->getValueType(0));
 769       break;
 770     case ISD::UINT_TO_FP:
 771       Res = ExpandOperand_UINT_TO_FP(N->getOperand(0), N->getValueType(0));
 772       break;
 773     case ISD::EXTRACT_ELEMENT: Res = ExpandOperand_EXTRACT_ELEMENT(N); break;
 774     case ISD::SETCC:           Res = ExpandOperand_SETCC(N); break;
 775
 776     case ISD::STORE:
 777       Res = ExpandOperand_STORE(cast<StoreSDNode>(N), OpNo);
 778       break;
 779     case ISD::MEMSET:
 780     case ISD::MEMCPY:
 781     case ISD::MEMMOVE:     Res = HandleMemIntrinsic(N); break;
 782     }
 783   }
 784
 785   // If the result is null, the sub-method took care of registering results etc.
 786   if (!Res.Val) return false;
 787   // If the result is N, the sub-method updated N in place.  Check to see if any
 788   // operands are new, and if so, mark them.
 789   if (Res.Val == N) {
 790     // Mark N as new and remark N and its operands.  This allows us to correctly
 791     // revisit N if it needs another step of promotion and allows us to visit
 792     // any new operands to N.
 793     N->setNodeId(NewNode);
 794     MarkNewNodes(N);
 795     return true;
 796   }
 797
 798   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
 799          "Invalid operand expansion");
 800
 801   ReplaceValueWith(SDOperand(N, 0), Res);
 802   return false;
 803 }
 804
 805 SDOperand DAGTypeLegalizer::ExpandOperand_TRUNCATE(SDNode *N) {
 806   SDOperand InL, InH;
 807   GetExpandedOp(N->getOperand(0), InL, InH);
 808   // Just truncate the low part of the source.
 809   return DAG.getNode(ISD::TRUNCATE, N->getValueType(0), InL);
 810 }
 811
 812 SDOperand DAGTypeLegalizer::ExpandOperand_BIT_CONVERT(SDNode *N) {
 813   return CreateStackStoreLoad(N->getOperand(0), N->getValueType(0));
 814 }
 815
 816 SDOperand DAGTypeLegalizer::ExpandOperand_SINT_TO_FP(SDOperand Source,
 817                                                      MVT::ValueType DestTy) {
 818   // We know the destination is legal, but that the input needs to be expanded.
 819   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
 820
 821   // Check to see if the target has a custom way to lower this.  If so, use it.
 822   switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) {
 823   default: assert(0 && "This action not implemented for this operation!");
 824   case TargetLowering::Legal:
 825   case TargetLowering::Expand:
 826     break;   // This case is handled below.
 827   case TargetLowering::Custom:
 828     SDOperand NV = TLI.LowerOperation(DAG.getNode(ISD::SINT_TO_FP, DestTy,
 829                                                   Source), DAG);
 830     if (NV.Val) return NV;
 831     break;   // The target lowered this.
 832   }
 833
 834   RTLIB::Libcall LC;
 835   if (DestTy == MVT::f32)
 836     LC = RTLIB::SINTTOFP_I64_F32;
 837   else {
 838     assert(DestTy == MVT::f64 && "Unknown fp value type!");
 839     LC = RTLIB::SINTTOFP_I64_F64;
 840   }
 841
 842   assert(0 && "FIXME: no libcalls yet!");
 843   abort();
 844 #if 0
 845   assert(TLI.getLibcallName(LC) && "Don't know how to expand this SINT_TO_FP!");
 846   Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source);
 847   SDOperand UnusedHiPart;
 848   return ExpandLibCall(TLI.getLibcallName(LC), Source.Val, true, UnusedHiPart);
 849 #endif
 850 }
 851
 852 SDOperand DAGTypeLegalizer::ExpandOperand_UINT_TO_FP(SDOperand Source,
 853                                                      MVT::ValueType DestTy) {
 854   // We know the destination is legal, but that the input needs to be expanded.
 855   assert(getTypeAction(Source.getValueType()) == Expand &&
 856          "This is not an expansion!");
 857   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
 858
 859   // If this is unsigned, and not supported, first perform the conversion to
 860   // signed, then adjust the result if the sign bit is set.
 861   SDOperand SignedConv = ExpandOperand_SINT_TO_FP(Source, DestTy);
 862
 863   // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
 864   // incoming integer is set.  To handle this, we dynamically test to see if
 865   // it is set, and, if so, add a fudge factor.
 866   SDOperand Lo, Hi;
 867   GetExpandedOp(Source, Lo, Hi);
 868
 869   SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi,
 870                                    DAG.getConstant(0, Hi.getValueType()),
 871                                    ISD::SETLT);
 872   SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
 873   SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
 874                                     SignSet, Four, Zero);
 875   uint64_t FF = 0x5f800000ULL;
 876   if (TLI.isLittleEndian()) FF <<= 32;
 877   Constant *FudgeFactor = ConstantInt::get((Type*)Type::Int64Ty, FF);
 878
 879   SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
 880   CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
 881   SDOperand FudgeInReg;
 882   if (DestTy == MVT::f32)
 883     FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, NULL, 0);
 884   else if (MVT::getSizeInBits(DestTy) > MVT::getSizeInBits(MVT::f32))
 885     // FIXME: Avoid the extend by construction the right constantpool?
 886     FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, DestTy, DAG.getEntryNode(),
 887                                 CPIdx, NULL, 0, MVT::f32);
 888   else
 889     assert(0 && "Unexpected conversion");
 890
 891   return DAG.getNode(ISD::FADD, DestTy, SignedConv, FudgeInReg);
 892 }
 893
 894 SDOperand DAGTypeLegalizer::ExpandOperand_EXTRACT_ELEMENT(SDNode *N) {
 895   SDOperand Lo, Hi;
 896   GetExpandedOp(N->getOperand(0), Lo, Hi);
 897   return cast<ConstantSDNode>(N->getOperand(1))->getValue() ? Hi : Lo;
 898 }
 899
 900 SDOperand DAGTypeLegalizer::ExpandOperand_SETCC(SDNode *N) {
 901   SDOperand NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
 902   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(2))->get();
 903   ExpandSetCCOperands(NewLHS, NewRHS, CCCode);
 904
 905   // If ExpandSetCCOperands returned a scalar, use it.
 906   if (NewRHS.Val == 0) return NewLHS;
 907
 908   // Otherwise, update N to have the operands specified.
 909   return DAG.UpdateNodeOperands(SDOperand(N, 0), NewLHS, NewRHS,
 910                                 DAG.getCondCode(CCCode));
 911 }
 912
 913 /// ExpandSetCCOperands - Expand the operands of a comparison.  This code is
 914 /// shared among BR_CC, SELECT_CC, and SETCC handlers.
 915 void DAGTypeLegalizer::ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS,
 916                                            ISD::CondCode &CCCode) {
 917   SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
 918   GetExpandedOp(NewLHS, LHSLo, LHSHi);
 919   GetExpandedOp(NewRHS, RHSLo, RHSHi);
 920
 921   MVT::ValueType VT = NewLHS.getValueType();
 922   if (VT == MVT::f32 || VT == MVT::f64) {
 923     assert(0 && "FIXME: softfp not implemented yet! should be promote not exp");
 924   }
 925
 926   if (VT == MVT::ppcf128) {
 927     // FIXME:  This generated code sucks.  We want to generate
 928     //         FCMP crN, hi1, hi2
 929     //         BNE crN, L:
 930     //         FCMP crN, lo1, lo2
 931     // The following can be improved, but not that much.
 932     SDOperand Tmp1, Tmp2, Tmp3;
 933     Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ);
 934     Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, CCCode);
 935     Tmp3 = DAG.getNode(ISD::AND, Tmp1.getValueType(), Tmp1, Tmp2);
 936     Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETNE);
 937     Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, CCCode);
 938     Tmp1 = DAG.getNode(ISD::AND, Tmp1.getValueType(), Tmp1, Tmp2);
 939     NewLHS = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp3);
 940     NewRHS = SDOperand();   // LHS is the result, not a compare.
 941     return;
 942   }
 943
 944
 945   if (CCCode == ISD::SETEQ || CCCode == ISD::SETNE) {
 946     if (RHSLo == RHSHi)
 947       if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
 948         if (RHSCST->isAllOnesValue()) {
 949           // Equality comparison to -1.
 950           NewLHS = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
 951           NewRHS = RHSLo;
 952           return;
 953         }
 954
 955     NewLHS = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
 956     NewRHS = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
 957     NewLHS = DAG.getNode(ISD::OR, NewLHS.getValueType(), NewLHS, NewRHS);
 958     NewRHS = DAG.getConstant(0, NewLHS.getValueType());
 959     return;
 960   }
 961
 962   // If this is a comparison of the sign bit, just look at the top part.
 963   // X > -1,  x < 0
 964   if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(NewRHS))
 965     if ((CCCode == ISD::SETLT && CST->getValue() == 0) ||   // X < 0
 966         (CCCode == ISD::SETGT && CST->isAllOnesValue())) {  // X > -1
 967       NewLHS = LHSHi;
 968       NewRHS = RHSHi;
 969       return;
 970     }
 971
 972   // FIXME: This generated code sucks.
 973   ISD::CondCode LowCC;
 974   switch (CCCode) {
 975   default: assert(0 && "Unknown integer setcc!");
 976   case ISD::SETLT:
 977   case ISD::SETULT: LowCC = ISD::SETULT; break;
 978   case ISD::SETGT:
 979   case ISD::SETUGT: LowCC = ISD::SETUGT; break;
 980   case ISD::SETLE:
 981   case ISD::SETULE: LowCC = ISD::SETULE; break;
 982   case ISD::SETGE:
 983   case ISD::SETUGE: LowCC = ISD::SETUGE; break;
 984   }
 985
 986   // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
 987   // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
 988   // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
 989
 990   // NOTE: on targets without efficient SELECT of bools, we can always use
 991   // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
 992   TargetLowering::DAGCombinerInfo DagCombineInfo(DAG, false, true, NULL);
 993   SDOperand Tmp1, Tmp2;
 994   Tmp1 = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC,
 995                            false, DagCombineInfo);
 996   if (!Tmp1.Val)
 997     Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC);
 998   Tmp2 = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi,
 999                            CCCode, false, DagCombineInfo);
1000   if (!Tmp2.Val)
1001     Tmp2 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), LHSHi, RHSHi,
1002                        DAG.getCondCode(CCCode));
1003
1004   ConstantSDNode *Tmp1C = dyn_cast<ConstantSDNode>(Tmp1.Val);
1005   ConstantSDNode *Tmp2C = dyn_cast<ConstantSDNode>(Tmp2.Val);
1006   if ((Tmp1C && Tmp1C->getValue() == 0) ||
1007       (Tmp2C && Tmp2C->getValue() == 0 &&
1008        (CCCode == ISD::SETLE || CCCode == ISD::SETGE ||
1009         CCCode == ISD::SETUGE || CCCode == ISD::SETULE)) ||
1010       (Tmp2C && Tmp2C->getValue() == 1 &&
1011        (CCCode == ISD::SETLT || CCCode == ISD::SETGT ||
1012         CCCode == ISD::SETUGT || CCCode == ISD::SETULT))) {
1013     // low part is known false, returns high part.
1014     // For LE / GE, if high part is known false, ignore the low part.
1015     // For LT / GT, if high part is known true, ignore the low part.
1016     NewLHS = Tmp2;
1017     NewRHS = SDOperand();
1018     return;
1019   }
1020
1021   NewLHS = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi,
1022                              ISD::SETEQ, false, DagCombineInfo);
1023   if (!NewLHS.Val)
1024     NewLHS = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ);
1025   NewLHS = DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
1026                        NewLHS, Tmp1, Tmp2);
1027   NewRHS = SDOperand();
1028 }
1029
1030 SDOperand DAGTypeLegalizer::ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo) {
1031   assert(OpNo == 1 && "Can only expand the stored value so far");
1032
1033   MVT::ValueType VT = N->getOperand(1).getValueType();
1034   MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1035   SDOperand Ch  = N->getChain();
1036   SDOperand Ptr = N->getBasePtr();
1037   int SVOffset = N->getSrcValueOffset();
1038   unsigned Alignment = N->getAlignment();
1039   bool isVolatile = N->isVolatile();
1040   SDOperand Lo, Hi;
1041
1042   assert(!(MVT::getSizeInBits(NVT) & 7) && "Expanded type not byte sized!");
1043
1044   if (!N->isTruncatingStore()) {
1045     unsigned IncrementSize = 0;
1046
1047     // If this is a vector type, then we have to calculate the increment as
1048     // the product of the element size in bytes, and the number of elements
1049     // in the high half of the vector.
1050     if (MVT::isVector(N->getValue().getValueType())) {
1051       assert(0 && "Vectors not supported yet");
1052   #if 0
1053       SDNode *InVal = ST->getValue().Val;
1054       unsigned NumElems = MVT::getVectorNumElements(InVal->getValueType(0));
1055       MVT::ValueType EVT = MVT::getVectorElementType(InVal->getValueType(0));
1056
1057       // Figure out if there is a simple type corresponding to this Vector
1058       // type.  If so, convert to the vector type.
1059       MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
1060       if (TLI.isTypeLegal(TVT)) {
1061         // Turn this into a normal store of the vector type.
1062         Tmp3 = LegalizeOp(Node->getOperand(1));
1063         Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1064                               SVOffset, isVolatile, Alignment);
1065         Result = LegalizeOp(Result);
1066         break;
1067       } else if (NumElems == 1) {
1068         // Turn this into a normal store of the scalar type.
1069         Tmp3 = ScalarizeVectorOp(Node->getOperand(1));
1070         Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1071                               SVOffset, isVolatile, Alignment);
1072         // The scalarized value type may not be legal, e.g. it might require
1073         // promotion or expansion.  Relegalize the scalar store.
1074         return LegalizeOp(Result);
1075       } else {
1076         SplitVectorOp(Node->getOperand(1), Lo, Hi);
1077         IncrementSize = NumElems/2 * MVT::getSizeInBits(EVT)/8;
1078       }
1079   #endif
1080     } else {
1081       GetExpandedOp(N->getValue(), Lo, Hi);
1082       IncrementSize = Hi.Val ? MVT::getSizeInBits(Hi.getValueType())/8 : 0;
1083
1084       if (!TLI.isLittleEndian())
1085         std::swap(Lo, Hi);
1086     }
1087
1088     Lo = DAG.getStore(Ch, Lo, Ptr, N->getSrcValue(),
1089                       SVOffset, isVolatile, Alignment);
1090
1091     assert(Hi.Val && "FIXME: int <-> float should be handled with promote!");
1092   #if 0
1093     if (Hi.Val == NULL) {
1094       // Must be int <-> float one-to-one expansion.
1095       return Lo;
1096     }
1097   #endif
1098
1099     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1100                       getIntPtrConstant(IncrementSize));
1101     assert(isTypeLegal(Ptr.getValueType()) && "Pointers must be legal!");
1102     Hi = DAG.getStore(Ch, Hi, Ptr, N->getSrcValue(), SVOffset+IncrementSize,
1103                       isVolatile, MinAlign(Alignment, IncrementSize));
1104     return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1105   } else if (MVT::getSizeInBits(N->getStoredVT()) <= MVT::getSizeInBits(NVT)) {
1106     GetExpandedOp(N->getValue(), Lo, Hi);
1107     return DAG.getTruncStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset,
1108                              N->getStoredVT(), isVolatile, Alignment);
1109   } else if (TLI.isLittleEndian()) {
1110     // Little-endian - low bits are at low addresses.
1111     GetExpandedOp(N->getValue(), Lo, Hi);
1112
1113     Lo = DAG.getStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset,
1114                       isVolatile, Alignment);
1115
1116     unsigned ExcessBits =
1117       MVT::getSizeInBits(N->getStoredVT()) - MVT::getSizeInBits(NVT);
1118     MVT::ValueType NEVT = MVT::getIntegerType(ExcessBits);
1119
1120     // Increment the pointer to the other half.
1121     unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
1122     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1123                       getIntPtrConstant(IncrementSize));
1124     Hi = DAG.getTruncStore(Ch, Hi, Ptr, N->getSrcValue(),
1125                            SVOffset+IncrementSize, NEVT,
1126                            isVolatile, MinAlign(Alignment, IncrementSize));
1127     return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1128   } else {
1129     // Big-endian - high bits are at low addresses.  Favor aligned stores at
1130     // the cost of some bit-fiddling.
1131     GetExpandedOp(N->getValue(), Lo, Hi);
1132
1133     MVT::ValueType EVT = N->getStoredVT();
1134     unsigned EBytes = MVT::getStoreSizeInBits(EVT)/8;
1135     unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
1136     unsigned ExcessBits = (EBytes - IncrementSize)*8;
1137     MVT::ValueType HiVT =
1138       MVT::getIntegerType(MVT::getSizeInBits(EVT)-ExcessBits);
1139
1140     if (ExcessBits < MVT::getSizeInBits(NVT)) {
1141       // Transfer high bits from the top of Lo to the bottom of Hi.
1142       Hi = DAG.getNode(ISD::SHL, NVT, Hi,
1143                        DAG.getConstant(MVT::getSizeInBits(NVT) - ExcessBits,
1144                                        TLI.getShiftAmountTy()));
1145       Hi = DAG.getNode(ISD::OR, NVT, Hi,
1146                        DAG.getNode(ISD::SRL, NVT, Lo,
1147                                    DAG.getConstant(ExcessBits,
1148                                                    TLI.getShiftAmountTy())));
1149     }
1150
1151     // Store both the high bits and maybe some of the low bits.
1152     Hi = DAG.getTruncStore(Ch, Hi, Ptr, N->getSrcValue(),
1153                            SVOffset, HiVT, isVolatile, Alignment);
1154
1155     // Increment the pointer to the other half.
1156     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1157                       getIntPtrConstant(IncrementSize));
1158     // Store the lowest ExcessBits bits in the second half.
1159     Lo = DAG.getTruncStore(Ch, Lo, Ptr, N->getSrcValue(),
1160                            SVOffset+IncrementSize,
1161                            MVT::getIntegerType(ExcessBits),
1162                            isVolatile, MinAlign(Alignment, IncrementSize));
1163     return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1164   }
1165 }
1166