domwalk.h revision 169689
153469Sobrien/* Generic dominator tree walker 2126432Sache Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 353469Sobrien Contributed by Diego Novillo <dnovillo@redhat.com> 453469Sobrien 553469SobrienThis file is part of GCC. 653469Sobrien 753469SobrienGCC is free software; you can redistribute it and/or modify 853469Sobrienit under the terms of the GNU General Public License as published by 953469Sobrienthe Free Software Foundation; either version 2, or (at your option) 1053469Sobrienany later version. 1153469Sobrien 1253469SobrienGCC is distributed in the hope that it will be useful, 1353469Sobrienbut WITHOUT ANY WARRANTY; without even the implied warranty of 1453469SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1553469SobrienGNU General Public License for more details. 1653469Sobrien 1753469SobrienYou should have received a copy of the GNU General Public License 1853469Sobrienalong with GCC; see the file COPYING. If not, write to 1953469Sobrienthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 2053469SobrienBoston, MA 02110-1301, USA. */ 2153469Sobrien 2253469Sobrientypedef void *void_p; 2353469SobrienDEF_VEC_P(void_p); 2453469SobrienDEF_VEC_ALLOC_P(void_p,heap); 2553469Sobrien 2653469Sobrien/* This is the main data structure for the dominator walker. It provides 2753469Sobrien the callback hooks as well as a convenient place to hang block local 2853469Sobrien data and pass-global data. */ 2953469Sobrien 3053469Sobrienstruct dom_walk_data 3153469Sobrien{ 3253469Sobrien /* This is the direction of the dominator tree we want to walk. i.e., 3353469Sobrien if it is set to CDI_DOMINATORS, then we walk the dominator tree, 3453469Sobrien if it is set to CDI_POST_DOMINATORS, then we walk the post 3553469Sobrien dominator tree. */ 3653469Sobrien ENUM_BITFIELD (cdi_direction) dom_direction : 2; 3753469Sobrien 3853469Sobrien /* Nonzero if the statement walker should walk the statements from 3955360Sobrien last to first within a basic block instead of first to last. 4055360Sobrien 4153469Sobrien Note this affects both statement walkers. We haven't yet needed 4253469Sobrien to use the second statement walker for anything, so it's hard to 4353469Sobrien predict if we really need the ability to select their direction 4453469Sobrien independently. */ 4553469Sobrien BOOL_BITFIELD walk_stmts_backward : 1; 4653469Sobrien 4753469Sobrien /* Function to initialize block local data. 4853469Sobrien 4953469Sobrien Note that the dominator walker infrastructure may provide a new 5053469Sobrien fresh, and zero'd block local data structure, or it may re-use an 5153469Sobrien existing block local data structure. 5253469Sobrien 5353469Sobrien If the block local structure has items such as virtual arrays, then 5453469Sobrien that allows your optimizer to re-use those arrays rather than 5553469Sobrien creating new ones. */ 56131554Stjr void (*initialize_block_local_data) (struct dom_walk_data *, 57131554Stjr basic_block, bool); 58131554Stjr 59131554Stjr /* Function to call before the statement walk occurring before the 6053469Sobrien recursive walk of the dominator children. 6153469Sobrien 6253469Sobrien This typically initializes a block local data and pushes that 6353469Sobrien data onto BLOCK_DATA_STACK. */ 6453469Sobrien void (*before_dom_children_before_stmts) (struct dom_walk_data *, 6553469Sobrien basic_block); 6653469Sobrien 6753469Sobrien /* Function to call to walk statements before the recursive walk 6853469Sobrien of the dominator children. */ 6953469Sobrien void (*before_dom_children_walk_stmts) (struct dom_walk_data *, 7053469Sobrien basic_block, block_stmt_iterator); 7153469Sobrien 7253469Sobrien /* Function to call after the statement walk occurring before the 7353469Sobrien recursive walk of the dominator children. */ 7453469Sobrien void (*before_dom_children_after_stmts) (struct dom_walk_data *, 7553469Sobrien basic_block); 7653469Sobrien 7753469Sobrien /* Function to call before the statement walk occurring after the 7853469Sobrien recursive walk of the dominator children. */ 7953469Sobrien void (*after_dom_children_before_stmts) (struct dom_walk_data *, 8053469Sobrien basic_block); 81131554Stjr 82131554Stjr /* Function to call to walk statements after the recursive walk 83131554Stjr of the dominator children. */ 8453469Sobrien void (*after_dom_children_walk_stmts) (struct dom_walk_data *, 8553469Sobrien basic_block, block_stmt_iterator); 8653469Sobrien 87131554Stjr /* Function to call after the statement walk occurring after the 8853469Sobrien recursive walk of the dominator children. 89131554Stjr 9053469Sobrien This typically finalizes any block local data and pops 9153469Sobrien that data from BLOCK_DATA_STACK. */ 9253469Sobrien void (*after_dom_children_after_stmts) (struct dom_walk_data *, 9353469Sobrien basic_block); 9453469Sobrien 9553469Sobrien /* Global data for a walk through the dominator tree. */ 9653469Sobrien void *global_data; 9753469Sobrien 9853469Sobrien /* Stack of any data we need to keep on a per-block basis. 9953469Sobrien 10053469Sobrien If you have no local data, then BLOCK_DATA_STACK will be NULL. */ 10153469Sobrien VEC(void_p,heap) *block_data_stack; 10253469Sobrien 10355360Sobrien /* Size of the block local data. If this is zero, then it is assumed 10453469Sobrien you have no local data and thus no BLOCK_DATA_STACK as well. */ 10553469Sobrien size_t block_local_data_size; 10653469Sobrien 10753469Sobrien /* From here below are private data. Please do not use this 10855360Sobrien information/data outside domwalk.c. */ 10955360Sobrien 11055360Sobrien /* Stack of available block local structures. */ 11153469Sobrien VEC(void_p,heap) *free_block_data; 11253469Sobrien 11353469Sobrien /* Interesting blocks to process. If this field is not NULL, this 11453469Sobrien set is used to determine which blocks to walk. If we encounter 11555360Sobrien block I in the dominator traversal, but block I is not present in 11653469Sobrien INTERESTING_BLOCKS, then none of the callback functions are 11753469Sobrien invoked on it. This is useful when a particular traversal wants 11853469Sobrien to filter out non-interesting blocks from the dominator tree. */ 11953469Sobrien sbitmap interesting_blocks; 12053469Sobrien}; 12153469Sobrien 12253469Sobrienvoid walk_dominator_tree (struct dom_walk_data *, basic_block); 12353469Sobrienvoid init_walk_dominator_tree (struct dom_walk_data *); 12453469Sobrienvoid fini_walk_dominator_tree (struct dom_walk_data *); 12553469Sobrien