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