X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FInstructionCombining.cpp;h=92b7f1a39bc719a7c367ff8fadc1463d8f10dc2e;hb=6ffe551f657c948d6a473a198ecbd1188bf9ce45;hp=fb7dc9849235706ceacbca8d9186c6d8bd891d68;hpb=d8864ce7666a1706c718ce1fb56daec65d81c9da;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp index fb7dc984923..92b7f1a39bc 100644 --- a/lib/Transforms/Scalar/InstructionCombining.cpp +++ b/lib/Transforms/Scalar/InstructionCombining.cpp @@ -33,8 +33,10 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "instcombine" #include "llvm/Transforms/Scalar.h" #include "llvm/Instructions.h" +#include "llvm/Intrinsics.h" #include "llvm/Pass.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" @@ -42,9 +44,11 @@ #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; @@ -60,15 +64,25 @@ namespace { 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: @@ -79,6 +93,8 @@ namespace { AU.setPreservesCFG(); } + TargetData &getTargetData() const { return *TD; } + // Visitation implementation - Implement instruction combining for different // instruction types. The semantics are as follows: // Return Value: @@ -97,6 +113,7 @@ 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); @@ -113,6 +130,7 @@ 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. // @@ -125,7 +143,6 @@ namespace { 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 @@ -133,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 @@ -186,6 +224,18 @@ static const Type *getSignedIntegralType(const Type *Ty) { } } +// 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) { @@ -347,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. @@ -381,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; @@ -434,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()) @@ -491,6 +585,11 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { 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; } } @@ -510,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); @@ -531,6 +645,41 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { 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)) @@ -639,6 +788,11 @@ 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 @@ -695,11 +849,15 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { } 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)) @@ -722,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. @@ -990,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); @@ -1055,6 +1220,11 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { 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) @@ -1165,6 +1335,11 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { 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 @@ -1467,7 +1642,7 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { if (CastInst *CI = dyn_cast(Op0)) { Value *CastOp0 = CI->getOperand(0); if (CastOp0->getType()->isLosslesslyConvertibleTo(CI->getType()) && - !isa(Op1) && + (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 @@ -1565,6 +1740,12 @@ 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. @@ -1586,6 +1767,10 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { 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. @@ -1905,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); } @@ -2015,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)); } } @@ -2073,7 +2467,7 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { // Otherwise, it's a call, just insert cast right after the call instr InsertNewInstBefore(NC, *Caller); } - AddUsesToWorkList(*Caller); + AddUsersToWorkList(*Caller); } else { NV = Constant::getNullValue(Caller->getType()); } @@ -2125,6 +2519,20 @@ Instruction *InstCombiner::visitPHINode(PHINode &PN) { 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' @@ -2139,27 +2547,88 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { 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, ... // @@ -2167,32 +2636,73 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { // chain to be resolved before we perform this transformation. This // avoids us creating a TON of code in some cases. // - if (isa(Src->getOperand(0)) && - cast(Src->getOperand(0))->getNumOperands() == 2) + if (isa(SrcGEPOperands[0]) && + cast(SrcGEPOperands[0])->getNumOperands() == 2) return 0; // Wait until our source is folded to completion. - Value *Sum = BinaryOperator::create(Instruction::Add, Src->getOperand(1), - GEP.getOperand(1), - Src->getName()+".sum", &GEP); - GEP.setOperand(0, Src->getOperand(0)); + 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 @@ -2250,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... @@ -2265,14 +2777,20 @@ 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; } @@ -2286,6 +2804,11 @@ Instruction *InstCombiner::visitFreeInst(FreeInst &FI) { 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; } @@ -2295,7 +2818,7 @@ Instruction *InstCombiner::visitFreeInst(FreeInst &FI) { /// 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 @@ -2320,8 +2843,11 @@ Instruction *InstCombiner::visitLoadInst(LoadInst &LI) { Value *Op = LI.getOperand(0); if (LI.isVolatile()) return 0; - if (ConstantPointerRef *CPR = dyn_cast(Op)) - Op = CPR->getValue(); + 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)) @@ -2336,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); @@ -2351,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; } @@ -2365,7 +2934,10 @@ bool InstCombiner::runOnFunction(Function &F) { bool Changed = false; TD = &getAnalysis(); - WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F)); + for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { + WorkList.push_back(&*i); + } + while (!WorkList.empty()) { Instruction *I = WorkList.back(); // Get an instruction from the worklist @@ -2376,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); @@ -2389,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; @@ -2400,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); @@ -2423,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. @@ -2437,7 +3020,7 @@ bool InstCombiner::runOnFunction(Function &F) { if (Result) { WorkList.push_back(Result); - AddUsesToWorkList(*Result); + AddUsersToWorkList(*Result); } Changed = true; }