[RFC] Fix PR63155 (some more)

The second testcase in the above PR runs into our O(N) bitmap element
search limitation and spends 8s (60%) of the compile-time in the SSA propagator
engine (when optimizing).  The patch improves that to 0.9s (15%).  For the 
first testcase it isn't that bad but still the patch improves CCP from 36% to 
14%.

The "solution" is to use sbitmap instead of a bitmap to avoid
the linearity when doing add_ssa_edge.  We pay for that (but not
actually with the testcases) with a linear-time bitmap_first_set_bit
in process_ssa_edge_worklist.  I do not (yet...) have a testcase
that overall gets slower with this approach.  I suppose using
std::set<int> would "solve" the complexity issue but we'd pay
back with horribly inefficient memory use.  Similarly with
our sparse bitmap implementation which lacks an ordered
first_set_bit (it only can get any set bit fast, breaking optimal
iteration order).

If we'd only had a O(log n) search sparse bitmap implementation ...
(Steven posted patches to switch bitmap from/to such one but IIRC
that at least lacked bitmap_first_set_bit).

Bootstrapped and tested on x86_64-unknown-linux-gnu.

OK for trunk?

Thanks,
Richard.

2018-09-19  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/63155
	* tree-ssa-propagate.h
	(ssa_propagation_engine::process_ssa_edge_worklist): Change
	prototype.
	* tree-ssa-propagate.c (ssa_edge_worklist): Turn into an sbitmap.
	(add_ssa_edge): Adjust.
	(ssa_propagation_engine::process_ssa_edge_worklist): If there
	was nothing to do return false.
	(ssa_prop_init): Allocate and clear ssa_edge_worklist.
	(ssa_prop_fini): Adjust.
	(ssa_propagation_engine::ssa_propagate): Elide the check
	for an empty ssa_edge_worklist by using the
	process_ssa_edge_worklist return value.

On Wed, Sep 19, 2018 at 03:06:30PM +0200, Richard Biener wrote:
> 
> The second testcase in the above PR runs into our O(N) bitmap element
> search limitation and spends 8s (60%) of the compile-time in the SSA propagator
> engine (when optimizing).  The patch improves that to 0.9s (15%).  For the 
> first testcase it isn't that bad but still the patch improves CCP from 36% to 
> 14%.
> 
> The "solution" is to use sbitmap instead of a bitmap to avoid
> the linearity when doing add_ssa_edge.  We pay for that (but not
> actually with the testcases) with a linear-time bitmap_first_set_bit
> in process_ssa_edge_worklist.  I do not (yet...) have a testcase

Perhaps you could remember the first set bit number in an integral variable
next to the bitmap.  On bitmap_set_bit this would be just a comparison +
conditional update, in simulate_stmt it would be again conditional on
clearing the first set bit and in that case it could start from that bit
onwards rather than from the beginning (EXECUTE_IF_SET_IN_BITMAP), similarly
in process_ssa_edge_worklist (non-conditional in that case, we are always
clearing the first bit).  Or instead of tracking exact first bit track
it lazily, i.e. just remember the smallest bitnum we've set and in
process_ssa_edge_worklist don't use bitmap_first_set_bit, but walk from
that minimum using EXECUTE_IF_SET_IN_BITMAP and update the minimum to
whatever we've found.

Similarly, empty_p can be done linearly by keeping on the side the count of
set bits and updating it on set_bit when previously not set, as well on
clear_bit.

	Jakub

On Wed, 19 Sep 2018, Jakub Jelinek wrote:

> On Wed, Sep 19, 2018 at 03:06:30PM +0200, Richard Biener wrote:
> > 
> > The second testcase in the above PR runs into our O(N) bitmap element
> > search limitation and spends 8s (60%) of the compile-time in the SSA propagator
> > engine (when optimizing).  The patch improves that to 0.9s (15%).  For the 
> > first testcase it isn't that bad but still the patch improves CCP from 36% to 
> > 14%.
> > 
> > The "solution" is to use sbitmap instead of a bitmap to avoid
> > the linearity when doing add_ssa_edge.  We pay for that (but not
> > actually with the testcases) with a linear-time bitmap_first_set_bit
> > in process_ssa_edge_worklist.  I do not (yet...) have a testcase
> 
> Perhaps you could remember the first set bit number in an integral variable
> next to the bitmap.  On bitmap_set_bit this would be just a comparison +
> conditional update, in simulate_stmt it would be again conditional on
> clearing the first set bit and in that case it could start from that bit
> onwards rather than from the beginning (EXECUTE_IF_SET_IN_BITMAP), similarly
> in process_ssa_edge_worklist (non-conditional in that case, we are always
> clearing the first bit).  Or instead of tracking exact first bit track
> it lazily, i.e. just remember the smallest bitnum we've set and in
> process_ssa_edge_worklist don't use bitmap_first_set_bit, but walk from
> that minimum using EXECUTE_IF_SET_IN_BITMAP and update the minimum to
> whatever we've found.

I thought about that but as you say it's easily invalidated and we can
only optimize the searching start point.  So it felt somewhat like
a hack ;)

