lib/Transforms/Instrumentation/RSProfiling.cpp

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