LLVM API Documentation
00001 //===- RSProfiling.cpp - Various profiling using random sampling ----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // These passes implement a random sampling based profiling. Different methods 00011 // of choosing when to sample are supported, as well as different types of 00012 // profiling. This is done as two passes. The first is a sequence of profiling 00013 // passes which insert profiling into the program, and remember what they 00014 // inserted. 00015 // 00016 // The second stage duplicates all instructions in a function, ignoring the 00017 // profiling code, then connects the two versions togeather at the entry and at 00018 // backedges. At each connection point a choice is made as to whether to jump 00019 // to the profiled code (take a sample) or execute the unprofiled code. 00020 // 00021 // It is highly recommeneded that after this pass one runs mem2reg and adce 00022 // (instcombine load-vn gdce dse also are good to run afterwards) 00023 // 00024 // This design is intended to make the profiling passes independent of the RS 00025 // framework, but any profiling pass that implements the RSProfiling interface 00026 // is compatible with the rs framework (and thus can be sampled) 00027 // 00028 // TODO: obviously the block and function profiling are almost identical to the 00029 // existing ones, so they can be unified (esp since these passes are valid 00030 // without the rs framework). 00031 // TODO: Fix choice code so that frequency is not hard coded 00032 // 00033 //===----------------------------------------------------------------------===// 00034 00035 #include "llvm/Pass.h" 00036 #include "llvm/Module.h" 00037 #include "llvm/Instructions.h" 00038 #include "llvm/Constants.h" 00039 #include "llvm/DerivedTypes.h" 00040 #include "llvm/Transforms/Scalar.h" 00041 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00042 #include "llvm/ADT/Statistic.h" 00043 #include "llvm/Support/CommandLine.h" 00044 #include "llvm/Support/Debug.h" 00045 #include "llvm/Transforms/Instrumentation.h" 00046 //#include "ProfilingUtils.h" 00047 #include "RSProfiling.h" 00048 00049 #include <set> 00050 #include <map> 00051 #include <queue> 00052 #include <list> 00053 #include <iostream> 00054 00055 using namespace llvm; 00056 00057 namespace { 00058 Statistic<> NumBackEdges("bedge", "Number of BackEdges"); 00059 00060 enum RandomMeth { 00061 GBV, GBVO, HOSTCC 00062 }; 00063 00064 cl::opt<RandomMeth> RandomMethod("profile-randomness", 00065 cl::desc("How to randomly choose to profile:"), 00066 cl::values( 00067 clEnumValN(GBV, "global", "global counter"), 00068 clEnumValN(GBVO, "ra_global", 00069 "register allocated global counter"), 00070 clEnumValN(HOSTCC, "rdcc", "cycle counter"), 00071 clEnumValEnd)); 00072 00073 /// NullProfilerRS - The basic profiler that does nothing. It is the default 00074 /// profiler and thus terminates RSProfiler chains. It is useful for 00075 /// measuring framework overhead 00076 class NullProfilerRS : public RSProfilers { 00077 public: 00078 bool isProfiling(Value* v) { 00079 return false; 00080 } 00081 bool runOnModule(Module &M) { 00082 return false; 00083 } 00084 void getAnalysisUsage(AnalysisUsage &AU) const { 00085 AU.setPreservesAll(); 00086 } 00087 }; 00088 00089 static RegisterAnalysisGroup<RSProfilers> A("Profiling passes"); 00090 static RegisterOpt<NullProfilerRS> NP("insert-null-profiling-rs", 00091 "Measure profiling framework overhead"); 00092 static RegisterAnalysisGroup<RSProfilers, NullProfilerRS, true> NPT; 00093 00094 /// Chooser - Something that chooses when to make a sample of the profiled code 00095 class Chooser { 00096 public: 00097 /// ProcessChoicePoint - is called for each basic block inserted to choose 00098 /// between normal and sample code 00099 virtual void ProcessChoicePoint(BasicBlock*) = 0; 00100 /// PrepFunction - is called once per function before other work is done. 00101 /// This gives the opertunity to insert new allocas and such. 00102 virtual void PrepFunction(Function*) = 0; 00103 virtual ~Chooser() {} 00104 }; 00105 00106 //Things that implement sampling policies 00107 //A global value that is read-mod-stored to choose when to sample. 00108 //A sample is taken when the global counter hits 0 00109 class GlobalRandomCounter : public Chooser { 00110 GlobalVariable* Counter; 00111 Value* ResetValue; 00112 const Type* T; 00113 public: 00114 GlobalRandomCounter(Module& M, const Type* t, uint64_t resetval); 00115 virtual ~GlobalRandomCounter(); 00116 virtual void PrepFunction(Function* F); 00117 virtual void ProcessChoicePoint(BasicBlock* bb); 00118 }; 00119 00120 //Same is GRC, but allow register allocation of the global counter 00121 class GlobalRandomCounterOpt : public Chooser { 00122 GlobalVariable* Counter; 00123 Value* ResetValue; 00124 AllocaInst* AI; 00125 const Type* T; 00126 public: 00127 GlobalRandomCounterOpt(Module& M, const Type* t, uint64_t resetval); 00128 virtual ~GlobalRandomCounterOpt(); 00129 virtual void PrepFunction(Function* F); 00130 virtual void ProcessChoicePoint(BasicBlock* bb); 00131 }; 00132 00133 //Use the cycle counter intrinsic as a source of pseudo randomness when 00134 //deciding when to sample. 00135 class CycleCounter : public Chooser { 00136 uint64_t rm; 00137 Function* F; 00138 public: 00139 CycleCounter(Module& m, uint64_t resetmask); 00140 virtual ~CycleCounter(); 00141 virtual void PrepFunction(Function* F); 00142 virtual void ProcessChoicePoint(BasicBlock* bb); 00143 }; 00144 00145 /// ProfilerRS - Insert the random sampling framework 00146 struct ProfilerRS : public FunctionPass { 00147 std::map<Value*, Value*> TransCache; 00148 std::set<BasicBlock*> ChoicePoints; 00149 Chooser* c; 00150 00151 //Translate and duplicate values for the new profile free version of stuff 00152 Value* Translate(Value* v); 00153 //Duplicate an entire function (with out profiling) 00154 void Duplicate(Function& F, RSProfilers& LI); 00155 //Called once for each backedge, handle the insertion of choice points and 00156 //the interconection of the two versions of the code 00157 void ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F); 00158 bool runOnFunction(Function& F); 00159 bool doInitialization(Module &M); 00160 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00161 }; 00162 00163 RegisterOpt<ProfilerRS> X("insert-rs-profiling-framework", 00164 "Insert random sampling instrumentation framework"); 00165 }; 00166 00167 //Local utilities 00168 static void ReplacePhiPred(BasicBlock* btarget, 00169 BasicBlock* bold, BasicBlock* bnew); 00170 00171 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc); 00172 00173 template<class T> 00174 static void recBackEdge(BasicBlock* bb, T& BackEdges, 00175 std::map<BasicBlock*, int>& color, 00176 std::map<BasicBlock*, int>& depth, 00177 std::map<BasicBlock*, int>& finish, 00178 int& time); 00179 00180 //find the back edges and where they go to 00181 template<class T> 00182 static void getBackEdges(Function& F, T& BackEdges); 00183 00184 00185 /////////////////////////////////////// 00186 // Methods of choosing when to profile 00187 /////////////////////////////////////// 00188 00189 GlobalRandomCounter::GlobalRandomCounter(Module& M, const Type* t, 00190 uint64_t resetval) : T(t) { 00191 Counter = new GlobalVariable(T, false, GlobalValue::InternalLinkage, 00192 ConstantUInt::get(T, resetval), 00193 "RandomSteeringCounter", &M); 00194 ResetValue = ConstantUInt::get(T, resetval); 00195 } 00196 00197 GlobalRandomCounter::~GlobalRandomCounter() {} 00198 00199 void GlobalRandomCounter::PrepFunction(Function* F) {} 00200 00201 void GlobalRandomCounter::ProcessChoicePoint(BasicBlock* bb) { 00202 BranchInst* t = cast<BranchInst>(bb->getTerminator()); 00203 00204 //decrement counter 00205 LoadInst* l = new LoadInst(Counter, "counter", t); 00206 00207 SetCondInst* s = new SetCondInst(Instruction::SetEQ, l, 00208 ConstantUInt::get(T, 0), 00209 "countercc", t); 00210 Value* nv = BinaryOperator::createSub(l, ConstantInt::get(T, 1), 00211 "counternew", t); 00212 new StoreInst(nv, Counter, t); 00213 t->setCondition(s); 00214 00215 //reset counter 00216 BasicBlock* oldnext = t->getSuccessor(0); 00217 BasicBlock* resetblock = new BasicBlock("reset", oldnext->getParent(), 00218 oldnext); 00219 TerminatorInst* t2 = new BranchInst(oldnext, resetblock); 00220 t->setSuccessor(0, resetblock); 00221 new StoreInst(ResetValue, Counter, t2); 00222 ReplacePhiPred(oldnext, bb, resetblock); 00223 } 00224 00225 GlobalRandomCounterOpt::GlobalRandomCounterOpt(Module& M, const Type* t, 00226 uint64_t resetval) 00227 : AI(0), T(t) { 00228 Counter = new GlobalVariable(T, false, GlobalValue::InternalLinkage, 00229 ConstantUInt::get(T, resetval), 00230 "RandomSteeringCounter", &M); 00231 ResetValue = ConstantUInt::get(T, resetval); 00232 } 00233 00234 GlobalRandomCounterOpt::~GlobalRandomCounterOpt() {} 00235 00236 void GlobalRandomCounterOpt::PrepFunction(Function* F) { 00237 //make a local temporary to cache the global 00238 BasicBlock& bb = F->getEntryBlock(); 00239 AI = new AllocaInst(T, 0, "localcounter", bb.begin()); 00240 LoadInst* l = new LoadInst(Counter, "counterload", AI->getNext()); 00241 new StoreInst(l, AI, l->getNext()); 00242 00243 //modify all functions and return values to restore the local variable to/from 00244 //the global variable 00245 for(Function::iterator fib = F->begin(), fie = F->end(); 00246 fib != fie; ++fib) 00247 for(BasicBlock::iterator bib = fib->begin(), bie = fib->end(); 00248 bib != bie; ++bib) 00249 if (isa<CallInst>(&*bib)) { 00250 LoadInst* l = new LoadInst(AI, "counter", bib); 00251 new StoreInst(l, Counter, bib); 00252 l = new LoadInst(Counter, "counter", bib->getNext()); 00253 new StoreInst(l, AI, l->getNext()); 00254 } else if (isa<InvokeInst>(&*bib)) { 00255 LoadInst* l = new LoadInst(AI, "counter", bib); 00256 new StoreInst(l, Counter, bib); 00257 00258 BasicBlock* bb = cast<InvokeInst>(&*bib)->getNormalDest(); 00259 Instruction* i = bb->begin(); 00260 while (isa<PHINode>(i)) i = i->getNext(); 00261 l = new LoadInst(Counter, "counter", i); 00262 00263 bb = cast<InvokeInst>(&*bib)->getUnwindDest(); 00264 i = bb->begin(); 00265 while (isa<PHINode>(i)) i = i->getNext(); 00266 l = new LoadInst(Counter, "counter", i); 00267 new StoreInst(l, AI, l->getNext()); 00268 } else if (isa<UnwindInst>(&*bib) || isa<ReturnInst>(&*bib)) { 00269 LoadInst* l = new LoadInst(AI, "counter", bib); 00270 new StoreInst(l, Counter, bib); 00271 } 00272 } 00273 00274 void GlobalRandomCounterOpt::ProcessChoicePoint(BasicBlock* bb) { 00275 BranchInst* t = cast<BranchInst>(bb->getTerminator()); 00276 00277 //decrement counter 00278 LoadInst* l = new LoadInst(AI, "counter", t); 00279 00280 SetCondInst* s = new SetCondInst(Instruction::SetEQ, l, 00281 ConstantUInt::get(T, 0), 00282 "countercc", t); 00283 Value* nv = BinaryOperator::createSub(l, ConstantInt::get(T, 1), 00284 "counternew", t); 00285 new StoreInst(nv, AI, t); 00286 t->setCondition(s); 00287 00288 //reset counter 00289 BasicBlock* oldnext = t->getSuccessor(0); 00290 BasicBlock* resetblock = new BasicBlock("reset", oldnext->getParent(), 00291 oldnext); 00292 TerminatorInst* t2 = new BranchInst(oldnext, resetblock); 00293 t->setSuccessor(0, resetblock); 00294 new StoreInst(ResetValue, AI, t2); 00295 ReplacePhiPred(oldnext, bb, resetblock); 00296 } 00297 00298 00299 CycleCounter::CycleCounter(Module& m, uint64_t resetmask) : rm(resetmask) { 00300 F = m.getOrInsertFunction("llvm.readcyclecounter", Type::ULongTy, NULL); 00301 } 00302 00303 CycleCounter::~CycleCounter() {} 00304 00305 void CycleCounter::PrepFunction(Function* F) {} 00306 00307 void CycleCounter::ProcessChoicePoint(BasicBlock* bb) { 00308 BranchInst* t = cast<BranchInst>(bb->getTerminator()); 00309 00310 CallInst* c = new CallInst(F, "rdcc", t); 00311 BinaryOperator* b = 00312 BinaryOperator::createAnd(c, ConstantUInt::get(Type::ULongTy, rm), 00313 "mrdcc", t); 00314 00315 SetCondInst* s = new SetCondInst(Instruction::SetEQ, b, 00316 ConstantUInt::get(Type::ULongTy, 0), 00317 "mrdccc", t); 00318 t->setCondition(s); 00319 } 00320 00321 /////////////////////////////////////// 00322 // Profiling: 00323 /////////////////////////////////////// 00324 bool RSProfilers_std::isProfiling(Value* v) { 00325 if (profcode.find(v) != profcode.end()) 00326 return true; 00327 //else 00328 RSProfilers& LI = getAnalysis<RSProfilers>(); 00329 return LI.isProfiling(v); 00330 } 00331 00332 void RSProfilers_std::IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum, 00333 GlobalValue *CounterArray) { 00334 // Insert the increment after any alloca or PHI instructions... 00335 BasicBlock::iterator InsertPos = BB->begin(); 00336 while (isa<AllocaInst>(InsertPos) || isa<PHINode>(InsertPos)) 00337 ++InsertPos; 00338 00339 // Create the getelementptr constant expression 00340 std::vector<Constant*> Indices(2); 00341 Indices[0] = Constant::getNullValue(Type::IntTy); 00342 Indices[1] = ConstantSInt::get(Type::IntTy, CounterNum); 00343 Constant *ElementPtr = ConstantExpr::getGetElementPtr(CounterArray, Indices); 00344 00345 // Load, increment and store the value back. 00346 Value *OldVal = new LoadInst(ElementPtr, "OldCounter", InsertPos); 00347 profcode.insert(OldVal); 00348 Value *NewVal = BinaryOperator::createAdd(OldVal, 00349 ConstantInt::get(Type::UIntTy, 1), 00350 "NewCounter", InsertPos); 00351 profcode.insert(NewVal); 00352 profcode.insert(new StoreInst(NewVal, ElementPtr, InsertPos)); 00353 } 00354 00355 void RSProfilers_std::getAnalysisUsage(AnalysisUsage &AU) const { 00356 //grab any outstanding profiler, or get the null one 00357 AU.addRequired<RSProfilers>(); 00358 } 00359 00360 /////////////////////////////////////// 00361 // RS Framework 00362 /////////////////////////////////////// 00363 00364 Value* ProfilerRS::Translate(Value* v) { 00365 if(TransCache[v]) 00366 return TransCache[v]; 00367 00368 if (BasicBlock* bb = dyn_cast<BasicBlock>(v)) { 00369 if (bb == &bb->getParent()->getEntryBlock()) 00370 TransCache[bb] = bb; //don't translate entry block 00371 else 00372 TransCache[bb] = new BasicBlock("dup_" + bb->getName(), bb->getParent(), 00373 NULL); 00374 return TransCache[bb]; 00375 } else if (Instruction* i = dyn_cast<Instruction>(v)) { 00376 //we have already translated this 00377 //do not translate entry block allocas 00378 if(&i->getParent()->getParent()->getEntryBlock() == i->getParent()) { 00379 TransCache[i] = i; 00380 return i; 00381 } else { 00382 //translate this 00383 Instruction* i2 = i->clone(); 00384 if (i->hasName()) 00385 i2->setName("dup_" + i->getName()); 00386 TransCache[i] = i2; 00387 //NumNewInst++; 00388 for (unsigned x = 0; x < i2->getNumOperands(); ++x) 00389 i2->setOperand(x, Translate(i2->getOperand(x))); 00390 return i2; 00391 } 00392 } else if (isa<Function>(v) || isa<Constant>(v) || isa<Argument>(v)) { 00393 TransCache[v] = v; 00394 return v; 00395 } 00396 assert(0 && "Value not handled"); 00397 return 0; 00398 } 00399 00400 void ProfilerRS::Duplicate(Function& F, RSProfilers& LI) 00401 { 00402 //perform a breadth first search, building up a duplicate of the code 00403 std::queue<BasicBlock*> worklist; 00404 std::set<BasicBlock*> seen; 00405 00406 //This loop ensures proper BB order, to help performance 00407 for (Function::iterator fib = F.begin(), fie = F.end(); fib != fie; ++fib) 00408 worklist.push(fib); 00409 while (!worklist.empty()) { 00410 Translate(worklist.front()); 00411 worklist.pop(); 00412 } 00413 00414 //remember than reg2mem created a new entry block we don't want to duplicate 00415 worklist.push(F.getEntryBlock().getTerminator()->getSuccessor(0)); 00416 seen.insert(&F.getEntryBlock()); 00417 00418 while (!worklist.empty()) { 00419 BasicBlock* bb = worklist.front(); 00420 worklist.pop(); 00421 if(seen.find(bb) == seen.end()) { 00422 BasicBlock* bbtarget = cast<BasicBlock>(Translate(bb)); 00423 BasicBlock::InstListType& instlist = bbtarget->getInstList(); 00424 for (BasicBlock::iterator iib = bb->begin(), iie = bb->end(); 00425 iib != iie; ++iib) { 00426 //NumOldInst++; 00427 if (!LI.isProfiling(&*iib)) { 00428 Instruction* i = cast<Instruction>(Translate(iib)); 00429 instlist.insert(bbtarget->end(), i); 00430 } 00431 } 00432 //updated search state; 00433 seen.insert(bb); 00434 TerminatorInst* ti = bb->getTerminator(); 00435 for (unsigned x = 0; x < ti->getNumSuccessors(); ++x) { 00436 BasicBlock* bbs = ti->getSuccessor(x); 00437 if (seen.find(bbs) == seen.end()) { 00438 worklist.push(bbs); 00439 } 00440 } 00441 } 00442 } 00443 } 00444 00445 void ProfilerRS::ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F) { 00446 //given a backedge from B -> A, and translations A' and B', 00447 //a: insert C and C' 00448 //b: add branches in C to A and A' and in C' to A and A' 00449 //c: mod terminators@B, replace A with C 00450 //d: mod terminators@B', replace A' with C' 00451 //e: mod phis@A for pred B to be pred C 00452 // if multiple entries, simplify to one 00453 //f: mod phis@A' for pred B' to be pred C' 00454 // if multiple entries, simplify to one 00455 //g: for all phis@A with pred C using x 00456 // add in edge from C' using x' 00457 // add in edge from C using x in A' 00458 00459 //a: 00460 BasicBlock* bbC = new BasicBlock("choice", &F, src->getNext() ); 00461 //ChoicePoints.insert(bbC); 00462 BasicBlock* bbCp = 00463 new BasicBlock("choice", &F, cast<BasicBlock>(Translate(src))->getNext() ); 00464 ChoicePoints.insert(bbCp); 00465 00466 //b: 00467 new BranchInst(cast<BasicBlock>(Translate(dst)), bbC); 00468 new BranchInst(dst, cast<BasicBlock>(Translate(dst)), 00469 ConstantBool::get(true), bbCp); 00470 //c: 00471 { 00472 TerminatorInst* iB = src->getTerminator(); 00473 for (unsigned x = 0; x < iB->getNumSuccessors(); ++x) 00474 if (iB->getSuccessor(x) == dst) 00475 iB->setSuccessor(x, bbC); 00476 } 00477 //d: 00478 { 00479 TerminatorInst* iBp = cast<TerminatorInst>(Translate(src->getTerminator())); 00480 for (unsigned x = 0; x < iBp->getNumSuccessors(); ++x) 00481 if (iBp->getSuccessor(x) == cast<BasicBlock>(Translate(dst))) 00482 iBp->setSuccessor(x, bbCp); 00483 } 00484 //e: 00485 ReplacePhiPred(dst, src, bbC); 00486 //src could be a switch, in which case we are replacing several edges with one 00487 //thus collapse those edges int the Phi 00488 CollapsePhi(dst, bbC); 00489 //f: 00490 ReplacePhiPred(cast<BasicBlock>(Translate(dst)), 00491 cast<BasicBlock>(Translate(src)),bbCp); 00492 CollapsePhi(cast<BasicBlock>(Translate(dst)), bbCp); 00493 //g: 00494 for(BasicBlock::iterator ib = dst->begin(), ie = dst->end(); ib != ie; 00495 ++ib) 00496 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) { 00497 for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x) 00498 if(bbC == phi->getIncomingBlock(x)) { 00499 phi->addIncoming(Translate(phi->getIncomingValue(x)), bbCp); 00500 cast<PHINode>(Translate(phi))->addIncoming(phi->getIncomingValue(x), 00501 bbC); 00502 } 00503 phi->removeIncomingValue(bbC); 00504 } 00505 } 00506 00507 bool ProfilerRS::runOnFunction(Function& F) { 00508 if (!F.isExternal()) { 00509 std::set<std::pair<BasicBlock*, BasicBlock*> > BackEdges; 00510 RSProfilers& LI = getAnalysis<RSProfilers>(); 00511 00512 getBackEdges(F, BackEdges); 00513 Duplicate(F, LI); 00514 //assume that stuff worked. now connect the duplicated basic blocks 00515 //with the originals in such a way as to preserve ssa. yuk! 00516 for (std::set<std::pair<BasicBlock*, BasicBlock*> >::iterator 00517 ib = BackEdges.begin(), ie = BackEdges.end(); ib != ie; ++ib) 00518 ProcessBackEdge(ib->first, ib->second, F); 00519 00520 //oh, and add the edge from the reg2mem created entry node to the 00521 //duplicated second node 00522 TerminatorInst* T = F.getEntryBlock().getTerminator(); 00523 ReplaceInstWithInst(T, new BranchInst(T->getSuccessor(0), 00524 cast<BasicBlock>(Translate(T->getSuccessor(0))), 00525 ConstantBool::get(true))); 00526 00527 //do whatever is needed now that the function is duplicated 00528 c->PrepFunction(&F); 00529 00530 //add entry node to choice points 00531 ChoicePoints.insert(&F.getEntryBlock()); 00532 00533 for (std::set<BasicBlock*>::iterator 00534 ii = ChoicePoints.begin(), ie = ChoicePoints.end(); ii != ie; ++ii) 00535 c->ProcessChoicePoint(*ii); 00536 00537 ChoicePoints.clear(); 00538 TransCache.clear(); 00539 00540 return true; 00541 } 00542 return false; 00543 } 00544 00545 bool ProfilerRS::doInitialization(Module &M) { 00546 switch (RandomMethod) { 00547 case GBV: 00548 c = new GlobalRandomCounter(M, Type::UIntTy, (1 << 14) - 1); 00549 break; 00550 case GBVO: 00551 c = new GlobalRandomCounterOpt(M, Type::UIntTy, (1 << 14) - 1); 00552 break; 00553 case HOSTCC: 00554 c = new CycleCounter(M, (1 << 14) - 1); 00555 break; 00556 }; 00557 return true; 00558 } 00559 00560 void ProfilerRS::getAnalysisUsage(AnalysisUsage &AU) const { 00561 AU.addRequired<RSProfilers>(); 00562 AU.addRequiredID(DemoteRegisterToMemoryID); 00563 } 00564 00565 /////////////////////////////////////// 00566 // Utilities: 00567 /////////////////////////////////////// 00568 static void ReplacePhiPred(BasicBlock* btarget, 00569 BasicBlock* bold, BasicBlock* bnew) { 00570 for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end(); 00571 ib != ie; ++ib) 00572 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) { 00573 for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x) 00574 if(bold == phi->getIncomingBlock(x)) 00575 phi->setIncomingBlock(x, bnew); 00576 } 00577 } 00578 00579 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc) { 00580 for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end(); 00581 ib != ie; ++ib) 00582 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) { 00583 unsigned total = phi->getNumIncomingValues(); 00584 std::map<BasicBlock*, Value*> counter; 00585 for(unsigned i = 0; i < phi->getNumIncomingValues(); ) { 00586 if (counter[phi->getIncomingBlock(i)]) { 00587 assert(phi->getIncomingValue(i) == counter[phi->getIncomingBlock(i)]); 00588 phi->removeIncomingValue(i, false); 00589 } else { 00590 counter[phi->getIncomingBlock(i)] = phi->getIncomingValue(i); 00591 ++i; 00592 } 00593 } 00594 } 00595 } 00596 00597 template<class T> 00598 static void recBackEdge(BasicBlock* bb, T& BackEdges, 00599 std::map<BasicBlock*, int>& color, 00600 std::map<BasicBlock*, int>& depth, 00601 std::map<BasicBlock*, int>& finish, 00602 int& time) 00603 { 00604 color[bb] = 1; 00605 ++time; 00606 depth[bb] = time; 00607 TerminatorInst* t= bb->getTerminator(); 00608 for(unsigned i = 0; i < t->getNumSuccessors(); ++i) { 00609 BasicBlock* bbnew = t->getSuccessor(i); 00610 if (color[bbnew] == 0) 00611 recBackEdge(bbnew, BackEdges, color, depth, finish, time); 00612 else if (color[bbnew] == 1) { 00613 BackEdges.insert(std::make_pair(bb, bbnew)); 00614 //NumBackEdges++; 00615 } 00616 } 00617 color[bb] = 2; 00618 ++time; 00619 finish[bb] = time; 00620 } 00621 00622 00623 00624 //find the back edges and where they go to 00625 template<class T> 00626 static void getBackEdges(Function& F, T& BackEdges) { 00627 std::map<BasicBlock*, int> color; 00628 std::map<BasicBlock*, int> depth; 00629 std::map<BasicBlock*, int> finish; 00630 int time = 0; 00631 recBackEdge(&F.getEntryBlock(), BackEdges, color, depth, finish, time); 00632 DEBUG(std::cerr << F.getName() << " " << BackEdges.size() << "\n"); 00633 } 00634 00635 00636 //Creation functions 00637 ModulePass* llvm::createNullProfilerRSPass() { 00638 return new NullProfilerRS(); 00639 } 00640 00641 FunctionPass* llvm::createRSProfilingPass() { 00642 return new ProfilerRS(); 00643 }