[patch] PR middle-end/39326 - limit LIM

[Steven Bosscher]

Hello,

The attached patch fixes another one of the scalability problems
reported in PR middle-end/39326.

This problem is that tree loop-invariant code motion explodes on basic
blocks with many memory references. Compile time is quadratic in the
number of memory references in the basic block, and so are the memory
requirements when the dependences or independences are propagated
bottom-up through the loop tree.

The fix is to give up on loops with too many memory references to
handle. There is already a param for that for loop dependence
analysis, and this patch makes LIM use the same param.

Bootstrapped&tested on {x86_64,powerpc64}-unknown-linux-gnu.
OK for trunk?

Ciao!
Steven

(The ChangeLog is a bit long but the patch is relatively straight-forward.)

        * tree-flow.h (enum move_pos): Moved to tree-ssa-loop-im.c.
        * tree-ssa-loop-im.c: Include diagnostic-core.h for warning_at()
        (enum move_pos): Moved here.
        (movement_possibility): Made static.  Reject memory operations in
        loops with too many memory references to handle.
        (determine_max_movement): Take loops_with_too_many_memrefs argument.
        For statements referencing memory, find the outermost superloop
        that is not in the loops_with_too_many_memrefs set.
        (determine_invariantness_stmt): Take loops_with_too_many_memrefs
        via dom_walk_data.global_data, and pass it along where necessary.
        Hoist "pos == MOVE_POSSIBLE" test.
        (determine_invariantness): Take loops_with_too_many_memrefs argument.
        (move_computations): Likewise, but unused for now.
        (gather_mem_refs_stmt): Fail if there are too many memory references.
        Use PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS as threshold.  Add disabled
        optimization warning.
        (gather_mem_refs_in_loops): Take loops_with_too_many_memrefs argument.
        Propagate it from inner loops to outer loops.  Do not propagate
        recorded memory references for loops on which memory optimizations
        are disabled.
        (create_vop_ref_mapping): Take loops_with_too_many_memrefs argument.
        Don't create a mapping on loops that are in this set.
        (analyze_memory_references): Take loops_with_too_many_memrefs argument
        and let subroutines fill it.
        (store_motion): Take loops_with_too_many_memrefs argument.
        Skip loops that are in this set.
        (tree_ssa_lim): Allocate, pass, and free loops_with_too_many_memrefs.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PR39326_LIM.diff
Type: application/octet-stream
Size: 16050 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20130310/619cb760/attachment.obj>