X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FInstructionCombining.cpp;h=92b7f1a39bc719a7c367ff8fadc1463d8f10dc2e;hb=6ffe551f657c948d6a473a198ecbd1188bf9ce45;hp=d69176f343e254f401ab9992b260b198fa0ed407;hpb=fd05924946ebfcfb3409b21996cfd0836e4ddb31;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp index d69176f343e..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 @@ -26,20 +33,25 @@ // //===----------------------------------------------------------------------===// +#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"); @@ -50,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: @@ -87,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); @@ -102,18 +130,19 @@ namespace { 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; } - public: // ReplaceInstUsesWith - This method is to be used when an instruction is // found to be dead, replacable with another preexisting expression. Here // we add all uses of I to the worklist, replace all uses of I with the new @@ -121,10 +150,31 @@ 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 @@ -162,6 +212,43 @@ static bool isOnlyUse(Value *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 // operators: // @@ -222,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; } @@ -306,30 +397,6 @@ Instruction *AssociativeOpt(BinaryOperator &Root, const Functor &F) { // reassociate the expression from ((? op A) op B) to (? op (A op B)) if (ShouldApply) { BasicBlock *BB = Root.getParent(); - // All of the instructions have a single use and have no side-effects, - // because of this, we can pull them all into the current basic block. - if (LHSI->getParent() != BB) { - // Move all of the instructions from root to LHSI into the current - // block. - Instruction *TmpLHSI = cast(Root.getOperand(0)); - Instruction *LastUse = &Root; - while (TmpLHSI->getParent() == BB) { - LastUse = TmpLHSI; - TmpLHSI = cast(TmpLHSI->getOperand(0)); - } - - // Loop over all of the instructions in other blocks, moving them into - // the current one. - Value *TmpLHS = TmpLHSI; - do { - TmpLHSI = cast(TmpLHS); - // Remove from current block... - TmpLHSI->getParent()->getInstList().remove(TmpLHSI); - // Insert before the last instruction... - BB->getInstList().insert(LastUse, TmpLHSI); - TmpLHS = TmpLHSI->getOperand(0); - } while (TmpLHSI != LHSI); - } // Now all of the instructions are in the current basic block, go ahead // and perform the reassociation. @@ -340,15 +407,27 @@ Instruction *AssociativeOpt(BinaryOperator &Root, const Functor &F) { // 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 - BB->getInstList().remove(&Root); // Remove root from the BB - BB->getInstList().insert(TmpLHSI, &Root); // Insert root before TmpLHSI + 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; @@ -393,15 +472,71 @@ struct AddMaskingAnd { } }; +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); - // X + 0 --> X - 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()) @@ -446,9 +581,15 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { if (ConstantInt *XorRHS = dyn_cast(ILHS->getOperand(1))) if (XorRHS->isAllOnesValue()) return BinaryOperator::create(Instruction::Sub, - *CRHS - *ConstantInt::get(I.getType(), 1), + 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; } } @@ -468,6 +609,21 @@ 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); @@ -478,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->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); @@ -532,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); @@ -545,8 +765,8 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { if (SI->getOpcode() == Instruction::Shl) if (Constant *ShOp = dyn_cast(SI->getOperand(1))) return BinaryOperator::create(Instruction::Mul, SI->getOperand(0), - *CI << *ShOp); - + ConstantExpr::get(Instruction::Shl, CI, ShOp)); + if (CI->isNullValue()) return ReplaceInstUsesWith(I, Op1); // X * 0 == 0 if (CI->equalsInt(1)) // X * 1 == X @@ -568,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)) @@ -605,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. @@ -744,9 +1021,13 @@ Instruction *InstCombiner::OptAndOp(Instruction *Op, 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 ((*AndRHS & *OpRHS)->isNullValue()) { + if (Together->isNullValue()) { // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0 return BinaryOperator::create(Instruction::And, X, AndRHS); } else if (Op->hasOneUse()) { @@ -755,15 +1036,14 @@ Instruction *InstCombiner::OptAndOp(Instruction *Op, Instruction *And = BinaryOperator::create(Instruction::And, X, AndRHS, OpName); InsertNewInstBefore(And, TheAnd); - return BinaryOperator::create(Instruction::Xor, And, *AndRHS & *OpRHS); + return BinaryOperator::create(Instruction::Xor, And, Together); } break; case Instruction::Or: // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0 - if ((*AndRHS & *OpRHS)->isNullValue()) + if (Together->isNullValue()) return BinaryOperator::create(Instruction::And, X, AndRHS); else { - Constant *Together = *AndRHS & *OpRHS; if (Together == AndRHS) // (X | C) & C --> C return ReplaceInstUsesWith(TheAnd, AndRHS); @@ -821,7 +1101,8 @@ Instruction *InstCombiner::OptAndOp(Instruction *Op, // the anded constant includes them, clear them now! // Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType()); - Constant *CI = *AndRHS & *(*AllOne << *OpRHS); + Constant *CI = ConstantExpr::get(Instruction::And, AndRHS, + ConstantExpr::get(Instruction::Shl, AllOne, OpRHS)); if (CI != AndRHS) { TheAnd.setOperand(1, CI); return &TheAnd; @@ -835,7 +1116,8 @@ Instruction *InstCombiner::OptAndOp(Instruction *Op, // if (AndRHS->getType()->isUnsigned()) { Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType()); - Constant *CI = *AndRHS & *(*AllOne >> *OpRHS); + Constant *CI = ConstantExpr::get(Instruction::And, AndRHS, + ConstantExpr::get(Instruction::Shr, AllOne, OpRHS)); if (CI != AndRHS) { TheAnd.setOperand(1, CI); return &TheAnd; @@ -868,6 +1150,11 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { 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); @@ -916,7 +1203,8 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { Op0I->getOperand(0), RHS, Op0Name); InsertNewInstBefore(Or, I); - return BinaryOperator::create(Instruction::And, Or, *RHS | *Op0CI); + return BinaryOperator::create(Instruction::And, Or, + ConstantExpr::get(Instruction::Or, RHS, Op0CI)); } // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2) @@ -927,9 +1215,16 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { Op0I->getOperand(0), RHS, Op0Name); InsertNewInstBefore(Or, I); - return BinaryOperator::create(Instruction::Xor, Or, *Op0CI & *~*RHS); + 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) @@ -939,7 +1234,7 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { if (Constant *C0 = dyn_castMaskingAnd(LHS)) if (Constant *C1 = dyn_castMaskingAnd(RHS)) return BinaryOperator::create(Instruction::And, LHS->getOperand(0), - *C0 | *C1); + ConstantExpr::get(Instruction::Or, C0, C1)); Value *Op0NotVal = dyn_castNotVal(Op0); Value *Op1NotVal = dyn_castNotVal(Op1); @@ -969,15 +1264,26 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { 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 *RHS = dyn_cast(Op1)) { // xor X, 0 == X @@ -990,18 +1296,50 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { 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))) - if (Op0I->getOpcode() == Instruction::And) { + 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 ((*RHS & *Op0CI)->isNullValue()) + if (ConstantExpr::get(Instruction::And, RHS, Op0CI)->isNullValue()) return BinaryOperator::create(Instruction::Or, Op0, RHS); - } else if (Op0I->getOpcode() == Instruction::Or) { + break; + case Instruction::Or: // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 - if ((*RHS & *Op0CI) == RHS) - return BinaryOperator::create(Instruction::And, Op0, ~*RHS); + 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 @@ -1015,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(); @@ -1023,7 +1361,13 @@ 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->hasOneUse()) { @@ -1035,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 @@ -1093,7 +1442,7 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { 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: @@ -1106,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... @@ -1119,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 @@ -1157,7 +1506,7 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { // the explicit xor. if (Constant *BOC = dyn_cast(BO->getOperand(1))) return BinaryOperator::create(I.getOpcode(), BO->getOperand(0), - *CI ^ *BOC); + ConstantExpr::get(Instruction::Xor, CI, BOC)); // FALLTHROUGH case Instruction::Sub: @@ -1170,16 +1519,19 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { 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))) - if (!(*BOC & *~*CI)->isNullValue()) + 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)); + } 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 @@ -1188,14 +1540,7 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { Value *X = BO->getOperand(0); // If 'X' is not signed, insert a cast now... if (!BOC->getType()->isSigned()) { - const Type *DestTy; - switch (BOC->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(); - } + const Type *DestTy = getSignedIntegralType(BOC->getType()); CastInst *NewCI = new CastInst(X,DestTy,X->getName()+".signed"); InsertNewInstBefore(NewCI, I); X = NewCI; @@ -1208,6 +1553,43 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { 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... @@ -1217,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 @@ -1227,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; } @@ -1272,22 +1740,37 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { 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 && - (!Op0->getType()->isSigned() || isLeftShift)) - return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType())); + 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), - *BOOp << *CUI); + 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. @@ -1320,8 +1803,7 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { } if (isValid) { - Constant *NewRHS = - ConstantFoldShiftInstruction(I.getOpcode(), Op0C, CUI); + Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, CUI); Instruction *NewShift = new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI, @@ -1344,6 +1826,8 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { // 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)); } @@ -1355,9 +1839,9 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { // Calculate bitmask for what gets shifted off the edge... Constant *C = ConstantIntegral::getAllOnesValue(I.getType()); if (isLeftShift) - C = ConstantExpr::getShift(Instruction::Shl, C, ShiftAmt1C); + C = ConstantExpr::get(Instruction::Shl, C, ShiftAmt1C); else - C = ConstantExpr::getShift(Instruction::Shr, C, ShiftAmt1C); + C = ConstantExpr::get(Instruction::Shr, C, ShiftAmt1C); Instruction *Mask = BinaryOperator::create(Instruction::And, Op0SI->getOperand(0), @@ -1529,6 +2013,33 @@ Instruction *InstCombiner::visitCastInst(CastInst &CI) { } } + // 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 (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); + } + } + // 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. @@ -1579,9 +2090,219 @@ Instruction *InstCombiner::visitCastInst(CastInst &CI) { 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) { + // 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); } @@ -1591,19 +2312,6 @@ Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) { 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) { @@ -1656,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); @@ -1685,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)); } } @@ -1721,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); @@ -1732,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()); } @@ -1751,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)); + } - // All of the incoming values are the same, replace the PHI node now. - return ReplaceInstUsesWith(PN, InVal); + // 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; +} + +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 @@ -1849,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; @@ -1863,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... @@ -1878,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 @@ -1915,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)) @@ -1931,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); @@ -1946,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; } @@ -1958,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 @@ -1970,9 +2948,7 @@ bool InstCombiner::runOnFunction(Function &F) { if (isInstructionTriviallyDead(I)) { // Add operands to the worklist... if (I->getNumOperands() < 4) - for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) - if (Instruction *Op = dyn_cast(I->getOperand(i))) - WorkList.push_back(Op); + AddUsesToWorkList(*I); ++NumDeadInst; I->getParent()->getInstList().erase(I); @@ -1983,9 +2959,7 @@ bool InstCombiner::runOnFunction(Function &F) { // 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; @@ -1994,11 +2968,24 @@ bool InstCombiner::runOnFunction(Function &F) { 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); @@ -2017,6 +3004,8 @@ bool InstCombiner::runOnFunction(Function &F) { // 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. @@ -2031,7 +3020,7 @@ bool InstCombiner::runOnFunction(Function &F) { if (Result) { WorkList.push_back(Result); - AddUsesToWorkList(*Result); + AddUsersToWorkList(*Result); } Changed = true; } @@ -2040,6 +3029,7 @@ bool InstCombiner::runOnFunction(Function &F) { return Changed; } -Pass *createInstructionCombiningPass() { +Pass *llvm::createInstructionCombiningPass() { return new InstCombiner(); } +