blob: 0999a279ef0dd379002be0dc9d879d49122d2272 [file] [log] [blame]
Andrew Lenharth701f5ac2005-11-28 00:58:09 +00001//===- RSProfiling.cpp - Various profiling using random sampling ----------===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Andrew Lenharth701f5ac2005-11-28 00:58:09 +00007//
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
Andrew Lenharthbb227c12005-11-28 18:00:38 +000013// passes which insert profiling into the program, and remember what they
14// inserted.
15//
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000016// 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//
Gordon Henriksen55cbec32007-10-26 03:03:51 +000021// It is highly recommended that after this pass one runs mem2reg and adce
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000022// (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"
Owen Anderson50895512009-07-06 18:42:36 +000036#include "llvm/LLVMContext.h"
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000037#include "llvm/Module.h"
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000038#include "llvm/Instructions.h"
39#include "llvm/Constants.h"
40#include "llvm/DerivedTypes.h"
Duncan Sandse2c43042008-04-07 13:45:04 +000041#include "llvm/Intrinsics.h"
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000042#include "llvm/Transforms/Scalar.h"
43#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000044#include "llvm/Support/CommandLine.h"
Reid Spencer9133fe22007-02-05 23:32:05 +000045#include "llvm/Support/Compiler.h"
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000046#include "llvm/Support/Debug.h"
47#include "llvm/Transforms/Instrumentation.h"
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000048#include "RSProfiling.h"
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000049#include <set>
50#include <map>
51#include <queue>
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000052using namespace llvm;
53
54namespace {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000055 enum RandomMeth {
56 GBV, GBVO, HOSTCC
57 };
Dan Gohman844731a2008-05-13 00:00:25 +000058}
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000059
Dan Gohman844731a2008-05-13 00:00:25 +000060static cl::opt<RandomMeth> RandomMethod("profile-randomness",
61 cl::desc("How to randomly choose to profile:"),
62 cl::values(
63 clEnumValN(GBV, "global", "global counter"),
64 clEnumValN(GBVO, "ra_global",
65 "register allocated global counter"),
66 clEnumValN(HOSTCC, "rdcc", "cycle counter"),
67 clEnumValEnd));
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000068
Dan Gohman844731a2008-05-13 00:00:25 +000069namespace {
Andrew Lenharth8dc2d502005-11-28 18:10:59 +000070 /// NullProfilerRS - The basic profiler that does nothing. It is the default
71 /// profiler and thus terminates RSProfiler chains. It is useful for
72 /// measuring framework overhead
Reid Spencer9133fe22007-02-05 23:32:05 +000073 class VISIBILITY_HIDDEN NullProfilerRS : public RSProfilers {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000074 public:
Nick Lewyckyecd94c82007-05-06 13:37:16 +000075 static char ID; // Pass identification, replacement for typeid
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000076 bool isProfiling(Value* v) {
77 return false;
78 }
79 bool runOnModule(Module &M) {
80 return false;
81 }
82 void getAnalysisUsage(AnalysisUsage &AU) const {
83 AU.setPreservesAll();
84 }
85 };
Dan Gohman844731a2008-05-13 00:00:25 +000086}
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000087
Dan Gohman844731a2008-05-13 00:00:25 +000088static RegisterAnalysisGroup<RSProfilers> A("Profiling passes");
89static RegisterPass<NullProfilerRS> NP("insert-null-profiling-rs",
90 "Measure profiling framework overhead");
91static RegisterAnalysisGroup<RSProfilers, true> NPT(NP);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000092
Dan Gohman844731a2008-05-13 00:00:25 +000093namespace {
Andrew Lenharth8dc2d502005-11-28 18:10:59 +000094 /// Chooser - Something that chooses when to make a sample of the profiled code
Reid Spencer9133fe22007-02-05 23:32:05 +000095 class VISIBILITY_HIDDEN Chooser {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000096 public:
Andrew Lenharth8dc2d502005-11-28 18:10:59 +000097 /// ProcessChoicePoint - is called for each basic block inserted to choose
98 /// between normal and sample code
Andrew Lenharth701f5ac2005-11-28 00:58:09 +000099 virtual void ProcessChoicePoint(BasicBlock*) = 0;
Andrew Lenharth8dc2d502005-11-28 18:10:59 +0000100 /// PrepFunction - is called once per function before other work is done.
101 /// This gives the opertunity to insert new allocas and such.
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000102 virtual void PrepFunction(Function*) = 0;
103 virtual ~Chooser() {}
104 };
105
106 //Things that implement sampling policies
Andrew Lenharth8dc2d502005-11-28 18:10:59 +0000107 //A global value that is read-mod-stored to choose when to sample.
108 //A sample is taken when the global counter hits 0
Reid Spencer9133fe22007-02-05 23:32:05 +0000109 class VISIBILITY_HIDDEN GlobalRandomCounter : public Chooser {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000110 GlobalVariable* Counter;
111 Value* ResetValue;
Dan Gohman6de29f82009-06-15 22:12:54 +0000112 const IntegerType* T;
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000113 public:
Dan Gohman6de29f82009-06-15 22:12:54 +0000114 GlobalRandomCounter(Module& M, const IntegerType* t, uint64_t resetval);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000115 virtual ~GlobalRandomCounter();
116 virtual void PrepFunction(Function* F);
117 virtual void ProcessChoicePoint(BasicBlock* bb);
118 };
119
Andrew Lenharth8dc2d502005-11-28 18:10:59 +0000120 //Same is GRC, but allow register allocation of the global counter
Reid Spencer9133fe22007-02-05 23:32:05 +0000121 class VISIBILITY_HIDDEN GlobalRandomCounterOpt : public Chooser {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000122 GlobalVariable* Counter;
123 Value* ResetValue;
124 AllocaInst* AI;
Dan Gohman6de29f82009-06-15 22:12:54 +0000125 const IntegerType* T;
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000126 public:
Dan Gohman6de29f82009-06-15 22:12:54 +0000127 GlobalRandomCounterOpt(Module& M, const IntegerType* t, uint64_t resetval);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000128 virtual ~GlobalRandomCounterOpt();
129 virtual void PrepFunction(Function* F);
130 virtual void ProcessChoicePoint(BasicBlock* bb);
131 };
132
Andrew Lenharth8dc2d502005-11-28 18:10:59 +0000133 //Use the cycle counter intrinsic as a source of pseudo randomness when
134 //deciding when to sample.
Reid Spencer9133fe22007-02-05 23:32:05 +0000135 class VISIBILITY_HIDDEN CycleCounter : public Chooser {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000136 uint64_t rm;
Chris Lattnerfebe5f12007-01-07 07:22:20 +0000137 Constant *F;
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000138 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
Andrew Lenharth8dc2d502005-11-28 18:10:59 +0000145 /// ProfilerRS - Insert the random sampling framework
Reid Spencer9133fe22007-02-05 23:32:05 +0000146 struct VISIBILITY_HIDDEN ProfilerRS : public FunctionPass {
Nick Lewyckyecd94c82007-05-06 13:37:16 +0000147 static char ID; // Pass identification, replacement for typeid
Dan Gohmanae73dc12008-09-04 17:05:41 +0000148 ProfilerRS() : FunctionPass(&ID) {}
Devang Patel794fd752007-05-01 21:15:47 +0000149
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000150 std::map<Value*, Value*> TransCache;
151 std::set<BasicBlock*> ChoicePoints;
152 Chooser* c;
153
Andrew Lenharth8dc2d502005-11-28 18:10:59 +0000154 //Translate and duplicate values for the new profile free version of stuff
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000155 Value* Translate(Value* v);
Andrew Lenharth8dc2d502005-11-28 18:10:59 +0000156 //Duplicate an entire function (with out profiling)
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000157 void Duplicate(Function& F, RSProfilers& LI);
Andrew Lenharth8dc2d502005-11-28 18:10:59 +0000158 //Called once for each backedge, handle the insertion of choice points and
159 //the interconection of the two versions of the code
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000160 void ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F);
161 bool runOnFunction(Function& F);
162 bool doInitialization(Module &M);
163 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
164 };
Chris Lattnerd74ea2b2006-05-24 17:04:05 +0000165}
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000166
Dan Gohman844731a2008-05-13 00:00:25 +0000167static RegisterPass<ProfilerRS>
168X("insert-rs-profiling-framework",
169 "Insert random sampling instrumentation framework");
170
Devang Patel19974732007-05-03 01:11:54 +0000171char RSProfilers::ID = 0;
172char NullProfilerRS::ID = 0;
173char ProfilerRS::ID = 0;
Lauro Ramos Venancioc7182882007-05-02 20:37:47 +0000174
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000175//Local utilities
176static void ReplacePhiPred(BasicBlock* btarget,
177 BasicBlock* bold, BasicBlock* bnew);
178
179static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc);
180
181template<class T>
182static void recBackEdge(BasicBlock* bb, T& BackEdges,
183 std::map<BasicBlock*, int>& color,
184 std::map<BasicBlock*, int>& depth,
185 std::map<BasicBlock*, int>& finish,
186 int& time);
187
188//find the back edges and where they go to
189template<class T>
190static void getBackEdges(Function& F, T& BackEdges);
191
192
193///////////////////////////////////////
194// Methods of choosing when to profile
195///////////////////////////////////////
196
Dan Gohman6de29f82009-06-15 22:12:54 +0000197GlobalRandomCounter::GlobalRandomCounter(Module& M, const IntegerType* t,
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000198 uint64_t resetval) : T(t) {
Owen Anderson50895512009-07-06 18:42:36 +0000199 ConstantInt* Init = M.getContext().getConstantInt(T, resetval);
Reid Spencerb83eb642006-10-20 07:07:24 +0000200 ResetValue = Init;
Owen Anderson3d29df32009-07-08 01:26:06 +0000201 Counter = new GlobalVariable(M.getContext(), T, false,
202 GlobalValue::InternalLinkage,
Reid Spencerb83eb642006-10-20 07:07:24 +0000203 Init, "RandomSteeringCounter", &M);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000204}
205
206GlobalRandomCounter::~GlobalRandomCounter() {}
207
208void GlobalRandomCounter::PrepFunction(Function* F) {}
209
210void GlobalRandomCounter::ProcessChoicePoint(BasicBlock* bb) {
211 BranchInst* t = cast<BranchInst>(bb->getTerminator());
Owen Anderson07cf79e2009-07-06 23:00:19 +0000212 LLVMContext *Context = bb->getContext();
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000213
214 //decrement counter
215 LoadInst* l = new LoadInst(Counter, "counter", t);
216
Owen Anderson50895512009-07-06 18:42:36 +0000217 ICmpInst* s = new ICmpInst(ICmpInst::ICMP_EQ, l,
218 Context->getConstantInt(T, 0),
Reid Spencere4d87aa2006-12-23 06:05:41 +0000219 "countercc", t);
220
Owen Anderson50895512009-07-06 18:42:36 +0000221 Value* nv = BinaryOperator::CreateSub(l, Context->getConstantInt(T, 1),
Anton Korobeynikovbed29462007-04-16 18:10:23 +0000222 "counternew", t);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000223 new StoreInst(nv, Counter, t);
224 t->setCondition(s);
225
226 //reset counter
227 BasicBlock* oldnext = t->getSuccessor(0);
Gabor Greif051a9502008-04-06 20:25:17 +0000228 BasicBlock* resetblock = BasicBlock::Create("reset", oldnext->getParent(),
229 oldnext);
230 TerminatorInst* t2 = BranchInst::Create(oldnext, resetblock);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000231 t->setSuccessor(0, resetblock);
232 new StoreInst(ResetValue, Counter, t2);
233 ReplacePhiPred(oldnext, bb, resetblock);
234}
235
Dan Gohman6de29f82009-06-15 22:12:54 +0000236GlobalRandomCounterOpt::GlobalRandomCounterOpt(Module& M, const IntegerType* t,
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000237 uint64_t resetval)
238 : AI(0), T(t) {
Owen Anderson50895512009-07-06 18:42:36 +0000239 ConstantInt* Init = M.getContext().getConstantInt(T, resetval);
Reid Spencerb83eb642006-10-20 07:07:24 +0000240 ResetValue = Init;
Owen Anderson3d29df32009-07-08 01:26:06 +0000241 Counter = new GlobalVariable(M.getContext(), T, false,
242 GlobalValue::InternalLinkage,
Reid Spencerb83eb642006-10-20 07:07:24 +0000243 Init, "RandomSteeringCounter", &M);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000244}
245
246GlobalRandomCounterOpt::~GlobalRandomCounterOpt() {}
247
248void GlobalRandomCounterOpt::PrepFunction(Function* F) {
249 //make a local temporary to cache the global
250 BasicBlock& bb = F->getEntryBlock();
Chris Lattnera0e1b0e2007-04-17 17:51:03 +0000251 BasicBlock::iterator InsertPt = bb.begin();
252 AI = new AllocaInst(T, 0, "localcounter", InsertPt);
253 LoadInst* l = new LoadInst(Counter, "counterload", InsertPt);
254 new StoreInst(l, AI, InsertPt);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000255
Andrew Lenharth8dc2d502005-11-28 18:10:59 +0000256 //modify all functions and return values to restore the local variable to/from
257 //the global variable
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000258 for(Function::iterator fib = F->begin(), fie = F->end();
259 fib != fie; ++fib)
260 for(BasicBlock::iterator bib = fib->begin(), bie = fib->end();
261 bib != bie; ++bib)
Chris Lattnera0e1b0e2007-04-17 17:51:03 +0000262 if (isa<CallInst>(bib)) {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000263 LoadInst* l = new LoadInst(AI, "counter", bib);
264 new StoreInst(l, Counter, bib);
Chris Lattnera0e1b0e2007-04-17 17:51:03 +0000265 l = new LoadInst(Counter, "counter", ++bib);
266 new StoreInst(l, AI, bib--);
267 } else if (isa<InvokeInst>(bib)) {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000268 LoadInst* l = new LoadInst(AI, "counter", bib);
269 new StoreInst(l, Counter, bib);
270
Chris Lattnera0e1b0e2007-04-17 17:51:03 +0000271 BasicBlock* bb = cast<InvokeInst>(bib)->getNormalDest();
Dan Gohman02dea8b2008-05-23 21:05:58 +0000272 BasicBlock::iterator i = bb->getFirstNonPHI();
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000273 l = new LoadInst(Counter, "counter", i);
274
Chris Lattnera0e1b0e2007-04-17 17:51:03 +0000275 bb = cast<InvokeInst>(bib)->getUnwindDest();
Dan Gohman02dea8b2008-05-23 21:05:58 +0000276 i = bb->getFirstNonPHI();
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000277 l = new LoadInst(Counter, "counter", i);
Chris Lattnera0e1b0e2007-04-17 17:51:03 +0000278 new StoreInst(l, AI, i);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000279 } else if (isa<UnwindInst>(&*bib) || isa<ReturnInst>(&*bib)) {
280 LoadInst* l = new LoadInst(AI, "counter", bib);
281 new StoreInst(l, Counter, bib);
282 }
283}
284
285void GlobalRandomCounterOpt::ProcessChoicePoint(BasicBlock* bb) {
286 BranchInst* t = cast<BranchInst>(bb->getTerminator());
Owen Anderson07cf79e2009-07-06 23:00:19 +0000287 LLVMContext *Context = bb->getContext();
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000288
289 //decrement counter
290 LoadInst* l = new LoadInst(AI, "counter", t);
291
Owen Anderson50895512009-07-06 18:42:36 +0000292 ICmpInst* s = new ICmpInst(ICmpInst::ICMP_EQ, l,
293 Context->getConstantInt(T, 0),
Reid Spencere4d87aa2006-12-23 06:05:41 +0000294 "countercc", t);
295
Owen Anderson50895512009-07-06 18:42:36 +0000296 Value* nv = BinaryOperator::CreateSub(l, Context->getConstantInt(T, 1),
Anton Korobeynikovbed29462007-04-16 18:10:23 +0000297 "counternew", t);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000298 new StoreInst(nv, AI, t);
299 t->setCondition(s);
300
301 //reset counter
302 BasicBlock* oldnext = t->getSuccessor(0);
Gabor Greif051a9502008-04-06 20:25:17 +0000303 BasicBlock* resetblock = BasicBlock::Create("reset", oldnext->getParent(),
304 oldnext);
305 TerminatorInst* t2 = BranchInst::Create(oldnext, resetblock);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000306 t->setSuccessor(0, resetblock);
307 new StoreInst(ResetValue, AI, t2);
308 ReplacePhiPred(oldnext, bb, resetblock);
309}
310
311
312CycleCounter::CycleCounter(Module& m, uint64_t resetmask) : rm(resetmask) {
Duncan Sandse2c43042008-04-07 13:45:04 +0000313 F = Intrinsic::getDeclaration(&m, Intrinsic::readcyclecounter);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000314}
315
316CycleCounter::~CycleCounter() {}
317
318void CycleCounter::PrepFunction(Function* F) {}
319
320void CycleCounter::ProcessChoicePoint(BasicBlock* bb) {
321 BranchInst* t = cast<BranchInst>(bb->getTerminator());
Owen Anderson07cf79e2009-07-06 23:00:19 +0000322 LLVMContext *Context = bb->getContext();
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000323
Gabor Greif051a9502008-04-06 20:25:17 +0000324 CallInst* c = CallInst::Create(F, "rdcc", t);
Andrew Lenharthbb227c12005-11-28 18:00:38 +0000325 BinaryOperator* b =
Owen Anderson50895512009-07-06 18:42:36 +0000326 BinaryOperator::CreateAnd(c, Context->getConstantInt(Type::Int64Ty, rm),
Anton Korobeynikovbed29462007-04-16 18:10:23 +0000327 "mrdcc", t);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000328
Reid Spencere4d87aa2006-12-23 06:05:41 +0000329 ICmpInst *s = new ICmpInst(ICmpInst::ICMP_EQ, b,
Owen Anderson50895512009-07-06 18:42:36 +0000330 Context->getConstantInt(Type::Int64Ty, 0),
Reid Spencere4d87aa2006-12-23 06:05:41 +0000331 "mrdccc", t);
332
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000333 t->setCondition(s);
334}
335
336///////////////////////////////////////
337// Profiling:
338///////////////////////////////////////
Andrew Lenharthbb227c12005-11-28 18:00:38 +0000339bool RSProfilers_std::isProfiling(Value* v) {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000340 if (profcode.find(v) != profcode.end())
341 return true;
342 //else
343 RSProfilers& LI = getAnalysis<RSProfilers>();
344 return LI.isProfiling(v);
345}
346
Andrew Lenharthbb227c12005-11-28 18:00:38 +0000347void RSProfilers_std::IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum,
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000348 GlobalValue *CounterArray) {
349 // Insert the increment after any alloca or PHI instructions...
Dan Gohman02dea8b2008-05-23 21:05:58 +0000350 BasicBlock::iterator InsertPos = BB->getFirstNonPHI();
351 while (isa<AllocaInst>(InsertPos))
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000352 ++InsertPos;
353
354 // Create the getelementptr constant expression
355 std::vector<Constant*> Indices(2);
Owen Anderson50895512009-07-06 18:42:36 +0000356 Indices[0] = Context->getNullValue(Type::Int32Ty);
357 Indices[1] = Context->getConstantInt(Type::Int32Ty, CounterNum);
358 Constant *ElementPtr = Context->getConstantExprGetElementPtr(CounterArray,
Chris Lattnerec1f7522007-02-19 07:34:47 +0000359 &Indices[0], 2);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000360
361 // Load, increment and store the value back.
362 Value *OldVal = new LoadInst(ElementPtr, "OldCounter", InsertPos);
363 profcode.insert(OldVal);
Gabor Greif7cbd8a32008-05-16 19:29:10 +0000364 Value *NewVal = BinaryOperator::CreateAdd(OldVal,
Owen Anderson50895512009-07-06 18:42:36 +0000365 Context->getConstantInt(Type::Int32Ty, 1),
Anton Korobeynikovbed29462007-04-16 18:10:23 +0000366 "NewCounter", InsertPos);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000367 profcode.insert(NewVal);
368 profcode.insert(new StoreInst(NewVal, ElementPtr, InsertPos));
369}
370
Andrew Lenharthbb227c12005-11-28 18:00:38 +0000371void RSProfilers_std::getAnalysisUsage(AnalysisUsage &AU) const {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000372 //grab any outstanding profiler, or get the null one
373 AU.addRequired<RSProfilers>();
374}
375
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000376///////////////////////////////////////
377// RS Framework
378///////////////////////////////////////
379
380Value* ProfilerRS::Translate(Value* v) {
381 if(TransCache[v])
382 return TransCache[v];
383
384 if (BasicBlock* bb = dyn_cast<BasicBlock>(v)) {
385 if (bb == &bb->getParent()->getEntryBlock())
386 TransCache[bb] = bb; //don't translate entry block
387 else
Gabor Greifb1dbcd82008-05-15 10:04:30 +0000388 TransCache[bb] = BasicBlock::Create("dup_" + bb->getName(),
389 bb->getParent(), NULL);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000390 return TransCache[bb];
391 } else if (Instruction* i = dyn_cast<Instruction>(v)) {
392 //we have already translated this
393 //do not translate entry block allocas
394 if(&i->getParent()->getParent()->getEntryBlock() == i->getParent()) {
395 TransCache[i] = i;
396 return i;
397 } else {
398 //translate this
399 Instruction* i2 = i->clone();
400 if (i->hasName())
401 i2->setName("dup_" + i->getName());
402 TransCache[i] = i2;
403 //NumNewInst++;
404 for (unsigned x = 0; x < i2->getNumOperands(); ++x)
405 i2->setOperand(x, Translate(i2->getOperand(x)));
406 return i2;
407 }
408 } else if (isa<Function>(v) || isa<Constant>(v) || isa<Argument>(v)) {
409 TransCache[v] = v;
410 return v;
411 }
412 assert(0 && "Value not handled");
Jeff Cohen3523f6e2005-11-28 06:45:57 +0000413 return 0;
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000414}
415
416void ProfilerRS::Duplicate(Function& F, RSProfilers& LI)
417{
418 //perform a breadth first search, building up a duplicate of the code
419 std::queue<BasicBlock*> worklist;
420 std::set<BasicBlock*> seen;
421
422 //This loop ensures proper BB order, to help performance
423 for (Function::iterator fib = F.begin(), fie = F.end(); fib != fie; ++fib)
424 worklist.push(fib);
425 while (!worklist.empty()) {
426 Translate(worklist.front());
427 worklist.pop();
428 }
429
430 //remember than reg2mem created a new entry block we don't want to duplicate
431 worklist.push(F.getEntryBlock().getTerminator()->getSuccessor(0));
432 seen.insert(&F.getEntryBlock());
433
434 while (!worklist.empty()) {
435 BasicBlock* bb = worklist.front();
436 worklist.pop();
437 if(seen.find(bb) == seen.end()) {
438 BasicBlock* bbtarget = cast<BasicBlock>(Translate(bb));
439 BasicBlock::InstListType& instlist = bbtarget->getInstList();
440 for (BasicBlock::iterator iib = bb->begin(), iie = bb->end();
441 iib != iie; ++iib) {
442 //NumOldInst++;
443 if (!LI.isProfiling(&*iib)) {
444 Instruction* i = cast<Instruction>(Translate(iib));
445 instlist.insert(bbtarget->end(), i);
446 }
447 }
448 //updated search state;
449 seen.insert(bb);
450 TerminatorInst* ti = bb->getTerminator();
451 for (unsigned x = 0; x < ti->getNumSuccessors(); ++x) {
452 BasicBlock* bbs = ti->getSuccessor(x);
453 if (seen.find(bbs) == seen.end()) {
454 worklist.push(bbs);
455 }
456 }
457 }
458 }
459}
460
461void ProfilerRS::ProcessBackEdge(BasicBlock* src, BasicBlock* dst, Function& F) {
462 //given a backedge from B -> A, and translations A' and B',
463 //a: insert C and C'
464 //b: add branches in C to A and A' and in C' to A and A'
465 //c: mod terminators@B, replace A with C
466 //d: mod terminators@B', replace A' with C'
467 //e: mod phis@A for pred B to be pred C
468 // if multiple entries, simplify to one
469 //f: mod phis@A' for pred B' to be pred C'
470 // if multiple entries, simplify to one
471 //g: for all phis@A with pred C using x
472 // add in edge from C' using x'
473 // add in edge from C using x in A'
474
475 //a:
Chris Lattnere24c92a2007-04-17 17:54:12 +0000476 Function::iterator BBN = src; ++BBN;
Gabor Greif051a9502008-04-06 20:25:17 +0000477 BasicBlock* bbC = BasicBlock::Create("choice", &F, BBN);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000478 //ChoicePoints.insert(bbC);
Chris Lattnere24c92a2007-04-17 17:54:12 +0000479 BBN = cast<BasicBlock>(Translate(src));
Gabor Greif051a9502008-04-06 20:25:17 +0000480 BasicBlock* bbCp = BasicBlock::Create("choice", &F, ++BBN);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000481 ChoicePoints.insert(bbCp);
482
483 //b:
Gabor Greif051a9502008-04-06 20:25:17 +0000484 BranchInst::Create(cast<BasicBlock>(Translate(dst)), bbC);
485 BranchInst::Create(dst, cast<BasicBlock>(Translate(dst)),
Owen Anderson50895512009-07-06 18:42:36 +0000486 Context->getConstantInt(Type::Int1Ty, true), bbCp);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000487 //c:
488 {
489 TerminatorInst* iB = src->getTerminator();
490 for (unsigned x = 0; x < iB->getNumSuccessors(); ++x)
491 if (iB->getSuccessor(x) == dst)
492 iB->setSuccessor(x, bbC);
493 }
494 //d:
495 {
496 TerminatorInst* iBp = cast<TerminatorInst>(Translate(src->getTerminator()));
497 for (unsigned x = 0; x < iBp->getNumSuccessors(); ++x)
498 if (iBp->getSuccessor(x) == cast<BasicBlock>(Translate(dst)))
499 iBp->setSuccessor(x, bbCp);
500 }
501 //e:
502 ReplacePhiPred(dst, src, bbC);
503 //src could be a switch, in which case we are replacing several edges with one
504 //thus collapse those edges int the Phi
505 CollapsePhi(dst, bbC);
506 //f:
Andrew Lenharthbb227c12005-11-28 18:00:38 +0000507 ReplacePhiPred(cast<BasicBlock>(Translate(dst)),
Anton Korobeynikovbed29462007-04-16 18:10:23 +0000508 cast<BasicBlock>(Translate(src)),bbCp);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000509 CollapsePhi(cast<BasicBlock>(Translate(dst)), bbCp);
510 //g:
511 for(BasicBlock::iterator ib = dst->begin(), ie = dst->end(); ib != ie;
512 ++ib)
513 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
514 for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x)
515 if(bbC == phi->getIncomingBlock(x)) {
516 phi->addIncoming(Translate(phi->getIncomingValue(x)), bbCp);
Andrew Lenharthbb227c12005-11-28 18:00:38 +0000517 cast<PHINode>(Translate(phi))->addIncoming(phi->getIncomingValue(x),
Anton Korobeynikovbed29462007-04-16 18:10:23 +0000518 bbC);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000519 }
520 phi->removeIncomingValue(bbC);
521 }
522}
523
524bool ProfilerRS::runOnFunction(Function& F) {
Reid Spencer5cbf9852007-01-30 20:08:39 +0000525 if (!F.isDeclaration()) {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000526 std::set<std::pair<BasicBlock*, BasicBlock*> > BackEdges;
527 RSProfilers& LI = getAnalysis<RSProfilers>();
528
529 getBackEdges(F, BackEdges);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000530 Duplicate(F, LI);
531 //assume that stuff worked. now connect the duplicated basic blocks
532 //with the originals in such a way as to preserve ssa. yuk!
Andrew Lenharthbb227c12005-11-28 18:00:38 +0000533 for (std::set<std::pair<BasicBlock*, BasicBlock*> >::iterator
Anton Korobeynikovbed29462007-04-16 18:10:23 +0000534 ib = BackEdges.begin(), ie = BackEdges.end(); ib != ie; ++ib)
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000535 ProcessBackEdge(ib->first, ib->second, F);
536
Andrew Lenharthbb227c12005-11-28 18:00:38 +0000537 //oh, and add the edge from the reg2mem created entry node to the
538 //duplicated second node
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000539 TerminatorInst* T = F.getEntryBlock().getTerminator();
Gabor Greif051a9502008-04-06 20:25:17 +0000540 ReplaceInstWithInst(T, BranchInst::Create(T->getSuccessor(0),
541 cast<BasicBlock>(
542 Translate(T->getSuccessor(0))),
Owen Anderson50895512009-07-06 18:42:36 +0000543 Context->getConstantInt(Type::Int1Ty,
Gabor Greif051a9502008-04-06 20:25:17 +0000544 true)));
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000545
546 //do whatever is needed now that the function is duplicated
547 c->PrepFunction(&F);
548
549 //add entry node to choice points
550 ChoicePoints.insert(&F.getEntryBlock());
551
Andrew Lenharthbb227c12005-11-28 18:00:38 +0000552 for (std::set<BasicBlock*>::iterator
Anton Korobeynikovbed29462007-04-16 18:10:23 +0000553 ii = ChoicePoints.begin(), ie = ChoicePoints.end(); ii != ie; ++ii)
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000554 c->ProcessChoicePoint(*ii);
555
556 ChoicePoints.clear();
557 TransCache.clear();
558
559 return true;
560 }
561 return false;
562}
563
564bool ProfilerRS::doInitialization(Module &M) {
565 switch (RandomMethod) {
566 case GBV:
Reid Spencerc5b206b2006-12-31 05:48:39 +0000567 c = new GlobalRandomCounter(M, Type::Int32Ty, (1 << 14) - 1);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000568 break;
569 case GBVO:
Reid Spencerc5b206b2006-12-31 05:48:39 +0000570 c = new GlobalRandomCounterOpt(M, Type::Int32Ty, (1 << 14) - 1);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000571 break;
572 case HOSTCC:
573 c = new CycleCounter(M, (1 << 14) - 1);
574 break;
575 };
576 return true;
577}
578
579void ProfilerRS::getAnalysisUsage(AnalysisUsage &AU) const {
580 AU.addRequired<RSProfilers>();
581 AU.addRequiredID(DemoteRegisterToMemoryID);
582}
583
584///////////////////////////////////////
585// Utilities:
586///////////////////////////////////////
587static void ReplacePhiPred(BasicBlock* btarget,
588 BasicBlock* bold, BasicBlock* bnew) {
589 for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
590 ib != ie; ++ib)
591 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
592 for(unsigned x = 0; x < phi->getNumIncomingValues(); ++x)
593 if(bold == phi->getIncomingBlock(x))
594 phi->setIncomingBlock(x, bnew);
595 }
596}
597
598static void CollapsePhi(BasicBlock* btarget, BasicBlock* bsrc) {
599 for(BasicBlock::iterator ib = btarget->begin(), ie = btarget->end();
600 ib != ie; ++ib)
601 if (PHINode* phi = dyn_cast<PHINode>(&*ib)) {
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000602 std::map<BasicBlock*, Value*> counter;
603 for(unsigned i = 0; i < phi->getNumIncomingValues(); ) {
604 if (counter[phi->getIncomingBlock(i)]) {
Andrew Lenharthbb227c12005-11-28 18:00:38 +0000605 assert(phi->getIncomingValue(i) == counter[phi->getIncomingBlock(i)]);
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000606 phi->removeIncomingValue(i, false);
607 } else {
608 counter[phi->getIncomingBlock(i)] = phi->getIncomingValue(i);
609 ++i;
610 }
611 }
612 }
613}
614
615template<class T>
616static void recBackEdge(BasicBlock* bb, T& BackEdges,
617 std::map<BasicBlock*, int>& color,
618 std::map<BasicBlock*, int>& depth,
619 std::map<BasicBlock*, int>& finish,
620 int& time)
621{
622 color[bb] = 1;
623 ++time;
624 depth[bb] = time;
625 TerminatorInst* t= bb->getTerminator();
626 for(unsigned i = 0; i < t->getNumSuccessors(); ++i) {
627 BasicBlock* bbnew = t->getSuccessor(i);
628 if (color[bbnew] == 0)
629 recBackEdge(bbnew, BackEdges, color, depth, finish, time);
630 else if (color[bbnew] == 1) {
631 BackEdges.insert(std::make_pair(bb, bbnew));
632 //NumBackEdges++;
633 }
634 }
635 color[bb] = 2;
636 ++time;
637 finish[bb] = time;
638}
639
640
641
642//find the back edges and where they go to
643template<class T>
644static void getBackEdges(Function& F, T& BackEdges) {
645 std::map<BasicBlock*, int> color;
646 std::map<BasicBlock*, int> depth;
647 std::map<BasicBlock*, int> finish;
648 int time = 0;
649 recBackEdge(&F.getEntryBlock(), BackEdges, color, depth, finish, time);
Bill Wendling62c804a2006-11-26 09:17:06 +0000650 DOUT << F.getName() << " " << BackEdges.size() << "\n";
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000651}
652
653
654//Creation functions
Andrew Lenharth701f5ac2005-11-28 00:58:09 +0000655ModulePass* llvm::createNullProfilerRSPass() {
656 return new NullProfilerRS();
657}
658
659FunctionPass* llvm::createRSProfilingPass() {
660 return new ProfilerRS();
661}