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