Avoid creating irreducible loops with threading jumps

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

This patch avoids creation of irreducible regions when threading jumps.

As I mentioned a while back, the way to do this without being overly
conservative is to have DOM record jump threading possibilities, then
let tree-ssa-threadupdate decide if a particular jump threading request
should be honored or not.

Other more simple approaches such as never threading across a loop entry
block are far too restrictive.  ie, it's pretty common to see code like


if (cond)
   set x;

for (...; cond; ...)
  use x

It is imperative that we turn that into

 if (cond)
   {
      set x
      do {
         use x;
      } while (cond)
   }

It's critical because if we don't make that kind of transformation, then
we may get bogus "x might be used uninitialized" warnings.

By deferring the question about whether or not it is wise to thread
through a loop entry block until we have seen all the jump threading
requests allows us to make better decisions.

The enterprising hacker could speed this up with a few changes.

  1. The loop discovery code actually inserts forwarder blocks in the
     CFG.  GRRRR.  We need to prune out those blocks after we have
     discovered the loops.  This results in a lot more calls to
     cleanup_tree_cfg than are strictly necessary.  Breaking out
     the code to remove forwarder blocks might be wise.

  2. We could reduce the frequency of rediscovering loops by finding
     a way to keep EDGE_LOOP_EXIT after threading to a loop exit edge.
     This may or may not be a hard problem.

  3. Similarly, if we could find a way to keep EDGE_DFS_BACK up-to-date,
     then we could avoid recomputing that all the time as well.


We're probably going to see a net slowdown of ~1% for this patch
as-is (and another percent for the next and last in this series).  I'll
be working on recovering more of the compile-time performance drops
once I install the final patch.

Attachment: PPP
Description: Text document