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