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