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