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