#include "llvm/GlobalVariable.h"
#include "llvm/Operator.h"
#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/MallocHelper.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Support/IRBuilder.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/PatternMatch.h"
-#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
/// Add - Add the specified instruction to the worklist if it isn't already
/// in it.
void Add(Instruction *I) {
+ DEBUG(errs() << "IC: ADD: " << *I << '\n');
if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second)
Worklist.push_back(I);
}
namespace {
- class VISIBILITY_HIDDEN InstCombiner
- : public FunctionPass,
- public InstVisitor<InstCombiner, Instruction*> {
+ class InstCombiner : public FunctionPass,
+ public InstVisitor<InstCombiner, Instruction*> {
TargetData *TD;
bool MustPreserveLCSSA;
+ bool MadeIRChange;
public:
/// Worklist - All of the instructions that need to be simplified.
InstCombineWorklist Worklist;
Worklist.Add(New);
return New;
}
-
- /// InsertCastBefore - Insert a cast of V to TY before the instruction POS.
- /// This also adds the cast to the worklist. Finally, this returns the
- /// cast.
- Value *InsertCastBefore(Instruction::CastOps opc, Value *V, const Type *Ty,
- Instruction &Pos) {
- if (V->getType() == Ty) return V;
-
- if (Constant *CV = dyn_cast<Constant>(V))
- return ConstantExpr::getCast(opc, CV, Ty);
-
- Instruction *C = CastInst::Create(opc, V, Ty, V->getName(), &Pos);
- Worklist.Add(C);
- return C;
- }
// ReplaceInstUsesWith - This method is to be used when an instruction is
// found to be dead, replacable with another preexisting expression. Here
// instruction. Instead, visit methods should return the value returned by
// this function.
Instruction *EraseInstFromFunction(Instruction &I) {
+ DEBUG(errs() << "IC: ERASE " << I << '\n');
+
assert(I.use_empty() && "Cannot erase instruction that is used!");
// Make sure that we reprocess all operands now that we reduced their
// use counts.
}
Worklist.Remove(&I);
I.eraseFromParent();
+ MadeIRChange = true;
return 0; // Don't do anything with FI
}
Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
APInt& UndefElts, unsigned Depth = 0);
- // FoldOpIntoPhi - Given a binary operator or cast instruction which has a
- // PHI node as operand #0, see if we can fold the instruction into the PHI
- // (which is only possible if all operands to the PHI are constants).
+ // FoldOpIntoPhi - Given a binary operator, cast instruction, or select
+ // which has a PHI node as operand #0, see if we can fold the instruction
+ // into the PHI (which is only possible if all operands to the PHI are
+ // constants).
Instruction *FoldOpIntoPhi(Instruction &I);
// FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary"
// If all of the demanded bits are known to be zero on one side or the
// other, turn this into an *inclusive* or.
// e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
- if ((DemandedMask & ~RHSKnownZero & ~LHSKnownZero) == 0)
- return Builder->CreateOr(I->getOperand(0), I->getOperand(1),I->getName());
+ if ((DemandedMask & ~RHSKnownZero & ~LHSKnownZero) == 0) {
+ Instruction *Or =
+ BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1),
+ I->getName());
+ return InsertNewInstBefore(Or, *I);
+ }
// If all of the demanded bits on one side are known, and all of the set
// bits on that side are also known to be set on the other side, turn this
static Value *FoldOperationIntoSelectOperand(Instruction &I, Value *SO,
InstCombiner *IC) {
if (CastInst *CI = dyn_cast<CastInst>(&I))
- return IC->InsertCastBefore(CI->getOpcode(), SO, I.getType(), I);
+ return IC->Builder->CreateCast(CI->getOpcode(), SO, I.getType());
// Figure out if the constant is the left or the right argument.
bool ConstIsRHS = isa<Constant>(I.getOperand(1));
}
-/// FoldOpIntoPhi - Given a binary operator or cast instruction which has a PHI
-/// node as operand #0, see if we can fold the instruction into the PHI (which
-/// is only possible if all operands to the PHI are constants).
+/// FoldOpIntoPhi - Given a binary operator, cast instruction, or select which
+/// has a PHI node as operand #0, see if we can fold the instruction into the
+/// PHI (which is only possible if all operands to the PHI are constants).
Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
PHINode *PN = cast<PHINode>(I.getOperand(0));
unsigned NumPHIValues = PN->getNumIncomingValues();
if (!PN->hasOneUse() || NumPHIValues == 0) return 0;
- // Check to see if all of the operands of the PHI are constants. If there is
- // one non-constant value, remember the BB it is. If there is more than one
- // or if *it* is a PHI, bail out.
+ // Check to see if all of the operands of the PHI are simple constants
+ // (constantint/constantfp/undef). If there is one non-constant value,
+ // remember the BB it is in. If there is more than one or if *it* is a PHI,
+ // bail out. We don't do arbitrary constant expressions here because moving
+ // their computation can be expensive without a cost model.
BasicBlock *NonConstBB = 0;
for (unsigned i = 0; i != NumPHIValues; ++i)
- if (!isa<Constant>(PN->getIncomingValue(i))) {
+ if (!isa<Constant>(PN->getIncomingValue(i)) ||
+ isa<ConstantExpr>(PN->getIncomingValue(i))) {
if (NonConstBB) return 0; // More than one non-const value.
if (isa<PHINode>(PN->getIncomingValue(i))) return 0; // Itself a phi.
NonConstBB = PN->getIncomingBlock(i);
NewPN->takeName(PN);
// Next, add all of the operands to the PHI.
- if (I.getNumOperands() == 2) {
+ if (SelectInst *SI = dyn_cast<SelectInst>(&I)) {
+ // We only currently try to fold the condition of a select when it is a phi,
+ // not the true/false values.
+ Value *TrueV = SI->getTrueValue();
+ Value *FalseV = SI->getFalseValue();
+ for (unsigned i = 0; i != NumPHIValues; ++i) {
+ BasicBlock *ThisBB = PN->getIncomingBlock(i);
+ Value *TrueVInPred = TrueV->DoPHITranslation(I.getParent(), ThisBB);
+ Value *FalseVInPred = FalseV->DoPHITranslation(I.getParent(), ThisBB);
+ Value *InV = 0;
+ if (Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i))) {
+ InV = InC->isNullValue() ? FalseVInPred : TrueVInPred;
+ } else {
+ assert(PN->getIncomingBlock(i) == NonConstBB);
+ InV = SelectInst::Create(PN->getIncomingValue(i), TrueVInPred,
+ FalseVInPred,
+ "phitmp", NonConstBB->getTerminator());
+ Worklist.Add(cast<Instruction>(InV));
+ }
+ NewPN->addIncoming(InV, ThisBB);
+ }
+ } else if (I.getNumOperands() == 2) {
Constant *C = cast<Constant>(I.getOperand(1));
for (unsigned i = 0; i != NumPHIValues; ++i) {
Value *InV = 0;
// If the multiply type is not the same as the source type, sign extend
// or truncate to the multiply type.
- if (I.getType() != V->getType()) {
- uint32_t SrcBits = V->getType()->getPrimitiveSizeInBits();
- uint32_t DstBits = I.getType()->getPrimitiveSizeInBits();
- Instruction::CastOps opcode =
- (SrcBits == DstBits ? Instruction::BitCast :
- (SrcBits < DstBits ? Instruction::SExt : Instruction::Trunc));
- V = InsertCastBefore(opcode, V, I.getType(), I);
- }
+ if (I.getType() != V->getType())
+ V = Builder->CreateIntCast(V, I.getType(), true);
Value *OtherOp = Op0 == BoolCast ? I.getOperand(1) : Op0;
return BinaryOperator::CreateAnd(V, OtherOp);
// Fold trivial predicates.
if (I.getPredicate() == FCmpInst::FCMP_FALSE)
- return ReplaceInstUsesWith(I, ConstantInt::getFalse(*Context));
+ return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), 0));
if (I.getPredicate() == FCmpInst::FCMP_TRUE)
- return ReplaceInstUsesWith(I, ConstantInt::getTrue(*Context));
+ return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), 1));
// Simplify 'fcmp pred X, X'
if (Op0 == Op1) {
case FCmpInst::FCMP_UEQ: // True if unordered or equal
case FCmpInst::FCMP_UGE: // True if unordered, greater than, or equal
case FCmpInst::FCMP_ULE: // True if unordered, less than, or equal
- return ReplaceInstUsesWith(I, ConstantInt::getTrue(*Context));
+ return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), 1));
case FCmpInst::FCMP_OGT: // True if ordered and greater than
case FCmpInst::FCMP_OLT: // True if ordered and less than
case FCmpInst::FCMP_ONE: // True if ordered and operands are unequal
- return ReplaceInstUsesWith(I, ConstantInt::getFalse(*Context));
+ return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), 0));
case FCmpInst::FCMP_UNO: // True if unordered: isnan(X) | isnan(Y)
case FCmpInst::FCMP_ULT: // True if unordered or less than
}
if (isa<UndefValue>(Op1)) // fcmp pred X, undef -> undef
- return ReplaceInstUsesWith(I, UndefValue::get(Type::getInt1Ty(*Context)));
+ return ReplaceInstUsesWith(I, UndefValue::get(I.getType()));
// Handle fcmp with constant RHS
if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
// icmp X, X
if (Op0 == Op1)
- return ReplaceInstUsesWith(I, ConstantInt::get(Type::getInt1Ty(*Context),
+ return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(),
I.isTrueWhenEqual()));
if (isa<UndefValue>(Op1)) // X icmp undef -> undef
- return ReplaceInstUsesWith(I, UndefValue::get(Type::getInt1Ty(*Context)));
+ return ReplaceInstUsesWith(I, UndefValue::get(I.getType()));
// icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
// addresses never equal each other! We already know that Op0 != Op1.
- if ((isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0) ||
+ if ((isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0) || isMalloc(Op0) ||
isa<ConstantPointerNull>(Op0)) &&
- (isa<GlobalValue>(Op1) || isa<AllocaInst>(Op1) ||
+ (isa<GlobalValue>(Op1) || isa<AllocaInst>(Op1) || isMalloc(Op1) ||
isa<ConstantPointerNull>(Op1)))
return ReplaceInstUsesWith(I, ConstantInt::get(Type::getInt1Ty(*Context),
!I.isTrueWhenEqual()));
// can assume it is successful and remove the malloc.
if (LHSI->hasOneUse() && isa<ConstantPointerNull>(RHSC)) {
Worklist.Add(LHSI);
- return ReplaceInstUsesWith(I, ConstantInt::get(Type::getInt1Ty(*Context),
- !I.isTrueWhenEqual()));
+ return ReplaceInstUsesWith(I,
+ ConstantInt::get(Type::getInt1Ty(*Context),
+ !I.isTrueWhenEqual()));
+ }
+ break;
+ case Instruction::Call:
+ // If we have (malloc != null), and if the malloc has a single use, we
+ // can assume it is successful and remove the malloc.
+ if (isMalloc(LHSI) && LHSI->hasOneUse() &&
+ isa<ConstantPointerNull>(RHSC)) {
+ Worklist.Add(LHSI);
+ return ReplaceInstUsesWith(I,
+ ConstantInt::get(Type::getInt1Ty(*Context),
+ !I.isTrueWhenEqual()));
+ }
+ break;
+ case Instruction::BitCast:
+ // If we have (malloc != null), and if the malloc has a single use, we
+ // can assume it is successful and remove the malloc.
+ CallInst* CI = extractMallocCallFromBitCast(LHSI);
+ if (CI && CI->hasOneUse() && LHSI->hasOneUse()
+ && isa<ConstantPointerNull>(RHSC)) {
+ Worklist.Add(LHSI);
+ Worklist.Add(CI);
+ return ReplaceInstUsesWith(I,
+ ConstantInt::get(Type::getInt1Ty(*Context),
+ !I.isTrueWhenEqual()));
}
break;
}
// If we were able to index down into an element, create the GEP
// and bitcast the result. This eliminates one bitcast, potentially
// two.
- Value *NGEP = Builder->CreateGEP(OrigBase, NewIndices.begin(),
- NewIndices.end());
+ Value *NGEP = cast<GEPOperator>(GEP)->isInBounds() ?
+ Builder->CreateInBoundsGEP(OrigBase,
+ NewIndices.begin(), NewIndices.end()) :
+ Builder->CreateGEP(OrigBase, NewIndices.begin(), NewIndices.end());
NGEP->takeName(GEP);
- if (isa<Instruction>(NGEP) && cast<GEPOperator>(GEP)->isInBounds())
- cast<GEPOperator>(NGEP)->setIsInBounds(true);
if (isa<BitCastInst>(CI))
return new BitCastInst(NGEP, CI.getType());
return ReplaceInstUsesWith(CI, Res);
// We need to emit a cast to truncate, then a cast to sext.
- return CastInst::Create(Instruction::SExt,
- InsertCastBefore(Instruction::Trunc, Res, Src->getType(),
- CI), DestTy);
+ return new SExtInst(Builder->CreateTrunc(Res, Src->getType()), DestTy);
}
}
}
// Don't insert two casts unless at least one can be eliminated.
if (!ValueRequiresCast(CI.getOpcode(), Op1, DestTy, TD) ||
!ValueRequiresCast(CI.getOpcode(), Op0, DestTy, TD)) {
- Value *Op0c = InsertCastBefore(Instruction::Trunc, Op0, DestTy, *SrcI);
- Value *Op1c = InsertCastBefore(Instruction::Trunc, Op1, DestTy, *SrcI);
+ Value *Op0c = Builder->CreateTrunc(Op0, DestTy, Op0->getName());
+ Value *Op1c = Builder->CreateTrunc(Op1, DestTy, Op1->getName());
return BinaryOperator::Create(
cast<BinaryOperator>(SrcI)->getOpcode(), Op0c, Op1c);
}
SrcI->getOpcode() == Instruction::Xor &&
Op1 == ConstantInt::getTrue(*Context) &&
(!Op0->hasOneUse() || !isa<CmpInst>(Op0))) {
- Value *New = InsertCastBefore(Instruction::ZExt, Op0, DestTy, CI);
+ Value *New = Builder->CreateZExt(Op0, DestTy, Op0->getName());
return BinaryOperator::CreateXor(New,
ConstantInt::get(CI.getType(), 1));
}
ConstantInt *CI = dyn_cast<ConstantInt>(Op1);
if (CI && DestBitSize < SrcBitSize &&
CI->getLimitedValue(DestBitSize) < DestBitSize) {
- Value *Op0c = InsertCastBefore(Instruction::Trunc, Op0, DestTy, *SrcI);
- Value *Op1c = InsertCastBefore(Instruction::Trunc, Op1, DestTy, *SrcI);
+ Value *Op0c = Builder->CreateTrunc(Op0, DestTy, Op0->getName());
+ Value *Op1c = Builder->CreateTrunc(Op1, DestTy, Op1->getName());
return BinaryOperator::CreateShl(Op0c, Op1c);
}
break;
// Okay, we can shrink this. Truncate the input, then return a new
// shift.
- Value *V1 = InsertCastBefore(Instruction::Trunc, ShiftOp, Ty, CI);
+ Value *V1 = Builder->CreateTrunc(ShiftOp, Ty, ShiftOp->getName());
Value *V2 = ConstantExpr::getTrunc(ShAmtV, Ty);
return BinaryOperator::CreateLShr(V1, V2);
}
if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() &&
(transformZExtICmp(LHS, CI, false) ||
transformZExtICmp(RHS, CI, false))) {
- Value *LCast = InsertCastBefore(Instruction::ZExt, LHS, CI.getType(), CI);
- Value *RCast = InsertCastBefore(Instruction::ZExt, RHS, CI.getType(), CI);
+ Value *LCast = Builder->CreateZExt(LHS, CI.getType(), LHS->getName());
+ Value *RCast = Builder->CreateZExt(RHS, CI.getType(), RHS->getName());
return BinaryOperator::Create(Instruction::Or, LCast, RCast);
}
}
// the cast, do this xform.
if (LHSTrunc->getType()->getScalarSizeInBits() <= DstSize &&
RHSTrunc->getType()->getScalarSizeInBits() <= DstSize) {
- LHSTrunc = InsertCastBefore(Instruction::FPExt, LHSTrunc,
- CI.getType(), CI);
- RHSTrunc = InsertCastBefore(Instruction::FPExt, RHSTrunc,
- CI.getType(), CI);
+ LHSTrunc = Builder->CreateFPExt(LHSTrunc, CI.getType());
+ RHSTrunc = Builder->CreateFPExt(RHSTrunc, CI.getType());
return BinaryOperator::Create(OpI->getOpcode(), LHSTrunc, RHSTrunc);
}
}
if (SrcPTy->getAddressSpace() != DstPTy->getAddressSpace())
return 0;
- // If we are casting a malloc or alloca to a pointer to a type of the same
+ // If we are casting a alloca to a pointer to a type of the same
// size, rewrite the allocation instruction to allocate the "right" type.
+ // There is no need to modify malloc calls because it is their bitcast that
+ // needs to be cleaned up.
if (AllocationInst *AI = dyn_cast<AllocationInst>(Src))
if (Instruction *V = PromoteCastOfAllocation(CI, *AI))
return V;
// If we found a path from the src to dest, create the getelementptr now.
if (SrcElTy == DstElTy) {
SmallVector<Value*, 8> Idxs(NumZeros+1, ZeroUInt);
- Instruction *GEP = GetElementPtrInst::Create(Src,
- Idxs.begin(), Idxs.end(), "",
- ((Instruction*) NULL));
- cast<GEPOperator>(GEP)->setIsInBounds(true);
- return GEP;
+ return GetElementPtrInst::CreateInBounds(Src, Idxs.begin(), Idxs.end(), "",
+ ((Instruction*) NULL));
}
}
if (const VectorType *DestVTy = dyn_cast<VectorType>(DestTy)) {
if (DestVTy->getNumElements() == 1) {
if (!isa<VectorType>(SrcTy)) {
- Value *Elem = InsertCastBefore(Instruction::BitCast, Src,
- DestVTy->getElementType(), CI);
+ Value *Elem = Builder->CreateBitCast(Src, DestVTy->getElementType());
return InsertElementInst::Create(UndefValue::get(DestTy), Elem,
- Constant::getNullValue(Type::getInt32Ty(*Context)));
+ Constant::getNullValue(Type::getInt32Ty(*Context)));
}
// FIXME: Canonicalize bitcast(insertelement) -> insertelement(bitcast)
}
Tmp->getOperand(0)->getType() == DestTy) ||
((Tmp = dyn_cast<CastInst>(SVI->getOperand(1))) &&
Tmp->getOperand(0)->getType() == DestTy)) {
- Value *LHS = InsertCastBefore(Instruction::BitCast,
- SVI->getOperand(0), DestTy, CI);
- Value *RHS = InsertCastBefore(Instruction::BitCast,
- SVI->getOperand(1), DestTy, CI);
+ Value *LHS = Builder->CreateBitCast(SVI->getOperand(0), DestTy);
+ Value *RHS = Builder->CreateBitCast(SVI->getOperand(1), DestTy);
// Return a new shuffle vector. Use the same element ID's, as we
// know the vector types match #elts.
return new ShuffleVectorInst(LHS, RHS, SVI->getOperand(2));
return Changed ? &SI : 0;
}
+/// isDefinedInBB - Return true if the value is an instruction defined in the
+/// specified basicblock.
+static bool isDefinedInBB(const Value *V, const BasicBlock *BB) {
+ const Instruction *I = dyn_cast<Instruction>(V);
+ return I != 0 && I->getParent() == BB;
+}
+
+
Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
Value *CondVal = SI.getCondition();
Value *TrueVal = SI.getTrueValue();
return FoldI;
}
+ // See if we can fold the select into a phi node. The true/false values have
+ // to be live in the predecessor blocks. If they are instructions in SI's
+ // block, we can't map to the predecessor.
+ if (isa<PHINode>(SI.getCondition()) &&
+ (!isDefinedInBB(SI.getTrueValue(), SI.getParent()) ||
+ isa<PHINode>(SI.getTrueValue())) &&
+ (!isDefinedInBB(SI.getFalseValue(), SI.getParent()) ||
+ isa<PHINode>(SI.getFalseValue())))
+ if (Instruction *NV = FoldOpIntoPhi(SI))
+ return NV;
+
if (BinaryOperator::isNot(CondVal)) {
SI.setOperand(0, BinaryOperator::getNotArgument(CondVal));
SI.setOperand(1, FalseVal);
Align = PrefAlign;
}
}
+ // No alignment changes are possible for malloc calls
}
return Align;
TerminatorInst *TI = II->getParent()->getTerminator();
bool CannotRemove = false;
for (++BI; &*BI != TI; ++BI) {
- if (isa<AllocaInst>(BI)) {
+ if (isa<AllocaInst>(BI) || isMalloc(BI)) {
CannotRemove = true;
break;
}
}
}
- if (Caller->getType() != Type::getVoidTy(*Context) && !Caller->use_empty())
+
+ if (!Caller->use_empty())
Caller->replaceAllUsesWith(NV);
- Caller->eraseFromParent();
- Worklist.Remove(Caller);
+
+ EraseInstFromFunction(*Caller);
return true;
}
return CS.getInstruction();
}
-/// FoldPHIArgBinOpIntoPHI - If we have something like phi [add (a,b), add(c,d)]
-/// and if a/b/c/d and the add's all have a single use, turn this into two phi's
+/// FoldPHIArgBinOpIntoPHI - If we have something like phi [add (a,b), add(a,c)]
+/// and if a/b/c and the add's all have a single use, turn this into a phi
/// and a single binop.
Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) {
Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
const Type *LHSType = LHSVal->getType();
const Type *RHSType = RHSVal->getType();
- // Scan to see if all operands are the same opcode, all have one use, and all
- // kill their operands (i.e. the operands have one use).
+ // Scan to see if all operands are the same opcode, and all have one use.
for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
Instruction *I = dyn_cast<Instruction>(PN.getIncomingValue(i));
if (!I || I->getOpcode() != Opc || !I->hasOneUse() ||
if (I->getOperand(0) != LHSVal) LHSVal = 0;
if (I->getOperand(1) != RHSVal) RHSVal = 0;
}
+
+ // If both LHS and RHS would need a PHI, don't do this transformation,
+ // because it would increase the number of PHIs entering the block,
+ // which leads to higher register pressure. This is especially
+ // bad when the PHIs are in the header of a loop.
+ if (!LHSVal && !RHSVal)
+ return 0;
// Otherwise, this is safe to transform!
// This is true if all GEP bases are allocas and if all indices into them are
// constants.
bool AllBasePointersAreAllocas = true;
+
+ // We don't want to replace this phi if the replacement would require
+ // more than one phi, which leads to higher register pressure. This is
+ // especially bad when the PHIs are in the header of a loop.
+ bool NeededPhi = false;
- // Scan to see if all operands are the same opcode, all have one use, and all
- // kill their operands (i.e. the operands have one use).
+ // Scan to see if all operands are the same opcode, and all have one use.
for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
GetElementPtrInst *GEP= dyn_cast<GetElementPtrInst>(PN.getIncomingValue(i));
if (!GEP || !GEP->hasOneUse() || GEP->getType() != FirstInst->getType() ||
if (FirstInst->getOperand(op)->getType() !=GEP->getOperand(op)->getType())
return 0;
+
+ // If we already needed a PHI for an earlier operand, and another operand
+ // also requires a PHI, we'd be introducing more PHIs than we're
+ // eliminating, which increases register pressure on entry to the PHI's
+ // block.
+ if (NeededPhi)
+ return 0;
+
FixedOperands[op] = 0; // Needs a PHI.
+ NeededPhi = true;
}
}
}
Value *Base = FixedOperands[0];
- GetElementPtrInst *GEP =
+ return cast<GEPOperator>(FirstInst)->isInBounds() ?
+ GetElementPtrInst::CreateInBounds(Base, FixedOperands.begin()+1,
+ FixedOperands.end()) :
GetElementPtrInst::Create(Base, FixedOperands.begin()+1,
FixedOperands.end());
- if (cast<GEPOperator>(FirstInst)->isInBounds())
- cast<GEPOperator>(GEP)->setIsInBounds(true);
- return GEP;
}
Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
Value *PtrOp = GEP.getOperand(0);
- // Is it 'getelementptr %P, i32 0' or 'getelementptr %P'
- // If so, eliminate the noop.
+ // Eliminate 'getelementptr %P, i32 0' and 'getelementptr %P', they are noops.
if (GEP.getNumOperands() == 1)
return ReplaceInstUsesWith(GEP, PtrOp);
// to what we need. If narrower, sign-extend it to what we need. This
// explicit cast can make subsequent optimizations more obvious.
unsigned OpBits = cast<IntegerType>((*I)->getType())->getBitWidth();
-
if (OpBits == PtrSize)
continue;
- Instruction::CastOps Opc =
- OpBits > PtrSize ? Instruction::Trunc : Instruction::SExt;
- *I = InsertCastBefore(Opc, *I, TD->getIntPtrType(GEP.getContext()), GEP);
+ *I = Builder->CreateIntCast(*I, TD->getIntPtrType(GEP.getContext()),true);
MadeChange = true;
}
if (MadeChange) return &GEP;
Indices.append(GEP.idx_begin()+1, GEP.idx_end());
}
- if (!Indices.empty()) {
- GetElementPtrInst *NewGEP =
+ if (!Indices.empty())
+ return (cast<GEPOperator>(&GEP)->isInBounds() &&
+ Src->isInBounds()) ?
+ GetElementPtrInst::CreateInBounds(Src->getOperand(0), Indices.begin(),
+ Indices.end(), GEP.getName()) :
GetElementPtrInst::Create(Src->getOperand(0), Indices.begin(),
Indices.end(), GEP.getName());
- if (cast<GEPOperator>(&GEP)->isInBounds() && Src->isInBounds())
- cast<GEPOperator>(NewGEP)->setIsInBounds(true);
- return NewGEP;
- }
}
// Handle gep(bitcast x) and gep(gep x, 0, 0, 0).
if (Value *X = getBitCastOperand(PtrOp)) {
assert(isa<PointerType>(X->getType()) && "Must be cast from pointer");
-
+
+ // If the input bitcast is actually "bitcast(bitcast(x))", then we don't
+ // want to change the gep until the bitcasts are eliminated.
+ if (getBitCastOperand(X)) {
+ Worklist.AddValue(PtrOp);
+ return 0;
+ }
+
+ // Transform: GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ...
+ // into : GEP [10 x i8]* X, i32 0, ...
+ //
+ // Likewise, transform: GEP (bitcast i8* X to [0 x i8]*), i32 0, ...
+ // into : GEP i8* X, ...
+ //
+ // This occurs when the program declares an array extern like "int X[];"
if (HasZeroPointerIndex) {
- // transform: GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ...
- // into : GEP [10 x i8]* X, i32 0, ...
- //
- // Likewise, transform: GEP (bitcast i8* X to [0 x i8]*), i32 0, ...
- // into : GEP i8* X, ...
- //
- // This occurs when the program declares an array extern like "int X[];"
const PointerType *CPTy = cast<PointerType>(PtrOp->getType());
const PointerType *XTy = cast<PointerType>(X->getType());
if (const ArrayType *CATy =
if (CATy->getElementType() == XTy->getElementType()) {
// -> GEP i8* X, ...
SmallVector<Value*, 8> Indices(GEP.idx_begin()+1, GEP.idx_end());
- GetElementPtrInst *NewGEP =
+ return cast<GEPOperator>(&GEP)->isInBounds() ?
+ GetElementPtrInst::CreateInBounds(X, Indices.begin(), Indices.end(),
+ GEP.getName()) :
GetElementPtrInst::Create(X, Indices.begin(), Indices.end(),
GEP.getName());
- if (cast<GEPOperator>(&GEP)->isInBounds())
- cast<GEPOperator>(NewGEP)->setIsInBounds(true);
- return NewGEP;
- } else if (const ArrayType *XATy =
- dyn_cast<ArrayType>(XTy->getElementType())) {
+ }
+
+ if (const ArrayType *XATy = dyn_cast<ArrayType>(XTy->getElementType())){
// GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ... ?
if (CATy->getElementType() == XATy->getElementType()) {
// -> GEP [10 x i8]* X, i32 0, ...
Value *Idx[2];
Idx[0] = Constant::getNullValue(Type::getInt32Ty(*Context));
Idx[1] = GEP.getOperand(1);
- Value *NewGEP =
+ Value *NewGEP = cast<GEPOperator>(&GEP)->isInBounds() ?
+ Builder->CreateInBoundsGEP(X, Idx, Idx + 2, GEP.getName()) :
Builder->CreateGEP(X, Idx, Idx + 2, GEP.getName());
- if (cast<GEPOperator>(&GEP)->isInBounds())
- cast<GEPOperator>(NewGEP)->setIsInBounds(true);
// V and GEP are both pointer types --> BitCast
return new BitCastInst(NewGEP, GEP.getType());
}
Value *Idx[2];
Idx[0] = Constant::getNullValue(Type::getInt32Ty(*Context));
Idx[1] = NewIdx;
- Value *NewGEP = Builder->CreateGEP(X, Idx, Idx + 2, GEP.getName());
- if (cast<GEPOperator>(&GEP)->isInBounds())
- cast<GEPOperator>(NewGEP)->setIsInBounds(true);
+ Value *NewGEP = cast<GEPOperator>(&GEP)->isInBounds() ?
+ Builder->CreateInBoundsGEP(X, Idx, Idx + 2, GEP.getName()) :
+ Builder->CreateGEP(X, Idx, Idx + 2, GEP.getName());
// The NewGEP must be pointer typed, so must the old one -> BitCast
return new BitCastInst(NewGEP, GEP.getType());
}
if (Offset == 0) {
// If the bitcast is of an allocation, and the allocation will be
// converted to match the type of the cast, don't touch this.
- if (isa<AllocationInst>(BCI->getOperand(0))) {
+ if (isa<AllocationInst>(BCI->getOperand(0)) ||
+ isMalloc(BCI->getOperand(0))) {
// See if the bitcast simplifies, if so, don't nuke this GEP yet.
if (Instruction *I = visitBitCast(*BCI)) {
if (I != BCI) {
const Type *InTy =
cast<PointerType>(BCI->getOperand(0)->getType())->getElementType();
if (FindElementAtOffset(InTy, Offset, NewIndices, TD, Context)) {
- Value *NGEP = Builder->CreateGEP(BCI->getOperand(0), NewIndices.begin(),
- NewIndices.end());
- if (cast<GEPOperator>(&GEP)->isInBounds())
- cast<GEPOperator>(NGEP)->setIsInBounds(true);
+ Value *NGEP = cast<GEPOperator>(&GEP)->isInBounds() ?
+ Builder->CreateInBoundsGEP(BCI->getOperand(0), NewIndices.begin(),
+ NewIndices.end()) :
+ Builder->CreateGEP(BCI->getOperand(0), NewIndices.begin(),
+ NewIndices.end());
if (NGEP->getType() == GEP.getType())
return ReplaceInstUsesWith(GEP, NGEP);
Value *Idx[2];
Idx[0] = NullIdx;
Idx[1] = NullIdx;
- Value *V = GetElementPtrInst::Create(New, Idx, Idx + 2,
- New->getName()+".sub", It);
- cast<GEPOperator>(V)->setIsInBounds(true);
+ Value *V = GetElementPtrInst::CreateInBounds(New, Idx, Idx + 2,
+ New->getName()+".sub", It);
// Now make everything use the getelementptr instead of the original
// allocation.
EraseInstFromFunction(FI);
return EraseInstFromFunction(*MI);
}
+ if (isMalloc(Op)) {
+ if (CallInst* CI = extractMallocCallFromBitCast(Op)) {
+ if (Op->hasOneUse() && CI->hasOneUse()) {
+ EraseInstFromFunction(FI);
+ EraseInstFromFunction(*CI);
+ return EraseInstFromFunction(*cast<Instruction>(Op));
+ }
+ } else {
+ // Op is a call to malloc
+ if (Op->hasOneUse()) {
+ EraseInstFromFunction(FI);
+ return EraseInstFromFunction(*cast<Instruction>(Op));
+ }
+ }
+ }
return 0;
}
LI.setAlignment(KnownAlign);
}
- // load (cast X) --> cast (load X) iff safe
+ // load (cast X) --> cast (load X) iff safe.
if (isa<CastInst>(Op))
if (Instruction *Res = InstCombineLoadCast(*this, LI, TD))
return Res;
if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Op)) {
const Value *GEPI0 = GEPI->getOperand(0);
// TODO: Consider a target hook for valid address spaces for this xform.
- if (isa<ConstantPointerNull>(GEPI0) &&
- cast<PointerType>(GEPI0->getType())->getAddressSpace() == 0) {
+ if (isa<ConstantPointerNull>(GEPI0) && GEPI->getPointerAddressSpace() == 0){
// Insert a new store to null instruction before the load to indicate
// that this code is not reachable. We do this instead of inserting
// an unreachable instruction directly because we cannot modify the
if (Constant *C = dyn_cast<Constant>(Op)) {
// load null/undef -> undef
// TODO: Consider a target hook for valid address spaces for this xform.
- if (isa<UndefValue>(C) || (C->isNullValue() &&
- cast<PointerType>(Op->getType())->getAddressSpace() == 0)) {
+ if (isa<UndefValue>(C) ||
+ (C->isNullValue() && LI.getPointerAddressSpace() == 0)) {
// Insert a new store to null instruction before the load to indicate that
// this code is not reachable. We do this instead of inserting an
// unreachable instruction directly because we cannot modify the CFG.
// SIOp0 is a pointer to aggregate and this is a store to the first field,
// emit a GEP to index into its first field.
- if (!NewGEPIndices.empty()) {
- CastOp = IC.Builder->CreateGEP(CastOp, NewGEPIndices.begin(),
- NewGEPIndices.end());
- cast<GEPOperator>(CastOp)->setIsInBounds(true);
- }
+ if (!NewGEPIndices.empty())
+ CastOp = IC.Builder->CreateInBoundsGEP(CastOp, NewGEPIndices.begin(),
+ NewGEPIndices.end());
NewCast = IC.Builder->CreateCast(opcode, SIOp0, CastDstTy,
SIOp0->getName()+".c");
if (SI.isVolatile()) return 0; // Don't hack volatile stores.
// store X, null -> turns into 'unreachable' in SimplifyCFG
- if (isa<ConstantPointerNull>(Ptr) &&
- cast<PointerType>(Ptr->getType())->getAddressSpace() == 0) {
+ if (isa<ConstantPointerNull>(Ptr) && SI.getPointerAddressSpace() == 0) {
if (!isa<UndefValue>(Val)) {
SI.setOperand(0, UndefValue::get(Val->getType()));
if (Instruction *U = dyn_cast<Instruction>(Val))
// that element. When the elements are not identical, we cannot replace yet
// (we do that below, but only when the index is constant).
Constant *op0 = C->getOperand(0);
- for (unsigned i = 1; i < C->getNumOperands(); ++i)
+ for (unsigned i = 1; i != C->getNumOperands(); ++i)
if (C->getOperand(i) != op0) {
op0 = 0;
break;
// find a previously computed scalar that was inserted into the vector.
if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) {
unsigned IndexVal = IdxC->getZExtValue();
- unsigned VectorWidth =
- cast<VectorType>(EI.getOperand(0)->getType())->getNumElements();
+ unsigned VectorWidth = EI.getVectorOperandType()->getNumElements();
// If this is extracting an invalid index, turn this into undef, to avoid
// crashing the code below.
}
if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) {
- if (I->hasOneUse()) {
- // Push extractelement into predecessor operation if legal and
- // profitable to do so
- if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
- bool isConstantElt = isa<ConstantInt>(EI.getOperand(1));
- if (CheapToScalarize(BO, isConstantElt)) {
- Value *newEI0 =
- Builder->CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
- EI.getName()+".lhs");
- Value *newEI1 =
- Builder->CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
- EI.getName()+".rhs");
- return BinaryOperator::Create(BO->getOpcode(), newEI0, newEI1);
- }
- } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
- unsigned AS = LI->getPointerAddressSpace();
- Value *Ptr = Builder->CreateBitCast(I->getOperand(0),
- PointerType::get(EI.getType(), AS),
- I->getOperand(0)->getName());
- Value *GEP =
- Builder->CreateGEP(Ptr, EI.getOperand(1), I->getName()+".gep");
- cast<GEPOperator>(GEP)->setIsInBounds(true);
-
- LoadInst *Load = Builder->CreateLoad(GEP, "tmp");
-
- // Make sure the Load goes before the load instruction in the source,
- // not wherever the extract happens to be.
- if (Instruction *P = dyn_cast<Instruction>(Ptr))
- P->moveBefore(I);
- if (Instruction *G = dyn_cast<Instruction>(GEP))
- G->moveBefore(I);
- Load->moveBefore(I);
-
- return ReplaceInstUsesWith(EI, Load);
- }
- }
- if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
+ // Push extractelement into predecessor operation if legal and
+ // profitable to do so
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
+ if (I->hasOneUse() &&
+ CheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) {
+ Value *newEI0 =
+ Builder->CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
+ EI.getName()+".lhs");
+ Value *newEI1 =
+ Builder->CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
+ EI.getName()+".rhs");
+ return BinaryOperator::Create(BO->getOpcode(), newEI0, newEI1);
+ }
+ } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
// Extracting the inserted element?
if (IE->getOperand(2) == EI.getOperand(1))
return ReplaceInstUsesWith(EI, IE->getOperand(1));
}
bool InstCombiner::DoOneIteration(Function &F, unsigned Iteration) {
- bool Changed = false;
+ MadeIRChange = false;
TD = getAnalysisIfAvailable<TargetData>();
DEBUG(errs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "
// going to do one without it.
if (!isa<DbgInfoIntrinsic>(I)) {
++NumDeadInst;
- Changed = true;
+ MadeIRChange = true;
}
if (!I->use_empty())
I->replaceAllUsesWith(UndefValue::get(I->getType()));
DEBUG(errs() << "IC: DCE: " << *I << '\n');
EraseInstFromFunction(*I);
++NumDeadInst;
- Changed = true;
+ MadeIRChange = true;
continue;
}
ReplaceInstUsesWith(*I, C);
++NumConstProp;
EraseInstFromFunction(*I);
- Changed = true;
+ MadeIRChange = true;
continue;
}
F.getContext(), TD))
if (NewC != CE) {
i->set(NewC);
- Changed = true;
+ MadeIRChange = true;
}
}
if (UserIsSuccessor && !isa<PHINode>(I->use_back()) &&
next(pred_begin(UserParent)) == pred_end(UserParent))
// Okay, the CFG is simple enough, try to sink this instruction.
- Changed |= TryToSinkInstruction(I, UserParent);
+ MadeIRChange |= TryToSinkInstruction(I, UserParent);
}
}
Worklist.AddUsersToWorkList(*I);
}
}
- Changed = true;
+ MadeIRChange = true;
}
}
Worklist.Zap();
- return Changed;
+ return MadeIRChange;
}
projects / oota-llvm.git / blobdiff