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