Re: FDO usability patch -- cfg and lineno checksum
Honza, any more comments? Thanks, David On Mon, Apr 25, 2011 at 9:35 AM, Xinliang David Li davi...@google.com wrote: Is the patch ok? Thanks, David On Fri, Apr 22, 2011 at 12:48 PM, Jan Hubicka hubi...@ucw.cz wrote: Please review the new patch which only implements cfg checksum. The auto version generation was introduced in 2002 before FDO support was added (so the old way never existed), so it might be better to make the change independent of this one. FDO support was there well before 2002, just with funny combination of flags. (-fprofile-arcs and -fbranch-probabilities) 2002 was about the time of GCOV format rewrite, but yes, lets change it independently I will look into the patch ASAP. Honza
Re: FDO usability patch -- cfg and lineno checksum
Please don't forget about changelogs.. Index: tree.c === --- tree.c(revision 172802) +++ tree.c(working copy) @@ -8513,14 +8513,12 @@ dump_tree_statistics (void) The crc bits was already reviewed, right? - else if (entry-checksum != checksum) + else if (entry-lineno_checksum != lineno_checksum +|| entry-cfg_checksum != cfg_checksum) { error (coverage mismatch for function %u while reading execution counters, fn_ident); - error (checksum is %x instead of %x, entry-checksum, checksum); + error (checksum is (%x,%x) instead of (%x,%x), + entry-lineno_checksum, entry-cfg_checksum, + lineno_checksum, cfg_checksum); Can't we give more informative message whether code changes or it seems to be optimization options disprepancy? +unsigned +coverage_compute_cfg_checksum (void) +{ + basic_block bb; + unsigned chksum = n_basic_blocks; + + FOR_EACH_BB (bb) +{ + edge e; + edge_iterator ei; Perhaps also chksum = crc32_byte (chksum, bb-index) for cases where destination stays the same, but source of edge moves (i.e. with forwarder blocks) Patch is OK, thanks Honza
Re: FDO usability patch -- cfg and lineno checksum
- else if (entry-checksum != checksum) + else if (entry-lineno_checksum != lineno_checksum + || entry-cfg_checksum != cfg_checksum) { error (coverage mismatch for function %u while reading execution counters, fn_ident); - error (checksum is %x instead of %x, entry-checksum, checksum); + error (checksum is (%x,%x) instead of (%x,%x), + entry-lineno_checksum, entry-cfg_checksum, + lineno_checksum, cfg_checksum); Can't we give more informative message whether code changes or it seems to be optimization options disprepancy? Good idea -- but to change the warning not the error here. For the warning (which is promoted to error by default) currently it is: error: coverage mismatch for function while reading counter yyy. note: control flow checksum is aaa instead of bbb Could be: error: function xxx's control flow does match its profile data (counter yyy). note: use -Wno-error=coverage-mismatch to tolerate the mismatch but performance may drop if the function is hot. Well, I had more in mind giving diffent message for lineno checksum difference than cfg checksum. But I agree that we probably don't want to output checksum numbers, those are useless even for debugging. Probably could follow same warning/error rules as the main loading routine whatever you converged to. Honza
Re: FDO usability patch -- cfg and lineno checksum
On Wed, Apr 27, 2011 at 10:03 AM, Jan Hubicka hubi...@ucw.cz wrote: - else if (entry-checksum != checksum) + else if (entry-lineno_checksum != lineno_checksum + || entry-cfg_checksum != cfg_checksum) { error (coverage mismatch for function %u while reading execution counters, fn_ident); - error (checksum is %x instead of %x, entry-checksum, checksum); + error (checksum is (%x,%x) instead of (%x,%x), + entry-lineno_checksum, entry-cfg_checksum, + lineno_checksum, cfg_checksum); Can't we give more informative message whether code changes or it seems to be optimization options disprepancy? Good idea -- but to change the warning not the error here. For the warning (which is promoted to error by default) currently it is: error: coverage mismatch for function while reading counter yyy. note: control flow checksum is aaa instead of bbb Could be: error: function xxx's control flow does match its profile data (counter yyy). note: use -Wno-error=coverage-mismatch to tolerate the mismatch but performance may drop if the function is hot. Well, I had more in mind giving diffent message for lineno checksum difference than cfg checksum. But I agree that we probably don't want to output checksum numbers, those are useless even for debugging. Probably could follow same warning/error rules as the main loading routine whatever you converged to. Sure. Thanks, David Honza
Re: FDO usability patch -- cfg and lineno checksum
Is the patch ok? Thanks, David On Fri, Apr 22, 2011 at 12:48 PM, Jan Hubicka hubi...@ucw.cz wrote: Please review the new patch which only implements cfg checksum. The auto version generation was introduced in 2002 before FDO support was added (so the old way never existed), so it might be better to make the change independent of this one. FDO support was there well before 2002, just with funny combination of flags. (-fprofile-arcs and -fbranch-probabilities) 2002 was about the time of GCOV format rewrite, but yes, lets change it independently I will look into the patch ASAP. Honza
Re: FDO usability patch -- cfg and lineno checksum
Please review the new patch which only implements cfg checksum. The auto version generation was introduced in 2002 before FDO support was added (so the old way never existed), so it might be better to make the change independent of this one. Thanks, David On Thu, Apr 21, 2011 at 2:15 PM, Xinliang David Li davi...@google.com wrote: On Thu, Apr 21, 2011 at 1:43 PM, Jan Hubicka hubi...@ucw.cz wrote: I don't really follow the logic here. buffer is allocated to be size of block+4 and it is expected that gcov_write_words is not executed on size greater than 4. Since gcov_write_string now seems to be expected to handle strings of bigger size, I think you acually need to make write_string to write in chunks when you reach block boundary? gcov_write_words is used to reserve words*4 bytes in buffer for data write later. The the old logic is wrong -- if 'words' is large enough, it will lead to out of bound access. The old logic assumes that writes are not bigger than 4 and it is documented somewhere in gcov-io.h if I remember right (it is not my code). I however still think your change won't solve it in general, since you might want to write more than block size, so you need write_string update. Right, 'words; can be large for string. -- the memcpy code following does not look right either. What gets into libgcov is very problematic busyness for embedded targets, where you really want libgcov to be small. Why do you need to store strings now? It is needed to store the assembler name for functions. It allows lookup of the profile data using assembler name as key instead of using function ids. For gcc, the total size of gcda files is about 59k bytes without storing the names, and about 65k with names -- about 10% increase. For eon, the size changes from 27k to 35k bytes. I can split the patches into two parts -- one with cfg checksum and one with the name string. Well, lets make it incremental change then at time we will have use for it once we agree it makes sense. Ok. So you want to do symbol name resolving at GCOV runtime? For now, it is just passed through as a tag for the profile data for each function. I duno about embedded targets, 10% increase is not too bad, but I don't know. libgcov has quite inflexible coding style just to be small and fit there, so I don't know what are the space constraints that are considered acceptable in that world. I will delay the string writing patch for now. We also need to bump gcov version, right? Yes -- but the version is currently derived from gcc version number and phase number --- this is wrong -- different version of gcc may have compatible coverage data format. Any suggestions to change this? --- probably just hard code the GCOV_VERSION string? Hmm, I am pretty sure we used to have minor/major numbering on the file format. Perhaps it went away with Nathan's changes. For -fprofile-use the compatibility across versions is pointless, Right, but also equally unnecessary to force version mismatch between compiler releases. at least now, but for gcov utility it makes sense. Yes. So I would go for explicit versioning again. Will dig through the revision history .. David Honza Index: tree.c === --- tree.c (revision 172802) +++ tree.c (working copy) @@ -8513,14 +8513,12 @@ dump_tree_statistics (void) #define FILE_FUNCTION_FORMAT _GLOBAL__%s_%s -/* Generate a crc32 of a string. */ +/* Generate a crc32 of a byte. */ unsigned -crc32_string (unsigned chksum, const char *string) +crc32_byte (unsigned chksum, char byte) { - do -{ - unsigned value = *string 24; + unsigned value = (unsigned) byte 24; unsigned ix; for (ix = 8; ix--; value = 1) @@ -8531,6 +8529,18 @@ crc32_string (unsigned chksum, const cha chksum = 1; chksum ^= feedback; } + return chksum; +} + + +/* Generate a crc32 of a string. */ + +unsigned +crc32_string (unsigned chksum, const char *string) +{ + do +{ + chksum = crc32_byte (chksum, *string); } while (*string++); return chksum; @@ -8554,8 +8564,10 @@ clean_symbol_name (char *p) *p = '_'; } -/* Generate a name for a special-purpose function function. +/* Generate a name for a special-purpose function. The generated name may need to be unique across the whole link. + Changes to this function may also require corresponding changes to + xstrdup_mask_random. TYPE is some string to identify the purpose of this function to the linker or collect2; it must start with an uppercase letter, one of: Index: tree.h === --- tree.h (revision 172802) +++ tree.h (working copy) @@ -4998,6 +4998,7 @@ inlined_function_outer_scope_p (const_tr /* In tree.c */ extern unsigned crc32_string (unsigned, const char *); +extern unsigned crc32_byte
Re: FDO usability patch -- cfg and lineno checksum
Please review the new patch which only implements cfg checksum. The auto version generation was introduced in 2002 before FDO support was added (so the old way never existed), so it might be better to make the change independent of this one. FDO support was there well before 2002, just with funny combination of flags. (-fprofile-arcs and -fbranch-probabilities) 2002 was about the time of GCOV format rewrite, but yes, lets change it independently I will look into the patch ASAP. Honza
Re: FDO usability patch -- cfg and lineno checksum
On Tue, Apr 19, 2011 at 15:47, Xinliang David Li davi...@google.com wrote: The attached is the revised patch with a warning suggested for cases when CFG matches, but source locations change. Ok for trunk? The tree.c changes are OK. Diego.
Re: FDO usability patch -- cfg and lineno checksum
I don't really follow the logic here. buffer is allocated to be size of block+4 and it is expected that gcov_write_words is not executed on size greater than 4. Since gcov_write_string now seems to be expected to handle strings of bigger size, I think you acually need to make write_string to write in chunks when you reach block boundary? gcov_write_words is used to reserve words*4 bytes in buffer for data write later. The the old logic is wrong -- if 'words' is large enough, it will lead to out of bound access. The old logic assumes that writes are not bigger than 4 and it is documented somewhere in gcov-io.h if I remember right (it is not my code). I however still think your change won't solve it in general, since you might want to write more than block size, so you need write_string update. What gets into libgcov is very problematic busyness for embedded targets, where you really want libgcov to be small. Why do you need to store strings now? It is needed to store the assembler name for functions. It allows lookup of the profile data using assembler name as key instead of using function ids. For gcc, the total size of gcda files is about 59k bytes without storing the names, and about 65k with names -- about 10% increase. For eon, the size changes from 27k to 35k bytes. I can split the patches into two parts -- one with cfg checksum and one with the name string. Well, lets make it incremental change then at time we will have use for it once we agree it makes sense. So you want to do symbol name resolving at GCOV runtime? I duno about embedded targets, 10% increase is not too bad, but I don't know. libgcov has quite inflexible coding style just to be small and fit there, so I don't know what are the space constraints that are considered acceptable in that world. We also need to bump gcov version, right? Yes -- but the version is currently derived from gcc version number and phase number --- this is wrong -- different version of gcc may have compatible coverage data format. Any suggestions to change this? --- probably just hard code the GCOV_VERSION string? Hmm, I am pretty sure we used to have minor/major numbering on the file format. Perhaps it went away with Nathan's changes. For -fprofile-use the compatibility across versions is pointless, at least now, but for gcov utility it makes sense. So I would go for explicit versioning again. Honza
Re: FDO usability patch -- cfg and lineno checksum
On Thu, Apr 21, 2011 at 1:43 PM, Jan Hubicka hubi...@ucw.cz wrote: I don't really follow the logic here. buffer is allocated to be size of block+4 and it is expected that gcov_write_words is not executed on size greater than 4. Since gcov_write_string now seems to be expected to handle strings of bigger size, I think you acually need to make write_string to write in chunks when you reach block boundary? gcov_write_words is used to reserve words*4 bytes in buffer for data write later. The the old logic is wrong -- if 'words' is large enough, it will lead to out of bound access. The old logic assumes that writes are not bigger than 4 and it is documented somewhere in gcov-io.h if I remember right (it is not my code). I however still think your change won't solve it in general, since you might want to write more than block size, so you need write_string update. Right, 'words; can be large for string. -- the memcpy code following does not look right either. What gets into libgcov is very problematic busyness for embedded targets, where you really want libgcov to be small. Why do you need to store strings now? It is needed to store the assembler name for functions. It allows lookup of the profile data using assembler name as key instead of using function ids. For gcc, the total size of gcda files is about 59k bytes without storing the names, and about 65k with names -- about 10% increase. For eon, the size changes from 27k to 35k bytes. I can split the patches into two parts -- one with cfg checksum and one with the name string. Well, lets make it incremental change then at time we will have use for it once we agree it makes sense. Ok. So you want to do symbol name resolving at GCOV runtime? For now, it is just passed through as a tag for the profile data for each function. I duno about embedded targets, 10% increase is not too bad, but I don't know. libgcov has quite inflexible coding style just to be small and fit there, so I don't know what are the space constraints that are considered acceptable in that world. I will delay the string writing patch for now. We also need to bump gcov version, right? Yes -- but the version is currently derived from gcc version number and phase number --- this is wrong -- different version of gcc may have compatible coverage data format. Any suggestions to change this? --- probably just hard code the GCOV_VERSION string? Hmm, I am pretty sure we used to have minor/major numbering on the file format. Perhaps it went away with Nathan's changes. For -fprofile-use the compatibility across versions is pointless, Right, but also equally unnecessary to force version mismatch between compiler releases. at least now, but for gcov utility it makes sense. Yes. So I would go for explicit versioning again. Will dig through the revision history .. David Honza
Re: FDO usability patch -- cfg and lineno checksum
On Tue, Apr 19, 2011 at 3:20 PM, Jan Hubicka hubi...@ucw.cz wrote: I can not review tree.c changes. I would probably suggest making crc_byte inline. Diego, can you review this change? This is just a simple refactoring. +#if IN_LIBGCOV + +/* These functions are guarded by #if to avoid compile time warning. */ + +/* Return the number of words STRING would need including the length + field in the output stream itself. This should be identical to + alloc calculation in gcov_write_string(). */ Hmm, probably better to make gcov_write_string to use gcov_string_length then. yes. @@ -238,13 +265,15 @@ gcov_write_words (unsigned words) gcc_assert (gcov_var.mode 0); #if IN_LIBGCOV - if (gcov_var.offset = GCOV_BLOCK_SIZE) + if (gcov_var.offset + words = GCOV_BLOCK_SIZE) { - gcov_write_block (GCOV_BLOCK_SIZE); + gcov_write_block (MIN (gcov_var.offset, GCOV_BLOCK_SIZE)); if (gcov_var.offset) { - gcc_assert (gcov_var.offset == 1); - memcpy (gcov_var.buffer, gcov_var.buffer + GCOV_BLOCK_SIZE, 4); + gcc_assert (gcov_var.offset GCOV_BLOCK_SIZE); + memcpy (gcov_var.buffer, + gcov_var.buffer + GCOV_BLOCK_SIZE, + gcov_var.offset 2); I don't really follow the logic here. buffer is allocated to be size of block+4 and it is expected that gcov_write_words is not executed on size greater than 4. Since gcov_write_string now seems to be expected to handle strings of bigger size, I think you acually need to make write_string to write in chunks when you reach block boundary? gcov_write_words is used to reserve words*4 bytes in buffer for data write later. The the old logic is wrong -- if 'words' is large enough, it will lead to out of bound access. As soon as you decide to not write out in the GCOV_BLOCK_SIZE chunks, the MIN computation above seems unnecesary (and bogus, since we won't let gcov_var.offset to grow past GCOV_BLOCK_SIZE. Yes, using gcov_var.offset should be good enough. What gets into libgcov is very problematic busyness for embedded targets, where you really want libgcov to be small. Why do you need to store strings now? It is needed to store the assembler name for functions. It allows lookup of the profile data using assembler name as key instead of using function ids. For gcc, the total size of gcda files is about 59k bytes without storing the names, and about 65k with names -- about 10% increase. For eon, the size changes from 27k to 35k bytes. I can split the patches into two parts -- one with cfg checksum and one with the name string. Index: gcov-io.h === --- gcov-io.h (revision 172693) +++ gcov-io.h (working copy) @@ -101,9 +101,10 @@ see the files COPYING3 and COPYING.RUNTI The basic block graph file contains the following records note: unit function-graph* - unit: header int32:checksum string:source + unit: header int32:checksum int32: string:source function-graph: announce_function basic_blocks {arcs | lines}* - announce_function: header int32:ident int32:checksum + announce_function: header int32:ident + int32:lineno_checksum int32:cfg_checksum string:name string:source int32:lineno basic_block: header int32:flags* arcs: header int32:block_no arc* @@ -132,7 +133,9 @@ see the files COPYING3 and COPYING.RUNTI data: {unit function-data* summary:object summary:program*}* unit: header int32:checksum function-data: announce_function arc_counts - announce_function: header int32:ident int32:checksum + announce_function: header int32:ident + int32:lineno_checksum int32:cfg_checksum + string:name arc_counts: header int64:count* summary: int32:checksum {count-summary}GCOV_COUNTERS count-summary: int32:num int32:runs int64:sum We also need to bump gcov version, right? Yes -- but the version is currently derived from gcc version number and phase number --- this is wrong -- different version of gcc may have compatible coverage data format. Any suggestions to change this? --- probably just hard code the GCOV_VERSION string? @@ -411,11 +417,20 @@ struct gcov_summary /* Information about a single function. This uses the trailing array idiom. The number of counters is determined from the counter_mask in gcov_info. We hold an array of function info, so have to - explicitly calculate the correct array stride. */ + explicitly calculate the correct array stride. + + ident is no longer used in hash computation. Additionally, + name is used in hash computation. This makes the profile data + not compatible across function name changes. + Also, the function pointer is stored for later use for indirect + function call name resolution. Hmm, your patch is not adding indirect function call
Re: FDO usability patch -- cfg and lineno checksum
The attached is the revised patch with a warning suggested for cases when CFG matches, but source locations change. Ok for trunk? thanks, David On Sun, Apr 17, 2011 at 8:36 AM, Jan Hubicka hubi...@ucw.cz wrote: Hi, in current FDO implementation, the source file version used in profile-generate needs to strictly match the version used in profile-use -- simple formating changes will invalidate the profile data (use of it will lead to compiler error or ICE). There are two main problems that lead to the weakness: 1) the function checksum is computed based on line number and number of basic blocks -- this means any line number change will invalidate the profile data. In fact, line number should play very minimal role in profile matching decision. Another problem is that number of basic blocks is also not a good indicator whether CFG matches or not. 2) cgraph's pid is used as the key to find the matching profile data for a function. If there is any new function added, or if the order of the functions changes, the profile data is invalidated. The attached is a patch from google that improves this. 1) function checksum is split into two parts: lineno checksum and cfg checksum 2) function assembler name is used in profile hashing. Well, the overall idea was to make profile intolerant to pretty much any source level change, since you never know if even when the CFG shape match, the actual probabiliies did not changed. I however see that during development it is not bad to make compiler grok the profile as long as it seems consistent. I did not looked in detail into the implementation yet, but it seems sane at first glance. However what about issuing a warning when line number information change telling user that profile might no longer be accurate and that he may want to remove it and train again? Honza Index: tree.c === --- tree.c (revision 172693) +++ tree.c (working copy) @@ -8508,14 +8508,12 @@ dump_tree_statistics (void) #define FILE_FUNCTION_FORMAT _GLOBAL__%s_%s -/* Generate a crc32 of a string. */ +/* Generate a crc32 of a byte. */ unsigned -crc32_string (unsigned chksum, const char *string) +crc32_byte (unsigned chksum, char byte) { - do -{ - unsigned value = *string 24; + unsigned value = (unsigned) byte 24; unsigned ix; for (ix = 8; ix--; value = 1) @@ -8526,6 +8524,18 @@ crc32_string (unsigned chksum, const cha chksum = 1; chksum ^= feedback; } + return chksum; +} + + +/* Generate a crc32 of a string. */ + +unsigned +crc32_string (unsigned chksum, const char *string) +{ + do +{ + chksum = crc32_byte (chksum, *string); } while (*string++); return chksum; @@ -8549,8 +8559,10 @@ clean_symbol_name (char *p) *p = '_'; } -/* Generate a name for a special-purpose function function. +/* Generate a name for a special-purpose function. The generated name may need to be unique across the whole link. + Changes to this function may also require corresponding changes to + xstrdup_mask_random. TYPE is some string to identify the purpose of this function to the linker or collect2; it must start with an uppercase letter, one of: Index: tree.h === --- tree.h (revision 172693) +++ tree.h (working copy) @@ -4998,6 +4998,7 @@ inlined_function_outer_scope_p (const_tr /* In tree.c */ extern unsigned crc32_string (unsigned, const char *); +extern unsigned crc32_byte (unsigned, char); extern void clean_symbol_name (char *); extern tree get_file_function_name (const char *); extern tree get_callee_fndecl (const_tree); Index: gcov.c === --- gcov.c (revision 172693) +++ gcov.c (working copy) @@ -54,6 +54,13 @@ along with Gcov; see the file COPYING3. some places we make use of the knowledge of how profile.c works to select particular algorithms here. */ +/* The code validates that the profile information read in corresponds + to the code currently being compiled. Rather than checking for + identical files, the code below computes a checksum on the CFG + (based on the order of basic blocks and the arcs in the CFG). If + the CFG checksum in the gcda file match the CFG checksum for the + code currently being compiled, the profile data will be used. */ + /* This is the size of the buffer used to read in source file lines. */ #define STRING_SIZE 200 @@ -161,7 +168,8 @@ typedef struct function_info /* Name of function. */ char *name; unsigned ident; - unsigned checksum; + unsigned lineno_checksum; + unsigned cfg_checksum; /* Array of basic blocks. */ block_t *blocks; @@ -809,12 +817,14 @@ read_graph_file (void) if (tag == GCOV_TAG_FUNCTION) { char *function_name; - unsigned ident, checksum, lineno; + unsigned ident, lineno;
Re: FDO usability patch -- cfg and lineno checksum
I can not review tree.c changes. I would probably suggest making crc_byte inline. +#if IN_LIBGCOV + +/* These functions are guarded by #if to avoid compile time warning. */ + +/* Return the number of words STRING would need including the length + field in the output stream itself. This should be identical to + alloc calculation in gcov_write_string(). */ Hmm, probably better to make gcov_write_string to use gcov_string_length then. @@ -238,13 +265,15 @@ gcov_write_words (unsigned words) gcc_assert (gcov_var.mode 0); #if IN_LIBGCOV - if (gcov_var.offset = GCOV_BLOCK_SIZE) + if (gcov_var.offset + words = GCOV_BLOCK_SIZE) { - gcov_write_block (GCOV_BLOCK_SIZE); + gcov_write_block (MIN (gcov_var.offset, GCOV_BLOCK_SIZE)); if (gcov_var.offset) { - gcc_assert (gcov_var.offset == 1); - memcpy (gcov_var.buffer, gcov_var.buffer + GCOV_BLOCK_SIZE, 4); + gcc_assert (gcov_var.offset GCOV_BLOCK_SIZE); + memcpy (gcov_var.buffer, + gcov_var.buffer + GCOV_BLOCK_SIZE, + gcov_var.offset 2); I don't really follow the logic here. buffer is allocated to be size of block+4 and it is expected that gcov_write_words is not executed on size greater than 4. Since gcov_write_string now seems to be expected to handle strings of bigger size, I think you acually need to make write_string to write in chunks when you reach block boundary? As soon as you decide to not write out in the GCOV_BLOCK_SIZE chunks, the MIN computation above seems unnecesary (and bogus, since we won't let gcov_var.offset to grow past GCOV_BLOCK_SIZE. What gets into libgcov is very problematic busyness for embedded targets, where you really want libgcov to be small. Why do you need to store strings now? Index: gcov-io.h === --- gcov-io.h (revision 172693) +++ gcov-io.h (working copy) @@ -101,9 +101,10 @@ see the files COPYING3 and COPYING.RUNTI The basic block graph file contains the following records note: unit function-graph* - unit: header int32:checksum string:source + unit: header int32:checksum int32: string:source function-graph: announce_function basic_blocks {arcs | lines}* - announce_function: header int32:ident int32:checksum + announce_function: header int32:ident + int32:lineno_checksum int32:cfg_checksum string:name string:source int32:lineno basic_block: header int32:flags* arcs: header int32:block_no arc* @@ -132,7 +133,9 @@ see the files COPYING3 and COPYING.RUNTI data: {unit function-data* summary:object summary:program*}* unit: header int32:checksum function-data: announce_function arc_counts - announce_function: header int32:ident int32:checksum + announce_function: header int32:ident + int32:lineno_checksum int32:cfg_checksum + string:name arc_counts: header int64:count* summary: int32:checksum {count-summary}GCOV_COUNTERS count-summary: int32:num int32:runs int64:sum We also need to bump gcov version, right? @@ -411,11 +417,20 @@ struct gcov_summary /* Information about a single function. This uses the trailing array idiom. The number of counters is determined from the counter_mask in gcov_info. We hold an array of function info, so have to - explicitly calculate the correct array stride. */ + explicitly calculate the correct array stride. + + ident is no longer used in hash computation. Additionally, + name is used in hash computation. This makes the profile data + not compatible across function name changes. + Also, the function pointer is stored for later use for indirect + function call name resolution. Hmm, your patch is not adding indirect function call name resolution, so independent change? Index: profile.c === --- profile.c (revision 172693) +++ profile.c (working copy) @@ -102,13 +102,6 @@ static int total_num_branches; /* Forward declarations. */ static void find_spanning_tree (struct edge_list *); -static unsigned instrument_edges (struct edge_list *); -static void instrument_values (histogram_values); -static void compute_branch_probabilities (void); -static void compute_value_histograms (histogram_values); -static gcov_type * get_exec_counts (void); -static basic_block find_group (basic_block); -static void union_groups (basic_block, basic_block); This is also independent and OK for mainline. /* Add edge instrumentation code to the entire insn chain. @@ -233,10 +226,12 @@ instrument_values (histogram_values valu } -/* Computes hybrid profile for all matching entries in da_file. */ +/* Computes hybrid profile for all matching entries in da_file. + + CFG_CHECKSUM is the precomputed checksum for
Re: FDO usability patch -- cfg and lineno checksum
On Sun, Apr 17, 2011 at 8:36 AM, Jan Hubicka hubi...@ucw.cz wrote: Hi, in current FDO implementation, the source file version used in profile-generate needs to strictly match the version used in profile-use -- simple formating changes will invalidate the profile data (use of it will lead to compiler error or ICE). There are two main problems that lead to the weakness: 1) the function checksum is computed based on line number and number of basic blocks -- this means any line number change will invalidate the profile data. In fact, line number should play very minimal role in profile matching decision. Another problem is that number of basic blocks is also not a good indicator whether CFG matches or not. 2) cgraph's pid is used as the key to find the matching profile data for a function. If there is any new function added, or if the order of the functions changes, the profile data is invalidated. The attached is a patch from google that improves this. 1) function checksum is split into two parts: lineno checksum and cfg checksum 2) function assembler name is used in profile hashing. Well, the overall idea was to make profile intolerant to pretty much any source level change, since you never know if even when the CFG shape match, the actual probabiliies did not changed. I however see that during development it is not bad to make compiler grok the profile as long as it seems consistent. Make FDO usable in development cycle is one usage of the better matching tolerance. There is another bigger use case which we are looking at -- using sample profiling data from production binary collected by the profile server to guide optimization. Of course there will be lots of other problems (e.g., compiler optimizations can drastically change control flow, etc.) before this can become reality. I did not looked in detail into the implementation yet, but it seems sane at first glance. However what about issuing a warning when line number information change telling user that profile might no longer be accurate and that he may want to remove it and train again? Yes, this may be good to have. Thanks, David Honza
Re: FDO usability patch -- cfg and lineno checksum
Resent in plain text mode .. David On Fri, Apr 15, 2011 at 9:28 AM, Xinliang David Li davi...@google.com wrote: Honza, do you have a chance to take a look at it? Thanks, David On Wed, Apr 13, 2011 at 3:25 PM, Xinliang David Li davi...@google.com wrote: Hi, in current FDO implementation, the source file version used in profile-generate needs to strictly match the version used in profile-use -- simple formating changes will invalidate the profile data (use of it will lead to compiler error or ICE). There are two main problems that lead to the weakness: 1) the function checksum is computed based on line number and number of basic blocks -- this means any line number change will invalidate the profile data. In fact, line number should play very minimal role in profile matching decision. Another problem is that number of basic blocks is also not a good indicator whether CFG matches or not. 2) cgraph's pid is used as the key to find the matching profile data for a function. If there is any new function added, or if the order of the functions changes, the profile data is invalidated. The attached is a patch from google that improves this. 1) function checksum is split into two parts: lineno checksum and cfg checksum 2) function assembler name is used in profile hashing. Bootstrapped and regression tested on x86_64/linux. Ok for trunk? Thanks, David 2011-04-13 Xinliang David Li davi...@google.com * tree.c (crc32_byte): New function. * tree.h (crc32_byte): New function. * gcov.c (function_info): Add new fields. (read_graph_file): Handle new fields. (read_count_file): Handle name. * gcov-io.c (gcov_string_length): New function. (gcov_write_words): Bug fix. (gcov_read_words): Bug fix. * gcov-io.h: New interfaces. * profile.c (get_exec_counts): New parameter. (compute_branch_probablilities): New parameter. (compute_value_histogram): New parameter. (branch_prob): Pass cfg_checksum. * coverage.c (get_const_string_type): New function. (hash_counts_entry_hash): Use string hash. (hash_counts_entry_eq): Use string compare. (htab_counts_entry_del): Delete name. (read_count_file): Add handling of cfg checksum. (get_coverage_counts): New parameter. (xstrdup_mask_random): New function. (coverage_compute_lineno_checksum): New function. (coverage_compute_cfg_checksum): New function. (coverage_begin_output): New parameter. (coverage_end_function): New parameter. (build_fn_info_type): Build new fields. (build_fn_info_value): Build new field values. * coverage.h: Interface changes. * libgcov.c (gcov_exit): Dump new fields. * gcov_dump.c (tag_function): Print new fields.
FDO usability patch -- cfg and lineno checksum
Hi, in current FDO implementation, the source file version used in profile-generate needs to strictly match the version used in profile-use -- simple formating changes will invalidate the profile data (use of it will lead to compiler error or ICE). There are two main problems that lead to the weakness: 1) the function checksum is computed based on line number and number of basic blocks -- this means any line number change will invalidate the profile data. In fact, line number should play very minimal role in profile matching decision. Another problem is that number of basic blocks is also not a good indicator whether CFG matches or not. 2) cgraph's pid is used as the key to find the matching profile data for a function. If there is any new function added, or if the order of the functions changes, the profile data is invalidated. The attached is a patch from google that improves this. 1) function checksum is split into two parts: lineno checksum and cfg checksum 2) function assembler name is used in profile hashing. Bootstrapped and regression tested on x86_64/linux. Ok for trunk? Thanks, David 2011-04-13 Xinliang David Li davi...@google.com * tree.c (crc32_byte): New function. * tree.h (crc32_byte): New function. * gcov.c (function_info): Add new fields. (read_graph_file): Handle new fields. (read_count_file): Handle name. * gcov-io.c (gcov_string_length): New function. (gcov_write_words): Bug fix. (gcov_read_words): Bug fix. * gcov-io.h: New interfaces. * profile.c (get_exec_counts): New parameter. (compute_branch_probablilities): New parameter. (compute_value_histogram): New parameter. (branch_prob): Pass cfg_checksum. * coverage.c (get_const_string_type): New function. (hash_counts_entry_hash): Use string hash. (hash_counts_entry_eq): Use string compare. (htab_counts_entry_del): Delete name. (read_count_file): Add handling of cfg checksum. (get_coverage_counts): New parameter. (xstrdup_mask_random): New function. (coverage_compute_lineno_checksum): New function. (coverage_compute_cfg_checksum): New function. (coverage_begin_output): New parameter. (coverage_end_function): New parameter. (build_fn_info_type): Build new fields. (build_fn_info_value): Build new field values. * coverage.h: Interface changes. * libgcov.c (gcov_exit): Dump new fields. * gcov_dump.c (tag_function): Print new fields. Index: tree.c === --- tree.c (revision 172385) +++ tree.c (working copy) @@ -8508,14 +8508,12 @@ dump_tree_statistics (void) #define FILE_FUNCTION_FORMAT _GLOBAL__%s_%s -/* Generate a crc32 of a string. */ +/* Generate a crc32 of a byte. */ unsigned -crc32_string (unsigned chksum, const char *string) +crc32_byte (unsigned chksum, char byte) { - do -{ - unsigned value = *string 24; + unsigned value = (unsigned) byte 24; unsigned ix; for (ix = 8; ix--; value = 1) @@ -8526,6 +8524,18 @@ crc32_string (unsigned chksum, const cha chksum = 1; chksum ^= feedback; } + return chksum; +} + + +/* Generate a crc32 of a string. */ + +unsigned +crc32_string (unsigned chksum, const char *string) +{ + do +{ + chksum = crc32_byte (chksum, *string); } while (*string++); return chksum; @@ -8549,8 +8559,10 @@ clean_symbol_name (char *p) *p = '_'; } -/* Generate a name for a special-purpose function function. +/* Generate a name for a special-purpose function. The generated name may need to be unique across the whole link. + Changes to this function may also require corresponding changes to + xstrdup_mask_random. TYPE is some string to identify the purpose of this function to the linker or collect2; it must start with an uppercase letter, one of: Index: tree.h === --- tree.h (revision 172385) +++ tree.h (working copy) @@ -4997,6 +4997,7 @@ inlined_function_outer_scope_p (const_tr /* In tree.c */ extern unsigned crc32_string (unsigned, const char *); +extern unsigned crc32_byte (unsigned, char); extern void clean_symbol_name (char *); extern tree get_file_function_name (const char *); extern tree get_callee_fndecl (const_tree); Index: gcov.c === --- gcov.c (revision 172385) +++ gcov.c (working copy) @@ -54,6 +54,13 @@ along with Gcov; see the file COPYING3. some places we make use of the knowledge of how profile.c works to select particular algorithms here. */ +/* The code validates that the profile information read in corresponds + to the code currently being compiled. Rather than checking for + identical files, the code below computes a checksum on the CFG + (based on the
Re: FDO usability patch -- cfg and lineno checksum
This was contributed by: 2011-04-13 Neil Vachharajani nvach...@gmail.com On Wed, Apr 13, 2011 at 3:25 PM, Xinliang David Li davi...@google.com wrote: Hi, in current FDO implementation, the source file version used in profile-generate needs to strictly match the version used in profile-use -- simple formating changes will invalidate the profile data (use of it will lead to compiler error or ICE). There are two main problems that lead to the weakness: 1) the function checksum is computed based on line number and number of basic blocks -- this means any line number change will invalidate the profile data. In fact, line number should play very minimal role in profile matching decision. Another problem is that number of basic blocks is also not a good indicator whether CFG matches or not. 2) cgraph's pid is used as the key to find the matching profile data for a function. If there is any new function added, or if the order of the functions changes, the profile data is invalidated. The attached is a patch from google that improves this. 1) function checksum is split into two parts: lineno checksum and cfg checksum 2) function assembler name is used in profile hashing. Bootstrapped and regression tested on x86_64/linux. Ok for trunk? Thanks, David 2011-04-13 Xinliang David Li davi...@google.com * tree.c (crc32_byte): New function. * tree.h (crc32_byte): New function. * gcov.c (function_info): Add new fields. (read_graph_file): Handle new fields. (read_count_file): Handle name. * gcov-io.c (gcov_string_length): New function. (gcov_write_words): Bug fix. (gcov_read_words): Bug fix. * gcov-io.h: New interfaces. * profile.c (get_exec_counts): New parameter. (compute_branch_probablilities): New parameter. (compute_value_histogram): New parameter. (branch_prob): Pass cfg_checksum. * coverage.c (get_const_string_type): New function. (hash_counts_entry_hash): Use string hash. (hash_counts_entry_eq): Use string compare. (htab_counts_entry_del): Delete name. (read_count_file): Add handling of cfg checksum. (get_coverage_counts): New parameter. (xstrdup_mask_random): New function. (coverage_compute_lineno_checksum): New function. (coverage_compute_cfg_checksum): New function. (coverage_begin_output): New parameter. (coverage_end_function): New parameter. (build_fn_info_type): Build new fields. (build_fn_info_value): Build new field values. * coverage.h: Interface changes. * libgcov.c (gcov_exit): Dump new fields. * gcov_dump.c (tag_function): Print new fields.