Profiling in LLVM Patch

Hi all,

as proposed in
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-February/020396.html
I implemented the algorithm presented in [Ball94]. It only instruments
the minimal number of edges necessary for edge profiling.

The main changes introduced by this patch are:
*) a interface compatible rewrite of ProfileInfo
*) a cleanup of ProfileInfoLoader
    (some functionality in ProfileInfoLoader was duplicated in ProfileInfo or
    ProfileInfoLoaderPass; ProfileInfoLoader now really only performs the
    loading but not the post-processing)
*) a new instrumentation pass that performs the optimal edge profiling
    instrumentation
*) a helper module MaximumSpanningTree that selects the edges with have to
    be instrumented for optimal edge profiling
*) a ProfileEstimatorPass that does an offline estimation of a profile based
    on branching and loop depth (also proposed in [Ball94])
    (it is possible to use this ProfileEstimator stand-alone to have at least
    some profile estimation available in the frontend without doing profiling
    runs)
*) a ProfileVerifierPass that checks the current profiling information
    against the flow preservation rules

I did performance measurements on the C and C++ portions of the SPEC CPU2000
benchmark, the results are:
*) on average 46% of the edges are instrumented with a counter (in
    comparison to 100% with the current edge profiling)
*) the performance overhead (on linux-x68_64, other platforms to follow) was
    14.76% with the current profiling and 8.20% with the optimal profiling
    (there are strange effects with the mcf and equake benchmarks where the
    current edge profiling is as fast as the un-instrumented code whereas the
    optimally instrumented code has a small (~5%) performance overhead)
*) when mcf and equake are excluded the average performance overhead is
    51.31% with optimal profiling (in comparison to 100% with the current
    edge profiling)

Please tell me what you do not like and if this is interesting enough to be
added to the trunk, if so, I will also devise test cases for "make check".

If you do not like the size of this patch it is possible to break it up a
little. I did not use the mkpatch utility since it does not include added
files, I hope the format is readable enough (it should be...)

I ran "make check" and there are not additional errors introduced
by the patch.

Grettings,

Andreas Neustifter

[Ball94] Thomas Ball, James R. Larus:
"Optimally profiling and tracing programs"
ACM TOPLAS, Volume 16, Issue 4, 1994

llvm-r74306.optimal_profiling.patch (83.5 KB)

Hi Andreas,

Thanks for submitting this back, I intend to review this today. Since
its a big patch, I wanted to point this out on the list in case anyone
else started tackling it.

- Daniel

Hi Andreas,

First, thanks again for undertaking this work and submitting it back. There is a
lot of good stuff here and it would be great to see it get back into the tree.

I have a few major high-level comments on the patch. First off, the patch is
quite large and should be broken down into separate incremental changes which
are easier to review and apply. I think the patches should more or less
correspond to the these high-level issues:

1. The intent of ProfileInfo is that it is the public interface used by the rest
of LLVM for all "profiling" related analyses. As such, we want it to have a
thin, well-defined interface which can be implemented by multiple analysis
providers, just like we have with the current alias analysis interface. Your
current patch has a large number of changes to ProfileInfo which should instead
be inside a subclass of ProfileInfo, where most of the implementation details
are private.

I think the first task should be to separate out the changes which are
appropriate for the ProfileInfo class itself and apply those to the tree. I
believe that the important changes which are worth reflecting in the API are
changed the weights to return a double instead of an int, and defining -1 as a
sentinel, "don't know", value.

This is the most important thing to separate out, and to do early, because it is
the main interface that is shared with LLVM. It is also important for my GSoC
student, who was going to work on static profiling for LLVM and will depend on
any changes to this interface.

The current ProfileInfo functions should also become virtual, and all other
implementation details should be left to the subclass.

Finally, I don't think the ignoreMissing parameter to getExecutionCount makes
sense, instead the provider should always return -1 if it doesn't have the
value, and clients should "do the right thing.

2. We shouldn't worry too much about preserving the functionality of the current
llvm-prof tool, which uses the ProfileInfoLoader directly. llvm-prof should be
rewritten to just use the public API provided by ProfileInfo. This should be
done early so there are less dependencies on the ProfileInfoLoader interface.

In fact, it might even make sense to just get rid of llvm-prof and instead
implement a module level pass which consumes profiling information and prints it
out as part of the pass. This would allow us to debug the preservation of
profiling information once we start modifying optimization passes to update it.

3. The static profiling estimator should be implemented as just another
ProfileInfo implementation. I believe this can be a separate patch. Similarly
the profile verifier is just another consumer of ProfileInfo and can be a
separate patch.

