 |
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
dfpreds.h
Go to the documentation of this file.00001 // $Id: dfpreds.h,v 1.6 2003/08/07 23:14:22 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_DFPREDS_H 00039 #define CBZ_DFPREDS_H 00040 00041 #include <set> 00042 #include "pointeroptions.h" 00043 #include "ref_clone_changer.h" 00044 #include "dominators.h" 00045 00046 // The DominanceFrontier class compute the dominance frontier for the 00047 // procedure given in its constructor. This version of the algorithm 00048 // also computes the particular set of predecessors of each element of 00049 // the dominance frontier. For example: 00050 00051 // _____3_______ 00052 // / \ 00053 // 1 __/ >--6 00054 // \ __5____/ 00055 // \__2__/ / 00056 // \__4__/ 00057 00058 // In the above graph, if we have a def at (2), the dominance frontier 00059 // is {6}. However, we also want to record the fact that the 00060 // particular predecessors of (6) that (2) dominates are {4,5}. This 00061 // will allow us to put the reaching definition directly into the 00062 // appropriate entry of the phi function at (6). 00063 00064 // Store the dominance frontier entries (with predecessor sets) 00065 00066 typedef map< basicblockNode *, basicblock_set > basicblock_set_map; 00067 typedef basicblock_set_map::iterator basicblock_set_map_p; 00068 00069 // Store all the dominance frontiers 00070 00071 typedef map< basicblockNode *, basicblock_set_map > basicblock_set_map_map; 00072 typedef basicblock_set_map_map::iterator basicblock_set_map_map_p; 00073 00074 /* 00075 typedef map< basicblockNode *, basicblock_set > basicblockset_map; 00076 typedef basicblockset_map::iterator basicblockset_map_p; 00077 00078 typedef map< basicblockNode *, basicblock_list> basicblock_map; 00079 typedef basicblock_map::iterator basicblock_map_p; 00080 */ 00081 00082 typedef vector<basicblockNode *> basicblock_vec; 00083 typedef basicblock_vec::iterator basicblock_vec_p; 00084 00085 class DFPreds : public basicblock_set_map_map 00086 { 00087 private: 00088 00089 // --- The procedure to analyze 00090 00091 procNode * _proc; 00092 00093 // --- The root node 00094 00095 basicblockNode * _root; 00096 00097 // --- Basic blocks in depth first order 00098 00099 basicblock_vec df_vec; 00100 00101 // --- Compute 00102 00103 void depth_first_search(basicblockNode * node); 00104 void compute_dominance_frontiers(); 00105 int _index; 00106 00107 public: 00108 00109 DFPreds(procNode * proc); 00110 }; 00111 00112 #endif //