LLVM API Documentation

InstructionCombining.cpp

Go to the documentation of this file.

//===- InstructionCombining.cpp - Combine multiple instructions -----------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// InstructionCombining - Combine instructions to form fewer, simple
// instructions.  This pass does not modify the CFG.  This pass is where
// algebraic simplification happens.
//
// This pass combines things like:
//    %Y = add i32 %X, 1
//    %Z = add i32 %Y, 1
// into:
//    %Z = add i32 %X, 2
//
// This is a simple worklist driven algorithm.
//
// This pass guarantees that the following canonicalizations are performed on
// the program:
//    1. If a binary operator has a constant operand, it is moved to the RHS
//    2. Bitwise operators with constant operands are always grouped so that
//       shifts are performed first, then or's, then and's, then xor's.
//    3. Compare instructions are converted from <,>,<=,>= to ==,!= if possible
//    4. All cmp instructions on boolean values are replaced with logical ops
//    5. add X, X is represented as (X*2) => (X << 1)
//    6. Multiplies with a power-of-two constant argument are transformed into
//       shifts.
//   ... etc.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "instcombine"
#include "llvm/Transforms/Scalar.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Pass.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/PatternMatch.h"
#include "llvm/Support/Compiler.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <climits>
#include <sstream>
using namespace llvm;
using namespace llvm::PatternMatch;

STATISTIC(NumCombined , "Number of insts combined");
STATISTIC(NumConstProp, "Number of constant folds");
STATISTIC(NumDeadInst , "Number of dead inst eliminated");
STATISTIC(NumDeadStore, "Number of dead stores eliminated");
STATISTIC(NumSunkInst , "Number of instructions sunk");

namespace {
  class VISIBILITY_HIDDEN InstCombiner
    : public FunctionPass,
      public InstVisitor<InstCombiner, Instruction*> {
    // Worklist of all of the instructions that need to be simplified.
    SmallVector<Instruction*, 256> Worklist;
    DenseMap<Instruction*, unsigned> WorklistMap;
    TargetData *TD;
    bool MustPreserveLCSSA;
  public:
    static char ID; // Pass identification, replacement for typeid
    InstCombiner() : FunctionPass(&ID) {}

    /// AddToWorkList - Add the specified instruction to the worklist if it
    /// isn't already in it.
    void AddToWorkList(Instruction *I) {
      if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second)
        Worklist.push_back(I);
    }
    
    // RemoveFromWorkList - remove I from the worklist if it exists.
    void RemoveFromWorkList(Instruction *I) {
      DenseMap<Instruction*, unsigned>::iterator It = WorklistMap.find(I);
      if (It == WorklistMap.end()) return; // Not in worklist.
      
      // Don't bother moving everything down, just null out the slot.
      Worklist[It->second] = 0;
      
      WorklistMap.erase(It);
    }
    