4. Finally, the new optimal edge instrumentation & ProfileInfo implementation
can be brought in.

Does this sound like a reasonable plan? Although it is a bit of work, I don't
think it will be that difficult and I am happy to help out with splitting up the
patch / refactoring the existing code.

In addition, I have a number of "nitpicks" mostly related to LLVM style:
- Please make comments complete sentences, including capitalizing the first
  word and trailing punctuation.

- Please format function prototypes to have the arguments following the '(',
  and wrapped onto new lines as appropriate to fit in 80 columns. That is,

Hi Daniel,

Daniel Dunbar wrote:

Hi Andreas,

First, thanks again for undertaking this work and submitting it back. There is a
lot of good stuff here and it would be great to see it get back into the tree.

Thanks for taking the time to review this, I know its a huge patch. I still have a few questions on how you would like this patch to be re-factored and split up.

[...]

1. The intent of ProfileInfo is that it is the public interface used by the rest
of LLVM for all "profiling" related analyses. As such, we want it to have a
thin, well-defined interface which can be implemented by multiple analysis
providers, just like we have with the current alias analysis interface. Your
current patch has a large number of changes to ProfileInfo which should instead
be inside a subclass of ProfileInfo, where most of the implementation details
are private.

I think the first task should be to separate out the changes which are
appropriate for the ProfileInfo class itself and apply those to the tree. I
believe that the important changes which are worth reflecting in the API are
changed the weights to return a double instead of an int, and defining -1 as a
sentinel, "don't know", value.

So you want the ProfileInfo to be untouched except for the double weights and the MissingValue? Then mark all methods virtual and do a subclass that has this sort of heavy implementation that I am using? Do you have any name suggestions for this subclass?
One thing I would like to patch in the current ProfileInfo implementation is the consistent use of the (0,entry) edge which is necessary to profile functions with only one block (namely the entry block).

This is the most important thing to separate out, and to do early, because it is
the main interface that is shared with LLVM. It is also important for my GSoC
student, who was going to work on static profiling for LLVM and will depend on
any changes to this interface.

Yes, I thought so, I will try to do this quick.

The current ProfileInfo functions should also become virtual, and all other
implementation details should be left to the subclass.

Finally, I don't think the ignoreMissing parameter to getExecutionCount makes
sense, instead the provider should always return -1 if it doesn't have the
value, and clients should "do the right thing.

Maybe, its of course always possibile to have custom wrappers that perform this sort of task if necessary...

2. We shouldn't worry too much about preserving the functionality of the current
llvm-prof tool, which uses the ProfileInfoLoader directly. llvm-prof should be
rewritten to just use the public API provided by ProfileInfo. This should be
done early so there are less dependencies on the ProfileInfoLoader interface.

Okay, thats no problem. I guess it makes sense to rewrite llvm-prof but I was not sure if this sort of changes would be appreciated.

In fact, it might even make sense to just get rid of llvm-prof and instead
implement a module level pass which consumes profiling information and prints it
out as part of the pass. This would allow us to debug the preservation of
profiling information once we start modifying optimization passes to update it.

Good point.

3. The static profiling estimator should be implemented as just another
ProfileInfo implementation. I believe this can be a separate patch. Similarly
the profile verifier is just another consumer of ProfileInfo and can be a
separate patch.

The ProfileEstimator is already a subclass of ProfileInfo and implements that interface. Yes, these two are easily split into separate patches.

4. Finally, the new optimal edge instrumentation & ProfileInfo implementation
can be brought in.

Does this sound like a reasonable plan? Although it is a bit of work, I don't
think it will be that difficult and I am happy to help out with splitting up the
patch / refactoring the existing code.

Yes, sounds good. I will try to split it up myself first and ask when there are decisions to be made I'm not sure about.

In addition, I have a number of "nitpicks" mostly related to LLVM style:

Well, they were to be expected :slight_smile: One never gets those right the first time contributing to a new project...

[...]

+ /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
+ /// (Modelled after getExitingBlocks().)
+ typedef std::pair<BlockT*,BlockT*> Edge;
+ void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());

Would it be better to use a DenseSet for this lookup?

Well, its the same that is used in getExitBlocks() where I got the implementation from. I really don't know but I think the current implementation is okay from what I gather form the LLVM Programmer's Manual.

--- llvm-van/include/llvm/Analysis/MaximumSpanningTree.h 1970-01-01 01:00:00.000000000 +0100
+++ llvm-c7/include/llvm/Analysis/MaximumSpanningTree.h 2009-06-26 16:47:01.000000000 +0200

...

+#include "llvm/Support/Streams.h"

