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