lib/Transforms/Instrumentation/RSProfiling.cpp

   1 //===- RSProfiling.cpp - Various profiling using random sampling ----------===//
   2 //
   3 //                      The LLVM Compiler Infrastructure
   4 //
   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.
   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 recommeneded 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/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"
  47 #include <set>
  48 #include <map>
  49 #include <queue>
  50 #include <list>
  51 using namespace llvm;
  52
  53 namespace {
  54   enum RandomMeth {
  55     GBV, GBVO, HOSTCC
  56   };
  57
  58   cl::opt<RandomMeth> RandomMethod("profile-randomness",
  59       cl::desc("How to randomly choose to profile:"),
  60       cl::values(
  61                  clEnumValN(GBV, "global", "global counter"),
  62                  clEnumValN(GBVO, "ra_global",
  63                             "register allocated global counter"),
  64                  clEnumValN(HOSTCC, "rdcc", "cycle counter"),
  65                  clEnumValEnd));
  66
  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 {
  71   public:
  72     static const int ID; // Pass identifcation, replacement for typeid
  73     bool isProfiling(Value* v) {
  74       return false;
  75     }
  76     bool runOnModule(Module &M) {
  77       return false;
  78     }
  79     void getAnalysisUsage(AnalysisUsage &AU) const {
  80       AU.setPreservesAll();
  81     }
  82   };
  83
  84   const int RSProfilers::ID = 0;
  85   static RegisterAnalysisGroup<RSProfilers> A("Profiling passes");
  86   const int NullProfilerRS::ID = 0;
  87   static RegisterPass<NullProfilerRS> NP("insert-null-profiling-rs",
  88                                          "Measure profiling framework overhead");
  89   static RegisterAnalysisGroup<RSProfilers, true> NPT(NP);
  90
  91   /// Chooser - Something that chooses when to make a sample of the profiled code
  92   class VISIBILITY_HIDDEN Chooser {
  93   public:
  94     /// ProcessChoicePoint - is called for each basic block inserted to choose
  95     /// between normal and sample code
  96     virtual void ProcessChoicePoint(BasicBlock*) = 0;
  97     /// PrepFunction - is called once per function before other work is done.
  98     /// This gives the opertunity to insert new allocas and such.
  99     virtual void PrepFunction(Function*) = 0;
 100     virtual ~Chooser() {}
 101   };
 102
 103   //Things that implement sampling policies
 104   //A global value that is read-mod-stored to choose when to sample.
 105   //A sample is taken when the global counter hits 0
 106   class VISIBILITY_HIDDEN GlobalRandomCounter : public Chooser {
 107     GlobalVariable* Counter;
 108     Value* ResetValue;
 109     const Type* T;
 110   public:
 111     GlobalRandomCounter(Module& M, const Type* t, uint64_t resetval);
 112     virtual ~GlobalRandomCounter();
 113     virtual void PrepFunction(Function* F);
 114     virtual void ProcessChoicePoint(BasicBlock* bb);
 115   };
 116
 117   //Same is GRC, but allow register allocation of the global counter
 118   class VISIBILITY_HIDDEN GlobalRandomCounterOpt : public Chooser {
 119     GlobalVariable* Counter;
 120     Value* ResetValue;
 121     AllocaInst* AI;
 122     const Type* T;
 123   public:
 124     GlobalRandomCounterOpt(Module& M, const Type* t, uint64_t resetval);
 125     virtual ~GlobalRandomCounterOpt();
 126     virtual void PrepFunction(Function* F);
 127     virtual void ProcessChoicePoint(BasicBlock* bb);
 128   };
 129
 130   //Use the cycle counter intrinsic as a source of pseudo randomness when
 131   //deciding when to sample.
 132   class VISIBILITY_HIDDEN CycleCounter : public Chooser {
 133     uint64_t rm;
 134     Constant *F;
 135   public:
 136     CycleCounter(Module& m, uint64_t resetmask);
 137     virtual ~CycleCounter();
 138     virtual void PrepFunction(Function* F);
 139     virtual void ProcessChoicePoint(BasicBlock* bb);
 140   };
 141
 142   /// ProfilerRS - Insert the random sampling framework
 143   struct VISIBILITY_HIDDEN ProfilerRS : public FunctionPass {
 144     static const int ID; // Pass identifcation, replacement for typeid
 145     ProfilerRS() : FunctionPass((intptr_t)&ID) {}
 146
 147     std::map<Value*, Value*> TransCache;
 148     std::set<BasicBlock*> ChoicePoints;
 149     Chooser* c;
 150
 151     //Translate and duplicate values for the new profile free version of stuff
 152     Value* Translate(Value* v);
 153     //Duplicate an entire function (with out profiling)
 154     void Duplicate(Function& F, RSProfilers& LI);
 155     //Called once for each backedge, handle the insertion of choice points and
 156     //the interconection of the two versions of the code
 157     void ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F);
 158     bool runOnFunction(Function& F);
 159     bool doInitialization(Module &M);
 160     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 161   };
 162
 163   const int ProfilerRS::ID = 0;
 164   RegisterPass<ProfilerRS> X("insert-rs-profiling-framework",
 165                              "Insert random sampling instrumentation framework");
 166 }
 167
 168 //Local utilities
 169 static void ReplacePhiPred(BasicBlock* btarget,
 170                            BasicBlock* bold, BasicBlock* bnew);
 171
 172 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc);
 173
 174 template<class T>
 175 static void recBackEdge(BasicBlock* bb, T& BackEdges,
 176                         std::map<BasicBlock*, int>& color,
 177                         std::map<BasicBlock*, int>& depth,
 178                         std::map<BasicBlock*, int>& finish,
 179                         int& time);
 180
 181 //find the back edges and where they go to
 182 template<class T>
 183 static void getBackEdges(Function& F, T& BackEdges);
 184
 185
 186 ///////////////////////////////////////
 187 // Methods of choosing when to profile
 188 ///////////////////////////////////////
 189
 190 GlobalRandomCounter::GlobalRandomCounter(Module& M, const Type* t,
 191                                          uint64_t resetval) : T(t) {
 192   ConstantInt* Init = ConstantInt::get(T, resetval);
 193   ResetValue = Init;
 194   Counter = new GlobalVariable(T, false, GlobalValue::InternalLinkage,
 195                                Init, "RandomSteeringCounter", &M);
 196 }
 197
 198 GlobalRandomCounter::~GlobalRandomCounter() {}
 199
 200 void GlobalRandomCounter::PrepFunction(Function* F) {}
 201
 202 void GlobalRandomCounter::ProcessChoicePoint(BasicBlock* bb) {
 203   BranchInst* t = cast<BranchInst>(bb->getTerminator());
 204
 205   //decrement counter
 206   LoadInst* l = new LoadInst(Counter, "counter", t);
 207
 208   ICmpInst* s = new ICmpInst(ICmpInst::ICMP_EQ, l, ConstantInt::get(T, 0),
 209                              "countercc", t);
 210
 211   Value* nv = BinaryOperator::createSub(l, ConstantInt::get(T, 1),
 212                                         "counternew", t);
 213   new StoreInst(nv, Counter, t);
 214   t->setCondition(s);
 215
 216   //reset counter
 217   BasicBlock* oldnext = t->getSuccessor(0);
 218   BasicBlock* resetblock = new BasicBlock("reset", oldnext->getParent(),
 219                                           oldnext);
 220   TerminatorInst* t2 = new BranchInst(oldnext, resetblock);
 221   t->setSuccessor(0, resetblock);
 222   new StoreInst(ResetValue, Counter, t2);
 223   ReplacePhiPred(oldnext, bb, resetblock);
 224 }
 225
 226 GlobalRandomCounterOpt::GlobalRandomCounterOpt(Module& M, const Type* t,
 227                                                uint64_t resetval)
 228   : AI(0), T(t) {
 229   ConstantInt* Init = ConstantInt::get(T, resetval);
 230   ResetValue  = Init;
 231   Counter = new GlobalVariable(T, false, GlobalValue::InternalLinkage,
 232                                Init, "RandomSteeringCounter", &M);
 233 }
 234
 235 GlobalRandomCounterOpt::~GlobalRandomCounterOpt() {}
 236
 237 void GlobalRandomCounterOpt::PrepFunction(Function* F) {
 238   //make a local temporary to cache the global
 239   BasicBlock& bb = F->getEntryBlock();
 240   BasicBlock::iterator InsertPt = bb.begin();
 241   AI = new AllocaInst(T, 0, "localcounter", InsertPt);
 242   LoadInst* l = new LoadInst(Counter, "counterload", InsertPt);
 243   new StoreInst(l, AI, InsertPt);
 244
 245   //modify all functions and return values to restore the local variable to/from
 246   //the global variable
 247   for(Function::iterator fib = F->begin(), fie = F->end();
 248       fib != fie; ++fib)
 249     for(BasicBlock::iterator bib = fib->begin(), bie = fib->end();
 250         bib != bie; ++bib)
 251       if (isa<CallInst>(bib)) {
 252         LoadInst* l = new LoadInst(AI, "counter", bib);
 253         new StoreInst(l, Counter, bib);
 254         l = new LoadInst(Counter, "counter", ++bib);
 255         new StoreInst(l, AI, bib--);
 256       } else if (isa<InvokeInst>(bib)) {
 257         LoadInst* l = new LoadInst(AI, "counter", bib);
 258         new StoreInst(l, Counter, bib);
 259
 260         BasicBlock* bb = cast<InvokeInst>(bib)->getNormalDest();
 261         BasicBlock::iterator i = bb->begin();
 262         while (isa<PHINode>(i))
 263           ++i;
 264         l = new LoadInst(Counter, "counter", i);
 265
 266         bb = cast<InvokeInst>(bib)->getUnwindDest();
 267         i = bb->begin();
 268         while (isa<PHINode>(i)) ++i;
 269         l = new LoadInst(Counter, "counter", i);
 270         new StoreInst(l, AI, i);
 271       } else if (isa<UnwindInst>(&*bib) || isa<ReturnInst>(&*bib)) {
 272         LoadInst* l = new LoadInst(AI, "counter", bib);
 273         new StoreInst(l, Counter, bib);
 274       }
 275 }
 276
 277 void GlobalRandomCounterOpt::ProcessChoicePoint(BasicBlock* bb) {
 278   BranchInst* t = cast<BranchInst>(bb->getTerminator());
 279
 280   //decrement counter
 281   LoadInst* l = new LoadInst(AI, "counter", t);
 282
 283   ICmpInst* s = new ICmpInst(ICmpInst::ICMP_EQ, l, ConstantInt::get(T, 0),
 284                              "countercc", t);
 285
 286   Value* nv = BinaryOperator::createSub(l, ConstantInt::get(T, 1),
 287                                         "counternew", t);
 288   new StoreInst(nv, AI, t);
 289   t->setCondition(s);
 290
 291   //reset counter
 292   BasicBlock* oldnext = t->getSuccessor(0);
 293   BasicBlock* resetblock = new BasicBlock("reset", oldnext->getParent(),
 294                                           oldnext);
 295   TerminatorInst* t2 = new BranchInst(oldnext, resetblock);
 296   t->setSuccessor(0, resetblock);
 297   new StoreInst(ResetValue, AI, t2);
 298   ReplacePhiPred(oldnext, bb, resetblock);
 299 }
 300
 301
 302 CycleCounter::CycleCounter(Module& m, uint64_t resetmask) : rm(resetmask) {
 303   F = m.getOrInsertFunction("llvm.readcyclecounter", Type::Int64Ty, NULL);
 304 }
 305
 306 CycleCounter::~CycleCounter() {}
 307
 308 void CycleCounter::PrepFunction(Function* F) {}
 309
 310 void CycleCounter::ProcessChoicePoint(BasicBlock* bb) {
 311   BranchInst* t = cast<BranchInst>(bb->getTerminator());
 312
 313   CallInst* c = new CallInst(F, "rdcc", t);
 314   BinaryOperator* b =
 315     BinaryOperator::createAnd(c, ConstantInt::get(Type::Int64Ty, rm),
 316                               "mrdcc", t);
 317
 318   ICmpInst *s = new ICmpInst(ICmpInst::ICMP_EQ, b,
 319                              ConstantInt::get(Type::Int64Ty, 0),
 320                              "mrdccc", t);
 321
 322   t->setCondition(s);
 323 }
 324
 325 ///////////////////////////////////////
 326 // Profiling:
 327 ///////////////////////////////////////
 328 bool RSProfilers_std::isProfiling(Value* v) {
 329   if (profcode.find(v) != profcode.end())
 330     return true;
 331   //else
 332   RSProfilers& LI = getAnalysis<RSProfilers>();
 333   return LI.isProfiling(v);
 334 }
 335
 336 void RSProfilers_std::IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum,
 337                                           GlobalValue *CounterArray) {
 338   // Insert the increment after any alloca or PHI instructions...
 339   BasicBlock::iterator InsertPos = BB->begin();
 340   while (isa<AllocaInst>(InsertPos) || isa<PHINode>(InsertPos))
 341     ++InsertPos;
 342
 343   // Create the getelementptr constant expression
 344   std::vector<Constant*> Indices(2);
 345   Indices[0] = Constant::getNullValue(Type::Int32Ty);
 346   Indices[1] = ConstantInt::get(Type::Int32Ty, CounterNum);
 347   Constant *ElementPtr = ConstantExpr::getGetElementPtr(CounterArray,
 348                                                         &Indices[0], 2);
 349
 350   // Load, increment and store the value back.
 351   Value *OldVal = new LoadInst(ElementPtr, "OldCounter", InsertPos);
 352   profcode.insert(OldVal);
 353   Value *NewVal = BinaryOperator::createAdd(OldVal,
 354                                             ConstantInt::get(Type::Int32Ty, 1),
 355                                             "NewCounter", InsertPos);
 356   profcode.insert(NewVal);
 357   profcode.insert(new StoreInst(NewVal, ElementPtr, InsertPos));
 358 }
 359
 360 void RSProfilers_std::getAnalysisUsage(AnalysisUsage &AU) const {
 361   //grab any outstanding profiler, or get the null one
 362   AU.addRequired<RSProfilers>();
 363 }
 364
 365 ///////////////////////////////////////
 366 // RS Framework
 367 ///////////////////////////////////////
 368
 369 Value* ProfilerRS::Translate(Value* v) {
 370   if(TransCache[v])
 371     return TransCache[v];
 372
 373   if (BasicBlock* bb = dyn_cast<BasicBlock>(v)) {
 374     if (bb == &bb->getParent()->getEntryBlock())
 375       TransCache[bb] = bb; //don't translate entry block
 376     else
 377       TransCache[bb] = new BasicBlock("dup_" + bb->getName(), bb->getParent(),
 378                                       NULL);
 379     return TransCache[bb];
 380   } else if (Instruction* i = dyn_cast<Instruction>(v)) {
 381     //we have already translated this
 382     //do not translate entry block allocas
 383     if(&i->getParent()->getParent()->getEntryBlock() == i->getParent()) {
 384       TransCache[i] = i;
 385       return i;
 386     } else {
 387       //translate this
 388       Instruction* i2 = i->clone();
 389       if (i->hasName())
 390         i2->setName("dup_" + i->getName());
 391       TransCache[i] = i2;
 392       //NumNewInst++;
 393       for (unsigned x = 0; x < i2->getNumOperands(); ++x)
 394         i2->setOperand(x, Translate(i2->getOperand(x)));
 395       return i2;
 396     }
 397   } else if (isa<Function>(v) || isa<Constant>(v) || isa<Argument>(v)) {
 398     TransCache[v] = v;
 399     return v;
 400   }
 401   assert(0 && "Value not handled");
 402   return 0;
 403 }
 404
 405 void ProfilerRS::Duplicate(Function& F, RSProfilers& LI)
 406 {
 407   //perform a breadth first search, building up a duplicate of the code
 408   std::queue<BasicBlock*> worklist;
 409   std::set<BasicBlock*> seen;
 410
 411   //This loop ensures proper BB order, to help performance
 412   for (Function::iterator fib = F.begin(), fie = F.end(); fib != fie; ++fib)
 413     worklist.push(fib);
 414   while (!worklist.empty()) {
 415     Translate(worklist.front());
 416     worklist.pop();
 417   }
 418
 419   //remember than reg2mem created a new entry block we don't want to duplicate
 420   worklist.push(F.getEntryBlock().getTerminator()->getSuccessor(0));
 421   seen.insert(&F.getEntryBlock());
 422
 423   while (!worklist.empty()) {
 424     BasicBlock* bb = worklist.front();
 425     worklist.pop();
 426     if(seen.find(bb) == seen.end()) {
 427       BasicBlock* bbtarget = cast<BasicBlock>(Translate(bb));
 428       BasicBlock::InstListType& instlist = bbtarget->getInstList();
 429       for (BasicBlock::iterator iib = bb->begin(), iie = bb->end();
 430            iib != iie; ++iib) {
 431         //NumOldInst++;
 432         if (!LI.isProfiling(&*iib)) {
 433           Instruction* i = cast<Instruction>(Translate(iib));
 434           instlist.insert(bbtarget->end(), i);
 435         }
 436       }
 437       //updated search state;
 438       seen.insert(bb);
 439       TerminatorInst* ti = bb->getTerminator();
 440       for (unsigned x = 0; x < ti->getNumSuccessors(); ++x) {
 441         BasicBlock* bbs = ti->getSuccessor(x);
 442         if (seen.find(bbs) == seen.end()) {
 443           worklist.push(bbs);
 444         }
 445       }
 446     }
 447   }
 448 }
 449
 450 void ProfilerRS::ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F) {
 451   //given a backedge from B -> A, and translations A' and B',
 452   //a: insert C and C'
 453   //b: add branches in C to A and A' and in C' to A and A'
 454   //c: mod terminators@B, replace A with C
 455   //d: mod terminators@B', replace A' with C'
 456   //e: mod phis@A for pred B to be pred C
 457   //       if multiple entries, simplify to one
 458   //f: mod phis@A' for pred B' to be pred C'
 459   //       if multiple entries, simplify to one
 460   //g: for all phis@A with pred C using x
 461   //       add in edge from C' using x'
 462   //       add in edge from C using x in A'
 463
 464   //a:
 465   Function::iterator BBN = src; ++BBN;
 466   BasicBlock* bbC = new BasicBlock("choice", &F, BBN);
 467   //ChoicePoints.insert(bbC);
 468   BBN = cast<BasicBlock>(Translate(src));
 469   BasicBlock* bbCp = new BasicBlock("choice", &F, ++BBN);
 470   ChoicePoints.insert(bbCp);
 471
 472   //b:
 473   new BranchInst(cast<BasicBlock>(Translate(dst)), bbC);
 474   new BranchInst(dst, cast<BasicBlock>(Translate(dst)),
 475                  ConstantInt::get(Type::Int1Ty, true), bbCp);
 476   //c:
 477   {
 478     TerminatorInst* iB = src->getTerminator();
 479     for (unsigned x = 0; x < iB->getNumSuccessors(); ++x)
 480       if (iB->getSuccessor(x) == dst)
 481         iB->setSuccessor(x, bbC);
 482   }
 483   //d:
 484   {
 485     TerminatorInst* iBp = cast<TerminatorInst>(Translate(src->getTerminator()));
 486     for (unsigned x = 0; x < iBp->getNumSuccessors(); ++x)
 487       if (iBp->getSuccessor(x) == cast<BasicBlock>(Translate(dst)))
 488         iBp->setSuccessor(x, bbCp);
 489   }
 490   //e:
 491   ReplacePhiPred(dst, src, bbC);
 492   //src could be a switch, in which case we are replacing several edges with one
 493   //thus collapse those edges int the Phi
 494   CollapsePhi(dst, bbC);
 495   //f:
 496   ReplacePhiPred(cast<BasicBlock>(Translate(dst)),
 497                  cast<BasicBlock>(Translate(src)),bbCp);
 498   CollapsePhi(cast<BasicBlock>(Translate(dst)), bbCp);
 499   //g:
 500   for(BasicBlock::iterator ib = dst->begin(), ie = dst->end(); ib != ie;
 501       ++ib)
 502     if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
 503       for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x)
 504         if(bbC == phi->getIncomingBlock(x)) {
 505           phi->addIncoming(Translate(phi->getIncomingValue(x)), bbCp);
 506           cast<PHINode>(Translate(phi))->addIncoming(phi->getIncomingValue(x),
 507                                                      bbC);
 508         }
 509       phi->removeIncomingValue(bbC);
 510     }
 511 }
 512
 513 bool ProfilerRS::runOnFunction(Function& F) {
 514   if (!F.isDeclaration()) {
 515     std::set<std::pair<BasicBlock*, BasicBlock*> > BackEdges;
 516     RSProfilers& LI = getAnalysis<RSProfilers>();
 517
 518     getBackEdges(F, BackEdges);
 519     Duplicate(F, LI);
 520     //assume that stuff worked.  now connect the duplicated basic blocks
 521     //with the originals in such a way as to preserve ssa.  yuk!
 522     for (std::set<std::pair<BasicBlock*, BasicBlock*> >::iterator
 523            ib = BackEdges.begin(), ie = BackEdges.end(); ib != ie; ++ib)
 524       ProcessBackEdge(ib->first, ib->second, F);
 525
 526     //oh, and add the edge from the reg2mem created entry node to the
 527     //duplicated second node
 528     TerminatorInst* T = F.getEntryBlock().getTerminator();
 529     ReplaceInstWithInst(T, new BranchInst(T->getSuccessor(0),
 530                                           cast<BasicBlock>(
 531                                             Translate(T->getSuccessor(0))),
 532                                           ConstantInt::get(Type::Int1Ty, true)));
 533
 534     //do whatever is needed now that the function is duplicated
 535     c->PrepFunction(&F);
 536
 537     //add entry node to choice points
 538     ChoicePoints.insert(&F.getEntryBlock());
 539
 540     for (std::set<BasicBlock*>::iterator
 541            ii = ChoicePoints.begin(), ie = ChoicePoints.end(); ii != ie; ++ii)
 542       c->ProcessChoicePoint(*ii);
 543
 544     ChoicePoints.clear();
 545     TransCache.clear();
 546
 547     return true;
 548   }
 549   return false;
 550 }
 551
 552 bool ProfilerRS::doInitialization(Module &M) {
 553   switch (RandomMethod) {
 554   case GBV:
 555     c = new GlobalRandomCounter(M, Type::Int32Ty, (1 << 14) - 1);
 556     break;
 557   case GBVO:
 558     c = new GlobalRandomCounterOpt(M, Type::Int32Ty, (1 << 14) - 1);
 559     break;
 560   case HOSTCC:
 561     c = new CycleCounter(M, (1 << 14) - 1);
 562     break;
 563   };
 564   return true;
 565 }
 566
 567 void ProfilerRS::getAnalysisUsage(AnalysisUsage &AU) const {
 568   AU.addRequired<RSProfilers>();
 569   AU.addRequiredID(DemoteRegisterToMemoryID);
 570 }
 571
 572 ///////////////////////////////////////
 573 // Utilities:
 574 ///////////////////////////////////////
 575 static void ReplacePhiPred(BasicBlock* btarget,
 576                            BasicBlock* bold, BasicBlock* bnew) {
 577   for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
 578       ib != ie; ++ib)
 579     if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
 580       for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x)
 581         if(bold == phi->getIncomingBlock(x))
 582           phi->setIncomingBlock(x, bnew);
 583     }
 584 }
 585
 586 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc) {
 587   for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
 588       ib != ie; ++ib)
 589     if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
 590       std::map<BasicBlock*, Value*> counter;
 591       for(unsigned i = 0; i < phi->getNumIncomingValues(); ) {
 592         if (counter[phi->getIncomingBlock(i)]) {
 593           assert(phi->getIncomingValue(i) == counter[phi->getIncomingBlock(i)]);
 594           phi->removeIncomingValue(i, false);
 595         } else {
 596           counter[phi->getIncomingBlock(i)] = phi->getIncomingValue(i);
 597           ++i;
 598         }
 599       }
 600     }
 601 }
 602
 603 template<class T>
 604 static void recBackEdge(BasicBlock* bb, T& BackEdges,
 605                         std::map<BasicBlock*, int>& color,
 606                         std::map<BasicBlock*, int>& depth,
 607                         std::map<BasicBlock*, int>& finish,
 608                         int& time)
 609 {
 610   color[bb] = 1;
 611   ++time;
 612   depth[bb] = time;
 613   TerminatorInst* t= bb->getTerminator();
 614   for(unsigned i = 0; i < t->getNumSuccessors(); ++i) {
 615     BasicBlock* bbnew = t->getSuccessor(i);
 616     if (color[bbnew] == 0)
 617       recBackEdge(bbnew, BackEdges, color, depth, finish, time);
 618     else if (color[bbnew] == 1) {
 619       BackEdges.insert(std::make_pair(bb, bbnew));
 620       //NumBackEdges++;
 621     }
 622   }
 623   color[bb] = 2;
 624   ++time;
 625   finish[bb] = time;
 626 }
 627
 628
 629
 630 //find the back edges and where they go to
 631 template<class T>
 632 static void getBackEdges(Function& F, T& BackEdges) {
 633   std::map<BasicBlock*, int> color;
 634   std::map<BasicBlock*, int> depth;
 635   std::map<BasicBlock*, int> finish;
 636   int time = 0;
 637   recBackEdge(&F.getEntryBlock(), BackEdges, color, depth, finish, time);
 638   DOUT << F.getName() << " " << BackEdges.size() << "\n";
 639 }
 640
 641
 642 //Creation functions
 643 ModulePass* llvm::createNullProfilerRSPass() {
 644   return new NullProfilerRS();
 645 }
 646
 647 FunctionPass* llvm::createRSProfilingPass() {
 648   return new ProfilerRS();
 649 }