LLVM API Documentation

RSProfiling.cpp

Go to the documentation of this file.
00001 //===- RSProfiling.cpp - Various profiling using random sampling ----------===//
00002 //
00003 //                      The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // These passes implement a random sampling based profiling.  Different methods
00011 // of choosing when to sample are supported, as well as different types of
00012 // profiling.  This is done as two passes.  The first is a sequence of profiling
00013 // passes which insert profiling into the program, and remember what they 
00014 // inserted.
00015 //
00016 // The second stage duplicates all instructions in a function, ignoring the 
00017 // profiling code, then connects the two versions togeather at the entry and at
00018 // backedges.  At each connection point a choice is made as to whether to jump
00019 // to the profiled code (take a sample) or execute the unprofiled code.
00020 //
00021 // It is highly recommeneded that after this pass one runs mem2reg and adce
00022 // (instcombine load-vn gdce dse also are good to run afterwards)
00023 //
00024 // This design is intended to make the profiling passes independent of the RS
00025 // framework, but any profiling pass that implements the RSProfiling interface
00026 // is compatible with the rs framework (and thus can be sampled)
00027 //
00028 // TODO: obviously the block and function profiling are almost identical to the
00029 // existing ones, so they can be unified (esp since these passes are valid
00030 // without the rs framework).
00031 // TODO: Fix choice code so that frequency is not hard coded
00032 //
00033 //===----------------------------------------------------------------------===//
00034 
00035 #include "llvm/Pass.h"
00036 #include "llvm/Module.h"
00037 #include "llvm/Instructions.h"
00038 #include "llvm/Constants.h"
00039 #include "llvm/DerivedTypes.h"
00040 #include "llvm/Transforms/Scalar.h"
00041 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00042 #include "llvm/ADT/Statistic.h"
00043 #include "llvm/Support/CommandLine.h"
00044 #include "llvm/Support/Debug.h"
00045 #include "llvm/Transforms/Instrumentation.h"
00046 //#include "ProfilingUtils.h"
00047 #include "RSProfiling.h"
00048 
00049 #include <set>
00050 #include <map>
00051 #include <queue>
00052 #include <list>
00053 #include <iostream>
00054 
00055 using namespace llvm;
00056 
00057 namespace {
00058   Statistic<> NumBackEdges("bedge", "Number of BackEdges");
00059 
00060   enum RandomMeth {
00061     GBV, GBVO, HOSTCC
00062   };
00063 
00064   cl::opt<RandomMeth> RandomMethod("profile-randomness",
00065       cl::desc("How to randomly choose to profile:"),
00066       cl::values(
00067                  clEnumValN(GBV, "global", "global counter"),
00068                  clEnumValN(GBVO, "ra_global", 
00069           "register allocated global counter"),
00070                  clEnumValN(HOSTCC, "rdcc", "cycle counter"),
00071                  clEnumValEnd));
00072   
00073   /// NullProfilerRS - The basic profiler that does nothing.  It is the default
00074   /// profiler and thus terminates RSProfiler chains.  It is useful for 
00075   /// measuring framework overhead
00076   class NullProfilerRS : public RSProfilers {
00077   public:
00078     bool isProfiling(Value* v) {
00079       return false;
00080     }
00081     bool runOnModule(Module &M) {
00082       return false;
00083     }
00084     void getAnalysisUsage(AnalysisUsage &AU) const {
00085       AU.setPreservesAll();
00086     }
00087   };
00088 
00089   static RegisterAnalysisGroup<RSProfilers> A("Profiling passes");
00090   static RegisterOpt<NullProfilerRS> NP("insert-null-profiling-rs",
00091           "Measure profiling framework overhead");
00092   static RegisterAnalysisGroup<RSProfilers, NullProfilerRS, true> NPT;
00093 
00094   /// Chooser - Something that chooses when to make a sample of the profiled code
00095   class Chooser {
00096   public:
00097     /// ProcessChoicePoint - is called for each basic block inserted to choose 
00098     /// between normal and sample code
00099     virtual void ProcessChoicePoint(BasicBlock*) = 0;
00100     /// PrepFunction - is called once per function before other work is done.
00101     /// This gives the opertunity to insert new allocas and such.
00102     virtual void PrepFunction(Function*) = 0;
00103     virtual ~Chooser() {}
00104   };
00105 
00106   //Things that implement sampling policies
00107   //A global value that is read-mod-stored to choose when to sample.
00108   //A sample is taken when the global counter hits 0
00109   class GlobalRandomCounter : public Chooser {
00110     GlobalVariable* Counter;
00111     Value* ResetValue;
00112     const Type* T;
00113   public:
00114     GlobalRandomCounter(Module& M, const Type* t, uint64_t resetval);
00115     virtual ~GlobalRandomCounter();
00116     virtual void PrepFunction(Function* F);
00117     virtual void ProcessChoicePoint(BasicBlock* bb);
00118   };
00119 
00120   //Same is GRC, but allow register allocation of the global counter
00121   class GlobalRandomCounterOpt : public Chooser {
00122     GlobalVariable* Counter;
00123     Value* ResetValue;
00124     AllocaInst* AI;
00125     const Type* T;
00126   public:
00127     GlobalRandomCounterOpt(Module& M, const Type* t, uint64_t resetval);
00128     virtual ~GlobalRandomCounterOpt();
00129     virtual void PrepFunction(Function* F);
00130     virtual void ProcessChoicePoint(BasicBlock* bb);
00131   };
00132 
00133   //Use the cycle counter intrinsic as a source of pseudo randomness when
00134   //deciding when to sample.
00135   class CycleCounter : public Chooser {
00136     uint64_t rm;
00137     Function* F;
00138   public:
00139     CycleCounter(Module& m, uint64_t resetmask);
00140     virtual ~CycleCounter();
00141     virtual void PrepFunction(Function* F);
00142     virtual void ProcessChoicePoint(BasicBlock* bb);
00143   };
00144 
00145   /// ProfilerRS - Insert the random sampling framework
00146   struct ProfilerRS : public FunctionPass {
00147     std::map<Value*, Value*> TransCache;
00148     std::set<BasicBlock*> ChoicePoints;
00149     Chooser* c;
00150 
00151     //Translate and duplicate values for the new profile free version of stuff
00152     Value* Translate(Value* v);
00153     //Duplicate an entire function (with out profiling)
00154     void Duplicate(Function& F, RSProfilers& LI);
00155     //Called once for each backedge, handle the insertion of choice points and
00156     //the interconection of the two versions of the code
00157     void ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F);
00158     bool runOnFunction(Function& F);
00159     bool doInitialization(Module &M);
00160     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00161   };
00162 
00163   RegisterOpt<ProfilerRS> X("insert-rs-profiling-framework",
00164          "Insert random sampling instrumentation  framework");
00165 };
00166 
00167 //Local utilities
00168 static void ReplacePhiPred(BasicBlock* btarget, 
00169                            BasicBlock* bold, BasicBlock* bnew);
00170 
00171 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc);
00172 
00173 template<class T>
00174 static void recBackEdge(BasicBlock* bb, T& BackEdges, 
00175                         std::map<BasicBlock*, int>& color,
00176                         std::map<BasicBlock*, int>& depth,
00177                         std::map<BasicBlock*, int>& finish,
00178                         int& time);
00179 
00180 //find the back edges and where they go to
00181 template<class T>
00182 static void getBackEdges(Function& F, T& BackEdges);
00183 
00184 
00185 ///////////////////////////////////////
00186 // Methods of choosing when to profile
00187 ///////////////////////////////////////
00188   
00189 GlobalRandomCounter::GlobalRandomCounter(Module& M, const Type* t, 
00190                                          uint64_t resetval) : T(t) {
00191   Counter = new GlobalVariable(T, false, GlobalValue::InternalLinkage,
00192                                ConstantUInt::get(T, resetval),
00193                                "RandomSteeringCounter", &M);
00194   ResetValue = ConstantUInt::get(T, resetval);
00195 }
00196 
00197 GlobalRandomCounter::~GlobalRandomCounter() {}
00198 
00199 void GlobalRandomCounter::PrepFunction(Function* F) {}
00200 
00201 void GlobalRandomCounter::ProcessChoicePoint(BasicBlock* bb) {
00202   BranchInst* t = cast<BranchInst>(bb->getTerminator());
00203   
00204   //decrement counter
00205   LoadInst* l = new LoadInst(Counter, "counter", t);
00206   
00207   SetCondInst* s = new SetCondInst(Instruction::SetEQ, l, 
00208            ConstantUInt::get(T, 0), 
00209                                    "countercc", t);
00210   Value* nv = BinaryOperator::createSub(l, ConstantInt::get(T, 1),
00211                                      "counternew", t);
00212   new StoreInst(nv, Counter, t);
00213   t->setCondition(s);
00214   
00215   //reset counter
00216   BasicBlock* oldnext = t->getSuccessor(0);
00217   BasicBlock* resetblock = new BasicBlock("reset", oldnext->getParent(), 
00218             oldnext);
00219   TerminatorInst* t2 = new BranchInst(oldnext, resetblock);
00220   t->setSuccessor(0, resetblock);
00221   new StoreInst(ResetValue, Counter, t2);
00222   ReplacePhiPred(oldnext, bb, resetblock);
00223 }
00224 
00225 GlobalRandomCounterOpt::GlobalRandomCounterOpt(Module& M, const Type* t, 
00226                                                uint64_t resetval) 
00227   : AI(0), T(t) {
00228   Counter = new GlobalVariable(T, false, GlobalValue::InternalLinkage,
00229                                ConstantUInt::get(T, resetval),
00230                                "RandomSteeringCounter", &M);
00231   ResetValue = ConstantUInt::get(T, resetval);
00232 }
00233 
00234 GlobalRandomCounterOpt::~GlobalRandomCounterOpt() {}
00235 
00236 void GlobalRandomCounterOpt::PrepFunction(Function* F) {
00237   //make a local temporary to cache the global
00238   BasicBlock& bb = F->getEntryBlock();
00239   AI = new AllocaInst(T, 0, "localcounter", bb.begin());
00240   LoadInst* l = new LoadInst(Counter, "counterload", AI->getNext());
00241   new StoreInst(l, AI, l->getNext());
00242   
00243   //modify all functions and return values to restore the local variable to/from
00244   //the global variable
00245   for(Function::iterator fib = F->begin(), fie = F->end();
00246       fib != fie; ++fib)
00247     for(BasicBlock::iterator bib = fib->begin(), bie = fib->end();
00248         bib != bie; ++bib)
00249       if (isa<CallInst>(&*bib)) {
00250         LoadInst* l = new LoadInst(AI, "counter", bib);
00251         new StoreInst(l, Counter, bib);
00252         l = new LoadInst(Counter, "counter", bib->getNext());
00253         new StoreInst(l, AI, l->getNext());
00254       } else if (isa<InvokeInst>(&*bib)) {
00255         LoadInst* l = new LoadInst(AI, "counter", bib);
00256         new StoreInst(l, Counter, bib);
00257         
00258         BasicBlock* bb = cast<InvokeInst>(&*bib)->getNormalDest();
00259         Instruction* i = bb->begin();
00260         while (isa<PHINode>(i)) i = i->getNext();
00261         l = new LoadInst(Counter, "counter", i);
00262         
00263         bb = cast<InvokeInst>(&*bib)->getUnwindDest();
00264         i = bb->begin();
00265         while (isa<PHINode>(i)) i = i->getNext();
00266         l = new LoadInst(Counter, "counter", i);
00267         new StoreInst(l, AI, l->getNext());
00268       } else if (isa<UnwindInst>(&*bib) || isa<ReturnInst>(&*bib)) {
00269         LoadInst* l = new LoadInst(AI, "counter", bib);
00270         new StoreInst(l, Counter, bib);
00271       }
00272 }
00273 
00274 void GlobalRandomCounterOpt::ProcessChoicePoint(BasicBlock* bb) {
00275   BranchInst* t = cast<BranchInst>(bb->getTerminator());
00276   
00277   //decrement counter
00278   LoadInst* l = new LoadInst(AI, "counter", t);
00279   
00280   SetCondInst* s = new SetCondInst(Instruction::SetEQ, l, 
00281            ConstantUInt::get(T, 0), 
00282                                    "countercc", t);
00283   Value* nv = BinaryOperator::createSub(l, ConstantInt::get(T, 1),
00284                                      "counternew", t);
00285   new StoreInst(nv, AI, t);
00286   t->setCondition(s);
00287   
00288   //reset counter
00289   BasicBlock* oldnext = t->getSuccessor(0);
00290   BasicBlock* resetblock = new BasicBlock("reset", oldnext->getParent(), 
00291             oldnext);
00292   TerminatorInst* t2 = new BranchInst(oldnext, resetblock);
00293   t->setSuccessor(0, resetblock);
00294   new StoreInst(ResetValue, AI, t2);
00295   ReplacePhiPred(oldnext, bb, resetblock);
00296 }
00297 
00298 
00299 CycleCounter::CycleCounter(Module& m, uint64_t resetmask) : rm(resetmask) {
00300   F = m.getOrInsertFunction("llvm.readcyclecounter", Type::ULongTy, NULL);
00301 }
00302 
00303 CycleCounter::~CycleCounter() {}
00304 
00305 void CycleCounter::PrepFunction(Function* F) {}
00306 
00307 void CycleCounter::ProcessChoicePoint(BasicBlock* bb) {
00308   BranchInst* t = cast<BranchInst>(bb->getTerminator());
00309   
00310   CallInst* c = new CallInst(F, "rdcc", t);
00311   BinaryOperator* b = 
00312     BinaryOperator::createAnd(c, ConstantUInt::get(Type::ULongTy, rm),
00313             "mrdcc", t);
00314   
00315   SetCondInst* s = new SetCondInst(Instruction::SetEQ, b, 
00316            ConstantUInt::get(Type::ULongTy, 0), 
00317                                    "mrdccc", t);
00318   t->setCondition(s);
00319 }
00320 
00321 ///////////////////////////////////////
00322 // Profiling:
00323 ///////////////////////////////////////
00324 bool RSProfilers_std::isProfiling(Value* v) {
00325   if (profcode.find(v) != profcode.end())
00326     return true;
00327   //else
00328   RSProfilers& LI = getAnalysis<RSProfilers>();
00329   return LI.isProfiling(v);
00330 }
00331 
00332 void RSProfilers_std::IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum,
00333                                           GlobalValue *CounterArray) {
00334   // Insert the increment after any alloca or PHI instructions...
00335   BasicBlock::iterator InsertPos = BB->begin();
00336   while (isa<AllocaInst>(InsertPos) || isa<PHINode>(InsertPos))
00337     ++InsertPos;
00338   
00339   // Create the getelementptr constant expression
00340   std::vector<Constant*> Indices(2);
00341   Indices[0] = Constant::getNullValue(Type::IntTy);
00342   Indices[1] = ConstantSInt::get(Type::IntTy, CounterNum);
00343   Constant *ElementPtr = ConstantExpr::getGetElementPtr(CounterArray, Indices);
00344   
00345   // Load, increment and store the value back.
00346   Value *OldVal = new LoadInst(ElementPtr, "OldCounter", InsertPos);
00347   profcode.insert(OldVal);
00348   Value *NewVal = BinaryOperator::createAdd(OldVal,
00349               ConstantInt::get(Type::UIntTy, 1),
00350               "NewCounter", InsertPos);
00351   profcode.insert(NewVal);
00352   profcode.insert(new StoreInst(NewVal, ElementPtr, InsertPos));
00353 }
00354 
00355 void RSProfilers_std::getAnalysisUsage(AnalysisUsage &AU) const {
00356   //grab any outstanding profiler, or get the null one
00357   AU.addRequired<RSProfilers>();
00358 }
00359 
00360 ///////////////////////////////////////
00361 // RS Framework
00362 ///////////////////////////////////////
00363 
00364 Value* ProfilerRS::Translate(Value* v) {
00365   if(TransCache[v])
00366     return TransCache[v];
00367   
00368   if (BasicBlock* bb = dyn_cast<BasicBlock>(v)) {
00369     if (bb == &bb->getParent()->getEntryBlock())
00370       TransCache[bb] = bb; //don't translate entry block
00371     else
00372       TransCache[bb] = new BasicBlock("dup_" + bb->getName(), bb->getParent(), 
00373               NULL);
00374     return TransCache[bb];
00375   } else if (Instruction* i = dyn_cast<Instruction>(v)) {
00376     //we have already translated this
00377     //do not translate entry block allocas
00378     if(&i->getParent()->getParent()->getEntryBlock() == i->getParent()) {
00379       TransCache[i] = i;
00380       return i;
00381     } else {
00382       //translate this
00383       Instruction* i2 = i->clone();
00384       if (i->hasName())
00385         i2->setName("dup_" + i->getName());
00386       TransCache[i] = i2;
00387       //NumNewInst++;
00388       for (unsigned x = 0; x < i2->getNumOperands(); ++x)
00389         i2->setOperand(x, Translate(i2->getOperand(x)));
00390       return i2;
00391     }
00392   } else if (isa<Function>(v) || isa<Constant>(v) || isa<Argument>(v)) {
00393     TransCache[v] = v;
00394     return v;
00395   }
00396   assert(0 && "Value not handled");
00397   return 0;
00398 }
00399 
00400 void ProfilerRS::Duplicate(Function& F, RSProfilers& LI)
00401 {
00402   //perform a breadth first search, building up a duplicate of the code
00403   std::queue<BasicBlock*> worklist;
00404   std::set<BasicBlock*> seen;
00405   
00406   //This loop ensures proper BB order, to help performance
00407   for (Function::iterator fib = F.begin(), fie = F.end(); fib != fie; ++fib)
00408     worklist.push(fib);
00409   while (!worklist.empty()) {
00410     Translate(worklist.front());
00411     worklist.pop();
00412   }
00413   
00414   //remember than reg2mem created a new entry block we don't want to duplicate
00415   worklist.push(F.getEntryBlock().getTerminator()->getSuccessor(0));
00416   seen.insert(&F.getEntryBlock());
00417   
00418   while (!worklist.empty()) {
00419     BasicBlock* bb = worklist.front();
00420     worklist.pop();
00421     if(seen.find(bb) == seen.end()) {
00422       BasicBlock* bbtarget = cast<BasicBlock>(Translate(bb));
00423       BasicBlock::InstListType& instlist = bbtarget->getInstList();
00424       for (BasicBlock::iterator iib = bb->begin(), iie = bb->end(); 
00425            iib != iie; ++iib) {
00426         //NumOldInst++;
00427         if (!LI.isProfiling(&*iib)) {
00428           Instruction* i = cast<Instruction>(Translate(iib));
00429           instlist.insert(bbtarget->end(), i);
00430         }
00431       }
00432       //updated search state;
00433       seen.insert(bb);
00434       TerminatorInst* ti = bb->getTerminator();
00435       for (unsigned x = 0; x < ti->getNumSuccessors(); ++x) {
00436         BasicBlock* bbs = ti->getSuccessor(x);
00437         if (seen.find(bbs) == seen.end()) {
00438           worklist.push(bbs);
00439         }
00440       }
00441     }
00442   }
00443 }
00444 
00445 void ProfilerRS::ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F) {
00446   //given a backedge from B -> A, and translations A' and B',
00447   //a: insert C and C'
00448   //b: add branches in C to A and A' and in C' to A and A'
00449   //c: mod terminators@B, replace A with C
00450   //d: mod terminators@B', replace A' with C'
00451   //e: mod phis@A for pred B to be pred C
00452   //       if multiple entries, simplify to one
00453   //f: mod phis@A' for pred B' to be pred C'
00454   //       if multiple entries, simplify to one
00455   //g: for all phis@A with pred C using x
00456   //       add in edge from C' using x'
00457   //       add in edge from C using x in A'
00458   
00459   //a:
00460   BasicBlock* bbC = new BasicBlock("choice", &F, src->getNext() );
00461   //ChoicePoints.insert(bbC);
00462   BasicBlock* bbCp = 
00463     new BasicBlock("choice", &F, cast<BasicBlock>(Translate(src))->getNext() );
00464   ChoicePoints.insert(bbCp);
00465   
00466   //b:
00467   new BranchInst(cast<BasicBlock>(Translate(dst)), bbC);
00468   new BranchInst(dst, cast<BasicBlock>(Translate(dst)), 
00469      ConstantBool::get(true), bbCp);
00470   //c:
00471   {
00472     TerminatorInst* iB = src->getTerminator();
00473     for (unsigned x = 0; x < iB->getNumSuccessors(); ++x)
00474       if (iB->getSuccessor(x) == dst)
00475         iB->setSuccessor(x, bbC);
00476   }
00477   //d:
00478   {
00479     TerminatorInst* iBp = cast<TerminatorInst>(Translate(src->getTerminator()));
00480     for (unsigned x = 0; x < iBp->getNumSuccessors(); ++x)
00481       if (iBp->getSuccessor(x) == cast<BasicBlock>(Translate(dst)))
00482         iBp->setSuccessor(x, bbCp);
00483   }
00484   //e:
00485   ReplacePhiPred(dst, src, bbC);
00486   //src could be a switch, in which case we are replacing several edges with one
00487   //thus collapse those edges int the Phi
00488   CollapsePhi(dst, bbC);
00489   //f:
00490   ReplacePhiPred(cast<BasicBlock>(Translate(dst)),
00491      cast<BasicBlock>(Translate(src)),bbCp);
00492   CollapsePhi(cast<BasicBlock>(Translate(dst)), bbCp);
00493   //g:
00494   for(BasicBlock::iterator ib = dst->begin(), ie = dst->end(); ib != ie;
00495       ++ib)
00496     if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
00497       for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x)
00498         if(bbC == phi->getIncomingBlock(x)) {
00499           phi->addIncoming(Translate(phi->getIncomingValue(x)), bbCp);
00500           cast<PHINode>(Translate(phi))->addIncoming(phi->getIncomingValue(x), 
00501                  bbC);
00502         }
00503       phi->removeIncomingValue(bbC);
00504     }
00505 }
00506 
00507 bool ProfilerRS::runOnFunction(Function& F) {
00508   if (!F.isExternal()) {
00509     std::set<std::pair<BasicBlock*, BasicBlock*> > BackEdges;
00510     RSProfilers& LI = getAnalysis<RSProfilers>();
00511     
00512     getBackEdges(F, BackEdges);
00513     Duplicate(F, LI);
00514     //assume that stuff worked.  now connect the duplicated basic blocks 
00515     //with the originals in such a way as to preserve ssa.  yuk!
00516     for (std::set<std::pair<BasicBlock*, BasicBlock*> >::iterator 
00517      ib = BackEdges.begin(), ie = BackEdges.end(); ib != ie; ++ib)
00518       ProcessBackEdge(ib->first, ib->second, F);
00519     
00520     //oh, and add the edge from the reg2mem created entry node to the 
00521     //duplicated second node
00522     TerminatorInst* T = F.getEntryBlock().getTerminator();
00523     ReplaceInstWithInst(T, new BranchInst(T->getSuccessor(0),
00524              cast<BasicBlock>(Translate(T->getSuccessor(0))),
00525             ConstantBool::get(true)));
00526     
00527     //do whatever is needed now that the function is duplicated
00528     c->PrepFunction(&F);
00529     
00530     //add entry node to choice points
00531     ChoicePoints.insert(&F.getEntryBlock());
00532     
00533     for (std::set<BasicBlock*>::iterator 
00534      ii = ChoicePoints.begin(), ie = ChoicePoints.end(); ii != ie; ++ii)
00535       c->ProcessChoicePoint(*ii);
00536     
00537     ChoicePoints.clear();
00538     TransCache.clear();
00539     
00540     return true;
00541   }
00542   return false;
00543 }
00544 
00545 bool ProfilerRS::doInitialization(Module &M) {
00546   switch (RandomMethod) {
00547   case GBV:
00548     c = new GlobalRandomCounter(M, Type::UIntTy, (1 << 14) - 1);
00549     break;
00550   case GBVO:
00551     c = new GlobalRandomCounterOpt(M, Type::UIntTy, (1 << 14) - 1);
00552     break;
00553   case HOSTCC:
00554     c = new CycleCounter(M, (1 << 14) - 1);
00555     break;
00556   };
00557   return true;
00558 }
00559 
00560 void ProfilerRS::getAnalysisUsage(AnalysisUsage &AU) const {
00561   AU.addRequired<RSProfilers>();
00562   AU.addRequiredID(DemoteRegisterToMemoryID);
00563 }
00564 
00565 ///////////////////////////////////////
00566 // Utilities:
00567 ///////////////////////////////////////
00568 static void ReplacePhiPred(BasicBlock* btarget, 
00569                            BasicBlock* bold, BasicBlock* bnew) {
00570   for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
00571       ib != ie; ++ib)
00572     if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
00573       for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x)
00574         if(bold == phi->getIncomingBlock(x))
00575           phi->setIncomingBlock(x, bnew);
00576     }
00577 }
00578 
00579 static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc) {
00580   for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
00581       ib != ie; ++ib)
00582     if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
00583       unsigned total = phi->getNumIncomingValues();
00584       std::map<BasicBlock*, Value*> counter;
00585       for(unsigned i = 0; i < phi->getNumIncomingValues(); ) {
00586         if (counter[phi->getIncomingBlock(i)]) {
00587           assert(phi->getIncomingValue(i) == counter[phi->getIncomingBlock(i)]);
00588           phi->removeIncomingValue(i, false);
00589         } else {
00590           counter[phi->getIncomingBlock(i)] = phi->getIncomingValue(i);
00591           ++i;
00592         }
00593       }
00594     } 
00595 }
00596 
00597 template<class T>
00598 static void recBackEdge(BasicBlock* bb, T& BackEdges, 
00599                         std::map<BasicBlock*, int>& color,
00600                         std::map<BasicBlock*, int>& depth,
00601                         std::map<BasicBlock*, int>& finish,
00602                         int& time)
00603 {
00604   color[bb] = 1;
00605   ++time;
00606   depth[bb] = time;
00607   TerminatorInst* t= bb->getTerminator();
00608   for(unsigned i = 0; i < t->getNumSuccessors(); ++i) {
00609     BasicBlock* bbnew = t->getSuccessor(i);
00610     if (color[bbnew] == 0)
00611       recBackEdge(bbnew, BackEdges, color, depth, finish, time);
00612     else if (color[bbnew] == 1) {
00613       BackEdges.insert(std::make_pair(bb, bbnew));
00614       //NumBackEdges++;
00615     }
00616   }
00617   color[bb] = 2;
00618   ++time;
00619   finish[bb] = time;
00620 }
00621 
00622 
00623 
00624 //find the back edges and where they go to
00625 template<class T>
00626 static void getBackEdges(Function& F, T& BackEdges) {
00627   std::map<BasicBlock*, int> color;
00628   std::map<BasicBlock*, int> depth;
00629   std::map<BasicBlock*, int> finish;
00630   int time = 0;
00631   recBackEdge(&F.getEntryBlock(), BackEdges, color, depth, finish, time);
00632   DEBUG(std::cerr << F.getName() << " " << BackEdges.size() << "\n");
00633 }
00634 
00635 
00636 //Creation functions
00637 ModulePass* llvm::createNullProfilerRSPass() {
00638   return new NullProfilerRS();
00639 }
00640 
00641 FunctionPass* llvm::createRSProfilingPass() {
00642   return new ProfilerRS();
00643 }