<commit_before>//===- InstCombineCasts.cpp -----------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the visit functions for cast operations.
//
//===----------------------------------------------------------------------===//

#include "InstCombine.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Support/PatternMatch.h"
using namespace llvm;
using namespace PatternMatch;

/// DecomposeSimpleLinearExpr - Analyze 'Val', seeing if it is a simple linear
/// expression.  If so, decompose it, returning some value X, such that Val is
/// X*Scale+Offset.
///
static Value *DecomposeSimpleLinearExpr(Value *Val, unsigned &Scale,
                                        int &Offset) {
  assert(Val->getType()->isInteger(32) && "Unexpected allocation size type!");
  if (ConstantInt *CI = dyn_cast<ConstantInt>(Val)) {
    Offset = CI->getZExtValue();
    Scale  = 0;
    return ConstantInt::get(Type::getInt32Ty(Val->getContext()), 0);
  }
  
  if (BinaryOperator *I = dyn_cast<BinaryOperator>(Val)) {
    if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
      if (I->getOpcode() == Instruction::Shl) {
        // This is a value scaled by '1 << the shift amt'.
        Scale = 1U << RHS->getZExtValue();
        Offset = 0;
        return I->getOperand(0);
      }
      
      if (I->getOpcode() == Instruction::Mul) {
        // This value is scaled by 'RHS'.
        Scale = RHS->getZExtValue();
        Offset = 0;
        return I->getOperand(0);
      }
      
      if (I->getOpcode() == Instruction::Add) {
        // We have X+C.  Check to see if we really have (X*C2)+C1, 
        // where C1 is divisible by C2.
        unsigned SubScale;
        Value *SubVal = 
          DecomposeSimpleLinearExpr(I->getOperand(0), SubScale, Offset);
        Offset += RHS->getZExtValue();
        Scale = SubScale;
        return SubVal;
      }
    }
  }

  // Otherwise, we can't look past this.
  Scale = 1;
  Offset = 0;
  return Val;
}

/// PromoteCastOfAllocation - If we find a cast of an allocation instruction,
/// try to eliminate the cast by moving the type information into the alloc.
Instruction *InstCombiner::PromoteCastOfAllocation(BitCastInst &CI,
                                                   AllocaInst &AI) {
  // This requires TargetData to get the alloca alignment and size information.
  if (!TD) return 0;

  const PointerType *PTy = cast<PointerType>(CI.getType());
  
  BuilderTy AllocaBuilder(*Builder);
  AllocaBuilder.SetInsertPoint(AI.getParent(), &AI);

  // Get the type really allocated and the type casted to.
  const Type *AllocElTy = AI.getAllocatedType();
  const Type *CastElTy = PTy->getElementType();
  if (!AllocElTy->isSized() || !CastElTy->isSized()) return 0;

  unsigned AllocElTyAlign = TD->getABITypeAlignment(AllocElTy);
  unsigned CastElTyAlign = TD->getABITypeAlignment(CastElTy);
  if (CastElTyAlign < AllocElTyAlign) return 0;

  // If the allocation has multiple uses, only promote it if we are strictly
  // increasing the alignment of the resultant allocation.  If we keep it the
  // same, we open the door to infinite loops of various kinds.  (A reference
  // from a dbg.declare doesn't count as a use for this purpose.)
  if (!AI.hasOneUse() && !hasOneUsePlusDeclare(&AI) &&
      CastElTyAlign == AllocElTyAlign) return 0;

  uint64_t AllocElTySize = TD->getTypeAllocSize(AllocElTy);
  uint64_t CastElTySize = TD->getTypeAllocSize(CastElTy);
  if (CastElTySize == 0 || AllocElTySize == 0) return 0;

  // See if we can satisfy the modulus by pulling a scale out of the array
  // size argument.
  unsigned ArraySizeScale;
  int ArrayOffset;
  Value *NumElements = // See if the array size is a decomposable linear expr.
    DecomposeSimpleLinearExpr(AI.getOperand(0), ArraySizeScale, ArrayOffset);
 
  // If we can now satisfy the modulus, by using a non-1 scale, we really can
  // do the xform.
  if ((AllocElTySize*ArraySizeScale) % CastElTySize != 0 ||
      (AllocElTySize*ArrayOffset   ) % CastElTySize != 0) return 0;

  unsigned Scale = (AllocElTySize*ArraySizeScale)/CastElTySize;
  Value *Amt = 0;
  if (Scale == 1) {
    Amt = NumElements;
  } else {
    Amt = ConstantInt::get(Type::getInt32Ty(CI.getContext()), Scale);
    // Insert before the alloca, not before the cast.
    Amt = AllocaBuilder.CreateMul(Amt, NumElements, "tmp");
  }
  
  if (int Offset = (AllocElTySize*ArrayOffset)/CastElTySize) {
    Value *Off = ConstantInt::get(Type::getInt32Ty(CI.getContext()),
                                  Offset, true);
    Amt = AllocaBuilder.CreateAdd(Amt, Off, "tmp");
  }
  
  AllocaInst *New = AllocaBuilder.CreateAlloca(CastElTy, Amt);
  New->setAlignment(AI.getAlignment());
  New->takeName(&AI);
  
  // If the allocation has one real use plus a dbg.declare, just remove the
  // declare.
  if (DbgDeclareInst *DI = hasOneUsePlusDeclare(&AI)) {
    EraseInstFromFunction(*(Instruction*)DI);
  }
  // If the allocation has multiple real uses, insert a cast and change all
  // things that used it to use the new cast.  This will also hack on CI, but it
  // will die soon.
  else if (!AI.hasOneUse()) {
    // New is the allocation instruction, pointer typed. AI is the original
    // allocation instruction, also pointer typed. Thus, cast to use is BitCast.
    Value *NewCast = AllocaBuilder.CreateBitCast(New, AI.getType(), "tmpcast");
    AI.replaceAllUsesWith(NewCast);
  }
  return ReplaceInstUsesWith(CI, New);
}