Please don't use Support/Streams.h in a header, it pollutes any translation unit
which imports this header.

Okay.

+ static void print(MaxSpanTree MST) {
+ cerr<<"{";
+ for ( MaxSpanTree::iterator ei = MST.begin(), ee = MST.end();
+ ei!=ee; ++ei ) {
+ cerr<<"("<<((*ei).first?(*ei).first->getName():"0")<<",";
+ cerr<<(*ei).second->getName()<<")";
+ }
+ cerr<<"}\n";
+ }
+ };

To be more in line with LLVM I would recommend making this a nullary const
method on the MST, and rename it to dump. Also, please use Support/raw_ostream.h
for output instead of C++ iostreams.

Okay.

--- llvm-van/include/llvm/Analysis/Passes.h 2009-06-29 13:49:13.000000000 +0200
+++ llvm-c7/include/llvm/Analysis/Passes.h 2009-06-26 16:48:02.000000000 +0200
   // createProfileLoaderPass - This pass loads information from a profile dump
- // file.
+ // file. Since its possible to use the ProfileInfoLoaderPass not only from
+ // opt but also e.g. from llvm-prof and with different profile info filenames
+ // a creator is provided where the toolname and profile info filename can be
+ // provided. (The toolname is used to create proper error messages.)
   //
   ModulePass *createProfileLoaderPass();
+ ModulePass *createProfileLoaderPass(const std::string &, const std::string &);

Please name the arguments so it is clear which is the toolname and which is the
profile info name (bonus points for switching to doxygen comments which
reference the parameters).

I guess I will go for the bonus points then.

--- llvm-van/include/llvm/Analysis/ProfileInfo.h 2009-05-12 10:37:52.000000000 +0200
+++ llvm-c7/include/llvm/Analysis/ProfileInfo.h 2009-06-26 16:47:01.000000000 +0200

Keep in mind that most comments here are assuming this functionality is moved to
a subclass specific to optimal edge profiling.

   protected:
- // EdgeCounts - Count the number of times a transition between two blocks is
- // executed. As a special case, we also hold an edge from the null
- // BasicBlock to the entry block to indicate how many times the function was
- // entered.
- std::map<std::pair<BasicBlock*, BasicBlock*>, unsigned> EdgeCounts;
+ // EdgeInformation - Count the number of times a transition between two
+ // blocks is executed. As a special case, we also hold an edge from the
+ // null BasicBlock to the entry block (henceforth (0,entry) to indicate
+ // how many times the function was entered. (This is especially necessary
+ // if there is only the entry block.)
+ std::map<Function*, EdgeCounts> EdgeInformation;
+
+ // BlockInformation - Count the number of times a block is executed
+ std::map<Function*, BlockCounts> BlockInformation;
+
+ // FunctionInformation - Count the number of times a function is executed
+ std::map<Function*, double> FunctionInformation;

Instead of multiple maps from Function* ->, would it make sense to collect these
three (or four) maps inside a per-function structure?

Yes, makes sense, its then easier to factor out the retrieval and handling of this structure.

+ // getFunctionForEdge() - This returns the Function for a given Edge. This
+ // requires special handling for (0,entry) so its centralised here.
+ static inline Function* getFunctionForEdge(Edge E) {
+ BasicBlock *BB = E.first;
+ if ( BB == 0 ) { BB = E.second; };
+ assert ( BB != 0 && "both BasicBlocks of Edge are NULL, can not "
+ "determine function");
+ return BB->getParent();
+ }

The edge destination should always be non-null, correct? Why not just
--
   static inline Function* getFunctionForEdge(Edge E) {
     assert(E.second && "Invalid profile edge!");
     return E.second->getParent();
   }
--

Nice one. Thanks!

+ // getFunctionForBlock() - Same as for Edges without special handling, for
+ // the sake of cleaner code.
+ static inline Function* getFunctionForBlock(BasicBlock* BB) {
+ return BB->getParent();
+ }

I would prefer this wasn't used, its "common knowledge" in the LLVM code that a
basic blocks parent is its Function.

I was not sure about this one anyways, so yes, it will go.

+ EdgeCounts getEdgeCounts(Function *F) {
+ std::map<Function*, EdgeCounts>::const_iterator J =
+ EdgeInformation.find(F);
+ if ( J != EdgeInformation.end() ) {
+ return J->second;
+ }
+ return EdgeCounts(); // Return empty EdgeCounts in case none found.
+ }

This is way too expensive, returning a deep copy of the edge counts map isn't
necessary. The simplest alternative is to return a const reference and insert
into the map for missing functions. Something like:
--

+ const EdgeCounts& getEdgeCounts(Function *F) {
+ return EdgeInformation[F];
+ }

