[PATCH][RFC] More update-ssa speedup

Jeff Law jeffreyalaw@gmail.com
Thu Jul 7 14:29:09 GMT 2022



On 7/7/2022 7:33 AM, Richard Biener via Gcc-patches wrote:
> When we do TODO_update_ssa_no_phi we already avoid computing
> dominance frontiers for all blocks - it is worth to also avoid
> walking all dominated blocks in the update domwalk and restrict
> the walk to the SEME region with the affected blocks.  We can
> do that by walking the CFG in reverse from blocks_to_update to
> the common immediate dominator, marking blocks in the region
> and telling the domwalk to STOP when leaving it.
>
> For an artificial testcase with N adjacent loops with one
> unswitching opportunity that takes the incremental SSA updating
> off the -ftime-report radar:
>
>   tree loop unswitching              :  11.25 (  3%)   0.09 (  5%)  11.53 (  3%)    36M (  9%)
>   `- tree SSA incremental            :  35.74 (  9%)   0.07 (  4%)  36.65 (  9%)  2734k (  1%)
>
> improves to
>
>   tree loop unswitching              :  10.21 (  3%)   0.05 (  3%)  11.50 (  3%)    36M (  9%)
>   `- tree SSA incremental            :   0.66 (  0%)   0.02 (  1%)   0.49 (  0%)  2734k (  1%)
>
> for less localized updates the SEME region isn't likely constrained
> enough so I've restricted the extra work to TODO_update_ssa_no_phi
> callers.
>
> Bootstrap & regtest running on x86_64-unknown-linux-gnu.
>
> It's probably the last change that makes a visible difference for
> general update-ssa and any specialized manual updating that would be
> possible as well would not show up in better numbers than above
> (unless I manage to complicate the testcase more).
>
> Comments?
>
> Thanks,
> Richard.
>
> 	* tree-into-ssa.cc (rewrite_mode::REWRITE_UPDATE_REGION): New.
> 	(rewrite_update_dom_walker::rewrite_update_dom_walker): Update.
> 	(rewrite_update_dom_walker::m_in_region_flag): New.
> 	(rewrite_update_dom_walker::before_dom_children): If the region
> 	to update is marked, STOP at exits.
> 	(rewrite_blocks): For REWRITE_UPDATE_REGION mark the region
> 	to be updated.
> 	(dump_update_ssa): Use bitmap_empty_p.
> 	(update_ssa): Likewise.  Use REWRITE_UPDATE_REGION when
> 	TODO_update_ssa_no_phi.
> 	* tree-cfgcleanup.cc (cleanup_tree_cfg_noloop): Account
> 	pending update_ssa to the caller.
Overall concept seems quite reasonable to me -- it also largely mirrors 
ideas I was exploring for incremental DOM many years ago.

Jeff


More information about the Gcc-patches mailing list