/// CanEvaluateTruncated - Return true if we can evaluate the specified
/// expression tree as type Ty instead of its larger type, and arrive with the
/// same value.  This is used by code that tries to eliminate truncates.
///
/// Ty will always be a type smaller than V.  We should return true if trunc(V)
/// can be computed by computing V in the smaller type.  If V is an instruction,
/// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only
/// makes sense if x and y can be efficiently truncated.
///
static bool CanEvaluateTruncated(Value *V, const Type *Ty) {
  // We can always evaluate constants in another type.
  if (isa<Constant>(V))
    return true;
  
  Instruction *I = dyn_cast<Instruction>(V);
  if (!I) return false;
  
  const Type *OrigTy = V->getType();
  
  // If this is an extension from the dest type, we can eliminate it.
  if ((isa<ZExtInst>(I) || isa<SExtInst>(I)) && 
      I->getOperand(0)->getType() == Ty)
    return true;

  // We can't extend or shrink something that has multiple uses: doing so would
  // require duplicating the instruction in general, which isn't profitable.
  if (!I->hasOneUse()) return false;

  unsigned Opc = I->getOpcode();
  switch (Opc) {
  case Instruction::Add:
  case Instruction::Sub:
  case Instruction::Mul:
  case Instruction::And:
  case Instruction::Or:
  case Instruction::Xor:
    // These operators can all arbitrarily be extended or truncated.
    return CanEvaluateTruncated(I->getOperand(0), Ty) &&
           CanEvaluateTruncated(I->getOperand(1), Ty);

  case Instruction::UDiv:
  case Instruction::URem: {
    // UDiv and URem can be truncated if all the truncated bits are zero.
    uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
    uint32_t BitWidth = Ty->getScalarSizeInBits();
    if (BitWidth < OrigBitWidth) {
      APInt Mask = APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth);
      if (MaskedValueIsZero(I->getOperand(0), Mask) &&
          MaskedValueIsZero(I->getOperand(1), Mask)) {
        return CanEvaluateTruncated(I->getOperand(0), Ty) &&
               CanEvaluateTruncated(I->getOperand(1), Ty);
      }
    }
    break;
  }
  case Instruction::Shl:
    // If we are truncating the result of this SHL, and if it's a shift of a
    // constant amount, we can always perform a SHL in a smaller type.
    if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
      uint32_t BitWidth = Ty->getScalarSizeInBits();
      if (CI->getLimitedValue(BitWidth) < BitWidth)
        return CanEvaluateTruncated(I->getOperand(0), Ty);
    }
    break;
  case Instruction::LShr:
    // If this is a truncate of a logical shr, we can truncate it to a smaller
    // lshr iff we know that the bits we would otherwise be shifting in are
    // already zeros.
    if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
      uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
      uint32_t BitWidth = Ty->getScalarSizeInBits();
      if (MaskedValueIsZero(I->getOperand(0),
            APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) &&
          CI->getLimitedValue(BitWidth) < BitWidth) {
        return CanEvaluateTruncated(I->getOperand(0), Ty);
      }
    }
    break;
  case Instruction::Trunc:
    // trunc(trunc(x)) -> trunc(x)
    return true;
  case Instruction::Select: {
    SelectInst *SI = cast<SelectInst>(I);
    return CanEvaluateTruncated(SI->getTrueValue(), Ty) &&
           CanEvaluateTruncated(SI->getFalseValue(), Ty);
  }
  case Instruction::PHI: {
    // We can change a phi if we can change all operands.  Note that we never
    // get into trouble with cyclic PHIs here because we only consider
    // instructions with a single use.
    PHINode *PN = cast<PHINode>(I);
    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
      if (!CanEvaluateTruncated(PN->getIncomingValue(i), Ty))
        return false;
    return true;
  }
  default:
    // TODO: Can handle more cases here.
    break;
  }
  
  return false;
}

