1 //===- RSProfiling.cpp - Various profiling using random sampling ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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 recommeneded 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/Module.h"
37 #include "llvm/Instructions.h"
38 #include "llvm/Constants.h"
39 #include "llvm/DerivedTypes.h"
40 #include "llvm/Transforms/Scalar.h"
41 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Support/Compiler.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Transforms/Instrumentation.h"
46 #include "RSProfiling.h"
58 cl::opt<RandomMeth> RandomMethod("profile-randomness",
59 cl::desc("How to randomly choose to profile:"),
61 clEnumValN(GBV, "global", "global counter"),
62 clEnumValN(GBVO, "ra_global",
63 "register allocated global counter"),
64 clEnumValN(HOSTCC, "rdcc", "cycle counter"),
67 /// NullProfilerRS - The basic profiler that does nothing. It is the default
68 /// profiler and thus terminates RSProfiler chains. It is useful for
69 /// measuring framework overhead
70 class VISIBILITY_HIDDEN NullProfilerRS : public RSProfilers {
72 bool isProfiling(Value* v) {
75 bool runOnModule(Module &M) {
78 void getAnalysisUsage(AnalysisUsage &AU) const {
83 static RegisterAnalysisGroup<RSProfilers> A("Profiling passes");
84 static RegisterPass<NullProfilerRS> NP("insert-null-profiling-rs",
85 "Measure profiling framework overhead");
86 static RegisterAnalysisGroup<RSProfilers, true> NPT(NP);
88 /// Chooser - Something that chooses when to make a sample of the profiled code
89 class VISIBILITY_HIDDEN Chooser {
91 /// ProcessChoicePoint - is called for each basic block inserted to choose
92 /// between normal and sample code
93 virtual void ProcessChoicePoint(BasicBlock*) = 0;
94 /// PrepFunction - is called once per function before other work is done.
95 /// This gives the opertunity to insert new allocas and such.
96 virtual void PrepFunction(Function*) = 0;
100 //Things that implement sampling policies
101 //A global value that is read-mod-stored to choose when to sample.
102 //A sample is taken when the global counter hits 0
103 class VISIBILITY_HIDDEN GlobalRandomCounter : public Chooser {
104 GlobalVariable* Counter;
108 GlobalRandomCounter(Module& M, const Type* t, uint64_t resetval);
109 virtual ~GlobalRandomCounter();
110 virtual void PrepFunction(Function* F);
111 virtual void ProcessChoicePoint(BasicBlock* bb);
114 //Same is GRC, but allow register allocation of the global counter
115 class VISIBILITY_HIDDEN GlobalRandomCounterOpt : public Chooser {
116 GlobalVariable* Counter;
121 GlobalRandomCounterOpt(Module& M, const Type* t, uint64_t resetval);
122 virtual ~GlobalRandomCounterOpt();
123 virtual void PrepFunction(Function* F);
124 virtual void ProcessChoicePoint(BasicBlock* bb);
127 //Use the cycle counter intrinsic as a source of pseudo randomness when
128 //deciding when to sample.
129 class VISIBILITY_HIDDEN CycleCounter : public Chooser {
133 CycleCounter(Module& m, uint64_t resetmask);
134 virtual ~CycleCounter();
135 virtual void PrepFunction(Function* F);
136 virtual void ProcessChoicePoint(BasicBlock* bb);
139 /// ProfilerRS - Insert the random sampling framework
140 struct VISIBILITY_HIDDEN ProfilerRS : public FunctionPass {
141 std::map<Value*, Value*> TransCache;
142 std::set<BasicBlock*> ChoicePoints;
145 //Translate and duplicate values for the new profile free version of stuff
146 Value* Translate(Value* v);
147 //Duplicate an entire function (with out profiling)
148 void Duplicate(Function& F, RSProfilers& LI);
149 //Called once for each backedge, handle the insertion of choice points and
150 //the interconection of the two versions of the code
151 void ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F);
152 bool runOnFunction(Function& F);
153 bool doInitialization(Module &M);
154 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
157 RegisterPass<ProfilerRS> X("insert-rs-profiling-framework",
158 "Insert random sampling instrumentation framework");
162 static void ReplacePhiPred(BasicBlock* btarget,
163 BasicBlock* bold, BasicBlock* bnew);
165 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc);
168 static void recBackEdge(BasicBlock* bb, T& BackEdges,
169 std::map<BasicBlock*, int>& color,
170 std::map<BasicBlock*, int>& depth,
171 std::map<BasicBlock*, int>& finish,
174 //find the back edges and where they go to
176 static void getBackEdges(Function& F, T& BackEdges);
179 ///////////////////////////////////////
180 // Methods of choosing when to profile
181 ///////////////////////////////////////
183 GlobalRandomCounter::GlobalRandomCounter(Module& M, const Type* t,
184 uint64_t resetval) : T(t) {
185 ConstantInt* Init = ConstantInt::get(T, resetval);
187 Counter = new GlobalVariable(T, false, GlobalValue::InternalLinkage,
188 Init, "RandomSteeringCounter", &M);
191 GlobalRandomCounter::~GlobalRandomCounter() {}
193 void GlobalRandomCounter::PrepFunction(Function* F) {}
195 void GlobalRandomCounter::ProcessChoicePoint(BasicBlock* bb) {
196 BranchInst* t = cast<BranchInst>(bb->getTerminator());
199 LoadInst* l = new LoadInst(Counter, "counter", t);
201 ICmpInst* s = new ICmpInst(ICmpInst::ICMP_EQ, l, ConstantInt::get(T, 0),
204 Value* nv = BinaryOperator::createSub(l, ConstantInt::get(T, 1),
206 new StoreInst(nv, Counter, t);
210 BasicBlock* oldnext = t->getSuccessor(0);
211 BasicBlock* resetblock = new BasicBlock("reset", oldnext->getParent(),
213 TerminatorInst* t2 = new BranchInst(oldnext, resetblock);
214 t->setSuccessor(0, resetblock);
215 new StoreInst(ResetValue, Counter, t2);
216 ReplacePhiPred(oldnext, bb, resetblock);
219 GlobalRandomCounterOpt::GlobalRandomCounterOpt(Module& M, const Type* t,
222 ConstantInt* Init = ConstantInt::get(T, resetval);
224 Counter = new GlobalVariable(T, false, GlobalValue::InternalLinkage,
225 Init, "RandomSteeringCounter", &M);
228 GlobalRandomCounterOpt::~GlobalRandomCounterOpt() {}
230 void GlobalRandomCounterOpt::PrepFunction(Function* F) {
231 //make a local temporary to cache the global
232 BasicBlock& bb = F->getEntryBlock();
233 AI = new AllocaInst(T, 0, "localcounter", bb.begin());
234 LoadInst* l = new LoadInst(Counter, "counterload", AI->getNext());
235 new StoreInst(l, AI, l->getNext());
237 //modify all functions and return values to restore the local variable to/from
238 //the global variable
239 for(Function::iterator fib = F->begin(), fie = F->end();
241 for(BasicBlock::iterator bib = fib->begin(), bie = fib->end();
243 if (isa<CallInst>(&*bib)) {
244 LoadInst* l = new LoadInst(AI, "counter", bib);
245 new StoreInst(l, Counter, bib);
246 l = new LoadInst(Counter, "counter", bib->getNext());
247 new StoreInst(l, AI, l->getNext());
248 } else if (isa<InvokeInst>(&*bib)) {
249 LoadInst* l = new LoadInst(AI, "counter", bib);
250 new StoreInst(l, Counter, bib);
252 BasicBlock* bb = cast<InvokeInst>(&*bib)->getNormalDest();
253 Instruction* i = bb->begin();
254 while (isa<PHINode>(i)) i = i->getNext();
255 l = new LoadInst(Counter, "counter", i);
257 bb = cast<InvokeInst>(&*bib)->getUnwindDest();
259 while (isa<PHINode>(i)) i = i->getNext();
260 l = new LoadInst(Counter, "counter", i);
261 new StoreInst(l, AI, l->getNext());
262 } else if (isa<UnwindInst>(&*bib) || isa<ReturnInst>(&*bib)) {
263 LoadInst* l = new LoadInst(AI, "counter", bib);
264 new StoreInst(l, Counter, bib);
268 void GlobalRandomCounterOpt::ProcessChoicePoint(BasicBlock* bb) {
269 BranchInst* t = cast<BranchInst>(bb->getTerminator());
272 LoadInst* l = new LoadInst(AI, "counter", t);
274 ICmpInst* s = new ICmpInst(ICmpInst::ICMP_EQ, l, ConstantInt::get(T, 0),
277 Value* nv = BinaryOperator::createSub(l, ConstantInt::get(T, 1),
279 new StoreInst(nv, AI, t);
283 BasicBlock* oldnext = t->getSuccessor(0);
284 BasicBlock* resetblock = new BasicBlock("reset", oldnext->getParent(),
286 TerminatorInst* t2 = new BranchInst(oldnext, resetblock);
287 t->setSuccessor(0, resetblock);
288 new StoreInst(ResetValue, AI, t2);
289 ReplacePhiPred(oldnext, bb, resetblock);
293 CycleCounter::CycleCounter(Module& m, uint64_t resetmask) : rm(resetmask) {
294 F = m.getOrInsertFunction("llvm.readcyclecounter", Type::Int64Ty, NULL);
297 CycleCounter::~CycleCounter() {}
299 void CycleCounter::PrepFunction(Function* F) {}
301 void CycleCounter::ProcessChoicePoint(BasicBlock* bb) {
302 BranchInst* t = cast<BranchInst>(bb->getTerminator());
304 CallInst* c = new CallInst(F, "rdcc", t);
306 BinaryOperator::createAnd(c, ConstantInt::get(Type::Int64Ty, rm),
309 ICmpInst *s = new ICmpInst(ICmpInst::ICMP_EQ, b,
310 ConstantInt::get(Type::Int64Ty, 0),
316 ///////////////////////////////////////
318 ///////////////////////////////////////
319 bool RSProfilers_std::isProfiling(Value* v) {
320 if (profcode.find(v) != profcode.end())
323 RSProfilers& LI = getAnalysis<RSProfilers>();
324 return LI.isProfiling(v);
327 void RSProfilers_std::IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum,
328 GlobalValue *CounterArray) {
329 // Insert the increment after any alloca or PHI instructions...
330 BasicBlock::iterator InsertPos = BB->begin();
331 while (isa<AllocaInst>(InsertPos) || isa<PHINode>(InsertPos))
334 // Create the getelementptr constant expression
335 std::vector<Constant*> Indices(2);
336 Indices[0] = Constant::getNullValue(Type::Int32Ty);
337 Indices[1] = ConstantInt::get(Type::Int32Ty, CounterNum);
338 Constant *ElementPtr = ConstantExpr::getGetElementPtr(CounterArray,
341 // Load, increment and store the value back.
342 Value *OldVal = new LoadInst(ElementPtr, "OldCounter", InsertPos);
343 profcode.insert(OldVal);
344 Value *NewVal = BinaryOperator::createAdd(OldVal,
345 ConstantInt::get(Type::Int32Ty, 1),
346 "NewCounter", InsertPos);
347 profcode.insert(NewVal);
348 profcode.insert(new StoreInst(NewVal, ElementPtr, InsertPos));
351 void RSProfilers_std::getAnalysisUsage(AnalysisUsage &AU) const {
352 //grab any outstanding profiler, or get the null one
353 AU.addRequired<RSProfilers>();
356 ///////////////////////////////////////
358 ///////////////////////////////////////
360 Value* ProfilerRS::Translate(Value* v) {
362 return TransCache[v];
364 if (BasicBlock* bb = dyn_cast<BasicBlock>(v)) {
365 if (bb == &bb->getParent()->getEntryBlock())
366 TransCache[bb] = bb; //don't translate entry block
368 TransCache[bb] = new BasicBlock("dup_" + bb->getName(), bb->getParent(),
370 return TransCache[bb];
371 } else if (Instruction* i = dyn_cast<Instruction>(v)) {
372 //we have already translated this
373 //do not translate entry block allocas
374 if(&i->getParent()->getParent()->getEntryBlock() == i->getParent()) {
379 Instruction* i2 = i->clone();
381 i2->setName("dup_" + i->getName());
384 for (unsigned x = 0; x < i2->getNumOperands(); ++x)
385 i2->setOperand(x, Translate(i2->getOperand(x)));
388 } else if (isa<Function>(v) || isa<Constant>(v) || isa<Argument>(v)) {
392 assert(0 && "Value not handled");
396 void ProfilerRS::Duplicate(Function& F, RSProfilers& LI)
398 //perform a breadth first search, building up a duplicate of the code
399 std::queue<BasicBlock*> worklist;
400 std::set<BasicBlock*> seen;
402 //This loop ensures proper BB order, to help performance
403 for (Function::iterator fib = F.begin(), fie = F.end(); fib != fie; ++fib)
405 while (!worklist.empty()) {
406 Translate(worklist.front());
410 //remember than reg2mem created a new entry block we don't want to duplicate
411 worklist.push(F.getEntryBlock().getTerminator()->getSuccessor(0));
412 seen.insert(&F.getEntryBlock());
414 while (!worklist.empty()) {
415 BasicBlock* bb = worklist.front();
417 if(seen.find(bb) == seen.end()) {
418 BasicBlock* bbtarget = cast<BasicBlock>(Translate(bb));
419 BasicBlock::InstListType& instlist = bbtarget->getInstList();
420 for (BasicBlock::iterator iib = bb->begin(), iie = bb->end();
423 if (!LI.isProfiling(&*iib)) {
424 Instruction* i = cast<Instruction>(Translate(iib));
425 instlist.insert(bbtarget->end(), i);
428 //updated search state;
430 TerminatorInst* ti = bb->getTerminator();
431 for (unsigned x = 0; x < ti->getNumSuccessors(); ++x) {
432 BasicBlock* bbs = ti->getSuccessor(x);
433 if (seen.find(bbs) == seen.end()) {
441 void ProfilerRS::ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F) {
442 //given a backedge from B -> A, and translations A' and B',
444 //b: add branches in C to A and A' and in C' to A and A'
445 //c: mod terminators@B, replace A with C
446 //d: mod terminators@B', replace A' with C'
447 //e: mod phis@A for pred B to be pred C
448 // if multiple entries, simplify to one
449 //f: mod phis@A' for pred B' to be pred C'
450 // if multiple entries, simplify to one
451 //g: for all phis@A with pred C using x
452 // add in edge from C' using x'
453 // add in edge from C using x in A'
456 BasicBlock* bbC = new BasicBlock("choice", &F, src->getNext() );
457 //ChoicePoints.insert(bbC);
459 new BasicBlock("choice", &F, cast<BasicBlock>(Translate(src))->getNext() );
460 ChoicePoints.insert(bbCp);
463 new BranchInst(cast<BasicBlock>(Translate(dst)), bbC);
464 new BranchInst(dst, cast<BasicBlock>(Translate(dst)),
465 ConstantInt::get(Type::Int1Ty, true), bbCp);
468 TerminatorInst* iB = src->getTerminator();
469 for (unsigned x = 0; x < iB->getNumSuccessors(); ++x)
470 if (iB->getSuccessor(x) == dst)
471 iB->setSuccessor(x, bbC);
475 TerminatorInst* iBp = cast<TerminatorInst>(Translate(src->getTerminator()));
476 for (unsigned x = 0; x < iBp->getNumSuccessors(); ++x)
477 if (iBp->getSuccessor(x) == cast<BasicBlock>(Translate(dst)))
478 iBp->setSuccessor(x, bbCp);
481 ReplacePhiPred(dst, src, bbC);
482 //src could be a switch, in which case we are replacing several edges with one
483 //thus collapse those edges int the Phi
484 CollapsePhi(dst, bbC);
486 ReplacePhiPred(cast<BasicBlock>(Translate(dst)),
487 cast<BasicBlock>(Translate(src)),bbCp);
488 CollapsePhi(cast<BasicBlock>(Translate(dst)), bbCp);
490 for(BasicBlock::iterator ib = dst->begin(), ie = dst->end(); ib != ie;
492 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
493 for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x)
494 if(bbC == phi->getIncomingBlock(x)) {
495 phi->addIncoming(Translate(phi->getIncomingValue(x)), bbCp);
496 cast<PHINode>(Translate(phi))->addIncoming(phi->getIncomingValue(x),
499 phi->removeIncomingValue(bbC);
503 bool ProfilerRS::runOnFunction(Function& F) {
504 if (!F.isDeclaration()) {
505 std::set<std::pair<BasicBlock*, BasicBlock*> > BackEdges;
506 RSProfilers& LI = getAnalysis<RSProfilers>();
508 getBackEdges(F, BackEdges);
510 //assume that stuff worked. now connect the duplicated basic blocks
511 //with the originals in such a way as to preserve ssa. yuk!
512 for (std::set<std::pair<BasicBlock*, BasicBlock*> >::iterator
513 ib = BackEdges.begin(), ie = BackEdges.end(); ib != ie; ++ib)
514 ProcessBackEdge(ib->first, ib->second, F);
516 //oh, and add the edge from the reg2mem created entry node to the
517 //duplicated second node
518 TerminatorInst* T = F.getEntryBlock().getTerminator();
519 ReplaceInstWithInst(T, new BranchInst(T->getSuccessor(0),
520 cast<BasicBlock>(Translate(T->getSuccessor(0))),
521 ConstantInt::get(Type::Int1Ty, true)));
523 //do whatever is needed now that the function is duplicated
526 //add entry node to choice points
527 ChoicePoints.insert(&F.getEntryBlock());
529 for (std::set<BasicBlock*>::iterator
530 ii = ChoicePoints.begin(), ie = ChoicePoints.end(); ii != ie; ++ii)
531 c->ProcessChoicePoint(*ii);
533 ChoicePoints.clear();
541 bool ProfilerRS::doInitialization(Module &M) {
542 switch (RandomMethod) {
544 c = new GlobalRandomCounter(M, Type::Int32Ty, (1 << 14) - 1);
547 c = new GlobalRandomCounterOpt(M, Type::Int32Ty, (1 << 14) - 1);
550 c = new CycleCounter(M, (1 << 14) - 1);
556 void ProfilerRS::getAnalysisUsage(AnalysisUsage &AU) const {
557 AU.addRequired<RSProfilers>();
558 AU.addRequiredID(DemoteRegisterToMemoryID);
561 ///////////////////////////////////////
563 ///////////////////////////////////////
564 static void ReplacePhiPred(BasicBlock* btarget,
565 BasicBlock* bold, BasicBlock* bnew) {
566 for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
568 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
569 for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x)
570 if(bold == phi->getIncomingBlock(x))
571 phi->setIncomingBlock(x, bnew);
575 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc) {
576 for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
578 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
579 std::map<BasicBlock*, Value*> counter;
580 for(unsigned i = 0; i < phi->getNumIncomingValues(); ) {
581 if (counter[phi->getIncomingBlock(i)]) {
582 assert(phi->getIncomingValue(i) == counter[phi->getIncomingBlock(i)]);
583 phi->removeIncomingValue(i, false);
585 counter[phi->getIncomingBlock(i)] = phi->getIncomingValue(i);
593 static void recBackEdge(BasicBlock* bb, T& BackEdges,
594 std::map<BasicBlock*, int>& color,
595 std::map<BasicBlock*, int>& depth,
596 std::map<BasicBlock*, int>& finish,
602 TerminatorInst* t= bb->getTerminator();
603 for(unsigned i = 0; i < t->getNumSuccessors(); ++i) {
604 BasicBlock* bbnew = t->getSuccessor(i);
605 if (color[bbnew] == 0)
606 recBackEdge(bbnew, BackEdges, color, depth, finish, time);
607 else if (color[bbnew] == 1) {
608 BackEdges.insert(std::make_pair(bb, bbnew));
619 //find the back edges and where they go to
621 static void getBackEdges(Function& F, T& BackEdges) {
622 std::map<BasicBlock*, int> color;
623 std::map<BasicBlock*, int> depth;
624 std::map<BasicBlock*, int> finish;
626 recBackEdge(&F.getEntryBlock(), BackEdges, color, depth, finish, time);
627 DOUT << F.getName() << " " << BackEdges.size() << "\n";
632 ModulePass* llvm::createNullProfilerRSPass() {
633 return new NullProfilerRS();
636 FunctionPass* llvm::createRSProfilingPass() {
637 return new ProfilerRS();