GCC Middle and Back End API Reference
gimple-range-path.h
Go to the documentation of this file.
1/* Header file for jump threading path solver.
2 Copyright (C) 2021-2024 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldyh@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 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_TREE_SSA_THREADSOLVER_H
22#define GCC_TREE_SSA_THREADSOLVER_H
23
24// This class is a basic block path solver. Given a set of BBs
25// indicating a path through the CFG, range_of_expr and range_of_stmt
26// will calculate the range of an SSA or STMT as if the BBs in the
27// path would have been executed in order.
28//
29// Note that the blocks are in reverse order, thus the exit block is
30// path[0].
31
33{
34public:
36 const vec<basic_block> &path,
37 const bitmap_head *dependencies = NULL,
38 bool resolve = true);
39 path_range_query (gimple_ranger &ranger, bool resolve = true);
40 virtual ~path_range_query ();
41 void reset_path (const vec<basic_block> &, const bitmap_head *dependencies);
42 bool range_of_expr (vrange &r, tree name, gimple * = NULL) override;
43 bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override;
44 bool unreachable_path_p ();
45 void dump (FILE *) override;
46 void debug ();
47
48private:
49 bool internal_range_of_expr (vrange &r, tree name, gimple *);
50 void compute_ranges (const bitmap_head *dependencies);
51 void compute_exit_dependencies (bitmap_head *dependencies);
52 bool defined_outside_path (tree name);
53 void range_on_path_entry (vrange &r, tree name);
55
56 // Cache manipulation.
57 bool get_cache (vrange &r, tree name);
58
59 // Methods to compute ranges for the given path.
64 void ssa_range_in_phi (vrange &r, gphi *phi);
68 bool add_to_exit_dependencies (tree name, bitmap dependencies);
69 bool exit_dependency_p (tree name);
70 bool ssa_defined_in_bb (tree name, basic_block bb);
72
73 // Path navigation.
74 basic_block entry_bb () { return m_path[m_path.length () - 1]; }
75 basic_block exit_bb () { return m_path[0]; }
77 basic_block prev_bb () { return m_path[m_pos + 1]; }
78 basic_block next_bb () { return m_path[m_pos - 1]; }
79 bool at_entry () { return m_pos == m_path.length () - 1; }
80 bool at_exit () { return m_pos == 0; }
81 void move_next () { --m_pos; }
82
83 // Range cache for SSA names.
85
86 // Path being analyzed.
88
89 // This is a list of SSA names that may have relevant context
90 // information for solving the final conditional along the path.
91 // Ranges for these SSA names are pre-calculated and cached during a
92 // top-down traversal of the path, and are then used to answer
93 // questions at the path exit.
95
96 // A ranger used to resolve ranges for SSA names whose values come
97 // from outside the path.
99
100 // Current path position.
101 unsigned m_pos;
102
103 // Use ranger to resolve anything not known on entry.
105
106 // Set if there were any undefined expressions while pre-calculating path.
108};
109
110#endif // GCC_TREE_SSA_THREADSOLVER_H
Definition bitmap.h:950
Definition vec.h:1656
Definition bitmap.h:328
Definition gimple-range.h:48
Definition value-relation.h:264
Definition gimple-range-path.h:33
bool defined_outside_path(tree name)
Definition gimple-range-path.cc:123
void compute_ranges(const bitmap_head *dependencies)
Definition gimple-range-path.cc:555
bool exit_dependency_p(tree name)
Definition gimple-range-path.cc:73
path_oracle * get_path_oracle()
Definition gimple-range-path.h:54
void range_on_path_entry(vrange &r, tree name)
Definition gimple-range-path.cc:134
void adjust_for_non_null_uses(basic_block bb)
Definition gimple-range-path.cc:448
auto_bitmap m_exit_dependencies
Definition gimple-range-path.h:94
unsigned m_pos
Definition gimple-range-path.h:101
bool ssa_defined_in_bb(tree name, basic_block bb)
Definition gimple-range-path.cc:212
path_range_query(class gimple_ranger &ranger, const vec< basic_block > &path, const bitmap_head *dependencies=NULL, bool resolve=true)
Definition gimple-range-path.cc:39
bool m_undefined_path
Definition gimple-range-path.h:107
basic_block next_bb()
Definition gimple-range-path.h:78
gimple_ranger & m_ranger
Definition gimple-range-path.h:98
bool range_defined_in_block(vrange &, tree name, basic_block bb)
Definition gimple-range-path.cc:287
bool add_to_exit_dependencies(tree name, bitmap dependencies)
Definition gimple-range-path.cc:477
void debug()
Definition gimple-range-path.cc:115
basic_block entry_bb()
Definition gimple-range-path.h:74
bool get_cache(vrange &r, tree name)
Definition gimple-range-path.cc:82
void dump(FILE *) override
Definition gimple-range-path.cc:91
ssa_lazy_cache m_cache
Definition gimple-range-path.h:84
virtual ~path_range_query()
Definition gimple-range-path.cc:64
basic_block curr_bb()
Definition gimple-range-path.h:76
void maybe_register_phi_relation(gphi *, edge e)
Definition gimple-range-path.cc:688
bool internal_range_of_expr(vrange &r, tree name, gimple *)
Definition gimple-range-path.cc:144
bool relations_may_be_invalidated(edge)
Definition gimple-range-path.cc:351
void compute_phi_relations(basic_block bb, basic_block prev)
Definition gimple-range-path.cc:720
bool range_of_expr(vrange &r, tree name, gimple *=NULL) override
Definition gimple-range-path.cc:178
void compute_ranges_in_block(basic_block bb)
Definition gimple-range-path.cc:365
basic_block exit_bb()
Definition gimple-range-path.h:75
bool m_resolve
Definition gimple-range-path.h:104
bool at_exit()
Definition gimple-range-path.h:80
auto_vec< basic_block > m_path
Definition gimple-range-path.h:87
bool unreachable_path_p()
Definition gimple-range-path.cc:191
bool range_of_stmt(vrange &r, gimple *, tree name=NULL) override
Definition gimple-range-path.cc:662
void compute_outgoing_relations(basic_block bb, basic_block next)
Definition gimple-range-path.cc:749
void compute_exit_dependencies(bitmap_head *dependencies)
Definition gimple-range-path.cc:489
void ssa_range_in_phi(vrange &r, gphi *phi)
Definition gimple-range-path.cc:227
bool at_entry()
Definition gimple-range-path.h:79
void move_next()
Definition gimple-range-path.h:81
basic_block prev_bb()
Definition gimple-range-path.h:77
void compute_ranges_in_phis(basic_block bb)
Definition gimple-range-path.cc:327
void reset_path(const vec< basic_block > &, const bitmap_head *dependencies)
Definition gimple-range-path.cc:199
Definition value-query.h:55
relation_oracle * m_relation
Definition value-query.h:99
Definition gimple-range-cache.h:79
Definition value-range.h:78
class edge_def * edge
Definition coretypes.h:343
class bitmap_head * bitmap
Definition coretypes.h:51
union tree_node * tree
Definition coretypes.h:97
poly_int< N, C > r
Definition poly-int.h:770
Definition basic-block.h:117
Definition gimple.h:225
Definition gimple.h:462
Definition vec.h:450
#define NULL
Definition system.h:50
static gimple_ranger * ranger
Definition tree-ssa-loop-unswitch.cc:203