[PATCH] Empty redirect_edge_var_map after each pass and function

[PATCH] Empty redirect_edge_var_map after each pass and function

[Alan Lawrence]

This follows on from discussion at
https://gcc.gnu.org/ml/gcc-patches/2015-11/msg03392.html
To recap: Starting in r229479 and continuing until at least 229711, compiling
polynom.c from spec2000 on aarch64-none-linux-gnu, with options
-O3 -mcpu=cortex-a53 -ffast-math (on both cross, native bootstrapped, and native
--disable-bootstrap compilers), produced a verify_gimple ICE after unswitch:

../spec2000/benchspec/CINT2000/254.gap/src/polynom.c: In function 'NormalizeCoeffsListx':
../spec2000/benchspec/CINT2000/254.gap/src/polynom.c:358:11: error: incompatible types in PHI argument 0
 TypHandle NormalizeCoeffsListx ( hdC )
           ^
long int

int

../spec2000/benchspec/CINT2000/254.gap/src/polynom.c:358:11: error: location references block not in block tree
l1_279 = PHI <1(28), l1_299(33)>
../spec2000/benchspec/CINT2000/254.gap/src/polynom.c:358:11: error: invalid PHI argument

../spec2000/benchspec/CINT2000/254.gap/src/polynom.c:358:11: internal compiler error: tree check: expected class 'type', have 'declaration' (namespace_decl) in useless_type_conversion_p, at gimple-expr.c:84
0xd110ef tree_class_check_failed(tree_node const*, tree_code_class, char const*, int, char const*)
        ../../gcc-fsf/gcc/tree.c:9643
0x82561b tree_class_check
        ../../gcc-fsf/gcc/tree.h:3042
0x82561b useless_type_conversion_p(tree_node*, tree_node*)
        ../../gcc-fsf/gcc/gimple-expr.c:84
0xaca043 verify_gimple_phi
        ../../gcc-fsf/gcc/tree-cfg.c:4673
0xaca043 verify_gimple_in_cfg(function*, bool)
        ../../gcc-fsf/gcc/tree-cfg.c:4967
0x9c2e0b execute_function_todo
        ../../gcc-fsf/gcc/passes.c:1967
0x9c360b do_per_function
        ../../gcc-fsf/gcc/passes.c:1659
0x9c3807 execute_todo
        ../../gcc-fsf/gcc/passes.c:2022

I was not able to reduce the testcase below about 30k characters, with e.g.
#define T_VOID 0
.... T_VOID ....
producing the ICE, but manually changing to
.... 0 ....
preventing the ICE; as did running the preprocessor as a separate step, or a
wide variety of options (e.g. -fdump-tree-alias).

In the end I traced this to loop_unswitch reading stale values from the edge
redirect map, which is keyed on 'edge' (a pointer to struct edge_def); the map
entries had been left there by pass_dominator (on a different function), and by
"chance" the edge *pointers* were the same as to some current edge_defs (even
though they pointed to structures created by different allocations, the first
of which had since been freed). Hence the fragility of the testcase and
environment.

While the ICE is prevented merely by adding a call to
redirect_edge_var_map_destroy at the end of pass_dominator::execute, given the
fragility of the bug, difficulty of reducing the testcase, and the low overhead
of emptying an already-empty map, I believe the right fix is to empty the map
as often as can correctly do so, hence this patch - based substantially on
Richard's comments in PR/68117.

Bootstrapped + check-gcc + check-g++ on x86_64 linux, based on r231105; I've
also built SPEC2000 on aarch64-none-linux-gnu by applying this patch (roughly)
onto the previously-failing r229711, which also passes aarch64 bootstrap, and
a more recent bootstrap on aarch64 is ongoing. Assuming/if no regressions there...

Is this ok for trunk?

This could also be a candidate for the 5.3 release; backporting depends only on
the (fairly trivial) r230357.

gcc/ChangeLog:

<DATE>  Alan Lawrence  <alan.lawrence@arm.com>
	Richard Biener  <richard.guenther@gmail.com>

	* cfgexpand.c (pass_expand::execute): Replace call to
	redirect_edge_var_map_destroy with redirect_edge_var_map_empty.
	* tree-ssa.c (delete_tree_ssa): Likewise.
	* function.c (set_cfun): Call redirect_edge_var_map_empty.
	* passes.c (execute_one_ipa_transform_pass, execute_one_pass): Likewise.
	* tree-ssa.h (redirect_edge_var_map_destroy): Remove.
	(redirect_edge_var_map_empty): New.
	* tree-ssa.c (redirect_edge_var_map_destroy): Remove.
	(redirect_edge_var_map_empty): New.

---
 gcc/cfgexpand.c | 2 +-
 gcc/function.c  | 2 ++
 gcc/passes.c    | 2 ++
 gcc/tree-ssa.c  | 8 ++++----
 gcc/tree-ssa.h  | 2 +-
 5 files changed, 10 insertions(+), 6 deletions(-)

diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c
index 1990e10..ede1b82 100644
--- a/gcc/cfgexpand.c
+++ b/gcc/cfgexpand.c
@@ -6291,7 +6291,7 @@ pass_expand::execute (function *fun)
   expand_phi_nodes (&SA);
 
   /* Release any stale SSA redirection data.  */
-  redirect_edge_var_map_destroy ();
+  redirect_edge_var_map_empty ();
 
   /* Register rtl specific functions for cfg.  */
   rtl_register_cfg_hooks ();
diff --git a/gcc/function.c b/gcc/function.c
index 515d7c0..e452865 100644
--- a/gcc/function.c
+++ b/gcc/function.c
@@ -75,6 +75,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-chkp.h"
 #include "rtl-chkp.h"
 #include "tree-dfa.h"
+#include "tree-ssa.h"
 
 /* So we can assign to cfun in this file.  */
 #undef cfun
@@ -4798,6 +4799,7 @@ set_cfun (struct function *new_cfun)
     {
       cfun = new_cfun;
       invoke_set_current_function_hook (new_cfun ? new_cfun->decl : NULL_TREE);
+      redirect_edge_var_map_empty ();
     }
 }
 
diff --git a/gcc/passes.c b/gcc/passes.c
index 0e23dcb..ba9bfc2 100644
--- a/gcc/passes.c
+++ b/gcc/passes.c
@@ -2218,6 +2218,7 @@ execute_one_ipa_transform_pass (struct cgraph_node *node,
   pass_fini_dump_file (pass);
 
   current_pass = NULL;
+  redirect_edge_var_map_empty ();
 
   /* Signal this is a suitable GC collection point.  */
   if (!(todo_after & TODO_do_not_ggc_collect))
@@ -2370,6 +2371,7 @@ execute_one_pass (opt_pass *pass)
 		|| pass->type != RTL_PASS);
 
   current_pass = NULL;
