domwalk.h revision 267654
1109998Smarkm/* Generic dominator tree walker 2280304Sjkim Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3280304Sjkim Contributed by Diego Novillo <dnovillo@redhat.com> 4280304Sjkim 5109998SmarkmThis file is part of GCC. 6109998Smarkm 7109998SmarkmGCC is free software; you can redistribute it and/or modify 8109998Smarkmit under the terms of the GNU General Public License as published by 9109998Smarkmthe Free Software Foundation; either version 2, or (at your option) 10109998Smarkmany later version. 11109998Smarkm 12109998SmarkmGCC is distributed in the hope that it will be useful, 13109998Smarkmbut WITHOUT ANY WARRANTY; without even the implied warranty of 14280304SjkimMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15109998SmarkmGNU General Public License for more details. 16109998Smarkm 17109998SmarkmYou should have received a copy of the GNU General Public License 18109998Smarkmalong with GCC; see the file COPYING. If not, write to 19109998Smarkmthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20109998SmarkmBoston, MA 02110-1301, USA. */ 21109998Smarkm 22109998Smarkmtypedef void *void_p; 23109998SmarkmDEF_VEC_P(void_p); 24109998SmarkmDEF_VEC_ALLOC_P(void_p,heap); 25109998Smarkm 26109998Smarkm/* This is the main data structure for the dominator walker. It provides 27109998Smarkm the callback hooks as well as a convenient place to hang block local 28109998Smarkm data and pass-global data. */ 29109998Smarkm 30109998Smarkmstruct dom_walk_data 31109998Smarkm{ 32109998Smarkm /* This is the direction of the dominator tree we want to walk. i.e., 33109998Smarkm if it is set to CDI_DOMINATORS, then we walk the dominator tree, 34109998Smarkm if it is set to CDI_POST_DOMINATORS, then we walk the post 35109998Smarkm dominator tree. */ 36109998Smarkm ENUM_BITFIELD (cdi_direction) dom_direction : 2; 37109998Smarkm 38109998Smarkm /* Nonzero if the statement walker should walk the statements from 39109998Smarkm last to first within a basic block instead of first to last. 40109998Smarkm 41109998Smarkm Note this affects both statement walkers. We haven't yet needed 42109998Smarkm to use the second statement walker for anything, so it's hard to 43109998Smarkm predict if we really need the ability to select their direction 44109998Smarkm independently. */ 45109998Smarkm BOOL_BITFIELD walk_stmts_backward : 1; 46109998Smarkm 47109998Smarkm /* Function to initialize block local data. 48109998Smarkm 49109998Smarkm Note that the dominator walker infrastructure may provide a new 50109998Smarkm fresh, and zero'd block local data structure, or it may re-use an 51109998Smarkm existing block local data structure. 52109998Smarkm 53109998Smarkm If the block local structure has items such as virtual arrays, then 54109998Smarkm that allows your optimizer to re-use those arrays rather than 55109998Smarkm creating new ones. */ 56109998Smarkm void (*initialize_block_local_data) (struct dom_walk_data *, 57109998Smarkm basic_block, bool); 58109998Smarkm 59109998Smarkm /* Function to call before the statement walk occurring before the 60109998Smarkm recursive walk of the dominator children. 61109998Smarkm 62109998Smarkm This typically initializes a block local data and pushes that 63109998Smarkm data onto BLOCK_DATA_STACK. */ 64109998Smarkm void (*before_dom_children_before_stmts) (struct dom_walk_data *, 65109998Smarkm basic_block); 66109998Smarkm 67109998Smarkm /* Function to call to walk statements before the recursive walk 68109998Smarkm of the dominator children. */ 69109998Smarkm void (*before_dom_children_walk_stmts) (struct dom_walk_data *, 70109998Smarkm basic_block, block_stmt_iterator); 71280304Sjkim 72280304Sjkim /* Function to call after the statement walk occurring before the 73280304Sjkim recursive walk of the dominator children. */ 74109998Smarkm void (*before_dom_children_after_stmts) (struct dom_walk_data *, 75109998Smarkm basic_block); 76280304Sjkim 77280304Sjkim /* Function to call before the statement walk occurring after the 78280304Sjkim recursive walk of the dominator children. */ 79280304Sjkim void (*after_dom_children_before_stmts) (struct dom_walk_data *, 80280304Sjkim basic_block); 81280304Sjkim 82280304Sjkim /* Function to call to walk statements after the recursive walk 83280304Sjkim of the dominator children. */ 84280304Sjkim void (*after_dom_children_walk_stmts) (struct dom_walk_data *, 85280304Sjkim basic_block, block_stmt_iterator); 86280304Sjkim 87280304Sjkim /* Function to call after the statement walk occurring after the 88280304Sjkim recursive walk of the dominator children. 89109998Smarkm 90280304Sjkim This typically finalizes any block local data and pops 91280304Sjkim that data from BLOCK_DATA_STACK. */ 92280304Sjkim void (*after_dom_children_after_stmts) (struct dom_walk_data *, 93280304Sjkim basic_block); 94109998Smarkm 95109998Smarkm /* Global data for a walk through the dominator tree. */ 96280304Sjkim void *global_data; 97280304Sjkim 98280304Sjkim /* Stack of any data we need to keep on a per-block basis. 99280304Sjkim 100280304Sjkim If you have no local data, then BLOCK_DATA_STACK will be NULL. */ 101280304Sjkim VEC(void_p,heap) *block_data_stack; 102280304Sjkim 103109998Smarkm /* Size of the block local data. If this is zero, then it is assumed 104109998Smarkm you have no local data and thus no BLOCK_DATA_STACK as well. */ 105109998Smarkm size_t block_local_data_size; 106109998Smarkm 107109998Smarkm /* From here below are private data. Please do not use this 108109998Smarkm information/data outside domwalk.c. */ 109109998Smarkm 110280304Sjkim /* Stack of available block local structures. */ 111109998Smarkm VEC(void_p,heap) *free_block_data; 112280304Sjkim 113280304Sjkim /* Interesting blocks to process. If this field is not NULL, this 114109998Smarkm set is used to determine which blocks to walk. If we encounter 115109998Smarkm block I in the dominator traversal, but block I is not present in 116280304Sjkim INTERESTING_BLOCKS, then none of the callback functions are 117109998Smarkm invoked on it. This is useful when a particular traversal wants 118280304Sjkim to filter out non-interesting blocks from the dominator tree. */ 119109998Smarkm sbitmap interesting_blocks; 120109998Smarkm}; 121109998Smarkm 122109998Smarkmvoid walk_dominator_tree (struct dom_walk_data *, basic_block); 123280304Sjkimvoid init_walk_dominator_tree (struct dom_walk_data *); 124280304Sjkimvoid fini_walk_dominator_tree (struct dom_walk_data *); 125280304Sjkim