/// GetLeadingZeros - Compute the number of known-zero leading bits.
static unsigned GetLeadingZeros(Value *V, const TargetData *TD) {
  unsigned Bits = V->getType()->getScalarSizeInBits();
  APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
  ComputeMaskedBits(V, APInt::getAllOnesValue(Bits), KnownZero, KnownOne, TD);
  return KnownZero.countLeadingOnes();
}

/// CanEvaluateZExtd - Determine if the specified value can be computed in the
/// specified wider type and produce the same low bits.  If not, return -1.  If
/// it is possible, return the number of high bits that are known to be zero in
/// the promoted value.
static int CanEvaluateZExtd(Value *V, const Type *Ty,unsigned &NumCastsRemoved,
                            const TargetData *TD) {
  const Type *OrigTy = V->getType();

  if (isa<Constant>(V)) {
    unsigned Extended = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();

    // Constants can always be zero ext'd, even if it requires a ConstantExpr.
    if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
      return Extended + CI->getValue().countLeadingZeros();
    return Extended;
  }
  
  Instruction *I = dyn_cast<Instruction>(V);
  if (!I) return -1;
  
  // If the input is a truncate from the destination type, we can trivially
  // eliminate it, and this will remove a cast overall.
  if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty) {
    // If the first operand is itself a cast, and is eliminable, do not count
    // this as an eliminable cast.  We would prefer to eliminate those two
    // casts first.
    if (!isa<CastInst>(I->getOperand(0)) && I->hasOneUse())
      ++NumCastsRemoved;
    
    // Figure out the number of known-zero bits coming in.
    return GetLeadingZeros(I->getOperand(0), TD);
  }
  
  // We can't extend or shrink something that has multiple uses: doing so would
  // require duplicating the instruction in general, which isn't profitable.
  if (!I->hasOneUse()) return -1;
  
  int Tmp1, Tmp2;
  unsigned Opc = I->getOpcode();
  switch (Opc) {
  case Instruction::And:
    Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
    if (Tmp1 == -1) return -1;
    Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    if (Tmp2 == -1) return -1;
    return std::max(Tmp1, Tmp2);
  case Instruction::Or:
  case Instruction::Xor:
    Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
    if (Tmp1 == -1) return -1;
    Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    return std::min(Tmp1, Tmp2);

  case Instruction::Add:
  case Instruction::Sub:
  case Instruction::Mul:
    Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
    if (Tmp1 == -1) return -1;
    Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    if (Tmp2 == -1) return -1;
    return 0;
      
  //case Instruction::Shl:
  //case Instruction::LShr:
  case Instruction::ZExt:
    // zext(zext(x)) -> zext(x).  Since we're replacing it, it isn't eliminated.
    Tmp1 = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();
    return GetLeadingZeros(I, TD)+Tmp1;
      
  //case Instruction::SExt:  zext(sext(x)) -> sext(x) with no upper bits known.
  //case Instruction::Trunc:
  case Instruction::Select:
    Tmp1 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    if (Tmp1 == -1) return -1;
    Tmp2 = CanEvaluateZExtd(I->getOperand(2), Ty, NumCastsRemoved, TD);
    return std::min(Tmp1, Tmp2);
      
  case Instruction::PHI: {
    // We can change a phi if we can change all operands.  Note that we never
    // get into trouble with cyclic PHIs here because we only consider
    // instructions with a single use.
    PHINode *PN = cast<PHINode>(I);
    int Result = CanEvaluateZExtd(PN->getIncomingValue(0), Ty,
                                  NumCastsRemoved, TD);
    for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
      if (Result == -1) return -1;
      Tmp1 = CanEvaluateZExtd(PN->getIncomingValue(i), Ty, NumCastsRemoved, TD);
      Result = std::min(Result, Tmp1);
    }
    return Result;
  }
  default:
    // TODO: Can handle more cases here.
    return -1;
  }
}

