#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
+#include "llvm/LLVMContext.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
/// Constant Propagation.
///
class SCCPSolver : public InstVisitor<SCCPSolver> {
- SmallSet<BasicBlock*, 16> BBExecutable;// The basic blocks that are executable
- DenseMap<Value*, LatticeVal> ValueState; // The state each value is in.
+ LLVMContext* Context;
+ DenseSet<BasicBlock*> BBExecutable;// The basic blocks that are executable
+ std::map<Value*, LatticeVal> ValueState; // The state each value is in.
/// GlobalValue - If we are tracking any values for the contents of a global
/// variable, we keep a mapping from the constant accessor to the element of
/// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
/// that return multiple values.
- std::map<std::pair<Function*, unsigned>, LatticeVal> TrackedMultipleRetVals;
+ DenseMap<std::pair<Function*, unsigned>, LatticeVal> TrackedMultipleRetVals;
// The reason for two worklists is that overdefined is the lowest state
// on the lattice, and moving things to overdefined as fast as possible
// By having a separate worklist, we accomplish this because everything
// possibly overdefined will become overdefined at the soonest possible
// point.
- std::vector<Value*> OverdefinedInstWorkList;
- std::vector<Value*> InstWorkList;
+ SmallVector<Value*, 64> OverdefinedInstWorkList;
+ SmallVector<Value*, 64> InstWorkList;
- std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list
+ SmallVector<BasicBlock*, 64> BBWorkList; // The BasicBlock work list
/// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not
/// overdefined, despite the fact that the PHI node is overdefined.
/// KnownFeasibleEdges - Entries in this set are edges which have already had
/// PHI nodes retriggered.
- typedef std::pair<BasicBlock*,BasicBlock*> Edge;
- std::set<Edge> KnownFeasibleEdges;
+ typedef std::pair<BasicBlock*, BasicBlock*> Edge;
+ DenseSet<Edge> KnownFeasibleEdges;
public:
+ void setContext(LLVMContext* C) { Context = C; }
/// MarkBlockExecutable - This method can be used by clients to mark all of
/// the blocks that are known to be intrinsically live in the processed unit.
/// and out of the specified function (which cannot have its address taken),
/// this method must be called.
void AddTrackedFunction(Function *F) {
- assert(F->hasInternalLinkage() && "Can only track internal functions!");
+ assert(F->hasLocalLinkage() && "Can only track internal functions!");
// Add an entry, F -> undef.
if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) {
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
/// should be rerun.
bool ResolvedUndefsIn(Function &F);
- /// getExecutableBlocks - Once we have solved for constants, return the set of
- /// blocks that is known to be executable.
- SmallSet<BasicBlock*, 16> &getExecutableBlocks() {
- return BBExecutable;
+ bool isBlockExecutable(BasicBlock *BB) const {
+ return BBExecutable.count(BB);
}
/// getValueMapping - Once we have solved for constants, return the mapping of
/// LLVM values to LatticeVals.
- DenseMap<Value*, LatticeVal> &getValueMapping() {
+ std::map<Value*, LatticeVal> &getValueMapping() {
return ValueState;
}
// Instruction object, then use this accessor to get its value from the map.
//
inline LatticeVal &getValueState(Value *V) {
- DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V);
+ std::map<Value*, LatticeVal>::iterator I = ValueState.find(V);
if (I != ValueState.end()) return I->second; // Common case, in the map
if (Constant *C = dyn_cast<Constant>(V)) {
Succs[0] = Succs[1] = true;
} else if (BCValue.isConstant()) {
// Constant condition variables mean the branch can only go a single way
- Succs[BCValue.getConstant() == ConstantInt::getFalse()] = true;
+ Succs[BCValue.getConstant() == Context->getConstantIntFalse()] = true;
}
}
} else if (isa<InvokeInst>(&TI)) {
// Constant condition variables mean the branch can only go a single way
return BI->getSuccessor(BCValue.getConstant() ==
- ConstantInt::getFalse()) == To;
+ Context->getConstantIntFalse()) == To;
}
return false;
}
if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) {
if (IV.isOverdefined()) { // PHI node becomes overdefined!
- markOverdefined(PNIV, &PN);
+ markOverdefined(&PN);
return;
}
// Yes there is. This means the PHI node is not constant.
// You must be overdefined poor PHI.
//
- markOverdefined(PNIV, &PN); // The PHI node now becomes overdefined
+ markOverdefined(&PN); // The PHI node now becomes overdefined
return; // I'm done analyzing you
}
}
// this is the case, the PHI remains undefined.
//
if (OperandVal)
- markConstant(PNIV, &PN, OperandVal); // Acquire operand value
+ markConstant(&PN, OperandVal); // Acquire operand value
}
void SCCPSolver::visitReturnInst(ReturnInst &I) {
Function *F = I.getParent()->getParent();
// If we are tracking the return value of this function, merge it in.
- if (!F->hasInternalLinkage())
+ if (!F->hasLocalLinkage())
return;
if (!TrackedRetVals.empty() && I.getNumOperands() == 1) {
// Handle functions that return multiple values.
if (!TrackedMultipleRetVals.empty() && I.getNumOperands() > 1) {
for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
- std::map<std::pair<Function*, unsigned>, LatticeVal>::iterator
+ DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
It = TrackedMultipleRetVals.find(std::make_pair(F, i));
if (It == TrackedMultipleRetVals.end()) break;
mergeInValue(It->second, F, getValueState(I.getOperand(i)));
isa<StructType>(I.getOperand(0)->getType())) {
for (unsigned i = 0, e = I.getOperand(0)->getType()->getNumContainedTypes();
i != e; ++i) {
- std::map<std::pair<Function*, unsigned>, LatticeVal>::iterator
+ DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
It = TrackedMultipleRetVals.find(std::make_pair(F, i));
if (It == TrackedMultipleRetVals.end()) break;
- Value *Val = FindInsertedValue(I.getOperand(0), i);
- mergeInValue(It->second, F, getValueState(Val));
+ if (Value *Val = FindInsertedValue(I.getOperand(0), i, Context))
+ mergeInValue(It->second, F, getValueState(Val));
}
}
}
if (VState.isOverdefined()) // Inherit overdefinedness of operand
markOverdefined(&I);
else if (VState.isConstant()) // Propagate constant value
- markConstant(&I, ConstantExpr::getCast(I.getOpcode(),
+ markConstant(&I, Context->getConstantExprCast(I.getOpcode(),
VState.getConstant(), I.getType()));
}
return;
}
- // See if we are tracking the result of the callee.
- std::map<std::pair<Function*, unsigned>, LatticeVal>::iterator
- It = TrackedMultipleRetVals.find(std::make_pair(F, *EVI.idx_begin()));
-
- // If not tracking this function (for example, it is a declaration) just move
- // to overdefined.
- if (It == TrackedMultipleRetVals.end()) {
+ // See if we are tracking the result of the callee. If not tracking this
+ // function (for example, it is a declaration) just move to overdefined.
+ if (!TrackedMultipleRetVals.count(std::make_pair(F, *EVI.idx_begin()))) {
markOverdefined(&EVI);
return;
}
// See if we are tracking the result of the callee.
Function *F = IVI.getParent()->getParent();
- std::map<std::pair<Function*, unsigned>, LatticeVal>::iterator
+ DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
It = TrackedMultipleRetVals.find(std::make_pair(F, *IVI.idx_begin()));
// Merge in the inserted member value.
if (NonOverdefVal->isUndefined()) {
// Could annihilate value.
if (I.getOpcode() == Instruction::And)
- markConstant(IV, &I, Constant::getNullValue(I.getType()));
+ markConstant(IV, &I, Context->getNullValue(I.getType()));
else if (const VectorType *PT = dyn_cast<VectorType>(I.getType()))
- markConstant(IV, &I, ConstantVector::getAllOnesValue(PT));
+ markConstant(IV, &I, Context->getConstantVectorAllOnesValue(PT));
else
- markConstant(IV, &I, ConstantInt::getAllOnesValue(I.getType()));
+ markConstant(IV, &I,
+ Context->getConstantIntAllOnesValue(I.getType()));
return;
} else {
if (I.getOpcode() == Instruction::And) {
Result.markOverdefined();
break; // Cannot fold this operation over the PHI nodes!
} else if (In1.isConstant() && In2.isConstant()) {
- Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(),
+ Constant *V =
+ Context->getConstantExpr(I.getOpcode(), In1.getConstant(),
In2.getConstant());
if (Result.isUndefined())
Result.markConstant(V);
markOverdefined(IV, &I);
} else if (V1State.isConstant() && V2State.isConstant()) {
- markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
+ markConstant(IV, &I,
+ Context->getConstantExpr(I.getOpcode(), V1State.getConstant(),
V2State.getConstant()));
}
}
Result.markOverdefined();
break; // Cannot fold this operation over the PHI nodes!
} else if (In1.isConstant() && In2.isConstant()) {
- Constant *V = ConstantExpr::getCompare(I.getPredicate(),
+ Constant *V = Context->getConstantExprCompare(I.getPredicate(),
In1.getConstant(),
In2.getConstant());
if (Result.isUndefined())
markOverdefined(IV, &I);
} else if (V1State.isConstant() && V2State.isConstant()) {
- markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(),
+ markConstant(IV, &I, Context->getConstantExprCompare(I.getPredicate(),
V1State.getConstant(),
V2State.getConstant()));
}
Constant *Ptr = Operands[0];
Operands.erase(Operands.begin()); // Erase the pointer from idx list...
- markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, &Operands[0],
+ markConstant(IV, &I, Context->getConstantExprGetElementPtr(Ptr, &Operands[0],
Operands.size()));
}
if (isa<ConstantPointerNull>(Ptr) &&
cast<PointerType>(Ptr->getType())->getAddressSpace() == 0) {
// load null -> null
- markConstant(IV, &I, Constant::getNullValue(I.getType()));
+ markConstant(IV, &I, Context->getNullValue(I.getType()));
return;
}
// Transform load (constant global) into the value loaded.
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
if (GV->isConstant()) {
- if (!GV->isDeclaration()) {
+ if (GV->hasDefinitiveInitializer()) {
markConstant(IV, &I, GV->getInitializer());
return;
}
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
if (CE->getOpcode() == Instruction::GetElementPtr)
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
- if (GV->isConstant() && !GV->isDeclaration())
+ if (GV->isConstant() && GV->hasDefinitiveInitializer())
if (Constant *V =
- ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) {
+ ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE,
+ Context)) {
markConstant(IV, &I, V);
return;
}
// The common case is that we aren't tracking the callee, either because we
// are not doing interprocedural analysis or the callee is indirect, or is
// external. Handle these cases first.
- if (F == 0 || !F->hasInternalLinkage()) {
+ if (F == 0 || !F->hasLocalLinkage()) {
CallOverdefined:
// Void return and not tracking callee, just bail.
if (I->getType() == Type::VoidTy) return;
// If we can constant fold this, mark the result of the call as a
// constant.
- if (Constant *C = ConstantFoldCall(F, &Operands[0], Operands.size())) {
+ if (Constant *C = ConstantFoldCall(F, Operands.data(), Operands.size())) {
markConstant(I, C);
return;
}
} else if (isa<StructType>(I->getType())) {
// Check to see if we're tracking this callee, if not, handle it in the
// common path above.
- std::map<std::pair<Function*, unsigned>, LatticeVal>::iterator
- TMRVI = TrackedMultipleRetVals.find(std::make_pair(F, 0));
+ DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
+ TMRVI = TrackedMultipleRetVals.find(std::make_pair(F, 0));
if (TMRVI == TrackedMultipleRetVals.end())
goto CallOverdefined;
// to be handled here, because we don't know whether the top part is 1's
// or 0's.
assert(Op0LV.isUndefined());
- markForcedConstant(LV, I, Constant::getNullValue(ITy));
+ markForcedConstant(LV, I, Context->getNullValue(ITy));
return true;
case Instruction::Mul:
case Instruction::And:
// undef * X -> 0. X could be zero.
// undef & X -> 0. X could be zero.
- markForcedConstant(LV, I, Constant::getNullValue(ITy));
+ markForcedConstant(LV, I, Context->getNullValue(ITy));
return true;
case Instruction::Or:
// undef | X -> -1. X could be -1.
if (const VectorType *PTy = dyn_cast<VectorType>(ITy))
- markForcedConstant(LV, I, ConstantVector::getAllOnesValue(PTy));
+ markForcedConstant(LV, I,
+ Context->getConstantVectorAllOnesValue(PTy));
else
- markForcedConstant(LV, I, ConstantInt::getAllOnesValue(ITy));
+ markForcedConstant(LV, I, Context->getConstantIntAllOnesValue(ITy));
return true;
case Instruction::SDiv:
// undef / X -> 0. X could be maxint.
// undef % X -> 0. X could be 1.
- markForcedConstant(LV, I, Constant::getNullValue(ITy));
+ markForcedConstant(LV, I, Context->getNullValue(ITy));
return true;
case Instruction::AShr:
// X >> undef -> 0. X could be 0.
// X << undef -> 0. X could be 0.
- markForcedConstant(LV, I, Constant::getNullValue(ITy));
+ markForcedConstant(LV, I, Context->getNullValue(ITy));
return true;
case Instruction::Select:
// undef ? X : Y -> X or Y. There could be commonality between X/Y.
// as undef, then further analysis could think the undef went another way
// leading to an inconsistent set of conclusions.
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
- BI->setCondition(ConstantInt::getFalse());
+ BI->setCondition(Context->getConstantIntFalse());
} else {
SwitchInst *SI = cast<SwitchInst>(TI);
SI->setCondition(SI->getCaseValue(1));
///
struct VISIBILITY_HIDDEN SCCP : public FunctionPass {
static char ID; // Pass identification, replacement for typeid
- SCCP() : FunctionPass((intptr_t)&ID) {}
+ SCCP() : FunctionPass(&ID) {}
// runOnFunction - Run the Sparse Conditional Constant Propagation
// algorithm, and return true if the function was modified.
bool SCCP::runOnFunction(Function &F) {
DOUT << "SCCP on function '" << F.getNameStart() << "'\n";
SCCPSolver Solver;
+ Solver.setContext(Context);
// Mark the first block of the function as being executable.
Solver.MarkBlockExecutable(F.begin());
// delete their contents now. Note that we cannot actually delete the blocks,
// as we cannot modify the CFG of the function.
//
- SmallSet<BasicBlock*, 16> &ExecutableBBs = Solver.getExecutableBlocks();
- SmallVector<Instruction*, 32> Insts;
- DenseMap<Value*, LatticeVal> &Values = Solver.getValueMapping();
+ SmallVector<Instruction*, 512> Insts;
+ std::map<Value*, LatticeVal> &Values = Solver.getValueMapping();
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
- if (!ExecutableBBs.count(BB)) {
+ if (!Solver.isBlockExecutable(BB)) {
DOUT << " BasicBlock Dead:" << *BB;
++NumDeadBlocks;
Instruction *I = Insts.back();
Insts.pop_back();
if (!I->use_empty())
- I->replaceAllUsesWith(UndefValue::get(I->getType()));
+ I->replaceAllUsesWith(Context->getUndef(I->getType()));
BB->getInstList().erase(I);
MadeChanges = true;
++NumInstRemoved;
continue;
Constant *Const = IV.isConstant()
- ? IV.getConstant() : UndefValue::get(Inst->getType());
+ ? IV.getConstant() : Context->getUndef(Inst->getType());
DOUT << " Constant: " << *Const << " = " << *Inst;
// Replaces all of the uses of a variable with uses of the constant.
///
struct VISIBILITY_HIDDEN IPSCCP : public ModulePass {
static char ID;
- IPSCCP() : ModulePass((intptr_t)&ID) {}
+ IPSCCP() : ModulePass(&ID) {}
bool runOnModule(Module &M);
};
} // end anonymous namespace
} else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) {
// Make sure we are calling the function, not passing the address.
CallSite CS = CallSite::get(cast<Instruction>(*UI));
- for (CallSite::arg_iterator AI = CS.arg_begin(),
- E = CS.arg_end(); AI != E; ++AI)
- if (*AI == GV)
- return true;
+ if (CS.hasArgument(GV))
+ return true;
} else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
if (LI->isVolatile())
return true;
// taken or that are external as overdefined.
//
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
- if (!F->hasInternalLinkage() || AddressIsTaken(F)) {
+ if (!F->hasLocalLinkage() || AddressIsTaken(F)) {
if (!F->isDeclaration())
Solver.MarkBlockExecutable(F->begin());
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
// their addresses taken, we can propagate constants through them.
for (Module::global_iterator G = M.global_begin(), E = M.global_end();
G != E; ++G)
- if (!G->isConstant() && G->hasInternalLinkage() && !AddressIsTaken(G))
+ if (!G->isConstant() && G->hasLocalLinkage() && !AddressIsTaken(G))
Solver.TrackValueOfGlobalVariable(G);
// Solve for constants.
// Iterate over all of the instructions in the module, replacing them with
// constants if we have found them to be of constant values.
//
- SmallSet<BasicBlock*, 16> &ExecutableBBs = Solver.getExecutableBlocks();
- SmallVector<Instruction*, 32> Insts;
- SmallVector<BasicBlock*, 32> BlocksToErase;
- DenseMap<Value*, LatticeVal> &Values = Solver.getValueMapping();
+ SmallVector<Instruction*, 512> Insts;
+ SmallVector<BasicBlock*, 512> BlocksToErase;
+ std::map<Value*, LatticeVal> &Values = Solver.getValueMapping();
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
LatticeVal &IV = Values[AI];
if (IV.isConstant() || IV.isUndefined()) {
Constant *CST = IV.isConstant() ?
- IV.getConstant() : UndefValue::get(AI->getType());
+ IV.getConstant() : Context->getUndef(AI->getType());
DOUT << "*** Arg " << *AI << " = " << *CST <<"\n";
// Replaces all of the uses of a variable with uses of the
}
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
- if (!ExecutableBBs.count(BB)) {
+ if (!Solver.isBlockExecutable(BB)) {
DOUT << " BasicBlock Dead:" << *BB;
++IPNumDeadBlocks;
Instruction *I = Insts.back();
Insts.pop_back();
if (!I->use_empty())
- I->replaceAllUsesWith(UndefValue::get(I->getType()));
+ I->replaceAllUsesWith(Context->getUndef(I->getType()));
BB->getInstList().erase(I);
MadeChanges = true;
++IPNumInstRemoved;
TI->getSuccessor(i)->removePredecessor(BB);
}
if (!TI->use_empty())
- TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
+ TI->replaceAllUsesWith(Context->getUndef(TI->getType()));
BB->getInstList().erase(TI);
if (&*BB != &F->front())
} else {
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
Instruction *Inst = BI++;
- if (Inst->getType() == Type::VoidTy ||
- isa<TerminatorInst>(Inst))
+ if (Inst->getType() == Type::VoidTy)
continue;
LatticeVal &IV = Values[Inst];
continue;
Constant *Const = IV.isConstant()
- ? IV.getConstant() : UndefValue::get(Inst->getType());
+ ? IV.getConstant() : Context->getUndef(Inst->getType());
DOUT << " Constant: " << *Const << " = " << *Inst;
// Replaces all of the uses of a variable with uses of the
Inst->replaceAllUsesWith(Const);
// Delete the instruction.
- if (!isa<CallInst>(Inst))
+ if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst))
Inst->eraseFromParent();
// Hey, we just changed something!
// The constant folder may not have been able to fold the terminator
// if this is a branch or switch on undef. Fold it manually as a
// branch to the first successor.
+#ifndef NDEBUG
if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) &&
"Branch should be foldable!");
} else {
assert(0 && "Didn't fold away reference to block!");
}
+#endif
// Make this an uncond branch to the first successor.
TerminatorInst *TI = I->getParent()->getTerminator();
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
if (!isa<UndefValue>(RI->getOperand(0)))
- RI->setOperand(0, UndefValue::get(F->getReturnType()));
+ RI->setOperand(0, Context->getUndef(F->getReturnType()));
}
// If we infered constant or undef values for globals variables, we can delete
projects / oota-llvm.git / blobdiff