\section{Natural loop analysis}
\label{sec-natural-loop-info}

\subsection{Class [[NaturalLoopInfo]]}

Class [[NaturalLoopInfo]] computes and caches information about the
natural loops in a CFG.

<<class [[NaturalLoopInfo]]>>=
class NaturalLoopInfo {
  public:
    NaturalLoopInfo(DominanceInfo *dom_info)
	: _dom_info(dom_info), _depth(NULL), _loop(NULL) { }
    virtual ~NaturalLoopInfo() { delete [] _depth; }

    DominanceInfo *dom_info() const { return _dom_info; }

    void find_natural_loops();

    const NatSet* loop_at(int n) const;
    const NatSet* loop_at(CfgNode *n) const;
    int loop_depth(int n) const;
    int loop_depth(CfgNode *n) const;
    void set_loop_depth(CfgNode *n, int d);
    void set_loop_depth(int n, int d);

    bool is_loop_begin(int n) const;	// true if block is loop entry
    bool is_loop_begin(CfgNode *cn) const;
    bool is_loop_end(int n) const;	// true if block jumps to loop entry
    bool is_loop_end(CfgNode *cn) const;
    bool is_loop_exit(int n) const;	// true if block is a loop exit
    bool is_loop_exit(CfgNode *cn) const;

    void print(FILE* = stdout) const;

<<[[NaturalLoopInfo]] protected parts>>
};
@

An instance of [[NaturalLoopInfo]] is constructed from a pointer to
[[DominanceInfo]] because dominators are used for the loop analysis.
You can recover the [[DominanceInfo]] object by using the [[dom_info]]
method.

Like dominance analysis, natural loops are computed only on demand.
Call [[find_natural_loops]] to run (or rerun) the analysis.  Before
doing so, you must have called [[find_dominators]] on the underlying
[[DominanceInfo]] structure.

The [[loop_at()]] method takes a node $n$ (or its node number) and returns
the set of node numbers comprising the natural loop with header $n$.  (If
$n$ is not a loop header, the result set is empty.)

The [[loop_depth()]] method returns the number of natural loops that
contain a node.  This can be set using the [[set_loop_depth()]] methods,
in case you need to override the results of [[find_natural_loops()]].

The [[is_loop_begin()]] method returns [[true]] if the specified node
dominates any of its predecessors.  The [[is_loop_end()]] method returns
[[true]] if the specified node is dominated by any of its successors.
And the [[is_loop_exit()]] method returns [[true]] if the specified node
has any successor with a different loop depth.  Note that this may not
be the right loop exit criterion to use in all cases.


\subsection{Implementation}

For finding natural loops, we use a method based on Algorithm 10.1 in
Aho, Sethi, and Ullman \cite{bibdragon}.

An instance of [[NaturalLoopInfo]] stores the dominance information
provided at its construction in its [[_dom_info]] field.  When a method
needs the CFG, it goes though [[_dom_info]] to reach it.  An instance of
[[NaturalLoopInfo]] also contains a pointer [[_depth]] that is
[[NULL]] until [[find_natural_loops]] is called and thereafter points to
an array of loop depths, one for each node in the CFG.

<<[[NaturalLoopInfo]] protected parts>>=
  private:
    DominanceInfo *_dom_info;
    int *_depth;			// int per node
    NatSetDense *_loop;			// bit vector per node
@


\subsection{Header file for module [[loop.h]]}

The [[NaturalLoopInfo]] class is defined in module [[loop]], which has
the following header file.

<<loop.h>>=
/* file "cfa/loop.h" -- Natural Loop Analysis */

<<Machine-SUIF copyright>>

#ifndef CFA_LOOP_H
#define CFA_LOOP_H

#include <machine/copyright.h>

#ifndef SUPPRESS_PRAGMA_INTERFACE
#pragma interface "cfa/loop.h"
#endif

#include <machine/machine.h>
#include <cfg/cfg.h>
#include <cfa/dom.h>

<<class [[NaturalLoopInfo]]>>

#endif /* CFA_LOOP_H */
@