//===- 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
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Transforms/Utils/BasicBlockUtils.h"
-#include "llvm/Transforms/Utils/Local.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/Target/TargetData.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/CallSite.h"
public InstVisitor<InstCombiner, Instruction*> {
// Worklist of all of the instructions that need to be simplified.
std::vector<Instruction*> WorkList;
+ TargetData *TD;
void AddUsesToWorkList(Instruction &I) {
// The instruction was simplified, add all users of the instruction to
virtual bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<TargetData>();
AU.setPreservesCFG();
}
// 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<Constant>(V);
+ return V->hasOneUse() || isa<Constant>(V);
}
// SimplifyCommutative - This performs a few simplifications for commutative
// 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<Instruction>(V))
if (I->getOpcode() == Instruction::Mul)
if (isa<Constant>(I->getOperand(1)))
// Otherwise, if the LHS is not of the same opcode as the root, return.
Instruction *LHSI = dyn_cast<Instruction>(LHS);
- while (LHSI && LHSI->getOpcode() == Opcode && LHSI->use_size() == 1) {
+ while (LHSI && LHSI->getOpcode() == Opcode && LHSI->hasOneUse()) {
// Should we apply this transform to the RHS?
bool ShouldApply = F.shouldApply(LHSI->getOperand(1));
return BinaryOperator::createNot(Op1);
if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1))
- if (Op1I->use_size() == 1) {
+ if (Op1I->hasOneUse()) {
// Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression
// is not used by anyone else...
//
if ((*AndRHS & *OpRHS)->isNullValue()) {
// (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0
return BinaryOperator::create(Instruction::And, X, AndRHS);
- } else if (Op->use_size() == 1) {
+ } else if (Op->hasOneUse()) {
// (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
std::string OpName = Op->getName(); Op->setName("");
Instruction *And = BinaryOperator::create(Instruction::And,
if (Together == AndRHS) // (X | C) & C --> C
return ReplaceInstUsesWith(TheAnd, AndRHS);
- if (Op->use_size() == 1 && Together != OpRHS) {
+ 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,
}
break;
case Instruction::Add:
- if (Op->use_size() == 1) {
+ 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.
if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
// xor (setcc A, B), true = not (setcc A, B) = setncc A, B
if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0I))
- if (RHS == ConstantBool::True && SCI->use_size() == 1)
+ if (RHS == ConstantBool::True && SCI->hasOneUse())
return new SetCondInst(SCI->getInverseCondition(),
SCI->getOperand(0), SCI->getOperand(1));
+
+ // ~(c-X) == X-(c-1) == X+(-c+1)
+ if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue() &&
+ isa<Constant>(Op0I->getOperand(0))) {
+ Constant *ConstantRHS = *-*cast<Constant>(Op0I->getOperand(0)) +
+ *ConstantInt::get(I.getType(), 1);
+ return BinaryOperator::create(Instruction::Add, Op0I->getOperand(1),
+ ConstantRHS);
+ }
if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
- if (Op0I->getOpcode() == Instruction::And) {
+ switch (Op0I->getOpcode()) {
+ case Instruction::Add:
+ // ~(X-c) --> (-c-1)-X
+ if (RHS->isAllOnesValue())
+ return BinaryOperator::create(Instruction::Sub,
+ *-*Op0CI -
+ *ConstantInt::get(I.getType(), 1),
+ Op0I->getOperand(0));
+ break;
+ case Instruction::And:
// (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0
if ((*RHS & *Op0CI)->isNullValue())
return BinaryOperator::create(Instruction::Or, Op0, RHS);
- } else if (Op0I->getOpcode() == Instruction::Or) {
+ break;
+ case Instruction::Or:
// (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
if ((*RHS & *Op0CI) == RHS)
return BinaryOperator::create(Instruction::And, Op0, ~*RHS);
+ break;
+ default: break;
}
}
}
}
if (Instruction *Op0I = dyn_cast<Instruction>(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<BinaryOperator>(Op0I)->swapOperands();
if (Op0I->getOperand(1) == Op1) { // (A|B)^B == A & ~B
if (Ty == Type::BoolTy) {
// If this is <, >, or !=, we can change this into a simple xor instruction
if (!isTrueWhenEqual(I))
- return BinaryOperator::create(Instruction::Xor, Op0, Op1, I.getName());
+ return BinaryOperator::create(Instruction::Xor, Op0, Op1);
// Otherwise we need to make a temporary intermediate instruction and insert
// it into the instruction stream. This is what we are after:
Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1,
I.getName()+"tmp");
InsertNewInstBefore(Xor, I);
- return BinaryOperator::createNot(Xor, I.getName());
+ return BinaryOperator::createNot(Xor);
}
// Handle the setXe cases...
// Now we just have the SetLE case.
Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
InsertNewInstBefore(Not, I);
- return BinaryOperator::create(Instruction::Or, Not, Op1, I.getName());
+ return BinaryOperator::create(Instruction::Or, Not, Op1);
}
// Check to see if we are doing one of many comparisons against constant
return new SetCondInst(I.getOpcode(), BOp0, NegVal);
else if (Value *NegVal = dyn_castNegVal(BOp0))
return new SetCondInst(I.getOpcode(), NegVal, BOp1);
- else if (BO->use_size() == 1) {
+ else if (BO->hasOneUse()) {
Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName());
BO->setName("");
InsertNewInstBefore(Neg, I);
if (I.getOpcode() == Instruction::SetGE) // A >= MIN -> TRUE
return ReplaceInstUsesWith(I, ConstantBool::True);
if (I.getOpcode() == Instruction::SetLE) // A <= MIN -> A == MIN
- return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
+ return BinaryOperator::create(Instruction::SetEQ, Op0, Op1);
if (I.getOpcode() == Instruction::SetGT) // A > MIN -> A != MIN
- return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
+ return BinaryOperator::create(Instruction::SetNE, Op0, Op1);
} else if (CI->isMaxValue()) {
if (I.getOpcode() == Instruction::SetGT) // A > MAX -> FALSE
if (I.getOpcode() == Instruction::SetLE) // A <= MAX -> TRUE
return ReplaceInstUsesWith(I, ConstantBool::True);
if (I.getOpcode() == Instruction::SetGE) // A >= MAX -> A == MAX
- return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
+ return BinaryOperator::create(Instruction::SetEQ, Op0, Op1);
if (I.getOpcode() == Instruction::SetLT) // A < MAX -> A != MAX
- return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
+ return BinaryOperator::create(Instruction::SetNE, Op0, Op1);
// Comparing against a value really close to min or max?
} else if (isMinValuePlusOne(CI)) {
if (I.getOpcode() == Instruction::SetLT) // A < MIN+1 -> A == MIN
- return BinaryOperator::create(Instruction::SetEQ, Op0,
- SubOne(CI), I.getName());
+ return BinaryOperator::create(Instruction::SetEQ, Op0, SubOne(CI));
if (I.getOpcode() == Instruction::SetGE) // A >= MIN-1 -> A != MIN
- return BinaryOperator::create(Instruction::SetNE, Op0,
- SubOne(CI), I.getName());
+ return BinaryOperator::create(Instruction::SetNE, Op0, SubOne(CI));
} else if (isMaxValueMinusOne(CI)) {
if (I.getOpcode() == Instruction::SetGT) // A > MAX-1 -> A == MAX
- return BinaryOperator::create(Instruction::SetEQ, Op0,
- AddOne(CI), I.getName());
+ return BinaryOperator::create(Instruction::SetEQ, Op0, AddOne(CI));
if (I.getOpcode() == Instruction::SetLE) // A <= MAX-1 -> A != MAX
- return BinaryOperator::create(Instruction::SetNE, Op0,
- AddOne(CI), I.getName());
+ return BinaryOperator::create(Instruction::SetNE, Op0, AddOne(CI));
}
}
+ // Test to see if the operands of the setcc are casted versions of other
+ // values. If the cast can be stripped off both arguments, we do so now.
+ if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
+ Value *CastOp0 = CI->getOperand(0);
+ if (CastOp0->getType()->isLosslesslyConvertibleTo(CI->getType()) &&
+ !isa<Argument>(Op1) &&
+ (I.getOpcode() == Instruction::SetEQ ||
+ I.getOpcode() == Instruction::SetNE)) {
+ // We keep moving the cast from the left operand over to the right
+ // operand, where it can often be eliminated completely.
+ Op0 = CastOp0;
+
+ // If operand #1 is a cast instruction, see if we can eliminate it as
+ // well.
+ if (CastInst *CI2 = dyn_cast<CastInst>(Op1))
+ if (CI2->getOperand(0)->getType()->isLosslesslyConvertibleTo(
+ Op0->getType()))
+ Op1 = CI2->getOperand(0);
+
+ // If Op1 is a constant, we can fold the cast into the constant.
+ if (Op1->getType() != Op0->getType())
+ if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
+ Op1 = ConstantExpr::getCast(Op1C, Op0->getType());
+ } else {
+ // Otherwise, cast the RHS right before the setcc
+ Op1 = new CastInst(Op1, Op0->getType(), Op1->getName());
+ InsertNewInstBefore(cast<Instruction>(Op1), I);
+ }
+ return BinaryOperator::create(I.getOpcode(), Op0, Op1);
+ }
+
+ // Handle the special case of: setcc (cast bool to X), <cst>
+ // This comes up when you have code like
+ // int X = A < B;
+ // if (X) ...
+ // For generality, we handle any zero-extension of any operand comparison
+ // with a constant.
+ if (ConstantInt *ConstantRHS = dyn_cast<ConstantInt>(Op1)) {
+ const Type *SrcTy = CastOp0->getType();
+ const Type *DestTy = Op0->getType();
+ if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() &&
+ (SrcTy->isUnsigned() || SrcTy == Type::BoolTy)) {
+ // Ok, we have an expansion of operand 0 into a new type. Get the
+ // constant value, masink off bits which are not set in the RHS. These
+ // could be set if the destination value is signed.
+ uint64_t ConstVal = ConstantRHS->getRawValue();
+ ConstVal &= (1ULL << DestTy->getPrimitiveSize()*8)-1;
+
+ // If the constant we are comparing it with has high bits set, which
+ // don't exist in the original value, the values could never be equal,
+ // because the source would be zero extended.
+ unsigned SrcBits =
+ SrcTy == Type::BoolTy ? 1 : SrcTy->getPrimitiveSize()*8;
+ bool HasSignBit = 1ULL << (DestTy->getPrimitiveSize()*8-1);
+ if (ConstVal & ((1ULL << SrcBits)-1)) {
+ switch (I.getOpcode()) {
+ default: assert(0 && "Unknown comparison type!");
+ case Instruction::SetEQ:
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ case Instruction::SetNE:
+ return ReplaceInstUsesWith(I, ConstantBool::True);
+ case Instruction::SetLT:
+ case Instruction::SetLE:
+ if (DestTy->isSigned() && HasSignBit)
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ return ReplaceInstUsesWith(I, ConstantBool::True);
+ case Instruction::SetGT:
+ case Instruction::SetGE:
+ if (DestTy->isSigned() && HasSignBit)
+ return ReplaceInstUsesWith(I, ConstantBool::True);
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ }
+ }
+
+ // Otherwise, we can replace the setcc with a setcc of the smaller
+ // operand value.
+ Op1 = ConstantExpr::getCast(cast<Constant>(Op1), SrcTy);
+ return BinaryOperator::create(I.getOpcode(), CastOp0, Op1);
+ }
+ }
+ }
return Changed ? &I : 0;
}
// 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->use_size() == 1)
+ if (Op0->hasOneUse())
if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0))
if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
bool isValid = true; // Valid only for And, Or, Xor
}
}
+ // If we are casting a malloc or alloca to a pointer to a type of the same
+ // size, rewrite the allocation instruction to allocate the "right" type.
+ //
+ if (AllocationInst *AI = dyn_cast<AllocationInst>(Src))
+ if (AI->hasOneUse() && !AI->isArrayAllocation())
+ if (const PointerType *PTy = dyn_cast<PointerType>(CI.getType())) {
+ // Get the type really allocated and the type casted to...
+ const Type *AllocElTy = AI->getAllocatedType();
+ unsigned AllocElTySize = TD->getTypeSize(AllocElTy);
+ const Type *CastElTy = PTy->getElementType();
+ unsigned CastElTySize = TD->getTypeSize(CastElTy);
+
+ // If the allocation is for an even multiple of the cast type size
+ if (CastElTySize && (AllocElTySize % CastElTySize == 0)) {
+ Value *Amt = ConstantUInt::get(Type::UIntTy,
+ AllocElTySize/CastElTySize);
+ std::string Name = AI->getName(); AI->setName("");
+ AllocationInst *New;
+ if (isa<MallocInst>(AI))
+ New = new MallocInst(CastElTy, Amt, Name);
+ else
+ New = new AllocaInst(CastElTy, Amt, Name);
+ InsertNewInstBefore(New, CI);
+ return ReplaceInstUsesWith(CI, New);
+ }
+ }
+
// If the source value is an instruction with only this use, we can attempt to
// propagate the cast into the instruction. Also, only handle integral types
// for now.
if (Instruction *SrcI = dyn_cast<Instruction>(Src))
- if (SrcI->use_size() == 1 && Src->getType()->isIntegral() &&
+ 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());
if (Caller->getType() != NV->getType() && !Caller->use_empty()) {
if (NV->getType() != Type::VoidTy) {
NV = NC = new CastInst(NC, Caller->getType(), "tmp");
- InsertNewInstBefore(NC, *Caller);
+
+ // If this is an invoke instruction, we should insert it after the first
+ // non-phi, instruction in the normal successor block.
+ if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
+ BasicBlock::iterator I = II->getNormalDest()->begin();
+ while (isa<PHINode>(I)) ++I;
+ InsertNewInstBefore(NC, *I);
+ } else {
+ // Otherwise, it's a call, just insert cast right after the call instr
+ InsertNewInstBefore(NC, *Caller);
+ }
AddUsesToWorkList(*Caller);
} else {
NV = Constant::getNullValue(Caller->getType());
bool InstCombiner::runOnFunction(Function &F) {
bool Changed = false;
+ TD = &getAnalysis<TargetData>();
WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F));
// Move the name to the new instruction first...
std::string OldName = I->getName(); I->setName("");
- Result->setName(I->getName());
+ Result->setName(OldName);
// Insert the new instruction into the basic block...
BasicBlock *InstParent = I->getParent();
projects / oota-llvm.git / blobdiff