X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FInstructionCombining.cpp;h=91c549d495ed99b1be1503f593c29a70eb0dcbb4;hb=b576c94c15af9a440f69d9d03c2afead7971118c;hp=d00cefd37d4ecc744c83a68c6de7ec5905682659;hpb=3f2ec3925fe3736d70220feb425c70bfbd5bbbad;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp index d00cefd37d4..91c549d495e 100644 --- a/lib/Transforms/Scalar/InstructionCombining.cpp +++ b/lib/Transforms/Scalar/InstructionCombining.cpp @@ -1,4 +1,11 @@ //===- InstructionCombining.cpp - Combine multiple instructions -----------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// // // InstructionCombining - Combine instructions to form fewer, simple // instructions. This pass does not modify the CFG This pass is where algebraic @@ -12,20 +19,32 @@ // // This is a simple worklist driven algorithm. // +// This pass guarantees that the following canonicalizations are performed on +// the program: +// 1. If a binary operator has a constant operand, it is moved to the RHS +// 2. Bitwise operators with constant operands are always grouped so that +// shifts are performed first, then or's, then and's, then xor's. +// 3. SetCC instructions are converted from <,>,<=,>= to ==,!= if possible +// 4. All SetCC instructions on boolean values are replaced with logical ops +// 5. add X, X is represented as (X*2) => (X << 1) +// 6. Multiplies with a power-of-two constant argument are transformed into +// shifts. +// N. This list is incomplete +// //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" -#include "llvm/ConstantHandling.h" -#include "llvm/iMemory.h" -#include "llvm/iOther.h" -#include "llvm/iPHINode.h" -#include "llvm/iOperators.h" +#include "llvm/Instructions.h" #include "llvm/Pass.h" +#include "llvm/Constants.h" +#include "llvm/ConstantHandling.h" #include "llvm/DerivedTypes.h" +#include "llvm/GlobalVariable.h" #include "llvm/Support/InstIterator.h" #include "llvm/Support/InstVisitor.h" +#include "llvm/Support/CallSite.h" #include "Support/Statistic.h" #include @@ -75,13 +94,21 @@ namespace { Instruction *visitSetCondInst(BinaryOperator &I); Instruction *visitShiftInst(ShiftInst &I); Instruction *visitCastInst(CastInst &CI); + Instruction *visitCallInst(CallInst &CI); + Instruction *visitInvokeInst(InvokeInst &II); Instruction *visitPHINode(PHINode &PN); Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP); Instruction *visitAllocationInst(AllocationInst &AI); + Instruction *visitLoadInst(LoadInst &LI); + Instruction *visitBranchInst(BranchInst &BI); // visitInstruction - Specify what to return for unhandled instructions... Instruction *visitInstruction(Instruction &I) { return 0; } + private: + Instruction *visitCallSite(CallSite CS); + bool transformConstExprCastCall(CallSite CS); + // InsertNewInstBefore - insert an instruction New before instruction Old // in the program. Add the new instruction to the worklist. // @@ -93,6 +120,7 @@ namespace { WorkList.push_back(New); // Add to worklist } + 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 @@ -104,11 +132,20 @@ namespace { I.replaceAllUsesWith(V); return &I; } + private: + /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the + /// InsertBefore instruction. This is specialized a bit to avoid inserting + /// casts that are known to not do anything... + /// + Value *InsertOperandCastBefore(Value *V, const Type *DestTy, + Instruction *InsertBefore); // SimplifyCommutative - This performs a few simplifications for commutative // operators... bool SimplifyCommutative(BinaryOperator &I); + Instruction *OptAndOp(Instruction *Op, ConstantIntegral *OpRHS, + ConstantIntegral *AndRHS, BinaryOperator &TheAnd); }; RegisterOpt X("instcombine", "Combine redundant instructions"); @@ -129,7 +166,7 @@ static unsigned getComplexity(Value *V) { // isOnlyUse - Return true if this instruction will be deleted if we stop using // it. static bool isOnlyUse(Value *V) { - return V->use_size() == 1 || isa(V); + return V->hasOneUse() || isa(V); } // SimplifyCommutative - This performs a few simplifications for commutative @@ -152,9 +189,9 @@ bool InstCombiner::SimplifyCommutative(BinaryOperator &I) { if (BinaryOperator *Op = dyn_cast(I.getOperand(0))) if (Op->getOpcode() == Opcode && isa(Op->getOperand(1))) { if (isa(I.getOperand(1))) { - Constant *Folded = ConstantFoldBinaryInstruction(I.getOpcode(), - cast(I.getOperand(1)), cast(Op->getOperand(1))); - assert(Folded && "Couldn't constant fold commutative operand?"); + Constant *Folded = ConstantExpr::get(I.getOpcode(), + cast(I.getOperand(1)), + cast(Op->getOperand(1))); I.setOperand(0, Op->getOperand(0)); I.setOperand(1, Folded); return true; @@ -165,8 +202,7 @@ bool InstCombiner::SimplifyCommutative(BinaryOperator &I) { Constant *C2 = cast(Op1->getOperand(1)); // Fold (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2)) - Constant *Folded = ConstantFoldBinaryInstruction(I.getOpcode(),C1,C2); - assert(Folded && "Couldn't constant fold commutative operand?"); + Constant *Folded = ConstantExpr::get(I.getOpcode(), C1, C2); Instruction *New = BinaryOperator::create(Opcode, Op->getOperand(0), Op1->getOperand(0), Op1->getName(), &I); @@ -188,7 +224,8 @@ static inline Value *dyn_castNegVal(Value *V) { // Constants can be considered to be negated values if they can be folded... if (Constant *C = dyn_cast(V)) - return *Constant::getNullValue(V->getType()) - *C; + return ConstantExpr::get(Instruction::Sub, + Constant::getNullValue(V->getType()), C); return 0; } @@ -198,7 +235,8 @@ static inline Value *dyn_castNotVal(Value *V) { // Constants can be considered to be not'ed values... if (ConstantIntegral *C = dyn_cast(V)) - return *ConstantIntegral::getAllOnesValue(C->getType()) ^ *C; + return ConstantExpr::get(Instruction::Xor, + ConstantIntegral::getAllOnesValue(C->getType()),C); return 0; } @@ -207,7 +245,7 @@ static inline Value *dyn_castNotVal(Value *V) { // non-constant operand of the multiply. // static inline Value *dyn_castFoldableMul(Value *V) { - if (V->use_size() == 1 && V->getType()->isInteger()) + if (V->hasOneUse() && V->getType()->isInteger()) if (Instruction *I = dyn_cast(V)) if (I->getOpcode() == Instruction::Mul) if (isa(I->getOperand(1))) @@ -218,7 +256,8 @@ static inline Value *dyn_castFoldableMul(Value *V) { // dyn_castMaskingAnd - If this value is an And instruction masking a value with // a constant, return the constant being anded with. // -static inline Constant *dyn_castMaskingAnd(Value *V) { +template +static inline Constant *dyn_castMaskingAnd(ValueType *V) { if (Instruction *I = dyn_cast(V)) if (I->getOpcode() == Instruction::And) return dyn_cast(I->getOperand(1)); @@ -240,14 +279,141 @@ static unsigned Log2(uint64_t Val) { return Count; } + +/// AssociativeOpt - Perform an optimization on an associative operator. This +/// function is designed to check a chain of associative operators for a +/// potential to apply a certain optimization. Since the optimization may be +/// applicable if the expression was reassociated, this checks the chain, then +/// reassociates the expression as necessary to expose the optimization +/// opportunity. This makes use of a special Functor, which must define +/// 'shouldApply' and 'apply' methods. +/// +template +Instruction *AssociativeOpt(BinaryOperator &Root, const Functor &F) { + unsigned Opcode = Root.getOpcode(); + Value *LHS = Root.getOperand(0); + + // Quick check, see if the immediate LHS matches... + if (F.shouldApply(LHS)) + return F.apply(Root); + + // Otherwise, if the LHS is not of the same opcode as the root, return. + Instruction *LHSI = dyn_cast(LHS); + while (LHSI && LHSI->getOpcode() == Opcode && LHSI->hasOneUse()) { + // Should we apply this transform to the RHS? + bool ShouldApply = F.shouldApply(LHSI->getOperand(1)); + + // If not to the RHS, check to see if we should apply to the LHS... + if (!ShouldApply && F.shouldApply(LHSI->getOperand(0))) { + cast(LHSI)->swapOperands(); // Make the LHS the RHS + ShouldApply = true; + } + + // If the functor wants to apply the optimization to the RHS of LHSI, + // reassociate the expression from ((? op A) op B) to (? op (A op B)) + if (ShouldApply) { + BasicBlock *BB = Root.getParent(); + // 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. + Instruction *TmpLHSI = cast(Root.getOperand(0)); + + // First move the selected RHS to the LHS of the root... + Root.setOperand(0, LHSI->getOperand(1)); + + // Make what used to be the LHS of the root be the user of the root... + Value *ExtraOperand = TmpLHSI->getOperand(1); + 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 + + // Now propagate the ExtraOperand down the chain of instructions until we + // get to LHSI. + while (TmpLHSI != LHSI) { + Instruction *NextLHSI = cast(TmpLHSI->getOperand(0)); + Value *NextOp = NextLHSI->getOperand(1); + NextLHSI->setOperand(1, ExtraOperand); + TmpLHSI = NextLHSI; + ExtraOperand = NextOp; + } + + // Now that the instructions are reassociated, have the functor perform + // the transformation... + return F.apply(Root); + } + + LHSI = dyn_cast(LHSI->getOperand(0)); + } + return 0; +} + + +// AddRHS - Implements: X + X --> X << 1 +struct AddRHS { + Value *RHS; + AddRHS(Value *rhs) : RHS(rhs) {} + bool shouldApply(Value *LHS) const { return LHS == RHS; } + Instruction *apply(BinaryOperator &Add) const { + return new ShiftInst(Instruction::Shl, Add.getOperand(0), + ConstantInt::get(Type::UByteTy, 1)); + } +}; + +// AddMaskingAnd - Implements (A & C1)+(B & C2) --> (A & C1)|(B & C2) +// iff C1&C2 == 0 +struct AddMaskingAnd { + Constant *C2; + AddMaskingAnd(Constant *c) : C2(c) {} + bool shouldApply(Value *LHS) const { + if (Constant *C1 = dyn_castMaskingAnd(LHS)) + return ConstantExpr::get(Instruction::And, C1, C2)->isNullValue(); + return false; + } + Instruction *apply(BinaryOperator &Add) const { + return BinaryOperator::create(Instruction::Or, Add.getOperand(0), + Add.getOperand(1)); + } +}; + + + Instruction *InstCombiner::visitAdd(BinaryOperator &I) { bool Changed = SimplifyCommutative(I); Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); - // Eliminate 'add int %X, 0' + // X + 0 --> X if (RHS == Constant::getNullValue(I.getType())) return ReplaceInstUsesWith(I, LHS); + // X + X --> X << 1 + if (I.getType()->isInteger()) + if (Instruction *Result = AssociativeOpt(I, AddRHS(RHS))) return Result; + // -A + B --> B - A if (Value *V = dyn_castNegVal(LHS)) return BinaryOperator::create(Instruction::Sub, RHS, V); @@ -259,29 +425,56 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { // X*C + X --> X * (C+1) if (dyn_castFoldableMul(LHS) == RHS) { - Constant *CP1 = *cast(cast(LHS)->getOperand(1)) + - *ConstantInt::get(I.getType(), 1); - assert(CP1 && "Couldn't constant fold C + 1?"); + Constant *CP1 = + ConstantExpr::get(Instruction::Add, + cast(cast(LHS)->getOperand(1)), + ConstantInt::get(I.getType(), 1)); return BinaryOperator::create(Instruction::Mul, RHS, CP1); } // X + X*C --> X * (C+1) if (dyn_castFoldableMul(RHS) == LHS) { - Constant *CP1 = *cast(cast(RHS)->getOperand(1)) + - *ConstantInt::get(I.getType(), 1); - assert(CP1 && "Couldn't constant fold C + 1?"); + Constant *CP1 = + ConstantExpr::get(Instruction::Add, + cast(cast(RHS)->getOperand(1)), + ConstantInt::get(I.getType(), 1)); return BinaryOperator::create(Instruction::Mul, LHS, CP1); } - // (A & C1)+(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 - if (Constant *C1 = dyn_castMaskingAnd(LHS)) - if (Constant *C2 = dyn_castMaskingAnd(RHS)) - if ((*C1 & *C2)->isNullValue()) - return BinaryOperator::create(Instruction::Or, LHS, RHS); + // (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0 + if (Constant *C2 = dyn_castMaskingAnd(RHS)) + if (Instruction *R = AssociativeOpt(I, AddMaskingAnd(C2))) return R; + + if (ConstantInt *CRHS = dyn_cast(RHS)) { + if (Instruction *ILHS = dyn_cast(LHS)) { + switch (ILHS->getOpcode()) { + case Instruction::Xor: + // ~X + C --> (C-1) - X + if (ConstantInt *XorRHS = dyn_cast(ILHS->getOperand(1))) + if (XorRHS->isAllOnesValue()) + return BinaryOperator::create(Instruction::Sub, + *CRHS - *ConstantInt::get(I.getType(), 1), + ILHS->getOperand(0)); + break; + default: break; + } + } + } return Changed ? &I : 0; } +// isSignBit - Return true if the value represented by the constant only has the +// highest order bit set. +static bool isSignBit(ConstantInt *CI) { + unsigned NumBits = CI->getType()->getPrimitiveSize()*8; + return (CI->getRawValue() & ~(-1LL << NumBits)) == (1ULL << (NumBits-1)); +} + +static unsigned getTypeSizeInBits(const Type *Ty) { + return Ty == Type::BoolTy ? 1 : Ty->getPrimitiveSize()*8; +} + Instruction *InstCombiner::visitSub(BinaryOperator &I) { Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); @@ -298,7 +491,7 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { return BinaryOperator::createNot(Op1); if (BinaryOperator *Op1I = dyn_cast(Op1)) - if (Op1I->use_size() == 1) { + if (Op1I->hasOneUse()) { // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression // is not used by anyone else... // @@ -324,8 +517,10 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { // X - X*C --> X * (1-C) if (dyn_castFoldableMul(Op1I) == Op0) { - Constant *CP1 = *ConstantInt::get(I.getType(), 1) - - *cast(cast(Op1)->getOperand(1)); + Constant *CP1 = + ConstantExpr::get(Instruction::Sub, + ConstantInt::get(I.getType(), 1), + cast(cast(Op1)->getOperand(1))); assert(CP1 && "Couldn't constant fold 1-C?"); return BinaryOperator::create(Instruction::Mul, Op0, CP1); } @@ -333,8 +528,10 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { // X*C - X --> X * (C-1) if (dyn_castFoldableMul(Op0) == Op1) { - Constant *CP1 = *cast(cast(Op0)->getOperand(1)) - - *ConstantInt::get(I.getType(), 1); + Constant *CP1 = + ConstantExpr::get(Instruction::Sub, + cast(cast(Op0)->getOperand(1)), + ConstantInt::get(I.getType(), 1)); assert(CP1 && "Couldn't constant fold C - 1?"); return BinaryOperator::create(Instruction::Mul, Op1, CP1); } @@ -349,19 +546,22 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { // Simplify mul instructions with a constant RHS... if (Constant *Op1 = dyn_cast(I.getOperand(1))) { if (ConstantInt *CI = dyn_cast(Op1)) { - const Type *Ty = CI->getType(); - uint64_t Val = Ty->isSigned() ? - (uint64_t)cast(CI)->getValue() : - cast(CI)->getValue(); - switch (Val) { - case 0: - return ReplaceInstUsesWith(I, Op1); // Eliminate 'mul double %X, 0' - case 1: - return ReplaceInstUsesWith(I, Op0); // Eliminate 'mul int %X, 1' - case 2: // Convert 'mul int %X, 2' to 'add int %X, %X' - return BinaryOperator::create(Instruction::Add, Op0, Op0, I.getName()); - } + // ((X << C1)*C2) == (X * (C2 << C1)) + if (ShiftInst *SI = dyn_cast(Op0)) + if (SI->getOpcode() == Instruction::Shl) + if (Constant *ShOp = dyn_cast(SI->getOperand(1))) + return BinaryOperator::create(Instruction::Mul, SI->getOperand(0), + *CI << *ShOp); + + if (CI->isNullValue()) + return ReplaceInstUsesWith(I, Op1); // X * 0 == 0 + if (CI->equalsInt(1)) // X * 1 == X + return ReplaceInstUsesWith(I, Op0); + if (CI->isAllOnesValue()) // X * -1 == 0 - X + return BinaryOperator::createNeg(Op0, I.getName()); + + int64_t Val = (int64_t)cast(CI)->getRawValue(); if (uint64_t C = Log2(Val)) // Replace X*(2^C) with X << C return new ShiftInst(Instruction::Shl, Op0, ConstantUInt::get(Type::UByteTy, C)); @@ -463,6 +663,196 @@ static bool isMinValuePlusOne(const ConstantInt *C) { return CS->getValue() == Val+1; } +/// getSetCondCode - Encode a setcc opcode into a three bit mask. These bits +/// are carefully arranged to allow folding of expressions such as: +/// +/// (A < B) | (A > B) --> (A != B) +/// +/// Bit value '4' represents that the comparison is true if A > B, bit value '2' +/// represents that the comparison is true if A == B, and bit value '1' is true +/// if A < B. +/// +static unsigned getSetCondCode(const SetCondInst *SCI) { + switch (SCI->getOpcode()) { + // False -> 0 + case Instruction::SetGT: return 1; + case Instruction::SetEQ: return 2; + case Instruction::SetGE: return 3; + case Instruction::SetLT: return 4; + case Instruction::SetNE: return 5; + case Instruction::SetLE: return 6; + // True -> 7 + default: + assert(0 && "Invalid SetCC opcode!"); + return 0; + } +} + +/// getSetCCValue - This is the complement of getSetCondCode, which turns an +/// opcode and two operands into either a constant true or false, or a brand new +/// SetCC instruction. +static Value *getSetCCValue(unsigned Opcode, Value *LHS, Value *RHS) { + switch (Opcode) { + case 0: return ConstantBool::False; + case 1: return new SetCondInst(Instruction::SetGT, LHS, RHS); + case 2: return new SetCondInst(Instruction::SetEQ, LHS, RHS); + case 3: return new SetCondInst(Instruction::SetGE, LHS, RHS); + case 4: return new SetCondInst(Instruction::SetLT, LHS, RHS); + case 5: return new SetCondInst(Instruction::SetNE, LHS, RHS); + case 6: return new SetCondInst(Instruction::SetLE, LHS, RHS); + case 7: return ConstantBool::True; + default: assert(0 && "Illegal SetCCCode!"); return 0; + } +} + +// FoldSetCCLogical - Implements (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B) +struct FoldSetCCLogical { + InstCombiner &IC; + Value *LHS, *RHS; + FoldSetCCLogical(InstCombiner &ic, SetCondInst *SCI) + : IC(ic), LHS(SCI->getOperand(0)), RHS(SCI->getOperand(1)) {} + bool shouldApply(Value *V) const { + if (SetCondInst *SCI = dyn_cast(V)) + return (SCI->getOperand(0) == LHS && SCI->getOperand(1) == RHS || + SCI->getOperand(0) == RHS && SCI->getOperand(1) == LHS); + return false; + } + Instruction *apply(BinaryOperator &Log) const { + SetCondInst *SCI = cast(Log.getOperand(0)); + if (SCI->getOperand(0) != LHS) { + assert(SCI->getOperand(1) == LHS); + SCI->swapOperands(); // Swap the LHS and RHS of the SetCC + } + + unsigned LHSCode = getSetCondCode(SCI); + unsigned RHSCode = getSetCondCode(cast(Log.getOperand(1))); + unsigned Code; + switch (Log.getOpcode()) { + case Instruction::And: Code = LHSCode & RHSCode; break; + case Instruction::Or: Code = LHSCode | RHSCode; break; + case Instruction::Xor: Code = LHSCode ^ RHSCode; break; + default: assert(0 && "Illegal logical opcode!"); return 0; + } + + Value *RV = getSetCCValue(Code, LHS, RHS); + if (Instruction *I = dyn_cast(RV)) + return I; + // Otherwise, it's a constant boolean value... + return IC.ReplaceInstUsesWith(Log, RV); + } +}; + + +// OptAndOp - This handles expressions of the form ((val OP C1) & C2). Where +// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is +// guaranteed to be either a shift instruction or a binary operator. +Instruction *InstCombiner::OptAndOp(Instruction *Op, + ConstantIntegral *OpRHS, + ConstantIntegral *AndRHS, + BinaryOperator &TheAnd) { + Value *X = Op->getOperand(0); + switch (Op->getOpcode()) { + case Instruction::Xor: + if ((*AndRHS & *OpRHS)->isNullValue()) { + // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0 + return BinaryOperator::create(Instruction::And, X, AndRHS); + } else if (Op->hasOneUse()) { + // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2) + std::string OpName = Op->getName(); Op->setName(""); + Instruction *And = BinaryOperator::create(Instruction::And, + X, AndRHS, OpName); + InsertNewInstBefore(And, TheAnd); + return BinaryOperator::create(Instruction::Xor, And, *AndRHS & *OpRHS); + } + break; + case Instruction::Or: + // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0 + if ((*AndRHS & *OpRHS)->isNullValue()) + return BinaryOperator::create(Instruction::And, X, AndRHS); + else { + Constant *Together = *AndRHS & *OpRHS; + if (Together == AndRHS) // (X | C) & C --> C + return ReplaceInstUsesWith(TheAnd, AndRHS); + + if (Op->hasOneUse() && Together != OpRHS) { + // (X | C1) & C2 --> (X | (C1&C2)) & C2 + std::string Op0Name = Op->getName(); Op->setName(""); + Instruction *Or = BinaryOperator::create(Instruction::Or, X, + Together, Op0Name); + InsertNewInstBefore(Or, TheAnd); + return BinaryOperator::create(Instruction::And, Or, AndRHS); + } + } + break; + case Instruction::Add: + if (Op->hasOneUse()) { + // Adding a one to a single bit bit-field should be turned into an XOR + // of the bit. First thing to check is to see if this AND is with a + // single bit constant. + unsigned long long AndRHSV = cast(AndRHS)->getRawValue(); + + // Clear bits that are not part of the constant. + AndRHSV &= (1ULL << AndRHS->getType()->getPrimitiveSize()*8)-1; + + // If there is only one bit set... + if ((AndRHSV & (AndRHSV-1)) == 0) { + // Ok, at this point, we know that we are masking the result of the + // ADD down to exactly one bit. If the constant we are adding has + // no bits set below this bit, then we can eliminate the ADD. + unsigned long long AddRHS = cast(OpRHS)->getRawValue(); + + // Check to see if any bits below the one bit set in AndRHSV are set. + if ((AddRHS & (AndRHSV-1)) == 0) { + // If not, the only thing that can effect the output of the AND is + // the bit specified by AndRHSV. If that bit is set, the effect of + // the XOR is to toggle the bit. If it is clear, then the ADD has + // no effect. + if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop + TheAnd.setOperand(0, X); + return &TheAnd; + } else { + std::string Name = Op->getName(); Op->setName(""); + // Pull the XOR out of the AND. + Instruction *NewAnd = + BinaryOperator::create(Instruction::And, X, AndRHS, Name); + InsertNewInstBefore(NewAnd, TheAnd); + return BinaryOperator::create(Instruction::Xor, NewAnd, AndRHS); + } + } + } + } + break; + + case Instruction::Shl: { + // We know that the AND will not produce any of the bits shifted in, so if + // the anded constant includes them, clear them now! + // + Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType()); + Constant *CI = *AndRHS & *(*AllOne << *OpRHS); + if (CI != AndRHS) { + TheAnd.setOperand(1, CI); + return &TheAnd; + } + break; + } + case Instruction::Shr: + // We know that the AND will not produce any of the bits shifted in, so if + // the anded constant includes them, clear them now! This only applies to + // unsigned shifts, because a signed shr may bring in set bits! + // + if (AndRHS->getType()->isUnsigned()) { + Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType()); + Constant *CI = *AndRHS & *(*AllOne >> *OpRHS); + if (CI != AndRHS) { + TheAnd.setOperand(1, CI); + return &TheAnd; + } + } + break; + } + return 0; +} + Instruction *InstCombiner::visitAnd(BinaryOperator &I) { bool Changed = SimplifyCommutative(I); @@ -473,25 +863,39 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { return ReplaceInstUsesWith(I, Op1); // and X, -1 == X - if (ConstantIntegral *RHS = dyn_cast(Op1)) + if (ConstantIntegral *RHS = dyn_cast(Op1)) { if (RHS->isAllOnesValue()) return ReplaceInstUsesWith(I, Op0); + // Optimize a variety of ((val OP C1) & C2) combinations... + if (isa(Op0) || isa(Op0)) { + Instruction *Op0I = cast(Op0); + Value *X = Op0I->getOperand(0); + if (ConstantInt *Op0CI = dyn_cast(Op0I->getOperand(1))) + if (Instruction *Res = OptAndOp(Op0I, Op0CI, RHS, I)) + return Res; + } + } + Value *Op0NotVal = dyn_castNotVal(Op0); Value *Op1NotVal = dyn_castNotVal(Op1); // (~A & ~B) == (~(A | B)) - Demorgan's Law if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) { Instruction *Or = BinaryOperator::create(Instruction::Or, Op0NotVal, - Op1NotVal,I.getName()+".demorgan", - &I); - WorkList.push_back(Or); + Op1NotVal,I.getName()+".demorgan"); + InsertNewInstBefore(Or, I); return BinaryOperator::createNot(Or); } if (Op0NotVal == Op1 || Op1NotVal == Op0) // A & ~A == ~A & A == 0 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); + // (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B) + if (SetCondInst *RHS = dyn_cast(I.getOperand(1))) + if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS))) + return R; + return Changed ? &I : 0; } @@ -506,10 +910,44 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { return ReplaceInstUsesWith(I, Op0); // or X, -1 == -1 - if (ConstantIntegral *RHS = dyn_cast(Op1)) + if (ConstantIntegral *RHS = dyn_cast(Op1)) { if (RHS->isAllOnesValue()) return ReplaceInstUsesWith(I, Op1); + if (Instruction *Op0I = dyn_cast(Op0)) { + // (X & C1) | C2 --> (X | C2) & (C1|C2) + if (Op0I->getOpcode() == Instruction::And && isOnlyUse(Op0)) + if (ConstantInt *Op0CI = dyn_cast(Op0I->getOperand(1))) { + std::string Op0Name = Op0I->getName(); Op0I->setName(""); + Instruction *Or = BinaryOperator::create(Instruction::Or, + Op0I->getOperand(0), RHS, + Op0Name); + InsertNewInstBefore(Or, I); + return BinaryOperator::create(Instruction::And, Or, *RHS | *Op0CI); + } + + // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2) + if (Op0I->getOpcode() == Instruction::Xor && isOnlyUse(Op0)) + if (ConstantInt *Op0CI = dyn_cast(Op0I->getOperand(1))) { + std::string Op0Name = Op0I->getName(); Op0I->setName(""); + Instruction *Or = BinaryOperator::create(Instruction::Or, + Op0I->getOperand(0), RHS, + Op0Name); + InsertNewInstBefore(Or, I); + return BinaryOperator::create(Instruction::Xor, Or, *Op0CI & *~*RHS); + } + } + } + + // (A & C1)|(A & C2) == A & (C1|C2) + if (Instruction *LHS = dyn_cast(Op0)) + if (Instruction *RHS = dyn_cast(Op1)) + if (LHS->getOperand(0) == RHS->getOperand(0)) + if (Constant *C0 = dyn_castMaskingAnd(LHS)) + if (Constant *C1 = dyn_castMaskingAnd(RHS)) + return BinaryOperator::create(Instruction::And, LHS->getOperand(0), + *C0 | *C1); + Value *Op0NotVal = dyn_castNotVal(Op0); Value *Op1NotVal = dyn_castNotVal(Op1); @@ -530,6 +968,11 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { return BinaryOperator::createNot(And); } + // (setcc1 A, B) | (setcc2 A, B) --> (setcc3 A, B) + if (SetCondInst *RHS = dyn_cast(I.getOperand(1))) + if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS))) + return R; + return Changed ? &I : 0; } @@ -543,22 +986,28 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { if (Op0 == Op1) return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); - if (ConstantIntegral *Op1C = dyn_cast(Op1)) { + if (ConstantIntegral *RHS = dyn_cast(Op1)) { // xor X, 0 == X - if (Op1C->isNullValue()) + if (RHS->isNullValue()) return ReplaceInstUsesWith(I, Op0); - // Is this a "NOT" instruction? - if (Op1C->isAllOnesValue()) { - // xor (xor X, -1), -1 = not (not X) = X - if (Value *X = dyn_castNotVal(Op0)) - return ReplaceInstUsesWith(I, X); - + if (BinaryOperator *Op0I = dyn_cast(Op0)) { // xor (setcc A, B), true = not (setcc A, B) = setncc A, B - if (SetCondInst *SCI = dyn_cast(Op0)) - if (SCI->use_size() == 1) + if (SetCondInst *SCI = dyn_cast(Op0I)) + if (RHS == ConstantBool::True && SCI->hasOneUse()) return new SetCondInst(SCI->getInverseCondition(), SCI->getOperand(0), SCI->getOperand(1)); + + if (ConstantInt *Op0CI = dyn_cast(Op0I->getOperand(1))) + if (Op0I->getOpcode() == Instruction::And) { + // (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0 + if ((*RHS & *Op0CI)->isNullValue()) + return BinaryOperator::create(Instruction::Or, Op0, RHS); + } else if (Op0I->getOpcode() == Instruction::Or) { + // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 + if ((*RHS & *Op0CI) == RHS) + return BinaryOperator::create(Instruction::And, Op0, ~*RHS); + } } } @@ -584,7 +1033,7 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { } if (Instruction *Op0I = dyn_cast(Op0)) - if (Op0I->getOpcode() == Instruction::Or && Op0I->use_size() == 1) { + if (Op0I->getOpcode() == Instruction::Or && Op0I->hasOneUse()) { if (Op0I->getOperand(0) == Op1) // (B|A)^B == (A|B)^B cast(Op0I)->swapOperands(); if (Op0I->getOperand(1) == Op1) { // (A|B)^B == A & ~B @@ -598,20 +1047,27 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1^C2 == 0 if (Constant *C1 = dyn_castMaskingAnd(Op0)) if (Constant *C2 = dyn_castMaskingAnd(Op1)) - if ((*C1 & *C2)->isNullValue()) + if (ConstantExpr::get(Instruction::And, C1, C2)->isNullValue()) return BinaryOperator::create(Instruction::Or, Op0, Op1); + // (setcc1 A, B) ^ (setcc2 A, B) --> (setcc3 A, B) + if (SetCondInst *RHS = dyn_cast(I.getOperand(1))) + if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS))) + return R; + return Changed ? &I : 0; } // AddOne, SubOne - Add or subtract a constant one from an integer constant... static Constant *AddOne(ConstantInt *C) { - Constant *Result = *C + *ConstantInt::get(C->getType(), 1); + Constant *Result = ConstantExpr::get(Instruction::Add, C, + ConstantInt::get(C->getType(), 1)); assert(Result && "Constant folding integer addition failed!"); return Result; } static Constant *SubOne(ConstantInt *C) { - Constant *Result = *C - *ConstantInt::get(C->getType(), 1); + Constant *Result = ConstantExpr::get(Instruction::Sub, C, + ConstantInt::get(C->getType(), 1)); assert(Result && "Constant folding integer addition failed!"); return Result; } @@ -634,10 +1090,12 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { if (Op0 == Op1) return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I))); - // setcc , 0 - Global value addresses are never null! - if (isa(Op0) && isa(Op1)) + // setcc , 0 - Global/Stack value addresses are never null! + if (isa(Op1) && + (isa(Op0) || isa(Op0))) return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I))); + // setcc's with boolean values can always be turned into bitwise operations if (Ty == Type::BoolTy) { // If this is <, >, or !=, we can change this into a simple xor instruction @@ -675,6 +1133,90 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { // integers at the end of their ranges... // if (ConstantInt *CI = dyn_cast(Op1)) { + // Simplify seteq and setne instructions... + if (I.getOpcode() == Instruction::SetEQ || + I.getOpcode() == Instruction::SetNE) { + bool isSetNE = I.getOpcode() == Instruction::SetNE; + + // If the first operand is (and|or|xor) with a constant, and the second + // operand is a constant, simplify a bit. + if (BinaryOperator *BO = dyn_cast(Op0)) { + switch (BO->getOpcode()) { + case Instruction::Add: + if (CI->isNullValue()) { + // Replace ((add A, B) != 0) with (A != -B) if A or B is + // efficiently invertible, or if the add has just this one use. + Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1); + if (Value *NegVal = dyn_castNegVal(BOp1)) + return new SetCondInst(I.getOpcode(), BOp0, NegVal); + else if (Value *NegVal = dyn_castNegVal(BOp0)) + return new SetCondInst(I.getOpcode(), NegVal, BOp1); + else if (BO->hasOneUse()) { + Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName()); + BO->setName(""); + InsertNewInstBefore(Neg, I); + return new SetCondInst(I.getOpcode(), BOp0, Neg); + } + } + break; + case Instruction::Xor: + // For the xor case, we can xor two constants together, eliminating + // the explicit xor. + if (Constant *BOC = dyn_cast(BO->getOperand(1))) + return BinaryOperator::create(I.getOpcode(), BO->getOperand(0), + *CI ^ *BOC); + + // FALLTHROUGH + case Instruction::Sub: + // Replace (([sub|xor] A, B) != 0) with (A != B) + if (CI->isNullValue()) + return new SetCondInst(I.getOpcode(), BO->getOperand(0), + BO->getOperand(1)); + break; + + case Instruction::Or: + // If bits are being or'd in that are not present in the constant we + // are comparing against, then the comparison could never succeed! + if (Constant *BOC = dyn_cast(BO->getOperand(1))) + if (!(*BOC & *~*CI)->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()) + return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE)); + + // Replace (and X, (1 << size(X)-1) != 0) with x < 0, converting X + // to be a signed value as appropriate. + if (isSignBit(BOC)) { + Value *X = BO->getOperand(0); + // If 'X' is not signed, insert a cast now... + if (!BOC->getType()->isSigned()) { + const Type *DestTy; + 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(); + } + CastInst *NewCI = new CastInst(X,DestTy,X->getName()+".signed"); + InsertNewInstBefore(NewCI, I); + X = NewCI; + } + return new SetCondInst(isSetNE ? Instruction::SetLT : + Instruction::SetGE, X, + Constant::getNullValue(X->getType())); + } + } + default: break; + } + } + } + // Check to see if we are comparing against the minimum or maximum value... if (CI->isMinValue()) { if (I.getOpcode() == Instruction::SetLT) // A < MIN -> FALSE @@ -723,6 +1265,7 @@ Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { assert(I.getOperand(1)->getType() == Type::UByteTy); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); + bool isLeftShift = I.getOpcode() == Instruction::Shl; // shl X, 0 == X and shr X, 0 == X // shl 0, X == 0 and shr 0, X == 0 @@ -730,70 +1273,118 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { Op0 == Constant::getNullValue(Op0->getType())) return ReplaceInstUsesWith(I, Op0); - // If this is a shift of a shift, see if we can fold the two together... - if (ShiftInst *Op0SI = dyn_cast(Op0)) { - if (isa(Op1) && isa(Op0SI->getOperand(1))) { - ConstantUInt *ShiftAmt1C = cast(Op0SI->getOperand(1)); - unsigned ShiftAmt1 = ShiftAmt1C->getValue(); - unsigned ShiftAmt2 = cast(Op1)->getValue(); - - // Check for (A << c1) << c2 and (A >> c1) >> c2 - if (I.getOpcode() == Op0SI->getOpcode()) { - unsigned Amt = ShiftAmt1+ShiftAmt2; // Fold into one big shift... - return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0), - ConstantUInt::get(Type::UByteTy, Amt)); - } - - if (I.getType()->isUnsigned()) { // Check for (A << c1) >> c2 or visaversa - // Calculate bitmask for what gets shifted off the edge... - Constant *C = ConstantIntegral::getAllOnesValue(I.getType()); - if (I.getOpcode() == Instruction::Shr) - C = *C >> *ShiftAmt1C; - else - C = *C << *ShiftAmt1C; - assert(C && "Couldn't constant fold shift expression?"); - - Instruction *Mask = - BinaryOperator::create(Instruction::And, Op0SI->getOperand(0), - C, Op0SI->getOperand(0)->getName()+".mask",&I); - WorkList.push_back(Mask); - - // Figure out what flavor of shift we should use... - if (ShiftAmt1 == ShiftAmt2) - return ReplaceInstUsesWith(I, Mask); // (A << c) >> c === A & c2 - else if (ShiftAmt1 < ShiftAmt2) { - return new ShiftInst(I.getOpcode(), Mask, - ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1)); - } else { - return new ShiftInst(Op0SI->getOpcode(), Mask, - ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2)); - } - } - } - } + // shr int -1, X = -1 (for any arithmetic shift rights of ~0) + if (!isLeftShift) + if (ConstantSInt *CSI = dyn_cast(Op0)) + if (CSI->isAllOnesValue()) + return ReplaceInstUsesWith(I, CSI); - // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr of - // a signed value. - // if (ConstantUInt *CUI = dyn_cast(Op1)) { + // 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() || I.getOpcode() == Instruction::Shl)) + (!Op0->getType()->isSigned() || isLeftShift)) return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType())); - // Check to see if we are shifting left by 1. If so, turn it into an add - // instruction. - if (I.getOpcode() == Instruction::Shl && CUI->equalsInt(1)) - // Convert 'shl int %X, 1' to 'add int %X, %X' - return BinaryOperator::create(Instruction::Add, Op0, Op0, I.getName()); + // ((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); + + + // If the operand is an bitwise operator with a constant RHS, and the + // shift is the only use, we can pull it out of the shift. + if (Op0->hasOneUse()) + if (BinaryOperator *Op0BO = dyn_cast(Op0)) + if (ConstantInt *Op0C = dyn_cast(Op0BO->getOperand(1))) { + bool isValid = true; // Valid only for And, Or, Xor + bool highBitSet = false; // Transform if high bit of constant set? + + switch (Op0BO->getOpcode()) { + default: isValid = false; break; // Do not perform transform! + case Instruction::Or: + case Instruction::Xor: + highBitSet = false; + break; + case Instruction::And: + highBitSet = true; + break; + } + + // If this is a signed shift right, and the high bit is modified + // by the logical operation, do not perform the transformation. + // The highBitSet boolean indicates the value of the high bit of + // the constant which would cause it to be modified for this + // operation. + // + if (isValid && !isLeftShift && !I.getType()->isUnsigned()) { + uint64_t Val = Op0C->getRawValue(); + isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet; + } + + if (isValid) { + Constant *NewRHS = + ConstantFoldShiftInstruction(I.getOpcode(), Op0C, CUI); + + Instruction *NewShift = + new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI, + Op0BO->getName()); + Op0BO->setName(""); + InsertNewInstBefore(NewShift, I); + + return BinaryOperator::create(Op0BO->getOpcode(), NewShift, + NewRHS); + } + } + // If this is a shift of a shift, see if we can fold the two together... + if (ShiftInst *Op0SI = dyn_cast(Op0)) + if (ConstantUInt *ShiftAmt1C = + dyn_cast(Op0SI->getOperand(1))) { + unsigned ShiftAmt1 = ShiftAmt1C->getValue(); + unsigned ShiftAmt2 = CUI->getValue(); + + // Check for (A << c1) << c2 and (A >> c1) >> c2 + if (I.getOpcode() == Op0SI->getOpcode()) { + unsigned Amt = ShiftAmt1+ShiftAmt2; // Fold into one big shift... + return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0), + ConstantUInt::get(Type::UByteTy, Amt)); + } + + // Check for (A << c1) >> c2 or visaversa. If we are dealing with + // signed types, we can only support the (A >> c1) << c2 configuration, + // because it can not turn an arbitrary bit of A into a sign bit. + if (I.getType()->isUnsigned() || isLeftShift) { + // Calculate bitmask for what gets shifted off the edge... + Constant *C = ConstantIntegral::getAllOnesValue(I.getType()); + if (isLeftShift) + C = ConstantExpr::getShift(Instruction::Shl, C, ShiftAmt1C); + else + C = ConstantExpr::getShift(Instruction::Shr, C, ShiftAmt1C); + + Instruction *Mask = + BinaryOperator::create(Instruction::And, Op0SI->getOperand(0), + C, Op0SI->getOperand(0)->getName()+".mask"); + InsertNewInstBefore(Mask, I); + + // Figure out what flavor of shift we should use... + if (ShiftAmt1 == ShiftAmt2) + return ReplaceInstUsesWith(I, Mask); // (A << c) >> c === A & c2 + else if (ShiftAmt1 < ShiftAmt2) { + return new ShiftInst(I.getOpcode(), Mask, + ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1)); + } else { + return new ShiftInst(Op0SI->getOpcode(), Mask, + ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2)); + } + } + } } - // shr int -1, X = -1 (for any arithmetic shift rights of ~0) - if (ConstantSInt *CSI = dyn_cast(Op0)) - if (I.getOpcode() == Instruction::Shr && CSI->isAllOnesValue()) - return ReplaceInstUsesWith(I, CSI); - return 0; } @@ -801,17 +1392,13 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { // isEliminableCastOfCast - Return true if it is valid to eliminate the CI // instruction. // -static inline bool isEliminableCastOfCast(const CastInst &CI, - const CastInst *CSrc) { - assert(CI.getOperand(0) == CSrc); - const Type *SrcTy = CSrc->getOperand(0)->getType(); - const Type *MidTy = CSrc->getType(); - const Type *DstTy = CI.getType(); +static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy, + const Type *DstTy) { // It is legal to eliminate the instruction if casting A->B->A if the sizes // are identical and the bits don't get reinterpreted (for example // int->float->int would not be allowed) - if (SrcTy == DstTy && SrcTy->isLosslesslyConvertableTo(MidTy)) + if (SrcTy == DstTy && SrcTy->isLosslesslyConvertibleTo(MidTy)) return true; // Allow free casting and conversion of sizes as long as the sign doesn't @@ -871,20 +1458,45 @@ static inline bool isEliminableCastOfCast(const CastInst &CI, return false; } +static bool ValueRequiresCast(const Value *V, const Type *Ty) { + if (V->getType() == Ty || isa(V)) return false; + if (const CastInst *CI = dyn_cast(V)) + if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty)) + return false; + return true; +} + +/// InsertOperandCastBefore - This inserts a cast of V to DestTy before the +/// InsertBefore instruction. This is specialized a bit to avoid inserting +/// casts that are known to not do anything... +/// +Value *InstCombiner::InsertOperandCastBefore(Value *V, const Type *DestTy, + Instruction *InsertBefore) { + if (V->getType() == DestTy) return V; + if (Constant *C = dyn_cast(V)) + return ConstantExpr::getCast(C, DestTy); + + CastInst *CI = new CastInst(V, DestTy, V->getName()); + InsertNewInstBefore(CI, *InsertBefore); + return CI; +} // CastInst simplification // Instruction *InstCombiner::visitCastInst(CastInst &CI) { + Value *Src = CI.getOperand(0); + // If the user is casting a value to the same type, eliminate this cast // instruction... - if (CI.getType() == CI.getOperand(0)->getType()) - return ReplaceInstUsesWith(CI, CI.getOperand(0)); + if (CI.getType() == Src->getType()) + return ReplaceInstUsesWith(CI, Src); // If casting the result of another cast instruction, try to eliminate this // one! // - if (CastInst *CSrc = dyn_cast(CI.getOperand(0))) { - if (isEliminableCastOfCast(CI, CSrc)) { + if (CastInst *CSrc = dyn_cast(Src)) { + if (isEliminableCastOfCast(CSrc->getOperand(0)->getType(), + CSrc->getType(), CI.getType())) { // This instruction now refers directly to the cast's src operand. This // has a good chance of making CSrc dead. CI.setOperand(0, CSrc->getOperand(0)); @@ -900,16 +1512,248 @@ Instruction *InstCombiner::visitCastInst(CastInst &CI) { CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){ assert(CSrc->getType() != Type::ULongTy && "Cannot have type bigger than ulong!"); - unsigned AndValue = (1U << CSrc->getType()->getPrimitiveSize()*8)-1; + uint64_t AndValue = (1ULL << CSrc->getType()->getPrimitiveSize()*8)-1; Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue); return BinaryOperator::create(Instruction::And, CSrc->getOperand(0), AndOp); } } + // If casting the result of a getelementptr instruction with no offset, turn + // this into a cast of the original pointer! + // + if (GetElementPtrInst *GEP = dyn_cast(Src)) { + bool AllZeroOperands = true; + for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i) + if (!isa(GEP->getOperand(i)) || + !cast(GEP->getOperand(i))->isNullValue()) { + AllZeroOperands = false; + break; + } + if (AllZeroOperands) { + CI.setOperand(0, GEP->getOperand(0)); + return &CI; + } + } + + // If the source value is an instruction with only this use, we can attempt to + // propagate the cast into the instruction. Also, only handle integral types + // for now. + if (Instruction *SrcI = dyn_cast(Src)) + if (SrcI->hasOneUse() && Src->getType()->isIntegral() && + CI.getType()->isInteger()) { // Don't mess with casts to bool here + const Type *DestTy = CI.getType(); + unsigned SrcBitSize = getTypeSizeInBits(Src->getType()); + unsigned DestBitSize = getTypeSizeInBits(DestTy); + + Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0; + Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0; + + switch (SrcI->getOpcode()) { + case Instruction::Add: + case Instruction::Mul: + case Instruction::And: + case Instruction::Or: + case Instruction::Xor: + // If we are discarding information, or just changing the sign, rewrite. + if (DestBitSize <= SrcBitSize && DestBitSize != 1) { + // Don't insert two casts if they cannot be eliminated. We allow two + // casts to be inserted if the sizes are the same. This could only be + // converting signedness, which is a noop. + if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy) || + !ValueRequiresCast(Op0, DestTy)) { + Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI); + Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI); + return BinaryOperator::create(cast(SrcI) + ->getOpcode(), Op0c, Op1c); + } + } + break; + case Instruction::Shl: + // Allow changing the sign of the source operand. Do not allow changing + // the size of the shift, UNLESS the shift amount is a constant. We + // mush not change variable sized shifts to a smaller size, because it + // is undefined to shift more bits out than exist in the value. + if (DestBitSize == SrcBitSize || + (DestBitSize < SrcBitSize && isa(Op1))) { + Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI); + return new ShiftInst(Instruction::Shl, Op0c, Op1); + } + break; + } + } + return 0; } +// CallInst simplification +// +Instruction *InstCombiner::visitCallInst(CallInst &CI) { + return visitCallSite(&CI); +} + +// InvokeInst simplification +// +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) { + bool Changed = false; + + // If the callee is a constexpr cast of a function, attempt to move the cast + // to the arguments of the call/invoke. + if (transformConstExprCastCall(CS)) return 0; + + Value *Callee = CS.getCalledValue(); + const PointerType *PTy = cast(Callee->getType()); + const FunctionType *FTy = cast(PTy->getElementType()); + if (FTy->isVarArg()) { + // See if we can optimize any arguments passed through the varargs area of + // the call. + for (CallSite::arg_iterator I = CS.arg_begin()+FTy->getNumParams(), + E = CS.arg_end(); I != E; ++I) + if (CastInst *CI = dyn_cast(*I)) { + // If this cast does not effect the value passed through the varargs + // area, we can eliminate the use of the cast. + Value *Op = CI->getOperand(0); + if (CI->getType()->isLosslesslyConvertibleTo(Op->getType())) { + *I = Op; + Changed = true; + } + } + } + + return Changed ? CS.getInstruction() : 0; +} + +// transformConstExprCastCall - If the callee is a constexpr cast of a function, +// attempt to move the cast to the arguments of the call/invoke. +// +bool InstCombiner::transformConstExprCastCall(CallSite CS) { + if (!isa(CS.getCalledValue())) return false; + ConstantExpr *CE = cast(CS.getCalledValue()); + if (CE->getOpcode() != Instruction::Cast || + !isa(CE->getOperand(0))) + return false; + ConstantPointerRef *CPR = cast(CE->getOperand(0)); + if (!isa(CPR->getValue())) return false; + Function *Callee = cast(CPR->getValue()); + Instruction *Caller = CS.getInstruction(); + + // Okay, this is a cast from a function to a different type. Unless doing so + // would cause a type conversion of one of our arguments, change this call to + // be a direct call with arguments casted to the appropriate types. + // + const FunctionType *FT = Callee->getFunctionType(); + const Type *OldRetTy = Caller->getType(); + + if (Callee->isExternal() && + !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType())) + return false; // Cannot transform this return value... + + unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin()); + unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs); + + CallSite::arg_iterator AI = CS.arg_begin(); + for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) { + const Type *ParamTy = FT->getParamType(i); + bool isConvertible = (*AI)->getType()->isLosslesslyConvertibleTo(ParamTy); + if (Callee->isExternal() && !isConvertible) return false; + } + + if (FT->getNumParams() < NumActualArgs && !FT->isVarArg() && + Callee->isExternal()) + return false; // Do not delete arguments unless we have a function body... + + // Okay, we decided that this is a safe thing to do: go ahead and start + // inserting cast instructions as necessary... + std::vector Args; + Args.reserve(NumActualArgs); + + AI = CS.arg_begin(); + for (unsigned i = 0; i != NumCommonArgs; ++i, ++AI) { + const Type *ParamTy = FT->getParamType(i); + if ((*AI)->getType() == ParamTy) { + Args.push_back(*AI); + } else { + Instruction *Cast = new CastInst(*AI, ParamTy, "tmp"); + InsertNewInstBefore(Cast, *Caller); + Args.push_back(Cast); + } + } + + // If the function takes more arguments than the call was taking, add them + // now... + for (unsigned i = NumCommonArgs; i != FT->getNumParams(); ++i) + Args.push_back(Constant::getNullValue(FT->getParamType(i))); + + // If we are removing arguments to the function, emit an obnoxious warning... + if (FT->getNumParams() < NumActualArgs) + if (!FT->isVarArg()) { + std::cerr << "WARNING: While resolving call to function '" + << Callee->getName() << "' arguments were dropped!\n"; + } else { + // Add all of the arguments in their promoted form to the arg list... + for (unsigned i = FT->getNumParams(); i != NumActualArgs; ++i, ++AI) { + const Type *PTy = getPromotedType((*AI)->getType()); + if (PTy != (*AI)->getType()) { + // Must promote to pass through va_arg area! + Instruction *Cast = new CastInst(*AI, PTy, "tmp"); + InsertNewInstBefore(Cast, *Caller); + Args.push_back(Cast); + } else { + Args.push_back(*AI); + } + } + } + + if (FT->getReturnType() == Type::VoidTy) + Caller->setName(""); // Void type should not have a name... + + Instruction *NC; + if (InvokeInst *II = dyn_cast(Caller)) { + NC = new InvokeInst(Callee, II->getNormalDest(), II->getExceptionalDest(), + Args, Caller->getName(), Caller); + } else { + NC = new CallInst(Callee, Args, Caller->getName(), Caller); + } + + // Insert a cast of the return type as necessary... + Value *NV = NC; + 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); + } else { + NV = Constant::getNullValue(Caller->getType()); + } + } + + if (Caller->getType() != Type::VoidTy && !Caller->use_empty()) + Caller->replaceAllUsesWith(NV); + Caller->getParent()->getInstList().erase(Caller); + removeFromWorkList(Caller); + return true; +} + + // PHINode simplification // @@ -941,7 +1785,7 @@ Instruction *InstCombiner::visitPHINode(PHINode &PN) { Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { - // Is it 'getelementptr %P, uint 0' or 'getelementptr %P' + // 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)) || @@ -956,18 +1800,19 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { std::vector Indices; // Can we combine the two pointer arithmetics offsets? - if (Src->getNumOperands() == 2 && isa(Src->getOperand(1)) && - isa(GEP.getOperand(1))) { + if (Src->getNumOperands() == 2 && isa(Src->getOperand(1)) && + isa(GEP.getOperand(1))) { // Replace: gep (gep %P, long C1), long C2, ... // With: gep %P, long (C1+C2), ... - Value *Sum = *cast(Src->getOperand(1)) + - *cast(GEP.getOperand(1)); + 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 return &GEP; - } else if (Src->getNumOperands() == 2 && Src->use_size() == 1) { + } else if (Src->getNumOperands() == 2) { // Replace: gep (gep %P, long B), long A, ... // With: T = long A+B; gep %P, T, ... // @@ -1051,6 +1896,66 @@ Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) { 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)) + 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); + 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); + if ((uint64_t)CS->getValue() >= CA->getValues().size()) return 0; + C = cast(CA->getValues()[CS->getValue()]); + } else + return 0; + return C; +} + +Instruction *InstCombiner::visitLoadInst(LoadInst &LI) { + Value *Op = LI.getOperand(0); + if (ConstantPointerRef *CPR = dyn_cast(Op)) + Op = CPR->getValue(); + + // Instcombine load (constant global) into the value loaded... + if (GlobalVariable *GV = dyn_cast(Op)) + if (GV->isConstant() && !GV->isExternal()) + return ReplaceInstUsesWith(LI, GV->getInitializer()); + + // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded... + if (ConstantExpr *CE = dyn_cast(Op)) + if (CE->getOpcode() == Instruction::GetElementPtr) + if (ConstantPointerRef *G=dyn_cast(CE->getOperand(0))) + if (GlobalVariable *GV = dyn_cast(G->getValue())) + if (GV->isConstant() && !GV->isExternal()) + if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE)) + return ReplaceInstUsesWith(LI, V); + 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 (Value *V = dyn_castNotVal(BI.getCondition())) { + BasicBlock *TrueDest = BI.getSuccessor(0); + BasicBlock *FalseDest = BI.getSuccessor(1); + // Swap Destinations and condition... + BI.setCondition(V); + BI.setSuccessor(0, FalseDest); + BI.setSuccessor(1, TrueDest); + return &BI; + } + return 0; +} void InstCombiner::removeFromWorkList(Instruction *I) { @@ -1071,17 +1976,16 @@ bool InstCombiner::runOnFunction(Function &F) { // Check to see if we can DIE the instruction... if (isInstructionTriviallyDead(I)) { // Add operands to the worklist... - for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) - if (Instruction *Op = dyn_cast(I->getOperand(i))) - WorkList.push_back(Op); - + if (I->getNumOperands() < 4) + for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) + if (Instruction *Op = dyn_cast(I->getOperand(i))) + WorkList.push_back(Op); ++NumDeadInst; - BasicBlock::iterator BBI = I; - if (dceInstruction(BBI)) { - removeFromWorkList(I); - continue; - } - } + + I->getParent()->getInstList().erase(I); + removeFromWorkList(I); + continue; + } // Instruction isn't dead, see if we can constant propagate it... if (Constant *C = ConstantFoldInstruction(I)) { @@ -1092,13 +1996,11 @@ bool InstCombiner::runOnFunction(Function &F) { ReplaceInstUsesWith(*I, C); ++NumConstProp; - BasicBlock::iterator BBI = I; - if (dceInstruction(BBI)) { - removeFromWorkList(I); - continue; - } + I->getParent()->getInstList().erase(I); + removeFromWorkList(I); + continue; } - + // Now that we have an instruction, try combining it to simplify it... if (Instruction *Result = visit(*I)) { ++NumCombined; @@ -1107,7 +2009,20 @@ bool InstCombiner::runOnFunction(Function &F) { // Instructions can end up on the worklist more than once. Make sure // we do not process an instruction that has been deleted. removeFromWorkList(I); - ReplaceInstWithInst(I, Result); + + // Move the name to the new instruction first... + std::string OldName = I->getName(); I->setName(""); + Result->setName(OldName); + + // Insert the new instruction into the basic block... + BasicBlock *InstParent = I->getParent(); + InstParent->getInstList().insert(I, Result); + + // Everything uses the new instruction now... + I->replaceAllUsesWith(Result); + + // Erase the old instruction. + InstParent->getInstList().erase(I); } else { BasicBlock::iterator II = I;