[patch] Allow analyzing loops without modifying cfg

[Diego Novillo]

Zdenek Dvorak wrote on 02/02/07 07:12:
> Hello,
> 
> I was asked several times about the possibility to analyze loops without
> changing cfg.  After about a hundred cleanups, this finally became
> possible to do in a satisfactory way.  The patch makes flow_loops_find
> to only find loops (without modifying cfg), and splits disambiguation
> of loops with multiple latches to a separate function (called by
> loop_optimizer_init).
> 
Nice, this can be very useful.  ISTR that VRP could use non-intrusive
CFG discovery.  Is that possible?  Dunno if SCEV may need single
latches.

> ! Heuristic based on profile information and structure of the induction
> ! variables in the loops is used to determine whether the latches
> ! correspond to sub-loops or to control flow in a single loop.  This means
> ! that the analysis sometimes changes the CFG, and if you run it in the
> ! middle of an optimization pass, you must be able to deal with the new
> ! blocks.  You may avoid CFG changes by passing
> ! @code{LOOPS_MAY_HAVE_MULTIPLE_LATCHES} flag to the loop discovery,
> ! note however that most other loop manipulation functions will not work
> ! correctly for loops with multiple latch edges.
>   
Enumerating the transformations that won't work in this case would be
error prone but we should describe what will be the observable
behaviour in these cases.  For instance, calling unsupported functions
with ICE with the message "found NULL latch block" or something.

> ! /* Creates place for a new LOOP in loops structure.  */
> ! static void
> ! place_new_loop (struct loop *loop)
>
Space between comment and function start.

> *************** flow_loops_find (struct loops *loops)
> *** 617,622 ****
> --- 493,756 ----
>     return VEC_length (loop_p, loops->larray);
>   }
>   
> + /* Ratio of frequencies of edges so that one of more latch edges is
> +    considered to belong to inner loop with same header.  */
> + #define HEAVY_EDGE_RATIO 8
> + 
> + /* Minimum number of samples for that we apply
> +    find_subloop_latch_edge_by_profile heuristics.  */
> + #define HEAVY_EDGE_MIN_SAMPLES 10
> + 
Where are these numbers coming from.  Is this something we want in
--param?

> + /* If the profile info is available, finds an edge in LATCHES that much more
> +    frequent than the remaining edges.  Returns such an edge, or NULL if we do
> +    not find one.
> + 
> +    We do not use guessed profile here, only the measured one.  The guessed
> +    profile is usually too flat and unreliable for this (and it is mostly based
> +    on the loop structure of the program, so it does not make much sense to
> +    derive the loop structure from it.  */
> +    
Missing closing ')'.