00001 /* 00002 Copyright (C) 2000-2003, Institute of Computing Technology, Chinese Academy of Sciences 00003 All rights reserved. 00004 00005 Redistribution and use in source and binary forms, with or without modification, 00006 are permitted provided that the following conditions are met: 00007 00008 Redistributions of source code must retain the above copyright notice, this list 00009 of conditions and the following disclaimer. 00010 00011 Redistributions in binary form must reproduce the above copyright notice, this list 00012 of conditions and the following disclaimer in the documentation and/or other materials 00013 provided with the distribution. 00014 00015 Neither the name of the owner nor the names of its contributors may be used to endorse or 00016 promote products derived from this software without specific prior written permission. 00017 00018 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR 00019 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 00020 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR 00021 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00022 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 00023 BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00024 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00025 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00026 */ 00027 00028 //-*-c++-*- 00029 00030 //====================================================================== 00031 // 00032 // Module: global_cycles_finder.cxx 00033 // $Revision: 1.1.1.1 $ 00034 // $Date: 2005/10/21 19:00:00 $ 00035 // $Author: marcel $ 00036 // $Source: /proj/osprey/CVS/open64/osprey1.0/be/cg/orc_ict/global_cycles_finder.cxx,v $ 00037 // 00038 //====================================================================== 00039 00040 #include "global_cycles_finder.h" 00041 00042 //============================================================================ 00043 // 00044 // Find Cycles 00045 // 00046 // Main control function of finding out all cycles. 00047 // 00048 //============================================================================ 00049 void 00050 GLOBAL_CYCLES_FINDER::Find_Global_Cycles(GLOBAL_CYCLE_VECTOR& cycles) { 00051 INT_VECTOR dfn(PU_BB_Count+2, (INT32)0,INT_ALLOC(&_m)); 00052 00053 INT32 next_dfn = 0; 00054 BS *visited = BS_Create_Empty(PU_BB_Count, &_m); 00055 00056 for (BB *bb = REGION_First_BB; bb != NULL; bb = BB_next(bb)) { 00057 Is_True(bb != NULL,("The BB is NULL in Find Global Cycles.")); 00058 if (BB_First_Pred(bb) == NULL) 00059 Detect_Global_Cycle(cycles,bb,dfn,visited,next_dfn); 00060 } 00061 } 00062 00063 void 00064 GLOBAL_CYCLES_FINDER::Detect_Global_Cycle(GLOBAL_CYCLE_VECTOR& cycles, 00065 BB *bb,INT_VECTOR dfn,BS *visited,INT32 next_dfn) { 00066 00067 dfn[BB_id(bb)] = ++next_dfn; 00068 00069 BBLIST *succs; 00070 00071 FOR_ALL_BB_SUCCS(bb, succs) { 00072 BB *succ = BBLIST_item(succs); 00073 Is_True(succ != NULL,("Succ BB is NULL in Detect Global Cycle.")); 00074 00075 if (!BS_MemberP(visited,BB_id(succ))) { 00076 if (dfn[BB_id(succ)] == 0) { 00077 Detect_Global_Cycle(cycles,succ,dfn,visited,next_dfn); 00078 } 00079 else if (dfn[BB_id(succ)] <= dfn[BB_id(bb)]) { 00080 GLOBAL_CYCLE cycle; 00081 cycle.src = bb; 00082 cycle.dest = succ; 00083 cycles.push_back(cycle); 00084 } 00085 } 00086 } 00087 00088 BS_Union1D(visited,BB_id(bb),&_m); 00089 } 00090 00091 void 00092 GLOBAL_CYCLES_FINDER::Print(GLOBAL_CYCLE_VECTOR cycles,FILE *f) { 00093 for (GLOBAL_CYCLE_VECTOR_ITER iter = cycles.begin(); 00094 iter != cycles.end();iter++) { 00095 fprintf(f," The cycle is : "); 00096 fprintf(f," pred %d:",BB_id((*iter).src)); 00097 fprintf(f," succ %d:\n",BB_id((*iter).dest)); 00098 } 00099 }
1.5.6