This is the mail archive of the
`gcc@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Richard Biener <rguenther at suse dot de>*To*: Prathamesh Kulkarni <prathamesh dot kulkarni at linaro dot org>*Cc*: "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>, Ramana Radhakrishnan <ramana dot radhakrishnan at arm dot com>, Jan Hubicka <hubicka at ucw dot cz>*Date*: Thu, 14 Apr 2016 14:16:04 +0200 (CEST)*Subject*: Re: How to check if two symbols are from same source unit during WPA ?*Authentication-results*: sourceware.org; auth=none*References*: <CAAgBjMm++Cf+iKD+BBgXO7Bk2DZwPMra9+VXrf6pateujN4MGg at mail dot gmail dot com> <36255F7F-1676-459B-B95F-A812B26214FF at suse dot de> <CAAgBjMkcNH6WAkgaB0p7xr7dwhmuMA0z2bwb6DQxH4WKvA1zfA at mail dot gmail dot com> <alpine dot LSU dot 2 dot 11 dot 1604141024150 dot 13384 at t29 dot fhfr dot qr> <CAAgBjM=5gwG8RNicUWs7hDjST=-dQtPOSqkm9MEEHZBzwx_STQ at mail dot gmail dot com>

On Thu, 14 Apr 2016, Prathamesh Kulkarni wrote: > On 14 April 2016 at 13:56, Richard Biener <rguenther@suse.de> wrote: > > On Thu, 14 Apr 2016, Prathamesh Kulkarni wrote: > > > >> On 12 April 2016 at 22:41, Richard Biener <rguenther@suse.de> wrote: > >> > On April 12, 2016 3:47:19 PM GMT+02:00, Prathamesh Kulkarni <prathamesh.kulkarni@linaro.org> wrote: > >> >>Hi, > >> >>How to check if two symbols are from same source file during WPA ? > >> >>Is symbol1->lto_file_data == symbol2->lto_file_data true if symbol1 > >> >>and symbol2 are from same > >> >>source files ? Would that be a sufficient condition or do I need to > >> >>check for something more ? > >> > > >> > Why would you want to know? The proposed check would verify it comes from the same TU. > >> Hi, > >> I am trying to address issue with section anchors with LTO. > >> In non-LTO mode (or 1to1 map), a TU is mapped to object-file 1:1 > >> Therefore we can take advantage of section anchors. > >> IIUC with balanced partitioning, variable is added in the first partition it is > >> referenced in. So it may get separated into other partition from functions > >> referencing it, thus causing it to be loaded as an external reference. > >> > >> My point is that the "first" partition to which the variable is added may not > >> be the best choice for it. > >> For instance: > >> file1.c defines variables 'a' and 'b' and functions f1(), f2() > >> file2.c defines f3(). > >> f1, f2, f3 use 'a' and 'b'. > >> > >> It could happen that f3, a and b are mapped to one partition (assuming > >> f3 is processed first), and f1, f2 are mapped to another partition. > >> so f1 and f2 are forced to load a, b as external references. > >> It would be better instead to put a and b in same partition as f1 and f2. > >> > >> As first cut I tried to implement the following very simple approach: > >> Assume V(f) gives a set of all variables referenced by function f. > >> Let S = V(f1) intersect V(f2) ... intersect V(fn). > >> Add f1, f2, .. fn and S to same partition if > >> a) S is non-empty, that is, we add functions and "common" variables > >> referenced by these functions to same partition. > >> b) Function uses at least two global variables. If a function uses > >> only a single global variable, then AFAIU it wouldn't matter if it's loaded > >> as external reference. > >> However the above approach results in quite distorted partitioning > >> creating very large partitions and took 4x time to build chromium with LTO. > >> > >> So I tried to restrain adding number of symbols, by allowing them to be added > >> only if they are from same TU. > >> This would (hopefully) ensure that we are not worse than non-LTO case > >> since we add functions and common set of variables referenced by these > >> functions to same partition provided all of them belong to same TU. > >> As a worst-case, it will add all symbols from the TU to which function > >> belongs, if all the functions in > >> that TU reference >=2 global variables and reference at least one global > >> variable in common from the same TU. We might want to put a higher upper > >> limit than 1 for number of shared referenced global vars to stop adding > >> too many symbols to same partition. > >> > >> For eg: > >> file1.c defines variables 'a', 'b' and functions f1_ab(), f2_ab() > >> file2.c: defines f3_ab() > >> where f1_ab, f2_ab, f3_ab both use a, b > >> If f1_ab is added to partiton, it would try adding 'a', 'b' and f2_ab > >> to the same partition but > >> not f3_ab() since it belongs to another TU. > >> (f3_ab() may get added to the same partition by another iteration if > >> there's enough space in > >> the partition but that's irrelevant). > >> > >> Ideally I would like to put those functions and variables in the same > >> partition such that the use > >> of section anchors can be maximized, which would also involve adding > >> functions from other TU. > >> In above case it's desirable to add f3_ab to the same > >> partition as f1_ab, however I am not sure what constraints to check for since > >> we could potentially end up adding lots of symbols (as in approach 1). > >> For now, I only considered the check if they are from same TU. > >> > >> I have attached a prototype patch that implements the above approach. > >> It passes testing on arm*-*-* and aarch64*-*-* and takes roughly same time > >> to build chromium with LTO as without patch. > >> The patch should only affect targets with section anchor support (arm, > >> aarch64, ppc). > >> I have to yet perform benchmarking with the patch, I will get back > >> with some results > >> after I get that done. > >> I would be grateful for feedback especially regarding correctness. > > > > Ok, I didn't try to fully understand what you did but why not simply > > keep partitioning of functions as-is and simply put variables into > > the partition which contains the most references to it? > > > > Section anchor optimization should be a 2nd choice for partitioning > > and really partitioning functions together like we do should have priority. > Well balanced partitioning would reorder functions without considering section > anchors, so putting variables in partition containing max references may not > be optimal. > For eg: > file1.c defines a, b, and three functions f1, f2, f3 using a, b. > As a worst case, balanced partitioning algo may put f1, f2, f3 > in separate partitions which would defeat section anchor optimization. > > With the patch, I try to retain {a, b, f1, f2, f3} in same > partition (other symbols from same TU may go elsewhere). > The rationale for this is that the effect of section anchors > remains the same as for non-LTO (although now we would eat up space > of callees which would be put in the same partition). > > Complication arises when different functions reference only some > of the global variables. > for eg: > file1.c: defines a, b, c and functions f1, f2, f3, f4, f5. > f1, f2 use a, b and f3, f4, f5 use a, c. > The patch would add all the symbols {a, b, c, f1, f2, f3, f4, f5} to the > same partition. As a worst-case this could end up adding > all symbols from the same TU, which would lean more towards 1to1 > rather than balanced. > > So I suppose we would rather want to add that subset of symbols that > has "maximum commonality" ? > for eg: > file1.c: defines a, b, c, d and functions: > f1 -> {a, b, c} > f2 -> {a, b, c} > f3 -> {a, b, c, d} > f4 -> {a, c, d} > f5 -> {a, b} > f6 -> {a, c} > f7 -> {a, b} > f8 -> {a, c, d} > > Here the pair {a, b, c} is referenced by 2 functions. > {a, b, c, d} referenced by 1 functions. > {a, c, d} referenced by 2 functions > {a, b} referenced by 2 functions > {a, c} referenced by 1 function. > > So to maximize "commonality", I suppose we would want to put > {a, b, c, f1, f2} or {a, c, d, f4, f8} in same partition instead of all > symbols. > > Finding "max commonality" > > Let map<V, F> be a hashtable. > where V = {set of variables referenced} > and F = {set of functions referencing the variables in set V} > > for (each function f) > { > V = {variables referenced by f} > map[V].insert (f); // insert f in map.F corresponding to map.V > } > > In above example, > map would be: > {a, b, c} -> {f1 f2} > {a, b, c, d} -> {f3} > {a, b} -> {f5, f7} > {a, c, d} -> {f4, f8} > {a, c} -> {f6} > > We could define max "commonality" then as those entries in map > which have max number of variables for max number of functions. > > In above eg, entries having maximum number of functions (2): > {a, b, c} -> {f1, f2} > {a, b} -> {f5, f7} > {a, c, d} -> {f4, f8} > > Among these we want to choose entries having max number of variables > (3), which is: > {a, b, c} -> {f1, f2} > {a, c, d} -> {f4, f8} > Among these we can choose either entry, so we either put {a, b, c, f1, f2} in > same partition or {a, c, d, f4, f8} in same partition. > Which I suppose would be better than putting {a, b, c, d, f1, f2, f3, > f4, f5, f6, f7, f8} > in same partition as is done currently in the patch. > > I am not sure if that's the best approach. > for instance if we have 3 functions referencing same 6 variables > and 4 functions referencing same 2 variables, > then the above method would choose to put {4 functions 2 variables } > in same partition which > might be inferior to putting { 3 functions 6 variables } in same partitions. > I suppose we could modify the above method to choose those entries > having number of functions within range [max - CONSTANT, max] > instead of choosing entries having max number of functions but I am > not sure what would be a good value for CONSTANT. > > We could also drop the same TU constraint since finding "max" commonality > doesn't check if symbols are in same TU. > This interferes with adding functions in callgraph order to same > partition so perhaps > we could have more constraints to ensure we don't add many symbols in > partition boundary. > > Does this sound reasonable ? What happens in practice? GCC doesn't put functions in random partitions. > If it's not desired by default could we gate it on an option ? > AFIAU, section anchors optimization is important for ARM and AArch64. For code size or for performance? I wonder why section anchors cannot be "implemented" using some special relocations and thus as linker optimization. Richard.

**Follow-Ups**:**Re: How to check if two symbols are from same source unit during WPA ?***From:*Ramana Radhakrishnan

**References**:**How to check if two symbols are from same source unit during WPA ?***From:*Prathamesh Kulkarni

**Re: How to check if two symbols are from same source unit during WPA ?***From:*Richard Biener

**Re: How to check if two symbols are from same source unit during WPA ?***From:*Prathamesh Kulkarni

**Re: How to check if two symbols are from same source unit during WPA ?***From:*Richard Biener

**Re: How to check if two symbols are from same source unit during WPA ?***From:*Prathamesh Kulkarni

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |