Re: [PATCH] Fix compile/memory hog in the combiner (PR rtl-optimization/69592)

[Jakub Jelinek <jakub@redhat.com>]

On Tue, Feb 02, 2016 at 12:50:39AM +0100, Bernd Schmidt wrote:
> On 02/01/2016 09:34 PM, Jakub Jelinek wrote:
> >On the following testcase we completely uselessly consume about 5.5GB
> >of RAM and lots of compile time.  The problem is the code to avoid
> >exponential behavior of nonzero_bits/num_sign_bit_copies on binary
> >arithmetics rtxes, which causes us to recurse even when handling
> >of those rtxes is going to ignore those arguments.
> >So, this patch limits those only to the cases where we are going
> >to recurse on both arguments, for rtxes where we don't look at arguments
> >at all or where we only recurse on a single arguments it doesn't make
> >sense.  On the testcase, one of the rtxes where the new predicates
> >return false but ARITHMETIC_P is true, is COMPARE, in particular
> >(compare:CCC (plus (x) (y)) (x)), where it is known even without
> >looking at the operands that only one bit is possibly non-zero and
> >number of sign bit copies is always 1.  But without the patch we
> >needlessly recurse on x, which is set by another similar operation etc.
> 
> Hmm, so the code we have to eliminate performance problems is itself causing
> them?

Yes.

> I don't see any code handling COMPARE in nonzero_bits1, only the various
> EQ/NE/etc. codes.

Right.

> I think I have a slight preference for listing the cases where we know we
> can avoid the exponential behaviour workaround - i.e. just test for compares
> and return false for them. Otherwise someone might add another of the
> arithmetic codes to nonzero_bits without noticing they have to adjust this
> function as well.

The problem is that there are more codes that aren't handled and thus
listing those that need to be handled is shorter and IMO more maintainable.
There are 32 ARITHMETIC_P codes, and nonzero_bits1 handles by recursing on
both operands 14 of them, and num_signed_bit_copies1 only 10.

I wonder if it wouldn't be better to pass around some structure, containing
for the common case fixed size cache and perhaps fall back to hash_map if
there are more calls to cache than that.  Plus perhaps a recursion depth, so
that we avoid other pathological cases.

	Jakub