Branch data Line data Source code
1 : : /* Generic dominator tree walker
2 : : Copyright (C) 2003-2024 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 : 9783749 : virtual edge before_dom_children (basic_block) { return NULL; }
87 : :
88 : : /* Function to call after the recursive walk of the dominator children. */
89 : 52168373 : 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
|
