LLVM API Documentation

TargetLowering.cpp

Go to the documentation of this file.
00001 //===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This implements the TargetLowering class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Target/TargetLowering.h"
00015 #include "llvm/Target/TargetAsmInfo.h"
00016 #include "llvm/Target/TargetData.h"
00017 #include "llvm/Target/TargetLoweringObjectFile.h"
00018 #include "llvm/Target/TargetMachine.h"
00019 #include "llvm/Target/TargetRegisterInfo.h"
00020 #include "llvm/Target/TargetSubtarget.h"
00021 #include "llvm/GlobalVariable.h"
00022 #include "llvm/DerivedTypes.h"
00023 #include "llvm/CodeGen/MachineFrameInfo.h"
00024 #include "llvm/CodeGen/SelectionDAG.h"
00025 #include "llvm/ADT/StringExtras.h"
00026 #include "llvm/ADT/STLExtras.h"
00027 #include "llvm/Support/ErrorHandling.h"
00028 #include "llvm/Support/MathExtras.h"
00029 using namespace llvm;
00030 
00031 namespace llvm {
00032 TLSModel::Model getTLSModel(const GlobalValue *GV, Reloc::Model reloc) {
00033   bool isLocal = GV->hasLocalLinkage();
00034   bool isDeclaration = GV->isDeclaration();
00035   // FIXME: what should we do for protected and internal visibility?
00036   // For variables, is internal different from hidden?
00037   bool isHidden = GV->hasHiddenVisibility();
00038 
00039   if (reloc == Reloc::PIC_) {
00040     if (isLocal || isHidden)
00041       return TLSModel::LocalDynamic;
00042     else
00043       return TLSModel::GeneralDynamic;
00044   } else {
00045     if (!isDeclaration || isHidden)
00046       return TLSModel::LocalExec;
00047     else
00048       return TLSModel::InitialExec;
00049   }
00050 }
00051 }
00052 
00053 /// InitLibcallNames - Set default libcall names.
00054 ///
00055 static void InitLibcallNames(const char **Names) {
00056   Names[RTLIB::SHL_I16] = "__ashlhi3";
00057   Names[RTLIB::SHL_I32] = "__ashlsi3";
00058   Names[RTLIB::SHL_I64] = "__ashldi3";
00059   Names[RTLIB::SHL_I128] = "__ashlti3";
00060   Names[RTLIB::SRL_I16] = "__lshrhi3";
00061   Names[RTLIB::SRL_I32] = "__lshrsi3";
00062   Names[RTLIB::SRL_I64] = "__lshrdi3";
00063   Names[RTLIB::SRL_I128] = "__lshrti3";
00064   Names[RTLIB::SRA_I16] = "__ashrhi3";
00065   Names[RTLIB::SRA_I32] = "__ashrsi3";
00066   Names[RTLIB::SRA_I64] = "__ashrdi3";
00067   Names[RTLIB::SRA_I128] = "__ashrti3";
00068   Names[RTLIB::MUL_I16] = "__mulhi3";
00069   Names[RTLIB::MUL_I32] = "__mulsi3";
00070   Names[RTLIB::MUL_I64] = "__muldi3";
00071   Names[RTLIB::MUL_I128] = "__multi3";
00072   Names[RTLIB::SDIV_I16] = "__divhi3";
00073   Names[RTLIB::SDIV_I32] = "__divsi3";
00074   Names[RTLIB::SDIV_I64] = "__divdi3";
00075   Names[RTLIB::SDIV_I128] = "__divti3";
00076   Names[RTLIB::UDIV_I16] = "__udivhi3";
00077   Names[RTLIB::UDIV_I32] = "__udivsi3";
00078   Names[RTLIB::UDIV_I64] = "__udivdi3";
00079   Names[RTLIB::UDIV_I128] = "__udivti3";
00080   Names[RTLIB::SREM_I16] = "__modhi3";
00081   Names[RTLIB::SREM_I32] = "__modsi3";
00082   Names[RTLIB::SREM_I64] = "__moddi3";
00083   Names[RTLIB::SREM_I128] = "__modti3";
00084   Names[RTLIB::UREM_I16] = "__umodhi3";
00085   Names[RTLIB::UREM_I32] = "__umodsi3";
00086   Names[RTLIB::UREM_I64] = "__umoddi3";
00087   Names[RTLIB::UREM_I128] = "__umodti3";
00088   Names[RTLIB::NEG_I32] = "__negsi2";
00089   Names[RTLIB::NEG_I64] = "__negdi2";
00090   Names[RTLIB::ADD_F32] = "__addsf3";
00091   Names[RTLIB::ADD_F64] = "__adddf3";
00092   Names[RTLIB::ADD_F80] = "__addxf3";
00093   Names[RTLIB::ADD_PPCF128] = "__gcc_qadd";
00094   Names[RTLIB::SUB_F32] = "__subsf3";
00095   Names[RTLIB::SUB_F64] = "__subdf3";
00096   Names[RTLIB::SUB_F80] = "__subxf3";
00097   Names[RTLIB::SUB_PPCF128] = "__gcc_qsub";
00098   Names[RTLIB::MUL_F32] = "__mulsf3";
00099   Names[RTLIB::MUL_F64] = "__muldf3";
00100   Names[RTLIB::MUL_F80] = "__mulxf3";
00101   Names[RTLIB::MUL_PPCF128] = "__gcc_qmul";
00102   Names[RTLIB::DIV_F32] = "__divsf3";
00103   Names[RTLIB::DIV_F64] = "__divdf3";
00104   Names[RTLIB::DIV_F80] = "__divxf3";
00105   Names[RTLIB::DIV_PPCF128] = "__gcc_qdiv";
00106   Names[RTLIB::REM_F32] = "fmodf";
00107   Names[RTLIB::REM_F64] = "fmod";
00108   Names[RTLIB::REM_F80] = "fmodl";
00109   Names[RTLIB::REM_PPCF128] = "fmodl";
00110   Names[RTLIB::POWI_F32] = "__powisf2";
00111   Names[RTLIB::POWI_F64] = "__powidf2";
00112   Names[RTLIB::POWI_F80] = "__powixf2";
00113   Names[RTLIB::POWI_PPCF128] = "__powitf2";
00114   Names[RTLIB::SQRT_F32] = "sqrtf";
00115   Names[RTLIB::SQRT_F64] = "sqrt";
00116   Names[RTLIB::SQRT_F80] = "sqrtl";
00117   Names[RTLIB::SQRT_PPCF128] = "sqrtl";
00118   Names[RTLIB::LOG_F32] = "logf";
00119   Names[RTLIB::LOG_F64] = "log";
00120   Names[RTLIB::LOG_F80] = "logl";
00121   Names[RTLIB::LOG_PPCF128] = "logl";
00122   Names[RTLIB::LOG2_F32] = "log2f";
00123   Names[RTLIB::LOG2_F64] = "log2";
00124   Names[RTLIB::LOG2_F80] = "log2l";
00125   Names[RTLIB::LOG2_PPCF128] = "log2l";
00126   Names[RTLIB::LOG10_F32] = "log10f";
00127   Names[RTLIB::LOG10_F64] = "log10";
00128   Names[RTLIB::LOG10_F80] = "log10l";
00129   Names[RTLIB::LOG10_PPCF128] = "log10l";
00130   Names[RTLIB::EXP_F32] = "expf";
00131   Names[RTLIB::EXP_F64] = "exp";
00132   Names[RTLIB::EXP_F80] = "expl";
00133   Names[RTLIB::EXP_PPCF128] = "expl";
00134   Names[RTLIB::EXP2_F32] = "exp2f";
00135   Names[RTLIB::EXP2_F64] = "exp2";
00136   Names[RTLIB::EXP2_F80] = "exp2l";
00137   Names[RTLIB::EXP2_PPCF128] = "exp2l";
00138   Names[RTLIB::SIN_F32] = "sinf";
00139   Names[RTLIB::SIN_F64] = "sin";
00140   Names[RTLIB::SIN_F80] = "sinl";
00141   Names[RTLIB::SIN_PPCF128] = "sinl";
00142   Names[RTLIB::COS_F32] = "cosf";
00143   Names[RTLIB::COS_F64] = "cos";
00144   Names[RTLIB::COS_F80] = "cosl";
00145   Names[RTLIB::COS_PPCF128] = "cosl";
00146   Names[RTLIB::POW_F32] = "powf";
00147   Names[RTLIB::POW_F64] = "pow";
00148   Names[RTLIB::POW_F80] = "powl";
00149   Names[RTLIB::POW_PPCF128] = "powl";
00150   Names[RTLIB::CEIL_F32] = "ceilf";
00151   Names[RTLIB::CEIL_F64] = "ceil";
00152   Names[RTLIB::CEIL_F80] = "ceill";
00153   Names[RTLIB::CEIL_PPCF128] = "ceill";
00154   Names[RTLIB::TRUNC_F32] = "truncf";
00155   Names[RTLIB::TRUNC_F64] = "trunc";
00156   Names[RTLIB::TRUNC_F80] = "truncl";
00157   Names[RTLIB::TRUNC_PPCF128] = "truncl";
00158   Names[RTLIB::RINT_F32] = "rintf";
00159   Names[RTLIB::RINT_F64] = "rint";
00160   Names[RTLIB::RINT_F80] = "rintl";
00161   Names[RTLIB::RINT_PPCF128] = "rintl";
00162   Names[RTLIB::NEARBYINT_F32] = "nearbyintf";
00163   Names[RTLIB::NEARBYINT_F64] = "nearbyint";
00164   Names[RTLIB::NEARBYINT_F80] = "nearbyintl";
00165   Names[RTLIB::NEARBYINT_PPCF128] = "nearbyintl";
00166   Names[RTLIB::FLOOR_F32] = "floorf";
00167   Names[RTLIB::FLOOR_F64] = "floor";
00168   Names[RTLIB::FLOOR_F80] = "floorl";
00169   Names[RTLIB::FLOOR_PPCF128] = "floorl";
00170   Names[RTLIB::FPEXT_F32_F64] = "__extendsfdf2";
00171   Names[RTLIB::FPROUND_F64_F32] = "__truncdfsf2";
00172   Names[RTLIB::FPROUND_F80_F32] = "__truncxfsf2";
00173   Names[RTLIB::FPROUND_PPCF128_F32] = "__trunctfsf2";
00174   Names[RTLIB::FPROUND_F80_F64] = "__truncxfdf2";
00175   Names[RTLIB::FPROUND_PPCF128_F64] = "__trunctfdf2";
00176   Names[RTLIB::FPTOSINT_F32_I8] = "__fixsfi8";
00177   Names[RTLIB::FPTOSINT_F32_I16] = "__fixsfi16";
00178   Names[RTLIB::FPTOSINT_F32_I32] = "__fixsfsi";
00179   Names[RTLIB::FPTOSINT_F32_I64] = "__fixsfdi";
00180   Names[RTLIB::FPTOSINT_F32_I128] = "__fixsfti";
00181   Names[RTLIB::FPTOSINT_F64_I32] = "__fixdfsi";
00182   Names[RTLIB::FPTOSINT_F64_I64] = "__fixdfdi";
00183   Names[RTLIB::FPTOSINT_F64_I128] = "__fixdfti";
00184   Names[RTLIB::FPTOSINT_F80_I32] = "__fixxfsi";
00185   Names[RTLIB::FPTOSINT_F80_I64] = "__fixxfdi";
00186   Names[RTLIB::FPTOSINT_F80_I128] = "__fixxfti";
00187   Names[RTLIB::FPTOSINT_PPCF128_I32] = "__fixtfsi";
00188   Names[RTLIB::FPTOSINT_PPCF128_I64] = "__fixtfdi";
00189   Names[RTLIB::FPTOSINT_PPCF128_I128] = "__fixtfti";
00190   Names[RTLIB::FPTOUINT_F32_I8] = "__fixunssfi8";
00191   Names[RTLIB::FPTOUINT_F32_I16] = "__fixunssfi16";
00192   Names[RTLIB::FPTOUINT_F32_I32] = "__fixunssfsi";
00193   Names[RTLIB::FPTOUINT_F32_I64] = "__fixunssfdi";
00194   Names[RTLIB::FPTOUINT_F32_I128] = "__fixunssfti";
00195   Names[RTLIB::FPTOUINT_F64_I32] = "__fixunsdfsi";
00196   Names[RTLIB::FPTOUINT_F64_I64] = "__fixunsdfdi";
00197   Names[RTLIB::FPTOUINT_F64_I128] = "__fixunsdfti";
00198   Names[RTLIB::FPTOUINT_F80_I32] = "__fixunsxfsi";
00199   Names[RTLIB::FPTOUINT_F80_I64] = "__fixunsxfdi";
00200   Names[RTLIB::FPTOUINT_F80_I128] = "__fixunsxfti";
00201   Names[RTLIB::FPTOUINT_PPCF128_I32] = "__fixunstfsi";
00202   Names[RTLIB::FPTOUINT_PPCF128_I64] = "__fixunstfdi";
00203   Names[RTLIB::FPTOUINT_PPCF128_I128] = "__fixunstfti";
00204   Names[RTLIB::SINTTOFP_I32_F32] = "__floatsisf";
00205   Names[RTLIB::SINTTOFP_I32_F64] = "__floatsidf";
00206   Names[RTLIB::SINTTOFP_I32_F80] = "__floatsixf";
00207   Names[RTLIB::SINTTOFP_I32_PPCF128] = "__floatsitf";
00208   Names[RTLIB::SINTTOFP_I64_F32] = "__floatdisf";
00209   Names[RTLIB::SINTTOFP_I64_F64] = "__floatdidf";
00210   Names[RTLIB::SINTTOFP_I64_F80] = "__floatdixf";
00211   Names[RTLIB::SINTTOFP_I64_PPCF128] = "__floatditf";
00212   Names[RTLIB::SINTTOFP_I128_F32] = "__floattisf";
00213   Names[RTLIB::SINTTOFP_I128_F64] = "__floattidf";
00214   Names[RTLIB::SINTTOFP_I128_F80] = "__floattixf";
00215   Names[RTLIB::SINTTOFP_I128_PPCF128] = "__floattitf";
00216   Names[RTLIB::UINTTOFP_I32_F32] = "__floatunsisf";
00217   Names[RTLIB::UINTTOFP_I32_F64] = "__floatunsidf";
00218   Names[RTLIB::UINTTOFP_I32_F80] = "__floatunsixf";
00219   Names[RTLIB::UINTTOFP_I32_PPCF128] = "__floatunsitf";
00220   Names[RTLIB::UINTTOFP_I64_F32] = "__floatundisf";
00221   Names[RTLIB::UINTTOFP_I64_F64] = "__floatundidf";
00222   Names[RTLIB::UINTTOFP_I64_F80] = "__floatundixf";
00223   Names[RTLIB::UINTTOFP_I64_PPCF128] = "__floatunditf";
00224   Names[RTLIB::UINTTOFP_I128_F32] = "__floatuntisf";
00225   Names[RTLIB::UINTTOFP_I128_F64] = "__floatuntidf";
00226   Names[RTLIB::UINTTOFP_I128_F80] = "__floatuntixf";
00227   Names[RTLIB::UINTTOFP_I128_PPCF128] = "__floatuntitf";
00228   Names[RTLIB::OEQ_F32] = "__eqsf2";
00229   Names[RTLIB::OEQ_F64] = "__eqdf2";
00230   Names[RTLIB::UNE_F32] = "__nesf2";
00231   Names[RTLIB::UNE_F64] = "__nedf2";
00232   Names[RTLIB::OGE_F32] = "__gesf2";
00233   Names[RTLIB::OGE_F64] = "__gedf2";
00234   Names[RTLIB::OLT_F32] = "__ltsf2";
00235   Names[RTLIB::OLT_F64] = "__ltdf2";
00236   Names[RTLIB::OLE_F32] = "__lesf2";
00237   Names[RTLIB::OLE_F64] = "__ledf2";
00238   Names[RTLIB::OGT_F32] = "__gtsf2";
00239   Names[RTLIB::OGT_F64] = "__gtdf2";
00240   Names[RTLIB::UO_F32] = "__unordsf2";
00241   Names[RTLIB::UO_F64] = "__unorddf2";
00242   Names[RTLIB::O_F32] = "__unordsf2";
00243   Names[RTLIB::O_F64] = "__unorddf2";
00244   Names[RTLIB::MEMCPY] = "memcpy";
00245   Names[RTLIB::MEMMOVE] = "memmove";
00246   Names[RTLIB::MEMSET] = "memset";
00247   Names[RTLIB::UNWIND_RESUME] = "_Unwind_Resume";
00248 }
00249 
00250 /// InitLibcallCallingConvs - Set default libcall CallingConvs.
00251 ///
00252 static void InitLibcallCallingConvs(CallingConv::ID *CCs) {
00253   for (int i = 0; i < RTLIB::UNKNOWN_LIBCALL; ++i) {
00254     CCs[i] = CallingConv::C;
00255   }
00256 }
00257 
00258 /// getFPEXT - Return the FPEXT_*_* value for the given types, or
00259 /// UNKNOWN_LIBCALL if there is none.
00260 RTLIB::Libcall RTLIB::getFPEXT(EVT OpVT, EVT RetVT) {
00261   if (OpVT == MVT::f32) {
00262     if (RetVT == MVT::f64)
00263       return FPEXT_F32_F64;
00264   }
00265   return UNKNOWN_LIBCALL;
00266 }
00267 
00268 /// getFPROUND - Return the FPROUND_*_* value for the given types, or
00269 /// UNKNOWN_LIBCALL if there is none.
00270 RTLIB::Libcall RTLIB::getFPROUND(EVT OpVT, EVT RetVT) {
00271   if (RetVT == MVT::f32) {
00272     if (OpVT == MVT::f64)
00273       return FPROUND_F64_F32;
00274     if (OpVT == MVT::f80)
00275       return FPROUND_F80_F32;
00276     if (OpVT == MVT::ppcf128)
00277       return FPROUND_PPCF128_F32;
00278   } else if (RetVT == MVT::f64) {
00279     if (OpVT == MVT::f80)
00280       return FPROUND_F80_F64;
00281     if (OpVT == MVT::ppcf128)
00282       return FPROUND_PPCF128_F64;
00283   }
00284   return UNKNOWN_LIBCALL;
00285 }
00286 
00287 /// getFPTOSINT - Return the FPTOSINT_*_* value for the given types, or
00288 /// UNKNOWN_LIBCALL if there is none.
00289 RTLIB::Libcall RTLIB::getFPTOSINT(EVT OpVT, EVT RetVT) {
00290   if (OpVT == MVT::f32) {
00291     if (RetVT == MVT::i8)
00292       return FPTOSINT_F32_I8;
00293     if (RetVT == MVT::i16)
00294       return FPTOSINT_F32_I16;
00295     if (RetVT == MVT::i32)
00296       return FPTOSINT_F32_I32;
00297     if (RetVT == MVT::i64)
00298       return FPTOSINT_F32_I64;
00299     if (RetVT == MVT::i128)
00300       return FPTOSINT_F32_I128;
00301   } else if (OpVT == MVT::f64) {
00302     if (RetVT == MVT::i32)
00303       return FPTOSINT_F64_I32;
00304     if (RetVT == MVT::i64)
00305       return FPTOSINT_F64_I64;
00306     if (RetVT == MVT::i128)
00307       return FPTOSINT_F64_I128;
00308   } else if (OpVT == MVT::f80) {
00309     if (RetVT == MVT::i32)
00310       return FPTOSINT_F80_I32;
00311     if (RetVT == MVT::i64)
00312       return FPTOSINT_F80_I64;
00313     if (RetVT == MVT::i128)
00314       return FPTOSINT_F80_I128;
00315   } else if (OpVT == MVT::ppcf128) {
00316     if (RetVT == MVT::i32)
00317       return FPTOSINT_PPCF128_I32;
00318     if (RetVT == MVT::i64)
00319       return FPTOSINT_PPCF128_I64;
00320     if (RetVT == MVT::i128)
00321       return FPTOSINT_PPCF128_I128;
00322   }
00323   return UNKNOWN_LIBCALL;
00324 }
00325 
00326 /// getFPTOUINT - Return the FPTOUINT_*_* value for the given types, or
00327 /// UNKNOWN_LIBCALL if there is none.
00328 RTLIB::Libcall RTLIB::getFPTOUINT(EVT OpVT, EVT RetVT) {
00329   if (OpVT == MVT::f32) {
00330     if (RetVT == MVT::i8)
00331       return FPTOUINT_F32_I8;
00332     if (RetVT == MVT::i16)
00333       return FPTOUINT_F32_I16;
00334     if (RetVT == MVT::i32)
00335       return FPTOUINT_F32_I32;
00336     if (RetVT == MVT::i64)
00337       return FPTOUINT_F32_I64;
00338     if (RetVT == MVT::i128)
00339       return FPTOUINT_F32_I128;
00340   } else if (OpVT == MVT::f64) {
00341     if (RetVT == MVT::i32)
00342       return FPTOUINT_F64_I32;
00343     if (RetVT == MVT::i64)
00344       return FPTOUINT_F64_I64;
00345     if (RetVT == MVT::i128)
00346       return FPTOUINT_F64_I128;
00347   } else if (OpVT == MVT::f80) {
00348     if (RetVT == MVT::i32)
00349       return FPTOUINT_F80_I32;
00350     if (RetVT == MVT::i64)
00351       return FPTOUINT_F80_I64;
00352     if (RetVT == MVT::i128)
00353       return FPTOUINT_F80_I128;
00354   } else if (OpVT == MVT::ppcf128) {
00355     if (RetVT == MVT::i32)
00356       return FPTOUINT_PPCF128_I32;
00357     if (RetVT == MVT::i64)
00358       return FPTOUINT_PPCF128_I64;
00359     if (RetVT == MVT::i128)
00360       return FPTOUINT_PPCF128_I128;
00361   }
00362   return UNKNOWN_LIBCALL;
00363 }
00364 
00365 /// getSINTTOFP - Return the SINTTOFP_*_* value for the given types, or
00366 /// UNKNOWN_LIBCALL if there is none.
00367 RTLIB::Libcall RTLIB::getSINTTOFP(EVT OpVT, EVT RetVT) {
00368   if (OpVT == MVT::i32) {
00369     if (RetVT == MVT::f32)
00370       return SINTTOFP_I32_F32;
00371     else if (RetVT == MVT::f64)
00372       return SINTTOFP_I32_F64;
00373     else if (RetVT == MVT::f80)
00374       return SINTTOFP_I32_F80;
00375     else if (RetVT == MVT::ppcf128)
00376       return SINTTOFP_I32_PPCF128;
00377   } else if (OpVT == MVT::i64) {
00378     if (RetVT == MVT::f32)
00379       return SINTTOFP_I64_F32;
00380     else if (RetVT == MVT::f64)
00381       return SINTTOFP_I64_F64;
00382     else if (RetVT == MVT::f80)
00383       return SINTTOFP_I64_F80;
00384     else if (RetVT == MVT::ppcf128)
00385       return SINTTOFP_I64_PPCF128;
00386   } else if (OpVT == MVT::i128) {
00387     if (RetVT == MVT::f32)
00388       return SINTTOFP_I128_F32;
00389     else if (RetVT == MVT::f64)
00390       return SINTTOFP_I128_F64;
00391     else if (RetVT == MVT::f80)
00392       return SINTTOFP_I128_F80;
00393     else if (RetVT == MVT::ppcf128)
00394       return SINTTOFP_I128_PPCF128;
00395   }
00396   return UNKNOWN_LIBCALL;
00397 }
00398 
00399 /// getUINTTOFP - Return the UINTTOFP_*_* value for the given types, or
00400 /// UNKNOWN_LIBCALL if there is none.
00401 RTLIB::Libcall RTLIB::getUINTTOFP(EVT OpVT, EVT RetVT) {
00402   if (OpVT == MVT::i32) {
00403     if (RetVT == MVT::f32)
00404       return UINTTOFP_I32_F32;
00405     else if (RetVT == MVT::f64)
00406       return UINTTOFP_I32_F64;
00407     else if (RetVT == MVT::f80)
00408       return UINTTOFP_I32_F80;
00409     else if (RetVT == MVT::ppcf128)
00410       return UINTTOFP_I32_PPCF128;
00411   } else if (OpVT == MVT::i64) {
00412     if (RetVT == MVT::f32)
00413       return UINTTOFP_I64_F32;
00414     else if (RetVT == MVT::f64)
00415       return UINTTOFP_I64_F64;
00416     else if (RetVT == MVT::f80)
00417       return UINTTOFP_I64_F80;
00418     else if (RetVT == MVT::ppcf128)
00419       return UINTTOFP_I64_PPCF128;
00420   } else if (OpVT == MVT::i128) {
00421     if (RetVT == MVT::f32)
00422       return UINTTOFP_I128_F32;
00423     else if (RetVT == MVT::f64)
00424       return UINTTOFP_I128_F64;
00425     else if (RetVT == MVT::f80)
00426       return UINTTOFP_I128_F80;
00427     else if (RetVT == MVT::ppcf128)
00428       return UINTTOFP_I128_PPCF128;
00429   }
00430   return UNKNOWN_LIBCALL;
00431 }
00432 
00433 /// InitCmpLibcallCCs - Set default comparison libcall CC.
00434 ///
00435 static void InitCmpLibcallCCs(ISD::CondCode *CCs) {
00436   memset(CCs, ISD::SETCC_INVALID, sizeof(ISD::CondCode)*RTLIB::UNKNOWN_LIBCALL);
00437   CCs[RTLIB::OEQ_F32] = ISD::SETEQ;
00438   CCs[RTLIB::OEQ_F64] = ISD::SETEQ;
00439   CCs[RTLIB::UNE_F32] = ISD::SETNE;
00440   CCs[RTLIB::UNE_F64] = ISD::SETNE;
00441   CCs[RTLIB::OGE_F32] = ISD::SETGE;
00442   CCs[RTLIB::OGE_F64] = ISD::SETGE;
00443   CCs[RTLIB::OLT_F32] = ISD::SETLT;
00444   CCs[RTLIB::OLT_F64] = ISD::SETLT;
00445   CCs[RTLIB::OLE_F32] = ISD::SETLE;
00446   CCs[RTLIB::OLE_F64] = ISD::SETLE;
00447   CCs[RTLIB::OGT_F32] = ISD::SETGT;
00448   CCs[RTLIB::OGT_F64] = ISD::SETGT;
00449   CCs[RTLIB::UO_F32] = ISD::SETNE;
00450   CCs[RTLIB::UO_F64] = ISD::SETNE;
00451   CCs[RTLIB::O_F32] = ISD::SETEQ;
00452   CCs[RTLIB::O_F64] = ISD::SETEQ;
00453 }
00454 
00455 /// NOTE: The constructor takes ownership of TLOF.
00456 TargetLowering::TargetLowering(TargetMachine &tm,TargetLoweringObjectFile *tlof)
00457   : TM(tm), TD(TM.getTargetData()), TLOF(*tlof) {
00458   // All operations default to being supported.
00459   memset(OpActions, 0, sizeof(OpActions));
00460   memset(LoadExtActions, 0, sizeof(LoadExtActions));
00461   memset(TruncStoreActions, 0, sizeof(TruncStoreActions));
00462   memset(IndexedModeActions, 0, sizeof(IndexedModeActions));
00463   memset(ConvertActions, 0, sizeof(ConvertActions));
00464   memset(CondCodeActions, 0, sizeof(CondCodeActions));
00465 
00466   // Set default actions for various operations.
00467   for (unsigned VT = 0; VT != (unsigned)MVT::LAST_VALUETYPE; ++VT) {
00468     // Default all indexed load / store to expand.
00469     for (unsigned IM = (unsigned)ISD::PRE_INC;
00470          IM != (unsigned)ISD::LAST_INDEXED_MODE; ++IM) {
00471       setIndexedLoadAction(IM, (MVT::SimpleValueType)VT, Expand);
00472       setIndexedStoreAction(IM, (MVT::SimpleValueType)VT, Expand);
00473     }
00474     
00475     // These operations default to expand.
00476     setOperationAction(ISD::FGETSIGN, (MVT::SimpleValueType)VT, Expand);
00477     setOperationAction(ISD::CONCAT_VECTORS, (MVT::SimpleValueType)VT, Expand);
00478   }
00479 
00480   // Most targets ignore the @llvm.prefetch intrinsic.
00481   setOperationAction(ISD::PREFETCH, MVT::Other, Expand);
00482   
00483   // ConstantFP nodes default to expand.  Targets can either change this to 
00484   // Legal, in which case all fp constants are legal, or use addLegalFPImmediate
00485   // to optimize expansions for certain constants.
00486   setOperationAction(ISD::ConstantFP, MVT::f32, Expand);
00487   setOperationAction(ISD::ConstantFP, MVT::f64, Expand);
00488   setOperationAction(ISD::ConstantFP, MVT::f80, Expand);
00489 
00490   // These library functions default to expand.
00491   setOperationAction(ISD::FLOG , MVT::f64, Expand);
00492   setOperationAction(ISD::FLOG2, MVT::f64, Expand);
00493   setOperationAction(ISD::FLOG10,MVT::f64, Expand);
00494   setOperationAction(ISD::FEXP , MVT::f64, Expand);
00495   setOperationAction(ISD::FEXP2, MVT::f64, Expand);
00496   setOperationAction(ISD::FLOG , MVT::f32, Expand);
00497   setOperationAction(ISD::FLOG2, MVT::f32, Expand);
00498   setOperationAction(ISD::FLOG10,MVT::f32, Expand);
00499   setOperationAction(ISD::FEXP , MVT::f32, Expand);
00500   setOperationAction(ISD::FEXP2, MVT::f32, Expand);
00501 
00502   // Default ISD::TRAP to expand (which turns it into abort).
00503   setOperationAction(ISD::TRAP, MVT::Other, Expand);
00504     
00505   IsLittleEndian = TD->isLittleEndian();
00506   UsesGlobalOffsetTable = false;
00507   ShiftAmountTy = PointerTy = MVT::getIntegerVT(8*TD->getPointerSize());
00508   memset(RegClassForVT, 0,MVT::LAST_VALUETYPE*sizeof(TargetRegisterClass*));
00509   memset(TargetDAGCombineArray, 0, array_lengthof(TargetDAGCombineArray));
00510   maxStoresPerMemset = maxStoresPerMemcpy = maxStoresPerMemmove = 8;
00511   benefitFromCodePlacementOpt = false;
00512   UseUnderscoreSetJmp = false;
00513   UseUnderscoreLongJmp = false;
00514   SelectIsExpensive = false;
00515   IntDivIsCheap = false;
00516   Pow2DivIsCheap = false;
00517   StackPointerRegisterToSaveRestore = 0;
00518   ExceptionPointerRegister = 0;
00519   ExceptionSelectorRegister = 0;
00520   BooleanContents = UndefinedBooleanContent;
00521   SchedPreferenceInfo = SchedulingForLatency;
00522   JumpBufSize = 0;
00523   JumpBufAlignment = 0;
00524   IfCvtBlockSizeLimit = 2;
00525   IfCvtDupBlockSizeLimit = 0;
00526   PrefLoopAlignment = 0;
00527 
00528   InitLibcallNames(LibcallRoutineNames);
00529   InitCmpLibcallCCs(CmpLibcallCCs);
00530   InitLibcallCallingConvs(LibcallCallingConvs);
00531 
00532   // Tell Legalize whether the assembler supports DEBUG_LOC.
00533   const TargetAsmInfo *TASM = TM.getTargetAsmInfo();
00534   if (!TASM || !TASM->hasDotLocAndDotFile())
00535     setOperationAction(ISD::DEBUG_LOC, MVT::Other, Expand);
00536 }
00537 
00538 TargetLowering::~TargetLowering() {
00539   delete &TLOF;
00540 }
00541 
00542 static unsigned getVectorTypeBreakdownMVT(MVT VT, MVT &IntermediateVT,
00543                                        unsigned &NumIntermediates,
00544                                        EVT &RegisterVT,
00545                                        TargetLowering* TLI) {
00546   // Figure out the right, legal destination reg to copy into.
00547   unsigned NumElts = VT.getVectorNumElements();
00548   MVT EltTy = VT.getVectorElementType();
00549   
00550   unsigned NumVectorRegs = 1;
00551   
00552   // FIXME: We don't support non-power-of-2-sized vectors for now.  Ideally we 
00553   // could break down into LHS/RHS like LegalizeDAG does.
00554   if (!isPowerOf2_32(NumElts)) {
00555     NumVectorRegs = NumElts;
00556     NumElts = 1;
00557   }
00558   
00559   // Divide the input until we get to a supported size.  This will always
00560   // end with a scalar if the target doesn't support vectors.
00561   while (NumElts > 1 && !TLI->isTypeLegal(MVT::getVectorVT(EltTy, NumElts))) {
00562     NumElts >>= 1;
00563     NumVectorRegs <<= 1;
00564   }
00565 
00566   NumIntermediates = NumVectorRegs;
00567   
00568   MVT NewVT = MVT::getVectorVT(EltTy, NumElts);
00569   if (!TLI->isTypeLegal(NewVT))
00570     NewVT = EltTy;
00571   IntermediateVT = NewVT;
00572 
00573   EVT DestVT = TLI->getRegisterType(NewVT);
00574   RegisterVT = DestVT;
00575   if (EVT(DestVT).bitsLT(NewVT)) {
00576     // Value is expanded, e.g. i64 -> i16.
00577     return NumVectorRegs*(NewVT.getSizeInBits()/DestVT.getSizeInBits());
00578   } else {
00579     // Otherwise, promotion or legal types use the same number of registers as
00580     // the vector decimated to the appropriate level.
00581     return NumVectorRegs;
00582   }
00583   
00584   return 1;
00585 }
00586 
00587 /// computeRegisterProperties - Once all of the register classes are added,
00588 /// this allows us to compute derived properties we expose.
00589 void TargetLowering::computeRegisterProperties() {
00590   assert(MVT::LAST_VALUETYPE <= MVT::MAX_ALLOWED_VALUETYPE &&
00591          "Too many value types for ValueTypeActions to hold!");
00592 
00593   // Everything defaults to needing one register.
00594   for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i) {
00595     NumRegistersForVT[i] = 1;
00596     RegisterTypeForVT[i] = TransformToType[i] = (MVT::SimpleValueType)i;
00597   }
00598   // ...except isVoid, which doesn't need any registers.
00599   NumRegistersForVT[MVT::isVoid] = 0;
00600 
00601   // Find the largest integer register class.
00602   unsigned LargestIntReg = MVT::LAST_INTEGER_VALUETYPE;
00603   for (; RegClassForVT[LargestIntReg] == 0; --LargestIntReg)
00604     assert(LargestIntReg != MVT::i1 && "No integer registers defined!");
00605 
00606   // Every integer value type larger than this largest register takes twice as
00607   // many registers to represent as the previous ValueType.
00608   for (unsigned ExpandedReg = LargestIntReg + 1; ; ++ExpandedReg) {
00609     EVT EVT = (MVT::SimpleValueType)ExpandedReg;
00610     if (!EVT.isInteger())
00611       break;
00612     NumRegistersForVT[ExpandedReg] = 2*NumRegistersForVT[ExpandedReg-1];
00613     RegisterTypeForVT[ExpandedReg] = (MVT::SimpleValueType)LargestIntReg;
00614     TransformToType[ExpandedReg] = (MVT::SimpleValueType)(ExpandedReg - 1);
00615     ValueTypeActions.setTypeAction(EVT, Expand);
00616   }
00617 
00618   // Inspect all of the ValueType's smaller than the largest integer
00619   // register to see which ones need promotion.
00620   unsigned LegalIntReg = LargestIntReg;
00621   for (unsigned IntReg = LargestIntReg - 1;
00622        IntReg >= (unsigned)MVT::i1; --IntReg) {
00623     EVT IVT = (MVT::SimpleValueType)IntReg;
00624     if (isTypeLegal(IVT)) {
00625       LegalIntReg = IntReg;
00626     } else {
00627       RegisterTypeForVT[IntReg] = TransformToType[IntReg] =
00628         (MVT::SimpleValueType)LegalIntReg;
00629       ValueTypeActions.setTypeAction(IVT, Promote);
00630     }
00631   }
00632 
00633   // ppcf128 type is really two f64's.
00634   if (!isTypeLegal(MVT::ppcf128)) {
00635     NumRegistersForVT[MVT::ppcf128] = 2*NumRegistersForVT[MVT::f64];
00636     RegisterTypeForVT[MVT::ppcf128] = MVT::f64;
00637     TransformToType[MVT::ppcf128] = MVT::f64;
00638     ValueTypeActions.setTypeAction(MVT::ppcf128, Expand);
00639   }    
00640 
00641   // Decide how to handle f64. If the target does not have native f64 support,
00642   // expand it to i64 and we will be generating soft float library calls.
00643   if (!isTypeLegal(MVT::f64)) {
00644     NumRegistersForVT[MVT::f64] = NumRegistersForVT[MVT::i64];
00645     RegisterTypeForVT[MVT::f64] = RegisterTypeForVT[MVT::i64];
00646     TransformToType[MVT::f64] = MVT::i64;
00647     ValueTypeActions.setTypeAction(MVT::f64, Expand);
00648   }
00649 
00650   // Decide how to handle f32. If the target does not have native support for
00651   // f32, promote it to f64 if it is legal. Otherwise, expand it to i32.
00652   if (!isTypeLegal(MVT::f32)) {
00653     if (isTypeLegal(MVT::f64)) {
00654       NumRegistersForVT[MVT::f32] = NumRegistersForVT[MVT::f64];
00655       RegisterTypeForVT[MVT::f32] = RegisterTypeForVT[MVT::f64];
00656       TransformToType[MVT::f32] = MVT::f64;
00657       ValueTypeActions.setTypeAction(MVT::f32, Promote);
00658     } else {
00659       NumRegistersForVT[MVT::f32] = NumRegistersForVT[MVT::i32];
00660       RegisterTypeForVT[MVT::f32] = RegisterTypeForVT[MVT::i32];
00661       TransformToType[MVT::f32] = MVT::i32;
00662       ValueTypeActions.setTypeAction(MVT::f32, Expand);
00663     }
00664   }
00665   
00666   // Loop over all of the vector value types to see which need transformations.
00667   for (unsigned i = MVT::FIRST_VECTOR_VALUETYPE;
00668        i <= (unsigned)MVT::LAST_VECTOR_VALUETYPE; ++i) {
00669     MVT VT = (MVT::SimpleValueType)i;
00670     if (!isTypeLegal(VT)) {
00671       MVT IntermediateVT;
00672       EVT RegisterVT;
00673       unsigned NumIntermediates;
00674       NumRegistersForVT[i] =
00675         getVectorTypeBreakdownMVT(VT, IntermediateVT, NumIntermediates,
00676                                   RegisterVT, this);
00677       RegisterTypeForVT[i] = RegisterVT;
00678       
00679       // Determine if there is a legal wider type.
00680       bool IsLegalWiderType = false;
00681       EVT EltVT = VT.getVectorElementType();
00682       unsigned NElts = VT.getVectorNumElements();
00683       for (unsigned nVT = i+1; nVT <= MVT::LAST_VECTOR_VALUETYPE; ++nVT) {
00684         EVT SVT = (MVT::SimpleValueType)nVT;
00685         if (isTypeLegal(SVT) && SVT.getVectorElementType() == EltVT &&
00686             SVT.getVectorNumElements() > NElts) {
00687           TransformToType[i] = SVT;
00688           ValueTypeActions.setTypeAction(VT, Promote);
00689           IsLegalWiderType = true;
00690           break;
00691         }
00692       }
00693       if (!IsLegalWiderType) {
00694         EVT NVT = VT.getPow2VectorType();
00695         if (NVT == VT) {
00696           // Type is already a power of 2.  The default action is to split.
00697           TransformToType[i] = MVT::Other;
00698           ValueTypeActions.setTypeAction(VT, Expand);
00699         } else {
00700           TransformToType[i] = NVT;
00701           ValueTypeActions.setTypeAction(VT, Promote);
00702         }
00703       }
00704     }
00705   }
00706 }
00707 
00708 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
00709   return NULL;
00710 }
00711 
00712 
00713 MVT::SimpleValueType TargetLowering::getSetCCResultType(EVT VT) const {
00714   return PointerTy.SimpleTy;
00715 }
00716 
00717 /// getVectorTypeBreakdown - Vector types are broken down into some number of
00718 /// legal first class types.  For example, MVT::v8f32 maps to 2 MVT::v4f32
00719 /// with Altivec or SSE1, or 8 promoted MVT::f64 values with the X86 FP stack.
00720 /// Similarly, MVT::v2i64 turns into 4 MVT::i32 values with both PPC and X86.
00721 ///
00722 /// This method returns the number of registers needed, and the VT for each
00723 /// register.  It also returns the VT and quantity of the intermediate values
00724 /// before they are promoted/expanded.
00725 ///
00726 unsigned TargetLowering::getVectorTypeBreakdown(LLVMContext &Context, EVT VT,
00727                                                 EVT &IntermediateVT,
00728                                                 unsigned &NumIntermediates,
00729                                                 EVT &RegisterVT) const {
00730   // Figure out the right, legal destination reg to copy into.
00731   unsigned NumElts = VT.getVectorNumElements();
00732   EVT EltTy = VT.getVectorElementType();
00733   
00734   unsigned NumVectorRegs = 1;
00735   
00736   // FIXME: We don't support non-power-of-2-sized vectors for now.  Ideally we 
00737   // could break down into LHS/RHS like LegalizeDAG does.
00738   if (!isPowerOf2_32(NumElts)) {
00739     NumVectorRegs = NumElts;
00740     NumElts = 1;
00741   }
00742   
00743   // Divide the input until we get to a supported size.  This will always
00744   // end with a scalar if the target doesn't support vectors.
00745   while (NumElts > 1 && !isTypeLegal(
00746                                    EVT::getVectorVT(Context, EltTy, NumElts))) {
00747     NumElts >>= 1;
00748     NumVectorRegs <<= 1;
00749   }
00750 
00751   NumIntermediates = NumVectorRegs;
00752   
00753   EVT NewVT = EVT::getVectorVT(Context, EltTy, NumElts);
00754   if (!isTypeLegal(NewVT))
00755     NewVT = EltTy;
00756   IntermediateVT = NewVT;
00757 
00758   EVT DestVT = getRegisterType(Context, NewVT);
00759   RegisterVT = DestVT;
00760   if (DestVT.bitsLT(NewVT)) {
00761     // Value is expanded, e.g. i64 -> i16.
00762     return NumVectorRegs*(NewVT.getSizeInBits()/DestVT.getSizeInBits());
00763   } else {
00764     // Otherwise, promotion or legal types use the same number of registers as
00765     // the vector decimated to the appropriate level.
00766     return NumVectorRegs;
00767   }
00768   
00769   return 1;
00770 }
00771 
00772 /// getWidenVectorType: given a vector type, returns the type to widen to
00773 /// (e.g., v7i8 to v8i8). If the vector type is legal, it returns itself.
00774 /// If there is no vector type that we want to widen to, returns MVT::Other
00775 /// When and where to widen is target dependent based on the cost of
00776 /// scalarizing vs using the wider vector type.
00777 EVT TargetLowering::getWidenVectorType(EVT VT) const {
00778   assert(VT.isVector());
00779   if (isTypeLegal(VT))
00780     return VT;
00781  
00782   // Default is not to widen until moved to LegalizeTypes
00783   return MVT::Other;
00784 }
00785 
00786 /// getByValTypeAlignment - Return the desired alignment for ByVal aggregate
00787 /// function arguments in the caller parameter area.  This is the actual
00788 /// alignment, not its logarithm.
00789 unsigned TargetLowering::getByValTypeAlignment(const Type *Ty) const {
00790   return TD->getCallFrameTypeAlignment(Ty);
00791 }
00792 
00793 SDValue TargetLowering::getPICJumpTableRelocBase(SDValue Table,
00794                                                  SelectionDAG &DAG) const {
00795   if (usesGlobalOffsetTable())
00796     return DAG.getGLOBAL_OFFSET_TABLE(getPointerTy());
00797   return Table;
00798 }
00799 
00800 bool
00801 TargetLowering::isOffsetFoldingLegal(const GlobalAddressSDNode *GA) const {
00802   // Assume that everything is safe in static mode.
00803   if (getTargetMachine().getRelocationModel() == Reloc::Static)
00804     return true;
00805 
00806   // In dynamic-no-pic mode, assume that known defined values are safe.
00807   if (getTargetMachine().getRelocationModel() == Reloc::DynamicNoPIC &&
00808       GA &&
00809       !GA->getGlobal()->isDeclaration() &&
00810       !GA->getGlobal()->isWeakForLinker())
00811     return true;
00812 
00813   // Otherwise assume nothing is safe.
00814   return false;
00815 }
00816 
00817 //===----------------------------------------------------------------------===//
00818 //  Optimization Methods
00819 //===----------------------------------------------------------------------===//
00820 
00821 /// ShrinkDemandedConstant - Check to see if the specified operand of the 
00822 /// specified instruction is a constant integer.  If so, check to see if there
00823 /// are any bits set in the constant that are not demanded.  If so, shrink the
00824 /// constant and return true.
00825 bool TargetLowering::TargetLoweringOpt::ShrinkDemandedConstant(SDValue Op, 
00826                                                         const APInt &Demanded) {
00827   DebugLoc dl = Op.getDebugLoc();
00828 
00829   // FIXME: ISD::SELECT, ISD::SELECT_CC
00830   switch (Op.getOpcode()) {
00831   default: break;
00832   case ISD::XOR:
00833   case ISD::AND:
00834   case ISD::OR: {
00835     ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
00836     if (!C) return false;
00837 
00838     if (Op.getOpcode() == ISD::XOR &&
00839         (C->getAPIntValue() | (~Demanded)).isAllOnesValue())
00840       return false;
00841 
00842     // if we can expand it to have all bits set, do it
00843     if (C->getAPIntValue().intersects(~Demanded)) {
00844       EVT VT = Op.getValueType();
00845       SDValue New = DAG.getNode(Op.getOpcode(), dl, VT, Op.getOperand(0),
00846                                 DAG.getConstant(Demanded &
00847                                                 C->getAPIntValue(), 
00848                                                 VT));
00849       return CombineTo(Op, New);
00850     }
00851 
00852     break;
00853   }
00854   }
00855 
00856   return false;
00857 }
00858 
00859 /// ShrinkDemandedOp - Convert x+y to (VT)((SmallVT)x+(SmallVT)y) if the
00860 /// casts are free.  This uses isZExtFree and ZERO_EXTEND for the widening
00861 /// cast, but it could be generalized for targets with other types of
00862 /// implicit widening casts.
00863 bool
00864 TargetLowering::TargetLoweringOpt::ShrinkDemandedOp(SDValue Op,
00865                                                     unsigned BitWidth,
00866                                                     const APInt &Demanded,
00867                                                     DebugLoc dl) {
00868   assert(Op.getNumOperands() == 2 &&
00869          "ShrinkDemandedOp only supports binary operators!");
00870   assert(Op.getNode()->getNumValues() == 1 &&
00871          "ShrinkDemandedOp only supports nodes with one result!");
00872 
00873   // Don't do this if the node has another user, which may require the
00874   // full value.
00875   if (!Op.getNode()->hasOneUse())
00876     return false;
00877 
00878   // Search for the smallest integer type with free casts to and from
00879   // Op's type. For expedience, just check power-of-2 integer types.
00880   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
00881   unsigned SmallVTBits = BitWidth - Demanded.countLeadingZeros();
00882   if (!isPowerOf2_32(SmallVTBits))
00883     SmallVTBits = NextPowerOf2(SmallVTBits);
00884   for (; SmallVTBits < BitWidth; SmallVTBits = NextPowerOf2(SmallVTBits)) {
00885     EVT SmallVT = EVT::getIntegerVT(*DAG.getContext(), SmallVTBits);
00886     if (TLI.isTruncateFree(Op.getValueType(), SmallVT) &&
00887         TLI.isZExtFree(SmallVT, Op.getValueType())) {
00888       // We found a type with free casts.
00889       SDValue X = DAG.getNode(Op.getOpcode(), dl, SmallVT,
00890                               DAG.getNode(ISD::TRUNCATE, dl, SmallVT,
00891                                           Op.getNode()->getOperand(0)),
00892                               DAG.getNode(ISD::TRUNCATE, dl, SmallVT,
00893                                           Op.getNode()->getOperand(1)));
00894       SDValue Z = DAG.getNode(ISD::ZERO_EXTEND, dl, Op.getValueType(), X);
00895       return CombineTo(Op, Z);
00896     }
00897   }
00898   return false;
00899 }
00900 
00901 /// SimplifyDemandedBits - Look at Op.  At this point, we know that only the
00902 /// DemandedMask bits of the result of Op are ever used downstream.  If we can
00903 /// use this information to simplify Op, create a new simplified DAG node and
00904 /// return true, returning the original and new nodes in Old and New. Otherwise,
00905 /// analyze the expression and return a mask of KnownOne and KnownZero bits for
00906 /// the expression (used to simplify the caller).  The KnownZero/One bits may
00907 /// only be accurate for those bits in the DemandedMask.
00908 bool TargetLowering::SimplifyDemandedBits(SDValue Op,
00909                                           const APInt &DemandedMask,
00910                                           APInt &KnownZero,
00911                                           APInt &KnownOne,
00912                                           TargetLoweringOpt &TLO,
00913                                           unsigned Depth) const {
00914   unsigned BitWidth = DemandedMask.getBitWidth();
00915   assert(Op.getValueSizeInBits() == BitWidth &&
00916          "Mask size mismatches value type size!");
00917   APInt NewMask = DemandedMask;
00918   DebugLoc dl = Op.getDebugLoc();
00919 
00920   // Don't know anything.
00921   KnownZero = KnownOne = APInt(BitWidth, 0);
00922 
00923   // Other users may use these bits.
00924   if (!Op.getNode()->hasOneUse()) { 
00925     if (Depth != 0) {
00926       // If not at the root, Just compute the KnownZero/KnownOne bits to 
00927       // simplify things downstream.
00928       TLO.DAG.ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth);
00929       return false;
00930     }
00931     // If this is the root being simplified, allow it to have multiple uses,
00932     // just set the NewMask to all bits.
00933     NewMask = APInt::getAllOnesValue(BitWidth);
00934   } else if (DemandedMask == 0) {   
00935     // Not demanding any bits from Op.
00936     if (Op.getOpcode() != ISD::UNDEF)
00937       return TLO.CombineTo(Op, TLO.DAG.getUNDEF(Op.getValueType()));
00938     return false;
00939   } else if (Depth == 6) {        // Limit search depth.
00940     return false;
00941   }
00942 
00943   APInt KnownZero2, KnownOne2, KnownZeroOut, KnownOneOut;
00944   switch (Op.getOpcode()) {
00945   case ISD::Constant:
00946     // We know all of the bits for a constant!
00947     KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue() & NewMask;
00948     KnownZero = ~KnownOne & NewMask;
00949     return false;   // Don't fall through, will infinitely loop.
00950   case ISD::AND:
00951     // If the RHS is a constant, check to see if the LHS would be zero without
00952     // using the bits from the RHS.  Below, we use knowledge about the RHS to
00953     // simplify the LHS, here we're using information from the LHS to simplify
00954     // the RHS.
00955     if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
00956       APInt LHSZero, LHSOne;
00957       TLO.DAG.ComputeMaskedBits(Op.getOperand(0), NewMask,
00958                                 LHSZero, LHSOne, Depth+1);
00959       // If the LHS already has zeros where RHSC does, this and is dead.
00960       if ((LHSZero & NewMask) == (~RHSC->getAPIntValue() & NewMask))
00961         return TLO.CombineTo(Op, Op.getOperand(0));
00962       // If any of the set bits in the RHS are known zero on the LHS, shrink
00963       // the constant.
00964       if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & NewMask))
00965         return true;
00966     }
00967     
00968     if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero,
00969                              KnownOne, TLO, Depth+1))
00970       return true;
00971     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
00972     if (SimplifyDemandedBits(Op.getOperand(0), ~KnownZero & NewMask,
00973                              KnownZero2, KnownOne2, TLO, Depth+1))
00974       return true;
00975     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 
00976       
00977     // If all of the demanded bits are known one on one side, return the other.
00978     // These bits cannot contribute to the result of the 'and'.
00979     if ((NewMask & ~KnownZero2 & KnownOne) == (~KnownZero2 & NewMask))
00980       return TLO.CombineTo(Op, Op.getOperand(0));
00981     if ((NewMask & ~KnownZero & KnownOne2) == (~KnownZero & NewMask))
00982       return TLO.CombineTo(Op, Op.getOperand(1));
00983     // If all of the demanded bits in the inputs are known zeros, return zero.
00984     if ((NewMask & (KnownZero|KnownZero2)) == NewMask)
00985       return TLO.CombineTo(Op, TLO.DAG.getConstant(0, Op.getValueType()));
00986     // If the RHS is a constant, see if we can simplify it.
00987     if (TLO.ShrinkDemandedConstant(Op, ~KnownZero2 & NewMask))
00988       return true;
00989     // If the operation can be done in a smaller type, do so.
00990     if (TLO.ShrinkDemandedOp(Op, BitWidth, NewMask, dl))
00991       return true;
00992 
00993     // Output known-1 bits are only known if set in both the LHS & RHS.
00994     KnownOne &= KnownOne2;
00995     // Output known-0 are known to be clear if zero in either the LHS | RHS.
00996     KnownZero |= KnownZero2;
00997     break;
00998   case ISD::OR:
00999     if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero, 
01000                              KnownOne, TLO, Depth+1))
01001       return true;
01002     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01003     if (SimplifyDemandedBits(Op.getOperand(0), ~KnownOne & NewMask,
01004                              KnownZero2, KnownOne2, TLO, Depth+1))
01005       return true;
01006     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 
01007     
01008     // If all of the demanded bits are known zero on one side, return the other.
01009     // These bits cannot contribute to the result of the 'or'.
01010     if ((NewMask & ~KnownOne2 & KnownZero) == (~KnownOne2 & NewMask))
01011       return TLO.CombineTo(Op, Op.getOperand(0));
01012     if ((NewMask & ~KnownOne & KnownZero2) == (~KnownOne & NewMask))
01013       return TLO.CombineTo(Op, Op.getOperand(1));
01014     // If all of the potentially set bits on one side are known to be set on
01015     // the other side, just use the 'other' side.
01016     if ((NewMask & ~KnownZero & KnownOne2) == (~KnownZero & NewMask))
01017       return TLO.CombineTo(Op, Op.getOperand(0));
01018     if ((NewMask & ~KnownZero2 & KnownOne) == (~KnownZero2 & NewMask))
01019       return TLO.CombineTo(Op, Op.getOperand(1));
01020     // If the RHS is a constant, see if we can simplify it.
01021     if (TLO.ShrinkDemandedConstant(Op, NewMask))
01022       return true;
01023     // If the operation can be done in a smaller type, do so.
01024     if (TLO.ShrinkDemandedOp(Op, BitWidth, NewMask, dl))
01025       return true;
01026 
01027     // Output known-0 bits are only known if clear in both the LHS & RHS.
01028     KnownZero &= KnownZero2;
01029     // Output known-1 are known to be set if set in either the LHS | RHS.
01030     KnownOne |= KnownOne2;
01031     break;
01032   case ISD::XOR:
01033     if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero, 
01034                              KnownOne, TLO, Depth+1))
01035       return true;
01036     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01037     if (SimplifyDemandedBits(Op.getOperand(0), NewMask, KnownZero2,
01038                              KnownOne2, TLO, Depth+1))
01039       return true;
01040     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 
01041     
01042     // If all of the demanded bits are known zero on one side, return the other.
01043     // These bits cannot contribute to the result of the 'xor'.
01044     if ((KnownZero & NewMask) == NewMask)
01045       return TLO.CombineTo(Op, Op.getOperand(0));
01046     if ((KnownZero2 & NewMask) == NewMask)
01047       return TLO.CombineTo(Op, Op.getOperand(1));
01048     // If the operation can be done in a smaller type, do so.
01049     if (TLO.ShrinkDemandedOp(Op, BitWidth, NewMask, dl))
01050       return true;
01051 
01052     // If all of the unknown bits are known to be zero on one side or the other
01053     // (but not both) turn this into an *inclusive* or.
01054     //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
01055     if ((NewMask & ~KnownZero & ~KnownZero2) == 0)
01056       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, dl, Op.getValueType(),
01057                                                Op.getOperand(0),
01058                                                Op.getOperand(1)));
01059     
01060     // Output known-0 bits are known if clear or set in both the LHS & RHS.
01061     KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
01062     // Output known-1 are known to be set if set in only one of the LHS, RHS.
01063     KnownOneOut = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
01064     
01065     // If all of the demanded bits on one side are known, and all of the set
01066     // bits on that side are also known to be set on the other side, turn this
01067     // into an AND, as we know the bits will be cleared.
01068     //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
01069     if ((NewMask & (KnownZero|KnownOne)) == NewMask) { // all known
01070       if ((KnownOne & KnownOne2) == KnownOne) {
01071         EVT VT = Op.getValueType();
01072         SDValue ANDC = TLO.DAG.getConstant(~KnownOne & NewMask, VT);
01073         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, dl, VT, 
01074                                                  Op.getOperand(0), ANDC));
01075       }
01076     }
01077     
01078     // If the RHS is a constant, see if we can simplify it.
01079     // for XOR, we prefer to force bits to 1 if they will make a -1.
01080     // if we can't force bits, try to shrink constant
01081     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
01082       APInt Expanded = C->getAPIntValue() | (~NewMask);
01083       // if we can expand it to have all bits set, do it
01084       if (Expanded.isAllOnesValue()) {
01085         if (Expanded != C->getAPIntValue()) {
01086           EVT VT = Op.getValueType();
01087           SDValue New = TLO.DAG.getNode(Op.getOpcode(), dl,VT, Op.getOperand(0),
01088                                           TLO.DAG.getConstant(Expanded, VT));
01089           return TLO.CombineTo(Op, New);
01090         }
01091         // if it already has all the bits set, nothing to change
01092         // but don't shrink either!
01093       } else if (TLO.ShrinkDemandedConstant(Op, NewMask)) {
01094         return true;
01095       }
01096     }
01097 
01098     KnownZero = KnownZeroOut;
01099     KnownOne  = KnownOneOut;
01100     break;
01101   case ISD::SELECT:
01102     if (SimplifyDemandedBits(Op.getOperand(2), NewMask, KnownZero, 
01103                              KnownOne, TLO, Depth+1))
01104       return true;
01105     if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero2,
01106                              KnownOne2, TLO, Depth+1))
01107       return true;
01108     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01109     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 
01110     
01111     // If the operands are constants, see if we can simplify them.
01112     if (TLO.ShrinkDemandedConstant(Op, NewMask))
01113       return true;
01114     
01115     // Only known if known in both the LHS and RHS.
01116     KnownOne &= KnownOne2;
01117     KnownZero &= KnownZero2;
01118     break;
01119   case ISD::SELECT_CC:
01120     if (SimplifyDemandedBits(Op.getOperand(3), NewMask, KnownZero, 
01121                              KnownOne, TLO, Depth+1))
01122       return true;
01123     if (SimplifyDemandedBits(Op.getOperand(2), NewMask, KnownZero2,
01124                              KnownOne2, TLO, Depth+1))
01125       return true;
01126     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01127     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 
01128     
01129     // If the operands are constants, see if we can simplify them.
01130     if (TLO.ShrinkDemandedConstant(Op, NewMask))
01131       return true;
01132       
01133     // Only known if known in both the LHS and RHS.
01134     KnownOne &= KnownOne2;
01135     KnownZero &= KnownZero2;
01136     break;
01137   case ISD::SHL:
01138     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
01139       unsigned ShAmt = SA->getZExtValue();
01140       SDValue InOp = Op.getOperand(0);
01141 
01142       // If the shift count is an invalid immediate, don't do anything.
01143       if (ShAmt >= BitWidth)
01144         break;
01145 
01146       // If this is ((X >>u C1) << ShAmt), see if we can simplify this into a
01147       // single shift.  We can do this if the bottom bits (which are shifted
01148       // out) are never demanded.
01149       if (InOp.getOpcode() == ISD::SRL &&
01150           isa<ConstantSDNode>(InOp.getOperand(1))) {
01151         if (ShAmt && (NewMask & APInt::getLowBitsSet(BitWidth, ShAmt)) == 0) {
01152           unsigned C1= cast<ConstantSDNode>(InOp.getOperand(1))->getZExtValue();
01153           unsigned Opc = ISD::SHL;
01154           int Diff = ShAmt-C1;
01155           if (Diff < 0) {
01156             Diff = -Diff;
01157             Opc = ISD::SRL;
01158           }          
01159           
01160           SDValue NewSA = 
01161             TLO.DAG.getConstant(Diff, Op.getOperand(1).getValueType());
01162           EVT VT = Op.getValueType();
01163           return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT,
01164                                                    InOp.getOperand(0), NewSA));
01165         }
01166       }      
01167       
01168       if (SimplifyDemandedBits(Op.getOperand(0), NewMask.lshr(ShAmt),
01169                                KnownZero, KnownOne, TLO, Depth+1))
01170         return true;
01171       KnownZero <<= SA->getZExtValue();
01172       KnownOne  <<= SA->getZExtValue();
01173       // low bits known zero.
01174       KnownZero |= APInt::getLowBitsSet(BitWidth, SA->getZExtValue());
01175     }
01176     break;
01177   case ISD::SRL:
01178     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
01179       EVT VT = Op.getValueType();
01180       unsigned ShAmt = SA->getZExtValue();
01181       unsigned VTSize = VT.getSizeInBits();
01182       SDValue InOp = Op.getOperand(0);
01183       
01184       // If the shift count is an invalid immediate, don't do anything.
01185       if (ShAmt >= BitWidth)
01186         break;
01187 
01188       // If this is ((X << C1) >>u ShAmt), see if we can simplify this into a
01189       // single shift.  We can do this if the top bits (which are shifted out)
01190       // are never demanded.
01191       if (InOp.getOpcode() == ISD::SHL &&
01192           isa<ConstantSDNode>(InOp.getOperand(1))) {
01193         if (ShAmt && (NewMask & APInt::getHighBitsSet(VTSize, ShAmt)) == 0) {
01194           unsigned C1= cast<ConstantSDNode>(InOp.getOperand(1))->getZExtValue();
01195           unsigned Opc = ISD::SRL;
01196           int Diff = ShAmt-C1;
01197           if (Diff < 0) {
01198             Diff = -Diff;
01199             Opc = ISD::SHL;
01200           }          
01201           
01202           SDValue NewSA =
01203             TLO.DAG.getConstant(Diff, Op.getOperand(1).getValueType());
01204           return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT,
01205                                                    InOp.getOperand(0), NewSA));
01206         }
01207       }      
01208       
01209       // Compute the new bits that are at the top now.
01210       if (SimplifyDemandedBits(InOp, (NewMask << ShAmt),
01211                                KnownZero, KnownOne, TLO, Depth+1))
01212         return true;
01213       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01214       KnownZero = KnownZero.lshr(ShAmt);
01215       KnownOne  = KnownOne.lshr(ShAmt);
01216 
01217       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
01218       KnownZero |= HighBits;  // High bits known zero.
01219     }
01220     break;
01221   case ISD::SRA:
01222     // If this is an arithmetic shift right and only the low-bit is set, we can
01223     // always convert this into a logical shr, even if the shift amount is
01224     // variable.  The low bit of the shift cannot be an input sign bit unless
01225     // the shift amount is >= the size of the datatype, which is undefined.
01226     if (DemandedMask == 1)
01227       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, Op.getValueType(),
01228                                                Op.getOperand(0), Op.getOperand(1)));
01229 
01230     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
01231       EVT VT = Op.getValueType();
01232       unsigned ShAmt = SA->getZExtValue();
01233       
01234       // If the shift count is an invalid immediate, don't do anything.
01235       if (ShAmt >= BitWidth)
01236         break;
01237 
01238       APInt InDemandedMask = (NewMask << ShAmt);
01239 
01240       // If any of the demanded bits are produced by the sign extension, we also
01241       // demand the input sign bit.
01242       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
01243       if (HighBits.intersects(NewMask))
01244         InDemandedMask |= APInt::getSignBit(VT.getSizeInBits());
01245       
01246       if (SimplifyDemandedBits(Op.getOperand(0), InDemandedMask,
01247                                KnownZero, KnownOne, TLO, Depth+1))
01248         return true;
01249       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01250       KnownZero = KnownZero.lshr(ShAmt);
01251       KnownOne  = KnownOne.lshr(ShAmt);
01252       
01253       // Handle the sign bit, adjusted to where it is now in the mask.
01254       APInt SignBit = APInt::getSignBit(BitWidth).lshr(ShAmt);
01255       
01256       // If the input sign bit is known to be zero, or if none of the top bits
01257       // are demanded, turn this into an unsigned shift right.
01258       if (KnownZero.intersects(SignBit) || (HighBits & ~NewMask) == HighBits) {
01259         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, VT, 
01260                                                  Op.getOperand(0),
01261                                                  Op.getOperand(1)));
01262       } else if (KnownOne.intersects(SignBit)) { // New bits are known one.
01263         KnownOne |= HighBits;
01264       }
01265     }
01266     break;
01267   case ISD::SIGN_EXTEND_INREG: {
01268     EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
01269 
01270     // Sign extension.  Compute the demanded bits in the result that are not 
01271     // present in the input.
01272     APInt NewBits = APInt::getHighBitsSet(BitWidth,
01273                                           BitWidth - EVT.getSizeInBits()) &
01274                     NewMask;
01275     
01276     // If none of the extended bits are demanded, eliminate the sextinreg.
01277     if (NewBits == 0)
01278       return TLO.CombineTo(Op, Op.getOperand(0));
01279 
01280     APInt InSignBit = APInt::getSignBit(EVT.getSizeInBits());
01281     InSignBit.zext(BitWidth);
01282     APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth,
01283                                                    EVT.getSizeInBits()) &
01284                               NewMask;
01285     
01286     // Since the sign extended bits are demanded, we know that the sign
01287     // bit is demanded.
01288     InputDemandedBits |= InSignBit;
01289 
01290     if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits,
01291                              KnownZero, KnownOne, TLO, Depth+1))
01292       return true;
01293     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01294 
01295     // If the sign bit of the input is known set or clear, then we know the
01296     // top bits of the result.
01297     
01298     // If the input sign bit is known zero, convert this into a zero extension.
01299     if (KnownZero.intersects(InSignBit))
01300       return TLO.CombineTo(Op, 
01301                            TLO.DAG.getZeroExtendInReg(Op.getOperand(0),dl,EVT));
01302     
01303     if (KnownOne.intersects(InSignBit)) {    // Input sign bit known set
01304       KnownOne |= NewBits;
01305       KnownZero &= ~NewBits;
01306     } else {                       // Input sign bit unknown
01307       KnownZero &= ~NewBits;
01308       KnownOne &= ~NewBits;
01309     }
01310     break;
01311   }
01312   case ISD::ZERO_EXTEND: {
01313     unsigned OperandBitWidth = Op.getOperand(0).getValueSizeInBits();
01314     APInt InMask = NewMask;
01315     InMask.trunc(OperandBitWidth);
01316     
01317     // If none of the top bits are demanded, convert this into an any_extend.
01318     APInt NewBits =
01319       APInt::getHighBitsSet(BitWidth, BitWidth - OperandBitWidth) & NewMask;
01320     if (!NewBits.intersects(NewMask))
01321       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl,
01322                                                Op.getValueType(), 
01323                                                Op.getOperand(0)));
01324     
01325     if (SimplifyDemandedBits(Op.getOperand(0), InMask,
01326                              KnownZero, KnownOne, TLO, Depth+1))
01327       return true;
01328     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01329     KnownZero.zext(BitWidth);
01330     KnownOne.zext(BitWidth);
01331     KnownZero |= NewBits;
01332     break;
01333   }
01334   case ISD::SIGN_EXTEND: {
01335     EVT InVT = Op.getOperand(0).getValueType();
01336     unsigned InBits = InVT.getSizeInBits();
01337     APInt InMask    = APInt::getLowBitsSet(BitWidth, InBits);
01338     APInt InSignBit = APInt::getBitsSet(BitWidth, InBits - 1, InBits);
01339     APInt NewBits   = ~InMask & NewMask;
01340     
01341     // If none of the top bits are demanded, convert this into an any_extend.
01342     if (NewBits == 0)
01343       return TLO.CombineTo(Op,TLO.DAG.getNode(ISD::ANY_EXTEND, dl,
01344                                               Op.getValueType(),
01345                                               Op.getOperand(0)));
01346     
01347     // Since some of the sign extended bits are demanded, we know that the sign
01348     // bit is demanded.
01349     APInt InDemandedBits = InMask & NewMask;
01350     InDemandedBits |= InSignBit;
01351     InDemandedBits.trunc(InBits);
01352     
01353     if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, KnownZero, 
01354                              KnownOne, TLO, Depth+1))
01355       return true;
01356     KnownZero.zext(BitWidth);
01357     KnownOne.zext(BitWidth);
01358     
01359     // If the sign bit is known zero, convert this to a zero extend.
01360     if (KnownZero.intersects(InSignBit))
01361       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, dl,
01362                                                Op.getValueType(), 
01363                                                Op.getOperand(0)));
01364     
01365     // If the sign bit is known one, the top bits match.
01366     if (KnownOne.intersects(InSignBit)) {
01367       KnownOne  |= NewBits;
01368       KnownZero &= ~NewBits;
01369     } else {   // Otherwise, top bits aren't known.
01370       KnownOne  &= ~NewBits;
01371       KnownZero &= ~NewBits;
01372     }
01373     break;
01374   }
01375   case ISD::ANY_EXTEND: {
01376     unsigned OperandBitWidth = Op.getOperand(0).getValueSizeInBits();
01377     APInt InMask = NewMask;
01378     InMask.trunc(OperandBitWidth);
01379     if (SimplifyDemandedBits(Op.getOperand(0), InMask,
01380                              KnownZero, KnownOne, TLO, Depth+1))
01381       return true;
01382     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01383     KnownZero.zext(BitWidth);
01384     KnownOne.zext(BitWidth);
01385     break;
01386   }
01387   case ISD::TRUNCATE: {
01388     // Simplify the input, using demanded bit information, and compute the known
01389     // zero/one bits live out.
01390     APInt TruncMask = NewMask;
01391     TruncMask.zext(Op.getOperand(0).getValueSizeInBits());
01392     if (SimplifyDemandedBits(Op.getOperand(0), TruncMask,
01393                              KnownZero, KnownOne, TLO, Depth+1))
01394       return true;
01395     KnownZero.trunc(BitWidth);
01396     KnownOne.trunc(BitWidth);
01397     
01398     // If the input is only used by this truncate, see if we can shrink it based
01399     // on the known demanded bits.
01400     if (Op.getOperand(0).getNode()->hasOneUse()) {
01401       SDValue In = Op.getOperand(0);
01402       unsigned InBitWidth = In.getValueSizeInBits();
01403       switch (In.getOpcode()) {
01404       default: break;
01405       case ISD::SRL:
01406         // Shrink SRL by a constant if none of the high bits shifted in are
01407         // demanded.
01408         if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(In.getOperand(1))){
01409           APInt HighBits = APInt::getHighBitsSet(InBitWidth,
01410                                                  InBitWidth - BitWidth);
01411           HighBits = HighBits.lshr(ShAmt->getZExtValue());
01412           HighBits.trunc(BitWidth);
01413           
01414           if (ShAmt->getZExtValue() < BitWidth && !(HighBits & NewMask)) {
01415             // None of the shifted in bits are needed.  Add a truncate of the
01416             // shift input, then shift it.
01417             SDValue NewTrunc = TLO.DAG.getNode(ISD::TRUNCATE, dl,
01418                                                  Op.getValueType(), 
01419                                                  In.getOperand(0));
01420             return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl,
01421                                                      Op.getValueType(),
01422                                                      NewTrunc, 
01423                                                      In.getOperand(1)));
01424           }
01425         }
01426         break;
01427       }
01428     }
01429     
01430     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01431     break;
01432   }
01433   case ISD::AssertZext: {
01434     EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
01435     APInt InMask = APInt::getLowBitsSet(BitWidth,
01436                                         VT.getSizeInBits());
01437     if (SimplifyDemandedBits(Op.getOperand(0), InMask & NewMask,
01438                              KnownZero, KnownOne, TLO, Depth+1))
01439       return true;
01440     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
01441     KnownZero |= ~InMask & NewMask;
01442     break;
01443   }
01444   case ISD::BIT_CONVERT:
01445 #if 0
01446     // If this is an FP->Int bitcast and if the sign bit is the only thing that
01447     // is demanded, turn this into a FGETSIGN.
01448     if (NewMask == EVT::getIntegerVTSignBit(Op.getValueType()) &&
01449         MVT::isFloatingPoint(Op.getOperand(0).getValueType()) &&
01450         !MVT::isVector(Op.getOperand(0).getValueType())) {
01451       // Only do this xform if FGETSIGN is valid or if before legalize.
01452       if (!TLO.AfterLegalize ||
01453           isOperationLegal(ISD::FGETSIGN, Op.getValueType())) {
01454         // Make a FGETSIGN + SHL to move the sign bit into the appropriate
01455         // place.  We expect the SHL to be eliminated by other optimizations.
01456         SDValue Sign = TLO.DAG.getNode(ISD::FGETSIGN, Op.getValueType(), 
01457                                          Op.getOperand(0));
01458         unsigned ShVal = Op.getValueType().getSizeInBits()-1;
01459         SDValue ShAmt = TLO.DAG.getConstant(ShVal, getShiftAmountTy());
01460         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, Op.getValueType(),
01461                                                  Sign, ShAmt));
01462       }
01463     }
01464 #endif
01465     break;
01466   case ISD::ADD:
01467   case ISD::MUL:
01468   case ISD::SUB: {
01469     // Add, Sub, and Mul don't demand any bits in positions beyond that
01470     // of the highest bit demanded of them.
01471     APInt LoMask = APInt::getLowBitsSet(BitWidth,
01472                                         BitWidth - NewMask.countLeadingZeros());
01473     if (SimplifyDemandedBits(Op.getOperand(0), LoMask, KnownZero2,
01474                              KnownOne2, TLO, Depth+1))
01475       return true;
01476     if (SimplifyDemandedBits(Op.getOperand(1), LoMask, KnownZero2,
01477                              KnownOne2, TLO, Depth+1))
01478       return true;
01479     // See if the operation should be performed at a smaller bit width.
01480     if (TLO.ShrinkDemandedOp(Op, BitWidth, NewMask, dl))
01481       return true;
01482   }
01483   // FALL THROUGH
01484   default:
01485     // Just use ComputeMaskedBits to compute output bits.
01486     TLO.DAG.ComputeMaskedBits(Op, NewMask, KnownZero, KnownOne, Depth);
01487     break;
01488   }
01489   
01490   // If we know the value of all of the demanded bits, return this as a
01491   // constant.
01492   if ((NewMask & (KnownZero|KnownOne)) == NewMask)
01493     return TLO.CombineTo(Op, TLO.DAG.getConstant(KnownOne, Op.getValueType()));
01494   
01495   return false;
01496 }
01497 
01498 /// computeMaskedBitsForTargetNode - Determine which of the bits specified 
01499 /// in Mask are known to be either zero or one and return them in the 
01500 /// KnownZero/KnownOne bitsets.
01501 void TargetLowering::computeMaskedBitsForTargetNode(const SDValue Op, 
01502                                                     const APInt &Mask,
01503                                                     APInt &KnownZero, 
01504                                                     APInt &KnownOne,
01505                                                     const SelectionDAG &DAG,
01506                                                     unsigned Depth) const {
01507   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
01508           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
01509           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
01510           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
01511          "Should use MaskedValueIsZero if you don't know whether Op"
01512          " is a target node!");
01513   KnownZero = KnownOne = APInt(Mask.getBitWidth(), 0);
01514 }
01515 
01516 /// ComputeNumSignBitsForTargetNode - This method can be implemented by
01517 /// targets that want to expose additional information about sign bits to the
01518 /// DAG Combiner.
01519 unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDValue Op,
01520                                                          unsigned Depth) const {
01521   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
01522           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
01523           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
01524           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
01525          "Should use ComputeNumSignBits if you don't know whether Op"
01526          " is a target node!");
01527   return 1;
01528 }
01529 
01530 /// ValueHasExactlyOneBitSet - Test if the given value is known to have exactly
01531 /// one bit set. This differs from ComputeMaskedBits in that it doesn't need to
01532 /// determine which bit is set.
01533 ///
01534 static bool ValueHasExactlyOneBitSet(SDValue Val, const SelectionDAG &DAG) {
01535   // A left-shift of a constant one will have exactly one bit set, because
01536   // shifting the bit off the end is undefined.
01537   if (Val.getOpcode() == ISD::SHL)
01538     if (ConstantSDNode *C =
01539          dyn_cast<ConstantSDNode>(Val.getNode()->getOperand(0)))
01540       if (C->getAPIntValue() == 1)
01541         return true;
01542 
01543   // Similarly, a right-shift of a constant sign-bit will have exactly
01544   // one bit set.
01545   if (Val.getOpcode() == ISD::SRL)
01546     if (ConstantSDNode *C =
01547          dyn_cast<ConstantSDNode>(Val.getNode()->getOperand(0)))
01548       if (C->getAPIntValue().isSignBit())
01549         return true;
01550 
01551   // More could be done here, though the above checks are enough
01552   // to handle some common cases.
01553 
01554   // Fall back to ComputeMaskedBits to catch other known cases.
01555   EVT OpVT = Val.getValueType();
01556   unsigned BitWidth = OpVT.getSizeInBits();
01557   APInt Mask = APInt::getAllOnesValue(BitWidth);
01558   APInt KnownZero, KnownOne;
01559   DAG.ComputeMaskedBits(Val, Mask, KnownZero, KnownOne);
01560   return (KnownZero.countPopulation() == BitWidth - 1) &&
01561          (KnownOne.countPopulation() == 1);
01562 }
01563 
01564 /// SimplifySetCC - Try to simplify a setcc built with the specified operands 
01565 /// and cc. If it is unable to simplify it, return a null SDValue.
01566 SDValue
01567 TargetLowering::SimplifySetCC(EVT VT, SDValue N0, SDValue N1,
01568                               ISD::CondCode Cond, bool foldBooleans,
01569                               DAGCombinerInfo &DCI, DebugLoc dl) const {
01570   SelectionDAG &DAG = DCI.DAG;
01571   LLVMContext &Context = *DAG.getContext();
01572 
01573   // These setcc operations always fold.
01574   switch (Cond) {
01575   default: break;
01576   case ISD::SETFALSE:
01577   case ISD::SETFALSE2: return DAG.getConstant(0, VT);
01578   case ISD::SETTRUE:
01579   case ISD::SETTRUE2:  return DAG.getConstant(1, VT);
01580   }
01581 
01582   if (isa<ConstantSDNode>(N0.getNode())) {
01583     // Ensure that the constant occurs on the RHS, and fold constant
01584     // comparisons.
01585     return DAG.getSetCC(dl, VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
01586   }
01587 
01588   if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
01589     const APInt &C1 = N1C->getAPIntValue();
01590 
01591     // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an
01592     // equality comparison, then we're just comparing whether X itself is
01593     // zero.
01594     if (N0.getOpcode() == ISD::SRL && (C1 == 0 || C1 == 1) &&
01595         N0.getOperand(0).getOpcode() == ISD::CTLZ &&
01596         N0.getOperand(1).getOpcode() == ISD::Constant) {
01597       unsigned ShAmt = cast<ConstantSDNode>(N0.getOperand(1))->getZExtValue();
01598       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
01599           ShAmt == Log2_32(N0.getValueType().getSizeInBits())) {
01600         if ((C1 == 0) == (Cond == ISD::SETEQ)) {
01601           // (srl (ctlz x), 5) == 0  -> X != 0
01602           // (srl (ctlz x), 5) != 1  -> X != 0
01603           Cond = ISD::SETNE;
01604         } else {
01605           // (srl (ctlz x), 5) != 0  -> X == 0
01606           // (srl (ctlz x), 5) == 1  -> X == 0
01607           Cond = ISD::SETEQ;
01608         }
01609         SDValue Zero = DAG.getConstant(0, N0.getValueType());
01610         return DAG.getSetCC(dl, VT, N0.getOperand(0).getOperand(0),
01611                             Zero, Cond);
01612       }
01613     }
01614 
01615     // If the LHS is '(and load, const)', the RHS is 0,
01616     // the test is for equality or unsigned, and all 1 bits of the const are
01617     // in the same partial word, see if we can shorten the load.
01618     if (DCI.isBeforeLegalize() &&
01619         N0.getOpcode() == ISD::AND && C1 == 0 &&
01620         N0.getNode()->hasOneUse() &&
01621         isa<LoadSDNode>(N0.getOperand(0)) &&
01622         N0.getOperand(0).getNode()->hasOneUse() &&
01623         isa<ConstantSDNode>(N0.getOperand(1))) {
01624       LoadSDNode *Lod = cast<LoadSDNode>(N0.getOperand(0));
01625       uint64_t bestMask = 0;
01626       unsigned bestWidth = 0, bestOffset = 0;
01627       if (!Lod->isVolatile() && Lod->isUnindexed() &&
01628           // FIXME: This uses getZExtValue() below so it only works on i64 and
01629           // below.
01630           N0.getValueType().getSizeInBits() <= 64) {
01631         unsigned origWidth = N0.getValueType().getSizeInBits();
01632         // We can narrow (e.g.) 16-bit extending loads on 32-bit target to 
01633         // 8 bits, but have to be careful...
01634         if (Lod->getExtensionType() != ISD::NON_EXTLOAD)
01635           origWidth = Lod->getMemoryVT().getSizeInBits();
01636         uint64_t Mask =cast<ConstantSDNode>(N0.getOperand(1))->getZExtValue();
01637         for (unsigned width = origWidth / 2; width>=8; width /= 2) {
01638           uint64_t newMask = (1ULL << width) - 1;
01639           for (unsigned offset=0; offset<origWidth/width; offset++) {
01640             if ((newMask & Mask) == Mask) {
01641               if (!TD->isLittleEndian())
01642                 bestOffset = (origWidth/width - offset - 1) * (width/8);
01643               else
01644                 bestOffset = (uint64_t)offset * (width/8);
01645               bestMask = Mask >> (offset * (width/8) * 8);
01646               bestWidth = width;
01647               break;
01648             }
01649             newMask = newMask << width;
01650           }
01651         }
01652       }
01653       if (bestWidth) {
01654         EVT newVT = EVT::getIntegerVT(Context, bestWidth);
01655         if (newVT.isRound()) {
01656           EVT PtrType = Lod->getOperand(1).getValueType();
01657           SDValue Ptr = Lod->getBasePtr();
01658           if (bestOffset != 0)
01659             Ptr = DAG.getNode(ISD::ADD, dl, PtrType, Lod->getBasePtr(),
01660                               DAG.getConstant(bestOffset, PtrType));
01661           unsigned NewAlign = MinAlign(Lod->getAlignment(), bestOffset);
01662           SDValue NewLoad = DAG.getLoad(newVT, dl, Lod->getChain(), Ptr,
01663                                         Lod->getSrcValue(), 
01664                                         Lod->getSrcValueOffset() + bestOffset,
01665                                         false, NewAlign);
01666           return DAG.getSetCC(dl, VT, 
01667                               DAG.getNode(ISD::AND, dl, newVT, NewLoad,
01668                                           DAG.getConstant(bestMask, newVT)),
01669                               DAG.getConstant(0LL, newVT), Cond);
01670         }
01671       }
01672     }
01673 
01674     // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
01675     if (N0.getOpcode() == ISD::ZERO_EXTEND) {
01676       unsigned InSize = N0.getOperand(0).getValueType().getSizeInBits();
01677 
01678       // If the comparison constant has bits in the upper part, the
01679       // zero-extended value could never match.
01680       if (C1.intersects(APInt::getHighBitsSet(C1.getBitWidth(),
01681                                               C1.getBitWidth() - InSize))) {
01682         switch (Cond) {
01683         case ISD::SETUGT:
01684         case ISD::SETUGE:
01685         case ISD::SETEQ: return DAG.getConstant(0, VT);
01686         case ISD::SETULT:
01687         case ISD::SETULE:
01688         case ISD::SETNE: return DAG.getConstant(1, VT);
01689         case ISD::SETGT:
01690         case ISD::SETGE:
01691           // True if the sign bit of C1 is set.
01692           return DAG.getConstant(C1.isNegative(), VT);
01693         case ISD::SETLT:
01694         case ISD::SETLE:
01695           // True if the sign bit of C1 isn't set.
01696           return DAG.getConstant(C1.isNonNegative(), VT);
01697         default:
01698           break;
01699         }
01700       }
01701 
01702       // Otherwise, we can perform the comparison with the low bits.
01703       switch (Cond) {
01704       case ISD::SETEQ:
01705       case ISD::SETNE:
01706       case ISD::SETUGT:
01707       case ISD::SETUGE:
01708       case ISD::SETULT:
01709       case ISD::SETULE: {
01710         EVT newVT = N0.getOperand(0).getValueType();
01711         if (DCI.isBeforeLegalizeOps() ||
01712             (isOperationLegal(ISD::SETCC, newVT) &&
01713               getCondCodeAction(Cond, newVT)==Legal))
01714           return DAG.getSetCC(dl, VT, N0.getOperand(0),
01715                               DAG.getConstant(APInt(C1).trunc(InSize), newVT),
01716                               Cond);
01717         break;
01718       }
01719       default:
01720         break;   // todo, be more careful with signed comparisons
01721       }
01722     } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
01723                 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
01724       EVT ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
01725       unsigned ExtSrcTyBits = ExtSrcTy.getSizeInBits();
01726       EVT ExtDstTy = N0.getValueType();
01727       unsigned ExtDstTyBits = ExtDstTy.getSizeInBits();
01728 
01729       // If the extended part has any inconsistent bits, it cannot ever
01730       // compare equal.  In other words, they have to be all ones or all
01731       // zeros.
01732       APInt ExtBits =
01733         APInt::getHighBitsSet(ExtDstTyBits, ExtDstTyBits - ExtSrcTyBits);
01734       if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits)
01735         return DAG.getConstant(Cond == ISD::SETNE, VT);
01736       
01737       SDValue ZextOp;
01738       EVT Op0Ty = N0.getOperand(0).getValueType();
01739       if (Op0Ty == ExtSrcTy) {
01740         ZextOp = N0.getOperand(0);
01741       } else {
01742         APInt Imm = APInt::getLowBitsSet(ExtDstTyBits, ExtSrcTyBits);
01743         ZextOp = DAG.getNode(ISD::AND, dl, Op0Ty, N0.getOperand(0),
01744                               DAG.getConstant(Imm, Op0Ty));
01745       }
01746       if (!DCI.isCalledByLegalizer())
01747         DCI.AddToWorklist(ZextOp.getNode());
01748       // Otherwise, make this a use of a zext.
01749       return DAG.getSetCC(dl, VT, ZextOp, 
01750                           DAG.getConstant(C1 & APInt::getLowBitsSet(
01751                                                               ExtDstTyBits,
01752                                                               ExtSrcTyBits), 
01753                                           ExtDstTy),
01754                           Cond);
01755     } else if ((N1C->isNullValue() || N1C->getAPIntValue() == 1) &&
01756                 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
01757       
01758       // SETCC (SETCC), [0|1], [EQ|NE]  -> SETCC
01759       if (N0.getOpcode() == ISD::SETCC) {
01760         bool TrueWhenTrue = (Cond == ISD::SETEQ) ^ (N1C->getZExtValue() != 1);
01761         if (TrueWhenTrue)
01762           return N0;
01763         
01764         // Invert the condition.
01765         ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get();
01766         CC = ISD::getSetCCInverse(CC, 
01767                                   N0.getOperand(0).getValueType().isInteger());
01768         return DAG.getSetCC(dl, VT, N0.getOperand(0), N0.getOperand(1), CC);
01769       }
01770       
01771       if ((N0.getOpcode() == ISD::XOR ||
01772             (N0.getOpcode() == ISD::AND && 
01773             N0.getOperand(0).getOpcode() == ISD::XOR &&
01774             N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
01775           isa<ConstantSDNode>(N0.getOperand(1)) &&
01776           cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue() == 1) {
01777         // If this is (X^1) == 0/1, swap the RHS and eliminate the xor.  We
01778         // can only do this if the top bits are known zero.
01779         unsigned BitWidth = N0.getValueSizeInBits();
01780         if (DAG.MaskedValueIsZero(N0,
01781                                   APInt::getHighBitsSet(BitWidth,
01782                                                         BitWidth-1))) {
01783           // Okay, get the un-inverted input value.
01784           SDValue Val;
01785           if (N0.getOpcode() == ISD::XOR)
01786             Val = N0.getOperand(0);
01787           else {
01788             assert(N0.getOpcode() == ISD::AND && 
01789                     N0.getOperand(0).getOpcode() == ISD::XOR);
01790             // ((X^1)&1)^1 -> X & 1
01791             Val = DAG.getNode(ISD::AND, dl, N0.getValueType(),
01792                               N0.getOperand(0).getOperand(0),
01793                               N0.getOperand(1));
01794           }
01795           return DAG.getSetCC(dl, VT, Val, N1,
01796                               Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
01797         }
01798       }
01799     }
01800     
01801     APInt MinVal, MaxVal;
01802     unsigned OperandBitSize = N1C->getValueType(0).getSizeInBits();
01803     if (ISD::isSignedIntSetCC(Cond)) {
01804       MinVal = APInt::getSignedMinValue(OperandBitSize);
01805       MaxVal = APInt::getSignedMaxValue(OperandBitSize);
01806     } else {
01807       MinVal = APInt::getMinValue(OperandBitSize);
01808       MaxVal = APInt::getMaxValue(OperandBitSize);
01809     }
01810 
01811     // Canonicalize GE/LE comparisons to use GT/LT comparisons.
01812     if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
01813       if (C1 == MinVal) return DAG.getConstant(1, VT);   // X >= MIN --> true
01814       // X >= C0 --> X > (C0-1)
01815       return DAG.getSetCC(dl, VT, N0, 
01816                           DAG.getConstant(C1-1, N1.getValueType()),
01817                           (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
01818     }
01819 
01820     if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
01821       if (C1 == MaxVal) return DAG.getConstant(1, VT);   // X <= MAX --> true
01822       // X <= C0 --> X < (C0+1)
01823       return DAG.getSetCC(dl, VT, N0, 
01824                           DAG.getConstant(C1+1, N1.getValueType()),
01825                           (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
01826     }
01827 
01828     if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
01829       return DAG.getConstant(0, VT);      // X < MIN --> false
01830     if ((Cond == ISD::SETGE || Cond == ISD::SETUGE) && C1 == MinVal)
01831       return DAG.getConstant(1, VT);      // X >= MIN --> true
01832     if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal)
01833       return DAG.getConstant(0, VT);      // X > MAX --> false
01834     if ((Cond == ISD::SETLE || Cond == ISD::SETULE) && C1 == MaxVal)
01835       return DAG.getConstant(1, VT);      // X <= MAX --> true
01836 
01837     // Canonicalize setgt X, Min --> setne X, Min
01838     if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal)
01839       return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
01840     // Canonicalize setlt X, Max --> setne X, Max
01841     if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal)
01842       return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
01843 
01844     // If we have setult X, 1, turn it into seteq X, 0
01845     if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1)
01846       return DAG.getSetCC(dl, VT, N0, 
01847                           DAG.getConstant(MinVal, N0.getValueType()), 
01848                           ISD::SETEQ);
01849     // If we have setugt X, Max-1, turn it into seteq X, Max
01850     else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1)
01851       return DAG.getSetCC(dl, VT, N0, 
01852                           DAG.getConstant(MaxVal, N0.getValueType()),
01853                           ISD::SETEQ);
01854 
01855     // If we have "setcc X, C0", check to see if we can shrink the immediate
01856     // by changing cc.
01857 
01858     // SETUGT X, SINTMAX  -> SETLT X, 0
01859     if (Cond == ISD::SETUGT && 
01860         C1 == APInt::getSignedMaxValue(OperandBitSize))
01861       return DAG.getSetCC(dl, VT, N0, 
01862                           DAG.getConstant(0, N1.getValueType()),
01863                           ISD::SETLT);
01864 
01865     // SETULT X, SINTMIN  -> SETGT X, -1
01866     if (Cond == ISD::SETULT &&
01867         C1 == APInt::getSignedMinValue(OperandBitSize)) {
01868       SDValue ConstMinusOne =
01869           DAG.getConstant(APInt::getAllOnesValue(OperandBitSize),
01870                           N1.getValueType());
01871       return DAG.getSetCC(dl, VT, N0, ConstMinusOne, ISD::SETGT);
01872     }
01873 
01874     // Fold bit comparisons when we can.
01875     if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
01876         VT == N0.getValueType() && N0.getOpcode() == ISD::AND)
01877       if (ConstantSDNode *AndRHS =
01878                   dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
01879         EVT ShiftTy = DCI.isBeforeLegalize() ?
01880           getPointerTy() : getShiftAmountTy();
01881         if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
01882           // Perform the xform if the AND RHS is a single bit.
01883           if (isPowerOf2_64(AndRHS->getZExtValue())) {
01884             return DAG.getNode(ISD::SRL, dl, VT, N0,
01885                                 DAG.getConstant(Log2_64(AndRHS->getZExtValue()),
01886                                                 ShiftTy));
01887           }
01888         } else if (Cond == ISD::SETEQ && C1 == AndRHS->getZExtValue()) {
01889           // (X & 8) == 8  -->  (X & 8) >> 3
01890           // Perform the xform if C1 is a single bit.
01891           if (C1.isPowerOf2()) {
01892             return DAG.getNode(ISD::SRL, dl, VT, N0,
01893                                 DAG.getConstant(C1.logBase2(), ShiftTy));
01894           }
01895         }
01896       }
01897   }
01898 
01899   if (isa<ConstantFPSDNode>(N0.getNode())) {
01900     // Constant fold or commute setcc.
01901     SDValue O = DAG.FoldSetCC(VT, N0, N1, Cond, dl);
01902     if (O.getNode()) return O;
01903   } else if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
01904     // If the RHS of an FP comparison is a constant, simplify it away in
01905     // some cases.
01906     if (CFP->getValueAPF().isNaN()) {
01907       // If an operand is known to be a nan, we can fold it.
01908       switch (ISD::getUnorderedFlavor(Cond)) {
01909       default: llvm_unreachable("Unknown flavor!");
01910       case 0:  // Known false.
01911         return DAG.getConstant(0, VT);
01912       case 1:  // Known true.
01913         return DAG.getConstant(1, VT);
01914       case 2:  // Undefined.
01915         return DAG.getUNDEF(VT);
01916       }
01917     }
01918     
01919     // Otherwise, we know the RHS is not a NaN.  Simplify the node to drop the
01920     // constant if knowing that the operand is non-nan is enough.  We prefer to
01921     // have SETO(x,x) instead of SETO(x, 0.0) because this avoids having to
01922     // materialize 0.0.
01923     if (Cond == ISD::SETO || Cond == ISD::SETUO)
01924       return DAG.getSetCC(dl, VT, N0, N0, Cond);
01925   }
01926 
01927   if (N0 == N1) {
01928     // We can always fold X == X for integer setcc's.
01929     if (N0.getValueType().isInteger())
01930       return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
01931     unsigned UOF = ISD::getUnorderedFlavor(Cond);
01932     if (UOF == 2)   // FP operators that are undefined on NaNs.
01933       return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
01934     if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
01935       return DAG.getConstant(UOF, VT);
01936     // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
01937     // if it is not already.
01938     ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO;
01939     if (NewCond != Cond)
01940       return DAG.getSetCC(dl, VT, N0, N1, NewCond);
01941   }
01942 
01943   if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
01944       N0.getValueType().isInteger()) {
01945     if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
01946         N0.getOpcode() == ISD::XOR) {
01947       // Simplify (X+Y) == (X+Z) -->  Y == Z
01948       if (N0.getOpcode() == N1.getOpcode()) {
01949         if (N0.getOperand(0) == N1.getOperand(0))
01950           return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(1), Cond);
01951         if (N0.getOperand(1) == N1.getOperand(1))
01952           return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(0), Cond);
01953         if (DAG.isCommutativeBinOp(N0.getOpcode())) {
01954           // If X op Y == Y op X, try other combinations.
01955           if (N0.getOperand(0) == N1.getOperand(1))
01956             return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(0), 
01957                                 Cond);
01958           if (N0.getOperand(1) == N1.getOperand(0))
01959             return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(1), 
01960                                 Cond);
01961         }
01962       }
01963       
01964       if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) {
01965         if (ConstantSDNode *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
01966           // Turn (X+C1) == C2 --> X == C2-C1
01967           if (N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse()) {
01968             return DAG.getSetCC(dl, VT, N0.getOperand(0),
01969                                 DAG.getConstant(RHSC->getAPIntValue()-
01970                                                 LHSR->getAPIntValue(),
01971                                 N0.getValueType()), Cond);
01972           }
01973           
01974           // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.
01975           if (N0.getOpcode() == ISD::XOR)
01976             // If we know that all of the inverted bits are zero, don't bother
01977             // performing the inversion.
01978             if (DAG.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getAPIntValue()))
01979               return
01980                 DAG.getSetCC(dl, VT, N0.getOperand(0),
01981                              DAG.getConstant(LHSR->getAPIntValue() ^
01982                                                RHSC->getAPIntValue(),
01983                                              N0.getValueType()),
01984                              Cond);
01985         }
01986         
01987         // Turn (C1-X) == C2 --> X == C1-C2
01988         if (ConstantSDNode *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) {
01989           if (N0.getOpcode() == ISD::SUB && N0.getNode()->hasOneUse()) {
01990             return
01991               DAG.getSetCC(dl, VT, N0.getOperand(1),
01992                            DAG.getConstant(SUBC->getAPIntValue() -
01993                                              RHSC->getAPIntValue(),
01994                                            N0.getValueType()),
01995                            Cond);
01996           }
01997         }          
01998       }
01999 
02000       // Simplify (X+Z) == X -->  Z == 0
02001       if (N0.getOperand(0) == N1)
02002         return DAG.getSetCC(dl, VT, N0.getOperand(1),
02003                         DAG.getConstant(0, N0.getValueType()), Cond);
02004       if (N0.getOperand(1) == N1) {
02005         if (DAG.isCommutativeBinOp(N0.getOpcode()))
02006           return DAG.getSetCC(dl, VT, N0.getOperand(0),
02007                           DAG.getConstant(0, N0.getValueType()), Cond);
02008         else if (N0.getNode()->hasOneUse()) {
02009           assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
02010           // (Z-X) == X  --> Z == X<<1
02011           SDValue SH = DAG.getNode(ISD::SHL, dl, N1.getValueType(),
02012                                      N1, 
02013                                      DAG.getConstant(1, getShiftAmountTy()));
02014           if (!DCI.isCalledByLegalizer())
02015             DCI.AddToWorklist(SH.getNode());
02016           return DAG.getSetCC(dl, VT, N0.getOperand(0), SH, Cond);
02017         }
02018       }
02019     }
02020 
02021     if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
02022         N1.getOpcode() == ISD::XOR) {
02023       // Simplify  X == (X+Z) -->  Z == 0
02024       if (N1.getOperand(0) == N0) {
02025         return DAG.getSetCC(dl, VT, N1.getOperand(1),
02026                         DAG.getConstant(0, N1.getValueType()), Cond);
02027       } else if (N1.getOperand(1) == N0) {
02028         if (DAG.isCommutativeBinOp(N1.getOpcode())) {
02029           return DAG.getSetCC(dl, VT, N1.getOperand(0),
02030                           DAG.getConstant(0, N1.getValueType()), Cond);
02031         } else if (N1.getNode()->hasOneUse()) {
02032           assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
02033           // X == (Z-X)  --> X<<1 == Z
02034           SDValue SH = DAG.getNode(ISD::SHL, dl, N1.getValueType(), N0, 
02035                                      DAG.getConstant(1, getShiftAmountTy()));
02036           if (!DCI.isCalledByLegalizer())
02037             DCI.AddToWorklist(SH.getNode());
02038           return DAG.getSetCC(dl, VT, SH, N1.getOperand(0), Cond);
02039         }
02040       }
02041     }
02042 
02043     // Simplify x&y == y to x&y != 0 if y has exactly one bit set.
02044     // Note that where y is variable and is known to have at most
02045     // one bit set (for example, if it is z&1) we cannot do this;
02046     // the expressions are not equivalent when y==0.
02047     if (N0.getOpcode() == ISD::AND)
02048       if (N0.getOperand(0) == N1 || N0.getOperand(1) == N1) {
02049         if (ValueHasExactlyOneBitSet(N1, DAG)) {
02050           Cond = ISD::getSetCCInverse(Cond, /*isInteger=*/true);
02051           SDValue Zero = DAG.getConstant(0, N1.getValueType());
02052           return DAG.getSetCC(dl, VT, N0, Zero, Cond);
02053         }
02054       }
02055     if (N1.getOpcode() == ISD::AND)
02056       if (N1.getOperand(0) == N0 || N1.getOperand(1) == N0) {
02057         if (ValueHasExactlyOneBitSet(N0, DAG)) {
02058           Cond = ISD::getSetCCInverse(Cond, /*isInteger=*/true);
02059           SDValue Zero = DAG.getConstant(0, N0.getValueType());
02060           return DAG.getSetCC(dl, VT, N1, Zero, Cond);
02061         }
02062       }
02063   }
02064 
02065   // Fold away ALL boolean setcc's.
02066   SDValue Temp;
02067   if (N0.getValueType() == MVT::i1 && foldBooleans) {
02068     switch (Cond) {
02069     default: llvm_unreachable("Unknown integer setcc!");
02070     case ISD::SETEQ:  // X == Y  -> ~(X^Y)
02071       Temp = DAG.getNode(ISD::XOR, dl, MVT::i1, N0, N1);
02072       N0 = DAG.getNOT(dl, Temp, MVT::i1);
02073       if (!DCI.isCalledByLegalizer())
02074         DCI.AddToWorklist(Temp.getNode());
02075       break;
02076     case ISD::SETNE:  // X != Y   -->  (X^Y)
02077       N0 = DAG.getNode(ISD::XOR, dl, MVT::i1, N0, N1);
02078       break;
02079     case ISD::SETGT:  // X >s Y   -->  X == 0 & Y == 1  -->  ~X & Y
02080     case ISD::SETULT: // X <u Y   -->  X == 0 & Y == 1  -->  ~X & Y
02081       Temp = DAG.getNOT(dl, N0, MVT::i1);
02082       N0 = DAG.getNode(ISD::AND, dl, MVT::i1, N1, Temp);
02083       if (!DCI.isCalledByLegalizer())
02084         DCI.AddToWorklist(Temp.getNode());
02085       break;
02086     case ISD::SETLT:  // X <s Y   --> X == 1 & Y == 0  -->  ~Y & X
02087     case ISD::SETUGT: // X >u Y   --> X == 1 & Y == 0  -->  ~Y & X
02088       Temp = DAG.getNOT(dl, N1, MVT::i1);
02089       N0 = DAG.getNode(ISD::AND, dl, MVT::i1, N0, Temp);
02090       if (!DCI.isCalledByLegalizer())
02091         DCI.AddToWorklist(Temp.getNode());
02092       break;
02093     case ISD::SETULE: // X <=u Y  --> X == 0 | Y == 1  -->  ~X | Y
02094     case ISD::SETGE:  // X >=s Y  --> X == 0 | Y == 1  -->  ~X | Y
02095       Temp = DAG.getNOT(dl, N0, MVT::i1);
02096       N0 = DAG.getNode(ISD::OR, dl, MVT::i1, N1, Temp);
02097       if (!DCI.isCalledByLegalizer())
02098         DCI.AddToWorklist(Temp.getNode());
02099       break;
02100     case ISD::SETUGE: // X >=u Y  --> X == 1 | Y == 0  -->  ~Y | X
02101     case ISD::SETLE:  // X <=s Y  --> X == 1 | Y == 0  -->  ~Y | X
02102       Temp = DAG.getNOT(dl, N1, MVT::i1);
02103       N0 = DAG.getNode(ISD::OR, dl, MVT::i1, N0, Temp);
02104       break;
02105     }
02106     if (VT != MVT::i1) {
02107       if (!DCI.isCalledByLegalizer())
02108         DCI.AddToWorklist(N0.getNode());
02109       // FIXME: If running after legalize, we probably can't do this.
02110       N0 = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, N0);
02111     }
02112     return N0;
02113   }
02114 
02115   // Could not fold it.
02116   return SDValue();
02117 }
02118 
02119 /// isGAPlusOffset - Returns true (and the GlobalValue and the offset) if the
02120 /// node is a GlobalAddress + offset.
02121 bool TargetLowering::isGAPlusOffset(SDNode *N, GlobalValue* &GA,
02122                                     int64_t &Offset) const {
02123   if (isa<GlobalAddressSDNode>(N)) {
02124     GlobalAddressSDNode *GASD = cast<GlobalAddressSDNode>(N);
02125     GA = GASD->getGlobal();
02126     Offset += GASD->getOffset();
02127     return true;
02128   }
02129 
02130   if (N->getOpcode() == ISD::ADD) {
02131     SDValue N1 = N->getOperand(0);
02132     SDValue N2 = N->getOperand(1);
02133     if (isGAPlusOffset(N1.getNode(), GA, Offset)) {
02134       ConstantSDNode *V = dyn_cast<ConstantSDNode>(N2);
02135       if (V) {
02136         Offset += V->getSExtValue();
02137         return true;
02138       }
02139     } else if (isGAPlusOffset(N2.getNode(), GA, Offset)) {
02140       ConstantSDNode *V = dyn_cast<ConstantSDNode>(N1);
02141       if (V) {
02142         Offset += V->getSExtValue();
02143         return true;
02144       }
02145     }
02146   }
02147   return false;
02148 }
02149 
02150 
02151 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a 
02152 /// location that is 'Dist' units away from the location that the 'Base' load 
02153 /// is loading from.
02154 bool TargetLowering::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base, 
02155                                        unsigned Bytes, int Dist, 
02156                                        const MachineFrameInfo *MFI) const {
02157   if (LD->getChain() != Base->getChain())
02158     return false;
02159   EVT VT = LD->getValueType(0);
02160   if (VT.getSizeInBits() / 8 != Bytes)
02161     return false;
02162 
02163   SDValue Loc = LD->getOperand(1);
02164   SDValue BaseLoc = Base->getOperand(1);
02165   if (Loc.getOpcode() == ISD::FrameIndex) {
02166     if (BaseLoc.getOpcode() != ISD::FrameIndex)
02167       return false;
02168     int FI  = cast<FrameIndexSDNode>(Loc)->getIndex();
02169     int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
02170     int FS  = MFI->getObjectSize(FI);
02171     int BFS = MFI->getObjectSize(BFI);
02172     if (FS != BFS || FS != (int)Bytes) return false;
02173     return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
02174   }
02175   if (Loc.getOpcode() == ISD::ADD && Loc.getOperand(0) == BaseLoc) {
02176     ConstantSDNode *V = dyn_cast<ConstantSDNode>(Loc.getOperand(1));
02177     if (V && (V->getSExtValue() == Dist*Bytes))
02178       return true;
02179   }
02180 
02181   GlobalValue *GV1 = NULL;
02182   GlobalValue *GV2 = NULL;
02183   int64_t Offset1 = 0;
02184   int64_t Offset2 = 0;
02185   bool isGA1 = isGAPlusOffset(Loc.getNode(), GV1, Offset1);
02186   bool isGA2 = isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
02187   if (isGA1 && isGA2 && GV1 == GV2)
02188     return Offset1 == (Offset2 + Dist*Bytes);
02189   return false;
02190 }
02191 
02192 
02193 SDValue TargetLowering::
02194 PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
02195   // Default implementation: no optimization.
02196   return SDValue();
02197 }
02198 
02199 //===----------------------------------------------------------------------===//
02200 //  Inline Assembler Implementation Methods
02201 //===----------------------------------------------------------------------===//
02202 
02203 
02204 TargetLowering::ConstraintType
02205 TargetLowering::getConstraintType(const std::string &Constraint) const {
02206   // FIXME: lots more standard ones to handle.
02207   if (Constraint.size() == 1) {
02208     switch (Constraint[0]) {
02209     default: break;
02210     case 'r': return C_RegisterClass;
02211     case 'm':    // memory
02212     case 'o':    // offsetable
02213     case 'V':    // not offsetable
02214       return C_Memory;
02215     case 'i':    // Simple Integer or Relocatable Constant
02216     case 'n':    // Simple Integer
02217     case 's':    // Relocatable Constant
02218     case 'X':    // Allow ANY value.
02219     case 'I':    // Target registers.
02220     case 'J':
02221     case 'K':
02222     case 'L':
02223     case 'M':
02224     case 'N':
02225     case 'O':
02226     case 'P':
02227       return C_Other;
02228     }
02229   }
02230   
02231   if (Constraint.size() > 1 && Constraint[0] == '{' && 
02232       Constraint[Constraint.size()-1] == '}')
02233     return C_Register;
02234   return C_Unknown;
02235 }
02236 
02237 /// LowerXConstraint - try to replace an X constraint, which matches anything,
02238 /// with another that has more specific requirements based on the type of the
02239 /// corresponding operand.
02240 const char *TargetLowering::LowerXConstraint(EVT ConstraintVT) const{
02241   if (ConstraintVT.isInteger())
02242     return "r";
02243   if (ConstraintVT.isFloatingPoint())
02244     return "f";      // works for many targets
02245   return 0;
02246 }
02247 
02248 /// LowerAsmOperandForConstraint - Lower the specified operand into the Ops
02249 /// vector.  If it is invalid, don't add anything to Ops.
02250 void TargetLowering::LowerAsmOperandForConstraint(SDValue Op,
02251                                                   char ConstraintLetter,
02252                                                   bool hasMemory,
02253                                                   std::vector<SDValue> &Ops,
02254                                                   SelectionDAG &DAG) const {
02255   switch (ConstraintLetter) {
02256   default: break;
02257   case 'X':     // Allows any operand; labels (basic block) use this.
02258     if (Op.getOpcode() == ISD::BasicBlock) {
02259       Ops.push_back(Op);
02260       return;
02261     }
02262     // fall through
02263   case 'i':    // Simple Integer or Relocatable Constant
02264   case 'n':    // Simple Integer
02265   case 's': {  // Relocatable Constant
02266     // These operands are interested in values of the form (GV+C), where C may
02267     // be folded in as an offset of GV, or it may be explicitly added.  Also, it
02268     // is possible and fine if either GV or C are missing.
02269     ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op);
02270     GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
02271     
02272     // If we have "(add GV, C)", pull out GV/C
02273     if (Op.getOpcode() == ISD::ADD) {
02274       C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
02275       GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(0));
02276       if (C == 0 || GA == 0) {
02277         C = dyn_cast<ConstantSDNode>(Op.getOperand(0));
02278         GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(1));
02279       }
02280       if (C == 0 || GA == 0)
02281         C = 0, GA = 0;
02282     }
02283     
02284     // If we find a valid operand, map to the TargetXXX version so that the
02285     // value itself doesn't get selected.
02286     if (GA) {   // Either &GV   or   &GV+C
02287       if (ConstraintLetter != 'n') {
02288         int64_t Offs = GA->getOffset();
02289         if (C) Offs += C->getZExtValue();
02290         Ops.push_back(DAG.getTargetGlobalAddress(GA->getGlobal(),
02291                                                  Op.getValueType(), Offs));
02292         return;
02293       }
02294     }
02295     if (C) {   // just C, no GV.
02296       // Simple constants are not allowed for 's'.
02297       if (ConstraintLetter != 's') {
02298         // gcc prints these as sign extended.  Sign extend value to 64 bits
02299         // now; without this it would get ZExt'd later in
02300         // ScheduleDAGSDNodes::EmitNode, which is very generic.
02301         Ops.push_back(DAG.getTargetConstant(C->getAPIntValue().getSExtValue(),
02302                                             MVT::i64));
02303         return;
02304       }
02305     }
02306     break;
02307   }
02308   }
02309 }
02310 
02311 std::vector<unsigned> TargetLowering::
02312 getRegClassForInlineAsmConstraint(const std::string &Constraint,
02313                                   EVT VT) const {
02314   return std::vector<unsigned>();
02315 }
02316 
02317 
02318 std::pair<unsigned, const TargetRegisterClass*> TargetLowering::
02319 getRegForInlineAsmConstraint(const std::string &Constraint,
02320                              EVT VT) const {
02321   if (Constraint[0] != '{')
02322     return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
02323   assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
02324 
02325   // Remove the braces from around the name.
02326   std::string RegName(Constraint.begin()+1, Constraint.end()-1);
02327 
02328   // Figure out which register class contains this reg.
02329   const TargetRegisterInfo *RI = TM.getRegisterInfo();
02330   for (TargetRegisterInfo::regclass_iterator RCI = RI->regclass_begin(),
02331        E = RI->regclass_end(); RCI != E; ++RCI) {
02332     const TargetRegisterClass *RC = *RCI;
02333     
02334     // If none of the the value types for this register class are valid, we 
02335     // can't use it.  For example, 64-bit reg classes on 32-bit targets.
02336     bool isLegal = false;
02337     for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
02338          I != E; ++I) {
02339       if (isTypeLegal(*I)) {
02340         isLegal = true;
02341         break;
02342       }
02343     }
02344     
02345     if (!isLegal) continue;
02346     
02347     for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 
02348          I != E; ++I) {
02349       if (StringsEqualNoCase(RegName, RI->get(*I).AsmName))
02350         return std::make_pair(*I, RC);
02351     }
02352   }
02353   
02354   return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
02355 }
02356 
02357 //===----------------------------------------------------------------------===//
02358 // Constraint Selection.
02359 
02360 /// isMatchingInputConstraint - Return true of this is an input operand that is
02361 /// a matching constraint like "4".
02362 bool TargetLowering::AsmOperandInfo::isMatchingInputConstraint() const {
02363   assert(!ConstraintCode.empty() && "No known constraint!");
02364   return isdigit(ConstraintCode[0]);
02365 }
02366 
02367 /// getMatchedOperand - If this is an input matching constraint, this method
02368 /// returns the output operand it matches.
02369 unsigned TargetLowering::AsmOperandInfo::getMatchedOperand() const {
02370   assert(!ConstraintCode.empty() && "No known constraint!");
02371   return atoi(ConstraintCode.c_str());
02372 }
02373 
02374 
02375 /// getConstraintGenerality - Return an integer indicating how general CT
02376 /// is.
02377 static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
02378   switch (CT) {
02379   default: llvm_unreachable("Unknown constraint type!");
02380   case TargetLowering::C_Other:
02381   case TargetLowering::C_Unknown:
02382     return 0;
02383   case TargetLowering::C_Register:
02384     return 1;
02385   case TargetLowering::C_RegisterClass:
02386     return 2;
02387   case TargetLowering::C_Memory:
02388     return 3;
02389   }
02390 }
02391 
02392 /// ChooseConstraint - If there are multiple different constraints that we
02393 /// could pick for this operand (e.g. "imr") try to pick the 'best' one.
02394 /// This is somewhat tricky: constraints fall into four classes:
02395 ///    Other         -> immediates and magic values
02396 ///    Register      -> one specific register
02397 ///    RegisterClass -> a group of regs
02398 ///    Memory        -> memory
02399 /// Ideally, we would pick the most specific constraint possible: if we have
02400 /// something that fits into a register, we would pick it.  The problem here
02401 /// is that if we have something that could either be in a register or in
02402 /// memory that use of the register could cause selection of *other*
02403 /// operands to fail: they might only succeed if we pick memory.  Because of
02404 /// this the heuristic we use is:
02405 ///
02406 ///  1) If there is an 'other' constraint, and if the operand is valid for
02407 ///     that constraint, use it.  This makes us take advantage of 'i'
02408 ///     constraints when available.
02409 ///  2) Otherwise, pick the most general constraint present.  This prefers
02410 ///     'm' over 'r', for example.
02411 ///
02412 static void ChooseConstraint(TargetLowering::AsmOperandInfo &OpInfo,
02413                              bool hasMemory,  const TargetLowering &TLI,
02414                              SDValue Op, SelectionDAG *DAG) {
02415   assert(OpInfo.Codes.size() > 1 && "Doesn't have multiple constraint options");
02416   unsigned BestIdx = 0;
02417   TargetLowering::ConstraintType BestType = TargetLowering::C_Unknown;
02418   int BestGenerality = -1;
02419   
02420   // Loop over the options, keeping track of the most general one.
02421   for (unsigned i = 0, e = OpInfo.Codes.size(); i != e; ++i) {
02422     TargetLowering::ConstraintType CType =
02423       TLI.getConstraintType(OpInfo.Codes[i]);
02424     
02425     // If this is an 'other' constraint, see if the operand is valid for it.
02426     // For example, on X86 we might have an 'rI' constraint.  If the operand
02427     // is an integer in the range [0..31] we want to use I (saving a load
02428     // of a register), otherwise we must use 'r'.
02429     if (CType == TargetLowering::C_Other && Op.getNode()) {
02430       assert(OpInfo.Codes[i].size() == 1 &&
02431              "Unhandled multi-letter 'other' constraint");
02432       std::vector<SDValue> ResultOps;
02433       TLI.LowerAsmOperandForConstraint(Op, OpInfo.Codes[i][0], hasMemory,
02434                                        ResultOps, *DAG);
02435       if (!ResultOps.empty()) {
02436         BestType = CType;
02437         BestIdx = i;
02438         break;
02439       }
02440     }
02441     
02442     // This constraint letter is more general than the previous one, use it.
02443     int Generality = getConstraintGenerality(CType);
02444     if (Generality > BestGenerality) {
02445       BestType = CType;
02446       BestIdx = i;
02447       BestGenerality = Generality;
02448     }
02449   }
02450   
02451   OpInfo.ConstraintCode = OpInfo.Codes[BestIdx];
02452   OpInfo.ConstraintType = BestType;
02453 }
02454 
02455 /// ComputeConstraintToUse - Determines the constraint code and constraint
02456 /// type to use for the specific AsmOperandInfo, setting
02457 /// OpInfo.ConstraintCode and OpInfo.ConstraintType.
02458 void TargetLowering::ComputeConstraintToUse(AsmOperandInfo &OpInfo,
02459                                             SDValue Op, 
02460                                             bool hasMemory,
02461                                             SelectionDAG *DAG) const {
02462   assert(!OpInfo.Codes.empty() && "Must have at least one constraint");
02463   
02464   // Single-letter constraints ('r') are very common.
02465   if (OpInfo.Codes.size() == 1) {
02466     OpInfo.ConstraintCode = OpInfo.Codes[0];
02467     OpInfo.ConstraintType = getConstraintType(OpInfo.ConstraintCode);
02468   } else {
02469     ChooseConstraint(OpInfo, hasMemory, *this, Op, DAG);
02470   }
02471   
02472   // 'X' matches anything.
02473   if (OpInfo.ConstraintCode == "X" && OpInfo.CallOperandVal) {
02474     // Labels and constants are handled elsewhere ('X' is the only thing
02475     // that matches labels).  For Functions, the type here is the type of
02476     // the result, which is not what we want to look at; leave them alone.
02477     Value *v = OpInfo.CallOperandVal;
02478     if (isa<BasicBlock>(v) || isa<ConstantInt>(v) || isa<Function>(v)) {
02479       OpInfo.CallOperandVal = v;
02480       return;
02481     }
02482     
02483     // Otherwise, try to resolve it to something we know about by looking at
02484     // the actual operand type.
02485     if (const char *Repl = LowerXConstraint(OpInfo.ConstraintVT)) {
02486       OpInfo.ConstraintCode = Repl;
02487       OpInfo.ConstraintType = getConstraintType(OpInfo.ConstraintCode);
02488     }
02489   }
02490 }
02491 
02492 //===----------------------------------------------------------------------===//
02493 //  Loop Strength Reduction hooks
02494 //===----------------------------------------------------------------------===//
02495 
02496 /// isLegalAddressingMode - Return true if the addressing mode represented
02497 /// by AM is legal for this target, for a load/store of the specified type.
02498 bool TargetLowering::isLegalAddressingMode(const AddrMode &AM, 
02499                                            const Type *Ty) const {
02500   // The default implementation of this implements a conservative RISCy, r+r and
02501   // r+i addr mode.
02502 
02503   // Allows a sign-extended 16-bit immediate field.
02504   if (AM.BaseOffs <= -(1LL << 16) || AM.BaseOffs >= (1LL << 16)-1)
02505     return false;
02506   
02507   // No global is ever allowed as a base.
02508   if (AM.BaseGV)
02509     return false;
02510   
02511   // Only support r+r, 
02512   switch (AM.Scale) {
02513   case 0:  // "r+i" or just "i", depending on HasBaseReg.
02514     break;
02515   case 1:
02516     if (AM.HasBaseReg && AM.BaseOffs)  // "r+r+i" is not allowed.
02517       return false;
02518     // Otherwise we have r+r or r+i.
02519     break;
02520   case 2:
02521     if (AM.HasBaseReg || AM.BaseOffs)  // 2*r+r  or  2*r+i is not allowed.
02522       return false;
02523     // Allow 2*r as r+r.
02524     break;
02525   }
02526   
02527   return true;
02528 }
02529 
02530 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
02531 /// return a DAG expression to select that will generate the same value by
02532 /// multiplying by a magic number.  See:
02533 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
02534 SDValue TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG, 
02535                                   std::vector<SDNode*>* Created) const {
02536   EVT VT = N->getValueType(0);
02537   DebugLoc dl= N->getDebugLoc();
02538   
02539   // Check to see if we can do this.
02540   // FIXME: We should be more aggressive here.
02541   if (!isTypeLegal(VT))
02542     return SDValue();
02543   
02544   APInt d = cast<ConstantSDNode>(N->getOperand(1))->getAPIntValue();
02545   APInt::ms magics = d.magic();
02546   
02547   // Multiply the numerator (operand 0) by the magic value
02548   // FIXME: We should support doing a MUL in a wider type
02549   SDValue Q;
02550   if (isOperationLegalOrCustom(ISD::MULHS, VT))
02551     Q = DAG.getNode(ISD::MULHS, dl, VT, N->getOperand(0),
02552                     DAG.getConstant(magics.m, VT));
02553   else if (isOperationLegalOrCustom(ISD::SMUL_LOHI, VT))
02554     Q = SDValue(DAG.getNode(ISD::SMUL_LOHI, dl, DAG.getVTList(VT, VT),
02555                               N->getOperand(0),
02556                               DAG.getConstant(magics.m, VT)).getNode(), 1);
02557   else
02558     return SDValue();       // No mulhs or equvialent
02559   // If d > 0 and m < 0, add the numerator
02560   if (d.isStrictlyPositive() && magics.m.isNegative()) { 
02561     Q = DAG.getNode(ISD::ADD, dl, VT, Q, N->getOperand(0));
02562     if (Created)
02563       Created->push_back(Q.getNode());
02564   }
02565   // If d < 0 and m > 0, subtract the numerator.
02566   if (d.isNegative() && magics.m.isStrictlyPositive()) {
02567     Q = DAG.getNode(ISD::SUB, dl, VT, Q, N->getOperand(0));
02568     if (Created)
02569       Created->push_back(Q.getNode());
02570   }
02571   // Shift right algebraic if shift value is nonzero
02572   if (magics.s > 0) {
02573     Q = DAG.getNode(ISD::SRA, dl, VT, Q, 
02574                     DAG.getConstant(magics.s, getShiftAmountTy()));
02575     if (Created)
02576       Created->push_back(Q.getNode());
02577   }
02578   // Extract the sign bit and add it to the quotient
02579   SDValue T =
02580     DAG.getNode(ISD::SRL, dl, VT, Q, DAG.getConstant(VT.getSizeInBits()-1,
02581                                                  getShiftAmountTy()));
02582   if (Created)
02583     Created->push_back(T.getNode());
02584   return DAG.getNode(ISD::ADD, dl, VT, Q, T);
02585 }
02586 
02587 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
02588 /// return a DAG expression to select that will generate the same value by
02589 /// multiplying by a magic number.  See:
02590 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
02591 SDValue TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
02592                                   std::vector<SDNode*>* Created) const {
02593   EVT VT = N->getValueType(0);
02594   DebugLoc dl = N->getDebugLoc();
02595 
02596   // Check to see if we can do this.
02597   // FIXME: We should be more aggressive here.
02598   if (!isTypeLegal(VT))
02599     return SDValue();
02600 
02601   // FIXME: We should use a narrower constant when the upper
02602   // bits are known to be zero.
02603   ConstantSDNode *N1C = cast<ConstantSDNode>(N->getOperand(1));
02604   APInt::mu magics = N1C->getAPIntValue().magicu();
02605 
02606   // Multiply the numerator (operand 0) by the magic value
02607   // FIXME: We should support doing a MUL in a wider type
02608   SDValue Q;
02609   if (isOperationLegalOrCustom(ISD::MULHU, VT))
02610     Q = DAG.getNode(ISD::MULHU, dl, VT, N->getOperand(0),
02611                     DAG.getConstant(magics.m, VT));
02612   else if (isOperationLegalOrCustom(ISD::UMUL_LOHI, VT))
02613     Q = SDValue(DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(VT, VT),
02614                               N->getOperand(0),
02615                               DAG.getConstant(magics.m, VT)).getNode(), 1);
02616   else
02617     return SDValue();       // No mulhu or equvialent
02618   if (Created)
02619     Created->push_back(Q.getNode());
02620 
02621   if (magics.a == 0) {
02622     assert(magics.s < N1C->getAPIntValue().getBitWidth() &&
02623            "We shouldn't generate an undefined shift!");
02624     return DAG.getNode(ISD::SRL, dl, VT, Q, 
02625                        DAG.getConstant(magics.s, getShiftAmountTy()));
02626   } else {
02627     SDValue NPQ = DAG.getNode(ISD::SUB, dl, VT, N->getOperand(0), Q);
02628     if (Created)
02629       Created->push_back(NPQ.getNode());
02630     NPQ = DAG.getNode(ISD::SRL, dl, VT, NPQ, 
02631                       DAG.getConstant(1, getShiftAmountTy()));
02632     if (Created)
02633       Created->push_back(NPQ.getNode());
02634     NPQ = DAG.getNode(ISD::ADD, dl, VT, NPQ, Q);
02635     if (Created)
02636       Created->push_back(NPQ.getNode());
02637     return DAG.getNode(ISD::SRL, dl, VT, NPQ, 
02638                        DAG.getConstant(magics.s-1, getShiftAmountTy()));
02639   }
02640 }