X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FSSI.cpp;h=3bb2e8ee691140b88134621494833303c132c973;hb=5fa75b0fa4af290ee4b7180f3e452942b4653aae;hp=4c4dd37ddf754b7ce0f050a16e802827bbe9e5c7;hpb=715029478c0a54cab2c366816d11d712bf51efc5;p=oota-llvm.git diff --git a/lib/Transforms/Utils/SSI.cpp b/lib/Transforms/Utils/SSI.cpp index 4c4dd37ddf7..3bb2e8ee691 100644 --- a/lib/Transforms/Utils/SSI.cpp +++ b/lib/Transforms/Utils/SSI.cpp @@ -23,6 +23,7 @@ #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/SSI.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/Dominators.h" using namespace llvm; @@ -30,11 +31,12 @@ using namespace llvm; static const std::string SSI_PHI = "SSI_phi"; static const std::string SSI_SIG = "SSI_sigma"; -static const unsigned UNSIGNED_INFINITE = ~0U; +STATISTIC(NumSigmaInserted, "Number of sigma functions inserted"); +STATISTIC(NumPhiInserted, "Number of phi functions inserted"); void SSI::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); - AU.addRequired(); + AU.addRequiredTransitive(); + AU.addRequiredTransitive(); AU.setPreservesAll(); } @@ -45,22 +47,23 @@ bool SSI::runOnFunction(Function &F) { /// This methods creates the SSI representation for the list of values /// received. It will only create SSI representation if a value is used -/// in a to decide a branch. Repeated values are created only once. +/// to decide a branch. Repeated values are created only once. /// void SSI::createSSI(SmallVectorImpl &value) { init(value); - for (unsigned i = 0; i < num_values; ++i) { - if (created.insert(value[i])) { - needConstruction[i] = true; - } - } - insertSigmaFunctions(value); + SmallPtrSet needConstruction; + for (SmallVectorImpl::iterator I = value.begin(), + E = value.end(); I != E; ++I) + if (created.insert(*I)) + needConstruction.insert(*I); + + insertSigmaFunctions(needConstruction); // Test if there is a need to transform to SSI - if (needConstruction.any()) { - insertPhiFunctions(value); - renameInit(value); + if (!needConstruction.empty()) { + insertPhiFunctions(needConstruction); + renameInit(needConstruction); rename(DT_->getRoot()); fixPhis(); } @@ -71,100 +74,107 @@ void SSI::createSSI(SmallVectorImpl &value) { /// Insert sigma functions (a sigma function is a phi function with one /// operator) /// -void SSI::insertSigmaFunctions(SmallVectorImpl &value) { - for (unsigned i = 0; i < num_values; ++i) { - if (!needConstruction[i]) - continue; - - bool need = false; - for (Value::use_iterator begin = value[i]->use_begin(), end = - value[i]->use_end(); begin != end; ++begin) { +void SSI::insertSigmaFunctions(SmallPtrSet &value) { + for (SmallPtrSet::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) { // Test if the Use of the Value is in a comparator - CmpInst *CI = dyn_cast(begin); - if (CI && isUsedInTerminator(CI)) { - // Basic Block of the Instruction - BasicBlock *BB = CI->getParent(); - // Last Instruction of the Basic Block - const TerminatorInst *TI = BB->getTerminator(); - - for (unsigned j = 0, e = TI->getNumSuccessors(); j < e; ++j) { - // Next Basic Block - BasicBlock *BB_next = TI->getSuccessor(j); - if (BB_next != BB && - BB_next->getUniquePredecessor() != NULL && - dominateAny(BB_next, value[i])) { - PHINode *PN = PHINode::Create( - value[i]->getType(), SSI_SIG, BB_next->begin()); - PN->addIncoming(value[i], BB); - sigmas.insert(std::make_pair(PN, i)); - created.insert(PN); - need = true; - defsites[i].push_back(BB_next); + if (CmpInst *CI = dyn_cast(begin)) { + // Iterates through all uses of CmpInst + for (Value::use_iterator begin_ci = CI->use_begin(), + end_ci = CI->use_end(); begin_ci != end_ci; ++begin_ci) { + // Test if any use of CmpInst is in a Terminator + if (TerminatorInst *TI = dyn_cast(begin_ci)) { + insertSigma(TI, *I); } } } } - needConstruction[i] = need; + } +} + +/// Inserts Sigma Functions in every BasicBlock successor to Terminator +/// Instruction TI. All inserted Sigma Function are related to Instruction I. +/// +void SSI::insertSigma(TerminatorInst *TI, Instruction *I) { + // Basic Block of the Terminator Instruction + BasicBlock *BB = TI->getParent(); + for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) { + // Next Basic Block + 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; + } } } /// Insert phi functions when necessary /// -void SSI::insertPhiFunctions(SmallVectorImpl &value) { +void SSI::insertPhiFunctions(SmallPtrSet &value) { DominanceFrontier *DF = &getAnalysis(); - for (unsigned i = 0; i < num_values; ++i) { + for (SmallPtrSet::iterator I = value.begin(), + E = value.end(); I != E; ++I) { // Test if there were any sigmas for this variable - if (needConstruction[i]) { - - SmallPtrSet BB_visited; - - // Insert phi functions if there is any sigma function - while (!defsites[i].empty()) { - - BasicBlock *BB = defsites[i].back(); - - defsites[i].pop_back(); - DominanceFrontier::iterator DF_BB = DF->find(BB); - - // Iterates through all the dominance frontier of BB - for (std::set::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; - - // Test if has not yet visited this node and if the - // original definition dominates this node - if (BB_visited.insert(BB_dominated) && - DT_->properlyDominates(value_original[i], BB_dominated) && - dominateAny(BB_dominated, value[i])) { - PHINode *PN = PHINode::Create( - value[i]->getType(), SSI_PHI, BB_dominated->begin()); - phis.insert(std::make_pair(PN, i)); - created.insert(PN); - - defsites[i].push_back(BB_dominated); - } + SmallPtrSet BB_visited; + + // Insert phi functions if there is any sigma function + while (!defsites[*I].empty()) { + + BasicBlock *BB = defsites[*I].back(); + + defsites[*I].pop_back(); + DominanceFrontier::iterator DF_BB = DF->find(BB); + + // The BB is unreachable. Skip it. + if (DF_BB == DF->end()) + continue; + + // Iterates through all the dominance frontier of BB + for (std::set::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; + + // Test if has not yet visited this node and if the + // original definition dominates this node + 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(); } + BB_visited.clear(); } } /// Some initialization for the rename part /// -void SSI::renameInit(SmallVectorImpl &value) { - value_stack.resize(num_values); - for (unsigned i = 0; i < num_values; ++i) { - value_stack[i].push_back(value[i]); - } +void SSI::renameInit(SmallPtrSet &value) { + for (SmallPtrSet::iterator I = value.begin(), + E = value.end(); I != E; ++I) + value_stack[*I].push_back(*I); } /// Renames all variables in the specified BasicBlock. /// Only variables that need to be rename will be. /// void SSI::rename(BasicBlock *BB) { - BitVector *defined = new BitVector(num_values, false); + SmallPtrSet defined; // Iterate through instructions and make appropriate renaming. // For SSI_PHI (b = PHI()), store b at value_stack as a new @@ -178,19 +188,17 @@ void SSI::rename(BasicBlock *BB) { begin != end; ++begin) { Instruction *I = begin; if (PHINode *PN = dyn_cast(I)) { // Treat PHI functions - int position; + Instruction* position; // Treat SSI_PHI - if ((position = getPositionPhi(PN)) != -1) { + if ((position = getPositionPhi(PN))) { value_stack[position].push_back(PN); - (*defined)[position] = true; - } - + defined.insert(position); // Treat SSI_SIG - else if ((position = getPositionSigma(PN)) != -1) { + } else if ((position = getPositionSigma(PN))) { substituteUse(I); value_stack[position].push_back(PN); - (*defined)[position] = true; + defined.insert(position); } // Treat all other PHI functions @@ -216,10 +224,9 @@ void SSI::rename(BasicBlock *BB) { for (BasicBlock::iterator begin = BB_succ->begin(), notPhi = BB_succ->getFirstNonPHI(); begin != *notPhi; ++begin) { Instruction *I = begin; - PHINode *PN; - int position; - if ((PN = dyn_cast(I)) && ((position - = getPositionPhi(PN)) != -1)) { + PHINode *PN = dyn_cast(I); + Instruction* position; + if (PN && ((position = getPositionPhi(PN)))) { PN->addIncoming(value_stack[position].back(), BB); } } @@ -237,13 +244,9 @@ void SSI::rename(BasicBlock *BB) { // Now we remove all inserted definitions of a variable from the top of // the stack leaving the previous one as the top. - if (defined->any()) { - for (unsigned i = 0; i < num_values; ++i) { - if ((*defined)[i]) { - value_stack[i].pop_back(); - } - } - } + for (SmallPtrSet::iterator DI = defined.begin(), + DE = defined.end(); DI != DE; ++DI) + value_stack[*DI].pop_back(); } /// Substitute any use in this instruction for the last definition of @@ -252,23 +255,24 @@ void SSI::rename(BasicBlock *BB) { void SSI::substituteUse(Instruction *I) { for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) { Value *operand = I->getOperand(i); - for (unsigned j = 0; j < num_values; ++j) { - if (operand == value_stack[j].front() && - I != value_stack[j].back()) { + for (DenseMap >::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(I); - PHINode *PN_vs = dyn_cast(value_stack[j].back()); + PHINode *PN_vs = dyn_cast(VI->second.back()); // If a phi created in a BasicBlock is used as an operand of another // created in the same BasicBlock, this step marks this second phi, // to fix this issue later. It cannot be fixed now, because the // operands of the first phi are not final yet. if (PN_I && PN_vs && - value_stack[j].back()->getParent() == I->getParent()) { + VI->second.back()->getParent() == I->getParent()) { phisToFix.insert(PN_I); } - I->setOperand(i, value_stack[j].back()); + I->setOperand(i, VI->second.back()); break; } } @@ -276,12 +280,16 @@ void SSI::substituteUse(Instruction *I) { } /// Test if the BasicBlock BB dominates any use or definition of value. +/// If it dominates a phi instruction that is on the same BasicBlock, +/// that does not count. /// 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(*begin); BasicBlock *BB_father = I->getParent(); + if (BB == BB_father && isa(I)) + continue; if (DT_->dominates(BB, BB_father)) { return true; } @@ -293,31 +301,54 @@ bool SSI::dominateAny(BasicBlock *BB, Instruction *value) { /// as an operand of another phi function used in the same BasicBlock, /// LLVM looks this as an error. So on the second phi, the first phi is called /// P and the BasicBlock it incomes is B. This P will be replaced by the value -/// it has for BasicBlock B. +/// it has for BasicBlock B. It also includes undef values for predecessors +/// that were not included in the phi. /// void SSI::fixPhis() { for (SmallPtrSet::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; - if ((PN_father = dyn_cast(PN->getIncomingValue(i))) && - PN->getParent() == PN_father->getParent()) { + PHINode *PN_father = dyn_cast(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 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 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); + } + } + } } /// Return which variable (position on the vector of variables) this phi /// represents on the phis list. /// -unsigned SSI::getPositionPhi(PHINode *PN) { - DenseMap::iterator val = phis.find(PN); +Instruction* SSI::getPositionPhi(PHINode *PN) { + DenseMap::iterator val = phis.find(PN); if (val == phis.end()) - return UNSIGNED_INFINITE; + return 0; else return val->second; } @@ -325,52 +356,27 @@ unsigned SSI::getPositionPhi(PHINode *PN) { /// Return which variable (position on the vector of variables) this phi /// represents on the sigmas list. /// -unsigned SSI::getPositionSigma(PHINode *PN) { - DenseMap::iterator val = sigmas.find(PN); +Instruction* SSI::getPositionSigma(PHINode *PN) { + DenseMap::iterator val = sigmas.find(PN); if (val == sigmas.end()) - return UNSIGNED_INFINITE; + return 0; else return val->second; } -/// Return true if the the Comparison Instruction is an operator -/// of the Terminator instruction of its Basic Block. -/// -unsigned SSI::isUsedInTerminator(CmpInst *CI) { - TerminatorInst *TI = CI->getParent()->getTerminator(); - if (TI->getNumOperands() == 0) { - return false; - } else if (CI == TI->getOperand(0)) { - return true; - } else { - return false; - } -} - /// Initializes /// void SSI::init(SmallVectorImpl &value) { - num_values = value.size(); - needConstruction.resize(num_values, false); - - value_original.resize(num_values); - defsites.resize(num_values); - - for (unsigned i = 0; i < num_values; ++i) { - value_original[i] = value[i]->getParent(); - defsites[i].push_back(value_original[i]); + for (SmallVectorImpl::iterator I = value.begin(), + E = value.end(); I != E; ++I) { + value_original[*I] = (*I)->getParent(); + defsites[*I].push_back((*I)->getParent()); } } /// Clean all used resources in this creation of SSI /// void SSI::clean() { - for (unsigned i = 0; i < num_values; ++i) { - defsites[i].clear(); - if (i < value_stack.size()) - value_stack[i].clear(); - } - phis.clear(); sigmas.clear(); phisToFix.clear(); @@ -378,7 +384,6 @@ void SSI::clean() { defsites.clear(); value_stack.clear(); value_original.clear(); - needConstruction.clear(); } /// createSSIPass - The public interface to this file... @@ -388,3 +393,40 @@ FunctionPass *llvm::createSSIPass() { return new SSI(); } char SSI::ID = 0; static RegisterPass X("ssi", "Static Single Information Construction"); +/// SSIEverything - A pass that runs createSSI on every non-void variable, +/// intended for debugging. +namespace { + struct VISIBILITY_HIDDEN SSIEverything : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + SSIEverything() : FunctionPass(&ID) {} + + bool runOnFunction(Function &F); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + } + }; +} + +bool SSIEverything::runOnFunction(Function &F) { + SmallVector Insts; + SSI &ssi = getAnalysis(); + + 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() != Type::getVoidTy(F.getContext())) + Insts.push_back(I); + + ssi.createSSI(Insts); + return true; +} + +/// createSSIEverythingPass - The public interface to this file... +/// +FunctionPass *llvm::createSSIEverythingPass() { return new SSIEverything(); } + +char SSIEverything::ID = 0; +static RegisterPass +Y("ssi-everything", "Static Single Information Construction");