---

loops.h

Go to the documentation of this file.

// ----------------------------------------------------------------------
//
//  C-Breeze
//  C Compiler Framework
// 
//  Copyright (c) 2000 University of Texas at Austin
// 
//  Samuel Z. Guyer
//  Daniel A. Jimenez
//  Calvin Lin
// 
//  Permission is hereby granted, free of charge, to any person
//  obtaining a copy of this software and associated documentation
//  files (the "Software"), to deal in the Software without
//  restriction, including without limitation the rights to use, copy,
//  modify, merge, publish, distribute, sublicense, and/or sell copies
//  of the Software, and to permit persons to whom the Software is
//  furnished to do so, subject to the following conditions:
//  
//  The above copyright notice and this permission notice shall be
//  included in all copies or substantial portions of the Software.
//  
//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
//  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
//  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
//  NONINFRINGEMENT.  IN NO EVENT SHALL THE UNIVERSITY OF TEXAS AT
//  AUSTIN BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
//  IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
//  OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//  THE SOFTWARE.
//
//  We acknowledge the C-to-C Translator from MIT Laboratory for
//  Computer Science for inspiring parts of the C-Breeze design.
//
// ----------------------------------------------------------------------

#ifndef CBZ_LOOPS_H
#define CBZ_LOOPS_H

#include <set>

typedef set< basicblockNode * > basicblock_set;
typedef basicblock_set::iterator basicblock_set_p;

typedef map< basicblockNode *, basicblock_set > edge_map;
typedef edge_map::iterator edge_map_p;

typedef map< basicblockNode *, basicblock_set > basicblock_set_map;
typedef basicblock_set_map::iterator basicblock_set_map_p;

typedef map< basicblockNode *, int > basicblock_int_map;
typedef basicblock_int_map::iterator basicblock_int_map_p;

class loopTreeNode;

typedef list< loopTreeNode * > loop_list;
typedef loop_list::iterator loop_list_p;

typedef set< loopTreeNode * > loop_set;
typedef loop_set::iterator loop_set_p;

class loopTreeNode
{
public:

  typedef enum { SingleEntry, MultipleEntry, Top } LoopKind;

private:

  LoopKind _kind;

  int _depth;

  basicblockNode * _header;

  basicblockNode * _preheader;

  loopTreeNode * _parentLoop;

  loop_set _nestedLoops;

  basicblock_set _blocks;

public:

  loopTreeNode(LoopKind kind, basicblockNode * header);

  inline void addBlock(basicblockNode * block) { _blocks.insert(block); }

  inline void addNestedLoop(loopTreeNode * nest){ _nestedLoops.insert(nest); }

  inline LoopKind kind() const { return _kind; }

  inline int depth() const { return _depth; }
  inline void depth(int d) { _depth = d; }

  inline basicblockNode * header() const { return _header; }

  inline basicblockNode * preheader() const { return _preheader; }

  inline loopTreeNode * parentLoop() const { return _parentLoop; }
  inline void parentLoop(loopTreeNode * parent) { _parentLoop = parent; }

  inline loop_set & nestedLoops() { return _nestedLoops; }

  inline basicblock_set & blocks() { return _blocks; }

  void report();
};

typedef map< basicblockNode *, loopTreeNode * > blockloop_map;
typedef blockloop_map::iterator blockloop_map_p;

class loopTree
{
public:

  typedef enum { TreeEdge, BackEdge, ForwardEdge, CrossEdge } EdgeKind;

private:

  procNode * _procedure;

  loopTreeNode * _top;

  loop_list _loops;

  blockloop_map _containedIn;

  edge_map _backEdges;

  edge_map _forwardEdges;

  edge_map _crossEdges;

  basicblock_int_map _preOrder;

  basicblock_int_map _rpostOrder;

public:

  loopTree(procNode * procedure);

  ~loopTree();

  inline procNode * procedure() const { return _procedure; }

  inline loopTreeNode * topLoop() const { return _top; }

  loopTreeNode * whichLoop(basicblockNode * block);

  loopTreeNode * loopAncestor(loopTreeNode * loop);

  EdgeKind classifyEdge(basicblockNode * source,
                        basicblockNode * target);

  void report();

private:

  void findLoop(basicblockNode * candidate,
                basicblock_set_map & generators_map);

  void findBody(basicblockNode * head,
                basicblock_set & generators,
                loopTreeNode::LoopKind kind);

  basicblockNode * commonDominator(basicblockNode * first,
                                   basicblockNode * second);

  void classifyEdges(basicblock_list & post_order);

  void depthFirstSearch(basicblockNode * cur,
                        basicblock_list & post_order,
                        int & pre_order_number,
                        int & post_order_number);

  void setDepths(loopTreeNode * cur, int depth);

  void report(loopTreeNode * cur, int level);

};

#endif // CBZ_LOOPS_H

---