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