--
Unless we really care about not inserting empty entries this seems reasonable to
me.

Here my somewhat laking C++ skills failed me. I didn't see that this is essentially doing a copy, of course this is not necessary!

+ void forceSynthesis(void) {
+ for (std::map<Function*, EdgeCounts>::iterator
+ FI = EdgeInformation.begin(), FIE = EdgeInformation.end();
+ FI != FIE; ++FI) {
+ Function *F = FI->first;
+ for (Function::iterator BB = F->begin(), BBE = F->end();
+ BB != BBE; ++BB) {
+ getExecutionCount(BB,false);
+ }
+ getExecutionCount(F,false);
+ }
+ }

It doesn't make sense to have this function here, clients should just do the
right thing if the count isn't present. It may be worth providing a ProfileInfo
level API to query whether any information is present for a particular function
so that clients don't perform needless queries.

I have to look into this one, I guess its possible to do this kind of check on demand and calculate BlockCounts from EdgeCounts and FunctionCounts form BlockCounts when necessary.

--- llvm-van/lib/Analysis/MaximumSpanningTree.cpp 1970-01-01 01:00:00.000000000 +0100
+++ llvm-c7/lib/Analysis/MaximumSpanningTree.cpp 2009-06-26 16:47:01.000000000 +0200

...

+#define WOOD_REP(M,V1,V2) \

Please use "forest" instead of "wood".

Oh, sorry, thats a false friend, in German "forest" is "Wald".

+ // compare two weighted edges
+ struct VISIBILITY_HIDDEN EdgeWeightCompare {
+ bool operator()(const ProfileInfo::EdgeWeight X,
+ const ProfileInfo::EdgeWeight Y) const {
+ if ( X.second > Y.second ) return true;
+ if ( X.second < Y.second ) return false;
+ if ( X.first.first != 0 && Y.first.first == 0 ) return true;
+ if ( X.first.first == 0 && Y.first.first != 0 ) return false;
+ if ( X.first.first == 0 && Y.first.first == 0 ) return false;
+ int c1 = X.first.first->getName().compare(Y.first.first->getName());
+ if ( c1 > 0 ) return true;
+ if ( c1 < 0 ) return false;
+ int c2 = X.first.second->getName().compare(Y.first.second->getName());
+ if ( c2 > 0 ) return true;
+ return false;
+ }
+ };

Comparing edges based on the basic block name is not a good idea, in some common
cases these will all be empty. If the ordering really needs to be deterministic
then you will need to number the basic blocks, but is there a compelling reason
to not order based on the basic block address?

This slipped my notice and shouldn't have made it into production code. Its sufficient to order based on weights.
(This implementation was necessary when the MST was also needed for reading the profiling information, but since now I handle this with the Constant-Initializer that provides this information directly in the profile, its only necessary to compare the weight.)

[...]

+// countSuccessors() - This gives an estimate of the number of successors of a
+// basic block. Returns 0, 1 or 2 depending on the block having no, one or more
+// than one successors respectively.
+static int countSuccessors(BasicBlock* BB) {
+ succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
+ if ( SI != SE ) { // at least one successor
+ ++SI;
+ if ( SI == SE ) { // exactly on successor
+ return 1;
+ } else { // more than one successor
+ return 2;
+ }
+ } else {
+ return 0;
+ }
+}

This routine is only used in one place, and its result is compared against 0. I
think it should be removed and the code should just check (succ_begin(BB) ==
succ_end(BB)), or for better readability add a succ_empty to CFG.h and use that.

Okay.

--- llvm-van/lib/Analysis/ProfileEstimatorPass.cpp 1970-01-01 01:00:00.000000000 +0100
+++ llvm-c7/lib/Analysis/ProfileEstimatorPass.cpp 2009-06-26 16:47:01.000000000 +0200

...

+bool OptimalEdgeProfiler::runOnModule(Module &M) {
+ Function *Main = M.getFunction("main");
+ if (Main == 0) {
+ cerr << "WARNING: cannot insert edge profiling into a module"
+ << " with no main function!\n";
+ return false; // No main, no instrumentation!
+ }
+
+ std::set<BasicBlock*> BlocksToInstrument;
+ unsigned NumEdges = 0;
+ for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+ if (F->isDeclaration()) continue;
+ // use one counter for the edge (0,entry) for each function
+ ++NumEdges;
+ for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
+ // Keep track of which blocks need to be instrumented. We don't want to
+ // instrument blocks that are added as the result of breaking critical
+ // edges!
+ BlocksToInstrument.insert(BB);
+ NumEdges += BB->getTerminator()->getNumSuccessors();
+ }
+ }
+
+ const ArrayType *ATy = ArrayType::get(Type::Int32Ty, NumEdges);
+ GlobalVariable *Counters =
+ new GlobalVariable(ATy, false, GlobalValue::InternalLinkage,
+ 0, "OptimalEdgeProfCounters", &M);
+
+ std::vector<Constant*> Initializer = std::vector<Constant*>(NumEdges);

