On Mon, Apr 14, 2025 at 3:11 PM Kyrylo Tkachov <ktkac...@nvidia.com> wrote:
>
> Hi Honza,
>
> > On 13 Apr 2025, at 23:19, Jan Hubicka <hubi...@ucw.cz> wrote:
> >
> >> +@opindex fipa-reorder-for-locality
> >> +@item -fipa-reorder-for-locality
> >> +Group call chains close together in the binary layout to improve code code
> >> +locality. This option is incompatible with an explicit
> >> +@option{-flto-partition=} option since it enforces a custom partitioning
> >> +scheme.
> >
> > Please also cross-link this with -fprofile-reorder-functions and
> > -freorder-functions, which does similar thing.
> > If you see how to clean-up the description of the other two so user is
> > not confused.
> >
> > Perhaps say that -freorder-functions only partitions functions into
> > never-executed/cold/normal/hot and -fprofile-reroder-functions is aiming
> > for program startup optimization (it reorders by measured first time the
> > function is executed. By accident it seems to kind of work for
> > locality.
>
> Yeah, the option names are quite similar aren't they?
> I’ve attempted to disambiguate them a bit in their description.
> I’m attaching a diff from the previous version (as the full updated patch) to
> make it easier to see what’s adjusted.
>
>
> >
> >> +
> >> +/* Helper function of to accumulate call counts. */
> >> +static bool
> >> +accumulate_profile_counts_after_cloning (cgraph_node *node, void *data)
> >> +{
> >> + struct profile_stats *stats = (struct profile_stats *) data;
> >> + for (cgraph_edge *e = node->callers; e; e = e->next_caller)
> >> + {
> >> + if (e->caller == stats->target)
> >> + {
> >> + if (stats->rec_count.compatible_p (e->count.ipa ()))
> >> + stats->rec_count += e->count.ipa ();
> >> + }
> >> + else
> >> + {
> >> + if (stats->nonrec_count.compatible_p (e->count.ipa ()))
> >> + stats->nonrec_count += e->count.ipa ();
> >> + }
> > In case part of profile is missing (which may happen if one unit has -O0
> > or so) , we may have counts to be uninitialized. Uninitialized counts are
> > compatible with everything, but any arithmetics with it will produce
> > uninitialized result which will likely confuse code later. So I would
> > skip edges with uninitialized counts.
> >
> > On the other hand ipa counts are always compatible, so compatible_p
> > should be redundat. Main reaosn for existence of compatible_p is that we
> > can have local profiles that are 0 or unknown at IPA level. The ipa ()
> > conversion turns all counts into IPA counts and those are compatible
> > with each other.
> >
> > I suppose compatibe_p test is there since the code ICEd in past,but I
> > think it was because of missing ipa() conversion.
> >
> >
> >> + }
> >> + return false;
> >> +}
> >> +
> >> +/* NEW_NODE is a previously created clone of ORIG_NODE already present in
> >> + current partition. EDGES contains newly redirected edges to NEW_NODE.
> >> + Adjust profile information for both nodes and the edge. */
> >> +
> >> +static void
> >> +adjust_profile_info_for_non_self_rec_edges (auto_vec<cgraph_edge *>
> >> &edges,
> >> + cgraph_node *new_node,
> >> + cgraph_node *orig_node)
> >> +{
> >> + profile_count orig_node_count = orig_node->count.ipa ();
> >> + profile_count edge_count = profile_count::zero ();
> >> + profile_count final_new_count = profile_count::zero ();
> >> + profile_count final_orig_count = profile_count::zero ();
> >> +
> >> + for (unsigned i = 0; i < edges.length (); ++i)
> >> + edge_count += edges[i]->count.ipa ();
> > Here I would again skip uninitialized. It is probably legal for -O0
> > function to end up in partition.
> >> +
> >> + final_orig_count = orig_node_count - edge_count;
> >> +
> >> + /* NEW_NODE->count was adjusted for other callers when the clone was
> >> + first created. Just add the new edge count. */
> >> + if (new_node->count.compatible_p (edge_count))
> >> + final_new_count = new_node->count + edge_count;
> > And here compatible_p should be unnecesary.
> >> +/* Accumulate frequency of all edges from EDGE->caller to EDGE->callee.
> >> */
> >> +
> >> +static sreal
> >> +accumulate_incoming_edge_frequency (cgraph_edge *edge)
> >> +{
> >> + sreal count = 0;
> >> + struct cgraph_edge *e;
> >> + for (e = edge->callee->callers; e; e = e->next_caller)
> >> + {
> >> + /* Make a local decision about all edges for EDGE->caller but not
> >> the
> >> + other nodes already in the partition. Their edges will be visited
> >> + later or may have been visited before and not fit the
> >> + cut-off criteria. */
> >> + if (e->caller == edge->caller)
> >> + {
> >> + profile_count caller_count = e->caller->inlined_to
> >> + ? e->caller->inlined_to->count
> >> + : e->caller->count;
> >> + if (e->count.compatible_p (caller_count))
> > Here again compatiblity check should not be necessary, since the counts
> > belong to one function body (after inlining) and should be compatible.
> > inliner calls e->sreal_frequency all the time withotu further checks.
> >
>
> Yeah, I’ve adjusted these uses and used checks for initialized_p where you
> highlighted.
> Indeed it seems to work with a profiled bootstrap and the ICEs we were seeing
> earlier in development aren’t appearing.
>
> > Patch is OK with these changes. I apologize for letting the review slip
> > for so long. I was setting up Firefox testing and LLVM builds to gather
> > some data that took longer than I hoped for. On Firefox and LLVM on zen
> > I can measure some improvements via instruction cache perofmrance
> > counters, but the overall benefit seems to be close to noise, but this
> > is likely very CPU specfic. Overall code locality is one of main missing
> > parts of the LTO framework. As discussed on Cauldron, I think next
> > stage1 we can untie this from partitining algorithm, but that needs more
> > work on linker side as well as on gas fragments, so I think it is a good
> > idea to move with this patch as it is and improve from it.
>
> Thank you very much for the evaluation and the feedback! I agree the effect
> can be very CPU-specific.
>
> >
> > I think the patch is modifying almost no code that is run w/o the
> > -fipa-reorder-for-locality so I hope it is safe for 15.1, but I would
> > like to let Richi and Jakub to comment on this.
>
> Thanks a lot for your reviews yet again. They were very helpful.
> I’ve updated the patch as per your suggestion and did a profiled lto
> bootstrap with the new bootstrap-lto-locality.mk that exercises this.
> All looks good on aarch64-none-linux-gnu.
> Richi, Jakub, is it okay for trunk now given Honza’s comments?
OK, prepare to back out if there are any issues though.
Quickly skimming over the patch shows
+/* Locality partitions, assigns nodes to partitions. These are used later in
+ WPA partitioning. */
+vec<locality_partition> locality_partitions;
+
+/* Map from original node to its latest clone. Gets overwritten whenever a new
+ clone is created from the same node. */
+hash_map<cgraph_node *, cgraph_node *> node_to_clone;
+/* Map from clone to its original node. */
+hash_map<cgraph_node *, cgraph_node *> clone_to_node;
those global CTORs are frowned upon (why are those not static?), we prefer
those to be pointers. They are also not marked for garbage collection
but cgraph_node generally are so I assume they are only live through the
IPA pass itself. So they should be ideally created in a more local scope.
Richard.
>
>
> >
> > Honza
>
