1 | /* Generic dominator tree walker |
2 | Copyright (C) 2003-2023 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 | /* You can provide a mapping of basic-block index to RPO if you |
64 | have that readily available or you do multiple walks. If you |
65 | specify NULL as BB_INDEX_TO_RPO this mapping will be computed |
66 | lazily at walk time. If you specify -1 dominator children will |
67 | not be walked in RPO order. */ |
68 | dom_walker (cdi_direction direction, enum reachability = ALL_BLOCKS, |
69 | int *bb_index_to_rpo = NULL); |
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). */ |
86 | virtual edge before_dom_children (basic_block) { return NULL; } |
87 | |
88 | /* Function to call after the recursive walk of the dominator children. */ |
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 | const ENUM_BITFIELD (reachability) m_reachability : 2; |
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 | |