00001 /* 00002 * Copyright 2004, 2005, 2006 PathScale, Inc. All Rights Reserved. 00003 */ 00004 00005 /* 00006 00007 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00008 00009 This program is free software; you can redistribute it and/or modify it 00010 under the terms of version 2 of the GNU General Public License as 00011 published by the Free Software Foundation. 00012 00013 This program is distributed in the hope that it would be useful, but 00014 WITHOUT ANY WARRANTY; without even the implied warranty of 00015 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00016 00017 Further, this software is distributed without any warranty that it is 00018 free of the rightful claim of any third person regarding infringement 00019 or the like. Any license provided herein, whether implied or 00020 otherwise, applies only to this software file. Patent licenses, if 00021 any, provided herein do not apply to combinations of this program with 00022 other software, or any other product whatsoever. 00023 00024 You should have received a copy of the GNU General Public License along 00025 with this program; if not, write the Free Software Foundation, Inc., 59 00026 Temple Place - Suite 330, Boston MA 02111-1307, USA. 00027 00028 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00029 Mountain View, CA 94043, or: 00030 00031 http://www.sgi.com 00032 00033 For further information regarding this notice, see: 00034 00035 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00036 00037 */ 00038 00039 00040 /* ======================================================================= 00041 * ======================================================================= 00042 * 00043 * Module: gra_live.h 00044 * $Revision: 1.6 $ 00045 * $Date: 05/12/05 08:59:07-08:00 $ 00046 * $Author: bos@eng-24.pathscale.com $ 00047 * $Source: /scratch/mee/2.4-65/kpro64-pending/be/cg/SCCS/s.gra_live.h $ 00048 * 00049 * Revision history: 00050 * 00051 * 26-MAY-93 - Original Version 00052 * 00053 * Description: 00054 * ============ 00055 * 00056 * This module exports a functional interface through which global 00057 * liveness and reaching definition information is initialized before 00058 * scheduling and maintained after scheduling. 00059 * 00060 * The product this analysis are four BB fields: 00061 * 00062 * BB_defreach_in - TN_SET whose members have a definition 00063 * that reaches the entry of the BB. 00064 * BB_defreach_out - TN_SET whose members have a definition 00065 * that reaches the exit of the BB. 00066 * BB_live_in - TN_SET whose members are live at the 00067 * entry to the BB. 00068 * BB_live_out - TN_SET whose members are live at the 00069 * exit to the BB. 00070 * 00071 * Highest level interface 00072 * ======================= 00073 * 00074 * In order to compute liveness for all the blocks in a PU or region, use the 00075 * following functions: 00076 * 00077 * void GRA_LIVE_Init_PU() 00078 * void GRA_LIVE_Finish_PU() 00079 * void GRA_LIVE_Finish_REGION() 00080 * 00081 * Compute/release liveness for all the blocks in the PU or given 00082 * <rid>. 00083 * 00084 * It is required that the _Init_PU or _Init_REGION function be 00085 * called before the package can be used at all. 00086 * 00087 * void GRA_LIVE_Recalc_Liveness() 00088 * 00089 * When pre-GCM phase is enabled, this may result in unnecessary 00090 * growth of GTN sets especially when some of them have been 00091 * converted back to local TNs. This phase does a recalculation of 00092 * global TN sets. 00093 * 00094 * Calculating and updating global local information: 00095 * ===================================================== 00096 * 00097 * extern void GRA_LIVE_Compute_Local_Info( BB *bb ); 00098 * 00099 * Calculating and updating global liveness information: 00100 * ===================================================== 00101 * 00102 * After the local liveness information for each block has been 00103 * calculated, we are ready to calculate global liveness 00104 * information (which is really the only exported product of this 00105 * package.) This is most simply done via 00106 * 00107 * void GRA_LIVE_Compute_GLobal_Live_Info( RID *rid ) 00108 * 00109 * (Re)compute the global live infomation for the 00110 * REGION described by rid, or the entire 00111 * PU flow graph if rid == NULL. 00112 * 00113 * Both GCM and SWP perform transformations on non-scheduled 00114 * blocks that invalidate previously computed liveness info. 00115 * We'd like to be able to the liveness information as cheaply as 00116 * possible. Our approach is to limit the number of blocks that 00117 * need to be considered in the recomputation. 00118 * 00119 * In the case of GCM, the transformations involve moving 00120 * operations between block, possibly duplicating them. In the 00121 * case of SWP, the transformations are of two types: 00122 * 00123 * 1. Creating new unscheduled blocks and splicing them into 00124 * the flow graph. 00125 * 00126 * 2. Adding instructions to the beginning or end of 00127 * unscheduled blocks. 00128 * 00129 * After these sort of transformations are done, we will want to 00130 * recompute liveness informations for a region of the flow 00131 * graph. In the case of SWP, this region may also include 00132 * some scheduled blocks as well, though they will always be 00133 * contiguous for now. 00134 * 00135 * (The following are tailored to the SWP, which is a more 00136 * difficult problem, I think. I haven't given the GCM as much 00137 * thought.) 00138 * 00139 * When new unscheduled blocks are added to the flow graph, their 00140 * liveness information is presented to GRA through the 00141 * GRA_BB_Init interface. See above. 00142 * 00143 * After transformations to an unscheduled block that may change 00144 * its liveness information, it's liveness information must be 00145 * re-presented to the GRA throught the GRA_BB_Init interface. 00146 * See above. 00147 * 00148 * When transformations have been made that may alter the global 00149 * liveness information within a set of blocks, we'll need to 00150 * recompute this. We'd like to avoid recomputing all the 00151 * liveness information for the entire program unit. To do this, 00152 * we define a region of the flow graph within which the changes 00153 * are contained. At the borders of this region, the liveness 00154 * information is assumed not to have changed. The region is 00155 * defined by two sets of BBs: 00156 * 00157 * 1. The "entry-set" of the region which are the blocks 00158 * through which the region may be entred from blocks 00159 * outside the region. 00160 * 00161 * 2. The "exit-set" of the region which are the blocks 00162 * through which the region may be exited to blocks 00163 * outside the region. 00164 * 00165 * Formally, a the entry-set and exit set define a region as follows: 00166 * 00167 * The members of the entry-set are members of the region. 00168 * 00169 * X is member of the region if x is a flow successor of y st 00170 * y is a member of the region and y is not a member of the 00171 * exit-set. 00172 * 00173 * The live_out and defreach_out fields any predecessors of an 00174 * entry block that are not in the region are assumed to be 00175 * unaffected by the transformation. Similarly, the live_in and 00176 * defreach_in fields of any successors of exit blocks that are 00177 * not in the region are assumed to be unaffected by the 00178 * transformation. 00179 * 00180 * void GRA_LIVE_Region_Start(void) 00181 * 00182 * Start the definition of a transformed region of the 00183 * flow-graph. 00184 * 00185 * void GRA_LIVE_Region_Entry( 00186 * BB *bb 00187 * ) 00188 * 00189 * Tells GRA that the given BB, 'bb', is a member of the 00190 * entry-set of region currently being defined. 00191 * 00192 * void GRA_LIVE_Region_Exit( 00193 * BB *bb 00194 * ) 00195 * 00196 * Tells GRA that the givne BB, 'bb', is a member of the 00197 * exit-set of the region currently being defined. 00198 * 00199 * void GRA_LIVE_Region_Compute_Global_Live_Info(void) 00200 * 00201 * Definition of a transformed region is now complete. 00202 * (Re)compute its global liveness information assuming the 00203 * information at the borders is correct. 00204 * 00205 * void GRA_LIVE_Init_Loop(BB *pbb, BB *ebb, 00206 * CG_LOOP_BACKPATCH *pbp, CG_LOOP_BACKPATCH *ebp) 00207 * void GRA_LIVE_Fini_Loop() 00208 * 00209 * Pass prolog/epilog backpatch information to GRA_LIVE. 00210 * At most 1 loop is active at a time. 00211 * The CG_LOOP_BACKPATCH mechanism needs a rewrite 00212 * because it is inaccessible outside cg_loop.cxx. 00213 * 00214 * 00215 * Updating global and live information in a BB_REGION 00216 * =================================================== 00217 * 00218 * Simplfied interface for recompute GRA live info. Fixed a latent bug of the 00219 * older interface. Consider a region composed of basic blocks A, B, C, D, E. 00220 * The CFG is: A->B, B->C,E, C->D. The region we want to specify is {A,B,C}. 00221 * The old interface will use A as the entry, and B,C as exits. The dataflow 00222 * on the edge B->C is not processed. 00223 * 00224 * void BB_REGION_Recompute_Global_Live_Info(const BB_REGION& region, BOOL recompute_local_info) 00225 * Recompute liveness for the region specified by BB_REGION. 00226 * Recompute local liveness if "recompute_local_info" is TRUE. 00227 * 00228 * 00229 * Low level (unstructured) liveness updating 00230 * ========================================== 00231 * 00232 * Sometimes it may be important to calculate liveness information is a 00233 * less structured way than above. For example, we may have the 00234 * following flow graph: 00235 * 00236 * b1 ... 00237 * goto b3 00238 * 00239 * b2 ... 00240 * goto b3 00241 * 00242 * b3 00243 * 00244 * Suppose we are only interested in the live_in data for b1 and we know 00245 * that the live_out data for b3 is correct (but do not know that the 00246 * defreach data for b1, b2 are correct. Using the region based 00247 * approach, we'd have to calculate the live-info for b2 as well as b1 00248 * and we'd have to calculate their defreach data as well. 00249 * 00250 * For these rare situations, we provide: 00251 * 00252 * void GRA_LIVE_Local_Live_Propagate2( 00253 * BB *pred, 00254 * BB *succ 00255 * ) 00256 * 00257 * (Re)calculate the live_in information of 'succ' assuming that it's 00258 * live_out information is correct. Use this to update the live_out 00259 * information of 'pred' and then (re)calculate its live_in 00260 * information. 00261 * 00262 * 00263 * void GRA_LIVE_Local_Live_Propagate( 00264 * BB *bb 00265 * ) 00266 * 00267 * (Re)calculate BB_live_in(bb), assuming that BB_live_out(bb) is 00268 * correct. 00269 * 00270 * 00271 * For an example of the use of thse see the function Create_Loop_Exits_P 00272 * in [n]be/cg/swp_sch_info.c. This function needs the live_in set for a 00273 * loop tail block that it had generated (the SWP winddown code). It 00274 * needs this information in order to generate the best possible loop 00275 * compensation code. The problem is that the flow graph at this point 00276 * is both complex and somewhat incomplete. However, the direct path to 00277 * the loop tail is simple and complete, so it just computes the local 00278 * live info for the two blocks involved, uses 00279 * GRA_LIVE_Local_Live_Propagate2 to propagate through the two block 00280 * path. Later on, all the blocks involved are included in a region that 00281 * has GRA_LIVE_Region_Compute_Global_Live_Info applied to it, which is 00282 * probably a good idea when dealing with siguations like this. 00283 * 00284 * Ultra low level liveness updating 00285 * ================================= 00286 * 00287 * For those times when you really can't live without getting in there and 00288 * munging the sets directly, here are functions to do just that. They are 00289 * added for the exclusive use of GRA, which updates the data structures for 00290 * its own purposes and is the final client for them. 00291 * 00292 * void GRA_LIVE_Add_Live_In_GTN( BB* bb, TN* tn ) 00293 * void GRA_LIVE_Remove_Live_In_GTN( BB* bb, TN* tn ) 00294 * void GRA_LIVE_Add_Live_Out_GTN( BB* bb, TN* tn ) 00295 * void GRA_LIVE_Remove_Live_Out_GTN( BB* bb, TN* tn ) 00296 * void GRA_LIVE_Add_Defreach_In_GTN( BB* bb, TN* tn ) 00297 * void GRA_LIVE_Remove_Defreach_In_GTN( BB* bb, TN* tn ) 00298 * void GRA_LIVE_Add_Defreach_Out_GTN( BB* bb, TN* tn ) 00299 * void GRA_LIVE_Remove_Defreach_Out_GTN( BB* bb, TN* tn ) 00300 * void GRA_LIVE_Add_Live_Use_GTN( BB* bb, TN* tn ) 00301 * void GRA_LIVE_Remove_Live_Use_GTN( BB* bb, TN* tn ) 00302 * 00303 * Directly add/remove 'tn' from the named liveness set of 'bb'. 00304 * 00305 * void GRA_LIVE_Merge_Blocks( BB *dst, BB *a, BB *b ) 00306 * 00307 * Block <b> has been merged with block <a> resulting in 00308 * block <dst>. Adjust the live sets of the merged block. 00309 * 00310 * 00311 * void GRA_LIVE_Compute_Liveness_For_BB( BB *bb ) 00312 * 00313 * Generic utility routine which computes the liveness sets of <bb>. 00314 * 00315 * Checking for liveness 00316 * ===================== 00317 * 00318 * The GRA_LIVE sets can be used to check for liveness of a <tn> 00319 * at either the entry or the exit of a <bb>. These interfaces 00320 * can be used only before register allocation. There is an assumption 00321 * that dedicated TNs are not live across multiple basic blocks. 00322 * 00323 * BOOL GRA_LIVE_TN_Live_Outof_BB (struct tn *tn, BB *bb); 00324 * BOOL GRA_LIVE_TN_Live_Into_BB (struct tn *tn, BB *bb); 00325 * 00326 * NOTE: For liveness information after register allocation use 00327 * the corresponding REG_LIVE interfaces. 00328 * 00329 * 00330 * Debugging & tracing 00331 * =================== 00332 * 00333 * void GRA_LIVE_Print_Liveness( BB* bb ) 00334 * Print the liveness info the <bb>. 00335 * 00336 * ======================================================================= 00337 * ======================================================================= 00338 */ 00339 00340 #ifndef GRA_LIVE_INCLUDED 00341 #define GRA_LIVE_INCLUDED 00342 00343 struct cg_loop_backpatch; 00344 00345 #include "region_util.h" 00346 #include "bb.h" 00347 #include "tn_set.h" 00348 00349 extern GTN_SET* force_live_gtns; /* exported list */ 00350 extern void Force_Live_Add (TN *tn); /* add a TN to the force list */ 00351 extern void Force_Live_Remove (TN *tn); /* remove a TN from the force list */ 00352 00353 extern void GRA_LIVE_Compute_Local_Info( BB *bb ); 00354 extern void GRA_LIVE_Region_Start(void); 00355 extern void GRA_LIVE_Region_Entry( BB *bb ); 00356 extern void GRA_LIVE_Region_Exit( BB *bb ); 00357 extern void GRA_LIVE_Region_Compute_Global_Live_Info(void); 00358 extern void GRA_LIVE_Local_Live_Propagate2( BB *pred, BB *succ ); 00359 extern void GRA_LIVE_Local_Live_Propagate( BB *bb ); 00360 00361 extern void GRA_LIVE_Add_Live_In_GTN( BB* bb, struct tn* tn ); 00362 extern void GRA_LIVE_Remove_Live_In_GTN( BB* bb, struct tn* tn ); 00363 extern void GRA_LIVE_Add_Live_Out_GTN( BB* bb, struct tn* tn ); 00364 extern void GRA_LIVE_Remove_Live_Out_GTN( BB* bb, struct tn* tn ); 00365 extern void GRA_LIVE_Add_Defreach_In_GTN( BB* bb, struct tn* tn ); 00366 extern void GRA_LIVE_Remove_Defreach_In_GTN( BB* bb, struct tn* tn ); 00367 extern void GRA_LIVE_Add_Defreach_Out_GTN( BB* bb, struct tn* tn ); 00368 extern void GRA_LIVE_Remove_Defreach_Out_GTN( BB* bb, struct tn* tn ); 00369 extern void GRA_LIVE_Add_Live_Use_GTN( BB* bb, struct tn* tn ); 00370 extern void GRA_LIVE_Remove_Live_Use_GTN( BB* bb, struct tn* tn ); 00371 extern void GRA_LIVE_Add_Live_Def_GTN( BB* bb, struct tn* tn ); 00372 extern void GRA_LIVE_Remove_Live_Def_GTN( BB* bb, struct tn* tn ); 00373 00374 extern BOOL GRA_LIVE_TN_Live_Outof_BB (struct tn *tn, BB *bb); 00375 extern BOOL GRA_LIVE_TN_Live_Into_BB (struct tn *tn, BB *bb); 00376 00377 extern void GRA_LIVE_Merge_Blocks( BB *dst, BB *a, BB *b ); 00378 extern void GRA_LIVE_Compute_Liveness_For_BB(BB *bb); 00379 00380 extern void GRA_LIVE_Init( RID *rid ); 00381 extern void GRA_LIVE_Recalc_Liveness( RID *rid); 00382 extern void GRA_LIVE_Finish_PU(void); 00383 extern void GRA_LIVE_Finish_REGION(void); 00384 00385 extern void GRA_LIVE_Print_Liveness( BB* bb ); 00386 00387 #ifdef KEY 00388 extern void Rename_TNs_For_BB (BB *bb, TN_SET *multiple_defined_set, 00389 OP *rename_local_TN_op = NULL); 00390 #else 00391 extern void Rename_TNs_For_BB (BB *bb, TN_SET *multiple_defined_set); 00392 #endif 00393 extern void GRA_LIVE_Rename_TNs (void); 00394 extern void BB_REGION_Recompute_Global_Live_Info(const BB_REGION& region, BOOL recompute_local_info); 00395 00396 extern void GRA_LIVE_Detect_GTNs_In_Set (BB_SET *bb_set); 00397 00398 extern void GRA_LIVE_Init_Loop(BB *pbb, BB *bbb, BB *ebb, 00399 struct cg_loop_backpatch *pbp, 00400 struct cg_loop_backpatch *ebp); 00401 extern void GRA_LIVE_Fini_Loop(); 00402 00403 #endif /* GRA_LIVE_INCLUDED */
1.5.6