Question about speculative make_edge_direct_to_target during LTO/IPA_PASS

Question about speculative make_edge_direct_to_target during LTO/IPA_PASS

[Erick Ochoa]

Hi,

I have a pass that is able to speculate the target of indirect function
calls. This pass is an IPA_PASS. It:

1. generates summaries with the possible targets.
2. writes analysis summary
3. reads analysis summary
4. combines the results from multiple partitions and if needed fixes the
targets
5. writes opt summary
6. reads opt summary
7. calls ipa_make_edge_direct_to_target with speculative=true

This pass is successful in that I can observe the transformation in the
generated gimple. (A function test and a direct function call in one branch
and the indirect function call in the other.)  However, I would like to
make the edges in the call graph visible to other IPA passes, particularly
ipa-cp. For this, I would need to create virtual clones during the WPA
stage. I am a little unfamiliar with virtual clones. What kind of
information would I need to store in the analysis summary and is there a
way to create speculative virtual clones? Can someone point to a similar
piece of code in GCC where this happens?

Thanks!

Re: Question about speculative make_edge_direct_to_target during LTO/IPA_PASS

[Martin Jambor]

Hi,

On Fri, Jul 01 2022, Erick Ochoa via Gcc wrote:
> Hi,
>
> I have a pass that is able to speculate the target of indirect function
> calls. This pass is an IPA_PASS. It:
>
> 1. generates summaries with the possible targets.
> 2. writes analysis summary
> 3. reads analysis summary
> 4. combines the results from multiple partitions and if needed fixes the
> targets
> 5. writes opt summary
> 6. reads opt summary
> 7. calls ipa_make_edge_direct_to_target with speculative=true

Why so late, why not as part of number 4?

>
> This pass is successful in that I can observe the transformation in the
> generated gimple. (A function test and a direct function call in one branch
> and the indirect function call in the other.)  However, I would like to
> make the edges in the call graph visible to other IPA passes, particularly
> ipa-cp.

As long as you schedule your pass before IPA-CP and create speculative
edges before its WPA, that should then just work.  I mean, IPA-CP may be
too conservative and its heuristics may need to be tweaked, but it
should see the speculative edges and propagate through them just fine.
Is that not so?

> For this, I would need to create virtual clones during the WPA
> stage.

I do not understand what the virtual clones would represent.  How should
they be different from the original when materialized?

> I am a little unfamiliar with virtual clones. What kind of
> information would I need to store in the analysis summary and is there a
> way to create speculative virtual clones? Can someone point to a similar
> piece of code in GCC where this happens?

Well, IPA-CP creates virtual clones.  Information associated with it
represents the special context for which they are created (see
create_specialized_node in ipa-cp.cc) but I am not sure what that would
be in your case.

I am also not sure what you mean by speculative virtual clones, if
virtual clones with only speculative edges leading to them, than those
can exist and (unless the call is considered cold), they are not removed
as uninteresting (see code in speculation_useful_p).

But I really think that making the edges speculative early is likely to
fix your issues.

Martin

Re: Question about speculative make_edge_direct_to_target during LTO/IPA_PASS

[Erick Ochoa]

On Fri, 1 Jul 2022 at 14:48, Martin Jambor <mjambor@suse.cz> wrote:

> Why so late, why not as part of number 4?
>

Hi Martin,

Thanks for the feedback. The original reason why the call to
make_edge_direct_to_target was done so late is because of the lack of
function bodies during WPA, summaries with insufficient information (I keep
track of only some information which when access to function bodies is
given during LTRANS I can finally have a cgraph_edge to use as a
parameter), and I am still figuring out things with edge summaries.

I have a couple of questions here to improve my summaries:

If I were to call make_edge_direct_to_target during WPA (or number 4) then
I need to have access to the indirect edge during WPA. This is because
make_edge_direct_to_target receives a cgraph_edge as a parameter. In order
to have access to the indirect edge during WPA, I need to generate
summaries which keep track of indirect edges.

I think this would be done with edge summaries. Again, my understanding of
edge summaries is incomplete. My understanding is that they contain
information to be transmitted along the edges of the call graph. However,
the implementation details are what is making it difficult for me to
understand. Unlike cgraph_nodes which can be encoded and decoded, it seems
to me that cgraph_edges have no encoding nor decoding. This makes it
somewhat hard to say that an information belongs to a given edge.

Looking into ipa-cp / ipa-prop it looks like edge summaries are stored by
first encoding the caller cgraph_node and then iterating over the edges in
the node->callees and node->indirect_calls. However, I know that edges can
be removed. That's why there are edge removal hooks. Shouldn't this affect
the information that is written if an edge was removed somewhere else?
Something that is not explicit, is also that the order in the node->callees
and node->indirect_calls is preserved from the moment the summary is
written to the moment the summary is read. Is this the case?

My understanding is also limited from the fact that ipa-cp does not have a
proper write_summary nor read_summary stages in its own class and instead
ipa-cp's summaries are written and read during ipa-prop. Is this an
implementation detail so that the edge information created for ipa-cp is
propagated correctly during inlining? (Or is there some other explanation
for this?) Would it also makes sense to write and read my edge summaries at
the same time as ipa-cp's edge summaries? I know that the base class
(call_summary) also has virtual methods for removal and duplication of
edges (which should be triggered during inlining / cleaning up of the
callgraph). But somehow the virtual methods ::remove and ::duplicate seem
different to me from the callbacks which need to be registered in the
IPA_PASSes. Again, why would one need to write and read ipa-cp's summaries
during ipa-prop if these callbacks exist which are triggered when summaries
need to be updated?

