1 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===// 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 file implements routines for folding instructions into simpler forms 11 // that do not require creating new instructions. This does constant folding 12 // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either 13 // returning a constant ("and i32 %x, 0" -> "0") or an already existing value 14 // ("and i32 %x, %x" -> "%x"). All operands are assumed to have already been 15 // simplified: This is usually true and assuming it simplifies the logic (if 16 // they have not been simplified then results are correct but maybe suboptimal). 17 // 18 //===----------------------------------------------------------------------===// 19 20 #include "llvm/Analysis/InstructionSimplify.h" 21 #include "llvm/ADT/SetVector.h" 22 #include "llvm/ADT/Statistic.h" 23 #include "llvm/Analysis/AliasAnalysis.h" 24 #include "llvm/Analysis/ConstantFolding.h" 25 #include "llvm/Analysis/MemoryBuiltins.h" 26 #include "llvm/Analysis/ValueTracking.h" 27 #include "llvm/IR/ConstantRange.h" 28 #include "llvm/IR/DataLayout.h" 29 #include "llvm/IR/Dominators.h" 30 #include "llvm/IR/GetElementPtrTypeIterator.h" 31 #include "llvm/IR/GlobalAlias.h" 32 #include "llvm/IR/Operator.h" 33 #include "llvm/IR/PatternMatch.h" 34 #include "llvm/IR/ValueHandle.h" 35 #include <algorithm> 36 using namespace llvm; 37 using namespace llvm::PatternMatch; 38 39 #define DEBUG_TYPE "instsimplify" 40 41 enum { RecursionLimit = 3 }; 42 43 STATISTIC(NumExpand, "Number of expansions"); 44 STATISTIC(NumReassoc, "Number of reassociations"); 45 46 namespace { 47 struct Query { 48 const DataLayout &DL; 49 const TargetLibraryInfo *TLI; 50 const DominatorTree *DT; 51 AssumptionCache *AC; 52 const Instruction *CxtI; 53 54 Query(const DataLayout &DL, const TargetLibraryInfo *tli, 55 const DominatorTree *dt, AssumptionCache *ac = nullptr, 56 const Instruction *cxti = nullptr) 57 : DL(DL), TLI(tli), DT(dt), AC(ac), CxtI(cxti) {} 58 }; 59 } // end anonymous namespace 60 61 static Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned); 62 static Value *SimplifyBinOp(unsigned, Value *, Value *, const Query &, 63 unsigned); 64 static Value *SimplifyFPBinOp(unsigned, Value *, Value *, const FastMathFlags &, 65 const Query &, unsigned); 66 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const Query &, 67 unsigned); 68 static Value *SimplifyOrInst(Value *, Value *, const Query &, unsigned); 69 static Value *SimplifyXorInst(Value *, Value *, const Query &, unsigned); 70 static Value *SimplifyTruncInst(Value *, Type *, const Query &, unsigned); 71 72 /// getFalse - For a boolean type, or a vector of boolean type, return false, or 73 /// a vector with every element false, as appropriate for the type. 74 static Constant *getFalse(Type *Ty) { 75 assert(Ty->getScalarType()->isIntegerTy(1) && 76 "Expected i1 type or a vector of i1!"); 77 return Constant::getNullValue(Ty); 78 } 79 80 /// getTrue - For a boolean type, or a vector of boolean type, return true, or 81 /// a vector with every element true, as appropriate for the type. 82 static Constant *getTrue(Type *Ty) { 83 assert(Ty->getScalarType()->isIntegerTy(1) && 84 "Expected i1 type or a vector of i1!"); 85 return Constant::getAllOnesValue(Ty); 86 } 87 88 /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"? 89 static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS, 90 Value *RHS) { 91 CmpInst *Cmp = dyn_cast<CmpInst>(V); 92 if (!Cmp) 93 return false; 94 CmpInst::Predicate CPred = Cmp->getPredicate(); 95 Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1); 96 if (CPred == Pred && CLHS == LHS && CRHS == RHS) 97 return true; 98 return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS && 99 CRHS == LHS; 100 } 101 102 /// ValueDominatesPHI - Does the given value dominate the specified phi node? 103 static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 104 Instruction *I = dyn_cast<Instruction>(V); 105 if (!I) 106 // Arguments and constants dominate all instructions. 107 return true; 108 109 // If we are processing instructions (and/or basic blocks) that have not been 110 // fully added to a function, the parent nodes may still be null. Simply 111 // return the conservative answer in these cases. 112 if (!I->getParent() || !P->getParent() || !I->getParent()->getParent()) 113 return false; 114 115 // If we have a DominatorTree then do a precise test. 116 if (DT) { 117 if (!DT->isReachableFromEntry(P->getParent())) 118 return true; 119 if (!DT->isReachableFromEntry(I->getParent())) 120 return false; 121 return DT->dominates(I, P); 122 } 123 124 // Otherwise, if the instruction is in the entry block, and is not an invoke, 125 // then it obviously dominates all phi nodes. 126 if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 127 !isa<InvokeInst>(I)) 128 return true; 129 130 return false; 131 } 132 133 /// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning 134 /// it into "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is 135 /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. 136 /// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". 137 /// Returns the simplified value, or null if no simplification was performed. 138 static Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS, 139 unsigned OpcToExpand, const Query &Q, 140 unsigned MaxRecurse) { 141 Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand; 142 // Recursion is always used, so bail out at once if we already hit the limit. 143 if (!MaxRecurse--) 144 return nullptr; 145 146 // Check whether the expression has the form "(A op' B) op C". 147 if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) 148 if (Op0->getOpcode() == OpcodeToExpand) { 149 // It does! Try turning it into "(A op C) op' (B op C)". 150 Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 151 // Do "A op C" and "B op C" both simplify? 152 if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) 153 if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { 154 // They do! Return "L op' R" if it simplifies or is already available. 155 // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. 156 if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand) 157 && L == B && R == A)) { 158 ++NumExpand; 159 return LHS; 160 } 161 // Otherwise return "L op' R" if it simplifies. 162 if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { 163 ++NumExpand; 164 return V; 165 } 166 } 167 } 168 169 // Check whether the expression has the form "A op (B op' C)". 170 if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS)) 171 if (Op1->getOpcode() == OpcodeToExpand) { 172 // It does! Try turning it into "(A op B) op' (A op C)". 173 Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 174 // Do "A op B" and "A op C" both simplify? 175 if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) 176 if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) { 177 // They do! Return "L op' R" if it simplifies or is already available. 178 // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. 179 if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand) 180 && L == C && R == B)) { 181 ++NumExpand; 182 return RHS; 183 } 184 // Otherwise return "L op' R" if it simplifies. 185 if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { 186 ++NumExpand; 187 return V; 188 } 189 } 190 } 191 192 return nullptr; 193 } 194 195 /// SimplifyAssociativeBinOp - Generic simplifications for associative binary 196 /// operations. Returns the simpler value, or null if none was found. 197 static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, 198 const Query &Q, unsigned MaxRecurse) { 199 Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc; 200 assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 201 202 // Recursion is always used, so bail out at once if we already hit the limit. 203 if (!MaxRecurse--) 204 return nullptr; 205 206 BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 207 BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 208 209 // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 210 if (Op0 && Op0->getOpcode() == Opcode) { 211 Value *A = Op0->getOperand(0); 212 Value *B = Op0->getOperand(1); 213 Value *C = RHS; 214 215 // Does "B op C" simplify? 216 if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { 217 // It does! Return "A op V" if it simplifies or is already available. 218 // If V equals B then "A op V" is just the LHS. 219 if (V == B) return LHS; 220 // Otherwise return "A op V" if it simplifies. 221 if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) { 222 ++NumReassoc; 223 return W; 224 } 225 } 226 } 227 228 // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 229 if (Op1 && Op1->getOpcode() == Opcode) { 230 Value *A = LHS; 231 Value *B = Op1->getOperand(0); 232 Value *C = Op1->getOperand(1); 233 234 // Does "A op B" simplify? 235 if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) { 236 // It does! Return "V op C" if it simplifies or is already available. 237 // If V equals B then "V op C" is just the RHS. 238 if (V == B) return RHS; 239 // Otherwise return "V op C" if it simplifies. 240 if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) { 241 ++NumReassoc; 242 return W; 243 } 244 } 245 } 246 247 // The remaining transforms require commutativity as well as associativity. 248 if (!Instruction::isCommutative(Opcode)) 249 return nullptr; 250 251 // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 252 if (Op0 && Op0->getOpcode() == Opcode) { 253 Value *A = Op0->getOperand(0); 254 Value *B = Op0->getOperand(1); 255 Value *C = RHS; 256 257 // Does "C op A" simplify? 258 if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) { 259 // It does! Return "V op B" if it simplifies or is already available. 260 // If V equals A then "V op B" is just the LHS. 261 if (V == A) return LHS; 262 // Otherwise return "V op B" if it simplifies. 263 if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) { 264 ++NumReassoc; 265 return W; 266 } 267 } 268 } 269 270 // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 271 if (Op1 && Op1->getOpcode() == Opcode) { 272 Value *A = LHS; 273 Value *B = Op1->getOperand(0); 274 Value *C = Op1->getOperand(1); 275 276 // Does "C op A" simplify? 277 if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) { 278 // It does! Return "B op V" if it simplifies or is already available. 279 // If V equals C then "B op V" is just the RHS. 280 if (V == C) return RHS; 281 // Otherwise return "B op V" if it simplifies. 282 if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) { 283 ++NumReassoc; 284 return W; 285 } 286 } 287 } 288 289 return nullptr; 290 } 291 292 /// ThreadBinOpOverSelect - In the case of a binary operation with a select 293 /// instruction as an operand, try to simplify the binop by seeing whether 294 /// evaluating it on both branches of the select results in the same value. 295 /// Returns the common value if so, otherwise returns null. 296 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 297 const Query &Q, unsigned MaxRecurse) { 298 // Recursion is always used, so bail out at once if we already hit the limit. 299 if (!MaxRecurse--) 300 return nullptr; 301 302 SelectInst *SI; 303 if (isa<SelectInst>(LHS)) { 304 SI = cast<SelectInst>(LHS); 305 } else { 306 assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 307 SI = cast<SelectInst>(RHS); 308 } 309 310 // Evaluate the BinOp on the true and false branches of the select. 311 Value *TV; 312 Value *FV; 313 if (SI == LHS) { 314 TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse); 315 FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse); 316 } else { 317 TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse); 318 FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse); 319 } 320 321 // If they simplified to the same value, then return the common value. 322 // If they both failed to simplify then return null. 323 if (TV == FV) 324 return TV; 325 326 // If one branch simplified to undef, return the other one. 327 if (TV && isa<UndefValue>(TV)) 328 return FV; 329 if (FV && isa<UndefValue>(FV)) 330 return TV; 331 332 // If applying the operation did not change the true and false select values, 333 // then the result of the binop is the select itself. 334 if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 335 return SI; 336 337 // If one branch simplified and the other did not, and the simplified 338 // value is equal to the unsimplified one, return the simplified value. 339 // For example, select (cond, X, X & Z) & Z -> X & Z. 340 if ((FV && !TV) || (TV && !FV)) { 341 // Check that the simplified value has the form "X op Y" where "op" is the 342 // same as the original operation. 343 Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 344 if (Simplified && Simplified->getOpcode() == Opcode) { 345 // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 346 // We already know that "op" is the same as for the simplified value. See 347 // if the operands match too. If so, return the simplified value. 348 Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 349 Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 350 Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 351 if (Simplified->getOperand(0) == UnsimplifiedLHS && 352 Simplified->getOperand(1) == UnsimplifiedRHS) 353 return Simplified; 354 if (Simplified->isCommutative() && 355 Simplified->getOperand(1) == UnsimplifiedLHS && 356 Simplified->getOperand(0) == UnsimplifiedRHS) 357 return Simplified; 358 } 359 } 360 361 return nullptr; 362 } 363 364 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 365 /// try to simplify the comparison by seeing whether both branches of the select 366 /// result in the same value. Returns the common value if so, otherwise returns 367 /// null. 368 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 369 Value *RHS, const Query &Q, 370 unsigned MaxRecurse) { 371 // Recursion is always used, so bail out at once if we already hit the limit. 372 if (!MaxRecurse--) 373 return nullptr; 374 375 // Make sure the select is on the LHS. 376 if (!isa<SelectInst>(LHS)) { 377 std::swap(LHS, RHS); 378 Pred = CmpInst::getSwappedPredicate(Pred); 379 } 380 assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 381 SelectInst *SI = cast<SelectInst>(LHS); 382 Value *Cond = SI->getCondition(); 383 Value *TV = SI->getTrueValue(); 384 Value *FV = SI->getFalseValue(); 385 386 // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it. 387 // Does "cmp TV, RHS" simplify? 388 Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse); 389 if (TCmp == Cond) { 390 // It not only simplified, it simplified to the select condition. Replace 391 // it with 'true'. 392 TCmp = getTrue(Cond->getType()); 393 } else if (!TCmp) { 394 // It didn't simplify. However if "cmp TV, RHS" is equal to the select 395 // condition then we can replace it with 'true'. Otherwise give up. 396 if (!isSameCompare(Cond, Pred, TV, RHS)) 397 return nullptr; 398 TCmp = getTrue(Cond->getType()); 399 } 400 401 // Does "cmp FV, RHS" simplify? 402 Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse); 403 if (FCmp == Cond) { 404 // It not only simplified, it simplified to the select condition. Replace 405 // it with 'false'. 406 FCmp = getFalse(Cond->getType()); 407 } else if (!FCmp) { 408 // It didn't simplify. However if "cmp FV, RHS" is equal to the select 409 // condition then we can replace it with 'false'. Otherwise give up. 410 if (!isSameCompare(Cond, Pred, FV, RHS)) 411 return nullptr; 412 FCmp = getFalse(Cond->getType()); 413 } 414 415 // If both sides simplified to the same value, then use it as the result of 416 // the original comparison. 417 if (TCmp == FCmp) 418 return TCmp; 419 420 // The remaining cases only make sense if the select condition has the same 421 // type as the result of the comparison, so bail out if this is not so. 422 if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy()) 423 return nullptr; 424 // If the false value simplified to false, then the result of the compare 425 // is equal to "Cond && TCmp". This also catches the case when the false 426 // value simplified to false and the true value to true, returning "Cond". 427 if (match(FCmp, m_Zero())) 428 if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse)) 429 return V; 430 // If the true value simplified to true, then the result of the compare 431 // is equal to "Cond || FCmp". 432 if (match(TCmp, m_One())) 433 if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse)) 434 return V; 435 // Finally, if the false value simplified to true and the true value to 436 // false, then the result of the compare is equal to "!Cond". 437 if (match(FCmp, m_One()) && match(TCmp, m_Zero())) 438 if (Value *V = 439 SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()), 440 Q, MaxRecurse)) 441 return V; 442 443 return nullptr; 444 } 445 446 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 447 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating 448 /// it on the incoming phi values yields the same result for every value. If so 449 /// returns the common value, otherwise returns null. 450 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 451 const Query &Q, unsigned MaxRecurse) { 452 // Recursion is always used, so bail out at once if we already hit the limit. 453 if (!MaxRecurse--) 454 return nullptr; 455 456 PHINode *PI; 457 if (isa<PHINode>(LHS)) { 458 PI = cast<PHINode>(LHS); 459 // Bail out if RHS and the phi may be mutually interdependent due to a loop. 460 if (!ValueDominatesPHI(RHS, PI, Q.DT)) 461 return nullptr; 462 } else { 463 assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 464 PI = cast<PHINode>(RHS); 465 // Bail out if LHS and the phi may be mutually interdependent due to a loop. 466 if (!ValueDominatesPHI(LHS, PI, Q.DT)) 467 return nullptr; 468 } 469 470 // Evaluate the BinOp on the incoming phi values. 471 Value *CommonValue = nullptr; 472 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 473 Value *Incoming = PI->getIncomingValue(i); 474 // If the incoming value is the phi node itself, it can safely be skipped. 475 if (Incoming == PI) continue; 476 Value *V = PI == LHS ? 477 SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) : 478 SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse); 479 // If the operation failed to simplify, or simplified to a different value 480 // to previously, then give up. 481 if (!V || (CommonValue && V != CommonValue)) 482 return nullptr; 483 CommonValue = V; 484 } 485 486 return CommonValue; 487 } 488 489 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 490 /// try to simplify the comparison by seeing whether comparing with all of the 491 /// incoming phi values yields the same result every time. If so returns the 492 /// common result, otherwise returns null. 493 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 494 const Query &Q, unsigned MaxRecurse) { 495 // Recursion is always used, so bail out at once if we already hit the limit. 496 if (!MaxRecurse--) 497 return nullptr; 498 499 // Make sure the phi is on the LHS. 500 if (!isa<PHINode>(LHS)) { 501 std::swap(LHS, RHS); 502 Pred = CmpInst::getSwappedPredicate(Pred); 503 } 504 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 505 PHINode *PI = cast<PHINode>(LHS); 506 507 // Bail out if RHS and the phi may be mutually interdependent due to a loop. 508 if (!ValueDominatesPHI(RHS, PI, Q.DT)) 509 return nullptr; 510 511 // Evaluate the BinOp on the incoming phi values. 512 Value *CommonValue = nullptr; 513 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 514 Value *Incoming = PI->getIncomingValue(i); 515 // If the incoming value is the phi node itself, it can safely be skipped. 516 if (Incoming == PI) continue; 517 Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse); 518 // If the operation failed to simplify, or simplified to a different value 519 // to previously, then give up. 520 if (!V || (CommonValue && V != CommonValue)) 521 return nullptr; 522 CommonValue = V; 523 } 524 525 return CommonValue; 526 } 527 528 /// SimplifyAddInst - Given operands for an Add, see if we can 529 /// fold the result. If not, this returns null. 530 static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 531 const Query &Q, unsigned MaxRecurse) { 532 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 533 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 534 Constant *Ops[] = { CLHS, CRHS }; 535 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), Ops, 536 Q.DL, Q.TLI); 537 } 538 539 // Canonicalize the constant to the RHS. 540 std::swap(Op0, Op1); 541 } 542 543 // X + undef -> undef 544 if (match(Op1, m_Undef())) 545 return Op1; 546 547 // X + 0 -> X 548 if (match(Op1, m_Zero())) 549 return Op0; 550 551 // X + (Y - X) -> Y 552 // (Y - X) + X -> Y 553 // Eg: X + -X -> 0 554 Value *Y = nullptr; 555 if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 556 match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 557 return Y; 558 559 // X + ~X -> -1 since ~X = -X-1 560 if (match(Op0, m_Not(m_Specific(Op1))) || 561 match(Op1, m_Not(m_Specific(Op0)))) 562 return Constant::getAllOnesValue(Op0->getType()); 563 564 /// i1 add -> xor. 565 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 566 if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) 567 return V; 568 569 // Try some generic simplifications for associative operations. 570 if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q, 571 MaxRecurse)) 572 return V; 573 574 // Threading Add over selects and phi nodes is pointless, so don't bother. 575 // Threading over the select in "A + select(cond, B, C)" means evaluating 576 // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 577 // only if B and C are equal. If B and C are equal then (since we assume 578 // that operands have already been simplified) "select(cond, B, C)" should 579 // have been simplified to the common value of B and C already. Analysing 580 // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 581 // for threading over phi nodes. 582 583 return nullptr; 584 } 585 586 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 587 const DataLayout &DL, const TargetLibraryInfo *TLI, 588 const DominatorTree *DT, AssumptionCache *AC, 589 const Instruction *CxtI) { 590 return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), 591 RecursionLimit); 592 } 593 594 /// \brief Compute the base pointer and cumulative constant offsets for V. 595 /// 596 /// This strips all constant offsets off of V, leaving it the base pointer, and 597 /// accumulates the total constant offset applied in the returned constant. It 598 /// returns 0 if V is not a pointer, and returns the constant '0' if there are 599 /// no constant offsets applied. 600 /// 601 /// This is very similar to GetPointerBaseWithConstantOffset except it doesn't 602 /// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc. 603 /// folding. 604 static Constant *stripAndComputeConstantOffsets(const DataLayout &DL, Value *&V, 605 bool AllowNonInbounds = false) { 606 assert(V->getType()->getScalarType()->isPointerTy()); 607 608 Type *IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType(); 609 APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth()); 610 611 // Even though we don't look through PHI nodes, we could be called on an 612 // instruction in an unreachable block, which may be on a cycle. 613 SmallPtrSet<Value *, 4> Visited; 614 Visited.insert(V); 615 do { 616 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 617 if ((!AllowNonInbounds && !GEP->isInBounds()) || 618 !GEP->accumulateConstantOffset(DL, Offset)) 619 break; 620 V = GEP->getPointerOperand(); 621 } else if (Operator::getOpcode(V) == Instruction::BitCast) { 622 V = cast<Operator>(V)->getOperand(0); 623 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 624 if (GA->mayBeOverridden()) 625 break; 626 V = GA->getAliasee(); 627 } else { 628 break; 629 } 630 assert(V->getType()->getScalarType()->isPointerTy() && 631 "Unexpected operand type!"); 632 } while (Visited.insert(V).second); 633 634 Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset); 635 if (V->getType()->isVectorTy()) 636 return ConstantVector::getSplat(V->getType()->getVectorNumElements(), 637 OffsetIntPtr); 638 return OffsetIntPtr; 639 } 640 641 /// \brief Compute the constant difference between two pointer values. 642 /// If the difference is not a constant, returns zero. 643 static Constant *computePointerDifference(const DataLayout &DL, Value *LHS, 644 Value *RHS) { 645 Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); 646 Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); 647 648 // If LHS and RHS are not related via constant offsets to the same base 649 // value, there is nothing we can do here. 650 if (LHS != RHS) 651 return nullptr; 652 653 // Otherwise, the difference of LHS - RHS can be computed as: 654 // LHS - RHS 655 // = (LHSOffset + Base) - (RHSOffset + Base) 656 // = LHSOffset - RHSOffset 657 return ConstantExpr::getSub(LHSOffset, RHSOffset); 658 } 659 660 /// SimplifySubInst - Given operands for a Sub, see if we can 661 /// fold the result. If not, this returns null. 662 static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 663 const Query &Q, unsigned MaxRecurse) { 664 if (Constant *CLHS = dyn_cast<Constant>(Op0)) 665 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 666 Constant *Ops[] = { CLHS, CRHS }; 667 return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 668 Ops, Q.DL, Q.TLI); 669 } 670 671 // X - undef -> undef 672 // undef - X -> undef 673 if (match(Op0, m_Undef()) || match(Op1, m_Undef())) 674 return UndefValue::get(Op0->getType()); 675 676 // X - 0 -> X 677 if (match(Op1, m_Zero())) 678 return Op0; 679 680 // X - X -> 0 681 if (Op0 == Op1) 682 return Constant::getNullValue(Op0->getType()); 683 684 // 0 - X -> 0 if the sub is NUW. 685 if (isNUW && match(Op0, m_Zero())) 686 return Op0; 687 688 // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. 689 // For example, (X + Y) - Y -> X; (Y + X) - Y -> X 690 Value *X = nullptr, *Y = nullptr, *Z = Op1; 691 if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z 692 // See if "V === Y - Z" simplifies. 693 if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1)) 694 // It does! Now see if "X + V" simplifies. 695 if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) { 696 // It does, we successfully reassociated! 697 ++NumReassoc; 698 return W; 699 } 700 // See if "V === X - Z" simplifies. 701 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1)) 702 // It does! Now see if "Y + V" simplifies. 703 if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) { 704 // It does, we successfully reassociated! 705 ++NumReassoc; 706 return W; 707 } 708 } 709 710 // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies. 711 // For example, X - (X + 1) -> -1 712 X = Op0; 713 if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z) 714 // See if "V === X - Y" simplifies. 715 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1)) 716 // It does! Now see if "V - Z" simplifies. 717 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) { 718 // It does, we successfully reassociated! 719 ++NumReassoc; 720 return W; 721 } 722 // See if "V === X - Z" simplifies. 723 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1)) 724 // It does! Now see if "V - Y" simplifies. 725 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) { 726 // It does, we successfully reassociated! 727 ++NumReassoc; 728 return W; 729 } 730 } 731 732 // Z - (X - Y) -> (Z - X) + Y if everything simplifies. 733 // For example, X - (X - Y) -> Y. 734 Z = Op0; 735 if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y) 736 // See if "V === Z - X" simplifies. 737 if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1)) 738 // It does! Now see if "V + Y" simplifies. 739 if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) { 740 // It does, we successfully reassociated! 741 ++NumReassoc; 742 return W; 743 } 744 745 // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies. 746 if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) && 747 match(Op1, m_Trunc(m_Value(Y)))) 748 if (X->getType() == Y->getType()) 749 // See if "V === X - Y" simplifies. 750 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1)) 751 // It does! Now see if "trunc V" simplifies. 752 if (Value *W = SimplifyTruncInst(V, Op0->getType(), Q, MaxRecurse-1)) 753 // It does, return the simplified "trunc V". 754 return W; 755 756 // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...). 757 if (match(Op0, m_PtrToInt(m_Value(X))) && 758 match(Op1, m_PtrToInt(m_Value(Y)))) 759 if (Constant *Result = computePointerDifference(Q.DL, X, Y)) 760 return ConstantExpr::getIntegerCast(Result, Op0->getType(), true); 761 762 // i1 sub -> xor. 763 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 764 if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) 765 return V; 766 767 // Threading Sub over selects and phi nodes is pointless, so don't bother. 768 // Threading over the select in "A - select(cond, B, C)" means evaluating 769 // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 770 // only if B and C are equal. If B and C are equal then (since we assume 771 // that operands have already been simplified) "select(cond, B, C)" should 772 // have been simplified to the common value of B and C already. Analysing 773 // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 774 // for threading over phi nodes. 775 776 return nullptr; 777 } 778 779 Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 780 const DataLayout &DL, const TargetLibraryInfo *TLI, 781 const DominatorTree *DT, AssumptionCache *AC, 782 const Instruction *CxtI) { 783 return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), 784 RecursionLimit); 785 } 786 787 /// Given operands for an FAdd, see if we can fold the result. If not, this 788 /// returns null. 789 static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, 790 const Query &Q, unsigned MaxRecurse) { 791 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 792 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 793 Constant *Ops[] = { CLHS, CRHS }; 794 return ConstantFoldInstOperands(Instruction::FAdd, CLHS->getType(), 795 Ops, Q.DL, Q.TLI); 796 } 797 798 // Canonicalize the constant to the RHS. 799 std::swap(Op0, Op1); 800 } 801 802 // fadd X, -0 ==> X 803 if (match(Op1, m_NegZero())) 804 return Op0; 805 806 // fadd X, 0 ==> X, when we know X is not -0 807 if (match(Op1, m_Zero()) && 808 (FMF.noSignedZeros() || CannotBeNegativeZero(Op0))) 809 return Op0; 810 811 // fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0 812 // where nnan and ninf have to occur at least once somewhere in this 813 // expression 814 Value *SubOp = nullptr; 815 if (match(Op1, m_FSub(m_AnyZero(), m_Specific(Op0)))) 816 SubOp = Op1; 817 else if (match(Op0, m_FSub(m_AnyZero(), m_Specific(Op1)))) 818 SubOp = Op0; 819 if (SubOp) { 820 Instruction *FSub = cast<Instruction>(SubOp); 821 if ((FMF.noNaNs() || FSub->hasNoNaNs()) && 822 (FMF.noInfs() || FSub->hasNoInfs())) 823 return Constant::getNullValue(Op0->getType()); 824 } 825 826 return nullptr; 827 } 828 829 /// Given operands for an FSub, see if we can fold the result. If not, this 830 /// returns null. 831 static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, 832 const Query &Q, unsigned MaxRecurse) { 833 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 834 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 835 Constant *Ops[] = { CLHS, CRHS }; 836 return ConstantFoldInstOperands(Instruction::FSub, CLHS->getType(), 837 Ops, Q.DL, Q.TLI); 838 } 839 } 840 841 // fsub X, 0 ==> X 842 if (match(Op1, m_Zero())) 843 return Op0; 844 845 // fsub X, -0 ==> X, when we know X is not -0 846 if (match(Op1, m_NegZero()) && 847 (FMF.noSignedZeros() || CannotBeNegativeZero(Op0))) 848 return Op0; 849 850 // fsub 0, (fsub -0.0, X) ==> X 851 Value *X; 852 if (match(Op0, m_AnyZero())) { 853 if (match(Op1, m_FSub(m_NegZero(), m_Value(X)))) 854 return X; 855 if (FMF.noSignedZeros() && match(Op1, m_FSub(m_AnyZero(), m_Value(X)))) 856 return X; 857 } 858 859 // fsub nnan ninf x, x ==> 0.0 860 if (FMF.noNaNs() && FMF.noInfs() && Op0 == Op1) 861 return Constant::getNullValue(Op0->getType()); 862 863 return nullptr; 864 } 865 866 /// Given the operands for an FMul, see if we can fold the result 867 static Value *SimplifyFMulInst(Value *Op0, Value *Op1, 868 FastMathFlags FMF, 869 const Query &Q, 870 unsigned MaxRecurse) { 871 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 872 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 873 Constant *Ops[] = { CLHS, CRHS }; 874 return ConstantFoldInstOperands(Instruction::FMul, CLHS->getType(), 875 Ops, Q.DL, Q.TLI); 876 } 877 878 // Canonicalize the constant to the RHS. 879 std::swap(Op0, Op1); 880 } 881 882 // fmul X, 1.0 ==> X 883 if (match(Op1, m_FPOne())) 884 return Op0; 885 886 // fmul nnan nsz X, 0 ==> 0 887 if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZero())) 888 return Op1; 889 890 return nullptr; 891 } 892 893 /// SimplifyMulInst - Given operands for a Mul, see if we can 894 /// fold the result. If not, this returns null. 895 static Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q, 896 unsigned MaxRecurse) { 897 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 898 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 899 Constant *Ops[] = { CLHS, CRHS }; 900 return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 901 Ops, Q.DL, Q.TLI); 902 } 903 904 // Canonicalize the constant to the RHS. 905 std::swap(Op0, Op1); 906 } 907 908 // X * undef -> 0 909 if (match(Op1, m_Undef())) 910 return Constant::getNullValue(Op0->getType()); 911 912 // X * 0 -> 0 913 if (match(Op1, m_Zero())) 914 return Op1; 915 916 // X * 1 -> X 917 if (match(Op1, m_One())) 918 return Op0; 919 920 // (X / Y) * Y -> X if the division is exact. 921 Value *X = nullptr; 922 if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y 923 match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0))))) // Y * (X / Y) 924 return X; 925 926 // i1 mul -> and. 927 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 928 if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1)) 929 return V; 930 931 // Try some generic simplifications for associative operations. 932 if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q, 933 MaxRecurse)) 934 return V; 935 936 // Mul distributes over Add. Try some generic simplifications based on this. 937 if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 938 Q, MaxRecurse)) 939 return V; 940 941 // If the operation is with the result of a select instruction, check whether 942 // operating on either branch of the select always yields the same value. 943 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 944 if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q, 945 MaxRecurse)) 946 return V; 947 948 // If the operation is with the result of a phi instruction, check whether 949 // operating on all incoming values of the phi always yields the same value. 950 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 951 if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q, 952 MaxRecurse)) 953 return V; 954 955 return nullptr; 956 } 957 958 Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, 959 const DataLayout &DL, 960 const TargetLibraryInfo *TLI, 961 const DominatorTree *DT, AssumptionCache *AC, 962 const Instruction *CxtI) { 963 return ::SimplifyFAddInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 964 RecursionLimit); 965 } 966 967 Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, 968 const DataLayout &DL, 969 const TargetLibraryInfo *TLI, 970 const DominatorTree *DT, AssumptionCache *AC, 971 const Instruction *CxtI) { 972 return ::SimplifyFSubInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 973 RecursionLimit); 974 } 975 976 Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF, 977 const DataLayout &DL, 978 const TargetLibraryInfo *TLI, 979 const DominatorTree *DT, AssumptionCache *AC, 980 const Instruction *CxtI) { 981 return ::SimplifyFMulInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 982 RecursionLimit); 983 } 984 985 Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout &DL, 986 const TargetLibraryInfo *TLI, 987 const DominatorTree *DT, AssumptionCache *AC, 988 const Instruction *CxtI) { 989 return ::SimplifyMulInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 990 RecursionLimit); 991 } 992 993 /// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can 994 /// fold the result. If not, this returns null. 995 static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 996 const Query &Q, unsigned MaxRecurse) { 997 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 998 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 999 Constant *Ops[] = { C0, C1 }; 1000 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 1001 } 1002 } 1003 1004 bool isSigned = Opcode == Instruction::SDiv; 1005 1006 // X / undef -> undef 1007 if (match(Op1, m_Undef())) 1008 return Op1; 1009 1010 // X / 0 -> undef, we don't need to preserve faults! 1011 if (match(Op1, m_Zero())) 1012 return UndefValue::get(Op1->getType()); 1013 1014 // undef / X -> 0 1015 if (match(Op0, m_Undef())) 1016 return Constant::getNullValue(Op0->getType()); 1017 1018 // 0 / X -> 0, we don't need to preserve faults! 1019 if (match(Op0, m_Zero())) 1020 return Op0; 1021 1022 // X / 1 -> X 1023 if (match(Op1, m_One())) 1024 return Op0; 1025 1026 if (Op0->getType()->isIntegerTy(1)) 1027 // It can't be division by zero, hence it must be division by one. 1028 return Op0; 1029 1030 // X / X -> 1 1031 if (Op0 == Op1) 1032 return ConstantInt::get(Op0->getType(), 1); 1033 1034 // (X * Y) / Y -> X if the multiplication does not overflow. 1035 Value *X = nullptr, *Y = nullptr; 1036 if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { 1037 if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 1038 OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0); 1039 // If the Mul knows it does not overflow, then we are good to go. 1040 if ((isSigned && Mul->hasNoSignedWrap()) || 1041 (!isSigned && Mul->hasNoUnsignedWrap())) 1042 return X; 1043 // If X has the form X = A / Y then X * Y cannot overflow. 1044 if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X)) 1045 if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) 1046 return X; 1047 } 1048 1049 // (X rem Y) / Y -> 0 1050 if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 1051 (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 1052 return Constant::getNullValue(Op0->getType()); 1053 1054 // (X /u C1) /u C2 -> 0 if C1 * C2 overflow 1055 ConstantInt *C1, *C2; 1056 if (!isSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) && 1057 match(Op1, m_ConstantInt(C2))) { 1058 bool Overflow; 1059 C1->getValue().umul_ov(C2->getValue(), Overflow); 1060 if (Overflow) 1061 return Constant::getNullValue(Op0->getType()); 1062 } 1063 1064 // If the operation is with the result of a select instruction, check whether 1065 // operating on either branch of the select always yields the same value. 1066 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1067 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1068 return V; 1069 1070 // If the operation is with the result of a phi instruction, check whether 1071 // operating on all incoming values of the phi always yields the same value. 1072 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1073 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1074 return V; 1075 1076 return nullptr; 1077 } 1078 1079 /// SimplifySDivInst - Given operands for an SDiv, see if we can 1080 /// fold the result. If not, this returns null. 1081 static Value *SimplifySDivInst(Value *Op0, Value *Op1, const Query &Q, 1082 unsigned MaxRecurse) { 1083 if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse)) 1084 return V; 1085 1086 return nullptr; 1087 } 1088 1089 Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout &DL, 1090 const TargetLibraryInfo *TLI, 1091 const DominatorTree *DT, AssumptionCache *AC, 1092 const Instruction *CxtI) { 1093 return ::SimplifySDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1094 RecursionLimit); 1095 } 1096 1097 /// SimplifyUDivInst - Given operands for a UDiv, see if we can 1098 /// fold the result. If not, this returns null. 1099 static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const Query &Q, 1100 unsigned MaxRecurse) { 1101 if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse)) 1102 return V; 1103 1104 return nullptr; 1105 } 1106 1107 Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout &DL, 1108 const TargetLibraryInfo *TLI, 1109 const DominatorTree *DT, AssumptionCache *AC, 1110 const Instruction *CxtI) { 1111 return ::SimplifyUDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1112 RecursionLimit); 1113 } 1114 1115 static Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF, 1116 const Query &Q, unsigned) { 1117 // undef / X -> undef (the undef could be a snan). 1118 if (match(Op0, m_Undef())) 1119 return Op0; 1120 1121 // X / undef -> undef 1122 if (match(Op1, m_Undef())) 1123 return Op1; 1124 1125 // 0 / X -> 0 1126 // Requires that NaNs are off (X could be zero) and signed zeroes are 1127 // ignored (X could be positive or negative, so the output sign is unknown). 1128 if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero())) 1129 return Op0; 1130 1131 return nullptr; 1132 } 1133 1134 Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF, 1135 const DataLayout &DL, 1136 const TargetLibraryInfo *TLI, 1137 const DominatorTree *DT, AssumptionCache *AC, 1138 const Instruction *CxtI) { 1139 return ::SimplifyFDivInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 1140 RecursionLimit); 1141 } 1142 1143 /// SimplifyRem - Given operands for an SRem or URem, see if we can 1144 /// fold the result. If not, this returns null. 1145 static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 1146 const Query &Q, unsigned MaxRecurse) { 1147 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1148 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1149 Constant *Ops[] = { C0, C1 }; 1150 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 1151 } 1152 } 1153 1154 // X % undef -> undef 1155 if (match(Op1, m_Undef())) 1156 return Op1; 1157 1158 // undef % X -> 0 1159 if (match(Op0, m_Undef())) 1160 return Constant::getNullValue(Op0->getType()); 1161 1162 // 0 % X -> 0, we don't need to preserve faults! 1163 if (match(Op0, m_Zero())) 1164 return Op0; 1165 1166 // X % 0 -> undef, we don't need to preserve faults! 1167 if (match(Op1, m_Zero())) 1168 return UndefValue::get(Op0->getType()); 1169 1170 // X % 1 -> 0 1171 if (match(Op1, m_One())) 1172 return Constant::getNullValue(Op0->getType()); 1173 1174 if (Op0->getType()->isIntegerTy(1)) 1175 // It can't be remainder by zero, hence it must be remainder by one. 1176 return Constant::getNullValue(Op0->getType()); 1177 1178 // X % X -> 0 1179 if (Op0 == Op1) 1180 return Constant::getNullValue(Op0->getType()); 1181 1182 // (X % Y) % Y -> X % Y 1183 if ((Opcode == Instruction::SRem && 1184 match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 1185 (Opcode == Instruction::URem && 1186 match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 1187 return Op0; 1188 1189 // If the operation is with the result of a select instruction, check whether 1190 // operating on either branch of the select always yields the same value. 1191 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1192 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1193 return V; 1194 1195 // If the operation is with the result of a phi instruction, check whether 1196 // operating on all incoming values of the phi always yields the same value. 1197 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1198 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1199 return V; 1200 1201 return nullptr; 1202 } 1203 1204 /// SimplifySRemInst - Given operands for an SRem, see if we can 1205 /// fold the result. If not, this returns null. 1206 static Value *SimplifySRemInst(Value *Op0, Value *Op1, const Query &Q, 1207 unsigned MaxRecurse) { 1208 if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse)) 1209 return V; 1210 1211 return nullptr; 1212 } 1213 1214 Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout &DL, 1215 const TargetLibraryInfo *TLI, 1216 const DominatorTree *DT, AssumptionCache *AC, 1217 const Instruction *CxtI) { 1218 return ::SimplifySRemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1219 RecursionLimit); 1220 } 1221 1222 /// SimplifyURemInst - Given operands for a URem, see if we can 1223 /// fold the result. If not, this returns null. 1224 static Value *SimplifyURemInst(Value *Op0, Value *Op1, const Query &Q, 1225 unsigned MaxRecurse) { 1226 if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse)) 1227 return V; 1228 1229 return nullptr; 1230 } 1231 1232 Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout &DL, 1233 const TargetLibraryInfo *TLI, 1234 const DominatorTree *DT, AssumptionCache *AC, 1235 const Instruction *CxtI) { 1236 return ::SimplifyURemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1237 RecursionLimit); 1238 } 1239 1240 static Value *SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF, 1241 const Query &, unsigned) { 1242 // undef % X -> undef (the undef could be a snan). 1243 if (match(Op0, m_Undef())) 1244 return Op0; 1245 1246 // X % undef -> undef 1247 if (match(Op1, m_Undef())) 1248 return Op1; 1249 1250 // 0 % X -> 0 1251 // Requires that NaNs are off (X could be zero) and signed zeroes are 1252 // ignored (X could be positive or negative, so the output sign is unknown). 1253 if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero())) 1254 return Op0; 1255 1256 return nullptr; 1257 } 1258 1259 Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF, 1260 const DataLayout &DL, 1261 const TargetLibraryInfo *TLI, 1262 const DominatorTree *DT, AssumptionCache *AC, 1263 const Instruction *CxtI) { 1264 return ::SimplifyFRemInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 1265 RecursionLimit); 1266 } 1267 1268 /// isUndefShift - Returns true if a shift by \c Amount always yields undef. 1269 static bool isUndefShift(Value *Amount) { 1270 Constant *C = dyn_cast<Constant>(Amount); 1271 if (!C) 1272 return false; 1273 1274 // X shift by undef -> undef because it may shift by the bitwidth. 1275 if (isa<UndefValue>(C)) 1276 return true; 1277 1278 // Shifting by the bitwidth or more is undefined. 1279 if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 1280 if (CI->getValue().getLimitedValue() >= 1281 CI->getType()->getScalarSizeInBits()) 1282 return true; 1283 1284 // If all lanes of a vector shift are undefined the whole shift is. 1285 if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) { 1286 for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I) 1287 if (!isUndefShift(C->getAggregateElement(I))) 1288 return false; 1289 return true; 1290 } 1291 1292 return false; 1293 } 1294 1295 /// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can 1296 /// fold the result. If not, this returns null. 1297 static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, 1298 const Query &Q, unsigned MaxRecurse) { 1299 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1300 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1301 Constant *Ops[] = { C0, C1 }; 1302 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 1303 } 1304 } 1305 1306 // 0 shift by X -> 0 1307 if (match(Op0, m_Zero())) 1308 return Op0; 1309 1310 // X shift by 0 -> X 1311 if (match(Op1, m_Zero())) 1312 return Op0; 1313 1314 // Fold undefined shifts. 1315 if (isUndefShift(Op1)) 1316 return UndefValue::get(Op0->getType()); 1317 1318 // If the operation is with the result of a select instruction, check whether 1319 // operating on either branch of the select always yields the same value. 1320 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1321 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1322 return V; 1323 1324 // If the operation is with the result of a phi instruction, check whether 1325 // operating on all incoming values of the phi always yields the same value. 1326 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1327 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1328 return V; 1329 1330 return nullptr; 1331 } 1332 1333 /// \brief Given operands for an Shl, LShr or AShr, see if we can 1334 /// fold the result. If not, this returns null. 1335 static Value *SimplifyRightShift(unsigned Opcode, Value *Op0, Value *Op1, 1336 bool isExact, const Query &Q, 1337 unsigned MaxRecurse) { 1338 if (Value *V = SimplifyShift(Opcode, Op0, Op1, Q, MaxRecurse)) 1339 return V; 1340 1341 // X >> X -> 0 1342 if (Op0 == Op1) 1343 return Constant::getNullValue(Op0->getType()); 1344 1345 // undef >> X -> 0 1346 // undef >> X -> undef (if it's exact) 1347 if (match(Op0, m_Undef())) 1348 return isExact ? Op0 : Constant::getNullValue(Op0->getType()); 1349 1350 // The low bit cannot be shifted out of an exact shift if it is set. 1351 if (isExact) { 1352 unsigned BitWidth = Op0->getType()->getScalarSizeInBits(); 1353 APInt Op0KnownZero(BitWidth, 0); 1354 APInt Op0KnownOne(BitWidth, 0); 1355 computeKnownBits(Op0, Op0KnownZero, Op0KnownOne, Q.DL, /*Depth=*/0, Q.AC, 1356 Q.CxtI, Q.DT); 1357 if (Op0KnownOne[0]) 1358 return Op0; 1359 } 1360 1361 return nullptr; 1362 } 1363 1364 /// SimplifyShlInst - Given operands for an Shl, see if we can 1365 /// fold the result. If not, this returns null. 1366 static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1367 const Query &Q, unsigned MaxRecurse) { 1368 if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse)) 1369 return V; 1370 1371 // undef << X -> 0 1372 // undef << X -> undef if (if it's NSW/NUW) 1373 if (match(Op0, m_Undef())) 1374 return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType()); 1375 1376 // (X >> A) << A -> X 1377 Value *X; 1378 if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1))))) 1379 return X; 1380 return nullptr; 1381 } 1382 1383 Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1384 const DataLayout &DL, const TargetLibraryInfo *TLI, 1385 const DominatorTree *DT, AssumptionCache *AC, 1386 const Instruction *CxtI) { 1387 return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), 1388 RecursionLimit); 1389 } 1390 1391 /// SimplifyLShrInst - Given operands for an LShr, see if we can 1392 /// fold the result. If not, this returns null. 1393 static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1394 const Query &Q, unsigned MaxRecurse) { 1395 if (Value *V = SimplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q, 1396 MaxRecurse)) 1397 return V; 1398 1399 // (X << A) >> A -> X 1400 Value *X; 1401 if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1)))) 1402 return X; 1403 1404 return nullptr; 1405 } 1406 1407 Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1408 const DataLayout &DL, 1409 const TargetLibraryInfo *TLI, 1410 const DominatorTree *DT, AssumptionCache *AC, 1411 const Instruction *CxtI) { 1412 return ::SimplifyLShrInst(Op0, Op1, isExact, Query(DL, TLI, DT, AC, CxtI), 1413 RecursionLimit); 1414 } 1415 1416 /// SimplifyAShrInst - Given operands for an AShr, see if we can 1417 /// fold the result. If not, this returns null. 1418 static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1419 const Query &Q, unsigned MaxRecurse) { 1420 if (Value *V = SimplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q, 1421 MaxRecurse)) 1422 return V; 1423 1424 // all ones >>a X -> all ones 1425 if (match(Op0, m_AllOnes())) 1426 return Op0; 1427 1428 // (X << A) >> A -> X 1429 Value *X; 1430 if (match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1)))) 1431 return X; 1432 1433 // Arithmetic shifting an all-sign-bit value is a no-op. 1434 unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); 1435 if (NumSignBits == Op0->getType()->getScalarSizeInBits()) 1436 return Op0; 1437 1438 return nullptr; 1439 } 1440 1441 Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1442 const DataLayout &DL, 1443 const TargetLibraryInfo *TLI, 1444 const DominatorTree *DT, AssumptionCache *AC, 1445 const Instruction *CxtI) { 1446 return ::SimplifyAShrInst(Op0, Op1, isExact, Query(DL, TLI, DT, AC, CxtI), 1447 RecursionLimit); 1448 } 1449 1450 static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp, 1451 ICmpInst *UnsignedICmp, bool IsAnd) { 1452 Value *X, *Y; 1453 1454 ICmpInst::Predicate EqPred; 1455 if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) || 1456 !ICmpInst::isEquality(EqPred)) 1457 return nullptr; 1458 1459 ICmpInst::Predicate UnsignedPred; 1460 if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) && 1461 ICmpInst::isUnsigned(UnsignedPred)) 1462 ; 1463 else if (match(UnsignedICmp, 1464 m_ICmp(UnsignedPred, m_Value(Y), m_Specific(X))) && 1465 ICmpInst::isUnsigned(UnsignedPred)) 1466 UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred); 1467 else 1468 return nullptr; 1469 1470 // X < Y && Y != 0 --> X < Y 1471 // X < Y || Y != 0 --> Y != 0 1472 if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE) 1473 return IsAnd ? UnsignedICmp : ZeroICmp; 1474 1475 // X >= Y || Y != 0 --> true 1476 // X >= Y || Y == 0 --> X >= Y 1477 if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) { 1478 if (EqPred == ICmpInst::ICMP_NE) 1479 return getTrue(UnsignedICmp->getType()); 1480 return UnsignedICmp; 1481 } 1482 1483 // X < Y && Y == 0 --> false 1484 if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ && 1485 IsAnd) 1486 return getFalse(UnsignedICmp->getType()); 1487 1488 return nullptr; 1489 } 1490 1491 // Simplify (and (icmp ...) (icmp ...)) to true when we can tell that the range 1492 // of possible values cannot be satisfied. 1493 static Value *SimplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) { 1494 ICmpInst::Predicate Pred0, Pred1; 1495 ConstantInt *CI1, *CI2; 1496 Value *V; 1497 1498 if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true)) 1499 return X; 1500 1501 if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)), 1502 m_ConstantInt(CI2)))) 1503 return nullptr; 1504 1505 if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Specific(CI1)))) 1506 return nullptr; 1507 1508 Type *ITy = Op0->getType(); 1509 1510 auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0)); 1511 bool isNSW = AddInst->hasNoSignedWrap(); 1512 bool isNUW = AddInst->hasNoUnsignedWrap(); 1513 1514 const APInt &CI1V = CI1->getValue(); 1515 const APInt &CI2V = CI2->getValue(); 1516 const APInt Delta = CI2V - CI1V; 1517 if (CI1V.isStrictlyPositive()) { 1518 if (Delta == 2) { 1519 if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_SGT) 1520 return getFalse(ITy); 1521 if (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT && isNSW) 1522 return getFalse(ITy); 1523 } 1524 if (Delta == 1) { 1525 if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_SGT) 1526 return getFalse(ITy); 1527 if (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGT && isNSW) 1528 return getFalse(ITy); 1529 } 1530 } 1531 if (CI1V.getBoolValue() && isNUW) { 1532 if (Delta == 2) 1533 if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT) 1534 return getFalse(ITy); 1535 if (Delta == 1) 1536 if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT) 1537 return getFalse(ITy); 1538 } 1539 1540 return nullptr; 1541 } 1542 1543 /// SimplifyAndInst - Given operands for an And, see if we can 1544 /// fold the result. If not, this returns null. 1545 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q, 1546 unsigned MaxRecurse) { 1547 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1548 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1549 Constant *Ops[] = { CLHS, CRHS }; 1550 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 1551 Ops, Q.DL, Q.TLI); 1552 } 1553 1554 // Canonicalize the constant to the RHS. 1555 std::swap(Op0, Op1); 1556 } 1557 1558 // X & undef -> 0 1559 if (match(Op1, m_Undef())) 1560 return Constant::getNullValue(Op0->getType()); 1561 1562 // X & X = X 1563 if (Op0 == Op1) 1564 return Op0; 1565 1566 // X & 0 = 0 1567 if (match(Op1, m_Zero())) 1568 return Op1; 1569 1570 // X & -1 = X 1571 if (match(Op1, m_AllOnes())) 1572 return Op0; 1573 1574 // A & ~A = ~A & A = 0 1575 if (match(Op0, m_Not(m_Specific(Op1))) || 1576 match(Op1, m_Not(m_Specific(Op0)))) 1577 return Constant::getNullValue(Op0->getType()); 1578 1579 // (A | ?) & A = A 1580 Value *A = nullptr, *B = nullptr; 1581 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1582 (A == Op1 || B == Op1)) 1583 return Op1; 1584 1585 // A & (A | ?) = A 1586 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1587 (A == Op0 || B == Op0)) 1588 return Op0; 1589 1590 // A & (-A) = A if A is a power of two or zero. 1591 if (match(Op0, m_Neg(m_Specific(Op1))) || 1592 match(Op1, m_Neg(m_Specific(Op0)))) { 1593 if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI, 1594 Q.DT)) 1595 return Op0; 1596 if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI, 1597 Q.DT)) 1598 return Op1; 1599 } 1600 1601 if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) { 1602 if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) { 1603 if (Value *V = SimplifyAndOfICmps(ICILHS, ICIRHS)) 1604 return V; 1605 if (Value *V = SimplifyAndOfICmps(ICIRHS, ICILHS)) 1606 return V; 1607 } 1608 } 1609 1610 // Try some generic simplifications for associative operations. 1611 if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q, 1612 MaxRecurse)) 1613 return V; 1614 1615 // And distributes over Or. Try some generic simplifications based on this. 1616 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1617 Q, MaxRecurse)) 1618 return V; 1619 1620 // And distributes over Xor. Try some generic simplifications based on this. 1621 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 1622 Q, MaxRecurse)) 1623 return V; 1624 1625 // If the operation is with the result of a select instruction, check whether 1626 // operating on either branch of the select always yields the same value. 1627 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1628 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q, 1629 MaxRecurse)) 1630 return V; 1631 1632 // If the operation is with the result of a phi instruction, check whether 1633 // operating on all incoming values of the phi always yields the same value. 1634 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1635 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q, 1636 MaxRecurse)) 1637 return V; 1638 1639 return nullptr; 1640 } 1641 1642 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout &DL, 1643 const TargetLibraryInfo *TLI, 1644 const DominatorTree *DT, AssumptionCache *AC, 1645 const Instruction *CxtI) { 1646 return ::SimplifyAndInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1647 RecursionLimit); 1648 } 1649 1650 // Simplify (or (icmp ...) (icmp ...)) to true when we can tell that the union 1651 // contains all possible values. 1652 static Value *SimplifyOrOfICmps(ICmpInst *Op0, ICmpInst *Op1) { 1653 ICmpInst::Predicate Pred0, Pred1; 1654 ConstantInt *CI1, *CI2; 1655 Value *V; 1656 1657 if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false)) 1658 return X; 1659 1660 if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)), 1661 m_ConstantInt(CI2)))) 1662 return nullptr; 1663 1664 if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Specific(CI1)))) 1665 return nullptr; 1666 1667 Type *ITy = Op0->getType(); 1668 1669 auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0)); 1670 bool isNSW = AddInst->hasNoSignedWrap(); 1671 bool isNUW = AddInst->hasNoUnsignedWrap(); 1672 1673 const APInt &CI1V = CI1->getValue(); 1674 const APInt &CI2V = CI2->getValue(); 1675 const APInt Delta = CI2V - CI1V; 1676 if (CI1V.isStrictlyPositive()) { 1677 if (Delta == 2) { 1678 if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_SLE) 1679 return getTrue(ITy); 1680 if (Pred0 == ICmpInst::ICMP_SGE && Pred1 == ICmpInst::ICMP_SLE && isNSW) 1681 return getTrue(ITy); 1682 } 1683 if (Delta == 1) { 1684 if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_SLE) 1685 return getTrue(ITy); 1686 if (Pred0 == ICmpInst::ICMP_SGT && Pred1 == ICmpInst::ICMP_SLE && isNSW) 1687 return getTrue(ITy); 1688 } 1689 } 1690 if (CI1V.getBoolValue() && isNUW) { 1691 if (Delta == 2) 1692 if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_ULE) 1693 return getTrue(ITy); 1694 if (Delta == 1) 1695 if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE) 1696 return getTrue(ITy); 1697 } 1698 1699 return nullptr; 1700 } 1701 1702 /// SimplifyOrInst - Given operands for an Or, see if we can 1703 /// fold the result. If not, this returns null. 1704 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q, 1705 unsigned MaxRecurse) { 1706 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1707 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1708 Constant *Ops[] = { CLHS, CRHS }; 1709 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 1710 Ops, Q.DL, Q.TLI); 1711 } 1712 1713 // Canonicalize the constant to the RHS. 1714 std::swap(Op0, Op1); 1715 } 1716 1717 // X | undef -> -1 1718 if (match(Op1, m_Undef())) 1719 return Constant::getAllOnesValue(Op0->getType()); 1720 1721 // X | X = X 1722 if (Op0 == Op1) 1723 return Op0; 1724 1725 // X | 0 = X 1726 if (match(Op1, m_Zero())) 1727 return Op0; 1728 1729 // X | -1 = -1 1730 if (match(Op1, m_AllOnes())) 1731 return Op1; 1732 1733 // A | ~A = ~A | A = -1 1734 if (match(Op0, m_Not(m_Specific(Op1))) || 1735 match(Op1, m_Not(m_Specific(Op0)))) 1736 return Constant::getAllOnesValue(Op0->getType()); 1737 1738 // (A & ?) | A = A 1739 Value *A = nullptr, *B = nullptr; 1740 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 1741 (A == Op1 || B == Op1)) 1742 return Op1; 1743 1744 // A | (A & ?) = A 1745 if (match(Op1, m_And(m_Value(A), m_Value(B))) && 1746 (A == Op0 || B == Op0)) 1747 return Op0; 1748 1749 // ~(A & ?) | A = -1 1750 if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) && 1751 (A == Op1 || B == Op1)) 1752 return Constant::getAllOnesValue(Op1->getType()); 1753 1754 // A | ~(A & ?) = -1 1755 if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) && 1756 (A == Op0 || B == Op0)) 1757 return Constant::getAllOnesValue(Op0->getType()); 1758 1759 if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) { 1760 if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) { 1761 if (Value *V = SimplifyOrOfICmps(ICILHS, ICIRHS)) 1762 return V; 1763 if (Value *V = SimplifyOrOfICmps(ICIRHS, ICILHS)) 1764 return V; 1765 } 1766 } 1767 1768 // Try some generic simplifications for associative operations. 1769 if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q, 1770 MaxRecurse)) 1771 return V; 1772 1773 // Or distributes over And. Try some generic simplifications based on this. 1774 if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q, 1775 MaxRecurse)) 1776 return V; 1777 1778 // If the operation is with the result of a select instruction, check whether 1779 // operating on either branch of the select always yields the same value. 1780 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1781 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q, 1782 MaxRecurse)) 1783 return V; 1784 1785 // (A & C)|(B & D) 1786 Value *C = nullptr, *D = nullptr; 1787 if (match(Op0, m_And(m_Value(A), m_Value(C))) && 1788 match(Op1, m_And(m_Value(B), m_Value(D)))) { 1789 ConstantInt *C1 = dyn_cast<ConstantInt>(C); 1790 ConstantInt *C2 = dyn_cast<ConstantInt>(D); 1791 if (C1 && C2 && (C1->getValue() == ~C2->getValue())) { 1792 // (A & C1)|(B & C2) 1793 // If we have: ((V + N) & C1) | (V & C2) 1794 // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0 1795 // replace with V+N. 1796 Value *V1, *V2; 1797 if ((C2->getValue() & (C2->getValue() + 1)) == 0 && // C2 == 0+1+ 1798 match(A, m_Add(m_Value(V1), m_Value(V2)))) { 1799 // Add commutes, try both ways. 1800 if (V1 == B && 1801 MaskedValueIsZero(V2, C2->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1802 return A; 1803 if (V2 == B && 1804 MaskedValueIsZero(V1, C2->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1805 return A; 1806 } 1807 // Or commutes, try both ways. 1808 if ((C1->getValue() & (C1->getValue() + 1)) == 0 && 1809 match(B, m_Add(m_Value(V1), m_Value(V2)))) { 1810 // Add commutes, try both ways. 1811 if (V1 == A && 1812 MaskedValueIsZero(V2, C1->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1813 return B; 1814 if (V2 == A && 1815 MaskedValueIsZero(V1, C1->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1816 return B; 1817 } 1818 } 1819 } 1820 1821 // If the operation is with the result of a phi instruction, check whether 1822 // operating on all incoming values of the phi always yields the same value. 1823 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1824 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse)) 1825 return V; 1826 1827 return nullptr; 1828 } 1829 1830 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout &DL, 1831 const TargetLibraryInfo *TLI, 1832 const DominatorTree *DT, AssumptionCache *AC, 1833 const Instruction *CxtI) { 1834 return ::SimplifyOrInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1835 RecursionLimit); 1836 } 1837 1838 /// SimplifyXorInst - Given operands for a Xor, see if we can 1839 /// fold the result. If not, this returns null. 1840 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const Query &Q, 1841 unsigned MaxRecurse) { 1842 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1843 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1844 Constant *Ops[] = { CLHS, CRHS }; 1845 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 1846 Ops, Q.DL, Q.TLI); 1847 } 1848 1849 // Canonicalize the constant to the RHS. 1850 std::swap(Op0, Op1); 1851 } 1852 1853 // A ^ undef -> undef 1854 if (match(Op1, m_Undef())) 1855 return Op1; 1856 1857 // A ^ 0 = A 1858 if (match(Op1, m_Zero())) 1859 return Op0; 1860 1861 // A ^ A = 0 1862 if (Op0 == Op1) 1863 return Constant::getNullValue(Op0->getType()); 1864 1865 // A ^ ~A = ~A ^ A = -1 1866 if (match(Op0, m_Not(m_Specific(Op1))) || 1867 match(Op1, m_Not(m_Specific(Op0)))) 1868 return Constant::getAllOnesValue(Op0->getType()); 1869 1870 // Try some generic simplifications for associative operations. 1871 if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q, 1872 MaxRecurse)) 1873 return V; 1874 1875 // Threading Xor over selects and phi nodes is pointless, so don't bother. 1876 // Threading over the select in "A ^ select(cond, B, C)" means evaluating 1877 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 1878 // only if B and C are equal. If B and C are equal then (since we assume 1879 // that operands have already been simplified) "select(cond, B, C)" should 1880 // have been simplified to the common value of B and C already. Analysing 1881 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 1882 // for threading over phi nodes. 1883 1884 return nullptr; 1885 } 1886 1887 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout &DL, 1888 const TargetLibraryInfo *TLI, 1889 const DominatorTree *DT, AssumptionCache *AC, 1890 const Instruction *CxtI) { 1891 return ::SimplifyXorInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1892 RecursionLimit); 1893 } 1894 1895 static Type *GetCompareTy(Value *Op) { 1896 return CmpInst::makeCmpResultType(Op->getType()); 1897 } 1898 1899 /// ExtractEquivalentCondition - Rummage around inside V looking for something 1900 /// equivalent to the comparison "LHS Pred RHS". Return such a value if found, 1901 /// otherwise return null. Helper function for analyzing max/min idioms. 1902 static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred, 1903 Value *LHS, Value *RHS) { 1904 SelectInst *SI = dyn_cast<SelectInst>(V); 1905 if (!SI) 1906 return nullptr; 1907 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition()); 1908 if (!Cmp) 1909 return nullptr; 1910 Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1); 1911 if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS) 1912 return Cmp; 1913 if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) && 1914 LHS == CmpRHS && RHS == CmpLHS) 1915 return Cmp; 1916 return nullptr; 1917 } 1918 1919 // A significant optimization not implemented here is assuming that alloca 1920 // addresses are not equal to incoming argument values. They don't *alias*, 1921 // as we say, but that doesn't mean they aren't equal, so we take a 1922 // conservative approach. 1923 // 1924 // This is inspired in part by C++11 5.10p1: 1925 // "Two pointers of the same type compare equal if and only if they are both 1926 // null, both point to the same function, or both represent the same 1927 // address." 1928 // 1929 // This is pretty permissive. 1930 // 1931 // It's also partly due to C11 6.5.9p6: 1932 // "Two pointers compare equal if and only if both are null pointers, both are 1933 // pointers to the same object (including a pointer to an object and a 1934 // subobject at its beginning) or function, both are pointers to one past the 1935 // last element of the same array object, or one is a pointer to one past the 1936 // end of one array object and the other is a pointer to the start of a 1937 // different array object that happens to immediately follow the first array 1938 // object in the address space.) 1939 // 1940 // C11's version is more restrictive, however there's no reason why an argument 1941 // couldn't be a one-past-the-end value for a stack object in the caller and be 1942 // equal to the beginning of a stack object in the callee. 1943 // 1944 // If the C and C++ standards are ever made sufficiently restrictive in this 1945 // area, it may be possible to update LLVM's semantics accordingly and reinstate 1946 // this optimization. 1947 static Constant *computePointerICmp(const DataLayout &DL, 1948 const TargetLibraryInfo *TLI, 1949 CmpInst::Predicate Pred, Value *LHS, 1950 Value *RHS) { 1951 // First, skip past any trivial no-ops. 1952 LHS = LHS->stripPointerCasts(); 1953 RHS = RHS->stripPointerCasts(); 1954 1955 // A non-null pointer is not equal to a null pointer. 1956 if (llvm::isKnownNonNull(LHS, TLI) && isa<ConstantPointerNull>(RHS) && 1957 (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE)) 1958 return ConstantInt::get(GetCompareTy(LHS), 1959 !CmpInst::isTrueWhenEqual(Pred)); 1960 1961 // We can only fold certain predicates on pointer comparisons. 1962 switch (Pred) { 1963 default: 1964 return nullptr; 1965 1966 // Equality comaprisons are easy to fold. 1967 case CmpInst::ICMP_EQ: 1968 case CmpInst::ICMP_NE: 1969 break; 1970 1971 // We can only handle unsigned relational comparisons because 'inbounds' on 1972 // a GEP only protects against unsigned wrapping. 1973 case CmpInst::ICMP_UGT: 1974 case CmpInst::ICMP_UGE: 1975 case CmpInst::ICMP_ULT: 1976 case CmpInst::ICMP_ULE: 1977 // However, we have to switch them to their signed variants to handle 1978 // negative indices from the base pointer. 1979 Pred = ICmpInst::getSignedPredicate(Pred); 1980 break; 1981 } 1982 1983 // Strip off any constant offsets so that we can reason about them. 1984 // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets 1985 // here and compare base addresses like AliasAnalysis does, however there are 1986 // numerous hazards. AliasAnalysis and its utilities rely on special rules 1987 // governing loads and stores which don't apply to icmps. Also, AliasAnalysis 1988 // doesn't need to guarantee pointer inequality when it says NoAlias. 1989 Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); 1990 Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); 1991 1992 // If LHS and RHS are related via constant offsets to the same base 1993 // value, we can replace it with an icmp which just compares the offsets. 1994 if (LHS == RHS) 1995 return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset); 1996 1997 // Various optimizations for (in)equality comparisons. 1998 if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) { 1999 // Different non-empty allocations that exist at the same time have 2000 // different addresses (if the program can tell). Global variables always 2001 // exist, so they always exist during the lifetime of each other and all 2002 // allocas. Two different allocas usually have different addresses... 2003 // 2004 // However, if there's an @llvm.stackrestore dynamically in between two 2005 // allocas, they may have the same address. It's tempting to reduce the 2006 // scope of the problem by only looking at *static* allocas here. That would 2007 // cover the majority of allocas while significantly reducing the likelihood 2008 // of having an @llvm.stackrestore pop up in the middle. However, it's not 2009 // actually impossible for an @llvm.stackrestore to pop up in the middle of 2010 // an entry block. Also, if we have a block that's not attached to a 2011 // function, we can't tell if it's "static" under the current definition. 2012 // Theoretically, this problem could be fixed by creating a new kind of 2013 // instruction kind specifically for static allocas. Such a new instruction 2014 // could be required to be at the top of the entry block, thus preventing it 2015 // from being subject to a @llvm.stackrestore. Instcombine could even 2016 // convert regular allocas into these special allocas. It'd be nifty. 2017 // However, until then, this problem remains open. 2018 // 2019 // So, we'll assume that two non-empty allocas have different addresses 2020 // for now. 2021 // 2022 // With all that, if the offsets are within the bounds of their allocations 2023 // (and not one-past-the-end! so we can't use inbounds!), and their 2024 // allocations aren't the same, the pointers are not equal. 2025 // 2026 // Note that it's not necessary to check for LHS being a global variable 2027 // address, due to canonicalization and constant folding. 2028 if (isa<AllocaInst>(LHS) && 2029 (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) { 2030 ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset); 2031 ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(RHSOffset); 2032 uint64_t LHSSize, RHSSize; 2033 if (LHSOffsetCI && RHSOffsetCI && 2034 getObjectSize(LHS, LHSSize, DL, TLI) && 2035 getObjectSize(RHS, RHSSize, DL, TLI)) { 2036 const APInt &LHSOffsetValue = LHSOffsetCI->getValue(); 2037 const APInt &RHSOffsetValue = RHSOffsetCI->getValue(); 2038 if (!LHSOffsetValue.isNegative() && 2039 !RHSOffsetValue.isNegative() && 2040 LHSOffsetValue.ult(LHSSize) && 2041 RHSOffsetValue.ult(RHSSize)) { 2042 return ConstantInt::get(GetCompareTy(LHS), 2043 !CmpInst::isTrueWhenEqual(Pred)); 2044 } 2045 } 2046 2047 // Repeat the above check but this time without depending on DataLayout 2048 // or being able to compute a precise size. 2049 if (!cast<PointerType>(LHS->getType())->isEmptyTy() && 2050 !cast<PointerType>(RHS->getType())->isEmptyTy() && 2051 LHSOffset->isNullValue() && 2052 RHSOffset->isNullValue()) 2053 return ConstantInt::get(GetCompareTy(LHS), 2054 !CmpInst::isTrueWhenEqual(Pred)); 2055 } 2056 2057 // Even if an non-inbounds GEP occurs along the path we can still optimize 2058 // equality comparisons concerning the result. We avoid walking the whole 2059 // chain again by starting where the last calls to 2060 // stripAndComputeConstantOffsets left off and accumulate the offsets. 2061 Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true); 2062 Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true); 2063 if (LHS == RHS) 2064 return ConstantExpr::getICmp(Pred, 2065 ConstantExpr::getAdd(LHSOffset, LHSNoBound), 2066 ConstantExpr::getAdd(RHSOffset, RHSNoBound)); 2067 2068 // If one side of the equality comparison must come from a noalias call 2069 // (meaning a system memory allocation function), and the other side must 2070 // come from a pointer that cannot overlap with dynamically-allocated 2071 // memory within the lifetime of the current function (allocas, byval 2072 // arguments, globals), then determine the comparison result here. 2073 SmallVector<Value *, 8> LHSUObjs, RHSUObjs; 2074 GetUnderlyingObjects(LHS, LHSUObjs, DL); 2075 GetUnderlyingObjects(RHS, RHSUObjs, DL); 2076 2077 // Is the set of underlying objects all noalias calls? 2078 auto IsNAC = [](SmallVectorImpl<Value *> &Objects) { 2079 return std::all_of(Objects.begin(), Objects.end(), 2080 [](Value *V){ return isNoAliasCall(V); }); 2081 }; 2082 2083 // Is the set of underlying objects all things which must be disjoint from 2084 // noalias calls. For allocas, we consider only static ones (dynamic 2085 // allocas might be transformed into calls to malloc not simultaneously 2086 // live with the compared-to allocation). For globals, we exclude symbols 2087 // that might be resolve lazily to symbols in another dynamically-loaded 2088 // library (and, thus, could be malloc'ed by the implementation). 2089 auto IsAllocDisjoint = [](SmallVectorImpl<Value *> &Objects) { 2090 return std::all_of(Objects.begin(), Objects.end(), 2091 [](Value *V){ 2092 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) 2093 return AI->getParent() && AI->getParent()->getParent() && 2094 AI->isStaticAlloca(); 2095 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 2096 return (GV->hasLocalLinkage() || 2097 GV->hasHiddenVisibility() || 2098 GV->hasProtectedVisibility() || 2099 GV->hasUnnamedAddr()) && 2100 !GV->isThreadLocal(); 2101 if (const Argument *A = dyn_cast<Argument>(V)) 2102 return A->hasByValAttr(); 2103 return false; 2104 }); 2105 }; 2106 2107 if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) || 2108 (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs))) 2109 return ConstantInt::get(GetCompareTy(LHS), 2110 !CmpInst::isTrueWhenEqual(Pred)); 2111 } 2112 2113 // Otherwise, fail. 2114 return nullptr; 2115 } 2116 2117 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 2118 /// fold the result. If not, this returns null. 2119 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2120 const Query &Q, unsigned MaxRecurse) { 2121 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 2122 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 2123 2124 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 2125 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 2126 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI); 2127 2128 // If we have a constant, make sure it is on the RHS. 2129 std::swap(LHS, RHS); 2130 Pred = CmpInst::getSwappedPredicate(Pred); 2131 } 2132 2133 Type *ITy = GetCompareTy(LHS); // The return type. 2134 Type *OpTy = LHS->getType(); // The operand type. 2135 2136 // icmp X, X -> true/false 2137 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 2138 // because X could be 0. 2139 if (LHS == RHS || isa<UndefValue>(RHS)) 2140 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 2141 2142 // Special case logic when the operands have i1 type. 2143 if (OpTy->getScalarType()->isIntegerTy(1)) { 2144 switch (Pred) { 2145 default: break; 2146 case ICmpInst::ICMP_EQ: 2147 // X == 1 -> X 2148 if (match(RHS, m_One())) 2149 return LHS; 2150 break; 2151 case ICmpInst::ICMP_NE: 2152 // X != 0 -> X 2153 if (match(RHS, m_Zero())) 2154 return LHS; 2155 break; 2156 case ICmpInst::ICMP_UGT: 2157 // X >u 0 -> X 2158 if (match(RHS, m_Zero())) 2159 return LHS; 2160 break; 2161 case ICmpInst::ICMP_UGE: 2162 // X >=u 1 -> X 2163 if (match(RHS, m_One())) 2164 return LHS; 2165 break; 2166 case ICmpInst::ICMP_SLT: 2167 // X <s 0 -> X 2168 if (match(RHS, m_Zero())) 2169 return LHS; 2170 break; 2171 case ICmpInst::ICMP_SLE: 2172 // X <=s -1 -> X 2173 if (match(RHS, m_One())) 2174 return LHS; 2175 break; 2176 } 2177 } 2178 2179 // If we are comparing with zero then try hard since this is a common case. 2180 if (match(RHS, m_Zero())) { 2181 bool LHSKnownNonNegative, LHSKnownNegative; 2182 switch (Pred) { 2183 default: llvm_unreachable("Unknown ICmp predicate!"); 2184 case ICmpInst::ICMP_ULT: 2185 return getFalse(ITy); 2186 case ICmpInst::ICMP_UGE: 2187 return getTrue(ITy); 2188 case ICmpInst::ICMP_EQ: 2189 case ICmpInst::ICMP_ULE: 2190 if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2191 return getFalse(ITy); 2192 break; 2193 case ICmpInst::ICMP_NE: 2194 case ICmpInst::ICMP_UGT: 2195 if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2196 return getTrue(ITy); 2197 break; 2198 case ICmpInst::ICMP_SLT: 2199 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2200 Q.CxtI, Q.DT); 2201 if (LHSKnownNegative) 2202 return getTrue(ITy); 2203 if (LHSKnownNonNegative) 2204 return getFalse(ITy); 2205 break; 2206 case ICmpInst::ICMP_SLE: 2207 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2208 Q.CxtI, Q.DT); 2209 if (LHSKnownNegative) 2210 return getTrue(ITy); 2211 if (LHSKnownNonNegative && 2212 isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2213 return getFalse(ITy); 2214 break; 2215 case ICmpInst::ICMP_SGE: 2216 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2217 Q.CxtI, Q.DT); 2218 if (LHSKnownNegative) 2219 return getFalse(ITy); 2220 if (LHSKnownNonNegative) 2221 return getTrue(ITy); 2222 break; 2223 case ICmpInst::ICMP_SGT: 2224 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2225 Q.CxtI, Q.DT); 2226 if (LHSKnownNegative) 2227 return getFalse(ITy); 2228 if (LHSKnownNonNegative && 2229 isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2230 return getTrue(ITy); 2231 break; 2232 } 2233 } 2234 2235 // See if we are doing a comparison with a constant integer. 2236 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2237 // Rule out tautological comparisons (eg., ult 0 or uge 0). 2238 ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue()); 2239 if (RHS_CR.isEmptySet()) 2240 return ConstantInt::getFalse(CI->getContext()); 2241 if (RHS_CR.isFullSet()) 2242 return ConstantInt::getTrue(CI->getContext()); 2243 2244 // Many binary operators with constant RHS have easy to compute constant 2245 // range. Use them to check whether the comparison is a tautology. 2246 unsigned Width = CI->getBitWidth(); 2247 APInt Lower = APInt(Width, 0); 2248 APInt Upper = APInt(Width, 0); 2249 ConstantInt *CI2; 2250 if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) { 2251 // 'urem x, CI2' produces [0, CI2). 2252 Upper = CI2->getValue(); 2253 } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) { 2254 // 'srem x, CI2' produces (-|CI2|, |CI2|). 2255 Upper = CI2->getValue().abs(); 2256 Lower = (-Upper) + 1; 2257 } else if (match(LHS, m_UDiv(m_ConstantInt(CI2), m_Value()))) { 2258 // 'udiv CI2, x' produces [0, CI2]. 2259 Upper = CI2->getValue() + 1; 2260 } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) { 2261 // 'udiv x, CI2' produces [0, UINT_MAX / CI2]. 2262 APInt NegOne = APInt::getAllOnesValue(Width); 2263 if (!CI2->isZero()) 2264 Upper = NegOne.udiv(CI2->getValue()) + 1; 2265 } else if (match(LHS, m_SDiv(m_ConstantInt(CI2), m_Value()))) { 2266 if (CI2->isMinSignedValue()) { 2267 // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2]. 2268 Lower = CI2->getValue(); 2269 Upper = Lower.lshr(1) + 1; 2270 } else { 2271 // 'sdiv CI2, x' produces [-|CI2|, |CI2|]. 2272 Upper = CI2->getValue().abs() + 1; 2273 Lower = (-Upper) + 1; 2274 } 2275 } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) { 2276 APInt IntMin = APInt::getSignedMinValue(Width); 2277 APInt IntMax = APInt::getSignedMaxValue(Width); 2278 APInt Val = CI2->getValue(); 2279 if (Val.isAllOnesValue()) { 2280 // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX] 2281 // where CI2 != -1 and CI2 != 0 and CI2 != 1 2282 Lower = IntMin + 1; 2283 Upper = IntMax + 1; 2284 } else if (Val.countLeadingZeros() < Width - 1) { 2285 // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2] 2286 // where CI2 != -1 and CI2 != 0 and CI2 != 1 2287 Lower = IntMin.sdiv(Val); 2288 Upper = IntMax.sdiv(Val); 2289 if (Lower.sgt(Upper)) 2290 std::swap(Lower, Upper); 2291 Upper = Upper + 1; 2292 assert(Upper != Lower && "Upper part of range has wrapped!"); 2293 } 2294 } else if (match(LHS, m_NUWShl(m_ConstantInt(CI2), m_Value()))) { 2295 // 'shl nuw CI2, x' produces [CI2, CI2 << CLZ(CI2)] 2296 Lower = CI2->getValue(); 2297 Upper = Lower.shl(Lower.countLeadingZeros()) + 1; 2298 } else if (match(LHS, m_NSWShl(m_ConstantInt(CI2), m_Value()))) { 2299 if (CI2->isNegative()) { 2300 // 'shl nsw CI2, x' produces [CI2 << CLO(CI2)-1, CI2] 2301 unsigned ShiftAmount = CI2->getValue().countLeadingOnes() - 1; 2302 Lower = CI2->getValue().shl(ShiftAmount); 2303 Upper = CI2->getValue() + 1; 2304 } else { 2305 // 'shl nsw CI2, x' produces [CI2, CI2 << CLZ(CI2)-1] 2306 unsigned ShiftAmount = CI2->getValue().countLeadingZeros() - 1; 2307 Lower = CI2->getValue(); 2308 Upper = CI2->getValue().shl(ShiftAmount) + 1; 2309 } 2310 } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) { 2311 // 'lshr x, CI2' produces [0, UINT_MAX >> CI2]. 2312 APInt NegOne = APInt::getAllOnesValue(Width); 2313 if (CI2->getValue().ult(Width)) 2314 Upper = NegOne.lshr(CI2->getValue()) + 1; 2315 } else if (match(LHS, m_LShr(m_ConstantInt(CI2), m_Value()))) { 2316 // 'lshr CI2, x' produces [CI2 >> (Width-1), CI2]. 2317 unsigned ShiftAmount = Width - 1; 2318 if (!CI2->isZero() && cast<BinaryOperator>(LHS)->isExact()) 2319 ShiftAmount = CI2->getValue().countTrailingZeros(); 2320 Lower = CI2->getValue().lshr(ShiftAmount); 2321 Upper = CI2->getValue() + 1; 2322 } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) { 2323 // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2]. 2324 APInt IntMin = APInt::getSignedMinValue(Width); 2325 APInt IntMax = APInt::getSignedMaxValue(Width); 2326 if (CI2->getValue().ult(Width)) { 2327 Lower = IntMin.ashr(CI2->getValue()); 2328 Upper = IntMax.ashr(CI2->getValue()) + 1; 2329 } 2330 } else if (match(LHS, m_AShr(m_ConstantInt(CI2), m_Value()))) { 2331 unsigned ShiftAmount = Width - 1; 2332 if (!CI2->isZero() && cast<BinaryOperator>(LHS)->isExact()) 2333 ShiftAmount = CI2->getValue().countTrailingZeros(); 2334 if (CI2->isNegative()) { 2335 // 'ashr CI2, x' produces [CI2, CI2 >> (Width-1)] 2336 Lower = CI2->getValue(); 2337 Upper = CI2->getValue().ashr(ShiftAmount) + 1; 2338 } else { 2339 // 'ashr CI2, x' produces [CI2 >> (Width-1), CI2] 2340 Lower = CI2->getValue().ashr(ShiftAmount); 2341 Upper = CI2->getValue() + 1; 2342 } 2343 } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) { 2344 // 'or x, CI2' produces [CI2, UINT_MAX]. 2345 Lower = CI2->getValue(); 2346 } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) { 2347 // 'and x, CI2' produces [0, CI2]. 2348 Upper = CI2->getValue() + 1; 2349 } 2350 if (Lower != Upper) { 2351 ConstantRange LHS_CR = ConstantRange(Lower, Upper); 2352 if (RHS_CR.contains(LHS_CR)) 2353 return ConstantInt::getTrue(RHS->getContext()); 2354 if (RHS_CR.inverse().contains(LHS_CR)) 2355 return ConstantInt::getFalse(RHS->getContext()); 2356 } 2357 } 2358 2359 // Compare of cast, for example (zext X) != 0 -> X != 0 2360 if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) { 2361 Instruction *LI = cast<CastInst>(LHS); 2362 Value *SrcOp = LI->getOperand(0); 2363 Type *SrcTy = SrcOp->getType(); 2364 Type *DstTy = LI->getType(); 2365 2366 // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input 2367 // if the integer type is the same size as the pointer type. 2368 if (MaxRecurse && isa<PtrToIntInst>(LI) && 2369 Q.DL.getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) { 2370 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 2371 // Transfer the cast to the constant. 2372 if (Value *V = SimplifyICmpInst(Pred, SrcOp, 2373 ConstantExpr::getIntToPtr(RHSC, SrcTy), 2374 Q, MaxRecurse-1)) 2375 return V; 2376 } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) { 2377 if (RI->getOperand(0)->getType() == SrcTy) 2378 // Compare without the cast. 2379 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 2380 Q, MaxRecurse-1)) 2381 return V; 2382 } 2383 } 2384 2385 if (isa<ZExtInst>(LHS)) { 2386 // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the 2387 // same type. 2388 if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) { 2389 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 2390 // Compare X and Y. Note that signed predicates become unsigned. 2391 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 2392 SrcOp, RI->getOperand(0), Q, 2393 MaxRecurse-1)) 2394 return V; 2395 } 2396 // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended 2397 // too. If not, then try to deduce the result of the comparison. 2398 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2399 // Compute the constant that would happen if we truncated to SrcTy then 2400 // reextended to DstTy. 2401 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 2402 Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy); 2403 2404 // If the re-extended constant didn't change then this is effectively 2405 // also a case of comparing two zero-extended values. 2406 if (RExt == CI && MaxRecurse) 2407 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 2408 SrcOp, Trunc, Q, MaxRecurse-1)) 2409 return V; 2410 2411 // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit 2412 // there. Use this to work out the result of the comparison. 2413 if (RExt != CI) { 2414 switch (Pred) { 2415 default: llvm_unreachable("Unknown ICmp predicate!"); 2416 // LHS <u RHS. 2417 case ICmpInst::ICMP_EQ: 2418 case ICmpInst::ICMP_UGT: 2419 case ICmpInst::ICMP_UGE: 2420 return ConstantInt::getFalse(CI->getContext()); 2421 2422 case ICmpInst::ICMP_NE: 2423 case ICmpInst::ICMP_ULT: 2424 case ICmpInst::ICMP_ULE: 2425 return ConstantInt::getTrue(CI->getContext()); 2426 2427 // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS 2428 // is non-negative then LHS <s RHS. 2429 case ICmpInst::ICMP_SGT: 2430 case ICmpInst::ICMP_SGE: 2431 return CI->getValue().isNegative() ? 2432 ConstantInt::getTrue(CI->getContext()) : 2433 ConstantInt::getFalse(CI->getContext()); 2434 2435 case ICmpInst::ICMP_SLT: 2436 case ICmpInst::ICMP_SLE: 2437 return CI->getValue().isNegative() ? 2438 ConstantInt::getFalse(CI->getContext()) : 2439 ConstantInt::getTrue(CI->getContext()); 2440 } 2441 } 2442 } 2443 } 2444 2445 if (isa<SExtInst>(LHS)) { 2446 // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the 2447 // same type. 2448 if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) { 2449 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 2450 // Compare X and Y. Note that the predicate does not change. 2451 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 2452 Q, MaxRecurse-1)) 2453 return V; 2454 } 2455 // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended 2456 // too. If not, then try to deduce the result of the comparison. 2457 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2458 // Compute the constant that would happen if we truncated to SrcTy then 2459 // reextended to DstTy. 2460 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 2461 Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy); 2462 2463 // If the re-extended constant didn't change then this is effectively 2464 // also a case of comparing two sign-extended values. 2465 if (RExt == CI && MaxRecurse) 2466 if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1)) 2467 return V; 2468 2469 // Otherwise the upper bits of LHS are all equal, while RHS has varying 2470 // bits there. Use this to work out the result of the comparison. 2471 if (RExt != CI) { 2472 switch (Pred) { 2473 default: llvm_unreachable("Unknown ICmp predicate!"); 2474 case ICmpInst::ICMP_EQ: 2475 return ConstantInt::getFalse(CI->getContext()); 2476 case ICmpInst::ICMP_NE: 2477 return ConstantInt::getTrue(CI->getContext()); 2478 2479 // If RHS is non-negative then LHS <s RHS. If RHS is negative then 2480 // LHS >s RHS. 2481 case ICmpInst::ICMP_SGT: 2482 case ICmpInst::ICMP_SGE: 2483 return CI->getValue().isNegative() ? 2484 ConstantInt::getTrue(CI->getContext()) : 2485 ConstantInt::getFalse(CI->getContext()); 2486 case ICmpInst::ICMP_SLT: 2487 case ICmpInst::ICMP_SLE: 2488 return CI->getValue().isNegative() ? 2489 ConstantInt::getFalse(CI->getContext()) : 2490 ConstantInt::getTrue(CI->getContext()); 2491 2492 // If LHS is non-negative then LHS <u RHS. If LHS is negative then 2493 // LHS >u RHS. 2494 case ICmpInst::ICMP_UGT: 2495 case ICmpInst::ICMP_UGE: 2496 // Comparison is true iff the LHS <s 0. 2497 if (MaxRecurse) 2498 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp, 2499 Constant::getNullValue(SrcTy), 2500 Q, MaxRecurse-1)) 2501 return V; 2502 break; 2503 case ICmpInst::ICMP_ULT: 2504 case ICmpInst::ICMP_ULE: 2505 // Comparison is true iff the LHS >=s 0. 2506 if (MaxRecurse) 2507 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp, 2508 Constant::getNullValue(SrcTy), 2509 Q, MaxRecurse-1)) 2510 return V; 2511 break; 2512 } 2513 } 2514 } 2515 } 2516 } 2517 2518 // Special logic for binary operators. 2519 BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS); 2520 BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS); 2521 if (MaxRecurse && (LBO || RBO)) { 2522 // Analyze the case when either LHS or RHS is an add instruction. 2523 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr; 2524 // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null). 2525 bool NoLHSWrapProblem = false, NoRHSWrapProblem = false; 2526 if (LBO && LBO->getOpcode() == Instruction::Add) { 2527 A = LBO->getOperand(0); B = LBO->getOperand(1); 2528 NoLHSWrapProblem = ICmpInst::isEquality(Pred) || 2529 (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) || 2530 (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap()); 2531 } 2532 if (RBO && RBO->getOpcode() == Instruction::Add) { 2533 C = RBO->getOperand(0); D = RBO->getOperand(1); 2534 NoRHSWrapProblem = ICmpInst::isEquality(Pred) || 2535 (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) || 2536 (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap()); 2537 } 2538 2539 // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow. 2540 if ((A == RHS || B == RHS) && NoLHSWrapProblem) 2541 if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A, 2542 Constant::getNullValue(RHS->getType()), 2543 Q, MaxRecurse-1)) 2544 return V; 2545 2546 // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow. 2547 if ((C == LHS || D == LHS) && NoRHSWrapProblem) 2548 if (Value *V = SimplifyICmpInst(Pred, 2549 Constant::getNullValue(LHS->getType()), 2550 C == LHS ? D : C, Q, MaxRecurse-1)) 2551 return V; 2552 2553 // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow. 2554 if (A && C && (A == C || A == D || B == C || B == D) && 2555 NoLHSWrapProblem && NoRHSWrapProblem) { 2556 // Determine Y and Z in the form icmp (X+Y), (X+Z). 2557 Value *Y, *Z; 2558 if (A == C) { 2559 // C + B == C + D -> B == D 2560 Y = B; 2561 Z = D; 2562 } else if (A == D) { 2563 // D + B == C + D -> B == C 2564 Y = B; 2565 Z = C; 2566 } else if (B == C) { 2567 // A + C == C + D -> A == D 2568 Y = A; 2569 Z = D; 2570 } else { 2571 assert(B == D); 2572 // A + D == C + D -> A == C 2573 Y = A; 2574 Z = C; 2575 } 2576 if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse-1)) 2577 return V; 2578 } 2579 } 2580 2581 // icmp pred (or X, Y), X 2582 if (LBO && match(LBO, m_CombineOr(m_Or(m_Value(), m_Specific(RHS)), 2583 m_Or(m_Specific(RHS), m_Value())))) { 2584 if (Pred == ICmpInst::ICMP_ULT) 2585 return getFalse(ITy); 2586 if (Pred == ICmpInst::ICMP_UGE) 2587 return getTrue(ITy); 2588 } 2589 // icmp pred X, (or X, Y) 2590 if (RBO && match(RBO, m_CombineOr(m_Or(m_Value(), m_Specific(LHS)), 2591 m_Or(m_Specific(LHS), m_Value())))) { 2592 if (Pred == ICmpInst::ICMP_ULE) 2593 return getTrue(ITy); 2594 if (Pred == ICmpInst::ICMP_UGT) 2595 return getFalse(ITy); 2596 } 2597 2598 // icmp pred (and X, Y), X 2599 if (LBO && match(LBO, m_CombineOr(m_And(m_Value(), m_Specific(RHS)), 2600 m_And(m_Specific(RHS), m_Value())))) { 2601 if (Pred == ICmpInst::ICMP_UGT) 2602 return getFalse(ITy); 2603 if (Pred == ICmpInst::ICMP_ULE) 2604 return getTrue(ITy); 2605 } 2606 // icmp pred X, (and X, Y) 2607 if (RBO && match(RBO, m_CombineOr(m_And(m_Value(), m_Specific(LHS)), 2608 m_And(m_Specific(LHS), m_Value())))) { 2609 if (Pred == ICmpInst::ICMP_UGE) 2610 return getTrue(ITy); 2611 if (Pred == ICmpInst::ICMP_ULT) 2612 return getFalse(ITy); 2613 } 2614 2615 // 0 - (zext X) pred C 2616 if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) { 2617 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 2618 if (RHSC->getValue().isStrictlyPositive()) { 2619 if (Pred == ICmpInst::ICMP_SLT) 2620 return ConstantInt::getTrue(RHSC->getContext()); 2621 if (Pred == ICmpInst::ICMP_SGE) 2622 return ConstantInt::getFalse(RHSC->getContext()); 2623 if (Pred == ICmpInst::ICMP_EQ) 2624 return ConstantInt::getFalse(RHSC->getContext()); 2625 if (Pred == ICmpInst::ICMP_NE) 2626 return ConstantInt::getTrue(RHSC->getContext()); 2627 } 2628 if (RHSC->getValue().isNonNegative()) { 2629 if (Pred == ICmpInst::ICMP_SLE) 2630 return ConstantInt::getTrue(RHSC->getContext()); 2631 if (Pred == ICmpInst::ICMP_SGT) 2632 return ConstantInt::getFalse(RHSC->getContext()); 2633 } 2634 } 2635 } 2636 2637 // icmp pred (urem X, Y), Y 2638 if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) { 2639 bool KnownNonNegative, KnownNegative; 2640 switch (Pred) { 2641 default: 2642 break; 2643 case ICmpInst::ICMP_SGT: 2644 case ICmpInst::ICMP_SGE: 2645 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2646 Q.CxtI, Q.DT); 2647 if (!KnownNonNegative) 2648 break; 2649 // fall-through 2650 case ICmpInst::ICMP_EQ: 2651 case ICmpInst::ICMP_UGT: 2652 case ICmpInst::ICMP_UGE: 2653 return getFalse(ITy); 2654 case ICmpInst::ICMP_SLT: 2655 case ICmpInst::ICMP_SLE: 2656 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2657 Q.CxtI, Q.DT); 2658 if (!KnownNonNegative) 2659 break; 2660 // fall-through 2661 case ICmpInst::ICMP_NE: 2662 case ICmpInst::ICMP_ULT: 2663 case ICmpInst::ICMP_ULE: 2664 return getTrue(ITy); 2665 } 2666 } 2667 2668 // icmp pred X, (urem Y, X) 2669 if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) { 2670 bool KnownNonNegative, KnownNegative; 2671 switch (Pred) { 2672 default: 2673 break; 2674 case ICmpInst::ICMP_SGT: 2675 case ICmpInst::ICMP_SGE: 2676 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2677 Q.CxtI, Q.DT); 2678 if (!KnownNonNegative) 2679 break; 2680 // fall-through 2681 case ICmpInst::ICMP_NE: 2682 case ICmpInst::ICMP_UGT: 2683 case ICmpInst::ICMP_UGE: 2684 return getTrue(ITy); 2685 case ICmpInst::ICMP_SLT: 2686 case ICmpInst::ICMP_SLE: 2687 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2688 Q.CxtI, Q.DT); 2689 if (!KnownNonNegative) 2690 break; 2691 // fall-through 2692 case ICmpInst::ICMP_EQ: 2693 case ICmpInst::ICMP_ULT: 2694 case ICmpInst::ICMP_ULE: 2695 return getFalse(ITy); 2696 } 2697 } 2698 2699 // x udiv y <=u x. 2700 if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) { 2701 // icmp pred (X /u Y), X 2702 if (Pred == ICmpInst::ICMP_UGT) 2703 return getFalse(ITy); 2704 if (Pred == ICmpInst::ICMP_ULE) 2705 return getTrue(ITy); 2706 } 2707 2708 // handle: 2709 // CI2 << X == CI 2710 // CI2 << X != CI 2711 // 2712 // where CI2 is a power of 2 and CI isn't 2713 if (auto *CI = dyn_cast<ConstantInt>(RHS)) { 2714 const APInt *CI2Val, *CIVal = &CI->getValue(); 2715 if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) && 2716 CI2Val->isPowerOf2()) { 2717 if (!CIVal->isPowerOf2()) { 2718 // CI2 << X can equal zero in some circumstances, 2719 // this simplification is unsafe if CI is zero. 2720 // 2721 // We know it is safe if: 2722 // - The shift is nsw, we can't shift out the one bit. 2723 // - The shift is nuw, we can't shift out the one bit. 2724 // - CI2 is one 2725 // - CI isn't zero 2726 if (LBO->hasNoSignedWrap() || LBO->hasNoUnsignedWrap() || 2727 *CI2Val == 1 || !CI->isZero()) { 2728 if (Pred == ICmpInst::ICMP_EQ) 2729 return ConstantInt::getFalse(RHS->getContext()); 2730 if (Pred == ICmpInst::ICMP_NE) 2731 return ConstantInt::getTrue(RHS->getContext()); 2732 } 2733 } 2734 if (CIVal->isSignBit() && *CI2Val == 1) { 2735 if (Pred == ICmpInst::ICMP_UGT) 2736 return ConstantInt::getFalse(RHS->getContext()); 2737 if (Pred == ICmpInst::ICMP_ULE) 2738 return ConstantInt::getTrue(RHS->getContext()); 2739 } 2740 } 2741 } 2742 2743 if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() && 2744 LBO->getOperand(1) == RBO->getOperand(1)) { 2745 switch (LBO->getOpcode()) { 2746 default: break; 2747 case Instruction::UDiv: 2748 case Instruction::LShr: 2749 if (ICmpInst::isSigned(Pred)) 2750 break; 2751 // fall-through 2752 case Instruction::SDiv: 2753 case Instruction::AShr: 2754 if (!LBO->isExact() || !RBO->isExact()) 2755 break; 2756 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2757 RBO->getOperand(0), Q, MaxRecurse-1)) 2758 return V; 2759 break; 2760 case Instruction::Shl: { 2761 bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap(); 2762 bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap(); 2763 if (!NUW && !NSW) 2764 break; 2765 if (!NSW && ICmpInst::isSigned(Pred)) 2766 break; 2767 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2768 RBO->getOperand(0), Q, MaxRecurse-1)) 2769 return V; 2770 break; 2771 } 2772 } 2773 } 2774 2775 // Simplify comparisons involving max/min. 2776 Value *A, *B; 2777 CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE; 2778 CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B". 2779 2780 // Signed variants on "max(a,b)>=a -> true". 2781 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2782 if (A != RHS) std::swap(A, B); // smax(A, B) pred A. 2783 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2784 // We analyze this as smax(A, B) pred A. 2785 P = Pred; 2786 } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) && 2787 (A == LHS || B == LHS)) { 2788 if (A != LHS) std::swap(A, B); // A pred smax(A, B). 2789 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2790 // We analyze this as smax(A, B) swapped-pred A. 2791 P = CmpInst::getSwappedPredicate(Pred); 2792 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2793 (A == RHS || B == RHS)) { 2794 if (A != RHS) std::swap(A, B); // smin(A, B) pred A. 2795 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2796 // We analyze this as smax(-A, -B) swapped-pred -A. 2797 // Note that we do not need to actually form -A or -B thanks to EqP. 2798 P = CmpInst::getSwappedPredicate(Pred); 2799 } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) && 2800 (A == LHS || B == LHS)) { 2801 if (A != LHS) std::swap(A, B); // A pred smin(A, B). 2802 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2803 // We analyze this as smax(-A, -B) pred -A. 2804 // Note that we do not need to actually form -A or -B thanks to EqP. 2805 P = Pred; 2806 } 2807 if (P != CmpInst::BAD_ICMP_PREDICATE) { 2808 // Cases correspond to "max(A, B) p A". 2809 switch (P) { 2810 default: 2811 break; 2812 case CmpInst::ICMP_EQ: 2813 case CmpInst::ICMP_SLE: 2814 // Equivalent to "A EqP B". This may be the same as the condition tested 2815 // in the max/min; if so, we can just return that. 2816 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2817 return V; 2818 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2819 return V; 2820 // Otherwise, see if "A EqP B" simplifies. 2821 if (MaxRecurse) 2822 if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1)) 2823 return V; 2824 break; 2825 case CmpInst::ICMP_NE: 2826 case CmpInst::ICMP_SGT: { 2827 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2828 // Equivalent to "A InvEqP B". This may be the same as the condition 2829 // tested in the max/min; if so, we can just return that. 2830 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2831 return V; 2832 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2833 return V; 2834 // Otherwise, see if "A InvEqP B" simplifies. 2835 if (MaxRecurse) 2836 if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1)) 2837 return V; 2838 break; 2839 } 2840 case CmpInst::ICMP_SGE: 2841 // Always true. 2842 return getTrue(ITy); 2843 case CmpInst::ICMP_SLT: 2844 // Always false. 2845 return getFalse(ITy); 2846 } 2847 } 2848 2849 // Unsigned variants on "max(a,b)>=a -> true". 2850 P = CmpInst::BAD_ICMP_PREDICATE; 2851 if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2852 if (A != RHS) std::swap(A, B); // umax(A, B) pred A. 2853 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2854 // We analyze this as umax(A, B) pred A. 2855 P = Pred; 2856 } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) && 2857 (A == LHS || B == LHS)) { 2858 if (A != LHS) std::swap(A, B); // A pred umax(A, B). 2859 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2860 // We analyze this as umax(A, B) swapped-pred A. 2861 P = CmpInst::getSwappedPredicate(Pred); 2862 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2863 (A == RHS || B == RHS)) { 2864 if (A != RHS) std::swap(A, B); // umin(A, B) pred A. 2865 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2866 // We analyze this as umax(-A, -B) swapped-pred -A. 2867 // Note that we do not need to actually form -A or -B thanks to EqP. 2868 P = CmpInst::getSwappedPredicate(Pred); 2869 } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) && 2870 (A == LHS || B == LHS)) { 2871 if (A != LHS) std::swap(A, B); // A pred umin(A, B). 2872 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2873 // We analyze this as umax(-A, -B) pred -A. 2874 // Note that we do not need to actually form -A or -B thanks to EqP. 2875 P = Pred; 2876 } 2877 if (P != CmpInst::BAD_ICMP_PREDICATE) { 2878 // Cases correspond to "max(A, B) p A". 2879 switch (P) { 2880 default: 2881 break; 2882 case CmpInst::ICMP_EQ: 2883 case CmpInst::ICMP_ULE: 2884 // Equivalent to "A EqP B". This may be the same as the condition tested 2885 // in the max/min; if so, we can just return that. 2886 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2887 return V; 2888 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2889 return V; 2890 // Otherwise, see if "A EqP B" simplifies. 2891 if (MaxRecurse) 2892 if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1)) 2893 return V; 2894 break; 2895 case CmpInst::ICMP_NE: 2896 case CmpInst::ICMP_UGT: { 2897 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2898 // Equivalent to "A InvEqP B". This may be the same as the condition 2899 // tested in the max/min; if so, we can just return that. 2900 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2901 return V; 2902 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2903 return V; 2904 // Otherwise, see if "A InvEqP B" simplifies. 2905 if (MaxRecurse) 2906 if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1)) 2907 return V; 2908 break; 2909 } 2910 case CmpInst::ICMP_UGE: 2911 // Always true. 2912 return getTrue(ITy); 2913 case CmpInst::ICMP_ULT: 2914 // Always false. 2915 return getFalse(ITy); 2916 } 2917 } 2918 2919 // Variants on "max(x,y) >= min(x,z)". 2920 Value *C, *D; 2921 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && 2922 match(RHS, m_SMin(m_Value(C), m_Value(D))) && 2923 (A == C || A == D || B == C || B == D)) { 2924 // max(x, ?) pred min(x, ?). 2925 if (Pred == CmpInst::ICMP_SGE) 2926 // Always true. 2927 return getTrue(ITy); 2928 if (Pred == CmpInst::ICMP_SLT) 2929 // Always false. 2930 return getFalse(ITy); 2931 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2932 match(RHS, m_SMax(m_Value(C), m_Value(D))) && 2933 (A == C || A == D || B == C || B == D)) { 2934 // min(x, ?) pred max(x, ?). 2935 if (Pred == CmpInst::ICMP_SLE) 2936 // Always true. 2937 return getTrue(ITy); 2938 if (Pred == CmpInst::ICMP_SGT) 2939 // Always false. 2940 return getFalse(ITy); 2941 } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && 2942 match(RHS, m_UMin(m_Value(C), m_Value(D))) && 2943 (A == C || A == D || B == C || B == D)) { 2944 // max(x, ?) pred min(x, ?). 2945 if (Pred == CmpInst::ICMP_UGE) 2946 // Always true. 2947 return getTrue(ITy); 2948 if (Pred == CmpInst::ICMP_ULT) 2949 // Always false. 2950 return getFalse(ITy); 2951 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2952 match(RHS, m_UMax(m_Value(C), m_Value(D))) && 2953 (A == C || A == D || B == C || B == D)) { 2954 // min(x, ?) pred max(x, ?). 2955 if (Pred == CmpInst::ICMP_ULE) 2956 // Always true. 2957 return getTrue(ITy); 2958 if (Pred == CmpInst::ICMP_UGT) 2959 // Always false. 2960 return getFalse(ITy); 2961 } 2962 2963 // Simplify comparisons of related pointers using a powerful, recursive 2964 // GEP-walk when we have target data available.. 2965 if (LHS->getType()->isPointerTy()) 2966 if (Constant *C = computePointerICmp(Q.DL, Q.TLI, Pred, LHS, RHS)) 2967 return C; 2968 2969 if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) { 2970 if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) { 2971 if (GLHS->getPointerOperand() == GRHS->getPointerOperand() && 2972 GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() && 2973 (ICmpInst::isEquality(Pred) || 2974 (GLHS->isInBounds() && GRHS->isInBounds() && 2975 Pred == ICmpInst::getSignedPredicate(Pred)))) { 2976 // The bases are equal and the indices are constant. Build a constant 2977 // expression GEP with the same indices and a null base pointer to see 2978 // what constant folding can make out of it. 2979 Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType()); 2980 SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end()); 2981 Constant *NewLHS = ConstantExpr::getGetElementPtr( 2982 GLHS->getSourceElementType(), Null, IndicesLHS); 2983 2984 SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end()); 2985 Constant *NewRHS = ConstantExpr::getGetElementPtr( 2986 GLHS->getSourceElementType(), Null, IndicesRHS); 2987 return ConstantExpr::getICmp(Pred, NewLHS, NewRHS); 2988 } 2989 } 2990 } 2991 2992 // If a bit is known to be zero for A and known to be one for B, 2993 // then A and B cannot be equal. 2994 if (ICmpInst::isEquality(Pred)) { 2995 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2996 uint32_t BitWidth = CI->getBitWidth(); 2997 APInt LHSKnownZero(BitWidth, 0); 2998 APInt LHSKnownOne(BitWidth, 0); 2999 computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, Q.DL, /*Depth=*/0, Q.AC, 3000 Q.CxtI, Q.DT); 3001 const APInt &RHSVal = CI->getValue(); 3002 if (((LHSKnownZero & RHSVal) != 0) || ((LHSKnownOne & ~RHSVal) != 0)) 3003 return Pred == ICmpInst::ICMP_EQ 3004 ? ConstantInt::getFalse(CI->getContext()) 3005 : ConstantInt::getTrue(CI->getContext()); 3006 } 3007 } 3008 3009 // If the comparison is with the result of a select instruction, check whether 3010 // comparing with either branch of the select always yields the same value. 3011 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 3012 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse)) 3013 return V; 3014 3015 // If the comparison is with the result of a phi instruction, check whether 3016 // doing the compare with each incoming phi value yields a common result. 3017 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 3018 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) 3019 return V; 3020 3021 return nullptr; 3022 } 3023 3024 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3025 const DataLayout &DL, 3026 const TargetLibraryInfo *TLI, 3027 const DominatorTree *DT, AssumptionCache *AC, 3028 Instruction *CxtI) { 3029 return ::SimplifyICmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3030 RecursionLimit); 3031 } 3032 3033 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 3034 /// fold the result. If not, this returns null. 3035 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3036 const Query &Q, unsigned MaxRecurse) { 3037 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 3038 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 3039 3040 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 3041 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 3042 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI); 3043 3044 // If we have a constant, make sure it is on the RHS. 3045 std::swap(LHS, RHS); 3046 Pred = CmpInst::getSwappedPredicate(Pred); 3047 } 3048 3049 // Fold trivial predicates. 3050 if (Pred == FCmpInst::FCMP_FALSE) 3051 return ConstantInt::get(GetCompareTy(LHS), 0); 3052 if (Pred == FCmpInst::FCMP_TRUE) 3053 return ConstantInt::get(GetCompareTy(LHS), 1); 3054 3055 // fcmp pred x, undef and fcmp pred undef, x 3056 // fold to true if unordered, false if ordered 3057 if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) { 3058 // Choosing NaN for the undef will always make unordered comparison succeed 3059 // and ordered comparison fail. 3060 return ConstantInt::get(GetCompareTy(LHS), CmpInst::isUnordered(Pred)); 3061 } 3062 3063 // fcmp x,x -> true/false. Not all compares are foldable. 3064 if (LHS == RHS) { 3065 if (CmpInst::isTrueWhenEqual(Pred)) 3066 return ConstantInt::get(GetCompareTy(LHS), 1); 3067 if (CmpInst::isFalseWhenEqual(Pred)) 3068 return ConstantInt::get(GetCompareTy(LHS), 0); 3069 } 3070 3071 // Handle fcmp with constant RHS 3072 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) { 3073 // If the constant is a nan, see if we can fold the comparison based on it. 3074 if (CFP->getValueAPF().isNaN()) { 3075 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 3076 return ConstantInt::getFalse(CFP->getContext()); 3077 assert(FCmpInst::isUnordered(Pred) && 3078 "Comparison must be either ordered or unordered!"); 3079 // True if unordered. 3080 return ConstantInt::getTrue(CFP->getContext()); 3081 } 3082 // Check whether the constant is an infinity. 3083 if (CFP->getValueAPF().isInfinity()) { 3084 if (CFP->getValueAPF().isNegative()) { 3085 switch (Pred) { 3086 case FCmpInst::FCMP_OLT: 3087 // No value is ordered and less than negative infinity. 3088 return ConstantInt::getFalse(CFP->getContext()); 3089 case FCmpInst::FCMP_UGE: 3090 // All values are unordered with or at least negative infinity. 3091 return ConstantInt::getTrue(CFP->getContext()); 3092 default: 3093 break; 3094 } 3095 } else { 3096 switch (Pred) { 3097 case FCmpInst::FCMP_OGT: 3098 // No value is ordered and greater than infinity. 3099 return ConstantInt::getFalse(CFP->getContext()); 3100 case FCmpInst::FCMP_ULE: 3101 // All values are unordered with and at most infinity. 3102 return ConstantInt::getTrue(CFP->getContext()); 3103 default: 3104 break; 3105 } 3106 } 3107 } 3108 if (CFP->getValueAPF().isZero()) { 3109 switch (Pred) { 3110 case FCmpInst::FCMP_UGE: 3111 if (CannotBeOrderedLessThanZero(LHS)) 3112 return ConstantInt::getTrue(CFP->getContext()); 3113 break; 3114 case FCmpInst::FCMP_OLT: 3115 // X < 0 3116 if (CannotBeOrderedLessThanZero(LHS)) 3117 return ConstantInt::getFalse(CFP->getContext()); 3118 break; 3119 default: 3120 break; 3121 } 3122 } 3123 } 3124 3125 // If the comparison is with the result of a select instruction, check whether 3126 // comparing with either branch of the select always yields the same value. 3127 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 3128 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse)) 3129 return V; 3130 3131 // If the comparison is with the result of a phi instruction, check whether 3132 // doing the compare with each incoming phi value yields a common result. 3133 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 3134 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) 3135 return V; 3136 3137 return nullptr; 3138 } 3139 3140 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3141 const DataLayout &DL, 3142 const TargetLibraryInfo *TLI, 3143 const DominatorTree *DT, AssumptionCache *AC, 3144 const Instruction *CxtI) { 3145 return ::SimplifyFCmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3146 RecursionLimit); 3147 } 3148 3149 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 3150 /// the result. If not, this returns null. 3151 static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, 3152 Value *FalseVal, const Query &Q, 3153 unsigned MaxRecurse) { 3154 // select true, X, Y -> X 3155 // select false, X, Y -> Y 3156 if (Constant *CB = dyn_cast<Constant>(CondVal)) { 3157 if (CB->isAllOnesValue()) 3158 return TrueVal; 3159 if (CB->isNullValue()) 3160 return FalseVal; 3161 } 3162 3163 // select C, X, X -> X 3164 if (TrueVal == FalseVal) 3165 return TrueVal; 3166 3167 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 3168 if (isa<Constant>(TrueVal)) 3169 return TrueVal; 3170 return FalseVal; 3171 } 3172 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 3173 return FalseVal; 3174 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 3175 return TrueVal; 3176 3177 const auto *ICI = dyn_cast<ICmpInst>(CondVal); 3178 unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits(); 3179 if (ICI && BitWidth) { 3180 ICmpInst::Predicate Pred = ICI->getPredicate(); 3181 APInt MinSignedValue = APInt::getSignBit(BitWidth); 3182 Value *X; 3183 const APInt *Y; 3184 bool TrueWhenUnset; 3185 bool IsBitTest = false; 3186 if (ICmpInst::isEquality(Pred) && 3187 match(ICI->getOperand(0), m_And(m_Value(X), m_APInt(Y))) && 3188 match(ICI->getOperand(1), m_Zero())) { 3189 IsBitTest = true; 3190 TrueWhenUnset = Pred == ICmpInst::ICMP_EQ; 3191 } else if (Pred == ICmpInst::ICMP_SLT && 3192 match(ICI->getOperand(1), m_Zero())) { 3193 X = ICI->getOperand(0); 3194 Y = &MinSignedValue; 3195 IsBitTest = true; 3196 TrueWhenUnset = false; 3197 } else if (Pred == ICmpInst::ICMP_SGT && 3198 match(ICI->getOperand(1), m_AllOnes())) { 3199 X = ICI->getOperand(0); 3200 Y = &MinSignedValue; 3201 IsBitTest = true; 3202 TrueWhenUnset = true; 3203 } 3204 if (IsBitTest) { 3205 const APInt *C; 3206 // (X & Y) == 0 ? X & ~Y : X --> X 3207 // (X & Y) != 0 ? X & ~Y : X --> X & ~Y 3208 if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) && 3209 *Y == ~*C) 3210 return TrueWhenUnset ? FalseVal : TrueVal; 3211 // (X & Y) == 0 ? X : X & ~Y --> X & ~Y 3212 // (X & Y) != 0 ? X : X & ~Y --> X 3213 if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) && 3214 *Y == ~*C) 3215 return TrueWhenUnset ? FalseVal : TrueVal; 3216 3217 if (Y->isPowerOf2()) { 3218 // (X & Y) == 0 ? X | Y : X --> X | Y 3219 // (X & Y) != 0 ? X | Y : X --> X 3220 if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) && 3221 *Y == *C) 3222 return TrueWhenUnset ? TrueVal : FalseVal; 3223 // (X & Y) == 0 ? X : X | Y --> X 3224 // (X & Y) != 0 ? X : X | Y --> X | Y 3225 if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) && 3226 *Y == *C) 3227 return TrueWhenUnset ? TrueVal : FalseVal; 3228 } 3229 } 3230 } 3231 3232 return nullptr; 3233 } 3234 3235 Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, 3236 const DataLayout &DL, 3237 const TargetLibraryInfo *TLI, 3238 const DominatorTree *DT, AssumptionCache *AC, 3239 const Instruction *CxtI) { 3240 return ::SimplifySelectInst(Cond, TrueVal, FalseVal, 3241 Query(DL, TLI, DT, AC, CxtI), RecursionLimit); 3242 } 3243 3244 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 3245 /// fold the result. If not, this returns null. 3246 static Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops, 3247 const Query &Q, unsigned) { 3248 // The type of the GEP pointer operand. 3249 unsigned AS = 3250 cast<PointerType>(Ops[0]->getType()->getScalarType())->getAddressSpace(); 3251 3252 // getelementptr P -> P. 3253 if (Ops.size() == 1) 3254 return Ops[0]; 3255 3256 // Compute the (pointer) type returned by the GEP instruction. 3257 Type *LastType = GetElementPtrInst::getIndexedType(SrcTy, Ops.slice(1)); 3258 Type *GEPTy = PointerType::get(LastType, AS); 3259 if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType())) 3260 GEPTy = VectorType::get(GEPTy, VT->getNumElements()); 3261 3262 if (isa<UndefValue>(Ops[0])) 3263 return UndefValue::get(GEPTy); 3264 3265 if (Ops.size() == 2) { 3266 // getelementptr P, 0 -> P. 3267 if (match(Ops[1], m_Zero())) 3268 return Ops[0]; 3269 3270 Type *Ty = SrcTy; 3271 if (Ty->isSized()) { 3272 Value *P; 3273 uint64_t C; 3274 uint64_t TyAllocSize = Q.DL.getTypeAllocSize(Ty); 3275 // getelementptr P, N -> P if P points to a type of zero size. 3276 if (TyAllocSize == 0) 3277 return Ops[0]; 3278 3279 // The following transforms are only safe if the ptrtoint cast 3280 // doesn't truncate the pointers. 3281 if (Ops[1]->getType()->getScalarSizeInBits() == 3282 Q.DL.getPointerSizeInBits(AS)) { 3283 auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * { 3284 if (match(P, m_Zero())) 3285 return Constant::getNullValue(GEPTy); 3286 Value *Temp; 3287 if (match(P, m_PtrToInt(m_Value(Temp)))) 3288 if (Temp->getType() == GEPTy) 3289 return Temp; 3290 return nullptr; 3291 }; 3292 3293 // getelementptr V, (sub P, V) -> P if P points to a type of size 1. 3294 if (TyAllocSize == 1 && 3295 match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))))) 3296 if (Value *R = PtrToIntOrZero(P)) 3297 return R; 3298 3299 // getelementptr V, (ashr (sub P, V), C) -> Q 3300 // if P points to a type of size 1 << C. 3301 if (match(Ops[1], 3302 m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))), 3303 m_ConstantInt(C))) && 3304 TyAllocSize == 1ULL << C) 3305 if (Value *R = PtrToIntOrZero(P)) 3306 return R; 3307 3308 // getelementptr V, (sdiv (sub P, V), C) -> Q 3309 // if P points to a type of size C. 3310 if (match(Ops[1], 3311 m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))), 3312 m_SpecificInt(TyAllocSize)))) 3313 if (Value *R = PtrToIntOrZero(P)) 3314 return R; 3315 } 3316 } 3317 } 3318 3319 // Check to see if this is constant foldable. 3320 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 3321 if (!isa<Constant>(Ops[i])) 3322 return nullptr; 3323 3324 return ConstantExpr::getGetElementPtr(SrcTy, cast<Constant>(Ops[0]), 3325 Ops.slice(1)); 3326 } 3327 3328 Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout &DL, 3329 const TargetLibraryInfo *TLI, 3330 const DominatorTree *DT, AssumptionCache *AC, 3331 const Instruction *CxtI) { 3332 return ::SimplifyGEPInst( 3333 cast<PointerType>(Ops[0]->getType()->getScalarType())->getElementType(), 3334 Ops, Query(DL, TLI, DT, AC, CxtI), RecursionLimit); 3335 } 3336 3337 /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we 3338 /// can fold the result. If not, this returns null. 3339 static Value *SimplifyInsertValueInst(Value *Agg, Value *Val, 3340 ArrayRef<unsigned> Idxs, const Query &Q, 3341 unsigned) { 3342 if (Constant *CAgg = dyn_cast<Constant>(Agg)) 3343 if (Constant *CVal = dyn_cast<Constant>(Val)) 3344 return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs); 3345 3346 // insertvalue x, undef, n -> x 3347 if (match(Val, m_Undef())) 3348 return Agg; 3349 3350 // insertvalue x, (extractvalue y, n), n 3351 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val)) 3352 if (EV->getAggregateOperand()->getType() == Agg->getType() && 3353 EV->getIndices() == Idxs) { 3354 // insertvalue undef, (extractvalue y, n), n -> y 3355 if (match(Agg, m_Undef())) 3356 return EV->getAggregateOperand(); 3357 3358 // insertvalue y, (extractvalue y, n), n -> y 3359 if (Agg == EV->getAggregateOperand()) 3360 return Agg; 3361 } 3362 3363 return nullptr; 3364 } 3365 3366 Value *llvm::SimplifyInsertValueInst( 3367 Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, const DataLayout &DL, 3368 const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, 3369 const Instruction *CxtI) { 3370 return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query(DL, TLI, DT, AC, CxtI), 3371 RecursionLimit); 3372 } 3373 3374 /// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 3375 static Value *SimplifyPHINode(PHINode *PN, const Query &Q) { 3376 // If all of the PHI's incoming values are the same then replace the PHI node 3377 // with the common value. 3378 Value *CommonValue = nullptr; 3379 bool HasUndefInput = false; 3380 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 3381 Value *Incoming = PN->getIncomingValue(i); 3382 // If the incoming value is the phi node itself, it can safely be skipped. 3383 if (Incoming == PN) continue; 3384 if (isa<UndefValue>(Incoming)) { 3385 // Remember that we saw an undef value, but otherwise ignore them. 3386 HasUndefInput = true; 3387 continue; 3388 } 3389 if (CommonValue && Incoming != CommonValue) 3390 return nullptr; // Not the same, bail out. 3391 CommonValue = Incoming; 3392 } 3393 3394 // If CommonValue is null then all of the incoming values were either undef or 3395 // equal to the phi node itself. 3396 if (!CommonValue) 3397 return UndefValue::get(PN->getType()); 3398 3399 // If we have a PHI node like phi(X, undef, X), where X is defined by some 3400 // instruction, we cannot return X as the result of the PHI node unless it 3401 // dominates the PHI block. 3402 if (HasUndefInput) 3403 return ValueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr; 3404 3405 return CommonValue; 3406 } 3407 3408 static Value *SimplifyTruncInst(Value *Op, Type *Ty, const Query &Q, unsigned) { 3409 if (Constant *C = dyn_cast<Constant>(Op)) 3410 return ConstantFoldInstOperands(Instruction::Trunc, Ty, C, Q.DL, Q.TLI); 3411 3412 return nullptr; 3413 } 3414 3415 Value *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout &DL, 3416 const TargetLibraryInfo *TLI, 3417 const DominatorTree *DT, AssumptionCache *AC, 3418 const Instruction *CxtI) { 3419 return ::SimplifyTruncInst(Op, Ty, Query(DL, TLI, DT, AC, CxtI), 3420 RecursionLimit); 3421 } 3422 3423 //=== Helper functions for higher up the class hierarchy. 3424 3425 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 3426 /// fold the result. If not, this returns null. 3427 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 3428 const Query &Q, unsigned MaxRecurse) { 3429 switch (Opcode) { 3430 case Instruction::Add: 3431 return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 3432 Q, MaxRecurse); 3433 case Instruction::FAdd: 3434 return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3435 3436 case Instruction::Sub: 3437 return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 3438 Q, MaxRecurse); 3439 case Instruction::FSub: 3440 return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3441 3442 case Instruction::Mul: return SimplifyMulInst (LHS, RHS, Q, MaxRecurse); 3443 case Instruction::FMul: 3444 return SimplifyFMulInst (LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3445 case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, Q, MaxRecurse); 3446 case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse); 3447 case Instruction::FDiv: 3448 return SimplifyFDivInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3449 case Instruction::SRem: return SimplifySRemInst(LHS, RHS, Q, MaxRecurse); 3450 case Instruction::URem: return SimplifyURemInst(LHS, RHS, Q, MaxRecurse); 3451 case Instruction::FRem: 3452 return SimplifyFRemInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3453 case Instruction::Shl: 3454 return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 3455 Q, MaxRecurse); 3456 case Instruction::LShr: 3457 return SimplifyLShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse); 3458 case Instruction::AShr: 3459 return SimplifyAShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse); 3460 case Instruction::And: return SimplifyAndInst(LHS, RHS, Q, MaxRecurse); 3461 case Instruction::Or: return SimplifyOrInst (LHS, RHS, Q, MaxRecurse); 3462 case Instruction::Xor: return SimplifyXorInst(LHS, RHS, Q, MaxRecurse); 3463 default: 3464 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 3465 if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 3466 Constant *COps[] = {CLHS, CRHS}; 3467 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, Q.DL, 3468 Q.TLI); 3469 } 3470 3471 // If the operation is associative, try some generic simplifications. 3472 if (Instruction::isAssociative(Opcode)) 3473 if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, Q, MaxRecurse)) 3474 return V; 3475 3476 // If the operation is with the result of a select instruction check whether 3477 // operating on either branch of the select always yields the same value. 3478 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 3479 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, Q, MaxRecurse)) 3480 return V; 3481 3482 // If the operation is with the result of a phi instruction, check whether 3483 // operating on all incoming values of the phi always yields the same value. 3484 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 3485 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, Q, MaxRecurse)) 3486 return V; 3487 3488 return nullptr; 3489 } 3490 } 3491 3492 /// SimplifyFPBinOp - Given operands for a BinaryOperator, see if we can 3493 /// fold the result. If not, this returns null. 3494 /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the 3495 /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp. 3496 static Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS, 3497 const FastMathFlags &FMF, const Query &Q, 3498 unsigned MaxRecurse) { 3499 switch (Opcode) { 3500 case Instruction::FAdd: 3501 return SimplifyFAddInst(LHS, RHS, FMF, Q, MaxRecurse); 3502 case Instruction::FSub: 3503 return SimplifyFSubInst(LHS, RHS, FMF, Q, MaxRecurse); 3504 case Instruction::FMul: 3505 return SimplifyFMulInst(LHS, RHS, FMF, Q, MaxRecurse); 3506 default: 3507 return SimplifyBinOp(Opcode, LHS, RHS, Q, MaxRecurse); 3508 } 3509 } 3510 3511 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 3512 const DataLayout &DL, const TargetLibraryInfo *TLI, 3513 const DominatorTree *DT, AssumptionCache *AC, 3514 const Instruction *CxtI) { 3515 return ::SimplifyBinOp(Opcode, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3516 RecursionLimit); 3517 } 3518 3519 Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS, 3520 const FastMathFlags &FMF, const DataLayout &DL, 3521 const TargetLibraryInfo *TLI, 3522 const DominatorTree *DT, AssumptionCache *AC, 3523 const Instruction *CxtI) { 3524 return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Query(DL, TLI, DT, AC, CxtI), 3525 RecursionLimit); 3526 } 3527 3528 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can 3529 /// fold the result. 3530 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3531 const Query &Q, unsigned MaxRecurse) { 3532 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 3533 return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse); 3534 return SimplifyFCmpInst(Predicate, LHS, RHS, Q, MaxRecurse); 3535 } 3536 3537 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3538 const DataLayout &DL, const TargetLibraryInfo *TLI, 3539 const DominatorTree *DT, AssumptionCache *AC, 3540 const Instruction *CxtI) { 3541 return ::SimplifyCmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3542 RecursionLimit); 3543 } 3544 3545 static bool IsIdempotent(Intrinsic::ID ID) { 3546 switch (ID) { 3547 default: return false; 3548 3549 // Unary idempotent: f(f(x)) = f(x) 3550 case Intrinsic::fabs: 3551 case Intrinsic::floor: 3552 case Intrinsic::ceil: 3553 case Intrinsic::trunc: 3554 case Intrinsic::rint: 3555 case Intrinsic::nearbyint: 3556 case Intrinsic::round: 3557 return true; 3558 } 3559 } 3560 3561 template <typename IterTy> 3562 static Value *SimplifyIntrinsic(Intrinsic::ID IID, IterTy ArgBegin, IterTy ArgEnd, 3563 const Query &Q, unsigned MaxRecurse) { 3564 // Perform idempotent optimizations 3565 if (!IsIdempotent(IID)) 3566 return nullptr; 3567 3568 // Unary Ops 3569 if (std::distance(ArgBegin, ArgEnd) == 1) 3570 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*ArgBegin)) 3571 if (II->getIntrinsicID() == IID) 3572 return II; 3573 3574 return nullptr; 3575 } 3576 3577 template <typename IterTy> 3578 static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd, 3579 const Query &Q, unsigned MaxRecurse) { 3580 Type *Ty = V->getType(); 3581 if (PointerType *PTy = dyn_cast<PointerType>(Ty)) 3582 Ty = PTy->getElementType(); 3583 FunctionType *FTy = cast<FunctionType>(Ty); 3584 3585 // call undef -> undef 3586 if (isa<UndefValue>(V)) 3587 return UndefValue::get(FTy->getReturnType()); 3588 3589 Function *F = dyn_cast<Function>(V); 3590 if (!F) 3591 return nullptr; 3592 3593 if (unsigned IID = F->getIntrinsicID()) 3594 if (Value *Ret = 3595 SimplifyIntrinsic((Intrinsic::ID) IID, ArgBegin, ArgEnd, Q, MaxRecurse)) 3596 return Ret; 3597 3598 if (!canConstantFoldCallTo(F)) 3599 return nullptr; 3600 3601 SmallVector<Constant *, 4> ConstantArgs; 3602 ConstantArgs.reserve(ArgEnd - ArgBegin); 3603 for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) { 3604 Constant *C = dyn_cast<Constant>(*I); 3605 if (!C) 3606 return nullptr; 3607 ConstantArgs.push_back(C); 3608 } 3609 3610 return ConstantFoldCall(F, ConstantArgs, Q.TLI); 3611 } 3612 3613 Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin, 3614 User::op_iterator ArgEnd, const DataLayout &DL, 3615 const TargetLibraryInfo *TLI, const DominatorTree *DT, 3616 AssumptionCache *AC, const Instruction *CxtI) { 3617 return ::SimplifyCall(V, ArgBegin, ArgEnd, Query(DL, TLI, DT, AC, CxtI), 3618 RecursionLimit); 3619 } 3620 3621 Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args, 3622 const DataLayout &DL, const TargetLibraryInfo *TLI, 3623 const DominatorTree *DT, AssumptionCache *AC, 3624 const Instruction *CxtI) { 3625 return ::SimplifyCall(V, Args.begin(), Args.end(), 3626 Query(DL, TLI, DT, AC, CxtI), RecursionLimit); 3627 } 3628 3629 /// SimplifyInstruction - See if we can compute a simplified version of this 3630 /// instruction. If not, this returns null. 3631 Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout &DL, 3632 const TargetLibraryInfo *TLI, 3633 const DominatorTree *DT, AssumptionCache *AC) { 3634 Value *Result; 3635 3636 switch (I->getOpcode()) { 3637 default: 3638 Result = ConstantFoldInstruction(I, DL, TLI); 3639 break; 3640 case Instruction::FAdd: 3641 Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1), 3642 I->getFastMathFlags(), DL, TLI, DT, AC, I); 3643 break; 3644 case Instruction::Add: 3645 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 3646 cast<BinaryOperator>(I)->hasNoSignedWrap(), 3647 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL, 3648 TLI, DT, AC, I); 3649 break; 3650 case Instruction::FSub: 3651 Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1), 3652 I->getFastMathFlags(), DL, TLI, DT, AC, I); 3653 break; 3654 case Instruction::Sub: 3655 Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 3656 cast<BinaryOperator>(I)->hasNoSignedWrap(), 3657 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL, 3658 TLI, DT, AC, I); 3659 break; 3660 case Instruction::FMul: 3661 Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1), 3662 I->getFastMathFlags(), DL, TLI, DT, AC, I); 3663 break; 3664 case Instruction::Mul: 3665 Result = 3666 SimplifyMulInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 3667 break; 3668 case Instruction::SDiv: 3669 Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3670 AC, I); 3671 break; 3672 case Instruction::UDiv: 3673 Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3674 AC, I); 3675 break; 3676 case Instruction::FDiv: 3677 Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), 3678 I->getFastMathFlags(), DL, TLI, DT, AC, I); 3679 break; 3680 case Instruction::SRem: 3681 Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3682 AC, I); 3683 break; 3684 case Instruction::URem: 3685 Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3686 AC, I); 3687 break; 3688 case Instruction::FRem: 3689 Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), 3690 I->getFastMathFlags(), DL, TLI, DT, AC, I); 3691 break; 3692 case Instruction::Shl: 3693 Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), 3694 cast<BinaryOperator>(I)->hasNoSignedWrap(), 3695 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL, 3696 TLI, DT, AC, I); 3697 break; 3698 case Instruction::LShr: 3699 Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), 3700 cast<BinaryOperator>(I)->isExact(), DL, TLI, DT, 3701 AC, I); 3702 break; 3703 case Instruction::AShr: 3704 Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), 3705 cast<BinaryOperator>(I)->isExact(), DL, TLI, DT, 3706 AC, I); 3707 break; 3708 case Instruction::And: 3709 Result = 3710 SimplifyAndInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 3711 break; 3712 case Instruction::Or: 3713 Result = 3714 SimplifyOrInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 3715 break; 3716 case Instruction::Xor: 3717 Result = 3718 SimplifyXorInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 3719 break; 3720 case Instruction::ICmp: 3721 Result = 3722 SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), I->getOperand(0), 3723 I->getOperand(1), DL, TLI, DT, AC, I); 3724 break; 3725 case Instruction::FCmp: 3726 Result = 3727 SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), I->getOperand(0), 3728 I->getOperand(1), DL, TLI, DT, AC, I); 3729 break; 3730 case Instruction::Select: 3731 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 3732 I->getOperand(2), DL, TLI, DT, AC, I); 3733 break; 3734 case Instruction::GetElementPtr: { 3735 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 3736 Result = SimplifyGEPInst(Ops, DL, TLI, DT, AC, I); 3737 break; 3738 } 3739 case Instruction::InsertValue: { 3740 InsertValueInst *IV = cast<InsertValueInst>(I); 3741 Result = SimplifyInsertValueInst(IV->getAggregateOperand(), 3742 IV->getInsertedValueOperand(), 3743 IV->getIndices(), DL, TLI, DT, AC, I); 3744 break; 3745 } 3746 case Instruction::PHI: 3747 Result = SimplifyPHINode(cast<PHINode>(I), Query(DL, TLI, DT, AC, I)); 3748 break; 3749 case Instruction::Call: { 3750 CallSite CS(cast<CallInst>(I)); 3751 Result = SimplifyCall(CS.getCalledValue(), CS.arg_begin(), CS.arg_end(), DL, 3752 TLI, DT, AC, I); 3753 break; 3754 } 3755 case Instruction::Trunc: 3756 Result = 3757 SimplifyTruncInst(I->getOperand(0), I->getType(), DL, TLI, DT, AC, I); 3758 break; 3759 } 3760 3761 /// If called on unreachable code, the above logic may report that the 3762 /// instruction simplified to itself. Make life easier for users by 3763 /// detecting that case here, returning a safe value instead. 3764 return Result == I ? UndefValue::get(I->getType()) : Result; 3765 } 3766 3767 /// \brief Implementation of recursive simplification through an instructions 3768 /// uses. 3769 /// 3770 /// This is the common implementation of the recursive simplification routines. 3771 /// If we have a pre-simplified value in 'SimpleV', that is forcibly used to 3772 /// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of 3773 /// instructions to process and attempt to simplify it using 3774 /// InstructionSimplify. 3775 /// 3776 /// This routine returns 'true' only when *it* simplifies something. The passed 3777 /// in simplified value does not count toward this. 3778 static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV, 3779 const TargetLibraryInfo *TLI, 3780 const DominatorTree *DT, 3781 AssumptionCache *AC) { 3782 bool Simplified = false; 3783 SmallSetVector<Instruction *, 8> Worklist; 3784 const DataLayout &DL = I->getModule()->getDataLayout(); 3785 3786 // If we have an explicit value to collapse to, do that round of the 3787 // simplification loop by hand initially. 3788 if (SimpleV) { 3789 for (User *U : I->users()) 3790 if (U != I) 3791 Worklist.insert(cast<Instruction>(U)); 3792 3793 // Replace the instruction with its simplified value. 3794 I->replaceAllUsesWith(SimpleV); 3795 3796 // Gracefully handle edge cases where the instruction is not wired into any 3797 // parent block. 3798 if (I->getParent()) 3799 I->eraseFromParent(); 3800 } else { 3801 Worklist.insert(I); 3802 } 3803 3804 // Note that we must test the size on each iteration, the worklist can grow. 3805 for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) { 3806 I = Worklist[Idx]; 3807 3808 // See if this instruction simplifies. 3809 SimpleV = SimplifyInstruction(I, DL, TLI, DT, AC); 3810 if (!SimpleV) 3811 continue; 3812 3813 Simplified = true; 3814 3815 // Stash away all the uses of the old instruction so we can check them for 3816 // recursive simplifications after a RAUW. This is cheaper than checking all 3817 // uses of To on the recursive step in most cases. 3818 for (User *U : I->users()) 3819 Worklist.insert(cast<Instruction>(U)); 3820 3821 // Replace the instruction with its simplified value. 3822 I->replaceAllUsesWith(SimpleV); 3823 3824 // Gracefully handle edge cases where the instruction is not wired into any 3825 // parent block. 3826 if (I->getParent()) 3827 I->eraseFromParent(); 3828 } 3829 return Simplified; 3830 } 3831 3832 bool llvm::recursivelySimplifyInstruction(Instruction *I, 3833 const TargetLibraryInfo *TLI, 3834 const DominatorTree *DT, 3835 AssumptionCache *AC) { 3836 return replaceAndRecursivelySimplifyImpl(I, nullptr, TLI, DT, AC); 3837 } 3838 3839 bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, 3840 const TargetLibraryInfo *TLI, 3841 const DominatorTree *DT, 3842 AssumptionCache *AC) { 3843 assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!"); 3844 assert(SimpleV && "Must provide a simplified value."); 3845 return replaceAndRecursivelySimplifyImpl(I, SimpleV, TLI, DT, AC); 3846 } 3847