TargetLowering.cpp revision 2bb1e3eede14dd8a965506465e2876fb1ae765c2
1//===-- TargetLowering.cpp - Implement the TargetLowering class -----------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This implements the TargetLowering class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/Target/TargetAsmInfo.h" 15#include "llvm/Target/TargetLowering.h" 16#include "llvm/Target/TargetSubtarget.h" 17#include "llvm/Target/TargetData.h" 18#include "llvm/Target/TargetMachine.h" 19#include "llvm/Target/TargetRegisterInfo.h" 20#include "llvm/GlobalVariable.h" 21#include "llvm/DerivedTypes.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/CodeGen/SelectionDAG.h" 24#include "llvm/ADT/StringExtras.h" 25#include "llvm/ADT/STLExtras.h" 26#include "llvm/Support/MathExtras.h" 27using namespace llvm; 28 29/// InitLibcallNames - Set default libcall names. 30/// 31static void InitLibcallNames(const char **Names) { 32 Names[RTLIB::SHL_I32] = "__ashlsi3"; 33 Names[RTLIB::SHL_I64] = "__ashldi3"; 34 Names[RTLIB::SHL_I128] = "__ashlti3"; 35 Names[RTLIB::SRL_I32] = "__lshrsi3"; 36 Names[RTLIB::SRL_I64] = "__lshrdi3"; 37 Names[RTLIB::SRL_I128] = "__lshrti3"; 38 Names[RTLIB::SRA_I32] = "__ashrsi3"; 39 Names[RTLIB::SRA_I64] = "__ashrdi3"; 40 Names[RTLIB::SRA_I128] = "__ashrti3"; 41 Names[RTLIB::MUL_I32] = "__mulsi3"; 42 Names[RTLIB::MUL_I64] = "__muldi3"; 43 Names[RTLIB::MUL_I128] = "__multi3"; 44 Names[RTLIB::SDIV_I32] = "__divsi3"; 45 Names[RTLIB::SDIV_I64] = "__divdi3"; 46 Names[RTLIB::SDIV_I128] = "__divti3"; 47 Names[RTLIB::UDIV_I32] = "__udivsi3"; 48 Names[RTLIB::UDIV_I64] = "__udivdi3"; 49 Names[RTLIB::UDIV_I128] = "__udivti3"; 50 Names[RTLIB::SREM_I32] = "__modsi3"; 51 Names[RTLIB::SREM_I64] = "__moddi3"; 52 Names[RTLIB::SREM_I128] = "__modti3"; 53 Names[RTLIB::UREM_I32] = "__umodsi3"; 54 Names[RTLIB::UREM_I64] = "__umoddi3"; 55 Names[RTLIB::UREM_I128] = "__umodti3"; 56 Names[RTLIB::NEG_I32] = "__negsi2"; 57 Names[RTLIB::NEG_I64] = "__negdi2"; 58 Names[RTLIB::ADD_F32] = "__addsf3"; 59 Names[RTLIB::ADD_F64] = "__adddf3"; 60 Names[RTLIB::ADD_F80] = "__addxf3"; 61 Names[RTLIB::ADD_PPCF128] = "__gcc_qadd"; 62 Names[RTLIB::SUB_F32] = "__subsf3"; 63 Names[RTLIB::SUB_F64] = "__subdf3"; 64 Names[RTLIB::SUB_F80] = "__subxf3"; 65 Names[RTLIB::SUB_PPCF128] = "__gcc_qsub"; 66 Names[RTLIB::MUL_F32] = "__mulsf3"; 67 Names[RTLIB::MUL_F64] = "__muldf3"; 68 Names[RTLIB::MUL_F80] = "__mulxf3"; 69 Names[RTLIB::MUL_PPCF128] = "__gcc_qmul"; 70 Names[RTLIB::DIV_F32] = "__divsf3"; 71 Names[RTLIB::DIV_F64] = "__divdf3"; 72 Names[RTLIB::DIV_F80] = "__divxf3"; 73 Names[RTLIB::DIV_PPCF128] = "__gcc_qdiv"; 74 Names[RTLIB::REM_F32] = "fmodf"; 75 Names[RTLIB::REM_F64] = "fmod"; 76 Names[RTLIB::REM_F80] = "fmodl"; 77 Names[RTLIB::REM_PPCF128] = "fmodl"; 78 Names[RTLIB::POWI_F32] = "__powisf2"; 79 Names[RTLIB::POWI_F64] = "__powidf2"; 80 Names[RTLIB::POWI_F80] = "__powixf2"; 81 Names[RTLIB::POWI_PPCF128] = "__powitf2"; 82 Names[RTLIB::SQRT_F32] = "sqrtf"; 83 Names[RTLIB::SQRT_F64] = "sqrt"; 84 Names[RTLIB::SQRT_F80] = "sqrtl"; 85 Names[RTLIB::SQRT_PPCF128] = "sqrtl"; 86 Names[RTLIB::SIN_F32] = "sinf"; 87 Names[RTLIB::SIN_F64] = "sin"; 88 Names[RTLIB::SIN_F80] = "sinl"; 89 Names[RTLIB::SIN_PPCF128] = "sinl"; 90 Names[RTLIB::COS_F32] = "cosf"; 91 Names[RTLIB::COS_F64] = "cos"; 92 Names[RTLIB::COS_F80] = "cosl"; 93 Names[RTLIB::COS_PPCF128] = "cosl"; 94 Names[RTLIB::POW_F32] = "powf"; 95 Names[RTLIB::POW_F64] = "pow"; 96 Names[RTLIB::POW_F80] = "powl"; 97 Names[RTLIB::POW_PPCF128] = "powl"; 98 Names[RTLIB::CEIL_F32] = "ceilf"; 99 Names[RTLIB::CEIL_F64] = "ceil"; 100 Names[RTLIB::CEIL_F80] = "ceill"; 101 Names[RTLIB::CEIL_PPCF128] = "ceill"; 102 Names[RTLIB::TRUNC_F32] = "truncf"; 103 Names[RTLIB::TRUNC_F64] = "trunc"; 104 Names[RTLIB::TRUNC_F80] = "truncl"; 105 Names[RTLIB::TRUNC_PPCF128] = "truncl"; 106 Names[RTLIB::RINT_F32] = "rintf"; 107 Names[RTLIB::RINT_F64] = "rint"; 108 Names[RTLIB::RINT_F80] = "rintl"; 109 Names[RTLIB::RINT_PPCF128] = "rintl"; 110 Names[RTLIB::NEARBYINT_F32] = "nearbyintf"; 111 Names[RTLIB::NEARBYINT_F64] = "nearbyint"; 112 Names[RTLIB::NEARBYINT_F80] = "nearbyintl"; 113 Names[RTLIB::NEARBYINT_PPCF128] = "nearbyintl"; 114 Names[RTLIB::FLOOR_F32] = "floorf"; 115 Names[RTLIB::FLOOR_F64] = "floor"; 116 Names[RTLIB::FLOOR_F80] = "floorl"; 117 Names[RTLIB::FLOOR_PPCF128] = "floorl"; 118 Names[RTLIB::FPEXT_F32_F64] = "__extendsfdf2"; 119 Names[RTLIB::FPROUND_F64_F32] = "__truncdfsf2"; 120 Names[RTLIB::FPROUND_F80_F32] = "__truncxfsf2"; 121 Names[RTLIB::FPROUND_PPCF128_F32] = "__trunctfsf2"; 122 Names[RTLIB::FPROUND_F80_F64] = "__truncxfdf2"; 123 Names[RTLIB::FPROUND_PPCF128_F64] = "__trunctfdf2"; 124 Names[RTLIB::FPTOSINT_F32_I32] = "__fixsfsi"; 125 Names[RTLIB::FPTOSINT_F32_I64] = "__fixsfdi"; 126 Names[RTLIB::FPTOSINT_F32_I128] = "__fixsfti"; 127 Names[RTLIB::FPTOSINT_F64_I32] = "__fixdfsi"; 128 Names[RTLIB::FPTOSINT_F64_I64] = "__fixdfdi"; 129 Names[RTLIB::FPTOSINT_F64_I128] = "__fixdfti"; 130 Names[RTLIB::FPTOSINT_F80_I32] = "__fixxfsi"; 131 Names[RTLIB::FPTOSINT_F80_I64] = "__fixxfdi"; 132 Names[RTLIB::FPTOSINT_F80_I128] = "__fixxfti"; 133 Names[RTLIB::FPTOSINT_PPCF128_I32] = "__fixtfsi"; 134 Names[RTLIB::FPTOSINT_PPCF128_I64] = "__fixtfdi"; 135 Names[RTLIB::FPTOSINT_PPCF128_I128] = "__fixtfti"; 136 Names[RTLIB::FPTOUINT_F32_I32] = "__fixunssfsi"; 137 Names[RTLIB::FPTOUINT_F32_I64] = "__fixunssfdi"; 138 Names[RTLIB::FPTOUINT_F32_I128] = "__fixunssfti"; 139 Names[RTLIB::FPTOUINT_F64_I32] = "__fixunsdfsi"; 140 Names[RTLIB::FPTOUINT_F64_I64] = "__fixunsdfdi"; 141 Names[RTLIB::FPTOUINT_F64_I128] = "__fixunsdfti"; 142 Names[RTLIB::FPTOUINT_F80_I32] = "__fixunsxfsi"; 143 Names[RTLIB::FPTOUINT_F80_I64] = "__fixunsxfdi"; 144 Names[RTLIB::FPTOUINT_F80_I128] = "__fixunsxfti"; 145 Names[RTLIB::FPTOUINT_PPCF128_I32] = "__fixunstfsi"; 146 Names[RTLIB::FPTOUINT_PPCF128_I64] = "__fixunstfdi"; 147 Names[RTLIB::FPTOUINT_PPCF128_I128] = "__fixunstfti"; 148 Names[RTLIB::SINTTOFP_I32_F32] = "__floatsisf"; 149 Names[RTLIB::SINTTOFP_I32_F64] = "__floatsidf"; 150 Names[RTLIB::SINTTOFP_I32_F80] = "__floatsixf"; 151 Names[RTLIB::SINTTOFP_I32_PPCF128] = "__floatsitf"; 152 Names[RTLIB::SINTTOFP_I64_F32] = "__floatdisf"; 153 Names[RTLIB::SINTTOFP_I64_F64] = "__floatdidf"; 154 Names[RTLIB::SINTTOFP_I64_F80] = "__floatdixf"; 155 Names[RTLIB::SINTTOFP_I64_PPCF128] = "__floatditf"; 156 Names[RTLIB::SINTTOFP_I128_F32] = "__floattisf"; 157 Names[RTLIB::SINTTOFP_I128_F64] = "__floattidf"; 158 Names[RTLIB::SINTTOFP_I128_F80] = "__floattixf"; 159 Names[RTLIB::SINTTOFP_I128_PPCF128] = "__floattitf"; 160 Names[RTLIB::UINTTOFP_I32_F32] = "__floatunsisf"; 161 Names[RTLIB::UINTTOFP_I32_F64] = "__floatunsidf"; 162 Names[RTLIB::UINTTOFP_I32_F80] = "__floatunsixf"; 163 Names[RTLIB::UINTTOFP_I32_PPCF128] = "__floatunsitf"; 164 Names[RTLIB::UINTTOFP_I64_F32] = "__floatundisf"; 165 Names[RTLIB::UINTTOFP_I64_F64] = "__floatundidf"; 166 Names[RTLIB::UINTTOFP_I64_F80] = "__floatundixf"; 167 Names[RTLIB::UINTTOFP_I64_PPCF128] = "__floatunditf"; 168 Names[RTLIB::UINTTOFP_I128_F32] = "__floatuntisf"; 169 Names[RTLIB::UINTTOFP_I128_F64] = "__floatuntidf"; 170 Names[RTLIB::UINTTOFP_I128_F80] = "__floatuntixf"; 171 Names[RTLIB::UINTTOFP_I128_PPCF128] = "__floatuntitf"; 172 Names[RTLIB::OEQ_F32] = "__eqsf2"; 173 Names[RTLIB::OEQ_F64] = "__eqdf2"; 174 Names[RTLIB::UNE_F32] = "__nesf2"; 175 Names[RTLIB::UNE_F64] = "__nedf2"; 176 Names[RTLIB::OGE_F32] = "__gesf2"; 177 Names[RTLIB::OGE_F64] = "__gedf2"; 178 Names[RTLIB::OLT_F32] = "__ltsf2"; 179 Names[RTLIB::OLT_F64] = "__ltdf2"; 180 Names[RTLIB::OLE_F32] = "__lesf2"; 181 Names[RTLIB::OLE_F64] = "__ledf2"; 182 Names[RTLIB::OGT_F32] = "__gtsf2"; 183 Names[RTLIB::OGT_F64] = "__gtdf2"; 184 Names[RTLIB::UO_F32] = "__unordsf2"; 185 Names[RTLIB::UO_F64] = "__unorddf2"; 186 Names[RTLIB::O_F32] = "__unordsf2"; 187 Names[RTLIB::O_F64] = "__unorddf2"; 188} 189 190/// getFPEXT - Return the FPEXT_*_* value for the given types, or 191/// UNKNOWN_LIBCALL if there is none. 192RTLIB::Libcall RTLIB::getFPEXT(MVT OpVT, MVT RetVT) { 193 if (OpVT == MVT::f32) { 194 if (RetVT == MVT::f64) 195 return FPEXT_F32_F64; 196 } 197 return UNKNOWN_LIBCALL; 198} 199 200/// getFPROUND - Return the FPROUND_*_* value for the given types, or 201/// UNKNOWN_LIBCALL if there is none. 202RTLIB::Libcall RTLIB::getFPROUND(MVT OpVT, MVT RetVT) { 203 if (RetVT == MVT::f32) { 204 if (OpVT == MVT::f64) 205 return FPROUND_F64_F32; 206 if (OpVT == MVT::f80) 207 return FPROUND_F80_F32; 208 if (OpVT == MVT::ppcf128) 209 return FPROUND_PPCF128_F32; 210 } else if (RetVT == MVT::f64) { 211 if (OpVT == MVT::f80) 212 return FPROUND_F80_F64; 213 if (OpVT == MVT::ppcf128) 214 return FPROUND_PPCF128_F64; 215 } 216 return UNKNOWN_LIBCALL; 217} 218 219/// getFPTOSINT - Return the FPTOSINT_*_* value for the given types, or 220/// UNKNOWN_LIBCALL if there is none. 221RTLIB::Libcall RTLIB::getFPTOSINT(MVT OpVT, MVT RetVT) { 222 if (OpVT == MVT::f32) { 223 if (RetVT == MVT::i32) 224 return FPTOSINT_F32_I32; 225 if (RetVT == MVT::i64) 226 return FPTOSINT_F32_I64; 227 if (RetVT == MVT::i128) 228 return FPTOSINT_F32_I128; 229 } else if (OpVT == MVT::f64) { 230 if (RetVT == MVT::i32) 231 return FPTOSINT_F64_I32; 232 if (RetVT == MVT::i64) 233 return FPTOSINT_F64_I64; 234 if (RetVT == MVT::i128) 235 return FPTOSINT_F64_I128; 236 } else if (OpVT == MVT::f80) { 237 if (RetVT == MVT::i32) 238 return FPTOSINT_F80_I32; 239 if (RetVT == MVT::i64) 240 return FPTOSINT_F80_I64; 241 if (RetVT == MVT::i128) 242 return FPTOSINT_F80_I128; 243 } else if (OpVT == MVT::ppcf128) { 244 if (RetVT == MVT::i32) 245 return FPTOSINT_PPCF128_I32; 246 if (RetVT == MVT::i64) 247 return FPTOSINT_PPCF128_I64; 248 if (RetVT == MVT::i128) 249 return FPTOSINT_PPCF128_I128; 250 } 251 return UNKNOWN_LIBCALL; 252} 253 254/// getFPTOUINT - Return the FPTOUINT_*_* value for the given types, or 255/// UNKNOWN_LIBCALL if there is none. 256RTLIB::Libcall RTLIB::getFPTOUINT(MVT OpVT, MVT RetVT) { 257 if (OpVT == MVT::f32) { 258 if (RetVT == MVT::i32) 259 return FPTOUINT_F32_I32; 260 if (RetVT == MVT::i64) 261 return FPTOUINT_F32_I64; 262 if (RetVT == MVT::i128) 263 return FPTOUINT_F32_I128; 264 } else if (OpVT == MVT::f64) { 265 if (RetVT == MVT::i32) 266 return FPTOUINT_F64_I32; 267 if (RetVT == MVT::i64) 268 return FPTOUINT_F64_I64; 269 if (RetVT == MVT::i128) 270 return FPTOUINT_F64_I128; 271 } else if (OpVT == MVT::f80) { 272 if (RetVT == MVT::i32) 273 return FPTOUINT_F80_I32; 274 if (RetVT == MVT::i64) 275 return FPTOUINT_F80_I64; 276 if (RetVT == MVT::i128) 277 return FPTOUINT_F80_I128; 278 } else if (OpVT == MVT::ppcf128) { 279 if (RetVT == MVT::i32) 280 return FPTOUINT_PPCF128_I32; 281 if (RetVT == MVT::i64) 282 return FPTOUINT_PPCF128_I64; 283 if (RetVT == MVT::i128) 284 return FPTOUINT_PPCF128_I128; 285 } 286 return UNKNOWN_LIBCALL; 287} 288 289/// getSINTTOFP - Return the SINTTOFP_*_* value for the given types, or 290/// UNKNOWN_LIBCALL if there is none. 291RTLIB::Libcall RTLIB::getSINTTOFP(MVT OpVT, MVT RetVT) { 292 if (OpVT == MVT::i32) { 293 if (RetVT == MVT::f32) 294 return SINTTOFP_I32_F32; 295 else if (RetVT == MVT::f64) 296 return SINTTOFP_I32_F64; 297 else if (RetVT == MVT::f80) 298 return SINTTOFP_I32_F80; 299 else if (RetVT == MVT::ppcf128) 300 return SINTTOFP_I32_PPCF128; 301 } else if (OpVT == MVT::i64) { 302 if (RetVT == MVT::f32) 303 return SINTTOFP_I64_F32; 304 else if (RetVT == MVT::f64) 305 return SINTTOFP_I64_F64; 306 else if (RetVT == MVT::f80) 307 return SINTTOFP_I64_F80; 308 else if (RetVT == MVT::ppcf128) 309 return SINTTOFP_I64_PPCF128; 310 } else if (OpVT == MVT::i128) { 311 if (RetVT == MVT::f32) 312 return SINTTOFP_I128_F32; 313 else if (RetVT == MVT::f64) 314 return SINTTOFP_I128_F64; 315 else if (RetVT == MVT::f80) 316 return SINTTOFP_I128_F80; 317 else if (RetVT == MVT::ppcf128) 318 return SINTTOFP_I128_PPCF128; 319 } 320 return UNKNOWN_LIBCALL; 321} 322 323/// getUINTTOFP - Return the UINTTOFP_*_* value for the given types, or 324/// UNKNOWN_LIBCALL if there is none. 325RTLIB::Libcall RTLIB::getUINTTOFP(MVT OpVT, MVT RetVT) { 326 if (OpVT == MVT::i32) { 327 if (RetVT == MVT::f32) 328 return UINTTOFP_I32_F32; 329 else if (RetVT == MVT::f64) 330 return UINTTOFP_I32_F64; 331 else if (RetVT == MVT::f80) 332 return UINTTOFP_I32_F80; 333 else if (RetVT == MVT::ppcf128) 334 return UINTTOFP_I32_PPCF128; 335 } else if (OpVT == MVT::i64) { 336 if (RetVT == MVT::f32) 337 return UINTTOFP_I64_F32; 338 else if (RetVT == MVT::f64) 339 return UINTTOFP_I64_F64; 340 else if (RetVT == MVT::f80) 341 return UINTTOFP_I64_F80; 342 else if (RetVT == MVT::ppcf128) 343 return UINTTOFP_I64_PPCF128; 344 } else if (OpVT == MVT::i128) { 345 if (RetVT == MVT::f32) 346 return UINTTOFP_I128_F32; 347 else if (RetVT == MVT::f64) 348 return UINTTOFP_I128_F64; 349 else if (RetVT == MVT::f80) 350 return UINTTOFP_I128_F80; 351 else if (RetVT == MVT::ppcf128) 352 return UINTTOFP_I128_PPCF128; 353 } 354 return UNKNOWN_LIBCALL; 355} 356 357/// InitCmpLibcallCCs - Set default comparison libcall CC. 358/// 359static void InitCmpLibcallCCs(ISD::CondCode *CCs) { 360 memset(CCs, ISD::SETCC_INVALID, sizeof(ISD::CondCode)*RTLIB::UNKNOWN_LIBCALL); 361 CCs[RTLIB::OEQ_F32] = ISD::SETEQ; 362 CCs[RTLIB::OEQ_F64] = ISD::SETEQ; 363 CCs[RTLIB::UNE_F32] = ISD::SETNE; 364 CCs[RTLIB::UNE_F64] = ISD::SETNE; 365 CCs[RTLIB::OGE_F32] = ISD::SETGE; 366 CCs[RTLIB::OGE_F64] = ISD::SETGE; 367 CCs[RTLIB::OLT_F32] = ISD::SETLT; 368 CCs[RTLIB::OLT_F64] = ISD::SETLT; 369 CCs[RTLIB::OLE_F32] = ISD::SETLE; 370 CCs[RTLIB::OLE_F64] = ISD::SETLE; 371 CCs[RTLIB::OGT_F32] = ISD::SETGT; 372 CCs[RTLIB::OGT_F64] = ISD::SETGT; 373 CCs[RTLIB::UO_F32] = ISD::SETNE; 374 CCs[RTLIB::UO_F64] = ISD::SETNE; 375 CCs[RTLIB::O_F32] = ISD::SETEQ; 376 CCs[RTLIB::O_F64] = ISD::SETEQ; 377} 378 379TargetLowering::TargetLowering(TargetMachine &tm) 380 : TM(tm), TD(TM.getTargetData()) { 381 assert(ISD::BUILTIN_OP_END <= OpActionsCapacity && 382 "Fixed size array in TargetLowering is not large enough!"); 383 // All operations default to being supported. 384 memset(OpActions, 0, sizeof(OpActions)); 385 memset(LoadXActions, 0, sizeof(LoadXActions)); 386 memset(TruncStoreActions, 0, sizeof(TruncStoreActions)); 387 memset(IndexedModeActions, 0, sizeof(IndexedModeActions)); 388 memset(ConvertActions, 0, sizeof(ConvertActions)); 389 390 // Set default actions for various operations. 391 for (unsigned VT = 0; VT != (unsigned)MVT::LAST_VALUETYPE; ++VT) { 392 // Default all indexed load / store to expand. 393 for (unsigned IM = (unsigned)ISD::PRE_INC; 394 IM != (unsigned)ISD::LAST_INDEXED_MODE; ++IM) { 395 setIndexedLoadAction(IM, (MVT::SimpleValueType)VT, Expand); 396 setIndexedStoreAction(IM, (MVT::SimpleValueType)VT, Expand); 397 } 398 399 // These operations default to expand. 400 setOperationAction(ISD::FGETSIGN, (MVT::SimpleValueType)VT, Expand); 401 } 402 403 // Most targets ignore the @llvm.prefetch intrinsic. 404 setOperationAction(ISD::PREFETCH, MVT::Other, Expand); 405 406 // ConstantFP nodes default to expand. Targets can either change this to 407 // Legal, in which case all fp constants are legal, or use addLegalFPImmediate 408 // to optimize expansions for certain constants. 409 setOperationAction(ISD::ConstantFP, MVT::f32, Expand); 410 setOperationAction(ISD::ConstantFP, MVT::f64, Expand); 411 setOperationAction(ISD::ConstantFP, MVT::f80, Expand); 412 413 // Default ISD::TRAP to expand (which turns it into abort). 414 setOperationAction(ISD::TRAP, MVT::Other, Expand); 415 416 IsLittleEndian = TD->isLittleEndian(); 417 UsesGlobalOffsetTable = false; 418 ShiftAmountTy = PointerTy = getValueType(TD->getIntPtrType()); 419 ShiftAmtHandling = Undefined; 420 memset(RegClassForVT, 0,MVT::LAST_VALUETYPE*sizeof(TargetRegisterClass*)); 421 memset(TargetDAGCombineArray, 0, array_lengthof(TargetDAGCombineArray)); 422 maxStoresPerMemset = maxStoresPerMemcpy = maxStoresPerMemmove = 8; 423 allowUnalignedMemoryAccesses = false; 424 UseUnderscoreSetJmp = false; 425 UseUnderscoreLongJmp = false; 426 SelectIsExpensive = false; 427 IntDivIsCheap = false; 428 Pow2DivIsCheap = false; 429 StackPointerRegisterToSaveRestore = 0; 430 ExceptionPointerRegister = 0; 431 ExceptionSelectorRegister = 0; 432 SetCCResultContents = UndefinedSetCCResult; 433 SchedPreferenceInfo = SchedulingForLatency; 434 JumpBufSize = 0; 435 JumpBufAlignment = 0; 436 IfCvtBlockSizeLimit = 2; 437 IfCvtDupBlockSizeLimit = 0; 438 PrefLoopAlignment = 0; 439 440 InitLibcallNames(LibcallRoutineNames); 441 InitCmpLibcallCCs(CmpLibcallCCs); 442 443 // Tell Legalize whether the assembler supports DEBUG_LOC. 444 if (!TM.getTargetAsmInfo()->hasDotLocAndDotFile()) 445 setOperationAction(ISD::DEBUG_LOC, MVT::Other, Expand); 446} 447 448TargetLowering::~TargetLowering() {} 449 450/// computeRegisterProperties - Once all of the register classes are added, 451/// this allows us to compute derived properties we expose. 452void TargetLowering::computeRegisterProperties() { 453 assert(MVT::LAST_VALUETYPE <= 32 && 454 "Too many value types for ValueTypeActions to hold!"); 455 456 // Everything defaults to needing one register. 457 for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i) { 458 NumRegistersForVT[i] = 1; 459 RegisterTypeForVT[i] = TransformToType[i] = (MVT::SimpleValueType)i; 460 } 461 // ...except isVoid, which doesn't need any registers. 462 NumRegistersForVT[MVT::isVoid] = 0; 463 464 // Find the largest integer register class. 465 unsigned LargestIntReg = MVT::LAST_INTEGER_VALUETYPE; 466 for (; RegClassForVT[LargestIntReg] == 0; --LargestIntReg) 467 assert(LargestIntReg != MVT::i1 && "No integer registers defined!"); 468 469 // Every integer value type larger than this largest register takes twice as 470 // many registers to represent as the previous ValueType. 471 for (unsigned ExpandedReg = LargestIntReg + 1; ; ++ExpandedReg) { 472 MVT EVT = (MVT::SimpleValueType)ExpandedReg; 473 if (!EVT.isInteger()) 474 break; 475 NumRegistersForVT[ExpandedReg] = 2*NumRegistersForVT[ExpandedReg-1]; 476 RegisterTypeForVT[ExpandedReg] = (MVT::SimpleValueType)LargestIntReg; 477 TransformToType[ExpandedReg] = (MVT::SimpleValueType)(ExpandedReg - 1); 478 ValueTypeActions.setTypeAction(EVT, Expand); 479 } 480 481 // Inspect all of the ValueType's smaller than the largest integer 482 // register to see which ones need promotion. 483 unsigned LegalIntReg = LargestIntReg; 484 for (unsigned IntReg = LargestIntReg - 1; 485 IntReg >= (unsigned)MVT::i1; --IntReg) { 486 MVT IVT = (MVT::SimpleValueType)IntReg; 487 if (isTypeLegal(IVT)) { 488 LegalIntReg = IntReg; 489 } else { 490 RegisterTypeForVT[IntReg] = TransformToType[IntReg] = 491 (MVT::SimpleValueType)LegalIntReg; 492 ValueTypeActions.setTypeAction(IVT, Promote); 493 } 494 } 495 496 // ppcf128 type is really two f64's. 497 if (!isTypeLegal(MVT::ppcf128)) { 498 NumRegistersForVT[MVT::ppcf128] = 2*NumRegistersForVT[MVT::f64]; 499 RegisterTypeForVT[MVT::ppcf128] = MVT::f64; 500 TransformToType[MVT::ppcf128] = MVT::f64; 501 ValueTypeActions.setTypeAction(MVT::ppcf128, Expand); 502 } 503 504 // Decide how to handle f64. If the target does not have native f64 support, 505 // expand it to i64 and we will be generating soft float library calls. 506 if (!isTypeLegal(MVT::f64)) { 507 NumRegistersForVT[MVT::f64] = NumRegistersForVT[MVT::i64]; 508 RegisterTypeForVT[MVT::f64] = RegisterTypeForVT[MVT::i64]; 509 TransformToType[MVT::f64] = MVT::i64; 510 ValueTypeActions.setTypeAction(MVT::f64, Expand); 511 } 512 513 // Decide how to handle f32. If the target does not have native support for 514 // f32, promote it to f64 if it is legal. Otherwise, expand it to i32. 515 if (!isTypeLegal(MVT::f32)) { 516 if (isTypeLegal(MVT::f64)) { 517 NumRegistersForVT[MVT::f32] = NumRegistersForVT[MVT::f64]; 518 RegisterTypeForVT[MVT::f32] = RegisterTypeForVT[MVT::f64]; 519 TransformToType[MVT::f32] = MVT::f64; 520 ValueTypeActions.setTypeAction(MVT::f32, Promote); 521 } else { 522 NumRegistersForVT[MVT::f32] = NumRegistersForVT[MVT::i32]; 523 RegisterTypeForVT[MVT::f32] = RegisterTypeForVT[MVT::i32]; 524 TransformToType[MVT::f32] = MVT::i32; 525 ValueTypeActions.setTypeAction(MVT::f32, Expand); 526 } 527 } 528 529 // Loop over all of the vector value types to see which need transformations. 530 for (unsigned i = MVT::FIRST_VECTOR_VALUETYPE; 531 i <= (unsigned)MVT::LAST_VECTOR_VALUETYPE; ++i) { 532 MVT VT = (MVT::SimpleValueType)i; 533 if (!isTypeLegal(VT)) { 534 MVT IntermediateVT, RegisterVT; 535 unsigned NumIntermediates; 536 NumRegistersForVT[i] = 537 getVectorTypeBreakdown(VT, 538 IntermediateVT, NumIntermediates, 539 RegisterVT); 540 RegisterTypeForVT[i] = RegisterVT; 541 TransformToType[i] = MVT::Other; // this isn't actually used 542 ValueTypeActions.setTypeAction(VT, Expand); 543 } 544 } 545} 546 547const char *TargetLowering::getTargetNodeName(unsigned Opcode) const { 548 return NULL; 549} 550 551 552MVT TargetLowering::getSetCCResultType(const SDValue &) const { 553 return getValueType(TD->getIntPtrType()); 554} 555 556 557/// getVectorTypeBreakdown - Vector types are broken down into some number of 558/// legal first class types. For example, MVT::v8f32 maps to 2 MVT::v4f32 559/// with Altivec or SSE1, or 8 promoted MVT::f64 values with the X86 FP stack. 560/// Similarly, MVT::v2i64 turns into 4 MVT::i32 values with both PPC and X86. 561/// 562/// This method returns the number of registers needed, and the VT for each 563/// register. It also returns the VT and quantity of the intermediate values 564/// before they are promoted/expanded. 565/// 566unsigned TargetLowering::getVectorTypeBreakdown(MVT VT, 567 MVT &IntermediateVT, 568 unsigned &NumIntermediates, 569 MVT &RegisterVT) const { 570 // Figure out the right, legal destination reg to copy into. 571 unsigned NumElts = VT.getVectorNumElements(); 572 MVT EltTy = VT.getVectorElementType(); 573 574 unsigned NumVectorRegs = 1; 575 576 // FIXME: We don't support non-power-of-2-sized vectors for now. Ideally we 577 // could break down into LHS/RHS like LegalizeDAG does. 578 if (!isPowerOf2_32(NumElts)) { 579 NumVectorRegs = NumElts; 580 NumElts = 1; 581 } 582 583 // Divide the input until we get to a supported size. This will always 584 // end with a scalar if the target doesn't support vectors. 585 while (NumElts > 1 && !isTypeLegal(MVT::getVectorVT(EltTy, NumElts))) { 586 NumElts >>= 1; 587 NumVectorRegs <<= 1; 588 } 589 590 NumIntermediates = NumVectorRegs; 591 592 MVT NewVT = MVT::getVectorVT(EltTy, NumElts); 593 if (!isTypeLegal(NewVT)) 594 NewVT = EltTy; 595 IntermediateVT = NewVT; 596 597 MVT DestVT = getTypeToTransformTo(NewVT); 598 RegisterVT = DestVT; 599 if (DestVT.bitsLT(NewVT)) { 600 // Value is expanded, e.g. i64 -> i16. 601 return NumVectorRegs*(NewVT.getSizeInBits()/DestVT.getSizeInBits()); 602 } else { 603 // Otherwise, promotion or legal types use the same number of registers as 604 // the vector decimated to the appropriate level. 605 return NumVectorRegs; 606 } 607 608 return 1; 609} 610 611/// getByValTypeAlignment - Return the desired alignment for ByVal aggregate 612/// function arguments in the caller parameter area. This is the actual 613/// alignment, not its logarithm. 614unsigned TargetLowering::getByValTypeAlignment(const Type *Ty) const { 615 return TD->getCallFrameTypeAlignment(Ty); 616} 617 618SDValue TargetLowering::getPICJumpTableRelocBase(SDValue Table, 619 SelectionDAG &DAG) const { 620 if (usesGlobalOffsetTable()) 621 return DAG.getNode(ISD::GLOBAL_OFFSET_TABLE, getPointerTy()); 622 return Table; 623} 624 625//===----------------------------------------------------------------------===// 626// Optimization Methods 627//===----------------------------------------------------------------------===// 628 629/// ShrinkDemandedConstant - Check to see if the specified operand of the 630/// specified instruction is a constant integer. If so, check to see if there 631/// are any bits set in the constant that are not demanded. If so, shrink the 632/// constant and return true. 633bool TargetLowering::TargetLoweringOpt::ShrinkDemandedConstant(SDValue Op, 634 const APInt &Demanded) { 635 // FIXME: ISD::SELECT, ISD::SELECT_CC 636 switch(Op.getOpcode()) { 637 default: break; 638 case ISD::AND: 639 case ISD::OR: 640 case ISD::XOR: 641 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 642 if (C->getAPIntValue().intersects(~Demanded)) { 643 MVT VT = Op.getValueType(); 644 SDValue New = DAG.getNode(Op.getOpcode(), VT, Op.getOperand(0), 645 DAG.getConstant(Demanded & 646 C->getAPIntValue(), 647 VT)); 648 return CombineTo(Op, New); 649 } 650 break; 651 } 652 return false; 653} 654 655/// SimplifyDemandedBits - Look at Op. At this point, we know that only the 656/// DemandedMask bits of the result of Op are ever used downstream. If we can 657/// use this information to simplify Op, create a new simplified DAG node and 658/// return true, returning the original and new nodes in Old and New. Otherwise, 659/// analyze the expression and return a mask of KnownOne and KnownZero bits for 660/// the expression (used to simplify the caller). The KnownZero/One bits may 661/// only be accurate for those bits in the DemandedMask. 662bool TargetLowering::SimplifyDemandedBits(SDValue Op, 663 const APInt &DemandedMask, 664 APInt &KnownZero, 665 APInt &KnownOne, 666 TargetLoweringOpt &TLO, 667 unsigned Depth) const { 668 unsigned BitWidth = DemandedMask.getBitWidth(); 669 assert(Op.getValueSizeInBits() == BitWidth && 670 "Mask size mismatches value type size!"); 671 APInt NewMask = DemandedMask; 672 673 // Don't know anything. 674 KnownZero = KnownOne = APInt(BitWidth, 0); 675 676 // Other users may use these bits. 677 if (!Op.Val->hasOneUse()) { 678 if (Depth != 0) { 679 // If not at the root, Just compute the KnownZero/KnownOne bits to 680 // simplify things downstream. 681 TLO.DAG.ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); 682 return false; 683 } 684 // If this is the root being simplified, allow it to have multiple uses, 685 // just set the NewMask to all bits. 686 NewMask = APInt::getAllOnesValue(BitWidth); 687 } else if (DemandedMask == 0) { 688 // Not demanding any bits from Op. 689 if (Op.getOpcode() != ISD::UNDEF) 690 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::UNDEF, Op.getValueType())); 691 return false; 692 } else if (Depth == 6) { // Limit search depth. 693 return false; 694 } 695 696 APInt KnownZero2, KnownOne2, KnownZeroOut, KnownOneOut; 697 switch (Op.getOpcode()) { 698 case ISD::Constant: 699 // We know all of the bits for a constant! 700 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue() & NewMask; 701 KnownZero = ~KnownOne & NewMask; 702 return false; // Don't fall through, will infinitely loop. 703 case ISD::AND: 704 // If the RHS is a constant, check to see if the LHS would be zero without 705 // using the bits from the RHS. Below, we use knowledge about the RHS to 706 // simplify the LHS, here we're using information from the LHS to simplify 707 // the RHS. 708 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 709 APInt LHSZero, LHSOne; 710 TLO.DAG.ComputeMaskedBits(Op.getOperand(0), NewMask, 711 LHSZero, LHSOne, Depth+1); 712 // If the LHS already has zeros where RHSC does, this and is dead. 713 if ((LHSZero & NewMask) == (~RHSC->getAPIntValue() & NewMask)) 714 return TLO.CombineTo(Op, Op.getOperand(0)); 715 // If any of the set bits in the RHS are known zero on the LHS, shrink 716 // the constant. 717 if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & NewMask)) 718 return true; 719 } 720 721 if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero, 722 KnownOne, TLO, Depth+1)) 723 return true; 724 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 725 if (SimplifyDemandedBits(Op.getOperand(0), ~KnownZero & NewMask, 726 KnownZero2, KnownOne2, TLO, Depth+1)) 727 return true; 728 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 729 730 // If all of the demanded bits are known one on one side, return the other. 731 // These bits cannot contribute to the result of the 'and'. 732 if ((NewMask & ~KnownZero2 & KnownOne) == (~KnownZero2 & NewMask)) 733 return TLO.CombineTo(Op, Op.getOperand(0)); 734 if ((NewMask & ~KnownZero & KnownOne2) == (~KnownZero & NewMask)) 735 return TLO.CombineTo(Op, Op.getOperand(1)); 736 // If all of the demanded bits in the inputs are known zeros, return zero. 737 if ((NewMask & (KnownZero|KnownZero2)) == NewMask) 738 return TLO.CombineTo(Op, TLO.DAG.getConstant(0, Op.getValueType())); 739 // If the RHS is a constant, see if we can simplify it. 740 if (TLO.ShrinkDemandedConstant(Op, ~KnownZero2 & NewMask)) 741 return true; 742 743 // Output known-1 bits are only known if set in both the LHS & RHS. 744 KnownOne &= KnownOne2; 745 // Output known-0 are known to be clear if zero in either the LHS | RHS. 746 KnownZero |= KnownZero2; 747 break; 748 case ISD::OR: 749 if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero, 750 KnownOne, TLO, Depth+1)) 751 return true; 752 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 753 if (SimplifyDemandedBits(Op.getOperand(0), ~KnownOne & NewMask, 754 KnownZero2, KnownOne2, TLO, Depth+1)) 755 return true; 756 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 757 758 // If all of the demanded bits are known zero on one side, return the other. 759 // These bits cannot contribute to the result of the 'or'. 760 if ((NewMask & ~KnownOne2 & KnownZero) == (~KnownOne2 & NewMask)) 761 return TLO.CombineTo(Op, Op.getOperand(0)); 762 if ((NewMask & ~KnownOne & KnownZero2) == (~KnownOne & NewMask)) 763 return TLO.CombineTo(Op, Op.getOperand(1)); 764 // If all of the potentially set bits on one side are known to be set on 765 // the other side, just use the 'other' side. 766 if ((NewMask & ~KnownZero & KnownOne2) == (~KnownZero & NewMask)) 767 return TLO.CombineTo(Op, Op.getOperand(0)); 768 if ((NewMask & ~KnownZero2 & KnownOne) == (~KnownZero2 & NewMask)) 769 return TLO.CombineTo(Op, Op.getOperand(1)); 770 // If the RHS is a constant, see if we can simplify it. 771 if (TLO.ShrinkDemandedConstant(Op, NewMask)) 772 return true; 773 774 // Output known-0 bits are only known if clear in both the LHS & RHS. 775 KnownZero &= KnownZero2; 776 // Output known-1 are known to be set if set in either the LHS | RHS. 777 KnownOne |= KnownOne2; 778 break; 779 case ISD::XOR: 780 if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero, 781 KnownOne, TLO, Depth+1)) 782 return true; 783 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 784 if (SimplifyDemandedBits(Op.getOperand(0), NewMask, KnownZero2, 785 KnownOne2, TLO, Depth+1)) 786 return true; 787 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 788 789 // If all of the demanded bits are known zero on one side, return the other. 790 // These bits cannot contribute to the result of the 'xor'. 791 if ((KnownZero & NewMask) == NewMask) 792 return TLO.CombineTo(Op, Op.getOperand(0)); 793 if ((KnownZero2 & NewMask) == NewMask) 794 return TLO.CombineTo(Op, Op.getOperand(1)); 795 796 // If all of the unknown bits are known to be zero on one side or the other 797 // (but not both) turn this into an *inclusive* or. 798 // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 799 if ((NewMask & ~KnownZero & ~KnownZero2) == 0) 800 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, Op.getValueType(), 801 Op.getOperand(0), 802 Op.getOperand(1))); 803 804 // Output known-0 bits are known if clear or set in both the LHS & RHS. 805 KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 806 // Output known-1 are known to be set if set in only one of the LHS, RHS. 807 KnownOneOut = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 808 809 // If all of the demanded bits on one side are known, and all of the set 810 // bits on that side are also known to be set on the other side, turn this 811 // into an AND, as we know the bits will be cleared. 812 // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 813 if ((NewMask & (KnownZero|KnownOne)) == NewMask) { // all known 814 if ((KnownOne & KnownOne2) == KnownOne) { 815 MVT VT = Op.getValueType(); 816 SDValue ANDC = TLO.DAG.getConstant(~KnownOne & NewMask, VT); 817 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, VT, Op.getOperand(0), 818 ANDC)); 819 } 820 } 821 822 // If the RHS is a constant, see if we can simplify it. 823 // for XOR, we prefer to force bits to 1 if they will make a -1. 824 // if we can't force bits, try to shrink constant 825 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 826 APInt Expanded = C->getAPIntValue() | (~NewMask); 827 // if we can expand it to have all bits set, do it 828 if (Expanded.isAllOnesValue()) { 829 if (Expanded != C->getAPIntValue()) { 830 MVT VT = Op.getValueType(); 831 SDValue New = TLO.DAG.getNode(Op.getOpcode(), VT, Op.getOperand(0), 832 TLO.DAG.getConstant(Expanded, VT)); 833 return TLO.CombineTo(Op, New); 834 } 835 // if it already has all the bits set, nothing to change 836 // but don't shrink either! 837 } else if (TLO.ShrinkDemandedConstant(Op, NewMask)) { 838 return true; 839 } 840 } 841 842 KnownZero = KnownZeroOut; 843 KnownOne = KnownOneOut; 844 break; 845 case ISD::SELECT: 846 if (SimplifyDemandedBits(Op.getOperand(2), NewMask, KnownZero, 847 KnownOne, TLO, Depth+1)) 848 return true; 849 if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero2, 850 KnownOne2, TLO, Depth+1)) 851 return true; 852 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 853 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 854 855 // If the operands are constants, see if we can simplify them. 856 if (TLO.ShrinkDemandedConstant(Op, NewMask)) 857 return true; 858 859 // Only known if known in both the LHS and RHS. 860 KnownOne &= KnownOne2; 861 KnownZero &= KnownZero2; 862 break; 863 case ISD::SELECT_CC: 864 if (SimplifyDemandedBits(Op.getOperand(3), NewMask, KnownZero, 865 KnownOne, TLO, Depth+1)) 866 return true; 867 if (SimplifyDemandedBits(Op.getOperand(2), NewMask, KnownZero2, 868 KnownOne2, TLO, Depth+1)) 869 return true; 870 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 871 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 872 873 // If the operands are constants, see if we can simplify them. 874 if (TLO.ShrinkDemandedConstant(Op, NewMask)) 875 return true; 876 877 // Only known if known in both the LHS and RHS. 878 KnownOne &= KnownOne2; 879 KnownZero &= KnownZero2; 880 break; 881 case ISD::SHL: 882 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 883 unsigned ShAmt = SA->getValue(); 884 SDValue InOp = Op.getOperand(0); 885 886 // If the shift count is an invalid immediate, don't do anything. 887 if (ShAmt >= BitWidth) 888 break; 889 890 // If this is ((X >>u C1) << ShAmt), see if we can simplify this into a 891 // single shift. We can do this if the bottom bits (which are shifted 892 // out) are never demanded. 893 if (InOp.getOpcode() == ISD::SRL && 894 isa<ConstantSDNode>(InOp.getOperand(1))) { 895 if (ShAmt && (NewMask & APInt::getLowBitsSet(BitWidth, ShAmt)) == 0) { 896 unsigned C1 = cast<ConstantSDNode>(InOp.getOperand(1))->getValue(); 897 unsigned Opc = ISD::SHL; 898 int Diff = ShAmt-C1; 899 if (Diff < 0) { 900 Diff = -Diff; 901 Opc = ISD::SRL; 902 } 903 904 SDValue NewSA = 905 TLO.DAG.getConstant(Diff, Op.getOperand(1).getValueType()); 906 MVT VT = Op.getValueType(); 907 return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, VT, 908 InOp.getOperand(0), NewSA)); 909 } 910 } 911 912 if (SimplifyDemandedBits(Op.getOperand(0), NewMask.lshr(ShAmt), 913 KnownZero, KnownOne, TLO, Depth+1)) 914 return true; 915 KnownZero <<= SA->getValue(); 916 KnownOne <<= SA->getValue(); 917 // low bits known zero. 918 KnownZero |= APInt::getLowBitsSet(BitWidth, SA->getValue()); 919 } 920 break; 921 case ISD::SRL: 922 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 923 MVT VT = Op.getValueType(); 924 unsigned ShAmt = SA->getValue(); 925 unsigned VTSize = VT.getSizeInBits(); 926 SDValue InOp = Op.getOperand(0); 927 928 // If the shift count is an invalid immediate, don't do anything. 929 if (ShAmt >= BitWidth) 930 break; 931 932 // If this is ((X << C1) >>u ShAmt), see if we can simplify this into a 933 // single shift. We can do this if the top bits (which are shifted out) 934 // are never demanded. 935 if (InOp.getOpcode() == ISD::SHL && 936 isa<ConstantSDNode>(InOp.getOperand(1))) { 937 if (ShAmt && (NewMask & APInt::getHighBitsSet(VTSize, ShAmt)) == 0) { 938 unsigned C1 = cast<ConstantSDNode>(InOp.getOperand(1))->getValue(); 939 unsigned Opc = ISD::SRL; 940 int Diff = ShAmt-C1; 941 if (Diff < 0) { 942 Diff = -Diff; 943 Opc = ISD::SHL; 944 } 945 946 SDValue NewSA = 947 TLO.DAG.getConstant(Diff, Op.getOperand(1).getValueType()); 948 return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, VT, 949 InOp.getOperand(0), NewSA)); 950 } 951 } 952 953 // Compute the new bits that are at the top now. 954 if (SimplifyDemandedBits(InOp, (NewMask << ShAmt), 955 KnownZero, KnownOne, TLO, Depth+1)) 956 return true; 957 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 958 KnownZero = KnownZero.lshr(ShAmt); 959 KnownOne = KnownOne.lshr(ShAmt); 960 961 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt); 962 KnownZero |= HighBits; // High bits known zero. 963 } 964 break; 965 case ISD::SRA: 966 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 967 MVT VT = Op.getValueType(); 968 unsigned ShAmt = SA->getValue(); 969 970 // If the shift count is an invalid immediate, don't do anything. 971 if (ShAmt >= BitWidth) 972 break; 973 974 APInt InDemandedMask = (NewMask << ShAmt); 975 976 // If any of the demanded bits are produced by the sign extension, we also 977 // demand the input sign bit. 978 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt); 979 if (HighBits.intersects(NewMask)) 980 InDemandedMask |= APInt::getSignBit(VT.getSizeInBits()); 981 982 if (SimplifyDemandedBits(Op.getOperand(0), InDemandedMask, 983 KnownZero, KnownOne, TLO, Depth+1)) 984 return true; 985 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 986 KnownZero = KnownZero.lshr(ShAmt); 987 KnownOne = KnownOne.lshr(ShAmt); 988 989 // Handle the sign bit, adjusted to where it is now in the mask. 990 APInt SignBit = APInt::getSignBit(BitWidth).lshr(ShAmt); 991 992 // If the input sign bit is known to be zero, or if none of the top bits 993 // are demanded, turn this into an unsigned shift right. 994 if (KnownZero.intersects(SignBit) || (HighBits & ~NewMask) == HighBits) { 995 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, VT, Op.getOperand(0), 996 Op.getOperand(1))); 997 } else if (KnownOne.intersects(SignBit)) { // New bits are known one. 998 KnownOne |= HighBits; 999 } 1000 } 1001 break; 1002 case ISD::SIGN_EXTEND_INREG: { 1003 MVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 1004 1005 // Sign extension. Compute the demanded bits in the result that are not 1006 // present in the input. 1007 APInt NewBits = APInt::getHighBitsSet(BitWidth, 1008 BitWidth - EVT.getSizeInBits()) & 1009 NewMask; 1010 1011 // If none of the extended bits are demanded, eliminate the sextinreg. 1012 if (NewBits == 0) 1013 return TLO.CombineTo(Op, Op.getOperand(0)); 1014 1015 APInt InSignBit = APInt::getSignBit(EVT.getSizeInBits()); 1016 InSignBit.zext(BitWidth); 1017 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, 1018 EVT.getSizeInBits()) & 1019 NewMask; 1020 1021 // Since the sign extended bits are demanded, we know that the sign 1022 // bit is demanded. 1023 InputDemandedBits |= InSignBit; 1024 1025 if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits, 1026 KnownZero, KnownOne, TLO, Depth+1)) 1027 return true; 1028 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1029 1030 // If the sign bit of the input is known set or clear, then we know the 1031 // top bits of the result. 1032 1033 // If the input sign bit is known zero, convert this into a zero extension. 1034 if (KnownZero.intersects(InSignBit)) 1035 return TLO.CombineTo(Op, 1036 TLO.DAG.getZeroExtendInReg(Op.getOperand(0), EVT)); 1037 1038 if (KnownOne.intersects(InSignBit)) { // Input sign bit known set 1039 KnownOne |= NewBits; 1040 KnownZero &= ~NewBits; 1041 } else { // Input sign bit unknown 1042 KnownZero &= ~NewBits; 1043 KnownOne &= ~NewBits; 1044 } 1045 break; 1046 } 1047 case ISD::ZERO_EXTEND: { 1048 unsigned OperandBitWidth = Op.getOperand(0).getValueSizeInBits(); 1049 APInt InMask = NewMask; 1050 InMask.trunc(OperandBitWidth); 1051 1052 // If none of the top bits are demanded, convert this into an any_extend. 1053 APInt NewBits = 1054 APInt::getHighBitsSet(BitWidth, BitWidth - OperandBitWidth) & NewMask; 1055 if (!NewBits.intersects(NewMask)) 1056 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, 1057 Op.getValueType(), 1058 Op.getOperand(0))); 1059 1060 if (SimplifyDemandedBits(Op.getOperand(0), InMask, 1061 KnownZero, KnownOne, TLO, Depth+1)) 1062 return true; 1063 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1064 KnownZero.zext(BitWidth); 1065 KnownOne.zext(BitWidth); 1066 KnownZero |= NewBits; 1067 break; 1068 } 1069 case ISD::SIGN_EXTEND: { 1070 MVT InVT = Op.getOperand(0).getValueType(); 1071 unsigned InBits = InVT.getSizeInBits(); 1072 APInt InMask = APInt::getLowBitsSet(BitWidth, InBits); 1073 APInt InSignBit = APInt::getBitsSet(BitWidth, InBits - 1, InBits); 1074 APInt NewBits = ~InMask & NewMask; 1075 1076 // If none of the top bits are demanded, convert this into an any_extend. 1077 if (NewBits == 0) 1078 return TLO.CombineTo(Op,TLO.DAG.getNode(ISD::ANY_EXTEND,Op.getValueType(), 1079 Op.getOperand(0))); 1080 1081 // Since some of the sign extended bits are demanded, we know that the sign 1082 // bit is demanded. 1083 APInt InDemandedBits = InMask & NewMask; 1084 InDemandedBits |= InSignBit; 1085 InDemandedBits.trunc(InBits); 1086 1087 if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, KnownZero, 1088 KnownOne, TLO, Depth+1)) 1089 return true; 1090 KnownZero.zext(BitWidth); 1091 KnownOne.zext(BitWidth); 1092 1093 // If the sign bit is known zero, convert this to a zero extend. 1094 if (KnownZero.intersects(InSignBit)) 1095 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, 1096 Op.getValueType(), 1097 Op.getOperand(0))); 1098 1099 // If the sign bit is known one, the top bits match. 1100 if (KnownOne.intersects(InSignBit)) { 1101 KnownOne |= NewBits; 1102 KnownZero &= ~NewBits; 1103 } else { // Otherwise, top bits aren't known. 1104 KnownOne &= ~NewBits; 1105 KnownZero &= ~NewBits; 1106 } 1107 break; 1108 } 1109 case ISD::ANY_EXTEND: { 1110 unsigned OperandBitWidth = Op.getOperand(0).getValueSizeInBits(); 1111 APInt InMask = NewMask; 1112 InMask.trunc(OperandBitWidth); 1113 if (SimplifyDemandedBits(Op.getOperand(0), InMask, 1114 KnownZero, KnownOne, TLO, Depth+1)) 1115 return true; 1116 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1117 KnownZero.zext(BitWidth); 1118 KnownOne.zext(BitWidth); 1119 break; 1120 } 1121 case ISD::TRUNCATE: { 1122 // Simplify the input, using demanded bit information, and compute the known 1123 // zero/one bits live out. 1124 APInt TruncMask = NewMask; 1125 TruncMask.zext(Op.getOperand(0).getValueSizeInBits()); 1126 if (SimplifyDemandedBits(Op.getOperand(0), TruncMask, 1127 KnownZero, KnownOne, TLO, Depth+1)) 1128 return true; 1129 KnownZero.trunc(BitWidth); 1130 KnownOne.trunc(BitWidth); 1131 1132 // If the input is only used by this truncate, see if we can shrink it based 1133 // on the known demanded bits. 1134 if (Op.getOperand(0).Val->hasOneUse()) { 1135 SDValue In = Op.getOperand(0); 1136 unsigned InBitWidth = In.getValueSizeInBits(); 1137 switch (In.getOpcode()) { 1138 default: break; 1139 case ISD::SRL: 1140 // Shrink SRL by a constant if none of the high bits shifted in are 1141 // demanded. 1142 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(In.getOperand(1))){ 1143 APInt HighBits = APInt::getHighBitsSet(InBitWidth, 1144 InBitWidth - BitWidth); 1145 HighBits = HighBits.lshr(ShAmt->getValue()); 1146 HighBits.trunc(BitWidth); 1147 1148 if (ShAmt->getValue() < BitWidth && !(HighBits & NewMask)) { 1149 // None of the shifted in bits are needed. Add a truncate of the 1150 // shift input, then shift it. 1151 SDValue NewTrunc = TLO.DAG.getNode(ISD::TRUNCATE, 1152 Op.getValueType(), 1153 In.getOperand(0)); 1154 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL,Op.getValueType(), 1155 NewTrunc, In.getOperand(1))); 1156 } 1157 } 1158 break; 1159 } 1160 } 1161 1162 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1163 break; 1164 } 1165 case ISD::AssertZext: { 1166 MVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 1167 APInt InMask = APInt::getLowBitsSet(BitWidth, 1168 VT.getSizeInBits()); 1169 if (SimplifyDemandedBits(Op.getOperand(0), InMask & NewMask, 1170 KnownZero, KnownOne, TLO, Depth+1)) 1171 return true; 1172 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1173 KnownZero |= ~InMask & NewMask; 1174 break; 1175 } 1176 case ISD::BIT_CONVERT: 1177#if 0 1178 // If this is an FP->Int bitcast and if the sign bit is the only thing that 1179 // is demanded, turn this into a FGETSIGN. 1180 if (NewMask == MVT::getIntegerVTSignBit(Op.getValueType()) && 1181 MVT::isFloatingPoint(Op.getOperand(0).getValueType()) && 1182 !MVT::isVector(Op.getOperand(0).getValueType())) { 1183 // Only do this xform if FGETSIGN is valid or if before legalize. 1184 if (!TLO.AfterLegalize || 1185 isOperationLegal(ISD::FGETSIGN, Op.getValueType())) { 1186 // Make a FGETSIGN + SHL to move the sign bit into the appropriate 1187 // place. We expect the SHL to be eliminated by other optimizations. 1188 SDValue Sign = TLO.DAG.getNode(ISD::FGETSIGN, Op.getValueType(), 1189 Op.getOperand(0)); 1190 unsigned ShVal = Op.getValueType().getSizeInBits()-1; 1191 SDValue ShAmt = TLO.DAG.getConstant(ShVal, getShiftAmountTy()); 1192 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, Op.getValueType(), 1193 Sign, ShAmt)); 1194 } 1195 } 1196#endif 1197 break; 1198 default: 1199 // Just use ComputeMaskedBits to compute output bits. 1200 TLO.DAG.ComputeMaskedBits(Op, NewMask, KnownZero, KnownOne, Depth); 1201 break; 1202 } 1203 1204 // If we know the value of all of the demanded bits, return this as a 1205 // constant. 1206 if ((NewMask & (KnownZero|KnownOne)) == NewMask) 1207 return TLO.CombineTo(Op, TLO.DAG.getConstant(KnownOne, Op.getValueType())); 1208 1209 return false; 1210} 1211 1212/// computeMaskedBitsForTargetNode - Determine which of the bits specified 1213/// in Mask are known to be either zero or one and return them in the 1214/// KnownZero/KnownOne bitsets. 1215void TargetLowering::computeMaskedBitsForTargetNode(const SDValue Op, 1216 const APInt &Mask, 1217 APInt &KnownZero, 1218 APInt &KnownOne, 1219 const SelectionDAG &DAG, 1220 unsigned Depth) const { 1221 assert((Op.getOpcode() >= ISD::BUILTIN_OP_END || 1222 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 1223 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 1224 Op.getOpcode() == ISD::INTRINSIC_VOID) && 1225 "Should use MaskedValueIsZero if you don't know whether Op" 1226 " is a target node!"); 1227 KnownZero = KnownOne = APInt(Mask.getBitWidth(), 0); 1228} 1229 1230/// ComputeNumSignBitsForTargetNode - This method can be implemented by 1231/// targets that want to expose additional information about sign bits to the 1232/// DAG Combiner. 1233unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDValue Op, 1234 unsigned Depth) const { 1235 assert((Op.getOpcode() >= ISD::BUILTIN_OP_END || 1236 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 1237 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 1238 Op.getOpcode() == ISD::INTRINSIC_VOID) && 1239 "Should use ComputeNumSignBits if you don't know whether Op" 1240 " is a target node!"); 1241 return 1; 1242} 1243 1244 1245/// SimplifySetCC - Try to simplify a setcc built with the specified operands 1246/// and cc. If it is unable to simplify it, return a null SDValue. 1247SDValue 1248TargetLowering::SimplifySetCC(MVT VT, SDValue N0, SDValue N1, 1249 ISD::CondCode Cond, bool foldBooleans, 1250 DAGCombinerInfo &DCI) const { 1251 SelectionDAG &DAG = DCI.DAG; 1252 1253 // These setcc operations always fold. 1254 switch (Cond) { 1255 default: break; 1256 case ISD::SETFALSE: 1257 case ISD::SETFALSE2: return DAG.getConstant(0, VT); 1258 case ISD::SETTRUE: 1259 case ISD::SETTRUE2: return DAG.getConstant(1, VT); 1260 } 1261 1262 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 1263 const APInt &C1 = N1C->getAPIntValue(); 1264 if (isa<ConstantSDNode>(N0.Val)) { 1265 return DAG.FoldSetCC(VT, N0, N1, Cond); 1266 } else { 1267 // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an 1268 // equality comparison, then we're just comparing whether X itself is 1269 // zero. 1270 if (N0.getOpcode() == ISD::SRL && (C1 == 0 || C1 == 1) && 1271 N0.getOperand(0).getOpcode() == ISD::CTLZ && 1272 N0.getOperand(1).getOpcode() == ISD::Constant) { 1273 unsigned ShAmt = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1274 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 1275 ShAmt == Log2_32(N0.getValueType().getSizeInBits())) { 1276 if ((C1 == 0) == (Cond == ISD::SETEQ)) { 1277 // (srl (ctlz x), 5) == 0 -> X != 0 1278 // (srl (ctlz x), 5) != 1 -> X != 0 1279 Cond = ISD::SETNE; 1280 } else { 1281 // (srl (ctlz x), 5) != 0 -> X == 0 1282 // (srl (ctlz x), 5) == 1 -> X == 0 1283 Cond = ISD::SETEQ; 1284 } 1285 SDValue Zero = DAG.getConstant(0, N0.getValueType()); 1286 return DAG.getSetCC(VT, N0.getOperand(0).getOperand(0), 1287 Zero, Cond); 1288 } 1289 } 1290 1291 // If the LHS is a ZERO_EXTEND, perform the comparison on the input. 1292 if (N0.getOpcode() == ISD::ZERO_EXTEND) { 1293 unsigned InSize = N0.getOperand(0).getValueType().getSizeInBits(); 1294 1295 // If the comparison constant has bits in the upper part, the 1296 // zero-extended value could never match. 1297 if (C1.intersects(APInt::getHighBitsSet(C1.getBitWidth(), 1298 C1.getBitWidth() - InSize))) { 1299 switch (Cond) { 1300 case ISD::SETUGT: 1301 case ISD::SETUGE: 1302 case ISD::SETEQ: return DAG.getConstant(0, VT); 1303 case ISD::SETULT: 1304 case ISD::SETULE: 1305 case ISD::SETNE: return DAG.getConstant(1, VT); 1306 case ISD::SETGT: 1307 case ISD::SETGE: 1308 // True if the sign bit of C1 is set. 1309 return DAG.getConstant(C1.isNegative(), VT); 1310 case ISD::SETLT: 1311 case ISD::SETLE: 1312 // True if the sign bit of C1 isn't set. 1313 return DAG.getConstant(C1.isNonNegative(), VT); 1314 default: 1315 break; 1316 } 1317 } 1318 1319 // Otherwise, we can perform the comparison with the low bits. 1320 switch (Cond) { 1321 case ISD::SETEQ: 1322 case ISD::SETNE: 1323 case ISD::SETUGT: 1324 case ISD::SETUGE: 1325 case ISD::SETULT: 1326 case ISD::SETULE: 1327 return DAG.getSetCC(VT, N0.getOperand(0), 1328 DAG.getConstant(APInt(C1).trunc(InSize), 1329 N0.getOperand(0).getValueType()), 1330 Cond); 1331 default: 1332 break; // todo, be more careful with signed comparisons 1333 } 1334 } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1335 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 1336 MVT ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT(); 1337 unsigned ExtSrcTyBits = ExtSrcTy.getSizeInBits(); 1338 MVT ExtDstTy = N0.getValueType(); 1339 unsigned ExtDstTyBits = ExtDstTy.getSizeInBits(); 1340 1341 // If the extended part has any inconsistent bits, it cannot ever 1342 // compare equal. In other words, they have to be all ones or all 1343 // zeros. 1344 APInt ExtBits = 1345 APInt::getHighBitsSet(ExtDstTyBits, ExtDstTyBits - ExtSrcTyBits); 1346 if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits) 1347 return DAG.getConstant(Cond == ISD::SETNE, VT); 1348 1349 SDValue ZextOp; 1350 MVT Op0Ty = N0.getOperand(0).getValueType(); 1351 if (Op0Ty == ExtSrcTy) { 1352 ZextOp = N0.getOperand(0); 1353 } else { 1354 APInt Imm = APInt::getLowBitsSet(ExtDstTyBits, ExtSrcTyBits); 1355 ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0), 1356 DAG.getConstant(Imm, Op0Ty)); 1357 } 1358 if (!DCI.isCalledByLegalizer()) 1359 DCI.AddToWorklist(ZextOp.Val); 1360 // Otherwise, make this a use of a zext. 1361 return DAG.getSetCC(VT, ZextOp, 1362 DAG.getConstant(C1 & APInt::getLowBitsSet( 1363 ExtDstTyBits, 1364 ExtSrcTyBits), 1365 ExtDstTy), 1366 Cond); 1367 } else if ((N1C->isNullValue() || N1C->getAPIntValue() == 1) && 1368 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 1369 1370 // SETCC (SETCC), [0|1], [EQ|NE] -> SETCC 1371 if (N0.getOpcode() == ISD::SETCC) { 1372 bool TrueWhenTrue = (Cond == ISD::SETEQ) ^ (N1C->getValue() != 1); 1373 if (TrueWhenTrue) 1374 return N0; 1375 1376 // Invert the condition. 1377 ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get(); 1378 CC = ISD::getSetCCInverse(CC, 1379 N0.getOperand(0).getValueType().isInteger()); 1380 return DAG.getSetCC(VT, N0.getOperand(0), N0.getOperand(1), CC); 1381 } 1382 1383 if ((N0.getOpcode() == ISD::XOR || 1384 (N0.getOpcode() == ISD::AND && 1385 N0.getOperand(0).getOpcode() == ISD::XOR && 1386 N0.getOperand(1) == N0.getOperand(0).getOperand(1))) && 1387 isa<ConstantSDNode>(N0.getOperand(1)) && 1388 cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue() == 1) { 1389 // If this is (X^1) == 0/1, swap the RHS and eliminate the xor. We 1390 // can only do this if the top bits are known zero. 1391 unsigned BitWidth = N0.getValueSizeInBits(); 1392 if (DAG.MaskedValueIsZero(N0, 1393 APInt::getHighBitsSet(BitWidth, 1394 BitWidth-1))) { 1395 // Okay, get the un-inverted input value. 1396 SDValue Val; 1397 if (N0.getOpcode() == ISD::XOR) 1398 Val = N0.getOperand(0); 1399 else { 1400 assert(N0.getOpcode() == ISD::AND && 1401 N0.getOperand(0).getOpcode() == ISD::XOR); 1402 // ((X^1)&1)^1 -> X & 1 1403 Val = DAG.getNode(ISD::AND, N0.getValueType(), 1404 N0.getOperand(0).getOperand(0), 1405 N0.getOperand(1)); 1406 } 1407 return DAG.getSetCC(VT, Val, N1, 1408 Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ); 1409 } 1410 } 1411 } 1412 1413 APInt MinVal, MaxVal; 1414 unsigned OperandBitSize = N1C->getValueType(0).getSizeInBits(); 1415 if (ISD::isSignedIntSetCC(Cond)) { 1416 MinVal = APInt::getSignedMinValue(OperandBitSize); 1417 MaxVal = APInt::getSignedMaxValue(OperandBitSize); 1418 } else { 1419 MinVal = APInt::getMinValue(OperandBitSize); 1420 MaxVal = APInt::getMaxValue(OperandBitSize); 1421 } 1422 1423 // Canonicalize GE/LE comparisons to use GT/LT comparisons. 1424 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { 1425 if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true 1426 // X >= C0 --> X > (C0-1) 1427 return DAG.getSetCC(VT, N0, DAG.getConstant(C1-1, N1.getValueType()), 1428 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); 1429 } 1430 1431 if (Cond == ISD::SETLE || Cond == ISD::SETULE) { 1432 if (C1 == MaxVal) return DAG.getConstant(1, VT); // X <= MAX --> true 1433 // X <= C0 --> X < (C0+1) 1434 return DAG.getSetCC(VT, N0, DAG.getConstant(C1+1, N1.getValueType()), 1435 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); 1436 } 1437 1438 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal) 1439 return DAG.getConstant(0, VT); // X < MIN --> false 1440 if ((Cond == ISD::SETGE || Cond == ISD::SETUGE) && C1 == MinVal) 1441 return DAG.getConstant(1, VT); // X >= MIN --> true 1442 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal) 1443 return DAG.getConstant(0, VT); // X > MAX --> false 1444 if ((Cond == ISD::SETLE || Cond == ISD::SETULE) && C1 == MaxVal) 1445 return DAG.getConstant(1, VT); // X <= MAX --> true 1446 1447 // Canonicalize setgt X, Min --> setne X, Min 1448 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal) 1449 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 1450 // Canonicalize setlt X, Max --> setne X, Max 1451 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal) 1452 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 1453 1454 // If we have setult X, 1, turn it into seteq X, 0 1455 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1) 1456 return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()), 1457 ISD::SETEQ); 1458 // If we have setugt X, Max-1, turn it into seteq X, Max 1459 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1) 1460 return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()), 1461 ISD::SETEQ); 1462 1463 // If we have "setcc X, C0", check to see if we can shrink the immediate 1464 // by changing cc. 1465 1466 // SETUGT X, SINTMAX -> SETLT X, 0 1467 if (Cond == ISD::SETUGT && OperandBitSize != 1 && 1468 C1 == (~0ULL >> (65-OperandBitSize))) 1469 return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()), 1470 ISD::SETLT); 1471 1472 // FIXME: Implement the rest of these. 1473 1474 // Fold bit comparisons when we can. 1475 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 1476 VT == N0.getValueType() && N0.getOpcode() == ISD::AND) 1477 if (ConstantSDNode *AndRHS = 1478 dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 1479 if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 1480 // Perform the xform if the AND RHS is a single bit. 1481 if (isPowerOf2_64(AndRHS->getValue())) { 1482 return DAG.getNode(ISD::SRL, VT, N0, 1483 DAG.getConstant(Log2_64(AndRHS->getValue()), 1484 getShiftAmountTy())); 1485 } 1486 } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) { 1487 // (X & 8) == 8 --> (X & 8) >> 3 1488 // Perform the xform if C1 is a single bit. 1489 if (C1.isPowerOf2()) { 1490 return DAG.getNode(ISD::SRL, VT, N0, 1491 DAG.getConstant(C1.logBase2(), getShiftAmountTy())); 1492 } 1493 } 1494 } 1495 } 1496 } else if (isa<ConstantSDNode>(N0.Val)) { 1497 // Ensure that the constant occurs on the RHS. 1498 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 1499 } 1500 1501 if (isa<ConstantFPSDNode>(N0.Val)) { 1502 // Constant fold or commute setcc. 1503 SDValue O = DAG.FoldSetCC(VT, N0, N1, Cond); 1504 if (O.Val) return O; 1505 } else if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1.Val)) { 1506 // If the RHS of an FP comparison is a constant, simplify it away in 1507 // some cases. 1508 if (CFP->getValueAPF().isNaN()) { 1509 // If an operand is known to be a nan, we can fold it. 1510 switch (ISD::getUnorderedFlavor(Cond)) { 1511 default: assert(0 && "Unknown flavor!"); 1512 case 0: // Known false. 1513 return DAG.getConstant(0, VT); 1514 case 1: // Known true. 1515 return DAG.getConstant(1, VT); 1516 case 2: // Undefined. 1517 return DAG.getNode(ISD::UNDEF, VT); 1518 } 1519 } 1520 1521 // Otherwise, we know the RHS is not a NaN. Simplify the node to drop the 1522 // constant if knowing that the operand is non-nan is enough. We prefer to 1523 // have SETO(x,x) instead of SETO(x, 0.0) because this avoids having to 1524 // materialize 0.0. 1525 if (Cond == ISD::SETO || Cond == ISD::SETUO) 1526 return DAG.getSetCC(VT, N0, N0, Cond); 1527 } 1528 1529 if (N0 == N1) { 1530 // We can always fold X == X for integer setcc's. 1531 if (N0.getValueType().isInteger()) 1532 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 1533 unsigned UOF = ISD::getUnorderedFlavor(Cond); 1534 if (UOF == 2) // FP operators that are undefined on NaNs. 1535 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 1536 if (UOF == unsigned(ISD::isTrueWhenEqual(Cond))) 1537 return DAG.getConstant(UOF, VT); 1538 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO 1539 // if it is not already. 1540 ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO; 1541 if (NewCond != Cond) 1542 return DAG.getSetCC(VT, N0, N1, NewCond); 1543 } 1544 1545 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 1546 N0.getValueType().isInteger()) { 1547 if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB || 1548 N0.getOpcode() == ISD::XOR) { 1549 // Simplify (X+Y) == (X+Z) --> Y == Z 1550 if (N0.getOpcode() == N1.getOpcode()) { 1551 if (N0.getOperand(0) == N1.getOperand(0)) 1552 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond); 1553 if (N0.getOperand(1) == N1.getOperand(1)) 1554 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond); 1555 if (DAG.isCommutativeBinOp(N0.getOpcode())) { 1556 // If X op Y == Y op X, try other combinations. 1557 if (N0.getOperand(0) == N1.getOperand(1)) 1558 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond); 1559 if (N0.getOperand(1) == N1.getOperand(0)) 1560 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(1), Cond); 1561 } 1562 } 1563 1564 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) { 1565 if (ConstantSDNode *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 1566 // Turn (X+C1) == C2 --> X == C2-C1 1567 if (N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse()) { 1568 return DAG.getSetCC(VT, N0.getOperand(0), 1569 DAG.getConstant(RHSC->getValue()-LHSR->getValue(), 1570 N0.getValueType()), Cond); 1571 } 1572 1573 // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0. 1574 if (N0.getOpcode() == ISD::XOR) 1575 // If we know that all of the inverted bits are zero, don't bother 1576 // performing the inversion. 1577 if (DAG.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getAPIntValue())) 1578 return 1579 DAG.getSetCC(VT, N0.getOperand(0), 1580 DAG.getConstant(LHSR->getAPIntValue() ^ 1581 RHSC->getAPIntValue(), 1582 N0.getValueType()), 1583 Cond); 1584 } 1585 1586 // Turn (C1-X) == C2 --> X == C1-C2 1587 if (ConstantSDNode *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) { 1588 if (N0.getOpcode() == ISD::SUB && N0.Val->hasOneUse()) { 1589 return 1590 DAG.getSetCC(VT, N0.getOperand(1), 1591 DAG.getConstant(SUBC->getAPIntValue() - 1592 RHSC->getAPIntValue(), 1593 N0.getValueType()), 1594 Cond); 1595 } 1596 } 1597 } 1598 1599 // Simplify (X+Z) == X --> Z == 0 1600 if (N0.getOperand(0) == N1) 1601 return DAG.getSetCC(VT, N0.getOperand(1), 1602 DAG.getConstant(0, N0.getValueType()), Cond); 1603 if (N0.getOperand(1) == N1) { 1604 if (DAG.isCommutativeBinOp(N0.getOpcode())) 1605 return DAG.getSetCC(VT, N0.getOperand(0), 1606 DAG.getConstant(0, N0.getValueType()), Cond); 1607 else if (N0.Val->hasOneUse()) { 1608 assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!"); 1609 // (Z-X) == X --> Z == X<<1 1610 SDValue SH = DAG.getNode(ISD::SHL, N1.getValueType(), 1611 N1, 1612 DAG.getConstant(1, getShiftAmountTy())); 1613 if (!DCI.isCalledByLegalizer()) 1614 DCI.AddToWorklist(SH.Val); 1615 return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond); 1616 } 1617 } 1618 } 1619 1620 if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB || 1621 N1.getOpcode() == ISD::XOR) { 1622 // Simplify X == (X+Z) --> Z == 0 1623 if (N1.getOperand(0) == N0) { 1624 return DAG.getSetCC(VT, N1.getOperand(1), 1625 DAG.getConstant(0, N1.getValueType()), Cond); 1626 } else if (N1.getOperand(1) == N0) { 1627 if (DAG.isCommutativeBinOp(N1.getOpcode())) { 1628 return DAG.getSetCC(VT, N1.getOperand(0), 1629 DAG.getConstant(0, N1.getValueType()), Cond); 1630 } else if (N1.Val->hasOneUse()) { 1631 assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!"); 1632 // X == (Z-X) --> X<<1 == Z 1633 SDValue SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0, 1634 DAG.getConstant(1, getShiftAmountTy())); 1635 if (!DCI.isCalledByLegalizer()) 1636 DCI.AddToWorklist(SH.Val); 1637 return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond); 1638 } 1639 } 1640 } 1641 } 1642 1643 // Fold away ALL boolean setcc's. 1644 SDValue Temp; 1645 if (N0.getValueType() == MVT::i1 && foldBooleans) { 1646 switch (Cond) { 1647 default: assert(0 && "Unknown integer setcc!"); 1648 case ISD::SETEQ: // X == Y -> (X^Y)^1 1649 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 1650 N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1)); 1651 if (!DCI.isCalledByLegalizer()) 1652 DCI.AddToWorklist(Temp.Val); 1653 break; 1654 case ISD::SETNE: // X != Y --> (X^Y) 1655 N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 1656 break; 1657 case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> X^1 & Y 1658 case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> X^1 & Y 1659 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 1660 N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp); 1661 if (!DCI.isCalledByLegalizer()) 1662 DCI.AddToWorklist(Temp.Val); 1663 break; 1664 case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> Y^1 & X 1665 case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> Y^1 & X 1666 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 1667 N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp); 1668 if (!DCI.isCalledByLegalizer()) 1669 DCI.AddToWorklist(Temp.Val); 1670 break; 1671 case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> X^1 | Y 1672 case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> X^1 | Y 1673 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 1674 N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp); 1675 if (!DCI.isCalledByLegalizer()) 1676 DCI.AddToWorklist(Temp.Val); 1677 break; 1678 case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> Y^1 | X 1679 case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> Y^1 | X 1680 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 1681 N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp); 1682 break; 1683 } 1684 if (VT != MVT::i1) { 1685 if (!DCI.isCalledByLegalizer()) 1686 DCI.AddToWorklist(N0.Val); 1687 // FIXME: If running after legalize, we probably can't do this. 1688 N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 1689 } 1690 return N0; 1691 } 1692 1693 // Could not fold it. 1694 return SDValue(); 1695} 1696 1697/// isGAPlusOffset - Returns true (and the GlobalValue and the offset) if the 1698/// node is a GlobalAddress + offset. 1699bool TargetLowering::isGAPlusOffset(SDNode *N, GlobalValue* &GA, 1700 int64_t &Offset) const { 1701 if (isa<GlobalAddressSDNode>(N)) { 1702 GlobalAddressSDNode *GASD = cast<GlobalAddressSDNode>(N); 1703 GA = GASD->getGlobal(); 1704 Offset += GASD->getOffset(); 1705 return true; 1706 } 1707 1708 if (N->getOpcode() == ISD::ADD) { 1709 SDValue N1 = N->getOperand(0); 1710 SDValue N2 = N->getOperand(1); 1711 if (isGAPlusOffset(N1.Val, GA, Offset)) { 1712 ConstantSDNode *V = dyn_cast<ConstantSDNode>(N2); 1713 if (V) { 1714 Offset += V->getSignExtended(); 1715 return true; 1716 } 1717 } else if (isGAPlusOffset(N2.Val, GA, Offset)) { 1718 ConstantSDNode *V = dyn_cast<ConstantSDNode>(N1); 1719 if (V) { 1720 Offset += V->getSignExtended(); 1721 return true; 1722 } 1723 } 1724 } 1725 return false; 1726} 1727 1728 1729/// isConsecutiveLoad - Return true if LD (which must be a LoadSDNode) is 1730/// loading 'Bytes' bytes from a location that is 'Dist' units away from the 1731/// location that the 'Base' load is loading from. 1732bool TargetLowering::isConsecutiveLoad(SDNode *LD, SDNode *Base, 1733 unsigned Bytes, int Dist, 1734 const MachineFrameInfo *MFI) const { 1735 if (LD->getOperand(0).Val != Base->getOperand(0).Val) 1736 return false; 1737 MVT VT = LD->getValueType(0); 1738 if (VT.getSizeInBits() / 8 != Bytes) 1739 return false; 1740 1741 SDValue Loc = LD->getOperand(1); 1742 SDValue BaseLoc = Base->getOperand(1); 1743 if (Loc.getOpcode() == ISD::FrameIndex) { 1744 if (BaseLoc.getOpcode() != ISD::FrameIndex) 1745 return false; 1746 int FI = cast<FrameIndexSDNode>(Loc)->getIndex(); 1747 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex(); 1748 int FS = MFI->getObjectSize(FI); 1749 int BFS = MFI->getObjectSize(BFI); 1750 if (FS != BFS || FS != (int)Bytes) return false; 1751 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes); 1752 } 1753 1754 GlobalValue *GV1 = NULL; 1755 GlobalValue *GV2 = NULL; 1756 int64_t Offset1 = 0; 1757 int64_t Offset2 = 0; 1758 bool isGA1 = isGAPlusOffset(Loc.Val, GV1, Offset1); 1759 bool isGA2 = isGAPlusOffset(BaseLoc.Val, GV2, Offset2); 1760 if (isGA1 && isGA2 && GV1 == GV2) 1761 return Offset1 == (Offset2 + Dist*Bytes); 1762 return false; 1763} 1764 1765 1766SDValue TargetLowering:: 1767PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const { 1768 // Default implementation: no optimization. 1769 return SDValue(); 1770} 1771 1772//===----------------------------------------------------------------------===// 1773// Inline Assembler Implementation Methods 1774//===----------------------------------------------------------------------===// 1775 1776 1777TargetLowering::ConstraintType 1778TargetLowering::getConstraintType(const std::string &Constraint) const { 1779 // FIXME: lots more standard ones to handle. 1780 if (Constraint.size() == 1) { 1781 switch (Constraint[0]) { 1782 default: break; 1783 case 'r': return C_RegisterClass; 1784 case 'm': // memory 1785 case 'o': // offsetable 1786 case 'V': // not offsetable 1787 return C_Memory; 1788 case 'i': // Simple Integer or Relocatable Constant 1789 case 'n': // Simple Integer 1790 case 's': // Relocatable Constant 1791 case 'X': // Allow ANY value. 1792 case 'I': // Target registers. 1793 case 'J': 1794 case 'K': 1795 case 'L': 1796 case 'M': 1797 case 'N': 1798 case 'O': 1799 case 'P': 1800 return C_Other; 1801 } 1802 } 1803 1804 if (Constraint.size() > 1 && Constraint[0] == '{' && 1805 Constraint[Constraint.size()-1] == '}') 1806 return C_Register; 1807 return C_Unknown; 1808} 1809 1810/// LowerXConstraint - try to replace an X constraint, which matches anything, 1811/// with another that has more specific requirements based on the type of the 1812/// corresponding operand. 1813const char *TargetLowering::LowerXConstraint(MVT ConstraintVT) const{ 1814 if (ConstraintVT.isInteger()) 1815 return "r"; 1816 if (ConstraintVT.isFloatingPoint()) 1817 return "f"; // works for many targets 1818 return 0; 1819} 1820 1821/// LowerAsmOperandForConstraint - Lower the specified operand into the Ops 1822/// vector. If it is invalid, don't add anything to Ops. 1823void TargetLowering::LowerAsmOperandForConstraint(SDValue Op, 1824 char ConstraintLetter, 1825 std::vector<SDValue> &Ops, 1826 SelectionDAG &DAG) const { 1827 switch (ConstraintLetter) { 1828 default: break; 1829 case 'X': // Allows any operand; labels (basic block) use this. 1830 if (Op.getOpcode() == ISD::BasicBlock) { 1831 Ops.push_back(Op); 1832 return; 1833 } 1834 // fall through 1835 case 'i': // Simple Integer or Relocatable Constant 1836 case 'n': // Simple Integer 1837 case 's': { // Relocatable Constant 1838 // These operands are interested in values of the form (GV+C), where C may 1839 // be folded in as an offset of GV, or it may be explicitly added. Also, it 1840 // is possible and fine if either GV or C are missing. 1841 ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op); 1842 GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op); 1843 1844 // If we have "(add GV, C)", pull out GV/C 1845 if (Op.getOpcode() == ISD::ADD) { 1846 C = dyn_cast<ConstantSDNode>(Op.getOperand(1)); 1847 GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(0)); 1848 if (C == 0 || GA == 0) { 1849 C = dyn_cast<ConstantSDNode>(Op.getOperand(0)); 1850 GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(1)); 1851 } 1852 if (C == 0 || GA == 0) 1853 C = 0, GA = 0; 1854 } 1855 1856 // If we find a valid operand, map to the TargetXXX version so that the 1857 // value itself doesn't get selected. 1858 if (GA) { // Either &GV or &GV+C 1859 if (ConstraintLetter != 'n') { 1860 int64_t Offs = GA->getOffset(); 1861 if (C) Offs += C->getValue(); 1862 Ops.push_back(DAG.getTargetGlobalAddress(GA->getGlobal(), 1863 Op.getValueType(), Offs)); 1864 return; 1865 } 1866 } 1867 if (C) { // just C, no GV. 1868 // Simple constants are not allowed for 's'. 1869 if (ConstraintLetter != 's') { 1870 Ops.push_back(DAG.getTargetConstant(C->getValue(), Op.getValueType())); 1871 return; 1872 } 1873 } 1874 break; 1875 } 1876 } 1877} 1878 1879std::vector<unsigned> TargetLowering:: 1880getRegClassForInlineAsmConstraint(const std::string &Constraint, 1881 MVT VT) const { 1882 return std::vector<unsigned>(); 1883} 1884 1885 1886std::pair<unsigned, const TargetRegisterClass*> TargetLowering:: 1887getRegForInlineAsmConstraint(const std::string &Constraint, 1888 MVT VT) const { 1889 if (Constraint[0] != '{') 1890 return std::pair<unsigned, const TargetRegisterClass*>(0, 0); 1891 assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?"); 1892 1893 // Remove the braces from around the name. 1894 std::string RegName(Constraint.begin()+1, Constraint.end()-1); 1895 1896 // Figure out which register class contains this reg. 1897 const TargetRegisterInfo *RI = TM.getRegisterInfo(); 1898 for (TargetRegisterInfo::regclass_iterator RCI = RI->regclass_begin(), 1899 E = RI->regclass_end(); RCI != E; ++RCI) { 1900 const TargetRegisterClass *RC = *RCI; 1901 1902 // If none of the the value types for this register class are valid, we 1903 // can't use it. For example, 64-bit reg classes on 32-bit targets. 1904 bool isLegal = false; 1905 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end(); 1906 I != E; ++I) { 1907 if (isTypeLegal(*I)) { 1908 isLegal = true; 1909 break; 1910 } 1911 } 1912 1913 if (!isLegal) continue; 1914 1915 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 1916 I != E; ++I) { 1917 if (StringsEqualNoCase(RegName, RI->get(*I).AsmName)) 1918 return std::make_pair(*I, RC); 1919 } 1920 } 1921 1922 return std::pair<unsigned, const TargetRegisterClass*>(0, 0); 1923} 1924 1925//===----------------------------------------------------------------------===// 1926// Constraint Selection. 1927 1928/// getConstraintGenerality - Return an integer indicating how general CT 1929/// is. 1930static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) { 1931 switch (CT) { 1932 default: assert(0 && "Unknown constraint type!"); 1933 case TargetLowering::C_Other: 1934 case TargetLowering::C_Unknown: 1935 return 0; 1936 case TargetLowering::C_Register: 1937 return 1; 1938 case TargetLowering::C_RegisterClass: 1939 return 2; 1940 case TargetLowering::C_Memory: 1941 return 3; 1942 } 1943} 1944 1945/// ChooseConstraint - If there are multiple different constraints that we 1946/// could pick for this operand (e.g. "imr") try to pick the 'best' one. 1947/// This is somewhat tricky: constraints fall into four classes: 1948/// Other -> immediates and magic values 1949/// Register -> one specific register 1950/// RegisterClass -> a group of regs 1951/// Memory -> memory 1952/// Ideally, we would pick the most specific constraint possible: if we have 1953/// something that fits into a register, we would pick it. The problem here 1954/// is that if we have something that could either be in a register or in 1955/// memory that use of the register could cause selection of *other* 1956/// operands to fail: they might only succeed if we pick memory. Because of 1957/// this the heuristic we use is: 1958/// 1959/// 1) If there is an 'other' constraint, and if the operand is valid for 1960/// that constraint, use it. This makes us take advantage of 'i' 1961/// constraints when available. 1962/// 2) Otherwise, pick the most general constraint present. This prefers 1963/// 'm' over 'r', for example. 1964/// 1965static void ChooseConstraint(TargetLowering::AsmOperandInfo &OpInfo, 1966 const TargetLowering &TLI, 1967 SDValue Op, SelectionDAG *DAG) { 1968 assert(OpInfo.Codes.size() > 1 && "Doesn't have multiple constraint options"); 1969 unsigned BestIdx = 0; 1970 TargetLowering::ConstraintType BestType = TargetLowering::C_Unknown; 1971 int BestGenerality = -1; 1972 1973 // Loop over the options, keeping track of the most general one. 1974 for (unsigned i = 0, e = OpInfo.Codes.size(); i != e; ++i) { 1975 TargetLowering::ConstraintType CType = 1976 TLI.getConstraintType(OpInfo.Codes[i]); 1977 1978 // If this is an 'other' constraint, see if the operand is valid for it. 1979 // For example, on X86 we might have an 'rI' constraint. If the operand 1980 // is an integer in the range [0..31] we want to use I (saving a load 1981 // of a register), otherwise we must use 'r'. 1982 if (CType == TargetLowering::C_Other && Op.Val) { 1983 assert(OpInfo.Codes[i].size() == 1 && 1984 "Unhandled multi-letter 'other' constraint"); 1985 std::vector<SDValue> ResultOps; 1986 TLI.LowerAsmOperandForConstraint(Op, OpInfo.Codes[i][0], 1987 ResultOps, *DAG); 1988 if (!ResultOps.empty()) { 1989 BestType = CType; 1990 BestIdx = i; 1991 break; 1992 } 1993 } 1994 1995 // This constraint letter is more general than the previous one, use it. 1996 int Generality = getConstraintGenerality(CType); 1997 if (Generality > BestGenerality) { 1998 BestType = CType; 1999 BestIdx = i; 2000 BestGenerality = Generality; 2001 } 2002 } 2003 2004 OpInfo.ConstraintCode = OpInfo.Codes[BestIdx]; 2005 OpInfo.ConstraintType = BestType; 2006} 2007 2008/// ComputeConstraintToUse - Determines the constraint code and constraint 2009/// type to use for the specific AsmOperandInfo, setting 2010/// OpInfo.ConstraintCode and OpInfo.ConstraintType. 2011void TargetLowering::ComputeConstraintToUse(AsmOperandInfo &OpInfo, 2012 SDValue Op, 2013 SelectionDAG *DAG) const { 2014 assert(!OpInfo.Codes.empty() && "Must have at least one constraint"); 2015 2016 // Single-letter constraints ('r') are very common. 2017 if (OpInfo.Codes.size() == 1) { 2018 OpInfo.ConstraintCode = OpInfo.Codes[0]; 2019 OpInfo.ConstraintType = getConstraintType(OpInfo.ConstraintCode); 2020 } else { 2021 ChooseConstraint(OpInfo, *this, Op, DAG); 2022 } 2023 2024 // 'X' matches anything. 2025 if (OpInfo.ConstraintCode == "X" && OpInfo.CallOperandVal) { 2026 // Labels and constants are handled elsewhere ('X' is the only thing 2027 // that matches labels). 2028 if (isa<BasicBlock>(OpInfo.CallOperandVal) || 2029 isa<ConstantInt>(OpInfo.CallOperandVal)) 2030 return; 2031 2032 // Otherwise, try to resolve it to something we know about by looking at 2033 // the actual operand type. 2034 if (const char *Repl = LowerXConstraint(OpInfo.ConstraintVT)) { 2035 OpInfo.ConstraintCode = Repl; 2036 OpInfo.ConstraintType = getConstraintType(OpInfo.ConstraintCode); 2037 } 2038 } 2039} 2040 2041//===----------------------------------------------------------------------===// 2042// Loop Strength Reduction hooks 2043//===----------------------------------------------------------------------===// 2044 2045/// isLegalAddressingMode - Return true if the addressing mode represented 2046/// by AM is legal for this target, for a load/store of the specified type. 2047bool TargetLowering::isLegalAddressingMode(const AddrMode &AM, 2048 const Type *Ty) const { 2049 // The default implementation of this implements a conservative RISCy, r+r and 2050 // r+i addr mode. 2051 2052 // Allows a sign-extended 16-bit immediate field. 2053 if (AM.BaseOffs <= -(1LL << 16) || AM.BaseOffs >= (1LL << 16)-1) 2054 return false; 2055 2056 // No global is ever allowed as a base. 2057 if (AM.BaseGV) 2058 return false; 2059 2060 // Only support r+r, 2061 switch (AM.Scale) { 2062 case 0: // "r+i" or just "i", depending on HasBaseReg. 2063 break; 2064 case 1: 2065 if (AM.HasBaseReg && AM.BaseOffs) // "r+r+i" is not allowed. 2066 return false; 2067 // Otherwise we have r+r or r+i. 2068 break; 2069 case 2: 2070 if (AM.HasBaseReg || AM.BaseOffs) // 2*r+r or 2*r+i is not allowed. 2071 return false; 2072 // Allow 2*r as r+r. 2073 break; 2074 } 2075 2076 return true; 2077} 2078 2079// Magic for divide replacement 2080 2081struct ms { 2082 int64_t m; // magic number 2083 int64_t s; // shift amount 2084}; 2085 2086struct mu { 2087 uint64_t m; // magic number 2088 int64_t a; // add indicator 2089 int64_t s; // shift amount 2090}; 2091 2092/// magic - calculate the magic numbers required to codegen an integer sdiv as 2093/// a sequence of multiply and shifts. Requires that the divisor not be 0, 1, 2094/// or -1. 2095static ms magic32(int32_t d) { 2096 int32_t p; 2097 uint32_t ad, anc, delta, q1, r1, q2, r2, t; 2098 const uint32_t two31 = 0x80000000U; 2099 struct ms mag; 2100 2101 ad = abs(d); 2102 t = two31 + ((uint32_t)d >> 31); 2103 anc = t - 1 - t%ad; // absolute value of nc 2104 p = 31; // initialize p 2105 q1 = two31/anc; // initialize q1 = 2p/abs(nc) 2106 r1 = two31 - q1*anc; // initialize r1 = rem(2p,abs(nc)) 2107 q2 = two31/ad; // initialize q2 = 2p/abs(d) 2108 r2 = two31 - q2*ad; // initialize r2 = rem(2p,abs(d)) 2109 do { 2110 p = p + 1; 2111 q1 = 2*q1; // update q1 = 2p/abs(nc) 2112 r1 = 2*r1; // update r1 = rem(2p/abs(nc)) 2113 if (r1 >= anc) { // must be unsigned comparison 2114 q1 = q1 + 1; 2115 r1 = r1 - anc; 2116 } 2117 q2 = 2*q2; // update q2 = 2p/abs(d) 2118 r2 = 2*r2; // update r2 = rem(2p/abs(d)) 2119 if (r2 >= ad) { // must be unsigned comparison 2120 q2 = q2 + 1; 2121 r2 = r2 - ad; 2122 } 2123 delta = ad - r2; 2124 } while (q1 < delta || (q1 == delta && r1 == 0)); 2125 2126 mag.m = (int32_t)(q2 + 1); // make sure to sign extend 2127 if (d < 0) mag.m = -mag.m; // resulting magic number 2128 mag.s = p - 32; // resulting shift 2129 return mag; 2130} 2131 2132/// magicu - calculate the magic numbers required to codegen an integer udiv as 2133/// a sequence of multiply, add and shifts. Requires that the divisor not be 0. 2134static mu magicu32(uint32_t d) { 2135 int32_t p; 2136 uint32_t nc, delta, q1, r1, q2, r2; 2137 struct mu magu; 2138 magu.a = 0; // initialize "add" indicator 2139 nc = - 1 - (-d)%d; 2140 p = 31; // initialize p 2141 q1 = 0x80000000/nc; // initialize q1 = 2p/nc 2142 r1 = 0x80000000 - q1*nc; // initialize r1 = rem(2p,nc) 2143 q2 = 0x7FFFFFFF/d; // initialize q2 = (2p-1)/d 2144 r2 = 0x7FFFFFFF - q2*d; // initialize r2 = rem((2p-1),d) 2145 do { 2146 p = p + 1; 2147 if (r1 >= nc - r1 ) { 2148 q1 = 2*q1 + 1; // update q1 2149 r1 = 2*r1 - nc; // update r1 2150 } 2151 else { 2152 q1 = 2*q1; // update q1 2153 r1 = 2*r1; // update r1 2154 } 2155 if (r2 + 1 >= d - r2) { 2156 if (q2 >= 0x7FFFFFFF) magu.a = 1; 2157 q2 = 2*q2 + 1; // update q2 2158 r2 = 2*r2 + 1 - d; // update r2 2159 } 2160 else { 2161 if (q2 >= 0x80000000) magu.a = 1; 2162 q2 = 2*q2; // update q2 2163 r2 = 2*r2 + 1; // update r2 2164 } 2165 delta = d - 1 - r2; 2166 } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0))); 2167 magu.m = q2 + 1; // resulting magic number 2168 magu.s = p - 32; // resulting shift 2169 return magu; 2170} 2171 2172/// magic - calculate the magic numbers required to codegen an integer sdiv as 2173/// a sequence of multiply and shifts. Requires that the divisor not be 0, 1, 2174/// or -1. 2175static ms magic64(int64_t d) { 2176 int64_t p; 2177 uint64_t ad, anc, delta, q1, r1, q2, r2, t; 2178 const uint64_t two63 = 9223372036854775808ULL; // 2^63 2179 struct ms mag; 2180 2181 ad = d >= 0 ? d : -d; 2182 t = two63 + ((uint64_t)d >> 63); 2183 anc = t - 1 - t%ad; // absolute value of nc 2184 p = 63; // initialize p 2185 q1 = two63/anc; // initialize q1 = 2p/abs(nc) 2186 r1 = two63 - q1*anc; // initialize r1 = rem(2p,abs(nc)) 2187 q2 = two63/ad; // initialize q2 = 2p/abs(d) 2188 r2 = two63 - q2*ad; // initialize r2 = rem(2p,abs(d)) 2189 do { 2190 p = p + 1; 2191 q1 = 2*q1; // update q1 = 2p/abs(nc) 2192 r1 = 2*r1; // update r1 = rem(2p/abs(nc)) 2193 if (r1 >= anc) { // must be unsigned comparison 2194 q1 = q1 + 1; 2195 r1 = r1 - anc; 2196 } 2197 q2 = 2*q2; // update q2 = 2p/abs(d) 2198 r2 = 2*r2; // update r2 = rem(2p/abs(d)) 2199 if (r2 >= ad) { // must be unsigned comparison 2200 q2 = q2 + 1; 2201 r2 = r2 - ad; 2202 } 2203 delta = ad - r2; 2204 } while (q1 < delta || (q1 == delta && r1 == 0)); 2205 2206 mag.m = q2 + 1; 2207 if (d < 0) mag.m = -mag.m; // resulting magic number 2208 mag.s = p - 64; // resulting shift 2209 return mag; 2210} 2211 2212/// magicu - calculate the magic numbers required to codegen an integer udiv as 2213/// a sequence of multiply, add and shifts. Requires that the divisor not be 0. 2214static mu magicu64(uint64_t d) 2215{ 2216 int64_t p; 2217 uint64_t nc, delta, q1, r1, q2, r2; 2218 struct mu magu; 2219 magu.a = 0; // initialize "add" indicator 2220 nc = - 1 - (-d)%d; 2221 p = 63; // initialize p 2222 q1 = 0x8000000000000000ull/nc; // initialize q1 = 2p/nc 2223 r1 = 0x8000000000000000ull - q1*nc; // initialize r1 = rem(2p,nc) 2224 q2 = 0x7FFFFFFFFFFFFFFFull/d; // initialize q2 = (2p-1)/d 2225 r2 = 0x7FFFFFFFFFFFFFFFull - q2*d; // initialize r2 = rem((2p-1),d) 2226 do { 2227 p = p + 1; 2228 if (r1 >= nc - r1 ) { 2229 q1 = 2*q1 + 1; // update q1 2230 r1 = 2*r1 - nc; // update r1 2231 } 2232 else { 2233 q1 = 2*q1; // update q1 2234 r1 = 2*r1; // update r1 2235 } 2236 if (r2 + 1 >= d - r2) { 2237 if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1; 2238 q2 = 2*q2 + 1; // update q2 2239 r2 = 2*r2 + 1 - d; // update r2 2240 } 2241 else { 2242 if (q2 >= 0x8000000000000000ull) magu.a = 1; 2243 q2 = 2*q2; // update q2 2244 r2 = 2*r2 + 1; // update r2 2245 } 2246 delta = d - 1 - r2; 2247 } while (p < 128 && (q1 < delta || (q1 == delta && r1 == 0))); 2248 magu.m = q2 + 1; // resulting magic number 2249 magu.s = p - 64; // resulting shift 2250 return magu; 2251} 2252 2253/// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant, 2254/// return a DAG expression to select that will generate the same value by 2255/// multiplying by a magic number. See: 2256/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 2257SDValue TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG, 2258 std::vector<SDNode*>* Created) const { 2259 MVT VT = N->getValueType(0); 2260 2261 // Check to see if we can do this. 2262 if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64)) 2263 return SDValue(); // BuildSDIV only operates on i32 or i64 2264 2265 int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended(); 2266 ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d); 2267 2268 // Multiply the numerator (operand 0) by the magic value 2269 SDValue Q; 2270 if (isOperationLegal(ISD::MULHS, VT)) 2271 Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0), 2272 DAG.getConstant(magics.m, VT)); 2273 else if (isOperationLegal(ISD::SMUL_LOHI, VT)) 2274 Q = SDValue(DAG.getNode(ISD::SMUL_LOHI, DAG.getVTList(VT, VT), 2275 N->getOperand(0), 2276 DAG.getConstant(magics.m, VT)).Val, 1); 2277 else 2278 return SDValue(); // No mulhs or equvialent 2279 // If d > 0 and m < 0, add the numerator 2280 if (d > 0 && magics.m < 0) { 2281 Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0)); 2282 if (Created) 2283 Created->push_back(Q.Val); 2284 } 2285 // If d < 0 and m > 0, subtract the numerator. 2286 if (d < 0 && magics.m > 0) { 2287 Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0)); 2288 if (Created) 2289 Created->push_back(Q.Val); 2290 } 2291 // Shift right algebraic if shift value is nonzero 2292 if (magics.s > 0) { 2293 Q = DAG.getNode(ISD::SRA, VT, Q, 2294 DAG.getConstant(magics.s, getShiftAmountTy())); 2295 if (Created) 2296 Created->push_back(Q.Val); 2297 } 2298 // Extract the sign bit and add it to the quotient 2299 SDValue T = 2300 DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(VT.getSizeInBits()-1, 2301 getShiftAmountTy())); 2302 if (Created) 2303 Created->push_back(T.Val); 2304 return DAG.getNode(ISD::ADD, VT, Q, T); 2305} 2306 2307/// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant, 2308/// return a DAG expression to select that will generate the same value by 2309/// multiplying by a magic number. See: 2310/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 2311SDValue TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG, 2312 std::vector<SDNode*>* Created) const { 2313 MVT VT = N->getValueType(0); 2314 2315 // Check to see if we can do this. 2316 if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64)) 2317 return SDValue(); // BuildUDIV only operates on i32 or i64 2318 2319 uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue(); 2320 mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d); 2321 2322 // Multiply the numerator (operand 0) by the magic value 2323 SDValue Q; 2324 if (isOperationLegal(ISD::MULHU, VT)) 2325 Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0), 2326 DAG.getConstant(magics.m, VT)); 2327 else if (isOperationLegal(ISD::UMUL_LOHI, VT)) 2328 Q = SDValue(DAG.getNode(ISD::UMUL_LOHI, DAG.getVTList(VT, VT), 2329 N->getOperand(0), 2330 DAG.getConstant(magics.m, VT)).Val, 1); 2331 else 2332 return SDValue(); // No mulhu or equvialent 2333 if (Created) 2334 Created->push_back(Q.Val); 2335 2336 if (magics.a == 0) { 2337 return DAG.getNode(ISD::SRL, VT, Q, 2338 DAG.getConstant(magics.s, getShiftAmountTy())); 2339 } else { 2340 SDValue NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q); 2341 if (Created) 2342 Created->push_back(NPQ.Val); 2343 NPQ = DAG.getNode(ISD::SRL, VT, NPQ, 2344 DAG.getConstant(1, getShiftAmountTy())); 2345 if (Created) 2346 Created->push_back(NPQ.Val); 2347 NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q); 2348 if (Created) 2349 Created->push_back(NPQ.Val); 2350 return DAG.getNode(ISD::SRL, VT, NPQ, 2351 DAG.getConstant(magics.s-1, getShiftAmountTy())); 2352 } 2353} 2354