/// CanEvaluateSExtd - Return true if we can take the specified value
/// and return it as type Ty without inserting any new casts and without
/// changing the value of the common low bits.  This is used by code that tries
/// to promote integer operations to a wider types will allow us to eliminate
/// the extension.
///
/// This returns 0 if we can't do this or the number of sign bits that would be
/// set if we can.  For example, CanEvaluateSExtd(i16 1, i64) would return 63,
/// because the computation can be extended (to "i64 1") and the resulting
/// computation has 63 equal sign bits.
///
/// This function works on both vectors and scalars.  For vectors, the result is
/// the number of bits known sign extended in each element.
///
static unsigned CanEvaluateSExtd(Value *V, const Type *Ty,
                                 unsigned &NumCastsRemoved, TargetData *TD) {
  assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() &&
         "Can't sign extend type to a smaller type");
  // If this is a constant, return the number of sign bits the extended version
  // of it would have.
  if (Constant *C = dyn_cast<Constant>(V))
    return ComputeNumSignBits(ConstantExpr::getSExt(C, Ty), TD);
  
  Instruction *I = dyn_cast<Instruction>(V);
  if (!I) return 0;
  
  // If this is a truncate from the destination type, we can trivially eliminate
  // it, and this will remove a cast overall.
  if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty) {
    // If the operand of the truncate is itself a cast, and is eliminable, do
    // not count this as an eliminable cast.  We would prefer to eliminate those
    // two casts first.
    if (!isa<CastInst>(I->getOperand(0)) && I->hasOneUse())
      ++NumCastsRemoved;
    return ComputeNumSignBits(I->getOperand(0), TD);
  }
  
  // We can't extend or shrink something that has multiple uses: doing so would
  // require duplicating the instruction in general, which isn't profitable.
  if (!I->hasOneUse()) return 0;

  const Type *OrigTy = V->getType();

  unsigned Opc = I->getOpcode();
  unsigned Tmp1, Tmp2;
  switch (Opc) {
  case Instruction::And:
  case Instruction::Or:
  case Instruction::Xor:
    // These operators can all arbitrarily be extended or truncated.
    Tmp1 = CanEvaluateSExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
    if (Tmp1 == 0) return 0;
    Tmp2 = CanEvaluateSExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    return std::min(Tmp1, Tmp2);
  case Instruction::Add:
  case Instruction::Sub:
    // Add/Sub can have at most one carry/borrow bit.
    Tmp1 = CanEvaluateSExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
    if (Tmp1 == 0) return 0;
    Tmp2 = CanEvaluateSExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    if (Tmp2 == 0) return 0;
    return std::min(Tmp1, Tmp2)-1;
  case Instruction::Mul:
    // These operators can all arbitrarily be extended or truncated.
    if (!CanEvaluateSExtd(I->getOperand(0), Ty, NumCastsRemoved, TD))
      return 0;
    if (!CanEvaluateSExtd(I->getOperand(1), Ty, NumCastsRemoved, TD))
      return 0;
    return 1; // IMPROVE?
      
  //case Instruction::Shl:   TODO
  //case Instruction::LShr:  TODO
  //case Instruction::Trunc: TODO
      
  case Instruction::SExt:
  case Instruction::ZExt: {
    // sext(sext(x)) -> sext(x)
    // sext(zext(x)) -> zext(x)
    // Note that replacing a cast does not reduce the number of casts in the
    // input.
    unsigned InSignBits = ComputeNumSignBits(I, TD);
    unsigned ExtBits = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();
    // We'll end up extending it all the way out.
    return InSignBits+ExtBits;
  }
  case Instruction::Select: {
    SelectInst *SI = cast<SelectInst>(I);
    Tmp1 = CanEvaluateSExtd(SI->getTrueValue(), Ty, NumCastsRemoved, TD);
    if (Tmp1 == 0) return 0;
    Tmp2 = CanEvaluateSExtd(SI->getFalseValue(), Ty, NumCastsRemoved,TD);
    return std::min(Tmp1, Tmp2);
  }
  case Instruction::PHI: {
    // We can change a phi if we can change all operands.  Note that we never
    // get into trouble with cyclic PHIs here because we only consider
    // instructions with a single use.
    PHINode *PN = cast<PHINode>(I);
    unsigned Result = ~0U;
    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
      Result = std::min(Result,
                        CanEvaluateSExtd(PN->getIncomingValue(i), Ty,
                                         NumCastsRemoved, TD));
      if (Result == 0) return 0;
    }
    return Result;
  }
  default:
    // TODO: Can handle more cases here.
    break;
  }
  
  return 0;
}