This unnecessarily copies the vector, please use:
std::vector<Constant*> Initializer(NumEdges);

Okay.

+ APInt zero(32,0); Constant* zeroc = ConstantInt::get(zero);
+ APInt minusone(32,-1); Constant* minusonec = ConstantInt::get(minusone);

Please use:

+ Constant* zeroc = ConstantInt::get(llvm::Type::Int32Ty, 0);
+ Constant* onec = ConstantInt::getSigned(llvm::Type::Int32Ty, -1);

Okay.

Thank you so much for taking the time and reviewing this giving me very valuable comments.

Andi

[...]

1. The intent of ProfileInfo is that it is the public interface used by the rest
of LLVM for all "profiling" related analyses. As such, we want it to have a
thin, well-defined interface which can be implemented by multiple analysis
providers, just like we have with the current alias analysis interface. Your
current patch has a large number of changes to ProfileInfo which should instead
be inside a subclass of ProfileInfo, where most of the implementation details
are private.

I think the first task should be to separate out the changes which are
appropriate for the ProfileInfo class itself and apply those to the tree. I
believe that the important changes which are worth reflecting in the API are
changed the weights to return a double instead of an int, and defining -1 as a
sentinel, "don't know", value.

So you want the ProfileInfo to be untouched except for the double weights and the MissingValue? Then mark all methods virtual and do a subclass that has this sort of heavy implementation that I am using?

Exactly.

Do you have any name suggestions for this subclass?

Not really. As with other interfaces, the actual implementation will
be completely hidden, so the only public part of the name is the
create...Pass call (and the options which end up being exposed to
'opt', etc). I would imagine something like DynamicProfileInfo,
OptimalEdgeDynamicProfileInfo, and StaticProfileInfoEstimator for the
main implementations.

One thing I would like to patch in the current ProfileInfo implementation is the consistent use of the (0,entry) edge which is necessary to profile functions with only one block (namely the entry block).

Yes, I agree, that should be part of the ProfileInfo API changes.

Eventually we will want to change the ProfileInfo API so that it is
easier to chain various ProfileInfo implementations. That way a client
can use dynamic profile information, but still get useful results for
code which wasn't profiled using the static estimator. Currently the
interfaces can't really accommodate this, because they return absolute
counts and there is no way to interpret results from two separate
profile info providers. However, I think for now its more important to
get stuff working than to worry about this problem.

This is the most important thing to separate out, and to do early, because it is
the main interface that is shared with LLVM. It is also important for my GSoC
student, who was going to work on static profiling for LLVM and will depend on
any changes to this interface.

Yes, I thought so, I will try to do this quick.

Great, thanks!

...

2. We shouldn't worry too much about preserving the functionality of the current
llvm-prof tool, which uses the ProfileInfoLoader directly. llvm-prof should be
rewritten to just use the public API provided by ProfileInfo. This should be
done early so there are less dependencies on the ProfileInfoLoader interface.

Okay, thats no problem. I guess it makes sense to rewrite llvm-prof but I was not sure if this sort of changes would be appreciated.

I'm pretty sure that no one uses llvm-prof, and I'm almost positive
that no one depends on it. I see its purpose as primarily to aid
developers working on profiling instrumentation -- it should be
useful, but not constraint the API or hinder development.

In fact, it might even make sense to just get rid of llvm-prof and instead
implement a module level pass which consumes profiling information and prints it
out as part of the pass. This would allow us to debug the preservation of
profiling information once we start modifying optimization passes to update it.

Good point.

Unless anyone objects I may end up just doing this if a rainy day
presents itself.

3. The static profiling estimator should be implemented as just another
ProfileInfo implementation. I believe this can be a separate patch. Similarly
the profile verifier is just another consumer of ProfileInfo and can be a
separate patch.

The ProfileEstimator is already a subclass of ProfileInfo and implements that interface. Yes, these two are easily split into separate patches.

Right. One nice benefit of having the ProfileInterface be completely
abstract is that it should be straightforward to move the
ProfileEstimator to being lazy and only computing information when a
client requests it.

4. Finally, the new optimal edge instrumentation & ProfileInfo implementation
can be brought in.

