[tcb] Incremental SSA updates

[Diego Novillo <dnovillo at redhat dot com>]

This patch replaces calls to rewrite_ssa_into_ssa with a new
incremental SSA updating mechanism.  This work is a combination
of the SSA updating I had to implement for VRP and Zdenek's work
on ssaupdate-branch.

This is essentially a helper function for passes that need to
replicate code (jump threading, loop transformations) or insert
new IL based on existing code (VRP).  The basic idea is that the
caller registers name mappings between new and old SSA names.

For instance, when creating a duplicate BB_DUP of a basic block
BB, all the names defined in BB need to get new names in BB_DUP
and some/all of the uses reached by the old definitions in BB
should now be reached by the new names in BB_DUP.

All the mappings between new and old names are registered in an
internal table.  The notation N_i -> O_j means that name N_i
replaces name O_j.  Once all the required replacements are
registered, a call to update_ssa does all the actual replacement
work.

There are two ways of creating such mappings:

- When copying statements, all the definitions in the newly
  copied statement can be updated with a call to
  create_new_def_for.  This replaces the existing definition O_j
  with a newly created name N_i and creates the mapping N_i -> O_j.
  This is the most common situation and is used by the jump
  threader and all the loop manipulation functions implicitly
  when they call copy_bbs.

- When creating new statements, the caller can register a new
  name mapping calling register_new_name_mapping.  This is what
  VPR uses after inserting ASSERT_EXPRs in the code.

The call to update_ssa is no more than a fancy search and replace
mechanism.  It first figures out the region of the CFG that needs
to be updated.  For that, we figure out which basic blocks
generate the old and new names that have been registered and
compute the nearest common dominator of all those blocks.

In most situations, the insertion of a new name N_i requires us
to insert new PHI nodes for the old name O_j replaced by it.
This happens when uses of O_j downstream from the new N_i are
reached by both O_j and N_i.  This typically happens in the jump
threader and loop transformations.  But not in passes like VRP
(although Kazu tells me that VRP ought to insert PHI nodes to
help jump threading, Kazu?).

In cases where we need to insert PHI nodes, then we do the usual
computation of IDF (iterated dominance frontier) and insert PHI
nodes there.  With the additional pruning that we are only
interested in IDF blocks inside the region we are to update.

Currently the pass is mostly compile time neutral (there's a .5%
slow down) but there are more speedups coming, so in the end this
should be faster than what we have now.  This is one of the first
things that I'll merge into mainline in a few days because it
affects the most code.

Note: this patch adds #if 0 around the ssa-into-ssa code because
otherwise the patch would've been harder to read.  I'll
physically remove that code in a subsequent patch.

Bootstrapped and tested x86, x86_64, ppc and ia64.


Diego.

Attachment: 20050318-incr-ssa.diff.gz
Description: GNU Zip compressed data