LLVM API Documentation

SSI.cpp

Go to the documentation of this file.
00001 //===------------------- SSI.cpp - Creates SSI Representation -------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass converts a list of variables to the Static Single Information
00011 // form. This is a program representation described by Scott Ananian in his
00012 // Master Thesis: "The Static Single Information Form (1999)".
00013 // We are building an on-demand representation, that is, we do not convert
00014 // every single variable in the target function to SSI form. Rather, we receive
00015 // a list of target variables that must be converted. We also do not
00016 // completely convert a target variable to the SSI format. Instead, we only
00017 // change the variable in the points where new information can be attached
00018 // to its live range, that is, at branch points.
00019 //
00020 //===----------------------------------------------------------------------===//
00021 
00022 #define DEBUG_TYPE "ssi"
00023 
00024 #include "llvm/Transforms/Scalar.h"
00025 #include "llvm/Transforms/Utils/SSI.h"
00026 #include "llvm/ADT/Statistic.h"
00027 #include "llvm/Analysis/Dominators.h"
00028 
00029 using namespace llvm;
00030 
00031 static const std::string SSI_PHI = "SSI_phi";
00032 static const std::string SSI_SIG = "SSI_sigma";
00033 
00034 static const unsigned UNSIGNED_INFINITE = ~0U;
00035 
00036 STATISTIC(NumSigmaInserted, "Number of sigma functions inserted");
00037 STATISTIC(NumPhiInserted, "Number of phi functions inserted");
00038 
00039 void SSI::getAnalysisUsage(AnalysisUsage &AU) const {
00040   AU.addRequired<DominanceFrontier>();
00041   AU.addRequired<DominatorTree>();
00042   AU.setPreservesCFG();
00043 }
00044 
00045 bool SSI::runOnFunction(Function &F) {
00046   DT_ = &getAnalysis<DominatorTree>();
00047   return false;
00048 }
00049 
00050 /// This methods creates the SSI representation for the list of values
00051 /// received. It will only create SSI representation if a value is used
00052 /// in a to decide a branch. Repeated values are created only once.
00053 ///
00054 void SSI::createSSI(SmallVectorImpl<Instruction *> &value) {
00055   init(value);
00056 
00057   for (unsigned i = 0; i < num_values; ++i) {
00058     if (created.insert(value[i])) {
00059       needConstruction[i] = true;
00060     }
00061   }
00062   insertSigmaFunctions(value);
00063 
00064   // Test if there is a need to transform to SSI
00065   if (needConstruction.any()) {
00066     insertPhiFunctions(value);
00067     renameInit(value);
00068     rename(DT_->getRoot());
00069     fixPhis();
00070   }
00071 
00072   clean();
00073 }
00074 
00075 /// Insert sigma functions (a sigma function is a phi function with one
00076 /// operator)
00077 ///
00078 void SSI::insertSigmaFunctions(SmallVectorImpl<Instruction *> &value) {
00079   for (unsigned i = 0; i < num_values; ++i) {
00080     if (!needConstruction[i])
00081       continue;
00082 
00083     bool need = false;
00084     for (Value::use_iterator begin = value[i]->use_begin(), end =
00085          value[i]->use_end(); begin != end; ++begin) {
00086       // Test if the Use of the Value is in a comparator
00087       CmpInst *CI = dyn_cast<CmpInst>(begin);
00088       if (CI && isUsedInTerminator(CI)) {
00089         // Basic Block of the Instruction
00090         BasicBlock *BB = CI->getParent();
00091         // Last Instruction of the Basic Block
00092         const TerminatorInst *TI = BB->getTerminator();
00093 
00094         for (unsigned j = 0, e = TI->getNumSuccessors(); j < e; ++j) {
00095           // Next Basic Block
00096           BasicBlock *BB_next = TI->getSuccessor(j);
00097           if (BB_next != BB &&
00098               BB_next->getSinglePredecessor() != NULL &&
00099               dominateAny(BB_next, value[i])) {
00100             PHINode *PN = PHINode::Create(
00101                 value[i]->getType(), SSI_SIG, BB_next->begin());
00102             PN->addIncoming(value[i], BB);
00103             sigmas.insert(std::make_pair(PN, i));
00104             created.insert(PN);
00105             need = true;
00106             defsites[i].push_back(BB_next);
00107             ++NumSigmaInserted;
00108           }
00109         }
00110       }
00111     }
00112     needConstruction[i] = need;
00113   }
00114 }
00115 
00116 /// Insert phi functions when necessary
00117 ///
00118 void SSI::insertPhiFunctions(SmallVectorImpl<Instruction *> &value) {
00119   DominanceFrontier *DF = &getAnalysis<DominanceFrontier>();
00120   for (unsigned i = 0; i < num_values; ++i) {
00121     // Test if there were any sigmas for this variable
00122     if (needConstruction[i]) {
00123 
00124       SmallPtrSet<BasicBlock *, 16> BB_visited;
00125 
00126       // Insert phi functions if there is any sigma function
00127       while (!defsites[i].empty()) {
00128 
00129         BasicBlock *BB = defsites[i].back();
00130 
00131         defsites[i].pop_back();
00132         DominanceFrontier::iterator DF_BB = DF->find(BB);
00133 
00134         // The BB is unreachable. Skip it.
00135         if (DF_BB == DF->end())
00136           continue; 
00137 
00138         // Iterates through all the dominance frontier of BB
00139         for (std::set<BasicBlock *>::iterator DF_BB_begin =
00140              DF_BB->second.begin(), DF_BB_end = DF_BB->second.end();
00141              DF_BB_begin != DF_BB_end; ++DF_BB_begin) {
00142           BasicBlock *BB_dominated = *DF_BB_begin;
00143 
00144           // Test if has not yet visited this node and if the
00145           // original definition dominates this node
00146           if (BB_visited.insert(BB_dominated) &&
00147               DT_->properlyDominates(value_original[i], BB_dominated) &&
00148               dominateAny(BB_dominated, value[i])) {
00149             PHINode *PN = PHINode::Create(
00150                 value[i]->getType(), SSI_PHI, BB_dominated->begin());
00151             phis.insert(std::make_pair(PN, i));
00152             created.insert(PN);
00153 
00154             defsites[i].push_back(BB_dominated);
00155             ++NumPhiInserted;
00156           }
00157         }
00158       }
00159       BB_visited.clear();
00160     }
00161   }
00162 }
00163 
00164 /// Some initialization for the rename part
00165 ///
00166 void SSI::renameInit(SmallVectorImpl<Instruction *> &value) {
00167   value_stack.resize(num_values);
00168   for (unsigned i = 0; i < num_values; ++i) {
00169     value_stack[i].push_back(value[i]);
00170   }
00171 }
00172 
00173 /// Renames all variables in the specified BasicBlock.
00174 /// Only variables that need to be rename will be.
00175 ///
00176 void SSI::rename(BasicBlock *BB) {
00177   BitVector *defined = new BitVector(num_values, false);
00178 
00179   // Iterate through instructions and make appropriate renaming.
00180   // For SSI_PHI (b = PHI()), store b at value_stack as a new
00181   // definition of the variable it represents.
00182   // For SSI_SIG (b = PHI(a)), substitute a with the current
00183   // value of a, present in the value_stack.
00184   // Then store bin the value_stack as the new definition of a.
00185   // For all other instructions (b = OP(a, c, d, ...)), we need to substitute
00186   // all operands with its current value, present in value_stack.
00187   for (BasicBlock::iterator begin = BB->begin(), end = BB->end();
00188        begin != end; ++begin) {
00189     Instruction *I = begin;
00190     if (PHINode *PN = dyn_cast<PHINode>(I)) { // Treat PHI functions
00191       int position;
00192 
00193       // Treat SSI_PHI
00194       if ((position = getPositionPhi(PN)) != -1) {
00195         value_stack[position].push_back(PN);
00196         (*defined)[position] = true;
00197       }
00198 
00199       // Treat SSI_SIG
00200       else if ((position = getPositionSigma(PN)) != -1) {
00201         substituteUse(I);
00202         value_stack[position].push_back(PN);
00203         (*defined)[position] = true;
00204       }
00205 
00206       // Treat all other PHI functions
00207       else {
00208         substituteUse(I);
00209       }
00210     }
00211 
00212     // Treat all other functions
00213     else {
00214       substituteUse(I);
00215     }
00216   }
00217 
00218   // This loop iterates in all BasicBlocks that are successors of the current
00219   // BasicBlock. For each SSI_PHI instruction found, insert an operand.
00220   // This operand is the current operand in value_stack for the variable
00221   // in "position". And the BasicBlock this operand represents is the current
00222   // BasicBlock.
00223   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) {
00224     BasicBlock *BB_succ = *SI;
00225 
00226     for (BasicBlock::iterator begin = BB_succ->begin(),
00227          notPhi = BB_succ->getFirstNonPHI(); begin != *notPhi; ++begin) {
00228       Instruction *I = begin;
00229       PHINode *PN = dyn_cast<PHINode>(I);
00230       int position;
00231       if (PN && ((position = getPositionPhi(PN)) != -1)) {
00232         PN->addIncoming(value_stack[position].back(), BB);
00233       }
00234     }
00235   }
00236 
00237   // This loop calls rename on all children from this block. This time children
00238   // refers to a successor block in the dominance tree.
00239   DomTreeNode *DTN = DT_->getNode(BB);
00240   for (DomTreeNode::iterator begin = DTN->begin(), end = DTN->end();
00241        begin != end; ++begin) {
00242     DomTreeNodeBase<BasicBlock> *DTN_children = *begin;
00243     BasicBlock *BB_children = DTN_children->getBlock();
00244     rename(BB_children);
00245   }
00246 
00247   // Now we remove all inserted definitions of a variable from the top of
00248   // the stack leaving the previous one as the top.
00249   if (defined->any()) {
00250     for (unsigned i = 0; i < num_values; ++i) {
00251       if ((*defined)[i]) {
00252         value_stack[i].pop_back();
00253       }
00254     }
00255   }
00256 
00257   delete defined;
00258 }
00259 
00260 /// Substitute any use in this instruction for the last definition of
00261 /// the variable
00262 ///
00263 void SSI::substituteUse(Instruction *I) {
00264   for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
00265     Value *operand = I->getOperand(i);
00266     for (unsigned j = 0; j < num_values; ++j) {
00267       if (operand == value_stack[j].front() &&
00268           I != value_stack[j].back()) {
00269         PHINode *PN_I = dyn_cast<PHINode>(I);
00270         PHINode *PN_vs = dyn_cast<PHINode>(value_stack[j].back());
00271 
00272         // If a phi created in a BasicBlock is used as an operand of another
00273         // created in the same BasicBlock, this step marks this second phi,
00274         // to fix this issue later. It cannot be fixed now, because the
00275         // operands of the first phi are not final yet.
00276         if (PN_I && PN_vs &&
00277             value_stack[j].back()->getParent() == I->getParent()) {
00278 
00279           phisToFix.insert(PN_I);
00280         }
00281 
00282         I->setOperand(i, value_stack[j].back());
00283         break;
00284       }
00285     }
00286   }
00287 }
00288 
00289 /// Test if the BasicBlock BB dominates any use or definition of value.
00290 /// If it dominates a phi instruction that is on the same BasicBlock,
00291 /// that does not count.
00292 ///
00293 bool SSI::dominateAny(BasicBlock *BB, Instruction *value) {
00294   for (Value::use_iterator begin = value->use_begin(),
00295        end = value->use_end(); begin != end; ++begin) {
00296     Instruction *I = cast<Instruction>(*begin);
00297     BasicBlock *BB_father = I->getParent();
00298     if (BB == BB_father && isa<PHINode>(I))
00299       continue;
00300     if (DT_->dominates(BB, BB_father)) {
00301       return true;
00302     }
00303   }
00304   return false;
00305 }
00306 
00307 /// When there is a phi node that is created in a BasicBlock and it is used
00308 /// as an operand of another phi function used in the same BasicBlock,
00309 /// LLVM looks this as an error. So on the second phi, the first phi is called
00310 /// P and the BasicBlock it incomes is B. This P will be replaced by the value
00311 /// it has for BasicBlock B. It also includes undef values for predecessors
00312 /// that were not included in the phi.
00313 ///
00314 void SSI::fixPhis() {
00315   for (SmallPtrSet<PHINode *, 1>::iterator begin = phisToFix.begin(),
00316        end = phisToFix.end(); begin != end; ++begin) {
00317     PHINode *PN = *begin;
00318     for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
00319       PHINode *PN_father = dyn_cast<PHINode>(PN->getIncomingValue(i));
00320       if (PN_father && PN->getParent() == PN_father->getParent() &&
00321           !DT_->dominates(PN->getParent(), PN->getIncomingBlock(i))) {
00322         BasicBlock *BB = PN->getIncomingBlock(i);
00323         int pos = PN_father->getBasicBlockIndex(BB);
00324         PN->setIncomingValue(i, PN_father->getIncomingValue(pos));
00325       }
00326     }
00327   }
00328 
00329   for (DenseMapIterator<PHINode *, unsigned> begin = phis.begin(),
00330        end = phis.end(); begin != end; ++begin) {
00331     PHINode *PN = begin->first;
00332     BasicBlock *BB = PN->getParent();
00333     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
00334     SmallVector<BasicBlock*, 8> Preds(PI, PE);
00335     for (unsigned size = Preds.size();
00336          PI != PE && PN->getNumIncomingValues() != size; ++PI) {
00337       bool found = false;
00338       for (unsigned i = 0, pn_end = PN->getNumIncomingValues();
00339            i < pn_end; ++i) {
00340         if (PN->getIncomingBlock(i) == *PI) {
00341           found = true;
00342           break;
00343         }
00344       }
00345       if (!found) {
00346         PN->addIncoming(UndefValue::get(PN->getType()), *PI);
00347       }
00348     }
00349   }
00350 }
00351 
00352 /// Return which variable (position on the vector of variables) this phi
00353 /// represents on the phis list.
00354 ///
00355 unsigned SSI::getPositionPhi(PHINode *PN) {
00356   DenseMap<PHINode *, unsigned>::iterator val = phis.find(PN);
00357   if (val == phis.end())
00358     return UNSIGNED_INFINITE;
00359   else
00360     return val->second;
00361 }
00362 
00363 /// Return which variable (position on the vector of variables) this phi
00364 /// represents on the sigmas list.
00365 ///
00366 unsigned SSI::getPositionSigma(PHINode *PN) {
00367   DenseMap<PHINode *, unsigned>::iterator val = sigmas.find(PN);
00368   if (val == sigmas.end())
00369     return UNSIGNED_INFINITE;
00370   else
00371     return val->second;
00372 }
00373 
00374 /// Return true if the the Comparison Instruction is an operator
00375 /// of the Terminator instruction of its Basic Block.
00376 ///
00377 unsigned SSI::isUsedInTerminator(CmpInst *CI) {
00378   TerminatorInst *TI = CI->getParent()->getTerminator();
00379   if (TI->getNumOperands() == 0) {
00380     return false;
00381   } else if (CI == TI->getOperand(0)) {
00382     return true;
00383   } else {
00384     return false;
00385   }
00386 }
00387 
00388 /// Initializes
00389 ///
00390 void SSI::init(SmallVectorImpl<Instruction *> &value) {
00391   num_values = value.size();
00392   needConstruction.resize(num_values, false);
00393 
00394   value_original.resize(num_values);
00395   defsites.resize(num_values);
00396 
00397   for (unsigned i = 0; i < num_values; ++i) {
00398     value_original[i] = value[i]->getParent();
00399     defsites[i].push_back(value_original[i]);
00400   }
00401 }
00402 
00403 /// Clean all used resources in this creation of SSI
00404 ///
00405 void SSI::clean() {
00406   for (unsigned i = 0; i < num_values; ++i) {
00407     defsites[i].clear();
00408     if (i < value_stack.size())
00409       value_stack[i].clear();
00410   }
00411 
00412   phis.clear();
00413   sigmas.clear();
00414   phisToFix.clear();
00415 
00416   defsites.clear();
00417   value_stack.clear();
00418   value_original.clear();
00419   needConstruction.clear();
00420 }
00421 
00422 /// createSSIPass - The public interface to this file...
00423 ///
00424 FunctionPass *llvm::createSSIPass() { return new SSI(); }
00425 
00426 char SSI::ID = 0;
00427 static RegisterPass<SSI> X("ssi", "Static Single Information Construction");
00428 
00429 /// SSIEverything - A pass that runs createSSI on every non-void variable,
00430 /// intended for debugging.
00431 namespace {
00432   struct VISIBILITY_HIDDEN SSIEverything : public FunctionPass {
00433     static char ID; // Pass identification, replacement for typeid
00434     SSIEverything() : FunctionPass(&ID) {}
00435 
00436     bool runOnFunction(Function &F);
00437 
00438     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00439       AU.addRequired<SSI>();
00440     }
00441   };
00442 }
00443 
00444 bool SSIEverything::runOnFunction(Function &F) {
00445   SmallVector<Instruction *, 16> Insts;
00446   SSI &ssi = getAnalysis<SSI>();
00447 
00448   if (F.isDeclaration() || F.isIntrinsic()) return false;
00449 
00450   for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B)
00451     for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I)
00452       if (I->getType() != Type::getVoidTy(F.getContext()))
00453         Insts.push_back(I);
00454 
00455   ssi.createSSI(Insts);
00456   return true;
00457 }
00458 
00459 /// createSSIEverythingPass - The public interface to this file...
00460 ///
00461 FunctionPass *llvm::createSSIEverythingPass() { return new SSIEverything(); }
00462 
00463 char SSIEverything::ID = 0;
00464 static RegisterPass<SSIEverything>
00465 Y("ssi-everything", "Static Single Information Construction");