InstructionSimplify.cpp revision 204642
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/// SimplifyAddInst - Given operands for an Add, see if we can 25/// fold the result. If not, this returns null. 26Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 27 const TargetData *TD) { 28 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 29 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 30 Constant *Ops[] = { CLHS, CRHS }; 31 return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 32 Ops, 2, TD); 33 } 34 35 // Canonicalize the constant to the RHS. 36 std::swap(Op0, Op1); 37 } 38 39 if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 40 // X + undef -> undef 41 if (isa<UndefValue>(Op1C)) 42 return Op1C; 43 44 // X + 0 --> X 45 if (Op1C->isNullValue()) 46 return Op0; 47 } 48 49 // FIXME: Could pull several more out of instcombine. 50 return 0; 51} 52 53/// SimplifyAndInst - Given operands for an And, see if we can 54/// fold the result. If not, this returns null. 55Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD) { 56 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 57 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 58 Constant *Ops[] = { CLHS, CRHS }; 59 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 60 Ops, 2, TD); 61 } 62 63 // Canonicalize the constant to the RHS. 64 std::swap(Op0, Op1); 65 } 66 67 // X & undef -> 0 68 if (isa<UndefValue>(Op1)) 69 return Constant::getNullValue(Op0->getType()); 70 71 // X & X = X 72 if (Op0 == Op1) 73 return Op0; 74 75 // X & <0,0> = <0,0> 76 if (isa<ConstantAggregateZero>(Op1)) 77 return Op1; 78 79 // X & <-1,-1> = X 80 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) 81 if (CP->isAllOnesValue()) 82 return Op0; 83 84 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) { 85 // X & 0 = 0 86 if (Op1CI->isZero()) 87 return Op1CI; 88 // X & -1 = X 89 if (Op1CI->isAllOnesValue()) 90 return Op0; 91 } 92 93 // A & ~A = ~A & A = 0 94 Value *A, *B; 95 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 96 (match(Op1, m_Not(m_Value(A))) && A == Op0)) 97 return Constant::getNullValue(Op0->getType()); 98 99 // (A | ?) & A = A 100 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 101 (A == Op1 || B == Op1)) 102 return Op1; 103 104 // A & (A | ?) = A 105 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 106 (A == Op0 || B == Op0)) 107 return Op0; 108 109 return 0; 110} 111 112/// SimplifyOrInst - Given operands for an Or, see if we can 113/// fold the result. If not, this returns null. 114Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) { 115 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 116 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 117 Constant *Ops[] = { CLHS, CRHS }; 118 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 119 Ops, 2, TD); 120 } 121 122 // Canonicalize the constant to the RHS. 123 std::swap(Op0, Op1); 124 } 125 126 // X | undef -> -1 127 if (isa<UndefValue>(Op1)) 128 return Constant::getAllOnesValue(Op0->getType()); 129 130 // X | X = X 131 if (Op0 == Op1) 132 return Op0; 133 134 // X | <0,0> = X 135 if (isa<ConstantAggregateZero>(Op1)) 136 return Op0; 137 138 // X | <-1,-1> = <-1,-1> 139 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) 140 if (CP->isAllOnesValue()) 141 return Op1; 142 143 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) { 144 // X | 0 = X 145 if (Op1CI->isZero()) 146 return Op0; 147 // X | -1 = -1 148 if (Op1CI->isAllOnesValue()) 149 return Op1CI; 150 } 151 152 // A | ~A = ~A | A = -1 153 Value *A, *B; 154 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 155 (match(Op1, m_Not(m_Value(A))) && A == Op0)) 156 return Constant::getAllOnesValue(Op0->getType()); 157 158 // (A & ?) | A = A 159 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 160 (A == Op1 || B == Op1)) 161 return Op1; 162 163 // A | (A & ?) = A 164 if (match(Op1, m_And(m_Value(A), m_Value(B))) && 165 (A == Op0 || B == Op0)) 166 return Op0; 167 168 return 0; 169} 170 171 172static const Type *GetCompareTy(Value *Op) { 173 return CmpInst::makeCmpResultType(Op->getType()); 174} 175 176 177/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 178/// fold the result. If not, this returns null. 179Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 180 const TargetData *TD) { 181 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 182 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 183 184 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 185 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 186 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 187 188 // If we have a constant, make sure it is on the RHS. 189 std::swap(LHS, RHS); 190 Pred = CmpInst::getSwappedPredicate(Pred); 191 } 192 193 // ITy - This is the return type of the compare we're considering. 194 const Type *ITy = GetCompareTy(LHS); 195 196 // icmp X, X -> true/false 197 if (LHS == RHS) 198 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 199 200 if (isa<UndefValue>(RHS)) // X icmp undef -> undef 201 return UndefValue::get(ITy); 202 203 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 204 // addresses never equal each other! We already know that Op0 != Op1. 205 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 206 isa<ConstantPointerNull>(LHS)) && 207 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 208 isa<ConstantPointerNull>(RHS))) 209 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 210 211 // See if we are doing a comparison with a constant. 212 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 213 // If we have an icmp le or icmp ge instruction, turn it into the 214 // appropriate icmp lt or icmp gt instruction. This allows us to rely on 215 // them being folded in the code below. 216 switch (Pred) { 217 default: break; 218 case ICmpInst::ICMP_ULE: 219 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 220 return ConstantInt::getTrue(CI->getContext()); 221 break; 222 case ICmpInst::ICMP_SLE: 223 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 224 return ConstantInt::getTrue(CI->getContext()); 225 break; 226 case ICmpInst::ICMP_UGE: 227 if (CI->isMinValue(false)) // A >=u MIN -> TRUE 228 return ConstantInt::getTrue(CI->getContext()); 229 break; 230 case ICmpInst::ICMP_SGE: 231 if (CI->isMinValue(true)) // A >=s MIN -> TRUE 232 return ConstantInt::getTrue(CI->getContext()); 233 break; 234 } 235 } 236 237 238 return 0; 239} 240 241/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 242/// fold the result. If not, this returns null. 243Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 244 const TargetData *TD) { 245 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 246 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 247 248 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 249 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 250 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 251 252 // If we have a constant, make sure it is on the RHS. 253 std::swap(LHS, RHS); 254 Pred = CmpInst::getSwappedPredicate(Pred); 255 } 256 257 // Fold trivial predicates. 258 if (Pred == FCmpInst::FCMP_FALSE) 259 return ConstantInt::get(GetCompareTy(LHS), 0); 260 if (Pred == FCmpInst::FCMP_TRUE) 261 return ConstantInt::get(GetCompareTy(LHS), 1); 262 263 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 264 return UndefValue::get(GetCompareTy(LHS)); 265 266 // fcmp x,x -> true/false. Not all compares are foldable. 267 if (LHS == RHS) { 268 if (CmpInst::isTrueWhenEqual(Pred)) 269 return ConstantInt::get(GetCompareTy(LHS), 1); 270 if (CmpInst::isFalseWhenEqual(Pred)) 271 return ConstantInt::get(GetCompareTy(LHS), 0); 272 } 273 274 // Handle fcmp with constant RHS 275 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 276 // If the constant is a nan, see if we can fold the comparison based on it. 277 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 278 if (CFP->getValueAPF().isNaN()) { 279 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 280 return ConstantInt::getFalse(CFP->getContext()); 281 assert(FCmpInst::isUnordered(Pred) && 282 "Comparison must be either ordered or unordered!"); 283 // True if unordered. 284 return ConstantInt::getTrue(CFP->getContext()); 285 } 286 // Check whether the constant is an infinity. 287 if (CFP->getValueAPF().isInfinity()) { 288 if (CFP->getValueAPF().isNegative()) { 289 switch (Pred) { 290 case FCmpInst::FCMP_OLT: 291 // No value is ordered and less than negative infinity. 292 return ConstantInt::getFalse(CFP->getContext()); 293 case FCmpInst::FCMP_UGE: 294 // All values are unordered with or at least negative infinity. 295 return ConstantInt::getTrue(CFP->getContext()); 296 default: 297 break; 298 } 299 } else { 300 switch (Pred) { 301 case FCmpInst::FCMP_OGT: 302 // No value is ordered and greater than infinity. 303 return ConstantInt::getFalse(CFP->getContext()); 304 case FCmpInst::FCMP_ULE: 305 // All values are unordered with and at most infinity. 306 return ConstantInt::getTrue(CFP->getContext()); 307 default: 308 break; 309 } 310 } 311 } 312 } 313 } 314 315 return 0; 316} 317 318/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 319/// fold the result. If not, this returns null. 320Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 321 const TargetData *TD) { 322 // getelementptr P -> P. 323 if (NumOps == 1) 324 return Ops[0]; 325 326 // TODO. 327 //if (isa<UndefValue>(Ops[0])) 328 // return UndefValue::get(GEP.getType()); 329 330 // getelementptr P, 0 -> P. 331 if (NumOps == 2) 332 if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 333 if (C->isZero()) 334 return Ops[0]; 335 336 // Check to see if this is constant foldable. 337 for (unsigned i = 0; i != NumOps; ++i) 338 if (!isa<Constant>(Ops[i])) 339 return 0; 340 341 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 342 (Constant *const*)Ops+1, NumOps-1); 343} 344 345 346//=== Helper functions for higher up the class hierarchy. 347 348/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 349/// fold the result. If not, this returns null. 350Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 351 const TargetData *TD) { 352 switch (Opcode) { 353 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD); 354 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD); 355 default: 356 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 357 if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 358 Constant *COps[] = {CLHS, CRHS}; 359 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 360 } 361 return 0; 362 } 363} 364 365/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 366/// fold the result. 367Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 368 const TargetData *TD) { 369 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 370 return SimplifyICmpInst(Predicate, LHS, RHS, TD); 371 return SimplifyFCmpInst(Predicate, LHS, RHS, TD); 372} 373 374 375/// SimplifyInstruction - See if we can compute a simplified version of this 376/// instruction. If not, this returns null. 377Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD) { 378 switch (I->getOpcode()) { 379 default: 380 return ConstantFoldInstruction(I, TD); 381 case Instruction::Add: 382 return SimplifyAddInst(I->getOperand(0), I->getOperand(1), 383 cast<BinaryOperator>(I)->hasNoSignedWrap(), 384 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), TD); 385 case Instruction::And: 386 return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD); 387 case Instruction::Or: 388 return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD); 389 case Instruction::ICmp: 390 return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 391 I->getOperand(0), I->getOperand(1), TD); 392 case Instruction::FCmp: 393 return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 394 I->getOperand(0), I->getOperand(1), TD); 395 case Instruction::GetElementPtr: { 396 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 397 return SimplifyGEPInst(&Ops[0], Ops.size(), TD); 398 } 399 } 400} 401 402/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 403/// delete the From instruction. In addition to a basic RAUW, this does a 404/// recursive simplification of the newly formed instructions. This catches 405/// things where one simplification exposes other opportunities. This only 406/// simplifies and deletes scalar operations, it does not change the CFG. 407/// 408void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 409 const TargetData *TD) { 410 assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 411 412 // FromHandle - This keeps a weakvh on the from value so that we can know if 413 // it gets deleted out from under us in a recursive simplification. 414 WeakVH FromHandle(From); 415 416 while (!From->use_empty()) { 417 // Update the instruction to use the new value. 418 Use &U = From->use_begin().getUse(); 419 Instruction *User = cast<Instruction>(U.getUser()); 420 U = To; 421 422 // See if we can simplify it. 423 if (Value *V = SimplifyInstruction(User, TD)) { 424 // Recursively simplify this. 425 ReplaceAndSimplifyAllUses(User, V, TD); 426 427 // If the recursive simplification ended up revisiting and deleting 'From' 428 // then we're done. 429 if (FromHandle == 0) 430 return; 431 } 432 } 433 From->eraseFromParent(); 434} 435 436