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