/// EvaluateInDifferentType - Given an expression that 
/// CanEvaluateTruncated or CanEvaluateSExtd returns true for, actually
/// insert the code to evaluate the expression.
Value *InstCombiner::EvaluateInDifferentType(Value *V, const Type *Ty, 
                                             bool isSigned) {
  // FIXME: use libanalysis constant folding.
  if (Constant *C = dyn_cast<Constant>(V))
    return ConstantExpr::getIntegerCast(C, Ty, isSigned /*Sext or ZExt*/);

  // Otherwise, it must be an instruction.
  Instruction *I = cast<Instruction>(V);
  Instruction *Res = 0;
  unsigned Opc = I->getOpcode();
  switch (Opc) {
  case Instruction::Add:
  case Instruction::Sub:
  case Instruction::Mul:
  case Instruction::And:<commit_msg>mplement a theoretical fixme.<commit_after>//===- InstCombineCasts.cpp -----------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the visit functions for cast operations.
//
//===----------------------------------------------------------------------===//

#include "InstCombine.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Support/PatternMatch.h"
using namespace llvm;
using namespace PatternMatch;

/// DecomposeSimpleLinearExpr - Analyze 'Val', seeing if it is a simple linear
/// expression.  If so, decompose it, returning some value X, such that Val is
/// X*Scale+Offset.
///
static Value *DecomposeSimpleLinearExpr(Value *Val, unsigned &Scale,
                                        int &Offset) {
  assert(Val->getType()->isInteger(32) && "Unexpected allocation size type!");
  if (ConstantInt *CI = dyn_cast<ConstantInt>(Val)) {
    Offset = CI->getZExtValue();
    Scale  = 0;
    return ConstantInt::get(Type::getInt32Ty(Val->getContext()), 0);
  }
  
  if (BinaryOperator *I = dyn_cast<BinaryOperator>(Val)) {
    if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
      if (I->getOpcode() == Instruction::Shl) {
        // This is a value scaled by '1 << the shift amt'.
        Scale = 1U << RHS->getZExtValue();
        Offset = 0;
        return I->getOperand(0);
      }
      
      if (I->getOpcode() == Instruction::Mul) {
        // This value is scaled by 'RHS'.
        Scale = RHS->getZExtValue();
        Offset = 0;
        return I->getOperand(0);
      }
      
      if (I->getOpcode() == Instruction::Add) {
        // We have X+C.  Check to see if we really have (X*C2)+C1, 
        // where C1 is divisible by C2.
        unsigned SubScale;
        Value *SubVal = 
          DecomposeSimpleLinearExpr(I->getOperand(0), SubScale, Offset);
        Offset += RHS->getZExtValue();
        Scale = SubScale;
        return SubVal;
      }
    }
  }

  // Otherwise, we can't look past this.
  Scale = 1;
  Offset = 0;
  return Val;
}

/// PromoteCastOfAllocation - If we find a cast of an allocation instruction,
/// try to eliminate the cast by moving the type information into the alloc.
Instruction *InstCombiner::PromoteCastOfAllocation(BitCastInst &CI,
                                                   AllocaInst &AI) {
  // This requires TargetData to get the alloca alignment and size information.
  if (!TD) return 0;

  const PointerType *PTy = cast<PointerType>(CI.getType());
  
  BuilderTy AllocaBuilder(*Builder);
  AllocaBuilder.SetInsertPoint(AI.getParent(), &AI);

  // Get the type really allocated and the type casted to.
  const Type *AllocElTy = AI.getAllocatedType();
  const Type *CastElTy = PTy->getElementType();
  if (!AllocElTy->isSized() || !CastElTy->isSized()) return 0;

  unsigned AllocElTyAlign = TD->getABITypeAlignment(AllocElTy);
  unsigned CastElTyAlign = TD->getABITypeAlignment(CastElTy);
  if (CastElTyAlign < AllocElTyAlign) return 0;

  // If the allocation has multiple uses, only promote it if we are strictly
  // increasing the alignment of the resultant allocation.  If we keep it the
  // same, we open the door to infinite loops of various kinds.  (A reference
  // from a dbg.declare doesn't count as a use for this purpose.)
  if (!AI.hasOneUse() && !hasOneUsePlusDeclare(&AI) &&
      CastElTyAlign == AllocElTyAlign) return 0;

  uint64_t AllocElTySize = TD->getTypeAllocSize(AllocElTy);
  uint64_t CastElTySize = TD->getTypeAllocSize(CastElTy);
  if (CastElTySize == 0 || AllocElTySize == 0) return 0;

  // See if we can satisfy the modulus by pulling a scale out of the array
  // size argument.
  unsigned ArraySizeScale;
  int ArrayOffset;
  Value *NumElements = // See if the array size is a decomposable linear expr.
    DecomposeSimpleLinearExpr(AI.getOperand(0), ArraySizeScale, ArrayOffset);
 
  // If we can now satisfy the modulus, by using a non-1 scale, we really can
  // do the xform.
  if ((AllocElTySize*ArraySizeScale) % CastElTySize != 0 ||
      (AllocElTySize*ArrayOffset   ) % CastElTySize != 0) return 0;

  unsigned Scale = (AllocElTySize*ArraySizeScale)/CastElTySize;
  Value *Amt = 0;
  if (Scale == 1) {
    Amt = NumElements;
  } else {
    Amt = ConstantInt::get(Type::getInt32Ty(CI.getContext()), Scale);
    // Insert before the alloca, not before the cast.
    Amt = AllocaBuilder.CreateMul(Amt, NumElements, "tmp");
  }
  
  if (int Offset = (AllocElTySize*ArrayOffset)/CastElTySize) {
    Value *Off = ConstantInt::get(Type::getInt32Ty(CI.getContext()),
                                  Offset, true);
    Amt = AllocaBuilder.CreateAdd(Amt, Off, "tmp");
  }
  
  AllocaInst *New = AllocaBuilder.CreateAlloca(CastElTy, Amt);
  New->setAlignment(AI.getAlignment());
  New->takeName(&AI);
  
  // If the allocation has one real use plus a dbg.declare, just remove the
  // declare.
  if (DbgDeclareInst *DI = hasOneUsePlusDeclare(&AI)) {
    EraseInstFromFunction(*(Instruction*)DI);
  }
  // If the allocation has multiple real uses, insert a cast and change all
  // things that used it to use the new cast.  This will also hack on CI, but it
  // will die soon.
  else if (!AI.hasOneUse()) {
    // New is the allocation instruction, pointer typed. AI is the original
    // allocation instruction, also pointer typed. Thus, cast to use is BitCast.
    Value *NewCast = AllocaBuilder.CreateBitCast(New, AI.getType(), "tmpcast");
    AI.replaceAllUsesWith(NewCast);
  }
  return ReplaceInstUsesWith(CI, New);
}


/// CanEvaluateTruncated - Return true if we can evaluate the specified
/// expression tree as type Ty instead of its larger type, and arrive with the
/// same value.  This is used by code that tries to eliminate truncates.
///
/// Ty will always be a type smaller than V.  We should return true if trunc(V)
/// can be computed by computing V in the smaller type.  If V is an instruction,
/// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only
/// makes sense if x and y can be efficiently truncated.
///
static bool CanEvaluateTruncated(Value *V, const Type *Ty) {
  // We can always evaluate constants in another type.
  if (isa<Constant>(V))
    return true;
  
  Instruction *I = dyn_cast<Instruction>(V);
  if (!I) return false;
  
  const Type *OrigTy = V->getType();
  
  // If this is an extension from the dest type, we can eliminate it.
  if ((isa<ZExtInst>(I) || isa<SExtInst>(I)) && 
      I->getOperand(0)->getType() == Ty)
    return true;

  // We can't extend or shrink something that has multiple uses: doing so would
  // require duplicating the instruction in general, which isn't profitable.
  if (!I->hasOneUse()) return false;

  unsigned Opc = I->getOpcode();
  switch (Opc) {
  case Instruction::Add:
  case Instruction::Sub:
  case Instruction::Mul:
  case Instruction::And:
  case Instruction::Or:
  case Instruction::Xor:
    // These operators can all arbitrarily be extended or truncated.
    return CanEvaluateTruncated(I->getOperand(0), Ty) &&
           CanEvaluateTruncated(I->getOperand(1), Ty);

  case Instruction::UDiv:
  case Instruction::URem: {
    // UDiv and URem can be truncated if all the truncated bits are zero.
    uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
    uint32_t BitWidth = Ty->getScalarSizeInBits();
    if (BitWidth < OrigBitWidth) {
      APInt Mask = APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth);
      if (MaskedValueIsZero(I->getOperand(0), Mask) &&
          MaskedValueIsZero(I->getOperand(1), Mask)) {
        return CanEvaluateTruncated(I->getOperand(0), Ty) &&
               CanEvaluateTruncated(I->getOperand(1), Ty);
      }
    }
    break;
  }
  case Instruction::Shl:
    // If we are truncating the result of this SHL, and if it's a shift of a
    // constant amount, we can always perform a SHL in a smaller type.
    if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
      uint32_t BitWidth = Ty->getScalarSizeInBits();
      if (CI->getLimitedValue(BitWidth) < BitWidth)
        return CanEvaluateTruncated(I->getOperand(0), Ty);
    }
    break;
  case Instruction::LShr:
    // If this is a truncate of a logical shr, we can truncate it to a smaller
    // lshr iff we know that the bits we would otherwise be shifting in are
    // already zeros.
    if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
      uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
      uint32_t BitWidth = Ty->getScalarSizeInBits();
      if (MaskedValueIsZero(I->getOperand(0),
            APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) &&
          CI->getLimitedValue(BitWidth) < BitWidth) {
        return CanEvaluateTruncated(I->getOperand(0), Ty);
      }
    }
    break;
  case Instruction::Trunc:
    // trunc(trunc(x)) -> trunc(x)
    return true;
  case Instruction::Select: {
    SelectInst *SI = cast<SelectInst>(I);
    return CanEvaluateTruncated(SI->getTrueValue(), Ty) &&
           CanEvaluateTruncated(SI->getFalseValue(), Ty);
  }
  case Instruction::PHI: {
    // We can change a phi if we can change all operands.  Note that we never
    // get into trouble with cyclic PHIs here because we only consider
    // instructions with a single use.
    PHINode *PN = cast<PHINode>(I);
    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
      if (!CanEvaluateTruncated(PN->getIncomingValue(i), Ty))
        return false;
    return true;
  }
  default:
    // TODO: Can handle more cases here.
    break;
  }
  
  return false;
}