    Instruction *RemoveOneFromWorkList() {
      Instruction *I = Worklist.back();
      Worklist.pop_back();
      WorklistMap.erase(I);
      return I;
    }

    
    /// AddUsersToWorkList - When an instruction is simplified, add all users of
    /// the instruction to the work lists because they might get more simplified
    /// now.
    ///
    void AddUsersToWorkList(Value &I) {
      for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
           UI != UE; ++UI)
        AddToWorkList(cast<Instruction>(*UI));
    }

    /// AddUsesToWorkList - When an instruction is simplified, add operands to
    /// the work lists because they might get more simplified now.
    ///
    void AddUsesToWorkList(Instruction &I) {
      for (User::op_iterator i = I.op_begin(), e = I.op_end(); i != e; ++i)
        if (Instruction *Op = dyn_cast<Instruction>(*i))
          AddToWorkList(Op);
    }
    
    /// AddSoonDeadInstToWorklist - The specified instruction is about to become
    /// dead.  Add all of its operands to the worklist, turning them into
    /// undef's to reduce the number of uses of those instructions.
    ///
    /// Return the specified operand before it is turned into an undef.
    ///
    Value *AddSoonDeadInstToWorklist(Instruction &I, unsigned op) {
      Value *R = I.getOperand(op);
      
      for (User::op_iterator i = I.op_begin(), e = I.op_end(); i != e; ++i)
        if (Instruction *Op = dyn_cast<Instruction>(*i)) {
          AddToWorkList(Op);
          // Set the operand to undef to drop the use.
          *i = UndefValue::get(Op->getType());
        }
      
      return R;
    }

  public:
    virtual bool runOnFunction(Function &F);
    
    bool DoOneIteration(Function &F, unsigned ItNum);

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<TargetData>();
      AU.addPreservedID(LCSSAID);
      AU.setPreservesCFG();
    }

    TargetData &getTargetData() const { return *TD; }

    // Visitation implementation - Implement instruction combining for different
    // instruction types.  The semantics are as follows:
    // Return Value:
    //    null        - No change was made
    //     I          - Change was made, I is still valid, I may be dead though
    //   otherwise    - Change was made, replace I with returned instruction
    //
    Instruction *visitAdd(BinaryOperator &I);
    Instruction *visitSub(BinaryOperator &I);
    Instruction *visitMul(BinaryOperator &I);
    Instruction *visitURem(BinaryOperator &I);
    Instruction *visitSRem(BinaryOperator &I);
    Instruction *visitFRem(BinaryOperator &I);
    bool SimplifyDivRemOfSelect(BinaryOperator &I);
    Instruction *commonRemTransforms(BinaryOperator &I);
    Instruction *commonIRemTransforms(BinaryOperator &I);
    Instruction *commonDivTransforms(BinaryOperator &I);
    Instruction *commonIDivTransforms(BinaryOperator &I);
    Instruction *visitUDiv(BinaryOperator &I);
    Instruction *visitSDiv(BinaryOperator &I);
    Instruction *visitFDiv(BinaryOperator &I);
    Instruction *visitAnd(BinaryOperator &I);
    Instruction *visitOr (BinaryOperator &I);
    Instruction *visitXor(BinaryOperator &I);
    Instruction *visitShl(BinaryOperator &I);
    Instruction *visitAShr(BinaryOperator &I);
    Instruction *visitLShr(BinaryOperator &I);
    Instruction *commonShiftTransforms(BinaryOperator &I);
    Instruction *FoldFCmp_IntToFP_Cst(FCmpInst &I, Instruction *LHSI,
                                      Constant *RHSC);
    Instruction *visitFCmpInst(FCmpInst &I);
    Instruction *visitICmpInst(ICmpInst &I);
    Instruction *visitICmpInstWithCastAndCast(ICmpInst &ICI);
    Instruction *visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
                                                Instruction *LHS,
                                                ConstantInt *RHS);
    Instruction *FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI,
                                ConstantInt *DivRHS);

    Instruction *FoldGEPICmp(User *GEPLHS, Value *RHS,
                             ICmpInst::Predicate Cond, Instruction &I);
    Instruction *FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
                                     BinaryOperator &I);
    Instruction *commonCastTransforms(CastInst &CI);
    Instruction *commonIntCastTransforms(CastInst &CI);
    Instruction *commonPointerCastTransforms(CastInst &CI);
    Instruction *visitTrunc(TruncInst &CI);
    Instruction *visitZExt(ZExtInst &CI);
    Instruction *visitSExt(SExtInst &CI);
    Instruction *visitFPTrunc(FPTruncInst &CI);
    Instruction *visitFPExt(CastInst &CI);
    Instruction *visitFPToUI(FPToUIInst &FI);
    Instruction *visitFPToSI(FPToSIInst &FI);
    Instruction *visitUIToFP(CastInst &CI);
    Instruction *visitSIToFP(CastInst &CI);
    Instruction *visitPtrToInt(CastInst &CI);
    Instruction *visitIntToPtr(IntToPtrInst &CI);
    Instruction *visitBitCast(BitCastInst &CI);
    Instruction *FoldSelectOpOp(SelectInst &SI, Instruction *TI,
                                Instruction *FI);
    Instruction *visitSelectInst(SelectInst &CI);
    Instruction *visitCallInst(CallInst &CI);
    Instruction *visitInvokeInst(InvokeInst &II);
    Instruction *visitPHINode(PHINode &PN);
    Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
    Instruction *visitAllocationInst(AllocationInst &AI);
    Instruction *visitFreeInst(FreeInst &FI);
    Instruction *visitLoadInst(LoadInst &LI);
    Instruction *visitStoreInst(StoreInst &SI);
    Instruction *visitBranchInst(BranchInst &BI);
    Instruction *visitSwitchInst(SwitchInst &SI);
    Instruction *visitInsertElementInst(InsertElementInst &IE);
    Instruction *visitExtractElementInst(ExtractElementInst &EI);
    Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
    Instruction *visitExtractValueInst(ExtractValueInst &EV);

    // visitInstruction - Specify what to return for unhandled instructions...
    Instruction *visitInstruction(Instruction &I) { return 0; }

  private:
    Instruction *visitCallSite(CallSite CS);
    bool transformConstExprCastCall(CallSite CS);
    Instruction *transformCallThroughTrampoline(CallSite CS);
    Instruction *transformZExtICmp(ICmpInst *ICI, Instruction &CI,
                                   bool DoXform = true);
    bool WillNotOverflowSignedAdd(Value *LHS, Value *RHS);

  public:
    // InsertNewInstBefore - insert an instruction New before instruction Old
    // in the program.  Add the new instruction to the worklist.
    //
    Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
      assert(New && New->getParent() == 0 &&
             "New instruction already inserted into a basic block!");
      BasicBlock *BB = Old.getParent();
      BB->getInstList().insert(&Old, New);  // Insert inst
      AddToWorkList(New);
      return New;
    }

    /// InsertCastBefore - Insert a cast of V to TY before the instruction POS.
    /// This also adds the cast to the worklist.  Finally, this returns the
    /// cast.
    Value *InsertCastBefore(Instruction::CastOps opc, Value *V, const Type *Ty,
                            Instruction &Pos) {
      if (V->getType() == Ty) return V;

      if (Constant *CV = dyn_cast<Constant>(V))
        return ConstantExpr::getCast(opc, CV, Ty);
      
      Instruction *C = CastInst::Create(opc, V, Ty, V->getName(), &Pos);
      AddToWorkList(C);
      return C;
    }
        
    Value *InsertBitCastBefore(Value *V, const Type *Ty, Instruction &Pos) {
      return InsertCastBefore(Instruction::BitCast, V, Ty, Pos);
    }


    // ReplaceInstUsesWith - This method is to be used when an instruction is
    // found to be dead, replacable with another preexisting expression.  Here
    // we add all uses of I to the worklist, replace all uses of I with the new
    // value, then return I, so that the inst combiner will know that I was
    // modified.
    //
    Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) {
      AddUsersToWorkList(I);         // Add all modified instrs to worklist
      if (&I != V) {
        I.replaceAllUsesWith(V);
        return &I;
      } else {
        // If we are replacing the instruction with itself, this must be in a
        // segment of unreachable code, so just clobber the instruction.
        I.replaceAllUsesWith(UndefValue::get(I.getType()));
        return &I;
      }
    }

    // UpdateValueUsesWith - This method is to be used when an value is
    // found to be replacable with another preexisting expression or was
    // updated.  Here we add all uses of I to the worklist, replace all uses of
    // I with the new value (unless the instruction was just updated), then
    // return true, so that the inst combiner will know that I was modified.
    //
    bool UpdateValueUsesWith(Value *Old, Value *New) {
      AddUsersToWorkList(*Old);         // Add all modified instrs to worklist
      if (Old != New)
        Old->replaceAllUsesWith(New);
      if (Instruction *I = dyn_cast<Instruction>(Old))
        AddToWorkList(I);
      if (Instruction *I = dyn_cast<Instruction>(New))
        AddToWorkList(I);
      return true;
    }
    
    // EraseInstFromFunction - When dealing with an instruction that has side
    // effects or produces a void value, we can't rely on DCE to delete the
    // instruction.  Instead, visit methods should return the value returned by
    // this function.
    Instruction *EraseInstFromFunction(Instruction &I) {
      assert(I.use_empty() && "Cannot erase instruction that is used!");
      AddUsesToWorkList(I);
      RemoveFromWorkList(&I);
      I.eraseFromParent();
      return 0;  // Don't do anything with FI
    }
        
    void ComputeMaskedBits(Value *V, const APInt &Mask, APInt &KnownZero,
                           APInt &KnownOne, unsigned Depth = 0) const {
      return llvm::ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth);
    }
    
    bool MaskedValueIsZero(Value *V, const APInt &Mask, 
                           unsigned Depth = 0) const {
      return llvm::MaskedValueIsZero(V, Mask, TD, Depth);
    }
    unsigned ComputeNumSignBits(Value *Op, unsigned Depth = 0) const {
      return llvm::ComputeNumSignBits(Op, TD, Depth);
    }

  private:
    /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
    /// InsertBefore instruction.  This is specialized a bit to avoid inserting
    /// casts that are known to not do anything...
    ///
    Value *InsertOperandCastBefore(Instruction::CastOps opcode,
                                   Value *V, const Type *DestTy,
                                   Instruction *InsertBefore);

    /// SimplifyCommutative - This performs a few simplifications for 
    /// commutative operators.
    bool SimplifyCommutative(BinaryOperator &I);

    /// SimplifyCompare - This reorders the operands of a CmpInst to get them in
    /// most-complex to least-complex order.
    bool SimplifyCompare(CmpInst &I);

    /// SimplifyDemandedBits - Attempts to replace V with a simpler value based
    /// on the demanded bits.
    bool SimplifyDemandedBits(Value *V, APInt DemandedMask, 
                              APInt& KnownZero, APInt& KnownOne,
                              unsigned Depth = 0);

    Value *SimplifyDemandedVectorElts(Value *V, uint64_t DemandedElts,
                                      uint64_t &UndefElts, unsigned Depth = 0);
      
    // FoldOpIntoPhi - Given a binary operator or cast instruction which has a
    // PHI node as operand #0, see if we can fold the instruction into the PHI
    // (which is only possible if all operands to the PHI are constants).
    Instruction *FoldOpIntoPhi(Instruction &I);

    // FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary"
    // operator and they all are only used by the PHI, PHI together their
    // inputs, and do the operation once, to the result of the PHI.
    Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
    Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN);
    
    
    Instruction *OptAndOp(Instruction *Op, ConstantInt *OpRHS,
                          ConstantInt *AndRHS, BinaryOperator &TheAnd);
    
    Value *FoldLogicalPlusAnd(Value *LHS, Value *RHS, ConstantInt *Mask,
                              bool isSub, Instruction &I);
    Instruction *InsertRangeTest(Value *V, Constant *Lo, Constant *Hi,
                                 bool isSigned, bool Inside, Instruction &IB);
    Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocationInst &AI);
    Instruction *MatchBSwap(BinaryOperator &I);
    bool SimplifyStoreAtEndOfBlock(StoreInst &SI);
    Instruction *SimplifyMemTransfer(MemIntrinsic *MI);
    Instruction *SimplifyMemSet(MemSetInst *MI);


    Value *EvaluateInDifferentType(Value *V, const Type *Ty, bool isSigned);

    bool CanEvaluateInDifferentType(Value *V, const IntegerType *Ty,
                                    unsigned CastOpc,
                                    int &NumCastsRemoved);
    unsigned GetOrEnforceKnownAlignment(Value *V,
                                        unsigned PrefAlign = 0);

  };
}

