lib/Analysis/InstructionSimplify.cpp

   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"
  20 using namespace llvm;
  21 using namespace llvm::PatternMatch;
  22
  23 /// SimplifyAndInst - Given operands for an And, see if we can
  24 /// fold the result.  If not, this returns null.
  25 Value *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.
  85 Value *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
 146 static 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.
 153 Value *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.
 217 Value *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.
 270 Value *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.
 287 Value *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
 295 /// SimplifyInstruction - See if we can compute a simplified version of this
 296 /// instruction.  If not, this returns null.
 297 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD) {
 298   switch (I->getOpcode()) {
 299   default:
 300     return ConstantFoldInstruction(I, TD);
 301   case Instruction::And:
 302     return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD);
 303   case Instruction::Or:
 304     return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD);
 305   case Instruction::ICmp:
 306     return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
 307                             I->getOperand(0), I->getOperand(1), TD);
 308   case Instruction::FCmp:
 309     return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
 310                             I->getOperand(0), I->getOperand(1), TD);
 311   }
 312 }
 313