/// GetLeadingZeros - Compute the number of known-zero leading bits.
static unsigned GetLeadingZeros(Value *V, const TargetData *TD) {
  unsigned Bits = V->getType()->getScalarSizeInBits();
  APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
  ComputeMaskedBits(V, APInt::getAllOnesValue(Bits), KnownZero, KnownOne, TD);
  return KnownZero.countLeadingOnes();
}

/// CanEvaluateZExtd - Determine if the specified value can be computed in the
/// specified wider type and produce the same low bits.  If not, return -1.  If
/// it is possible, return the number of high bits that are known to be zero in
/// the promoted value.
static int CanEvaluateZExtd(Value *V, const Type *Ty,unsigned &NumCastsRemoved,
                            const TargetData *TD) {
  const Type *OrigTy = V->getType();

  if (isa<Constant>(V)) {
    unsigned Extended = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();

    // Constants can always be zero ext'd, even if it requires a ConstantExpr.
    if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
      return Extended + CI->getValue().countLeadingZeros();
    return Extended;
  }
  
  Instruction *I = dyn_cast<Instruction>(V);
  if (!I) return -1;
  
  // If the input is a truncate from the destination type, we can trivially
  // eliminate it, and this will remove a cast overall.
  if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty) {
    // If the first operand is itself a cast, and is eliminable, do not count
    // this as an eliminable cast.  We would prefer to eliminate those two
    // casts first.
    if (!isa<CastInst>(I->getOperand(0)) && I->hasOneUse())
      ++NumCastsRemoved;
    
    // Figure out the number of known-zero bits coming in.
    return GetLeadingZeros(I->getOperand(0), TD);
  }
  
  // We can't extend or shrink something that has multiple uses: doing so would
  // require duplicating the instruction in general, which isn't profitable.
  if (!I->hasOneUse()) return -1;
  
  int Tmp1, Tmp2;
  unsigned Opc = I->getOpcode();
  switch (Opc) {
  case Instruction::And:
    Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
    if (Tmp1 == -1) return -1;
    Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    if (Tmp2 == -1) return -1;
    return std::max(Tmp1, Tmp2);
  case Instruction::Or:
  case Instruction::Xor:
    Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
    if (Tmp1 == -1) return -1;
    Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    return std::min(Tmp1, Tmp2);

  case Instruction::Add:
  case Instruction::Sub:
  case Instruction::Mul:
    Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
    if (Tmp1 == -1) return -1;
    Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    if (Tmp2 == -1) return -1;
    return 0;
      
  //case Instruction::Shl:
  //case Instruction::LShr:
  case Instruction::ZExt:
    // zext(zext(x)) -> zext(x).  Since we're replacing it, it isn't eliminated.
    Tmp1 = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();
    return GetLeadingZeros(I, TD)+Tmp1;
      
  //case Instruction::SExt:  zext(sext(x)) -> sext(x) with no upper bits known.
  //case Instruction::Trunc:
  case Instruction::Select:
    Tmp1 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    if (Tmp1 == -1) return -1;
    Tmp2 = CanEvaluateZExtd(I->getOperand(2), Ty, NumCastsRemoved, TD);
    return std::min(Tmp1, Tmp2);
      
  case Instruction::PHI: {
    // We can change a phi if we can change all operands.  Note that we never
    // get into trouble with cyclic PHIs here because we only consider
    // instructions with a single use.
    PHINode *PN = cast<PHINode>(I);
    int Result = CanEvaluateZExtd(PN->getIncomingValue(0), Ty,
                                  NumCastsRemoved, TD);
    for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
      if (Result == -1) return -1;
      Tmp1 = CanEvaluateZExtd(PN->getIncomingValue(i), Ty, NumCastsRemoved, TD);
      Result = std::min(Result, Tmp1);
    }
    return Result;
  }
  default:
    // TODO: Can handle more cases here.
    return -1;
  }
}

