Diego Novillo - Re: [patch] Allow analyzing loops without modifying cfg (original) (raw)

This is the mail archive of the gcc-patches@gcc.gnu.orgmailing list for the GCC project.

• From: Diego Novillo
• To: Zdenek Dvorak
• Cc: gcc-patches at gcc dot gnu dot org, stevenb dot gcc at gmail dot com
• Date: Fri, 02 Feb 2007 10:19:29 -0500
• Subject: Re: [patch] Allow analyzing loops without modifying cfg
• References: <20070202121224.GB5319@atrey.karlin.mff.cuni.cz>

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 ')'.

• Follow-Ups:
  • Re: [patch] Allow analyzing loops without modifying cfg
    * From: Zdenek Dvorak
• References:
  • [patch] Allow analyzing loops without modifying cfg
    * From: Zdenek Dvorak