char InstCombiner::ID = 0;
static RegisterPass<InstCombiner>
X("instcombine", "Combine redundant instructions");

// getComplexity:  Assign a complexity or rank value to LLVM Values...
//   0 -> undef, 1 -> Const, 2 -> Other, 3 -> Arg, 3 -> Unary, 4 -> OtherInst
static unsigned getComplexity(Value *V) {
  if (isa<Instruction>(V)) {
    if (BinaryOperator::isNeg(V) || BinaryOperator::isNot(V))
      return 3;
    return 4;
  }
  if (isa<Argument>(V)) return 3;
  return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
}

// isOnlyUse - Return true if this instruction will be deleted if we stop using
// it.
static bool isOnlyUse(Value *V) {
  return V->hasOneUse() || isa<Constant>(V);
}

// getPromotedType - Return the specified type promoted as it would be to pass
// though a va_arg area...
static const Type *getPromotedType(const Type *Ty) {
  if (const IntegerType* ITy = dyn_cast<IntegerType>(Ty)) {
    if (ITy->getBitWidth() < 32)
      return Type::Int32Ty;
  }
  return Ty;
}

/// getBitCastOperand - If the specified operand is a CastInst or a constant 
/// expression bitcast,  return the operand value, otherwise return null.
static Value *getBitCastOperand(Value *V) {
  if (BitCastInst *I = dyn_cast<BitCastInst>(V))
    return I->getOperand(0);
  else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    if (CE->getOpcode() == Instruction::BitCast)
      return CE->getOperand(0);
  return 0;
}

/// This function is a wrapper around CastInst::isEliminableCastPair. It
/// simply extracts arguments and returns what that function returns.
static Instruction::CastOps 
isEliminableCastPair(
  const CastInst *CI, ///< The first cast instruction
  unsigned opcode,       ///< The opcode of the second cast instruction
  const Type *DstTy,     ///< The target type for the second cast instruction
  TargetData *TD         ///< The target data for pointer size
) {
  
  const Type *SrcTy = CI->getOperand(0)->getType();   // A from above
  const Type *MidTy = CI->getType();                  // B from above

  // Get the opcodes of the two Cast instructions
  Instruction::CastOps firstOp = Instruction::CastOps(CI->getOpcode());
  Instruction::CastOps secondOp = Instruction::CastOps(opcode);

  return Instruction::CastOps(
      CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy,
                                     DstTy, TD->getIntPtrType()));
}

/// ValueRequiresCast - Return true if the cast from "V to Ty" actually results
/// in any code being generated.  It does not require codegen if V is simple
/// enough or if the cast can be folded into other casts.
static bool ValueRequiresCast(Instruction::CastOps opcode, const Value *V, 
                              const Type *Ty, TargetData *TD) {
  if (V->getType() == Ty || isa<Constant>(V)) return false;
  
  // If this is another cast that can be eliminated, it isn't codegen either.
  if (const CastInst *CI = dyn_cast<CastInst>(V))
    if (isEliminableCastPair(CI, opcode, Ty, TD)) 
      return false;
  return true;
}

/// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
/// InsertBefore instruction.  This is specialized a bit to avoid inserting
/// casts that are known to not do anything...
///
Value *InstCombiner::InsertOperandCastBefore(Instruction::CastOps opcode,
                                             Value *V, const Type *DestTy,
                                             Instruction *InsertBefore) {
  if (V->getType() == DestTy) return V;
  if (Constant *C = dyn_cast<Constant>(V))
    return ConstantExpr::getCast(opcode, C, DestTy);
  
  return InsertCastBefore(opcode, V, DestTy, *InsertBefore);
}

// SimplifyCommutative - This performs a few simplifications for commutative
// operators:
//
//  1. Order operands such that they are listed from right (least complex) to
//     left (most complex).  This puts constants before unary operators before
//     binary operators.
//
//  2. Transform: (op (op V, C1), C2) ==> (op V, (op C1, C2))
//  3. Transform: (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
//
bool InstCombiner::SimplifyCommutative(BinaryOperator &I) {
  bool Changed = false;
  if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1)))
    Changed = !I.swapOperands();

  if (!I.isAssociative()) return Changed;
  Instruction::BinaryOps Opcode = I.getOpcode();
  if (BinaryOperator *Op = dyn_cast<BinaryOperator>(I.getOperand(0)))
    if (Op->getOpcode() == Opcode && isa<Constant>(Op->getOperand(1))) {
      if (isa<Constant>(I.getOperand(1))) {
        Constant *Folded = ConstantExpr::get(I.getOpcode(),
                                             cast<Constant>(I.getOperand(1)),
                                             cast<Constant>(Op->getOperand(1)));
        I.setOperand(0, Op->getOperand(0));
        I.setOperand(1, Folded);
        return true;
      } else if (BinaryOperator *Op1=dyn_cast<BinaryOperator>(I.getOperand(1)))
        if (Op1->getOpcode() == Opcode && isa<Constant>(Op1->getOperand(1)) &&
            isOnlyUse(Op) && isOnlyUse(Op1)) {
          Constant *C1 = cast<Constant>(Op->getOperand(1));
          Constant *C2 = cast<Constant>(Op1->getOperand(1));

          // Fold (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
          Constant *Folded = ConstantExpr::get(I.getOpcode(), C1, C2);
          Instruction *New = BinaryOperator::Create(Opcode, Op->getOperand(0),
                                                    Op1->getOperand(0),
                                                    Op1->getName(), &I);
          AddToWorkList(New);
          I.setOperand(0, New);
          I.setOperand(1, Folded);
          return true;
        }
    }
  return Changed;
}

/// SimplifyCompare - For a CmpInst this function just orders the operands
/// so that theyare listed from right (least complex) to left (most complex).
/// This puts constants before unary operators before binary operators.
bool InstCombiner::SimplifyCompare(CmpInst &I) {
  if (getComplexity(I.getOperand(0)) >= getComplexity(I.getOperand(1)))
    return false;
  I.swapOperands();
  // Compare instructions are not associative so there's nothing else we can do.
  return true;
}

// dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction
// if the LHS is a constant zero (which is the 'negate' form).
//
static inline Value *dyn_castNegVal(Value *V) {
  if (BinaryOperator::isNeg(V))
    return BinaryOperator::getNegArgument(V);

  // Constants can be considered to be negated values if they can be folded.
  if (ConstantInt *C = dyn_cast<ConstantInt>(V))
    return ConstantExpr::getNeg(C);

  if (ConstantVector *C = dyn_cast<ConstantVector>(V))
    if (C->getType()->getElementType()->isInteger())
      return ConstantExpr::getNeg(C);

  return 0;
}

static inline Value *dyn_castNotVal(Value *V) {
  if (BinaryOperator::isNot(V))
    return BinaryOperator::getNotArgument(V);

  // Constants can be considered to be not'ed values...
  if (ConstantInt *C = dyn_cast<ConstantInt>(V))
    return ConstantInt::get(~C->getValue());
  return 0;
}

// dyn_castFoldableMul - If this value is a multiply that can be folded into
// other computations (because it has a constant operand), return the
// non-constant operand of the multiply, and set CST to point to the multiplier.
// Otherwise, return null.
//
static inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) {
  if (V->hasOneUse() && V->getType()->isInteger())
    if (Instruction *I = dyn_cast<Instruction>(V)) {
      if (I->getOpcode() == Instruction::Mul)
        if ((CST = dyn_cast<ConstantInt>(I->getOperand(1))))
          return I->getOperand(0);
      if (I->getOpcode() == Instruction::Shl)
        if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) {
          // The multiplier is really 1 << CST.
          uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
          uint32_t CSTVal = CST->getLimitedValue(BitWidth);
          CST = ConstantInt::get(APInt(BitWidth, 1).shl(CSTVal));
          return I->getOperand(0);
        }
    }
  return 0;
}

/// dyn_castGetElementPtr - If this is a getelementptr instruction or constant
/// expression, return it.
static User *dyn_castGetElementPtr(Value *V) {
  if (isa<GetElementPtrInst>(V)) return cast<User>(V);
  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    if (CE->getOpcode() == Instruction::GetElementPtr)
      return cast<User>(V);
  return false;
}

/// 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;
}

