Repost: RFA: re-instate struct_equiv code

[Kenneth Zadeck]

Daniel Berlin wrote:
> Bernd Schmidt wrote:
>   
>> Bernd Schmidt wrote:
>>     
>>> What we must do is ensure that we can rely on life information in
>>> struct_equiv_init by making all transformations done during
>>> try_optimize_cfg keep register life information intact.  This seems to
>>> be true for things like merge_blocks etc.
>>>       
>> I found one that doesn't.  Replacing condjumps with unconditional jumps
>> with try_redirect_by_replacing_jump can kill flag registers.
>>
>>     
> I still think the idea above is a losing proposition.
>
> Your choices are
> 1. Make it quite slow in some cases because each life update can change
> liveness in a large number of blocks. (This is just a fact of liveness)
> 2. Make the liveness information "fast" but imprecise.
>
> Neither of these is a good option.
>
> Why doesn't the struct-equiv code run a single time in a separate pass
> or something, instead of inserting stuff into cleanup_cfg?
>
> I highly doubt it needs to be run 50 or 60 times.
>
> --Dan
>   
Let me add to what Danny has said: It is quite difficult to make
delete assignments of variables and then resolve the live variable
data flow equations.  (What I am going to say also applies to general
changes to the control flow graph and other data flow problems but is
easier to understand with live variables.)

You either end up having to analyze the control flow graph to predict
the places where the 1 bit should be deleted (Danny's #1), or you end
up with too many places that have 1 bits (Danny's point #2).  It is
also possible to have a third outcome, you end up with no enough bits
turned on, in which case the solution is wrong. 

The problem is that there is no easy way to tell which of the 1 bits
came from the assignment being deleted and which came from some other
assignment.  This is not a problem that you are going to see addressed
in the near future or even at all.  Over the last 25 years there have
been a lot of attempts to do incremental data flow, but I would
suggest implementing any of them (my own phd thesis included).  The
algorithms are complex to implement and do not do much better than
starting from scratch.

GCC's current implementation of flow implements all three
possibilities.  The reason that we do not see more bugs is that we do
not make very good use of the information and despite having a general
(and generally incorrect) incremental implementation, we overcall it
enough to be at least generally be correct.

We got rid of the incremental interface in the new df.  All that you
can do, is specify the set of blocks that need to be rescanned and the
solution is recomputed from scratch.  This is fine for the style of
programming where you compute the dataflow and process the entire
function (or a region) and then possibly rerun again to get the
secondary effects.  But this will be too slow for the fine grained
transformation and reanalysis that you want to do.

The only data structures that support this kind of fine grained
transformation and reanalyis is SSA form and this is not available at
the RTL level.

Danny and I hope to replace all of the dataflow with df.   While df's
interface is likely to broaden over time, incremental reanalysis is
unlikely to be one of the features because there are no good
algorithms to put behind the interfaces. 

I would strongly encourage you to rethink your problem so that it fits
into a framework where you analyze the whole program, make as many
transformations as you can given the information and then repeat.  If
you want Danny or myself to help, we will be happy to do so.  But what
you are seeing is the tip of the iceberg. 

Kenny