#define DEBUG_TYPE "sccp"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/IPO.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Compiler.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"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <map>
using namespace llvm;
STATISTIC(NumInstRemoved, "Number of instructions removed");
STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
STATISTIC(IPNumDeadBlocks , "Number of basic blocks unreachable by IPSCCP");
STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
namespace {
class VISIBILITY_HIDDEN LatticeVal {
enum {
undefined,
constant,
forcedconstant,
overdefined
} LatticeValue;
Constant *ConstantVal; public:
inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {}
inline bool markOverdefined() {
if (LatticeValue != overdefined) {
LatticeValue = overdefined;
return true;
}
return false;
}
inline bool markConstant(Constant *V) {
if (LatticeValue != constant) {
if (LatticeValue == undefined) {
LatticeValue = constant;
assert(V && "Marking constant with NULL");
ConstantVal = V;
} else {
assert(LatticeValue == forcedconstant &&
"Cannot move from overdefined to constant!");
if (V == ConstantVal) return false;
LatticeValue = overdefined;
}
return true;
} else {
assert(ConstantVal == V && "Marking constant with different value");
}
return false;
}
inline void markForcedConstant(Constant *V) {
assert(LatticeValue == undefined && "Can't force a defined value!");
LatticeValue = forcedconstant;
ConstantVal = V;
}
inline bool isUndefined() const { return LatticeValue == undefined; }
inline bool isConstant() const {
return LatticeValue == constant || LatticeValue == forcedconstant;
}
inline bool isOverdefined() const { return LatticeValue == overdefined; }
inline Constant *getConstant() const {
assert(isConstant() && "Cannot get the constant of a non-constant!");
return ConstantVal;
}
};
class SCCPSolver : public InstVisitor<SCCPSolver> {
DenseSet<BasicBlock*> BBExecutable; std::map<Value*, LatticeVal> ValueState;
DenseMap<GlobalVariable*, LatticeVal> TrackedGlobals;
DenseMap<Function*, LatticeVal> TrackedRetVals;
DenseMap<std::pair<Function*, unsigned>, LatticeVal> TrackedMultipleRetVals;
SmallVector<Value*, 64> OverdefinedInstWorkList;
SmallVector<Value*, 64> InstWorkList;
SmallVector<BasicBlock*, 64> BBWorkList;
std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs;
typedef std::pair<BasicBlock*, BasicBlock*> Edge;
DenseSet<Edge> KnownFeasibleEdges;
public:
void MarkBlockExecutable(BasicBlock *BB) {
DOUT << "Marking Block Executable: " << BB->getNameStart() << "\n";
BBExecutable.insert(BB); BBWorkList.push_back(BB); }
void TrackValueOfGlobalVariable(GlobalVariable *GV) {
const Type *ElTy = GV->getType()->getElementType();
if (ElTy->isFirstClassType()) {
LatticeVal &IV = TrackedGlobals[GV];
if (!isa<UndefValue>(GV->getInitializer()))
IV.markConstant(GV->getInitializer());
}
}
void AddTrackedFunction(Function *F) {
assert(F->hasLocalLinkage() && "Can only track internal functions!");
if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) {
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i),
LatticeVal()));
} else
TrackedRetVals.insert(std::make_pair(F, LatticeVal()));
}
void Solve();
bool ResolvedUndefsIn(Function &F);
bool isBlockExecutable(BasicBlock *BB) const {
return BBExecutable.count(BB);
}
std::map<Value*, LatticeVal> &getValueMapping() {
return ValueState;
}
const DenseMap<Function*, LatticeVal> &getTrackedRetVals() {
return TrackedRetVals;
}
const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() {
return TrackedGlobals;
}
inline void markOverdefined(Value *V) {
markOverdefined(ValueState[V], V);
}
private:
inline void markConstant(LatticeVal &IV, Value *V, Constant *C) {
if (IV.markConstant(C)) {
DOUT << "markConstant: " << *C << ": " << *V;
InstWorkList.push_back(V);
}
}
inline void markForcedConstant(LatticeVal &IV, Value *V, Constant *C) {
IV.markForcedConstant(C);
DOUT << "markForcedConstant: " << *C << ": " << *V;
InstWorkList.push_back(V);
}
inline void markConstant(Value *V, Constant *C) {
markConstant(ValueState[V], V, C);
}
inline void markOverdefined(LatticeVal &IV, Value *V) {
if (IV.markOverdefined()) {
DEBUG(DOUT << "markOverdefined: ";
if (Function *F = dyn_cast<Function>(V))
DOUT << "Function '" << F->getName() << "'\n";
else
DOUT << *V);
OverdefinedInstWorkList.push_back(V);
}
}
inline void mergeInValue(LatticeVal &IV, Value *V, LatticeVal &MergeWithV) {
if (IV.isOverdefined() || MergeWithV.isUndefined())
return; if (MergeWithV.isOverdefined())
markOverdefined(IV, V);
else if (IV.isUndefined())
markConstant(IV, V, MergeWithV.getConstant());
else if (IV.getConstant() != MergeWithV.getConstant())
markOverdefined(IV, V);
}
inline void mergeInValue(Value *V, LatticeVal &MergeWithV) {
return mergeInValue(ValueState[V], V, MergeWithV);
}
inline LatticeVal &getValueState(Value *V) {
std::map<Value*, LatticeVal>::iterator I = ValueState.find(V);
if (I != ValueState.end()) return I->second;
if (Constant *C = dyn_cast<Constant>(V)) {
if (isa<UndefValue>(V)) {
} else {
LatticeVal &LV = ValueState[C];
LV.markConstant(C); return LV;
}
}
return ValueState[V];
}
void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
return;
if (BBExecutable.count(Dest)) {
DOUT << "Marking Edge Executable: " << Source->getNameStart()
<< " -> " << Dest->getNameStart() << "\n";
for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I)
visitPHINode(*cast<PHINode>(I));
} else {
MarkBlockExecutable(Dest);
}
}
void getFeasibleSuccessors(TerminatorInst &TI, SmallVector<bool, 16> &Succs);
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
void OperandChangedState(User *U) {
Instruction &I = cast<Instruction>(*U);
if (BBExecutable.count(I.getParent())) visit(I);
}
private:
friend class InstVisitor<SCCPSolver>;
void visitPHINode(PHINode &I);
void visitReturnInst(ReturnInst &I);
void visitTerminatorInst(TerminatorInst &TI);
void visitCastInst(CastInst &I);
void visitSelectInst(SelectInst &I);
void visitBinaryOperator(Instruction &I);
void visitCmpInst(CmpInst &I);
void visitExtractElementInst(ExtractElementInst &I);
void visitInsertElementInst(InsertElementInst &I);
void visitShuffleVectorInst(ShuffleVectorInst &I);
void visitExtractValueInst(ExtractValueInst &EVI);
void visitInsertValueInst(InsertValueInst &IVI);
void visitStoreInst (Instruction &I);
void visitLoadInst (LoadInst &I);
void visitGetElementPtrInst(GetElementPtrInst &I);
void visitCallInst (CallInst &I) { visitCallSite(CallSite::get(&I)); }
void visitInvokeInst (InvokeInst &II) {
visitCallSite(CallSite::get(&II));
visitTerminatorInst(II);
}
void visitCallSite (CallSite CS);
void visitUnwindInst (TerminatorInst &I) { }
void visitUnreachableInst(TerminatorInst &I) { }
void visitAllocationInst(Instruction &I) { markOverdefined(&I); }
void visitVANextInst (Instruction &I) { markOverdefined(&I); }
void visitVAArgInst (Instruction &I) { markOverdefined(&I); }
void visitFreeInst (Instruction &I) { }
void visitInstruction(Instruction &I) {
cerr << "SCCP: Don't know how to handle: " << I;
markOverdefined(&I); }
};
}
void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
SmallVector<bool, 16> &Succs) {
Succs.resize(TI.getNumSuccessors());
if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
if (BI->isUnconditional()) {
Succs[0] = true;
} else {
LatticeVal &BCValue = getValueState(BI->getCondition());
if (BCValue.isOverdefined() ||
(BCValue.isConstant() && !isa<ConstantInt>(BCValue.getConstant()))) {
Succs[0] = Succs[1] = true;
} else if (BCValue.isConstant()) {
Succs[BCValue.getConstant() == ConstantInt::getFalse()] = true;
}
}
} else if (isa<InvokeInst>(&TI)) {
Succs[0] = Succs[1] = true;
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) {
LatticeVal &SCValue = getValueState(SI->getCondition());
if (SCValue.isOverdefined() || (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) {
Succs.assign(TI.getNumSuccessors(), true);
} else if (SCValue.isConstant())
Succs[SI->findCaseValue(cast<ConstantInt>(SCValue.getConstant()))] = true;
} else {
assert(0 && "SCCP: Don't know how to handle this terminator!");
}
}
bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
assert(BBExecutable.count(To) && "Dest should always be alive!");
if (!BBExecutable.count(From)) return false;
TerminatorInst *TI = From->getTerminator();
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
if (BI->isUnconditional())
return true;
else {
LatticeVal &BCValue = getValueState(BI->getCondition());
if (BCValue.isOverdefined()) {
return true;
} else if (BCValue.isConstant()) {
if (!isa<ConstantInt>(BCValue.getConstant())) return true;
return BI->getSuccessor(BCValue.getConstant() ==
ConstantInt::getFalse()) == To;
}
return false;
}
} else if (isa<InvokeInst>(TI)) {
return true;
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
LatticeVal &SCValue = getValueState(SI->getCondition());
if (SCValue.isOverdefined()) { return true;
} else if (SCValue.isConstant()) {
Constant *CPV = SCValue.getConstant();
if (!isa<ConstantInt>(CPV))
return true;
for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i)
if (SI->getSuccessorValue(i) == CPV) return SI->getSuccessor(i) == To;
return SI->getDefaultDest() == To;
}
return false;
} else {
cerr << "Unknown terminator instruction: " << *TI;
abort();
}
}
void SCCPSolver::visitPHINode(PHINode &PN) {
LatticeVal &PNIV = getValueState(&PN);
if (PNIV.isOverdefined()) {
std::multimap<PHINode*, Instruction*>::iterator I, E;
tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN);
if (I != E) {
SmallVector<Instruction*, 16> Users;
for (; I != E; ++I) Users.push_back(I->second);
while (!Users.empty()) {
visit(Users.back());
Users.pop_back();
}
}
return; }
if (PN.getNumIncomingValues() > 64) {
markOverdefined(PNIV, &PN);
return;
}
Constant *OperandVal = 0;
for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
LatticeVal &IV = getValueState(PN.getIncomingValue(i));
if (IV.isUndefined()) continue;
if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) {
if (IV.isOverdefined()) { markOverdefined(&PN);
return;
}
if (OperandVal == 0) { OperandVal = IV.getConstant();
} else {
if (IV.getConstant() != OperandVal) {
markOverdefined(&PN); return; }
}
}
}
if (OperandVal)
markConstant(&PN, OperandVal); }
void SCCPSolver::visitReturnInst(ReturnInst &I) {
if (I.getNumOperands() == 0) return;
Function *F = I.getParent()->getParent();
if (!F->hasLocalLinkage())
return;
if (!TrackedRetVals.empty() && I.getNumOperands() == 1) {
DenseMap<Function*, LatticeVal>::iterator TFRVI =
TrackedRetVals.find(F);
if (TFRVI != TrackedRetVals.end() &&
!TFRVI->second.isOverdefined()) {
LatticeVal &IV = getValueState(I.getOperand(0));
mergeInValue(TFRVI->second, F, IV);
return;
}
}
if (!TrackedMultipleRetVals.empty() && I.getNumOperands() > 1) {
for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
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)));
}
} else if (!TrackedMultipleRetVals.empty() &&
I.getNumOperands() == 1 &&
isa<StructType>(I.getOperand(0)->getType())) {
for (unsigned i = 0, e = I.getOperand(0)->getType()->getNumContainedTypes();
i != e; ++i) {
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));
}
}
}
void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
SmallVector<bool, 16> SuccFeasible;
getFeasibleSuccessors(TI, SuccFeasible);
BasicBlock *BB = TI.getParent();
for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
if (SuccFeasible[i])
markEdgeExecutable(BB, TI.getSuccessor(i));
}
void SCCPSolver::visitCastInst(CastInst &I) {
Value *V = I.getOperand(0);
LatticeVal &VState = getValueState(V);
if (VState.isOverdefined()) markOverdefined(&I);
else if (VState.isConstant()) markConstant(&I, ConstantExpr::getCast(I.getOpcode(),
VState.getConstant(), I.getType()));
}
void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
Value *Aggr = EVI.getAggregateOperand();
if (isa<UndefValue>(Aggr))
return;
if (EVI.getNumIndices() != 1) {
markOverdefined(&EVI);
return;
}
Function *F = 0;
if (CallInst *CI = dyn_cast<CallInst>(Aggr))
F = CI->getCalledFunction();
else if (InvokeInst *II = dyn_cast<InvokeInst>(Aggr))
F = II->getCalledFunction();
if (F == 0 || TrackedMultipleRetVals.empty()) {
markOverdefined(&EVI);
return;
}
if (!TrackedMultipleRetVals.count(std::make_pair(F, *EVI.idx_begin()))) {
markOverdefined(&EVI);
return;
}
}
void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) {
Value *Aggr = IVI.getAggregateOperand();
Value *Val = IVI.getInsertedValueOperand();
if (isa<UndefValue>(Aggr) && isa<UndefValue>(Val))
return;
if (IVI.getNumIndices() != 1) {
markOverdefined(&IVI);
return;
}
for (const InsertValueInst *TmpIVI = &IVI; ; ) {
if (!TmpIVI->hasOneUse()) {
markOverdefined(&IVI);
return;
}
const Value *V = *TmpIVI->use_begin();
if (isa<ReturnInst>(V))
break;
TmpIVI = dyn_cast<InsertValueInst>(V);
if (!TmpIVI) {
markOverdefined(&IVI);
return;
}
}
Function *F = IVI.getParent()->getParent();
DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
It = TrackedMultipleRetVals.find(std::make_pair(F, *IVI.idx_begin()));
if (It != TrackedMultipleRetVals.end())
mergeInValue(It->second, F, getValueState(Val));
markOverdefined(&IVI);
}
void SCCPSolver::visitSelectInst(SelectInst &I) {
LatticeVal &CondValue = getValueState(I.getCondition());
if (CondValue.isUndefined())
return;
if (CondValue.isConstant()) {
if (ConstantInt *CondCB = dyn_cast<ConstantInt>(CondValue.getConstant())){
mergeInValue(&I, getValueState(CondCB->getZExtValue() ? I.getTrueValue()
: I.getFalseValue()));
return;
}
}
LatticeVal &TVal = getValueState(I.getTrueValue());
LatticeVal &FVal = getValueState(I.getFalseValue());
if (TVal.isConstant() && FVal.isConstant() &&
TVal.getConstant() == FVal.getConstant()) {
markConstant(&I, FVal.getConstant());
return;
}
if (TVal.isUndefined()) { mergeInValue(&I, FVal);
} else if (FVal.isUndefined()) { mergeInValue(&I, TVal);
} else {
markOverdefined(&I);
}
}
void SCCPSolver::visitBinaryOperator(Instruction &I) {
LatticeVal &IV = ValueState[&I];
if (IV.isOverdefined()) return;
LatticeVal &V1State = getValueState(I.getOperand(0));
LatticeVal &V2State = getValueState(I.getOperand(1));
if (V1State.isOverdefined() || V2State.isOverdefined()) {
if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) {
LatticeVal *NonOverdefVal = 0;
if (!V1State.isOverdefined()) {
NonOverdefVal = &V1State;
} else if (!V2State.isOverdefined()) {
NonOverdefVal = &V2State;
}
if (NonOverdefVal) {
if (NonOverdefVal->isUndefined()) {
if (I.getOpcode() == Instruction::And)
markConstant(IV, &I, Constant::getNullValue(I.getType()));
else if (const VectorType *PT = dyn_cast<VectorType>(I.getType()))
markConstant(IV, &I, ConstantVector::getAllOnesValue(PT));
else
markConstant(IV, &I, ConstantInt::getAllOnesValue(I.getType()));
return;
} else {
if (I.getOpcode() == Instruction::And) {
if (NonOverdefVal->getConstant()->isNullValue()) {
markConstant(IV, &I, NonOverdefVal->getConstant());
return; }
} else {
if (ConstantInt *CI =
dyn_cast<ConstantInt>(NonOverdefVal->getConstant()))
if (CI->isAllOnesValue()) {
markConstant(IV, &I, NonOverdefVal->getConstant());
return; }
}
}
}
}
if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0)))
if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1)))
if (PN1->getParent() == PN2->getParent()) {
LatticeVal Result;
for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
LatticeVal &In1 = getValueState(PN1->getIncomingValue(i));
BasicBlock *InBlock = PN1->getIncomingBlock(i);
LatticeVal &In2 =
getValueState(PN2->getIncomingValueForBlock(InBlock));
if (In1.isOverdefined() || In2.isOverdefined()) {
Result.markOverdefined();
break; } else if (In1.isConstant() && In2.isConstant()) {
Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(),
In2.getConstant());
if (Result.isUndefined())
Result.markConstant(V);
else if (Result.isConstant() && Result.getConstant() != V) {
Result.markOverdefined();
break;
}
}
}
if (Result.isConstant()) {
markConstant(IV, &I, Result.getConstant());
UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I));
UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I));
return;
} else if (Result.isUndefined()) {
return;
}
std::multimap<PHINode*, Instruction*>::iterator It, E;
tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1);
while (It != E) {
if (It->second == &I) {
UsersOfOverdefinedPHIs.erase(It++);
} else
++It;
}
tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2);
while (It != E) {
if (It->second == &I) {
UsersOfOverdefinedPHIs.erase(It++);
} else
++It;
}
}
markOverdefined(IV, &I);
} else if (V1State.isConstant() && V2State.isConstant()) {
markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
V2State.getConstant()));
}
}
void SCCPSolver::visitCmpInst(CmpInst &I) {
LatticeVal &IV = ValueState[&I];
if (IV.isOverdefined()) return;
LatticeVal &V1State = getValueState(I.getOperand(0));
LatticeVal &V2State = getValueState(I.getOperand(1));
if (V1State.isOverdefined() || V2State.isOverdefined()) {
if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0)))
if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1)))
if (PN1->getParent() == PN2->getParent()) {
LatticeVal Result;
for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
LatticeVal &In1 = getValueState(PN1->getIncomingValue(i));
BasicBlock *InBlock = PN1->getIncomingBlock(i);
LatticeVal &In2 =
getValueState(PN2->getIncomingValueForBlock(InBlock));
if (In1.isOverdefined() || In2.isOverdefined()) {
Result.markOverdefined();
break; } else if (In1.isConstant() && In2.isConstant()) {
Constant *V = ConstantExpr::getCompare(I.getPredicate(),
In1.getConstant(),
In2.getConstant());
if (Result.isUndefined())
Result.markConstant(V);
else if (Result.isConstant() && Result.getConstant() != V) {
Result.markOverdefined();
break;
}
}
}
if (Result.isConstant()) {
markConstant(IV, &I, Result.getConstant());
UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I));
UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I));
return;
} else if (Result.isUndefined()) {
return;
}
std::multimap<PHINode*, Instruction*>::iterator It, E;
tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1);
while (It != E) {
if (It->second == &I) {
UsersOfOverdefinedPHIs.erase(It++);
} else
++It;
}
tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2);
while (It != E) {
if (It->second == &I) {
UsersOfOverdefinedPHIs.erase(It++);
} else
++It;
}
}
markOverdefined(IV, &I);
} else if (V1State.isConstant() && V2State.isConstant()) {
markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(),
V1State.getConstant(),
V2State.getConstant()));
}
}
void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) {
markOverdefined(&I);
return;
#if 0
LatticeVal &ValState = getValueState(I.getOperand(0));
LatticeVal &IdxState = getValueState(I.getOperand(1));
if (ValState.isOverdefined() || IdxState.isOverdefined())
markOverdefined(&I);
else if(ValState.isConstant() && IdxState.isConstant())
markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(),
IdxState.getConstant()));
#endif
}
void SCCPSolver::visitInsertElementInst(InsertElementInst &I) {
markOverdefined(&I);
return;
#if 0
LatticeVal &ValState = getValueState(I.getOperand(0));
LatticeVal &EltState = getValueState(I.getOperand(1));
LatticeVal &IdxState = getValueState(I.getOperand(2));
if (ValState.isOverdefined() || EltState.isOverdefined() ||
IdxState.isOverdefined())
markOverdefined(&I);
else if(ValState.isConstant() && EltState.isConstant() &&
IdxState.isConstant())
markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(),
EltState.getConstant(),
IdxState.getConstant()));
else if (ValState.isUndefined() && EltState.isConstant() &&
IdxState.isConstant())
markConstant(&I,ConstantExpr::getInsertElement(UndefValue::get(I.getType()),
EltState.getConstant(),
IdxState.getConstant()));
#endif
}
void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) {
markOverdefined(&I);
return;
#if 0
LatticeVal &V1State = getValueState(I.getOperand(0));
LatticeVal &V2State = getValueState(I.getOperand(1));
LatticeVal &MaskState = getValueState(I.getOperand(2));
if (MaskState.isUndefined() ||
(V1State.isUndefined() && V2State.isUndefined()))
return;
if (V1State.isOverdefined() || V2State.isOverdefined() ||
MaskState.isOverdefined()) {
markOverdefined(&I);
} else {
Constant *V1 = V1State.isConstant() ?
V1State.getConstant() : UndefValue::get(I.getType());
Constant *V2 = V2State.isConstant() ?
V2State.getConstant() : UndefValue::get(I.getType());
Constant *Mask = MaskState.isConstant() ?
MaskState.getConstant() : UndefValue::get(I.getOperand(2)->getType());
markConstant(&I, ConstantExpr::getShuffleVector(V1, V2, Mask));
}
#endif
}
void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
LatticeVal &IV = ValueState[&I];
if (IV.isOverdefined()) return;
SmallVector<Constant*, 8> Operands;
Operands.reserve(I.getNumOperands());
for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
LatticeVal &State = getValueState(I.getOperand(i));
if (State.isUndefined())
return; else if (State.isOverdefined()) {
markOverdefined(IV, &I);
return;
}
assert(State.isConstant() && "Unknown state!");
Operands.push_back(State.getConstant());
}
Constant *Ptr = Operands[0];
Operands.erase(Operands.begin());
markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, &Operands[0],
Operands.size()));
}
void SCCPSolver::visitStoreInst(Instruction &SI) {
if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
return;
GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV);
if (I == TrackedGlobals.end() || I->second.isOverdefined()) return;
LatticeVal &PtrVal = getValueState(SI.getOperand(0));
mergeInValue(I->second, GV, PtrVal);
if (I->second.isOverdefined())
TrackedGlobals.erase(I); }
void SCCPSolver::visitLoadInst(LoadInst &I) {
LatticeVal &IV = ValueState[&I];
if (IV.isOverdefined()) return;
LatticeVal &PtrVal = getValueState(I.getOperand(0));
if (PtrVal.isUndefined()) return; if (PtrVal.isConstant() && !I.isVolatile()) {
Value *Ptr = PtrVal.getConstant();
if (isa<ConstantPointerNull>(Ptr) &&
cast<PointerType>(Ptr->getType())->getAddressSpace() == 0) {
markConstant(IV, &I, Constant::getNullValue(I.getType()));
return;
}
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
if (GV->isConstant()) {
if (GV->hasDefinitiveInitializer()) {
markConstant(IV, &I, GV->getInitializer());
return;
}
} else if (!TrackedGlobals.empty()) {
DenseMap<GlobalVariable*, LatticeVal>::iterator It =
TrackedGlobals.find(GV);
if (It != TrackedGlobals.end()) {
mergeInValue(IV, &I, It->second);
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->hasDefinitiveInitializer())
if (Constant *V =
ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) {
markConstant(IV, &I, V);
return;
}
}
markOverdefined(IV, &I);
}
void SCCPSolver::visitCallSite(CallSite CS) {
Function *F = CS.getCalledFunction();
Instruction *I = CS.getInstruction();
if (F == 0 || !F->hasLocalLinkage()) {
CallOverdefined:
if (I->getType() == Type::VoidTy) return;
if (!isa<StructType>(I->getType()) && F && F->isDeclaration() &&
canConstantFoldCallTo(F)) {
SmallVector<Constant*, 8> Operands;
for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
AI != E; ++AI) {
LatticeVal &State = getValueState(*AI);
if (State.isUndefined())
return; else if (State.isOverdefined()) {
markOverdefined(I);
return;
}
assert(State.isConstant() && "Unknown state!");
Operands.push_back(State.getConstant());
}
if (Constant *C = ConstantFoldCall(F, &Operands[0], Operands.size())) {
markConstant(I, C);
return;
}
}
markOverdefined(I);
return;
}
DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F);
if (TFRVI != TrackedRetVals.end()) {
mergeInValue(I, TFRVI->second);
} else if (isa<StructType>(I->getType())) {
DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
TMRVI = TrackedMultipleRetVals.find(std::make_pair(F, 0));
if (TMRVI == TrackedMultipleRetVals.end())
goto CallOverdefined;
for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
UI != E; ++UI) {
if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(*UI)) {
if (EVI->getNumIndices() == 1) {
mergeInValue(EVI,
TrackedMultipleRetVals[std::make_pair(F, *EVI->idx_begin())]);
continue;
}
}
markOverdefined(*UI);
}
} else {
goto CallOverdefined;
}
if (!BBExecutable.count(F->begin()))
MarkBlockExecutable(F->begin());
CallSite::arg_iterator CAI = CS.arg_begin();
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
AI != E; ++AI, ++CAI) {
LatticeVal &IV = ValueState[AI];
if (!IV.isOverdefined())
mergeInValue(IV, AI, getValueState(*CAI));
}
}
void SCCPSolver::Solve() {
while (!BBWorkList.empty() || !InstWorkList.empty() ||
!OverdefinedInstWorkList.empty()) {
while (!OverdefinedInstWorkList.empty()) {
Value *I = OverdefinedInstWorkList.back();
OverdefinedInstWorkList.pop_back();
DOUT << "\nPopped off OI-WL: " << *I;
for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
UI != E; ++UI)
OperandChangedState(*UI);
}
while (!InstWorkList.empty()) {
Value *I = InstWorkList.back();
InstWorkList.pop_back();
DOUT << "\nPopped off I-WL: " << *I;
if (!getValueState(I).isOverdefined())
for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
UI != E; ++UI)
OperandChangedState(*UI);
}
while (!BBWorkList.empty()) {
BasicBlock *BB = BBWorkList.back();
BBWorkList.pop_back();
DOUT << "\nPopped off BBWL: " << *BB;
visit(BB);
}
}
}
bool SCCPSolver::ResolvedUndefsIn(Function &F) {
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
if (!BBExecutable.count(BB))
continue;
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
if (I->getType() == Type::VoidTy) continue;
LatticeVal &LV = getValueState(I);
if (!LV.isUndefined()) continue;
LatticeVal &Op0LV = getValueState(I->getOperand(0));
LatticeVal Op1LV;
if (I->getNumOperands() == 2) {
Op1LV = getValueState(I->getOperand(1));
if (Op0LV.isUndefined() && Op1LV.isUndefined())
continue;
}
const Type *ITy = I->getType();
switch (I->getOpcode()) {
default: break; case Instruction::ZExt:
assert(Op0LV.isUndefined());
markForcedConstant(LV, I, Constant::getNullValue(ITy));
return true;
case Instruction::Mul:
case Instruction::And:
markForcedConstant(LV, I, Constant::getNullValue(ITy));
return true;
case Instruction::Or:
if (const VectorType *PTy = dyn_cast<VectorType>(ITy))
markForcedConstant(LV, I, ConstantVector::getAllOnesValue(PTy));
else
markForcedConstant(LV, I, ConstantInt::getAllOnesValue(ITy));
return true;
case Instruction::SDiv:
case Instruction::UDiv:
case Instruction::SRem:
case Instruction::URem:
if (Op1LV.isUndefined()) break;
markForcedConstant(LV, I, Constant::getNullValue(ITy));
return true;
case Instruction::AShr:
if (Op0LV.isUndefined()) break;
if (Op0LV.isConstant())
markForcedConstant(LV, I, Op0LV.getConstant());
else
markOverdefined(LV, I);
return true;
case Instruction::LShr:
case Instruction::Shl:
if (Op0LV.isUndefined()) break;
markForcedConstant(LV, I, Constant::getNullValue(ITy));
return true;
case Instruction::Select:
if (Op0LV.isUndefined()) {
if (!Op1LV.isConstant()) Op1LV = getValueState(I->getOperand(2));
} else if (Op1LV.isUndefined()) {
Op1LV = getValueState(I->getOperand(2));
if (Op1LV.isUndefined())
break;
} else {
}
if (Op1LV.isConstant())
markForcedConstant(LV, I, Op1LV.getConstant());
else
markOverdefined(LV, I);
return true;
case Instruction::Call:
markOverdefined(LV, I);
return true;
}
}
TerminatorInst *TI = BB->getTerminator();
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
if (!BI->isConditional()) continue;
if (!getValueState(BI->getCondition()).isUndefined())
continue;
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
if (SI->getNumSuccessors()<2) continue;
if (!getValueState(SI->getCondition()).isUndefined())
continue;
} else {
continue;
}
if (KnownFeasibleEdges.count(Edge(BB, TI->getSuccessor(1))))
continue;
markEdgeExecutable(BB, TI->getSuccessor(1));
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
BI->setCondition(ConstantInt::getFalse());
} else {
SwitchInst *SI = cast<SwitchInst>(TI);
SI->setCondition(SI->getCaseValue(1));
}
return true;
}
return false;
}
namespace {
struct VISIBILITY_HIDDEN SCCP : public FunctionPass {
static char ID; SCCP() : FunctionPass(&ID) {}
bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
}
};
}
char SCCP::ID = 0;
static RegisterPass<SCCP>
X("sccp", "Sparse Conditional Constant Propagation");
FunctionPass *llvm::createSCCPPass() {
return new SCCP();
}
bool SCCP::runOnFunction(Function &F) {
DOUT << "SCCP on function '" << F.getNameStart() << "'\n";
SCCPSolver Solver;
Solver.MarkBlockExecutable(F.begin());
for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI)
Solver.markOverdefined(AI);
bool ResolvedUndefs = true;
while (ResolvedUndefs) {
Solver.Solve();
DOUT << "RESOLVING UNDEFs\n";
ResolvedUndefs = Solver.ResolvedUndefsIn(F);
}
bool MadeChanges = false;
SmallVector<Instruction*, 512> Insts;
std::map<Value*, LatticeVal> &Values = Solver.getValueMapping();
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
if (!Solver.isBlockExecutable(BB)) {
DOUT << " BasicBlock Dead:" << *BB;
++NumDeadBlocks;
for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator();
I != E; ++I)
Insts.push_back(I);
while (!Insts.empty()) {
Instruction *I = Insts.back();
Insts.pop_back();
if (!I->use_empty())
I->replaceAllUsesWith(UndefValue::get(I->getType()));
BB->getInstList().erase(I);
MadeChanges = true;
++NumInstRemoved;
}
} else {
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
Instruction *Inst = BI++;
if (Inst->getType() == Type::VoidTy ||
isa<TerminatorInst>(Inst))
continue;
LatticeVal &IV = Values[Inst];
if (!IV.isConstant() && !IV.isUndefined())
continue;
Constant *Const = IV.isConstant()
? IV.getConstant() : UndefValue::get(Inst->getType());
DOUT << " Constant: " << *Const << " = " << *Inst;
Inst->replaceAllUsesWith(Const);
Inst->eraseFromParent();
MadeChanges = true;
++NumInstRemoved;
}
}
return MadeChanges;
}
namespace {
struct VISIBILITY_HIDDEN IPSCCP : public ModulePass {
static char ID;
IPSCCP() : ModulePass(&ID) {}
bool runOnModule(Module &M);
};
}
char IPSCCP::ID = 0;
static RegisterPass<IPSCCP>
Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation");
ModulePass *llvm::createIPSCCPPass() {
return new IPSCCP();
}
static bool AddressIsTaken(GlobalValue *GV) {
GV->removeDeadConstantUsers();
for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end();
UI != E; ++UI)
if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
if (SI->getOperand(0) == GV || SI->isVolatile())
return true; } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) {
CallSite CS = CallSite::get(cast<Instruction>(*UI));
if (CS.hasArgument(GV))
return true;
} else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
if (LI->isVolatile())
return true;
} else {
return true;
}
return false;
}
bool IPSCCP::runOnModule(Module &M) {
SCCPSolver Solver;
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++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();
AI != E; ++AI)
Solver.markOverdefined(AI);
} else {
Solver.AddTrackedFunction(F);
}
for (Module::global_iterator G = M.global_begin(), E = M.global_end();
G != E; ++G)
if (!G->isConstant() && G->hasLocalLinkage() && !AddressIsTaken(G))
Solver.TrackValueOfGlobalVariable(G);
bool ResolvedUndefs = true;
while (ResolvedUndefs) {
Solver.Solve();
DOUT << "RESOLVING UNDEFS\n";
ResolvedUndefs = false;
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
ResolvedUndefs |= Solver.ResolvedUndefsIn(*F);
}
bool MadeChanges = false;
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();
AI != E; ++AI)
if (!AI->use_empty()) {
LatticeVal &IV = Values[AI];
if (IV.isConstant() || IV.isUndefined()) {
Constant *CST = IV.isConstant() ?
IV.getConstant() : UndefValue::get(AI->getType());
DOUT << "*** Arg " << *AI << " = " << *CST <<"\n";
AI->replaceAllUsesWith(CST);
++IPNumArgsElimed;
}
}
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
if (!Solver.isBlockExecutable(BB)) {
DOUT << " BasicBlock Dead:" << *BB;
++IPNumDeadBlocks;
TerminatorInst *TI = BB->getTerminator();
for (BasicBlock::iterator I = BB->begin(), E = TI; I != E; ++I)
Insts.push_back(I);
while (!Insts.empty()) {
Instruction *I = Insts.back();
Insts.pop_back();
if (!I->use_empty())
I->replaceAllUsesWith(UndefValue::get(I->getType()));
BB->getInstList().erase(I);
MadeChanges = true;
++IPNumInstRemoved;
}
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
BasicBlock *Succ = TI->getSuccessor(i);
if (!Succ->empty() && isa<PHINode>(Succ->begin()))
TI->getSuccessor(i)->removePredecessor(BB);
}
if (!TI->use_empty())
TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
BB->getInstList().erase(TI);
if (&*BB != &F->front())
BlocksToErase.push_back(BB);
else
new UnreachableInst(BB);
} else {
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
Instruction *Inst = BI++;
if (Inst->getType() == Type::VoidTy)
continue;
LatticeVal &IV = Values[Inst];
if (!IV.isConstant() && !IV.isUndefined())
continue;
Constant *Const = IV.isConstant()
? IV.getConstant() : UndefValue::get(Inst->getType());
DOUT << " Constant: " << *Const << " = " << *Inst;
Inst->replaceAllUsesWith(Const);
if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst))
Inst->eraseFromParent();
MadeChanges = true;
++IPNumInstRemoved;
}
}
for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
BasicBlock *DeadBB = BlocksToErase[i];
while (!DeadBB->use_empty()) {
Instruction *I = cast<Instruction>(DeadBB->use_back());
bool Folded = ConstantFoldTerminator(I->getParent());
if (!Folded) {
#ifndef NDEBUG
if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) &&
"Branch should be foldable!");
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
assert(isa<UndefValue>(SI->getCondition()) && "Switch should fold");
} else {
assert(0 && "Didn't fold away reference to block!");
}
#endif
TerminatorInst *TI = I->getParent()->getTerminator();
BranchInst::Create(TI->getSuccessor(0), TI);
for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i)
TI->getSuccessor(i)->removePredecessor(TI->getParent());
TI->eraseFromParent();
}
}
F->getBasicBlockList().erase(DeadBB);
}
BlocksToErase.clear();
}
const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(),
E = RV.end(); I != E; ++I)
if (!I->second.isOverdefined() &&
I->first->getReturnType() != Type::VoidTy) {
Function *F = I->first;
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()));
}
const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals();
for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(),
E = TG.end(); I != E; ++I) {
GlobalVariable *GV = I->first;
assert(!I->second.isOverdefined() &&
"Overdefined values should have been taken out of the map!");
DOUT << "Found that GV '" << GV->getNameStart() << "' is constant!\n";
while (!GV->use_empty()) {
StoreInst *SI = cast<StoreInst>(GV->use_back());
SI->eraseFromParent();
}
M.getGlobalList().erase(GV);
++IPNumGlobalConst;
}
return MadeChanges;
}