InstructionSimplify.cpp revision 218893
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/ADT/Statistic.h" 22#include "llvm/Analysis/InstructionSimplify.h" 23#include "llvm/Analysis/ConstantFolding.h" 24#include "llvm/Analysis/Dominators.h" 25#include "llvm/Analysis/ValueTracking.h" 26#include "llvm/Support/PatternMatch.h" 27#include "llvm/Support/ValueHandle.h" 28#include "llvm/Target/TargetData.h" 29using namespace llvm; 30using namespace llvm::PatternMatch; 31 32enum { RecursionLimit = 3 }; 33 34STATISTIC(NumExpand, "Number of expansions"); 35STATISTIC(NumFactor , "Number of factorizations"); 36STATISTIC(NumReassoc, "Number of reassociations"); 37 38static Value *SimplifyAndInst(Value *, Value *, const TargetData *, 39 const DominatorTree *, unsigned); 40static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *, 41 const DominatorTree *, unsigned); 42static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *, 43 const DominatorTree *, unsigned); 44static Value *SimplifyOrInst(Value *, Value *, const TargetData *, 45 const DominatorTree *, unsigned); 46static Value *SimplifyXorInst(Value *, Value *, const TargetData *, 47 const DominatorTree *, unsigned); 48 49/// ValueDominatesPHI - Does the given value dominate the specified phi node? 50static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 51 Instruction *I = dyn_cast<Instruction>(V); 52 if (!I) 53 // Arguments and constants dominate all instructions. 54 return true; 55 56 // If we have a DominatorTree then do a precise test. 57 if (DT) 58 return DT->dominates(I, P); 59 60 // Otherwise, if the instruction is in the entry block, and is not an invoke, 61 // then it obviously dominates all phi nodes. 62 if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 63 !isa<InvokeInst>(I)) 64 return true; 65 66 return false; 67} 68 69/// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning 70/// it into "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is 71/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. 72/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". 73/// Returns the simplified value, or null if no simplification was performed. 74static Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS, 75 unsigned OpcToExpand, const TargetData *TD, 76 const DominatorTree *DT, unsigned MaxRecurse) { 77 Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand; 78 // Recursion is always used, so bail out at once if we already hit the limit. 79 if (!MaxRecurse--) 80 return 0; 81 82 // Check whether the expression has the form "(A op' B) op C". 83 if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) 84 if (Op0->getOpcode() == OpcodeToExpand) { 85 // It does! Try turning it into "(A op C) op' (B op C)". 86 Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 87 // Do "A op C" and "B op C" both simplify? 88 if (Value *L = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) 89 if (Value *R = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 90 // They do! Return "L op' R" if it simplifies or is already available. 91 // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. 92 if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand) 93 && L == B && R == A)) { 94 ++NumExpand; 95 return LHS; 96 } 97 // Otherwise return "L op' R" if it simplifies. 98 if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT, 99 MaxRecurse)) { 100 ++NumExpand; 101 return V; 102 } 103 } 104 } 105 106 // Check whether the expression has the form "A op (B op' C)". 107 if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS)) 108 if (Op1->getOpcode() == OpcodeToExpand) { 109 // It does! Try turning it into "(A op B) op' (A op C)". 110 Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 111 // Do "A op B" and "A op C" both simplify? 112 if (Value *L = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) 113 if (Value *R = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) { 114 // They do! Return "L op' R" if it simplifies or is already available. 115 // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. 116 if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand) 117 && L == C && R == B)) { 118 ++NumExpand; 119 return RHS; 120 } 121 // Otherwise return "L op' R" if it simplifies. 122 if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT, 123 MaxRecurse)) { 124 ++NumExpand; 125 return V; 126 } 127 } 128 } 129 130 return 0; 131} 132 133/// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term 134/// using the operation OpCodeToExtract. For example, when Opcode is Add and 135/// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)". 136/// Returns the simplified value, or null if no simplification was performed. 137static Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS, 138 unsigned OpcToExtract, const TargetData *TD, 139 const DominatorTree *DT, unsigned MaxRecurse) { 140 Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract; 141 // Recursion is always used, so bail out at once if we already hit the limit. 142 if (!MaxRecurse--) 143 return 0; 144 145 BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 146 BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 147 148 if (!Op0 || Op0->getOpcode() != OpcodeToExtract || 149 !Op1 || Op1->getOpcode() != OpcodeToExtract) 150 return 0; 151 152 // The expression has the form "(A op' B) op (C op' D)". 153 Value *A = Op0->getOperand(0), *B = Op0->getOperand(1); 154 Value *C = Op1->getOperand(0), *D = Op1->getOperand(1); 155 156 // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)". 157 // Does the instruction have the form "(A op' B) op (A op' D)" or, in the 158 // commutative case, "(A op' B) op (C op' A)"? 159 if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) { 160 Value *DD = A == C ? D : C; 161 // Form "A op' (B op DD)" if it simplifies completely. 162 // Does "B op DD" simplify? 163 if (Value *V = SimplifyBinOp(Opcode, B, DD, TD, DT, MaxRecurse)) { 164 // It does! Return "A op' V" if it simplifies or is already available. 165 // If V equals B then "A op' V" is just the LHS. If V equals DD then 166 // "A op' V" is just the RHS. 167 if (V == B || V == DD) { 168 ++NumFactor; 169 return V == B ? LHS : RHS; 170 } 171 // Otherwise return "A op' V" if it simplifies. 172 if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, TD, DT, MaxRecurse)) { 173 ++NumFactor; 174 return W; 175 } 176 } 177 } 178 179 // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)". 180 // Does the instruction have the form "(A op' B) op (C op' B)" or, in the 181 // commutative case, "(A op' B) op (B op' D)"? 182 if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) { 183 Value *CC = B == D ? C : D; 184 // Form "(A op CC) op' B" if it simplifies completely.. 185 // Does "A op CC" simplify? 186 if (Value *V = SimplifyBinOp(Opcode, A, CC, TD, DT, MaxRecurse)) { 187 // It does! Return "V op' B" if it simplifies or is already available. 188 // If V equals A then "V op' B" is just the LHS. If V equals CC then 189 // "V op' B" is just the RHS. 190 if (V == A || V == CC) { 191 ++NumFactor; 192 return V == A ? LHS : RHS; 193 } 194 // Otherwise return "V op' B" if it simplifies. 195 if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, TD, DT, MaxRecurse)) { 196 ++NumFactor; 197 return W; 198 } 199 } 200 } 201 202 return 0; 203} 204 205/// SimplifyAssociativeBinOp - Generic simplifications for associative binary 206/// operations. Returns the simpler value, or null if none was found. 207static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, 208 const TargetData *TD, 209 const DominatorTree *DT, 210 unsigned MaxRecurse) { 211 Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc; 212 assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 213 214 // Recursion is always used, so bail out at once if we already hit the limit. 215 if (!MaxRecurse--) 216 return 0; 217 218 BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 219 BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 220 221 // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 222 if (Op0 && Op0->getOpcode() == Opcode) { 223 Value *A = Op0->getOperand(0); 224 Value *B = Op0->getOperand(1); 225 Value *C = RHS; 226 227 // Does "B op C" simplify? 228 if (Value *V = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 229 // It does! Return "A op V" if it simplifies or is already available. 230 // If V equals B then "A op V" is just the LHS. 231 if (V == B) return LHS; 232 // Otherwise return "A op V" if it simplifies. 233 if (Value *W = SimplifyBinOp(Opcode, A, V, TD, DT, MaxRecurse)) { 234 ++NumReassoc; 235 return W; 236 } 237 } 238 } 239 240 // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 241 if (Op1 && Op1->getOpcode() == Opcode) { 242 Value *A = LHS; 243 Value *B = Op1->getOperand(0); 244 Value *C = Op1->getOperand(1); 245 246 // Does "A op B" simplify? 247 if (Value *V = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) { 248 // It does! Return "V op C" if it simplifies or is already available. 249 // If V equals B then "V op C" is just the RHS. 250 if (V == B) return RHS; 251 // Otherwise return "V op C" if it simplifies. 252 if (Value *W = SimplifyBinOp(Opcode, V, C, TD, DT, MaxRecurse)) { 253 ++NumReassoc; 254 return W; 255 } 256 } 257 } 258 259 // The remaining transforms require commutativity as well as associativity. 260 if (!Instruction::isCommutative(Opcode)) 261 return 0; 262 263 // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 264 if (Op0 && Op0->getOpcode() == Opcode) { 265 Value *A = Op0->getOperand(0); 266 Value *B = Op0->getOperand(1); 267 Value *C = RHS; 268 269 // Does "C op A" simplify? 270 if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 271 // It does! Return "V op B" if it simplifies or is already available. 272 // If V equals A then "V op B" is just the LHS. 273 if (V == A) return LHS; 274 // Otherwise return "V op B" if it simplifies. 275 if (Value *W = SimplifyBinOp(Opcode, V, B, TD, DT, MaxRecurse)) { 276 ++NumReassoc; 277 return W; 278 } 279 } 280 } 281 282 // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 283 if (Op1 && Op1->getOpcode() == Opcode) { 284 Value *A = LHS; 285 Value *B = Op1->getOperand(0); 286 Value *C = Op1->getOperand(1); 287 288 // Does "C op A" simplify? 289 if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 290 // It does! Return "B op V" if it simplifies or is already available. 291 // If V equals C then "B op V" is just the RHS. 292 if (V == C) return RHS; 293 // Otherwise return "B op V" if it simplifies. 294 if (Value *W = SimplifyBinOp(Opcode, B, V, TD, DT, MaxRecurse)) { 295 ++NumReassoc; 296 return W; 297 } 298 } 299 } 300 301 return 0; 302} 303 304/// ThreadBinOpOverSelect - In the case of a binary operation with a select 305/// instruction as an operand, try to simplify the binop by seeing whether 306/// evaluating it on both branches of the select results in the same value. 307/// Returns the common value if so, otherwise returns null. 308static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 309 const TargetData *TD, 310 const DominatorTree *DT, 311 unsigned MaxRecurse) { 312 // Recursion is always used, so bail out at once if we already hit the limit. 313 if (!MaxRecurse--) 314 return 0; 315 316 SelectInst *SI; 317 if (isa<SelectInst>(LHS)) { 318 SI = cast<SelectInst>(LHS); 319 } else { 320 assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 321 SI = cast<SelectInst>(RHS); 322 } 323 324 // Evaluate the BinOp on the true and false branches of the select. 325 Value *TV; 326 Value *FV; 327 if (SI == LHS) { 328 TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse); 329 FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse); 330 } else { 331 TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse); 332 FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse); 333 } 334 335 // If they simplified to the same value, then return the common value. 336 // If they both failed to simplify then return null. 337 if (TV == FV) 338 return TV; 339 340 // If one branch simplified to undef, return the other one. 341 if (TV && isa<UndefValue>(TV)) 342 return FV; 343 if (FV && isa<UndefValue>(FV)) 344 return TV; 345 346 // If applying the operation did not change the true and false select values, 347 // then the result of the binop is the select itself. 348 if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 349 return SI; 350 351 // If one branch simplified and the other did not, and the simplified 352 // value is equal to the unsimplified one, return the simplified value. 353 // For example, select (cond, X, X & Z) & Z -> X & Z. 354 if ((FV && !TV) || (TV && !FV)) { 355 // Check that the simplified value has the form "X op Y" where "op" is the 356 // same as the original operation. 357 Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 358 if (Simplified && Simplified->getOpcode() == Opcode) { 359 // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 360 // We already know that "op" is the same as for the simplified value. See 361 // if the operands match too. If so, return the simplified value. 362 Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 363 Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 364 Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 365 if (Simplified->getOperand(0) == UnsimplifiedLHS && 366 Simplified->getOperand(1) == UnsimplifiedRHS) 367 return Simplified; 368 if (Simplified->isCommutative() && 369 Simplified->getOperand(1) == UnsimplifiedLHS && 370 Simplified->getOperand(0) == UnsimplifiedRHS) 371 return Simplified; 372 } 373 } 374 375 return 0; 376} 377 378/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 379/// try to simplify the comparison by seeing whether both branches of the select 380/// result in the same value. Returns the common value if so, otherwise returns 381/// null. 382static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 383 Value *RHS, const TargetData *TD, 384 const DominatorTree *DT, 385 unsigned MaxRecurse) { 386 // Recursion is always used, so bail out at once if we already hit the limit. 387 if (!MaxRecurse--) 388 return 0; 389 390 // Make sure the select is on the LHS. 391 if (!isa<SelectInst>(LHS)) { 392 std::swap(LHS, RHS); 393 Pred = CmpInst::getSwappedPredicate(Pred); 394 } 395 assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 396 SelectInst *SI = cast<SelectInst>(LHS); 397 398 // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it. 399 // Does "cmp TV, RHS" simplify? 400 if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT, 401 MaxRecurse)) { 402 // It does! Does "cmp FV, RHS" simplify? 403 if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT, 404 MaxRecurse)) { 405 // It does! If they simplified to the same value, then use it as the 406 // result of the original comparison. 407 if (TCmp == FCmp) 408 return TCmp; 409 Value *Cond = SI->getCondition(); 410 // If the false value simplified to false, then the result of the compare 411 // is equal to "Cond && TCmp". This also catches the case when the false 412 // value simplified to false and the true value to true, returning "Cond". 413 if (match(FCmp, m_Zero())) 414 if (Value *V = SimplifyAndInst(Cond, TCmp, TD, DT, MaxRecurse)) 415 return V; 416 // If the true value simplified to true, then the result of the compare 417 // is equal to "Cond || FCmp". 418 if (match(TCmp, m_One())) 419 if (Value *V = SimplifyOrInst(Cond, FCmp, TD, DT, MaxRecurse)) 420 return V; 421 // Finally, if the false value simplified to true and the true value to 422 // false, then the result of the compare is equal to "!Cond". 423 if (match(FCmp, m_One()) && match(TCmp, m_Zero())) 424 if (Value *V = 425 SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()), 426 TD, DT, MaxRecurse)) 427 return V; 428 } 429 } 430 431 return 0; 432} 433 434/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 435/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 436/// it on the incoming phi values yields the same result for every value. If so 437/// returns the common value, otherwise returns null. 438static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 439 const TargetData *TD, const DominatorTree *DT, 440 unsigned MaxRecurse) { 441 // Recursion is always used, so bail out at once if we already hit the limit. 442 if (!MaxRecurse--) 443 return 0; 444 445 PHINode *PI; 446 if (isa<PHINode>(LHS)) { 447 PI = cast<PHINode>(LHS); 448 // Bail out if RHS and the phi may be mutually interdependent due to a loop. 449 if (!ValueDominatesPHI(RHS, PI, DT)) 450 return 0; 451 } else { 452 assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 453 PI = cast<PHINode>(RHS); 454 // Bail out if LHS and the phi may be mutually interdependent due to a loop. 455 if (!ValueDominatesPHI(LHS, PI, DT)) 456 return 0; 457 } 458 459 // Evaluate the BinOp on the incoming phi values. 460 Value *CommonValue = 0; 461 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 462 Value *Incoming = PI->getIncomingValue(i); 463 // If the incoming value is the phi node itself, it can safely be skipped. 464 if (Incoming == PI) continue; 465 Value *V = PI == LHS ? 466 SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) : 467 SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse); 468 // If the operation failed to simplify, or simplified to a different value 469 // to previously, then give up. 470 if (!V || (CommonValue && V != CommonValue)) 471 return 0; 472 CommonValue = V; 473 } 474 475 return CommonValue; 476} 477 478/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 479/// try to simplify the comparison by seeing whether comparing with all of the 480/// incoming phi values yields the same result every time. If so returns the 481/// common result, otherwise returns null. 482static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 483 const TargetData *TD, const DominatorTree *DT, 484 unsigned MaxRecurse) { 485 // Recursion is always used, so bail out at once if we already hit the limit. 486 if (!MaxRecurse--) 487 return 0; 488 489 // Make sure the phi is on the LHS. 490 if (!isa<PHINode>(LHS)) { 491 std::swap(LHS, RHS); 492 Pred = CmpInst::getSwappedPredicate(Pred); 493 } 494 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 495 PHINode *PI = cast<PHINode>(LHS); 496 497 // Bail out if RHS and the phi may be mutually interdependent due to a loop. 498 if (!ValueDominatesPHI(RHS, PI, DT)) 499 return 0; 500 501 // Evaluate the BinOp on the incoming phi values. 502 Value *CommonValue = 0; 503 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 504 Value *Incoming = PI->getIncomingValue(i); 505 // If the incoming value is the phi node itself, it can safely be skipped. 506 if (Incoming == PI) continue; 507 Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse); 508 // If the operation failed to simplify, or simplified to a different value 509 // to previously, then give up. 510 if (!V || (CommonValue && V != CommonValue)) 511 return 0; 512 CommonValue = V; 513 } 514 515 return CommonValue; 516} 517 518/// SimplifyAddInst - Given operands for an Add, see if we can 519/// fold the result. If not, this returns null. 520static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 521 const TargetData *TD, const DominatorTree *DT, 522 unsigned MaxRecurse) { 523 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 524 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 525 Constant *Ops[] = { CLHS, CRHS }; 526 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 527 Ops, 2, TD); 528 } 529 530 // Canonicalize the constant to the RHS. 531 std::swap(Op0, Op1); 532 } 533 534 // X + undef -> undef 535 if (match(Op1, m_Undef())) 536 return Op1; 537 538 // X + 0 -> X 539 if (match(Op1, m_Zero())) 540 return Op0; 541 542 // X + (Y - X) -> Y 543 // (Y - X) + X -> Y 544 // Eg: X + -X -> 0 545 Value *Y = 0; 546 if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 547 match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 548 return Y; 549 550 // X + ~X -> -1 since ~X = -X-1 551 if (match(Op0, m_Not(m_Specific(Op1))) || 552 match(Op1, m_Not(m_Specific(Op0)))) 553 return Constant::getAllOnesValue(Op0->getType()); 554 555 /// i1 add -> xor. 556 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 557 if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 558 return V; 559 560 // Try some generic simplifications for associative operations. 561 if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT, 562 MaxRecurse)) 563 return V; 564 565 // Mul distributes over Add. Try some generic simplifications based on this. 566 if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul, 567 TD, DT, MaxRecurse)) 568 return V; 569 570 // Threading Add over selects and phi nodes is pointless, so don't bother. 571 // Threading over the select in "A + select(cond, B, C)" means evaluating 572 // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 573 // only if B and C are equal. If B and C are equal then (since we assume 574 // that operands have already been simplified) "select(cond, B, C)" should 575 // have been simplified to the common value of B and C already. Analysing 576 // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 577 // for threading over phi nodes. 578 579 return 0; 580} 581 582Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 583 const TargetData *TD, const DominatorTree *DT) { 584 return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 585} 586 587/// SimplifySubInst - Given operands for a Sub, see if we can 588/// fold the result. If not, this returns null. 589static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 590 const TargetData *TD, const DominatorTree *DT, 591 unsigned MaxRecurse) { 592 if (Constant *CLHS = dyn_cast<Constant>(Op0)) 593 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 594 Constant *Ops[] = { CLHS, CRHS }; 595 return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 596 Ops, 2, TD); 597 } 598 599 // X - undef -> undef 600 // undef - X -> undef 601 if (match(Op0, m_Undef()) || match(Op1, m_Undef())) 602 return UndefValue::get(Op0->getType()); 603 604 // X - 0 -> X 605 if (match(Op1, m_Zero())) 606 return Op0; 607 608 // X - X -> 0 609 if (Op0 == Op1) 610 return Constant::getNullValue(Op0->getType()); 611 612 // (X*2) - X -> X 613 // (X<<1) - X -> X 614 Value *X = 0; 615 if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) || 616 match(Op0, m_Shl(m_Specific(Op1), m_One()))) 617 return Op1; 618 619 // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. 620 // For example, (X + Y) - Y -> X; (Y + X) - Y -> X 621 Value *Y = 0, *Z = Op1; 622 if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z 623 // See if "V === Y - Z" simplifies. 624 if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, TD, DT, MaxRecurse-1)) 625 // It does! Now see if "X + V" simplifies. 626 if (Value *W = SimplifyBinOp(Instruction::Add, X, V, TD, DT, 627 MaxRecurse-1)) { 628 // It does, we successfully reassociated! 629 ++NumReassoc; 630 return W; 631 } 632 // See if "V === X - Z" simplifies. 633 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, DT, MaxRecurse-1)) 634 // It does! Now see if "Y + V" simplifies. 635 if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, TD, DT, 636 MaxRecurse-1)) { 637 // It does, we successfully reassociated! 638 ++NumReassoc; 639 return W; 640 } 641 } 642 643 // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies. 644 // For example, X - (X + 1) -> -1 645 X = Op0; 646 if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z) 647 // See if "V === X - Y" simplifies. 648 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, TD, DT, MaxRecurse-1)) 649 // It does! Now see if "V - Z" simplifies. 650 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, TD, DT, 651 MaxRecurse-1)) { 652 // It does, we successfully reassociated! 653 ++NumReassoc; 654 return W; 655 } 656 // See if "V === X - Z" simplifies. 657 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, DT, MaxRecurse-1)) 658 // It does! Now see if "V - Y" simplifies. 659 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, TD, DT, 660 MaxRecurse-1)) { 661 // It does, we successfully reassociated! 662 ++NumReassoc; 663 return W; 664 } 665 } 666 667 // Z - (X - Y) -> (Z - X) + Y if everything simplifies. 668 // For example, X - (X - Y) -> Y. 669 Z = Op0; 670 if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y) 671 // See if "V === Z - X" simplifies. 672 if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, TD, DT, MaxRecurse-1)) 673 // It does! Now see if "V + Y" simplifies. 674 if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, TD, DT, 675 MaxRecurse-1)) { 676 // It does, we successfully reassociated! 677 ++NumReassoc; 678 return W; 679 } 680 681 // Mul distributes over Sub. Try some generic simplifications based on this. 682 if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul, 683 TD, DT, MaxRecurse)) 684 return V; 685 686 // i1 sub -> xor. 687 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 688 if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 689 return V; 690 691 // Threading Sub over selects and phi nodes is pointless, so don't bother. 692 // Threading over the select in "A - select(cond, B, C)" means evaluating 693 // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 694 // only if B and C are equal. If B and C are equal then (since we assume 695 // that operands have already been simplified) "select(cond, B, C)" should 696 // have been simplified to the common value of B and C already. Analysing 697 // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 698 // for threading over phi nodes. 699 700 return 0; 701} 702 703Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 704 const TargetData *TD, const DominatorTree *DT) { 705 return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 706} 707 708/// SimplifyMulInst - Given operands for a Mul, see if we can 709/// fold the result. If not, this returns null. 710static Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 711 const DominatorTree *DT, unsigned MaxRecurse) { 712 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 713 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 714 Constant *Ops[] = { CLHS, CRHS }; 715 return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 716 Ops, 2, TD); 717 } 718 719 // Canonicalize the constant to the RHS. 720 std::swap(Op0, Op1); 721 } 722 723 // X * undef -> 0 724 if (match(Op1, m_Undef())) 725 return Constant::getNullValue(Op0->getType()); 726 727 // X * 0 -> 0 728 if (match(Op1, m_Zero())) 729 return Op1; 730 731 // X * 1 -> X 732 if (match(Op1, m_One())) 733 return Op0; 734 735 // (X / Y) * Y -> X if the division is exact. 736 Value *X = 0, *Y = 0; 737 if ((match(Op0, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op1) || // (X / Y) * Y 738 (match(Op1, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op0)) { // Y * (X / Y) 739 BinaryOperator *Div = cast<BinaryOperator>(Y == Op1 ? Op0 : Op1); 740 if (Div->isExact()) 741 return X; 742 } 743 744 // i1 mul -> and. 745 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 746 if (Value *V = SimplifyAndInst(Op0, Op1, TD, DT, MaxRecurse-1)) 747 return V; 748 749 // Try some generic simplifications for associative operations. 750 if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, DT, 751 MaxRecurse)) 752 return V; 753 754 // Mul distributes over Add. Try some generic simplifications based on this. 755 if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 756 TD, DT, MaxRecurse)) 757 return V; 758 759 // If the operation is with the result of a select instruction, check whether 760 // operating on either branch of the select always yields the same value. 761 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 762 if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, DT, 763 MaxRecurse)) 764 return V; 765 766 // If the operation is with the result of a phi instruction, check whether 767 // operating on all incoming values of the phi always yields the same value. 768 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 769 if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, DT, 770 MaxRecurse)) 771 return V; 772 773 return 0; 774} 775 776Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 777 const DominatorTree *DT) { 778 return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit); 779} 780 781/// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can 782/// fold the result. If not, this returns null. 783static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 784 const TargetData *TD, const DominatorTree *DT, 785 unsigned MaxRecurse) { 786 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 787 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 788 Constant *Ops[] = { C0, C1 }; 789 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, 2, TD); 790 } 791 } 792 793 bool isSigned = Opcode == Instruction::SDiv; 794 795 // X / undef -> undef 796 if (match(Op1, m_Undef())) 797 return Op1; 798 799 // undef / X -> 0 800 if (match(Op0, m_Undef())) 801 return Constant::getNullValue(Op0->getType()); 802 803 // 0 / X -> 0, we don't need to preserve faults! 804 if (match(Op0, m_Zero())) 805 return Op0; 806 807 // X / 1 -> X 808 if (match(Op1, m_One())) 809 return Op0; 810 811 if (Op0->getType()->isIntegerTy(1)) 812 // It can't be division by zero, hence it must be division by one. 813 return Op0; 814 815 // X / X -> 1 816 if (Op0 == Op1) 817 return ConstantInt::get(Op0->getType(), 1); 818 819 // (X * Y) / Y -> X if the multiplication does not overflow. 820 Value *X = 0, *Y = 0; 821 if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { 822 if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 823 BinaryOperator *Mul = cast<BinaryOperator>(Op0); 824 // If the Mul knows it does not overflow, then we are good to go. 825 if ((isSigned && Mul->hasNoSignedWrap()) || 826 (!isSigned && Mul->hasNoUnsignedWrap())) 827 return X; 828 // If X has the form X = A / Y then X * Y cannot overflow. 829 if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X)) 830 if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) 831 return X; 832 } 833 834 // (X rem Y) / Y -> 0 835 if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 836 (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 837 return Constant::getNullValue(Op0->getType()); 838 839 // If the operation is with the result of a select instruction, check whether 840 // operating on either branch of the select always yields the same value. 841 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 842 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 843 return V; 844 845 // If the operation is with the result of a phi instruction, check whether 846 // operating on all incoming values of the phi always yields the same value. 847 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 848 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 849 return V; 850 851 return 0; 852} 853 854/// SimplifySDivInst - Given operands for an SDiv, see if we can 855/// fold the result. If not, this returns null. 856static Value *SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, 857 const DominatorTree *DT, unsigned MaxRecurse) { 858 if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, TD, DT, MaxRecurse)) 859 return V; 860 861 return 0; 862} 863 864Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, 865 const DominatorTree *DT) { 866 return ::SimplifySDivInst(Op0, Op1, TD, DT, RecursionLimit); 867} 868 869/// SimplifyUDivInst - Given operands for a UDiv, see if we can 870/// fold the result. If not, this returns null. 871static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, 872 const DominatorTree *DT, unsigned MaxRecurse) { 873 if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, TD, DT, MaxRecurse)) 874 return V; 875 876 return 0; 877} 878 879Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, 880 const DominatorTree *DT) { 881 return ::SimplifyUDivInst(Op0, Op1, TD, DT, RecursionLimit); 882} 883 884static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *, 885 const DominatorTree *, unsigned) { 886 // undef / X -> undef (the undef could be a snan). 887 if (match(Op0, m_Undef())) 888 return Op0; 889 890 // X / undef -> undef 891 if (match(Op1, m_Undef())) 892 return Op1; 893 894 return 0; 895} 896 897Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *TD, 898 const DominatorTree *DT) { 899 return ::SimplifyFDivInst(Op0, Op1, TD, DT, RecursionLimit); 900} 901 902/// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can 903/// fold the result. If not, this returns null. 904static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, 905 const TargetData *TD, const DominatorTree *DT, 906 unsigned MaxRecurse) { 907 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 908 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 909 Constant *Ops[] = { C0, C1 }; 910 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, 2, TD); 911 } 912 } 913 914 // 0 shift by X -> 0 915 if (match(Op0, m_Zero())) 916 return Op0; 917 918 // X shift by 0 -> X 919 if (match(Op1, m_Zero())) 920 return Op0; 921 922 // X shift by undef -> undef because it may shift by the bitwidth. 923 if (match(Op1, m_Undef())) 924 return Op1; 925 926 // Shifting by the bitwidth or more is undefined. 927 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) 928 if (CI->getValue().getLimitedValue() >= 929 Op0->getType()->getScalarSizeInBits()) 930 return UndefValue::get(Op0->getType()); 931 932 // If the operation is with the result of a select instruction, check whether 933 // operating on either branch of the select always yields the same value. 934 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 935 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 936 return V; 937 938 // If the operation is with the result of a phi instruction, check whether 939 // operating on all incoming values of the phi always yields the same value. 940 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 941 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 942 return V; 943 944 return 0; 945} 946 947/// SimplifyShlInst - Given operands for an Shl, see if we can 948/// fold the result. If not, this returns null. 949static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 950 const TargetData *TD, const DominatorTree *DT, 951 unsigned MaxRecurse) { 952 if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, TD, DT, MaxRecurse)) 953 return V; 954 955 // undef << X -> 0 956 if (match(Op0, m_Undef())) 957 return Constant::getNullValue(Op0->getType()); 958 959 // (X >> A) << A -> X 960 Value *X; 961 if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1))) && 962 cast<PossiblyExactOperator>(Op0)->isExact()) 963 return X; 964 return 0; 965} 966 967Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 968 const TargetData *TD, const DominatorTree *DT) { 969 return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 970} 971 972/// SimplifyLShrInst - Given operands for an LShr, see if we can 973/// fold the result. If not, this returns null. 974static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 975 const TargetData *TD, const DominatorTree *DT, 976 unsigned MaxRecurse) { 977 if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, TD, DT, MaxRecurse)) 978 return V; 979 980 // undef >>l X -> 0 981 if (match(Op0, m_Undef())) 982 return Constant::getNullValue(Op0->getType()); 983 984 // (X << A) >> A -> X 985 Value *X; 986 if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) && 987 cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap()) 988 return X; 989 990 return 0; 991} 992 993Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 994 const TargetData *TD, const DominatorTree *DT) { 995 return ::SimplifyLShrInst(Op0, Op1, isExact, TD, DT, RecursionLimit); 996} 997 998/// SimplifyAShrInst - Given operands for an AShr, see if we can 999/// fold the result. If not, this returns null. 1000static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1001 const TargetData *TD, const DominatorTree *DT, 1002 unsigned MaxRecurse) { 1003 if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, TD, DT, MaxRecurse)) 1004 return V; 1005 1006 // all ones >>a X -> all ones 1007 if (match(Op0, m_AllOnes())) 1008 return Op0; 1009 1010 // undef >>a X -> all ones 1011 if (match(Op0, m_Undef())) 1012 return Constant::getAllOnesValue(Op0->getType()); 1013 1014 // (X << A) >> A -> X 1015 Value *X; 1016 if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) && 1017 cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap()) 1018 return X; 1019 1020 return 0; 1021} 1022 1023Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1024 const TargetData *TD, const DominatorTree *DT) { 1025 return ::SimplifyAShrInst(Op0, Op1, isExact, TD, DT, RecursionLimit); 1026} 1027 1028/// SimplifyAndInst - Given operands for an And, see if we can 1029/// fold the result. If not, this returns null. 1030static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 1031 const DominatorTree *DT, unsigned MaxRecurse) { 1032 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1033 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1034 Constant *Ops[] = { CLHS, CRHS }; 1035 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 1036 Ops, 2, TD); 1037 } 1038 1039 // Canonicalize the constant to the RHS. 1040 std::swap(Op0, Op1); 1041 } 1042 1043 // X & undef -> 0 1044 if (match(Op1, m_Undef())) 1045 return Constant::getNullValue(Op0->getType()); 1046 1047 // X & X = X 1048 if (Op0 == Op1) 1049 return Op0; 1050 1051 // X & 0 = 0 1052 if (match(Op1, m_Zero())) 1053 return Op1; 1054 1055 // X & -1 = X 1056 if (match(Op1, m_AllOnes())) 1057 return Op0; 1058 1059 // A & ~A = ~A & A = 0 1060 if (match(Op0, m_Not(m_Specific(Op1))) || 1061 match(Op1, m_Not(m_Specific(Op0)))) 1062 return Constant::getNullValue(Op0->getType()); 1063 1064 // (A | ?) & A = A 1065 Value *A = 0, *B = 0; 1066 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1067 (A == Op1 || B == Op1)) 1068 return Op1; 1069 1070 // A & (A | ?) = A 1071 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1072 (A == Op0 || B == Op0)) 1073 return Op0; 1074 1075 // Try some generic simplifications for associative operations. 1076 if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT, 1077 MaxRecurse)) 1078 return V; 1079 1080 // And distributes over Or. Try some generic simplifications based on this. 1081 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1082 TD, DT, MaxRecurse)) 1083 return V; 1084 1085 // And distributes over Xor. Try some generic simplifications based on this. 1086 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 1087 TD, DT, MaxRecurse)) 1088 return V; 1089 1090 // Or distributes over And. Try some generic simplifications based on this. 1091 if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1092 TD, DT, MaxRecurse)) 1093 return V; 1094 1095 // If the operation is with the result of a select instruction, check whether 1096 // operating on either branch of the select always yields the same value. 1097 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1098 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT, 1099 MaxRecurse)) 1100 return V; 1101 1102 // If the operation is with the result of a phi instruction, check whether 1103 // operating on all incoming values of the phi always yields the same value. 1104 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1105 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT, 1106 MaxRecurse)) 1107 return V; 1108 1109 return 0; 1110} 1111 1112Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 1113 const DominatorTree *DT) { 1114 return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit); 1115} 1116 1117/// SimplifyOrInst - Given operands for an Or, see if we can 1118/// fold the result. If not, this returns null. 1119static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 1120 const DominatorTree *DT, unsigned MaxRecurse) { 1121 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1122 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1123 Constant *Ops[] = { CLHS, CRHS }; 1124 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 1125 Ops, 2, TD); 1126 } 1127 1128 // Canonicalize the constant to the RHS. 1129 std::swap(Op0, Op1); 1130 } 1131 1132 // X | undef -> -1 1133 if (match(Op1, m_Undef())) 1134 return Constant::getAllOnesValue(Op0->getType()); 1135 1136 // X | X = X 1137 if (Op0 == Op1) 1138 return Op0; 1139 1140 // X | 0 = X 1141 if (match(Op1, m_Zero())) 1142 return Op0; 1143 1144 // X | -1 = -1 1145 if (match(Op1, m_AllOnes())) 1146 return Op1; 1147 1148 // A | ~A = ~A | A = -1 1149 if (match(Op0, m_Not(m_Specific(Op1))) || 1150 match(Op1, m_Not(m_Specific(Op0)))) 1151 return Constant::getAllOnesValue(Op0->getType()); 1152 1153 // (A & ?) | A = A 1154 Value *A = 0, *B = 0; 1155 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 1156 (A == Op1 || B == Op1)) 1157 return Op1; 1158 1159 // A | (A & ?) = A 1160 if (match(Op1, m_And(m_Value(A), m_Value(B))) && 1161 (A == Op0 || B == Op0)) 1162 return Op0; 1163 1164 // Try some generic simplifications for associative operations. 1165 if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT, 1166 MaxRecurse)) 1167 return V; 1168 1169 // Or distributes over And. Try some generic simplifications based on this. 1170 if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, 1171 TD, DT, MaxRecurse)) 1172 return V; 1173 1174 // And distributes over Or. Try some generic simplifications based on this. 1175 if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And, 1176 TD, DT, MaxRecurse)) 1177 return V; 1178 1179 // If the operation is with the result of a select instruction, check whether 1180 // operating on either branch of the select always yields the same value. 1181 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1182 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT, 1183 MaxRecurse)) 1184 return V; 1185 1186 // If the operation is with the result of a phi instruction, check whether 1187 // operating on all incoming values of the phi always yields the same value. 1188 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1189 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT, 1190 MaxRecurse)) 1191 return V; 1192 1193 return 0; 1194} 1195 1196Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 1197 const DominatorTree *DT) { 1198 return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit); 1199} 1200 1201/// SimplifyXorInst - Given operands for a Xor, see if we can 1202/// fold the result. If not, this returns null. 1203static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 1204 const DominatorTree *DT, unsigned MaxRecurse) { 1205 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1206 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1207 Constant *Ops[] = { CLHS, CRHS }; 1208 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 1209 Ops, 2, TD); 1210 } 1211 1212 // Canonicalize the constant to the RHS. 1213 std::swap(Op0, Op1); 1214 } 1215 1216 // A ^ undef -> undef 1217 if (match(Op1, m_Undef())) 1218 return Op1; 1219 1220 // A ^ 0 = A 1221 if (match(Op1, m_Zero())) 1222 return Op0; 1223 1224 // A ^ A = 0 1225 if (Op0 == Op1) 1226 return Constant::getNullValue(Op0->getType()); 1227 1228 // A ^ ~A = ~A ^ A = -1 1229 if (match(Op0, m_Not(m_Specific(Op1))) || 1230 match(Op1, m_Not(m_Specific(Op0)))) 1231 return Constant::getAllOnesValue(Op0->getType()); 1232 1233 // Try some generic simplifications for associative operations. 1234 if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT, 1235 MaxRecurse)) 1236 return V; 1237 1238 // And distributes over Xor. Try some generic simplifications based on this. 1239 if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And, 1240 TD, DT, MaxRecurse)) 1241 return V; 1242 1243 // Threading Xor over selects and phi nodes is pointless, so don't bother. 1244 // Threading over the select in "A ^ select(cond, B, C)" means evaluating 1245 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 1246 // only if B and C are equal. If B and C are equal then (since we assume 1247 // that operands have already been simplified) "select(cond, B, C)" should 1248 // have been simplified to the common value of B and C already. Analysing 1249 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 1250 // for threading over phi nodes. 1251 1252 return 0; 1253} 1254 1255Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 1256 const DominatorTree *DT) { 1257 return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit); 1258} 1259 1260static const Type *GetCompareTy(Value *Op) { 1261 return CmpInst::makeCmpResultType(Op->getType()); 1262} 1263 1264/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 1265/// fold the result. If not, this returns null. 1266static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1267 const TargetData *TD, const DominatorTree *DT, 1268 unsigned MaxRecurse) { 1269 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 1270 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 1271 1272 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 1273 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1274 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 1275 1276 // If we have a constant, make sure it is on the RHS. 1277 std::swap(LHS, RHS); 1278 Pred = CmpInst::getSwappedPredicate(Pred); 1279 } 1280 1281 const Type *ITy = GetCompareTy(LHS); // The return type. 1282 const Type *OpTy = LHS->getType(); // The operand type. 1283 1284 // icmp X, X -> true/false 1285 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 1286 // because X could be 0. 1287 if (LHS == RHS || isa<UndefValue>(RHS)) 1288 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 1289 1290 // Special case logic when the operands have i1 type. 1291 if (OpTy->isIntegerTy(1) || (OpTy->isVectorTy() && 1292 cast<VectorType>(OpTy)->getElementType()->isIntegerTy(1))) { 1293 switch (Pred) { 1294 default: break; 1295 case ICmpInst::ICMP_EQ: 1296 // X == 1 -> X 1297 if (match(RHS, m_One())) 1298 return LHS; 1299 break; 1300 case ICmpInst::ICMP_NE: 1301 // X != 0 -> X 1302 if (match(RHS, m_Zero())) 1303 return LHS; 1304 break; 1305 case ICmpInst::ICMP_UGT: 1306 // X >u 0 -> X 1307 if (match(RHS, m_Zero())) 1308 return LHS; 1309 break; 1310 case ICmpInst::ICMP_UGE: 1311 // X >=u 1 -> X 1312 if (match(RHS, m_One())) 1313 return LHS; 1314 break; 1315 case ICmpInst::ICMP_SLT: 1316 // X <s 0 -> X 1317 if (match(RHS, m_Zero())) 1318 return LHS; 1319 break; 1320 case ICmpInst::ICMP_SLE: 1321 // X <=s -1 -> X 1322 if (match(RHS, m_One())) 1323 return LHS; 1324 break; 1325 } 1326 } 1327 1328 // icmp <alloca*>, <global/alloca*/null> - Different stack variables have 1329 // different addresses, and what's more the address of a stack variable is 1330 // never null or equal to the address of a global. Note that generalizing 1331 // to the case where LHS is a global variable address or null is pointless, 1332 // since if both LHS and RHS are constants then we already constant folded 1333 // the compare, and if only one of them is then we moved it to RHS already. 1334 if (isa<AllocaInst>(LHS) && (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 1335 isa<ConstantPointerNull>(RHS))) 1336 // We already know that LHS != LHS. 1337 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 1338 1339 // If we are comparing with zero then try hard since this is a common case. 1340 if (match(RHS, m_Zero())) { 1341 bool LHSKnownNonNegative, LHSKnownNegative; 1342 switch (Pred) { 1343 default: 1344 assert(false && "Unknown ICmp predicate!"); 1345 case ICmpInst::ICMP_ULT: 1346 return ConstantInt::getFalse(LHS->getContext()); 1347 case ICmpInst::ICMP_UGE: 1348 return ConstantInt::getTrue(LHS->getContext()); 1349 case ICmpInst::ICMP_EQ: 1350 case ICmpInst::ICMP_ULE: 1351 if (isKnownNonZero(LHS, TD)) 1352 return ConstantInt::getFalse(LHS->getContext()); 1353 break; 1354 case ICmpInst::ICMP_NE: 1355 case ICmpInst::ICMP_UGT: 1356 if (isKnownNonZero(LHS, TD)) 1357 return ConstantInt::getTrue(LHS->getContext()); 1358 break; 1359 case ICmpInst::ICMP_SLT: 1360 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1361 if (LHSKnownNegative) 1362 return ConstantInt::getTrue(LHS->getContext()); 1363 if (LHSKnownNonNegative) 1364 return ConstantInt::getFalse(LHS->getContext()); 1365 break; 1366 case ICmpInst::ICMP_SLE: 1367 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1368 if (LHSKnownNegative) 1369 return ConstantInt::getTrue(LHS->getContext()); 1370 if (LHSKnownNonNegative && isKnownNonZero(LHS, TD)) 1371 return ConstantInt::getFalse(LHS->getContext()); 1372 break; 1373 case ICmpInst::ICMP_SGE: 1374 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1375 if (LHSKnownNegative) 1376 return ConstantInt::getFalse(LHS->getContext()); 1377 if (LHSKnownNonNegative) 1378 return ConstantInt::getTrue(LHS->getContext()); 1379 break; 1380 case ICmpInst::ICMP_SGT: 1381 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1382 if (LHSKnownNegative) 1383 return ConstantInt::getFalse(LHS->getContext()); 1384 if (LHSKnownNonNegative && isKnownNonZero(LHS, TD)) 1385 return ConstantInt::getTrue(LHS->getContext()); 1386 break; 1387 } 1388 } 1389 1390 // See if we are doing a comparison with a constant integer. 1391 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1392 switch (Pred) { 1393 default: break; 1394 case ICmpInst::ICMP_UGT: 1395 if (CI->isMaxValue(false)) // A >u MAX -> FALSE 1396 return ConstantInt::getFalse(CI->getContext()); 1397 break; 1398 case ICmpInst::ICMP_UGE: 1399 if (CI->isMinValue(false)) // A >=u MIN -> TRUE 1400 return ConstantInt::getTrue(CI->getContext()); 1401 break; 1402 case ICmpInst::ICMP_ULT: 1403 if (CI->isMinValue(false)) // A <u MIN -> FALSE 1404 return ConstantInt::getFalse(CI->getContext()); 1405 break; 1406 case ICmpInst::ICMP_ULE: 1407 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 1408 return ConstantInt::getTrue(CI->getContext()); 1409 break; 1410 case ICmpInst::ICMP_SGT: 1411 if (CI->isMaxValue(true)) // A >s MAX -> FALSE 1412 return ConstantInt::getFalse(CI->getContext()); 1413 break; 1414 case ICmpInst::ICMP_SGE: 1415 if (CI->isMinValue(true)) // A >=s MIN -> TRUE 1416 return ConstantInt::getTrue(CI->getContext()); 1417 break; 1418 case ICmpInst::ICMP_SLT: 1419 if (CI->isMinValue(true)) // A <s MIN -> FALSE 1420 return ConstantInt::getFalse(CI->getContext()); 1421 break; 1422 case ICmpInst::ICMP_SLE: 1423 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 1424 return ConstantInt::getTrue(CI->getContext()); 1425 break; 1426 } 1427 } 1428 1429 // Compare of cast, for example (zext X) != 0 -> X != 0 1430 if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) { 1431 Instruction *LI = cast<CastInst>(LHS); 1432 Value *SrcOp = LI->getOperand(0); 1433 const Type *SrcTy = SrcOp->getType(); 1434 const Type *DstTy = LI->getType(); 1435 1436 // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input 1437 // if the integer type is the same size as the pointer type. 1438 if (MaxRecurse && TD && isa<PtrToIntInst>(LI) && 1439 TD->getPointerSizeInBits() == DstTy->getPrimitiveSizeInBits()) { 1440 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 1441 // Transfer the cast to the constant. 1442 if (Value *V = SimplifyICmpInst(Pred, SrcOp, 1443 ConstantExpr::getIntToPtr(RHSC, SrcTy), 1444 TD, DT, MaxRecurse-1)) 1445 return V; 1446 } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) { 1447 if (RI->getOperand(0)->getType() == SrcTy) 1448 // Compare without the cast. 1449 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 1450 TD, DT, MaxRecurse-1)) 1451 return V; 1452 } 1453 } 1454 1455 if (isa<ZExtInst>(LHS)) { 1456 // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the 1457 // same type. 1458 if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) { 1459 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 1460 // Compare X and Y. Note that signed predicates become unsigned. 1461 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 1462 SrcOp, RI->getOperand(0), TD, DT, 1463 MaxRecurse-1)) 1464 return V; 1465 } 1466 // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended 1467 // too. If not, then try to deduce the result of the comparison. 1468 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1469 // Compute the constant that would happen if we truncated to SrcTy then 1470 // reextended to DstTy. 1471 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 1472 Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy); 1473 1474 // If the re-extended constant didn't change then this is effectively 1475 // also a case of comparing two zero-extended values. 1476 if (RExt == CI && MaxRecurse) 1477 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 1478 SrcOp, Trunc, TD, DT, MaxRecurse-1)) 1479 return V; 1480 1481 // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit 1482 // there. Use this to work out the result of the comparison. 1483 if (RExt != CI) { 1484 switch (Pred) { 1485 default: 1486 assert(false && "Unknown ICmp predicate!"); 1487 // LHS <u RHS. 1488 case ICmpInst::ICMP_EQ: 1489 case ICmpInst::ICMP_UGT: 1490 case ICmpInst::ICMP_UGE: 1491 return ConstantInt::getFalse(CI->getContext()); 1492 1493 case ICmpInst::ICMP_NE: 1494 case ICmpInst::ICMP_ULT: 1495 case ICmpInst::ICMP_ULE: 1496 return ConstantInt::getTrue(CI->getContext()); 1497 1498 // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS 1499 // is non-negative then LHS <s RHS. 1500 case ICmpInst::ICMP_SGT: 1501 case ICmpInst::ICMP_SGE: 1502 return CI->getValue().isNegative() ? 1503 ConstantInt::getTrue(CI->getContext()) : 1504 ConstantInt::getFalse(CI->getContext()); 1505 1506 case ICmpInst::ICMP_SLT: 1507 case ICmpInst::ICMP_SLE: 1508 return CI->getValue().isNegative() ? 1509 ConstantInt::getFalse(CI->getContext()) : 1510 ConstantInt::getTrue(CI->getContext()); 1511 } 1512 } 1513 } 1514 } 1515 1516 if (isa<SExtInst>(LHS)) { 1517 // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the 1518 // same type. 1519 if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) { 1520 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 1521 // Compare X and Y. Note that the predicate does not change. 1522 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 1523 TD, DT, MaxRecurse-1)) 1524 return V; 1525 } 1526 // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended 1527 // too. If not, then try to deduce the result of the comparison. 1528 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1529 // Compute the constant that would happen if we truncated to SrcTy then 1530 // reextended to DstTy. 1531 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 1532 Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy); 1533 1534 // If the re-extended constant didn't change then this is effectively 1535 // also a case of comparing two sign-extended values. 1536 if (RExt == CI && MaxRecurse) 1537 if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, TD, DT, 1538 MaxRecurse-1)) 1539 return V; 1540 1541 // Otherwise the upper bits of LHS are all equal, while RHS has varying 1542 // bits there. Use this to work out the result of the comparison. 1543 if (RExt != CI) { 1544 switch (Pred) { 1545 default: 1546 assert(false && "Unknown ICmp predicate!"); 1547 case ICmpInst::ICMP_EQ: 1548 return ConstantInt::getFalse(CI->getContext()); 1549 case ICmpInst::ICMP_NE: 1550 return ConstantInt::getTrue(CI->getContext()); 1551 1552 // If RHS is non-negative then LHS <s RHS. If RHS is negative then 1553 // LHS >s RHS. 1554 case ICmpInst::ICMP_SGT: 1555 case ICmpInst::ICMP_SGE: 1556 return CI->getValue().isNegative() ? 1557 ConstantInt::getTrue(CI->getContext()) : 1558 ConstantInt::getFalse(CI->getContext()); 1559 case ICmpInst::ICMP_SLT: 1560 case ICmpInst::ICMP_SLE: 1561 return CI->getValue().isNegative() ? 1562 ConstantInt::getFalse(CI->getContext()) : 1563 ConstantInt::getTrue(CI->getContext()); 1564 1565 // If LHS is non-negative then LHS <u RHS. If LHS is negative then 1566 // LHS >u RHS. 1567 case ICmpInst::ICMP_UGT: 1568 case ICmpInst::ICMP_UGE: 1569 // Comparison is true iff the LHS <s 0. 1570 if (MaxRecurse) 1571 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp, 1572 Constant::getNullValue(SrcTy), 1573 TD, DT, MaxRecurse-1)) 1574 return V; 1575 break; 1576 case ICmpInst::ICMP_ULT: 1577 case ICmpInst::ICMP_ULE: 1578 // Comparison is true iff the LHS >=s 0. 1579 if (MaxRecurse) 1580 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp, 1581 Constant::getNullValue(SrcTy), 1582 TD, DT, MaxRecurse-1)) 1583 return V; 1584 break; 1585 } 1586 } 1587 } 1588 } 1589 } 1590 1591 // Special logic for binary operators. 1592 BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS); 1593 BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS); 1594 if (MaxRecurse && (LBO || RBO)) { 1595 // Analyze the case when either LHS or RHS is an add instruction. 1596 Value *A = 0, *B = 0, *C = 0, *D = 0; 1597 // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null). 1598 bool NoLHSWrapProblem = false, NoRHSWrapProblem = false; 1599 if (LBO && LBO->getOpcode() == Instruction::Add) { 1600 A = LBO->getOperand(0); B = LBO->getOperand(1); 1601 NoLHSWrapProblem = ICmpInst::isEquality(Pred) || 1602 (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) || 1603 (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap()); 1604 } 1605 if (RBO && RBO->getOpcode() == Instruction::Add) { 1606 C = RBO->getOperand(0); D = RBO->getOperand(1); 1607 NoRHSWrapProblem = ICmpInst::isEquality(Pred) || 1608 (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) || 1609 (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap()); 1610 } 1611 1612 // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow. 1613 if ((A == RHS || B == RHS) && NoLHSWrapProblem) 1614 if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A, 1615 Constant::getNullValue(RHS->getType()), 1616 TD, DT, MaxRecurse-1)) 1617 return V; 1618 1619 // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow. 1620 if ((C == LHS || D == LHS) && NoRHSWrapProblem) 1621 if (Value *V = SimplifyICmpInst(Pred, 1622 Constant::getNullValue(LHS->getType()), 1623 C == LHS ? D : C, TD, DT, MaxRecurse-1)) 1624 return V; 1625 1626 // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow. 1627 if (A && C && (A == C || A == D || B == C || B == D) && 1628 NoLHSWrapProblem && NoRHSWrapProblem) { 1629 // Determine Y and Z in the form icmp (X+Y), (X+Z). 1630 Value *Y = (A == C || A == D) ? B : A; 1631 Value *Z = (C == A || C == B) ? D : C; 1632 if (Value *V = SimplifyICmpInst(Pred, Y, Z, TD, DT, MaxRecurse-1)) 1633 return V; 1634 } 1635 } 1636 1637 // If the comparison is with the result of a select instruction, check whether 1638 // comparing with either branch of the select always yields the same value. 1639 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 1640 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1641 return V; 1642 1643 // If the comparison is with the result of a phi instruction, check whether 1644 // doing the compare with each incoming phi value yields a common result. 1645 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 1646 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1647 return V; 1648 1649 return 0; 1650} 1651 1652Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1653 const TargetData *TD, const DominatorTree *DT) { 1654 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1655} 1656 1657/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 1658/// fold the result. If not, this returns null. 1659static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1660 const TargetData *TD, const DominatorTree *DT, 1661 unsigned MaxRecurse) { 1662 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 1663 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 1664 1665 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 1666 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1667 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 1668 1669 // If we have a constant, make sure it is on the RHS. 1670 std::swap(LHS, RHS); 1671 Pred = CmpInst::getSwappedPredicate(Pred); 1672 } 1673 1674 // Fold trivial predicates. 1675 if (Pred == FCmpInst::FCMP_FALSE) 1676 return ConstantInt::get(GetCompareTy(LHS), 0); 1677 if (Pred == FCmpInst::FCMP_TRUE) 1678 return ConstantInt::get(GetCompareTy(LHS), 1); 1679 1680 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 1681 return UndefValue::get(GetCompareTy(LHS)); 1682 1683 // fcmp x,x -> true/false. Not all compares are foldable. 1684 if (LHS == RHS) { 1685 if (CmpInst::isTrueWhenEqual(Pred)) 1686 return ConstantInt::get(GetCompareTy(LHS), 1); 1687 if (CmpInst::isFalseWhenEqual(Pred)) 1688 return ConstantInt::get(GetCompareTy(LHS), 0); 1689 } 1690 1691 // Handle fcmp with constant RHS 1692 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 1693 // If the constant is a nan, see if we can fold the comparison based on it. 1694 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 1695 if (CFP->getValueAPF().isNaN()) { 1696 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 1697 return ConstantInt::getFalse(CFP->getContext()); 1698 assert(FCmpInst::isUnordered(Pred) && 1699 "Comparison must be either ordered or unordered!"); 1700 // True if unordered. 1701 return ConstantInt::getTrue(CFP->getContext()); 1702 } 1703 // Check whether the constant is an infinity. 1704 if (CFP->getValueAPF().isInfinity()) { 1705 if (CFP->getValueAPF().isNegative()) { 1706 switch (Pred) { 1707 case FCmpInst::FCMP_OLT: 1708 // No value is ordered and less than negative infinity. 1709 return ConstantInt::getFalse(CFP->getContext()); 1710 case FCmpInst::FCMP_UGE: 1711 // All values are unordered with or at least negative infinity. 1712 return ConstantInt::getTrue(CFP->getContext()); 1713 default: 1714 break; 1715 } 1716 } else { 1717 switch (Pred) { 1718 case FCmpInst::FCMP_OGT: 1719 // No value is ordered and greater than infinity. 1720 return ConstantInt::getFalse(CFP->getContext()); 1721 case FCmpInst::FCMP_ULE: 1722 // All values are unordered with and at most infinity. 1723 return ConstantInt::getTrue(CFP->getContext()); 1724 default: 1725 break; 1726 } 1727 } 1728 } 1729 } 1730 } 1731 1732 // If the comparison is with the result of a select instruction, check whether 1733 // comparing with either branch of the select always yields the same value. 1734 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 1735 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1736 return V; 1737 1738 // If the comparison is with the result of a phi instruction, check whether 1739 // doing the compare with each incoming phi value yields a common result. 1740 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 1741 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1742 return V; 1743 1744 return 0; 1745} 1746 1747Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1748 const TargetData *TD, const DominatorTree *DT) { 1749 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1750} 1751 1752/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 1753/// the result. If not, this returns null. 1754Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 1755 const TargetData *TD, const DominatorTree *) { 1756 // select true, X, Y -> X 1757 // select false, X, Y -> Y 1758 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 1759 return CB->getZExtValue() ? TrueVal : FalseVal; 1760 1761 // select C, X, X -> X 1762 if (TrueVal == FalseVal) 1763 return TrueVal; 1764 1765 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 1766 return FalseVal; 1767 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 1768 return TrueVal; 1769 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 1770 if (isa<Constant>(TrueVal)) 1771 return TrueVal; 1772 return FalseVal; 1773 } 1774 1775 return 0; 1776} 1777 1778/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 1779/// fold the result. If not, this returns null. 1780Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 1781 const TargetData *TD, const DominatorTree *) { 1782 // The type of the GEP pointer operand. 1783 const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()); 1784 1785 // getelementptr P -> P. 1786 if (NumOps == 1) 1787 return Ops[0]; 1788 1789 if (isa<UndefValue>(Ops[0])) { 1790 // Compute the (pointer) type returned by the GEP instruction. 1791 const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1], 1792 NumOps-1); 1793 const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 1794 return UndefValue::get(GEPTy); 1795 } 1796 1797 if (NumOps == 2) { 1798 // getelementptr P, 0 -> P. 1799 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 1800 if (C->isZero()) 1801 return Ops[0]; 1802 // getelementptr P, N -> P if P points to a type of zero size. 1803 if (TD) { 1804 const Type *Ty = PtrTy->getElementType(); 1805 if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0) 1806 return Ops[0]; 1807 } 1808 } 1809 1810 // Check to see if this is constant foldable. 1811 for (unsigned i = 0; i != NumOps; ++i) 1812 if (!isa<Constant>(Ops[i])) 1813 return 0; 1814 1815 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 1816 (Constant *const*)Ops+1, NumOps-1); 1817} 1818 1819/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 1820static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 1821 // If all of the PHI's incoming values are the same then replace the PHI node 1822 // with the common value. 1823 Value *CommonValue = 0; 1824 bool HasUndefInput = false; 1825 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1826 Value *Incoming = PN->getIncomingValue(i); 1827 // If the incoming value is the phi node itself, it can safely be skipped. 1828 if (Incoming == PN) continue; 1829 if (isa<UndefValue>(Incoming)) { 1830 // Remember that we saw an undef value, but otherwise ignore them. 1831 HasUndefInput = true; 1832 continue; 1833 } 1834 if (CommonValue && Incoming != CommonValue) 1835 return 0; // Not the same, bail out. 1836 CommonValue = Incoming; 1837 } 1838 1839 // If CommonValue is null then all of the incoming values were either undef or 1840 // equal to the phi node itself. 1841 if (!CommonValue) 1842 return UndefValue::get(PN->getType()); 1843 1844 // If we have a PHI node like phi(X, undef, X), where X is defined by some 1845 // instruction, we cannot return X as the result of the PHI node unless it 1846 // dominates the PHI block. 1847 if (HasUndefInput) 1848 return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 1849 1850 return CommonValue; 1851} 1852 1853 1854//=== Helper functions for higher up the class hierarchy. 1855 1856/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 1857/// fold the result. If not, this returns null. 1858static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 1859 const TargetData *TD, const DominatorTree *DT, 1860 unsigned MaxRecurse) { 1861 switch (Opcode) { 1862 case Instruction::Add: 1863 return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 1864 TD, DT, MaxRecurse); 1865 case Instruction::Sub: 1866 return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 1867 TD, DT, MaxRecurse); 1868 case Instruction::Mul: return SimplifyMulInst (LHS, RHS, TD, DT, MaxRecurse); 1869 case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, TD, DT, MaxRecurse); 1870 case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, TD, DT, MaxRecurse); 1871 case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, TD, DT, MaxRecurse); 1872 case Instruction::Shl: 1873 return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 1874 TD, DT, MaxRecurse); 1875 case Instruction::LShr: 1876 return SimplifyLShrInst(LHS, RHS, /*isExact*/false, TD, DT, MaxRecurse); 1877 case Instruction::AShr: 1878 return SimplifyAShrInst(LHS, RHS, /*isExact*/false, TD, DT, MaxRecurse); 1879 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse); 1880 case Instruction::Or: return SimplifyOrInst (LHS, RHS, TD, DT, MaxRecurse); 1881 case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse); 1882 default: 1883 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1884 if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 1885 Constant *COps[] = {CLHS, CRHS}; 1886 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 1887 } 1888 1889 // If the operation is associative, try some generic simplifications. 1890 if (Instruction::isAssociative(Opcode)) 1891 if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT, 1892 MaxRecurse)) 1893 return V; 1894 1895 // If the operation is with the result of a select instruction, check whether 1896 // operating on either branch of the select always yields the same value. 1897 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 1898 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT, 1899 MaxRecurse)) 1900 return V; 1901 1902 // If the operation is with the result of a phi instruction, check whether 1903 // operating on all incoming values of the phi always yields the same value. 1904 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 1905 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse)) 1906 return V; 1907 1908 return 0; 1909 } 1910} 1911 1912Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 1913 const TargetData *TD, const DominatorTree *DT) { 1914 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit); 1915} 1916 1917/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 1918/// fold the result. 1919static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1920 const TargetData *TD, const DominatorTree *DT, 1921 unsigned MaxRecurse) { 1922 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 1923 return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 1924 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 1925} 1926 1927Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1928 const TargetData *TD, const DominatorTree *DT) { 1929 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1930} 1931 1932/// SimplifyInstruction - See if we can compute a simplified version of this 1933/// instruction. If not, this returns null. 1934Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 1935 const DominatorTree *DT) { 1936 Value *Result; 1937 1938 switch (I->getOpcode()) { 1939 default: 1940 Result = ConstantFoldInstruction(I, TD); 1941 break; 1942 case Instruction::Add: 1943 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 1944 cast<BinaryOperator>(I)->hasNoSignedWrap(), 1945 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1946 TD, DT); 1947 break; 1948 case Instruction::Sub: 1949 Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 1950 cast<BinaryOperator>(I)->hasNoSignedWrap(), 1951 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1952 TD, DT); 1953 break; 1954 case Instruction::Mul: 1955 Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT); 1956 break; 1957 case Instruction::SDiv: 1958 Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), TD, DT); 1959 break; 1960 case Instruction::UDiv: 1961 Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), TD, DT); 1962 break; 1963 case Instruction::FDiv: 1964 Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), TD, DT); 1965 break; 1966 case Instruction::Shl: 1967 Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), 1968 cast<BinaryOperator>(I)->hasNoSignedWrap(), 1969 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1970 TD, DT); 1971 break; 1972 case Instruction::LShr: 1973 Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), 1974 cast<BinaryOperator>(I)->isExact(), 1975 TD, DT); 1976 break; 1977 case Instruction::AShr: 1978 Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), 1979 cast<BinaryOperator>(I)->isExact(), 1980 TD, DT); 1981 break; 1982 case Instruction::And: 1983 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT); 1984 break; 1985 case Instruction::Or: 1986 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT); 1987 break; 1988 case Instruction::Xor: 1989 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT); 1990 break; 1991 case Instruction::ICmp: 1992 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 1993 I->getOperand(0), I->getOperand(1), TD, DT); 1994 break; 1995 case Instruction::FCmp: 1996 Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 1997 I->getOperand(0), I->getOperand(1), TD, DT); 1998 break; 1999 case Instruction::Select: 2000 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 2001 I->getOperand(2), TD, DT); 2002 break; 2003 case Instruction::GetElementPtr: { 2004 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 2005 Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT); 2006 break; 2007 } 2008 case Instruction::PHI: 2009 Result = SimplifyPHINode(cast<PHINode>(I), DT); 2010 break; 2011 } 2012 2013 /// If called on unreachable code, the above logic may report that the 2014 /// instruction simplified to itself. Make life easier for users by 2015 /// detecting that case here, returning a safe value instead. 2016 return Result == I ? UndefValue::get(I->getType()) : Result; 2017} 2018 2019/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 2020/// delete the From instruction. In addition to a basic RAUW, this does a 2021/// recursive simplification of the newly formed instructions. This catches 2022/// things where one simplification exposes other opportunities. This only 2023/// simplifies and deletes scalar operations, it does not change the CFG. 2024/// 2025void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 2026 const TargetData *TD, 2027 const DominatorTree *DT) { 2028 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 2029 2030 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 2031 // we can know if it gets deleted out from under us or replaced in a 2032 // recursive simplification. 2033 WeakVH FromHandle(From); 2034 WeakVH ToHandle(To); 2035 2036 while (!From->use_empty()) { 2037 // Update the instruction to use the new value. 2038 Use &TheUse = From->use_begin().getUse(); 2039 Instruction *User = cast<Instruction>(TheUse.getUser()); 2040 TheUse = To; 2041 2042 // Check to see if the instruction can be folded due to the operand 2043 // replacement. For example changing (or X, Y) into (or X, -1) can replace 2044 // the 'or' with -1. 2045 Value *SimplifiedVal; 2046 { 2047 // Sanity check to make sure 'User' doesn't dangle across 2048 // SimplifyInstruction. 2049 AssertingVH<> UserHandle(User); 2050 2051 SimplifiedVal = SimplifyInstruction(User, TD, DT); 2052 if (SimplifiedVal == 0) continue; 2053 } 2054 2055 // Recursively simplify this user to the new value. 2056 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 2057 From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 2058 To = ToHandle; 2059 2060 assert(ToHandle && "To value deleted by recursive simplification?"); 2061 2062 // If the recursive simplification ended up revisiting and deleting 2063 // 'From' then we're done. 2064 if (From == 0) 2065 return; 2066 } 2067 2068 // If 'From' has value handles referring to it, do a real RAUW to update them. 2069 From->replaceAllUsesWith(To); 2070 2071 From->eraseFromParent(); 2072} 2073