]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Generic dominator tree walker |
8d9254fc | 2 | Copyright (C) 2003-2020 Free Software Foundation, Inc. |
6de9cd9a DN |
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 | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a | 20 | |
4d9192b5 TS |
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 | |
6de9cd9a | 31 | { |
4d9192b5 | 32 | public: |
d2552094 RB |
33 | static const edge STOP; |
34 | ||
9972bbbc DM |
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 | |
dc3b4a20 RB |
64 | have that readily available or you do multiple walks. If you |
65 | specify NULL as BB_INDEX_TO_RPO dominator children will not be | |
66 | walked in RPO order. */ | |
e37240b0 RB |
67 | dom_walker (cdi_direction direction, enum reachability = ALL_BLOCKS, |
68 | int *bb_index_to_rpo = NULL); | |
d2552094 RB |
69 | |
70 | ~dom_walker (); | |
6de9cd9a | 71 | |
4d9192b5 TS |
72 | /* Walk the dominator tree. */ |
73 | void walk (basic_block); | |
6de9cd9a | 74 | |
3daacdcd JL |
75 | /* Function to call before the recursive walk of the dominator children. |
76 | ||
77 | Return value is the always taken edge if the block has multiple outgoing | |
78 | edges, NULL otherwise. When skipping unreachable blocks, the walker | |
79 | uses the taken edge information to clear EDGE_EXECUTABLE on the other | |
80 | edges, exposing unreachable blocks. A NULL return value means all | |
d2552094 RB |
81 | outgoing edges should still be considered executable. A return value |
82 | of STOP means to stop the domwalk from processing dominated blocks from | |
83 | here. This can be used to process a SEME region only (note domwalk | |
84 | will still do work linear in function size). */ | |
3daacdcd | 85 | virtual edge before_dom_children (basic_block) { return NULL; } |
6de9cd9a | 86 | |
ccf5c864 | 87 | /* Function to call after the recursive walk of the dominator children. */ |
4d9192b5 | 88 | virtual void after_dom_children (basic_block) {} |
6de9cd9a | 89 | |
4d9192b5 TS |
90 | private: |
91 | /* This is the direction of the dominator tree we want to walk. i.e., | |
92 | if it is set to CDI_DOMINATORS, then we walk the dominator tree, | |
93 | if it is set to CDI_POST_DOMINATORS, then we walk the post | |
94 | dominator tree. */ | |
65d3284b | 95 | const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2; |
e37240b0 | 96 | const ENUM_BITFIELD (reachability) m_reachability : 2; |
d2552094 | 97 | bool m_user_bb_to_rpo; |
3daacdcd | 98 | basic_block m_unreachable_dom; |
d2552094 | 99 | int *m_bb_to_rpo; |
3daacdcd JL |
100 | |
101 | /* Query whether or not the given block is reachable or not. */ | |
102 | bool bb_reachable (struct function *, basic_block); | |
103 | ||
104 | /* Given an unreachable block, propagate that property to outgoing | |
105 | and possibly incoming edges for the block. Typically called after | |
106 | determining a block is unreachable in the before_dom_children | |
107 | callback. */ | |
1a817418 | 108 | void propagate_unreachable_to_edges (basic_block, FILE *, dump_flags_t); |
3daacdcd | 109 | |
6de9cd9a DN |
110 | }; |
111 | ||
9972bbbc DM |
112 | extern void set_all_edges_as_executable (function *fn); |
113 | ||
4d9192b5 | 114 | #endif |