LLVM API Documentation
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");