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