/// AddOne - Add one to a ConstantInt
static ConstantInt *AddOne(ConstantInt *C) {
  APInt Val(C->getValue());
  return ConstantInt::get(++Val);
}
/// SubOne - Subtract one from a ConstantInt
static ConstantInt *SubOne(ConstantInt *C) {
  APInt Val(C->getValue());
  return ConstantInt::get(--Val);
}
/// Add - Add two ConstantInts together
static ConstantInt *Add(ConstantInt *C1, ConstantInt *C2) {
  return ConstantInt::get(C1->getValue() + C2->getValue());
}
/// And - Bitwise AND two ConstantInts together
static ConstantInt *And(ConstantInt *C1, ConstantInt *C2) {
  return ConstantInt::get(C1->getValue() & C2->getValue());
}
/// Subtract - Subtract one ConstantInt from another
static ConstantInt *Subtract(ConstantInt *C1, ConstantInt *C2) {
  return ConstantInt::get(C1->getValue() - C2->getValue());
}
/// Multiply - Multiply two ConstantInts together
static ConstantInt *Multiply(ConstantInt *C1, ConstantInt *C2) {
  return ConstantInt::get(C1->getValue() * C2->getValue());
}
/// MultiplyOverflows - True if the multiply can not be expressed in an int
/// this size.
static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) {
  uint32_t W = C1->getBitWidth();
  APInt LHSExt = C1->getValue(), RHSExt = C2->getValue();
  if (sign) {
    LHSExt.sext(W * 2);
    RHSExt.sext(W * 2);
  } else {
    LHSExt.zext(W * 2);
    RHSExt.zext(W * 2);
  }

  APInt MulExt = LHSExt * RHSExt;

  if (sign) {
    APInt Min = APInt::getSignedMinValue(W).sext(W * 2);
    APInt Max = APInt::getSignedMaxValue(W).sext(W * 2);
    return MulExt.slt(Min) || MulExt.sgt(Max);
  } else 
    return MulExt.ugt(APInt::getLowBitsSet(W * 2, W));
}


/// ShrinkDemandedConstant - Check to see if the specified operand of the 
/// specified instruction is a constant integer.  If so, check to see if there
/// are any bits set in the constant that are not demanded.  If so, shrink the
/// constant and return true.
static bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo, 
                                   APInt Demanded) {
  assert(I && "No instruction?");
  assert(OpNo < I->getNumOperands() && "Operand index too large");

  // If the operand is not a constant integer, nothing to do.
  ConstantInt *OpC = dyn_cast<ConstantInt>(I->getOperand(OpNo));
  if (!OpC) return false;

  // If there are no bits set that aren't demanded, nothing to do.
  Demanded.zextOrTrunc(OpC->getValue().getBitWidth());
  if ((~Demanded & OpC->getValue()) == 0)
    return false;

  // This instruction is producing bits that are not demanded. Shrink the RHS.
  Demanded &= OpC->getValue();
  I->setOperand(OpNo, ConstantInt::get(Demanded));
  return true;
}

// ComputeSignedMinMaxValuesFromKnownBits - Given a signed integer type and a 
// set of known zero and one bits, compute the maximum and minimum values that
// could have the specified known zero and known one bits, returning them in
// min/max.
static void ComputeSignedMinMaxValuesFromKnownBits(const Type *Ty,
                                                   const APInt& KnownZero,
                                                   const APInt& KnownOne,
                                                   APInt& Min, APInt& Max) {
  uint32_t BitWidth = cast<IntegerType>(Ty)->getBitWidth();
  assert(KnownZero.getBitWidth() == BitWidth && 
         KnownOne.getBitWidth() == BitWidth &&
         Min.getBitWidth() == BitWidth && Max.getBitWidth() == BitWidth &&
         "Ty, KnownZero, KnownOne and Min, Max must have equal bitwidth.");
  APInt UnknownBits = ~(KnownZero|KnownOne);

  // The minimum value is when all unknown bits are zeros, EXCEPT for the sign
  // bit if it is unknown.
  Min = KnownOne;
  Max = KnownOne|UnknownBits;
  
  if (UnknownBits[BitWidth-1]) { // Sign bit is unknown
    Min.set(BitWidth-1);
    Max.clear(BitWidth-1);
  }
}

// ComputeUnsignedMinMaxValuesFromKnownBits - Given an unsigned integer type and
// a set of known zero and one bits, compute the maximum and minimum values that
// could have the specified known zero and known one bits, returning them in
// min/max.
static void ComputeUnsignedMinMaxValuesFromKnownBits(const Type *Ty,
                                                     const APInt &KnownZero,
                                                     const APInt &KnownOne,
                                                     APInt &Min, APInt &Max) {
  uint32_t BitWidth = cast<IntegerType>(Ty)->getBitWidth(); BitWidth = BitWidth;
  assert(KnownZero.getBitWidth() == BitWidth && 
         KnownOne.getBitWidth() == BitWidth &&
         Min.getBitWidth() == BitWidth && Max.getBitWidth() &&
         "Ty, KnownZero, KnownOne and Min, Max must have equal bitwidth.");
  APInt UnknownBits = ~(KnownZero|KnownOne);
  
  // The minimum value is when the unknown bits are all zeros.
  Min = KnownOne;
  // The maximum value is when the unknown bits are all ones.
  Max = KnownOne|UnknownBits;
}

