InstructionSimplify.cpp revision 1608769abeb1430dc34f31ffac0d9850f99ae36a
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, *Y = 0; 816 if ((match(Op0, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op1) || // (X / Y) * Y 817 (match(Op1, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op0)) { // Y * (X / Y) 818 PossiblyExactOperator *Div = 819 cast<PossiblyExactOperator>(Y == Op1 ? Op0 : Op1); 820 if (Div->isExact()) 821 return X; 822 } 823 824 // i1 mul -> and. 825 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 826 if (Value *V = SimplifyAndInst(Op0, Op1, TD, TLI, DT, MaxRecurse-1)) 827 return V; 828 829 // Try some generic simplifications for associative operations. 830 if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, TLI, DT, 831 MaxRecurse)) 832 return V; 833 834 // Mul distributes over Add. Try some generic simplifications based on this. 835 if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 836 TD, TLI, DT, MaxRecurse)) 837 return V; 838 839 // If the operation is with the result of a select instruction, check whether 840 // operating on either branch of the select always yields the same value. 841 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 842 if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, TLI, DT, 843 MaxRecurse)) 844 return V; 845 846 // If the operation is with the result of a phi instruction, check whether 847 // operating on all incoming values of the phi always yields the same value. 848 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 849 if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, TLI, DT, 850 MaxRecurse)) 851 return V; 852 853 return 0; 854} 855 856Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 857 const TargetLibraryInfo *TLI, 858 const DominatorTree *DT) { 859 return ::SimplifyMulInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 860} 861 862/// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can 863/// fold the result. If not, this returns null. 864static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 865 const TargetData *TD, const TargetLibraryInfo *TLI, 866 const DominatorTree *DT, unsigned MaxRecurse) { 867 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 868 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 869 Constant *Ops[] = { C0, C1 }; 870 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, TD, TLI); 871 } 872 } 873 874 bool isSigned = Opcode == Instruction::SDiv; 875 876 // X / undef -> undef 877 if (match(Op1, m_Undef())) 878 return Op1; 879 880 // undef / X -> 0 881 if (match(Op0, m_Undef())) 882 return Constant::getNullValue(Op0->getType()); 883 884 // 0 / X -> 0, we don't need to preserve faults! 885 if (match(Op0, m_Zero())) 886 return Op0; 887 888 // X / 1 -> X 889 if (match(Op1, m_One())) 890 return Op0; 891 892 if (Op0->getType()->isIntegerTy(1)) 893 // It can't be division by zero, hence it must be division by one. 894 return Op0; 895 896 // X / X -> 1 897 if (Op0 == Op1) 898 return ConstantInt::get(Op0->getType(), 1); 899 900 // (X * Y) / Y -> X if the multiplication does not overflow. 901 Value *X = 0, *Y = 0; 902 if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { 903 if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 904 OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0); 905 // If the Mul knows it does not overflow, then we are good to go. 906 if ((isSigned && Mul->hasNoSignedWrap()) || 907 (!isSigned && Mul->hasNoUnsignedWrap())) 908 return X; 909 // If X has the form X = A / Y then X * Y cannot overflow. 910 if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X)) 911 if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) 912 return X; 913 } 914 915 // (X rem Y) / Y -> 0 916 if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 917 (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 918 return Constant::getNullValue(Op0->getType()); 919 920 // If the operation is with the result of a select instruction, check whether 921 // operating on either branch of the select always yields the same value. 922 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 923 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, TLI, DT, 924 MaxRecurse)) 925 return V; 926 927 // If the operation is with the result of a phi instruction, check whether 928 // operating on all incoming values of the phi always yields the same value. 929 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 930 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, TLI, DT, 931 MaxRecurse)) 932 return V; 933 934 return 0; 935} 936 937/// SimplifySDivInst - Given operands for an SDiv, see if we can 938/// fold the result. If not, this returns null. 939static Value *SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, 940 const TargetLibraryInfo *TLI, 941 const DominatorTree *DT, unsigned MaxRecurse) { 942 if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, TD, TLI, DT, 943 MaxRecurse)) 944 return V; 945 946 return 0; 947} 948 949Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, 950 const TargetLibraryInfo *TLI, 951 const DominatorTree *DT) { 952 return ::SimplifySDivInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 953} 954 955/// SimplifyUDivInst - Given operands for a UDiv, see if we can 956/// fold the result. If not, this returns null. 957static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, 958 const TargetLibraryInfo *TLI, 959 const DominatorTree *DT, unsigned MaxRecurse) { 960 if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, TD, TLI, DT, 961 MaxRecurse)) 962 return V; 963 964 return 0; 965} 966 967Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, 968 const TargetLibraryInfo *TLI, 969 const DominatorTree *DT) { 970 return ::SimplifyUDivInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 971} 972 973static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *, 974 const TargetLibraryInfo *, 975 const DominatorTree *, unsigned) { 976 // undef / X -> undef (the undef could be a snan). 977 if (match(Op0, m_Undef())) 978 return Op0; 979 980 // X / undef -> undef 981 if (match(Op1, m_Undef())) 982 return Op1; 983 984 return 0; 985} 986 987Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *TD, 988 const TargetLibraryInfo *TLI, 989 const DominatorTree *DT) { 990 return ::SimplifyFDivInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 991} 992 993/// SimplifyRem - Given operands for an SRem or URem, see if we can 994/// fold the result. If not, this returns null. 995static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 996 const TargetData *TD, const TargetLibraryInfo *TLI, 997 const DominatorTree *DT, unsigned MaxRecurse) { 998 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 999 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1000 Constant *Ops[] = { C0, C1 }; 1001 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, TD, TLI); 1002 } 1003 } 1004 1005 // X % undef -> undef 1006 if (match(Op1, m_Undef())) 1007 return Op1; 1008 1009 // undef % X -> 0 1010 if (match(Op0, m_Undef())) 1011 return Constant::getNullValue(Op0->getType()); 1012 1013 // 0 % X -> 0, we don't need to preserve faults! 1014 if (match(Op0, m_Zero())) 1015 return Op0; 1016 1017 // X % 0 -> undef, we don't need to preserve faults! 1018 if (match(Op1, m_Zero())) 1019 return UndefValue::get(Op0->getType()); 1020 1021 // X % 1 -> 0 1022 if (match(Op1, m_One())) 1023 return Constant::getNullValue(Op0->getType()); 1024 1025 if (Op0->getType()->isIntegerTy(1)) 1026 // It can't be remainder by zero, hence it must be remainder by one. 1027 return Constant::getNullValue(Op0->getType()); 1028 1029 // X % X -> 0 1030 if (Op0 == Op1) 1031 return Constant::getNullValue(Op0->getType()); 1032 1033 // If the operation is with the result of a select instruction, check whether 1034 // operating on either branch of the select always yields the same value. 1035 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1036 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1037 return V; 1038 1039 // If the operation is with the result of a phi instruction, check whether 1040 // operating on all incoming values of the phi always yields the same value. 1041 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1042 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1043 return V; 1044 1045 return 0; 1046} 1047 1048/// SimplifySRemInst - Given operands for an SRem, see if we can 1049/// fold the result. If not, this returns null. 1050static Value *SimplifySRemInst(Value *Op0, Value *Op1, const TargetData *TD, 1051 const TargetLibraryInfo *TLI, 1052 const DominatorTree *DT, 1053 unsigned MaxRecurse) { 1054 if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1055 return V; 1056 1057 return 0; 1058} 1059 1060Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const TargetData *TD, 1061 const TargetLibraryInfo *TLI, 1062 const DominatorTree *DT) { 1063 return ::SimplifySRemInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1064} 1065 1066/// SimplifyURemInst - Given operands for a URem, see if we can 1067/// fold the result. If not, this returns null. 1068static Value *SimplifyURemInst(Value *Op0, Value *Op1, const TargetData *TD, 1069 const TargetLibraryInfo *TLI, 1070 const DominatorTree *DT, 1071 unsigned MaxRecurse) { 1072 if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1073 return V; 1074 1075 return 0; 1076} 1077 1078Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const TargetData *TD, 1079 const TargetLibraryInfo *TLI, 1080 const DominatorTree *DT) { 1081 return ::SimplifyURemInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1082} 1083 1084static Value *SimplifyFRemInst(Value *Op0, Value *Op1, const TargetData *, 1085 const TargetLibraryInfo *, 1086 const DominatorTree *, 1087 unsigned) { 1088 // undef % X -> undef (the undef could be a snan). 1089 if (match(Op0, m_Undef())) 1090 return Op0; 1091 1092 // X % undef -> undef 1093 if (match(Op1, m_Undef())) 1094 return Op1; 1095 1096 return 0; 1097} 1098 1099Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const TargetData *TD, 1100 const TargetLibraryInfo *TLI, 1101 const DominatorTree *DT) { 1102 return ::SimplifyFRemInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1103} 1104 1105/// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can 1106/// fold the result. If not, this returns null. 1107static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, 1108 const TargetData *TD, const TargetLibraryInfo *TLI, 1109 const DominatorTree *DT, unsigned MaxRecurse) { 1110 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1111 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1112 Constant *Ops[] = { C0, C1 }; 1113 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, TD, TLI); 1114 } 1115 } 1116 1117 // 0 shift by X -> 0 1118 if (match(Op0, m_Zero())) 1119 return Op0; 1120 1121 // X shift by 0 -> X 1122 if (match(Op1, m_Zero())) 1123 return Op0; 1124 1125 // X shift by undef -> undef because it may shift by the bitwidth. 1126 if (match(Op1, m_Undef())) 1127 return Op1; 1128 1129 // Shifting by the bitwidth or more is undefined. 1130 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) 1131 if (CI->getValue().getLimitedValue() >= 1132 Op0->getType()->getScalarSizeInBits()) 1133 return UndefValue::get(Op0->getType()); 1134 1135 // If the operation is with the result of a select instruction, check whether 1136 // operating on either branch of the select always yields the same value. 1137 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1138 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1139 return V; 1140 1141 // If the operation is with the result of a phi instruction, check whether 1142 // operating on all incoming values of the phi always yields the same value. 1143 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1144 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1145 return V; 1146 1147 return 0; 1148} 1149 1150/// SimplifyShlInst - Given operands for an Shl, see if we can 1151/// fold the result. If not, this returns null. 1152static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1153 const TargetData *TD, 1154 const TargetLibraryInfo *TLI, 1155 const DominatorTree *DT, unsigned MaxRecurse) { 1156 if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1157 return V; 1158 1159 // undef << X -> 0 1160 if (match(Op0, m_Undef())) 1161 return Constant::getNullValue(Op0->getType()); 1162 1163 // (X >> A) << A -> X 1164 Value *X; 1165 if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1))) && 1166 cast<PossiblyExactOperator>(Op0)->isExact()) 1167 return X; 1168 return 0; 1169} 1170 1171Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1172 const TargetData *TD, const TargetLibraryInfo *TLI, 1173 const DominatorTree *DT) { 1174 return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, TD, TLI, DT, RecursionLimit); 1175} 1176 1177/// SimplifyLShrInst - Given operands for an LShr, see if we can 1178/// fold the result. If not, this returns null. 1179static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1180 const TargetData *TD, 1181 const TargetLibraryInfo *TLI, 1182 const DominatorTree *DT, 1183 unsigned MaxRecurse) { 1184 if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1185 return V; 1186 1187 // undef >>l X -> 0 1188 if (match(Op0, m_Undef())) 1189 return Constant::getNullValue(Op0->getType()); 1190 1191 // (X << A) >> A -> X 1192 Value *X; 1193 if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) && 1194 cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap()) 1195 return X; 1196 1197 return 0; 1198} 1199 1200Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1201 const TargetData *TD, 1202 const TargetLibraryInfo *TLI, 1203 const DominatorTree *DT) { 1204 return ::SimplifyLShrInst(Op0, Op1, isExact, TD, TLI, DT, RecursionLimit); 1205} 1206 1207/// SimplifyAShrInst - Given operands for an AShr, see if we can 1208/// fold the result. If not, this returns null. 1209static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1210 const TargetData *TD, 1211 const TargetLibraryInfo *TLI, 1212 const DominatorTree *DT, 1213 unsigned MaxRecurse) { 1214 if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, TD, TLI, DT, MaxRecurse)) 1215 return V; 1216 1217 // all ones >>a X -> all ones 1218 if (match(Op0, m_AllOnes())) 1219 return Op0; 1220 1221 // undef >>a X -> all ones 1222 if (match(Op0, m_Undef())) 1223 return Constant::getAllOnesValue(Op0->getType()); 1224 1225 // (X << A) >> A -> X 1226 Value *X; 1227 if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) && 1228 cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap()) 1229 return X; 1230 1231 return 0; 1232} 1233 1234Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1235 const TargetData *TD, 1236 const TargetLibraryInfo *TLI, 1237 const DominatorTree *DT) { 1238 return ::SimplifyAShrInst(Op0, Op1, isExact, TD, TLI, DT, RecursionLimit); 1239} 1240 1241/// SimplifyAndInst - Given operands for an And, see if we can 1242/// fold the result. If not, this returns null. 1243static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 1244 const TargetLibraryInfo *TLI, 1245 const DominatorTree *DT, 1246 unsigned MaxRecurse) { 1247 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1248 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1249 Constant *Ops[] = { CLHS, CRHS }; 1250 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 1251 Ops, TD, TLI); 1252 } 1253 1254 // Canonicalize the constant to the RHS. 1255 std::swap(Op0, Op1); 1256 } 1257 1258 // X & undef -> 0 1259 if (match(Op1, m_Undef())) 1260 return Constant::getNullValue(Op0->getType()); 1261 1262 // X & X = X 1263 if (Op0 == Op1) 1264 return Op0; 1265 1266 // X & 0 = 0 1267 if (match(Op1, m_Zero())) 1268 return Op1; 1269 1270 // X & -1 = X 1271 if (match(Op1, m_AllOnes())) 1272 return Op0; 1273 1274 // A & ~A = ~A & A = 0 1275 if (match(Op0, m_Not(m_Specific(Op1))) || 1276 match(Op1, m_Not(m_Specific(Op0)))) 1277 return Constant::getNullValue(Op0->getType()); 1278 1279 // (A | ?) & A = A 1280 Value *A = 0, *B = 0; 1281 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1282 (A == Op1 || B == Op1)) 1283 return Op1; 1284 1285 // A & (A | ?) = A 1286 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1287 (A == Op0 || B == Op0)) 1288 return Op0; 1289 1290 // A & (-A) = A if A is a power of two or zero. 1291 if (match(Op0, m_Neg(m_Specific(Op1))) || 1292 match(Op1, m_Neg(m_Specific(Op0)))) { 1293 if (isPowerOfTwo(Op0, TD, /*OrZero*/true)) 1294 return Op0; 1295 if (isPowerOfTwo(Op1, TD, /*OrZero*/true)) 1296 return Op1; 1297 } 1298 1299 // Try some generic simplifications for associative operations. 1300 if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, TLI, 1301 DT, MaxRecurse)) 1302 return V; 1303 1304 // And distributes over Or. Try some generic simplifications based on this. 1305 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1306 TD, TLI, DT, MaxRecurse)) 1307 return V; 1308 1309 // And distributes over Xor. Try some generic simplifications based on this. 1310 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 1311 TD, TLI, DT, MaxRecurse)) 1312 return V; 1313 1314 // Or distributes over And. Try some generic simplifications based on this. 1315 if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1316 TD, TLI, DT, MaxRecurse)) 1317 return V; 1318 1319 // If the operation is with the result of a select instruction, check whether 1320 // operating on either branch of the select always yields the same value. 1321 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1322 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, TLI, 1323 DT, MaxRecurse)) 1324 return V; 1325 1326 // If the operation is with the result of a phi instruction, check whether 1327 // operating on all incoming values of the phi always yields the same value. 1328 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1329 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, TLI, DT, 1330 MaxRecurse)) 1331 return V; 1332 1333 return 0; 1334} 1335 1336Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 1337 const TargetLibraryInfo *TLI, 1338 const DominatorTree *DT) { 1339 return ::SimplifyAndInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1340} 1341 1342/// SimplifyOrInst - Given operands for an Or, see if we can 1343/// fold the result. If not, this returns null. 1344static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 1345 const TargetLibraryInfo *TLI, 1346 const DominatorTree *DT, unsigned MaxRecurse) { 1347 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1348 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1349 Constant *Ops[] = { CLHS, CRHS }; 1350 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 1351 Ops, TD, TLI); 1352 } 1353 1354 // Canonicalize the constant to the RHS. 1355 std::swap(Op0, Op1); 1356 } 1357 1358 // X | undef -> -1 1359 if (match(Op1, m_Undef())) 1360 return Constant::getAllOnesValue(Op0->getType()); 1361 1362 // X | X = X 1363 if (Op0 == Op1) 1364 return Op0; 1365 1366 // X | 0 = X 1367 if (match(Op1, m_Zero())) 1368 return Op0; 1369 1370 // X | -1 = -1 1371 if (match(Op1, m_AllOnes())) 1372 return Op1; 1373 1374 // A | ~A = ~A | A = -1 1375 if (match(Op0, m_Not(m_Specific(Op1))) || 1376 match(Op1, m_Not(m_Specific(Op0)))) 1377 return Constant::getAllOnesValue(Op0->getType()); 1378 1379 // (A & ?) | A = A 1380 Value *A = 0, *B = 0; 1381 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 1382 (A == Op1 || B == Op1)) 1383 return Op1; 1384 1385 // A | (A & ?) = A 1386 if (match(Op1, m_And(m_Value(A), m_Value(B))) && 1387 (A == Op0 || B == Op0)) 1388 return Op0; 1389 1390 // ~(A & ?) | A = -1 1391 if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) && 1392 (A == Op1 || B == Op1)) 1393 return Constant::getAllOnesValue(Op1->getType()); 1394 1395 // A | ~(A & ?) = -1 1396 if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) && 1397 (A == Op0 || B == Op0)) 1398 return Constant::getAllOnesValue(Op0->getType()); 1399 1400 // Try some generic simplifications for associative operations. 1401 if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, TLI, 1402 DT, MaxRecurse)) 1403 return V; 1404 1405 // Or distributes over And. Try some generic simplifications based on this. 1406 if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, TD, 1407 TLI, DT, MaxRecurse)) 1408 return V; 1409 1410 // And distributes over Or. Try some generic simplifications based on this. 1411 if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And, 1412 TD, TLI, DT, MaxRecurse)) 1413 return V; 1414 1415 // If the operation is with the result of a select instruction, check whether 1416 // operating on either branch of the select always yields the same value. 1417 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1418 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, TLI, DT, 1419 MaxRecurse)) 1420 return V; 1421 1422 // If the operation is with the result of a phi instruction, check whether 1423 // operating on all incoming values of the phi always yields the same value. 1424 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1425 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, TLI, DT, 1426 MaxRecurse)) 1427 return V; 1428 1429 return 0; 1430} 1431 1432Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 1433 const TargetLibraryInfo *TLI, 1434 const DominatorTree *DT) { 1435 return ::SimplifyOrInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1436} 1437 1438/// SimplifyXorInst - Given operands for a Xor, see if we can 1439/// fold the result. If not, this returns null. 1440static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 1441 const TargetLibraryInfo *TLI, 1442 const DominatorTree *DT, unsigned MaxRecurse) { 1443 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1444 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1445 Constant *Ops[] = { CLHS, CRHS }; 1446 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 1447 Ops, TD, TLI); 1448 } 1449 1450 // Canonicalize the constant to the RHS. 1451 std::swap(Op0, Op1); 1452 } 1453 1454 // A ^ undef -> undef 1455 if (match(Op1, m_Undef())) 1456 return Op1; 1457 1458 // A ^ 0 = A 1459 if (match(Op1, m_Zero())) 1460 return Op0; 1461 1462 // A ^ A = 0 1463 if (Op0 == Op1) 1464 return Constant::getNullValue(Op0->getType()); 1465 1466 // A ^ ~A = ~A ^ A = -1 1467 if (match(Op0, m_Not(m_Specific(Op1))) || 1468 match(Op1, m_Not(m_Specific(Op0)))) 1469 return Constant::getAllOnesValue(Op0->getType()); 1470 1471 // Try some generic simplifications for associative operations. 1472 if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, TLI, 1473 DT, MaxRecurse)) 1474 return V; 1475 1476 // And distributes over Xor. Try some generic simplifications based on this. 1477 if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And, 1478 TD, TLI, DT, MaxRecurse)) 1479 return V; 1480 1481 // Threading Xor over selects and phi nodes is pointless, so don't bother. 1482 // Threading over the select in "A ^ select(cond, B, C)" means evaluating 1483 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 1484 // only if B and C are equal. If B and C are equal then (since we assume 1485 // that operands have already been simplified) "select(cond, B, C)" should 1486 // have been simplified to the common value of B and C already. Analysing 1487 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 1488 // for threading over phi nodes. 1489 1490 return 0; 1491} 1492 1493Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 1494 const TargetLibraryInfo *TLI, 1495 const DominatorTree *DT) { 1496 return ::SimplifyXorInst(Op0, Op1, TD, TLI, DT, RecursionLimit); 1497} 1498 1499static Type *GetCompareTy(Value *Op) { 1500 return CmpInst::makeCmpResultType(Op->getType()); 1501} 1502 1503/// ExtractEquivalentCondition - Rummage around inside V looking for something 1504/// equivalent to the comparison "LHS Pred RHS". Return such a value if found, 1505/// otherwise return null. Helper function for analyzing max/min idioms. 1506static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred, 1507 Value *LHS, Value *RHS) { 1508 SelectInst *SI = dyn_cast<SelectInst>(V); 1509 if (!SI) 1510 return 0; 1511 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition()); 1512 if (!Cmp) 1513 return 0; 1514 Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1); 1515 if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS) 1516 return Cmp; 1517 if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) && 1518 LHS == CmpRHS && RHS == CmpLHS) 1519 return Cmp; 1520 return 0; 1521} 1522 1523/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 1524/// fold the result. If not, this returns null. 1525static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1526 const TargetData *TD, 1527 const TargetLibraryInfo *TLI, 1528 const DominatorTree *DT, 1529 unsigned MaxRecurse) { 1530 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 1531 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 1532 1533 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 1534 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1535 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD, TLI); 1536 1537 // If we have a constant, make sure it is on the RHS. 1538 std::swap(LHS, RHS); 1539 Pred = CmpInst::getSwappedPredicate(Pred); 1540 } 1541 1542 Type *ITy = GetCompareTy(LHS); // The return type. 1543 Type *OpTy = LHS->getType(); // The operand type. 1544 1545 // icmp X, X -> true/false 1546 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 1547 // because X could be 0. 1548 if (LHS == RHS || isa<UndefValue>(RHS)) 1549 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 1550 1551 // Special case logic when the operands have i1 type. 1552 if (OpTy->getScalarType()->isIntegerTy(1)) { 1553 switch (Pred) { 1554 default: break; 1555 case ICmpInst::ICMP_EQ: 1556 // X == 1 -> X 1557 if (match(RHS, m_One())) 1558 return LHS; 1559 break; 1560 case ICmpInst::ICMP_NE: 1561 // X != 0 -> X 1562 if (match(RHS, m_Zero())) 1563 return LHS; 1564 break; 1565 case ICmpInst::ICMP_UGT: 1566 // X >u 0 -> X 1567 if (match(RHS, m_Zero())) 1568 return LHS; 1569 break; 1570 case ICmpInst::ICMP_UGE: 1571 // X >=u 1 -> X 1572 if (match(RHS, m_One())) 1573 return LHS; 1574 break; 1575 case ICmpInst::ICMP_SLT: 1576 // X <s 0 -> X 1577 if (match(RHS, m_Zero())) 1578 return LHS; 1579 break; 1580 case ICmpInst::ICMP_SLE: 1581 // X <=s -1 -> X 1582 if (match(RHS, m_One())) 1583 return LHS; 1584 break; 1585 } 1586 } 1587 1588 // icmp <alloca*>, <global/alloca*/null> - Different stack variables have 1589 // different addresses, and what's more the address of a stack variable is 1590 // never null or equal to the address of a global. Note that generalizing 1591 // to the case where LHS is a global variable address or null is pointless, 1592 // since if both LHS and RHS are constants then we already constant folded 1593 // the compare, and if only one of them is then we moved it to RHS already. 1594 if (isa<AllocaInst>(LHS) && (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 1595 isa<ConstantPointerNull>(RHS))) 1596 // We already know that LHS != RHS. 1597 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 1598 1599 // If we are comparing with zero then try hard since this is a common case. 1600 if (match(RHS, m_Zero())) { 1601 bool LHSKnownNonNegative, LHSKnownNegative; 1602 switch (Pred) { 1603 default: 1604 assert(false && "Unknown ICmp predicate!"); 1605 case ICmpInst::ICMP_ULT: 1606 return getFalse(ITy); 1607 case ICmpInst::ICMP_UGE: 1608 return getTrue(ITy); 1609 case ICmpInst::ICMP_EQ: 1610 case ICmpInst::ICMP_ULE: 1611 if (isKnownNonZero(LHS, TD)) 1612 return getFalse(ITy); 1613 break; 1614 case ICmpInst::ICMP_NE: 1615 case ICmpInst::ICMP_UGT: 1616 if (isKnownNonZero(LHS, TD)) 1617 return getTrue(ITy); 1618 break; 1619 case ICmpInst::ICMP_SLT: 1620 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1621 if (LHSKnownNegative) 1622 return getTrue(ITy); 1623 if (LHSKnownNonNegative) 1624 return getFalse(ITy); 1625 break; 1626 case ICmpInst::ICMP_SLE: 1627 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1628 if (LHSKnownNegative) 1629 return getTrue(ITy); 1630 if (LHSKnownNonNegative && isKnownNonZero(LHS, TD)) 1631 return getFalse(ITy); 1632 break; 1633 case ICmpInst::ICMP_SGE: 1634 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1635 if (LHSKnownNegative) 1636 return getFalse(ITy); 1637 if (LHSKnownNonNegative) 1638 return getTrue(ITy); 1639 break; 1640 case ICmpInst::ICMP_SGT: 1641 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1642 if (LHSKnownNegative) 1643 return getFalse(ITy); 1644 if (LHSKnownNonNegative && isKnownNonZero(LHS, TD)) 1645 return getTrue(ITy); 1646 break; 1647 } 1648 } 1649 1650 // See if we are doing a comparison with a constant integer. 1651 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1652 // Rule out tautological comparisons (eg., ult 0 or uge 0). 1653 ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue()); 1654 if (RHS_CR.isEmptySet()) 1655 return ConstantInt::getFalse(CI->getContext()); 1656 if (RHS_CR.isFullSet()) 1657 return ConstantInt::getTrue(CI->getContext()); 1658 1659 // Many binary operators with constant RHS have easy to compute constant 1660 // range. Use them to check whether the comparison is a tautology. 1661 uint32_t Width = CI->getBitWidth(); 1662 APInt Lower = APInt(Width, 0); 1663 APInt Upper = APInt(Width, 0); 1664 ConstantInt *CI2; 1665 if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) { 1666 // 'urem x, CI2' produces [0, CI2). 1667 Upper = CI2->getValue(); 1668 } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) { 1669 // 'srem x, CI2' produces (-|CI2|, |CI2|). 1670 Upper = CI2->getValue().abs(); 1671 Lower = (-Upper) + 1; 1672 } else if (match(LHS, m_UDiv(m_ConstantInt(CI2), m_Value()))) { 1673 // 'udiv CI2, x' produces [0, CI2]. 1674 Upper = CI2->getValue() + 1; 1675 } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) { 1676 // 'udiv x, CI2' produces [0, UINT_MAX / CI2]. 1677 APInt NegOne = APInt::getAllOnesValue(Width); 1678 if (!CI2->isZero()) 1679 Upper = NegOne.udiv(CI2->getValue()) + 1; 1680 } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) { 1681 // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2]. 1682 APInt IntMin = APInt::getSignedMinValue(Width); 1683 APInt IntMax = APInt::getSignedMaxValue(Width); 1684 APInt Val = CI2->getValue().abs(); 1685 if (!Val.isMinValue()) { 1686 Lower = IntMin.sdiv(Val); 1687 Upper = IntMax.sdiv(Val) + 1; 1688 } 1689 } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) { 1690 // 'lshr x, CI2' produces [0, UINT_MAX >> CI2]. 1691 APInt NegOne = APInt::getAllOnesValue(Width); 1692 if (CI2->getValue().ult(Width)) 1693 Upper = NegOne.lshr(CI2->getValue()) + 1; 1694 } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) { 1695 // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2]. 1696 APInt IntMin = APInt::getSignedMinValue(Width); 1697 APInt IntMax = APInt::getSignedMaxValue(Width); 1698 if (CI2->getValue().ult(Width)) { 1699 Lower = IntMin.ashr(CI2->getValue()); 1700 Upper = IntMax.ashr(CI2->getValue()) + 1; 1701 } 1702 } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) { 1703 // 'or x, CI2' produces [CI2, UINT_MAX]. 1704 Lower = CI2->getValue(); 1705 } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) { 1706 // 'and x, CI2' produces [0, CI2]. 1707 Upper = CI2->getValue() + 1; 1708 } 1709 if (Lower != Upper) { 1710 ConstantRange LHS_CR = ConstantRange(Lower, Upper); 1711 if (RHS_CR.contains(LHS_CR)) 1712 return ConstantInt::getTrue(RHS->getContext()); 1713 if (RHS_CR.inverse().contains(LHS_CR)) 1714 return ConstantInt::getFalse(RHS->getContext()); 1715 } 1716 } 1717 1718 // Compare of cast, for example (zext X) != 0 -> X != 0 1719 if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) { 1720 Instruction *LI = cast<CastInst>(LHS); 1721 Value *SrcOp = LI->getOperand(0); 1722 Type *SrcTy = SrcOp->getType(); 1723 Type *DstTy = LI->getType(); 1724 1725 // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input 1726 // if the integer type is the same size as the pointer type. 1727 if (MaxRecurse && TD && isa<PtrToIntInst>(LI) && 1728 TD->getPointerSizeInBits() == DstTy->getPrimitiveSizeInBits()) { 1729 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 1730 // Transfer the cast to the constant. 1731 if (Value *V = SimplifyICmpInst(Pred, SrcOp, 1732 ConstantExpr::getIntToPtr(RHSC, SrcTy), 1733 TD, TLI, DT, MaxRecurse-1)) 1734 return V; 1735 } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) { 1736 if (RI->getOperand(0)->getType() == SrcTy) 1737 // Compare without the cast. 1738 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 1739 TD, TLI, DT, MaxRecurse-1)) 1740 return V; 1741 } 1742 } 1743 1744 if (isa<ZExtInst>(LHS)) { 1745 // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the 1746 // same type. 1747 if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) { 1748 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 1749 // Compare X and Y. Note that signed predicates become unsigned. 1750 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 1751 SrcOp, RI->getOperand(0), TD, TLI, DT, 1752 MaxRecurse-1)) 1753 return V; 1754 } 1755 // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended 1756 // too. If not, then try to deduce the result of the comparison. 1757 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1758 // Compute the constant that would happen if we truncated to SrcTy then 1759 // reextended to DstTy. 1760 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 1761 Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy); 1762 1763 // If the re-extended constant didn't change then this is effectively 1764 // also a case of comparing two zero-extended values. 1765 if (RExt == CI && MaxRecurse) 1766 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 1767 SrcOp, Trunc, TD, TLI, DT, MaxRecurse-1)) 1768 return V; 1769 1770 // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit 1771 // there. Use this to work out the result of the comparison. 1772 if (RExt != CI) { 1773 switch (Pred) { 1774 default: 1775 assert(false && "Unknown ICmp predicate!"); 1776 // LHS <u RHS. 1777 case ICmpInst::ICMP_EQ: 1778 case ICmpInst::ICMP_UGT: 1779 case ICmpInst::ICMP_UGE: 1780 return ConstantInt::getFalse(CI->getContext()); 1781 1782 case ICmpInst::ICMP_NE: 1783 case ICmpInst::ICMP_ULT: 1784 case ICmpInst::ICMP_ULE: 1785 return ConstantInt::getTrue(CI->getContext()); 1786 1787 // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS 1788 // is non-negative then LHS <s RHS. 1789 case ICmpInst::ICMP_SGT: 1790 case ICmpInst::ICMP_SGE: 1791 return CI->getValue().isNegative() ? 1792 ConstantInt::getTrue(CI->getContext()) : 1793 ConstantInt::getFalse(CI->getContext()); 1794 1795 case ICmpInst::ICMP_SLT: 1796 case ICmpInst::ICMP_SLE: 1797 return CI->getValue().isNegative() ? 1798 ConstantInt::getFalse(CI->getContext()) : 1799 ConstantInt::getTrue(CI->getContext()); 1800 } 1801 } 1802 } 1803 } 1804 1805 if (isa<SExtInst>(LHS)) { 1806 // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the 1807 // same type. 1808 if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) { 1809 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 1810 // Compare X and Y. Note that the predicate does not change. 1811 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 1812 TD, TLI, DT, MaxRecurse-1)) 1813 return V; 1814 } 1815 // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended 1816 // too. If not, then try to deduce the result of the comparison. 1817 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1818 // Compute the constant that would happen if we truncated to SrcTy then 1819 // reextended to DstTy. 1820 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 1821 Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy); 1822 1823 // If the re-extended constant didn't change then this is effectively 1824 // also a case of comparing two sign-extended values. 1825 if (RExt == CI && MaxRecurse) 1826 if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, TD, TLI, DT, 1827 MaxRecurse-1)) 1828 return V; 1829 1830 // Otherwise the upper bits of LHS are all equal, while RHS has varying 1831 // bits there. Use this to work out the result of the comparison. 1832 if (RExt != CI) { 1833 switch (Pred) { 1834 default: 1835 assert(false && "Unknown ICmp predicate!"); 1836 case ICmpInst::ICMP_EQ: 1837 return ConstantInt::getFalse(CI->getContext()); 1838 case ICmpInst::ICMP_NE: 1839 return ConstantInt::getTrue(CI->getContext()); 1840 1841 // If RHS is non-negative then LHS <s RHS. If RHS is negative then 1842 // LHS >s RHS. 1843 case ICmpInst::ICMP_SGT: 1844 case ICmpInst::ICMP_SGE: 1845 return CI->getValue().isNegative() ? 1846 ConstantInt::getTrue(CI->getContext()) : 1847 ConstantInt::getFalse(CI->getContext()); 1848 case ICmpInst::ICMP_SLT: 1849 case ICmpInst::ICMP_SLE: 1850 return CI->getValue().isNegative() ? 1851 ConstantInt::getFalse(CI->getContext()) : 1852 ConstantInt::getTrue(CI->getContext()); 1853 1854 // If LHS is non-negative then LHS <u RHS. If LHS is negative then 1855 // LHS >u RHS. 1856 case ICmpInst::ICMP_UGT: 1857 case ICmpInst::ICMP_UGE: 1858 // Comparison is true iff the LHS <s 0. 1859 if (MaxRecurse) 1860 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp, 1861 Constant::getNullValue(SrcTy), 1862 TD, TLI, DT, MaxRecurse-1)) 1863 return V; 1864 break; 1865 case ICmpInst::ICMP_ULT: 1866 case ICmpInst::ICMP_ULE: 1867 // Comparison is true iff the LHS >=s 0. 1868 if (MaxRecurse) 1869 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp, 1870 Constant::getNullValue(SrcTy), 1871 TD, TLI, DT, MaxRecurse-1)) 1872 return V; 1873 break; 1874 } 1875 } 1876 } 1877 } 1878 } 1879 1880 // Special logic for binary operators. 1881 BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS); 1882 BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS); 1883 if (MaxRecurse && (LBO || RBO)) { 1884 // Analyze the case when either LHS or RHS is an add instruction. 1885 Value *A = 0, *B = 0, *C = 0, *D = 0; 1886 // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null). 1887 bool NoLHSWrapProblem = false, NoRHSWrapProblem = false; 1888 if (LBO && LBO->getOpcode() == Instruction::Add) { 1889 A = LBO->getOperand(0); B = LBO->getOperand(1); 1890 NoLHSWrapProblem = ICmpInst::isEquality(Pred) || 1891 (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) || 1892 (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap()); 1893 } 1894 if (RBO && RBO->getOpcode() == Instruction::Add) { 1895 C = RBO->getOperand(0); D = RBO->getOperand(1); 1896 NoRHSWrapProblem = ICmpInst::isEquality(Pred) || 1897 (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) || 1898 (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap()); 1899 } 1900 1901 // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow. 1902 if ((A == RHS || B == RHS) && NoLHSWrapProblem) 1903 if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A, 1904 Constant::getNullValue(RHS->getType()), 1905 TD, TLI, DT, MaxRecurse-1)) 1906 return V; 1907 1908 // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow. 1909 if ((C == LHS || D == LHS) && NoRHSWrapProblem) 1910 if (Value *V = SimplifyICmpInst(Pred, 1911 Constant::getNullValue(LHS->getType()), 1912 C == LHS ? D : C, TD, TLI, DT, MaxRecurse-1)) 1913 return V; 1914 1915 // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow. 1916 if (A && C && (A == C || A == D || B == C || B == D) && 1917 NoLHSWrapProblem && NoRHSWrapProblem) { 1918 // Determine Y and Z in the form icmp (X+Y), (X+Z). 1919 Value *Y = (A == C || A == D) ? B : A; 1920 Value *Z = (C == A || C == B) ? D : C; 1921 if (Value *V = SimplifyICmpInst(Pred, Y, Z, TD, TLI, DT, MaxRecurse-1)) 1922 return V; 1923 } 1924 } 1925 1926 if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) { 1927 bool KnownNonNegative, KnownNegative; 1928 switch (Pred) { 1929 default: 1930 break; 1931 case ICmpInst::ICMP_SGT: 1932 case ICmpInst::ICMP_SGE: 1933 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, TD); 1934 if (!KnownNonNegative) 1935 break; 1936 // fall-through 1937 case ICmpInst::ICMP_EQ: 1938 case ICmpInst::ICMP_UGT: 1939 case ICmpInst::ICMP_UGE: 1940 return getFalse(ITy); 1941 case ICmpInst::ICMP_SLT: 1942 case ICmpInst::ICMP_SLE: 1943 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, TD); 1944 if (!KnownNonNegative) 1945 break; 1946 // fall-through 1947 case ICmpInst::ICMP_NE: 1948 case ICmpInst::ICMP_ULT: 1949 case ICmpInst::ICMP_ULE: 1950 return getTrue(ITy); 1951 } 1952 } 1953 if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) { 1954 bool KnownNonNegative, KnownNegative; 1955 switch (Pred) { 1956 default: 1957 break; 1958 case ICmpInst::ICMP_SGT: 1959 case ICmpInst::ICMP_SGE: 1960 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, TD); 1961 if (!KnownNonNegative) 1962 break; 1963 // fall-through 1964 case ICmpInst::ICMP_NE: 1965 case ICmpInst::ICMP_UGT: 1966 case ICmpInst::ICMP_UGE: 1967 return getTrue(ITy); 1968 case ICmpInst::ICMP_SLT: 1969 case ICmpInst::ICMP_SLE: 1970 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, TD); 1971 if (!KnownNonNegative) 1972 break; 1973 // fall-through 1974 case ICmpInst::ICMP_EQ: 1975 case ICmpInst::ICMP_ULT: 1976 case ICmpInst::ICMP_ULE: 1977 return getFalse(ITy); 1978 } 1979 } 1980 1981 // x udiv y <=u x. 1982 if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) { 1983 // icmp pred (X /u Y), X 1984 if (Pred == ICmpInst::ICMP_UGT) 1985 return getFalse(ITy); 1986 if (Pred == ICmpInst::ICMP_ULE) 1987 return getTrue(ITy); 1988 } 1989 1990 if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() && 1991 LBO->getOperand(1) == RBO->getOperand(1)) { 1992 switch (LBO->getOpcode()) { 1993 default: break; 1994 case Instruction::UDiv: 1995 case Instruction::LShr: 1996 if (ICmpInst::isSigned(Pred)) 1997 break; 1998 // fall-through 1999 case Instruction::SDiv: 2000 case Instruction::AShr: 2001 if (!LBO->isExact() || !RBO->isExact()) 2002 break; 2003 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2004 RBO->getOperand(0), TD, TLI, DT, MaxRecurse-1)) 2005 return V; 2006 break; 2007 case Instruction::Shl: { 2008 bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap(); 2009 bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap(); 2010 if (!NUW && !NSW) 2011 break; 2012 if (!NSW && ICmpInst::isSigned(Pred)) 2013 break; 2014 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2015 RBO->getOperand(0), TD, TLI, DT, MaxRecurse-1)) 2016 return V; 2017 break; 2018 } 2019 } 2020 } 2021 2022 // Simplify comparisons involving max/min. 2023 Value *A, *B; 2024 CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE; 2025 CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B". 2026 2027 // Signed variants on "max(a,b)>=a -> true". 2028 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2029 if (A != RHS) std::swap(A, B); // smax(A, B) pred A. 2030 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2031 // We analyze this as smax(A, B) pred A. 2032 P = Pred; 2033 } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) && 2034 (A == LHS || B == LHS)) { 2035 if (A != LHS) std::swap(A, B); // A pred smax(A, B). 2036 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2037 // We analyze this as smax(A, B) swapped-pred A. 2038 P = CmpInst::getSwappedPredicate(Pred); 2039 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2040 (A == RHS || B == RHS)) { 2041 if (A != RHS) std::swap(A, B); // smin(A, B) pred A. 2042 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2043 // We analyze this as smax(-A, -B) swapped-pred -A. 2044 // Note that we do not need to actually form -A or -B thanks to EqP. 2045 P = CmpInst::getSwappedPredicate(Pred); 2046 } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) && 2047 (A == LHS || B == LHS)) { 2048 if (A != LHS) std::swap(A, B); // A pred smin(A, B). 2049 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2050 // We analyze this as smax(-A, -B) pred -A. 2051 // Note that we do not need to actually form -A or -B thanks to EqP. 2052 P = Pred; 2053 } 2054 if (P != CmpInst::BAD_ICMP_PREDICATE) { 2055 // Cases correspond to "max(A, B) p A". 2056 switch (P) { 2057 default: 2058 break; 2059 case CmpInst::ICMP_EQ: 2060 case CmpInst::ICMP_SLE: 2061 // Equivalent to "A EqP B". This may be the same as the condition tested 2062 // in the max/min; if so, we can just return that. 2063 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2064 return V; 2065 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2066 return V; 2067 // Otherwise, see if "A EqP B" simplifies. 2068 if (MaxRecurse) 2069 if (Value *V = SimplifyICmpInst(EqP, A, B, TD, TLI, DT, MaxRecurse-1)) 2070 return V; 2071 break; 2072 case CmpInst::ICMP_NE: 2073 case CmpInst::ICMP_SGT: { 2074 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2075 // Equivalent to "A InvEqP B". This may be the same as the condition 2076 // tested in the max/min; if so, we can just return that. 2077 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2078 return V; 2079 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2080 return V; 2081 // Otherwise, see if "A InvEqP B" simplifies. 2082 if (MaxRecurse) 2083 if (Value *V = SimplifyICmpInst(InvEqP, A, B, TD, TLI, DT, MaxRecurse-1)) 2084 return V; 2085 break; 2086 } 2087 case CmpInst::ICMP_SGE: 2088 // Always true. 2089 return getTrue(ITy); 2090 case CmpInst::ICMP_SLT: 2091 // Always false. 2092 return getFalse(ITy); 2093 } 2094 } 2095 2096 // Unsigned variants on "max(a,b)>=a -> true". 2097 P = CmpInst::BAD_ICMP_PREDICATE; 2098 if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2099 if (A != RHS) std::swap(A, B); // umax(A, B) pred A. 2100 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2101 // We analyze this as umax(A, B) pred A. 2102 P = Pred; 2103 } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) && 2104 (A == LHS || B == LHS)) { 2105 if (A != LHS) std::swap(A, B); // A pred umax(A, B). 2106 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2107 // We analyze this as umax(A, B) swapped-pred A. 2108 P = CmpInst::getSwappedPredicate(Pred); 2109 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2110 (A == RHS || B == RHS)) { 2111 if (A != RHS) std::swap(A, B); // umin(A, B) pred A. 2112 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2113 // We analyze this as umax(-A, -B) swapped-pred -A. 2114 // Note that we do not need to actually form -A or -B thanks to EqP. 2115 P = CmpInst::getSwappedPredicate(Pred); 2116 } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) && 2117 (A == LHS || B == LHS)) { 2118 if (A != LHS) std::swap(A, B); // A pred umin(A, B). 2119 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2120 // We analyze this as umax(-A, -B) pred -A. 2121 // Note that we do not need to actually form -A or -B thanks to EqP. 2122 P = Pred; 2123 } 2124 if (P != CmpInst::BAD_ICMP_PREDICATE) { 2125 // Cases correspond to "max(A, B) p A". 2126 switch (P) { 2127 default: 2128 break; 2129 case CmpInst::ICMP_EQ: 2130 case CmpInst::ICMP_ULE: 2131 // Equivalent to "A EqP B". This may be the same as the condition tested 2132 // in the max/min; if so, we can just return that. 2133 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2134 return V; 2135 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2136 return V; 2137 // Otherwise, see if "A EqP B" simplifies. 2138 if (MaxRecurse) 2139 if (Value *V = SimplifyICmpInst(EqP, A, B, TD, TLI, DT, MaxRecurse-1)) 2140 return V; 2141 break; 2142 case CmpInst::ICMP_NE: 2143 case CmpInst::ICMP_UGT: { 2144 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2145 // Equivalent to "A InvEqP B". This may be the same as the condition 2146 // tested in the max/min; if so, we can just return that. 2147 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2148 return V; 2149 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2150 return V; 2151 // Otherwise, see if "A InvEqP B" simplifies. 2152 if (MaxRecurse) 2153 if (Value *V = SimplifyICmpInst(InvEqP, A, B, TD, TLI, DT, MaxRecurse-1)) 2154 return V; 2155 break; 2156 } 2157 case CmpInst::ICMP_UGE: 2158 // Always true. 2159 return getTrue(ITy); 2160 case CmpInst::ICMP_ULT: 2161 // Always false. 2162 return getFalse(ITy); 2163 } 2164 } 2165 2166 // Variants on "max(x,y) >= min(x,z)". 2167 Value *C, *D; 2168 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && 2169 match(RHS, m_SMin(m_Value(C), m_Value(D))) && 2170 (A == C || A == D || B == C || B == D)) { 2171 // max(x, ?) pred min(x, ?). 2172 if (Pred == CmpInst::ICMP_SGE) 2173 // Always true. 2174 return getTrue(ITy); 2175 if (Pred == CmpInst::ICMP_SLT) 2176 // Always false. 2177 return getFalse(ITy); 2178 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2179 match(RHS, m_SMax(m_Value(C), m_Value(D))) && 2180 (A == C || A == D || B == C || B == D)) { 2181 // min(x, ?) pred max(x, ?). 2182 if (Pred == CmpInst::ICMP_SLE) 2183 // Always true. 2184 return getTrue(ITy); 2185 if (Pred == CmpInst::ICMP_SGT) 2186 // Always false. 2187 return getFalse(ITy); 2188 } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && 2189 match(RHS, m_UMin(m_Value(C), m_Value(D))) && 2190 (A == C || A == D || B == C || B == D)) { 2191 // max(x, ?) pred min(x, ?). 2192 if (Pred == CmpInst::ICMP_UGE) 2193 // Always true. 2194 return getTrue(ITy); 2195 if (Pred == CmpInst::ICMP_ULT) 2196 // Always false. 2197 return getFalse(ITy); 2198 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2199 match(RHS, m_UMax(m_Value(C), m_Value(D))) && 2200 (A == C || A == D || B == C || B == D)) { 2201 // min(x, ?) pred max(x, ?). 2202 if (Pred == CmpInst::ICMP_ULE) 2203 // Always true. 2204 return getTrue(ITy); 2205 if (Pred == CmpInst::ICMP_UGT) 2206 // Always false. 2207 return getFalse(ITy); 2208 } 2209 2210 // If the comparison is with the result of a select instruction, check whether 2211 // comparing with either branch of the select always yields the same value. 2212 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 2213 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, TLI, DT, MaxRecurse)) 2214 return V; 2215 2216 // If the comparison is with the result of a phi instruction, check whether 2217 // doing the compare with each incoming phi value yields a common result. 2218 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 2219 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, TLI, DT, MaxRecurse)) 2220 return V; 2221 2222 return 0; 2223} 2224 2225Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2226 const TargetData *TD, 2227 const TargetLibraryInfo *TLI, 2228 const DominatorTree *DT) { 2229 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, TLI, DT, RecursionLimit); 2230} 2231 2232/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 2233/// fold the result. If not, this returns null. 2234static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2235 const TargetData *TD, 2236 const TargetLibraryInfo *TLI, 2237 const DominatorTree *DT, 2238 unsigned MaxRecurse) { 2239 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 2240 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 2241 2242 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 2243 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 2244 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD, TLI); 2245 2246 // If we have a constant, make sure it is on the RHS. 2247 std::swap(LHS, RHS); 2248 Pred = CmpInst::getSwappedPredicate(Pred); 2249 } 2250 2251 // Fold trivial predicates. 2252 if (Pred == FCmpInst::FCMP_FALSE) 2253 return ConstantInt::get(GetCompareTy(LHS), 0); 2254 if (Pred == FCmpInst::FCMP_TRUE) 2255 return ConstantInt::get(GetCompareTy(LHS), 1); 2256 2257 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 2258 return UndefValue::get(GetCompareTy(LHS)); 2259 2260 // fcmp x,x -> true/false. Not all compares are foldable. 2261 if (LHS == RHS) { 2262 if (CmpInst::isTrueWhenEqual(Pred)) 2263 return ConstantInt::get(GetCompareTy(LHS), 1); 2264 if (CmpInst::isFalseWhenEqual(Pred)) 2265 return ConstantInt::get(GetCompareTy(LHS), 0); 2266 } 2267 2268 // Handle fcmp with constant RHS 2269 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 2270 // If the constant is a nan, see if we can fold the comparison based on it. 2271 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 2272 if (CFP->getValueAPF().isNaN()) { 2273 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 2274 return ConstantInt::getFalse(CFP->getContext()); 2275 assert(FCmpInst::isUnordered(Pred) && 2276 "Comparison must be either ordered or unordered!"); 2277 // True if unordered. 2278 return ConstantInt::getTrue(CFP->getContext()); 2279 } 2280 // Check whether the constant is an infinity. 2281 if (CFP->getValueAPF().isInfinity()) { 2282 if (CFP->getValueAPF().isNegative()) { 2283 switch (Pred) { 2284 case FCmpInst::FCMP_OLT: 2285 // No value is ordered and less than negative infinity. 2286 return ConstantInt::getFalse(CFP->getContext()); 2287 case FCmpInst::FCMP_UGE: 2288 // All values are unordered with or at least negative infinity. 2289 return ConstantInt::getTrue(CFP->getContext()); 2290 default: 2291 break; 2292 } 2293 } else { 2294 switch (Pred) { 2295 case FCmpInst::FCMP_OGT: 2296 // No value is ordered and greater than infinity. 2297 return ConstantInt::getFalse(CFP->getContext()); 2298 case FCmpInst::FCMP_ULE: 2299 // All values are unordered with and at most infinity. 2300 return ConstantInt::getTrue(CFP->getContext()); 2301 default: 2302 break; 2303 } 2304 } 2305 } 2306 } 2307 } 2308 2309 // If the comparison is with the result of a select instruction, check whether 2310 // comparing with either branch of the select always yields the same value. 2311 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 2312 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, TLI, DT, MaxRecurse)) 2313 return V; 2314 2315 // If the comparison is with the result of a phi instruction, check whether 2316 // doing the compare with each incoming phi value yields a common result. 2317 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 2318 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, TLI, DT, MaxRecurse)) 2319 return V; 2320 2321 return 0; 2322} 2323 2324Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2325 const TargetData *TD, 2326 const TargetLibraryInfo *TLI, 2327 const DominatorTree *DT) { 2328 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, TLI, DT, RecursionLimit); 2329} 2330 2331/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 2332/// the result. If not, this returns null. 2333Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 2334 const TargetData *TD, const DominatorTree *) { 2335 // select true, X, Y -> X 2336 // select false, X, Y -> Y 2337 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 2338 return CB->getZExtValue() ? TrueVal : FalseVal; 2339 2340 // select C, X, X -> X 2341 if (TrueVal == FalseVal) 2342 return TrueVal; 2343 2344 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 2345 if (isa<Constant>(TrueVal)) 2346 return TrueVal; 2347 return FalseVal; 2348 } 2349 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 2350 return FalseVal; 2351 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 2352 return TrueVal; 2353 2354 return 0; 2355} 2356 2357/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 2358/// fold the result. If not, this returns null. 2359Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const TargetData *TD, 2360 const DominatorTree *) { 2361 // The type of the GEP pointer operand. 2362 PointerType *PtrTy = dyn_cast<PointerType>(Ops[0]->getType()); 2363 // The GEP pointer operand is not a pointer, it's a vector of pointers. 2364 if (!PtrTy) 2365 return 0; 2366 2367 // getelementptr P -> P. 2368 if (Ops.size() == 1) 2369 return Ops[0]; 2370 2371 if (isa<UndefValue>(Ops[0])) { 2372 // Compute the (pointer) type returned by the GEP instruction. 2373 Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, Ops.slice(1)); 2374 Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 2375 return UndefValue::get(GEPTy); 2376 } 2377 2378 if (Ops.size() == 2) { 2379 // getelementptr P, 0 -> P. 2380 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 2381 if (C->isZero()) 2382 return Ops[0]; 2383 // getelementptr P, N -> P if P points to a type of zero size. 2384 if (TD) { 2385 Type *Ty = PtrTy->getElementType(); 2386 if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0) 2387 return Ops[0]; 2388 } 2389 } 2390 2391 // Check to see if this is constant foldable. 2392 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 2393 if (!isa<Constant>(Ops[i])) 2394 return 0; 2395 2396 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), Ops.slice(1)); 2397} 2398 2399/// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we 2400/// can fold the result. If not, this returns null. 2401Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val, 2402 ArrayRef<unsigned> Idxs, 2403 const TargetData *, 2404 const DominatorTree *) { 2405 if (Constant *CAgg = dyn_cast<Constant>(Agg)) 2406 if (Constant *CVal = dyn_cast<Constant>(Val)) 2407 return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs); 2408 2409 // insertvalue x, undef, n -> x 2410 if (match(Val, m_Undef())) 2411 return Agg; 2412 2413 // insertvalue x, (extractvalue y, n), n 2414 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val)) 2415 if (EV->getAggregateOperand()->getType() == Agg->getType() && 2416 EV->getIndices() == Idxs) { 2417 // insertvalue undef, (extractvalue y, n), n -> y 2418 if (match(Agg, m_Undef())) 2419 return EV->getAggregateOperand(); 2420 2421 // insertvalue y, (extractvalue y, n), n -> y 2422 if (Agg == EV->getAggregateOperand()) 2423 return Agg; 2424 } 2425 2426 return 0; 2427} 2428 2429/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 2430static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 2431 // If all of the PHI's incoming values are the same then replace the PHI node 2432 // with the common value. 2433 Value *CommonValue = 0; 2434 bool HasUndefInput = false; 2435 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 2436 Value *Incoming = PN->getIncomingValue(i); 2437 // If the incoming value is the phi node itself, it can safely be skipped. 2438 if (Incoming == PN) continue; 2439 if (isa<UndefValue>(Incoming)) { 2440 // Remember that we saw an undef value, but otherwise ignore them. 2441 HasUndefInput = true; 2442 continue; 2443 } 2444 if (CommonValue && Incoming != CommonValue) 2445 return 0; // Not the same, bail out. 2446 CommonValue = Incoming; 2447 } 2448 2449 // If CommonValue is null then all of the incoming values were either undef or 2450 // equal to the phi node itself. 2451 if (!CommonValue) 2452 return UndefValue::get(PN->getType()); 2453 2454 // If we have a PHI node like phi(X, undef, X), where X is defined by some 2455 // instruction, we cannot return X as the result of the PHI node unless it 2456 // dominates the PHI block. 2457 if (HasUndefInput) 2458 return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 2459 2460 return CommonValue; 2461} 2462 2463//=== Helper functions for higher up the class hierarchy. 2464 2465/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 2466/// fold the result. If not, this returns null. 2467static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 2468 const TargetData *TD, 2469 const TargetLibraryInfo *TLI, 2470 const DominatorTree *DT, 2471 unsigned MaxRecurse) { 2472 switch (Opcode) { 2473 case Instruction::Add: 2474 return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 2475 TD, TLI, DT, MaxRecurse); 2476 case Instruction::Sub: 2477 return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 2478 TD, TLI, DT, MaxRecurse); 2479 case Instruction::Mul: return SimplifyMulInst (LHS, RHS, TD, TLI, DT, 2480 MaxRecurse); 2481 case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, TD, TLI, DT, 2482 MaxRecurse); 2483 case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, TD, TLI, DT, 2484 MaxRecurse); 2485 case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, TD, TLI, DT, 2486 MaxRecurse); 2487 case Instruction::SRem: return SimplifySRemInst(LHS, RHS, TD, TLI, DT, 2488 MaxRecurse); 2489 case Instruction::URem: return SimplifyURemInst(LHS, RHS, TD, TLI, DT, 2490 MaxRecurse); 2491 case Instruction::FRem: return SimplifyFRemInst(LHS, RHS, TD, TLI, DT, 2492 MaxRecurse); 2493 case Instruction::Shl: 2494 return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 2495 TD, TLI, DT, MaxRecurse); 2496 case Instruction::LShr: 2497 return SimplifyLShrInst(LHS, RHS, /*isExact*/false, TD, TLI, DT, 2498 MaxRecurse); 2499 case Instruction::AShr: 2500 return SimplifyAShrInst(LHS, RHS, /*isExact*/false, TD, TLI, DT, 2501 MaxRecurse); 2502 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, TLI, DT, 2503 MaxRecurse); 2504 case Instruction::Or: return SimplifyOrInst (LHS, RHS, TD, TLI, DT, 2505 MaxRecurse); 2506 case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, TLI, DT, 2507 MaxRecurse); 2508 default: 2509 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 2510 if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 2511 Constant *COps[] = {CLHS, CRHS}; 2512 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, TD, TLI); 2513 } 2514 2515 // If the operation is associative, try some generic simplifications. 2516 if (Instruction::isAssociative(Opcode)) 2517 if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, TLI, DT, 2518 MaxRecurse)) 2519 return V; 2520 2521 // If the operation is with the result of a select instruction, check whether 2522 // operating on either branch of the select always yields the same value. 2523 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 2524 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, TLI, DT, 2525 MaxRecurse)) 2526 return V; 2527 2528 // If the operation is with the result of a phi instruction, check whether 2529 // operating on all incoming values of the phi always yields the same value. 2530 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 2531 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, TLI, DT, 2532 MaxRecurse)) 2533 return V; 2534 2535 return 0; 2536 } 2537} 2538 2539Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 2540 const TargetData *TD, const TargetLibraryInfo *TLI, 2541 const DominatorTree *DT) { 2542 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, TLI, DT, RecursionLimit); 2543} 2544 2545/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 2546/// fold the result. 2547static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2548 const TargetData *TD, 2549 const TargetLibraryInfo *TLI, 2550 const DominatorTree *DT, 2551 unsigned MaxRecurse) { 2552 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 2553 return SimplifyICmpInst(Predicate, LHS, RHS, TD, TLI, DT, MaxRecurse); 2554 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, TLI, DT, MaxRecurse); 2555} 2556 2557Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2558 const TargetData *TD, const TargetLibraryInfo *TLI, 2559 const DominatorTree *DT) { 2560 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, TLI, DT, RecursionLimit); 2561} 2562 2563static Value *SimplifyCallInst(CallInst *CI) { 2564 // call undef -> undef 2565 if (isa<UndefValue>(CI->getCalledValue())) 2566 return UndefValue::get(CI->getType()); 2567 2568 return 0; 2569} 2570 2571/// SimplifyInstruction - See if we can compute a simplified version of this 2572/// instruction. If not, this returns null. 2573Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 2574 const TargetLibraryInfo *TLI, 2575 const DominatorTree *DT) { 2576 Value *Result; 2577 2578 switch (I->getOpcode()) { 2579 default: 2580 Result = ConstantFoldInstruction(I, TD, TLI); 2581 break; 2582 case Instruction::Add: 2583 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 2584 cast<BinaryOperator>(I)->hasNoSignedWrap(), 2585 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 2586 TD, TLI, DT); 2587 break; 2588 case Instruction::Sub: 2589 Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 2590 cast<BinaryOperator>(I)->hasNoSignedWrap(), 2591 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 2592 TD, TLI, DT); 2593 break; 2594 case Instruction::Mul: 2595 Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2596 break; 2597 case Instruction::SDiv: 2598 Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2599 break; 2600 case Instruction::UDiv: 2601 Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2602 break; 2603 case Instruction::FDiv: 2604 Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2605 break; 2606 case Instruction::SRem: 2607 Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2608 break; 2609 case Instruction::URem: 2610 Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2611 break; 2612 case Instruction::FRem: 2613 Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2614 break; 2615 case Instruction::Shl: 2616 Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), 2617 cast<BinaryOperator>(I)->hasNoSignedWrap(), 2618 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 2619 TD, TLI, DT); 2620 break; 2621 case Instruction::LShr: 2622 Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), 2623 cast<BinaryOperator>(I)->isExact(), 2624 TD, TLI, DT); 2625 break; 2626 case Instruction::AShr: 2627 Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), 2628 cast<BinaryOperator>(I)->isExact(), 2629 TD, TLI, DT); 2630 break; 2631 case Instruction::And: 2632 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2633 break; 2634 case Instruction::Or: 2635 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2636 break; 2637 case Instruction::Xor: 2638 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2639 break; 2640 case Instruction::ICmp: 2641 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 2642 I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2643 break; 2644 case Instruction::FCmp: 2645 Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 2646 I->getOperand(0), I->getOperand(1), TD, TLI, DT); 2647 break; 2648 case Instruction::Select: 2649 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 2650 I->getOperand(2), TD, DT); 2651 break; 2652 case Instruction::GetElementPtr: { 2653 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 2654 Result = SimplifyGEPInst(Ops, TD, DT); 2655 break; 2656 } 2657 case Instruction::InsertValue: { 2658 InsertValueInst *IV = cast<InsertValueInst>(I); 2659 Result = SimplifyInsertValueInst(IV->getAggregateOperand(), 2660 IV->getInsertedValueOperand(), 2661 IV->getIndices(), TD, DT); 2662 break; 2663 } 2664 case Instruction::PHI: 2665 Result = SimplifyPHINode(cast<PHINode>(I), DT); 2666 break; 2667 case Instruction::Call: 2668 Result = SimplifyCallInst(cast<CallInst>(I)); 2669 break; 2670 } 2671 2672 /// If called on unreachable code, the above logic may report that the 2673 /// instruction simplified to itself. Make life easier for users by 2674 /// detecting that case here, returning a safe value instead. 2675 return Result == I ? UndefValue::get(I->getType()) : Result; 2676} 2677 2678/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 2679/// delete the From instruction. In addition to a basic RAUW, this does a 2680/// recursive simplification of the newly formed instructions. This catches 2681/// things where one simplification exposes other opportunities. This only 2682/// simplifies and deletes scalar operations, it does not change the CFG. 2683/// 2684void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 2685 const TargetData *TD, 2686 const TargetLibraryInfo *TLI, 2687 const DominatorTree *DT) { 2688 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 2689 2690 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 2691 // we can know if it gets deleted out from under us or replaced in a 2692 // recursive simplification. 2693 WeakVH FromHandle(From); 2694 WeakVH ToHandle(To); 2695 2696 while (!From->use_empty()) { 2697 // Update the instruction to use the new value. 2698 Use &TheUse = From->use_begin().getUse(); 2699 Instruction *User = cast<Instruction>(TheUse.getUser()); 2700 TheUse = To; 2701 2702 // Check to see if the instruction can be folded due to the operand 2703 // replacement. For example changing (or X, Y) into (or X, -1) can replace 2704 // the 'or' with -1. 2705 Value *SimplifiedVal; 2706 { 2707 // Sanity check to make sure 'User' doesn't dangle across 2708 // SimplifyInstruction. 2709 AssertingVH<> UserHandle(User); 2710 2711 SimplifiedVal = SimplifyInstruction(User, TD, TLI, DT); 2712 if (SimplifiedVal == 0) continue; 2713 } 2714 2715 // Recursively simplify this user to the new value. 2716 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, TLI, DT); 2717 From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 2718 To = ToHandle; 2719 2720 assert(ToHandle && "To value deleted by recursive simplification?"); 2721 2722 // If the recursive simplification ended up revisiting and deleting 2723 // 'From' then we're done. 2724 if (From == 0) 2725 return; 2726 } 2727 2728 // If 'From' has value handles referring to it, do a real RAUW to update them. 2729 From->replaceAllUsesWith(To); 2730 2731 From->eraseFromParent(); 2732} 2733