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/Debug.h"
46 #include "llvm/Support/ErrorHandling.h"
47 #include "llvm/Support/raw_ostream.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 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
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 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 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 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 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
= ConstantInt::get(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());
214 LoadInst
* l
= new LoadInst(Counter
, "counter", t
);
216 ICmpInst
* s
= new ICmpInst(t
, ICmpInst::ICMP_EQ
, l
,
217 ConstantInt::get(T
, 0),
220 Value
* nv
= BinaryOperator::CreateSub(l
, ConstantInt::get(T
, 1),
222 new StoreInst(nv
, Counter
, t
);
226 BasicBlock
* oldnext
= t
->getSuccessor(0);
227 BasicBlock
* resetblock
= BasicBlock::Create(bb
->getContext(),
228 "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
= ConstantInt::get(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());
288 LoadInst
* l
= new LoadInst(AI
, "counter", t
);
290 ICmpInst
* s
= new ICmpInst(t
, ICmpInst::ICMP_EQ
, l
,
291 ConstantInt::get(T
, 0),
294 Value
* nv
= BinaryOperator::CreateSub(l
, ConstantInt::get(T
, 1),
296 new StoreInst(nv
, AI
, t
);
300 BasicBlock
* oldnext
= t
->getSuccessor(0);
301 BasicBlock
* resetblock
= BasicBlock::Create(bb
->getContext(),
302 "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());
322 CallInst
* c
= CallInst::Create(F
, "rdcc", t
);
324 BinaryOperator::CreateAnd(c
,
325 ConstantInt::get(Type::getInt64Ty(bb
->getContext()), rm
),
328 ICmpInst
*s
= new ICmpInst(t
, ICmpInst::ICMP_EQ
, b
,
329 ConstantInt::get(Type::getInt64Ty(bb
->getContext()), 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] = Constant::getNullValue(Type::getInt32Ty(BB
->getContext()));
356 Indices
[1] = ConstantInt::get(Type::getInt32Ty(BB
->getContext()), CounterNum
);
357 Constant
*ElementPtr
=ConstantExpr::getGetElementPtr(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 ConstantInt::get(Type::getInt32Ty(BB
->getContext()), 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(v
->getContext(),
388 "dup_" + bb
->getName(),
389 bb
->getParent(), NULL
);
390 return TransCache
[bb
];
391 } else if (Instruction
* i
= dyn_cast
<Instruction
>(v
)) {
392 //we have already translated this
393 //do not translate entry block allocas
394 if(&i
->getParent()->getParent()->getEntryBlock() == i
->getParent()) {
399 Instruction
* i2
= i
->clone();
401 i2
->setName("dup_" + i
->getName());
404 for (unsigned x
= 0; x
< i2
->getNumOperands(); ++x
)
405 i2
->setOperand(x
, Translate(i2
->getOperand(x
)));
408 } else if (isa
<Function
>(v
) || isa
<Constant
>(v
) || isa
<Argument
>(v
)) {
412 llvm_unreachable("Value not handled");
416 void ProfilerRS::Duplicate(Function
& F
, RSProfilers
& LI
)
418 //perform a breadth first search, building up a duplicate of the code
419 std::queue
<BasicBlock
*> worklist
;
420 std::set
<BasicBlock
*> seen
;
422 //This loop ensures proper BB order, to help performance
423 for (Function::iterator fib
= F
.begin(), fie
= F
.end(); fib
!= fie
; ++fib
)
425 while (!worklist
.empty()) {
426 Translate(worklist
.front());
430 //remember than reg2mem created a new entry block we don't want to duplicate
431 worklist
.push(F
.getEntryBlock().getTerminator()->getSuccessor(0));
432 seen
.insert(&F
.getEntryBlock());
434 while (!worklist
.empty()) {
435 BasicBlock
* bb
= worklist
.front();
437 if(seen
.find(bb
) == seen
.end()) {
438 BasicBlock
* bbtarget
= cast
<BasicBlock
>(Translate(bb
));
439 BasicBlock::InstListType
& instlist
= bbtarget
->getInstList();
440 for (BasicBlock::iterator iib
= bb
->begin(), iie
= bb
->end();
443 if (!LI
.isProfiling(&*iib
)) {
444 Instruction
* i
= cast
<Instruction
>(Translate(iib
));
445 instlist
.insert(bbtarget
->end(), i
);
448 //updated search state;
450 TerminatorInst
* ti
= bb
->getTerminator();
451 for (unsigned x
= 0; x
< ti
->getNumSuccessors(); ++x
) {
452 BasicBlock
* bbs
= ti
->getSuccessor(x
);
453 if (seen
.find(bbs
) == seen
.end()) {
461 void ProfilerRS::ProcessBackEdge(BasicBlock
* src
, BasicBlock
* dst
, Function
& F
) {
462 //given a backedge from B -> A, and translations A' and B',
464 //b: add branches in C to A and A' and in C' to A and A'
465 //c: mod terminators@B, replace A with C
466 //d: mod terminators@B', replace A' with C'
467 //e: mod phis@A for pred B to be pred C
468 // if multiple entries, simplify to one
469 //f: mod phis@A' for pred B' to be pred C'
470 // if multiple entries, simplify to one
471 //g: for all phis@A with pred C using x
472 // add in edge from C' using x'
473 // add in edge from C using x in A'
476 Function::iterator BBN
= src
; ++BBN
;
477 BasicBlock
* bbC
= BasicBlock::Create(F
.getContext(), "choice", &F
, BBN
);
478 //ChoicePoints.insert(bbC);
479 BBN
= cast
<BasicBlock
>(Translate(src
));
480 BasicBlock
* bbCp
= BasicBlock::Create(F
.getContext(), "choice", &F
, ++BBN
);
481 ChoicePoints
.insert(bbCp
);
484 BranchInst::Create(cast
<BasicBlock
>(Translate(dst
)), bbC
);
485 BranchInst::Create(dst
, cast
<BasicBlock
>(Translate(dst
)),
486 ConstantInt::get(Type::getInt1Ty(src
->getContext()), true), bbCp
);
489 TerminatorInst
* iB
= src
->getTerminator();
490 for (unsigned x
= 0; x
< iB
->getNumSuccessors(); ++x
)
491 if (iB
->getSuccessor(x
) == dst
)
492 iB
->setSuccessor(x
, bbC
);
496 TerminatorInst
* iBp
= cast
<TerminatorInst
>(Translate(src
->getTerminator()));
497 for (unsigned x
= 0; x
< iBp
->getNumSuccessors(); ++x
)
498 if (iBp
->getSuccessor(x
) == cast
<BasicBlock
>(Translate(dst
)))
499 iBp
->setSuccessor(x
, bbCp
);
502 ReplacePhiPred(dst
, src
, bbC
);
503 //src could be a switch, in which case we are replacing several edges with one
504 //thus collapse those edges int the Phi
505 CollapsePhi(dst
, bbC
);
507 ReplacePhiPred(cast
<BasicBlock
>(Translate(dst
)),
508 cast
<BasicBlock
>(Translate(src
)),bbCp
);
509 CollapsePhi(cast
<BasicBlock
>(Translate(dst
)), bbCp
);
511 for(BasicBlock::iterator ib
= dst
->begin(), ie
= dst
->end(); ib
!= ie
;
513 if (PHINode
* phi
= dyn_cast
<PHINode
>(&*ib
)) {
514 for(unsigned x
= 0; x
< phi
->getNumIncomingValues(); ++x
)
515 if(bbC
== phi
->getIncomingBlock(x
)) {
516 phi
->addIncoming(Translate(phi
->getIncomingValue(x
)), bbCp
);
517 cast
<PHINode
>(Translate(phi
))->addIncoming(phi
->getIncomingValue(x
),
520 phi
->removeIncomingValue(bbC
);
524 bool ProfilerRS::runOnFunction(Function
& F
) {
525 if (!F
.isDeclaration()) {
526 std::set
<std::pair
<BasicBlock
*, BasicBlock
*> > BackEdges
;
527 RSProfilers
& LI
= getAnalysis
<RSProfilers
>();
529 getBackEdges(F
, BackEdges
);
531 //assume that stuff worked. now connect the duplicated basic blocks
532 //with the originals in such a way as to preserve ssa. yuk!
533 for (std::set
<std::pair
<BasicBlock
*, BasicBlock
*> >::iterator
534 ib
= BackEdges
.begin(), ie
= BackEdges
.end(); ib
!= ie
; ++ib
)
535 ProcessBackEdge(ib
->first
, ib
->second
, F
);
537 //oh, and add the edge from the reg2mem created entry node to the
538 //duplicated second node
539 TerminatorInst
* T
= F
.getEntryBlock().getTerminator();
540 ReplaceInstWithInst(T
, BranchInst::Create(T
->getSuccessor(0),
542 Translate(T
->getSuccessor(0))),
543 ConstantInt::get(Type::getInt1Ty(F
.getContext()), true)));
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::getInt32Ty(M
.getContext()),
570 c
= new GlobalRandomCounterOpt(M
, Type::getInt32Ty(M
.getContext()),
574 c
= new CycleCounter(M
, (1 << 14) - 1);
580 void ProfilerRS::getAnalysisUsage(AnalysisUsage
&AU
) const {
581 AU
.addRequired
<RSProfilers
>();
582 AU
.addRequiredID(DemoteRegisterToMemoryID
);
585 ///////////////////////////////////////
587 ///////////////////////////////////////
588 static void ReplacePhiPred(BasicBlock
* btarget
,
589 BasicBlock
* bold
, BasicBlock
* bnew
) {
590 for(BasicBlock::iterator ib
= btarget
->begin(), ie
= btarget
->end();
592 if (PHINode
* phi
= dyn_cast
<PHINode
>(&*ib
)) {
593 for(unsigned x
= 0; x
< phi
->getNumIncomingValues(); ++x
)
594 if(bold
== phi
->getIncomingBlock(x
))
595 phi
->setIncomingBlock(x
, bnew
);
599 static void CollapsePhi(BasicBlock
* btarget
, BasicBlock
* bsrc
) {
600 for(BasicBlock::iterator ib
= btarget
->begin(), ie
= btarget
->end();
602 if (PHINode
* phi
= dyn_cast
<PHINode
>(&*ib
)) {
603 std::map
<BasicBlock
*, Value
*> counter
;
604 for(unsigned i
= 0; i
< phi
->getNumIncomingValues(); ) {
605 if (counter
[phi
->getIncomingBlock(i
)]) {
606 assert(phi
->getIncomingValue(i
) == counter
[phi
->getIncomingBlock(i
)]);
607 phi
->removeIncomingValue(i
, false);
609 counter
[phi
->getIncomingBlock(i
)] = phi
->getIncomingValue(i
);
617 static void recBackEdge(BasicBlock
* bb
, T
& BackEdges
,
618 std::map
<BasicBlock
*, int>& color
,
619 std::map
<BasicBlock
*, int>& depth
,
620 std::map
<BasicBlock
*, int>& finish
,
626 TerminatorInst
* t
= bb
->getTerminator();
627 for(unsigned i
= 0; i
< t
->getNumSuccessors(); ++i
) {
628 BasicBlock
* bbnew
= t
->getSuccessor(i
);
629 if (color
[bbnew
] == 0)
630 recBackEdge(bbnew
, BackEdges
, color
, depth
, finish
, time
);
631 else if (color
[bbnew
] == 1) {
632 BackEdges
.insert(std::make_pair(bb
, bbnew
));
643 //find the back edges and where they go to
645 static void getBackEdges(Function
& F
, T
& BackEdges
) {
646 std::map
<BasicBlock
*, int> color
;
647 std::map
<BasicBlock
*, int> depth
;
648 std::map
<BasicBlock
*, int> finish
;
650 recBackEdge(&F
.getEntryBlock(), BackEdges
, color
, depth
, finish
, time
);
651 DEBUG(errs() << F
.getName() << " " << BackEdges
.size() << "\n");
656 ModulePass
* llvm::createNullProfilerRSPass() {
657 return new NullProfilerRS();
660 FunctionPass
* llvm::createRSProfilingPass() {
661 return new ProfilerRS();