Fix O(region-size) unwind in VN
authorRichard Biener <rguenther@suse.de>
Tue, 9 Feb 2021 10:59:06 +0000 (11:59 +0100)
committerRichard Biener <rguenther@suse.de>
Tue, 9 Feb 2021 12:06:55 +0000 (13:06 +0100)
commit396cc31317ebad416e234dfa5f85d42585d32437
tree90973acdc77a92ed5a5630f73b6b0075c6b4e310
parente14ea108faa6eba6a60a45ff0ca3099ce6ae45c2
Fix O(region-size) unwind in VN

This fixes the currently O(region-size) unwinding of avail info
to be O(unwind-size) by tracking a linked-list stack of pushed
avails.  This reduces the compile-time spent in complete unrolling
for WRF.

2021-02-09  Richard Biener  <rguenther@suse.de>

PR tree-optimization/98863
* tree-ssa-sccvn.h (vn_avail::next_undo): Add.
* tree-ssa-sccvn.c (last_pushed_avail): New global.
(rpo_elim::eliminate_push_avail): Chain pushed avails.
(unwind_state::avail_top): Add.
(do_unwind): Rewrite unwinding of avail entries.
(do_rpo_vn): Initialize last_pushed_avail and
avail_top of the undo state.
gcc/tree-ssa-sccvn.c
gcc/tree-ssa-sccvn.h