InstructionSimplify.cpp revision eff0581583ef10e2872e9baf537a04b67d992101
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. For example, this does 12// constant folding, and can handle identities like (X&0)->0. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/Analysis/InstructionSimplify.h" 17#include "llvm/Analysis/ConstantFolding.h" 18#include "llvm/Support/ValueHandle.h" 19#include "llvm/Instructions.h" 20#include "llvm/Support/PatternMatch.h" 21using namespace llvm; 22using namespace llvm::PatternMatch; 23 24#define MaxRecursionDepth 3 25 26static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *, 27 unsigned); 28static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *, 29 unsigned); 30 31/// ThreadBinOpOverSelect - In the case of a binary operation with a select 32/// instruction as an operand, try to simplify the binop by seeing whether 33/// evaluating it on both branches of the select results in the same value. 34/// Returns the common value if so, otherwise returns null. 35static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 36 const TargetData *TD, unsigned MaxRecurse) { 37 SelectInst *SI; 38 if (isa<SelectInst>(LHS)) { 39 SI = cast<SelectInst>(LHS); 40 } else { 41 assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 42 SI = cast<SelectInst>(RHS); 43 } 44 45 // Evaluate the BinOp on the true and false branches of the select. 46 Value *TV; 47 Value *FV; 48 if (SI == LHS) { 49 TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, MaxRecurse); 50 FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, MaxRecurse); 51 } else { 52 TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, MaxRecurse); 53 FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, MaxRecurse); 54 } 55 56 // If they simplified to the same value, then return the common value. 57 // If they both failed to simplify then return null. 58 if (TV == FV) 59 return TV; 60 61 // If one branch simplified to undef, return the other one. 62 if (TV && isa<UndefValue>(TV)) 63 return FV; 64 if (FV && isa<UndefValue>(FV)) 65 return TV; 66 67 // If applying the operation did not change the true and false select values, 68 // then the result of the binop is the select itself. 69 if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 70 return SI; 71 72 // If one branch simplified and the other did not, and the simplified 73 // value is equal to the unsimplified one, return the simplified value. 74 // For example, select (cond, X, X & Z) & Z -> X & Z. 75 if ((FV && !TV) || (TV && !FV)) { 76 // Check that the simplified value has the form "X op Y" where "op" is the 77 // same as the original operation. 78 Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 79 if (Simplified && Simplified->getOpcode() == Opcode) { 80 // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 81 // We already know that "op" is the same as for the simplified value. See 82 // if the operands match too. If so, return the simplified value. 83 Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 84 Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 85 Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 86 if (Simplified->getOperand(0) == UnsimplifiedLHS && 87 Simplified->getOperand(1) == UnsimplifiedRHS) 88 return Simplified; 89 if (Simplified->isCommutative() && 90 Simplified->getOperand(1) == UnsimplifiedLHS && 91 Simplified->getOperand(0) == UnsimplifiedRHS) 92 return Simplified; 93 } 94 } 95 96 return 0; 97} 98 99/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 100/// try to simplify the comparison by seeing whether both branches of the select 101/// result in the same value. Returns the common value if so, otherwise returns 102/// null. 103static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 104 Value *RHS, const TargetData *TD, 105 unsigned MaxRecurse) { 106 // Make sure the select is on the LHS. 107 if (!isa<SelectInst>(LHS)) { 108 std::swap(LHS, RHS); 109 Pred = CmpInst::getSwappedPredicate(Pred); 110 } 111 assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 112 SelectInst *SI = cast<SelectInst>(LHS); 113 114 // Now that we have "cmp select(cond, TV, FV), RHS", analyse it. 115 // Does "cmp TV, RHS" simplify? 116 if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, 117 MaxRecurse)) 118 // It does! Does "cmp FV, RHS" simplify? 119 if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, 120 MaxRecurse)) 121 // It does! If they simplified to the same value, then use it as the 122 // result of the original comparison. 123 if (TCmp == FCmp) 124 return TCmp; 125 return 0; 126} 127 128/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 129/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 130/// it on the incoming phi values yields the same result for every value. If so 131/// returns the common value, otherwise returns null. 132static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 133 const TargetData *TD, unsigned MaxRecurse) { 134 PHINode *PI; 135 if (isa<PHINode>(LHS)) { 136 PI = cast<PHINode>(LHS); 137 } else { 138 assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 139 PI = cast<PHINode>(RHS); 140 } 141 142 // Evaluate the BinOp on the incoming phi values. 143 Value *CommonValue = 0; 144 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 145 Value *V = PI == LHS ? 146 SimplifyBinOp(Opcode, PI->getIncomingValue(i), RHS, TD, MaxRecurse) : 147 SimplifyBinOp(Opcode, LHS, PI->getIncomingValue(i), TD, MaxRecurse); 148 // If the operation failed to simplify, or simplified to a different value 149 // to previously, then give up. 150 if (!V || (CommonValue && V != CommonValue)) 151 return 0; 152 CommonValue = V; 153 } 154 155 return CommonValue; 156} 157 158/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 159/// try to simplify the comparison by seeing whether comparing with all of the 160/// incoming phi values yields the same result every time. If so returns the 161/// common result, otherwise returns null. 162static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 163 const TargetData *TD, unsigned MaxRecurse) { 164 // Make sure the phi is on the LHS. 165 if (!isa<PHINode>(LHS)) { 166 std::swap(LHS, RHS); 167 Pred = CmpInst::getSwappedPredicate(Pred); 168 } 169 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 170 PHINode *PI = cast<PHINode>(LHS); 171 172 // Evaluate the BinOp on the incoming phi values. 173 Value *CommonValue = 0; 174 for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 175 Value *V = SimplifyCmpInst(Pred, PI->getIncomingValue(i), RHS, TD, 176 MaxRecurse); 177 // If the operation failed to simplify, or simplified to a different value 178 // to previously, then give up. 179 if (!V || (CommonValue && V != CommonValue)) 180 return 0; 181 CommonValue = V; 182 } 183 184 return CommonValue; 185} 186 187/// SimplifyAddInst - Given operands for an Add, see if we can 188/// fold the result. If not, this returns null. 189Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 190 const TargetData *TD) { 191 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 192 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 193 Constant *Ops[] = { CLHS, CRHS }; 194 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 195 Ops, 2, TD); 196 } 197 198 // Canonicalize the constant to the RHS. 199 std::swap(Op0, Op1); 200 } 201 202 if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 203 // X + undef -> undef 204 if (isa<UndefValue>(Op1C)) 205 return Op1C; 206 207 // X + 0 --> X 208 if (Op1C->isNullValue()) 209 return Op0; 210 } 211 212 // FIXME: Could pull several more out of instcombine. 213 return 0; 214} 215 216/// SimplifyAndInst - Given operands for an And, see if we can 217/// fold the result. If not, this returns null. 218static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 219 unsigned MaxRecurse) { 220 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 221 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 222 Constant *Ops[] = { CLHS, CRHS }; 223 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 224 Ops, 2, TD); 225 } 226 227 // Canonicalize the constant to the RHS. 228 std::swap(Op0, Op1); 229 } 230 231 // X & undef -> 0 232 if (isa<UndefValue>(Op1)) 233 return Constant::getNullValue(Op0->getType()); 234 235 // X & X = X 236 if (Op0 == Op1) 237 return Op0; 238 239 // X & <0,0> = <0,0> 240 if (isa<ConstantAggregateZero>(Op1)) 241 return Op1; 242 243 // X & <-1,-1> = X 244 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) 245 if (CP->isAllOnesValue()) 246 return Op0; 247 248 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) { 249 // X & 0 = 0 250 if (Op1CI->isZero()) 251 return Op1CI; 252 // X & -1 = X 253 if (Op1CI->isAllOnesValue()) 254 return Op0; 255 } 256 257 // A & ~A = ~A & A = 0 258 Value *A, *B; 259 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 260 (match(Op1, m_Not(m_Value(A))) && A == Op0)) 261 return Constant::getNullValue(Op0->getType()); 262 263 // (A | ?) & A = A 264 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 265 (A == Op1 || B == Op1)) 266 return Op1; 267 268 // A & (A | ?) = A 269 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 270 (A == Op0 || B == Op0)) 271 return Op0; 272 273 // (A & B) & A -> A & B 274 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 275 (A == Op1 || B == Op1)) 276 return Op0; 277 278 // A & (A & B) -> A & B 279 if (match(Op1, m_And(m_Value(A), m_Value(B))) && 280 (A == Op0 || B == Op0)) 281 return Op1; 282 283 // If the operation is with the result of a select instruction, check whether 284 // operating on either branch of the select always yields the same value. 285 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 286 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, 287 MaxRecurse-1)) 288 return V; 289 290 // If the operation is with the result of a phi instruction, check whether 291 // operating on all incoming values of the phi always yields the same value. 292 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 293 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, 294 MaxRecurse-1)) 295 return V; 296 297 return 0; 298} 299 300Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD) { 301 return ::SimplifyAndInst(Op0, Op1, TD, MaxRecursionDepth); 302} 303 304/// SimplifyOrInst - Given operands for an Or, see if we can 305/// fold the result. If not, this returns null. 306static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 307 unsigned MaxRecurse) { 308 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 309 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 310 Constant *Ops[] = { CLHS, CRHS }; 311 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 312 Ops, 2, TD); 313 } 314 315 // Canonicalize the constant to the RHS. 316 std::swap(Op0, Op1); 317 } 318 319 // X | undef -> -1 320 if (isa<UndefValue>(Op1)) 321 return Constant::getAllOnesValue(Op0->getType()); 322 323 // X | X = X 324 if (Op0 == Op1) 325 return Op0; 326 327 // X | <0,0> = X 328 if (isa<ConstantAggregateZero>(Op1)) 329 return Op0; 330 331 // X | <-1,-1> = <-1,-1> 332 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) 333 if (CP->isAllOnesValue()) 334 return Op1; 335 336 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) { 337 // X | 0 = X 338 if (Op1CI->isZero()) 339 return Op0; 340 // X | -1 = -1 341 if (Op1CI->isAllOnesValue()) 342 return Op1CI; 343 } 344 345 // A | ~A = ~A | A = -1 346 Value *A, *B; 347 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 348 (match(Op1, m_Not(m_Value(A))) && A == Op0)) 349 return Constant::getAllOnesValue(Op0->getType()); 350 351 // (A & ?) | A = A 352 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 353 (A == Op1 || B == Op1)) 354 return Op1; 355 356 // A | (A & ?) = A 357 if (match(Op1, m_And(m_Value(A), m_Value(B))) && 358 (A == Op0 || B == Op0)) 359 return Op0; 360 361 // (A | B) | A -> A | B 362 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 363 (A == Op1 || B == Op1)) 364 return Op0; 365 366 // A | (A | B) -> A | B 367 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 368 (A == Op0 || B == Op0)) 369 return Op1; 370 371 // If the operation is with the result of a select instruction, check whether 372 // operating on either branch of the select always yields the same value. 373 if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 374 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, 375 MaxRecurse-1)) 376 return V; 377 378 // If the operation is with the result of a phi instruction, check whether 379 // operating on all incoming values of the phi always yields the same value. 380 if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 381 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, 382 MaxRecurse-1)) 383 return V; 384 385 return 0; 386} 387 388Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) { 389 return ::SimplifyOrInst(Op0, Op1, TD, MaxRecursionDepth); 390} 391 392static const Type *GetCompareTy(Value *Op) { 393 return CmpInst::makeCmpResultType(Op->getType()); 394} 395 396/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 397/// fold the result. If not, this returns null. 398static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 399 const TargetData *TD, unsigned MaxRecurse) { 400 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 401 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 402 403 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 404 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 405 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 406 407 // If we have a constant, make sure it is on the RHS. 408 std::swap(LHS, RHS); 409 Pred = CmpInst::getSwappedPredicate(Pred); 410 } 411 412 // ITy - This is the return type of the compare we're considering. 413 const Type *ITy = GetCompareTy(LHS); 414 415 // icmp X, X -> true/false 416 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 417 // because X could be 0. 418 if (LHS == RHS || isa<UndefValue>(RHS)) 419 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 420 421 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 422 // addresses never equal each other! We already know that Op0 != Op1. 423 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 424 isa<ConstantPointerNull>(LHS)) && 425 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 426 isa<ConstantPointerNull>(RHS))) 427 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 428 429 // See if we are doing a comparison with a constant. 430 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 431 // If we have an icmp le or icmp ge instruction, turn it into the 432 // appropriate icmp lt or icmp gt instruction. This allows us to rely on 433 // them being folded in the code below. 434 switch (Pred) { 435 default: break; 436 case ICmpInst::ICMP_ULE: 437 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 438 return ConstantInt::getTrue(CI->getContext()); 439 break; 440 case ICmpInst::ICMP_SLE: 441 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 442 return ConstantInt::getTrue(CI->getContext()); 443 break; 444 case ICmpInst::ICMP_UGE: 445 if (CI->isMinValue(false)) // A >=u MIN -> TRUE 446 return ConstantInt::getTrue(CI->getContext()); 447 break; 448 case ICmpInst::ICMP_SGE: 449 if (CI->isMinValue(true)) // A >=s MIN -> TRUE 450 return ConstantInt::getTrue(CI->getContext()); 451 break; 452 } 453 } 454 455 // If the comparison is with the result of a select instruction, check whether 456 // comparing with either branch of the select always yields the same value. 457 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 458 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, MaxRecurse-1)) 459 return V; 460 461 // If the comparison is with the result of a phi instruction, check whether 462 // doing the compare with each incoming phi value yields a common result. 463 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 464 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, MaxRecurse-1)) 465 return V; 466 467 return 0; 468} 469 470Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 471 const TargetData *TD) { 472 return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth); 473} 474 475/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 476/// fold the result. If not, this returns null. 477static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 478 const TargetData *TD, unsigned MaxRecurse) { 479 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 480 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 481 482 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 483 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 484 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 485 486 // If we have a constant, make sure it is on the RHS. 487 std::swap(LHS, RHS); 488 Pred = CmpInst::getSwappedPredicate(Pred); 489 } 490 491 // Fold trivial predicates. 492 if (Pred == FCmpInst::FCMP_FALSE) 493 return ConstantInt::get(GetCompareTy(LHS), 0); 494 if (Pred == FCmpInst::FCMP_TRUE) 495 return ConstantInt::get(GetCompareTy(LHS), 1); 496 497 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 498 return UndefValue::get(GetCompareTy(LHS)); 499 500 // fcmp x,x -> true/false. Not all compares are foldable. 501 if (LHS == RHS) { 502 if (CmpInst::isTrueWhenEqual(Pred)) 503 return ConstantInt::get(GetCompareTy(LHS), 1); 504 if (CmpInst::isFalseWhenEqual(Pred)) 505 return ConstantInt::get(GetCompareTy(LHS), 0); 506 } 507 508 // Handle fcmp with constant RHS 509 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 510 // If the constant is a nan, see if we can fold the comparison based on it. 511 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 512 if (CFP->getValueAPF().isNaN()) { 513 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 514 return ConstantInt::getFalse(CFP->getContext()); 515 assert(FCmpInst::isUnordered(Pred) && 516 "Comparison must be either ordered or unordered!"); 517 // True if unordered. 518 return ConstantInt::getTrue(CFP->getContext()); 519 } 520 // Check whether the constant is an infinity. 521 if (CFP->getValueAPF().isInfinity()) { 522 if (CFP->getValueAPF().isNegative()) { 523 switch (Pred) { 524 case FCmpInst::FCMP_OLT: 525 // No value is ordered and less than negative infinity. 526 return ConstantInt::getFalse(CFP->getContext()); 527 case FCmpInst::FCMP_UGE: 528 // All values are unordered with or at least negative infinity. 529 return ConstantInt::getTrue(CFP->getContext()); 530 default: 531 break; 532 } 533 } else { 534 switch (Pred) { 535 case FCmpInst::FCMP_OGT: 536 // No value is ordered and greater than infinity. 537 return ConstantInt::getFalse(CFP->getContext()); 538 case FCmpInst::FCMP_ULE: 539 // All values are unordered with and at most infinity. 540 return ConstantInt::getTrue(CFP->getContext()); 541 default: 542 break; 543 } 544 } 545 } 546 } 547 } 548 549 // If the comparison is with the result of a select instruction, check whether 550 // comparing with either branch of the select always yields the same value. 551 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 552 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, MaxRecurse-1)) 553 return V; 554 555 // If the comparison is with the result of a phi instruction, check whether 556 // doing the compare with each incoming phi value yields a common result. 557 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 558 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, MaxRecurse-1)) 559 return V; 560 561 return 0; 562} 563 564Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 565 const TargetData *TD) { 566 return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth); 567} 568 569/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 570/// the result. If not, this returns null. 571Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 572 const TargetData *TD) { 573 // select true, X, Y -> X 574 // select false, X, Y -> Y 575 if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 576 return CB->getZExtValue() ? TrueVal : FalseVal; 577 578 // select C, X, X -> X 579 if (TrueVal == FalseVal) 580 return TrueVal; 581 582 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 583 return FalseVal; 584 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 585 return TrueVal; 586 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 587 if (isa<Constant>(TrueVal)) 588 return TrueVal; 589 return FalseVal; 590 } 591 592 return 0; 593} 594 595 596/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 597/// fold the result. If not, this returns null. 598Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 599 const TargetData *TD) { 600 // getelementptr P -> P. 601 if (NumOps == 1) 602 return Ops[0]; 603 604 // TODO. 605 //if (isa<UndefValue>(Ops[0])) 606 // return UndefValue::get(GEP.getType()); 607 608 // getelementptr P, 0 -> P. 609 if (NumOps == 2) 610 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 611 if (C->isZero()) 612 return Ops[0]; 613 614 // Check to see if this is constant foldable. 615 for (unsigned i = 0; i != NumOps; ++i) 616 if (!isa<Constant>(Ops[i])) 617 return 0; 618 619 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 620 (Constant *const*)Ops+1, NumOps-1); 621} 622 623 624//=== Helper functions for higher up the class hierarchy. 625 626/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 627/// fold the result. If not, this returns null. 628static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 629 const TargetData *TD, unsigned MaxRecurse) { 630 switch (Opcode) { 631 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, MaxRecurse); 632 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, MaxRecurse); 633 default: 634 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 635 if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 636 Constant *COps[] = {CLHS, CRHS}; 637 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 638 } 639 640 // If the operation is with the result of a select instruction, check whether 641 // operating on either branch of the select always yields the same value. 642 if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 643 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, MaxRecurse-1)) 644 return V; 645 646 // If the operation is with the result of a phi instruction, check whether 647 // operating on all incoming values of the phi always yields the same value. 648 if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 649 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, MaxRecurse-1)) 650 return V; 651 652 return 0; 653 } 654} 655 656Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 657 const TargetData *TD) { 658 return ::SimplifyBinOp(Opcode, LHS, RHS, TD, MaxRecursionDepth); 659} 660 661/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 662/// fold the result. 663static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 664 const TargetData *TD, unsigned MaxRecurse) { 665 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 666 return SimplifyICmpInst(Predicate, LHS, RHS, TD, MaxRecurse); 667 return SimplifyFCmpInst(Predicate, LHS, RHS, TD, MaxRecurse); 668} 669 670Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 671 const TargetData *TD) { 672 return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth); 673} 674 675/// SimplifyInstruction - See if we can compute a simplified version of this 676/// instruction. If not, this returns null. 677Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 678 const DominatorTree *DT) { 679 switch (I->getOpcode()) { 680 default: 681 return ConstantFoldInstruction(I, TD); 682 case Instruction::Add: 683 return SimplifyAddInst(I->getOperand(0), I->getOperand(1), 684 cast<BinaryOperator>(I)->hasNoSignedWrap(), 685 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), TD); 686 case Instruction::And: 687 return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD); 688 case Instruction::Or: 689 return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD); 690 case Instruction::ICmp: 691 return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 692 I->getOperand(0), I->getOperand(1), TD); 693 case Instruction::FCmp: 694 return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 695 I->getOperand(0), I->getOperand(1), TD); 696 case Instruction::Select: 697 return SimplifySelectInst(I->getOperand(0), I->getOperand(1), 698 I->getOperand(2), TD); 699 case Instruction::GetElementPtr: { 700 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 701 return SimplifyGEPInst(&Ops[0], Ops.size(), TD); 702 } 703 case Instruction::PHI: 704 return cast<PHINode>(I)->hasConstantValue(DT); 705 } 706} 707 708/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 709/// delete the From instruction. In addition to a basic RAUW, this does a 710/// recursive simplification of the newly formed instructions. This catches 711/// things where one simplification exposes other opportunities. This only 712/// simplifies and deletes scalar operations, it does not change the CFG. 713/// 714void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 715 const TargetData *TD, 716 const DominatorTree *DT) { 717 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 718 719 // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 720 // we can know if it gets deleted out from under us or replaced in a 721 // recursive simplification. 722 WeakVH FromHandle(From); 723 WeakVH ToHandle(To); 724 725 while (!From->use_empty()) { 726 // Update the instruction to use the new value. 727 Use &TheUse = From->use_begin().getUse(); 728 Instruction *User = cast<Instruction>(TheUse.getUser()); 729 TheUse = To; 730 731 // Check to see if the instruction can be folded due to the operand 732 // replacement. For example changing (or X, Y) into (or X, -1) can replace 733 // the 'or' with -1. 734 Value *SimplifiedVal; 735 { 736 // Sanity check to make sure 'User' doesn't dangle across 737 // SimplifyInstruction. 738 AssertingVH<> UserHandle(User); 739 740 SimplifiedVal = SimplifyInstruction(User, TD, DT); 741 if (SimplifiedVal == 0) continue; 742 } 743 744 // Recursively simplify this user to the new value. 745 ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 746 From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 747 To = ToHandle; 748 749 assert(ToHandle && "To value deleted by recursive simplification?"); 750 751 // If the recursive simplification ended up revisiting and deleting 752 // 'From' then we're done. 753 if (From == 0) 754 return; 755 } 756 757 // If 'From' has value handles referring to it, do a real RAUW to update them. 758 From->replaceAllUsesWith(To); 759 760 From->eraseFromParent(); 761} 762