Jump threading as a subroutine, removal of DOM iteration

[Jeffrey A Law <law at redhat dot com>]

I've been working over the last many months to rip bits out of
DOM which have better implementations elsewhere in the SSA
optimization pipeline.

The current target is removal of the DOM VRP code; it's mostly
redundant with the tree-vrp.c code -- especially with the various
small improvements that have been made to tree-vrp.c over the last
couple months.

The three major problems with removing the DOM VRP code are:

  1. DOM's VRP data is often used for threading jumps.

  2. A significant number of VRP opportunities are exposed
     by other optimizations after tree-vrp's VRP implementation
     has been run.

  3. Compile-time performance -- believe it or not DOM is actually
     quite efficient.


The first thing this patch does is make jump threading a shared
module that can be used by more than one optimizer.  This turned
out to be rather simple.  There's a callback function that allows
a consumer of the threading module to use pass-specific data to
simplify statements.  [ Yes, there's a PR which should be fixed by
this change, I'll be updating the jump threading PRs shortly. ]

This patch adds a second pass of tree-vrp.c late in the SSA
optimization pipeline.   The goal (of course) is to pick up the
numerous VRP opportunities exposed by the other optimizers in
the SSA pipeline.  This has a secondary long term effect in that
we depend less on DOM for constant propagation.

The other significant change is DOM no longer iterates when it
finds jump threading opportunities.  Most of the secondary 
optimization opportunities we wanted to pick up via iteration
we get simply because tree-vrp threads many jumps before DOM runs
and thus exposes a significant number of the secondary optimization
opportunities to DOM.


Overall this is a small compile-time performance win.  Not huge,
less than 1%, but it's definitely not in the noise.

We do lose a small number of jump threading optimizations due to this
change.  They fall into two rough categories.

  1. A very small number are missed because we're not iterating.  ie,
     VRP exposes redundancies, which in turn expose new VRP
     opportunties, which in turn expose new redundancies, repeat.

  2. A larger number are missed because tree-vrp.c prunes ASSERT_EXPR
     locations a little too aggressively.   There's a comment in
     tree-vrp.c which touches on this issue.  I don't know if it's
     worth addressing yet.

Next on the hit list is DOM's null pointer check elimination code
which is just a very special subcase of VRP.

Bootstrapped and regression tested on i686-pc-linux-gnu.

Attachment: QQQ
Description: Text document