/// SimplifyDemandedBits - This function attempts to replace V with a simpler
/// value based on the demanded bits. When this function is called, it is known
/// that only the bits set in DemandedMask of the result of V are ever used
/// downstream. Consequently, depending on the mask and V, it may be possible
/// to replace V with a constant or one of its operands. In such cases, this
/// function does the replacement and returns true. In all other cases, it
/// returns false after analyzing the expression and setting KnownOne and known
/// to be one in the expression. KnownZero contains all the bits that are known
/// to be zero in the expression. These are provided to potentially allow the
/// caller (which might recursively be SimplifyDemandedBits itself) to simplify
/// the expression. KnownOne and KnownZero always follow the invariant that 
/// KnownOne & KnownZero == 0. That is, a bit can't be both 1 and 0. Note that
/// the bits in KnownOne and KnownZero may only be accurate for those bits set
/// in DemandedMask. Note also that the bitwidth of V, DemandedMask, KnownZero
/// and KnownOne must all be the same.
bool InstCombiner::SimplifyDemandedBits(Value *V, APInt DemandedMask,
                                        APInt& KnownZero, APInt& KnownOne,
                                        unsigned Depth) {
  assert(V != 0 && "Null pointer of Value???");
  assert(Depth <= 6 && "Limit Search Depth");
  uint32_t BitWidth = DemandedMask.getBitWidth();
  const IntegerType *VTy = cast<IntegerType>(V->getType());
  assert(VTy->getBitWidth() == BitWidth && 
         KnownZero.getBitWidth() == BitWidth && 
         KnownOne.getBitWidth() == BitWidth &&
         "Value *V, DemandedMask, KnownZero and KnownOne \
          must have same BitWidth");
  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
    // We know all of the bits for a constant!
    KnownOne = CI->getValue() & DemandedMask;
    KnownZero = ~KnownOne & DemandedMask;
    return false;
  }
  
  KnownZero.clear(); 
  KnownOne.clear();
  if (!V->hasOneUse()) {    // Other users may use these bits.
    if (Depth != 0) {       // Not at the root.
      // Just compute the KnownZero/KnownOne bits to simplify things downstream.
      ComputeMaskedBits(V, DemandedMask, KnownZero, KnownOne, Depth);
      return false;
    }
    // If this is the root being simplified, allow it to have multiple uses,
    // just set the DemandedMask to all bits.
    DemandedMask = APInt::getAllOnesValue(BitWidth);
  } else if (DemandedMask == 0) {   // Not demanding any bits from V.
    if (V != UndefValue::get(VTy))
      return UpdateValueUsesWith(V, UndefValue::get(VTy));
    return false;
  } else if (Depth == 6) {        // Limit search depth.
    return false;
  }
  
  Instruction *I = dyn_cast<Instruction>(V);
  if (!I) return false;        // Only analyze instructions.

  APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
  APInt &RHSKnownZero = KnownZero, &RHSKnownOne = KnownOne;
  switch (I->getOpcode()) {
  default:
    ComputeMaskedBits(V, DemandedMask, RHSKnownZero, RHSKnownOne, Depth);
    break;
  case Instruction::And:
    // If either the LHS or the RHS are Zero, the result is zero.
    if (SimplifyDemandedBits(I->getOperand(1), DemandedMask,
                             RHSKnownZero, RHSKnownOne, Depth+1))
      return true;
    assert((RHSKnownZero & RHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 

    // If something is known zero on the RHS, the bits aren't demanded on the
    // LHS.
    if (SimplifyDemandedBits(I->getOperand(0), DemandedMask & ~RHSKnownZero,
                             LHSKnownZero, LHSKnownOne, Depth+1))
      return true;
    assert((LHSKnownZero & LHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 

    // If all of the demanded bits are known 1 on one side, return the other.
    // These bits cannot contribute to the result of the 'and'.
    if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == 
        (DemandedMask & ~LHSKnownZero))
      return UpdateValueUsesWith(I, I->getOperand(0));
    if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == 
        (DemandedMask & ~RHSKnownZero))
      return UpdateValueUsesWith(I, I->getOperand(1));
    
    // If all of the demanded bits in the inputs are known zeros, return zero.
    if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask)
      return UpdateValueUsesWith(I, Constant::getNullValue(VTy));
      
    // If the RHS is a constant, see if we can simplify it.
    if (ShrinkDemandedConstant(I, 1, DemandedMask & ~LHSKnownZero))
      return UpdateValueUsesWith(I, I);
      
    // Output known-1 bits are only known if set in both the LHS & RHS.
    RHSKnownOne &= LHSKnownOne;
    // Output known-0 are known to be clear if zero in either the LHS | RHS.
    RHSKnownZero |= LHSKnownZero;
    break;
  case Instruction::Or:
    // If either the LHS or the RHS are One, the result is One.
    if (SimplifyDemandedBits(I->getOperand(1), DemandedMask, 
                             RHSKnownZero, RHSKnownOne, Depth+1))
      return true;
    assert((RHSKnownZero & RHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 
    // If something is known one on the RHS, the bits aren't demanded on the
    // LHS.
    if (SimplifyDemandedBits(I->getOperand(0), DemandedMask & ~RHSKnownOne, 
                             LHSKnownZero, LHSKnownOne, Depth+1))
      return true;
    assert((LHSKnownZero & LHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 
    
    // If all of the demanded bits are known zero on one side, return the other.
    // These bits cannot contribute to the result of the 'or'.
    if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == 
        (DemandedMask & ~LHSKnownOne))
      return UpdateValueUsesWith(I, I->getOperand(0));
    if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == 
        (DemandedMask & ~RHSKnownOne))
      return UpdateValueUsesWith(I, I->getOperand(1));

    // If all of the potentially set bits on one side are known to be set on
    // the other side, just use the 'other' side.
    if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == 
        (DemandedMask & (~RHSKnownZero)))
      return UpdateValueUsesWith(I, I->getOperand(0));
    if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == 
        (DemandedMask & (~LHSKnownZero)))
      return UpdateValueUsesWith(I, I->getOperand(1));
        
    // If the RHS is a constant, see if we can simplify it.
    if (ShrinkDemandedConstant(I, 1, DemandedMask))
      return UpdateValueUsesWith(I, I);
          
    // Output known-0 bits are only known if clear in both the LHS & RHS.
    RHSKnownZero &= LHSKnownZero;
    // Output known-1 are known to be set if set in either the LHS | RHS.
    RHSKnownOne |= LHSKnownOne;
    break;
  case Instruction::Xor: {
    if (SimplifyDemandedBits(I->getOperand(1), DemandedMask,
                             RHSKnownZero, RHSKnownOne, Depth+1))
      return true;
    assert((RHSKnownZero & RHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 
    if (SimplifyDemandedBits(I->getOperand(0), DemandedMask, 
                             LHSKnownZero, LHSKnownOne, Depth+1))
      return true;
    assert((LHSKnownZero & LHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 
    
    // If all of the demanded bits are known zero on one side, return the other.
    // These bits cannot contribute to the result of the 'xor'.
    if ((DemandedMask & RHSKnownZero) == DemandedMask)
      return UpdateValueUsesWith(I, I->getOperand(0));
    if ((DemandedMask & LHSKnownZero) == DemandedMask)
      return UpdateValueUsesWith(I, I->getOperand(1));
    
    // Output known-0 bits are known if clear or set in both the LHS & RHS.
    APInt KnownZeroOut = (RHSKnownZero & LHSKnownZero) | 
                         (RHSKnownOne & LHSKnownOne);
    // Output known-1 are known to be set if set in only one of the LHS, RHS.
    APInt KnownOneOut = (RHSKnownZero & LHSKnownOne) | 
                        (RHSKnownOne & LHSKnownZero);
    
    // If all of the demanded bits are known to be zero on one side or the
    // other, turn this into an *inclusive* or.
    //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
    if ((DemandedMask & ~RHSKnownZero & ~LHSKnownZero) == 0) {
      Instruction *Or =
        BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1),
                                 I->getName());
      InsertNewInstBefore(Or, *I);
      return UpdateValueUsesWith(I, Or);
    }
    
    // If all of the demanded bits on one side are known, and all of the set
    // bits on that side are also known to be set on the other side, turn this
    // into an AND, as we know the bits will be cleared.
    //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
    if ((DemandedMask & (RHSKnownZero|RHSKnownOne)) == DemandedMask) { 
      // all known
      if ((RHSKnownOne & LHSKnownOne) == RHSKnownOne) {
        Constant *AndC = ConstantInt::get(~RHSKnownOne & DemandedMask);
        Instruction *And = 
          BinaryOperator::CreateAnd(I->getOperand(0), AndC, "tmp");
        InsertNewInstBefore(And, *I);
        return UpdateValueUsesWith(I, And);
      }
    }
    
    // If the RHS is a constant, see if we can simplify it.
    // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1.
    if (ShrinkDemandedConstant(I, 1, DemandedMask))
      return UpdateValueUsesWith(I, I);
    
    RHSKnownZero = KnownZeroOut;
    RHSKnownOne  = KnownOneOut;
    break;
  }
  case Instruction::Select:
    if (SimplifyDemandedBits(I->getOperand(2), DemandedMask,
                             RHSKnownZero, RHSKnownOne, Depth+1))
      return true;
    if (SimplifyDemandedBits(I->getOperand(1), DemandedMask, 
                             LHSKnownZero, LHSKnownOne, Depth+1))
      return true;
    assert((RHSKnownZero & RHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 
    assert((LHSKnownZero & LHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 
    
    // If the operands are constants, see if we can simplify them.
    if (ShrinkDemandedConstant(I, 1, DemandedMask))
      return UpdateValueUsesWith(I, I);
    if (ShrinkDemandedConstant(I, 2, DemandedMask))
      return UpdateValueUsesWith(I, I);
    
    // Only known if known in both the LHS and RHS.
    RHSKnownOne &= LHSKnownOne;
    RHSKnownZero &= LHSKnownZero;
    break;
  case Instruction::Trunc: {
    uint32_t truncBf = 
      cast<IntegerType>(I->getOperand(0)->getType())->getBitWidth();
    DemandedMask.zext(truncBf);
    RHSKnownZero.zext(truncBf);
    RHSKnownOne.zext(truncBf);
    if (SimplifyDemandedBits(I->getOperand(0), DemandedMask, 
                             RHSKnownZero, RHSKnownOne, Depth+1))
      return true;
    DemandedMask.trunc(BitWidth);
    RHSKnownZero.trunc(BitWidth);
    RHSKnownOne.trunc(BitWidth);
    assert((RHSKnownZero & RHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 
    break;
  }
  case Instruction::BitCast:
    if (!I->getOperand(0)->getType()->isInteger())
      return false;
      
    if (SimplifyDemandedBits(I->getOperand(0), DemandedMask,
                             RHSKnownZero, RHSKnownOne, Depth+1))
      return true;
    assert((RHSKnownZero & RHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 
    break;
  case Instruction::ZExt: {
    // Compute the bits in the result that are not present in the input.
    const IntegerType *SrcTy = cast<IntegerType>(I->getOperand(0)->getType());
    uint32_t SrcBitWidth = SrcTy->getBitWidth();
    
    DemandedMask.trunc(SrcBitWidth);
    RHSKnownZero.trunc(SrcBitWidth);
    RHSKnownOne.trunc(SrcBitWidth);
    if (SimplifyDemandedBits(I->getOperand(0), DemandedMask,
                             RHSKnownZero, RHSKnownOne, Depth+1))
      return true;
    DemandedMask.zext(BitWidth);
    RHSKnownZero.zext(BitWidth);
    RHSKnownOne.zext(BitWidth);
    assert((RHSKnownZero & RHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 
    // The top bits are known to be zero.
    RHSKnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth);
    break;
  }
  case Instruction::SExt: {
    // Compute the bits in the result that are not present in the input.
    const IntegerType *SrcTy = cast<IntegerType>(I->getOperand(0)->getType());
    uint32_t SrcBitWidth = SrcTy->getBitWidth();
    
    APInt InputDemandedBits = DemandedMask & 
                              APInt::getLowBitsSet(BitWidth, SrcBitWidth);

    APInt NewBits(APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth));
    // If any of the sign extended bits are demanded, we know that the sign
    // bit is demanded.
    if ((NewBits & DemandedMask) != 0)
      InputDemandedBits.set(SrcBitWidth-1);
      
    InputDemandedBits.trunc(SrcBitWidth);
    RHSKnownZero.trunc(SrcBitWidth);
    RHSKnownOne.trunc(SrcBitWidth);
    if (SimplifyDemandedBits(I->getOperand(0), InputDemandedBits,
                             RHSKnownZero, RHSKnownOne, Depth+1))
      return true;
    InputDemandedBits.zext(BitWidth);
    RHSKnownZero.zext(BitWidth);
    RHSKnownOne.zext(BitWidth);
    assert((RHSKnownZero & RHSKnownOne) == 0 && 
           "Bits known to be one AND zero?"); 
      
    // If the sign bit of the input is known set or clear, then we know the
    // top bits of the result.

    // If the input sign bit is known zero, or if the NewBits are not demanded
    // convert this into a zero extension.
    if (RHSKnownZero[SrcBitWidth-1] || (NewBits & ~DemandedMask) == NewBits)
    {
      // Convert to ZExt cast
      CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName(), I);
      return UpdateValueUsesWith(I, NewCast);
    } else if (RHSKnownOne[SrcBitWidth-1]) {    // Input sign bit known set
      RHSKnownOne |= NewBits;
    }
    break;
  }
  case Instruction::Add: {
    // Figure out what the input bits are.  If the top bits of the and result
    // are not demanded, then the add doesn't demand them from its input
    // either.
    uint32_t NLZ = DemandedMask.countLeadingZeros();
      
    // If there is a constant on the RHS, there are a variety of xformations
    // we can do.
    if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
      // If null, this should be simplified elsewhere.  Some of the xforms here
      // won't work if the RHS is zero.
      if (RHS->isZero())
        break;
      
      // If the top bit of the output is demanded, demand everything from the
      // input.  Otherwise, we demand all the input bits except NLZ top bits.
      APInt InDemandedBits(APInt::getLowBitsSet(BitWidth, BitWidth - NLZ));

      // Find information about known zero/one bits in the input.
      if (SimplifyDemandedBits(I->getOperand(0), InDemandedBits, 
                               LHSKnownZero, LHSKnownOne, Depth+1))
        return true;

      // If the RHS of the add has bits set that can't affect the input, reduce
      // the constant.
      if (ShrinkDemandedConstant(I, 1, InDemandedBits))
        return UpdateValueUsesWith(I, I);
      
      // Avoid excess work.
      if (LHSKnownZero == 0 && LHSKnownOne == 0)
        break;
      
      // Turn it into OR if input bits are zero.
      if ((LHSKnownZero & RHS->getValue()) == RHS->getValue()) {
        Instruction *Or =
          BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1),
                                   I->getName());
        InsertNewInstBefore(Or, *I);
        return UpdateValueUsesWith(I, Or);
      }
      
      // We can say something about the output known-zero and known-one bits,
      // depending on potential carries from the input constant and the
      // unknowns.  For example if the LHS is known to have at most the 0x0F0F0
      // bits set and the RHS constant is 0x01001, then we know we have a known
      // one mask of 0x00001 and a known zero mask of 0xE0F0E.
      
      // To compute this, we first compute the potential carry bits.  These are
      // the bits which may be modified.  I'm not aware of a better way to do
      // this scan.
      const APInt& RHSVal = RHS->getValue();
      APInt CarryBits((~LHSKnownZero + RHSVal) ^ (~LHSKnownZero ^ RHSVal));
      
      // Now that we know which bits have carries, compute the known-1/0 sets.
      
      // Bits are known one if they are known zero in one operand and one in the
      // other, and there is no input carry.
      RHSKnownOne = ((LHSKnownZero & RHSVal) | 
                     (LHSKnownOne & ~RHSVal)) & ~CarryBits;
      
      // Bits are known zero if they are known zero in both operands and there
      // is no input carry.
      RHSKnownZero = LHSKnownZero & ~RHSVal & ~CarryBits;
    } else {
      // If the high-bits of this ADD are not demanded, then it does not demand
      // the high bits of its LHS or RHS.
      if (DemandedMask[BitWidth-1] == 0) {
        // Right fill the mask of bits for this ADD to demand the most
        // significant bit and all those below it.
        APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ));
        if (SimplifyDemandedBits(I->getOperand(0), DemandedFromOps,
                                 LHSKnownZero, LHSKnownOne, Depth+1))
          return true;
        if (SimplifyDemandedBits(I->getOperand(1), DemandedFromOps,
                                 LHSKnownZero, LHSKnownOne, Depth+1))
          return true;
      }
    }
    break;
  }
  case Instruction::Sub:
    // If the high-bits of this SUB are not demanded, then it does not demand
    // the high bits of its LHS or RHS.
    if (DemandedMask[BitWidth-1] == 0) {
      // Right fill the mask of bits for this SUB to demand the most
      // significant bit and all those below it.
      uint32_t NLZ = DemandedMask.countLeadingZeros();
      APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ));
      if (SimplifyDemandedBits(I->getOperand(0), DemandedFromOps,
                               LHSKnownZero, LHSKnownOne, Depth+1))
        return true;
      if (SimplifyDemandedBits(I->getOperand(1), DemandedFromOps,
                               LHSKnownZero, LHSKnownOne, Depth+1))
        return true;
    }
    // Otherwise just hand the sub off to ComputeMaskedBits to fill in
    // the known zeros and ones.
    ComputeMaskedBits(V, DemandedMask, RHSKnownZero, RHSKnownOne, Depth);
    break;
  case Instruction::Shl:
    if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
      uint64_t ShiftAmt = SA->getLimitedValue(BitWidth);
      APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt));
      if (SimplifyDemandedBits(I->getOperand(0), DemandedMaskIn, 
                               RHSKnownZero, RHSKnownOne, Depth+1))
        return true;
      assert((RHSKnownZero & RHSKnownOne) == 0 && 
             "Bits known to be one AND zero?"); 
      RHSKnownZero <<= ShiftAmt;
      RHSKnownOne  <<= ShiftAmt;
      // low bits known zero.
      if (ShiftAmt)
        RHSKnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
    }
    break;
  case Instruction::LShr:
    // For a logical shift right
    if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
      uint64_t ShiftAmt = SA->getLimitedValue(BitWidth);
      
      // Unsigned shift right.
      APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
      if (SimplifyDemandedBits(I->getOperand(0), DemandedMaskIn,
                               RHSKnownZero, RHSKnownOne, Depth+1))
        return true;
      assert((RHSKnownZero & RHSKnownOne) == 0 && 
             "Bits known to be one AND zero?"); 
      RHSKnownZero = APIntOps::lshr(RHSKnownZero, ShiftAmt);
      RHSKnownOne  = APIntOps::lshr(RHSKnownOne, ShiftAmt);
      if (ShiftAmt) {
        // Compute the new bits that are at the top now.
        APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt));
        RHSKnownZero |= HighBits;  // high bits known zero.
      }
    }
    break;
  case Instruction::AShr:
    // If this is an arithmetic shift right and only the low-bit is set, we can
    // always convert this into a logical shr, even if the shift amount is
    // variable.  The low bit of the shift cannot be an input sign bit unless
    // the shift amount is >= the size of the datatype, which is undefined.
    if (DemandedMask == 1) {
      // Perform the logical shift right.
      Value *NewVal = BinaryOperator::CreateLShr(
                        I->getOperand(0), I->getOperand(1), I->getName());
      InsertNewInstBefore(cast<Instruction>(NewVal), *I);
      return UpdateValueUsesWith(I, NewVal);
    }    

    // If the sign bit is the only bit demanded by this ashr, th