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

[Alan Lawrence <alan.lawrence@arm.com>]

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