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]

[PATCH] Free dominance info if any edges are eliminated


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?


-- 
H.J.
From 2593e9041e27081e549b8fc2ea14899a264dcc6b Mon Sep 17 00:00:00 2001
From: "H.J. Lu" <hjl.tools@gmail.com>
Date: Fri, 11 Mar 2016 06:35:49 -0800
Subject: [PATCH] Free dominance info if any edges are eliminated

When any edges are eliminated, dominators are invalidated and we should
free dominance info unconditonally.

	* cfgrtl.c (purge_dead_edges): Renamed to ...
	(purge_dead_edges_1): This.
	(purge_dead_edges): New.  Call purge_dead_edges_1 and free
	dominance info if any edges are eliminated.
	(purge_all_dead_edges): Free dominance info if any edges are
	eliminated.
---
 gcc/cfgrtl.c | 21 ++++++++++++++++++---
 1 file changed, 18 insertions(+), 3 deletions(-)

diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c
index 62b0596..8183c3a 100644
--- a/gcc/cfgrtl.c
+++ b/gcc/cfgrtl.c
@@ -2996,8 +2996,8 @@ rtl_verify_flow_info (void)
    or converted the unconditional jumps.  Eliminate the edges from CFG.
    Return true if any edges are eliminated.  */
 
-bool
-purge_dead_edges (basic_block bb)
+static bool
+purge_dead_edges_1 (basic_block bb)
 {
   edge e;
   rtx_insn *insn = BB_END (bb);
@@ -3214,6 +3214,19 @@ purge_dead_edges (basic_block bb)
   return purged;
 }
 
+/* Assume that the preceding pass has possibly eliminated jump instructions
+   or converted the unconditional jumps.  Eliminate the edges from CFG.
+   Return true and free dominance info if any edges are eliminated.  */
+
+bool
+purge_dead_edges (basic_block bb)
+{
+  bool purged = purge_dead_edges_1 (bb);
+  if (purged)
+    free_dominance_info (CDI_DOMINATORS);
+  return purged;
+}
+
 /* Search all basic blocks for potentially dead edges and purge them.  Return
    true if some edge has been eliminated.  */
 
@@ -3225,11 +3238,13 @@ purge_all_dead_edges (void)
 
   FOR_EACH_BB_FN (bb, cfun)
     {
-      bool purged_here = purge_dead_edges (bb);
+      bool purged_here = purge_dead_edges_1 (bb);
 
       purged |= purged_here;
     }
 
+  if (purged)
+    free_dominance_info (CDI_DOMINATORS);
   return purged;
 }
 
-- 
2.5.0


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]