Does this sound like a reasonable plan? Although it is a bit of work, I don't
think it will be that difficult and I am happy to help out with splitting up the
patch / refactoring the existing code.

Yes, sounds good. I will try to split it up myself first and ask when there are decisions to be made I'm not sure about.

Ok!

+ /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
+ /// (Modelled after getExitingBlocks().)
+ typedef std::pair<BlockT*,BlockT*> Edge;
+ void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());

Would it be better to use a DenseSet for this lookup?

Well, its the same that is used in getExitBlocks() where I got the implementation from. I really don't know but I think the current implementation is okay from what I gather form the LLVM Programmer's Manual.

There is nothing wrong with it, but using a DenseSet has better
asymptotic performance and shortens the code. OTOH it may have a
higher construction cost in most practical scenarios, some I'm not
convinced about which is really best.

Thanks,
- Daniel

Hi,

I am having some difficulties getting the LLVM JIT to resolve extern "C" functions which I have defined in source file and invoking them via EE::runFunction() after generating a Function prototype for it. Is this possible or do I need to generate a .so for my functions are link against it?

Thanks in advanced,

Carter.

Hi,

this is the first in a series of patches to cleanup and improve the LLVM Profiling Infrastructure.

First and foremost this patch removes duplicate functionality from ProfileInfoLoader and ProfileInfo:
The ProfileInfoLoader performed not only the loading of the profile information but also some synthesis of block and function execution counts from edge profiling information. Since the ProfileInfo performs this synthesis anyways, the ProfileInfoLoader was demoted to be really only the interface to the profile information file.

Since the llvm-prof was the only client of the synthesis portion of the ProfileInfoLoader it had to be changed to fetch this kind of information from the ProfileInfo with the help of the ProfileInfoLoaderPass.

The next step are to
*) add proper handling of an edge (0,entry) for each function to the Profiling Infrastructure
*) provide a dedicated return value if the profiling information for a certain element is not available
*) change the profiling values itself to double as preparation for future passes that require floating point support from ProfileInfo

Greetings, Andi

llvm-r74697.profileinfo.cleanup.patch (26 KB)

Hi,

this is the second in a series of patches to cleanup and improve the
LLVM Profiling Infrastructure. It depends on the previous patch from
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023569.html

The ProfileInfoLoaderPass was only dealing with edge profiling
information, this patch adds support for block and function profiling
information.

Grettings, Andi

Hi,

this is the third in a series of patches to cleanup and improve the
LLVM Profiling Infrastructure. It depends on the previous patches from
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023569.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023602.html

This patch cleans up the ProfilingInfo by:
*) supplying a MissingValue marker for communicating to clients that a
certain piece of profiling information is not available
*) change the data type that profile info is stored in from unsigned to
double (needed for future changes)
*) add caching of synthesised values (e.g. when block information is
calculated from edge information)
*) support in the ProfileInfoLoaderPass for loading also block and
function profiles (up until now only edge profiles were loaded)
*) adding support for a (0,entry) edge to all profile related code

The next part is to implement a static profile estimator to support the
final goal of having optimal edge profiling.

To all the US-Folks: have a nice holiday weekend. To the rest of the
world: have a nice weekend too!

Andi

llvm-r74779.zero-entry-edge.double.cleanup.patch (17.5 KB)

Hi,

this is the third in a series of patches to cleanup and improve the
LLVM Profiling Infrastructure. It depends on the previous patches from
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023569.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023602.html

This patch cleans up the ProfilingInfo by:
*) supplying a MissingValue marker for communicating to clients that a
certain piece of profiling information is not available
*) change the data type that profile info is stored in from unsigned to
double (needed for future changes)
*) add caching of synthesised values (e.g. when block information is
calculated from edge information)
*) support in the ProfileInfoLoaderPass for loading also block and
function profiles (up until now only edge profiles were loaded)
*) adding support for a (0,entry) edge to all profile related code

The next part is to implement a static profile estimator to support the
final goal of having optimal edge profiling.

To all the US-Folks: have a nice holiday weekend. To the rest of the
world: have a nice weekend too!

Andi

llvm-r74779.zero-entry-edge.double.cleanup.patch (17.5 KB)

Hi,

this is the fourth in a series of patches to cleanup and improve the
LLVM Profiling Infrastructure. It depends on the previous patches from
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023569.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023602.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023642.html

This patch introduces an implementation of the ProfileInfo that
estimates a profile as proposed in [Ball94]. (It distributes incoming
flow in an block equally to the successor edges and assumes an loop
iteration count of 10.)

Andi

[Ball94] Thomas Ball, James R. Larus:
"Optimally profiling and tracing programs"
ACM TOPLAS, Volume 16, Issue 4, 1994
http://portal.acm.org/citation.cfm?id=183527

