Loop Tree

Loop tree describes the structure of loops. Nodes correspond to loops, while edges reflect the subloop/superloop stucture. Root of the tree is a dummy loop containing the whole function (including ENTRY_BLOCK_PTR as latch and EXIT_BLOCK_PTR as header).

Struct loop is defined as follows:

struct loop
{
  /* Index into loops array.  */
  int num;

  /* Basic block of loop header.  */
  basic_block header;

  /* Basic block of loop latch.  */
  basic_block latch;

  /* Number of blocks contained within the loop.  */
  int num_nodes;

  /* The loop nesting depth.  */
  int depth;

  /* Array of superloops of the loop.  */
  struct loop **pred;

  /* The outer (parent) loop or NULL if outermost loop.  */
  struct loop *outer;

  /* The first inner (child) loop or NULL if innermost loop.  */
  struct loop *inner;

  /* Link to the next (sibling) loop.  */
  struct loop *next;

  /* Loop that is copy of this loop
     (must be valid only just after copying the loop).  */
  struct loop *copy;

 ... /* Fields specific for the old loop optimizer
        are omitted.  */
};

The whole loop tree (plus additional information) is stored in struct loops:

struct loops
 {
  /* Number of natural loops in the function.  */
  int num;

  /* Array of pointers to loops.  Subloops should always
     have greater index than their parents.  */
  struct loop **parray;

  /* Pointer to root of loop hierarchy tree.  */
  struct loop *tree_root;

 ... /* Fields specific for old loop optimizer
        are omitted.  */
 };

Field loop_father of basic_block is a pointer to the innermost loop containing the basic block.

Functions for building, modifying and querying the loop structure are provided in cfgloop.c and cfgloopanal.c; some higher level functions for manipulating it may be found in loop-new.c.