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