1/* Generic dominator tree walker 2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Diego Novillo <dnovillo@redhat.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, MA 02110-1301, USA. */ 21 22typedef void *void_p; 23DEF_VEC_P(void_p); 24DEF_VEC_ALLOC_P(void_p,heap); 25 26/* This is the main data structure for the dominator walker. It provides 27 the callback hooks as well as a convenient place to hang block local 28 data and pass-global data. */ 29 30struct dom_walk_data 31{ 32 /* This is the direction of the dominator tree we want to walk. i.e., 33 if it is set to CDI_DOMINATORS, then we walk the dominator tree, 34 if it is set to CDI_POST_DOMINATORS, then we walk the post 35 dominator tree. */ 36 ENUM_BITFIELD (cdi_direction) dom_direction : 2; 37 38 /* Nonzero if the statement walker should walk the statements from 39 last to first within a basic block instead of first to last. 40 41 Note this affects both statement walkers. We haven't yet needed 42 to use the second statement walker for anything, so it's hard to 43 predict if we really need the ability to select their direction 44 independently. */ 45 BOOL_BITFIELD walk_stmts_backward : 1; 46 47 /* Function to initialize block local data. 48 49 Note that the dominator walker infrastructure may provide a new 50 fresh, and zero'd block local data structure, or it may re-use an 51 existing block local data structure. 52 53 If the block local structure has items such as virtual arrays, then 54 that allows your optimizer to re-use those arrays rather than 55 creating new ones. */ 56 void (*initialize_block_local_data) (struct dom_walk_data *, 57 basic_block, bool); 58 59 /* Function to call before the statement walk occurring before the 60 recursive walk of the dominator children. 61 62 This typically initializes a block local data and pushes that 63 data onto BLOCK_DATA_STACK. */ 64 void (*before_dom_children_before_stmts) (struct dom_walk_data *, 65 basic_block); 66 67 /* Function to call to walk statements before the recursive walk 68 of the dominator children. */ 69 void (*before_dom_children_walk_stmts) (struct dom_walk_data *, 70 basic_block, block_stmt_iterator); 71 72 /* Function to call after the statement walk occurring before the 73 recursive walk of the dominator children. */ 74 void (*before_dom_children_after_stmts) (struct dom_walk_data *, 75 basic_block); 76 77 /* Function to call before the statement walk occurring after the 78 recursive walk of the dominator children. */ 79 void (*after_dom_children_before_stmts) (struct dom_walk_data *, 80 basic_block); 81 82 /* Function to call to walk statements after the recursive walk 83 of the dominator children. */ 84 void (*after_dom_children_walk_stmts) (struct dom_walk_data *, 85 basic_block, block_stmt_iterator); 86 87 /* Function to call after the statement walk occurring after the 88 recursive walk of the dominator children. 89 90 This typically finalizes any block local data and pops 91 that data from BLOCK_DATA_STACK. */ 92 void (*after_dom_children_after_stmts) (struct dom_walk_data *, 93 basic_block); 94 95 /* Global data for a walk through the dominator tree. */ 96 void *global_data; 97 98 /* Stack of any data we need to keep on a per-block basis. 99 100 If you have no local data, then BLOCK_DATA_STACK will be NULL. */ 101 VEC(void_p,heap) *block_data_stack; 102 103 /* Size of the block local data. If this is zero, then it is assumed 104 you have no local data and thus no BLOCK_DATA_STACK as well. */ 105 size_t block_local_data_size; 106 107 /* From here below are private data. Please do not use this 108 information/data outside domwalk.c. */ 109 110 /* Stack of available block local structures. */ 111 VEC(void_p,heap) *free_block_data; 112 113 /* Interesting blocks to process. If this field is not NULL, this 114 set is used to determine which blocks to walk. If we encounter 115 block I in the dominator traversal, but block I is not present in 116 INTERESTING_BLOCKS, then none of the callback functions are 117 invoked on it. This is useful when a particular traversal wants 118 to filter out non-interesting blocks from the dominator tree. */ 119 sbitmap interesting_blocks; 120}; 121 122void walk_dominator_tree (struct dom_walk_data *, basic_block); 123void init_walk_dominator_tree (struct dom_walk_data *); 124void fini_walk_dominator_tree (struct dom_walk_data *); 125