[PATCH]: Move linear loop changes from lno to mainline

[Daniel Berlin <dberlin at dberlin dot org>]

This moves most (everything but sebastian's data dependence changes) from 
LNO to the mainline.
This includes
1. fixes for detecting and handling imperfect nests in easy cases.
2. an algorithmic fix to the broken replacement 
algorithm in lambda-code
3. not doing anything when the optimal determined transform is the 
identity transform.
4. A small amount of cleanup and refactoring.

One Sebastian returns at the end of next week (he's on his way back to 
france, via vacation) he'll move his data dependence changes to the 
mainline.  Mark, i can  attempt to merge his changes now if you don't want 
to wait that long, but there are some differences between mainline and 
lno so it's not just a straight merge (i attempted it the other day), and 
i'd rather not screw it  up.

In fact, i'd rather spend the time trying to get some linear loop tests 
into our testing infrastructure, since right now, we only have 
compile-time tests.

Bootstrapped and regtested on i686-pc-linux-gnu.

Okay for mainline?

(Changelog is also in the patch, in case this one is a bit mangled. since 
my mailer screws up read-in patches, i've attached the actual patch + 
Changelog in non-mangled form).

2004-09-15  Daniel Berlin  <dberlin@dberlin.org>

        * cfgloop.h (duplicate_loop):  Add prototype.
        * cfgloopmanip.c (duplicate_loop): Make non-static.
        * lambda-code.c (perfect_nestify): Factor out test whether
        we can handle this loop into separate function.
        Call it.
        (can_convert_to_perfect_nest): New function.
        (replace_uses_of_x_with_y): Add modify_stmt call.
        * tree-loop-linear.c (linear_transform_loops): Call
        rewrite_into_loop_closed_ssa and free_df.

2004-09-13  Daniel Berlin  <dberlin@dberlin.org>

        * lambda-code.c (invariant_in_loop): is_gimple_min_invariant is
        loop invariant as well.
        (perfect_nestify): new function.
        (gcc_loop_to_lambda_loop): New parameters to track lower bounds,
        upper bounds, and steps.
        Set outerinductionvar properly.
        (gcc_loopnest_to_lambda_loopnest): Add loops and need_perfect
        parameters.
        Return NULL if we need a perfect loop and can't make one.
        (lambda_loopnest_to_gcc_loopnest): Correct algorithm.
        (not_interesting_stmt): New function.
        (phi_loop_edge_uses_def): Ditto.
        (stmt_uses_phi_result): Ditto.
        (stmt_is_bumper_for_loop): Ditto.
        (perfect_nest_p): Ditto.
        (nestify_update_pending_stmts): Ditto.
        (replace_uses_of_x_with_y): Ditto.
        (stmt_uses_op): Ditto.
        (perfect_nestify): Ditto.
        * lambda-mat.c (lambda_matrix_id_p): New function.
        * lambda-trans.c (lambda_trans_matrix_id_p): Ditto.
        * lambda.h: Update prototypes.
        * tree-loop-linear (linear_transform_loop): Use new
        perfect_nest_p. Detect and ignore identity transform.
        * tree-ssa-loop.c (pass_linear_transform): Use TODO_write_loop_closed.

2004-09-02  Sebastian Pop  <pop@cri.ensmp.fr>

        * tree-loop-linear.c (gather_interchange_stats): Add more comments.
        Gather also strides of accessed data.  Pass in the data references
        array.
        (try_interchange_loops): Add a new heuristic for handling the temporal
        locality.  Pass in the data references array.
        (linear_transform_loops): Pass the data references array to
	try_interchange_loops.

Attachment: linearloopdiff.diff
Description: Text document