lib/Transforms/Instrumentation/RSProfiling.cpp

   1 //===- RSProfiling.cpp - Various profiling using random sampling ----------===//
   2 //
   3 //                      The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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
  14 // inserted.
  15 //
  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.
  20 //
  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)
  23 //
  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)
  27 //
  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
  32 //
  33 //===----------------------------------------------------------------------===//
  34
  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"
  50 #include <set>
  51 #include <map>
  52 #include <queue>
  53 using namespace llvm;
  54
  55 namespace {
  56   enum RandomMeth {
  57     GBV, GBVO, HOSTCC
  58   };
  59 }
  60
  61 static cl::opt<RandomMeth> RandomMethod("profile-randomness",
  62     cl::desc("How to randomly choose to profile:"),
  63     cl::values(
  64                clEnumValN(GBV, "global", "global counter"),
  65                clEnumValN(GBVO, "ra_global",
  66                           "register allocated global counter"),
  67                clEnumValN(HOSTCC, "rdcc", "cycle counter"),
  68                clEnumValEnd));
  69
  70 namespace {
  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 {
  75   public:
  76     static char ID; // Pass identification, replacement for typeid
  77     bool isProfiling(Value* v) {
  78       return false;
  79     }
  80     bool runOnModule(Module &M) {
  81       return false;
  82     }
  83     void getAnalysisUsage(AnalysisUsage &AU) const {
  84       AU.setPreservesAll();
  85     }
  86   };
  87 }
  88
  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);
  93
  94 namespace {
  95   /// Chooser - Something that chooses when to make a sample of the profiled code
  96   class Chooser {
  97   public:
  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() {}
 105   };
 106
 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;
 112     Value* ResetValue;
 113     const IntegerType* T;
 114   public:
 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);
 119   };
 120
 121   //Same is GRC, but allow register allocation of the global counter
 122   class GlobalRandomCounterOpt : public Chooser {
 123     GlobalVariable* Counter;
 124     Value* ResetValue;
 125     AllocaInst* AI;
 126     const IntegerType* T;
 127   public:
 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);
 132   };
 133
 134   //Use the cycle counter intrinsic as a source of pseudo randomness when
 135   //deciding when to sample.
 136   class CycleCounter : public Chooser {
 137     uint64_t rm;
 138     Constant *F;
 139   public:
 140     CycleCounter(Module& m, uint64_t resetmask);
 141     virtual ~CycleCounter();
 142     virtual void PrepFunction(Function* F);
 143     virtual void ProcessChoicePoint(BasicBlock* bb);
 144   };
 145
 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) {}
 150
 151     std::map<Value*, Value*> TransCache;
 152     std::set<BasicBlock*> ChoicePoints;
 153     Chooser* c;
 154
 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;
 165   };
 166 }
 167
 168 static RegisterPass<ProfilerRS>
 169 X("insert-rs-profiling-framework",
 170   "Insert random sampling instrumentation framework");
 171
 172 char RSProfilers::ID = 0;
 173 char NullProfilerRS::ID = 0;
 174 char ProfilerRS::ID = 0;
 175
 176 //Local utilities
 177 static void ReplacePhiPred(BasicBlock* btarget,
 178                            BasicBlock* bold, BasicBlock* bnew);
 179
 180 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc);
 181
 182 template<class T>
 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,
 187                         int& time);
 188
 189 //find the back edges and where they go to
 190 template<class T>
 191 static void getBackEdges(Function& F, T& BackEdges);
 192
 193
 194 ///////////////////////////////////////
 195 // Methods of choosing when to profile
 196 ///////////////////////////////////////
 197
 198 GlobalRandomCounter::GlobalRandomCounter(Module& M, const IntegerType* t,
 199                                          uint64_t resetval) : T(t) {
 200   ConstantInt* Init = ConstantInt::get(T, resetval);
 201   ResetValue = Init;
 202   Counter = new GlobalVariable(M, T, false, GlobalValue::InternalLinkage,
 203                                Init, "RandomSteeringCounter");
 204 }
 205
 206 GlobalRandomCounter::~GlobalRandomCounter() {}
 207
 208 void GlobalRandomCounter::PrepFunction(Function* F) {}
 209
 210 void GlobalRandomCounter::ProcessChoicePoint(BasicBlock* bb) {
 211   BranchInst* t = cast<BranchInst>(bb->getTerminator());
 212
 213   //decrement counter
 214   LoadInst* l = new LoadInst(Counter, "counter", t);
 215
 216   ICmpInst* s = new ICmpInst(t, ICmpInst::ICMP_EQ, l,
 217                              ConstantInt::get(T, 0),
 218                              "countercc");
 219
 220   Value* nv = BinaryOperator::CreateSub(l, ConstantInt::get(T, 1),
 221                                         "counternew", t);
 222   new StoreInst(nv, Counter, t);
 223   t->setCondition(s);
 224
 225   //reset counter
 226   BasicBlock* oldnext = t->getSuccessor(0);
 227   BasicBlock* resetblock = BasicBlock::Create(bb->getContext(),
 228                                               "reset", oldnext->getParent(),
 229                                               oldnext);
 230   TerminatorInst* t2 = BranchInst::Create(oldnext, resetblock);
 231   t->setSuccessor(0, resetblock);
 232   new StoreInst(ResetValue, Counter, t2);
 233   ReplacePhiPred(oldnext, bb, resetblock);
 234 }
 235
 236 GlobalRandomCounterOpt::GlobalRandomCounterOpt(Module& M, const IntegerType* t,
 237                                                uint64_t resetval)
 238   : AI(0), T(t) {
 239   ConstantInt* Init = ConstantInt::get(T, resetval);
 240   ResetValue  = Init;
 241   Counter = new GlobalVariable(M, T, false, GlobalValue::InternalLinkage,
 242                                Init, "RandomSteeringCounter");
 243 }
 244
 245 GlobalRandomCounterOpt::~GlobalRandomCounterOpt() {}
 246
 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);
 254
 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();
 258       fib != fie; ++fib)
 259     for(BasicBlock::iterator bib = fib->begin(), bie = fib->end();
 260         bib != bie; ++bib)
 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);
 269
 270         BasicBlock* bb = cast<InvokeInst>(bib)->getNormalDest();
 271         BasicBlock::iterator i = bb->getFirstNonPHI();
 272         l = new LoadInst(Counter, "counter", i);
 273
 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);
 281       }
 282 }
 283
 284 void GlobalRandomCounterOpt::ProcessChoicePoint(BasicBlock* bb) {
 285   BranchInst* t = cast<BranchInst>(bb->getTerminator());
 286
 287   //decrement counter
 288   LoadInst* l = new LoadInst(AI, "counter", t);
 289
 290   ICmpInst* s = new ICmpInst(t, ICmpInst::ICMP_EQ, l,
 291                              ConstantInt::get(T, 0),
 292                              "countercc");
 293
 294   Value* nv = BinaryOperator::CreateSub(l, ConstantInt::get(T, 1),
 295                                         "counternew", t);
 296   new StoreInst(nv, AI, t);
 297   t->setCondition(s);
 298
 299   //reset counter
 300   BasicBlock* oldnext = t->getSuccessor(0);
 301   BasicBlock* resetblock = BasicBlock::Create(bb->getContext(),
 302                                               "reset", oldnext->getParent(),
 303                                               oldnext);
 304   TerminatorInst* t2 = BranchInst::Create(oldnext, resetblock);
 305   t->setSuccessor(0, resetblock);
 306   new StoreInst(ResetValue, AI, t2);
 307   ReplacePhiPred(oldnext, bb, resetblock);
 308 }
 309
 310
 311 CycleCounter::CycleCounter(Module& m, uint64_t resetmask) : rm(resetmask) {
 312   F = Intrinsic::getDeclaration(&m, Intrinsic::readcyclecounter);
 313 }
 314
 315 CycleCounter::~CycleCounter() {}
 316
 317 void CycleCounter::PrepFunction(Function* F) {}
 318
 319 void CycleCounter::ProcessChoicePoint(BasicBlock* bb) {
 320   BranchInst* t = cast<BranchInst>(bb->getTerminator());
 321
 322   CallInst* c = CallInst::Create(F, "rdcc", t);
 323   BinaryOperator* b =
 324     BinaryOperator::CreateAnd(c,
 325                       ConstantInt::get(Type::getInt64Ty(bb->getContext()), rm),
 326                               "mrdcc", t);
 327
 328   ICmpInst *s = new ICmpInst(t, ICmpInst::ICMP_EQ, b,
 329                         ConstantInt::get(Type::getInt64Ty(bb->getContext()), 0),
 330                              "mrdccc");
 331
 332   t->setCondition(s);
 333 }
 334
 335 ///////////////////////////////////////
 336 // Profiling:
 337 ///////////////////////////////////////
 338 bool RSProfilers_std::isProfiling(Value* v) {
 339   if (profcode.find(v) != profcode.end())
 340     return true;
 341   //else
 342   RSProfilers& LI = getAnalysis<RSProfilers>();
 343   return LI.isProfiling(v);
 344 }
 345
 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))
 351     ++InsertPos;
 352
 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,
 358                                                         &Indices[0], 2);
 359
 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));
 368 }
 369
 370 void RSProfilers_std::getAnalysisUsage(AnalysisUsage &AU) const {
 371   //grab any outstanding profiler, or get the null one
 372   AU.addRequired<RSProfilers>();
 373 }
 374
 375 ///////////////////////////////////////
 376 // RS Framework
 377 ///////////////////////////////////////
 378
 379 Value* ProfilerRS::Translate(Value* v) {
 380   if(TransCache[v])
 381     return TransCache[v];
 382
 383   if (BasicBlock* bb = dyn_cast<BasicBlock>(v)) {
 384     if (bb == &bb->getParent()->getEntryBlock())
 385       TransCache[bb] = bb; //don't translate entry block
 386     else
 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()) {
 395       TransCache[i] = i;
 396       return i;
 397     } else {
 398       //translate this
 399       Instruction* i2 = i->clone();
 400       if (i->hasName())
 401         i2->setName("dup_" + i->getName());
 402       TransCache[i] = i2;
 403       //NumNewInst++;
 404       for (unsigned x = 0; x < i2->getNumOperands(); ++x)
 405         i2->setOperand(x, Translate(i2->getOperand(x)));
 406       return i2;
 407     }
 408   } else if (isa<Function>(v) || isa<Constant>(v) || isa<Argument>(v)) {
 409     TransCache[v] = v;
 410     return v;
 411   }
 412   llvm_unreachable("Value not handled");
 413   return 0;
 414 }
 415
 416 void ProfilerRS::Duplicate(Function& F, RSProfilers& LI)
 417 {
 418   //perform a breadth first search, building up a duplicate of the code
 419   std::queue<BasicBlock*> worklist;
 420   std::set<BasicBlock*> seen;
 421
 422   //This loop ensures proper BB order, to help performance
 423   for (Function::iterator fib = F.begin(), fie = F.end(); fib != fie; ++fib)
 424     worklist.push(fib);
 425   while (!worklist.empty()) {
 426     Translate(worklist.front());
 427     worklist.pop();
 428   }
 429
 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());
 433
 434   while (!worklist.empty()) {
 435     BasicBlock* bb = worklist.front();
 436     worklist.pop();
 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();
 441            iib != iie; ++iib) {
 442         //NumOldInst++;
 443         if (!LI.isProfiling(&*iib)) {
 444           Instruction* i = cast<Instruction>(Translate(iib));
 445           instlist.insert(bbtarget->end(), i);
 446         }
 447       }
 448       //updated search state;
 449       seen.insert(bb);
 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()) {
 454           worklist.push(bbs);
 455         }
 456       }
 457     }
 458   }
 459 }
 460
 461 void ProfilerRS::ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F) {
 462   //given a backedge from B -> A, and translations A' and B',
 463   //a: insert C and C'
 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'
 474
 475   //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);
 482
 483   //b:
 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);
 487   //c:
 488   {
 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);
 493   }
 494   //d:
 495   {
 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);
 500   }
 501   //e:
 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);
 506   //f:
 507   ReplacePhiPred(cast<BasicBlock>(Translate(dst)),
 508                  cast<BasicBlock>(Translate(src)),bbCp);
 509   CollapsePhi(cast<BasicBlock>(Translate(dst)), bbCp);
 510   //g:
 511   for(BasicBlock::iterator ib = dst->begin(), ie = dst->end(); ib != ie;
 512       ++ib)
 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),
 518                                                      bbC);
 519         }
 520       phi->removeIncomingValue(bbC);
 521     }
 522 }
 523
 524 bool ProfilerRS::runOnFunction(Function& F) {
 525   if (!F.isDeclaration()) {
 526     std::set<std::pair<BasicBlock*, BasicBlock*> > BackEdges;
 527     RSProfilers& LI = getAnalysis<RSProfilers>();
 528
 529     getBackEdges(F, BackEdges);
 530     Duplicate(F, LI);
 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);
 536
 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),
 541                                               cast<BasicBlock>(
 542                    Translate(T->getSuccessor(0))),
 543                       ConstantInt::get(Type::getInt1Ty(F.getContext()), true)));
 544
 545     //do whatever is needed now that the function is duplicated
 546     c->PrepFunction(&F);
 547
 548     //add entry node to choice points
 549     ChoicePoints.insert(&F.getEntryBlock());
 550
 551     for (std::set<BasicBlock*>::iterator
 552            ii = ChoicePoints.begin(), ie = ChoicePoints.end(); ii != ie; ++ii)
 553       c->ProcessChoicePoint(*ii);
 554
 555     ChoicePoints.clear();
 556     TransCache.clear();
 557
 558     return true;
 559   }
 560   return false;
 561 }
 562
 563 bool ProfilerRS::doInitialization(Module &M) {
 564   switch (RandomMethod) {
 565   case GBV:
 566     c = new GlobalRandomCounter(M, Type::getInt32Ty(M.getContext()),
 567                                 (1 << 14) - 1);
 568     break;
 569   case GBVO:
 570     c = new GlobalRandomCounterOpt(M, Type::getInt32Ty(M.getContext()),
 571                                    (1 << 14) - 1);
 572     break;
 573   case HOSTCC:
 574     c = new CycleCounter(M, (1 << 14) - 1);
 575     break;
 576   };
 577   return true;
 578 }
 579
 580 void ProfilerRS::getAnalysisUsage(AnalysisUsage &AU) const {
 581   AU.addRequired<RSProfilers>();
 582   AU.addRequiredID(DemoteRegisterToMemoryID);
 583 }
 584
 585 ///////////////////////////////////////
 586 // Utilities:
 587 ///////////////////////////////////////
 588 static void ReplacePhiPred(BasicBlock* btarget,
 589                            BasicBlock* bold, BasicBlock* bnew) {
 590   for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
 591       ib != ie; ++ib)
 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);
 596     }
 597 }
 598
 599 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc) {
 600   for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
 601       ib != ie; ++ib)
 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);
 608         } else {
 609           counter[phi->getIncomingBlock(i)] = phi->getIncomingValue(i);
 610           ++i;
 611         }
 612       }
 613     }
 614 }
 615
 616 template<class T>
 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,
 621                         int& time)
 622 {
 623   color[bb] = 1;
 624   ++time;
 625   depth[bb] = time;
 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));
 633       //NumBackEdges++;
 634     }
 635   }
 636   color[bb] = 2;
 637   ++time;
 638   finish[bb] = time;
 639 }
 640
 641
 642
 643 //find the back edges and where they go to
 644 template<class T>
 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;
 649   int time = 0;
 650   recBackEdge(&F.getEntryBlock(), BackEdges, color, depth, finish, time);
 651   DEBUG(errs() << F.getName() << " " << BackEdges.size() << "\n");
 652 }
 653
 654
 655 //Creation functions
 656 ModulePass* llvm::createNullProfilerRSPass() {
 657   return new NullProfilerRS();
 658 }
 659
 660 FunctionPass* llvm::createRSProfilingPass() {
 661   return new ProfilerRS();
 662 }