This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Free dominance info if any edges are eliminated

On Fri, Mar 11, 2016 at 6:46 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
> 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]$

It means fwprop calls purge_dead_edges but expects dominators to remain
intact (which they do not, in all cases).  What passes should do is queue
edge purging and do that after they otherwise finished.

I suppose adding a verify_dominators to each dominated_by_p check
(ick!) would have catched this.  Note we don't have a notion of a partially
correct DOM tree so what fwprop runs into might be ok in practice
(I didn't try to investigate what it possibly calls dominated_by_p on
after purging dead edges from a BB).

Richard.

>
>
>
> --
> H.J.
Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]