[LLVMdev] Reviewer for our Path Profiling Implementation

[Adam Preuss]

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>