Possible g77 bug

[Craig Burley]

>One of my co-workers gave me the following piece of code which he was
>trying to compile on our alpha-linux box using egcs-1.0.3.  When we try to
>compile it, the compilation process never reaches the end. No errors or
>warnings are given.  I have tried compiling with egcs-1.0.2 on the same
>machine with the same result.  It *does* compile properly with egcs-1.0.2
>on an MIPS machine.
>
>If someone else is using egcs on alpha-linux, then perhaps they can see if
>they get the same result.  If it is just something screwed up on my end, I
>am sorry for the inconvenience.

This is likely to be a known performance problem in some versions
of g77 (really the gcc back end).

If I'm right, you won't see the problem in g77 0.5.21 or 0.5.22, but
will see it return in g77 0.5.23 (since it'll be based on an unpatched
gcc 2.8.1) and in any current version of egcs.

The patch I wrote to solve the problem in gcc 2.7.2.3 for g77's use
wasn't ideal, so I held off trying to get it into egcs or gcc.

Since then, I've discovered a related problem that egcs 1.0.x has
but gcc 2.8.1 and egcs 1.1-in-progress does not, and in looking
into how it was fixed, I've noticed that the back end provides a
much nicer way to solve the g77 problem stimulated by code like
yours than I'd used before.

So, if nobody else gets to it before I do, I'll get to it within a
few weeks (surely in time for egcs 1.1 anyway).

In the meantime, here's what is needed.

In safe_from_p(), a recursive descent is done on the supplied tree.
If there are lots of occurrences of even a few SAVE_EXPR's, they'll
each be recursively descended upon as if they were each unique,
causing a combinatorial explosion, and hence long compile times.

(The compile *will* finish, you just have to be very patient.)

contains_placeholder_p() has a similar problem.  To avoid it, it
sets a bit in the SAVE_EXPR tree node before recursively invoking
on the tree.  That bit inhibits the recursive invoke when it sees
the same SAVE_EXPR node.  Of course, it unsets the bit afterwards.
(I forget what test case stimulated the bug in contains_placeholder_p
offhand, but it was a recent report somewhere, IIRC.)

safe_from_p() probably can't use that same bit, but it has worked
okay for g77 0.5.22 to rewrite the SAVE_EXPR code with an ERROR_MARK
one, so doing that instead, and restoring it, and making sure that
an ERROR_MARK node returns "safe" as well, should be sufficient to
fix this problem.

(In 0.5.22 I covered the whole breadth of the problem so same-depth-
but-identical SAVE_EXPR's were explored only once.  That required
keeping track of where the rewrites of the code value were done, so
as to undo them.  I like the contains_placeholder_p() solution better,
since it reduces the most difficult aspects of the combinatorial
explosion, without the need for a separate array to track rewrites,
or even a helper static function, etc.  Even if the same SAVE_EXPR
is explored multiple times, that multiple is likely to be two or
three, which isn't noticably worse than one, the number for my
original solution.  Which, by the way, can be found in the
f/gbe/2.7.2.3.diff patch provided with g77-0.5.22.tar.gz at a GNU
location near you.  :)

        tq vm, (burley)