/// CanEvaluateSExtd - Return true if we can take the specified value
/// and return it as type Ty without inserting any new casts and without
/// changing the value of the common low bits.  This is used by code that tries
/// to promote integer operations to a wider types will allow us to eliminate
/// the extension.
///
/// This returns 0 if we can't do this or the number of sign bits that would be
/// set if we can.  For example, CanEvaluateSExtd(i16 1, i64) would return 63,
/// because the computation can be extended (to "i64 1") and the resulting
/// computation has 63 equal sign bits.
///
/// This function works on both vectors and scalars.  For vectors, the result is
/// the number of bits known sign extended in each element.
///
static unsigned CanEvaluateSExtd(Value *V, const Type *Ty,
                                 unsigned &NumCastsRemoved, TargetData *TD) {
  assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() &&
         "Can't sign extend type to a smaller type");
  // If this is a constant, return the number of sign bits the extended version
  // of it would have.
  if (Constant *C = dyn_cast<Constant>(V))
    return ComputeNumSignBits(ConstantExpr::getSExt(C, Ty), TD);
  
  Instruction *I = dyn_cast<Instruction>(V);
  if (!I) return 0;
  
  // If this is a truncate from the destination type, we can trivially eliminate
  // it, and this will remove a cast overall.
  if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty) {
    // If the operand of the truncate is itself a cast, and is eliminable, do
    // not count this as an eliminable cast.  We would prefer to eliminate those
    // two casts first.
    if (!isa<CastInst>(I->getOperand(0)) && I->hasOneUse())
      ++NumCastsRemoved;
    return ComputeNumSignBits(I->getOperand(0), TD);
  }
  
  // We can't extend or shrink something that has multiple uses: doing so would
  // require duplicating the instruction in general, which isn't profitable.
  if (!I->hasOneUse()) return 0;

  const Type *OrigTy = V->getType();

  unsigned Opc = I->getOpcode();
  unsigned Tmp1, Tmp2;
  switch (Opc) {
  case Instruction::And:
  case Instruction::Or:
  case Instruction::Xor:
    // These operators can all arbitrarily be extended or truncated.
    Tmp1 = CanEvaluateSExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
    if (Tmp1 == 0) return 0;
    Tmp2 = CanEvaluateSExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    return std::min(Tmp1, Tmp2);
  case Instruction::Add:
  case Instruction::Sub:
    // Add/Sub can have at most one carry/borrow bit.
    Tmp1 = CanEvaluateSExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
    if (Tmp1 == 0) return 0;
    Tmp2 = CanEvaluateSExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
    if (Tmp2 == 0) return 0;
    return std::min(Tmp1, Tmp2)-1;
  case Instruction::Mul:
    // These operators can all arbitrarily be extended or truncated.
    if (!CanEvaluateSExtd(I->getOperand(0), Ty, NumCastsRemoved, TD))
      return 0;
    if (!CanEvaluateSExtd(I->getOperand(1), Ty, NumCastsRemoved, TD))
      return 0;
    return 1; // IMPROVE?
      
  //case Instruction::Shl:   TODO
  //case Instruction::LShr:  TODO
  //case Instruction::Trunc: TODO
      
  case Instruction::SExt:
  case Instruction::ZExt: {
    // sext(sext(x)) -> sext(x)
    // sext(zext(x)) -> zext(x)
    // Note that replacing a cast does not reduce the number of casts in the
    // input.
    unsigned InSignBits = ComputeNumSignBits(I, TD);
    unsigned ExtBits = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();
    // We'll end up extending it all the way out.
    return InSignBits+ExtBits;
  }
  case Instruction::Select: {
    SelectInst *SI = cast<SelectInst>(I);
    Tmp1 = CanEvaluateSExtd(SI->getTrueValue(), Ty, NumCastsRemoved, TD);
    if (Tmp1 == 0) return 0;
    Tmp2 = CanEvaluateSExtd(SI->getFalseValue(), Ty, NumCastsRemoved,TD);
    return std::min(Tmp1, Tmp2);
  }
  case Instruction::PHI: {
    // We can change a phi if we can change all operands.  Note that we never
    // get into trouble with cyclic PHIs here because we only consider
    // instructions with a single use.
    PHINode *PN = cast<PHINode>(I);
    unsigned Result = ~0U;
    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
      Result = std::min(Result,
                        CanEvaluateSExtd(PN->getIncomingValue(i), Ty,
                                         NumCastsRemoved, TD));
      if (Result == 0) return 0;
    }
    return Result;
  }
  default:
    // TODO: Can handle more cases here.
    break;
  }
  
  return 0;
}