Okay, I guess I should attach the patch too...

Andreas Neustifter wrote:

llvm-r74818.profile-estimator.patch (10.6 KB)

I'm sorry, I saw that this patch is missing too...

Andreas Neustifter wrote:

llvm-r74762.added.block.function.profiling.patch (4.51 KB)

Hi,

this is the fifth in a series of patches to cleanup and improve the
LLVM Profiling Infrastructure. It depends on the previous patches from
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023569.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023602.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023642.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023643.html

Cleans up the previous patches a little bit and fixes some small bugs in
the llvm-prof output.

Andi

llvm-r74824.small.cleanup.patch (6.17 KB)

Hi,

this is the sixth in a series of patches to cleanup and improve the
LLVM Profiling Infrastructure. It depends on the previous patches from
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023569.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023602.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023642.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023643.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023649.html

This patch adds optimal edge profiling along the lines of [Ball94] throughout the LLVM Profiling Infrastructure.
(It also contains some small bugfixes and comment-fixes in the ProfileInfo.)

Andi

[Ball94] Thomas Ball, James R. Larus:
"Optimally profiling and tracing programs"
ACM TOPLAS, Volume 16, Issue 4, 1994

llvm-r74898.optimal.edge.profiling.patch (31.9 KB)

Hi,

this is the seventh in a series of patches to cleanup and improve the
LLVM Profiling Infrastructure. It depends on the previous patches from
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023569.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023602.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023642.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023643.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023649.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023683.html

It corrects an error which occured when loading the optimal edge profile. (The MissingValue marker was not handled correctly.)

Andi

llvm-r74898.missingvalue.bugfix.patch (4.47 KB)

Hi,

this is the eighth in a series of patches to cleanup and improve the
LLVM Profiling Infrastructure. It depends on the previous patches from
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023569.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023602.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023642.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023643.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023649.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023683.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023713.html

It improves the initialisation of the MaximumSpanningTree data structure.

Andi

llvm-r74898.maxspantree.init.patch (831 Bytes)

Hi,

this is the ninth (and last, for now) in a series of patches to cleanup and improve the LLVM Profiling Infrastructure. It depends on the previous patches from
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023569.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023602.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023642.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023643.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023649.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023683.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023713.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023715.html

This patch introduces the ProfileVerifier, a pass that calculates for each block if the sum of the incoming weights is equal to the weight of the block and equal to the sum of the outgoing weights. It is not strictly necessary for profiling but it makes development of profiling related passes easier, thus its published also.

Andi

llvm-r74993.profileverifier.patch (8.85 KB)

Hi Daniel,

I just want to make a few remarks to the things we discussed before I split up the patch from [1] to the patches, the last being [2]. Some of the code from the first patch [1] was rewritten in the process so some of the things we talked about changed a little, I want to give the rationale behind my new design decisions.

Andreas Neustifter wrote:

Daniel Dunbar wrote:
[...]

1. The intent of ProfileInfo is that it is the public interface used by the rest
of LLVM for all "profiling" related analyses. As such, we want it to have a
thin, well-defined interface which can be implemented by multiple analysis
providers, just like we have with the current alias analysis interface. Your
current patch has a large number of changes to ProfileInfo which should instead
be inside a subclass of ProfileInfo, where most of the implementation details
are private.

I think the first task should be to separate out the changes which are
appropriate for the ProfileInfo class itself and apply those to the tree. I
believe that the important changes which are worth reflecting in the API are
changed the weights to return a double instead of an int, and defining -1 as a
sentinel, "don't know", value.

So you want the ProfileInfo to be untouched except for the double weights and the MissingValue? Then mark all methods virtual and do a subclass that has this sort of heavy implementation that I am using? Do you have any name suggestions for this subclass?
One thing I would like to patch in the current ProfileInfo implementation is the consistent use of the (0,entry) edge which is necessary to profile functions with only one block (namely the entry block).

>
> [...]
>> The current ProfileInfo functions should also become virtual, and all other
>> implementation details should be left to the subclass.
>>
>> Finally, I don't think the ignoreMissing parameter to getExecutionCount makes
>> sense, instead the provider should always return -1 if it doesn't have the
>> value, and clients should "do the right thing.
> Maybe, its of course always possibile to have custom wrappers that perform this sort of task if necessary...
>
The so called "heavy implementation" has resolved itself partially, I changed in ProfileInfo only the synthesis that was there already to cache the synthesised values, for the ProfileInfo to be complete I also added BasicBlock and Function profiling. So the interface is just slightly bigger than before (MissingValue, Block and Function profiling) but now usable for (I guess) all ProfileInfo tasks.

