Re: Natural loop detection

[Jeffrey A Law <law at cygnus dot com>]

  In message <14403.17542.369128.144755@ongaonga.elec.canterbury.ac.nz>you writ
e:
  > I ended up opting for an array of edges.  I would have liked a linked
  > list of edges but this didn't seem to be worth the memory allocation
  > overhead.  Using EXPR_LIST for non-rtx data seemed grubby.
I suspect we rarely need to modify the outgoing edge list for a loop, so
an array is probably reasonable.

  > Here's the modified patch, incorporating your suggestions.
  > 
  > 1999-11-30  Michael Hayes  <m.hayes@elec.canterbury.ac.nz>
  > 
  > 	* flow.c (flow_nodes_print, flow_loops_cfg_dump, flow_loop_nested_p,
  > 		flow_loops_dump, flow_loops_free, flow_loop_exits_find, 
  > 		flow_loop_nodes_find, flow_depth_first_order_compute, 
  > 		flow_loop_pre_header_find, flow_loop_tree_node_add,
  > 		flow_loops_tree_build, flow_loop_level_compute, 
  > 		flow_loops_level_compute, flow_loops_find,
  > 		flow_loop_outside_edge_p): New functions to find natural
  > 		loops in the CFG and to build loop heirachy tree.
  > 	* basic-block.h (flow_loops_find, flow_loops_free, flow_loop_dump):
  > 	Added protoypes.
  > 	(struct loops, struct loop): Define.
  > 	* sbitmap.c (sbitmap_a_subset_b_p): New function.
  > 	* sbitmap.h (sbitmap_a_subset_b_p): Added prototype.
  > 	* bitmap.h
The patch looks real good.  Just a few additional comments.

The ChangeLog entry is a little out of style.  What I tend to do in this kind
of case is


	* flow.c (flow_nodes_print, flow_loops_from_cfg_loop): New functions.
	(func2, func3, func4, ....): Likewise.
	(funcN, funcN+1, ...): Likewise.

It also appears that your ChangeLog entry got truncated.  You didn't mention
what you changed in bitmap.h.  You should also mention that basic-block.h and
sbitmap.h  were changed to be safe for multiple inclusion.

You included basic-block.h in loop.h, but didn't update the dependencies in
Makefile.in.  You should probably create LOOP_H in Makefile.in, initialize
it to varray.h and basic-block.h, then replace all references to loop.h to
LOOP_H.

In flow_loop_pre_header_find you have this comment:

+             /* There are multiple forward edges into the header.  */

While I believe the comment is technically correct due to graph
reducibility, it might be clearer to say "There are multiple edges which
reach the header from outside the loop.".

[ This is mostly for folks that are relatively new to the theory and practice
  of using dominance relationships to determine properties of blocks/edges
  in a flow graph. ]

In flow_loops_find you have this comment:

+   /* Count the number of back edges.  This should be the same as the number
+      of natural loops.  */

You might use the term "loop edge" rather than "back edge".  Again, mostly
to help folks not as familiar with the theory behind this stuff or someone
that is casually reading the code to determine overall structure.  It caught
me off-guard until I looked at the comments in the next nesting level down.


Once you resolve these last few nits you can install the patch.  No need to
wait for another review cycle.

jeff