X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FInstructionCombining.cpp;h=92b7f1a39bc719a7c367ff8fadc1463d8f10dc2e;hb=6ffe551f657c948d6a473a198ecbd1188bf9ce45;hp=d9c6ccee8d48fa0d31b7eaa58c48ebb659cd9c18;hpb=bc5d41482392d4ebd7fa2b992bbe89980ebd4f6c;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp index d9c6ccee8d4..92b7f1a39bc 100644 --- a/lib/Transforms/Scalar/InstructionCombining.cpp +++ b/lib/Transforms/Scalar/InstructionCombining.cpp @@ -1,4 +1,11 @@ //===- InstructionCombining.cpp - Combine multiple instructions -----------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and 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 @@ -12,22 +19,39 @@ // // 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. SetCC instructions are converted from <,>,<=,>= to ==,!= if possible +// 4. All SetCC 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. +// N. This list is incomplete +// //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "instcombine" #include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Transforms/Utils/Local.h" #include "llvm/Instructions.h" +#include "llvm/Intrinsics.h" #include "llvm/Pass.h" #include "llvm/Constants.h" -#include "llvm/ConstantHandling.h" #include "llvm/DerivedTypes.h" #include "llvm/GlobalVariable.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/GetElementPtrTypeIterator.h" #include "llvm/Support/InstIterator.h" #include "llvm/Support/InstVisitor.h" -#include "llvm/Support/CallSite.h" +#include "Support/Debug.h" #include "Support/Statistic.h" #include +using namespace llvm; namespace { Statistic<> NumCombined ("instcombine", "Number of insts combined"); @@ -38,25 +62,39 @@ namespace { public InstVisitor { // Worklist of all of the instructions that need to be simplified. std::vector WorkList; + TargetData *TD; - void AddUsesToWorkList(Instruction &I) { - // The instruction was simplified, add all users of the instruction to - // the work lists because they might get more simplified now... - // + /// 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(Instruction &I) { for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE; ++UI) WorkList.push_back(cast(*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 (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) + if (Instruction *Op = dyn_cast(I.getOperand(i))) + WorkList.push_back(Op); + } + // removeFromWorkList - remove all instances of I from the worklist. void removeFromWorkList(Instruction *I); public: virtual bool runOnFunction(Function &F); virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); AU.setPreservesCFG(); } + TargetData &getTargetData() const { return *TD; } + // Visitation implementation - Implement instruction combining for different // instruction types. The semantics are as follows: // Return Value: @@ -75,11 +113,13 @@ namespace { Instruction *visitSetCondInst(BinaryOperator &I); Instruction *visitShiftInst(ShiftInst &I); Instruction *visitCastInst(CastInst &CI); + 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 *visitBranchInst(BranchInst &BI); @@ -87,17 +127,20 @@ namespace { Instruction *visitInstruction(Instruction &I) { return 0; } private: + Instruction *visitCallSite(CallSite CS); bool transformConstExprCastCall(CallSite CS); + public: // InsertNewInstBefore - insert an instruction New before instruction Old // in the program. Add the new instruction to the worklist. // - void InsertNewInstBefore(Instruction *New, Instruction &Old) { + Value *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 WorkList.push_back(New); // Add to worklist + return New; } // ReplaceInstUsesWith - This method is to be used when an instruction is @@ -107,14 +150,45 @@ namespace { // modified. // Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) { - AddUsesToWorkList(I); // Add all modified instrs to worklist - I.replaceAllUsesWith(V); - return &I; + 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(Constant::getNullValue(I.getType())); + return &I; + } } + // 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.getParent()->getInstList().erase(&I); + return 0; // Don't do anything with FI + } + + + 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(Value *V, const Type *DestTy, + Instruction *InsertBefore); + // SimplifyCommutative - This performs a few simplifications for commutative // operators... bool SimplifyCommutative(BinaryOperator &I); + + Instruction *OptAndOp(Instruction *Op, ConstantIntegral *OpRHS, + ConstantIntegral *AndRHS, BinaryOperator &TheAnd); }; RegisterOpt X("instcombine", "Combine redundant instructions"); @@ -135,7 +209,44 @@ static unsigned getComplexity(Value *V) { // isOnlyUse - Return true if this instruction will be deleted if we stop using // it. static bool isOnlyUse(Value *V) { - return V->use_size() == 1 || isa(V); + return V->hasOneUse() || isa(V); +} + +// getSignedIntegralType - Given an unsigned integral type, return the signed +// version of it that has the same size. +static const Type *getSignedIntegralType(const Type *Ty) { + switch (Ty->getPrimitiveID()) { + default: assert(0 && "Invalid unsigned integer type!"); abort(); + case Type::UByteTyID: return Type::SByteTy; + case Type::UShortTyID: return Type::ShortTy; + case Type::UIntTyID: return Type::IntTy; + case Type::ULongTyID: return Type::LongTy; + } +} + +// getUnsignedIntegralType - Given an signed integral type, return the unsigned +// version of it that has the same size. +static const Type *getUnsignedIntegralType(const Type *Ty) { + switch (Ty->getPrimitiveID()) { + default: assert(0 && "Invalid signed integer type!"); abort(); + case Type::SByteTyID: return Type::UByteTy; + case Type::ShortTyID: return Type::UShortTy; + case Type::IntTyID: return Type::UIntTy; + case Type::LongTyID: return Type::ULongTy; + } +} + +// getPromotedType - Return the specified type promoted as it would be to pass +// though a va_arg area... +static const Type *getPromotedType(const Type *Ty) { + switch (Ty->getPrimitiveID()) { + case Type::SByteTyID: + case Type::ShortTyID: return Type::IntTy; + case Type::UByteTyID: + case Type::UShortTyID: return Type::UIntTy; + case Type::FloatTyID: return Type::DoubleTy; + default: return Ty; + } } // SimplifyCommutative - This performs a few simplifications for commutative @@ -198,14 +309,18 @@ static inline Value *dyn_castNegVal(Value *V) { return 0; } +static Constant *NotConstant(Constant *C) { + return ConstantExpr::get(Instruction::Xor, C, + ConstantIntegral::getAllOnesValue(C->getType())); +} + static inline Value *dyn_castNotVal(Value *V) { if (BinaryOperator::isNot(V)) return BinaryOperator::getNotArgument(cast(V)); // Constants can be considered to be not'ed values... if (ConstantIntegral *C = dyn_cast(V)) - return ConstantExpr::get(Instruction::Xor, - ConstantIntegral::getAllOnesValue(C->getType()),C); + return NotConstant(C); return 0; } @@ -214,7 +329,7 @@ static inline Value *dyn_castNotVal(Value *V) { // non-constant operand of the multiply. // static inline Value *dyn_castFoldableMul(Value *V) { - if (V->use_size() == 1 && V->getType()->isInteger()) + if (V->hasOneUse() && V->getType()->isInteger()) if (Instruction *I = dyn_cast(V)) if (I->getOpcode() == Instruction::Mul) if (isa(I->getOperand(1))) @@ -225,7 +340,8 @@ static inline Value *dyn_castFoldableMul(Value *V) { // dyn_castMaskingAnd - If this value is an And instruction masking a value with // a constant, return the constant being anded with. // -static inline Constant *dyn_castMaskingAnd(Value *V) { +template +static inline Constant *dyn_castMaskingAnd(ValueType *V) { if (Instruction *I = dyn_cast(V)) if (I->getOpcode() == Instruction::And) return dyn_cast(I->getOperand(1)); @@ -247,13 +363,184 @@ static unsigned Log2(uint64_t Val) { return Count; } + +/// AssociativeOpt - Perform an optimization on an associative operator. This +/// function is designed to check a chain of associative operators for a +/// potential to apply a certain optimization. Since the optimization may be +/// applicable if the expression was reassociated, this checks the chain, then +/// reassociates the expression as necessary to expose the optimization +/// opportunity. This makes use of a special Functor, which must define +/// 'shouldApply' and 'apply' methods. +/// +template +Instruction *AssociativeOpt(BinaryOperator &Root, const Functor &F) { + unsigned Opcode = Root.getOpcode(); + Value *LHS = Root.getOperand(0); + + // Quick check, see if the immediate LHS matches... + if (F.shouldApply(LHS)) + return F.apply(Root); + + // Otherwise, if the LHS is not of the same opcode as the root, return. + Instruction *LHSI = dyn_cast(LHS); + while (LHSI && LHSI->getOpcode() == Opcode && LHSI->hasOneUse()) { + // Should we apply this transform to the RHS? + bool ShouldApply = F.shouldApply(LHSI->getOperand(1)); + + // If not to the RHS, check to see if we should apply to the LHS... + if (!ShouldApply && F.shouldApply(LHSI->getOperand(0))) { + cast(LHSI)->swapOperands(); // Make the LHS the RHS + ShouldApply = true; + } + + // If the functor wants to apply the optimization to the RHS of LHSI, + // reassociate the expression from ((? op A) op B) to (? op (A op B)) + if (ShouldApply) { + BasicBlock *BB = Root.getParent(); + + // Now all of the instructions are in the current basic block, go ahead + // and perform the reassociation. + Instruction *TmpLHSI = cast(Root.getOperand(0)); + + // First move the selected RHS to the LHS of the root... + Root.setOperand(0, LHSI->getOperand(1)); + + // Make what used to be the LHS of the root be the user of the root... + Value *ExtraOperand = TmpLHSI->getOperand(1); + if (&Root == TmpLHSI) { + Root.replaceAllUsesWith(Constant::getNullValue(TmpLHSI->getType())); + return 0; + } + Root.replaceAllUsesWith(TmpLHSI); // Users now use TmpLHSI + TmpLHSI->setOperand(1, &Root); // TmpLHSI now uses the root + TmpLHSI->getParent()->getInstList().remove(TmpLHSI); + BasicBlock::iterator ARI = &Root; ++ARI; + BB->getInstList().insert(ARI, TmpLHSI); // Move TmpLHSI to after Root + ARI = Root; + + // Now propagate the ExtraOperand down the chain of instructions until we + // get to LHSI. + while (TmpLHSI != LHSI) { + Instruction *NextLHSI = cast(TmpLHSI->getOperand(0)); + // Move the instruction to immediately before the chain we are + // constructing to avoid breaking dominance properties. + NextLHSI->getParent()->getInstList().remove(NextLHSI); + BB->getInstList().insert(ARI, NextLHSI); + ARI = NextLHSI; + + Value *NextOp = NextLHSI->getOperand(1); + NextLHSI->setOperand(1, ExtraOperand); + TmpLHSI = NextLHSI; + ExtraOperand = NextOp; + } + + // Now that the instructions are reassociated, have the functor perform + // the transformation... + return F.apply(Root); + } + + LHSI = dyn_cast(LHSI->getOperand(0)); + } + return 0; +} + + +// AddRHS - Implements: X + X --> X << 1 +struct AddRHS { + Value *RHS; + AddRHS(Value *rhs) : RHS(rhs) {} + bool shouldApply(Value *LHS) const { return LHS == RHS; } + Instruction *apply(BinaryOperator &Add) const { + return new ShiftInst(Instruction::Shl, Add.getOperand(0), + ConstantInt::get(Type::UByteTy, 1)); + } +}; + +// AddMaskingAnd - Implements (A & C1)+(B & C2) --> (A & C1)|(B & C2) +// iff C1&C2 == 0 +struct AddMaskingAnd { + Constant *C2; + AddMaskingAnd(Constant *c) : C2(c) {} + bool shouldApply(Value *LHS) const { + if (Constant *C1 = dyn_castMaskingAnd(LHS)) + return ConstantExpr::get(Instruction::And, C1, C2)->isNullValue(); + return false; + } + Instruction *apply(BinaryOperator &Add) const { + return BinaryOperator::create(Instruction::Or, Add.getOperand(0), + Add.getOperand(1)); + } +}; + +static Value *FoldOperationIntoSelectOperand(Instruction &BI, Value *SO, + InstCombiner *IC) { + // Figure out if the constant is the left or the right argument. + bool ConstIsRHS = isa(BI.getOperand(1)); + Constant *ConstOperand = cast(BI.getOperand(ConstIsRHS)); + + if (Constant *SOC = dyn_cast(SO)) { + if (ConstIsRHS) + return ConstantExpr::get(BI.getOpcode(), SOC, ConstOperand); + return ConstantExpr::get(BI.getOpcode(), ConstOperand, SOC); + } + + Value *Op0 = SO, *Op1 = ConstOperand; + if (!ConstIsRHS) + std::swap(Op0, Op1); + Instruction *New; + if (BinaryOperator *BO = dyn_cast(&BI)) + New = BinaryOperator::create(BO->getOpcode(), Op0, Op1); + else if (ShiftInst *SI = dyn_cast(&BI)) + New = new ShiftInst(SI->getOpcode(), Op0, Op1); + else { + assert(0 && "Unknown binary instruction type!"); + abort(); + } + return IC->InsertNewInstBefore(New, BI); +} + +// FoldBinOpIntoSelect - Given an instruction with a select as one operand and a +// constant as the other operand, try to fold the binary operator into the +// select arguments. +static Instruction *FoldBinOpIntoSelect(Instruction &BI, SelectInst *SI, + InstCombiner *IC) { + // Don't modify shared select instructions + if (!SI->hasOneUse()) return 0; + Value *TV = SI->getOperand(1); + Value *FV = SI->getOperand(2); + + if (isa(TV) || isa(FV)) { + Value *SelectTrueVal = FoldOperationIntoSelectOperand(BI, TV, IC); + Value *SelectFalseVal = FoldOperationIntoSelectOperand(BI, FV, IC); + + return new SelectInst(SI->getCondition(), SelectTrueVal, + SelectFalseVal); + } + return 0; +} + Instruction *InstCombiner::visitAdd(BinaryOperator &I) { bool Changed = SimplifyCommutative(I); Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); - // Eliminate 'add int %X, 0' - if (RHS == Constant::getNullValue(I.getType())) - return ReplaceInstUsesWith(I, LHS); + if (Constant *RHSC = dyn_cast(RHS)) { + // X + 0 --> X + if (!I.getType()->isFloatingPoint() && // -0 + +0 = +0, so it's not a noop + RHSC->isNullValue()) + return ReplaceInstUsesWith(I, LHS); + + // X + (signbit) --> X ^ signbit + if (ConstantInt *CI = dyn_cast(RHSC)) { + unsigned NumBits = CI->getType()->getPrimitiveSize()*8; + uint64_t Val = CI->getRawValue() & (1ULL << NumBits)-1; + if (Val == (1ULL << NumBits-1)) + return BinaryOperator::create(Instruction::Xor, LHS, RHS); + } + } + + // X + X --> X << 1 + if (I.getType()->isInteger()) + if (Instruction *Result = AssociativeOpt(I, AddRHS(RHS))) return Result; // -A + B --> B - A if (Value *V = dyn_castNegVal(LHS)) @@ -282,11 +569,31 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { return BinaryOperator::create(Instruction::Mul, LHS, CP1); } - // (A & C1)+(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 - if (Constant *C1 = dyn_castMaskingAnd(LHS)) - if (Constant *C2 = dyn_castMaskingAnd(RHS)) - if (ConstantExpr::get(Instruction::And, C1, C2)->isNullValue()) - return BinaryOperator::create(Instruction::Or, LHS, RHS); + // (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0 + if (Constant *C2 = dyn_castMaskingAnd(RHS)) + if (Instruction *R = AssociativeOpt(I, AddMaskingAnd(C2))) return R; + + if (ConstantInt *CRHS = dyn_cast(RHS)) { + if (Instruction *ILHS = dyn_cast(LHS)) { + switch (ILHS->getOpcode()) { + case Instruction::Xor: + // ~X + C --> (C-1) - X + if (ConstantInt *XorRHS = dyn_cast(ILHS->getOperand(1))) + if (XorRHS->isAllOnesValue()) + return BinaryOperator::create(Instruction::Sub, + ConstantExpr::get(Instruction::Sub, + CRHS, ConstantInt::get(I.getType(), 1)), + ILHS->getOperand(0)); + break; + case Instruction::Select: + // Try to fold constant add into select arguments. + if (Instruction *R = FoldBinOpIntoSelect(I,cast(ILHS),this)) + return R; + + default: break; + } + } + } return Changed ? &I : 0; } @@ -298,6 +605,25 @@ static bool isSignBit(ConstantInt *CI) { return (CI->getRawValue() & ~(-1LL << NumBits)) == (1ULL << (NumBits-1)); } +static unsigned getTypeSizeInBits(const Type *Ty) { + return Ty == Type::BoolTy ? 1 : Ty->getPrimitiveSize()*8; +} + +/// RemoveNoopCast - Strip off nonconverting casts from the value. +/// +static Value *RemoveNoopCast(Value *V) { + if (CastInst *CI = dyn_cast(V)) { + const Type *CTy = CI->getType(); + const Type *OpTy = CI->getOperand(0)->getType(); + if (CTy->isInteger() && OpTy->isInteger()) { + if (CTy->getPrimitiveSize() == OpTy->getPrimitiveSize()) + return RemoveNoopCast(CI->getOperand(0)); + } else if (isa(CTy) && isa(OpTy)) + return RemoveNoopCast(CI->getOperand(0)); + } + return V; +} + Instruction *InstCombiner::visitSub(BinaryOperator &I) { Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); @@ -308,17 +634,61 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { if (Value *V = dyn_castNegVal(Op1)) return BinaryOperator::create(Instruction::Add, Op0, V); - // Replace (-1 - A) with (~A)... - if (ConstantInt *C = dyn_cast(Op0)) + if (ConstantInt *C = dyn_cast(Op0)) { + // Replace (-1 - A) with (~A)... if (C->isAllOnesValue()) return BinaryOperator::createNot(Op1); + // C - ~X == X + (1+C) + if (BinaryOperator::isNot(Op1)) + return BinaryOperator::create(Instruction::Add, + BinaryOperator::getNotArgument(cast(Op1)), + ConstantExpr::get(Instruction::Add, C, + ConstantInt::get(I.getType(), 1))); + // -((uint)X >> 31) -> ((int)X >> 31) + // -((int)X >> 31) -> ((uint)X >> 31) + if (C->isNullValue()) { + Value *NoopCastedRHS = RemoveNoopCast(Op1); + if (ShiftInst *SI = dyn_cast(NoopCastedRHS)) + if (SI->getOpcode() == Instruction::Shr) + if (ConstantUInt *CU = dyn_cast(SI->getOperand(1))) { + const Type *NewTy; + if (SI->getType()->isSigned()) + NewTy = getUnsignedIntegralType(SI->getType()); + else + NewTy = getSignedIntegralType(SI->getType()); + // Check to see if we are shifting out everything but the sign bit. + if (CU->getValue() == SI->getType()->getPrimitiveSize()*8-1) { + // Ok, the transformation is safe. Insert a cast of the incoming + // value, then the new shift, then the new cast. + Instruction *FirstCast = new CastInst(SI->getOperand(0), NewTy, + SI->getOperand(0)->getName()); + Value *InV = InsertNewInstBefore(FirstCast, I); + Instruction *NewShift = new ShiftInst(Instruction::Shr, FirstCast, + CU, SI->getName()); + if (NewShift->getType() == I.getType()) + return NewShift; + else { + InV = InsertNewInstBefore(NewShift, I); + return new CastInst(NewShift, I.getType()); + } + } + } + } + + // Try to fold constant sub into select arguments. + if (SelectInst *SI = dyn_cast(Op1)) + if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) + return R; + } + if (BinaryOperator *Op1I = dyn_cast(Op1)) - if (Op1I->use_size() == 1) { + if (Op1I->hasOneUse()) { // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression // is not used by anyone else... // - if (Op1I->getOpcode() == Instruction::Sub) { + if (Op1I->getOpcode() == Instruction::Sub && + !Op1I->getType()->isFloatingPoint()) { // Swap the two operands of the subexpr... Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1); Op1I->setOperand(0, IIOp1); @@ -362,6 +732,26 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { return 0; } +/// isSignBitCheck - Given an exploded setcc instruction, return true if it is +/// really just returns true if the most significant (sign) bit is set. +static bool isSignBitCheck(unsigned Opcode, Value *LHS, ConstantInt *RHS) { + if (RHS->getType()->isSigned()) { + // True if source is LHS < 0 or LHS <= -1 + return Opcode == Instruction::SetLT && RHS->isNullValue() || + Opcode == Instruction::SetLE && RHS->isAllOnesValue(); + } else { + ConstantUInt *RHSC = cast(RHS); + // True if source is LHS > 127 or LHS >= 128, where the constants depend on + // the size of the integer type. + if (Opcode == Instruction::SetGE) + return RHSC->getValue() == 1ULL<<(RHS->getType()->getPrimitiveSize()*8-1); + if (Opcode == Instruction::SetGT) + return RHSC->getValue() == + (1ULL << (RHS->getType()->getPrimitiveSize()*8-1))-1; + } + return false; +} + Instruction *InstCombiner::visitMul(BinaryOperator &I) { bool Changed = SimplifyCommutative(I); Value *Op0 = I.getOperand(0); @@ -369,19 +759,22 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { // Simplify mul instructions with a constant RHS... if (Constant *Op1 = dyn_cast(I.getOperand(1))) { if (ConstantInt *CI = dyn_cast(Op1)) { - const Type *Ty = CI->getType(); - int64_t Val = (int64_t)cast(CI)->getRawValue(); - switch (Val) { - case -1: // X * -1 -> -X + + // ((X << C1)*C2) == (X * (C2 << C1)) + if (ShiftInst *SI = dyn_cast(Op0)) + if (SI->getOpcode() == Instruction::Shl) + if (Constant *ShOp = dyn_cast(SI->getOperand(1))) + return BinaryOperator::create(Instruction::Mul, SI->getOperand(0), + ConstantExpr::get(Instruction::Shl, CI, ShOp)); + + if (CI->isNullValue()) + return ReplaceInstUsesWith(I, Op1); // X * 0 == 0 + if (CI->equalsInt(1)) // X * 1 == X + return ReplaceInstUsesWith(I, Op0); + if (CI->isAllOnesValue()) // X * -1 == 0 - X return BinaryOperator::createNeg(Op0, I.getName()); - case 0: - return ReplaceInstUsesWith(I, Op1); // Eliminate 'mul double %X, 0' - case 1: - return ReplaceInstUsesWith(I, Op0); // Eliminate 'mul int %X, 1' - case 2: // Convert 'mul int %X, 2' to 'add int %X, %X' - return BinaryOperator::create(Instruction::Add, Op0, Op0, I.getName()); - } + int64_t Val = (int64_t)cast(CI)->getRawValue(); if (uint64_t C = Log2(Val)) // Replace X*(2^C) with X << C return new ShiftInst(Instruction::Shl, Op0, ConstantUInt::get(Type::UByteTy, C)); @@ -395,21 +788,76 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { if (Op1F->getValue() == 1.0) return ReplaceInstUsesWith(I, Op0); // Eliminate 'mul double %X, 1.0' } + + // Try to fold constant mul into select arguments. + if (SelectInst *SI = dyn_cast(Op0)) + if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) + return R; } if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y if (Value *Op1v = dyn_castNegVal(I.getOperand(1))) return BinaryOperator::create(Instruction::Mul, Op0v, Op1v); + // If one of the operands of the multiply is a cast from a boolean value, then + // we know the bool is either zero or one, so this is a 'masking' multiply. + // See if we can simplify things based on how the boolean was originally + // formed. + CastInst *BoolCast = 0; + if (CastInst *CI = dyn_cast(I.getOperand(0))) + if (CI->getOperand(0)->getType() == Type::BoolTy) + BoolCast = CI; + if (!BoolCast) + if (CastInst *CI = dyn_cast(I.getOperand(1))) + if (CI->getOperand(0)->getType() == Type::BoolTy) + BoolCast = CI; + if (BoolCast) { + if (SetCondInst *SCI = dyn_cast(BoolCast->getOperand(0))) { + Value *SCIOp0 = SCI->getOperand(0), *SCIOp1 = SCI->getOperand(1); + const Type *SCOpTy = SCIOp0->getType(); + + // If the setcc is true iff the sign bit of X is set, then convert this + // multiply into a shift/and combination. + if (isa(SCIOp1) && + isSignBitCheck(SCI->getOpcode(), SCIOp0, cast(SCIOp1))) { + // Shift the X value right to turn it into "all signbits". + Constant *Amt = ConstantUInt::get(Type::UByteTy, + SCOpTy->getPrimitiveSize()*8-1); + if (SCIOp0->getType()->isUnsigned()) { + const Type *NewTy = getSignedIntegralType(SCIOp0->getType()); + SCIOp0 = InsertNewInstBefore(new CastInst(SCIOp0, NewTy, + SCIOp0->getName()), I); + } + + Value *V = + InsertNewInstBefore(new ShiftInst(Instruction::Shr, SCIOp0, Amt, + BoolCast->getOperand(0)->getName()+ + ".mask"), I); + + // If the multiply type is not the same as the source type, sign extend + // or truncate to the multiply type. + if (I.getType() != V->getType()) + V = InsertNewInstBefore(new CastInst(V, I.getType(), V->getName()),I); + + Value *OtherOp = Op0 == BoolCast ? I.getOperand(1) : Op0; + return BinaryOperator::create(Instruction::And, V, OtherOp); + } + } + } + return Changed ? &I : 0; } Instruction *InstCombiner::visitDiv(BinaryOperator &I) { - // div X, 1 == X if (ConstantInt *RHS = dyn_cast(I.getOperand(1))) { + // div X, 1 == X if (RHS->equalsInt(1)) return ReplaceInstUsesWith(I, I.getOperand(0)); + // div X, -1 == -X + if (RHS->isAllOnesValue()) + return BinaryOperator::createNeg(I.getOperand(0)); + // Check to see if this is an unsigned division with an exact power of 2, // if so, convert to a right shift. if (ConstantUInt *C = dyn_cast(RHS)) @@ -432,6 +880,8 @@ Instruction *InstCombiner::visitRem(BinaryOperator &I) { if (ConstantInt *RHS = dyn_cast(I.getOperand(1))) { if (RHS->equalsInt(1)) // X % 1 == 0 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); + if (RHS->isAllOnesValue()) // X % -1 == 0 + return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); // Check to see if this is an unsigned remainder with an exact power of 2, // if so, convert to a bitwise and. @@ -483,6 +933,201 @@ static bool isMinValuePlusOne(const ConstantInt *C) { return CS->getValue() == Val+1; } +/// getSetCondCode - Encode a setcc opcode into a three bit mask. These bits +/// are carefully arranged to allow folding of expressions such as: +/// +/// (A < B) | (A > B) --> (A != B) +/// +/// Bit value '4' represents that the comparison is true if A > B, bit value '2' +/// represents that the comparison is true if A == B, and bit value '1' is true +/// if A < B. +/// +static unsigned getSetCondCode(const SetCondInst *SCI) { + switch (SCI->getOpcode()) { + // False -> 0 + case Instruction::SetGT: return 1; + case Instruction::SetEQ: return 2; + case Instruction::SetGE: return 3; + case Instruction::SetLT: return 4; + case Instruction::SetNE: return 5; + case Instruction::SetLE: return 6; + // True -> 7 + default: + assert(0 && "Invalid SetCC opcode!"); + return 0; + } +} + +/// getSetCCValue - This is the complement of getSetCondCode, which turns an +/// opcode and two operands into either a constant true or false, or a brand new +/// SetCC instruction. +static Value *getSetCCValue(unsigned Opcode, Value *LHS, Value *RHS) { + switch (Opcode) { + case 0: return ConstantBool::False; + case 1: return new SetCondInst(Instruction::SetGT, LHS, RHS); + case 2: return new SetCondInst(Instruction::SetEQ, LHS, RHS); + case 3: return new SetCondInst(Instruction::SetGE, LHS, RHS); + case 4: return new SetCondInst(Instruction::SetLT, LHS, RHS); + case 5: return new SetCondInst(Instruction::SetNE, LHS, RHS); + case 6: return new SetCondInst(Instruction::SetLE, LHS, RHS); + case 7: return ConstantBool::True; + default: assert(0 && "Illegal SetCCCode!"); return 0; + } +} + +// FoldSetCCLogical - Implements (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B) +struct FoldSetCCLogical { + InstCombiner &IC; + Value *LHS, *RHS; + FoldSetCCLogical(InstCombiner &ic, SetCondInst *SCI) + : IC(ic), LHS(SCI->getOperand(0)), RHS(SCI->getOperand(1)) {} + bool shouldApply(Value *V) const { + if (SetCondInst *SCI = dyn_cast(V)) + return (SCI->getOperand(0) == LHS && SCI->getOperand(1) == RHS || + SCI->getOperand(0) == RHS && SCI->getOperand(1) == LHS); + return false; + } + Instruction *apply(BinaryOperator &Log) const { + SetCondInst *SCI = cast(Log.getOperand(0)); + if (SCI->getOperand(0) != LHS) { + assert(SCI->getOperand(1) == LHS); + SCI->swapOperands(); // Swap the LHS and RHS of the SetCC + } + + unsigned LHSCode = getSetCondCode(SCI); + unsigned RHSCode = getSetCondCode(cast(Log.getOperand(1))); + unsigned Code; + switch (Log.getOpcode()) { + case Instruction::And: Code = LHSCode & RHSCode; break; + case Instruction::Or: Code = LHSCode | RHSCode; break; + case Instruction::Xor: Code = LHSCode ^ RHSCode; break; + default: assert(0 && "Illegal logical opcode!"); return 0; + } + + Value *RV = getSetCCValue(Code, LHS, RHS); + if (Instruction *I = dyn_cast(RV)) + return I; + // Otherwise, it's a constant boolean value... + return IC.ReplaceInstUsesWith(Log, RV); + } +}; + + +// OptAndOp - This handles expressions of the form ((val OP C1) & C2). Where +// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is +// guaranteed to be either a shift instruction or a binary operator. +Instruction *InstCombiner::OptAndOp(Instruction *Op, + ConstantIntegral *OpRHS, + ConstantIntegral *AndRHS, + BinaryOperator &TheAnd) { + Value *X = Op->getOperand(0); + Constant *Together = 0; + if (!isa(Op)) + Together = ConstantExpr::get(Instruction::And, AndRHS, OpRHS); + + switch (Op->getOpcode()) { + case Instruction::Xor: + if (Together->isNullValue()) { + // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0 + return BinaryOperator::create(Instruction::And, X, AndRHS); + } else if (Op->hasOneUse()) { + // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2) + std::string OpName = Op->getName(); Op->setName(""); + Instruction *And = BinaryOperator::create(Instruction::And, + X, AndRHS, OpName); + InsertNewInstBefore(And, TheAnd); + return BinaryOperator::create(Instruction::Xor, And, Together); + } + break; + case Instruction::Or: + // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0 + if (Together->isNullValue()) + return BinaryOperator::create(Instruction::And, X, AndRHS); + else { + if (Together == AndRHS) // (X | C) & C --> C + return ReplaceInstUsesWith(TheAnd, AndRHS); + + if (Op->hasOneUse() && Together != OpRHS) { + // (X | C1) & C2 --> (X | (C1&C2)) & C2 + std::string Op0Name = Op->getName(); Op->setName(""); + Instruction *Or = BinaryOperator::create(Instruction::Or, X, + Together, Op0Name); + InsertNewInstBefore(Or, TheAnd); + return BinaryOperator::create(Instruction::And, Or, AndRHS); + } + } + break; + case Instruction::Add: + if (Op->hasOneUse()) { + // Adding a one to a single bit bit-field should be turned into an XOR + // of the bit. First thing to check is to see if this AND is with a + // single bit constant. + unsigned long long AndRHSV = cast(AndRHS)->getRawValue(); + + // Clear bits that are not part of the constant. + AndRHSV &= (1ULL << AndRHS->getType()->getPrimitiveSize()*8)-1; + + // If there is only one bit set... + if ((AndRHSV & (AndRHSV-1)) == 0) { + // Ok, at this point, we know that we are masking the result of the + // ADD down to exactly one bit. If the constant we are adding has + // no bits set below this bit, then we can eliminate the ADD. + unsigned long long AddRHS = cast(OpRHS)->getRawValue(); + + // Check to see if any bits below the one bit set in AndRHSV are set. + if ((AddRHS & (AndRHSV-1)) == 0) { + // If not, the only thing that can effect the output of the AND is + // the bit specified by AndRHSV. If that bit is set, the effect of + // the XOR is to toggle the bit. If it is clear, then the ADD has + // no effect. + if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop + TheAnd.setOperand(0, X); + return &TheAnd; + } else { + std::string Name = Op->getName(); Op->setName(""); + // Pull the XOR out of the AND. + Instruction *NewAnd = + BinaryOperator::create(Instruction::And, X, AndRHS, Name); + InsertNewInstBefore(NewAnd, TheAnd); + return BinaryOperator::create(Instruction::Xor, NewAnd, AndRHS); + } + } + } + } + break; + + case Instruction::Shl: { + // We know that the AND will not produce any of the bits shifted in, so if + // the anded constant includes them, clear them now! + // + Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType()); + Constant *CI = ConstantExpr::get(Instruction::And, AndRHS, + ConstantExpr::get(Instruction::Shl, AllOne, OpRHS)); + if (CI != AndRHS) { + TheAnd.setOperand(1, CI); + return &TheAnd; + } + break; + } + case Instruction::Shr: + // We know that the AND will not produce any of the bits shifted in, so if + // the anded constant includes them, clear them now! This only applies to + // unsigned shifts, because a signed shr may bring in set bits! + // + if (AndRHS->getType()->isUnsigned()) { + Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType()); + Constant *CI = ConstantExpr::get(Instruction::And, AndRHS, + ConstantExpr::get(Instruction::Shr, AllOne, OpRHS)); + if (CI != AndRHS) { + TheAnd.setOperand(1, CI); + return &TheAnd; + } + } + break; + } + return 0; +} + Instruction *InstCombiner::visitAnd(BinaryOperator &I) { bool Changed = SimplifyCommutative(I); @@ -493,25 +1138,44 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { return ReplaceInstUsesWith(I, Op1); // and X, -1 == X - if (ConstantIntegral *RHS = dyn_cast(Op1)) + if (ConstantIntegral *RHS = dyn_cast(Op1)) { if (RHS->isAllOnesValue()) return ReplaceInstUsesWith(I, Op0); + // Optimize a variety of ((val OP C1) & C2) combinations... + if (isa(Op0) || isa(Op0)) { + Instruction *Op0I = cast(Op0); + Value *X = Op0I->getOperand(0); + if (ConstantInt *Op0CI = dyn_cast(Op0I->getOperand(1))) + if (Instruction *Res = OptAndOp(Op0I, Op0CI, RHS, I)) + return Res; + } + + // Try to fold constant and into select arguments. + if (SelectInst *SI = dyn_cast(Op0)) + if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) + return R; + } + Value *Op0NotVal = dyn_castNotVal(Op0); Value *Op1NotVal = dyn_castNotVal(Op1); // (~A & ~B) == (~(A | B)) - Demorgan's Law if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) { Instruction *Or = BinaryOperator::create(Instruction::Or, Op0NotVal, - Op1NotVal,I.getName()+".demorgan", - &I); - WorkList.push_back(Or); + Op1NotVal,I.getName()+".demorgan"); + InsertNewInstBefore(Or, I); return BinaryOperator::createNot(Or); } if (Op0NotVal == Op1 || Op1NotVal == Op0) // A & ~A == ~A & A == 0 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); + // (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B) + if (SetCondInst *RHS = dyn_cast(I.getOperand(1))) + if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS))) + return R; + return Changed ? &I : 0; } @@ -526,10 +1190,52 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { return ReplaceInstUsesWith(I, Op0); // or X, -1 == -1 - if (ConstantIntegral *RHS = dyn_cast(Op1)) + if (ConstantIntegral *RHS = dyn_cast(Op1)) { if (RHS->isAllOnesValue()) return ReplaceInstUsesWith(I, Op1); + if (Instruction *Op0I = dyn_cast(Op0)) { + // (X & C1) | C2 --> (X | C2) & (C1|C2) + if (Op0I->getOpcode() == Instruction::And && isOnlyUse(Op0)) + if (ConstantInt *Op0CI = dyn_cast(Op0I->getOperand(1))) { + std::string Op0Name = Op0I->getName(); Op0I->setName(""); + Instruction *Or = BinaryOperator::create(Instruction::Or, + Op0I->getOperand(0), RHS, + Op0Name); + InsertNewInstBefore(Or, I); + return BinaryOperator::create(Instruction::And, Or, + ConstantExpr::get(Instruction::Or, RHS, Op0CI)); + } + + // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2) + if (Op0I->getOpcode() == Instruction::Xor && isOnlyUse(Op0)) + if (ConstantInt *Op0CI = dyn_cast(Op0I->getOperand(1))) { + std::string Op0Name = Op0I->getName(); Op0I->setName(""); + Instruction *Or = BinaryOperator::create(Instruction::Or, + Op0I->getOperand(0), RHS, + Op0Name); + InsertNewInstBefore(Or, I); + return BinaryOperator::create(Instruction::Xor, Or, + ConstantExpr::get(Instruction::And, Op0CI, + NotConstant(RHS))); + } + } + + // Try to fold constant and into select arguments. + if (SelectInst *SI = dyn_cast(Op0)) + if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) + return R; + } + + // (A & C1)|(A & C2) == A & (C1|C2) + if (Instruction *LHS = dyn_cast(Op0)) + if (Instruction *RHS = dyn_cast(Op1)) + if (LHS->getOperand(0) == RHS->getOperand(0)) + if (Constant *C0 = dyn_castMaskingAnd(LHS)) + if (Constant *C1 = dyn_castMaskingAnd(RHS)) + return BinaryOperator::create(Instruction::And, LHS->getOperand(0), + ConstantExpr::get(Instruction::Or, C0, C1)); + Value *Op0NotVal = dyn_castNotVal(Op0); Value *Op1NotVal = dyn_castNotVal(Op1); @@ -550,36 +1256,90 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { return BinaryOperator::createNot(And); } + // (setcc1 A, B) | (setcc2 A, B) --> (setcc3 A, B) + if (SetCondInst *RHS = dyn_cast(I.getOperand(1))) + if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS))) + return R; + return Changed ? &I : 0; } +// XorSelf - Implements: X ^ X --> 0 +struct XorSelf { + Value *RHS; + XorSelf(Value *rhs) : RHS(rhs) {} + bool shouldApply(Value *LHS) const { return LHS == RHS; } + Instruction *apply(BinaryOperator &Xor) const { + return &Xor; + } +}; Instruction *InstCombiner::visitXor(BinaryOperator &I) { bool Changed = SimplifyCommutative(I); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); - // xor X, X = 0 - if (Op0 == Op1) + // xor X, X = 0, even if X is nested in a sequence of Xor's. + if (Instruction *Result = AssociativeOpt(I, XorSelf(Op1))) { + assert(Result == &I && "AssociativeOpt didn't work?"); return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); + } - if (ConstantIntegral *Op1C = dyn_cast(Op1)) { + if (ConstantIntegral *RHS = dyn_cast(Op1)) { // xor X, 0 == X - if (Op1C->isNullValue()) + if (RHS->isNullValue()) return ReplaceInstUsesWith(I, Op0); - // Is this a "NOT" instruction? - if (Op1C->isAllOnesValue()) { - // xor (xor X, -1), -1 = not (not X) = X - if (Value *X = dyn_castNotVal(Op0)) - return ReplaceInstUsesWith(I, X); - + if (BinaryOperator *Op0I = dyn_cast(Op0)) { // xor (setcc A, B), true = not (setcc A, B) = setncc A, B - if (SetCondInst *SCI = dyn_cast(Op0)) - if (SCI->use_size() == 1) + if (SetCondInst *SCI = dyn_cast(Op0I)) + if (RHS == ConstantBool::True && SCI->hasOneUse()) return new SetCondInst(SCI->getInverseCondition(), SCI->getOperand(0), SCI->getOperand(1)); + + // ~(c-X) == X-c-1 == X+(-c-1) + if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue()) + if (Constant *Op0I0C = dyn_cast(Op0I->getOperand(0))) { + Constant *NegOp0I0C = ConstantExpr::get(Instruction::Sub, + Constant::getNullValue(Op0I0C->getType()), Op0I0C); + Constant *ConstantRHS = ConstantExpr::get(Instruction::Sub, NegOp0I0C, + ConstantInt::get(I.getType(), 1)); + return BinaryOperator::create(Instruction::Add, Op0I->getOperand(1), + ConstantRHS); + } + + if (ConstantInt *Op0CI = dyn_cast(Op0I->getOperand(1))) + switch (Op0I->getOpcode()) { + case Instruction::Add: + // ~(X-c) --> (-c-1)-X + if (RHS->isAllOnesValue()) { + Constant *NegOp0CI = ConstantExpr::get(Instruction::Sub, + Constant::getNullValue(Op0CI->getType()), Op0CI); + return BinaryOperator::create(Instruction::Sub, + ConstantExpr::get(Instruction::Sub, NegOp0CI, + ConstantInt::get(I.getType(), 1)), + Op0I->getOperand(0)); + } + break; + case Instruction::And: + // (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0 + if (ConstantExpr::get(Instruction::And, RHS, Op0CI)->isNullValue()) + return BinaryOperator::create(Instruction::Or, Op0, RHS); + break; + case Instruction::Or: + // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 + if (ConstantExpr::get(Instruction::And, RHS, Op0CI) == RHS) + return BinaryOperator::create(Instruction::And, Op0, + NotConstant(RHS)); + break; + default: break; + } } + + // Try to fold constant and into select arguments. + if (SelectInst *SI = dyn_cast(Op0)) + if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) + return R; } if (Value *X = dyn_castNotVal(Op0)) // ~A ^ A == -1 @@ -593,7 +1353,7 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { ConstantIntegral::getAllOnesValue(I.getType())); if (Instruction *Op1I = dyn_cast(Op1)) - if (Op1I->getOpcode() == Instruction::Or) + if (Op1I->getOpcode() == Instruction::Or) { if (Op1I->getOperand(0) == Op0) { // B^(B|A) == (A|B)^B cast(Op1I)->swapOperands(); I.swapOperands(); @@ -601,10 +1361,16 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { } else if (Op1I->getOperand(1) == Op0) { // B^(A|B) == (A|B)^B I.swapOperands(); std::swap(Op0, Op1); - } + } + } else if (Op1I->getOpcode() == Instruction::Xor) { + if (Op0 == Op1I->getOperand(0)) // A^(A^B) == B + return ReplaceInstUsesWith(I, Op1I->getOperand(1)); + else if (Op0 == Op1I->getOperand(1)) // A^(B^A) == B + return ReplaceInstUsesWith(I, Op1I->getOperand(0)); + } if (Instruction *Op0I = dyn_cast(Op0)) - if (Op0I->getOpcode() == Instruction::Or && Op0I->use_size() == 1) { + if (Op0I->getOpcode() == Instruction::Or && Op0I->hasOneUse()) { if (Op0I->getOperand(0) == Op1) // (B|A)^B == (A|B)^B cast(Op0I)->swapOperands(); if (Op0I->getOperand(1) == Op1) { // (A|B)^B == A & ~B @@ -613,6 +1379,11 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { return BinaryOperator::create(Instruction::And, Op0I->getOperand(0), NotB); } + } else if (Op0I->getOpcode() == Instruction::Xor) { + if (Op1 == Op0I->getOperand(0)) // (A^B)^A == B + return ReplaceInstUsesWith(I, Op0I->getOperand(1)); + else if (Op1 == Op0I->getOperand(1)) // (B^A)^A == B + return ReplaceInstUsesWith(I, Op0I->getOperand(0)); } // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1^C2 == 0 @@ -621,6 +1392,11 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { if (ConstantExpr::get(Instruction::And, C1, C2)->isNullValue()) return BinaryOperator::create(Instruction::Or, Op0, Op1); + // (setcc1 A, B) ^ (setcc2 A, B) --> (setcc3 A, B) + if (SetCondInst *RHS = dyn_cast(I.getOperand(1))) + if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS))) + return R; + return Changed ? &I : 0; } @@ -656,15 +1432,17 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { if (Op0 == Op1) return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I))); - // setcc , 0 - Global value addresses are never null! - if (isa(Op0) && isa(Op1)) + // setcc , 0 - Global/Stack value addresses are never null! + if (isa(Op1) && + (isa(Op0) || isa(Op0))) return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I))); + // setcc's with boolean values can always be turned into bitwise operations if (Ty == Type::BoolTy) { // If this is <, >, or !=, we can change this into a simple xor instruction if (!isTrueWhenEqual(I)) - return BinaryOperator::create(Instruction::Xor, Op0, Op1, I.getName()); + return BinaryOperator::create(Instruction::Xor, Op0, Op1); // Otherwise we need to make a temporary intermediate instruction and insert // it into the instruction stream. This is what we are after: @@ -677,7 +1455,7 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1, I.getName()+"tmp"); InsertNewInstBefore(Xor, I); - return BinaryOperator::createNot(Xor, I.getName()); + return BinaryOperator::createNot(Xor); } // Handle the setXe cases... @@ -690,7 +1468,7 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { // Now we just have the SetLE case. Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp"); InsertNewInstBefore(Not, I); - return BinaryOperator::create(Instruction::Or, Not, Op1, I.getName()); + return BinaryOperator::create(Instruction::Or, Not, Op1); } // Check to see if we are doing one of many comparisons against constant @@ -702,30 +1480,116 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { I.getOpcode() == Instruction::SetNE) { bool isSetNE = I.getOpcode() == Instruction::SetNE; - if (CI->isNullValue()) { // Simplify [seteq|setne] X, 0 - CastInst *Val = new CastInst(Op0, Type::BoolTy, I.getName()+".not"); - if (isSetNE) return Val; - - // seteq X, 0 -> not (cast X to bool) - InsertNewInstBefore(Val, I); - return BinaryOperator::createNot(Val, I.getName()); - } - - // If the first operand is (and|or) with a constant, and the second + // If the first operand is (and|or|xor) with a constant, and the second // operand is a constant, simplify a bit. - if (BinaryOperator *BO = dyn_cast(Op0)) - if (ConstantInt *BOC = dyn_cast(BO->getOperand(1))) - if (BO->getOpcode() == Instruction::Or) { - // If bits are being or'd in that are not present in the constant we - // are comparing against, then the comparison could never succeed! - if (!(*BOC & *~*CI)->isNullValue()) + if (BinaryOperator *BO = dyn_cast(Op0)) { + switch (BO->getOpcode()) { + case Instruction::Add: + if (CI->isNullValue()) { + // Replace ((add A, B) != 0) with (A != -B) if A or B is + // efficiently invertible, or if the add has just this one use. + Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1); + if (Value *NegVal = dyn_castNegVal(BOp1)) + return new SetCondInst(I.getOpcode(), BOp0, NegVal); + else if (Value *NegVal = dyn_castNegVal(BOp0)) + return new SetCondInst(I.getOpcode(), NegVal, BOp1); + else if (BO->hasOneUse()) { + Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName()); + BO->setName(""); + InsertNewInstBefore(Neg, I); + return new SetCondInst(I.getOpcode(), BOp0, Neg); + } + } + break; + case Instruction::Xor: + // For the xor case, we can xor two constants together, eliminating + // the explicit xor. + if (Constant *BOC = dyn_cast(BO->getOperand(1))) + return BinaryOperator::create(I.getOpcode(), BO->getOperand(0), + ConstantExpr::get(Instruction::Xor, CI, BOC)); + + // FALLTHROUGH + case Instruction::Sub: + // Replace (([sub|xor] A, B) != 0) with (A != B) + if (CI->isNullValue()) + return new SetCondInst(I.getOpcode(), BO->getOperand(0), + BO->getOperand(1)); + break; + + case Instruction::Or: + // If bits are being or'd in that are not present in the constant we + // are comparing against, then the comparison could never succeed! + if (Constant *BOC = dyn_cast(BO->getOperand(1))) { + Constant *NotCI = NotConstant(CI); + if (!ConstantExpr::get(Instruction::And, BOC, NotCI)->isNullValue()) return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE)); - } else if (BO->getOpcode() == Instruction::And) { + } + break; + + case Instruction::And: + if (ConstantInt *BOC = dyn_cast(BO->getOperand(1))) { // If bits are being compared against that are and'd out, then the // comparison can never succeed! - if (!(*CI & *~*BOC)->isNullValue()) + if (!ConstantExpr::get(Instruction::And, CI, + NotConstant(BOC))->isNullValue()) return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE)); + + // Replace (and X, (1 << size(X)-1) != 0) with x < 0, converting X + // to be a signed value as appropriate. + if (isSignBit(BOC)) { + Value *X = BO->getOperand(0); + // If 'X' is not signed, insert a cast now... + if (!BOC->getType()->isSigned()) { + const Type *DestTy = getSignedIntegralType(BOC->getType()); + CastInst *NewCI = new CastInst(X,DestTy,X->getName()+".signed"); + InsertNewInstBefore(NewCI, I); + X = NewCI; + } + return new SetCondInst(isSetNE ? Instruction::SetLT : + Instruction::SetGE, X, + Constant::getNullValue(X->getType())); + } + } + default: break; + } + } + } else { // Not a SetEQ/SetNE + // If the LHS is a cast from an integral value of the same size, + if (CastInst *Cast = dyn_cast(Op0)) { + Value *CastOp = Cast->getOperand(0); + const Type *SrcTy = CastOp->getType(); + unsigned SrcTySize = SrcTy->getPrimitiveSize(); + if (SrcTy != Cast->getType() && SrcTy->isInteger() && + SrcTySize == Cast->getType()->getPrimitiveSize()) { + assert((SrcTy->isSigned() ^ Cast->getType()->isSigned()) && + "Source and destination signednesses should differ!"); + if (Cast->getType()->isSigned()) { + // If this is a signed comparison, check for comparisons in the + // vicinity of zero. + if (I.getOpcode() == Instruction::SetLT && CI->isNullValue()) + // X < 0 => x > 127 + return BinaryOperator::create(Instruction::SetGT, CastOp, + ConstantUInt::get(SrcTy, (1ULL << (SrcTySize*8-1))-1)); + else if (I.getOpcode() == Instruction::SetGT && + cast(CI)->getValue() == -1) + // X > -1 => x < 128 + return BinaryOperator::create(Instruction::SetLT, CastOp, + ConstantUInt::get(SrcTy, 1ULL << (SrcTySize*8-1))); + } else { + ConstantUInt *CUI = cast(CI); + if (I.getOpcode() == Instruction::SetLT && + CUI->getValue() == 1ULL << (SrcTySize*8-1)) + // X < 128 => X > -1 + return BinaryOperator::create(Instruction::SetGT, CastOp, + ConstantSInt::get(SrcTy, -1)); + else if (I.getOpcode() == Instruction::SetGT && + CUI->getValue() == (1ULL << (SrcTySize*8-1))-1) + // X > 127 => X < 0 + return BinaryOperator::create(Instruction::SetLT, CastOp, + Constant::getNullValue(SrcTy)); } + } + } } // Check to see if we are comparing against the minimum or maximum value... @@ -735,9 +1599,9 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { if (I.getOpcode() == Instruction::SetGE) // A >= MIN -> TRUE return ReplaceInstUsesWith(I, ConstantBool::True); if (I.getOpcode() == Instruction::SetLE) // A <= MIN -> A == MIN - return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName()); + return BinaryOperator::create(Instruction::SetEQ, Op0, Op1); if (I.getOpcode() == Instruction::SetGT) // A > MIN -> A != MIN - return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName()); + return BinaryOperator::create(Instruction::SetNE, Op0, Op1); } else if (CI->isMaxValue()) { if (I.getOpcode() == Instruction::SetGT) // A > MAX -> FALSE @@ -745,29 +1609,115 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { if (I.getOpcode() == Instruction::SetLE) // A <= MAX -> TRUE return ReplaceInstUsesWith(I, ConstantBool::True); if (I.getOpcode() == Instruction::SetGE) // A >= MAX -> A == MAX - return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName()); + return BinaryOperator::create(Instruction::SetEQ, Op0, Op1); if (I.getOpcode() == Instruction::SetLT) // A < MAX -> A != MAX - return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName()); + return BinaryOperator::create(Instruction::SetNE, Op0, Op1); // Comparing against a value really close to min or max? } else if (isMinValuePlusOne(CI)) { if (I.getOpcode() == Instruction::SetLT) // A < MIN+1 -> A == MIN - return BinaryOperator::create(Instruction::SetEQ, Op0, - SubOne(CI), I.getName()); + return BinaryOperator::create(Instruction::SetEQ, Op0, SubOne(CI)); if (I.getOpcode() == Instruction::SetGE) // A >= MIN-1 -> A != MIN - return BinaryOperator::create(Instruction::SetNE, Op0, - SubOne(CI), I.getName()); + return BinaryOperator::create(Instruction::SetNE, Op0, SubOne(CI)); } else if (isMaxValueMinusOne(CI)) { if (I.getOpcode() == Instruction::SetGT) // A > MAX-1 -> A == MAX - return BinaryOperator::create(Instruction::SetEQ, Op0, - AddOne(CI), I.getName()); + return BinaryOperator::create(Instruction::SetEQ, Op0, AddOne(CI)); if (I.getOpcode() == Instruction::SetLE) // A <= MAX-1 -> A != MAX - return BinaryOperator::create(Instruction::SetNE, Op0, - AddOne(CI), I.getName()); + return BinaryOperator::create(Instruction::SetNE, Op0, AddOne(CI)); } + + // If we still have a setle or setge instruction, turn it into the + // appropriate setlt or setgt instruction. Since the border cases have + // already been handled above, this requires little checking. + // + if (I.getOpcode() == Instruction::SetLE) + return BinaryOperator::create(Instruction::SetLT, Op0, AddOne(CI)); + if (I.getOpcode() == Instruction::SetGE) + return BinaryOperator::create(Instruction::SetGT, Op0, SubOne(CI)); } + // Test to see if the operands of the setcc are casted versions of other + // values. If the cast can be stripped off both arguments, we do so now. + if (CastInst *CI = dyn_cast(Op0)) { + Value *CastOp0 = CI->getOperand(0); + if (CastOp0->getType()->isLosslesslyConvertibleTo(CI->getType()) && + (isa(Op1) || isa(Op1)) && + (I.getOpcode() == Instruction::SetEQ || + I.getOpcode() == Instruction::SetNE)) { + // We keep moving the cast from the left operand over to the right + // operand, where it can often be eliminated completely. + Op0 = CastOp0; + + // If operand #1 is a cast instruction, see if we can eliminate it as + // well. + if (CastInst *CI2 = dyn_cast(Op1)) + if (CI2->getOperand(0)->getType()->isLosslesslyConvertibleTo( + Op0->getType())) + Op1 = CI2->getOperand(0); + + // If Op1 is a constant, we can fold the cast into the constant. + if (Op1->getType() != Op0->getType()) + if (Constant *Op1C = dyn_cast(Op1)) { + Op1 = ConstantExpr::getCast(Op1C, Op0->getType()); + } else { + // Otherwise, cast the RHS right before the setcc + Op1 = new CastInst(Op1, Op0->getType(), Op1->getName()); + InsertNewInstBefore(cast(Op1), I); + } + return BinaryOperator::create(I.getOpcode(), Op0, Op1); + } + + // Handle the special case of: setcc (cast bool to X), + // This comes up when you have code like + // int X = A < B; + // if (X) ... + // For generality, we handle any zero-extension of any operand comparison + // with a constant. + if (ConstantInt *ConstantRHS = dyn_cast(Op1)) { + const Type *SrcTy = CastOp0->getType(); + const Type *DestTy = Op0->getType(); + if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() && + (SrcTy->isUnsigned() || SrcTy == Type::BoolTy)) { + // Ok, we have an expansion of operand 0 into a new type. Get the + // constant value, masink off bits which are not set in the RHS. These + // could be set if the destination value is signed. + uint64_t ConstVal = ConstantRHS->getRawValue(); + ConstVal &= (1ULL << DestTy->getPrimitiveSize()*8)-1; + + // If the constant we are comparing it with has high bits set, which + // don't exist in the original value, the values could never be equal, + // because the source would be zero extended. + unsigned SrcBits = + SrcTy == Type::BoolTy ? 1 : SrcTy->getPrimitiveSize()*8; + bool HasSignBit = ConstVal & (1ULL << (DestTy->getPrimitiveSize()*8-1)); + if (ConstVal & ~((1ULL << SrcBits)-1)) { + switch (I.getOpcode()) { + default: assert(0 && "Unknown comparison type!"); + case Instruction::SetEQ: + return ReplaceInstUsesWith(I, ConstantBool::False); + case Instruction::SetNE: + return ReplaceInstUsesWith(I, ConstantBool::True); + case Instruction::SetLT: + case Instruction::SetLE: + if (DestTy->isSigned() && HasSignBit) + return ReplaceInstUsesWith(I, ConstantBool::False); + return ReplaceInstUsesWith(I, ConstantBool::True); + case Instruction::SetGT: + case Instruction::SetGE: + if (DestTy->isSigned() && HasSignBit) + return ReplaceInstUsesWith(I, ConstantBool::True); + return ReplaceInstUsesWith(I, ConstantBool::False); + } + } + + // Otherwise, we can replace the setcc with a setcc of the smaller + // operand value. + Op1 = ConstantExpr::getCast(cast(Op1), SrcTy); + return BinaryOperator::create(I.getOpcode(), CastOp0, Op1); + } + } + } return Changed ? &I : 0; } @@ -776,6 +1726,7 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { assert(I.getOperand(1)->getType() == Type::UByteTy); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); + bool isLeftShift = I.getOpcode() == Instruction::Shl; // shl X, 0 == X and shr X, 0 == X // shl 0, X == 0 and shr 0, X == 0 @@ -783,69 +1734,134 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { Op0 == Constant::getNullValue(Op0->getType())) return ReplaceInstUsesWith(I, Op0); - // If this is a shift of a shift, see if we can fold the two together... - if (ShiftInst *Op0SI = dyn_cast(Op0)) { - if (isa(Op1) && isa(Op0SI->getOperand(1))) { - ConstantUInt *ShiftAmt1C = cast(Op0SI->getOperand(1)); - unsigned ShiftAmt1 = ShiftAmt1C->getValue(); - unsigned ShiftAmt2 = cast(Op1)->getValue(); - - // Check for (A << c1) << c2 and (A >> c1) >> c2 - if (I.getOpcode() == Op0SI->getOpcode()) { - unsigned Amt = ShiftAmt1+ShiftAmt2; // Fold into one big shift... - return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0), - ConstantUInt::get(Type::UByteTy, Amt)); + // shr int -1, X = -1 (for any arithmetic shift rights of ~0) + if (!isLeftShift) + if (ConstantSInt *CSI = dyn_cast(Op0)) + if (CSI->isAllOnesValue()) + return ReplaceInstUsesWith(I, CSI); + + // Try to fold constant and into select arguments. + if (isa(Op0)) + if (SelectInst *SI = dyn_cast(Op1)) + if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) + return R; + + if (ConstantUInt *CUI = dyn_cast(Op1)) { + // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr + // of a signed value. + // + unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8; + if (CUI->getValue() >= TypeBits) { + if (!Op0->getType()->isSigned() || isLeftShift) + return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType())); + else { + I.setOperand(1, ConstantUInt::get(Type::UByteTy, TypeBits-1)); + return &I; } + } + + // ((X*C1) << C2) == (X * (C1 << C2)) + if (BinaryOperator *BO = dyn_cast(Op0)) + if (BO->getOpcode() == Instruction::Mul && isLeftShift) + if (Constant *BOOp = dyn_cast(BO->getOperand(1))) + return BinaryOperator::create(Instruction::Mul, BO->getOperand(0), + ConstantExpr::get(Instruction::Shl, BOOp, CUI)); + + // Try to fold constant and into select arguments. + if (SelectInst *SI = dyn_cast(Op0)) + if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) + return R; + + // If the operand is an bitwise operator with a constant RHS, and the + // shift is the only use, we can pull it out of the shift. + if (Op0->hasOneUse()) + if (BinaryOperator *Op0BO = dyn_cast(Op0)) + if (ConstantInt *Op0C = dyn_cast(Op0BO->getOperand(1))) { + bool isValid = true; // Valid only for And, Or, Xor + bool highBitSet = false; // Transform if high bit of constant set? + + switch (Op0BO->getOpcode()) { + default: isValid = false; break; // Do not perform transform! + case Instruction::Or: + case Instruction::Xor: + highBitSet = false; + break; + case Instruction::And: + highBitSet = true; + break; + } + + // If this is a signed shift right, and the high bit is modified + // by the logical operation, do not perform the transformation. + // The highBitSet boolean indicates the value of the high bit of + // the constant which would cause it to be modified for this + // operation. + // + if (isValid && !isLeftShift && !I.getType()->isUnsigned()) { + uint64_t Val = Op0C->getRawValue(); + isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet; + } + + if (isValid) { + Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, CUI); + + Instruction *NewShift = + new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI, + Op0BO->getName()); + Op0BO->setName(""); + InsertNewInstBefore(NewShift, I); + + return BinaryOperator::create(Op0BO->getOpcode(), NewShift, + NewRHS); + } + } - if (I.getType()->isUnsigned()) { // Check for (A << c1) >> c2 or visaversa - // Calculate bitmask for what gets shifted off the edge... - Constant *C = ConstantIntegral::getAllOnesValue(I.getType()); - if (I.getOpcode() == Instruction::Shr) - C = ConstantExpr::getShift(Instruction::Shr, C, ShiftAmt1C); - else - C = ConstantExpr::getShift(Instruction::Shl, C, ShiftAmt1C); + // If this is a shift of a shift, see if we can fold the two together... + if (ShiftInst *Op0SI = dyn_cast(Op0)) + if (ConstantUInt *ShiftAmt1C = + dyn_cast(Op0SI->getOperand(1))) { + unsigned ShiftAmt1 = ShiftAmt1C->getValue(); + unsigned ShiftAmt2 = CUI->getValue(); + + // Check for (A << c1) << c2 and (A >> c1) >> c2 + if (I.getOpcode() == Op0SI->getOpcode()) { + unsigned Amt = ShiftAmt1+ShiftAmt2; // Fold into one big shift... + if (Op0->getType()->getPrimitiveSize()*8 < Amt) + Amt = Op0->getType()->getPrimitiveSize()*8; + return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0), + ConstantUInt::get(Type::UByteTy, Amt)); + } + + // Check for (A << c1) >> c2 or visaversa. If we are dealing with + // signed types, we can only support the (A >> c1) << c2 configuration, + // because it can not turn an arbitrary bit of A into a sign bit. + if (I.getType()->isUnsigned() || isLeftShift) { + // Calculate bitmask for what gets shifted off the edge... + Constant *C = ConstantIntegral::getAllOnesValue(I.getType()); + if (isLeftShift) + C = ConstantExpr::get(Instruction::Shl, C, ShiftAmt1C); + else + C = ConstantExpr::get(Instruction::Shr, C, ShiftAmt1C); - Instruction *Mask = - BinaryOperator::create(Instruction::And, Op0SI->getOperand(0), - C, Op0SI->getOperand(0)->getName()+".mask",&I); - WorkList.push_back(Mask); + Instruction *Mask = + BinaryOperator::create(Instruction::And, Op0SI->getOperand(0), + C, Op0SI->getOperand(0)->getName()+".mask"); + InsertNewInstBefore(Mask, I); - // Figure out what flavor of shift we should use... - if (ShiftAmt1 == ShiftAmt2) - return ReplaceInstUsesWith(I, Mask); // (A << c) >> c === A & c2 - else if (ShiftAmt1 < ShiftAmt2) { - return new ShiftInst(I.getOpcode(), Mask, + // Figure out what flavor of shift we should use... + if (ShiftAmt1 == ShiftAmt2) + return ReplaceInstUsesWith(I, Mask); // (A << c) >> c === A & c2 + else if (ShiftAmt1 < ShiftAmt2) { + return new ShiftInst(I.getOpcode(), Mask, ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1)); - } else { - return new ShiftInst(Op0SI->getOpcode(), Mask, + } else { + return new ShiftInst(Op0SI->getOpcode(), Mask, ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2)); + } } } - } - } - - // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr of - // a signed value. - // - if (ConstantUInt *CUI = dyn_cast(Op1)) { - unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8; - if (CUI->getValue() >= TypeBits && - (!Op0->getType()->isSigned() || I.getOpcode() == Instruction::Shl)) - return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType())); - - // Check to see if we are shifting left by 1. If so, turn it into an add - // instruction. - if (I.getOpcode() == Instruction::Shl && CUI->equalsInt(1)) - // Convert 'shl int %X, 1' to 'add int %X, %X' - return BinaryOperator::create(Instruction::Add, Op0, Op0, I.getName()); - } - // shr int -1, X = -1 (for any arithmetic shift rights of ~0) - if (ConstantSInt *CSI = dyn_cast(Op0)) - if (I.getOpcode() == Instruction::Shr && CSI->isAllOnesValue()) - return ReplaceInstUsesWith(I, CSI); - return 0; } @@ -853,12 +1869,8 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { // isEliminableCastOfCast - Return true if it is valid to eliminate the CI // instruction. // -static inline bool isEliminableCastOfCast(const CastInst &CI, - const CastInst *CSrc) { - assert(CI.getOperand(0) == CSrc); - const Type *SrcTy = CSrc->getOperand(0)->getType(); - const Type *MidTy = CSrc->getType(); - const Type *DstTy = CI.getType(); +static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy, + const Type *DstTy) { // It is legal to eliminate the instruction if casting A->B->A if the sizes // are identical and the bits don't get reinterpreted (for example @@ -923,6 +1935,28 @@ static inline bool isEliminableCastOfCast(const CastInst &CI, return false; } +static bool ValueRequiresCast(const Value *V, const Type *Ty) { + if (V->getType() == Ty || isa(V)) return false; + if (const CastInst *CI = dyn_cast(V)) + if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty)) + 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(Value *V, const Type *DestTy, + Instruction *InsertBefore) { + if (V->getType() == DestTy) return V; + if (Constant *C = dyn_cast(V)) + return ConstantExpr::getCast(C, DestTy); + + CastInst *CI = new CastInst(V, DestTy, V->getName()); + InsertNewInstBefore(CI, *InsertBefore); + return CI; +} // CastInst simplification // @@ -938,7 +1972,8 @@ Instruction *InstCombiner::visitCastInst(CastInst &CI) { // one! // if (CastInst *CSrc = dyn_cast(Src)) { - if (isEliminableCastOfCast(CI, CSrc)) { + if (isEliminableCastOfCast(CSrc->getOperand(0)->getType(), + CSrc->getType(), CI.getType())) { // This instruction now refers directly to the cast's src operand. This // has a good chance of making CSrc dead. CI.setOperand(0, CSrc->getOperand(0)); @@ -978,93 +2013,334 @@ Instruction *InstCombiner::visitCastInst(CastInst &CI) { } } - // If this is a cast to bool (which is effectively a "!=0" test), then we can - // perform a few optimizations... + // If we are casting a malloc or alloca to a pointer to a type of the same + // size, rewrite the allocation instruction to allocate the "right" type. // - if (CI.getType() == Type::BoolTy) { - if (BinaryOperator *BO = dyn_cast(Src)) { - Value *Op0 = BO->getOperand(0), *Op1 = BO->getOperand(1); + if (AllocationInst *AI = dyn_cast(Src)) + if (AI->hasOneUse() && !AI->isArrayAllocation()) + if (const PointerType *PTy = dyn_cast(CI.getType())) { + // Get the type really allocated and the type casted to... + const Type *AllocElTy = AI->getAllocatedType(); + unsigned AllocElTySize = TD->getTypeSize(AllocElTy); + const Type *CastElTy = PTy->getElementType(); + unsigned CastElTySize = TD->getTypeSize(CastElTy); + + // If the allocation is for an even multiple of the cast type size + if (CastElTySize && (AllocElTySize % CastElTySize == 0)) { + Value *Amt = ConstantUInt::get(Type::UIntTy, + AllocElTySize/CastElTySize); + std::string Name = AI->getName(); AI->setName(""); + AllocationInst *New; + if (isa(AI)) + New = new MallocInst(CastElTy, Amt, Name); + else + New = new AllocaInst(CastElTy, Amt, Name); + InsertNewInstBefore(New, CI); + return ReplaceInstUsesWith(CI, New); + } + } - switch (BO->getOpcode()) { - case Instruction::Sub: - case Instruction::Xor: - // Replace (cast ([sub|xor] A, B) to bool) with (setne A, B) - return new SetCondInst(Instruction::SetNE, Op0, Op1); + // If the source value is an instruction with only this use, we can attempt to + // propagate the cast into the instruction. Also, only handle integral types + // for now. + if (Instruction *SrcI = dyn_cast(Src)) + if (SrcI->hasOneUse() && Src->getType()->isIntegral() && + CI.getType()->isInteger()) { // Don't mess with casts to bool here + const Type *DestTy = CI.getType(); + unsigned SrcBitSize = getTypeSizeInBits(Src->getType()); + unsigned DestBitSize = getTypeSizeInBits(DestTy); - // Replace (cast (add A, B) to bool) with (setne A, -B) if B is - // efficiently invertible, or if the add has just this one use. - case Instruction::Add: - if (Value *NegVal = dyn_castNegVal(Op1)) - return new SetCondInst(Instruction::SetNE, Op0, NegVal); - else if (Value *NegVal = dyn_castNegVal(Op0)) - return new SetCondInst(Instruction::SetNE, NegVal, Op1); - else if (BO->use_size() == 1) { - Instruction *Neg = BinaryOperator::createNeg(Op1, BO->getName()); - BO->setName(""); - InsertNewInstBefore(Neg, CI); - return new SetCondInst(Instruction::SetNE, Op0, Neg); - } - break; + Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0; + Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0; + switch (SrcI->getOpcode()) { + case Instruction::Add: + case Instruction::Mul: case Instruction::And: - // Replace (cast (and X, (1 << size(X)-1)) to bool) with x < 0, - // converting X to be a signed value as appropriate. Don't worry about - // bool values, as they will be optimized other ways if they occur in - // this configuration. - if (ConstantInt *CInt = dyn_cast(Op1)) - if (isSignBit(CInt)) { - // If 'X' is not signed, insert a cast now... - if (!CInt->getType()->isSigned()) { - const Type *DestTy; - switch (CInt->getType()->getPrimitiveID()) { - case Type::UByteTyID: DestTy = Type::SByteTy; break; - case Type::UShortTyID: DestTy = Type::ShortTy; break; - case Type::UIntTyID: DestTy = Type::IntTy; break; - case Type::ULongTyID: DestTy = Type::LongTy; break; - default: assert(0 && "Invalid unsigned integer type!"); abort(); - } - CastInst *NewCI = new CastInst(Op0, DestTy, - Op0->getName()+".signed"); - InsertNewInstBefore(NewCI, CI); - Op0 = NewCI; - } - return new SetCondInst(Instruction::SetLT, Op0, - Constant::getNullValue(Op0->getType())); + case Instruction::Or: + case Instruction::Xor: + // If we are discarding information, or just changing the sign, rewrite. + if (DestBitSize <= SrcBitSize && DestBitSize != 1) { + // Don't insert two casts if they cannot be eliminated. We allow two + // casts to be inserted if the sizes are the same. This could only be + // converting signedness, which is a noop. + if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy) || + !ValueRequiresCast(Op0, DestTy)) { + Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI); + Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI); + return BinaryOperator::create(cast(SrcI) + ->getOpcode(), Op0c, Op1c); } + } + break; + case Instruction::Shl: + // Allow changing the sign of the source operand. Do not allow changing + // the size of the shift, UNLESS the shift amount is a constant. We + // mush not change variable sized shifts to a smaller size, because it + // is undefined to shift more bits out than exist in the value. + if (DestBitSize == SrcBitSize || + (DestBitSize < SrcBitSize && isa(Op1))) { + Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI); + return new ShiftInst(Instruction::Shl, Op0c, Op1); + } break; - default: break; } } + + return 0; +} + +/// GetSelectFoldableOperands - We want to turn code that looks like this: +/// %C = or %A, %B +/// %D = select %cond, %C, %A +/// into: +/// %C = select %cond, %B, 0 +/// %D = or %A, %C +/// +/// Assuming that the specified instruction is an operand to the select, return +/// a bitmask indicating which operands of this instruction are foldable if they +/// equal the other incoming value of the select. +/// +static unsigned GetSelectFoldableOperands(Instruction *I) { + switch (I->getOpcode()) { + case Instruction::Add: + case Instruction::Mul: + case Instruction::And: + case Instruction::Or: + case Instruction::Xor: + return 3; // Can fold through either operand. + case Instruction::Sub: // Can only fold on the amount subtracted. + case Instruction::Shl: // Can only fold on the shift amount. + case Instruction::Shr: + return 1; + default: + return 0; // Cannot fold } +} +/// GetSelectFoldableConstant - For the same transformation as the previous +/// function, return the identity constant that goes into the select. +static Constant *GetSelectFoldableConstant(Instruction *I) { + switch (I->getOpcode()) { + default: assert(0 && "This cannot happen!"); abort(); + case Instruction::Add: + case Instruction::Sub: + case Instruction::Or: + case Instruction::Xor: + return Constant::getNullValue(I->getType()); + case Instruction::Shl: + case Instruction::Shr: + return Constant::getNullValue(Type::UByteTy); + case Instruction::And: + return ConstantInt::getAllOnesValue(I->getType()); + case Instruction::Mul: + return ConstantInt::get(I->getType(), 1); + } +} + +Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { + Value *CondVal = SI.getCondition(); + Value *TrueVal = SI.getTrueValue(); + Value *FalseVal = SI.getFalseValue(); + + // select true, X, Y -> X + // select false, X, Y -> Y + if (ConstantBool *C = dyn_cast(CondVal)) + if (C == ConstantBool::True) + return ReplaceInstUsesWith(SI, TrueVal); + else { + assert(C == ConstantBool::False); + return ReplaceInstUsesWith(SI, FalseVal); + } + + // select C, X, X -> X + if (TrueVal == FalseVal) + return ReplaceInstUsesWith(SI, TrueVal); + + if (SI.getType() == Type::BoolTy) + if (ConstantBool *C = dyn_cast(TrueVal)) { + if (C == ConstantBool::True) { + // Change: A = select B, true, C --> A = or B, C + return BinaryOperator::create(Instruction::Or, CondVal, FalseVal); + } else { + // Change: A = select B, false, C --> A = and !B, C + Value *NotCond = + InsertNewInstBefore(BinaryOperator::createNot(CondVal, + "not."+CondVal->getName()), SI); + return BinaryOperator::create(Instruction::And, NotCond, FalseVal); + } + } else if (ConstantBool *C = dyn_cast(FalseVal)) { + if (C == ConstantBool::False) { + // Change: A = select B, C, false --> A = and B, C + return BinaryOperator::create(Instruction::And, CondVal, TrueVal); + } else { + // Change: A = select B, C, true --> A = or !B, C + Value *NotCond = + InsertNewInstBefore(BinaryOperator::createNot(CondVal, + "not."+CondVal->getName()), SI); + return BinaryOperator::create(Instruction::Or, NotCond, TrueVal); + } + } + + // Selecting between two integer constants? + if (ConstantInt *TrueValC = dyn_cast(TrueVal)) + if (ConstantInt *FalseValC = dyn_cast(FalseVal)) { + // select C, 1, 0 -> cast C to int + if (FalseValC->isNullValue() && TrueValC->getRawValue() == 1) { + return new CastInst(CondVal, SI.getType()); + } else if (TrueValC->isNullValue() && FalseValC->getRawValue() == 1) { + // select C, 0, 1 -> cast !C to int + Value *NotCond = + InsertNewInstBefore(BinaryOperator::createNot(CondVal, + "not."+CondVal->getName()), SI); + return new CastInst(NotCond, SI.getType()); + } + } + + // See if we are selecting two values based on a comparison of the two values. + if (SetCondInst *SCI = dyn_cast(CondVal)) { + if (SCI->getOperand(0) == TrueVal && SCI->getOperand(1) == FalseVal) { + // Transform (X == Y) ? X : Y -> Y + if (SCI->getOpcode() == Instruction::SetEQ) + return ReplaceInstUsesWith(SI, FalseVal); + // Transform (X != Y) ? X : Y -> X + if (SCI->getOpcode() == Instruction::SetNE) + return ReplaceInstUsesWith(SI, TrueVal); + // NOTE: if we wanted to, this is where to detect MIN/MAX/ABS/etc. + + } else if (SCI->getOperand(0) == FalseVal && SCI->getOperand(1) == TrueVal){ + // Transform (X == Y) ? Y : X -> X + if (SCI->getOpcode() == Instruction::SetEQ) + return ReplaceInstUsesWith(SI, FalseVal); + // Transform (X != Y) ? Y : X -> Y + if (SCI->getOpcode() == Instruction::SetNE) + return ReplaceInstUsesWith(SI, TrueVal); + // NOTE: if we wanted to, this is where to detect MIN/MAX/ABS/etc. + } + } + + // See if we can fold the select into one of our operands. + if (SI.getType()->isInteger()) { + // See the comment above GetSelectFoldableOperands for a description of the + // transformation we are doing here. + if (Instruction *TVI = dyn_cast(TrueVal)) + if (TVI->hasOneUse() && TVI->getNumOperands() == 2 && + !isa(FalseVal)) + if (unsigned SFO = GetSelectFoldableOperands(TVI)) { + unsigned OpToFold = 0; + if ((SFO & 1) && FalseVal == TVI->getOperand(0)) { + OpToFold = 1; + } else if ((SFO & 2) && FalseVal == TVI->getOperand(1)) { + OpToFold = 2; + } + + if (OpToFold) { + Constant *C = GetSelectFoldableConstant(TVI); + std::string Name = TVI->getName(); TVI->setName(""); + Instruction *NewSel = + new SelectInst(SI.getCondition(), TVI->getOperand(2-OpToFold), C, + Name); + InsertNewInstBefore(NewSel, SI); + if (BinaryOperator *BO = dyn_cast(TVI)) + return BinaryOperator::create(BO->getOpcode(), FalseVal, NewSel); + else if (ShiftInst *SI = dyn_cast(TVI)) + return new ShiftInst(SI->getOpcode(), FalseVal, NewSel); + else { + assert(0 && "Unknown instruction!!"); + } + } + } + + if (Instruction *FVI = dyn_cast(FalseVal)) + if (FVI->hasOneUse() && FVI->getNumOperands() == 2 && + !isa(TrueVal)) + if (unsigned SFO = GetSelectFoldableOperands(FVI)) { + unsigned OpToFold = 0; + if ((SFO & 1) && TrueVal == FVI->getOperand(0)) { + OpToFold = 1; + } else if ((SFO & 2) && TrueVal == FVI->getOperand(1)) { + OpToFold = 2; + } + + if (OpToFold) { + Constant *C = GetSelectFoldableConstant(FVI); + std::string Name = FVI->getName(); FVI->setName(""); + Instruction *NewSel = + new SelectInst(SI.getCondition(), C, FVI->getOperand(2-OpToFold), + Name); + InsertNewInstBefore(NewSel, SI); + if (BinaryOperator *BO = dyn_cast(FVI)) + return BinaryOperator::create(BO->getOpcode(), TrueVal, NewSel); + else if (ShiftInst *SI = dyn_cast(FVI)) + return new ShiftInst(SI->getOpcode(), TrueVal, NewSel); + else { + assert(0 && "Unknown instruction!!"); + } + } + } + } return 0; } + // CallInst simplification // Instruction *InstCombiner::visitCallInst(CallInst &CI) { - if (transformConstExprCastCall(&CI)) return 0; - return 0; + // Intrinsics cannot occur in an invoke, so handle them here instead of in + // visitCallSite. + if (Function *F = CI.getCalledFunction()) + switch (F->getIntrinsicID()) { + case Intrinsic::memmove: + case Intrinsic::memcpy: + case Intrinsic::memset: + // memmove/cpy/set of zero bytes is a noop. + if (Constant *NumBytes = dyn_cast(CI.getOperand(3))) { + if (NumBytes->isNullValue()) + return EraseInstFromFunction(CI); + } + break; + default: + break; + } + + return visitCallSite(&CI); } // InvokeInst simplification // Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) { - if (transformConstExprCastCall(&II)) return 0; - return 0; + return visitCallSite(&II); } -// getPromotedType - Return the specified type promoted as it would be to pass -// though a va_arg area... -static const Type *getPromotedType(const Type *Ty) { - switch (Ty->getPrimitiveID()) { - case Type::SByteTyID: - case Type::ShortTyID: return Type::IntTy; - case Type::UByteTyID: - case Type::UShortTyID: return Type::UIntTy; - case Type::FloatTyID: return Type::DoubleTy; - default: return Ty; +// visitCallSite - Improvements for call and invoke instructions. +// +Instruction *InstCombiner::visitCallSite(CallSite CS) { + bool Changed = false; + + // If the callee is a constexpr cast of a function, attempt to move the cast + // to the arguments of the call/invoke. + if (transformConstExprCastCall(CS)) return 0; + + Value *Callee = CS.getCalledValue(); + const PointerType *PTy = cast(Callee->getType()); + const FunctionType *FTy = cast(PTy->getElementType()); + if (FTy->isVarArg()) { + // See if we can optimize any arguments passed through the varargs area of + // the call. + for (CallSite::arg_iterator I = CS.arg_begin()+FTy->getNumParams(), + E = CS.arg_end(); I != E; ++I) + if (CastInst *CI = dyn_cast(*I)) { + // If this cast does not effect the value passed through the varargs + // area, we can eliminate the use of the cast. + Value *Op = CI->getOperand(0); + if (CI->getType()->isLosslesslyConvertibleTo(Op->getType())) { + *I = Op; + Changed = true; + } + } } + + return Changed ? CS.getInstruction() : 0; } // transformConstExprCastCall - If the callee is a constexpr cast of a function, @@ -1088,9 +2364,26 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { const FunctionType *FT = Callee->getFunctionType(); const Type *OldRetTy = Caller->getType(); - if (Callee->isExternal() && - !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType())) - return false; // Cannot transform this return value... + // Check to see if we are changing the return type... + if (OldRetTy != FT->getReturnType()) { + if (Callee->isExternal() && + !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType()) && + !Caller->use_empty()) + return false; // Cannot transform this return value... + + // If the callsite is an invoke instruction, and the return value is used by + // a PHI node in a successor, we cannot change the return type of the call + // because there is no place to put the cast instruction (without breaking + // the critical edge). Bail out in this case. + if (!Caller->use_empty()) + if (InvokeInst *II = dyn_cast(Caller)) + for (Value::use_iterator UI = II->use_begin(), E = II->use_end(); + UI != E; ++UI) + if (PHINode *PN = dyn_cast(*UI)) + if (PN->getParent() == II->getNormalDest() || + PN->getParent() == II->getUnwindDest()) + return false; + } unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin()); unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs); @@ -1117,9 +2410,8 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { if ((*AI)->getType() == ParamTy) { Args.push_back(*AI); } else { - Instruction *Cast = new CastInst(*AI, ParamTy, "tmp"); - InsertNewInstBefore(Cast, *Caller); - Args.push_back(Cast); + Args.push_back(InsertNewInstBefore(new CastInst(*AI, ParamTy, "tmp"), + *Caller)); } } @@ -1153,7 +2445,7 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { Instruction *NC; if (InvokeInst *II = dyn_cast(Caller)) { - NC = new InvokeInst(Callee, II->getNormalDest(), II->getExceptionalDest(), + NC = new InvokeInst(Callee, II->getNormalDest(), II->getUnwindDest(), Args, Caller->getName(), Caller); } else { NC = new CallInst(Callee, Args, Caller->getName(), Caller); @@ -1164,8 +2456,18 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { if (Caller->getType() != NV->getType() && !Caller->use_empty()) { if (NV->getType() != Type::VoidTy) { NV = NC = new CastInst(NC, Caller->getType(), "tmp"); - InsertNewInstBefore(NC, *Caller); - AddUsesToWorkList(*Caller); + + // If this is an invoke instruction, we should insert it after the first + // non-phi, instruction in the normal successor block. + if (InvokeInst *II = dyn_cast(Caller)) { + BasicBlock::iterator I = II->getNormalDest()->begin(); + while (isa(I)) ++I; + InsertNewInstBefore(NC, *I); + } else { + // Otherwise, it's a call, just insert cast right after the call instr + InsertNewInstBefore(NC, *Caller); + } + AddUsersToWorkList(*Caller); } else { NV = Constant::getNullValue(Caller->getType()); } @@ -1183,86 +2485,224 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { // PHINode simplification // Instruction *InstCombiner::visitPHINode(PHINode &PN) { - // If the PHI node only has one incoming value, eliminate the PHI node... - if (PN.getNumIncomingValues() == 1) - return ReplaceInstUsesWith(PN, PN.getIncomingValue(0)); - - // Otherwise if all of the incoming values are the same for the PHI, replace - // the PHI node with the incoming value. - // - Value *InVal = 0; - for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) - if (PN.getIncomingValue(i) != &PN) // Not the PHI node itself... - if (InVal && PN.getIncomingValue(i) != InVal) - return 0; // Not the same, bail out. - else - InVal = PN.getIncomingValue(i); - - // The only case that could cause InVal to be null is if we have a PHI node - // that only has entries for itself. In this case, there is no entry into the - // loop, so kill the PHI. - // - if (InVal == 0) InVal = Constant::getNullValue(PN.getType()); + if (Value *V = hasConstantValue(&PN)) + return ReplaceInstUsesWith(PN, V); + + // If the only user of this instruction is a cast instruction, and all of the + // incoming values are constants, change this PHI to merge together the casted + // constants. + if (PN.hasOneUse()) + if (CastInst *CI = dyn_cast(PN.use_back())) + if (CI->getType() != PN.getType()) { // noop casts will be folded + bool AllConstant = true; + for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) + if (!isa(PN.getIncomingValue(i))) { + AllConstant = false; + break; + } + if (AllConstant) { + // Make a new PHI with all casted values. + PHINode *New = new PHINode(CI->getType(), PN.getName(), &PN); + for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { + Constant *OldArg = cast(PN.getIncomingValue(i)); + New->addIncoming(ConstantExpr::getCast(OldArg, New->getType()), + PN.getIncomingBlock(i)); + } + + // Update the cast instruction. + CI->setOperand(0, New); + WorkList.push_back(CI); // revisit the cast instruction to fold. + WorkList.push_back(New); // Make sure to revisit the new Phi + return &PN; // PN is now dead! + } + } + return 0; +} - // All of the incoming values are the same, replace the PHI node now. - return ReplaceInstUsesWith(PN, InVal); +static Value *InsertSignExtendToPtrTy(Value *V, const Type *DTy, + Instruction *InsertPoint, + InstCombiner *IC) { + unsigned PS = IC->getTargetData().getPointerSize(); + const Type *VTy = V->getType(); + Instruction *Cast; + if (!VTy->isSigned() && VTy->getPrimitiveSize() < PS) + // We must insert a cast to ensure we sign-extend. + V = IC->InsertNewInstBefore(new CastInst(V, VTy->getSignedVersion(), + V->getName()), *InsertPoint); + return IC->InsertNewInstBefore(new CastInst(V, DTy, V->getName()), + *InsertPoint); } Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { // Is it 'getelementptr %P, long 0' or 'getelementptr %P' // If so, eliminate the noop. - if ((GEP.getNumOperands() == 2 && - GEP.getOperand(1) == Constant::getNullValue(Type::LongTy)) || - GEP.getNumOperands() == 1) + if (GEP.getNumOperands() == 1) return ReplaceInstUsesWith(GEP, GEP.getOperand(0)); + bool HasZeroPointerIndex = false; + if (Constant *C = dyn_cast(GEP.getOperand(1))) + HasZeroPointerIndex = C->isNullValue(); + + if (GEP.getNumOperands() == 2 && HasZeroPointerIndex) + return ReplaceInstUsesWith(GEP, GEP.getOperand(0)); + + // Eliminate unneeded casts for indices. + bool MadeChange = false; + gep_type_iterator GTI = gep_type_begin(GEP); + for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i, ++GTI) + if (isa(*GTI)) { + if (CastInst *CI = dyn_cast(GEP.getOperand(i))) { + Value *Src = CI->getOperand(0); + const Type *SrcTy = Src->getType(); + const Type *DestTy = CI->getType(); + if (Src->getType()->isInteger()) { + if (SrcTy->getPrimitiveSize() == DestTy->getPrimitiveSize()) { + // We can always eliminate a cast from ulong or long to the other. + // We can always eliminate a cast from uint to int or the other on + // 32-bit pointer platforms. + if (DestTy->getPrimitiveSize() >= TD->getPointerSize()) { + MadeChange = true; + GEP.setOperand(i, Src); + } + } else if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() && + SrcTy->getPrimitiveSize() == 4) { + // We can always eliminate a cast from int to [u]long. We can + // eliminate a cast from uint to [u]long iff the target is a 32-bit + // pointer target. + if (SrcTy->isSigned() || + SrcTy->getPrimitiveSize() >= TD->getPointerSize()) { + MadeChange = true; + GEP.setOperand(i, Src); + } + } + } + } + // If we are using a wider index than needed for this platform, shrink it + // to what we need. If the incoming value needs a cast instruction, + // insert it. This explicit cast can make subsequent optimizations more + // obvious. + Value *Op = GEP.getOperand(i); + if (Op->getType()->getPrimitiveSize() > TD->getPointerSize()) + if (Constant *C = dyn_cast(Op)) { + GEP.setOperand(i, ConstantExpr::getCast(C, TD->getIntPtrType())); + MadeChange = true; + } else { + Op = InsertNewInstBefore(new CastInst(Op, TD->getIntPtrType(), + Op->getName()), GEP); + GEP.setOperand(i, Op); + MadeChange = true; + } + } + if (MadeChange) return &GEP; + // Combine Indices - If the source pointer to this getelementptr instruction // is a getelementptr instruction, combine the indices of the two // getelementptr instructions into a single instruction. // + std::vector SrcGEPOperands; if (GetElementPtrInst *Src = dyn_cast(GEP.getOperand(0))) { + SrcGEPOperands.assign(Src->op_begin(), Src->op_end()); + } else if (ConstantExpr *CE = dyn_cast(GEP.getOperand(0))) { + if (CE->getOpcode() == Instruction::GetElementPtr) + SrcGEPOperands.assign(CE->op_begin(), CE->op_end()); + } + + if (!SrcGEPOperands.empty()) { std::vector Indices; // Can we combine the two pointer arithmetics offsets? - if (Src->getNumOperands() == 2 && isa(Src->getOperand(1)) && + if (SrcGEPOperands.size() == 2 && isa(SrcGEPOperands[1]) && isa(GEP.getOperand(1))) { + Constant *SGC = cast(SrcGEPOperands[1]); + Constant *GC = cast(GEP.getOperand(1)); + if (SGC->getType() != GC->getType()) { + SGC = ConstantExpr::getSignExtend(SGC, Type::LongTy); + GC = ConstantExpr::getSignExtend(GC, Type::LongTy); + } + // Replace: gep (gep %P, long C1), long C2, ... // With: gep %P, long (C1+C2), ... - Value *Sum = ConstantExpr::get(Instruction::Add, - cast(Src->getOperand(1)), - cast(GEP.getOperand(1))); - assert(Sum && "Constant folding of longs failed!?"); - GEP.setOperand(0, Src->getOperand(0)); - GEP.setOperand(1, Sum); - AddUsesToWorkList(*Src); // Reduce use count of Src + GEP.setOperand(0, SrcGEPOperands[0]); + GEP.setOperand(1, ConstantExpr::getAdd(SGC, GC)); + if (Instruction *I = dyn_cast(GEP.getOperand(0))) + AddUsersToWorkList(*I); // Reduce use count of Src return &GEP; - } else if (Src->getNumOperands() == 2) { + } else if (SrcGEPOperands.size() == 2) { // Replace: gep (gep %P, long B), long A, ... // With: T = long A+B; gep %P, T, ... // - Value *Sum = BinaryOperator::create(Instruction::Add, Src->getOperand(1), - GEP.getOperand(1), - Src->getName()+".sum", &GEP); - GEP.setOperand(0, Src->getOperand(0)); + // Note that if our source is a gep chain itself that we wait for that + // chain to be resolved before we perform this transformation. This + // avoids us creating a TON of code in some cases. + // + if (isa(SrcGEPOperands[0]) && + cast(SrcGEPOperands[0])->getNumOperands() == 2) + return 0; // Wait until our source is folded to completion. + + Value *Sum, *SO1 = SrcGEPOperands[1], *GO1 = GEP.getOperand(1); + if (SO1 == Constant::getNullValue(SO1->getType())) { + Sum = GO1; + } else if (GO1 == Constant::getNullValue(GO1->getType())) { + Sum = SO1; + } else { + // If they aren't the same type, convert both to an integer of the + // target's pointer size. + if (SO1->getType() != GO1->getType()) { + if (Constant *SO1C = dyn_cast(SO1)) { + SO1 = ConstantExpr::getCast(SO1C, GO1->getType()); + } else if (Constant *GO1C = dyn_cast(GO1)) { + GO1 = ConstantExpr::getCast(GO1C, SO1->getType()); + } else { + unsigned PS = TD->getPointerSize(); + Instruction *Cast; + if (SO1->getType()->getPrimitiveSize() == PS) { + // Convert GO1 to SO1's type. + GO1 = InsertSignExtendToPtrTy(GO1, SO1->getType(), &GEP, this); + + } else if (GO1->getType()->getPrimitiveSize() == PS) { + // Convert SO1 to GO1's type. + SO1 = InsertSignExtendToPtrTy(SO1, GO1->getType(), &GEP, this); + } else { + const Type *PT = TD->getIntPtrType(); + SO1 = InsertSignExtendToPtrTy(SO1, PT, &GEP, this); + GO1 = InsertSignExtendToPtrTy(GO1, PT, &GEP, this); + } + } + } + Sum = BinaryOperator::create(Instruction::Add, SO1, GO1, + GEP.getOperand(0)->getName()+".sum", &GEP); + WorkList.push_back(cast(Sum)); + } + GEP.setOperand(0, SrcGEPOperands[0]); GEP.setOperand(1, Sum); - WorkList.push_back(cast(Sum)); return &GEP; - } else if (*GEP.idx_begin() == Constant::getNullValue(Type::LongTy) && - Src->getNumOperands() != 1) { + } else if (isa(*GEP.idx_begin()) && + cast(*GEP.idx_begin())->isNullValue() && + SrcGEPOperands.size() != 1) { // Otherwise we can do the fold if the first index of the GEP is a zero - Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end()); + Indices.insert(Indices.end(), SrcGEPOperands.begin()+1, + SrcGEPOperands.end()); Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end()); - } else if (Src->getOperand(Src->getNumOperands()-1) == - Constant::getNullValue(Type::LongTy)) { - // If the src gep ends with a constant array index, merge this get into - // it, even if we have a non-zero array index. - Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end()-1); - Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end()); + } else if (SrcGEPOperands.back() == + Constant::getNullValue(SrcGEPOperands.back()->getType())) { + // We have to check to make sure this really is an ARRAY index we are + // ending up with, not a struct index. + generic_gep_type_iterator::iterator> + GTI = gep_type_begin(SrcGEPOperands[0]->getType(), + SrcGEPOperands.begin()+1, SrcGEPOperands.end()); + std::advance(GTI, SrcGEPOperands.size()-2); + if (isa(*GTI)) { + // If the src gep ends with a constant array index, merge this get into + // it, even if we have a non-zero array index. + Indices.insert(Indices.end(), SrcGEPOperands.begin()+1, + SrcGEPOperands.end()-1); + Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end()); + } } if (!Indices.empty()) - return new GetElementPtrInst(Src->getOperand(0), Indices, GEP.getName()); + return new GetElementPtrInst(SrcGEPOperands[0], Indices, GEP.getName()); } else if (GlobalValue *GV = dyn_cast(GEP.getOperand(0))) { // GEP of global variable. If all of the indices for this GEP are @@ -1281,6 +2721,31 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { // Replace all uses of the GEP with the new constexpr... return ReplaceInstUsesWith(GEP, CE); } + } else if (ConstantExpr *CE = dyn_cast(GEP.getOperand(0))) { + if (CE->getOpcode() == Instruction::Cast) { + if (HasZeroPointerIndex) { + // transform: GEP (cast [10 x ubyte]* X to [0 x ubyte]*), long 0, ... + // into : GEP [10 x ubyte]* X, long 0, ... + // + // This occurs when the program declares an array extern like "int X[];" + // + Constant *X = CE->getOperand(0); + const PointerType *CPTy = cast(CE->getType()); + if (const PointerType *XTy = dyn_cast(X->getType())) + if (const ArrayType *XATy = + dyn_cast(XTy->getElementType())) + if (const ArrayType *CATy = + dyn_cast(CPTy->getElementType())) + if (CATy->getElementType() == XATy->getElementType()) { + // At this point, we know that the cast source type is a pointer + // to an array of the same type as the destination pointer + // array. Because the array type is never stepped over (there + // is a leading zero) we can fold the cast into this GEP. + GEP.setOperand(0, X); + return &GEP; + } + } + } } return 0; @@ -1295,11 +2760,13 @@ Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) { // Create and insert the replacement instruction... if (isa(AI)) - New = new MallocInst(NewTy, 0, AI.getName(), &AI); + New = new MallocInst(NewTy, 0, AI.getName()); else { assert(isa(AI) && "Unknown type of allocation inst!"); - New = new AllocaInst(NewTy, 0, AI.getName(), &AI); + New = new AllocaInst(NewTy, 0, AI.getName()); } + + InsertNewInstBefore(New, AI); // Scan to the end of the allocation instructions, to skip over a block of // allocas if possible... @@ -1310,34 +2777,61 @@ Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) { // Now that I is pointing to the first non-allocation-inst in the block, // insert our getelementptr instruction... // - std::vector Idx(2, Constant::getNullValue(Type::LongTy)); + std::vector Idx(2, Constant::getNullValue(Type::IntTy)); Value *V = new GetElementPtrInst(New, Idx, New->getName()+".sub", It); // Now make everything use the getelementptr instead of the original // allocation. - ReplaceInstUsesWith(AI, V); - return &AI; + return ReplaceInstUsesWith(AI, V); + } + + // If alloca'ing a zero byte object, replace the alloca with a null pointer. + // Note that we only do this for alloca's, because malloc should allocate and + // return a unique pointer, even for a zero byte allocation. + if (isa(AI) && TD->getTypeSize(AI.getAllocatedType()) == 0) + return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType())); + + return 0; +} + +Instruction *InstCombiner::visitFreeInst(FreeInst &FI) { + Value *Op = FI.getOperand(0); + + // Change free * (cast * X to *) into free * X + if (CastInst *CI = dyn_cast(Op)) + if (isa(CI->getOperand(0)->getType())) { + FI.setOperand(0, CI->getOperand(0)); + return &FI; } + + // If we have 'free null' delete the instruction. This can happen in stl code + // when lots of inlining happens. + if (isa(Op)) + return EraseInstFromFunction(FI); + return 0; } + /// GetGEPGlobalInitializer - Given a constant, and a getelementptr /// constantexpr, return the constant value being addressed by the constant /// expression, or null if something is funny. /// static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) { - if (CE->getOperand(1) != Constant::getNullValue(Type::LongTy)) + if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) return 0; // Do not allow stepping over the value! // Loop over all of the operands, tracking down which value we are // addressing... for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i) if (ConstantUInt *CU = dyn_cast(CE->getOperand(i))) { - ConstantStruct *CS = cast(C); + ConstantStruct *CS = dyn_cast(C); + if (CS == 0) return 0; if (CU->getValue() >= CS->getValues().size()) return 0; C = cast(CS->getValues()[CU->getValue()]); } else if (ConstantSInt *CS = dyn_cast(CE->getOperand(i))) { - ConstantArray *CA = cast(C); + ConstantArray *CA = dyn_cast(C); + if (CA == 0) return 0; if ((uint64_t)CS->getValue() >= CA->getValues().size()) return 0; C = cast(CA->getValues()[CS->getValue()]); } else @@ -1347,8 +2841,13 @@ static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) { Instruction *InstCombiner::visitLoadInst(LoadInst &LI) { Value *Op = LI.getOperand(0); - if (ConstantPointerRef *CPR = dyn_cast(Op)) - Op = CPR->getValue(); + if (LI.isVolatile()) return 0; + + if (Constant *C = dyn_cast(Op)) + if (C->isNullValue()) // load null -> 0 + return ReplaceInstUsesWith(LI, Constant::getNullValue(LI.getType())); + else if (ConstantPointerRef *CPR = dyn_cast(C)) + Op = CPR->getValue(); // Instcombine load (constant global) into the value loaded... if (GlobalVariable *GV = dyn_cast(Op)) @@ -1363,13 +2862,34 @@ Instruction *InstCombiner::visitLoadInst(LoadInst &LI) { if (GV->isConstant() && !GV->isExternal()) if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE)) return ReplaceInstUsesWith(LI, V); + + // load (cast X) --> cast (load X) iff safe + if (CastInst *CI = dyn_cast(Op)) { + const Type *DestPTy = cast(CI->getType())->getElementType(); + if (const PointerType *SrcTy = + dyn_cast(CI->getOperand(0)->getType())) { + const Type *SrcPTy = SrcTy->getElementType(); + if (TD->getTypeSize(SrcPTy) == TD->getTypeSize(DestPTy) && + (SrcPTy->isInteger() || isa(SrcPTy)) && + (DestPTy->isInteger() || isa(DestPTy))) { + // Okay, we are casting from one integer or pointer type to another of + // the same size. Instead of casting the pointer before the load, cast + // the result of the loaded value. + Value *NewLoad = InsertNewInstBefore(new LoadInst(CI->getOperand(0), + CI->getName()), LI); + // Now cast the result of the load. + return new CastInst(NewLoad, LI.getType()); + } + } + } + return 0; } Instruction *InstCombiner::visitBranchInst(BranchInst &BI) { // Change br (not X), label True, label False to: br X, label False, True - if (BI.isConditional() && !isa(BI.getCondition())) + if (BI.isConditional() && !isa(BI.getCondition())) { if (Value *V = dyn_castNotVal(BI.getCondition())) { BasicBlock *TrueDest = BI.getSuccessor(0); BasicBlock *FalseDest = BI.getSuccessor(1); @@ -1378,7 +2898,29 @@ Instruction *InstCombiner::visitBranchInst(BranchInst &BI) { BI.setSuccessor(0, FalseDest); BI.setSuccessor(1, TrueDest); return &BI; + } else if (SetCondInst *I = dyn_cast(BI.getCondition())) { + // Cannonicalize setne -> seteq + if ((I->getOpcode() == Instruction::SetNE || + I->getOpcode() == Instruction::SetLE || + I->getOpcode() == Instruction::SetGE) && I->hasOneUse()) { + std::string Name = I->getName(); I->setName(""); + Instruction::BinaryOps NewOpcode = + SetCondInst::getInverseCondition(I->getOpcode()); + Value *NewSCC = BinaryOperator::create(NewOpcode, I->getOperand(0), + I->getOperand(1), Name, I); + BasicBlock *TrueDest = BI.getSuccessor(0); + BasicBlock *FalseDest = BI.getSuccessor(1); + // Swap Destinations and condition... + BI.setCondition(NewSCC); + BI.setSuccessor(0, FalseDest); + BI.setSuccessor(1, TrueDest); + removeFromWorkList(I); + I->getParent()->getInstList().erase(I); + WorkList.push_back(cast(NewSCC)); + return &BI; + } } + } return 0; } @@ -1390,8 +2932,12 @@ void InstCombiner::removeFromWorkList(Instruction *I) { bool InstCombiner::runOnFunction(Function &F) { bool Changed = false; + TD = &getAnalysis(); + + for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { + WorkList.push_back(&*i); + } - WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F)); while (!WorkList.empty()) { Instruction *I = WorkList.back(); // Get an instruction from the worklist @@ -1401,44 +2947,65 @@ bool InstCombiner::runOnFunction(Function &F) { // Check to see if we can DIE the instruction... if (isInstructionTriviallyDead(I)) { // Add operands to the worklist... - for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) - if (Instruction *Op = dyn_cast(I->getOperand(i))) - WorkList.push_back(Op); - + if (I->getNumOperands() < 4) + AddUsesToWorkList(*I); ++NumDeadInst; - BasicBlock::iterator BBI = I; - if (dceInstruction(BBI)) { - removeFromWorkList(I); - continue; - } - } + + I->getParent()->getInstList().erase(I); + removeFromWorkList(I); + continue; + } // Instruction isn't dead, see if we can constant propagate it... if (Constant *C = ConstantFoldInstruction(I)) { // Add operands to the worklist... - for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) - if (Instruction *Op = dyn_cast(I->getOperand(i))) - WorkList.push_back(Op); + AddUsesToWorkList(*I); ReplaceInstUsesWith(*I, C); ++NumConstProp; - BasicBlock::iterator BBI = I; - if (dceInstruction(BBI)) { - removeFromWorkList(I); - continue; - } + I->getParent()->getInstList().erase(I); + removeFromWorkList(I); + continue; } - + + // Check to see if any of the operands of this instruction are a + // ConstantPointerRef. Since they sneak in all over the place and inhibit + // optimization, we want to strip them out unconditionally! + for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) + if (ConstantPointerRef *CPR = + dyn_cast(I->getOperand(i))) { + I->setOperand(i, CPR->getValue()); + Changed = true; + } + // Now that we have an instruction, try combining it to simplify it... if (Instruction *Result = visit(*I)) { ++NumCombined; // Should we replace the old instruction with a new one? if (Result != I) { + DEBUG(std::cerr << "IC: Old = " << *I + << " New = " << *Result); + // Instructions can end up on the worklist more than once. Make sure // we do not process an instruction that has been deleted. removeFromWorkList(I); - ReplaceInstWithInst(I, Result); + + // Move the name to the new instruction first... + std::string OldName = I->getName(); I->setName(""); + Result->setName(OldName); + + // Insert the new instruction into the basic block... + BasicBlock *InstParent = I->getParent(); + InstParent->getInstList().insert(I, Result); + + // Everything uses the new instruction now... + I->replaceAllUsesWith(Result); + + // Erase the old instruction. + InstParent->getInstList().erase(I); } else { + DEBUG(std::cerr << "IC: MOD = " << *I); + BasicBlock::iterator II = I; // If the instruction was modified, it's possible that it is now dead. @@ -1453,7 +3020,7 @@ bool InstCombiner::runOnFunction(Function &F) { if (Result) { WorkList.push_back(Result); - AddUsesToWorkList(*Result); + AddUsersToWorkList(*Result); } Changed = true; } @@ -1462,6 +3029,7 @@ bool InstCombiner::runOnFunction(Function &F) { return Changed; } -Pass *createInstructionCombiningPass() { +Pass *llvm::createInstructionCombiningPass() { return new InstCombiner(); } +