This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Free dominance info if any edges are eliminated
- From: "H.J. Lu" <hjl dot tools at gmail dot com>
- To: Richard Biener <richard dot guenther at gmail dot com>
- Cc: Jeff Law <law at redhat dot com>, Jakub Jelinek <jakub at redhat dot com>, "Enkovich, Ilya" <ilya dot enkovich at intel dot com>, Uros Bizjak <ubizjak at gmail dot com>, GCC Development <gcc at gcc dot gnu dot org>
- Date: Fri, 11 Mar 2016 09:46:56 -0800
- Subject: Re: [PATCH] Free dominance info if any edges are eliminated
- Authentication-results: sourceware.org; auth=none
- References: <CAMe9rOo5=22xxzi9MfiX3o7NuvGGa7ySCg3jD6YsRyGX+TBvEg at mail dot gmail dot com>
On Fri, Mar 11, 2016 at 6:45 AM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Fri, Mar 11, 2016 at 6:03 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Fri, Mar 11, 2016 at 3:01 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
>>> On Fri, Mar 11, 2016 at 5:50 AM, H.J. Lu <hjl.tools@gmail.com> wrote:
>>>> On Fri, Mar 11, 2016 at 5:19 AM, Richard Biener
>>>> <richard.guenther@gmail.com> wrote:
>>>>> On Fri, Mar 11, 2016 at 2:02 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
>>>>>> On Fri, Mar 11, 2016 at 4:58 AM, Richard Biener
>>>>>> <richard.guenther@gmail.com> wrote:
>>>>>>> On Fri, Mar 11, 2016 at 1:47 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
>>>>>>>> On Fri, Mar 11, 2016 at 2:06 AM, Richard Biener
>>>>>>>> <richard.guenther@gmail.com> wrote:
>>>>>>>>> On Fri, Mar 11, 2016 at 4:10 AM, H.J. Lu <hjl.tools@gmail.com> wrote:
>>>>>>>>>> On Thu, Mar 10, 2016 at 7:03 PM, Jeff Law <law@redhat.com> wrote:
>>>>>>>>>>> On 03/10/2016 08:00 PM, H.J. Lu wrote:
>>>>>>>>>>>>
>>>>>>>>>>>> On Thu, Mar 10, 2016 at 1:30 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>> On Thu, Mar 10, 2016 at 1:24 PM, Jeff Law <law@redhat.com> wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> On 03/10/2016 01:18 PM, Richard Biener wrote:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> On March 10, 2016 6:02:58 PM GMT+01:00, "H.J. Lu" <hjl.tools@gmail.com>
>>>>>>>>>>>>>>> wrote:
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> On Thu, Mar 10, 2016 at 6:57 AM, H.J. Lu <hjl.tools@gmail.com> wrote:
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> On Thu, Mar 10, 2016 at 5:49 AM, Jakub Jelinek <jakub@redhat.com>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> wrote:
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> On Thu, Mar 10, 2016 at 05:43:27AM -0800, H.J. Lu wrote:
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> free_dominance_info (CDI_DOMINATORS);
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> Since convert_scalars_to_vector may add instructions, dominance
>>>>>>>>>>>>>>>>>>> info is no longer up to date.
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> Adding instructions doesn't change anything on the dominance info,
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> just
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> cfg manipulations that don't keep the dominators updated.
>>>>>>>>>>>>>>>>>> You can try to verify the dominance info at the end of the stv pass,
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> I added
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> verify_dominators (CDI_DOMINATORS);
>>>>>>>>>>>>>>>>> '
>>>>>>>>>>>>>>>>> It did trigger assert in my 64-bit STV pass in 64-bit libgcc build:
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> /export/gnu/import/git/sources/gcc/libgcc/config/libbid/bid128_fma.c:
>>>>>>>>>>>>>>>>> In function \u2018add_and_round.constprop\u2019:
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> /export/gnu/import/git/sources/gcc/libgcc/config/libbid/bid128_fma.c:629:1:
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> error: dominator of 158 should be 107, not 101
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> I will investigate.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Here is the problem:
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> 1. I extended the STV pass to 64-bit to convert TI load/store to
>>>>>>>>>>>>>>>> V1TI load/store to use SSE load/store for 128-bit load/store.
>>>>>>>>>>>>>>>> 2. The 64-bit STV pass generates settings of CONST0_RTX and
>>>>>>>>>>>>>>>> CONSTM1_RTX to store 128-bit 0 and -1.
>>>>>>>>>>>>>>>> 3. I placed the 64-bit STV pass before the CSE pass so that
>>>>>>>>>>>>>>>> CONST0_RTX and CONSTM1_RTX generated by the STV pass
>>>>>>>>>>>>>>>> can be CSEed.
>>>>>>>>>>>>>>>> 4. After settings of CONST0_RTX and CONSTM1_RTX are CSEed,
>>>>>>>>>>>>>>>> dominance info will be wrong.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Can't see how cse can ever invalidate dominators.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> cse can simplify jumps which can invalidate dominance information.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> But cse-ing CONST0_RTX and CONSTM1_RTX shouldn't invalidate dominators,
>>>>>>>>>>>>>> that's just utter nonsense -- ultimately it has to come down to changing
>>>>>>>>>>>>>> jumps. ISTM HJ has more digging to do here.
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Not just CONST0_RTX and CONSTM1_RTX. The new STV
>>>>>>>>>>>>> pass changes mode of SET from TImode to V1TImode which
>>>>>>>>>>>>> exposes more opportunities to CSE.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> What I did is equivalent to
>>>>>>>>>>>>
>>>>>>>>>>>> diff --git a/gcc/cse.c b/gcc/cse.c
>>>>>>>>>>>> index 2665d9a..43202a1 100644
>>>>>>>>>>>> --- a/gcc/cse.c
>>>>>>>>>>>> +++ b/gcc/cse.c
>>>>>>>>>>>> @@ -7644,7 +7644,11 @@ public:
>>>>>>>>>>>> return optimize > 0 && flag_rerun_cse_after_loop;
>>>>>>>>>>>> }
>>>>>>>>>>>>
>>>>>>>>>>>> - virtual unsigned int execute (function *) { return rest_of_handle_cse2
>>>>>>>>>>>> (); }
>>>>>>>>>>>> + virtual unsigned int execute (function *)
>>>>>>>>>>>> + {
>>>>>>>>>>>> + calculate_dominance_info (CDI_DOMINATORS);
>>>>>>>>>>>> + return rest_of_handle_cse2 ();
>>>>>>>>>>>> + }
>>>>>>>>>>>>
>>>>>>>>>>>> }; // class pass_cse2
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> which leads to the same ICE:
>>>>>>>>>>>
>>>>>>>>>>> But you haven't done the proper analysis to understand why the dominance
>>>>>>>>>>> relationships have changed. Nothing of the changes you've outlined in your
>>>>>>>>>>> messages should invalidate the dominance information.
>>>>>>>>>>
>>>>>>>>>> Nothing is changed. Just calling
>>>>>>>>>>
>>>>>>>>>> calculate_dominance_info (CDI_DOMINATORS);
>>>>>>>>>>
>>>>>>>>>> before rest_of_handle_cse2 will lead to ICE.
>>>>>>>>>
>>>>>>>>> Well, so CSE2 invalidates dominators but fails to free them when necessary.
>>>>>>>>> Please figure out the CSE transform that invalidates them and free dominators
>>>>>>>>> there.
>>>>>>>>
>>>>>>>> I can give it a try. But I'd like to first ask since CSE2 never calls
>>>>>>>> calculate_dominance_info (CDI_DOMINATORS), does it need to
>>>>>>>> keep dominators valid?
>>>>>>>
>>>>>>> If it doesn't free them then yes.
>>>>>>>
>>>>>>>> free_dominance_info (CDI_DOMINATORS);
>>>>>>>>
>>>>>>>> at beginning will do the job.
>>>>>>>
>>>>>>> Of course. But that may be not always necessary and thus cause extra
>>>>>>> dominance compute for the next user.
>>>>>>
>>>>>> Do we need to both CDI_DOMINATORS and CDI_POST_DOMINATORS
>>>>>> valid?
>>>>>
>>>>> CDI_POST_DOMINATORS is required to be freed by passes.
>>>>>
>>>>
>>>> This works for me. Should I submit a patch?
>>>>
>>>> H.J.
>>>> ---
>>>> diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c
>>>> index 62b0596..1307e22 100644
>>>> --- a/gcc/cfgrtl.c
>>>> +++ b/gcc/cfgrtl.c
>>>> @@ -228,7 +228,11 @@ delete_insn_and_edges (rtx_insn *insn)
>>>> purge = true;
>>>> delete_insn (insn);
>>>> if (purge)
>>>> - purge_dead_edges (BLOCK_FOR_INSN (insn));
>>>> + {
>>>> + purge_dead_edges (BLOCK_FOR_INSN (insn));
>>>> + if (dom_info_available_p (CDI_DOMINATORS))
>>>> + free_dominance_info (CDI_DOMINATORS);
>>>> + }
>>>> }
>>>>
>>>> /* Unlink a chain of insns between START and FINISH, leaving notes
>>>
>>> Or should do it in purge_dead_edges?
>>
>> If it does purge any edge, yes, and you can free unconditonally
>> w/o checking if it is available.
>>
>
> Here is a patch. OK for trunk?
>
It isn't sufficient:
[hjl@gnu-18 libjava]$ /bin/sh ./libtool --tag=GCJ --mode=compile
/export/build/gnu/gcc/build-x86_64-linux/./gcc/gcj
-B/export/build/gnu/gcc/build-x86_64-linux/x86_64-pc-linux-gnu/32/libjava/
-B/export/build/gnu/gcc/build-x86_64-linux/x86_64-pc-linux-gnu/32/libjava/
-B/export/build/gnu/gcc/build-x86_64-linux/./gcc/
-B/usr/gcc-6.0.0/x86_64-pc-linux-gnu/bin/
-B/usr/gcc-6.0.0/x86_64-pc-linux-gnu/lib/ -isystem
/usr/gcc-6.0.0/x86_64-pc-linux-gnu/include -isystem
/usr/gcc-6.0.0/x86_64-pc-linux-gnu/sys-include -m32 -ffloat-store
-fomit-frame-pointer -Usun -fclasspath=
-fbootclasspath=/export/gnu/import/git/sources/gcc/libjava/classpath/lib
--encoding=UTF-8 -Wno-deprecated -fbootstrap-classes -g -O2 -m32 -c
-o java/lang/Class.lo
-fsource-filename=/export/gnu/import/git/sources/gcc/libjava/java/lang/Class.java
/export/gnu/import/git/sources/gcc/libjava/classpath/lib/java/lang/Class.class
libtool: compile: /export/build/gnu/gcc/build-x86_64-linux/./gcc/gcj
-B/export/build/gnu/gcc/build-x86_64-linux/x86_64-pc-linux-gnu/32/libjava/
-B/export/build/gnu/gcc/build-x86_64-linux/x86_64-pc-linux-gnu/32/libjava/
-B/export/build/gnu/gcc/build-x86_64-linux/./gcc/
-B/usr/gcc-6.0.0/x86_64-pc-linux-gnu/bin/
-B/usr/gcc-6.0.0/x86_64-pc-linux-gnu/lib/ -isystem
/usr/gcc-6.0.0/x86_64-pc-linux-gnu/include -isystem
/usr/gcc-6.0.0/x86_64-pc-linux-gnu/sys-include -m32 -ffloat-store
-fomit-frame-pointer -Usun -fclasspath=
-fbootclasspath=/export/gnu/import/git/sources/gcc/libjava/classpath/lib
--encoding=UTF-8 -Wno-deprecated -fbootstrap-classes -g -O2 -m32 -c
-fsource-filename=/export/gnu/import/git/sources/gcc/libjava/java/lang/Class.java
/export/gnu/import/git/sources/gcc/libjava/classpath/lib/java/lang/Class.class
-fPIC -o java/lang/.libs/Class.o
/export/gnu/import/git/sources/gcc/libjava/java/lang/Class.java: In
class 'java.lang.Class':
/export/gnu/import/git/sources/gcc/libjava/java/lang/Class.java: In
method 'java.lang.Class.desiredAssertionStatus()':
In file included from <built-in>:223:0:
/export/gnu/import/git/sources/gcc/libjava/java/lang/Class.java:911:0:
internal compiler error: in dominated_by_p, at dominance.c:975
return c.defaultAssertionStatus;
0x6d2c6b dominated_by_p(cdi_direction, basic_block_def const*,
basic_block_def const*)
/export/gnu/import/git/sources/gcc/gcc/dominance.c:975
0x10ecd63 use_killed_between
/export/gnu/import/git/sources/gcc/gcc/fwprop.c:742
0x10ed585 all_uses_available_at
/export/gnu/import/git/sources/gcc/gcc/fwprop.c:829
0x10ee15e forward_propagate_and_simplify
/export/gnu/import/git/sources/gcc/gcc/fwprop.c:1253
0x10ee15e forward_propagate_into
/export/gnu/import/git/sources/gcc/gcc/fwprop.c:1377
0x10ef6f4 fwprop
/export/gnu/import/git/sources/gcc/gcc/fwprop.c:1460
0x10ef6f4 execute
/export/gnu/import/git/sources/gcc/gcc/fwprop.c:1493
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.
[hjl@gnu-18 libjava]$
--
H.J.