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

[Richard Biener <rguenther at suse dot de>]

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.

Richard.