LLVM API Documentation

RSProfiling.cpp

Go to the documentation of this file.
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 }