 |
C-Breeze C Compiler Infrastructure [ Project home page] |
dominators.h
Go to the documentation of this file.00001 // $Id: dominators.h,v 1.10 2003/08/07 23:14:14 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_DOMINATORS_H 00039 #define CBZ_DOMINATORS_H 00040 00041 #include <bitset> 00042 00043 #define BASICBLOCK_BITSET_SIZE 4096 00044 00045 typedef bitset<BASICBLOCK_BITSET_SIZE> basicblock_bitset; 00046 00050 class dominator_info : public algorithm_info 00051 { 00052 public: 00053 00054 // --- Used in computing dominator tree 00055 00056 basicblockNode * label; 00057 basicblockNode * parent; 00058 basicblockNode * ancestor; 00059 basicblockNode * child; 00060 int sdno; 00061 int size; 00062 basicblock_bitset bucket; 00063 00064 dominator_info(basicblockNode * node, int depth_first_num); 00065 }; 00066 00067 00068 00072 class Dominators 00073 { 00074 friend class dominator_info; 00075 00076 public: 00077 // --- Some useful types 00078 00079 typedef vector<basicblockNode *> basicblock_vec; 00080 typedef map<basicblockNode *, int> index_map; 00081 typedef map<basicblockNode *, basicblockNode *> basicblock_map; 00082 typedef map<basicblockNode *, basicblock_bitset> basicblockset_map; 00083 00084 private: 00085 00087 procNode * _proc; 00088 00090 basicblockNode * _root; 00091 00097 const bool _forward; 00098 00100 index_map node_index; 00101 00103 basicblock_vec df_vec; 00104 00106 static basicblockNode * None; 00107 00108 int _index; 00109 00110 // ---------------------------------------- 00111 00112 00113 // --- Compute dominator tree 00114 00115 void dominator_tree(); 00116 void depth_first_search(basicblockNode * node, 00117 basicblockNode * par); 00118 void compress(basicblockNode * v); 00119 basicblockNode * eval(basicblockNode * v); 00120 void link(basicblockNode * v, basicblockNode * w); 00121 00122 public: 00123 00124 Dominators(procNode * proc, bool forward); 00125 00126 ~Dominators(); 00127 00129 static bool dominates(basicblockNode * A, basicblockNode * B); 00130 00131 00132 void print(); 00133 00134 }; 00135 00136 #endif // CBZ_DOMINATORS_H