llvm dev - Dec 2010 - [LLVMdev] Reviewer for our Path Profiling Implementation

I am a student at the University of Alberta under the  
supervision of José Nelson Amaral, and I have been working on  
implementing path profiling into LLVM. I have completed my project
and would like to submit it.

We are looking for a reviewer for the path profiling implementation. We
have sent previous requests to the llvmdev list but have so far been
unsuccessful.

Please see the attached patch and associated documentation.

Adam Preuss

-------------- next part --------------
A non-text attachment was scrubbed...
Name: path-profiling.patch
Type: application/octet-stream
Size: 125334 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101203/33fa1268/attachment.obj>
-------------- next part --------------

-------------- next part --------------
A non-text attachment was scrubbed...
Name: doc.pdf
Type: application/pdf
Size: 81389 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101203/33fa1268/attachment.pdf>
-------------- next part --------------

On Dec 3, 2010, at 11:21 AM, Adam Preuss wrote:
> I am a student at the University of Alberta under the  
> supervision of José Nelson Amaral, and I have been working on  
> implementing path profiling into LLVM. I have completed my project
> and would like to submit it.
> 
> We are looking for a reviewer for the path profiling implementation. We
> have sent previous requests to the llvmdev list but have so far been
> unsuccessful.

As far as I know, none of LLVM's standard passes make use of any profiling
information.  If we are going to get any value from having profiling support in
LLVM, so that it is worth the effort of maintaining that code, we need to figure
out how we're going to use it.

In my opinion, it is essential that LLVM passes be able to query the profile
information with a standard API, and that they also be able to update the
profile information to account for changes to the code (e.g., when a block is
duplicated, when a loop is unrolled, etc.).  We need to have one API for those
things regardless of whether the profile information came from __builtin_expect,
simple heuristics, static analysis, or some kind of profile feedback.

The existing support for profile information does not include such an API, which
is at least part of the reason why nothing uses it. Adding path profiling would
only make things worse in that it would be yet another format of profiling
information.  Do you have any thoughts on how to provide an API for LLVM to use
and manipulate the path profiling information, in ways that would also apply to
other kinds of profile info?

I have not reviewed your patch in detail, but as you can tell, I have some
concerns about whether it makes sense to include this in LLVM.  I've never
worked on a compiler with path profiling, and the kind of profiling APIs that I
can think of would not work very well with path profiling.  I don't think it
makes sense to include this as a standard part of LLVM unless we can come up
with a way to make it useful.  If you have suggestions on how to do that, it
would help.

On Dec 3, 2010, at 11:21 AM, Adam Preuss wrote:
> I am a student at the University of Alberta under the  
> supervision of José Nelson Amaral, and I have been working on  
> implementing path profiling into LLVM. I have completed my project
> and would like to submit it.
> 
> We are looking for a reviewer for the path profiling implementation. We
> have sent previous requests to the llvmdev list but have so far been
> unsuccessful.
> 
> Please see the attached patch and associated documentation.
> 
> Adam Preuss
> 
> <path-profiling.patch>
> <doc.pdf>
Hi Adam,

Thanks for making the effort to contribute. I have seen some valid
feedback to the effect that we can't keep something in mainline unless
is it actively used or maintained. However, I'm willing to give you a
review so it can be checked in, with no guarantee that the code won't
be removed if it breaks, or replaced by a different profiler if we
ever adopt one for active use.

Thanks for the design doc. We'll be sure to get that checked into
llvm.org/pubs. A couple of design questions: Can you compare the
overhead of LLVM's edge profiler vs path profiler, both run time
(profile time) and compile time? How do you anticipate the path
profile to be used by the optimizer?

Regarding the implementation, a couple of style problems should be addressed:

- Tabs absolutely need to be removed:
http://llvm.org/docs/CodingStandards.html#scf_spacestabs

- I see a few violation of 80 cols. Not many, but too many for me
  to list here.

If you think any of my specific suggestions below are off-base, don't
follow them, just respond with some justification. Since you've
already done rigorous verification, and I'm not overly concerned with
optimality, most of my comments are style related.

