InstructionSimplify.cpp revision d06094f0682f2ede03caff4892b1a57469896d48
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/Instructions.h" 19#include "llvm/Support/PatternMatch.h" 20using namespace llvm; 21using namespace llvm::PatternMatch; 22 23/// SimplifyAndInst - Given operands for an And, see if we can 24/// fold the result. If not, this returns null. 25Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, 26 const TargetData *TD) { 27 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 28 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 29 Constant *Ops[] = { CLHS, CRHS }; 30 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 31 Ops, 2, TD); 32 } 33 34 // Canonicalize the constant to the RHS. 35 std::swap(Op0, Op1); 36 } 37 38 // X & undef -> 0 39 if (isa<UndefValue>(Op1)) 40 return Constant::getNullValue(Op0->getType()); 41 42 // X & X = X 43 if (Op0 == Op1) 44 return Op0; 45 46 // X & <0,0> = <0,0> 47 if (isa<ConstantAggregateZero>(Op1)) 48 return Op1; 49 50 // X & <-1,-1> = X 51 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) 52 if (CP->isAllOnesValue()) 53 return Op0; 54 55 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) { 56 // X & 0 = 0 57 if (Op1CI->isZero()) 58 return Op1CI; 59 // X & -1 = X 60 if (Op1CI->isAllOnesValue()) 61 return Op0; 62 } 63 64 // A & ~A = ~A & A = 0 65 Value *A, *B; 66 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 67 (match(Op1, m_Not(m_Value(A))) && A == Op0)) 68 return Constant::getNullValue(Op0->getType()); 69 70 // (A | ?) & A = A 71 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 72 (A == Op1 || B == Op1)) 73 return Op1; 74 75 // A & (A | ?) = A 76 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 77 (A == Op0 || B == Op0)) 78 return Op0; 79 80 return 0; 81} 82 83/// SimplifyOrInst - Given operands for an Or, see if we can 84/// fold the result. If not, this returns null. 85Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, 86 const TargetData *TD) { 87 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 88 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 89 Constant *Ops[] = { CLHS, CRHS }; 90 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 91 Ops, 2, TD); 92 } 93 94 // Canonicalize the constant to the RHS. 95 std::swap(Op0, Op1); 96 } 97 98 // X | undef -> -1 99 if (isa<UndefValue>(Op1)) 100 return Constant::getAllOnesValue(Op0->getType()); 101 102 // X | X = X 103 if (Op0 == Op1) 104 return Op0; 105 106 // X | <0,0> = X 107 if (isa<ConstantAggregateZero>(Op1)) 108 return Op0; 109 110 // X | <-1,-1> = <-1,-1> 111 if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) 112 if (CP->isAllOnesValue()) 113 return Op1; 114 115 if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) { 116 // X | 0 = X 117 if (Op1CI->isZero()) 118 return Op0; 119 // X | -1 = -1 120 if (Op1CI->isAllOnesValue()) 121 return Op1CI; 122 } 123 124 // A | ~A = ~A | A = -1 125 Value *A, *B; 126 if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 127 (match(Op1, m_Not(m_Value(A))) && A == Op0)) 128 return Constant::getAllOnesValue(Op0->getType()); 129 130 // (A & ?) | A = A 131 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 132 (A == Op1 || B == Op1)) 133 return Op1; 134 135 // A | (A & ?) = A 136 if (match(Op1, m_And(m_Value(A), m_Value(B))) && 137 (A == Op0 || B == Op0)) 138 return Op0; 139 140 return 0; 141} 142 143 144 145 146static const Type *GetCompareTy(Value *Op) { 147 return CmpInst::makeCmpResultType(Op->getType()); 148} 149 150 151/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 152/// fold the result. If not, this returns null. 153Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 154 const TargetData *TD) { 155 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 156 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 157 158 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 159 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 160 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 161 162 // If we have a constant, make sure it is on the RHS. 163 std::swap(LHS, RHS); 164 Pred = CmpInst::getSwappedPredicate(Pred); 165 } 166 167 // ITy - This is the return type of the compare we're considering. 168 const Type *ITy = GetCompareTy(LHS); 169 170 // icmp X, X -> true/false 171 if (LHS == RHS) 172 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 173 174 if (isa<UndefValue>(RHS)) // X icmp undef -> undef 175 return UndefValue::get(ITy); 176 177 // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 178 // addresses never equal each other! We already know that Op0 != Op1. 179 if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 180 isa<ConstantPointerNull>(LHS)) && 181 (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 182 isa<ConstantPointerNull>(RHS))) 183 return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 184 185 // See if we are doing a comparison with a constant. 186 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 187 // If we have an icmp le or icmp ge instruction, turn it into the 188 // appropriate icmp lt or icmp gt instruction. This allows us to rely on 189 // them being folded in the code below. 190 switch (Pred) { 191 default: break; 192 case ICmpInst::ICMP_ULE: 193 if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 194 return ConstantInt::getTrue(CI->getContext()); 195 break; 196 case ICmpInst::ICMP_SLE: 197 if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 198 return ConstantInt::getTrue(CI->getContext()); 199 break; 200 case ICmpInst::ICMP_UGE: 201 if (CI->isMinValue(false)) // A >=u MIN -> TRUE 202 return ConstantInt::getTrue(CI->getContext()); 203 break; 204 case ICmpInst::ICMP_SGE: 205 if (CI->isMinValue(true)) // A >=s MIN -> TRUE 206 return ConstantInt::getTrue(CI->getContext()); 207 break; 208 } 209 } 210 211 212 return 0; 213} 214 215/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 216/// fold the result. If not, this returns null. 217Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 218 const TargetData *TD) { 219 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 220 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 221 222 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 223 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 224 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 225 226 // If we have a constant, make sure it is on the RHS. 227 std::swap(LHS, RHS); 228 Pred = CmpInst::getSwappedPredicate(Pred); 229 } 230 231 // Fold trivial predicates. 232 if (Pred == FCmpInst::FCMP_FALSE) 233 return ConstantInt::get(GetCompareTy(LHS), 0); 234 if (Pred == FCmpInst::FCMP_TRUE) 235 return ConstantInt::get(GetCompareTy(LHS), 1); 236 237 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 238 return UndefValue::get(GetCompareTy(LHS)); 239 240 // fcmp x,x -> true/false. Not all compares are foldable. 241 if (LHS == RHS) { 242 if (CmpInst::isTrueWhenEqual(Pred)) 243 return ConstantInt::get(GetCompareTy(LHS), 1); 244 if (CmpInst::isFalseWhenEqual(Pred)) 245 return ConstantInt::get(GetCompareTy(LHS), 0); 246 } 247 248 // Handle fcmp with constant RHS 249 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 250 // If the constant is a nan, see if we can fold the comparison based on it. 251 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 252 if (CFP->getValueAPF().isNaN()) { 253 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 254 return ConstantInt::getFalse(CFP->getContext()); 255 assert(FCmpInst::isUnordered(Pred) && 256 "Comparison must be either ordered or unordered!"); 257 // True if unordered. 258 return ConstantInt::getTrue(CFP->getContext()); 259 } 260 } 261 } 262 263 return 0; 264} 265 266//=== Helper functions for higher up the class hierarchy. 267 268/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 269/// fold the result. If not, this returns null. 270Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 271 const TargetData *TD) { 272 switch (Opcode) { 273 case Instruction::And: return SimplifyAndInst(LHS, RHS, TD); 274 case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD); 275 default: 276 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 277 if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 278 Constant *COps[] = {CLHS, CRHS}; 279 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 280 } 281 return 0; 282 } 283} 284 285/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 286/// fold the result. 287Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 288 const TargetData *TD) { 289 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 290 return SimplifyICmpInst(Predicate, LHS, RHS, TD); 291 return SimplifyFCmpInst(Predicate, LHS, RHS, TD); 292} 293 294