Thanks!

-Erick

Re: Question about speculative make_edge_direct_to_target during LTO/IPA_PASS

[Martin Jambor]

Hi Erick,,

On Thu, Jul 07 2022, Erick Ochoa wrote:
> On Fri, 1 Jul 2022 at 14:48, Martin Jambor <mjambor@suse.cz> wrote:
>
>> Why so late, why not as part of number 4?
>>
> Thanks for the feedback. The original reason why the call to
> make_edge_direct_to_target was done so late is because of the lack of
> function bodies during WPA, summaries with insufficient information (I keep
> track of only some information which when access to function bodies is
> given during LTRANS I can finally have a cgraph_edge to use as a
> parameter), and I am still figuring out things with edge summaries.
>
> I have a couple of questions here to improve my summaries:
>
> If I were to call make_edge_direct_to_target during WPA (or number 4) then
> I need to have access to the indirect edge during WPA. This is because
> make_edge_direct_to_target receives a cgraph_edge as a parameter. In order
> to have access to the indirect edge during WPA, I need to generate
> summaries which keep track of indirect edges.

That is being done and should not be a problem.  You just iterate over
the list beginning with node->indirect_calls and analyze it like normal
edges.

>
> I think this would be done with edge summaries. Again, my understanding of
> edge summaries is incomplete.

They are meant to be a generic mechanism to describe calls that is
pass-specific, they contain what the author of the pass puts in there.

> My understanding is that they contain
> information to be transmitted along the edges of the call graph.

That is how they are often used but generally speaking they are simply
some sort of a description of a call.

> However,
> the implementation details are what is making it difficult for me to
> understand. Unlike cgraph_nodes which can be encoded and decoded, it seems
> to me that cgraph_edges have no encoding nor decoding. This makes it
> somewhat hard to say that an information belongs to a given edge.

I am not sure I understand, you mean the encoding and decoding during
streaming?  I simply suggest that you do what ipa-fnsummary and IPA-SRA
do.  The mechanism is quite ugly, improvement in the streaming API would
be IMHO desirable, but I guess that is quite outside the scope of your
project.

>
> Looking into ipa-cp / ipa-prop it looks like edge summaries are stored by
> first encoding the caller cgraph_node and then iterating over the edges in
> the node->callees and node->indirect_calls. However, I know that edges can
> be removed.

Fortunately, not in between streaming them to disk and then back, so this
should not be a concern.

> That's why there are edge removal hooks.

No, removal hooks are there mainly to deallocate memory that is no
longer necessary (plus they are used by reference counting and stuff,
but not for streaming consistency).

> Shouldn't this affect
> the information that is written if an edge was removed somewhere else?
> Something that is not explicit, is also that the order in the node->callees
> and node->indirect_calls is preserved from the moment the summary is
> written to the moment the summary is read. Is this the case?

Yes, otherwise the code in place would not work, I guess.

>
> My understanding is also limited from the fact that ipa-cp does not have a
> proper write_summary nor read_summary stages in its own class and instead
> ipa-cp's summaries are written and read during ipa-prop.

ipa-prop is a file, not a pass.  The summaries are generated and written
during pass_ipa_fn_summary.  The only reason for that is that both
IPA-CP and inlining (and now also IPA-modref, I think) use what
previously were summaries of the other pass and eventually it made sense
to gather and stream them together.

> Is this an
> implementation detail so that the edge information created for ipa-cp is
> propagated correctly during inlining? (Or is there some other explanation
> for this?)

See above, there are no correctness reasons for this.

> Would it also makes sense to write and read my edge summaries at
> the same time as ipa-cp's edge summaries?

That is difficult to say without knowing what is in your summary and
what else you need.  If you make heavy use of information gathered by
IPA-CP/inlining, then perhaps yes.

But some isolation of the individual passes is also good.  So for
example IPA-SRA has its own node and edge summaries.

> I know that the base class
> (call_summary) also has virtual methods for removal and duplication of
> edges (which should be triggered during inlining / cleaning up of the
> callgraph). But somehow the virtual methods ::remove and ::duplicate seem
> different to me from the callbacks which need to be registered in the
> IPA_PASSes.

I'm not sure I understand.  Do you mean hooks like add_edge_removal_hook
of the symbol_table class?  Summaries use these internally to implement
the virtual methods you describe but there is nothing compulsory about
the hooks.  I also do not see what difference in between the two you
find troubling.

> Again, why would one need to write and read ipa-cp's summaries
> during ipa-prop if these callbacks exist which are triggered when summaries
> need to be updated?

The summary updating callbacks exist because passes run one after each
other and when one modifies the call-graph, the others often need to
update their own internal data structures, which summaries are.  The
division of code between ipa-prop.cc and ipa-cp.cc does not really
matter here.

Martin

Re: Question about speculative make_edge_direct_to_target during LTO/IPA_PASS

[Erick Ochoa]

Hi Martin,

thanks a lot for your help! You were right!  I am now able to call
make_edge_direct_to_target during WPA.

-Erick