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