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