00001 /* 00002 * Copyright 2003, 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 *** WN walk, insert and copy routines 00042 *** 00043 *** Description: 00044 *** 00045 *** This file contains routines that operate on a given WHIRL tree 00046 *** The operations performed on the tree include walking the tree 00047 *** inserting a node into a block of nodes and copying a tree 00048 *** 00049 *** 00050 *** Reserved prefix: 00051 *** WN_WALK for WHIRL node walk routines 00052 *** WN_INSERT for WHIRL node insert routines 00053 *** WN_COPY for WHIRL node copy routines 00054 *** WN_DELETE for WHIRL node delete routines 00055 *** WN_EXTRACT for WHIRL node extraction (but not delete) routines 00056 *** WN_LOOP for WHIRL node loop routines 00057 *** 00058 *** 00059 *** 00060 *** Exported types: 00061 *** 00062 *** 00063 *** WN_ITER 00064 *** 00065 *** A tree node iterator. This type has one client visible field 00066 *** 00067 *** WN *wn 00068 *** 00069 *** Gives the current tree node. 00070 *** 00071 *** 00072 *** 00073 *** Exported functions: 00074 *** 00075 *** 00076 *** WN_ITER* WN_WALK_TreeIter( 00077 *** WN* wn) 00078 *** 00079 *** 00080 *** Creates and returns a tree iterator. The tree iterator iterates over 00081 *** all nodes in the tree including structured control flow nodes, 00082 *** statement nodes, and expression nodes 00083 *** 00084 *** 00085 *** WN_ITER* WN_WALK_TreeNext( 00086 *** WN_ITER *wni) 00087 *** 00088 *** 00089 *** Walks the tree in preorder and returns the tree iterator 00090 *** containing the next node in the tree walk 00091 *** 00092 *** 00093 *** 00094 *** WN_ITER *WN_WALK_SCFIter( 00095 *** WN_ITER *wni) 00096 *** 00097 *** 00098 *** Creates and returns a tree iterator. The tree iterator iterates over 00099 *** nodes at the structured control flow level 00100 *** 00101 *** 00102 *** WN_ITER *WN_WALK_SCFNext( 00103 *** WN_ITER *wni) 00104 *** 00105 *** Walks the tree in preorder and returns the next node whose 00106 *** opcode falls into the structured control flow category 00107 *** 00108 *** 00109 *** 00110 *** WN_ITER *WN_WALK_StmtIter( 00111 *** WN *wn) 00112 *** 00113 *** Creates and returns a tree iterator. The tree iterator will return 00114 *** all statement nodes and structured control flow nodes. For expressions 00115 *** it will only return them if they are kids of structured control flow 00116 *** nodes. 00117 *** 00118 *** 00119 *** 00120 *** WN_ITER *WN_WALK_StmtNext( 00121 *** WN_ITER *wni) 00122 *** 00123 *** Walks the tree in preorder and returns the next node, the node 00124 *** must fall into the category described in WN_StmtIter 00125 *** 00126 *** 00127 *** 00128 *** WN_ITER *WN_WALK_Abort( 00129 *** WN_ITER *wni) 00130 *** 00131 *** To exit prematurely from a tree walk a call to this routine must 00132 *** be made. It frees the data structures used during a walk operation 00133 *** 00134 *** 00135 *** 00136 *** void WN_INSERT_BlockBefore( 00137 *** WN* b, 00138 *** WN* wn, 00139 *** WN* in) 00140 *** 00141 *** To insert a node before a given node in a block node. Node "in" is 00142 *** inserted before node "wn" in block "b". Note, wn may be NULL, in that 00143 *** case "in" is inserted at the end. Also, "in" may be a block, 00144 *** in which case all the statements in the block are inserted 00145 *** 00146 *** void WN_INSERT_BlockFirst( 00147 *** WN* b, 00148 *** WN* in) 00149 *** 00150 *** To insert a node before the first node in a block. Note, "in" may be 00151 *** a block, in which case all the statements in the block are inserted. 00152 *** 00153 *** 00154 *** void WN_INSERT_BlockAfter( 00155 *** WN* b, 00156 *** WN* wn, 00157 *** WN* in) 00158 *** 00159 *** To insert a node after a given node in a block node. Node "in" is 00160 *** inserted after node "wn" in block "b". Note, "wn" may be NULL, in that 00161 *** case "in" is inserted at the beginning. Also, "in" may be a block, 00162 *** in which case all the statements in the block are inserted 00163 *** 00164 *** void WN_INSERT_BlockLast( 00165 *** WN* b, 00166 *** WN* in) 00167 *** 00168 *** To insert a node after the last node in a block. Note, "in" may be 00169 *** a block, in which case all the statements in the block are inserted. 00170 *** 00171 *** 00172 *** 00173 *** WN* WN_COPY_Tree( 00174 *** WN* wn) 00175 *** 00176 *** To copy node wn. 00177 *** No annotations are copied at this point. This is strictly a tree copy, 00178 *** and a recursive one 00179 *** 00180 *** 00181 *** WN* WN_COPY_Tree_With_Map( 00182 *** WN* wn) 00183 *** 00184 *** To copy node wn and its map. 00185 *** This is strictly a tree copy, and a recursive one 00186 *** 00187 *** 00188 *** void WN_COPY_All_Maps( 00189 *** WN* dst, 00190 *** WN* src) 00191 *** 00192 *** To copy all maps from src to dst. 00193 *** 00194 *** 00195 *** void WN_DELETE_Tree( 00196 *** WN *tree) 00197 *** 00198 *** Deletes a tree recursively. No annotations are deleted at this point. 00199 *** 00200 *** 00201 *** WN* WN_DELETE_FromBlock( 00202 *** WN* blck, 00203 *** WN* wn) 00204 *** 00205 *** To delete node "wn" from a BLOCK node. Note, WN_DELETE_Tree is called 00206 *** which is a recursive delete, it deletes all the kids. 00207 *** 00208 *** WN *WN_EXTRACT_FromBlock( 00209 *** WN *parent, 00210 *** WN *item) 00211 *** 00212 *** Extract node "item" from a BLOCK, but don't delete it. 00213 *** 00214 *** WN *WN_EXTRACT_ItemsFromBlock( 00215 *** WN *parent, 00216 *** WN *first_item, 00217 *** WN *last_item) 00218 *** Extract nodes between first_item and last_item from a BLOCK, 00219 *** but don't delete them. 00220 *** 00221 *** WN *WN_LOOP_InductionVariable( 00222 *** const WN *loop) 00223 *** 00224 *** Determine the loop's induction variable. Returns either an 00225 *** IDNAME or LDID. If unable to determine it, returns NULL. 00226 *** 00227 *** WN *WN_LOOP_LowerBound( 00228 *** const WN *loop) 00229 *** 00230 *** Determine the lower bound of the loop, which is basically 00231 *** the value stored to the induction variable to initialize 00232 *** the loop. If unable to determine it, returns NULL. 00233 *** 00234 *** WN *WN_LOOP_UpperBound( 00235 *** const WN *loop, 00236 *** OPCODE *compare) 00237 *** 00238 *** Determine the upper bound of the loop, which is basically 00239 *** the value which can not be exceeded (going in either 00240 *** direction (positive dir if increment is positive, or 00241 *** negative direction is increment is negative 00242 *** Also returns the comparison operator to know how the iv is 00243 *** related to this upper bound. We canonicalize it so the iv 00244 *** is always on the lhs of the comparison, and the upper bound 00245 *** is always on the rhs: iv <,<=,==,!=,>=,> upper bound 00246 *** If unable to determine it, returns NULL. 00247 *** 00248 *** WN *WN_LOOP_Increment( 00249 *** const WN *loop, 00250 *** BOOL *is_incr) 00251 *** 00252 *** Determine the increment (if is_incr = TRUE) value 00253 *** the value which can not be exceeded (going in either 00254 *** direction (positive dir if is_incr is true, or negative 00255 *** direction if is_incr is false (actually decrements iv) 00256 *** If unable to determine it, returns NULL. 00257 *** 00258 *** WN *WN_LOOP_TripCount( 00259 *** const WN *loop) 00260 *** 00261 *** Determine the trip count, which may be a LDID, or INTCONST 00262 *** If unable to determine it, returns NULL. 00263 *** 00264 *** WN_object_ty(const WN *) 00265 *** Obtain the high level type of the object being accessed. 00266 *** 00267 *** WN_hl_object_ty (const WN*, TY_IDX& ty, UINT32& fld_id) 00268 *** Obtain the higher level type of object being accessed. 00269 *** 00270 *** WN_object_size(const WN *) 00271 *** Obtain the size of the object being accessed. 00272 *** 00273 *** 00274 *** 00275 *** 00276 *** 00277 *** void Add_Pragma_To_MP_Regions (WN_VECTOR *wnv, 00278 *** WN_PRAGMA_ID pragma_id, 00279 *** ST *st, WN_OFFSET ofst, 00280 *** WN_MAP parent_map, 00281 *** BOOL make_compiler_generated) 00282 *** Given a vector of WHIRL-MP regions innermost to outermost 00283 *** (i.e. the innermost MP region is first, outermost is last) 00284 *** add a pragma of the given type for the given ST *as required* 00285 *** to the MP regions. The algorithm for adding pragmas 00286 *** currently works for LOCAL and SHARED pragmas only. 00287 *** Also, if the parent_map is non-NULL, then update the 00288 *** parent-map when inserting. 00289 *** 00290 *** 00291 ***------------------------------------------------------------------*/ 00292 00293 00301 #ifndef wn_util_INCLUDED 00302 #define wn_util_INCLUDED 00303 00304 #include "wn.h" 00305 00306 #ifdef __cplusplus 00307 extern "C" { 00308 #endif 00309 00310 typedef struct wn_stack{ 00311 WN** stack; 00312 WN** sp; 00313 INT size; 00314 } WN_STACK; 00315 00316 typedef struct wn_iter { 00317 WN *wn; /* current tree node */ 00318 WN_STACK *stack; /* stack used during the walk */ 00319 } WN_ITER; 00320 00321 /* access macro */ 00322 00323 #define WN_STACK_stack(wns) ((wns)->stack) 00324 #define WN_STACK_sp(wns) ((wns)->sp) 00325 #define WN_STACK_size(wns) ((wns)->size) 00326 00327 #define WN_ITER_wn(wni) ((wni)->wn) 00328 #define WN_ITER_stack(wni) ((wni)->stack) 00329 00330 extern WN_ITER* WN_WALK_TreeIter( 00331 WN* 00332 ); 00333 00334 extern WN_ITER* WN_WALK_TreeNext( 00335 WN_ITER* 00336 ); 00337 00338 extern WN_ITER* WN_WALK_StmtIter( 00339 WN* 00340 ); 00341 00342 extern WN_ITER* WN_WALK_StmtNext( 00343 WN_ITER* 00344 ); 00345 00346 extern WN_ITER* WN_WALK_SCFIter( 00347 WN *wn 00348 ); 00349 00350 extern WN_ITER* WN_WALK_SCFNext( 00351 WN_ITER* 00352 ); 00353 00354 extern void WN_WALK_Abort( 00355 WN_ITER* 00356 ); 00357 00358 extern void WN_INSERT_BlockBefore( 00359 WN* b, 00360 WN* wn, 00361 WN* in 00362 ); 00363 00364 #define WN_INSERT_BlockFirst(b, in) \ 00365 WN_INSERT_BlockBefore(b, WN_first(b), in) 00366 00367 extern void WN_INSERT_BlockAfter( 00368 WN* b, 00369 WN* wn, 00370 WN* in 00371 ); 00372 00373 #define WN_INSERT_BlockLast(b, in) \ 00374 WN_INSERT_BlockAfter(b, WN_last(b), in) 00375 00376 extern WN* WN_COPY_Tree( 00377 WN *tree_node 00378 ); 00379 00380 extern WN* WN_COPY_Tree_With_Map( 00381 WN *tree_node 00382 ); 00383 00384 extern void WN_COPY_All_Maps( 00385 WN *dst, 00386 WN *src 00387 ); 00388 00389 extern void WN_DELETE_Tree( 00390 WN* tree 00391 ); 00392 00393 extern void WN_DELETE_FromBlock( 00394 WN *blck, 00395 WN *wn 00396 ); 00397 00398 WN *WN_EXTRACT_FromBlock( 00399 WN *parent, 00400 WN *item 00401 ); 00402 00403 WN *WN_EXTRACT_ItemsFromBlock( 00404 WN *parent, 00405 WN *first_item, 00406 WN *last_item 00407 ); 00408 00409 WN *WN_LOOP_LowerBound( 00410 const WN *loop 00411 ); 00412 00413 WN *WN_LOOP_UpperBound( 00414 const WN *loop, 00415 OPCODE *compare, 00416 #ifdef KEY 00417 BOOL enhanced = FALSE 00418 #endif 00419 ); 00420 00421 WN *WN_LOOP_Increment( 00422 const WN *loop, 00423 BOOL *is_incr 00424 ); 00425 00426 WN *WN_LOOP_TripCount( 00427 const WN *loop, 00428 #ifdef KEY 00429 BOOL enhanced = FALSE 00430 #endif 00431 ); 00432 00433 WN *WN_LOOP_InductionVariable( 00434 const WN *loop 00435 ); 00436 00437 00438 00439 /* Other WN utilities */ 00440 00441 /* Obtain the high-level type of the item accessed */ 00442 extern TY_IDX WN_object_ty(const WN *); 00443 00444 /* Obtain the higher level type of object being accessed. */ 00445 extern void WN_hl_object_ty (const WN*, TY_IDX& ty, UINT32& fld_id); 00446 00447 /* Obtain the size of object being accessed */ 00448 extern INT32 WN_object_size(const WN *); 00449 00450 inline BOOL WN_is_black_box(const WN *wn) 00451 { 00452 return OPCODE_is_black_box( WN_opcode(wn) ); 00453 } 00454 00455 #ifdef __cplusplus 00456 } /* close extern "C" */ 00457 00458 00459 /* Needed for the STL vector class used below 00460 */ 00461 #include "vector" 00462 #include "mempool_allocator.h" 00463 00464 typedef mempool_allocator<WN*> VEC_POOL_ALLOCATOR; 00465 typedef vector<WN*, VEC_POOL_ALLOCATOR> WN_VECTOR; 00466 00467 typedef std::vector< bool, mempool_allocator<bool> > BOOL_VECTOR; 00468 00469 extern "C" void Add_Pragma_To_MP_Regions (WN_VECTOR *wnv, 00470 WN_PRAGMA_ID pragma_id, 00471 ST *st, WN_OFFSET ofst, 00472 WN_MAP parent_map, 00473 BOOL make_compiler_generated); 00474 00475 #endif /* __cplusplus */ 00476 00477 #endif /* wn_util_INCLUDED */
1.5.6