C-Breeze C Compiler Infrastructure [ Project home page]

loops.h Go to the documentation of this file. // $Id: loops.h,v 1.4 2003/08/07 23:14:19 pnav Exp $ // ---------------------------------------------------------------------- // // 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(); void output(output_context &, Node * parent); void output_stmt(output_context &, Node * parent); }; 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 _treeEdges; 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; } inline edge_map & backedges() { return _backEdges; } inline edge_map & treeedges() { return _treeEdges; } inline loop_list & loops() { return _loops; } 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

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