path: root/lib/Analysis/ValueTracking.cpp

//===- ValueTracking.cpp - Walk computations to compute properties --------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains routines that help analyze properties that chains of
// computations have.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/GlobalVariable.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/MathExtras.h"
#include <cstring>
using namespace llvm;

/// getOpcode - If this is an Instruction or a ConstantExpr, return the
/// opcode value. Otherwise return UserOp1.
static unsigned getOpcode(const Value *V) {
  if (const Instruction *I = dyn_cast<Instruction>(V))
    return I->getOpcode();
  if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    return CE->getOpcode();
  // Use UserOp1 to mean there's no opcode.
  return Instruction::UserOp1;
}


/// ComputeMaskedBits - Determine which of the bits specified in Mask are
/// known to be either zero or one and return them in the KnownZero/KnownOne
/// bit sets.  This code only analyzes bits in Mask, in order to short-circuit
/// processing.
/// NOTE: we cannot consider 'undef' to be "IsZero" here.  The problem is that
/// we cannot optimize based on the assumption that it is zero without changing
/// it to be an explicit zero.  If we don't change it to zero, other code could
/// optimized based on the contradictory assumption that it is non-zero.
/// Because instcombine aggressively folds operations with undef args anyway,
/// this won't lose us code quality.
void llvm::ComputeMaskedBits(Value *V, const APInt &Mask,
                             APInt &KnownZero, APInt &KnownOne,
                             TargetData *TD, unsigned Depth) {
  assert(V && "No Value?");
  assert(Depth <= 6 && "Limit Search Depth");
  uint32_t BitWidth = Mask.getBitWidth();
  assert((V->getType()->isInteger() || isa<PointerType>(V->getType())) &&
         "Not integer or pointer type!");
  assert((!TD || TD->getTypeSizeInBits(V->getType()) == BitWidth) &&
         (!isa<IntegerType>(V->getType()) ||
          V->getType()->getPrimitiveSizeInBits() == BitWidth) &&
         KnownZero.getBitWidth() == BitWidth && 
         KnownOne.getBitWidth() == BitWidth &&
         "V, Mask, KnownOne and KnownZero should have same BitWidth");

  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
    // We know all of the bits for a constant!
    KnownOne = CI->getValue() & Mask;
    KnownZero = ~KnownOne & Mask;
    return;
  }
  // Null is all-zeros.
  if (isa<ConstantPointerNull>(V)) {
    KnownOne.clear();
    KnownZero = Mask;
    return;
  }
  // The address of an aligned GlobalValue has trailing zeros.
  if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
    unsigned Align = GV->getAlignment();
    if (Align == 0 && TD && GV->getType()->getElementType()->isSized()) 
      Align = TD->getPrefTypeAlignment(GV->getType()->getElementType());
    if (Align > 0)
      KnownZero = Mask & APInt::getLowBitsSet(BitWidth,
                                              CountTrailingZeros_32(Align));
    else
      KnownZero.clear();
    KnownOne.clear();
    return;
  }

  KnownZero.clear(); KnownOne.clear();   // Start out not knowing anything.

  if (Depth == 6 || Mask == 0)
    return;  // Limit search depth.

  User *I = dyn_cast<User>(V);
  if (!I) return;

  APInt KnownZero2(KnownZero), KnownOne2(KnownOne);
  switch (getOpcode(I)) {
  default: break;
  case Instruction::And: {
    // If either the LHS or the RHS are Zero, the result is zero.
    ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1);
    APInt Mask2(Mask & ~KnownZero);
    ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD,
                      Depth+1);
    assert