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