Integrated immediate use patch

[Andrew MacLeod <amacleod at redhat dot com>]

This patch provides integrated immediate use information directly
embedded in the operands.  

I have to re-apply it once Diego's TCB changes are integrated, and do
some final verification.  At the moment, compile time results with
checking disabled are typically within a couple of percent on either
side of neutral. Some things compile a little faster, some a little
slower, but nothing earth shattering.  TCB makes more extensive use of
immediate uses, so maybe we'll see a little bit there. I imagine there
are also tweaks that can be made to existing immediate use applications,
I just did a straightforward conversion on most optimizations.


***  Immediate uses use to be stmt based.  You would ask for all the
immediate uses of a stmt. It would aggregate all the DEFs on the stmt,
subject to an inclusion bitmap. The end result was a list of stmt's
containing uses of the specified defs.
  Now, immediate uses is based on an SSA_NAME.  You simply ask for all
the immediate uses of an SSA_NAME var, and iterate over the uses.  The
iterators return a pointer to each use.
    ie, to change each use of ssa_var to ssa_var_2:

      FOR_EACH_IMM_USE_SAFE (imm_use_p, iterator, ssa_var)
        SET_USE (imm_use_p, ssa_var_2);

There are 2 iterators:

  FOR_EACH_IMM_USE_FAST    
            &
  FOR_EACH_IMM_USE_SAFE

...FAST is used when the immediate uses are not changed, ie you are
looking at the uses, but not setting them.  If They get set, then care
must be taken that things are not changed under the iterators nose, so
use the ...SAFE iterator. 

  The ...SAFE iterator attempts to preserve the sanity of the use list
by moving an iterator element through the use list so insertions and
deletions in the list don't result in invalid pointers.  This is a
little slower, and since it adds an element to the list, this element
must be removed if the loop is terminated early.  A macro is provided
for this, like so:

   FOR_EACH_IMM_USE_SAFE (use_p, iter, var)
     {
       if (var == last_var)
         BREAK_FROM_SAFE_IMM_USE (iter);
       else
         SET_USE (use_p, var2);
     }

There are new checks in verify_ssa which look for invalidity in the
imm_use list as well as forgetting to use this macro to break form the
loop.  verify_ssa ought to trigger if an optimization breaks from the
loop, but doesn't use the macro.  It is safe to simply 'break'; from a
...FAST traverse.


***   In order to have immediate uses available all the time, we no
longer lazily update the operands via calls to get_stmt_operands(). 
Stmts are now updated when they are changed.  If stmt elements are
changed via SET_USE or SET_DEF, no further action need be taken (ie,
those macros take care of whatever updating is required). If changes are
made by manipulating the stmt's tree directly, then a call must be made
to update_stmt() when complete.  

  For the moment, get_stmt_operands() is still present, but its
basically a NOP. With checking enabled, it verifies that the modified
bit is NOT set. (ie, the operands *ought* to be up to date any time we
would have called get_stmt_operands.)  This will not remain in the code
base forever, its just there to verify and catch errors for a while
while we make this transition.


*** useful functions/macros:

-  has_zero_uses (ssa_var) : Returns true if there are no uses of
ssa_var
-  has_single_use (ssa_var) : Returns true if there is only a single use
of an SSA_NAME
-  single_imm_use (ssa_var, use_operand_p *ptr, tree *stmt) : Returns
true if there is only a single use of ssa_var, and also returns the use
pointer and stmt it occurs in in the second and third parameters.
-  num_imm_uses (ssa_var) : Returns the number of immediate uses of
ssa_var. Its better not to use this if you can, because it simply
implements a loop and counts the uses.
- PHI_ARG_INDEX_FROM_USE (use_p) : Given a use within a PHI node, return
the index number for the use.  An assert is triggered if the use ISN'T
located in a PHI node.
- USE_STMT (use_p) : Return the stmt a use occurs in.


Note that PHI_ARG_INDEX_FROM_USE and USE_STMT apply to *all*
use_operand_p's... not just the ones returned from IMM_USE iterators.



Other notable changes:

  - there is a new tree-dump option  "stmtaddr"  which prints the
address of a stmt just before the stmt in listings.  I have found this
invaluable.

  - modify_stmt() has been changed to update_stmt() to better represent
its new role.  The operands are processed immediately upon calling
update_stmt().

  - There are a couple of optimizations, (alias analysis and DOM) which
require the operands to be in an non-updated state for extended
periods.  For these, the routine mark_stmt_modified() is still
available, and at the end of the optimization, a loop over the IL is
performed calling update_stmt_if_modified().  Typically we want to avoid
this type of thing, and we might be able to do so in both these
optimizations, I just don't understand them well enough to spend the
time trying to figure it out.  These routines can also be used to in
other shorter contexts, such as in tree-complex.

  - verify_ssa is now called after every pass in which the ssa property
is available. We may want to trim this down a bit in the future, but
early on its good for catching anything that goes wrong with imm_uses.

  - uses are NOT put into the immediate use list until they are actually
inserted into the instruction stream. 
  
  - The macros PHI_ARG_DEF_TREE and PHI_RESULT_TREE should *not* be used
by anyone. they manipulate the PHI tree directly.  One should rather use
SET_USE and SET_DEF on the results of PHI_ARG_DEF_PTR and
PHI_RESULT_PTR. 

I will supply a new patch next week after TCB is in and I have updated
to match.

Andrew
----------------------------------------------------------------

Attachment: CHANGE
Description: Text document

Attachment: immuse.diff
Description: Text document