#define DEBUG_TYPE "ssi"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/SSI.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Dominators.h"
using namespace llvm;
static const std::string SSI_PHI = "SSI_phi";
static const std::string SSI_SIG = "SSI_sigma";
STATISTIC(NumSigmaInserted, "Number of sigma functions inserted");
STATISTIC(NumPhiInserted, "Number of phi functions inserted");
void SSI::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequiredTransitive<DominanceFrontier>();
AU.addRequiredTransitive<DominatorTree>();
AU.setPreservesAll();
}
bool SSI::runOnFunction(Function &F) {
DT_ = &getAnalysis<DominatorTree>();
return false;
}
void SSI::createSSI(SmallVectorImpl<Instruction *> &value) {
init(value);
SmallPtrSet<Instruction*, 4> needConstruction;
for (SmallVectorImpl<Instruction*>::iterator I = value.begin(),
E = value.end(); I != E; ++I)
if (created.insert(*I))
needConstruction.insert(*I);
insertSigmaFunctions(needConstruction);
if (!needConstruction.empty()) {
insertPhiFunctions(needConstruction);
renameInit(needConstruction);
rename(DT_->getRoot());
fixPhis();
}
clean();
}
void SSI::insertSigmaFunctions(SmallPtrSet<Instruction*, 4> &value) {
for (SmallPtrSet<Instruction*, 4>::iterator I = value.begin(),
E = value.end(); I != E; ++I) {
for (Value::use_iterator begin = (*I)->use_begin(),
end = (*I)->use_end(); begin != end; ++begin) {
if (CmpInst *CI = dyn_cast<CmpInst>(begin)) {
for (Value::use_iterator begin_ci = CI->use_begin(),
end_ci = CI->use_end(); begin_ci != end_ci; ++begin_ci) {
if (TerminatorInst *TI = dyn_cast<TerminatorInst>(begin_ci)) {
insertSigma(TI, *I);
}
}
}
}
}
}
void SSI::insertSigma(TerminatorInst *TI, Instruction *I) {
BasicBlock *BB = TI->getParent();
for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
BasicBlock *BB_next = TI->getSuccessor(i);
if (BB_next != BB &&
BB_next->getSinglePredecessor() != NULL &&
dominateAny(BB_next, I)) {
PHINode *PN = PHINode::Create(I->getType(), SSI_SIG, BB_next->begin());
PN->addIncoming(I, BB);
sigmas[PN] = I;
created.insert(PN);
defsites[I].push_back(BB_next);
++NumSigmaInserted;
}
}
}
void SSI::insertPhiFunctions(SmallPtrSet<Instruction*, 4> &value) {
DominanceFrontier *DF = &getAnalysis<DominanceFrontier>();
for (SmallPtrSet<Instruction*, 4>::iterator I = value.begin(),
E = value.end(); I != E; ++I) {
SmallPtrSet<BasicBlock *, 16> BB_visited;
while (!defsites[*I].empty()) {
BasicBlock *BB = defsites[*I].back();
defsites[*I].pop_back();
DominanceFrontier::iterator DF_BB = DF->find(BB);
if (DF_BB == DF->end())
continue;
for (std::set<BasicBlock *>::iterator DF_BB_begin =
DF_BB->second.begin(), DF_BB_end = DF_BB->second.end();
DF_BB_begin != DF_BB_end; ++DF_BB_begin) {
BasicBlock *BB_dominated = *DF_BB_begin;
if (BB_visited.insert(BB_dominated) &&
DT_->properlyDominates(value_original[*I], BB_dominated) &&
dominateAny(BB_dominated, *I)) {
PHINode *PN = PHINode::Create(
(*I)->getType(), SSI_PHI, BB_dominated->begin());
phis.insert(std::make_pair(PN, *I));
created.insert(PN);
defsites[*I].push_back(BB_dominated);
++NumPhiInserted;
}
}
}
BB_visited.clear();
}
}
void SSI::renameInit(SmallPtrSet<Instruction*, 4> &value) {
for (SmallPtrSet<Instruction*, 4>::iterator I = value.begin(),
E = value.end(); I != E; ++I)
value_stack[*I].push_back(*I);
}
void SSI::rename(BasicBlock *BB) {
SmallPtrSet<Instruction*, 8> defined;
for (BasicBlock::iterator begin = BB->begin(), end = BB->end();
begin != end; ++begin) {
Instruction *I = begin;
if (PHINode *PN = dyn_cast<PHINode>(I)) { Instruction* position;
if ((position = getPositionPhi(PN))) {
value_stack[position].push_back(PN);
defined.insert(position);
} else if ((position = getPositionSigma(PN))) {
substituteUse(I);
value_stack[position].push_back(PN);
defined.insert(position);
}
else {
substituteUse(I);
}
}
else {
substituteUse(I);
}
}
for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) {
BasicBlock *BB_succ = *SI;
for (BasicBlock::iterator begin = BB_succ->begin(),
notPhi = BB_succ->getFirstNonPHI(); begin != *notPhi; ++begin) {
Instruction *I = begin;
PHINode *PN = dyn_cast<PHINode>(I);
Instruction* position;
if (PN && ((position = getPositionPhi(PN)))) {
PN->addIncoming(value_stack[position].back(), BB);
}
}
}
DomTreeNode *DTN = DT_->getNode(BB);
for (DomTreeNode::iterator begin = DTN->begin(), end = DTN->end();
begin != end; ++begin) {
DomTreeNodeBase<BasicBlock> *DTN_children = *begin;
BasicBlock *BB_children = DTN_children->getBlock();
rename(BB_children);
}
for (SmallPtrSet<Instruction*, 8>::iterator DI = defined.begin(),
DE = defined.end(); DI != DE; ++DI)
value_stack[*DI].pop_back();
}
void SSI::substituteUse(Instruction *I) {
for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
Value *operand = I->getOperand(i);
for (DenseMap<Instruction*, SmallVector<Instruction*, 1> >::iterator
VI = value_stack.begin(), VE = value_stack.end(); VI != VE; ++VI) {
if (operand == VI->second.front() &&
I != VI->second.back()) {
PHINode *PN_I = dyn_cast<PHINode>(I);
PHINode *PN_vs = dyn_cast<PHINode>(VI->second.back());
if (PN_I && PN_vs &&
VI->second.back()->getParent() == I->getParent()) {
phisToFix.insert(PN_I);
}
I->setOperand(i, VI->second.back());
break;
}
}
}
}
bool SSI::dominateAny(BasicBlock *BB, Instruction *value) {
for (Value::use_iterator begin = value->use_begin(),
end = value->use_end(); begin != end; ++begin) {
Instruction *I = cast<Instruction>(*begin);
BasicBlock *BB_father = I->getParent();
if (BB == BB_father && isa<PHINode>(I))
continue;
if (DT_->dominates(BB, BB_father)) {
return true;
}
}
return false;
}
void SSI::fixPhis() {
for (SmallPtrSet<PHINode *, 1>::iterator begin = phisToFix.begin(),
end = phisToFix.end(); begin != end; ++begin) {
PHINode *PN = *begin;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
PHINode *PN_father = dyn_cast<PHINode>(PN->getIncomingValue(i));
if (PN_father && PN->getParent() == PN_father->getParent() &&
!DT_->dominates(PN->getParent(), PN->getIncomingBlock(i))) {
BasicBlock *BB = PN->getIncomingBlock(i);
int pos = PN_father->getBasicBlockIndex(BB);
PN->setIncomingValue(i, PN_father->getIncomingValue(pos));
}
}
}
for (DenseMapIterator<PHINode *, Instruction*> begin = phis.begin(),
end = phis.end(); begin != end; ++begin) {
PHINode *PN = begin->first;
BasicBlock *BB = PN->getParent();
pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
SmallVector<BasicBlock*, 8> Preds(PI, PE);
for (unsigned size = Preds.size();
PI != PE && PN->getNumIncomingValues() != size; ++PI) {
bool found = false;
for (unsigned i = 0, pn_end = PN->getNumIncomingValues();
i < pn_end; ++i) {
if (PN->getIncomingBlock(i) == *PI) {
found = true;
break;
}
}
if (!found) {
PN->addIncoming(UndefValue::get(PN->getType()), *PI);
}
}
}
}
Instruction* SSI::getPositionPhi(PHINode *PN) {
DenseMap<PHINode *, Instruction*>::iterator val = phis.find(PN);
if (val == phis.end())
return 0;
else
return val->second;
}
Instruction* SSI::getPositionSigma(PHINode *PN) {
DenseMap<PHINode *, Instruction*>::iterator val = sigmas.find(PN);
if (val == sigmas.end())
return 0;
else
return val->second;
}
void SSI::init(SmallVectorImpl<Instruction *> &value) {
for (SmallVectorImpl<Instruction *>::iterator I = value.begin(),
E = value.end(); I != E; ++I) {
value_original[*I] = (*I)->getParent();
defsites[*I].push_back((*I)->getParent());
}
}
void SSI::clean() {
phis.clear();
sigmas.clear();
phisToFix.clear();
defsites.clear();
value_stack.clear();
value_original.clear();
}
FunctionPass *llvm::createSSIPass() { return new SSI(); }
char SSI::ID = 0;
static RegisterPass<SSI> X("ssi", "Static Single Information Construction");
namespace {
struct SSIEverything : public FunctionPass {
static char ID; SSIEverything() : FunctionPass(&ID) {}
bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<SSI>();
}
};
}
bool SSIEverything::runOnFunction(Function &F) {
SmallVector<Instruction *, 16> Insts;
SSI &ssi = getAnalysis<SSI>();
if (F.isDeclaration() || F.isIntrinsic()) return false;
for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B)
for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I)
if (!I->getType()->isVoidTy())
Insts.push_back(I);
ssi.createSSI(Insts);
return true;
}
FunctionPass *llvm::createSSIEverythingPass() { return new SSIEverything(); }
char SSIEverything::ID = 0;
static RegisterPass<SSIEverything>
Y("ssi-everything", "Static Single Information Construction");