From: Martin Jambor <mjambor@suse.cz>
To: "Arsen Arsenović" <arsen@aarsen.me>
Cc: GCC Mailing List <gcc@gcc.gnu.org>, Jan Hubicka <hubicka@ucw.cz>,
Martin Liska <mliska@suse.cz>
Subject: Re: cgraph: does node->inlined_to imply node->clones is non-empty?
Date: Fri, 24 Mar 2023 13:40:08 +0100 [thread overview]
Message-ID: <ri6v8iq5nmf.fsf@suse.cz> (raw)
In-Reply-To: <86cz55c15x.fsf@aarsen.me>
Hi,
On Sat, Mar 18 2023, Arsen Arsenović wrote:
> Martin Jambor <mjambor@suse.cz> writes:
[...]
>>>
>>> For the test case in the PR, in ipa.cc:remove_unreachable_nodes, GCC
>>> seems to try to remove an unreachable function that was already inlined
>>> into a different unreachable function.
>>
>> No, it fails to remove it. It is still there but should not have been,
>> that is the problem.
>
> Ah - I see.
>
>>>
>>> This decision later trips up the gcc_assert in:
>>>
>>> /* Inline clones might be kept around so their materializing allows further
>>> cloning. If the function the clone is inlined into is removed, we need
>>> to turn it into normal cone. */
>>> FOR_EACH_FUNCTION (node)
>>> {
>>> if (node->inlined_to
>>> && !node->callers)
>>> {
>>> gcc_assert (node->clones);
>>> node->inlined_to = NULL;
>>> update_inlined_to_pointer (node, node);
>>> }
>>> node->aux = NULL;
>>> }
>>>
>>> .. because it is expecting that an inlined function without callers
>>> (which is necessarily true here as this function is unreachable and so
>>> was ->remove ()'d earlier) has clones.
>>
>> The assert makes sure that if we encounter an inlined-to node without
>> any caller, that it merely holds as the holder of the function body for
>> its other specialized (think IPA-CP) or inline clones. If node->clones
>> is false, there are no such clones and it was a bug to mark the node as
>> required during the removal of unreachable nodes.
>
> I see. That makes sense. So, this assert is placed here by convenience
> rather than being this invariant being absolutely required for the
> purpose of the loop? (it is related, so this placement makes sense, I
> just want to confirm whether it's a "mandatory" invariant)
If the assert fails, the algorithm does not work as intended. OTOH, It
could be a gcc_checking_assert only since user compiled code would still
work, just would be unnecessarily bigger.
>
>>>
>>> Either removing the assertion or making clone_inline_nodes clone when
>>> there are no existing clones 'fixes' (suppresses, but I haven't verified
>>> whether the results are correct) the problem.
>>>
>>> Is this gcc_assert correct in that an inlined function without callers
>>> necessarily must have clones?
>>
>> It is correct. An inlined function without a caller is even a logical
>> oxymoron and can only exist if it has the purpose described above (and
>> even then probably only in a fairly special circumstances).
>
> Right. I wasn't quite sure whether setting inlined_to would remove that
> caller, but if I understood right, it should not.
>
> What is interesting, though, is that there is an attempt to remove this
> node during ipa_inline:
IPA-inline calls remove_unreachable_nodes to get rid of call graph nodes
which are known not to be necessary after inlining (inlining can lead to
redirection of some call graph edges to __builtin_unreachable) and
unreachable removal... well.. removes nodes.
>
> (gdb) bt
> #0 cgraph_edge::remove_callee (
> this=<cgraph_edge* 0x7ffff6de0410 (<cgraph_node * 0x7ffff6dedaa0
> "__ct_base "/18> -> <cgraph_node * 0x7ffff6c5b660 "value"/28>)>)
> at ../../gcc/gcc/cgraph.h:3299
> #1 0x0000000000d03c37 in cgraph_node::remove_callees (this=<cgraph_node
> * const 0x7ffff6dedaa0 "__ct_base "/18>) at
> ../../gcc/gcc/cgraph.cc:1743
> #2 0x0000000000d04387 in cgraph_node::remove (this=<cgraph_node * const
> 0x7ffff6dedaa0 "__ct_base "/18>) at ../../gcc/gcc/cgraph.cc:1884
> #3 0x00000000010da74f in symbol_table::remove_unreachable_nodes
> (this=0x7ffff6ddb000, file=0x7ffff7a814c0 <_IO_2_1_stderr_>) at
> ../../gcc/gcc/ipa.cc:518
> #4 0x0000000002b51e53 in ipa_inline () at
> ../../gcc/gcc/ipa-inline.cc:2761
> #5 0x0000000002b52cf7 in (anonymous
> namespace)::pass_ipa_inline::execute (this=0x3c8d5b0) at
> ../../gcc/gcc/ipa-inline.cc:3153
> (etc)
>
> ... I presume that my assumption that cgraph_node::remove () should
> remove nodes from the cgraph_node::next chain is wrong?
Ummm.... the function does that through the call to
symtab_node::unregister. But how is that related?
>
>>>
>>> And as a side question, do all clone nodes have a ->clones pointing to
>>> the same list of all clones, or are they in a tree-ish arrangement,
>>> where clones of clones end up forming a tree, with the clone_of pointer
>>> being a pointer to the parent?
>>
>> The latter, they form a tree.
>
> I see, that makes sense. Thanks.
>
>>> (in this instance, the node that trips
>>> the assert has a nullptr clone_of and clones value, which would AIUI
>>> imply that it is the original)
>>
>> Yes.
>>
>>> This train of thinking doesn't end up involving any devirtualization
>>> code, which the PR was originally reproduced with, but my current theory
>>> is that devirtualizing here just exposed an edge case that is decently
>>> well hidden, rather than it playing a crucial role.
>>
>> The inlined function is - I believe erroneously - marked as reachable by
>> walk_polymorphic_call_targets() within the unreachable analysis - so
>> devirtualizing is somewhat crucial.
>>
>> I believe the real question - to which I don't have an answer yet - is
>> why does possible_polymorphic_call_targets return a method that is not
>> virtual?
>>
>> (gdb) p n->decl->decl_common.virtual_flag
>> $19 = 0
>>
>> Or even
>>
>> (gdb) p referenced_from_vtable_p(n)
>> $24 = false
>>
>> Time to dig into ipa-devirt.cc, I guess....
>>
>> Martin
>
> I saw your response on the PR itself, thanks for handling that in my
> absence. With the information you've shared I believe I understand that
> the fix you provided: an inlined call can no longer be a polymorphic
> call target, and so reaching an inlined function inside
> walk_polymorphic_call_targets should not be possible?
The thing is that ICF discovers that a virtual function, which was
originally a possible target, is semantically identically to a
non-virtual function and merges them, making the virtual function an
alias of the non-virtual one. Devirtualization can then suddenly spit
out non-virtual potential targets which is kind of unexpected.
It seems to me that the most correct fix is to add to
walk_polymorphic_call_targets a check that the obtained possible target
is still referenced_from_vtable_p() - because the alias that was
originally a virtual function is referenced from a vtable that at this
point is also known to be gone. But the check looks like it is possibly
expensive, so I wanted to discuss this with Honza first (hopefully next
week).
>
> I had already figured that an error could've likely been in
> reach-ability analysis, but my time ran low, and I had not confirmed
> anything, or as little as formalized a theory, so I just wrote the
> original email instead of following this trail of thought fully.
>
> Thank you for your guidance! Have a lovely night :)
It is good thing that you asked, I also learned something new (that
virtual and non-virtual functions can be ICFed together).
Martin
next prev parent reply other threads:[~2023-03-24 12:48 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-03-13 10:24 Arsen Arsenović
2023-03-14 12:42 ` Martin Liška
2023-03-15 17:12 ` Martin Jambor
2023-03-18 15:26 ` Arsen Arsenović
2023-03-24 12:40 ` Martin Jambor [this message]
2023-03-24 13:29 ` Jan Hubicka
2023-03-28 1:10 ` Arsen Arsenović
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=ri6v8iq5nmf.fsf@suse.cz \
--to=mjambor@suse.cz \
--cc=arsen@aarsen.me \
--cc=gcc@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=mliska@suse.cz \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).