1*38fd1498Szrj /* Generic dominator tree walker 2*38fd1498Szrj Copyright (C) 2003-2018 Free Software Foundation, Inc. 3*38fd1498Szrj Contributed by Diego Novillo <dnovillo@redhat.com> 4*38fd1498Szrj 5*38fd1498Szrj This file is part of GCC. 6*38fd1498Szrj 7*38fd1498Szrj GCC is free software; you can redistribute it and/or modify 8*38fd1498Szrj it under the terms of the GNU General Public License as published by 9*38fd1498Szrj the Free Software Foundation; either version 3, or (at your option) 10*38fd1498Szrj any later version. 11*38fd1498Szrj 12*38fd1498Szrj GCC is distributed in the hope that it will be useful, 13*38fd1498Szrj but WITHOUT ANY WARRANTY; without even the implied warranty of 14*38fd1498Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15*38fd1498Szrj GNU General Public License for more details. 16*38fd1498Szrj 17*38fd1498Szrj You should have received a copy of the GNU General Public License 18*38fd1498Szrj along with GCC; see the file COPYING3. If not see 19*38fd1498Szrj <http://www.gnu.org/licenses/>. */ 20*38fd1498Szrj 21*38fd1498Szrj #ifndef GCC_DOM_WALK_H 22*38fd1498Szrj #define GCC_DOM_WALK_H 23*38fd1498Szrj 24*38fd1498Szrj /** 25*38fd1498Szrj * This is the main class for the dominator walker. It is expected that 26*38fd1498Szrj * consumers will have a custom class inheriting from it, which will over ride 27*38fd1498Szrj * at least one of before_dom_children and after_dom_children to implement the 28*38fd1498Szrj * custom behavior. 29*38fd1498Szrj */ 30*38fd1498Szrj class dom_walker 31*38fd1498Szrj { 32*38fd1498Szrj public: 33*38fd1498Szrj static const edge STOP; 34*38fd1498Szrj 35*38fd1498Szrj /* An enum for determining whether the dom walk should be constrained to 36*38fd1498Szrj blocks reachable by executable edges. */ 37*38fd1498Szrj 38*38fd1498Szrj enum reachability 39*38fd1498Szrj { 40*38fd1498Szrj /* Walk all blocks within the CFG. */ 41*38fd1498Szrj ALL_BLOCKS, 42*38fd1498Szrj 43*38fd1498Szrj /* Use REACHABLE_BLOCKS when your subclass can discover that some edges 44*38fd1498Szrj are not executable. 45*38fd1498Szrj 46*38fd1498Szrj If a subclass can discover that a COND, SWITCH or GOTO has a static 47*38fd1498Szrj target in the before_dom_children callback, the taken edge should 48*38fd1498Szrj be returned. The generic walker will clear EDGE_EXECUTABLE on all 49*38fd1498Szrj edges it can determine are not executable. 50*38fd1498Szrj 51*38fd1498Szrj With REACHABLE_BLOCKS, EDGE_EXECUTABLE will be set on every edge in 52*38fd1498Szrj the dom_walker ctor; the flag will then be cleared on edges that are 53*38fd1498Szrj determined to be not executable. */ 54*38fd1498Szrj REACHABLE_BLOCKS, 55*38fd1498Szrj 56*38fd1498Szrj /* Identical to REACHABLE_BLOCKS, but the initial state of EDGE_EXECUTABLE 57*38fd1498Szrj will instead be preserved in the ctor, allowing for information about 58*38fd1498Szrj non-executable edges to be merged in from an earlier analysis (and 59*38fd1498Szrj potentially for additional edges to be marked as non-executable). */ 60*38fd1498Szrj REACHABLE_BLOCKS_PRESERVING_FLAGS 61*38fd1498Szrj }; 62*38fd1498Szrj 63*38fd1498Szrj dom_walker (cdi_direction direction, enum reachability = ALL_BLOCKS); 64*38fd1498Szrj 65*38fd1498Szrj /* You can provide a mapping of basic-block index to RPO if you 66*38fd1498Szrj have that readily available or you do multiple walks. If you 67*38fd1498Szrj specify NULL as BB_INDEX_TO_RPO dominator children will not be 68*38fd1498Szrj walked in RPO order. */ 69*38fd1498Szrj dom_walker (cdi_direction direction, enum reachability, int *bb_index_to_rpo); 70*38fd1498Szrj 71*38fd1498Szrj ~dom_walker (); 72*38fd1498Szrj 73*38fd1498Szrj /* Walk the dominator tree. */ 74*38fd1498Szrj void walk (basic_block); 75*38fd1498Szrj 76*38fd1498Szrj /* Function to call before the recursive walk of the dominator children. 77*38fd1498Szrj 78*38fd1498Szrj Return value is the always taken edge if the block has multiple outgoing 79*38fd1498Szrj edges, NULL otherwise. When skipping unreachable blocks, the walker 80*38fd1498Szrj uses the taken edge information to clear EDGE_EXECUTABLE on the other 81*38fd1498Szrj edges, exposing unreachable blocks. A NULL return value means all 82*38fd1498Szrj outgoing edges should still be considered executable. A return value 83*38fd1498Szrj of STOP means to stop the domwalk from processing dominated blocks from 84*38fd1498Szrj here. This can be used to process a SEME region only (note domwalk 85*38fd1498Szrj will still do work linear in function size). */ before_dom_children(basic_block)86*38fd1498Szrj virtual edge before_dom_children (basic_block) { return NULL; } 87*38fd1498Szrj 88*38fd1498Szrj /* Function to call after the recursive walk of the dominator children. */ after_dom_children(basic_block)89*38fd1498Szrj virtual void after_dom_children (basic_block) {} 90*38fd1498Szrj 91*38fd1498Szrj private: 92*38fd1498Szrj /* This is the direction of the dominator tree we want to walk. i.e., 93*38fd1498Szrj if it is set to CDI_DOMINATORS, then we walk the dominator tree, 94*38fd1498Szrj if it is set to CDI_POST_DOMINATORS, then we walk the post 95*38fd1498Szrj dominator tree. */ 96*38fd1498Szrj const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2; 97*38fd1498Szrj bool m_skip_unreachable_blocks; 98*38fd1498Szrj bool m_user_bb_to_rpo; 99*38fd1498Szrj basic_block m_unreachable_dom; 100*38fd1498Szrj int *m_bb_to_rpo; 101*38fd1498Szrj 102*38fd1498Szrj /* Query whether or not the given block is reachable or not. */ 103*38fd1498Szrj bool bb_reachable (struct function *, basic_block); 104*38fd1498Szrj 105*38fd1498Szrj /* Given an unreachable block, propagate that property to outgoing 106*38fd1498Szrj and possibly incoming edges for the block. Typically called after 107*38fd1498Szrj determining a block is unreachable in the before_dom_children 108*38fd1498Szrj callback. */ 109*38fd1498Szrj void propagate_unreachable_to_edges (basic_block, FILE *, dump_flags_t); 110*38fd1498Szrj 111*38fd1498Szrj }; 112*38fd1498Szrj 113*38fd1498Szrj extern void set_all_edges_as_executable (function *fn); 114*38fd1498Szrj 115*38fd1498Szrj #endif 116