Xinliang David Li via llvm-dev
2016-Mar-11 06:36 UTC
[llvm-dev] RFC: Pass to prune redundant profiling instrumentation
On Thu, Mar 10, 2016 at 10:13 PM, Sean Silva <chisophugis at gmail.com> wrote:> > > On Thu, Mar 10, 2016 at 9:42 PM, Xinliang David Li <xinliangli at gmail.com> > wrote: > >> >> >> On Thu, Mar 10, 2016 at 8:33 PM, Sean Silva via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> >>> >>> On Thu, Mar 10, 2016 at 7:21 PM, Vedant Kumar via llvm-dev < >>> llvm-dev at lists.llvm.org> wrote: >>> >>>> Hi, >>>> >>>> I'd like to add a new pass to LLVM which removes redundant profile >>>> counter >>>> updates. The goal is to speed up code coverage testing and profile >>>> generation >>>> for PGO. >>>> >>> >>> We may want to have a focused discussion about this goal, rather than a >>> particular suggestion. There are a lot of things we can do. Off the top of >>> my head, some are: >>> >>> 1. add some sort of alias annotation (such as an independent TBAA root >>> node) to all the counter increment memory instructions to tell the >>> optimizer they don't interfere with the usual loads and stores. >>> >>> 2. communicate to the optimizer that counters can be registerized. In a >>> loop like: >>> for (int i = 0; i < N; i++) { >>> if (foo()) >>> bar(); >>> else >>> baz(); >>> } >>> we perform O(N) counter increments (i.e. load, increment, store) last I >>> checked. However, if the counters are in registers, then we only perform >>> O(1) memory operations. This can dramatically reduce the pressure on the >>> CPU's load/store units and also relieve cross-core cache line ping-pong >>> when two cores are executing the same code. Note that the latter benefit is >>> attained even if we ultimately end up spilling the counters due to >>> increased register pressure. >>> >>> I actually don't know what is preventing the usual optimization pipeline >>> from getting 2 right. >>> >> >> Call Mod-ref. We need to teach the optimizer that the counter owned by >> the current function (if the function is proved to be non-recursive in some >> way) can not be modified by any other calls. >> > > I don't think that's a sufficient explanation. Consider the following > example: > > Sean:~/tmp % cat testprofile.cpp > int foo(int n) { > unsigned Ret = 42; > for (int i = 0; i < n; i++) { > if (i % 100) { > Ret += 789; > } else { > Ret *= (283 + Ret); > } > } > return Ret; > } > > Sean:~/tmp % ~/pg/release/bin/clang++ -o - -fprofile-instr-generate > testprofile.cpp -S -emit-llvm -O2 >foo.ll > Sean:~/tmp % ~/pg/release/bin/opt -view-cfg foo.ll > > >(resent) I saw your example has function call in the loop, thus the comment about Modref. For this example, the reason seems to that we don't yet do speculative PRE which usually requires profile information. Note that the update is conditionally done in a branch. Also note that the counter update of the block %8 is fully optimized away. David> > -- Sean Silva > > >> >> David >> >> >> >> >>> >>> >>>> >>>> I'm sending this email out to describe my approach, share some early >>>> results, >>>> and gather feedback. >>>> >>>> >>>> Problem Overview >>>> ===============>>>> >>>> A profile counter is redundant if it's incremented in exactly the same >>>> basic >>>> blocks as some other profile counter. Consider the following module: >>>> >>>> local void f1() { >>>> instrprof_increment(profc_f1); >>>> } >>>> >>>> void f2() { >>>> instrprof_increment(profc_f2); >>>> f1(); >>>> } >>>> >>>> Once the inliner runs and deletes f1, we're left with: >>>> >>>> void f2() { >>>> instrprof_increment(profc_f2); >>>> instrprof_increment(profc_f1); >>>> } >>>> >>>> Now we can say profc_f1 is redundant (or, an alias for profc_f2). >>>> >>>> I've noticed that frontend-based instrumentation can generate many >>>> redundant >>>> profile counters. This degrades performance and increases code size. >>>> We can >>>> address the problem by getting rid of redundant counter updates. The >>>> trick is >>>> to make sure we get back the same profiles. >>>> >>>> >>>> Proposed Solution >>>> ================>>>> >>>> I propose a pruning pass which takes the following steps: >>>> >>>> 1. Delete functions with local linkage and only one use, if that use >>>> is in >>>> a profile data record. >>>> >>>> These functions are left around by the inliner (it doesn't know >>>> that >>>> they're safe to delete). Deleting them reduces code size and >>>> simplifies >>>> subsequent analysis of profile counters. >>>> >>>> 2. Determine which profile counters are essential. >>>> >>>> 3. Erase all updates to redundant profile counters. >>>> >>>> 4. Emit the aliases into a new section in the binary. >>>> >>>> Aliases are represented as { Dst: i64*, Src: i64* } tuples. Some >>>> changes >>>> in compiler-rt are required to walk the alias section and fill in >>>> the >>>> correct execution counts at program exit time. >>>> >>>> This pass needs to be run after the inliner in order to be effective. >>>> >>>> The complexity of this pass is O(N*M), where N is the number of profile >>>> counters, and M is the average number of updates per counter. In >>>> practice it is >>>> a bit faster, since we can skip the analysis of counters which are >>>> discovered to >>>> be redundant early on in the process. >>>> >>> >>> I think a conceptually simpler design is something like: >>> >>> for each CFG edge: >>> record which FE counters have ended up associated with it >>> remove FE counters >>> run IR instrumentation pass >>> emit a side table mapping IR instr counters to FE counters (more >>> generally: how to reconstruct FE counters from the IR counters) >>> >>> The problem is simply reduced to the IR instrumentation pass. >>> >>> >>>> >>>> >>>> Early Results >>>> ============>>>> >>>> The pruning pass results in 25% speed improvement in the example >>>> program above >>>> (where f2 is called in a loop 10^8 times). >>>> >>>> Here is a slightly less contrived example: >>>> >>>> #include <vector> >>>> #include <algorithm> >>>> #include <cstdlib> >>>> >>>> static void escape(void *p) { >>>> asm volatile("" : : "g"(p) : "memory"); >>>> } >>>> >>>> int main(int argc, char **argv) { >>>> std::vector<int> V(atoi(argv[1])); >>>> escape(reinterpret_cast<void *>(V.data())); >>>> std::sort(V.begin(), V.end()); >>> >>> return V[0]; >>>> } >>>> >>>> I get the following results on my desktop (10^8 elements, 5 runs each): >>>> >>>> O3: 0.262s >>>> O3 + PGOInstr: 0.663s >>>> O3 + PGOInstr + Pruning: 0.606s (8.6% performance win, 672 >>>> aliases) >>>> O3 + CoverageInstr: 0.690s >>>> O3 + CoverageInstr + Pruning: 0.610s (11.6% performance win, 688 >>>> aliases) >>>> >>>> >>>> Next Steps? >>>> ==========>>>> >>>> Is the performance of instrumented code something we think we need to >>>> fix? >>>> >>> >>> With frontend instrumentation it definitely is. >>> >>> What's an acceptable compile-time overhead for running this pruning pass? >>> >>> >>> Instrumented builds are "special" anyway so a fair slowdown is probably >>> acceptable. I.e. this doesn't affect regular developer compilation times. >>> As a baseline, maybe compare compile time of `-fprofile-instr-generate -O2` >>> vs. `-O2`. If `-fprofile-instr-generate -O2` is 10% slower than the >>> control, then that indicates that a 5% extra slowdown is probably >>> reasonable for a substantial reduction in profiling overhead (which can >>> result in a qualitative improvement to the actual usability of the >>> instrumented program). >>> >>> -- Sean Silva >>> >>> >>> >>>> Is >>>> the general approach a non-starter for anybody? >>>> >>>> I'd like to get some feedback and gauge interest before pursuing this >>>> further. >>>> Possible next steps include benchmarking instrumented versions of clang >>>> and >>>> swift on the relevant test suites, running performance tests from lnt, >>>> running >>>> compile-time tests, and measuring any code size differences. >>>> >>>> >>>> thanks >>>> vedant >>>> >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> llvm-dev at lists.llvm.org >>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>> >>> >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >>> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160310/b14013dc/attachment.html>
Sean Silva via llvm-dev
2016-Mar-11 08:20 UTC
[llvm-dev] RFC: Pass to prune redundant profiling instrumentation
On Thu, Mar 10, 2016 at 10:36 PM, Xinliang David Li <xinliangli at gmail.com> wrote:> > > On Thu, Mar 10, 2016 at 10:13 PM, Sean Silva <chisophugis at gmail.com> > wrote: > >> >> >> On Thu, Mar 10, 2016 at 9:42 PM, Xinliang David Li <xinliangli at gmail.com> >> wrote: >> >>> >>> >>> On Thu, Mar 10, 2016 at 8:33 PM, Sean Silva via llvm-dev < >>> llvm-dev at lists.llvm.org> wrote: >>> >>>> >>>> >>>> On Thu, Mar 10, 2016 at 7:21 PM, Vedant Kumar via llvm-dev < >>>> llvm-dev at lists.llvm.org> wrote: >>>> >>>>> Hi, >>>>> >>>>> I'd like to add a new pass to LLVM which removes redundant profile >>>>> counter >>>>> updates. The goal is to speed up code coverage testing and profile >>>>> generation >>>>> for PGO. >>>>> >>>> >>>> We may want to have a focused discussion about this goal, rather than a >>>> particular suggestion. There are a lot of things we can do. Off the top of >>>> my head, some are: >>>> >>>> 1. add some sort of alias annotation (such as an independent TBAA root >>>> node) to all the counter increment memory instructions to tell the >>>> optimizer they don't interfere with the usual loads and stores. >>>> >>>> 2. communicate to the optimizer that counters can be registerized. In a >>>> loop like: >>>> for (int i = 0; i < N; i++) { >>>> if (foo()) >>>> bar(); >>>> else >>>> baz(); >>>> } >>>> we perform O(N) counter increments (i.e. load, increment, store) last I >>>> checked. However, if the counters are in registers, then we only perform >>>> O(1) memory operations. This can dramatically reduce the pressure on the >>>> CPU's load/store units and also relieve cross-core cache line ping-pong >>>> when two cores are executing the same code. Note that the latter benefit is >>>> attained even if we ultimately end up spilling the counters due to >>>> increased register pressure. >>>> >>>> I actually don't know what is preventing the usual optimization >>>> pipeline from getting 2 right. >>>> >>> >>> Call Mod-ref. We need to teach the optimizer that the counter owned by >>> the current function (if the function is proved to be non-recursive in some >>> way) can not be modified by any other calls. >>> >> >> I don't think that's a sufficient explanation. Consider the following >> example: >> >> Sean:~/tmp % cat testprofile.cpp >> int foo(int n) { >> unsigned Ret = 42; >> for (int i = 0; i < n; i++) { >> if (i % 100) { >> Ret += 789; >> } else { >> Ret *= (283 + Ret); >> } >> } >> return Ret; >> } >> >> Sean:~/tmp % ~/pg/release/bin/clang++ -o - -fprofile-instr-generate >> testprofile.cpp -S -emit-llvm -O2 >foo.ll >> Sean:~/tmp % ~/pg/release/bin/opt -view-cfg foo.ll >> >> >> > (resent) > > I saw your example has function call in the loop, thus the comment about > Modref. > > For this example, the reason seems to that we don't yet do speculative PRE > which usually requires profile information. Note that the update is > conditionally done in a branch. Also note that the counter update of the > block %8 is fully optimized away. >(forgive my ignorance of compiler theory) Should we generally expect the optimizer to get this right at some point? (i.e. is it a bug in the optimizer?) Or do you think that a special pass is needed to get the desired effect for counters for normal use of instrumentation? It seems like inherently counter updates will happen only conditionally, and so this kind of situation will be common. Counters seem like they have special semantics that allows more flexibility. For example, the call mod-ref problem is actually not a problem due to commutativity. We know that the callee will at most increment the counter, so as long as the load,increment,store is not interrupted by a call (which is easy to avoid) then we can freely move it across calls. (actually, in theory a call into the profile lib could read the counters, but in practice I expect this to not be an issue). -- Sean Silva> > David > > > >> >> -- Sean Silva >> >> >>> >>> David >>> >>> >>> >>> >>>> >>>> >>>>> >>>>> I'm sending this email out to describe my approach, share some early >>>>> results, >>>>> and gather feedback. >>>>> >>>>> >>>>> Problem Overview >>>>> ===============>>>>> >>>>> A profile counter is redundant if it's incremented in exactly the same >>>>> basic >>>>> blocks as some other profile counter. Consider the following module: >>>>> >>>>> local void f1() { >>>>> instrprof_increment(profc_f1); >>>>> } >>>>> >>>>> void f2() { >>>>> instrprof_increment(profc_f2); >>>>> f1(); >>>>> } >>>>> >>>>> Once the inliner runs and deletes f1, we're left with: >>>>> >>>>> void f2() { >>>>> instrprof_increment(profc_f2); >>>>> instrprof_increment(profc_f1); >>>>> } >>>>> >>>>> Now we can say profc_f1 is redundant (or, an alias for profc_f2). >>>>> >>>>> I've noticed that frontend-based instrumentation can generate many >>>>> redundant >>>>> profile counters. This degrades performance and increases code size. >>>>> We can >>>>> address the problem by getting rid of redundant counter updates. The >>>>> trick is >>>>> to make sure we get back the same profiles. >>>>> >>>>> >>>>> Proposed Solution >>>>> ================>>>>> >>>>> I propose a pruning pass which takes the following steps: >>>>> >>>>> 1. Delete functions with local linkage and only one use, if that use >>>>> is in >>>>> a profile data record. >>>>> >>>>> These functions are left around by the inliner (it doesn't know >>>>> that >>>>> they're safe to delete). Deleting them reduces code size and >>>>> simplifies >>>>> subsequent analysis of profile counters. >>>>> >>>>> 2. Determine which profile counters are essential. >>>>> >>>>> 3. Erase all updates to redundant profile counters. >>>>> >>>>> 4. Emit the aliases into a new section in the binary. >>>>> >>>>> Aliases are represented as { Dst: i64*, Src: i64* } tuples. Some >>>>> changes >>>>> in compiler-rt are required to walk the alias section and fill in >>>>> the >>>>> correct execution counts at program exit time. >>>>> >>>>> This pass needs to be run after the inliner in order to be effective. >>>>> >>>>> The complexity of this pass is O(N*M), where N is the number of profile >>>>> counters, and M is the average number of updates per counter. In >>>>> practice it is >>>>> a bit faster, since we can skip the analysis of counters which are >>>>> discovered to >>>>> be redundant early on in the process. >>>>> >>>> >>>> I think a conceptually simpler design is something like: >>>> >>>> for each CFG edge: >>>> record which FE counters have ended up associated with it >>>> remove FE counters >>>> run IR instrumentation pass >>>> emit a side table mapping IR instr counters to FE counters (more >>>> generally: how to reconstruct FE counters from the IR counters) >>>> >>>> The problem is simply reduced to the IR instrumentation pass. >>>> >>>> >>>>> >>>>> >>>>> Early Results >>>>> ============>>>>> >>>>> The pruning pass results in 25% speed improvement in the example >>>>> program above >>>>> (where f2 is called in a loop 10^8 times). >>>>> >>>>> Here is a slightly less contrived example: >>>>> >>>>> #include <vector> >>>>> #include <algorithm> >>>>> #include <cstdlib> >>>>> >>>>> static void escape(void *p) { >>>>> asm volatile("" : : "g"(p) : "memory"); >>>>> } >>>>> >>>>> int main(int argc, char **argv) { >>>>> std::vector<int> V(atoi(argv[1])); >>>>> escape(reinterpret_cast<void *>(V.data())); >>>>> std::sort(V.begin(), V.end()); >>>> >>>> return V[0]; >>>>> } >>>>> >>>>> I get the following results on my desktop (10^8 elements, 5 runs each): >>>>> >>>>> O3: 0.262s >>>>> O3 + PGOInstr: 0.663s >>>>> O3 + PGOInstr + Pruning: 0.606s (8.6% performance win, 672 >>>>> aliases) >>>>> O3 + CoverageInstr: 0.690s >>>>> O3 + CoverageInstr + Pruning: 0.610s (11.6% performance win, 688 >>>>> aliases) >>>>> >>>>> >>>>> Next Steps? >>>>> ==========>>>>> >>>>> Is the performance of instrumented code something we think we need to >>>>> fix? >>>>> >>>> >>>> With frontend instrumentation it definitely is. >>>> >>>> What's an acceptable compile-time overhead for running this pruning >>>>> pass? >>>> >>>> >>>> Instrumented builds are "special" anyway so a fair slowdown is probably >>>> acceptable. I.e. this doesn't affect regular developer compilation times. >>>> As a baseline, maybe compare compile time of `-fprofile-instr-generate -O2` >>>> vs. `-O2`. If `-fprofile-instr-generate -O2` is 10% slower than the >>>> control, then that indicates that a 5% extra slowdown is probably >>>> reasonable for a substantial reduction in profiling overhead (which can >>>> result in a qualitative improvement to the actual usability of the >>>> instrumented program). >>>> >>>> -- Sean Silva >>>> >>>> >>>> >>>>> Is >>>>> the general approach a non-starter for anybody? >>>>> >>>>> I'd like to get some feedback and gauge interest before pursuing this >>>>> further. >>>>> Possible next steps include benchmarking instrumented versions of >>>>> clang and >>>>> swift on the relevant test suites, running performance tests from lnt, >>>>> running >>>>> compile-time tests, and measuring any code size differences. >>>>> >>>>> >>>>> thanks >>>>> vedant >>>>> >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> llvm-dev at lists.llvm.org >>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>>> >>>> >>>> >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> llvm-dev at lists.llvm.org >>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>> >>>> >>> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160311/1ba731c9/attachment.html>
Xinliang David Li via llvm-dev
2016-Mar-11 16:44 UTC
[llvm-dev] RFC: Pass to prune redundant profiling instrumentation
On Fri, Mar 11, 2016 at 12:20 AM, Sean Silva <chisophugis at gmail.com> wrote:> > On Thu, Mar 10, 2016 at 10:36 PM, Xinliang David Li <xinliangli at gmail.com> > wrote: > >> >> >> On Thu, Mar 10, 2016 at 10:13 PM, Sean Silva <chisophugis at gmail.com> >> wrote: >> >>> >>> >>> On Thu, Mar 10, 2016 at 9:42 PM, Xinliang David Li <xinliangli at gmail.com >>> > wrote: >>> >>>> >>>> >>>> On Thu, Mar 10, 2016 at 8:33 PM, Sean Silva via llvm-dev < >>>> llvm-dev at lists.llvm.org> wrote: >>>> >>>>> >>>>> >>>>> On Thu, Mar 10, 2016 at 7:21 PM, Vedant Kumar via llvm-dev < >>>>> llvm-dev at lists.llvm.org> wrote: >>>>> >>>>>> Hi, >>>>>> >>>>>> I'd like to add a new pass to LLVM which removes redundant profile >>>>>> counter >>>>>> updates. The goal is to speed up code coverage testing and profile >>>>>> generation >>>>>> for PGO. >>>>>> >>>>> >>>>> We may want to have a focused discussion about this goal, rather than >>>>> a particular suggestion. There are a lot of things we can do. Off the top >>>>> of my head, some are: >>>>> >>>>> 1. add some sort of alias annotation (such as an independent TBAA root >>>>> node) to all the counter increment memory instructions to tell the >>>>> optimizer they don't interfere with the usual loads and stores. >>>>> >>>>> 2. communicate to the optimizer that counters can be registerized. In >>>>> a loop like: >>>>> for (int i = 0; i < N; i++) { >>>>> if (foo()) >>>>> bar(); >>>>> else >>>>> baz(); >>>>> } >>>>> we perform O(N) counter increments (i.e. load, increment, store) last >>>>> I checked. However, if the counters are in registers, then we only perform >>>>> O(1) memory operations. This can dramatically reduce the pressure on the >>>>> CPU's load/store units and also relieve cross-core cache line ping-pong >>>>> when two cores are executing the same code. Note that the latter benefit is >>>>> attained even if we ultimately end up spilling the counters due to >>>>> increased register pressure. >>>>> >>>>> I actually don't know what is preventing the usual optimization >>>>> pipeline from getting 2 right. >>>>> >>>> >>>> Call Mod-ref. We need to teach the optimizer that the counter owned by >>>> the current function (if the function is proved to be non-recursive in some >>>> way) can not be modified by any other calls. >>>> >>> >>> I don't think that's a sufficient explanation. Consider the following >>> example: >>> >>> Sean:~/tmp % cat testprofile.cpp >>> int foo(int n) { >>> unsigned Ret = 42; >>> for (int i = 0; i < n; i++) { >>> if (i % 100) { >>> Ret += 789; >>> } else { >>> Ret *= (283 + Ret); >>> } >>> } >>> return Ret; >>> } >>> >>> Sean:~/tmp % ~/pg/release/bin/clang++ -o - -fprofile-instr-generate >>> testprofile.cpp -S -emit-llvm -O2 >foo.ll >>> Sean:~/tmp % ~/pg/release/bin/opt -view-cfg foo.ll >>> >>> >>> >> (resent) >> >> I saw your example has function call in the loop, thus the comment about >> Modref. >> >> For this example, the reason seems to that we don't yet do speculative >> PRE which usually requires profile information. Note that the update is >> conditionally done in a branch. Also note that the counter update of the >> block %8 is fully optimized away. >> > > (forgive my ignorance of compiler theory) > > Should we generally expect the optimizer to get this right at some point? > (i.e. is it a bug in the optimizer?) Or do you think that a special pass is > needed to get the desired effect for counters for normal use of > instrumentation? > It seems like inherently counter updates will happen only conditionally, > and so this kind of situation will be common. >This is a limitation of the compiler. It is not specific to counter variables -- same applies to user defined globals. There might be a bug tracking this.> > Counters seem like they have special semantics that allows more > flexibility. For example, the call mod-ref problem is actually not a > problem due to commutativity. We know that the callee will at most > increment the counter, so as long as the load,increment,store is not > interrupted by a call (which is easy to avoid) then we can freely move it > across calls. (actually, in theory a call into the profile lib could read > the counters, but in practice I expect this to not be an issue). > >Good observation, but it can cause problems with no access by call assumption -- for instance register promotion of a counter variable across call but it is actually updated by a call in the loop body. At the end of the loop, the update from the calls will be lost. David> -- Sean Silva > > >> >> David >> >> >> >>> >>> -- Sean Silva >>> >>> >>>> >>>> David >>>> >>>> >>>> >>>> >>>>> >>>>> >>>>>> >>>>>> I'm sending this email out to describe my approach, share some early >>>>>> results, >>>>>> and gather feedback. >>>>>> >>>>>> >>>>>> Problem Overview >>>>>> ===============>>>>>> >>>>>> A profile counter is redundant if it's incremented in exactly the >>>>>> same basic >>>>>> blocks as some other profile counter. Consider the following module: >>>>>> >>>>>> local void f1() { >>>>>> instrprof_increment(profc_f1); >>>>>> } >>>>>> >>>>>> void f2() { >>>>>> instrprof_increment(profc_f2); >>>>>> f1(); >>>>>> } >>>>>> >>>>>> Once the inliner runs and deletes f1, we're left with: >>>>>> >>>>>> void f2() { >>>>>> instrprof_increment(profc_f2); >>>>>> instrprof_increment(profc_f1); >>>>>> } >>>>>> >>>>>> Now we can say profc_f1 is redundant (or, an alias for profc_f2). >>>>>> >>>>>> I've noticed that frontend-based instrumentation can generate many >>>>>> redundant >>>>>> profile counters. This degrades performance and increases code size. >>>>>> We can >>>>>> address the problem by getting rid of redundant counter updates. The >>>>>> trick is >>>>>> to make sure we get back the same profiles. >>>>>> >>>>>> >>>>>> Proposed Solution >>>>>> ================>>>>>> >>>>>> I propose a pruning pass which takes the following steps: >>>>>> >>>>>> 1. Delete functions with local linkage and only one use, if that >>>>>> use is in >>>>>> a profile data record. >>>>>> >>>>>> These functions are left around by the inliner (it doesn't know >>>>>> that >>>>>> they're safe to delete). Deleting them reduces code size and >>>>>> simplifies >>>>>> subsequent analysis of profile counters. >>>>>> >>>>>> 2. Determine which profile counters are essential. >>>>>> >>>>>> 3. Erase all updates to redundant profile counters. >>>>>> >>>>>> 4. Emit the aliases into a new section in the binary. >>>>>> >>>>>> Aliases are represented as { Dst: i64*, Src: i64* } tuples. Some >>>>>> changes >>>>>> in compiler-rt are required to walk the alias section and fill >>>>>> in the >>>>>> correct execution counts at program exit time. >>>>>> >>>>>> This pass needs to be run after the inliner in order to be effective. >>>>>> >>>>>> The complexity of this pass is O(N*M), where N is the number of >>>>>> profile >>>>>> counters, and M is the average number of updates per counter. In >>>>>> practice it is >>>>>> a bit faster, since we can skip the analysis of counters which are >>>>>> discovered to >>>>>> be redundant early on in the process. >>>>>> >>>>> >>>>> I think a conceptually simpler design is something like: >>>>> >>>>> for each CFG edge: >>>>> record which FE counters have ended up associated with it >>>>> remove FE counters >>>>> run IR instrumentation pass >>>>> emit a side table mapping IR instr counters to FE counters (more >>>>> generally: how to reconstruct FE counters from the IR counters) >>>>> >>>>> The problem is simply reduced to the IR instrumentation pass. >>>>> >>>>> >>>>>> >>>>>> >>>>>> Early Results >>>>>> ============>>>>>> >>>>>> The pruning pass results in 25% speed improvement in the example >>>>>> program above >>>>>> (where f2 is called in a loop 10^8 times). >>>>>> >>>>>> Here is a slightly less contrived example: >>>>>> >>>>>> #include <vector> >>>>>> #include <algorithm> >>>>>> #include <cstdlib> >>>>>> >>>>>> static void escape(void *p) { >>>>>> asm volatile("" : : "g"(p) : "memory"); >>>>>> } >>>>>> >>>>>> int main(int argc, char **argv) { >>>>>> std::vector<int> V(atoi(argv[1])); >>>>>> escape(reinterpret_cast<void *>(V.data())); >>>>>> std::sort(V.begin(), V.end()); >>>>> >>>>> return V[0]; >>>>>> } >>>>>> >>>>>> I get the following results on my desktop (10^8 elements, 5 runs >>>>>> each): >>>>>> >>>>>> O3: 0.262s >>>>>> O3 + PGOInstr: 0.663s >>>>>> O3 + PGOInstr + Pruning: 0.606s (8.6% performance win, 672 >>>>>> aliases) >>>>>> O3 + CoverageInstr: 0.690s >>>>>> O3 + CoverageInstr + Pruning: 0.610s (11.6% performance win, 688 >>>>>> aliases) >>>>>> >>>>>> >>>>>> Next Steps? >>>>>> ==========>>>>>> >>>>>> Is the performance of instrumented code something we think we need to >>>>>> fix? >>>>>> >>>>> >>>>> With frontend instrumentation it definitely is. >>>>> >>>>> What's an acceptable compile-time overhead for running this pruning >>>>>> pass? >>>>> >>>>> >>>>> Instrumented builds are "special" anyway so a fair slowdown is >>>>> probably acceptable. I.e. this doesn't affect regular developer compilation >>>>> times. As a baseline, maybe compare compile time of >>>>> `-fprofile-instr-generate -O2` vs. `-O2`. If `-fprofile-instr-generate -O2` >>>>> is 10% slower than the control, then that indicates that a 5% extra >>>>> slowdown is probably reasonable for a substantial reduction in profiling >>>>> overhead (which can result in a qualitative improvement to the actual >>>>> usability of the instrumented program). >>>>> >>>>> -- Sean Silva >>>>> >>>>> >>>>> >>>>>> Is >>>>>> the general approach a non-starter for anybody? >>>>>> >>>>>> I'd like to get some feedback and gauge interest before pursuing this >>>>>> further. >>>>>> Possible next steps include benchmarking instrumented versions of >>>>>> clang and >>>>>> swift on the relevant test suites, running performance tests from >>>>>> lnt, running >>>>>> compile-time tests, and measuring any code size differences. >>>>>> >>>>>> >>>>>> thanks >>>>>> vedant >>>>>> >>>>>> _______________________________________________ >>>>>> LLVM Developers mailing list >>>>>> llvm-dev at lists.llvm.org >>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>>>> >>>>> >>>>> >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> llvm-dev at lists.llvm.org >>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>>> >>>>> >>>> >>> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160311/b594deac/attachment.html>