 |
C-Breeze C Compiler Infrastructure [ Project home page] |
loops.h
Go to the documentation of this file.00001 // $Id: loops.h,v 1.4 2003/08/07 23:14:19 pnav Exp $ 00002 // ---------------------------------------------------------------------- 00003 // 00004 // C-Breeze 00005 // C Compiler Framework 00006 // 00007 // Copyright (c) 2000 University of Texas at Austin 00008 // 00009 // Samuel Z. Guyer 00010 // Daniel A. Jimenez 00011 // Calvin Lin 00012 // 00013 // Permission is hereby granted, free of charge, to any person 00014 // obtaining a copy of this software and associated documentation 00015 // files (the "Software"), to deal in the Software without 00016 // restriction, including without limitation the rights to use, copy, 00017 // modify, merge, publish, distribute, sublicense, and/or sell copies 00018 // of the Software, and to permit persons to whom the Software is 00019 // furnished to do so, subject to the following conditions: 00020 // 00021 // The above copyright notice and this permission notice shall be 00022 // included in all copies or substantial portions of the Software. 00023 // 00024 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00025 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00026 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00027 // NONINFRINGEMENT. IN NO EVENT SHALL THE UNIVERSITY OF TEXAS AT 00028 // AUSTIN BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER 00029 // IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 00030 // OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 00031 // THE SOFTWARE. 00032 // 00033 // We acknowledge the C-to-C Translator from MIT Laboratory for 00034 // Computer Science for inspiring parts of the C-Breeze design. 00035 // 00036 // ---------------------------------------------------------------------- 00037 00038 #ifndef CBZ_LOOPS_H 00039 #define CBZ_LOOPS_H 00040 00041 #include <set> 00042 00043 typedef set< basicblockNode * > basicblock_set; 00044 typedef basicblock_set::iterator basicblock_set_p; 00045 00046 typedef map< basicblockNode *, basicblock_set > edge_map; 00047 typedef edge_map::iterator edge_map_p; 00048 00049 typedef map< basicblockNode *, basicblock_set > basicblock_set_map; 00050 typedef basicblock_set_map::iterator basicblock_set_map_p; 00051 00052 typedef map< basicblockNode *, int > basicblock_int_map; 00053 typedef basicblock_int_map::iterator basicblock_int_map_p; 00054 00055 class loopTreeNode; 00056 00057 typedef list< loopTreeNode * > loop_list; 00058 typedef loop_list::iterator loop_list_p; 00059 00060 typedef set< loopTreeNode * > loop_set; 00061 typedef loop_set::iterator loop_set_p; 00062 00063 class loopTreeNode 00064 { 00065 public: 00066 00069 typedef enum { SingleEntry, MultipleEntry, Top } LoopKind; 00070 00071 private: 00072 00075 LoopKind _kind; 00076 00079 int _depth; 00080 00083 basicblockNode * _header; 00084 00087 basicblockNode * _preheader; 00088 00091 loopTreeNode * _parentLoop; 00092 00095 loop_set _nestedLoops; 00096 00099 basicblock_set _blocks; 00100 00101 public: 00102 00105 loopTreeNode(LoopKind kind, basicblockNode * header); 00106 00109 inline void addBlock(basicblockNode * block) { _blocks.insert(block); } 00110 00113 inline void addNestedLoop(loopTreeNode * nest){ _nestedLoops.insert(nest); } 00114 00117 inline LoopKind kind() const { return _kind; } 00118 00119 inline int depth() const { return _depth; } 00120 inline void depth(int d) { _depth = d; } 00121 00122 inline basicblockNode * header() const { return _header; } 00123 00124 inline basicblockNode * preheader() const { return _preheader; } 00125 00126 inline loopTreeNode * parentLoop() const { return _parentLoop; } 00127 inline void parentLoop(loopTreeNode * parent) { _parentLoop = parent; } 00128 00129 inline loop_set & nestedLoops() { return _nestedLoops; } 00130 00131 inline basicblock_set & blocks() { return _blocks; } 00132 00135 void report(); 00136 00137 void output(output_context &, Node * parent); 00138 void output_stmt(output_context &, Node * parent); 00139 }; 00140 00141 typedef map< basicblockNode *, loopTreeNode * > blockloop_map; 00142 typedef blockloop_map::iterator blockloop_map_p; 00143 00144 class loopTree 00145 { 00146 public: 00147 00148 typedef enum { TreeEdge, BackEdge, ForwardEdge, CrossEdge } EdgeKind; 00149 00150 private: 00151 00154 procNode * _procedure; 00155 00158 loopTreeNode * _top; 00159 00162 loop_list _loops; 00163 00166 blockloop_map _containedIn; 00167 00174 edge_map _backEdges; 00175 00180 edge_map _forwardEdges; 00181 00186 edge_map _treeEdges; 00187 00192 edge_map _crossEdges; 00193 00196 basicblock_int_map _preOrder; 00197 00200 basicblock_int_map _rpostOrder; 00201 00202 public: 00203 00212 loopTree(procNode * procedure); 00213 00219 ~loopTree(); 00220 00223 inline procNode * procedure() const { return _procedure; } 00224 00230 inline loopTreeNode * topLoop() const { return _top; } 00231 00232 00235 inline edge_map & backedges() { return _backEdges; } 00236 inline edge_map & treeedges() { return _treeEdges; } 00237 00242 loopTreeNode * whichLoop(basicblockNode * block); 00243 00246 loopTreeNode * loopAncestor(loopTreeNode * loop); 00247 00254 EdgeKind classifyEdge(basicblockNode * source, 00255 basicblockNode * target); 00256 00259 void report(); 00260 00261 private: 00262 00265 void findLoop(basicblockNode * candidate, 00266 basicblock_set_map & generators_map); 00267 00270 void findBody(basicblockNode * head, 00271 basicblock_set & generators, 00272 loopTreeNode::LoopKind kind); 00273 00276 basicblockNode * commonDominator(basicblockNode * first, 00277 basicblockNode * second); 00278 00286 void classifyEdges(basicblock_list & post_order); 00287 00290 void depthFirstSearch(basicblockNode * cur, 00291 basicblock_list & post_order, 00292 int & pre_order_number, 00293 int & post_order_number); 00294 00297 void setDepths(loopTreeNode * cur, int depth); 00298 00301 void report(loopTreeNode * cur, int level); 00302 00303 }; 00304 00305 #endif // CBZ_LOOPS_H 00306