Line data Source code
1 : /* Header file for gimple range GORI structures.
2 : Copyright (C) 2017-2026 Free Software Foundation, Inc.
3 : Contributed by Andrew MacLeod <amacleod@redhat.com>
4 : and Aldy Hernandez <aldyh@redhat.com>.
5 :
6 : This file is part of GCC.
7 :
8 : GCC is free software; you can redistribute it and/or modify it under
9 : the terms of the GNU General Public License as published by the Free
10 : Software Foundation; either version 3, or (at your option) any later
11 : version.
12 :
13 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 : for more details.
17 :
18 : You should have received a copy of the GNU General Public License
19 : along with GCC; see the file COPYING3. If not see
20 : <http://www.gnu.org/licenses/>. */
21 :
22 : #ifndef GCC_GIMPLE_RANGE_GORI_H
23 : #define GCC_GIMPLE_RANGE_GORI_H
24 :
25 : // RANGE_DEF_CHAIN is used to determine which SSA names in a block can
26 : // have range information calculated for them, and what the
27 : // dependencies on each other are.
28 :
29 : class range_def_chain
30 : {
31 : public:
32 : range_def_chain ();
33 : ~range_def_chain ();
34 : tree depend1 (tree name) const;
35 : tree depend2 (tree name) const;
36 : bool in_chain_p (tree name, tree def);
37 : bool chain_import_p (tree name, tree import);
38 : void register_dependency (tree name, tree ssa1, basic_block bb = NULL);
39 : void dump (FILE *f, basic_block bb, const char *prefix = NULL);
40 : protected:
41 : bool has_def_chain (tree name);
42 : bool def_chain_in_bitmap_p (tree name, bitmap b);
43 : void add_def_chain_to_bitmap (bitmap b, tree name);
44 : bitmap get_def_chain (tree name);
45 : bitmap get_imports (tree name);
46 : bitmap_obstack m_bitmaps;
47 : private:
48 : struct rdc {
49 : unsigned int ssa1; // First direct dependency
50 : unsigned int ssa2; // Second direct dependency
51 : bitmap bm; // All dependencies
52 : bitmap m_import;
53 : };
54 : vec<rdc> m_def_chain; // SSA_NAME : def chain components.
55 : void set_import (struct rdc &data, tree imp, bitmap b);
56 : int m_logical_depth;
57 : };
58 :
59 : // Return the first direct dependency for NAME, if there is one.
60 : // Direct dependencies are those which occur on the definition statement.
61 : // Only the first 2 such names are cached.
62 :
63 : inline tree
64 1394341872 : range_def_chain::depend1 (tree name) const
65 : {
66 1394341872 : unsigned v = SSA_NAME_VERSION (name);
67 1394341872 : if (v >= m_def_chain.length ())
68 : return NULL_TREE;
69 1394341582 : unsigned v1 = m_def_chain[v].ssa1;
70 1394341582 : if (!v1)
71 : return NULL_TREE;
72 974057024 : return ssa_name (v1);
73 : }
74 :
75 : // Return the second direct dependency for NAME, if there is one.
76 :
77 : inline tree
78 1394341872 : range_def_chain::depend2 (tree name) const
79 : {
80 1394341872 : unsigned v = SSA_NAME_VERSION (name);
81 1394341872 : if (v >= m_def_chain.length ())
82 : return NULL_TREE;
83 1394341582 : unsigned v2 = m_def_chain[v].ssa2;
84 1394341582 : if (!v2)
85 : return NULL_TREE;
86 388988061 : return ssa_name (v2);
87 : }
88 :
89 : // GORI_MAP is used to accumulate what SSA names in a block can
90 : // generate range information, and provides tools for the block ranger
91 : // to enable it to efficiently calculate these ranges.
92 :
93 : class gori_map : public range_def_chain
94 : {
95 : public:
96 : gori_map ();
97 : ~gori_map ();
98 :
99 : bool is_export_p (tree name, basic_block bb = NULL);
100 : bool is_import_p (tree name, basic_block bb);
101 : bitmap exports (basic_block bb);
102 : bitmap exports_and_deps (basic_block bb, bitmap tmpbit);
103 : bitmap imports (basic_block bb);
104 : void set_range_invariant (tree name, bool invariant = true);
105 :
106 : void dump (FILE *f);
107 : void dump (FILE *f, basic_block bb, bool verbose = true);
108 : private:
109 : vec<bitmap> m_outgoing; // BB: Outgoing ranges calculable on edges
110 : vec<bitmap> m_incoming; // BB: Incoming ranges which can affect exports.
111 : bitmap m_maybe_variant; // Names which might have outgoing ranges.
112 : void maybe_add_gori (tree name, basic_block bb);
113 : void calculate_gori (basic_block bb);
114 : };
115 :
116 :
117 : // This class is used to determine which SSA_NAMES can have ranges
118 : // calculated for them on outgoing edges from basic blocks. This represents
119 : // ONLY the effect of the basic block edge->src on a range.
120 : //
121 : // There are 2 primary entry points:
122 : //
123 : // has_edge_range_p (tree name, edge e)
124 : // returns true if the outgoing edge *may* be able to produce range
125 : // information for ssa_name NAME on edge E.
126 : // FALSE is returned if this edge does not affect the range of NAME.
127 : // if no edge is specified, return TRUE if name may have a value calculated
128 : // on *ANY* edge that has been seen. FALSE indicates that the global value
129 : // is applicable everywhere that has been processed.
130 : //
131 : // edge_range_p (vrange &range, edge e, tree name)
132 : // Actually does the calculation of RANGE for name on E
133 : // This represents application of whatever static range effect edge E
134 : // may have on NAME, not any cumulative effect.
135 :
136 : // There are also some internal APIs
137 : //
138 : // ssa_range_in_bb () is an internal routine which is used to start any
139 : // calculation chain using SSA_NAMES which come from outside the block. ie
140 : // a_2 = b_4 - 8
141 : // if (a_2 < 30)
142 : // on the true edge, a_2 is known to be [0, 29]
143 : // b_4 can be calculated as [8, 37]
144 : // during this calculation, b_4 is considered an "import" and ssa_range_in_bb
145 : // is queried for a starting range which is used in the calculation.
146 : // A default value of VARYING provides the raw static info for the edge.
147 : //
148 : // If there is any known range for b_4 coming into this block, it can refine
149 : // the results. This allows for cascading results to be propagated.
150 : // if b_4 is [100, 200] on entry to the block, feeds into the calculation
151 : // of a_2 = [92, 192], and finally on the true edge the range would be
152 : // an empty range [] because it is not possible for the true edge to be taken.
153 : //
154 : // expr_range_in_bb is simply a wrapper which calls ssa_range_in_bb for
155 : // SSA_NAMES and otherwise simply calculates the range of the expression.
156 : //
157 : // The constructor takes a flag value to use on edges to check for the
158 : // NON_EXECUTABLE_EDGE property. The zero default means no flag is checked.
159 : // All value requests from NON_EXECUTABLE_EDGE edges are returned UNDEFINED.
160 : //
161 : // The remaining routines are internal use only.
162 :
163 : class value_relation;
164 :
165 : class gori_compute : public gimple_outgoing_range
166 : {
167 : public:
168 : gori_compute (gori_map &map, int not_executable_flag = 0,
169 : int max_sw_edges = 0);
170 : virtual ~gori_compute ();
171 : bool edge_range_p (vrange &r, edge e, tree name, range_query &q);
172 : bool has_edge_range_p (tree name, basic_block bb = NULL);
173 : bool has_edge_range_p (tree name, edge e);
174 : void dump (FILE *f);
175 : bool compute_operand_range (vrange &r, gimple *stmt, const vrange &lhs,
176 : tree name, class fur_source &src,
177 : value_relation *rel = NULL);
178 : private:
179 : gori_map &m_map;
180 : bool refine_using_relation (tree op1, vrange &op1_range,
181 : tree op2, vrange &op2_range,
182 : fur_source &src, relation_kind k);
183 : bool may_recompute_p (tree name, edge e, int depth = -1);
184 : bool may_recompute_p (tree name, basic_block bb = NULL, int depth = -1);
185 : bool compute_operand_range_switch (vrange &r, gswitch *s, const vrange &lhs,
186 : tree name, fur_source &src);
187 : bool compute_operand1_range (vrange &r, gimple_range_op_handler &handler,
188 : const vrange &lhs, fur_source &src,
189 : value_relation *rel = NULL);
190 : bool compute_operand2_range (vrange &r, gimple_range_op_handler &handler,
191 : const vrange &lhs, fur_source &src,
192 : value_relation *rel = NULL);
193 : bool compute_operand1_and_operand2_range (vrange &r,
194 : gimple_range_op_handler &handler,
195 : const vrange &lhs, tree name,
196 : fur_source &src,
197 : value_relation *rel = NULL);
198 : void compute_logical_operands (vrange &true_range, vrange &false_range,
199 : gimple_range_op_handler &handler,
200 : const irange &lhs, tree name, fur_source &src,
201 : tree op, bool op_in_chain);
202 : bool logical_combine (vrange &r, enum tree_code code, const irange &lhs,
203 : const vrange &op1_true, const vrange &op1_false,
204 : const vrange &op2_true, const vrange &op2_false);
205 : int_range<2> m_bool_zero; // Boolean false cached.
206 : int_range<2> m_bool_one; // Boolean true cached.
207 :
208 : range_tracer tracer;
209 : int m_not_executable_flag;
210 : int m_recompute_depth;
211 : };
212 :
213 : // These APIs are used to query GORI if there are ranges generated on an edge.
214 : // GORI_ON_EDGE is used to get all the ranges at once (returned in an
215 : // ssa_cache structure).
216 : // GORI_NAME_ON_EDGE is used to simply ask if NAME has a range on edge E
217 :
218 : // Fill ssa-cache R with any outgoing ranges on edge E, using QUERY.
219 : bool gori_on_edge (class ssa_cache &r, edge e, range_query *query = NULL);
220 :
221 : // Query if NAME has an outgoing range on edge E, and return it in R if so.
222 : // Note this doesnt use ranger, its a static GORI analysis of the range in
223 : // block e->src and is based on any branch at the exit of that block.
224 : bool gori_name_on_edge (vrange &r, tree name, edge e, range_query *q = NULL);
225 :
226 : // For each name that is an import into BB's exports..
227 : #define FOR_EACH_GORI_IMPORT_NAME(gorimap, bb, name) \
228 : for (gori_export_iterator iter ((gorimap)->imports ((bb))); \
229 : ((name) = iter.get_name ()); \
230 : iter.next ())
231 :
232 : // For each name possibly exported from block BB.
233 : #define FOR_EACH_GORI_EXPORT_NAME(gorimap, bb, name) \
234 : for (gori_export_iterator iter ((gorimap)->exports ((bb))); \
235 : ((name) = iter.get_name ()); \
236 : iter.next ())
237 :
238 : // For each name and all their dependencies possibly exported from block BB.
239 : #define FOR_EACH_GORI_EXPORT_AND_DEP_NAME(gorimap, bb, name, bm) \
240 : for (gori_export_iterator iter ((gorimap)->exports_and_deps ((bb),(bm))); \
241 : ((name) = iter.get_name ()); \
242 : iter.next ())
243 :
244 : // Used to assist with iterating over the GORI export list in various ways
245 : class gori_export_iterator {
246 : public:
247 : gori_export_iterator (bitmap b);
248 : void next ();
249 : tree get_name ();
250 : protected:
251 : bitmap bm;
252 : bitmap_iterator bi;
253 : unsigned y;
254 : };
255 :
256 : #endif // GCC_GIMPLE_RANGE_GORI_H
|
