Natural loop detection

[Jeffrey A Law]

  In message < 14387.49331.113613.131101@ongaonga.elec.canterbury.ac.nz >you writ
e:
  > 1999-11-18  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.
Some additional comments on this code:

  > + 
  > + /* Dump the list of basic blocks in the bitmap NODES.  */
  > + static void flow_nodes_print (str, nodes, file)
The function's scope & return type belong on a different line than the
function's name.  So that should be rewritten

static void
flow_nodes_print (str, nodes, file)



  > + /* Dump loop related CFG information.  */
  > + static void flow_loops_cfg_dump (loops, file)
  > +      const struct loops *loops;
  > +      FILE *file;
Similarly.  It looks like you need to fix most/all of the new functions
you added.

  > +   for (i = 0; i < n_basic_blocks; i++)
  > +     {
  > +       edge succ;
  > + 
  > +       fprintf (file, ";; %d succs { ", i);
  > +       for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
  > + 	fprintf (file, "%d ", succ->dest->index);
  > +       flow_nodes_print ("} dom", loops->cfg.dom[i], file);	
  > +     }
Won't this do an out of range access into loops->cfg.dom[i] when the
successor is the exit block?

The easiest way to check for this is to verify that
succ->dest != EXIT_BLOCK_PTR

There may be other instances of this buglet.  You should probably
review your code for them.  Basically look at any loop that uses
the index of a block referenced by an edge to index into an array.

Why not allocate/deallocate the visited array in
flow_depth_first_order_compute?  That seems cleaner since it's an
internal implementation detail and nobody else uses that information.

You allocate and free memory for LOOP_STACK, but you never do anything
with the memory as far as I can tell.

You should probably use xcalloc to allocate memory that you immediate
clear like loops->array.


Stan -- you might be able to use this stuff for your basic block
reordering code.

jeff