+  redirect_edge_var_map_empty ();
 
   if (todo_after & TODO_discard_function)
     {
diff --git a/gcc/tree-ssa.c b/gcc/tree-ssa.c
index 02fca4c..ddc7a65 100644
--- a/gcc/tree-ssa.c
+++ b/gcc/tree-ssa.c
@@ -119,10 +119,10 @@ redirect_edge_var_map_vector (edge e)
 /* Clear the edge variable mappings.  */
 
 void
-redirect_edge_var_map_destroy (void)
+redirect_edge_var_map_empty (void)
 {
-  delete edge_var_maps;
-  edge_var_maps = NULL;
+  if (edge_var_maps)
+    edge_var_maps->empty ();
 }
 
 
@@ -1128,7 +1128,7 @@ delete_tree_ssa (struct function *fn)
   fn->gimple_df = NULL;
 
   /* We no longer need the edge variable maps.  */
-  redirect_edge_var_map_destroy ();
+  redirect_edge_var_map_empty ();
 }
 
 /* Return true if EXPR is a useless type conversion, otherwise return
diff --git a/gcc/tree-ssa.h b/gcc/tree-ssa.h
index 3b5bd70..d33eb9c 100644
--- a/gcc/tree-ssa.h
+++ b/gcc/tree-ssa.h
@@ -35,7 +35,7 @@ extern void redirect_edge_var_map_add (edge, tree, tree, source_location);
 extern void redirect_edge_var_map_clear (edge);
 extern void redirect_edge_var_map_dup (edge, edge);
 extern vec<edge_var_map> *redirect_edge_var_map_vector (edge);
-extern void redirect_edge_var_map_destroy (void);
+extern void redirect_edge_var_map_empty (void);
 extern edge ssa_redirect_edge (edge, basic_block);
 extern void flush_pending_stmts (edge);
 extern void gimple_replace_ssa_lhs (gimple *, tree);
-- 
1.9.1

Re: [PATCH] Empty redirect_edge_var_map after each pass and function

[Jeff Law]

On 12/01/2015 11:33 AM, Alan Lawrence wrote:
>
> I was not able to reduce the testcase below about 30k characters, with e.g.
> #define T_VOID 0
> .... T_VOID ....
> producing the ICE, but manually changing to
> .... 0 ....
> preventing the ICE; as did running the preprocessor as a separate step, or a
> wide variety of options (e.g. -fdump-tree-alias).
Which is almost always an indication that there's a memory corruption, 
or uninitialized memory read or something similar.


>
> In the end I traced this to loop_unswitch reading stale values from the edge
> redirect map, which is keyed on 'edge' (a pointer to struct edge_def); the map
> entries had been left there by pass_dominator (on a different function), and by
> "chance" the edge *pointers* were the same as to some current edge_defs (even
> though they pointed to structures created by different allocations, the first
> of which had since been freed). Hence the fragility of the testcase and
> environment.
Right.  So the question I have is how/why did DOM leave anything in the 
map.   And if DOM is fixed to not leave stuff lying around, can we then 
assert that nothing is ever left in those maps between passes?  There's 
certainly no good reason I'm aware of why DOM would leave things in this 
state.

Jeff

Re: [PATCH] Empty redirect_edge_var_map after each pass and function

[Richard Biener]

On Tue, 1 Dec 2015, Jeff Law wrote:

> On 12/01/2015 11:33 AM, Alan Lawrence wrote:
> > 
> > I was not able to reduce the testcase below about 30k characters, with e.g.
> > #define T_VOID 0
> > .... T_VOID ....
> > producing the ICE, but manually changing to
> > .... 0 ....
> > preventing the ICE; as did running the preprocessor as a separate step, or a
> > wide variety of options (e.g. -fdump-tree-alias).
> Which is almost always an indication that there's a memory corruption, or
> uninitialized memory read or something similar.
> 
> 
> > 
> > In the end I traced this to loop_unswitch reading stale values from the edge
> > redirect map, which is keyed on 'edge' (a pointer to struct edge_def); the
> > map
> > entries had been left there by pass_dominator (on a different function), and
> > by
> > "chance" the edge *pointers* were the same as to some current edge_defs
> > (even
> > though they pointed to structures created by different allocations, the
> > first
> > of which had since been freed). Hence the fragility of the testcase and
> > environment.
> Right.  So the question I have is how/why did DOM leave anything in the map.
> And if DOM is fixed to not leave stuff lying around, can we then assert that
> nothing is ever left in those maps between passes?  There's certainly no good
> reason I'm aware of why DOM would leave things in this state.

It happens not only with DOM but with all passes doing edge redirection.
This is because the map is populated by GIMPLE cfg hooks just in case
it might be used.  But there is no such thing as a "start CFG manip"
and "end CFG manip" to cleanup such dead state.

IMHO the redirect-edge-var-map stuff is just the very most possible
unclean implementation possible. :(  (see how remove_edge "clears"
stale info from the map to avoid even more "interesting" stale
data)

Ideally we could assert the map is empty whenever we leave a pass,
but as said it triggers all over the place.  Even cfg-cleanup causes
such stale data.

I agree that the patch is only a half-way "solution", but a full
solution would require sth more explicit, like we do with
initialize_original_copy_tables/free_original_copy_tables.  Thus
require passes to explicitely request the edge data to be preserved
with a initialize_edge_var_map/free_edge_var_map call pair.

Not appropriate at this stage IMHO (well, unless it turns out to be
a very localized patch).

Richard.

Re: [PATCH] Empty redirect_edge_var_map after each pass and function

[Jeff Law]

On 12/02/2015 01:33 AM, Richard Biener wrote:
>> Right.  So the question I have is how/why did DOM leave anything in the map.
>> And if DOM is fixed to not leave stuff lying around, can we then assert that
>> nothing is ever left in those maps between passes?  There's certainly no good
>> reason I'm aware of why DOM would leave things in this state.
>
> It happens not only with DOM but with all passes doing edge redirection.
> This is because the map is populated by GIMPLE cfg hooks just in case
> it might be used.  But there is no such thing as a "start CFG manip"
> and "end CFG manip" to cleanup such dead state.
Sigh.

>
> IMHO the redirect-edge-var-map stuff is just the very most possible
> unclean implementation possible. :(  (see how remove_edge "clears"
> stale info from the map to avoid even more "interesting" stale
> data)
>
> Ideally we could assert the map is empty whenever we leave a pass,
> but as said it triggers all over the place.  Even cfg-cleanup causes
> such stale data.
>
> I agree that the patch is only a half-way "solution", but a full
> solution would require sth more explicit, like we do with
> initialize_original_copy_tables/free_original_copy_tables.  Thus
> require passes to explicitely request the edge data to be preserved
> with a initialize_edge_var_map/free_edge_var_map call pair.
>
> Not appropriate at this stage IMHO (well, unless it turns out to be
> a very localized patch).
So maybe as a follow-up to aid folks in the future, how about a 
debugging verify_whatever function that we can call manually if 
debugging a problem in this space.  With a comment indicating why we 
can't call it unconditionally (yet).


jeff

Re: [PATCH] Empty redirect_edge_var_map after each pass and function

[Alan Lawrence]

On 02/12/15 14:13, Jeff Law wrote:
> On 12/02/2015 01:33 AM, Richard Biener wrote:
>>> Right.  So the question I have is how/why did DOM leave anything in the map.
>>> And if DOM is fixed to not leave stuff lying around, can we then assert that
>>> nothing is ever left in those maps between passes?  There's certainly no good
>>> reason I'm aware of why DOM would leave things in this state.
>>
>> It happens not only with DOM but with all passes doing edge redirection.
>> This is because the map is populated by GIMPLE cfg hooks just in case
>> it might be used.  But there is no such thing as a "start CFG manip"
>> and "end CFG manip" to cleanup such dead state.
> Sigh.
>
>>
>> IMHO the redirect-edge-var-map stuff is just the very most possible
>> unclean implementation possible. :(  (see how remove_edge "clears"
>> stale info from the map to avoid even more "interesting" stale
>> data)
>>
>> Ideally we could assert the map is empty whenever we leave a pass,
>> but as said it triggers all over the place.  Even cfg-cleanup causes
>> such stale data.
>>
>> I agree that the patch is only a half-way "solution", but a full
>> solution would require sth more explicit, like we do with
>> initialize_original_copy_tables/free_original_copy_tables.  Thus
>> require passes to explicitely request the edge data to be preserved
>> with a initialize_edge_var_map/free_edge_var_map call pair.
>>
>> Not appropriate at this stage IMHO (well, unless it turns out to be
>> a very localized patch).
> So maybe as a follow-up to aid folks in the future, how about a debugging
> verify_whatever function that we can call manually if debugging a problem in
> this space.  With a comment indicating why we can't call it unconditionally (yet).
>
>
> jeff

I did a (fwiw disable bootstrap) build with the map-emptying code in passes.c 
(not functions.c), printing out passes after which the map was non-empty (before 
emptying it, to make sure passes weren't just carrying through stale data from 
earlier). My (non-exhaustive!) list of passes after which the 
edge_var_redirect_map can be non-empty stands at...

aprefetch ccp cddce ch ch_vect copyprop crited crited cselim cunroll cunrolli 
dce dom ehcleanup einline esra fab fnsplit forwprop fre graphite ifcvt 
isolate-paths ldist lim local-pure-const mergephi oaccdevlow ompexpssa optimized 
parloops pcom phicprop phiopt phiprop pre profile profile_estimate sccp sink 
slsr split-paths sra switchconv tailc tailr tracer unswitch veclower2 vect vrm 
vrp whole-program

FWIW, the route by which dom added the edge to the redirect map was:
#0  redirect_edge_var_map_add (e=e@entry=0x7fb7a5f508, result=0x7fb725a000,
     def=0x7fb78eaea0, locus=2147483884) at ../../gcc/gcc/tree-ssa.c:54
#1  0x0000000000cccf58 in ssa_redirect_edge (e=e@entry=0x7fb7a5f508,
     dest=dest@entry=0x7fb79cc680) at ../../gcc/gcc/tree-ssa.c:158
#2  0x0000000000b00738 in gimple_redirect_edge_and_branch (e=0x7fb7a5f508,
     dest=0x7fb79cc680) at ../../gcc/gcc/tree-cfg.c:5662
#3  0x00000000006ec678 in redirect_edge_and_branch (e=e@entry=0x7fb7a5f508,
     dest=<optimised out>) at ../../gcc/gcc/cfghooks.c:356
#4  0x0000000000cb4530 in ssa_fix_duplicate_block_edges (rd=0x1a29f10,
     local_info=local_info@entry=0x7fffffed40)
     at ../../gcc/gcc/tree-ssa-threadupdate.c:1184
#5  0x0000000000cb5520 in ssa_fixup_template_block (slot=<optimised out>,
     local_info=0x7fffffed40) at ../../gcc/gcc/tree-ssa-threadupdate.c:1369
#6  traverse_noresize<ssa_local_info_t*, ssa_fixup_template_block> (
     argument=0x7fffffed40, this=0x1a21a00) at ../../gcc/gcc/hash-table.h:911
#7  traverse<ssa_local_info_t*, ssa_fixup_template_block> (
     argument=0x7fffffed40, this=0x1a21a00) at ../../gcc/gcc/hash-table.h:933
#8  thread_block_1 (bb=bb@entry=0x7fb7485bc8,
     noloop_only=noloop_only@entry=true, joiners=joiners@entry=true)
     at ../../gcc/gcc/tree-ssa-threadupdate.c:1592
#9  0x0000000000cb5a40 in thread_block (bb=0x7fb7485bc8,
     noloop_only=noloop_only@entry=true)
     at ../../gcc/gcc/tree-ssa-threadupdate.c:1629
---Type <return> to continue, or q <return> to quit---
#10 0x0000000000cb6bf8 in thread_through_all_blocks (
     may_peel_loop_headers=true) at ../../gcc/gcc/tree-ssa-threadupdate.c:2736
#11 0x0000000000becf6c in (anonymous namespace)::pass_dominator::execute (
     this=<optimised out>, fun=0x7fb77d1b28)
     at ../../gcc/gcc/tree-ssa-dom.c:622
#12 0x00000000009feef4 in execute_one_pass (pass=pass@entry=0x16d1a80)
     at ../../gcc/gcc/passes.c:2311

The edge is then deleted much later:
#3  0x0000000000f858e4 in free_edge (fn=<optimised out>, e=<optimised out>)
     at ../../gcc/gcc/cfg.c:91
#4  remove_edge_raw (e=<optimised out>) at ../../gcc/gcc/cfg.c:350
#5  0x00000000006ec814 in remove_edge (e=<optimised out>)
     at ../../gcc/gcc/cfghooks.c:418
#6  0x00000000006ecaec in delete_basic_block (bb=bb@entry=0x7fb74b3618)
     at ../../gcc/gcc/cfghooks.c:597
#7  0x0000000000f8d1d4 in try_optimize_cfg (mode=32)
     at ../../gcc/gcc/cfgcleanup.c:2701
#8  cleanup_cfg (mode=mode@entry=32) at ../../gcc/gcc/cfgcleanup.c:3028
#9  0x000000000070180c in cfg_layout_initialize (flags=flags@entry=0)
     at ../../gcc/gcc/cfgrtl.c:4264
#10 0x0000000000f7cdc8 in (anonymous 
namespace)::pass_duplicate_computed_gotos::execute (this=<optimised out>, 
fun=0x7fb77d1b28)
     at ../../gcc/gcc/bb-reorder.c:2622
#11 0x00000000009feef4 in execute_one_pass (pass=pass@entry=0x16d5680)
     at ../../gcc/gcc/passes.c:2311

Adding a call to redirect_edge_var_map_clear in cfg.c (free_edge), does fix the 
ICE in polynom.c, but still leaves many passes ending with the redirect map 
non-empty.

--Alan

Re: [PATCH] Empty redirect_edge_var_map after each pass and function

[Richard Biener]

On Thu, 3 Dec 2015, Alan Lawrence wrote:

> On 02/12/15 14:13, Jeff Law wrote:
> > On 12/02/2015 01:33 AM, Richard Biener wrote:
> > > > Right.  So the question I have is how/why did DOM leave anything in the
> > > > map.
> > > > And if DOM is fixed to not leave stuff lying around, can we then assert
> > > > that
> > > > nothing is ever left in those maps between passes?  There's certainly no
> > > > good
> > > > reason I'm aware of why DOM would leave things in this state.
> > > 
> > > It happens not only with DOM but with all passes doing edge redirection.
> > > This is because the map is populated by GIMPLE cfg hooks just in case
> > > it might be used.  But there is no such thing as a "start CFG manip"
> > > and "end CFG manip" to cleanup such dead state.
> > Sigh.
> > 
> > > 
> > > IMHO the redirect-edge-var-map stuff is just the very most possible
> > > unclean implementation possible. :(  (see how remove_edge "clears"
> > > stale info from the map to avoid even more "interesting" stale
> > > data)
> > > 
> > > Ideally we could assert the map is empty whenever we leave a pass,
> > > but as said it triggers all over the place.  Even cfg-cleanup causes
> > > such stale data.
> > > 
> > > I agree that the patch is only a half-way "solution", but a full
> > > solution would require sth more explicit, like we do with
> > > initialize_original_copy_tables/free_original_copy_tables.  Thus
> > > require passes to explicitely request the edge data to be preserved
> > > with a initialize_edge_var_map/free_edge_var_map call pair.
> > > 
> > > Not appropriate at this stage IMHO (well, unless it turns out to be
> > > a very localized patch).
> > So maybe as a follow-up to aid folks in the future, how about a debugging
> > verify_whatever function that we can call manually if debugging a problem in
> > this space.  With a comment indicating why we can't call it unconditionally
> > (yet).
> > 
> > 
> > jeff
> 
> I did a (fwiw disable bootstrap) build with the map-emptying code in passes.c
> (not functions.c), printing out passes after which the map was non-empty
> (before emptying it, to make sure passes weren't just carrying through stale
> data from earlier). My (non-exhaustive!) list of passes after which the
> edge_var_redirect_map can be non-empty stands at...
> 
> aprefetch ccp cddce ch ch_vect copyprop crited crited cselim cunroll cunrolli
> dce dom ehcleanup einline esra fab fnsplit forwprop fre graphite ifcvt
> isolate-paths ldist lim local-pure-const mergephi oaccdevlow ompexpssa
> optimized parloops pcom phicprop phiopt phiprop pre profile profile_estimate
> sccp sink slsr split-paths sra switchconv tailc tailr tracer unswitch
> veclower2 vect vrm vrp whole-program

Yeah, exactly my findings...  note that most of the above are likely
due to cfgcleanup even though it already does sth like

              e = redirect_edge_and_branch (e, dest);
              redirect_edge_var_map_clear (e);

so eventually placing a redirect_edge_var_map_empty () at the end
of the cleanup_tree_cfg function should prune down the above list
considerably (well, then assert the map is empty on entry to that
function of course)

> FWIW, the route by which dom added the edge to the redirect map was:
> #0  redirect_edge_var_map_add (e=e@entry=0x7fb7a5f508, result=0x7fb725a000,
>     def=0x7fb78eaea0, locus=2147483884) at ../../gcc/gcc/tree-ssa.c:54
> #1  0x0000000000cccf58 in ssa_redirect_edge (e=e@entry=0x7fb7a5f508,
>     dest=dest@entry=0x7fb79cc680) at ../../gcc/gcc/tree-ssa.c:158
> #2  0x0000000000b00738 in gimple_redirect_edge_and_branch (e=0x7fb7a5f508,
>     dest=0x7fb79cc680) at ../../gcc/gcc/tree-cfg.c:5662
> #3  0x00000000006ec678 in redirect_edge_and_branch (e=e@entry=0x7fb7a5f508,
>     dest=<optimised out>) at ../../gcc/gcc/cfghooks.c:356
> #4  0x0000000000cb4530 in ssa_fix_duplicate_block_edges (rd=0x1a29f10,
>     local_info=local_info@entry=0x7fffffed40)
>     at ../../gcc/gcc/tree-ssa-threadupdate.c:1184
> #5  0x0000000000cb5520 in ssa_fixup_template_block (slot=<optimised out>,
>     local_info=0x7fffffed40) at ../../gcc/gcc/tree-ssa-threadupdate.c:1369
> #6  traverse_noresize<ssa_local_info_t*, ssa_fixup_template_block> (
>     argument=0x7fffffed40, this=0x1a21a00) at ../../gcc/gcc/hash-table.h:911
> #7  traverse<ssa_local_info_t*, ssa_fixup_template_block> (
>     argument=0x7fffffed40, this=0x1a21a00) at ../../gcc/gcc/hash-table.h:933
> #8  thread_block_1 (bb=bb@entry=0x7fb7485bc8,
>     noloop_only=noloop_only@entry=true, joiners=joiners@entry=true)
>     at ../../gcc/gcc/tree-ssa-threadupdate.c:1592
> #9  0x0000000000cb5a40 in thread_block (bb=0x7fb7485bc8,
>     noloop_only=noloop_only@entry=true)
>     at ../../gcc/gcc/tree-ssa-threadupdate.c:1629
> ---Type <return> to continue, or q <return> to quit---
> #10 0x0000000000cb6bf8 in thread_through_all_blocks (
>     may_peel_loop_headers=true) at ../../gcc/gcc/tree-ssa-threadupdate.c:2736
> #11 0x0000000000becf6c in (anonymous namespace)::pass_dominator::execute (
>     this=<optimised out>, fun=0x7fb77d1b28)
>     at ../../gcc/gcc/tree-ssa-dom.c:622
> #12 0x00000000009feef4 in execute_one_pass (pass=pass@entry=0x16d1a80)
>     at ../../gcc/gcc/passes.c:2311
> 
> The edge is then deleted much later:
> #3  0x0000000000f858e4 in free_edge (fn=<optimised out>, e=<optimised out>)
>     at ../../gcc/gcc/cfg.c:91
> #4  remove_edge_raw (e=<optimised out>) at ../../gcc/gcc/cfg.c:350
> #5  0x00000000006ec814 in remove_edge (e=<optimised out>)
>     at ../../gcc/gcc/cfghooks.c:418
> #6  0x00000000006ecaec in delete_basic_block (bb=bb@entry=0x7fb74b3618)
>     at ../../gcc/gcc/cfghooks.c:597
> #7  0x0000000000f8d1d4 in try_optimize_cfg (mode=32)
>     at ../../gcc/gcc/cfgcleanup.c:2701
> #8  cleanup_cfg (mode=mode@entry=32) at ../../gcc/gcc/cfgcleanup.c:3028
> #9  0x000000000070180c in cfg_layout_initialize (flags=flags@entry=0)
>     at ../../gcc/gcc/cfgrtl.c:4264
> #10 0x0000000000f7cdc8 in (anonymous
> namespace)::pass_duplicate_computed_gotos::execute (this=<optimised out>,
> fun=0x7fb77d1b28)
>     at ../../gcc/gcc/bb-reorder.c:2622
> #11 0x00000000009feef4 in execute_one_pass (pass=pass@entry=0x16d5680)
>     at ../../gcc/gcc/passes.c:2311
> 
> Adding a call to redirect_edge_var_map_clear in cfg.c (free_edge), does fix
> the ICE in polynom.c, but still leaves many passes ending with the redirect
> map non-empty.

It's also not correct - I think it's supposed to survive multiple
edge redirections / deletions.

That said I think we need to refactor this bookkeeping facility
so something more sensible.

Richard.

Re: [PATCH] Empty redirect_edge_var_map after each pass and function

[Richard Biener]

On Thu, 3 Dec 2015, Richard Biener wrote:

> On Thu, 3 Dec 2015, Alan Lawrence wrote:
> 
> > On 02/12/15 14:13, Jeff Law wrote:
> > > On 12/02/2015 01:33 AM, Richard Biener wrote:
> > > > > Right.  So the question I have is how/why did DOM leave anything in the
> > > > > map.
> > > > > And if DOM is fixed to not leave stuff lying around, can we then assert
> > > > > that
> > > > > nothing is ever left in those maps between passes?  There's certainly no
> > > > > good
> > > > > reason I'm aware of why DOM would leave things in this state.
> > > > 
> > > > It happens not only with DOM but with all passes doing edge redirection.
> > > > This is because the map is populated by GIMPLE cfg hooks just in case
> > > > it might be used.  But there is no such thing as a "start CFG manip"
> > > > and "end CFG manip" to cleanup such dead state.
> > > Sigh.
> > > 
> > > > 
> > > > IMHO the redirect-edge-var-map stuff is just the very most possible
> > > > unclean implementation possible. :(  (see how remove_edge "clears"
> > > > stale info from the map to avoid even more "interesting" stale
> > > > data)
> > > > 
> > > > Ideally we could assert the map is empty whenever we leave a pass,
> > > > but as said it triggers all over the place.  Even cfg-cleanup causes
> > > > such stale data.
> > > > 
> > > > I agree that the patch is only a half-way "solution", but a full
> > > > solution would require sth more explicit, like we do with
> > > > initialize_original_copy_tables/free_original_copy_tables.  Thus
> > > > require passes to explicitely request the edge data to be preserved
> > > > with a initialize_edge_var_map/free_edge_var_map call pair.
> > > > 
> > > > Not appropriate at this stage IMHO (well, unless it turns out to be
> > > > a very localized patch).
> > > So maybe as a follow-up to aid folks in the future, how about a debugging
> > > verify_whatever function that we can call manually if debugging a problem in
> > > this space.  With a comment indicating why we can't call it unconditionally
> > > (yet).
> > > 
> > > 
> > > jeff
> > 
> > I did a (fwiw disable bootstrap) build with the map-emptying code in passes.c
> > (not functions.c), printing out passes after which the map was non-empty
> > (before emptying it, to make sure passes weren't just carrying through stale
> > data from earlier). My (non-exhaustive!) list of passes after which the
> > edge_var_redirect_map can be non-empty stands at...
> > 
> > aprefetch ccp cddce ch ch_vect copyprop crited crited cselim cunroll cunrolli
> > dce dom ehcleanup einline esra fab fnsplit forwprop fre graphite ifcvt
> > isolate-paths ldist lim local-pure-const mergephi oaccdevlow ompexpssa
> > optimized parloops pcom phicprop phiopt phiprop pre profile profile_estimate
> > sccp sink slsr split-paths sra switchconv tailc tailr tracer unswitch
> > veclower2 vect vrm vrp whole-program
> 
> Yeah, exactly my findings...  note that most of the above are likely
> due to cfgcleanup even though it already does sth like
> 
>               e = redirect_edge_and_branch (e, dest);
>               redirect_edge_var_map_clear (e);
> 
> so eventually placing a redirect_edge_var_map_empty () at the end
> of the cleanup_tree_cfg function should prune down the above list
> considerably (well, then assert the map is empty on entry to that
> function of course)

Maybe

Index: gcc/tree-cfgcleanup.c
===================================================================
--- gcc/tree-cfgcleanup.c       (revision 231221)
+++ gcc/tree-cfgcleanup.c       (working copy)
@@ -456,6 +456,7 @@ remove_forwarder_block (basic_block bb)
        }
       else
        s = redirect_edge_and_branch (e, dest);
+      redirect_edge_var_map_clear (s);
 
       if (s == e)
        {

also helps...

Richard.

> 
> > FWIW, the route by which dom added the edge to the redirect map was:
> > #0  redirect_edge_var_map_add (e=e@entry=0x7fb7a5f508, result=0x7fb725a000,
> >     def=0x7fb78eaea0, locus=2147483884) at ../../gcc/gcc/tree-ssa.c:54
> > #1  0x0000000000cccf58 in ssa_redirect_edge (e=e@entry=0x7fb7a5f508,
> >     dest=dest@entry=0x7fb79cc680) at ../../gcc/gcc/tree-ssa.c:158
> > #2  0x0000000000b00738 in gimple_redirect_edge_and_branch (e=0x7fb7a5f508,
> >     dest=0x7fb79cc680) at ../../gcc/gcc/tree-cfg.c:5662
> > #3  0x00000000006ec678 in redirect_edge_and_branch (e=e@entry=0x7fb7a5f508,
> >     dest=<optimised out>) at ../../gcc/gcc/cfghooks.c:356
> > #4  0x0000000000cb4530 in ssa_fix_duplicate_block_edges (rd=0x1a29f10,
> >     local_info=local_info@entry=0x7fffffed40)
> >     at ../../gcc/gcc/tree-ssa-threadupdate.c:1184
> > #5  0x0000000000cb5520 in ssa_fixup_template_block (slot=<optimised out>,
> >     local_info=0x7fffffed40) at ../../gcc/gcc/tree-ssa-threadupdate.c:1369
> > #6  traverse_noresize<ssa_local_info_t*, ssa_fixup_template_block> (
> >     argument=0x7fffffed40, this=0x1a21a00) at ../../gcc/gcc/hash-table.h:911
> > #7  traverse<ssa_local_info_t*, ssa_fixup_template_block> (
> >     argument=0x7fffffed40, this=0x1a21a00) at ../../gcc/gcc/hash-table.h:933
> > #8  thread_block_1 (bb=bb@entry=0x7fb7485bc8,
> >     noloop_only=noloop_only@entry=true, joiners=joiners@entry=true)
> >     at ../../gcc/gcc/tree-ssa-threadupdate.c:1592
> > #9  0x0000000000cb5a40 in thread_block (bb=0x7fb7485bc8,
> >     noloop_only=noloop_only@entry=true)
> >     at ../../gcc/gcc/tree-ssa-threadupdate.c:1629
> > ---Type <return> to continue, or q <return> to quit---
> > #10 0x0000000000cb6bf8 in thread_through_all_blocks (
> >     may_peel_loop_headers=true) at ../../gcc/gcc/tree-ssa-threadupdate.c:2736
> > #11 0x0000000000becf6c in (anonymous namespace)::pass_dominator::execute (
> >     this=<optimised out>, fun=0x7fb77d1b28)
> >     at ../../gcc/gcc/tree-ssa-dom.c:622
> > #12 0x00000000009feef4 in execute_one_pass (pass=pass@entry=0x16d1a80)
> >     at ../../gcc/gcc/passes.c:2311
> > 
> > The edge is then deleted much later:
> > #3  0x0000000000f858e4 in free_edge (fn=<optimised out>, e=<optimised out>)
> >     at ../../gcc/gcc/cfg.c:91
> > #4  remove_edge_raw (e=<optimised out>) at ../../gcc/gcc/cfg.c:350
> > #5  0x00000000006ec814 in remove_edge (e=<optimised out>)
> >     at ../../gcc/gcc/cfghooks.c:418
> > #6  0x00000000006ecaec in delete_basic_block (bb=bb@entry=0x7fb74b3618)
> >     at ../../gcc/gcc/cfghooks.c:597
> > #7  0x0000000000f8d1d4 in try_optimize_cfg (mode=32)
> >     at ../../gcc/gcc/cfgcleanup.c:2701
> > #8  cleanup_cfg (mode=mode@entry=32) at ../../gcc/gcc/cfgcleanup.c:3028
> > #9  0x000000000070180c in cfg_layout_initialize (flags=flags@entry=0)
> >     at ../../gcc/gcc/cfgrtl.c:4264
> > #10 0x0000000000f7cdc8 in (anonymous
> > namespace)::pass_duplicate_computed_gotos::execute (this=<optimised out>,
> > fun=0x7fb77d1b28)
> >     at ../../gcc/gcc/bb-reorder.c:2622
> > #11 0x00000000009feef4 in execute_one_pass (pass=pass@entry=0x16d5680)
> >     at ../../gcc/gcc/passes.c:2311
> > 
> > Adding a call to redirect_edge_var_map_clear in cfg.c (free_edge), does fix
> > the ICE in polynom.c, but still leaves many passes ending with the redirect
> > map non-empty.
> 
> It's also not correct - I think it's supposed to survive multiple
> edge redirections / deletions.
> 
> That said I think we need to refactor this bookkeeping facility
> so something more sensible.
> 
> Richard.
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: [PATCH] Empty redirect_edge_var_map after each pass and function

[Alan Lawrence]

On 03/12/15 12:58, Richard Biener wrote:
> On Thu, 3 Dec 2015, Alan Lawrence wrote:
>
>> On 02/12/15 14:13, Jeff Law wrote:
>>> On 12/02/2015 01:33 AM, Richard Biener wrote:
>>>>> Right.  So the question I have is how/why did DOM leave anything in the
>>>>> map.
>>>>> And if DOM is fixed to not leave stuff lying around, can we then assert
>>>>> that
>>>>> nothing is ever left in those maps between passes?  There's certainly no
>>>>> good
>>>>> reason I'm aware of why DOM would leave things in this state.
>>>>
>>>> It happens not only with DOM but with all passes doing edge redirection.
>>>> This is because the map is populated by GIMPLE cfg hooks just in case
>>>> it might be used.  But there is no such thing as a "start CFG manip"
>>>> and "end CFG manip" to cleanup such dead state.
>>> Sigh.
>>>
>>>>
>>>> IMHO the redirect-edge-var-map stuff is just the very most possible
>>>> unclean implementation possible. :(  (see how remove_edge "clears"
>>>> stale info from the map to avoid even more "interesting" stale
>>>> data)
>>>>
>>>> Ideally we could assert the map is empty whenever we leave a pass,
>>>> but as said it triggers all over the place.  Even cfg-cleanup causes
>>>> such stale data.
>>>>
>>>> I agree that the patch is only a half-way "solution", but a full
>>>> solution would require sth more explicit, like we do with
>>>> initialize_original_copy_tables/free_original_copy_tables.  Thus
>>>> require passes to explicitely request the edge data to be preserved
>>>> with a initialize_edge_var_map/free_edge_var_map call pair.
>>>>
>>>> Not appropriate at this stage IMHO (well, unless it turns out to be
>>>> a very localized patch).
>>> So maybe as a follow-up to aid folks in the future, how about a debugging
>>> verify_whatever function that we can call manually if debugging a problem in
>>> this space.  With a comment indicating why we can't call it unconditionally
>>> (yet).
>>>
>>>
>>> jeff
>>
>> I did a (fwiw disable bootstrap) build with the map-emptying code in passes.c
>> (not functions.c), printing out passes after which the map was non-empty
>> (before emptying it, to make sure passes weren't just carrying through stale
>> data from earlier). My (non-exhaustive!) list of passes after which the
>> edge_var_redirect_map can be non-empty stands at...
>>
>> aprefetch ccp cddce ch ch_vect copyprop crited crited cselim cunroll cunrolli
>> dce dom ehcleanup einline esra fab fnsplit forwprop fre graphite ifcvt
>> isolate-paths ldist lim local-pure-const mergephi oaccdevlow ompexpssa
>> optimized parloops pcom phicprop phiopt phiprop pre profile profile_estimate
>> sccp sink slsr split-paths sra switchconv tailc tailr tracer unswitch
>> veclower2 vect vrm vrp whole-program
>
> Yeah, exactly my findings...  note that most of the above are likely
> due to cfgcleanup even though it already does sth like
>
>                e = redirect_edge_and_branch (e, dest);
>                redirect_edge_var_map_clear (e);
>
> so eventually placing a redirect_edge_var_map_empty () at the end
> of the cleanup_tree_cfg function should prune down the above list
> considerably (well, then assert the map is empty on entry to that
> function of course)
>
>> FWIW, the route by which dom added the edge to the redirect map was:
>> #0  redirect_edge_var_map_add (e=e@entry=0x7fb7a5f508, result=0x7fb725a000,
>>      def=0x7fb78eaea0, locus=2147483884) at ../../gcc/gcc/tree-ssa.c:54
>> #1  0x0000000000cccf58 in ssa_redirect_edge (e=e@entry=0x7fb7a5f508,
>>      dest=dest@entry=0x7fb79cc680) at ../../gcc/gcc/tree-ssa.c:158
>> #2  0x0000000000b00738 in gimple_redirect_edge_and_branch (e=0x7fb7a5f508,
>>      dest=0x7fb79cc680) at ../../gcc/gcc/tree-cfg.c:5662
>> #3  0x00000000006ec678 in redirect_edge_and_branch (e=e@entry=0x7fb7a5f508,
>>      dest=<optimised out>) at ../../gcc/gcc/cfghooks.c:356
>> #4  0x0000000000cb4530 in ssa_fix_duplicate_block_edges (rd=0x1a29f10,
>>      local_info=local_info@entry=0x7fffffed40)
>>      at ../../gcc/gcc/tree-ssa-threadupdate.c:1184
>> #5  0x0000000000cb5520 in ssa_fixup_template_block (slot=<optimised out>,
>>      local_info=0x7fffffed40) at ../../gcc/gcc/tree-ssa-threadupdate.c:1369
>> #6  traverse_noresize<ssa_local_info_t*, ssa_fixup_template_block> (
>>      argument=0x7fffffed40, this=0x1a21a00) at ../../gcc/gcc/hash-table.h:911
>> #7  traverse<ssa_local_info_t*, ssa_fixup_template_block> (
>>      argument=0x7fffffed40, this=0x1a21a00) at ../../gcc/gcc/hash-table.h:933
>> #8  thread_block_1 (bb=bb@entry=0x7fb7485bc8,
>>      noloop_only=noloop_only@entry=true, joiners=joiners@entry=true)
>>      at ../../gcc/gcc/tree-ssa-threadupdate.c:1592
>> #9  0x0000000000cb5a40 in thread_block (bb=0x7fb7485bc8,
>>      noloop_only=noloop_only@entry=true)
>>      at ../../gcc/gcc/tree-ssa-threadupdate.c:1629
>> ---Type <return> to continue, or q <return> to quit---
>> #10 0x0000000000cb6bf8 in thread_through_all_blocks (
>>      may_peel_loop_headers=true) at ../../gcc/gcc/tree-ssa-threadupdate.c:2736
>> #11 0x0000000000becf6c in (anonymous namespace)::pass_dominator::execute (
>>      this=<optimised out>, fun=0x7fb77d1b28)
>>      at ../../gcc/gcc/tree-ssa-dom.c:622
>> #12 0x00000000009feef4 in execute_one_pass (pass=pass@entry=0x16d1a80)
>>      at ../../gcc/gcc/passes.c:2311
>>
>> The edge is then deleted much later:
>> #3  0x0000000000f858e4 in free_edge (fn=<optimised out>, e=<optimised out>)
>>      at ../../gcc/gcc/cfg.c:91
>> #4  remove_edge_raw (e=<optimised out>) at ../../gcc/gcc/cfg.c:350
>> #5  0x00000000006ec814 in remove_edge (e=<optimised out>)
>>      at ../../gcc/gcc/cfghooks.c:418
>> #6  0x00000000006ecaec in delete_basic_block (bb=bb@entry=0x7fb74b3618)
>>      at ../../gcc/gcc/cfghooks.c:597
>> #7  0x0000000000f8d1d4 in try_optimize_cfg (mode=32)
>>      at ../../gcc/gcc/cfgcleanup.c:2701
>> #8  cleanup_cfg (mode=mode@entry=32) at ../../gcc/gcc/cfgcleanup.c:3028
>> #9  0x000000000070180c in cfg_layout_initialize (flags=flags@entry=0)
>>      at ../../gcc/gcc/cfgrtl.c:4264
>> #10 0x0000000000f7cdc8 in (anonymous
>> namespace)::pass_duplicate_computed_gotos::execute (this=<optimised out>,
>> fun=0x7fb77d1b28)
>>      at ../../gcc/gcc/bb-reorder.c:2622
>> #11 0x00000000009feef4 in execute_one_pass (pass=pass@entry=0x16d5680)
>>      at ../../gcc/gcc/passes.c:2311
>>
>> Adding a call to redirect_edge_var_map_clear in cfg.c (free_edge), does fix
>> the ICE in polynom.c, but still leaves many passes ending with the redirect
>> map non-empty.
>
> It's also not correct - I think it's supposed to survive multiple
> edge redirections / deletions.

Really, how? That puts redirect_edge_var_map_clear immediately prior to 
ggc_free; I'd be surprised to see the compiler depending upon pointer equality 
across allocations?! [/me prepares to be surprised.] Note there is also 
redirect_edge_var_map_dup, for moving entries for one edge to another.

I tried adding redirect_var_edge_map_destroy() to cleanup_tree_cfg, I was still 
left with this (shorter) list of phases leaving entries in there:

cddce ch crited cselim cunrolli graphite ifcvt ldist lim local-pure-const 
mergephi parloops phiprop pre profile_estimate sink slsr split-paths switchconv 
unswitch vect whole-program

> That said I think we need to refactor this bookkeeping facility
> so something more sensible.

A structure for each phase that needs it, deallocated at the end of the phase? 
Then if one misses the dealloc, at least you don't mess up the other phases!
However, that looks quite invasive, as you have to pass the map around quite a bit.

So having not seen any *simple* improvements, I'm still inclined to commit the 
original patch...

--Alan

Re: [PATCH] Empty redirect_edge_var_map after each pass and function

[Richard Biener]

On Thu, 3 Dec 2015, Alan Lawrence wrote:

> On 03/12/15 12:58, Richard Biener wrote:
> > On Thu, 3 Dec 2015, Alan Lawrence wrote:
> > 
> > > On 02/12/15 14:13, Jeff Law wrote:
> > > > On 12/02/2015 01:33 AM, Richard Biener wrote:
> > > > > > Right.  So the question I have is how/why did DOM leave anything in
> > > > > > the
> > > > > > map.
> > > > > > And if DOM is fixed to not leave stuff lying around, can we then
> > > > > > assert
> > > > > > that
> > > > > > nothing is ever left in those maps between passes?  There's
> > > > > > certainly no
> > > > > > good
> > > > > > reason I'm aware of why DOM would leave things in this state.
> > > > > 
> > > > > It happens not only with DOM but with all passes doing edge
> > > > > redirection.
> > > > > This is because the map is populated by GIMPLE cfg hooks just in case
> > > > > it might be used.  But there is no such thing as a "start CFG manip"
> > > > > and "end CFG manip" to cleanup such dead state.
> > > > Sigh.
> > > > 
> > > > > 
> > > > > IMHO the redirect-edge-var-map stuff is just the very most possible
> > > > > unclean implementation possible. :(  (see how remove_edge "clears"
> > > > > stale info from the map to avoid even more "interesting" stale
> > > > > data)
> > > > > 
> > > > > Ideally we could assert the map is empty whenever we leave a pass,
> > > > > but as said it triggers all over the place.  Even cfg-cleanup causes
> > > > > such stale data.
> > > > > 
> > > > > I agree that the patch is only a half-way "solution", but a full
> > > > > solution would require sth more explicit, like we do with
> > > > > initialize_original_copy_tables/free_original_copy_tables.  Thus
> > > > > require passes to explicitely request the edge data to be preserved
> > > > > with a initialize_edge_var_map/free_edge_var_map call pair.
> > > > > 
> > > > > Not appropriate at this stage IMHO (well, unless it turns out to be
> > > > > a very localized patch).
> > > > So maybe as a follow-up to aid folks in the future, how about a
> > > > debugging
> > > > verify_whatever function that we can call manually if debugging a
> > > > problem in
> > > > this space.  With a comment indicating why we can't call it
> > > > unconditionally
> > > > (yet).
> > > > 
> > > > 
> > > > jeff
> > > 
> > > I did a (fwiw disable bootstrap) build with the map-emptying code in
> > > passes.c
> > > (not functions.c), printing out passes after which the map was non-empty
> > > (before emptying it, to make sure passes weren't just carrying through
> > > stale
> > > data from earlier). My (non-exhaustive!) list of passes after which the
> > > edge_var_redirect_map can be non-empty stands at...
> > > 
> > > aprefetch ccp cddce ch ch_vect copyprop crited crited cselim cunroll
> > > cunrolli
> > > dce dom ehcleanup einline esra fab fnsplit forwprop fre graphite ifcvt
> > > isolate-paths ldist lim local-pure-const mergephi oaccdevlow ompexpssa
> > > optimized parloops pcom phicprop phiopt phiprop pre profile
> > > profile_estimate
> > > sccp sink slsr split-paths sra switchconv tailc tailr tracer unswitch
> > > veclower2 vect vrm vrp whole-program
> > 
> > Yeah, exactly my findings...  note that most of the above are likely
> > due to cfgcleanup even though it already does sth like
> > 
> >                e = redirect_edge_and_branch (e, dest);
> >                redirect_edge_var_map_clear (e);
> > 
> > so eventually placing a redirect_edge_var_map_empty () at the end
> > of the cleanup_tree_cfg function should prune down the above list
> > considerably (well, then assert the map is empty on entry to that
> > function of course)
> > 
> > > FWIW, the route by which dom added the edge to the redirect map was:
> > > #0  redirect_edge_var_map_add (e=e@entry=0x7fb7a5f508,
> > > result=0x7fb725a000,
> > >      def=0x7fb78eaea0, locus=2147483884) at ../../gcc/gcc/tree-ssa.c:54
> > > #1  0x0000000000cccf58 in ssa_redirect_edge (e=e@entry=0x7fb7a5f508,
> > >      dest=dest@entry=0x7fb79cc680) at ../../gcc/gcc/tree-ssa.c:158
> > > #2  0x0000000000b00738 in gimple_redirect_edge_and_branch (e=0x7fb7a5f508,
> > >      dest=0x7fb79cc680) at ../../gcc/gcc/tree-cfg.c:5662
> > > #3  0x00000000006ec678 in redirect_edge_and_branch
> > > (e=e@entry=0x7fb7a5f508,
> > >      dest=<optimised out>) at ../../gcc/gcc/cfghooks.c:356
> > > #4  0x0000000000cb4530 in ssa_fix_duplicate_block_edges (rd=0x1a29f10,
> > >      local_info=local_info@entry=0x7fffffed40)
> > >      at ../../gcc/gcc/tree-ssa-threadupdate.c:1184
> > > #5  0x0000000000cb5520 in ssa_fixup_template_block (slot=<optimised out>,
> > >      local_info=0x7fffffed40) at
> > > ../../gcc/gcc/tree-ssa-threadupdate.c:1369
> > > #6  traverse_noresize<ssa_local_info_t*, ssa_fixup_template_block> (
> > >      argument=0x7fffffed40, this=0x1a21a00) at
> > > ../../gcc/gcc/hash-table.h:911
> > > #7  traverse<ssa_local_info_t*, ssa_fixup_template_block> (
> > >      argument=0x7fffffed40, this=0x1a21a00) at
> > > ../../gcc/gcc/hash-table.h:933
> > > #8  thread_block_1 (bb=bb@entry=0x7fb7485bc8,
> > >      noloop_only=noloop_only@entry=true, joiners=joiners@entry=true)
> > >      at ../../gcc/gcc/tree-ssa-threadupdate.c:1592
> > > #9  0x0000000000cb5a40 in thread_block (bb=0x7fb7485bc8,
> > >      noloop_only=noloop_only@entry=true)
> > >      at ../../gcc/gcc/tree-ssa-threadupdate.c:1629
> > > ---Type <return> to continue, or q <return> to quit---
> > > #10 0x0000000000cb6bf8 in thread_through_all_blocks (
> > >      may_peel_loop_headers=true) at
> > > ../../gcc/gcc/tree-ssa-threadupdate.c:2736
> > > #11 0x0000000000becf6c in (anonymous namespace)::pass_dominator::execute (
> > >      this=<optimised out>, fun=0x7fb77d1b28)
> > >      at ../../gcc/gcc/tree-ssa-dom.c:622
> > > #12 0x00000000009feef4 in execute_one_pass (pass=pass@entry=0x16d1a80)
> > >      at ../../gcc/gcc/passes.c:2311
> > > 
> > > The edge is then deleted much later:
> > > #3  0x0000000000f858e4 in free_edge (fn=<optimised out>, e=<optimised
> > > out>)
> > >      at ../../gcc/gcc/cfg.c:91
> > > #4  remove_edge_raw (e=<optimised out>) at ../../gcc/gcc/cfg.c:350
> > > #5  0x00000000006ec814 in remove_edge (e=<optimised out>)
> > >      at ../../gcc/gcc/cfghooks.c:418
> > > #6  0x00000000006ecaec in delete_basic_block (bb=bb@entry=0x7fb74b3618)
> > >      at ../../gcc/gcc/cfghooks.c:597
> > > #7  0x0000000000f8d1d4 in try_optimize_cfg (mode=32)
> > >      at ../../gcc/gcc/cfgcleanup.c:2701
> > > #8  cleanup_cfg (mode=mode@entry=32) at ../../gcc/gcc/cfgcleanup.c:3028
> > > #9  0x000000000070180c in cfg_layout_initialize (flags=flags@entry=0)
> > >      at ../../gcc/gcc/cfgrtl.c:4264
> > > #10 0x0000000000f7cdc8 in (anonymous
> > > namespace)::pass_duplicate_computed_gotos::execute (this=<optimised out>,
> > > fun=0x7fb77d1b28)
> > >      at ../../gcc/gcc/bb-reorder.c:2622
> > > #11 0x00000000009feef4 in execute_one_pass (pass=pass@entry=0x16d5680)
> > >      at ../../gcc/gcc/passes.c:2311
> > > 
> > > Adding a call to redirect_edge_var_map_clear in cfg.c (free_edge), does
> > > fix
> > > the ICE in polynom.c, but still leaves many passes ending with the
> > > redirect
> > > map non-empty.
> > 
> > It's also not correct - I think it's supposed to survive multiple
> > edge redirections / deletions.
> 
> Really, how? That puts redirect_edge_var_map_clear immediately prior to
> ggc_free; I'd be surprised to see the compiler depending upon pointer equality
> across allocations?! [/me prepares to be surprised.] Note there is also
> redirect_edge_var_map_dup, for moving entries for one edge to another.
> 
> I tried adding redirect_var_edge_map_destroy() to cleanup_tree_cfg, I was
> still left with this (shorter) list of phases leaving entries in there:
> 
> cddce ch crited cselim cunrolli graphite ifcvt ldist lim local-pure-const
> mergephi parloops phiprop pre profile_estimate sink slsr split-paths
> switchconv unswitch vect whole-program
> 
> > That said I think we need to refactor this bookkeeping facility
> > so something more sensible.
> 
> A structure for each phase that needs it, deallocated at the end of the phase?
> Then if one misses the dealloc, at least you don't mess up the other phases!
> However, that looks quite invasive, as you have to pass the map around quite a
> bit.
> 
> So having not seen any *simple* improvements, I'm still inclined to commit the
> original patch...

Sure, at this stage that's the simplest "solution".

Richard.

Re: [PATCH] Empty redirect_edge_var_map after each pass and function

[Richard Biener]

On Tue, 1 Dec 2015, Alan Lawrence wrote:

> This follows on from discussion at
> https://gcc.gnu.org/ml/gcc-patches/2015-11/msg03392.html
> To recap: Starting in r229479 and continuing until at least 229711, compiling
> polynom.c from spec2000 on aarch64-none-linux-gnu, with options
> -O3 -mcpu=cortex-a53 -ffast-math (on both cross, native bootstrapped, and native
> --disable-bootstrap compilers), produced a verify_gimple ICE after unswitch:
> 
> ../spec2000/benchspec/CINT2000/254.gap/src/polynom.c: In function 'NormalizeCoeffsListx':
> ../spec2000/benchspec/CINT2000/254.gap/src/polynom.c:358:11: error: incompatible types in PHI argument 0
>  TypHandle NormalizeCoeffsListx ( hdC )
>            ^
> long int
> 
> int
> 
> ../spec2000/benchspec/CINT2000/254.gap/src/polynom.c:358:11: error: location references block not in block tree
> l1_279 = PHI <1(28), l1_299(33)>
> ../spec2000/benchspec/CINT2000/254.gap/src/polynom.c:358:11: error: invalid PHI argument
> 
> ../spec2000/benchspec/CINT2000/254.gap/src/polynom.c:358:11: internal compiler error: tree check: expected class 'type', have 'declaration' (namespace_decl) in useless_type_conversion_p, at gimple-expr.c:84
> 0xd110ef tree_class_check_failed(tree_node const*, tree_code_class, char const*, int, char const*)
>         ../../gcc-fsf/gcc/tree.c:9643
> 0x82561b tree_class_check
>         ../../gcc-fsf/gcc/tree.h:3042
> 0x82561b useless_type_conversion_p(tree_node*, tree_node*)
>         ../../gcc-fsf/gcc/gimple-expr.c:84
> 0xaca043 verify_gimple_phi
>         ../../gcc-fsf/gcc/tree-cfg.c:4673
> 0xaca043 verify_gimple_in_cfg(function*, bool)
>         ../../gcc-fsf/gcc/tree-cfg.c:4967
> 0x9c2e0b execute_function_todo
>         ../../gcc-fsf/gcc/passes.c:1967
> 0x9c360b do_per_function
>         ../../gcc-fsf/gcc/passes.c:1659
> 0x9c3807 execute_todo
>         ../../gcc-fsf/gcc/passes.c:2022
> 
> I was not able to reduce the testcase below about 30k characters, with e.g.
> #define T_VOID 0
> .... T_VOID ....
> producing the ICE, but manually changing to
> .... 0 ....
> preventing the ICE; as did running the preprocessor as a separate step, or a
> wide variety of options (e.g. -fdump-tree-alias).
> 
> In the end I traced this to loop_unswitch reading stale values from the edge
> redirect map, which is keyed on 'edge' (a pointer to struct edge_def); the map
> entries had been left there by pass_dominator (on a different function), and by
> "chance" the edge *pointers* were the same as to some current edge_defs (even
> though they pointed to structures created by different allocations, the first
> of which had since been freed). Hence the fragility of the testcase and
> environment.
> 
> While the ICE is prevented merely by adding a call to
> redirect_edge_var_map_destroy at the end of pass_dominator::execute, given the
> fragility of the bug, difficulty of reducing the testcase, and the low overhead
> of emptying an already-empty map, I believe the right fix is to empty the map
> as often as can correctly do so, hence this patch - based substantially on
> Richard's comments in PR/68117.
> 
> Bootstrapped + check-gcc + check-g++ on x86_64 linux, based on r231105; I've
> also built SPEC2000 on aarch64-none-linux-gnu by applying this patch (roughly)
> onto the previously-failing r229711, which also passes aarch64 bootstrap, and
> a more recent bootstrap on aarch64 is ongoing. Assuming/if no regressions there...
> 
> Is this ok for trunk?
> 
> This could also be a candidate for the 5.3 release; backporting depends only on
> the (fairly trivial) r230357.

Looks good to me (for both, but backport only after 5.3 is released).  But
please wait for the discussion with Jeff to settle down.

Thanks,
Richard.
 
> gcc/ChangeLog:
> 
> <DATE>  Alan Lawrence  <alan.lawrence@arm.com>
> 	Richard Biener  <richard.guenther@gmail.com>
> 
> 	* cfgexpand.c (pass_expand::execute): Replace call to
> 	redirect_edge_var_map_destroy with redirect_edge_var_map_empty.
> 	* tree-ssa.c (delete_tree_ssa): Likewise.
> 	* function.c (set_cfun): Call redirect_edge_var_map_empty.
> 	* passes.c (execute_one_ipa_transform_pass, execute_one_pass): Likewise.
> 	* tree-ssa.h (redirect_edge_var_map_destroy): Remove.
> 	(redirect_edge_var_map_empty): New.
> 	* tree-ssa.c (redirect_edge_var_map_destroy): Remove.
> 	(redirect_edge_var_map_empty): New.
> 
> ---
>  gcc/cfgexpand.c | 2 +-
>  gcc/function.c  | 2 ++
>  gcc/passes.c    | 2 ++
>  gcc/tree-ssa.c  | 8 ++++----
>  gcc/tree-ssa.h  | 2 +-
>  5 files changed, 10 insertions(+), 6 deletions(-)
> 
> diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c
> index 1990e10..ede1b82 100644
> --- a/gcc/cfgexpand.c
> +++ b/gcc/cfgexpand.c
> @@ -6291,7 +6291,7 @@ pass_expand::execute (function *fun)
>    expand_phi_nodes (&SA);
>  
>    /* Release any stale SSA redirection data.  */
> -  redirect_edge_var_map_destroy ();
> +  redirect_edge_var_map_empty ();
>  
>    /* Register rtl specific functions for cfg.  */
>    rtl_register_cfg_hooks ();
> diff --git a/gcc/function.c b/gcc/function.c
> index 515d7c0..e452865 100644
> --- a/gcc/function.c
> +++ b/gcc/function.c
> @@ -75,6 +75,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "tree-chkp.h"
>  #include "rtl-chkp.h"
>  #include "tree-dfa.h"
> +#include "tree-ssa.h"
>  
>  /* So we can assign to cfun in this file.  */
>  #undef cfun
> @@ -4798,6 +4799,7 @@ set_cfun (struct function *new_cfun)
>      {
>        cfun = new_cfun;
>        invoke_set_current_function_hook (new_cfun ? new_cfun->decl : NULL_TREE);
> +      redirect_edge_var_map_empty ();
>      }
>  }
>  
> diff --git a/gcc/passes.c b/gcc/passes.c
> index 0e23dcb..ba9bfc2 100644
> --- a/gcc/passes.c
> +++ b/gcc/passes.c
> @@ -2218,6 +2218,7 @@ execute_one_ipa_transform_pass (struct cgraph_node *node,
>    pass_fini_dump_file (pass);
>  
>    current_pass = NULL;
> +  redirect_edge_var_map_empty ();
>  
>    /* Signal this is a suitable GC collection point.  */
>    if (!(todo_after & TODO_do_not_ggc_collect))
> @@ -2370,6 +2371,7 @@ execute_one_pass (opt_pass *pass)
>  		|| pass->type != RTL_PASS);
>  
>    current_pass = NULL;
> +  redirect_edge_var_map_empty ();
>  
>    if (todo_after & TODO_discard_function)
>      {
> diff --git a/gcc/tree-ssa.c b/gcc/tree-ssa.c
> index 02fca4c..ddc7a65 100644
> --- a/gcc/tree-ssa.c
> +++ b/gcc/tree-ssa.c
> @@ -119,10 +119,10 @@ redirect_edge_var_map_vector (edge e)
>  /* Clear the edge variable mappings.  */
>  
>  void
> -redirect_edge_var_map_destroy (void)
> +redirect_edge_var_map_empty (void)
>  {
> -  delete edge_var_maps;
> -  edge_var_maps = NULL;
> +  if (edge_var_maps)
> +    edge_var_maps->empty ();
>  }
>  
>  
> @@ -1128,7 +1128,7 @@ delete_tree_ssa (struct function *fn)
>    fn->gimple_df = NULL;
>  
>    /* We no longer need the edge variable maps.  */
> -  redirect_edge_var_map_destroy ();
> +  redirect_edge_var_map_empty ();
>  }
>  
>  /* Return true if EXPR is a useless type conversion, otherwise return
> diff --git a/gcc/tree-ssa.h b/gcc/tree-ssa.h
> index 3b5bd70..d33eb9c 100644
> --- a/gcc/tree-ssa.h
> +++ b/gcc/tree-ssa.h
> @@ -35,7 +35,7 @@ extern void redirect_edge_var_map_add (edge, tree, tree, source_location);
>  extern void redirect_edge_var_map_clear (edge);
>  extern void redirect_edge_var_map_dup (edge, edge);
>  extern vec<edge_var_map> *redirect_edge_var_map_vector (edge);
> -extern void redirect_edge_var_map_destroy (void);
> +extern void redirect_edge_var_map_empty (void);
>  extern edge ssa_redirect_edge (edge, basic_block);
>  extern void flush_pending_stmts (edge);
>  extern void gimple_replace_ssa_lhs (gimple *, tree);
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: [PATCH] Empty redirect_edge_var_map after each pass and function

[Jeff Law]

On 12/02/2015 01:36 AM, Richard Biener wrote:

>>
>> This could also be a candidate for the 5.3 release; backporting depends only on
>> the (fairly trivial) r230357.
>
> Looks good to me (for both, but backport only after 5.3 is released).  But
> please wait for the discussion with Jeff to settle down.
No need to wait on me.  I think if we want the little debug/verify 
function, that can go in as a follow-up.

jeff