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