C-Breeze
C Compiler Infrastructure

[ Project home page]
Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

loopTree Class Reference

#include <loops.h>

List of all members.

Public Types

enum  EdgeKind { TreeEdge, BackEdge, ForwardEdge, CrossEdge }

Public Member Functions

 loopTree (procNode *procedure)
 Create a loop tree.
 ~loopTree ()
 Delete a loop tree.
procNode * procedure () const
 Procedure.
loopTreeNode * topLoop () const
 Top loop object.
edge_map & backedges ()
 Accessors.
edge_map & treeedges ()
loop_list & loops ()
loopTreeNode * whichLoop (basicblockNode *block)
 Which loop.
loopTreeNode * loopAncestor (loopTreeNode *loop)
 Find a loop ancestor.
EdgeKind classifyEdge (basicblockNode *source, basicblockNode *target)
 Edge classification.
void report ()
 Report.

Private Member Functions

void findLoop (basicblockNode *candidate, basicblock_set_map &generators_map)
 Decide if a block is a loop header.
void findBody (basicblockNode *head, basicblock_set &generators, loopTreeNode::LoopKind kind)
 Determine the body of a loop.
basicblockNode * commonDominator (basicblockNode *first, basicblockNode *second)
 Find a common dominator for two blocks.
void classifyEdges (basicblock_list &post_order)
 Classify edges.
void depthFirstSearch (basicblockNode *cur, basicblock_list &post_order, int &pre_order_number, int &post_order_number)
 Depth-first search.
void setDepths (loopTreeNode *cur, int depth)
 Set the depth on each loop nest.
void report (loopTreeNode *cur, int level)
 Report (tree recursion).

Private Attributes

procNode * _procedure
 The procedure.
loopTreeNode * _top
 The loop tree.
loop_list _loops
 A list of the loops.
blockloop_map _containedIn
 Mapping from basic blocks to loops.
edge_map _backEdges
 List of back edges.
edge_map _forwardEdges
 List of forward edges.
edge_map _treeEdges
 List of tree edges.
edge_map _crossEdges
 List of cross edges.
basicblock_int_map _preOrder
 Depth-first pre-order of the nodes.
basicblock_int_map _rpostOrder
 Depth-first reverse-post-order of the nodes.

Member Enumeration Documentation

enum loopTree::EdgeKind
 

Enumeration values:
TreeEdge 
BackEdge 
ForwardEdge 
CrossEdge 

Definition at line 148 of file loops.h.

Constructor & Destructor Documentation

loopTree::loopTree (  procNode *  procedure  ) 
 

Create a loop tree.

This constructor is responsible for creating the loop tree. Dominators(procedure, boolean) must be run before this phase will work. Since there is no way to run this from the command line, you MUST run the dominators pass yourself.

loopTree::~loopTree (   ) 
 

Delete a loop tree.

This destructor is reponsible for deleting all of the loop tree nodes as well.

Member Function Documentation

edge_map& loopTree::backedges (   )  [inline]
 

Accessors.

Definition at line 235 of file loops.h.

References _backEdges.

EdgeKind loopTree::classifyEdge (  basicblockNode *  source,
basicblockNode *  target
) 
 

Edge classification.

Given a particular source and target in the control-flow graph, indicate which kind of edge it is: tree, forward, backward, or cross.

void loopTree::classifyEdges (  basicblock_list &  post_order  )  [private]
 

Classify edges.

Perform a depth-first search of the control-flow graph, building pre-order and reverse-post-order orderings of the nodes, as well as classifying th edges. Also, return a list with the post-order traversal.

basicblockNode* loopTree::commonDominator (  basicblockNode *  first,
basicblockNode *  second
)  [private]
 

Find a common dominator for two blocks.

void loopTree::depthFirstSearch (  basicblockNode *  cur,
basicblock_list &  post_order,
int &  pre_order_number,
int &  post_order_number
)  [private]
 

Depth-first search.

void loopTree::findBody (  basicblockNode *  head,
basicblock_set &  generators,
loopTreeNode::LoopKind  kind
)  [private]
 

Determine the body of a loop.

void loopTree::findLoop (  basicblockNode *  candidate,
basicblock_set_map &  generators_map
)  [private]
 

Decide if a block is a loop header.

loopTreeNode* loopTree::loopAncestor (  loopTreeNode *  loop  ) 
 

Find a loop ancestor.

loop_list& loopTree::loops (   )  [inline]
 

Definition at line 237 of file loops.h.

References _loops.

procNode* loopTree::procedure (   )  const [inline]
 

Procedure.

Definition at line 223 of file loops.h.

References _procedure.

void loopTree::report (  loopTreeNode *  cur,
int  level
)  [private]
 

Report (tree recursion).

void loopTree::report (   ) 
 

Report.

void loopTree::setDepths (  loopTreeNode *  cur,
int  depth
)  [private]
 

Set the depth on each loop nest.

loopTreeNode* loopTree::topLoop (   )  const [inline]
 

Top loop object.

Note that this is not really a loop; it's just used as the root of the tree

Definition at line 230 of file loops.h.

References _top.

edge_map& loopTree::treeedges (   )  [inline]
 

Definition at line 236 of file loops.h.

References _treeEdges.

loopTreeNode* loopTree::whichLoop (  basicblockNode *  block  ) 
 

Which loop.

Determine which loop a particular basic block belongs to.

Member Data Documentation

edge_map loopTree::_backEdges [private]
 

List of back edges.

Back edges are stored according to the *target* of the back-edge, not the source. This is because the algorithm needs to easily find all the back-edges that impinge on a candidate node.

Definition at line 174 of file loops.h.

Referenced by backedges().

blockloop_map loopTree::_containedIn [private]
 

Mapping from basic blocks to loops.

Definition at line 166 of file loops.h.

edge_map loopTree::_crossEdges [private]
 

List of cross edges.

Stored according to the source of the edge

Definition at line 192 of file loops.h.

edge_map loopTree::_forwardEdges [private]
 

List of forward edges.

Stored according to the source of the edge

Definition at line 180 of file loops.h.

loop_list loopTree::_loops [private]
 

A list of the loops.

Definition at line 162 of file loops.h.

Referenced by loops().

basicblock_int_map loopTree::_preOrder [private]
 

Depth-first pre-order of the nodes.

Definition at line 196 of file loops.h.

procNode* loopTree::_procedure [private]
 

The procedure.

Definition at line 154 of file loops.h.

Referenced by procedure().

basicblock_int_map loopTree::_rpostOrder [private]
 

Depth-first reverse-post-order of the nodes.

Definition at line 200 of file loops.h.

loopTreeNode* loopTree::_top [private]
 

The loop tree.

Definition at line 158 of file loops.h.

Referenced by topLoop().

edge_map loopTree::_treeEdges [private]
 

List of tree edges.

Stored according to the source of the edge

Definition at line 186 of file loops.h.

Referenced by treeedges().

The documentation for this class was generated from the following file:

Generated on February 1, 2006
Back to the C-Breeze home page