During this I killed the synthesis part of ProfileInfoLoader (which was duplicated code from ProfileInfo) and I also had to rewrite llvm-prof to use ProfileInfo instead of ProfileInfoLoader. (I think llvm-prof is now quite cleanly implemented...).

2. We shouldn't worry too much about preserving the functionality of the current
llvm-prof tool, which uses the ProfileInfoLoader directly. llvm-prof should be
rewritten to just use the public API provided by ProfileInfo. This should be
done early so there are less dependencies on the ProfileInfoLoader interface.

Okay, thats no problem. I guess it makes sense to rewrite llvm-prof but I was not sure if this sort of changes would be appreciated.

See my comments to point 1., its rewritten now and works as before but with a interface towards ProfileInfo.

[...]

--- llvm-van/include/llvm/Analysis/ProfileInfo.h 2009-05-12 10:37:52.000000000 +0200
+++ llvm-c7/include/llvm/Analysis/ProfileInfo.h 2009-06-26 16:47:01.000000000 +0200
[...]

Instead of multiple maps from Function* ->, would it make sense to collect these
three (or four) maps inside a per-function structure?

Yes, makes sense, its then easier to factor out the retrieval and handling of this structure.

I tried this, it cluttered up the code with another redirection, I kept the 3 maps and I think this works good enough.

> [...]

--- llvm-van/lib/Analysis/MaximumSpanningTree.cpp 1970-01-01 01:00:00.000000000 +0100
+++ llvm-c7/lib/Analysis/MaximumSpanningTree.cpp 2009-06-26 16:47:01.000000000 +0200

...

+#define WOOD_REP(M,V1,V2) \

Please use "forest" instead of "wood".

Oh, sorry, thats a false friend, in German "forest" is "Wald".

All the wood is not combined into an forest :slight_smile:

> [...]

+ // compare two weighted edges
+ struct VISIBILITY_HIDDEN EdgeWeightCompare {
+ bool operator()(const ProfileInfo::EdgeWeight X,
+ const ProfileInfo::EdgeWeight Y) const {
+ if ( X.second > Y.second ) return true;
+ if ( X.second < Y.second ) return false;
+ if ( X.first.first != 0 && Y.first.first == 0 ) return true;
+ if ( X.first.first == 0 && Y.first.first != 0 ) return false;
+ if ( X.first.first == 0 && Y.first.first == 0 ) return false;
+ int c1 = X.first.first->getName().compare(Y.first.first->getName());
+ if ( c1 > 0 ) return true;
+ if ( c1 < 0 ) return false;
+ int c2 = X.first.second->getName().compare(Y.first.second->getName());
+ if ( c2 > 0 ) return true;
+ return false;
+ }
+ };

Comparing edges based on the basic block name is not a good idea, in some common
cases these will all be empty. If the ordering really needs to be deterministic
then you will need to number the basic blocks, but is there a compelling reason
to not order based on the basic block address?

This slipped my notice and shouldn't have made it into production code. Its sufficient to order based on weights.
(This implementation was necessary when the MST was also needed for reading the profiling information, but since now I handle this with the Constant-Initializer that provides this information directly in the profile, its only necessary to compare the weight.)

I have regression scripts that test the debug output of the various passes against a reference output to have a quick check if everything works as expected. For this its necessary to have a deterministic sorting of the edges. Since then block name is not good in this case (I knew, but I couldn't find another solution at that time) I use the block size now, this should stay the same if code is translated by the regression script. But I include the "advanced sorting" only in debug builds, in regular builds its still only sorting by edge weight.

[...]

The patches are still not as small as possible, I tried to go between reasonable sized patches and flooding the list with small patches, I hope its okay.

I have no or limited EMail this and next week, I will be back on the 20th of July.

Thanks, Andi

[1] http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-June/023427.html

[2] http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-July/023716.html

Hi Andreas,

Thanks for breaking things up.

I applied two pieces of this patch in separate no-functionality-change
commits, here:
  http://llvm.org/viewvc/llvm-project?view=rev&revision=75623
and here:
  http://llvm.org/viewvc/llvm-project?view=rev&revision=75625

I merged in my changes to your patch, which results in the attached
patch. There may be some missed merge errors. The main problem I have
with the rest of this patch is that it causes a regression in
llvm-prof's behavior. I tried running edge profiling on the
MultiSource/Applications/aha benchmark in the llvm test-suite, and
llvm-prof no longer prints any function information:

llvm-r74697.profileinfo.cleanup.regenerated.patch (18.7 KB)