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