1169689Skan/* Generic dominator tree walker 2169689Skan Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Diego Novillo <dnovillo@redhat.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanit under the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2, or (at your option) 10169689Skanany later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21169689Skan 22169689Skantypedef void *void_p; 23169689SkanDEF_VEC_P(void_p); 24169689SkanDEF_VEC_ALLOC_P(void_p,heap); 25169689Skan 26169689Skan/* This is the main data structure for the dominator walker. It provides 27169689Skan the callback hooks as well as a convenient place to hang block local 28169689Skan data and pass-global data. */ 29169689Skan 30169689Skanstruct dom_walk_data 31169689Skan{ 32169689Skan /* This is the direction of the dominator tree we want to walk. i.e., 33169689Skan if it is set to CDI_DOMINATORS, then we walk the dominator tree, 34169689Skan if it is set to CDI_POST_DOMINATORS, then we walk the post 35169689Skan dominator tree. */ 36169689Skan ENUM_BITFIELD (cdi_direction) dom_direction : 2; 37169689Skan 38169689Skan /* Nonzero if the statement walker should walk the statements from 39169689Skan last to first within a basic block instead of first to last. 40169689Skan 41169689Skan Note this affects both statement walkers. We haven't yet needed 42169689Skan to use the second statement walker for anything, so it's hard to 43169689Skan predict if we really need the ability to select their direction 44169689Skan independently. */ 45169689Skan BOOL_BITFIELD walk_stmts_backward : 1; 46169689Skan 47169689Skan /* Function to initialize block local data. 48169689Skan 49169689Skan Note that the dominator walker infrastructure may provide a new 50169689Skan fresh, and zero'd block local data structure, or it may re-use an 51169689Skan existing block local data structure. 52169689Skan 53169689Skan If the block local structure has items such as virtual arrays, then 54169689Skan that allows your optimizer to re-use those arrays rather than 55169689Skan creating new ones. */ 56169689Skan void (*initialize_block_local_data) (struct dom_walk_data *, 57169689Skan basic_block, bool); 58169689Skan 59169689Skan /* Function to call before the statement walk occurring before the 60169689Skan recursive walk of the dominator children. 61169689Skan 62169689Skan This typically initializes a block local data and pushes that 63169689Skan data onto BLOCK_DATA_STACK. */ 64169689Skan void (*before_dom_children_before_stmts) (struct dom_walk_data *, 65169689Skan basic_block); 66169689Skan 67169689Skan /* Function to call to walk statements before the recursive walk 68169689Skan of the dominator children. */ 69169689Skan void (*before_dom_children_walk_stmts) (struct dom_walk_data *, 70169689Skan basic_block, block_stmt_iterator); 71169689Skan 72169689Skan /* Function to call after the statement walk occurring before the 73169689Skan recursive walk of the dominator children. */ 74169689Skan void (*before_dom_children_after_stmts) (struct dom_walk_data *, 75169689Skan basic_block); 76169689Skan 77169689Skan /* Function to call before the statement walk occurring after the 78169689Skan recursive walk of the dominator children. */ 79169689Skan void (*after_dom_children_before_stmts) (struct dom_walk_data *, 80169689Skan basic_block); 81169689Skan 82169689Skan /* Function to call to walk statements after the recursive walk 83169689Skan of the dominator children. */ 84169689Skan void (*after_dom_children_walk_stmts) (struct dom_walk_data *, 85169689Skan basic_block, block_stmt_iterator); 86169689Skan 87169689Skan /* Function to call after the statement walk occurring after the 88169689Skan recursive walk of the dominator children. 89169689Skan 90169689Skan This typically finalizes any block local data and pops 91169689Skan that data from BLOCK_DATA_STACK. */ 92169689Skan void (*after_dom_children_after_stmts) (struct dom_walk_data *, 93169689Skan basic_block); 94169689Skan 95169689Skan /* Global data for a walk through the dominator tree. */ 96169689Skan void *global_data; 97169689Skan 98169689Skan /* Stack of any data we need to keep on a per-block basis. 99169689Skan 100169689Skan If you have no local data, then BLOCK_DATA_STACK will be NULL. */ 101169689Skan VEC(void_p,heap) *block_data_stack; 102169689Skan 103169689Skan /* Size of the block local data. If this is zero, then it is assumed 104169689Skan you have no local data and thus no BLOCK_DATA_STACK as well. */ 105169689Skan size_t block_local_data_size; 106169689Skan 107169689Skan /* From here below are private data. Please do not use this 108169689Skan information/data outside domwalk.c. */ 109169689Skan 110169689Skan /* Stack of available block local structures. */ 111169689Skan VEC(void_p,heap) *free_block_data; 112169689Skan 113169689Skan /* Interesting blocks to process. If this field is not NULL, this 114169689Skan set is used to determine which blocks to walk. If we encounter 115169689Skan block I in the dominator traversal, but block I is not present in 116169689Skan INTERESTING_BLOCKS, then none of the callback functions are 117169689Skan invoked on it. This is useful when a particular traversal wants 118169689Skan to filter out non-interesting blocks from the dominator tree. */ 119169689Skan sbitmap interesting_blocks; 120169689Skan}; 121169689Skan 122169689Skanvoid walk_dominator_tree (struct dom_walk_data *, basic_block); 123169689Skanvoid init_walk_dominator_tree (struct dom_walk_data *); 124169689Skanvoid fini_walk_dominator_tree (struct dom_walk_data *); 125