InstructionSimplify.cpp revision 28e215ba63164f201292f8c77bf038b4282aa052
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#define DEBUG_TYPE "instsimplify" 21#include "llvm/Operator.h" 22#include "llvm/ADT/Statistic.h" 23#include "llvm/Analysis/InstructionSimplify.h" 24#include "llvm/Analysis/AliasAnalysis.h" 25#include "llvm/Analysis/ConstantFolding.h" 26#include "llvm/Analysis/Dominators.h" 27#include "llvm/Analysis/ValueTracking.h" 28#include "llvm/Support/ConstantRange.h" 29#include "llvm/Support/PatternMatch.h" 30#include "llvm/Support/ValueHandle.h" 31#include "llvm/Target/TargetData.h" 32using namespace llvm; 33using namespace llvm::PatternMatch; 34 35enum { RecursionLimit = 3 }; 36 37STATISTIC(NumExpand, "Number of expansions"); 38STATISTIC(NumFactor , "Number of factorizations"); 39STATISTIC(NumReassoc, "Number of reassociations"); 40 41static Value *SimplifyAndInst(Value *, Value *, const TargetData *, 42 const TargetLibraryInfo *, const DominatorTree *, 43 unsigned); 44static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *, 45 const TargetLibraryInfo *, const DominatorTree *, 46 unsigned); 47static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *, 48 const TargetLibraryInfo *, const DominatorTree *, 49 unsigned); 50static Value *SimplifyOrInst(Value *, Value *, const TargetData *, 51 const TargetLibraryInfo *, const DominatorTree *, 52 unsigned); 53static Value *SimplifyXorInst(Value *, Value *, const TargetData *, 54 const TargetLibraryInfo *, const DominatorTree *, 55 unsigned); 56 57/// getFalse - For a boolean type, or a vector of boolean type, return false, or 58/// a vector with every element false, as appropriate for the type. 59static Constant *getFalse(Type *Ty) { 60 assert(Ty->getScalarType()->isIntegerTy(1) && 61 "Expected i1 type or a vector of i1!"); 62 return Constant::getNullValue(Ty); 63} 64 65/// getTrue - For a boolean type, or a vector of boolean type, return true, or 66/// a vector with every element true, as appropriate for the type. 67static Constant *getTrue(Type *Ty) { 68 assert(Ty->getScalarType()->isIntegerTy(1) && 69 "Expected i1 type or a vector of i1!"); 70 return Constant::getAllOnesValue(Ty); 71} 72 73/// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"? 74static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS, 75 Value *RHS) { 76 CmpInst *Cmp = dyn_cast<CmpInst>(V); 77 if (!Cmp) 78 return false; 79 CmpInst::Predicate CPred = Cmp->getPredicate(); 80 Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1); 81 if (CPred == Pred && CLHS == LHS && CRHS == RHS) 82 return true; 83 return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS && 84 CRHS == LHS; 85} 86 87/// ValueDominatesPHI - Does the given value dominate the specified phi node? 88static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 89 Instruction *I = dyn_cast<Instruction>(V); 90 if (!I) 91 // Arguments and constants dominate all instructions. 92 return true; 93 94 // If we have a DominatorTree then do a precise test. 95 if (DT) 96 return DT->dominates(I, P); 97 98 // Otherwise, if the instruction is in the entry block, and is not an invoke, 99 // then it obviously dominates all phi nodes. 100 if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 101 !isa<InvokeInst>(I)) 102 return true; 103 104 return false; 105} 106 107/// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning 108/// it into "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is 109/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. 110/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". 111/// Returns the simplified value, or null if no simplification was performed. 112static Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS, 113 unsigned OpcToExpand, const TargetData *TD, 114 const TargetLibraryInfo *TLI, const DominatorTree *DT, 115 unsigned MaxRecurse) { 116 Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand; 117 // Recursion is always used, so bail out at once if we already hit the limit. 118 if (!MaxRecurse--) 119 return 0; 120 121 // Check whether the expression has the form "(A op' B) op C". 122 if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) 123 if (Op0->getOpcode() == OpcodeToExpand) { 124 // It does! Try turning it into "(A op C) op' (B op C)". 125 Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 126 // Do "A op C" and "B op C" both simplify? 127 if (Value *L = SimplifyBinOp(Opcode, A, C, TD, TLI, DT, MaxRecurse)) 128 if (Value *R = SimplifyBinOp(Opcode, B, C, TD, TLI, DT, MaxRecurse)) { 129 // They do! Return "L op' R" if it simplifies or is already available. 130 // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. 131 if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand) 132 && L == B && R == A)) { 133 ++NumExpand; 134 return LHS; 135 } 136 // Otherwise return "L op' R" if it simplifies. 137 if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, TLI, DT, 138 MaxRecurse)) { 139 ++NumExpand; 140 return V; 141 } 142 } 143 } 144 145 // Check whether the expression has the form "A op (B op' C)". 146 if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS)) 147 if (Op1->getOpcode() == OpcodeToExpand) { 148 // It does! Try turning it into "(A op B) op' (A op C)". 149 Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 150 // Do "A op B" and "A op C" both simplify? 151 if (Value *L = SimplifyBinOp(Opcode, A, B, TD, TLI, DT, MaxRecurse)) 152 if (Value *R = SimplifyBinOp(Opcode, A, C, TD, TLI, DT, MaxRecurse)) { 153 // They do! Return "L op' R" if it simplifies or is already available. 154 // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. 155 if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand) 156 && L == C && R == B)) { 157 ++NumExpand; 158 return RHS; 159 } 160 // Otherwise return "L op' R" if it simplifies. 161 if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, TLI, DT, 162 MaxRecurse)) { 163 ++NumExpand; 164 return V; 165 } 166 } 167 } 168 169 return 0; 170} 171 172/// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term 173/// using the operation OpCodeToExtract. For example, when Opcode is Add and 174/// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)". 175/// Returns the simplified value, or null if no simplification was performed. 176static Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS, 177 unsigned OpcToExtract, const TargetData *TD, 178 const TargetLibraryInfo *TLI, 179 const DominatorTree *DT, 180 unsigned MaxRecurse) { 181 Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract; 182 // Recursion is always used, so bail out at once if we already hit the limit. 183 if (!MaxRecurse--) 184 return 0; 185 186 BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 187 BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 188 189 if (!Op0 || Op0->getOpcode() != OpcodeToExtract || 190 !Op1 || Op1->getOpcode() != OpcodeToExtract) 191 return 0; 192 193 // The expression has the form "(A op' B) op (C op' D)". 194 Value *A = Op0->getOperand(0), *B = Op0->getOperand(1); 195 Value *C = Op1->getOperand(0), *D = Op1->getOperand(1); 196 197 // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)". 198 // Does the instruction have the form "(A op' B) op (A op' D)" or, in the 199 // commutative case, "(A op' B) op (C op' A)"? 200 if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) { 201 Value *DD = A == C ? D : C; 202 // Form "A op' (B op DD)" if it simplifies completely. 203 // Does "B op DD" simplify? 204 if (Value *V = SimplifyBinOp(Opcode, B, DD, TD, TLI, DT, MaxRecurse)) { 205 // It does! Return "A op' V" if it simplifies or is already available. 206 // If V equals B then "A op' V" is just the LHS. If V equals DD then 207 // "A op' V" is just the RHS. 208 if (V == B || V == DD) { 209 ++NumFactor; 210 return V == B ? LHS : RHS; 211 } 212 // Otherwise return "A op' V" if it simplifies. 213 if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, TD, TLI, DT, 214 MaxRecurse)) { 215 ++NumFactor; 216 return W; 217 } 218 } 219 } 220 221 // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)". 222 // Does the instruction have the form "(A op' B) op (C op' B)" or, in the 223 // commutative case, "(A op' B) op (B op' D)"? 224 if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) { 225 Value *CC = B == D ? C : D; 226 // Form "(A op CC) op' B" if it simplifies completely.. 227 // Does "A op CC" simplify? 228 if (Value *V = SimplifyBinOp(Opcode, A, CC, TD, TLI, DT, MaxRecurse)) { 229 // It does! Return "V op' B" if it simplifies or is already available. 230 // If V equals A then "V op' B" is just the LHS. If V equals CC then 231 // "V op' B" is just the RHS. 232 if (V == A || V == CC) { 233 ++NumFactor; 234 return V == A ? LHS : RHS; 235 } 236 // Otherwise return "V op' B" if it simplifies. 237 if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, TD, TLI, DT, 238 MaxRecurse)) { 239 ++NumFactor; 240 return W; 241 } 242 } 243 } 244 245 return 0; 246} 247 248/// SimplifyAssociativeBinOp - Generic simplifications for associative binary 249/// operations. Returns the simpler value, or null if none was found. 250static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, 251 const TargetData *TD, 252 const TargetLibraryInfo *TLI, 253 const DominatorTree *DT, 254 unsigned MaxRecurse) { 255 Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc; 256 assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 257 258 // Recursion is always used, so bail out at once if we already hit the limit. 259 if (!MaxRecurse--) 260 return 0; 261 262 BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 263 BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 264 265 // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 266 if (Op0 && Op0->getOpcode() == Opcode) { 267 Value *A = Op0->getOperand(0); 268 Value *B = Op0->getOperand(1); 269 Value *C = RHS; 270 271 // Does "B op C" simplify? 272 if (Value *V = SimplifyBinOp(Opcode, B, C, TD, TLI, DT, MaxRecurse)) { 273 // It does! Return "A op V" if it simplifies or is already available. 274 // If V equals B then "A op V" is just the LHS. 275 if (V == B) return LHS; 276 // Otherwise return "A op V" if it simplifies. 277 if (Value *W = SimplifyBinOp(Opcode, A, V, TD, TLI, DT, MaxRecurse)) { 278 ++NumReassoc; 279 return W; 280 } 281 } 282 } 283 284 // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 285 if (Op1 && Op1->getOpcode() == Opcode) { 286 Value *A = LHS; 287 Value *B = Op1->getOperand(0); 288 Value *C = Op1->getOperand(1); 289 290 // Does "A op B" simplify? 291 if (Value *V = SimplifyBinOp(Opcode, A, B, TD, TLI, DT, MaxRecurse)) { 292 // It does! Return "V op C" if it simplifies or is already available. 293 // If V equals B then "V op C" is just the RHS. 294 if (V == B) return RHS; 295 // Otherwise return "V op C" if it simplifies. 296 if (Value *W = SimplifyBinOp(Opcode, V, C, TD, TLI, DT, MaxRecurse)) { 297 ++NumReassoc; 298 return W; 299 } 300 } 301 } 302 303 // The remaining transforms require commutativity as well as associativity. 304 if (!Instruction::isCommutative(Opcode)) 305 return 0; 306 307 // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 308 if (Op0 && Op0->getOpcode() == Opcode) { 309 Value *A = Op0->getOperand(0); 310 Value *B = Op0->getOperand(1); 311 Value *C = RHS; 312 313 // Does "C op A" simplify? 314 if (Value *V = SimplifyBinOp(Opcode, C, A, TD, TLI, DT, MaxRecurse)) { 315 // It does! Return "V op B" if it simplifies or is already available. 316 // If V equals A then "V op B" is just the LHS. 317 if (V == A) return LHS; 318 // Otherwise return "V op B" if it simplifies. 319 if (Value *W = SimplifyBinOp(Opcode, V, B, TD, TLI, DT, MaxRecurse)) { 320 ++NumReassoc; 321 return W; 322 } 323 } 324 } 325 326 // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 327 if (Op1 && Op1->getOpcode() == Opcode) { 328 Value *A = LHS; 329 Value *B = Op1->getOperand(0); 330 Value *C = Op1->getOperand(1); 331 332 // Does "C op A" simplify? 333 if (Value *V = SimplifyBinOp(Opcode, C, A, TD, TLI, DT, MaxRecurse)) { 334 // It does! Return "B op V" if it simplifies or is already available. 335 // If V equals C then "B op V" is just the RHS. 336 if (V == C) return RHS; 337 // Otherwise return "B op V" if it simplifies. 338 if (Value *W = SimplifyBinOp(Opcode, B, V, TD, TLI, DT, MaxRecurse)) { 339 ++NumReassoc; 340 return W; 341 } 342 } 343 } 344 345 return 0; 346} 347 348/// ThreadBinOpOverSelect - In the case of a binary operation with a select 349/// instruction as an operand, try to simplify the binop by seeing whether 350/// evaluating it on both branches of the select results in the same value. 351/// Returns the common value if so, otherwise returns null. 352static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 353 const TargetData *TD, 354 const TargetLibraryInfo *TLI, 355 const DominatorTree *DT, 356 unsigned MaxRecurse) { 357 // Recursion is always used, so bail out at once if we already hit the limit. 358 if (!MaxRecurse--) 359 return 0; 360 361 SelectInst *SI; 362 if (isa<SelectInst>(LHS)) { 363 SI = cast<SelectInst>(LHS); 364 } else { 365 assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 366 SI = cast<SelectInst>(RHS); 367 } 368 369 // Evaluate the BinOp on the true and false branches of the select. 370 Value *TV; 371 Value *FV; 372 if (SI == LHS) { 373 TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, TLI, DT, MaxRecurse); 374 FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, TLI, DT, MaxRecurse); 375 } else { 376 TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, TLI, DT, MaxRecurse); 377 FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, TLI, DT, MaxRecurse); 378 } 379 380 // If they simplified to the same value, then return the common value. 381 // If they both failed to simplify then return null. 382 if (TV == FV) 383 return TV; 384 385 // If one branch simplified to undef, return the other one. 386 if (TV && isa<UndefValue>(TV)) 387 return FV; 388 if (FV && isa<UndefValue>(FV)) 389 return TV; 390 391 // If applying the operation did not change the true and false select values, 392 // then the result of the binop is the select itself. 393 if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 394 return SI; 395 396 // If one branch simplified and the other did not, and the simplified 397 // value is equal to the unsimplified one, return the simplified value. 398 // For example, select (cond, X, X & Z) & Z -> X & Z. 399 if ((FV && !TV) || (TV && !FV)) { 400 // Check that the simplified value has the form "X op Y" where "op" is the 401 // same as the original operation. 402 Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 403 if (Simplified && Simplified->getOpcode() == Opcode) { 404 // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 405 // We already know that "op" is the same as for the simplified value. See 406 // if the operands match too. If so, return the simplified value. 407 Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 408 Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 409 Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 410 if (Simplified->getOperand(0) == UnsimplifiedLHS && 411 Simplified->getOperand(1) == UnsimplifiedRHS) 412 return Simplified; 413 if (Simplified->isCommutative() && 414 Simplified->getOperand(1) == UnsimplifiedLHS && 415 Simplified->getOperand(0) == UnsimplifiedRHS) 416 return Simplified; 417 } 418 } 419 420 return 0; 421} 422 423/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 424/// try to simplify the comparison by seeing whether both branches of the select 425/// result in the same value. Returns the common value if so, otherwise returns 426/// null. 427static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 428 Value *RHS, const TargetData *TD, 429 const TargetLibraryInfo *TLI, 430 const DominatorTree *DT, 431 unsigned MaxRecurse) { 432 // Recursion is always used, so bail out at once if we already hit the limit. 433 if (!MaxRecurse--) 434 return 0; 435 436 // Make sure the select is on the LHS. 437 if (!isa<SelectInst>(LHS)) { 438 std::swap(LHS, RHS); 439 Pred = CmpInst::getSwappedPredicate(Pred); 440 } 441 assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 442 SelectInst *SI = cast<SelectInst>(LHS); 443 Value *Cond = SI->getCondition(); 444 Value *TV = SI->getTrueValue(); 445 Value *FV = SI->getFalseValue(); 446 447 // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it. 448 // Does "cmp TV, RHS" simplify? 449 Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, TD, TLI, DT, MaxRecurse); 450 if (TCmp == Cond) { 451 // It not only simplified, it simplified to the select condition. Replace 452 // it with 'true'. 453 TCmp = getTrue(Cond->getType()); 454 } else if (!TCmp) { 455 // It didn't simplify. However if "cmp TV, RHS" is equal to the select 456 // condition then we can replace it with 'true'. Otherwise give up. 457 if (!isSameCompare(Cond, Pred, TV, RHS)) 458 return 0; 459 TCmp = getTrue(Cond->getType()); 460 } 461 462 // Does "cmp FV, RHS" simplify? 463 Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, TD, TLI, DT, MaxRecurse); 464 if (FCmp == Cond) { 465 // It not only simplified, it simplified to the select condition. Replace 466 // it with 'false'. 467 FCmp = getFalse(Cond->getType()); 468 } else if (!FCmp) { 469 // It didn't simplify. However if "cmp FV, RHS" is equal to the select 470 // condition then we can replace it with 'false'. Otherwise give up. 471 if (!isSameCompare(Cond, Pred, FV, RHS)) 472 return 0; 473 FCmp = getFalse(Cond->getType()); 474 } 475 476 // If both sides simplified to the same value, then use it as the result of 477 // the original comparison. 478 if (TCmp == FCmp) 479 return TCmp; 480 481 // The remaining cases only make sense if the select condition has the same 482 // type as the result of the comparison, so bail out if this is not so. 483 if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy()) 484 return 0; 485 // If the false value simplified to false, then the result of the compare 486 // is equal to "Cond && TCmp". This also catches the case when the false 487 // value simplified to false and the true value to true, returning "Cond". 488 if (match(FCmp, m_Zero())) 489 if (Value *V = SimplifyAndInst(Cond, TCmp, TD, TLI, DT, MaxRecurse)) 490 return V; 491 // If the true value simplified to true, then the result of the compare 492 // is equal to "Cond || FCmp". 493 if (match(TCmp, m_One())) 494 if (Value *V = SimplifyOrInst(Cond, FCmp, TD, TLI, DT, MaxRecurse)) 495 return V; 496 // Finally, if the false value simplified to true and the true value to 497 // false, then the result of the compare is equal to "!Cond". 498 if (match(FCmp, m_One()) && match(TCmp, m_Zero())) 499 if (Value *V = 500 SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()), 501 TD, TLI, DT, MaxRecurse)) 502 return V; 503 504 return 0; 505} 506 507/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 508/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 509/// it on the incoming phi values yields the same result for every value. If so 510/// returns the common value, otherwise returns null. 511static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 512 const TargetData *TD, 513 const TargetLibraryInfo *TLI, 514 const DominatorTree *DT, 515 unsigned MaxRecurse) { 516 // Recursion is always used, so bail out at once if we already hit the limit. 517 if (!MaxRecurse--) 518 return 0; 519 520 PHINode *PI; 521 if (isa<PHINode>(LHS)) { 522 PI = cast<PHINode>(LHS); 523 // Bail out if RHS and the phi may be mutually interdependent due to a loop. 524 if (!ValueDominatesPHI(RHS, PI, DT)) 525 return 0; 526 } else { 527 assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 528 PI = cast<PHINode>(RHS); 529 // Bail out if LHS and the phi may be mutually interdependent due to a loop. 530 if (!ValueDominatesPHI(LHS, PI, DT)) 531 return 0; 532 } 533 534 // Evaluate the BinOp on the incoming phi values. 535 Value *CommonValue = 0; 536 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 537 Value *Incoming = PI->getIncomingValue(i); 538 // If the incoming value is the phi node itself, it can safely be skipped. 539 if (Incoming == PI) continue; 540 Value *V = PI == LHS ? 541 SimplifyBinOp(Opcode, Incoming, RHS, TD, TLI, DT, MaxRecurse) : 542 SimplifyBinOp(Opcode, LHS, Incoming, TD, TLI, DT, MaxRecurse); 543 // If the operation failed to simplify, or simplified to a different value 544 // to previously, then give up. 545 if (!V || (CommonValue && V != CommonValue)) 546 return 0; 547 CommonValue = V; 548 } 549 550 return CommonValue; 551} 552 553/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 554/// try to simplify the comparison by seeing whether comparing with all of the 555/// incoming phi values yields the same result every time. If so returns the 556/// common result, otherwise returns null. 557static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 558 const TargetData *TD, 559 const TargetLibraryInfo *TLI, 560 const DominatorTree *DT, 561 unsigned MaxRecurse) { 562 // Recursion is always used, so bail out at once if we already hit the limit. 563 if (!MaxRecurse--) 564 return 0; 565 566 // Make sure the phi is on the LHS. 567 if (!isa<PHINode>(LHS)) { 568 std::swap(LHS, RHS); 569 Pred = CmpInst::getSwappedPredicate(Pred); 570 } 571 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 572 PHINode *PI = cast<PHINode>(LHS); 573 574 // Bail out if RHS and the phi may be mutually interdependent due to a loop. 575 if (!ValueDominatesPHI(RHS, PI, DT)) 576 return 0; 577 578 // Evaluate the BinOp on the incoming phi values. 579 Value *CommonValue = 0; 580 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 581 Value *Incoming = PI->getIncomingValue(i); 582 // If the incoming value is the phi node itself, it can safely be skipped. 583 if (Incoming == PI) continue; 584 Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, TLI, DT, MaxRecurse); 585 // If the operation failed to simplify, or simplified to a different value 586 // to previously, then give up. 587 if (!V || (CommonValue && V != CommonValue)) 588 return 0; 589 CommonValue = V; 590 } 591 592 return CommonValue; 593} 594 595/// SimplifyAddInst - Given operands for an Add, see if we can 596/// fold the result. If not, this returns null. 597static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 598 const TargetData *TD, 599 const TargetLibraryInfo *TLI, 600 const DominatorTree *DT, 601 unsigned MaxRecurse) { 602 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 603 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 604 Constant *Ops[] = { CLHS, CRHS }; 605 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 606 Ops, TD, TLI); 607 } 608 609 // Canonicalize the constant to the RHS. 610 std::swap(Op0, Op1); 611 } 612 613 // X + undef -> undef 614 if (match(Op1, m_Undef())) 615 return Op1; 616 617 // X + 0 -> X 618 if (match(Op1, m_Zero())) 619 return Op0; 620 621 // X + (Y - X) -> Y 622 // (Y - X) + X -> Y 623 // Eg: X + -X -> 0 624 Value *Y = 0; 625 if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 626 match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 627 return Y; 628 629 // X + ~X -> -1 since ~X = -X-1 630 if (match(Op0, m_Not(m_Specific(Op1))) || 631 match(Op1, m_Not(m_Specific(Op0)))) 632 return Constant::getAllOnesValue(Op0->getType()); 633 634 /// i1 add -> xor. 635 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 636 if (Value *V = SimplifyXorInst(Op0, Op1, TD, TLI, DT, MaxRecurse-1)) 637 return V; 638 639 // Try some generic simplifications for associative operations. 640 if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, TLI, DT, 641 MaxRecurse)) 642 return V; 643 644 // Mul distributes over Add. Try some generic simplifications based on this. 645 if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul, 646 TD, TLI, DT, MaxRecurse)) 647 return V; 648 649 // Threading Add over selects and phi nodes is pointless, so don't bother. 650 // Threading over the select in "A + select(cond, B, C)" means evaluating 651 // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 652 // only if B and C are equal. If B and C are equal then (since we assume 653 // that operands have already been simplified) "select(cond, B, C)" should 654 // have been simplified to the common value of B and C already. Analysing 655 // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 656 // for threading over phi nodes. 657 658 return 0; 659} 660 661Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 662 const TargetData *TD, const TargetLibraryInfo *TLI, 663 const DominatorTree *DT) { 664 return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, TLI, DT, RecursionLimit); 665} 666 667/// SimplifySubInst - Given operands for a Sub, see if we can 668/// fold the result. If not, this returns null. 669static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 670 const TargetData *TD, 671 const TargetLibraryInfo *TLI, 672 const DominatorTree *DT, 673 unsigned MaxRecurse) { 674 if (Constant *CLHS = dyn_cast<Constant>(Op0)) 675 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 676 Constant *Ops[] = { CLHS, CRHS }; 677 return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 678 Ops, TD, TLI); 679 } 680 681 // X - undef -> undef 682 // undef - X -> undef 683 if (match(Op0, m_Undef()) || match(Op1, m_Undef())) 684 return UndefValue::get(Op0->getType()); 685 686 // X - 0 -> X 687 if (match(Op1, m_Zero())) 688 return Op0; 689 690 // X - X -> 0 691 if (Op0 == Op1) 692 return Constant::getNullValue(Op0->getType()); 693 694 // (X*2) - X -> X 695 // (X<<1) - X -> X 696 Value *X = 0; 697 if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) || 698 match(Op0, m_Shl(m_Specific(Op1), m_One()))) 699 return Op1; 700 701 // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. 702 // For example, (X + Y) - Y -> X; (Y + X) - Y -> X 703 Value *Y = 0, *Z = Op1; 704 if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z 705 // See if "V === Y - Z" simplifies. 706 if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, TD, TLI, DT, MaxRecurse-1)) 707 // It does! Now see if "X + V" simplifies. 708 if (Value *W = SimplifyBinOp(Instruction::Add, X, V, TD, TLI, DT, 709 MaxRecurse-1)) { 710 // It does, we successfully reassociated! 711 ++NumReassoc; 712 return W; 713 } 714 // See if "V === X - Z" simplifies. 715 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, TLI, DT, MaxRecurse-1)) 716 // It does! Now see if "Y + V" simplifies. 717 if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, TD, TLI, DT, 718 MaxRecurse-1)) { 719 // It does, we successfully reassociated! 720 ++NumReassoc; 721 return W; 722 } 723 } 724 725 // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies. 726 // For example, X - (X + 1) -> -1 727 X = Op0; 728 if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z) 729 // See if "V === X - Y" simplifies. 730 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, TD, TLI, DT, MaxRecurse-1)) 731 // It does! Now see if "V - Z" simplifies. 732 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, TD, TLI, DT, 733 MaxRecurse-1)) { 734 // It does, we successfully reassociated! 735 ++NumReassoc; 736 return W; 737 } 738 // See if "V === X - Z" simplifies. 739 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, TLI, DT, MaxRecurse-1)) 740 // It does! Now see if "V - Y" simplifies. 741 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, TD, TLI, DT, 742 MaxRecurse-1)) { 743 // It does, we successfully reassociated! 744 ++NumReassoc; 745 return W; 746 } 747 } 748 749 // Z - (X - Y) -> (Z - X) + Y if everything simplifies. 750 // For example, X - (X - Y) -> Y. 751 Z = Op0; 752 if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y) 753 // See if "V === Z - X" simplifies. 754 if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, TD, TLI, DT, MaxRecurse-1)) 755 // It does! Now see if "V + Y" simplifies. 756 if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, TD, TLI, DT, 757 MaxRecurse-1)) { 758 // It does, we successfully reassociated! 759 ++NumReassoc; 760 return W; 761 } 762 763 // Mul distributes over Sub. Try some generic simplifications based on this. 764 if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul, 765 TD, TLI, DT, MaxRecurse)) 766 return V; 767 768 // i1 sub -> xor. 769 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 770 if (Value *V = SimplifyXorInst(Op0, Op1, TD, TLI, DT, MaxRecurse-1)) 771 return V; 772 773 // Threading Sub over selects and phi nodes is pointless, so don't bother. 774 // Threading over the select in "A - select(cond, B, C)" means evaluating 775 // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 776 // only if B and C are equal. If B and C are equal then (since we assume 777 // that operands have already been simplified) "select(cond, B, C)" should 778 // have been simplified to the common value of B and C already. Analysing 779 // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 780 // for threading over phi nodes. 781 782 return 0; 783} 784 785Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 786 const TargetData *TD, 787 const TargetLibraryInfo *TLI, 788 const DominatorTree *DT) { 789 return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, TLI, DT, RecursionLimit); 790} 791 792/// SimplifyMulInst - Given operands for a Mul, see if we can 793/// fold the result. If not, this returns null. 794static Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 795 const TargetLibraryInfo *TLI, 796 const DominatorTree *DT, unsigned MaxRecurse) { 797 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 798 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 799 Constant *Ops[] = { CLHS, CRHS }; 800 return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 801 Ops, TD, TLI); 802 } 803 804 // Canonicalize the constant to the RHS. 805 std::swap(Op0, Op1); 806 } 807 808 // X * undef -> 0 809 if (match(Op1, m_Undef())) 810 return Constant::getNullValue(Op0->getType()); 811 812 // X * 0 -> 0 813 if (match(Op1, m_Zero())) 814 return Op1; 815 816 // X * 1 -> X 817 if (match(Op1, m_One())) 818 return Op0; 819 820 // (X / Y) * Y -> X if the division is exact. 821 Value *X = 0; 822 if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y 823 match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0))))) // Y * (X / Y) 824 return X; 825 826 // i1 mul -> and. 827 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 828 if (Value *V = SimplifyAndInst(Op0, Op1, TD, TLI, DT, MaxRecurse-1)) 829 return V; 830 831 // Try some generic simplifications for associative operations. 832 if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, TLI, DT, 833 MaxRecurse)) 834 return V; 835 836 // Mul distributes over Add. Try some generic simplifications based on this. 837 if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 838 TD, TLI, DT, MaxRecurse)) 839 return V; 840 841 // If the operation is with the result of a select instruction, check whether 842 // operating on either branch of the select always yields the same value. 843 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 844 if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, TLI, DT, 845 MaxRecurse)) 846 return V; 847 848 // If the operation is with the result of a phi instruction, check whether 849 // operating on all incoming values of the phi always yields the same value. 850 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 851 if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, TLI, DT, 852 MaxRecurse)) 853 return V; 854 855 return 0; 856} 857 858Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 859 const TargetLibraryInfo *TLI, 860 const DominatorTree *DT) { 861 return ::SimplifyMulInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 862} 863 864/// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can 865/// fold the result. If not, this returns null. 866static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 867 const TargetData *TD, const TargetLibraryInfo *TLI, 868 const DominatorTree *DT, unsigned MaxRecurse) { 869 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 870 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 871 Constant *Ops[] = { C0, C1 }; 872 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, TD, TLI); 873 } 874 } 875 876 bool isSigned = Opcode == Instruction::SDiv; 877 878 // X / undef -> undef 879 if (match(Op1, m_Undef())) 880 return Op1; 881 882 // undef / X -> 0 883 if (match(Op0, m_Undef())) 884 return Constant::getNullValue(Op0->getType()); 885 886 // 0 / X -> 0, we don't need to preserve faults! 887 if (match(Op0, m_Zero())) 888 return Op0; 889 890 // X / 1 -> X 891 if (match(Op1, m_One())) 892 return Op0; 893 894 if (Op0->getType()->isIntegerTy(1)) 895 // It can't be division by zero, hence it must be division by one. 896 return Op0; 897 898 // X / X -> 1 899 if (Op0 == Op1) 900 return ConstantInt::get(Op0->getType(), 1); 901 902 // (X * Y) / Y -> X if the multiplication does not overflow. 903 Value *X = 0, *Y = 0; 904 if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { 905 if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 906 OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0); 907 // If the Mul knows it does not overflow, then we are good to go. 908 if ((isSigned && Mul->hasNoSignedWrap()) || 909 (!isSigned && Mul->hasNoUnsignedWrap())) 910 return X; 911 // If X has the form X = A / Y then X * Y cannot overflow. 912 if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X)) 913 if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) 914 return X; 915 } 916 917 // (X rem Y) / Y -> 0 918 if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 919 (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 920 return Constant::getNullValue(Op0->getType()); 921 922 // If the operation is with the result of a select instruction, check whether 923 // operating on either branch of the select always yields the same value. 924 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 925 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, TLI, DT, 926 MaxRecurse)) 927 return V; 928 929 // If the operation is with the result of a phi instruction, check whether 930 // operating on all incoming values of the phi always yields the same value. 931 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 932 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, TLI, DT, 933 MaxRecurse)) 934 return V; 935 936 return 0; 937} 938 939/// SimplifySDivInst - Given operands for an SDiv, see if we can 940/// fold the result. If not, this returns null. 941static Value *SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, 942 const TargetLibraryInfo *TLI, 943 const DominatorTree *DT, unsigned MaxRecurse) { 944 if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, TD, TLI, DT, 945 MaxRecurse)) 946 return V; 947 948 return 0; 949} 950 951Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, 952 const TargetLibraryInfo *TLI, 953 const DominatorTree *DT) { 954 return ::SimplifySDivInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 955} 956 957/// SimplifyUDivInst - Given operands for a UDiv, see if we can 958/// fold the result. If not, this returns null. 959static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, 960 const TargetLibraryInfo *TLI, 961 const DominatorTree *DT, unsigned MaxRecurse) { 962 if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, TD, TLI, DT, 963 MaxRecurse)) 964 return V; 965 966 return 0; 967} 968 969Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, 970 const TargetLibraryInfo *TLI, 971 const DominatorTree *DT) { 972 return ::SimplifyUDivInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 973} 974 975static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *, 976 const TargetLibraryInfo *, 977 const DominatorTree *, unsigned) { 978 // undef / X -> undef (the undef could be a snan). 979 if (match(Op0, m_Undef())) 980 return Op0; 981 982 // X / undef -> undef 983 if (match(Op1, m_Undef())) 984 return Op1; 985 986 return 0; 987} 988 989Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *TD, 990 const TargetLibraryInfo *TLI, 991 const DominatorTree *DT) { 992 return ::SimplifyFDivInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 993} 994 995/// SimplifyRem - Given operands for an SRem or URem, see if we can 996/// fold the result. If not, this returns null. 997static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 998 const TargetData *TD, const TargetLibraryInfo *TLI, 999 const DominatorTree *DT, unsigned MaxRecurse) { 1000 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1001 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1002 Constant *Ops[] = { C0, C1 }; 1003 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, TD, TLI); 1004 } 1005 } 1006 1007 // X % undef -> undef 1008 if (match(Op1, m_Undef())) 1009 return Op1; 1010 1011 // undef % X -> 0 1012 if (match(Op0, m_Undef())) 1013 return Constant::getNullValue(Op0->getType()); 1014 1015 // 0 % X -> 0, we don't need to preserve faults! 1016 if (match(Op0, m_Zero())) 1017 return Op0; 1018 1019 // X % 0 -> undef, we don't need to preserve faults! 1020 if (match(Op1, m_Zero())) 1021 return UndefValue::get(Op0->getType()); 1022 1023 // X % 1 -> 0 1024 if (match(Op1, m_One())) 1025 return Constant::getNullValue(Op0->getType()); 1026 1027 if (Op0->getType()->isIntegerTy(1)) 1028 // It can't be remainder by zero, hence it must be remainder by one. 1029 return Constant::getNullValue(Op0->getType()); 1030 1031 // X % X -> 0 1032 if (Op0 == Op1) 1033 return Constant::getNullValue(Op0->getType()); 1034 1035 // If the operation is with the result of a select instruction, check whether 1036 // operating on either branch of the select always yields the same value. 1037 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1038 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1039 return V; 1040 1041 // If the operation is with the result of a phi instruction, check whether 1042 // operating on all incoming values of the phi always yields the same value. 1043 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1044 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1045 return V; 1046 1047 return 0; 1048} 1049 1050/// SimplifySRemInst - Given operands for an SRem, see if we can 1051/// fold the result. If not, this returns null. 1052static Value *SimplifySRemInst(Value *Op0, Value *Op1, const TargetData *TD, 1053 const TargetLibraryInfo *TLI, 1054 const DominatorTree *DT, 1055 unsigned MaxRecurse) { 1056 if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1057 return V; 1058 1059 return 0; 1060} 1061 1062Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const TargetData *TD, 1063 const TargetLibraryInfo *TLI, 1064 const DominatorTree *DT) { 1065 return ::SimplifySRemInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1066} 1067 1068/// SimplifyURemInst - Given operands for a URem, see if we can 1069/// fold the result. If not, this returns null. 1070static Value *SimplifyURemInst(Value *Op0, Value *Op1, const TargetData *TD, 1071 const TargetLibraryInfo *TLI, 1072 const DominatorTree *DT, 1073 unsigned MaxRecurse) { 1074 if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1075 return V; 1076 1077 return 0; 1078} 1079 1080Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const TargetData *TD, 1081 const TargetLibraryInfo *TLI, 1082 const DominatorTree *DT) { 1083 return ::SimplifyURemInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1084} 1085 1086static Value *SimplifyFRemInst(Value *Op0, Value *Op1, const TargetData *, 1087 const TargetLibraryInfo *, 1088 const DominatorTree *, 1089 unsigned) { 1090 // undef % X -> undef (the undef could be a snan). 1091 if (match(Op0, m_Undef())) 1092 return Op0; 1093 1094 // X % undef -> undef 1095 if (match(Op1, m_Undef())) 1096 return Op1; 1097 1098 return 0; 1099} 1100 1101Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const TargetData *TD, 1102 const TargetLibraryInfo *TLI, 1103 const DominatorTree *DT) { 1104 return ::SimplifyFRemInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1105} 1106 1107/// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can 1108/// fold the result. If not, this returns null. 1109static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, 1110 const TargetData *TD, const TargetLibraryInfo *TLI, 1111 const DominatorTree *DT, unsigned MaxRecurse) { 1112 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1113 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1114 Constant *Ops[] = { C0, C1 }; 1115 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, TD, TLI); 1116 } 1117 } 1118 1119 // 0 shift by X -> 0 1120 if (match(Op0, m_Zero())) 1121 return Op0; 1122 1123 // X shift by 0 -> X 1124 if (match(Op1, m_Zero())) 1125 return Op0; 1126 1127 // X shift by undef -> undef because it may shift by the bitwidth. 1128 if (match(Op1, m_Undef())) 1129 return Op1; 1130 1131 // Shifting by the bitwidth or more is undefined. 1132 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) 1133 if (CI->getValue().getLimitedValue() >= 1134 Op0->getType()->getScalarSizeInBits()) 1135 return UndefValue::get(Op0->getType()); 1136 1137 // If the operation is with the result of a select instruction, check whether 1138 // operating on either branch of the select always yields the same value. 1139 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1140 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1141 return V; 1142 1143 // If the operation is with the result of a phi instruction, check whether 1144 // operating on all incoming values of the phi always yields the same value. 1145 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1146 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1147 return V; 1148 1149 return 0; 1150} 1151 1152/// SimplifyShlInst - Given operands for an Shl, see if we can 1153/// fold the result. If not, this returns null. 1154static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1155 const TargetData *TD, 1156 const TargetLibraryInfo *TLI, 1157 const DominatorTree *DT, unsigned MaxRecurse) { 1158 if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1159 return V; 1160 1161 // undef << X -> 0 1162 if (match(Op0, m_Undef())) 1163 return Constant::getNullValue(Op0->getType()); 1164 1165 // (X >> A) << A -> X 1166 Value *X; 1167 if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1))))) 1168 return X; 1169 return 0; 1170} 1171 1172Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1173 const TargetData *TD, const TargetLibraryInfo *TLI, 1174 const DominatorTree *DT) { 1175 return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, TD, TLI, DT, RecursionLimit); 1176} 1177 1178/// SimplifyLShrInst - Given operands for an LShr, see if we can 1179/// fold the result. If not, this returns null. 1180static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1181 const TargetData *TD, 1182 const TargetLibraryInfo *TLI, 1183 const DominatorTree *DT, 1184 unsigned MaxRecurse) { 1185 if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1186 return V; 1187 1188 // undef >>l X -> 0 1189 if (match(Op0, m_Undef())) 1190 return Constant::getNullValue(Op0->getType()); 1191 1192 // (X << A) >> A -> X 1193 Value *X; 1194 if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) && 1195 cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap()) 1196 return X; 1197 1198 return 0; 1199} 1200 1201Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1202 const TargetData *TD, 1203 const TargetLibraryInfo *TLI, 1204 const DominatorTree *DT) { 1205 return ::SimplifyLShrInst(Op0, Op1, isExact, TD, TLI, DT, RecursionLimit); 1206} 1207 1208/// SimplifyAShrInst - Given operands for an AShr, see if we can 1209/// fold the result. If not, this returns null. 1210static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1211 const TargetData *TD, 1212 const TargetLibraryInfo *TLI, 1213 const DominatorTree *DT, 1214 unsigned MaxRecurse) { 1215 if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1216 return V; 1217 1218 // all ones >>a X -> all ones 1219 if (match(Op0, m_AllOnes())) 1220 return Op0; 1221 1222 // undef >>a X -> all ones 1223 if (match(Op0, m_Undef())) 1224 return Constant::getAllOnesValue(Op0->getType()); 1225 1226 // (X << A) >> A -> X 1227 Value *X; 1228 if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) && 1229 cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap()) 1230 return X; 1231 1232 return 0; 1233} 1234 1235Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1236 const TargetData *TD, 1237 const TargetLibraryInfo *TLI, 1238 const DominatorTree *DT) { 1239 return ::SimplifyAShrInst(Op0, Op1, isExact, TD, TLI, DT, RecursionLimit); 1240} 1241 1242/// SimplifyAndInst - Given operands for an And, see if we can 1243/// fold the result. If not, this returns null. 1244static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 1245 const TargetLibraryInfo *TLI, 1246 const DominatorTree *DT, 1247 unsigned MaxRecurse) { 1248 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1249 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1250 Constant *Ops[] = { CLHS, CRHS }; 1251 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 1252 Ops, TD, TLI); 1253 } 1254 1255 // Canonicalize the constant to the RHS. 1256 std::swap(Op0, Op1); 1257 } 1258 1259 // X & undef -> 0 1260 if (match(Op1, m_Undef())) 1261 return Constant::getNullValue(Op0->getType()); 1262 1263 // X & X = X 1264 if (Op0 == Op1) 1265 return Op0; 1266 1267 // X & 0 = 0 1268 if (match(Op1, m_Zero())) 1269 return Op1; 1270 1271 // X & -1 = X 1272 if (match(Op1, m_AllOnes())) 1273 return Op0; 1274 1275 // A & ~A = ~A & A = 0 1276 if (match(Op0, m_Not(m_Specific(Op1))) || 1277 match(Op1, m_Not(m_Specific(Op0)))) 1278 return Constant::getNullValue(Op0->getType()); 1279 1280 // (A | ?) & A = A 1281 Value *A = 0, *B = 0; 1282 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1283 (A == Op1 || B == Op1)) 1284 return Op1; 1285 1286 // A & (A | ?) = A 1287 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1288 (A == Op0 || B == Op0)) 1289 return Op0; 1290 1291 // A & (-A) = A if A is a power of two or zero. 1292 if (match(Op0, m_Neg(m_Specific(Op1))) || 1293 match(Op1, m_Neg(m_Specific(Op0)))) { 1294 if (isPowerOfTwo(Op0, TD, /*OrZero*/true)) 1295 return Op0; 1296 if (isPowerOfTwo(Op1, TD, /*OrZero*/true)) 1297 return Op1; 1298 } 1299 1300 // Try some generic simplifications for associative operations. 1301 if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, TLI, 1302 DT, MaxRecurse)) 1303 return V; 1304 1305 // And distributes over Or. Try some generic simplifications based on this. 1306 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1307 TD, TLI, DT, MaxRecurse)) 1308 return V; 1309 1310 // And distributes over Xor. Try some generic simplifications based on this. 1311 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 1312 TD, TLI, DT, MaxRecurse)) 1313 return V; 1314 1315 // Or distributes over And. Try some generic simplifications based on this. 1316 if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1317 TD, TLI, DT, MaxRecurse)) 1318 return V; 1319 1320 // If the operation is with the result of a select instruction, check whether 1321 // operating on either branch of the select always yields the same value. 1322 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1323 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, TLI, 1324 DT, MaxRecurse)) 1325 return V; 1326 1327 // If the operation is with the result of a phi instruction, check whether 1328 // operating on all incoming values of the phi always yields the same value. 1329 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1330 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, TLI, DT, 1331 MaxRecurse)) 1332 return V; 1333 1334 return 0; 1335} 1336 1337Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 1338 const TargetLibraryInfo *TLI, 1339 const DominatorTree *DT) { 1340 return ::SimplifyAndInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1341} 1342 1343/// SimplifyOrInst - Given operands for an Or, see if we can 1344/// fold the result. If not, this returns null. 1345static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 1346 const TargetLibraryInfo *TLI, 1347 const DominatorTree *DT, unsigned MaxRecurse) { 1348 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1349 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1350 Constant *Ops[] = { CLHS, CRHS }; 1351 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 1352 Ops, TD, TLI); 1353 } 1354 1355 // Canonicalize the constant to the RHS. 1356 std::swap(Op0, Op1); 1357 } 1358 1359 // X | undef -> -1 1360 if (match(Op1, m_Undef())) 1361 return Constant::getAllOnesValue(Op0->getType()); 1362 1363 // X | X = X 1364 if (Op0 == Op1) 1365 return Op0; 1366 1367 // X | 0 = X 1368 if (match(Op1, m_Zero())) 1369 return Op0; 1370 1371 // X | -1 = -1 1372 if (match(Op1, m_AllOnes())) 1373 return Op1; 1374 1375 // A | ~A = ~A | A = -1 1376 if (match(Op0, m_Not(m_Specific(Op1))) || 1377 match(Op1, m_Not(m_Specific(Op0)))) 1378 return Constant::getAllOnesValue(Op0->getType()); 1379 1380 // (A & ?) | A = A 1381 Value *A = 0, *B = 0; 1382 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 1383 (A == Op1 || B == Op1)) 1384 return Op1; 1385 1386 // A | (A & ?) = A 1387 if (match(Op1, m_And(m_Value(A), m_Value(B))) && 1388 (A == Op0 || B == Op0)) 1389 return Op0; 1390 1391 // ~(A & ?) | A = -1 1392 if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) && 1393 (A == Op1 || B == Op1)) 1394 return Constant::getAllOnesValue(Op1->getType()); 1395 1396 // A | ~(A & ?) = -1 1397 if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) && 1398 (A == Op0 || B == Op0)) 1399 return Constant::getAllOnesValue(Op0->getType()); 1400 1401 // Try some generic simplifications for associative operations. 1402 if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, TLI, 1403 DT, MaxRecurse)) 1404 return V; 1405 1406 // Or distributes over And. Try some generic simplifications based on this. 1407 if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, TD, 1408 TLI, DT, MaxRecurse)) 1409 return V; 1410 1411 // And distributes over Or. Try some generic simplifications based on this. 1412 if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And, 1413 TD, TLI, DT, MaxRecurse)) 1414 return V; 1415 1416 // If the operation is with the result of a select instruction, check whether 1417 // operating on either branch of the select always yields the same value. 1418 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1419 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, TLI, DT, 1420 MaxRecurse)) 1421 return V; 1422 1423 // If the operation is with the result of a phi instruction, check whether 1424 // operating on all incoming values of the phi always yields the same value. 1425 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1426 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, TLI, DT, 1427 MaxRecurse)) 1428 return V; 1429 1430 return 0; 1431} 1432 1433Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 1434 const TargetLibraryInfo *TLI, 1435 const DominatorTree *DT) { 1436 return ::SimplifyOrInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1437} 1438 1439/// SimplifyXorInst - Given operands for a Xor, see if we can 1440/// fold the result. If not, this returns null. 1441static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 1442 const TargetLibraryInfo *TLI, 1443 const DominatorTree *DT, unsigned MaxRecurse) { 1444 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1445 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1446 Constant *Ops[] = { CLHS, CRHS }; 1447 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 1448 Ops, TD, TLI); 1449 } 1450 1451 // Canonicalize the constant to the RHS. 1452 std::swap(Op0, Op1); 1453 } 1454 1455 // A ^ undef -> undef 1456 if (match(Op1, m_Undef())) 1457 return Op1; 1458 1459 // A ^ 0 = A 1460 if (match(Op1, m_Zero())) 1461 return Op0; 1462 1463 // A ^ A = 0 1464 if (Op0 == Op1) 1465 return Constant::getNullValue(Op0->getType()); 1466 1467 // A ^ ~A = ~A ^ A = -1 1468 if (match(Op0, m_Not(m_Specific(Op1))) || 1469 match(Op1, m_Not(m_Specific(Op0)))) 1470 return Constant::getAllOnesValue(Op0->getType()); 1471 1472 // Try some generic simplifications for associative operations. 1473 if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, TLI, 1474 DT, MaxRecurse)) 1475 return V; 1476 1477 // And distributes over Xor. Try some generic simplifications based on this. 1478 if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And, 1479 TD, TLI, DT, MaxRecurse)) 1480 return V; 1481 1482 // Threading Xor over selects and phi nodes is pointless, so don't bother. 1483 // Threading over the select in "A ^ select(cond, B, C)" means evaluating 1484 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 1485 // only if B and C are equal. If B and C are equal then (since we assume 1486 // that operands have already been simplified) "select(cond, B, C)" should 1487 // have been simplified to the common value of B and C already. Analysing 1488 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 1489 // for threading over phi nodes. 1490 1491 return 0; 1492} 1493 1494Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 1495 const TargetLibraryInfo *TLI, 1496 const DominatorTree *DT) { 1497 return ::SimplifyXorInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1498} 1499 1500static Type *GetCompareTy(Value *Op) { 1501 return CmpInst::makeCmpResultType(Op->getType()); 1502} 1503 1504/// ExtractEquivalentCondition - Rummage around inside V looking for something 1505/// equivalent to the comparison "LHS Pred RHS". Return such a value if found, 1506/// otherwise return null. Helper function for analyzing max/min idioms. 1507static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred, 1508 Value *LHS, Value *RHS) { 1509 SelectInst *SI = dyn_cast<SelectInst>(V); 1510 if (!SI) 1511 return 0; 1512 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition()); 1513 if (!Cmp) 1514 return 0; 1515 Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1); 1516 if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS) 1517 return Cmp; 1518 if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) && 1519 LHS == CmpRHS && RHS == CmpLHS) 1520 return Cmp; 1521 return 0; 1522} 1523 1524/// stripPointerAdjustments - This is like Value::stripPointerCasts, but also 1525/// removes inbounds gep operations, regardless of their indices. 1526static Value *stripPointerAdjustmentsImpl(Value *V, 1527 SmallPtrSet<GEPOperator*, 8> &VisitedGEPs) { 1528 GEPOperator *GEP = dyn_cast<GEPOperator>(V); 1529 if (GEP == 0 || !GEP->isInBounds()) 1530 return V; 1531 1532 // If we've already seen this GEP, we will end up infinitely looping. This 1533 // can happen in unreachable code. 1534 if (!VisitedGEPs.insert(GEP)) 1535 return V; 1536 1537 return stripPointerAdjustmentsImpl(GEP->getOperand(0)->stripPointerCasts(), 1538 VisitedGEPs); 1539} 1540 1541static Value *stripPointerAdjustments(Value *V) { 1542 SmallPtrSet<GEPOperator*, 8> VisitedGEPs; 1543 return stripPointerAdjustmentsImpl(V, VisitedGEPs); 1544} 1545 1546 1547/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 1548/// fold the result. If not, this returns null. 1549static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1550 const TargetData *TD, 1551 const TargetLibraryInfo *TLI, 1552 const DominatorTree *DT, 1553 unsigned MaxRecurse) { 1554 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 1555 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 1556 1557 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 1558 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1559 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD, TLI); 1560 1561 // If we have a constant, make sure it is on the RHS. 1562 std::swap(LHS, RHS); 1563 Pred = CmpInst::getSwappedPredicate(Pred); 1564 } 1565 1566 Type *ITy = GetCompareTy(LHS); // The return type. 1567 Type *OpTy = LHS->getType(); // The operand type. 1568 1569 // icmp X, X -> true/false 1570 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 1571 // because X could be 0. 1572 if (LHS == RHS || isa<UndefValue>(RHS)) 1573 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 1574 1575 // Special case logic when the operands have i1 type. 1576 if (OpTy->getScalarType()->isIntegerTy(1)) { 1577 switch (Pred) { 1578 default: break; 1579 case ICmpInst::ICMP_EQ: 1580 // X == 1 -> X 1581 if (match(RHS, m_One())) 1582 return LHS; 1583 break; 1584 case ICmpInst::ICMP_NE: 1585 // X != 0 -> X 1586 if (match(RHS, m_Zero())) 1587 return LHS; 1588 break; 1589 case ICmpInst::ICMP_UGT: 1590 // X >u 0 -> X 1591 if (match(RHS, m_Zero())) 1592 return LHS; 1593 break; 1594 case ICmpInst::ICMP_UGE: 1595 // X >=u 1 -> X 1596 if (match(RHS, m_One())) 1597 return LHS; 1598 break; 1599 case ICmpInst::ICMP_SLT: 1600 // X <s 0 -> X 1601 if (match(RHS, m_Zero())) 1602 return LHS; 1603 break; 1604 case ICmpInst::ICMP_SLE: 1605 // X <=s -1 -> X 1606 if (match(RHS, m_One())) 1607 return LHS; 1608 break; 1609 } 1610 } 1611 1612 // icmp <object*>, <object*/null> - Different identified objects have 1613 // different addresses, and what's more the address of a stack variable is 1614 // never equal to another argument. Note that generalizing to the case where 1615 // LHS is a global variable address or null is pointless, since if both LHS 1616 // and RHS are constants then we already constant folded the compare, and if 1617 // only one of them is then we moved it to RHS already. 1618 Value *LHSPtr = LHS->stripPointerCasts(); 1619 Value *RHSPtr = RHS->stripPointerCasts(); 1620 if (LHSPtr == RHSPtr) 1621 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 1622 1623 // Be more aggressive about stripping pointer adjustments when checking a 1624 // comparison of an alloca address to another object. We can rip off all 1625 // inbounds GEP operations, even if they are variable. 1626 LHSPtr = stripPointerAdjustments(LHSPtr); 1627 if (llvm::isIdentifiedObject(LHSPtr)) { 1628 RHSPtr = stripPointerAdjustments(RHSPtr); 1629 if (llvm::isKnownNonNull(LHSPtr) || llvm::isKnownNonNull(RHSPtr)) { 1630 // If both sides are different identified objects, they aren't equal 1631 // unless they're null. 1632 if (LHSPtr != RHSPtr && llvm::isIdentifiedObject(RHSPtr)) 1633 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 1634 1635 // A local identified object (alloca or noalias call) can't equal any 1636 // incoming argument, unless they're both null. 1637 if ((isa<Instruction>(LHSPtr) && isa<Argument>(RHSPtr)) || 1638 (isa<Instruction>(RHSPtr) && isa<Argument>(LHSPtr))) 1639 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 1640 } 1641 1642 // Assume that the constant null is on the right. 1643 if (llvm::isKnownNonNull(LHSPtr) && isa<ConstantPointerNull>(RHSPtr)) 1644 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 1645 } 1646 1647 // If we are comparing with zero then try hard since this is a common case. 1648 if (match(RHS, m_Zero())) { 1649 bool LHSKnownNonNegative, LHSKnownNegative; 1650 switch (Pred) { 1651 default: llvm_unreachable("Unknown ICmp predicate!"); 1652 case ICmpInst::ICMP_ULT: 1653 return getFalse(ITy); 1654 case ICmpInst::ICMP_UGE: 1655 return getTrue(ITy); 1656 case ICmpInst::ICMP_EQ: 1657 case ICmpInst::ICMP_ULE: 1658 if (isKnownNonZero(LHS, TD)) 1659 return getFalse(ITy); 1660 break; 1661 case ICmpInst::ICMP_NE: 1662 case ICmpInst::ICMP_UGT: 1663 if (isKnownNonZero(LHS, TD)) 1664 return getTrue(ITy); 1665 break; 1666 case ICmpInst::ICMP_SLT: 1667 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1668 if (LHSKnownNegative) 1669 return getTrue(ITy); 1670 if (LHSKnownNonNegative) 1671 return getFalse(ITy); 1672 break; 1673 case ICmpInst::ICMP_SLE: 1674 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1675 if (LHSKnownNegative) 1676 return getTrue(ITy); 1677 if (LHSKnownNonNegative && isKnownNonZero(LHS, TD)) 1678 return getFalse(ITy); 1679 break; 1680 case ICmpInst::ICMP_SGE: 1681 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1682 if (LHSKnownNegative) 1683 return getFalse(ITy); 1684 if (LHSKnownNonNegative) 1685 return getTrue(ITy); 1686 break; 1687 case ICmpInst::ICMP_SGT: 1688 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1689 if (LHSKnownNegative) 1690 return getFalse(ITy); 1691 if (LHSKnownNonNegative && isKnownNonZero(LHS, TD)) 1692 return getTrue(ITy); 1693 break; 1694 } 1695 } 1696 1697 // See if we are doing a comparison with a constant integer. 1698 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1699 // Rule out tautological comparisons (eg., ult 0 or uge 0). 1700 ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue()); 1701 if (RHS_CR.isEmptySet()) 1702 return ConstantInt::getFalse(CI->getContext()); 1703 if (RHS_CR.isFullSet()) 1704 return ConstantInt::getTrue(CI->getContext()); 1705 1706 // Many binary operators with constant RHS have easy to compute constant 1707 // range. Use them to check whether the comparison is a tautology. 1708 uint32_t Width = CI->getBitWidth(); 1709 APInt Lower = APInt(Width, 0); 1710 APInt Upper = APInt(Width, 0); 1711 ConstantInt *CI2; 1712 if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) { 1713 // 'urem x, CI2' produces [0, CI2). 1714 Upper = CI2->getValue(); 1715 } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) { 1716 // 'srem x, CI2' produces (-|CI2|, |CI2|). 1717 Upper = CI2->getValue().abs(); 1718 Lower = (-Upper) + 1; 1719 } else if (match(LHS, m_UDiv(m_ConstantInt(CI2), m_Value()))) { 1720 // 'udiv CI2, x' produces [0, CI2]. 1721 Upper = CI2->getValue() + 1; 1722 } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) { 1723 // 'udiv x, CI2' produces [0, UINT_MAX / CI2]. 1724 APInt NegOne = APInt::getAllOnesValue(Width); 1725 if (!CI2->isZero()) 1726 Upper = NegOne.udiv(CI2->getValue()) + 1; 1727 } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) { 1728 // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2]. 1729 APInt IntMin = APInt::getSignedMinValue(Width); 1730 APInt IntMax = APInt::getSignedMaxValue(Width); 1731 APInt Val = CI2->getValue().abs(); 1732 if (!Val.isMinValue()) { 1733 Lower = IntMin.sdiv(Val); 1734 Upper = IntMax.sdiv(Val) + 1; 1735 } 1736 } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) { 1737 // 'lshr x, CI2' produces [0, UINT_MAX >> CI2]. 1738 APInt NegOne = APInt::getAllOnesValue(Width); 1739 if (CI2->getValue().ult(Width)) 1740 Upper = NegOne.lshr(CI2->getValue()) + 1; 1741 } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) { 1742 // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2]. 1743 APInt IntMin = APInt::getSignedMinValue(Width); 1744 APInt IntMax = APInt::getSignedMaxValue(Width); 1745 if (CI2->getValue().ult(Width)) { 1746 Lower = IntMin.ashr(CI2->getValue()); 1747 Upper = IntMax.ashr(CI2->getValue()) + 1; 1748 } 1749 } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) { 1750 // 'or x, CI2' produces [CI2, UINT_MAX]. 1751 Lower = CI2->getValue(); 1752 } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) { 1753 // 'and x, CI2' produces [0, CI2]. 1754 Upper = CI2->getValue() + 1; 1755 } 1756 if (Lower != Upper) { 1757 ConstantRange LHS_CR = ConstantRange(Lower, Upper); 1758 if (RHS_CR.contains(LHS_CR)) 1759 return ConstantInt::getTrue(RHS->getContext()); 1760 if (RHS_CR.inverse().contains(LHS_CR)) 1761 return ConstantInt::getFalse(RHS->getContext()); 1762 } 1763 } 1764 1765 // Compare of cast, for example (zext X) != 0 -> X != 0 1766 if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) { 1767 Instruction *LI = cast<CastInst>(LHS); 1768 Value *SrcOp = LI->getOperand(0); 1769 Type *SrcTy = SrcOp->getType(); 1770 Type *DstTy = LI->getType(); 1771 1772 // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input 1773 // if the integer type is the same size as the pointer type. 1774 if (MaxRecurse && TD && isa<PtrToIntInst>(LI) && 1775 TD->getPointerSizeInBits() == DstTy->getPrimitiveSizeInBits()) { 1776 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 1777 // Transfer the cast to the constant. 1778 if (Value *V = SimplifyICmpInst(Pred, SrcOp, 1779 ConstantExpr::getIntToPtr(RHSC, SrcTy), 1780 TD, TLI, DT, MaxRecurse-1)) 1781 return V; 1782 } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) { 1783 if (RI->getOperand(0)->getType() == SrcTy) 1784 // Compare without the cast. 1785 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 1786 TD, TLI, DT, MaxRecurse-1)) 1787 return V; 1788 } 1789 } 1790 1791 if (isa<ZExtInst>(LHS)) { 1792 // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the 1793 // same type. 1794 if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) { 1795 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 1796 // Compare X and Y. Note that signed predicates become unsigned. 1797 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 1798 SrcOp, RI->getOperand(0), TD, TLI, DT, 1799 MaxRecurse-1)) 1800 return V; 1801 } 1802 // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended 1803 // too. If not, then try to deduce the result of the comparison. 1804 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1805 // Compute the constant that would happen if we truncated to SrcTy then 1806 // reextended to DstTy. 1807 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 1808 Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy); 1809 1810 // If the re-extended constant didn't change then this is effectively 1811 // also a case of comparing two zero-extended values. 1812 if (RExt == CI && MaxRecurse) 1813 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 1814 SrcOp, Trunc, TD, TLI, DT, MaxRecurse-1)) 1815 return V; 1816 1817 // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit 1818 // there. Use this to work out the result of the comparison. 1819 if (RExt != CI) { 1820 switch (Pred) { 1821 default: llvm_unreachable("Unknown ICmp predicate!"); 1822 // LHS <u RHS. 1823 case ICmpInst::ICMP_EQ: 1824 case ICmpInst::ICMP_UGT: 1825 case ICmpInst::ICMP_UGE: 1826 return ConstantInt::getFalse(CI->getContext()); 1827 1828 case ICmpInst::ICMP_NE: 1829 case ICmpInst::ICMP_ULT: 1830 case ICmpInst::ICMP_ULE: 1831 return ConstantInt::getTrue(CI->getContext()); 1832 1833 // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS 1834 // is non-negative then LHS <s RHS. 1835 case ICmpInst::ICMP_SGT: 1836 case ICmpInst::ICMP_SGE: 1837 return CI->getValue().isNegative() ? 1838 ConstantInt::getTrue(CI->getContext()) : 1839 ConstantInt::getFalse(CI->getContext()); 1840 1841 case ICmpInst::ICMP_SLT: 1842 case ICmpInst::ICMP_SLE: 1843 return CI->getValue().isNegative() ? 1844 ConstantInt::getFalse(CI->getContext()) : 1845 ConstantInt::getTrue(CI->getContext()); 1846 } 1847 } 1848 } 1849 } 1850 1851 if (isa<SExtInst>(LHS)) { 1852 // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the 1853 // same type. 1854 if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) { 1855 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 1856 // Compare X and Y. Note that the predicate does not change. 1857 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 1858 TD, TLI, DT, MaxRecurse-1)) 1859 return V; 1860 } 1861 // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended 1862 // too. If not, then try to deduce the result of the comparison. 1863 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1864 // Compute the constant that would happen if we truncated to SrcTy then 1865 // reextended to DstTy. 1866 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 1867 Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy); 1868 1869 // If the re-extended constant didn't change then this is effectively 1870 // also a case of comparing two sign-extended values. 1871 if (RExt == CI && MaxRecurse) 1872 if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, TD, TLI, DT, 1873 MaxRecurse-1)) 1874 return V; 1875 1876 // Otherwise the upper bits of LHS are all equal, while RHS has varying 1877 // bits there. Use this to work out the result of the comparison. 1878 if (RExt != CI) { 1879 switch (Pred) { 1880 default: llvm_unreachable("Unknown ICmp predicate!"); 1881 case ICmpInst::ICMP_EQ: 1882 return ConstantInt::getFalse(CI->getContext()); 1883 case ICmpInst::ICMP_NE: 1884 return ConstantInt::getTrue(CI->getContext()); 1885 1886 // If RHS is non-negative then LHS <s RHS. If RHS is negative then 1887 // LHS >s RHS. 1888 case ICmpInst::ICMP_SGT: 1889 case ICmpInst::ICMP_SGE: 1890 return CI->getValue().isNegative() ? 1891 ConstantInt::getTrue(CI->getContext()) : 1892 ConstantInt::getFalse(CI->getContext()); 1893 case ICmpInst::ICMP_SLT: 1894 case ICmpInst::ICMP_SLE: 1895 return CI->getValue().isNegative() ? 1896 ConstantInt::getFalse(CI->getContext()) : 1897 ConstantInt::getTrue(CI->getContext()); 1898 1899 // If LHS is non-negative then LHS <u RHS. If LHS is negative then 1900 // LHS >u RHS. 1901 case ICmpInst::ICMP_UGT: 1902 case ICmpInst::ICMP_UGE: 1903 // Comparison is true iff the LHS <s 0. 1904 if (MaxRecurse) 1905 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp, 1906 Constant::getNullValue(SrcTy), 1907 TD, TLI, DT, MaxRecurse-1)) 1908 return V; 1909 break; 1910 case ICmpInst::ICMP_ULT: 1911 case ICmpInst::ICMP_ULE: 1912 // Comparison is true iff the LHS >=s 0. 1913 if (MaxRecurse) 1914 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp, 1915 Constant::getNullValue(SrcTy), 1916 TD, TLI, DT, MaxRecurse-1)) 1917 return V; 1918 break; 1919 } 1920 } 1921 } 1922 } 1923 } 1924 1925 // Special logic for binary operators. 1926 BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS); 1927 BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS); 1928 if (MaxRecurse && (LBO || RBO)) { 1929 // Analyze the case when either LHS or RHS is an add instruction. 1930 Value *A = 0, *B = 0, *C = 0, *D = 0; 1931 // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null). 1932 bool NoLHSWrapProblem = false, NoRHSWrapProblem = false; 1933 if (LBO && LBO->getOpcode() == Instruction::Add) { 1934 A = LBO->getOperand(0); B = LBO->getOperand(1); 1935 NoLHSWrapProblem = ICmpInst::isEquality(Pred) || 1936 (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) || 1937 (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap()); 1938 } 1939 if (RBO && RBO->getOpcode() == Instruction::Add) { 1940 C = RBO->getOperand(0); D = RBO->getOperand(1); 1941 NoRHSWrapProblem = ICmpInst::isEquality(Pred) || 1942 (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) || 1943 (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap()); 1944 } 1945 1946 // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow. 1947 if ((A == RHS || B == RHS) && NoLHSWrapProblem) 1948 if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A, 1949 Constant::getNullValue(RHS->getType()), 1950 TD, TLI, DT, MaxRecurse-1)) 1951 return V; 1952 1953 // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow. 1954 if ((C == LHS || D == LHS) && NoRHSWrapProblem) 1955 if (Value *V = SimplifyICmpInst(Pred, 1956 Constant::getNullValue(LHS->getType()), 1957 C == LHS ? D : C, TD, TLI, DT, MaxRecurse-1)) 1958 return V; 1959 1960 // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow. 1961 if (A && C && (A == C || A == D || B == C || B == D) && 1962 NoLHSWrapProblem && NoRHSWrapProblem) { 1963 // Determine Y and Z in the form icmp (X+Y), (X+Z). 1964 Value *Y = (A == C || A == D) ? B : A; 1965 Value *Z = (C == A || C == B) ? D : C; 1966 if (Value *V = SimplifyICmpInst(Pred, Y, Z, TD, TLI, DT, MaxRecurse-1)) 1967 return V; 1968 } 1969 } 1970 1971 if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) { 1972 bool KnownNonNegative, KnownNegative; 1973 switch (Pred) { 1974 default: 1975 break; 1976 case ICmpInst::ICMP_SGT: 1977 case ICmpInst::ICMP_SGE: 1978 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, TD); 1979 if (!KnownNonNegative) 1980 break; 1981 // fall-through 1982 case ICmpInst::ICMP_EQ: 1983 case ICmpInst::ICMP_UGT: 1984 case ICmpInst::ICMP_UGE: 1985 return getFalse(ITy); 1986 case ICmpInst::ICMP_SLT: 1987 case ICmpInst::ICMP_SLE: 1988 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, TD); 1989 if (!KnownNonNegative) 1990 break; 1991 // fall-through 1992 case ICmpInst::ICMP_NE: 1993 case ICmpInst::ICMP_ULT: 1994 case ICmpInst::ICMP_ULE: 1995 return getTrue(ITy); 1996 } 1997 } 1998 if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) { 1999 bool KnownNonNegative, KnownNegative; 2000 switch (Pred) { 2001 default: 2002 break; 2003 case ICmpInst::ICMP_SGT: 2004 case ICmpInst::ICMP_SGE: 2005 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, TD); 2006 if (!KnownNonNegative) 2007 break; 2008 // fall-through 2009 case ICmpInst::ICMP_NE: 2010 case ICmpInst::ICMP_UGT: 2011 case ICmpInst::ICMP_UGE: 2012 return getTrue(ITy); 2013 case ICmpInst::ICMP_SLT: 2014 case ICmpInst::ICMP_SLE: 2015 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, TD); 2016 if (!KnownNonNegative) 2017 break; 2018 // fall-through 2019 case ICmpInst::ICMP_EQ: 2020 case ICmpInst::ICMP_ULT: 2021 case ICmpInst::ICMP_ULE: 2022 return getFalse(ITy); 2023 } 2024 } 2025 2026 // x udiv y <=u x. 2027 if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) { 2028 // icmp pred (X /u Y), X 2029 if (Pred == ICmpInst::ICMP_UGT) 2030 return getFalse(ITy); 2031 if (Pred == ICmpInst::ICMP_ULE) 2032 return getTrue(ITy); 2033 } 2034 2035 if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() && 2036 LBO->getOperand(1) == RBO->getOperand(1)) { 2037 switch (LBO->getOpcode()) { 2038 default: break; 2039 case Instruction::UDiv: 2040 case Instruction::LShr: 2041 if (ICmpInst::isSigned(Pred)) 2042 break; 2043 // fall-through 2044 case Instruction::SDiv: 2045 case Instruction::AShr: 2046 if (!LBO->isExact() || !RBO->isExact()) 2047 break; 2048 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2049 RBO->getOperand(0), TD, TLI, DT, MaxRecurse-1)) 2050 return V; 2051 break; 2052 case Instruction::Shl: { 2053 bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap(); 2054 bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap(); 2055 if (!NUW && !NSW) 2056 break; 2057 if (!NSW && ICmpInst::isSigned(Pred)) 2058 break; 2059 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2060 RBO->getOperand(0), TD, TLI, DT, MaxRecurse-1)) 2061 return V; 2062 break; 2063 } 2064 } 2065 } 2066 2067 // Simplify comparisons involving max/min. 2068 Value *A, *B; 2069 CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE; 2070 CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B". 2071 2072 // Signed variants on "max(a,b)>=a -> true". 2073 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2074 if (A != RHS) std::swap(A, B); // smax(A, B) pred A. 2075 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2076 // We analyze this as smax(A, B) pred A. 2077 P = Pred; 2078 } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) && 2079 (A == LHS || B == LHS)) { 2080 if (A != LHS) std::swap(A, B); // A pred smax(A, B). 2081 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2082 // We analyze this as smax(A, B) swapped-pred A. 2083 P = CmpInst::getSwappedPredicate(Pred); 2084 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2085 (A == RHS || B == RHS)) { 2086 if (A != RHS) std::swap(A, B); // smin(A, B) pred A. 2087 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2088 // We analyze this as smax(-A, -B) swapped-pred -A. 2089 // Note that we do not need to actually form -A or -B thanks to EqP. 2090 P = CmpInst::getSwappedPredicate(Pred); 2091 } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) && 2092 (A == LHS || B == LHS)) { 2093 if (A != LHS) std::swap(A, B); // A pred smin(A, B). 2094 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2095 // We analyze this as smax(-A, -B) pred -A. 2096 // Note that we do not need to actually form -A or -B thanks to EqP. 2097 P = Pred; 2098 } 2099 if (P != CmpInst::BAD_ICMP_PREDICATE) { 2100 // Cases correspond to "max(A, B) p A". 2101 switch (P) { 2102 default: 2103 break; 2104 case CmpInst::ICMP_EQ: 2105 case CmpInst::ICMP_SLE: 2106 // Equivalent to "A EqP B". This may be the same as the condition tested 2107 // in the max/min; if so, we can just return that. 2108 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2109 return V; 2110 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2111 return V; 2112 // Otherwise, see if "A EqP B" simplifies. 2113 if (MaxRecurse) 2114 if (Value *V = SimplifyICmpInst(EqP, A, B, TD, TLI, DT, MaxRecurse-1)) 2115 return V; 2116 break; 2117 case CmpInst::ICMP_NE: 2118 case CmpInst::ICMP_SGT: { 2119 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2120 // Equivalent to "A InvEqP B". This may be the same as the condition 2121 // tested in the max/min; if so, we can just return that. 2122 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2123 return V; 2124 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2125 return V; 2126 // Otherwise, see if "A InvEqP B" simplifies. 2127 if (MaxRecurse) 2128 if (Value *V = SimplifyICmpInst(InvEqP, A, B, TD, TLI, DT, MaxRecurse-1)) 2129 return V; 2130 break; 2131 } 2132 case CmpInst::ICMP_SGE: 2133 // Always true. 2134 return getTrue(ITy); 2135 case CmpInst::ICMP_SLT: 2136 // Always false. 2137 return getFalse(ITy); 2138 } 2139 } 2140 2141 // Unsigned variants on "max(a,b)>=a -> true". 2142 P = CmpInst::BAD_ICMP_PREDICATE; 2143 if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2144 if (A != RHS) std::swap(A, B); // umax(A, B) pred A. 2145 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2146 // We analyze this as umax(A, B) pred A. 2147 P = Pred; 2148 } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) && 2149 (A == LHS || B == LHS)) { 2150 if (A != LHS) std::swap(A, B); // A pred umax(A, B). 2151 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2152 // We analyze this as umax(A, B) swapped-pred A. 2153 P = CmpInst::getSwappedPredicate(Pred); 2154 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2155 (A == RHS || B == RHS)) { 2156 if (A != RHS) std::swap(A, B); // umin(A, B) pred A. 2157 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2158 // We analyze this as umax(-A, -B) swapped-pred -A. 2159 // Note that we do not need to actually form -A or -B thanks to EqP. 2160 P = CmpInst::getSwappedPredicate(Pred); 2161 } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) && 2162 (A == LHS || B == LHS)) { 2163 if (A != LHS) std::swap(A, B); // A pred umin(A, B). 2164 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2165 // We analyze this as umax(-A, -B) pred -A. 2166 // Note that we do not need to actually form -A or -B thanks to EqP. 2167 P = Pred; 2168 } 2169 if (P != CmpInst::BAD_ICMP_PREDICATE) { 2170 // Cases correspond to "max(A, B) p A". 2171 switch (P) { 2172 default: 2173 break; 2174 case CmpInst::ICMP_EQ: 2175 case CmpInst::ICMP_ULE: 2176 // Equivalent to "A EqP B". This may be the same as the condition tested 2177 // in the max/min; if so, we can just return that. 2178 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2179 return V; 2180 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2181 return V; 2182 // Otherwise, see if "A EqP B" simplifies. 2183 if (MaxRecurse) 2184 if (Value *V = SimplifyICmpInst(EqP, A, B, TD, TLI, DT, MaxRecurse-1)) 2185 return V; 2186 break; 2187 case CmpInst::ICMP_NE: 2188 case CmpInst::ICMP_UGT: { 2189 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2190 // Equivalent to "A InvEqP B". This may be the same as the condition 2191 // tested in the max/min; if so, we can just return that. 2192 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2193 return V; 2194 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2195 return V; 2196 // Otherwise, see if "A InvEqP B" simplifies. 2197 if (MaxRecurse) 2198 if (Value *V = SimplifyICmpInst(InvEqP, A, B, TD, TLI, DT, MaxRecurse-1)) 2199 return V; 2200 break; 2201 } 2202 case CmpInst::ICMP_UGE: 2203 // Always true. 2204 return getTrue(ITy); 2205 case CmpInst::ICMP_ULT: 2206 // Always false. 2207 return getFalse(ITy); 2208 } 2209 } 2210 2211 // Variants on "max(x,y) >= min(x,z)". 2212 Value *C, *D; 2213 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && 2214 match(RHS, m_SMin(m_Value(C), m_Value(D))) && 2215 (A == C || A == D || B == C || B == D)) { 2216 // max(x, ?) pred min(x, ?). 2217 if (Pred == CmpInst::ICMP_SGE) 2218 // Always true. 2219 return getTrue(ITy); 2220 if (Pred == CmpInst::ICMP_SLT) 2221 // Always false. 2222 return getFalse(ITy); 2223 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2224 match(RHS, m_SMax(m_Value(C), m_Value(D))) && 2225 (A == C || A == D || B == C || B == D)) { 2226 // min(x, ?) pred max(x, ?). 2227 if (Pred == CmpInst::ICMP_SLE) 2228 // Always true. 2229 return getTrue(ITy); 2230 if (Pred == CmpInst::ICMP_SGT) 2231 // Always false. 2232 return getFalse(ITy); 2233 } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && 2234 match(RHS, m_UMin(m_Value(C), m_Value(D))) && 2235 (A == C || A == D || B == C || B == D)) { 2236 // max(x, ?) pred min(x, ?). 2237 if (Pred == CmpInst::ICMP_UGE) 2238 // Always true. 2239 return getTrue(ITy); 2240 if (Pred == CmpInst::ICMP_ULT) 2241 // Always false. 2242 return getFalse(ITy); 2243 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2244 match(RHS, m_UMax(m_Value(C), m_Value(D))) && 2245 (A == C || A == D || B == C || B == D)) { 2246 // min(x, ?) pred max(x, ?). 2247 if (Pred == CmpInst::ICMP_ULE) 2248 // Always true. 2249 return getTrue(ITy); 2250 if (Pred == CmpInst::ICMP_UGT) 2251 // Always false. 2252 return getFalse(ITy); 2253 } 2254 2255 // Simplify comparisons of GEPs. 2256 if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) { 2257 if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) { 2258 if (GLHS->getPointerOperand() == GRHS->getPointerOperand() && 2259 GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices()) { 2260 // The bases are equal and the indices are constant. Build a constant 2261 // expression GEP with the same indices and a null base pointer to see 2262 // what constant folding can make out of it. 2263 Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType()); 2264 SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end()); 2265 Constant *NewLHS = ConstantExpr::getGetElementPtr(Null, IndicesLHS); 2266 2267 SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end()); 2268 Constant *NewRHS = ConstantExpr::getGetElementPtr(Null, IndicesRHS); 2269 return ConstantExpr::getICmp(Pred, NewLHS, NewRHS); 2270 } 2271 } 2272 } 2273 2274 // If the comparison is with the result of a select instruction, check whether 2275 // comparing with either branch of the select always yields the same value. 2276 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 2277 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, TLI, DT, MaxRecurse)) 2278 return V; 2279 2280 // If the comparison is with the result of a phi instruction, check whether 2281 // doing the compare with each incoming phi value yields a common result. 2282 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 2283 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, TLI, DT, MaxRecurse)) 2284 return V; 2285 2286 return 0; 2287} 2288 2289Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2290 const TargetData *TD, 2291 const TargetLibraryInfo *TLI, 2292 const DominatorTree *DT) { 2293 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, TLI, DT, RecursionLimit); 2294} 2295 2296/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 2297/// fold the result. If not, this returns null. 2298static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2299 const TargetData *TD, 2300 const TargetLibraryInfo *TLI, 2301 const DominatorTree *DT, 2302 unsigned MaxRecurse) { 2303 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 2304 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 2305 2306 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 2307 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 2308 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD, TLI); 2309 2310 // If we have a constant, make sure it is on the RHS. 2311 std::swap(LHS, RHS); 2312 Pred = CmpInst::getSwappedPredicate(Pred); 2313 } 2314 2315 // Fold trivial predicates. 2316 if (Pred == FCmpInst::FCMP_FALSE) 2317 return ConstantInt::get(GetCompareTy(LHS), 0); 2318 if (Pred == FCmpInst::FCMP_TRUE) 2319 return ConstantInt::get(GetCompareTy(LHS), 1); 2320 2321 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 2322 return UndefValue::get(GetCompareTy(LHS)); 2323 2324 // fcmp x,x -> true/false. Not all compares are foldable. 2325 if (LHS == RHS) { 2326 if (CmpInst::isTrueWhenEqual(Pred)) 2327 return ConstantInt::get(GetCompareTy(LHS), 1); 2328 if (CmpInst::isFalseWhenEqual(Pred)) 2329 return ConstantInt::get(GetCompareTy(LHS), 0); 2330 } 2331 2332 // Handle fcmp with constant RHS 2333 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 2334 // If the constant is a nan, see if we can fold the comparison based on it. 2335 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 2336 if (CFP->getValueAPF().isNaN()) { 2337 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 2338 return ConstantInt::getFalse(CFP->getContext()); 2339 assert(FCmpInst::isUnordered(Pred) && 2340 "Comparison must be either ordered or unordered!"); 2341 // True if unordered. 2342 return ConstantInt::getTrue(CFP->getContext()); 2343 } 2344 // Check whether the constant is an infinity. 2345 if (CFP->getValueAPF().isInfinity()) { 2346 if (CFP->getValueAPF().isNegative()) { 2347 switch (Pred) { 2348 case FCmpInst::FCMP_OLT: 2349 // No value is ordered and less than negative infinity. 2350 return ConstantInt::getFalse(CFP->getContext()); 2351 case FCmpInst::FCMP_UGE: 2352 // All values are unordered with or at least negative infinity. 2353 return ConstantInt::getTrue(CFP->getContext()); 2354 default: 2355 break; 2356 } 2357 } else { 2358 switch (Pred) { 2359 case FCmpInst::FCMP_OGT: 2360 // No value is ordered and greater than infinity. 2361 return ConstantInt::getFalse(CFP->getContext()); 2362 case FCmpInst::FCMP_ULE: 2363 // All values are unordered with and at most infinity. 2364 return ConstantInt::getTrue(CFP->getContext()); 2365 default: 2366 break; 2367 } 2368 } 2369 } 2370 } 2371 } 2372 2373 // If the comparison is with the result of a select instruction, check whether 2374 // comparing with either branch of the select always yields the same value. 2375 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 2376 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, TLI, DT, MaxRecurse)) 2377 return V; 2378 2379 // If the comparison is with the result of a phi instruction, check whether 2380 // doing the compare with each incoming phi value yields a common result. 2381 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 2382 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, TLI, DT, MaxRecurse)) 2383 return V; 2384 2385 return 0; 2386} 2387 2388Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2389 const TargetData *TD, 2390 const TargetLibraryInfo *TLI, 2391 const DominatorTree *DT) { 2392 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, TLI, DT, RecursionLimit); 2393} 2394 2395/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 2396/// the result. If not, this returns null. 2397Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 2398 const TargetData *TD, const DominatorTree *) { 2399 // select true, X, Y -> X 2400 // select false, X, Y -> Y 2401 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 2402 return CB->getZExtValue() ? TrueVal : FalseVal; 2403 2404 // select C, X, X -> X 2405 if (TrueVal == FalseVal) 2406 return TrueVal; 2407 2408 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 2409 if (isa<Constant>(TrueVal)) 2410 return TrueVal; 2411 return FalseVal; 2412 } 2413 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 2414 return FalseVal; 2415 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 2416 return TrueVal; 2417 2418 return 0; 2419} 2420 2421/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 2422/// fold the result. If not, this returns null. 2423Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const TargetData *TD, 2424 const DominatorTree *) { 2425 // The type of the GEP pointer operand. 2426 PointerType *PtrTy = dyn_cast<PointerType>(Ops[0]->getType()); 2427 // The GEP pointer operand is not a pointer, it's a vector of pointers. 2428 if (!PtrTy) 2429 return 0; 2430 2431 // getelementptr P -> P. 2432 if (Ops.size() == 1) 2433 return Ops[0]; 2434 2435 if (isa<UndefValue>(Ops[0])) { 2436 // Compute the (pointer) type returned by the GEP instruction. 2437 Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, Ops.slice(1)); 2438 Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 2439 return UndefValue::get(GEPTy); 2440 } 2441 2442 if (Ops.size() == 2) { 2443 // getelementptr P, 0 -> P. 2444 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 2445 if (C->isZero()) 2446 return Ops[0]; 2447 // getelementptr P, N -> P if P points to a type of zero size. 2448 if (TD) { 2449 Type *Ty = PtrTy->getElementType(); 2450 if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0) 2451 return Ops[0]; 2452 } 2453 } 2454 2455 // Check to see if this is constant foldable. 2456 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 2457 if (!isa<Constant>(Ops[i])) 2458 return 0; 2459 2460 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), Ops.slice(1)); 2461} 2462 2463/// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we 2464/// can fold the result. If not, this returns null. 2465Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val, 2466 ArrayRef<unsigned> Idxs, 2467 const TargetData *, 2468 const DominatorTree *) { 2469 if (Constant *CAgg = dyn_cast<Constant>(Agg)) 2470 if (Constant *CVal = dyn_cast<Constant>(Val)) 2471 return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs); 2472 2473 // insertvalue x, undef, n -> x 2474 if (match(Val, m_Undef())) 2475 return Agg; 2476 2477 // insertvalue x, (extractvalue y, n), n 2478 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val)) 2479 if (EV->getAggregateOperand()->getType() == Agg->getType() && 2480 EV->getIndices() == Idxs) { 2481 // insertvalue undef, (extractvalue y, n), n -> y 2482 if (match(Agg, m_Undef())) 2483 return EV->getAggregateOperand(); 2484 2485 // insertvalue y, (extractvalue y, n), n -> y 2486 if (Agg == EV->getAggregateOperand()) 2487 return Agg; 2488 } 2489 2490 return 0; 2491} 2492 2493/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 2494static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 2495 // If all of the PHI's incoming values are the same then replace the PHI node 2496 // with the common value. 2497 Value *CommonValue = 0; 2498 bool HasUndefInput = false; 2499 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 2500 Value *Incoming = PN->getIncomingValue(i); 2501 // If the incoming value is the phi node itself, it can safely be skipped. 2502 if (Incoming == PN) continue; 2503 if (isa<UndefValue>(Incoming)) { 2504 // Remember that we saw an undef value, but otherwise ignore them. 2505 HasUndefInput = true; 2506 continue; 2507 } 2508 if (CommonValue && Incoming != CommonValue) 2509 return 0; // Not the same, bail out. 2510 CommonValue = Incoming; 2511 } 2512 2513 // If CommonValue is null then all of the incoming values were either undef or 2514 // equal to the phi node itself. 2515 if (!CommonValue) 2516 return UndefValue::get(PN->getType()); 2517 2518 // If we have a PHI node like phi(X, undef, X), where X is defined by some 2519 // instruction, we cannot return X as the result of the PHI node unless it 2520 // dominates the PHI block. 2521 if (HasUndefInput) 2522 return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 2523 2524 return CommonValue; 2525} 2526 2527//=== Helper functions for higher up the class hierarchy. 2528 2529/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 2530/// fold the result. If not, this returns null. 2531static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 2532 const TargetData *TD, 2533 const TargetLibraryInfo *TLI, 2534 const DominatorTree *DT, 2535 unsigned MaxRecurse) { 2536 switch (Opcode) { 2537 case Instruction::Add: 2538 return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 2539 TD, TLI, DT, MaxRecurse); 2540 case Instruction::Sub: 2541 return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 2542 TD, TLI, DT, MaxRecurse); 2543 case Instruction::Mul: return SimplifyMulInst (LHS, RHS, TD, TLI, DT, 2544 MaxRecurse); 2545 case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, TD, TLI, DT, 2546 MaxRecurse); 2547 case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, TD, TLI, DT, 2548 MaxRecurse); 2549 case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, TD, TLI, DT, 2550 MaxRecurse); 2551 case Instruction::SRem: return SimplifySRemInst(LHS, RHS, TD, TLI, DT, 2552 MaxRecurse); 2553 case Instruction::URem: return SimplifyURemInst(LHS, RHS, TD, TLI, DT, 2554 MaxRecurse); 2555 case Instruction::FRem: return SimplifyFRemInst(LHS, RHS, TD, TLI, DT, 2556 MaxRecurse); 2557 case Instruction::Shl: 2558 return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 2559 TD, TLI, DT, MaxRecurse); 2560 case Instruction::LShr: 2561 return SimplifyLShrInst(LHS, RHS, /*isExact*/false, TD, TLI, DT, 2562 MaxRecurse); 2563 case Instruction::AShr: 2564 return SimplifyAShrInst(LHS, RHS, /*isExact*/false, TD, TLI, DT, 2565 MaxRecurse); 2566 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, TLI, DT, 2567 MaxRecurse); 2568 case Instruction::Or: return SimplifyOrInst (LHS, RHS, TD, TLI, DT, 2569 MaxRecurse); 2570 case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, TLI, DT, 2571 MaxRecurse); 2572 default: 2573 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 2574 if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 2575 Constant *COps[] = {CLHS, CRHS}; 2576 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, TD, TLI); 2577 } 2578 2579 // If the operation is associative, try some generic simplifications. 2580 if (Instruction::isAssociative(Opcode)) 2581 if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, TLI, DT, 2582 MaxRecurse)) 2583 return V; 2584 2585 // If the operation is with the result of a select instruction, check whether 2586 // operating on either branch of the select always yields the same value. 2587 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 2588 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, TLI, DT, 2589 MaxRecurse)) 2590 return V; 2591 2592 // If the operation is with the result of a phi instruction, check whether 2593 // operating on all incoming values of the phi always yields the same value. 2594 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 2595 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, TLI, DT, 2596 MaxRecurse)) 2597 return V; 2598 2599 return 0; 2600 } 2601} 2602 2603Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 2604 const TargetData *TD, const TargetLibraryInfo *TLI, 2605 const DominatorTree *DT) { 2606 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, TLI, DT, RecursionLimit); 2607} 2608 2609/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 2610/// fold the result. 2611static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2612 const TargetData *TD, 2613 const TargetLibraryInfo *TLI, 2614 const DominatorTree *DT, 2615 unsigned MaxRecurse) { 2616 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 2617 return SimplifyICmpInst(Predicate, LHS, RHS, TD, TLI, DT, MaxRecurse); 2618 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, TLI, DT, MaxRecurse); 2619} 2620 2621Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2622 const TargetData *TD, const TargetLibraryInfo *TLI, 2623 const DominatorTree *DT) { 2624 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, TLI, DT, RecursionLimit); 2625} 2626 2627static Value *SimplifyCallInst(CallInst *CI) { 2628 // call undef -> undef 2629 if (isa<UndefValue>(CI->getCalledValue())) 2630 return UndefValue::get(CI->getType()); 2631 2632 return 0; 2633} 2634 2635/// SimplifyInstruction - See if we can compute a simplified version of this 2636/// instruction. If not, this returns null. 2637Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 2638 const TargetLibraryInfo *TLI, 2639 const DominatorTree *DT) { 2640 Value *Result; 2641 2642 switch (I->getOpcode()) { 2643 default: 2644 Result = ConstantFoldInstruction(I, TD, TLI); 2645 break; 2646 case Instruction::Add: 2647 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 2648 cast<BinaryOperator>(I)->hasNoSignedWrap(), 2649 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 2650 TD, TLI, DT); 2651 break; 2652 case Instruction::Sub: 2653 Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 2654 cast<BinaryOperator>(I)->hasNoSignedWrap(), 2655 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 2656 TD, TLI, DT); 2657 break; 2658 case Instruction::Mul: 2659 Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2660 break; 2661 case Instruction::SDiv: 2662 Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2663 break; 2664 case Instruction::UDiv: 2665 Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2666 break; 2667 case Instruction::FDiv: 2668 Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2669 break; 2670 case Instruction::SRem: 2671 Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2672 break; 2673 case Instruction::URem: 2674 Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2675 break; 2676 case Instruction::FRem: 2677 Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2678 break; 2679 case Instruction::Shl: 2680 Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), 2681 cast<BinaryOperator>(I)->hasNoSignedWrap(), 2682 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 2683 TD, TLI, DT); 2684 break; 2685 case Instruction::LShr: 2686 Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), 2687 cast<BinaryOperator>(I)->isExact(), 2688 TD, TLI, DT); 2689 break; 2690 case Instruction::AShr: 2691 Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), 2692 cast<BinaryOperator>(I)->isExact(), 2693 TD, TLI, DT); 2694 break; 2695 case Instruction::And: 2696 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2697 break; 2698 case Instruction::Or: 2699 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2700 break; 2701 case Instruction::Xor: 2702 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2703 break; 2704 case Instruction::ICmp: 2705 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 2706 I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2707 break; 2708 case Instruction::FCmp: 2709 Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 2710 I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2711 break; 2712 case Instruction::Select: 2713 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 2714 I->getOperand(2), TD, DT); 2715 break; 2716 case Instruction::GetElementPtr: { 2717 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 2718 Result = SimplifyGEPInst(Ops, TD, DT); 2719 break; 2720 } 2721 case Instruction::InsertValue: { 2722 InsertValueInst *IV = cast<InsertValueInst>(I); 2723 Result = SimplifyInsertValueInst(IV->getAggregateOperand(), 2724 IV->getInsertedValueOperand(), 2725 IV->getIndices(), TD, DT); 2726 break; 2727 } 2728 case Instruction::PHI: 2729 Result = SimplifyPHINode(cast<PHINode>(I), DT); 2730 break; 2731 case Instruction::Call: 2732 Result = SimplifyCallInst(cast<CallInst>(I)); 2733 break; 2734 } 2735 2736 /// If called on unreachable code, the above logic may report that the 2737 /// instruction simplified to itself. Make life easier for users by 2738 /// detecting that case here, returning a safe value instead. 2739 return Result == I ? UndefValue::get(I->getType()) : Result; 2740} 2741 2742/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 2743/// delete the From instruction. In addition to a basic RAUW, this does a 2744/// recursive simplification of the newly formed instructions. This catches 2745/// things where one simplification exposes other opportunities. This only 2746/// simplifies and deletes scalar operations, it does not change the CFG. 2747/// 2748void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 2749 const TargetData *TD, 2750 const TargetLibraryInfo *TLI, 2751 const DominatorTree *DT) { 2752 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 2753 2754 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 2755 // we can know if it gets deleted out from under us or replaced in a 2756 // recursive simplification. 2757 WeakVH FromHandle(From); 2758 WeakVH ToHandle(To); 2759 2760 while (!From->use_empty()) { 2761 // Update the instruction to use the new value. 2762 Use &TheUse = From->use_begin().getUse(); 2763 Instruction *User = cast<Instruction>(TheUse.getUser()); 2764 TheUse = To; 2765 2766 // Check to see if the instruction can be folded due to the operand 2767 // replacement. For example changing (or X, Y) into (or X, -1) can replace 2768 // the 'or' with -1. 2769 Value *SimplifiedVal; 2770 { 2771 // Sanity check to make sure 'User' doesn't dangle across 2772 // SimplifyInstruction. 2773 AssertingVH<> UserHandle(User); 2774 2775 SimplifiedVal = SimplifyInstruction(User, TD, TLI, DT); 2776 if (SimplifiedVal == 0) continue; 2777 } 2778 2779 // Recursively simplify this user to the new value. 2780 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, TLI, DT); 2781 From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 2782 To = ToHandle; 2783 2784 assert(ToHandle && "To value deleted by recursive simplification?"); 2785 2786 // If the recursive simplification ended up revisiting and deleting 2787 // 'From' then we're done. 2788 if (From == 0) 2789 return; 2790 } 2791 2792 // If 'From' has value handles referring to it, do a real RAUW to update them. 2793 From->replaceAllUsesWith(To); 2794 2795 From->eraseFromParent(); 2796} 2797