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