---
+static cl::opt<std::string>
+EdgeProfileFilename("path-profile-verifier-file",
+	cl::init("edgefrompath.llvmprof.out"),
+	cl::value_desc("filename"),
+  cl::desc("Edge profile file generated by -path-profile-verifier"));
...
+// command line option for loading path profiles
+static cl::opt<std::string>
+PathProfileInfoFilename("path-profile-loader-file",
cl::init("llvmprof.out"),
+                        cl::value_desc("filename"),
+                        cl::desc("Path profile file loaded by
-path-profile-loader"));
...
+// Are we enabling early termination
+static cl::opt<bool>
ProcessEarlyTermination("process-early-termination",
+	cl::desc("In path profiling, insert extra instrumentation to account for
"
+           "unexpected function termination."));
...
+// Should we print the dot-graphs
+static cl::opt<bool> DotPathDag("dot-pathdag",
+	cl::desc("Output the path profiling DAG for each function."));

Please add cl::Hidden to all new flags, and give them all
a "path-profile" prefix so they aren't scattered in the hidden
help text.

+++ include/llvm/Analysis/ProfileInfoTypes.h

+#define PP_ARRAY 0
+#define PP_HASH  1

Why not an enum?

+typedef struct {
+  unsigned fnNumber; /* function number for these counters */
+  unsigned numEntries;   /* number of entries stored */
+} PathHeader;
+
+typedef struct {
+  unsigned pathNumber;
+  unsigned pathCounter;
+} PathTableEntry;

Being global types, they need a PathProfiling-specific name or prefix
(there are other kinds of paths). To be proper, should they also be under:
#if defined(__cplusplus)
 extern "C" {
endif

You may even want to remove the emacs hint "-*- C++ -*-" from both
this header and Profiling.h

+++ runtime/libprofile/Profiling.h

+#include <stdint.h>
+#include <unistd.h>

Include these only in the .cpp files in which they're needed. Include
them after any non-system headers.

+typedef int PType; /* type for storing enum ProfilingType on disk */

I realize PType is currently only included within libprofile, but the
general guideline is to make type names in the global namespace
descriptive. Such as ProfileInfoStorageType.

I'm not sure why you made it a global type. Was it for use by the
profile loader? If so, I think it would need to be in
ProfileInfoTypes.h under extern "C".

+++ runtime/libprofile/CommonProfiling.c

+static int OutFile = -1;

I'm not sure why OutFile cannot remain a local static within
getOutFile.

+  int res;
...
+  res = write(outFile, &PTy, sizeof( Profile));

Some builds may warn of the unused result. If you're not checking the
result, you probably shouldn't retrieve it.

+++ runtime/libprofile/PathProfiling.c

+ inline uint32_t* getPathCounter(uint32_t functionNumber, uint32_t pathNumber)
{
...
+	if( ((ftEntry_t*)ft)[functionNumber-1].array == 0)
+		((ftEntry_t*)ft)[functionNumber-1].array calloc(sizeof(pathHashTable_t), 1);

It's not immediately obvious to me why you always cast "ft".

Since this is a runtime lib, it may be wise to add array bounds checks.

In getPathCounter can you check that type == PP_HASH and size == 0
before writing to the data structure?

+++ lib/Transforms/Instrumentation/ProfilingUtils.h	(working copy)

+#include "llvm/DerivedTypes.h"

Add the include only in the .cpp files that need it.

+++ include/llvm/Analysis/PathNumbering.h

+namespace llvm {
+	class BallLarusNode;

I don't think you should indent large namespaces bodies. Same goes for
the rest of the files.

+++ lib/Analysis/PathNumbering.cpp

The constructor and accessors are trivial and can be defined inline.

+ void BallLarusDag::calculatePathNumbersFrom(BallLarusNode* node) {
...
+      BallLarusEdge* currEdge = *succ;
+      currEdge->setWeight(sumPaths);
+      succNode = currEdge->getTarget();
+      unsigned succPaths = succNode->getNumberPaths();
+      isReady = isReady && (succPaths != 0);

If a successor is not finished, can you early return here instead of
prematurely setting the edge weights? Better yet, keep a count
of the remaining successors, then only call calculatePathNumberFrom()
once per node after all successors are visited? You already visiting
each pred edge after finishing a node, just decrement its remaining
count at that time.

+++ lib/Transforms/Instrumentation/PathProfiling.cpp

+ void PathProfiler::insertInstrumentationStartingAt(BLInstrumentationEdge*

Does this need to be recursive? If you simply visit the edges in dfs
order (creation order?) would that be sufficient? I don't think you
even need to create RPO order, since phis can be lazily prepared.

+++ include/llvm/Analysis/PathProfileInfo.h

+ #ifndef LLVM_ANALYSIS_BALLLARUSPATHPROFILEINFO_H

Symbol doesn't really need to be this long.

+#include <stack>
+#include "llvm/BasicBlock.h"
+#include "llvm/Analysis/PathNumbering.h"

Put system headers after user headers.

+namespace llvm {
+	class Path;

A class Path already exists. You just got lucky it's in llvm::sys. Please
wrap your classes in a namespace (e.g. llvm::PathProfile) or give
them fully descriptive names.

+++ include/llvm/Analysis/PathProfileInfo.cpp

+unsigned PathEdge::getDuplicateNumber() {
+	return _duplicateNumber;
+}
+
+BasicBlock* PathEdge::getSource() {
+	return _source;
+}
+
+BasicBlock* PathEdge::getTarget() {
+	return _target;
+}
...

Trivial accessors should be defined inline.

-Andy

Thank you for your suggestions on the patch. If the patch is committed, I would
be willing to maintain it, though
I am not sure what is all involved or how I am made aware of changes that need
to be made.

The technical report
https://www.cs.ualberta.ca/system/files/tech_report/2010/PreussPathProfLLVM.pdf
contains
my benchmarks relating to profiling overhead in LLVM.

Over the next week I will work through the patch and make the appropriate
adjustments. I have some responses to your
comments below as well. Things that I haven't commented on make sense and I
will change them.

Adam

On 2010-12-07, at 5:09 PM, Andrew Trick wrote:
> On Dec 3, 2010, at 11:21 AM, Adam Preuss wrote:
>> I am a student at the University of Alberta under the  
>> supervision of José Nelson Amaral, and I have been working on  
>> implementing path profiling into LLVM. I have completed my project
>> and would like to submit it.
>> 
>> We are looking for a reviewer for the path profiling implementation. We
>> have sent previous requests to the llvmdev list but have so far been
>> unsuccessful.
>> 
>> Please see the attached patch and associated documentation.
>> 
>> Adam Preuss
>> 
>> <path-profiling.patch>
>> <doc.pdf>
> 
> Hi Adam,
> 
> Thanks for making the effort to contribute. I have seen some valid
> feedback to the effect that we can't keep something in mainline unless
> is it actively used or maintained. However, I'm willing to give you a
> review so it can be checked in, with no guarantee that the code won't
> be removed if it breaks, or replaced by a different profiler if we
> ever adopt one for active use.
> 
> Thanks for the design doc. We'll be sure to get that checked into
> llvm.org/pubs. A couple of design questions: Can you compare the
> overhead of LLVM's edge profiler vs path profiler, both run time
> (profile time) and compile time? How do you anticipate the path
> profile to be used by the optimizer?
> 
> Regarding the implementation, a couple of style problems should be
addressed:
> 
> - Tabs absolutely need to be removed:
> http://llvm.org/docs/CodingStandards.html#scf_spacestabs
> 
> - I see a few violation of 80 cols. Not many, but too many for me
>  to list here.
> 
> If you think any of my specific suggestions below are off-base, don't
> follow them, just respond with some justification. Since you've
> already done rigorous verification, and I'm not overly concerned with
> optimality, most of my comments are style related.
> 
> ---
> +static cl::opt<std::string>
> +EdgeProfileFilename("path-profile-verifier-file",
> +	cl::init("edgefrompath.llvmprof.out"),
> +	cl::value_desc("filename"),
> +  cl::desc("Edge profile file generated by
-path-profile-verifier"));
> ...
> +// command line option for loading path profiles
> +static cl::opt<std::string>
> +PathProfileInfoFilename("path-profile-loader-file",
cl::init("llvmprof.out"),
> +                        cl::value_desc("filename"),
> +                        cl::desc("Path profile file loaded by
-path-profile-loader"));
> ...
> +// Are we enabling early termination
> +static cl::opt<bool>
ProcessEarlyTermination("process-early-termination",
> +	cl::desc("In path profiling, insert extra instrumentation to account
for "
> +           "unexpected function termination."));
> ...
> +// Should we print the dot-graphs
> +static cl::opt<bool> DotPathDag("dot-pathdag",
> +	cl::desc("Output the path profiling DAG for each function."));
> 
> Please add cl::Hidden to all new flags, and give them all
> a "path-profile" prefix so they aren't scattered in the
hidden help text.
> 
> +++ include/llvm/Analysis/ProfileInfoTypes.h
> 
> +#define PP_ARRAY 0
> +#define PP_HASH  1
> 
> Why not an enum?
> 
> +typedef struct {
> +  unsigned fnNumber; /* function number for these counters */
> +  unsigned numEntries;   /* number of entries stored */
> +} PathHeader;
> +
> +typedef struct {
> +  unsigned pathNumber;
> +  unsigned pathCounter;
> +} PathTableEntry;
> 
> Being global types, they need a PathProfiling-specific name or prefix
> (there are other kinds of paths). To be proper, should they also be under:
> #if defined(__cplusplus)
> extern "C" {
> endif
> 
> You may even want to remove the emacs hint "-*- C++ -*-" from
both
> this header and Profiling.h
> 
> +++ runtime/libprofile/Profiling.h
> 
> +#include <stdint.h>
> +#include <unistd.h>
> 
> Include these only in the .cpp files in which they're needed. Include
> them after any non-system headers.
> 
> +typedef int PType; /* type for storing enum ProfilingType on disk */
> 
> I realize PType is currently only included within libprofile, but the
> general guideline is to make type names in the global namespace
> descriptive. Such as ProfileInfoStorageType.
> 
> I'm not sure why you made it a global type. Was it for use by the
> profile loader? If so, I think it would need to be in
> ProfileInfoTypes.h under extern "C".
> 
> +++ runtime/libprofile/CommonProfiling.c
> 
> +static int OutFile = -1;
> 
> I'm not sure why OutFile cannot remain a local static within
> getOutFile.
> 
> +  int res;
> ...
> +  res = write(outFile, &PTy, sizeof( Profile));
> 
> Some builds may warn of the unused result. If you're not checking the
> result, you probably shouldn't retrieve it.
> 
> +++ runtime/libprofile/PathProfiling.c
> 
> + inline uint32_t* getPathCounter(uint32_t functionNumber, uint32_t
pathNumber) {
> ...
> +	if( ((ftEntry_t*)ft)[functionNumber-1].array == 0)
> +		((ftEntry_t*)ft)[functionNumber-1].array >
calloc(sizeof(pathHashTable_t), 1);
> 
> It's not immediately obvious to me why you always cast "ft".
I think there used to be a reason, but I don't see a reason to any more.
> 
> Since this is a runtime lib, it may be wise to add array bounds checks.
I can, but a path number will never be larger than the array size so I don't
think it's necessary.
> 
> In getPathCounter can you check that type == PP_HASH and size == 0
> before writing to the data structure?
> 
> +++ lib/Transforms/Instrumentation/ProfilingUtils.h	(working copy)
> 
> +#include "llvm/DerivedTypes.h"
> 
> Add the include only in the .cpp files that need it.
> 
> +++ include/llvm/Analysis/PathNumbering.h
> 
> +namespace llvm {
> +	class BallLarusNode;
> 
> I don't think you should indent large namespaces bodies. Same goes for
> the rest of the files.
> 
> +++ lib/Analysis/PathNumbering.cpp
> 
> The constructor and accessors are trivial and can be defined inline.
> 
> + void BallLarusDag::calculatePathNumbersFrom(BallLarusNode* node) {
> ...
> +      BallLarusEdge* currEdge = *succ;
> +      currEdge->setWeight(sumPaths);
> +      succNode = currEdge->getTarget();
> +      unsigned succPaths = succNode->getNumberPaths();
> +      isReady = isReady && (succPaths != 0);
> 
> If a successor is not finished, can you early return here instead of
> prematurely setting the edge weights? Better yet, keep a count
> of the remaining successors, then only call calculatePathNumberFrom()
> once per node after all successors are visited? You already visiting
> each pred edge after finishing a node, just decrement its remaining
> count at that time.
Yes, I don't see why not.
> 
> +++ lib/Transforms/Instrumentation/PathProfiling.cpp
> 
> + void PathProfiler::insertInstrumentationStartingAt(BLInstrumentationEdge*
> 
> Does this need to be recursive? If you simply visit the edges in dfs
> order (creation order?) would that be sufficient? I don't think you
> even need to create RPO order, since phis can be lazily prepared.
I think it has to traverse in the current method, otherwise certain pointers to
path counters, phi nodes, etc will not be initialized properly in my
representation
of the graph. I will it over more closely though.
> 
> +++ include/llvm/Analysis/PathProfileInfo.h
> 
> + #ifndef LLVM_ANALYSIS_BALLLARUSPATHPROFILEINFO_H
> 
> Symbol doesn't really need to be this long.
> 
> +#include <stack>
> +#include "llvm/BasicBlock.h"
> +#include "llvm/Analysis/PathNumbering.h"
> 
> Put system headers after user headers.
> 
> +namespace llvm {
> +	class Path;
> 
> A class Path already exists. You just got lucky it's in llvm::sys.
Please
> wrap your classes in a namespace (e.g. llvm::PathProfile) or give
> them fully descriptive names.
> 
> +++ include/llvm/Analysis/PathProfileInfo.cpp
> 
> +unsigned PathEdge::getDuplicateNumber() {
> +	return _duplicateNumber;
> +}
> +
> +BasicBlock* PathEdge::getSource() {
> +	return _source;
> +}
> +
> +BasicBlock* PathEdge::getTarget() {
> +	return _target;
> +}
> ...
> 
> Trivial accessors should be defined inline.
> 
> -Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101208/b3583233/attachment.html>

[Cc'd to a bunch of people who have in the past expressed interest in
profiling with LLVM.]

On Mon, Dec 06, 2010 at 10:39:37 -0800, Bob Wilson
wrote:
> As far as I know, none of LLVM's standard passes make use of any
profiling
> information.  If we are going to get any value from having profiling
> support in LLVM, so that it is worth the effort of maintaining that code,
> we need to figure out how we're going to use it.
Right. That's a lot of grunt work, and no one person or group will probably
want to do it, especially if the results will not be very visible to others.

For this reason, our group in Vienna would like to propose a bundling of
various people's efforts in profiling. In particular, we would be willing to
host an LLVM branch that is open to profiling-related contributions such as:
- various kinds of profilers
- patches to preserve/update profiling information across existing passes
- code that improves existing passes based on profiling info
- code that communicates profiling data to the backend (to get MBB profile
  data, profile-based spill weights etc.)

The idea is to be more open to such submissions than mainline LLVM is, so
that we can experiment with and compare different approaches. Hopefully,
some parts of this would converge to a state that would then deemed
acceptable for mainline LLVM. Even if not, we would have a common codebase
in which the more boring parts (such as preserving info across simple
passes) are solved once and for all.
> In my opinion, it is essential that LLVM passes be able to query the
profile information with a standard API, and that they also be able to update
the profile information to account for changes to the code (e.g., when a block
is duplicated, when a loop is unrolled, etc.).  We need to have one API for
those things regardless of whether the profile information came from
__builtin_expect, simple heuristics, static analysis, or some kind of profile
feedback.
Absolutely. Bringing together people with different approaches to profiling
should hopefully help us get a good picture about what this standard API
could look like; and then also provide a number of profilers and clients
conforming to that API.

To get some idea about the number of people who could be involved in a
project like this, I would like to ask for a quick show of hands: Who would
be interested in contributing code to LLVM-with-profiling? (Either actual
profiling code, or passes that use profiling information.)
Who would want to use the branch, even without contributing?

-- 
Gergö Barany, research assistant                   gergo at
complang.tuwien.ac.at
Institute of Computer Languages        http://www.complang.tuwien.ac.at/gergo/
Vienna University of Technology                         Tel: +43-1-58801-58522
Argentinierstrasse 8/E185, 1040 Wien, Austria           Fax: +43-1-58801-18598