1 //===- RSProfiling.cpp - Various profiling using random sampling ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // These passes implement a random sampling based profiling. Different methods
11 // of choosing when to sample are supported, as well as different types of
12 // profiling. This is done as two passes. The first is a sequence of profiling
13 // passes which insert profiling into the program, and remember what they
16 // The second stage duplicates all instructions in a function, ignoring the
17 // profiling code, then connects the two versions togeather at the entry and at
18 // backedges. At each connection point a choice is made as to whether to jump
19 // to the profiled code (take a sample) or execute the unprofiled code.
21 // It is highly recommended that after this pass one runs mem2reg and adce
22 // (instcombine load-vn gdce dse also are good to run afterwards)
24 // This design is intended to make the profiling passes independent of the RS
25 // framework, but any profiling pass that implements the RSProfiling interface
26 // is compatible with the rs framework (and thus can be sampled)
28 // TODO: obviously the block and function profiling are almost identical to the
29 // existing ones, so they can be unified (esp since these passes are valid
30 // without the rs framework).
31 // TODO: Fix choice code so that frequency is not hard coded
33 //===----------------------------------------------------------------------===//
35 #include "llvm/Pass.h"
36 #include "llvm/LLVMContext.h"
37 #include "llvm/Module.h"
38 #include "llvm/Instructions.h"
39 #include "llvm/Constants.h"
40 #include "llvm/DerivedTypes.h"
41 #include "llvm/Intrinsics.h"
42 #include "llvm/Transforms/Scalar.h"
43 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
44 #include "llvm/Support/CommandLine.h"
45 #include "llvm/Support/Compiler.h"
46 #include "llvm/Support/Debug.h"
47 #include "llvm/Support/ErrorHandling.h"
48 #include "llvm/Transforms/Instrumentation.h"
49 #include "RSProfiling.h"
61 static cl::opt<RandomMeth> RandomMethod("profile-randomness",
62 cl::desc("How to randomly choose to profile:"),
64 clEnumValN(GBV, "global", "global counter"),
65 clEnumValN(GBVO, "ra_global",
66 "register allocated global counter"),
67 clEnumValN(HOSTCC, "rdcc", "cycle counter"),
71 /// NullProfilerRS - The basic profiler that does nothing. It is the default
72 /// profiler and thus terminates RSProfiler chains. It is useful for
73 /// measuring framework overhead
74 class VISIBILITY_HIDDEN NullProfilerRS : public RSProfilers {
76 static char ID; // Pass identification, replacement for typeid
77 bool isProfiling(Value* v) {
80 bool runOnModule(Module &M) {
83 void getAnalysisUsage(AnalysisUsage &AU) const {
89 static RegisterAnalysisGroup<RSProfilers> A("Profiling passes");
90 static RegisterPass<NullProfilerRS> NP("insert-null-profiling-rs",
91 "Measure profiling framework overhead");
92 static RegisterAnalysisGroup<RSProfilers, true> NPT(NP);
95 /// Chooser - Something that chooses when to make a sample of the profiled code
96 class VISIBILITY_HIDDEN Chooser {
98 /// ProcessChoicePoint - is called for each basic block inserted to choose
99 /// between normal and sample code
100 virtual void ProcessChoicePoint(BasicBlock*) = 0;
101 /// PrepFunction - is called once per function before other work is done.
102 /// This gives the opertunity to insert new allocas and such.
103 virtual void PrepFunction(Function*) = 0;
104 virtual ~Chooser() {}
107 //Things that implement sampling policies
108 //A global value that is read-mod-stored to choose when to sample.
109 //A sample is taken when the global counter hits 0
110 class VISIBILITY_HIDDEN GlobalRandomCounter : public Chooser {
111 GlobalVariable* Counter;
113 const IntegerType* T;
115 GlobalRandomCounter(Module& M, const IntegerType* t, uint64_t resetval);
116 virtual ~GlobalRandomCounter();
117 virtual void PrepFunction(Function* F);
118 virtual void ProcessChoicePoint(BasicBlock* bb);
121 //Same is GRC, but allow register allocation of the global counter
122 class VISIBILITY_HIDDEN GlobalRandomCounterOpt : public Chooser {
123 GlobalVariable* Counter;
126 const IntegerType* T;
128 GlobalRandomCounterOpt(Module& M, const IntegerType* t, uint64_t resetval);
129 virtual ~GlobalRandomCounterOpt();
130 virtual void PrepFunction(Function* F);
131 virtual void ProcessChoicePoint(BasicBlock* bb);
134 //Use the cycle counter intrinsic as a source of pseudo randomness when
135 //deciding when to sample.
136 class VISIBILITY_HIDDEN CycleCounter : public Chooser {
140 CycleCounter(Module& m, uint64_t resetmask);
141 virtual ~CycleCounter();
142 virtual void PrepFunction(Function* F);
143 virtual void ProcessChoicePoint(BasicBlock* bb);
146 /// ProfilerRS - Insert the random sampling framework
147 struct VISIBILITY_HIDDEN ProfilerRS : public FunctionPass {
148 static char ID; // Pass identification, replacement for typeid
149 ProfilerRS() : FunctionPass(&ID) {}
151 std::map<Value*, Value*> TransCache;
152 std::set<BasicBlock*> ChoicePoints;
155 //Translate and duplicate values for the new profile free version of stuff
156 Value* Translate(Value* v);
157 //Duplicate an entire function (with out profiling)
158 void Duplicate(Function& F, RSProfilers& LI);
159 //Called once for each backedge, handle the insertion of choice points and
160 //the interconection of the two versions of the code
161 void ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F);
162 bool runOnFunction(Function& F);
163 bool doInitialization(Module &M);
164 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
168 static RegisterPass<ProfilerRS>
169 X("insert-rs-profiling-framework",
170 "Insert random sampling instrumentation framework");
172 char RSProfilers::ID = 0;
173 char NullProfilerRS::ID = 0;
174 char ProfilerRS::ID = 0;
177 static void ReplacePhiPred(BasicBlock* btarget,
178 BasicBlock* bold, BasicBlock* bnew);
180 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc);
183 static void recBackEdge(BasicBlock* bb, T& BackEdges,
184 std::map<BasicBlock*, int>& color,
185 std::map<BasicBlock*, int>& depth,
186 std::map<BasicBlock*, int>& finish,
189 //find the back edges and where they go to
191 static void getBackEdges(Function& F, T& BackEdges);
194 ///////////////////////////////////////
195 // Methods of choosing when to profile
196 ///////////////////////////////////////
198 GlobalRandomCounter::GlobalRandomCounter(Module& M, const IntegerType* t,
199 uint64_t resetval) : T(t) {
200 ConstantInt* Init = M.getContext().getConstantInt(T, resetval);
202 Counter = new GlobalVariable(M, T, false, GlobalValue::InternalLinkage,
203 Init, "RandomSteeringCounter");
206 GlobalRandomCounter::~GlobalRandomCounter() {}
208 void GlobalRandomCounter::PrepFunction(Function* F) {}
210 void GlobalRandomCounter::ProcessChoicePoint(BasicBlock* bb) {
211 BranchInst* t = cast<BranchInst>(bb->getTerminator());
212 LLVMContext *Context = bb->getContext();
215 LoadInst* l = new LoadInst(Counter, "counter", t);
217 ICmpInst* s = new ICmpInst(t, ICmpInst::ICMP_EQ, l,
218 Context->getConstantInt(T, 0),
221 Value* nv = BinaryOperator::CreateSub(l, Context->getConstantInt(T, 1),
223 new StoreInst(nv, Counter, t);
227 BasicBlock* oldnext = t->getSuccessor(0);
228 BasicBlock* resetblock = BasicBlock::Create("reset", oldnext->getParent(),
230 TerminatorInst* t2 = BranchInst::Create(oldnext, resetblock);
231 t->setSuccessor(0, resetblock);
232 new StoreInst(ResetValue, Counter, t2);
233 ReplacePhiPred(oldnext, bb, resetblock);
236 GlobalRandomCounterOpt::GlobalRandomCounterOpt(Module& M, const IntegerType* t,
239 ConstantInt* Init = M.getContext().getConstantInt(T, resetval);
241 Counter = new GlobalVariable(M, T, false, GlobalValue::InternalLinkage,
242 Init, "RandomSteeringCounter");
245 GlobalRandomCounterOpt::~GlobalRandomCounterOpt() {}
247 void GlobalRandomCounterOpt::PrepFunction(Function* F) {
248 //make a local temporary to cache the global
249 BasicBlock& bb = F->getEntryBlock();
250 BasicBlock::iterator InsertPt = bb.begin();
251 AI = new AllocaInst(T, 0, "localcounter", InsertPt);
252 LoadInst* l = new LoadInst(Counter, "counterload", InsertPt);
253 new StoreInst(l, AI, InsertPt);
255 //modify all functions and return values to restore the local variable to/from
256 //the global variable
257 for(Function::iterator fib = F->begin(), fie = F->end();
259 for(BasicBlock::iterator bib = fib->begin(), bie = fib->end();
261 if (isa<CallInst>(bib)) {
262 LoadInst* l = new LoadInst(AI, "counter", bib);
263 new StoreInst(l, Counter, bib);
264 l = new LoadInst(Counter, "counter", ++bib);
265 new StoreInst(l, AI, bib--);
266 } else if (isa<InvokeInst>(bib)) {
267 LoadInst* l = new LoadInst(AI, "counter", bib);
268 new StoreInst(l, Counter, bib);
270 BasicBlock* bb = cast<InvokeInst>(bib)->getNormalDest();
271 BasicBlock::iterator i = bb->getFirstNonPHI();
272 l = new LoadInst(Counter, "counter", i);
274 bb = cast<InvokeInst>(bib)->getUnwindDest();
275 i = bb->getFirstNonPHI();
276 l = new LoadInst(Counter, "counter", i);
277 new StoreInst(l, AI, i);
278 } else if (isa<UnwindInst>(&*bib) || isa<ReturnInst>(&*bib)) {
279 LoadInst* l = new LoadInst(AI, "counter", bib);
280 new StoreInst(l, Counter, bib);
284 void GlobalRandomCounterOpt::ProcessChoicePoint(BasicBlock* bb) {
285 BranchInst* t = cast<BranchInst>(bb->getTerminator());
286 LLVMContext *Context = bb->getContext();
289 LoadInst* l = new LoadInst(AI, "counter", t);
291 ICmpInst* s = new ICmpInst(t, ICmpInst::ICMP_EQ, l,
292 Context->getConstantInt(T, 0),
295 Value* nv = BinaryOperator::CreateSub(l, Context->getConstantInt(T, 1),
297 new StoreInst(nv, AI, t);
301 BasicBlock* oldnext = t->getSuccessor(0);
302 BasicBlock* resetblock = BasicBlock::Create("reset", oldnext->getParent(),
304 TerminatorInst* t2 = BranchInst::Create(oldnext, resetblock);
305 t->setSuccessor(0, resetblock);
306 new StoreInst(ResetValue, AI, t2);
307 ReplacePhiPred(oldnext, bb, resetblock);
311 CycleCounter::CycleCounter(Module& m, uint64_t resetmask) : rm(resetmask) {
312 F = Intrinsic::getDeclaration(&m, Intrinsic::readcyclecounter);
315 CycleCounter::~CycleCounter() {}
317 void CycleCounter::PrepFunction(Function* F) {}
319 void CycleCounter::ProcessChoicePoint(BasicBlock* bb) {
320 BranchInst* t = cast<BranchInst>(bb->getTerminator());
321 LLVMContext *Context = bb->getContext();
323 CallInst* c = CallInst::Create(F, "rdcc", t);
325 BinaryOperator::CreateAnd(c, Context->getConstantInt(Type::Int64Ty, rm),
328 ICmpInst *s = new ICmpInst(t, ICmpInst::ICMP_EQ, b,
329 Context->getConstantInt(Type::Int64Ty, 0),
335 ///////////////////////////////////////
337 ///////////////////////////////////////
338 bool RSProfilers_std::isProfiling(Value* v) {
339 if (profcode.find(v) != profcode.end())
342 RSProfilers& LI = getAnalysis<RSProfilers>();
343 return LI.isProfiling(v);
346 void RSProfilers_std::IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum,
347 GlobalValue *CounterArray) {
348 // Insert the increment after any alloca or PHI instructions...
349 BasicBlock::iterator InsertPos = BB->getFirstNonPHI();
350 while (isa<AllocaInst>(InsertPos))
353 // Create the getelementptr constant expression
354 std::vector<Constant*> Indices(2);
355 Indices[0] = Context->getNullValue(Type::Int32Ty);
356 Indices[1] = Context->getConstantInt(Type::Int32Ty, CounterNum);
357 Constant *ElementPtr = Context->getConstantExprGetElementPtr(CounterArray,
360 // Load, increment and store the value back.
361 Value *OldVal = new LoadInst(ElementPtr, "OldCounter", InsertPos);
362 profcode.insert(OldVal);
363 Value *NewVal = BinaryOperator::CreateAdd(OldVal,
364 Context->getConstantInt(Type::Int32Ty, 1),
365 "NewCounter", InsertPos);
366 profcode.insert(NewVal);
367 profcode.insert(new StoreInst(NewVal, ElementPtr, InsertPos));
370 void RSProfilers_std::getAnalysisUsage(AnalysisUsage &AU) const {
371 //grab any outstanding profiler, or get the null one
372 AU.addRequired<RSProfilers>();
375 ///////////////////////////////////////
377 ///////////////////////////////////////
379 Value* ProfilerRS::Translate(Value* v) {
381 return TransCache[v];
383 if (BasicBlock* bb = dyn_cast<BasicBlock>(v)) {
384 if (bb == &bb->getParent()->getEntryBlock())
385 TransCache[bb] = bb; //don't translate entry block
387 TransCache[bb] = BasicBlock::Create("dup_" + bb->getName(),
388 bb->getParent(), NULL);
389 return TransCache[bb];
390 } else if (Instruction* i = dyn_cast<Instruction>(v)) {
391 //we have already translated this
392 //do not translate entry block allocas
393 if(&i->getParent()->getParent()->getEntryBlock() == i->getParent()) {
398 Instruction* i2 = i->clone(*Context);
400 i2->setName("dup_" + i->getName());
403 for (unsigned x = 0; x < i2->getNumOperands(); ++x)
404 i2->setOperand(x, Translate(i2->getOperand(x)));
407 } else if (isa<Function>(v) || isa<Constant>(v) || isa<Argument>(v)) {
411 llvm_unreachable("Value not handled");
415 void ProfilerRS::Duplicate(Function& F, RSProfilers& LI)
417 //perform a breadth first search, building up a duplicate of the code
418 std::queue<BasicBlock*> worklist;
419 std::set<BasicBlock*> seen;
421 //This loop ensures proper BB order, to help performance
422 for (Function::iterator fib = F.begin(), fie = F.end(); fib != fie; ++fib)
424 while (!worklist.empty()) {
425 Translate(worklist.front());
429 //remember than reg2mem created a new entry block we don't want to duplicate
430 worklist.push(F.getEntryBlock().getTerminator()->getSuccessor(0));
431 seen.insert(&F.getEntryBlock());
433 while (!worklist.empty()) {
434 BasicBlock* bb = worklist.front();
436 if(seen.find(bb) == seen.end()) {
437 BasicBlock* bbtarget = cast<BasicBlock>(Translate(bb));
438 BasicBlock::InstListType& instlist = bbtarget->getInstList();
439 for (BasicBlock::iterator iib = bb->begin(), iie = bb->end();
442 if (!LI.isProfiling(&*iib)) {
443 Instruction* i = cast<Instruction>(Translate(iib));
444 instlist.insert(bbtarget->end(), i);
447 //updated search state;
449 TerminatorInst* ti = bb->getTerminator();
450 for (unsigned x = 0; x < ti->getNumSuccessors(); ++x) {
451 BasicBlock* bbs = ti->getSuccessor(x);
452 if (seen.find(bbs) == seen.end()) {
460 void ProfilerRS::ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F) {
461 //given a backedge from B -> A, and translations A' and B',
463 //b: add branches in C to A and A' and in C' to A and A'
464 //c: mod terminators@B, replace A with C
465 //d: mod terminators@B', replace A' with C'
466 //e: mod phis@A for pred B to be pred C
467 // if multiple entries, simplify to one
468 //f: mod phis@A' for pred B' to be pred C'
469 // if multiple entries, simplify to one
470 //g: for all phis@A with pred C using x
471 // add in edge from C' using x'
472 // add in edge from C using x in A'
475 Function::iterator BBN = src; ++BBN;
476 BasicBlock* bbC = BasicBlock::Create("choice", &F, BBN);
477 //ChoicePoints.insert(bbC);
478 BBN = cast<BasicBlock>(Translate(src));
479 BasicBlock* bbCp = BasicBlock::Create("choice", &F, ++BBN);
480 ChoicePoints.insert(bbCp);
483 BranchInst::Create(cast<BasicBlock>(Translate(dst)), bbC);
484 BranchInst::Create(dst, cast<BasicBlock>(Translate(dst)),
485 Context->getConstantInt(Type::Int1Ty, true), bbCp);
488 TerminatorInst* iB = src->getTerminator();
489 for (unsigned x = 0; x < iB->getNumSuccessors(); ++x)
490 if (iB->getSuccessor(x) == dst)
491 iB->setSuccessor(x, bbC);
495 TerminatorInst* iBp = cast<TerminatorInst>(Translate(src->getTerminator()));
496 for (unsigned x = 0; x < iBp->getNumSuccessors(); ++x)
497 if (iBp->getSuccessor(x) == cast<BasicBlock>(Translate(dst)))
498 iBp->setSuccessor(x, bbCp);
501 ReplacePhiPred(dst, src, bbC);
502 //src could be a switch, in which case we are replacing several edges with one
503 //thus collapse those edges int the Phi
504 CollapsePhi(dst, bbC);
506 ReplacePhiPred(cast<BasicBlock>(Translate(dst)),
507 cast<BasicBlock>(Translate(src)),bbCp);
508 CollapsePhi(cast<BasicBlock>(Translate(dst)), bbCp);
510 for(BasicBlock::iterator ib = dst->begin(), ie = dst->end(); ib != ie;
512 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
513 for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x)
514 if(bbC == phi->getIncomingBlock(x)) {
515 phi->addIncoming(Translate(phi->getIncomingValue(x)), bbCp);
516 cast<PHINode>(Translate(phi))->addIncoming(phi->getIncomingValue(x),
519 phi->removeIncomingValue(bbC);
523 bool ProfilerRS::runOnFunction(Function& F) {
524 if (!F.isDeclaration()) {
525 std::set<std::pair<BasicBlock*, BasicBlock*> > BackEdges;
526 RSProfilers& LI = getAnalysis<RSProfilers>();
528 getBackEdges(F, BackEdges);
530 //assume that stuff worked. now connect the duplicated basic blocks
531 //with the originals in such a way as to preserve ssa. yuk!
532 for (std::set<std::pair<BasicBlock*, BasicBlock*> >::iterator
533 ib = BackEdges.begin(), ie = BackEdges.end(); ib != ie; ++ib)
534 ProcessBackEdge(ib->first, ib->second, F);
536 //oh, and add the edge from the reg2mem created entry node to the
537 //duplicated second node
538 TerminatorInst* T = F.getEntryBlock().getTerminator();
539 ReplaceInstWithInst(T, BranchInst::Create(T->getSuccessor(0),
541 Translate(T->getSuccessor(0))),
542 Context->getConstantInt(Type::Int1Ty,
545 //do whatever is needed now that the function is duplicated
548 //add entry node to choice points
549 ChoicePoints.insert(&F.getEntryBlock());
551 for (std::set<BasicBlock*>::iterator
552 ii = ChoicePoints.begin(), ie = ChoicePoints.end(); ii != ie; ++ii)
553 c->ProcessChoicePoint(*ii);
555 ChoicePoints.clear();
563 bool ProfilerRS::doInitialization(Module &M) {
564 switch (RandomMethod) {
566 c = new GlobalRandomCounter(M, Type::Int32Ty, (1 << 14) - 1);
569 c = new GlobalRandomCounterOpt(M, Type::Int32Ty, (1 << 14) - 1);
572 c = new CycleCounter(M, (1 << 14) - 1);
578 void ProfilerRS::getAnalysisUsage(AnalysisUsage &AU) const {
579 AU.addRequired<RSProfilers>();
580 AU.addRequiredID(DemoteRegisterToMemoryID);
583 ///////////////////////////////////////
585 ///////////////////////////////////////
586 static void ReplacePhiPred(BasicBlock* btarget,
587 BasicBlock* bold, BasicBlock* bnew) {
588 for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
590 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
591 for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x)
592 if(bold == phi->getIncomingBlock(x))
593 phi->setIncomingBlock(x, bnew);
597 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc) {
598 for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
600 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
601 std::map<BasicBlock*, Value*> counter;
602 for(unsigned i = 0; i < phi->getNumIncomingValues(); ) {
603 if (counter[phi->getIncomingBlock(i)]) {
604 assert(phi->getIncomingValue(i) == counter[phi->getIncomingBlock(i)]);
605 phi->removeIncomingValue(i, false);
607 counter[phi->getIncomingBlock(i)] = phi->getIncomingValue(i);
615 static void recBackEdge(BasicBlock* bb, T& BackEdges,
616 std::map<BasicBlock*, int>& color,
617 std::map<BasicBlock*, int>& depth,
618 std::map<BasicBlock*, int>& finish,
624 TerminatorInst* t= bb->getTerminator();
625 for(unsigned i = 0; i < t->getNumSuccessors(); ++i) {
626 BasicBlock* bbnew = t->getSuccessor(i);
627 if (color[bbnew] == 0)
628 recBackEdge(bbnew, BackEdges, color, depth, finish, time);
629 else if (color[bbnew] == 1) {
630 BackEdges.insert(std::make_pair(bb, bbnew));
641 //find the back edges and where they go to
643 static void getBackEdges(Function& F, T& BackEdges) {
644 std::map<BasicBlock*, int> color;
645 std::map<BasicBlock*, int> depth;
646 std::map<BasicBlock*, int> finish;
648 recBackEdge(&F.getEntryBlock(), BackEdges, color, depth, finish, time);
649 DOUT << F.getName() << " " << BackEdges.size() << "\n";
654 ModulePass* llvm::createNullProfilerRSPass() {
655 return new NullProfilerRS();
658 FunctionPass* llvm::createRSProfilingPass() {
659 return new ProfilerRS();