I can still do that if you think that otherwise using an sbitmap
is fine (I'm not 100% convinced about that yet).

> Similarly, empty_p can be done linearly by keeping on the side the count of
> set bits and updating it on set_bit when previously not set, as well on
> clear_bit.

I elided empty_p by re-using the fact that bitmap_first_set_bit
already has to do the walk (and may fail).  Of course using a 
on-the-side count might be more optimal (I was wondering why
sbitmap itself didn't have that).

I wonder if reviving Stevens [patch][RFC] bitmaps as lists *or* trees
makes more sense so we can turn this kind of random-access bitmaps
to tree view.

Richard.

On Wed, Sep 19, 2018 at 3:06 PM Richard Biener wrote:
> If we'd only had a O(log n) search sparse bitmap implementation ...
> (Steven posted patches to switch bitmap from/to such one but IIRC
> that at least lacked bitmap_first_set_bit).

But bitmap_first_set_bit would be easy to implement. Just take the
left-most node of the splay tree.

Actually all bit-tests would be easy to implement. It's only
enumeration and set operations on the tree-views that would be
complicated fluff (easier to "switch views" than re-implement).

Impressive that you remember >5yr old patches like that ;-)

Ciao!
Steven

On Wed, 19 Sep 2018, Steven Bosscher wrote:

> On Wed, Sep 19, 2018 at 3:06 PM Richard Biener wrote:
> > If we'd only had a O(log n) search sparse bitmap implementation ...
> > (Steven posted patches to switch bitmap from/to such one but IIRC
> > that at least lacked bitmap_first_set_bit).
> 
> But bitmap_first_set_bit would be easy to implement. Just take the
> left-most node of the splay tree.
> 
> Actually all bit-tests would be easy to implement. It's only
> enumeration and set operations on the tree-views that would be
> complicated fluff (easier to "switch views" than re-implement).
> 
> Impressive that you remember >5yr old patches like that ;-)

;)

Well, it's still useful (but obviously doesn't apply).  Not sure
iff the worst-case behavior of splay-trees makes it a pointless
exercise though ;)

Richard.

On Wed, 19 Sep 2018, Richard Biener wrote:

> 
> The second testcase in the above PR runs into our O(N) bitmap element
> search limitation and spends 8s (60%) of the compile-time in the SSA propagator
> engine (when optimizing).  The patch improves that to 0.9s (15%).  For the 
> first testcase it isn't that bad but still the patch improves CCP from 36% to 
> 14%.
> 
> The "solution" is to use sbitmap instead of a bitmap to avoid
> the linearity when doing add_ssa_edge.  We pay for that (but not
> actually with the testcases) with a linear-time bitmap_first_set_bit
> in process_ssa_edge_worklist.  I do not (yet...) have a testcase
> that overall gets slower with this approach.  I suppose using
> std::set<int> would "solve" the complexity issue but we'd pay
> back with horribly inefficient memory use.  Similarly with
> our sparse bitmap implementation which lacks an ordered
> first_set_bit (it only can get any set bit fast, breaking optimal
> iteration order).
> 
> If we'd only had a O(log n) search sparse bitmap implementation ...
> (Steven posted patches to switch bitmap from/to such one but IIRC
> that at least lacked bitmap_first_set_bit).
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> 
> OK for trunk?

So it turns out that while the bitmap data structure isn't optimal
the issue with the testcase is that we end up with a full-set-universe
for the SSA worklist mostly because we are queueing PHIs via uses
on backedges that are not yet executable (so we'd re-simulate the PHI
anyway once that became excutable - no need to set the individual bits).

So I'm testing the following instead.

Bootstrap & regtest running on x86_64-unknown-linux-gnu.

Richard.

2018-09-20  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/63155
	* tree-ssa-propagate.c (add_ssa_edge): Avoid adding PHIs to
	the worklist when the edge of the respective argument isn't
	executable.

Index: gcc/tree-ssa-propagate.c
===================================================================
--- gcc/tree-ssa-propagate.c	(revision 264438)
+++ gcc/tree-ssa-propagate.c	(working copy)
@@ -168,10 +168,18 @@ add_ssa_edge (tree var)
   FOR_EACH_IMM_USE_FAST (use_p, iter, var)
     {
       gimple *use_stmt = USE_STMT (use_p);
+      basic_block use_bb = gimple_bb (use_stmt);
 
       /* If we did not yet simulate the block wait for this to happen
          and do not add the stmt to the SSA edge worklist.  */
-      if (! (gimple_bb (use_stmt)->flags & BB_VISITED))
+      if (! (use_bb->flags & BB_VISITED))
+	continue;
+
+      /* If this is a use on a not yet executable edge do not bother to
+	 queue it.  */
+      if (gimple_code (use_stmt) == GIMPLE_PHI
+	  && !(EDGE_PRED (use_bb, PHI_ARG_INDEX_FROM_USE (use_p))->flags
+	       & EDGE_EXECUTABLE))
 	continue;
 
       if (prop_simulate_again_p (use_stmt)