1/* Generic dominator tree walker
2   Copyright (C) 2003-2020 Free Software Foundation, Inc.
3   Contributed by Diego Novillo <dnovillo@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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 */
30class dom_walker
31{
32public:
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 dominator children will not be
66     walked in RPO order.  */
67  dom_walker (cdi_direction direction, enum reachability = ALL_BLOCKS,
68	      int *bb_index_to_rpo = NULL);
69
70  ~dom_walker ();
71
72  /* Walk the dominator tree.  */
73  void walk (basic_block);
74
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
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).  */
85  virtual edge before_dom_children (basic_block) { return NULL; }
86
87  /* Function to call after the recursive walk of the dominator children.  */
88  virtual void after_dom_children (basic_block) {}
89
90private:
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.  */
95  const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2;
96  const ENUM_BITFIELD (reachability) m_reachability : 2;
97  bool m_user_bb_to_rpo;
98  basic_block m_unreachable_dom;
99  int *m_bb_to_rpo;
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.  */
108  void propagate_unreachable_to_edges (basic_block, FILE *, dump_flags_t);
109
110};
111
112extern void set_all_edges_as_executable (function *fn);
113
114#endif
115