InstructionSimplify.cpp revision 4b720718fbda1194f925e0a9d931bc220e8b0e3a
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 32#define 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 return 0; 410} 411 412/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 413/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 414/// it on the incoming phi values yields the same result for every value. If so 415/// returns the common value, otherwise returns null. 416static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 417 const TargetData *TD, const DominatorTree *DT, 418 unsigned MaxRecurse) { 419 // Recursion is always used, so bail out at once if we already hit the limit. 420 if (!MaxRecurse--) 421 return 0; 422 423 PHINode *PI; 424 if (isa<PHINode>(LHS)) { 425 PI = cast<PHINode>(LHS); 426 // Bail out if RHS and the phi may be mutually interdependent due to a loop. 427 if (!ValueDominatesPHI(RHS, PI, DT)) 428 return 0; 429 } else { 430 assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 431 PI = cast<PHINode>(RHS); 432 // Bail out if LHS and the phi may be mutually interdependent due to a loop. 433 if (!ValueDominatesPHI(LHS, PI, DT)) 434 return 0; 435 } 436 437 // Evaluate the BinOp on the incoming phi values. 438 Value *CommonValue = 0; 439 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 440 Value *Incoming = PI->getIncomingValue(i); 441 // If the incoming value is the phi node itself, it can safely be skipped. 442 if (Incoming == PI) continue; 443 Value *V = PI == LHS ? 444 SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) : 445 SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse); 446 // If the operation failed to simplify, or simplified to a different value 447 // to previously, then give up. 448 if (!V || (CommonValue && V != CommonValue)) 449 return 0; 450 CommonValue = V; 451 } 452 453 return CommonValue; 454} 455 456/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 457/// try to simplify the comparison by seeing whether comparing with all of the 458/// incoming phi values yields the same result every time. If so returns the 459/// common result, otherwise returns null. 460static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, 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 // Make sure the phi is on the LHS. 468 if (!isa<PHINode>(LHS)) { 469 std::swap(LHS, RHS); 470 Pred = CmpInst::getSwappedPredicate(Pred); 471 } 472 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 473 PHINode *PI = cast<PHINode>(LHS); 474 475 // Bail out if RHS and the phi may be mutually interdependent due to a loop. 476 if (!ValueDominatesPHI(RHS, PI, DT)) 477 return 0; 478 479 // Evaluate the BinOp on the incoming phi values. 480 Value *CommonValue = 0; 481 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 482 Value *Incoming = PI->getIncomingValue(i); 483 // If the incoming value is the phi node itself, it can safely be skipped. 484 if (Incoming == PI) continue; 485 Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse); 486 // If the operation failed to simplify, or simplified to a different value 487 // to previously, then give up. 488 if (!V || (CommonValue && V != CommonValue)) 489 return 0; 490 CommonValue = V; 491 } 492 493 return CommonValue; 494} 495 496/// SimplifyAddInst - Given operands for an Add, see if we can 497/// fold the result. If not, this returns null. 498static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 499 const TargetData *TD, const DominatorTree *DT, 500 unsigned MaxRecurse) { 501 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 502 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 503 Constant *Ops[] = { CLHS, CRHS }; 504 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 505 Ops, 2, TD); 506 } 507 508 // Canonicalize the constant to the RHS. 509 std::swap(Op0, Op1); 510 } 511 512 // X + undef -> undef 513 if (match(Op1, m_Undef())) 514 return Op1; 515 516 // X + 0 -> X 517 if (match(Op1, m_Zero())) 518 return Op0; 519 520 // X + (Y - X) -> Y 521 // (Y - X) + X -> Y 522 // Eg: X + -X -> 0 523 Value *Y = 0; 524 if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 525 match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 526 return Y; 527 528 // X + ~X -> -1 since ~X = -X-1 529 if (match(Op0, m_Not(m_Specific(Op1))) || 530 match(Op1, m_Not(m_Specific(Op0)))) 531 return Constant::getAllOnesValue(Op0->getType()); 532 533 /// i1 add -> xor. 534 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 535 if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 536 return V; 537 538 // Try some generic simplifications for associative operations. 539 if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT, 540 MaxRecurse)) 541 return V; 542 543 // Mul distributes over Add. Try some generic simplifications based on this. 544 if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul, 545 TD, DT, MaxRecurse)) 546 return V; 547 548 // Threading Add over selects and phi nodes is pointless, so don't bother. 549 // Threading over the select in "A + select(cond, B, C)" means evaluating 550 // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 551 // only if B and C are equal. If B and C are equal then (since we assume 552 // that operands have already been simplified) "select(cond, B, C)" should 553 // have been simplified to the common value of B and C already. Analysing 554 // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 555 // for threading over phi nodes. 556 557 return 0; 558} 559 560Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 561 const TargetData *TD, const DominatorTree *DT) { 562 return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 563} 564 565/// SimplifySubInst - Given operands for a Sub, see if we can 566/// fold the result. If not, this returns null. 567static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 568 const TargetData *TD, const DominatorTree *DT, 569 unsigned MaxRecurse) { 570 if (Constant *CLHS = dyn_cast<Constant>(Op0)) 571 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 572 Constant *Ops[] = { CLHS, CRHS }; 573 return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 574 Ops, 2, TD); 575 } 576 577 // X - undef -> undef 578 // undef - X -> undef 579 if (match(Op0, m_Undef()) || match(Op1, m_Undef())) 580 return UndefValue::get(Op0->getType()); 581 582 // X - 0 -> X 583 if (match(Op1, m_Zero())) 584 return Op0; 585 586 // X - X -> 0 587 if (Op0 == Op1) 588 return Constant::getNullValue(Op0->getType()); 589 590 // (X*2) - X -> X 591 // (X<<1) - X -> X 592 Value *X = 0; 593 if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) || 594 match(Op0, m_Shl(m_Specific(Op1), m_One()))) 595 return Op1; 596 597 // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. 598 // For example, (X + Y) - Y -> X; (Y + X) - Y -> X 599 Value *Y = 0, *Z = Op1; 600 if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z 601 // See if "V === Y - Z" simplifies. 602 if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, TD, DT, MaxRecurse-1)) 603 // It does! Now see if "X + V" simplifies. 604 if (Value *W = SimplifyBinOp(Instruction::Add, X, V, TD, DT, 605 MaxRecurse-1)) { 606 // It does, we successfully reassociated! 607 ++NumReassoc; 608 return W; 609 } 610 // See if "V === X - Z" simplifies. 611 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, DT, MaxRecurse-1)) 612 // It does! Now see if "Y + V" simplifies. 613 if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, TD, DT, 614 MaxRecurse-1)) { 615 // It does, we successfully reassociated! 616 ++NumReassoc; 617 return W; 618 } 619 } 620 621 // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies. 622 // For example, X - (X + 1) -> -1 623 X = Op0; 624 if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z) 625 // See if "V === X - Y" simplifies. 626 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, TD, DT, MaxRecurse-1)) 627 // It does! Now see if "V - Z" simplifies. 628 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, TD, DT, 629 MaxRecurse-1)) { 630 // It does, we successfully reassociated! 631 ++NumReassoc; 632 return W; 633 } 634 // See if "V === X - Z" simplifies. 635 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, DT, MaxRecurse-1)) 636 // It does! Now see if "V - Y" simplifies. 637 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, TD, DT, 638 MaxRecurse-1)) { 639 // It does, we successfully reassociated! 640 ++NumReassoc; 641 return W; 642 } 643 } 644 645 // Z - (X - Y) -> (Z - X) + Y if everything simplifies. 646 // For example, X - (X - Y) -> Y. 647 Z = Op0; 648 if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y) 649 // See if "V === Z - X" simplifies. 650 if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, TD, DT, MaxRecurse-1)) 651 // It does! Now see if "V + Y" simplifies. 652 if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, TD, DT, 653 MaxRecurse-1)) { 654 // It does, we successfully reassociated! 655 ++NumReassoc; 656 return W; 657 } 658 659 // Mul distributes over Sub. Try some generic simplifications based on this. 660 if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul, 661 TD, DT, MaxRecurse)) 662 return V; 663 664 // i1 sub -> xor. 665 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 666 if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 667 return V; 668 669 // Threading Sub over selects and phi nodes is pointless, so don't bother. 670 // Threading over the select in "A - select(cond, B, C)" means evaluating 671 // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 672 // only if B and C are equal. If B and C are equal then (since we assume 673 // that operands have already been simplified) "select(cond, B, C)" should 674 // have been simplified to the common value of B and C already. Analysing 675 // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 676 // for threading over phi nodes. 677 678 return 0; 679} 680 681Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 682 const TargetData *TD, const DominatorTree *DT) { 683 return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 684} 685 686/// SimplifyMulInst - Given operands for a Mul, see if we can 687/// fold the result. If not, this returns null. 688static Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 689 const DominatorTree *DT, unsigned MaxRecurse) { 690 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 691 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 692 Constant *Ops[] = { CLHS, CRHS }; 693 return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 694 Ops, 2, TD); 695 } 696 697 // Canonicalize the constant to the RHS. 698 std::swap(Op0, Op1); 699 } 700 701 // X * undef -> 0 702 if (match(Op1, m_Undef())) 703 return Constant::getNullValue(Op0->getType()); 704 705 // X * 0 -> 0 706 if (match(Op1, m_Zero())) 707 return Op1; 708 709 // X * 1 -> X 710 if (match(Op1, m_One())) 711 return Op0; 712 713 // (X / Y) * Y -> X if the division is exact. 714 Value *X = 0, *Y = 0; 715 if ((match(Op0, m_SDiv(m_Value(X), m_Value(Y))) && Y == Op1) || // (X / Y) * Y 716 (match(Op1, m_SDiv(m_Value(X), m_Value(Y))) && Y == Op0)) { // Y * (X / Y) 717 BinaryOperator *SDiv = cast<BinaryOperator>(Y == Op1 ? Op0 : Op1); 718 if (SDiv->isExact()) 719 return X; 720 } 721 722 // i1 mul -> and. 723 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 724 if (Value *V = SimplifyAndInst(Op0, Op1, TD, DT, MaxRecurse-1)) 725 return V; 726 727 // Try some generic simplifications for associative operations. 728 if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, DT, 729 MaxRecurse)) 730 return V; 731 732 // Mul distributes over Add. Try some generic simplifications based on this. 733 if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 734 TD, DT, MaxRecurse)) 735 return V; 736 737 // If the operation is with the result of a select instruction, check whether 738 // operating on either branch of the select always yields the same value. 739 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 740 if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, DT, 741 MaxRecurse)) 742 return V; 743 744 // If the operation is with the result of a phi instruction, check whether 745 // operating on all incoming values of the phi always yields the same value. 746 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 747 if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, DT, 748 MaxRecurse)) 749 return V; 750 751 return 0; 752} 753 754Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 755 const DominatorTree *DT) { 756 return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit); 757} 758 759/// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can 760/// fold the result. If not, this returns null. 761static Value *SimplifyDiv(unsigned Opcode, Value *Op0, Value *Op1, 762 const TargetData *TD, const DominatorTree *DT, 763 unsigned MaxRecurse) { 764 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 765 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 766 Constant *Ops[] = { C0, C1 }; 767 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, 2, TD); 768 } 769 } 770 771 bool isSigned = Opcode == Instruction::SDiv; 772 773 // X / undef -> undef 774 if (match(Op1, m_Undef())) 775 return Op1; 776 777 // undef / X -> 0 778 if (match(Op0, m_Undef())) 779 return Constant::getNullValue(Op0->getType()); 780 781 // 0 / X -> 0, we don't need to preserve faults! 782 if (match(Op0, m_Zero())) 783 return Op0; 784 785 // X / 1 -> X 786 if (match(Op1, m_One())) 787 return Op0; 788 789 if (Op0->getType()->isIntegerTy(1)) 790 // It can't be division by zero, hence it must be division by one. 791 return Op0; 792 793 // X / X -> 1 794 if (Op0 == Op1) 795 return ConstantInt::get(Op0->getType(), 1); 796 797 // (X * Y) / Y -> X if the multiplication does not overflow. 798 Value *X = 0, *Y = 0; 799 if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { 800 if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 801 BinaryOperator *Mul = cast<BinaryOperator>(Op0); 802 // If the Mul knows it does not overflow, then we are good to go. 803 if ((isSigned && Mul->hasNoSignedWrap()) || 804 (!isSigned && Mul->hasNoUnsignedWrap())) 805 return X; 806 // If X has the form X = A / Y then X * Y cannot overflow. 807 if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X)) 808 if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) 809 return X; 810 } 811 812 // (X rem Y) / Y -> 0 813 if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 814 (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 815 return Constant::getNullValue(Op0->getType()); 816 817 // If the operation is with the result of a select instruction, check whether 818 // operating on either branch of the select always yields the same value. 819 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 820 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 821 return V; 822 823 // If the operation is with the result of a phi instruction, check whether 824 // operating on all incoming values of the phi always yields the same value. 825 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 826 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 827 return V; 828 829 return 0; 830} 831 832/// SimplifySDivInst - Given operands for an SDiv, see if we can 833/// fold the result. If not, this returns null. 834static Value *SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, 835 const DominatorTree *DT, unsigned MaxRecurse) { 836 if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, TD, DT, MaxRecurse)) 837 return V; 838 839 return 0; 840} 841 842Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, 843 const DominatorTree *DT) { 844 return ::SimplifySDivInst(Op0, Op1, TD, DT, RecursionLimit); 845} 846 847/// SimplifyUDivInst - Given operands for a UDiv, see if we can 848/// fold the result. If not, this returns null. 849static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, 850 const DominatorTree *DT, unsigned MaxRecurse) { 851 if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, TD, DT, MaxRecurse)) 852 return V; 853 854 return 0; 855} 856 857Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, 858 const DominatorTree *DT) { 859 return ::SimplifyUDivInst(Op0, Op1, TD, DT, RecursionLimit); 860} 861 862static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *, 863 const DominatorTree *, unsigned) { 864 // undef / X -> undef (the undef could be a snan). 865 if (match(Op0, m_Undef())) 866 return Op0; 867 868 // X / undef -> undef 869 if (match(Op1, m_Undef())) 870 return Op1; 871 872 return 0; 873} 874 875Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *TD, 876 const DominatorTree *DT) { 877 return ::SimplifyFDivInst(Op0, Op1, TD, DT, RecursionLimit); 878} 879 880/// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can 881/// fold the result. If not, this returns null. 882static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, 883 const TargetData *TD, const DominatorTree *DT, 884 unsigned MaxRecurse) { 885 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 886 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 887 Constant *Ops[] = { C0, C1 }; 888 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, 2, TD); 889 } 890 } 891 892 // 0 shift by X -> 0 893 if (match(Op0, m_Zero())) 894 return Op0; 895 896 // X shift by 0 -> X 897 if (match(Op1, m_Zero())) 898 return Op0; 899 900 // X shift by undef -> undef because it may shift by the bitwidth. 901 if (match(Op1, m_Undef())) 902 return Op1; 903 904 // Shifting by the bitwidth or more is undefined. 905 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) 906 if (CI->getValue().getLimitedValue() >= 907 Op0->getType()->getScalarSizeInBits()) 908 return UndefValue::get(Op0->getType()); 909 910 // If the operation is with the result of a select instruction, check whether 911 // operating on either branch of the select always yields the same value. 912 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 913 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 914 return V; 915 916 // If the operation is with the result of a phi instruction, check whether 917 // operating on all incoming values of the phi always yields the same value. 918 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 919 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 920 return V; 921 922 return 0; 923} 924 925/// SimplifyShlInst - Given operands for an Shl, see if we can 926/// fold the result. If not, this returns null. 927static Value *SimplifyShlInst(Value *Op0, Value *Op1, const TargetData *TD, 928 const DominatorTree *DT, unsigned MaxRecurse) { 929 if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, TD, DT, MaxRecurse)) 930 return V; 931 932 // undef << X -> 0 933 if (match(Op0, m_Undef())) 934 return Constant::getNullValue(Op0->getType()); 935 936 return 0; 937} 938 939Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, const TargetData *TD, 940 const DominatorTree *DT) { 941 return ::SimplifyShlInst(Op0, Op1, TD, DT, RecursionLimit); 942} 943 944/// SimplifyLShrInst - Given operands for an LShr, see if we can 945/// fold the result. If not, this returns null. 946static Value *SimplifyLShrInst(Value *Op0, Value *Op1, const TargetData *TD, 947 const DominatorTree *DT, unsigned MaxRecurse) { 948 if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, TD, DT, MaxRecurse)) 949 return V; 950 951 // undef >>l X -> 0 952 if (match(Op0, m_Undef())) 953 return Constant::getNullValue(Op0->getType()); 954 955 return 0; 956} 957 958Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, const TargetData *TD, 959 const DominatorTree *DT) { 960 return ::SimplifyLShrInst(Op0, Op1, TD, DT, RecursionLimit); 961} 962 963/// SimplifyAShrInst - Given operands for an AShr, see if we can 964/// fold the result. If not, this returns null. 965static Value *SimplifyAShrInst(Value *Op0, Value *Op1, const TargetData *TD, 966 const DominatorTree *DT, unsigned MaxRecurse) { 967 if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, TD, DT, MaxRecurse)) 968 return V; 969 970 // all ones >>a X -> all ones 971 if (match(Op0, m_AllOnes())) 972 return Op0; 973 974 // undef >>a X -> all ones 975 if (match(Op0, m_Undef())) 976 return Constant::getAllOnesValue(Op0->getType()); 977 978 return 0; 979} 980 981Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, const TargetData *TD, 982 const DominatorTree *DT) { 983 return ::SimplifyAShrInst(Op0, Op1, TD, DT, RecursionLimit); 984} 985 986/// SimplifyAndInst - Given operands for an And, see if we can 987/// fold the result. If not, this returns null. 988static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 989 const DominatorTree *DT, unsigned MaxRecurse) { 990 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 991 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 992 Constant *Ops[] = { CLHS, CRHS }; 993 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 994 Ops, 2, TD); 995 } 996 997 // Canonicalize the constant to the RHS. 998 std::swap(Op0, Op1); 999 } 1000 1001 // X & undef -> 0 1002 if (match(Op1, m_Undef())) 1003 return Constant::getNullValue(Op0->getType()); 1004 1005 // X & X = X 1006 if (Op0 == Op1) 1007 return Op0; 1008 1009 // X & 0 = 0 1010 if (match(Op1, m_Zero())) 1011 return Op1; 1012 1013 // X & -1 = X 1014 if (match(Op1, m_AllOnes())) 1015 return Op0; 1016 1017 // A & ~A = ~A & A = 0 1018 Value *A = 0, *B = 0; 1019 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 1020 (match(Op1, m_Not(m_Value(A))) && A == Op0)) 1021 return Constant::getNullValue(Op0->getType()); 1022 1023 // (A | ?) & A = A 1024 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1025 (A == Op1 || B == Op1)) 1026 return Op1; 1027 1028 // A & (A | ?) = A 1029 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1030 (A == Op0 || B == Op0)) 1031 return Op0; 1032 1033 // Try some generic simplifications for associative operations. 1034 if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT, 1035 MaxRecurse)) 1036 return V; 1037 1038 // And distributes over Or. Try some generic simplifications based on this. 1039 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1040 TD, DT, MaxRecurse)) 1041 return V; 1042 1043 // And distributes over Xor. Try some generic simplifications based on this. 1044 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 1045 TD, DT, MaxRecurse)) 1046 return V; 1047 1048 // Or distributes over And. Try some generic simplifications based on this. 1049 if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1050 TD, DT, MaxRecurse)) 1051 return V; 1052 1053 // If the operation is with the result of a select instruction, check whether 1054 // operating on either branch of the select always yields the same value. 1055 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1056 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT, 1057 MaxRecurse)) 1058 return V; 1059 1060 // If the operation is with the result of a phi instruction, check whether 1061 // operating on all incoming values of the phi always yields the same value. 1062 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1063 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT, 1064 MaxRecurse)) 1065 return V; 1066 1067 return 0; 1068} 1069 1070Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 1071 const DominatorTree *DT) { 1072 return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit); 1073} 1074 1075/// SimplifyOrInst - Given operands for an Or, see if we can 1076/// fold the result. If not, this returns null. 1077static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 1078 const DominatorTree *DT, unsigned MaxRecurse) { 1079 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1080 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1081 Constant *Ops[] = { CLHS, CRHS }; 1082 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 1083 Ops, 2, TD); 1084 } 1085 1086 // Canonicalize the constant to the RHS. 1087 std::swap(Op0, Op1); 1088 } 1089 1090 // X | undef -> -1 1091 if (match(Op1, m_Undef())) 1092 return Constant::getAllOnesValue(Op0->getType()); 1093 1094 // X | X = X 1095 if (Op0 == Op1) 1096 return Op0; 1097 1098 // X | 0 = X 1099 if (match(Op1, m_Zero())) 1100 return Op0; 1101 1102 // X | -1 = -1 1103 if (match(Op1, m_AllOnes())) 1104 return Op1; 1105 1106 // A | ~A = ~A | A = -1 1107 Value *A = 0, *B = 0; 1108 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 1109 (match(Op1, m_Not(m_Value(A))) && A == Op0)) 1110 return Constant::getAllOnesValue(Op0->getType()); 1111 1112 // (A & ?) | A = A 1113 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 1114 (A == Op1 || B == Op1)) 1115 return Op1; 1116 1117 // A | (A & ?) = A 1118 if (match(Op1, m_And(m_Value(A), m_Value(B))) && 1119 (A == Op0 || B == Op0)) 1120 return Op0; 1121 1122 // Try some generic simplifications for associative operations. 1123 if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT, 1124 MaxRecurse)) 1125 return V; 1126 1127 // Or distributes over And. Try some generic simplifications based on this. 1128 if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, 1129 TD, DT, MaxRecurse)) 1130 return V; 1131 1132 // And distributes over Or. Try some generic simplifications based on this. 1133 if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And, 1134 TD, DT, MaxRecurse)) 1135 return V; 1136 1137 // If the operation is with the result of a select instruction, check whether 1138 // operating on either branch of the select always yields the same value. 1139 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1140 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT, 1141 MaxRecurse)) 1142 return V; 1143 1144 // If the operation is with the result of a phi instruction, check whether 1145 // operating on all incoming values of the phi always yields the same value. 1146 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1147 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT, 1148 MaxRecurse)) 1149 return V; 1150 1151 return 0; 1152} 1153 1154Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 1155 const DominatorTree *DT) { 1156 return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit); 1157} 1158 1159/// SimplifyXorInst - Given operands for a Xor, see if we can 1160/// fold the result. If not, this returns null. 1161static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 1162 const DominatorTree *DT, unsigned MaxRecurse) { 1163 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1164 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1165 Constant *Ops[] = { CLHS, CRHS }; 1166 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 1167 Ops, 2, TD); 1168 } 1169 1170 // Canonicalize the constant to the RHS. 1171 std::swap(Op0, Op1); 1172 } 1173 1174 // A ^ undef -> undef 1175 if (match(Op1, m_Undef())) 1176 return Op1; 1177 1178 // A ^ 0 = A 1179 if (match(Op1, m_Zero())) 1180 return Op0; 1181 1182 // A ^ A = 0 1183 if (Op0 == Op1) 1184 return Constant::getNullValue(Op0->getType()); 1185 1186 // A ^ ~A = ~A ^ A = -1 1187 Value *A = 0; 1188 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 1189 (match(Op1, m_Not(m_Value(A))) && A == Op0)) 1190 return Constant::getAllOnesValue(Op0->getType()); 1191 1192 // Try some generic simplifications for associative operations. 1193 if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT, 1194 MaxRecurse)) 1195 return V; 1196 1197 // And distributes over Xor. Try some generic simplifications based on this. 1198 if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And, 1199 TD, DT, MaxRecurse)) 1200 return V; 1201 1202 // Threading Xor over selects and phi nodes is pointless, so don't bother. 1203 // Threading over the select in "A ^ select(cond, B, C)" means evaluating 1204 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 1205 // only if B and C are equal. If B and C are equal then (since we assume 1206 // that operands have already been simplified) "select(cond, B, C)" should 1207 // have been simplified to the common value of B and C already. Analysing 1208 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 1209 // for threading over phi nodes. 1210 1211 return 0; 1212} 1213 1214Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 1215 const DominatorTree *DT) { 1216 return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit); 1217} 1218 1219static const Type *GetCompareTy(Value *Op) { 1220 return CmpInst::makeCmpResultType(Op->getType()); 1221} 1222 1223/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 1224/// fold the result. If not, this returns null. 1225static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1226 const TargetData *TD, const DominatorTree *DT, 1227 unsigned MaxRecurse) { 1228 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 1229 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 1230 1231 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 1232 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1233 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 1234 1235 // If we have a constant, make sure it is on the RHS. 1236 std::swap(LHS, RHS); 1237 Pred = CmpInst::getSwappedPredicate(Pred); 1238 } 1239 1240 const Type *ITy = GetCompareTy(LHS); // The return type. 1241 const Type *OpTy = LHS->getType(); // The operand type. 1242 1243 // icmp X, X -> true/false 1244 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 1245 // because X could be 0. 1246 if (LHS == RHS || isa<UndefValue>(RHS)) 1247 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 1248 1249 // Special case logic when the operands have i1 type. 1250 if (OpTy->isIntegerTy(1) || (OpTy->isVectorTy() && 1251 cast<VectorType>(OpTy)->getElementType()->isIntegerTy(1))) { 1252 switch (Pred) { 1253 default: break; 1254 case ICmpInst::ICMP_EQ: 1255 // X == 1 -> X 1256 if (match(RHS, m_One())) 1257 return LHS; 1258 break; 1259 case ICmpInst::ICMP_NE: 1260 // X != 0 -> X 1261 if (match(RHS, m_Zero())) 1262 return LHS; 1263 break; 1264 case ICmpInst::ICMP_UGT: 1265 // X >u 0 -> X 1266 if (match(RHS, m_Zero())) 1267 return LHS; 1268 break; 1269 case ICmpInst::ICMP_UGE: 1270 // X >=u 1 -> X 1271 if (match(RHS, m_One())) 1272 return LHS; 1273 break; 1274 case ICmpInst::ICMP_SLT: 1275 // X <s 0 -> X 1276 if (match(RHS, m_Zero())) 1277 return LHS; 1278 break; 1279 case ICmpInst::ICMP_SLE: 1280 // X <=s -1 -> X 1281 if (match(RHS, m_One())) 1282 return LHS; 1283 break; 1284 } 1285 } 1286 1287 // icmp <alloca*>, <global/alloca*/null> - Different stack variables have 1288 // different addresses, and what's more the address of a stack variable is 1289 // never null or equal to the address of a global. Note that generalizing 1290 // to the case where LHS is a global variable address or null is pointless, 1291 // since if both LHS and RHS are constants then we already constant folded 1292 // the compare, and if only one of them is then we moved it to RHS already. 1293 if (isa<AllocaInst>(LHS) && (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 1294 isa<ConstantPointerNull>(RHS))) 1295 // We already know that LHS != LHS. 1296 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 1297 1298 // If we are comparing with zero then try hard since this is a common case. 1299 if (match(RHS, m_Zero())) { 1300 bool LHSKnownNonNegative, LHSKnownNegative; 1301 switch (Pred) { 1302 default: 1303 assert(false && "Unknown ICmp predicate!"); 1304 case ICmpInst::ICMP_ULT: 1305 return ConstantInt::getFalse(LHS->getContext()); 1306 case ICmpInst::ICMP_UGE: 1307 return ConstantInt::getTrue(LHS->getContext()); 1308 case ICmpInst::ICMP_EQ: 1309 case ICmpInst::ICMP_ULE: 1310 if (isKnownNonZero(LHS, TD)) 1311 return ConstantInt::getFalse(LHS->getContext()); 1312 break; 1313 case ICmpInst::ICMP_NE: 1314 case ICmpInst::ICMP_UGT: 1315 if (isKnownNonZero(LHS, TD)) 1316 return ConstantInt::getTrue(LHS->getContext()); 1317 break; 1318 case ICmpInst::ICMP_SLT: 1319 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1320 if (LHSKnownNegative) 1321 return ConstantInt::getTrue(LHS->getContext()); 1322 if (LHSKnownNonNegative) 1323 return ConstantInt::getFalse(LHS->getContext()); 1324 break; 1325 case ICmpInst::ICMP_SLE: 1326 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1327 if (LHSKnownNegative) 1328 return ConstantInt::getTrue(LHS->getContext()); 1329 if (LHSKnownNonNegative && isKnownNonZero(LHS, TD)) 1330 return ConstantInt::getFalse(LHS->getContext()); 1331 break; 1332 case ICmpInst::ICMP_SGE: 1333 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1334 if (LHSKnownNegative) 1335 return ConstantInt::getFalse(LHS->getContext()); 1336 if (LHSKnownNonNegative) 1337 return ConstantInt::getTrue(LHS->getContext()); 1338 break; 1339 case ICmpInst::ICMP_SGT: 1340 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1341 if (LHSKnownNegative) 1342 return ConstantInt::getFalse(LHS->getContext()); 1343 if (LHSKnownNonNegative && isKnownNonZero(LHS, TD)) 1344 return ConstantInt::getTrue(LHS->getContext()); 1345 break; 1346 } 1347 } 1348 1349 // See if we are doing a comparison with a constant integer. 1350 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1351 switch (Pred) { 1352 default: break; 1353 case ICmpInst::ICMP_UGT: 1354 if (CI->isMaxValue(false)) // A >u MAX -> FALSE 1355 return ConstantInt::getFalse(CI->getContext()); 1356 break; 1357 case ICmpInst::ICMP_UGE: 1358 if (CI->isMinValue(false)) // A >=u MIN -> TRUE 1359 return ConstantInt::getTrue(CI->getContext()); 1360 break; 1361 case ICmpInst::ICMP_ULT: 1362 if (CI->isMinValue(false)) // A <u MIN -> FALSE 1363 return ConstantInt::getFalse(CI->getContext()); 1364 break; 1365 case ICmpInst::ICMP_ULE: 1366 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 1367 return ConstantInt::getTrue(CI->getContext()); 1368 break; 1369 case ICmpInst::ICMP_SGT: 1370 if (CI->isMaxValue(true)) // A >s MAX -> FALSE 1371 return ConstantInt::getFalse(CI->getContext()); 1372 break; 1373 case ICmpInst::ICMP_SGE: 1374 if (CI->isMinValue(true)) // A >=s MIN -> TRUE 1375 return ConstantInt::getTrue(CI->getContext()); 1376 break; 1377 case ICmpInst::ICMP_SLT: 1378 if (CI->isMinValue(true)) // A <s MIN -> FALSE 1379 return ConstantInt::getFalse(CI->getContext()); 1380 break; 1381 case ICmpInst::ICMP_SLE: 1382 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 1383 return ConstantInt::getTrue(CI->getContext()); 1384 break; 1385 } 1386 } 1387 1388 // Compare of cast, for example (zext X) != 0 -> X != 0 1389 if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) { 1390 Instruction *LI = cast<CastInst>(LHS); 1391 Value *SrcOp = LI->getOperand(0); 1392 const Type *SrcTy = SrcOp->getType(); 1393 const Type *DstTy = LI->getType(); 1394 1395 // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input 1396 // if the integer type is the same size as the pointer type. 1397 if (MaxRecurse && TD && isa<PtrToIntInst>(LI) && 1398 TD->getPointerSizeInBits() == DstTy->getPrimitiveSizeInBits()) { 1399 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 1400 // Transfer the cast to the constant. 1401 if (Value *V = SimplifyICmpInst(Pred, SrcOp, 1402 ConstantExpr::getIntToPtr(RHSC, SrcTy), 1403 TD, DT, MaxRecurse-1)) 1404 return V; 1405 } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) { 1406 if (RI->getOperand(0)->getType() == SrcTy) 1407 // Compare without the cast. 1408 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 1409 TD, DT, MaxRecurse-1)) 1410 return V; 1411 } 1412 } 1413 1414 if (isa<ZExtInst>(LHS)) { 1415 // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the 1416 // same type. 1417 if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) { 1418 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 1419 // Compare X and Y. Note that signed predicates become unsigned. 1420 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 1421 SrcOp, RI->getOperand(0), TD, DT, 1422 MaxRecurse-1)) 1423 return V; 1424 } 1425 // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended 1426 // too. If not, then try to deduce the result of the comparison. 1427 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1428 // Compute the constant that would happen if we truncated to SrcTy then 1429 // reextended to DstTy. 1430 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 1431 Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy); 1432 1433 // If the re-extended constant didn't change then this is effectively 1434 // also a case of comparing two zero-extended values. 1435 if (RExt == CI && MaxRecurse) 1436 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 1437 SrcOp, Trunc, TD, DT, MaxRecurse-1)) 1438 return V; 1439 1440 // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit 1441 // there. Use this to work out the result of the comparison. 1442 if (RExt != CI) { 1443 switch (Pred) { 1444 default: 1445 assert(false && "Unknown ICmp predicate!"); 1446 // LHS <u RHS. 1447 case ICmpInst::ICMP_EQ: 1448 case ICmpInst::ICMP_UGT: 1449 case ICmpInst::ICMP_UGE: 1450 return ConstantInt::getFalse(CI->getContext()); 1451 1452 case ICmpInst::ICMP_NE: 1453 case ICmpInst::ICMP_ULT: 1454 case ICmpInst::ICMP_ULE: 1455 return ConstantInt::getTrue(CI->getContext()); 1456 1457 // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS 1458 // is non-negative then LHS <s RHS. 1459 case ICmpInst::ICMP_SGT: 1460 case ICmpInst::ICMP_SGE: 1461 return CI->getValue().isNegative() ? 1462 ConstantInt::getTrue(CI->getContext()) : 1463 ConstantInt::getFalse(CI->getContext()); 1464 1465 case ICmpInst::ICMP_SLT: 1466 case ICmpInst::ICMP_SLE: 1467 return CI->getValue().isNegative() ? 1468 ConstantInt::getFalse(CI->getContext()) : 1469 ConstantInt::getTrue(CI->getContext()); 1470 } 1471 } 1472 } 1473 } 1474 1475 if (isa<SExtInst>(LHS)) { 1476 // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the 1477 // same type. 1478 if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) { 1479 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 1480 // Compare X and Y. Note that the predicate does not change. 1481 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 1482 TD, DT, MaxRecurse-1)) 1483 return V; 1484 } 1485 // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended 1486 // too. If not, then try to deduce the result of the comparison. 1487 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1488 // Compute the constant that would happen if we truncated to SrcTy then 1489 // reextended to DstTy. 1490 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 1491 Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy); 1492 1493 // If the re-extended constant didn't change then this is effectively 1494 // also a case of comparing two sign-extended values. 1495 if (RExt == CI && MaxRecurse) 1496 if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, TD, DT, 1497 MaxRecurse-1)) 1498 return V; 1499 1500 // Otherwise the upper bits of LHS are all equal, while RHS has varying 1501 // bits there. Use this to work out the result of the comparison. 1502 if (RExt != CI) { 1503 switch (Pred) { 1504 default: 1505 assert(false && "Unknown ICmp predicate!"); 1506 case ICmpInst::ICMP_EQ: 1507 return ConstantInt::getFalse(CI->getContext()); 1508 case ICmpInst::ICMP_NE: 1509 return ConstantInt::getTrue(CI->getContext()); 1510 1511 // If RHS is non-negative then LHS <s RHS. If RHS is negative then 1512 // LHS >s RHS. 1513 case ICmpInst::ICMP_SGT: 1514 case ICmpInst::ICMP_SGE: 1515 return CI->getValue().isNegative() ? 1516 ConstantInt::getTrue(CI->getContext()) : 1517 ConstantInt::getFalse(CI->getContext()); 1518 case ICmpInst::ICMP_SLT: 1519 case ICmpInst::ICMP_SLE: 1520 return CI->getValue().isNegative() ? 1521 ConstantInt::getFalse(CI->getContext()) : 1522 ConstantInt::getTrue(CI->getContext()); 1523 1524 // If LHS is non-negative then LHS <u RHS. If LHS is negative then 1525 // LHS >u RHS. 1526 case ICmpInst::ICMP_UGT: 1527 case ICmpInst::ICMP_UGE: 1528 // Comparison is true iff the LHS <s 0. 1529 if (MaxRecurse) 1530 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp, 1531 Constant::getNullValue(SrcTy), 1532 TD, DT, MaxRecurse-1)) 1533 return V; 1534 break; 1535 case ICmpInst::ICMP_ULT: 1536 case ICmpInst::ICMP_ULE: 1537 // Comparison is true iff the LHS >=s 0. 1538 if (MaxRecurse) 1539 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp, 1540 Constant::getNullValue(SrcTy), 1541 TD, DT, MaxRecurse-1)) 1542 return V; 1543 break; 1544 } 1545 } 1546 } 1547 } 1548 } 1549 1550 // If the comparison is with the result of a select instruction, check whether 1551 // comparing with either branch of the select always yields the same value. 1552 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 1553 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1554 return V; 1555 1556 // If the comparison is with the result of a phi instruction, check whether 1557 // doing the compare with each incoming phi value yields a common result. 1558 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 1559 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1560 return V; 1561 1562 return 0; 1563} 1564 1565Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1566 const TargetData *TD, const DominatorTree *DT) { 1567 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1568} 1569 1570/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 1571/// fold the result. If not, this returns null. 1572static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1573 const TargetData *TD, const DominatorTree *DT, 1574 unsigned MaxRecurse) { 1575 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 1576 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 1577 1578 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 1579 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1580 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 1581 1582 // If we have a constant, make sure it is on the RHS. 1583 std::swap(LHS, RHS); 1584 Pred = CmpInst::getSwappedPredicate(Pred); 1585 } 1586 1587 // Fold trivial predicates. 1588 if (Pred == FCmpInst::FCMP_FALSE) 1589 return ConstantInt::get(GetCompareTy(LHS), 0); 1590 if (Pred == FCmpInst::FCMP_TRUE) 1591 return ConstantInt::get(GetCompareTy(LHS), 1); 1592 1593 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 1594 return UndefValue::get(GetCompareTy(LHS)); 1595 1596 // fcmp x,x -> true/false. Not all compares are foldable. 1597 if (LHS == RHS) { 1598 if (CmpInst::isTrueWhenEqual(Pred)) 1599 return ConstantInt::get(GetCompareTy(LHS), 1); 1600 if (CmpInst::isFalseWhenEqual(Pred)) 1601 return ConstantInt::get(GetCompareTy(LHS), 0); 1602 } 1603 1604 // Handle fcmp with constant RHS 1605 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 1606 // If the constant is a nan, see if we can fold the comparison based on it. 1607 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 1608 if (CFP->getValueAPF().isNaN()) { 1609 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 1610 return ConstantInt::getFalse(CFP->getContext()); 1611 assert(FCmpInst::isUnordered(Pred) && 1612 "Comparison must be either ordered or unordered!"); 1613 // True if unordered. 1614 return ConstantInt::getTrue(CFP->getContext()); 1615 } 1616 // Check whether the constant is an infinity. 1617 if (CFP->getValueAPF().isInfinity()) { 1618 if (CFP->getValueAPF().isNegative()) { 1619 switch (Pred) { 1620 case FCmpInst::FCMP_OLT: 1621 // No value is ordered and less than negative infinity. 1622 return ConstantInt::getFalse(CFP->getContext()); 1623 case FCmpInst::FCMP_UGE: 1624 // All values are unordered with or at least negative infinity. 1625 return ConstantInt::getTrue(CFP->getContext()); 1626 default: 1627 break; 1628 } 1629 } else { 1630 switch (Pred) { 1631 case FCmpInst::FCMP_OGT: 1632 // No value is ordered and greater than infinity. 1633 return ConstantInt::getFalse(CFP->getContext()); 1634 case FCmpInst::FCMP_ULE: 1635 // All values are unordered with and at most infinity. 1636 return ConstantInt::getTrue(CFP->getContext()); 1637 default: 1638 break; 1639 } 1640 } 1641 } 1642 } 1643 } 1644 1645 // If the comparison is with the result of a select instruction, check whether 1646 // comparing with either branch of the select always yields the same value. 1647 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 1648 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1649 return V; 1650 1651 // If the comparison is with the result of a phi instruction, check whether 1652 // doing the compare with each incoming phi value yields a common result. 1653 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 1654 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1655 return V; 1656 1657 return 0; 1658} 1659 1660Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1661 const TargetData *TD, const DominatorTree *DT) { 1662 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1663} 1664 1665/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 1666/// the result. If not, this returns null. 1667Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 1668 const TargetData *TD, const DominatorTree *) { 1669 // select true, X, Y -> X 1670 // select false, X, Y -> Y 1671 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 1672 return CB->getZExtValue() ? TrueVal : FalseVal; 1673 1674 // select C, X, X -> X 1675 if (TrueVal == FalseVal) 1676 return TrueVal; 1677 1678 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 1679 return FalseVal; 1680 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 1681 return TrueVal; 1682 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 1683 if (isa<Constant>(TrueVal)) 1684 return TrueVal; 1685 return FalseVal; 1686 } 1687 1688 return 0; 1689} 1690 1691/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 1692/// fold the result. If not, this returns null. 1693Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 1694 const TargetData *TD, const DominatorTree *) { 1695 // The type of the GEP pointer operand. 1696 const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()); 1697 1698 // getelementptr P -> P. 1699 if (NumOps == 1) 1700 return Ops[0]; 1701 1702 if (isa<UndefValue>(Ops[0])) { 1703 // Compute the (pointer) type returned by the GEP instruction. 1704 const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1], 1705 NumOps-1); 1706 const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 1707 return UndefValue::get(GEPTy); 1708 } 1709 1710 if (NumOps == 2) { 1711 // getelementptr P, 0 -> P. 1712 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 1713 if (C->isZero()) 1714 return Ops[0]; 1715 // getelementptr P, N -> P if P points to a type of zero size. 1716 if (TD) { 1717 const Type *Ty = PtrTy->getElementType(); 1718 if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0) 1719 return Ops[0]; 1720 } 1721 } 1722 1723 // Check to see if this is constant foldable. 1724 for (unsigned i = 0; i != NumOps; ++i) 1725 if (!isa<Constant>(Ops[i])) 1726 return 0; 1727 1728 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 1729 (Constant *const*)Ops+1, NumOps-1); 1730} 1731 1732/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 1733static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 1734 // If all of the PHI's incoming values are the same then replace the PHI node 1735 // with the common value. 1736 Value *CommonValue = 0; 1737 bool HasUndefInput = false; 1738 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1739 Value *Incoming = PN->getIncomingValue(i); 1740 // If the incoming value is the phi node itself, it can safely be skipped. 1741 if (Incoming == PN) continue; 1742 if (isa<UndefValue>(Incoming)) { 1743 // Remember that we saw an undef value, but otherwise ignore them. 1744 HasUndefInput = true; 1745 continue; 1746 } 1747 if (CommonValue && Incoming != CommonValue) 1748 return 0; // Not the same, bail out. 1749 CommonValue = Incoming; 1750 } 1751 1752 // If CommonValue is null then all of the incoming values were either undef or 1753 // equal to the phi node itself. 1754 if (!CommonValue) 1755 return UndefValue::get(PN->getType()); 1756 1757 // If we have a PHI node like phi(X, undef, X), where X is defined by some 1758 // instruction, we cannot return X as the result of the PHI node unless it 1759 // dominates the PHI block. 1760 if (HasUndefInput) 1761 return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 1762 1763 return CommonValue; 1764} 1765 1766 1767//=== Helper functions for higher up the class hierarchy. 1768 1769/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 1770/// fold the result. If not, this returns null. 1771static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 1772 const TargetData *TD, const DominatorTree *DT, 1773 unsigned MaxRecurse) { 1774 switch (Opcode) { 1775 case Instruction::Add: return SimplifyAddInst(LHS, RHS, /* isNSW */ false, 1776 /* isNUW */ false, TD, DT, 1777 MaxRecurse); 1778 case Instruction::Sub: return SimplifySubInst(LHS, RHS, /* isNSW */ false, 1779 /* isNUW */ false, TD, DT, 1780 MaxRecurse); 1781 case Instruction::Mul: return SimplifyMulInst(LHS, RHS, TD, DT, MaxRecurse); 1782 case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, TD, DT, MaxRecurse); 1783 case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, TD, DT, MaxRecurse); 1784 case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, TD, DT, MaxRecurse); 1785 case Instruction::Shl: return SimplifyShlInst(LHS, RHS, TD, DT, MaxRecurse); 1786 case Instruction::LShr: return SimplifyLShrInst(LHS, RHS, TD, DT, MaxRecurse); 1787 case Instruction::AShr: return SimplifyAShrInst(LHS, RHS, TD, DT, MaxRecurse); 1788 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse); 1789 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse); 1790 case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse); 1791 default: 1792 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1793 if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 1794 Constant *COps[] = {CLHS, CRHS}; 1795 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 1796 } 1797 1798 // If the operation is associative, try some generic simplifications. 1799 if (Instruction::isAssociative(Opcode)) 1800 if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT, 1801 MaxRecurse)) 1802 return V; 1803 1804 // If the operation is with the result of a select instruction, check whether 1805 // operating on either branch of the select always yields the same value. 1806 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 1807 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT, 1808 MaxRecurse)) 1809 return V; 1810 1811 // If the operation is with the result of a phi instruction, check whether 1812 // operating on all incoming values of the phi always yields the same value. 1813 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 1814 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse)) 1815 return V; 1816 1817 return 0; 1818 } 1819} 1820 1821Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 1822 const TargetData *TD, const DominatorTree *DT) { 1823 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit); 1824} 1825 1826/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 1827/// fold the result. 1828static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1829 const TargetData *TD, const DominatorTree *DT, 1830 unsigned MaxRecurse) { 1831 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 1832 return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 1833 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 1834} 1835 1836Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1837 const TargetData *TD, const DominatorTree *DT) { 1838 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1839} 1840 1841/// SimplifyInstruction - See if we can compute a simplified version of this 1842/// instruction. If not, this returns null. 1843Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 1844 const DominatorTree *DT) { 1845 Value *Result; 1846 1847 switch (I->getOpcode()) { 1848 default: 1849 Result = ConstantFoldInstruction(I, TD); 1850 break; 1851 case Instruction::Add: 1852 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 1853 cast<BinaryOperator>(I)->hasNoSignedWrap(), 1854 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1855 TD, DT); 1856 break; 1857 case Instruction::Sub: 1858 Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 1859 cast<BinaryOperator>(I)->hasNoSignedWrap(), 1860 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1861 TD, DT); 1862 break; 1863 case Instruction::Mul: 1864 Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT); 1865 break; 1866 case Instruction::SDiv: 1867 Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), TD, DT); 1868 break; 1869 case Instruction::UDiv: 1870 Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), TD, DT); 1871 break; 1872 case Instruction::FDiv: 1873 Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), TD, DT); 1874 break; 1875 case Instruction::Shl: 1876 Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), TD, DT); 1877 break; 1878 case Instruction::LShr: 1879 Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), TD, DT); 1880 break; 1881 case Instruction::AShr: 1882 Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), TD, DT); 1883 break; 1884 case Instruction::And: 1885 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT); 1886 break; 1887 case Instruction::Or: 1888 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT); 1889 break; 1890 case Instruction::Xor: 1891 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT); 1892 break; 1893 case Instruction::ICmp: 1894 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 1895 I->getOperand(0), I->getOperand(1), TD, DT); 1896 break; 1897 case Instruction::FCmp: 1898 Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 1899 I->getOperand(0), I->getOperand(1), TD, DT); 1900 break; 1901 case Instruction::Select: 1902 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 1903 I->getOperand(2), TD, DT); 1904 break; 1905 case Instruction::GetElementPtr: { 1906 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 1907 Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT); 1908 break; 1909 } 1910 case Instruction::PHI: 1911 Result = SimplifyPHINode(cast<PHINode>(I), DT); 1912 break; 1913 } 1914 1915 /// If called on unreachable code, the above logic may report that the 1916 /// instruction simplified to itself. Make life easier for users by 1917 /// detecting that case here, returning a safe value instead. 1918 return Result == I ? UndefValue::get(I->getType()) : Result; 1919} 1920 1921/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 1922/// delete the From instruction. In addition to a basic RAUW, this does a 1923/// recursive simplification of the newly formed instructions. This catches 1924/// things where one simplification exposes other opportunities. This only 1925/// simplifies and deletes scalar operations, it does not change the CFG. 1926/// 1927void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 1928 const TargetData *TD, 1929 const DominatorTree *DT) { 1930 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 1931 1932 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 1933 // we can know if it gets deleted out from under us or replaced in a 1934 // recursive simplification. 1935 WeakVH FromHandle(From); 1936 WeakVH ToHandle(To); 1937 1938 while (!From->use_empty()) { 1939 // Update the instruction to use the new value. 1940 Use &TheUse = From->use_begin().getUse(); 1941 Instruction *User = cast<Instruction>(TheUse.getUser()); 1942 TheUse = To; 1943 1944 // Check to see if the instruction can be folded due to the operand 1945 // replacement. For example changing (or X, Y) into (or X, -1) can replace 1946 // the 'or' with -1. 1947 Value *SimplifiedVal; 1948 { 1949 // Sanity check to make sure 'User' doesn't dangle across 1950 // SimplifyInstruction. 1951 AssertingVH<> UserHandle(User); 1952 1953 SimplifiedVal = SimplifyInstruction(User, TD, DT); 1954 if (SimplifiedVal == 0) continue; 1955 } 1956 1957 // Recursively simplify this user to the new value. 1958 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 1959 From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 1960 To = ToHandle; 1961 1962 assert(ToHandle && "To value deleted by recursive simplification?"); 1963 1964 // If the recursive simplification ended up revisiting and deleting 1965 // 'From' then we're done. 1966 if (From == 0) 1967 return; 1968 } 1969 1970 // If 'From' has value handles referring to it, do a real RAUW to update them. 1971 From->replaceAllUsesWith(To); 1972 1973 From->eraseFromParent(); 1974} 1975