/// EvaluateInDifferentType - Given an expression that 
/// CanEvaluateTruncated or CanEvaluateSExtd returns true for, actually
/// insert the code to evaluate the expression.
Value *InstCombiner::EvaluateInDifferentType(Value *V, const Type *Ty, 
                                             bool isSigned) {
  if (Constant *C = dyn_cast<Constant>(V)) {
    C = ConstantExpr::getIntegerCast(C, Ty, isSigned /*Sext or ZExt*/);
    // If we got a constantexpr back, try to simplify it with TD info.
    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
      C = ConstantFoldConstantExpression(CE, TD);
    return C;
  }

  // Otherwise, it must be an instruction.
  Instruction *I = cast<Instruction>(V);
  Instruction *Res = 0;
  unsigned Opc = I->getOpcode();
  switch (Opc) {
  case Instruction::Add:
  case Instruction::Sub:
  case Instruction::Mul:
  case Instruction::And:
{'fraction_non_alphanumeric': 0.12967658473479948, 'fraction_numerical': 0.009573091849935317, 'mean_word_length': 2.9476049433152895, 'pattern_counts': {'":': 0, '<': 74, '<?xml version=': 0, '>': 266, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7142510', 'n_tokens_mistral': 12410, 'n_tokens_neox': 12076, 'n_words': 3913}