]>
Commit | Line | Data |
---|---|---|
90e88fd3 | 1 | /* Code for GIMPLE range related routines. |
99dee823 | 2 | Copyright (C) 2019-2021 Free Software Foundation, Inc. |
90e88fd3 AM |
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 | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License 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 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "backend.h" | |
90e88fd3 AM |
26 | #include "tree.h" |
27 | #include "gimple.h" | |
28 | #include "ssa.h" | |
29 | #include "gimple-pretty-print.h" | |
30 | #include "gimple-iterator.h" | |
90e88fd3 AM |
31 | #include "tree-cfg.h" |
32 | #include "fold-const.h" | |
33 | #include "tree-cfg.h" | |
90e88fd3 | 34 | #include "cfgloop.h" |
90e88fd3 | 35 | #include "tree-scalar-evolution.h" |
90e88fd3 AM |
36 | #include "gimple-range.h" |
37 | ||
e68c8280 | 38 | gimple_ranger::gimple_ranger () : tracer ("") |
a2c91733 AM |
39 | { |
40 | // If the cache has a relation oracle, use it. | |
41 | m_oracle = m_cache.oracle (); | |
e68c8280 AM |
42 | if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) |
43 | tracer.enable_trace (); | |
a2c91733 AM |
44 | } |
45 | ||
90e88fd3 AM |
46 | bool |
47 | gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) | |
48 | { | |
e68c8280 | 49 | unsigned idx; |
90e88fd3 | 50 | if (!gimple_range_ssa_p (expr)) |
caa60c12 | 51 | return get_tree_range (r, expr, stmt); |
90e88fd3 | 52 | |
e68c8280 AM |
53 | if ((idx = tracer.header ("range_of_expr("))) |
54 | { | |
55 | print_generic_expr (dump_file, expr, TDF_SLIM); | |
56 | fputs (")", dump_file); | |
57 | if (stmt) | |
58 | { | |
59 | fputs (" at stmt ", dump_file); | |
60 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
61 | } | |
62 | else | |
63 | fputs ("\n", dump_file); | |
64 | } | |
65 | ||
90e88fd3 AM |
66 | // If there is no statement, just get the global value. |
67 | if (!stmt) | |
68 | { | |
220929c0 | 69 | if (!m_cache.get_global_range (r, expr)) |
90e88fd3 | 70 | r = gimple_range_global (expr); |
90e88fd3 | 71 | } |
715914d3 AM |
72 | // For a debug stmt, pick the best value currently available, do not |
73 | // trigger new value calculations. PR 100781. | |
e68c8280 AM |
74 | else if (is_gimple_debug (stmt)) |
75 | m_cache.range_of_expr (r, expr, stmt); | |
76 | else | |
715914d3 | 77 | { |
e68c8280 AM |
78 | basic_block bb = gimple_bb (stmt); |
79 | gimple *def_stmt = SSA_NAME_DEF_STMT (expr); | |
90e88fd3 | 80 | |
e68c8280 AM |
81 | // If name is defined in this block, try to get an range from S. |
82 | if (def_stmt && gimple_bb (def_stmt) == bb) | |
83 | { | |
84 | range_of_stmt (r, def_stmt, expr); | |
85 | m_cache.m_non_null.adjust_range (r, expr, bb, true); | |
86 | } | |
87 | // Otherwise OP comes from outside this block, use range on entry. | |
88 | else | |
89 | range_on_entry (r, bb, expr); | |
35c78c6f | 90 | } |
e68c8280 AM |
91 | if (idx) |
92 | tracer.trailer (idx, "range_of_expr", true, expr, r); | |
90e88fd3 AM |
93 | return true; |
94 | } | |
95 | ||
96 | // Return the range of NAME on entry to block BB in R. | |
97 | ||
98 | void | |
99 | gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name) | |
100 | { | |
101 | int_range_max entry_range; | |
102 | gcc_checking_assert (gimple_range_ssa_p (name)); | |
103 | ||
e68c8280 AM |
104 | unsigned idx; |
105 | if ((idx = tracer.header ("range_on_entry ("))) | |
106 | { | |
107 | print_generic_expr (dump_file, name, TDF_SLIM); | |
108 | fprintf (dump_file, ") to BB %d\n", bb->index); | |
109 | } | |
110 | ||
90e88fd3 | 111 | // Start with any known range |
c25d317c | 112 | range_of_stmt (r, SSA_NAME_DEF_STMT (name), name); |
90e88fd3 AM |
113 | |
114 | // Now see if there is any on_entry value which may refine it. | |
115 | if (m_cache.block_range (entry_range, bb, name)) | |
116 | r.intersect (entry_range); | |
35c78c6f | 117 | |
79f71ec6 | 118 | m_cache.m_non_null.adjust_range (r, name, bb, true); |
e68c8280 AM |
119 | |
120 | if (idx) | |
121 | tracer.trailer (idx, "range_on_entry", true, name, r); | |
90e88fd3 AM |
122 | } |
123 | ||
124 | // Calculate the range for NAME at the end of block BB and return it in R. | |
125 | // Return false if no range can be calculated. | |
126 | ||
127 | void | |
128 | gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name) | |
129 | { | |
130 | // on-exit from the exit block? | |
131 | gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
c25d317c | 132 | gcc_checking_assert (gimple_range_ssa_p (name)); |
90e88fd3 | 133 | |
e68c8280 AM |
134 | unsigned idx; |
135 | if ((idx = tracer.header ("range_on_exit ("))) | |
136 | { | |
137 | print_generic_expr (dump_file, name, TDF_SLIM); | |
138 | fprintf (dump_file, ") from BB %d\n", bb->index); | |
139 | } | |
140 | ||
d942d733 AM |
141 | gimple *s = SSA_NAME_DEF_STMT (name); |
142 | basic_block def_bb = gimple_bb (s); | |
143 | // If this is not the definition block, get the range on the last stmt in | |
144 | // the block... if there is one. | |
145 | if (def_bb != bb) | |
146 | s = last_stmt (bb); | |
147 | // If there is no statement provided, get the range_on_entry for this block. | |
148 | if (s) | |
c25d317c | 149 | range_of_expr (r, name, s); |
d942d733 | 150 | else |
35c78c6f | 151 | range_on_entry (r, bb, name); |
90e88fd3 | 152 | gcc_checking_assert (r.undefined_p () |
6e02de94 | 153 | || range_compatible_p (r.type (), TREE_TYPE (name))); |
e68c8280 AM |
154 | |
155 | if (idx) | |
156 | tracer.trailer (idx, "range_on_exit", true, name, r); | |
90e88fd3 AM |
157 | } |
158 | ||
159 | // Calculate a range for NAME on edge E and return it in R. | |
160 | ||
161 | bool | |
162 | gimple_ranger::range_on_edge (irange &r, edge e, tree name) | |
163 | { | |
164 | int_range_max edge_range; | |
165 | gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name))); | |
166 | ||
167 | // PHI arguments can be constants, catch these here. | |
168 | if (!gimple_range_ssa_p (name)) | |
c25d317c | 169 | return range_of_expr (r, name); |
90e88fd3 | 170 | |
e68c8280 AM |
171 | unsigned idx; |
172 | if ((idx = tracer.header ("range_on_edge ("))) | |
173 | { | |
174 | print_generic_expr (dump_file, name, TDF_SLIM); | |
175 | fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index); | |
176 | } | |
177 | ||
90e88fd3 AM |
178 | range_on_exit (r, e->src, name); |
179 | gcc_checking_assert (r.undefined_p () | |
6e02de94 | 180 | || range_compatible_p (r.type(), TREE_TYPE (name))); |
90e88fd3 AM |
181 | |
182 | // Check to see if NAME is defined on edge e. | |
47ea02bb | 183 | if (m_cache.range_on_edge (edge_range, e, name)) |
90e88fd3 AM |
184 | r.intersect (edge_range); |
185 | ||
e68c8280 AM |
186 | if (idx) |
187 | tracer.trailer (idx, "range_on_edge", true, name, r); | |
90e88fd3 AM |
188 | return true; |
189 | } | |
190 | ||
dc6758f0 AM |
191 | // fold_range wrapper for range_of_stmt to use as an internal client. |
192 | ||
193 | bool | |
194 | gimple_ranger::fold_range_internal (irange &r, gimple *s, tree name) | |
195 | { | |
196 | fold_using_range f; | |
87f9ac93 | 197 | fur_depend src (s, &(gori ()), this); |
dc6758f0 AM |
198 | return f.fold_stmt (r, s, src, name); |
199 | } | |
200 | ||
90e88fd3 AM |
201 | // Calculate a range for statement S and return it in R. If NAME is |
202 | // provided it represents the SSA_NAME on the LHS of the statement. | |
203 | // It is only required if there is more than one lhs/output. Check | |
204 | // the global cache for NAME first to see if the evaluation can be | |
c25d317c | 205 | // avoided. If a range cannot be calculated, return false and UNDEFINED. |
90e88fd3 AM |
206 | |
207 | bool | |
208 | gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) | |
209 | { | |
e68c8280 | 210 | bool res; |
c25d317c AM |
211 | r.set_undefined (); |
212 | ||
e68c8280 AM |
213 | unsigned idx; |
214 | if ((idx = tracer.header ("range_of_stmt ("))) | |
215 | { | |
216 | if (name) | |
217 | print_generic_expr (dump_file, name, TDF_SLIM); | |
218 | fputs (") at stmt ", dump_file); | |
219 | print_gimple_stmt (dump_file, s, 0, TDF_SLIM); | |
220 | } | |
221 | ||
90e88fd3 AM |
222 | if (!name) |
223 | name = gimple_get_lhs (s); | |
224 | ||
c25d317c | 225 | // If no name, simply call the base routine. |
90e88fd3 | 226 | if (!name) |
e68c8280 AM |
227 | res = fold_range_internal (r, s, NULL_TREE); |
228 | else if (!gimple_range_ssa_p (name)) | |
229 | res = false; | |
e86fd6a1 | 230 | // Check if the stmt has already been processed, and is not stale. |
e68c8280 AM |
231 | else if (m_cache.get_non_stale_global_range (r, name)) |
232 | { | |
233 | if (idx) | |
234 | tracer.trailer (idx, " cached", true, name, r); | |
235 | return true; | |
236 | } | |
237 | else | |
238 | { | |
239 | // Otherwise calculate a new value. | |
240 | int_range_max tmp; | |
241 | fold_range_internal (tmp, s, name); | |
242 | ||
243 | // Combine the new value with the old value. This is required because | |
244 | // the way value propagation works, when the IL changes on the fly we | |
245 | // can sometimes get different results. See PR 97741. | |
246 | r.intersect (tmp); | |
247 | m_cache.set_global_range (name, r); | |
248 | res = true; | |
249 | } | |
2dd1f944 | 250 | |
e68c8280 AM |
251 | if (idx) |
252 | tracer.trailer (idx, "range_of_stmt", res, name, r); | |
253 | return res; | |
90e88fd3 AM |
254 | } |
255 | ||
256 | // This routine will export whatever global ranges are known to GCC | |
160fe603 | 257 | // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields. |
90e88fd3 AM |
258 | |
259 | void | |
260 | gimple_ranger::export_global_ranges () | |
261 | { | |
ed3de423 MS |
262 | /* Cleared after the table header has been printed. */ |
263 | bool print_header = true; | |
264 | for (unsigned x = 1; x < num_ssa_names; x++) | |
90e88fd3 | 265 | { |
ed3de423 | 266 | int_range_max r; |
90e88fd3 AM |
267 | tree name = ssa_name (x); |
268 | if (name && !SSA_NAME_IN_FREE_LIST (name) | |
269 | && gimple_range_ssa_p (name) | |
220929c0 | 270 | && m_cache.get_global_range (r, name) |
90e88fd3 AM |
271 | && !r.varying_p()) |
272 | { | |
160fe603 | 273 | bool updated = update_global_range (r, name); |
ed3de423 MS |
274 | if (!updated || !dump_file || !(dump_flags & TDF_DETAILS)) |
275 | continue; | |
276 | ||
277 | if (print_header) | |
278 | { | |
279 | /* Print the header only when there's something else | |
280 | to print below. */ | |
281 | fprintf (dump_file, "Exported global range table:\n"); | |
282 | fprintf (dump_file, "============================\n"); | |
283 | print_header = false; | |
284 | } | |
160fe603 | 285 | |
ed3de423 MS |
286 | value_range vr = r; |
287 | print_generic_expr (dump_file, name , TDF_SLIM); | |
288 | fprintf (dump_file, " : "); | |
289 | vr.dump (dump_file); | |
290 | fprintf (dump_file, "\n"); | |
291 | int_range_max same = vr; | |
292 | if (same != r) | |
90e88fd3 | 293 | { |
ed3de423 MS |
294 | fprintf (dump_file, " irange : "); |
295 | r.dump (dump_file); | |
160fe603 | 296 | fprintf (dump_file, "\n"); |
90e88fd3 AM |
297 | } |
298 | } | |
299 | } | |
300 | } | |
301 | ||
302 | // Print the known table values to file F. | |
303 | ||
304 | void | |
35c78c6f | 305 | gimple_ranger::dump_bb (FILE *f, basic_block bb) |
90e88fd3 | 306 | { |
35c78c6f AM |
307 | unsigned x; |
308 | edge_iterator ei; | |
309 | edge e; | |
e68c8280 | 310 | int_range_max range, tmp_range; |
35c78c6f | 311 | fprintf (f, "\n=========== BB %d ============\n", bb->index); |
47ea02bb | 312 | m_cache.dump_bb (f, bb); |
90e88fd3 | 313 | |
35c78c6f | 314 | ::dump_bb (f, bb, 4, TDF_NONE); |
90e88fd3 | 315 | |
35c78c6f AM |
316 | // Now find any globals defined in this block. |
317 | for (x = 1; x < num_ssa_names; x++) | |
318 | { | |
319 | tree name = ssa_name (x); | |
320 | if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) && | |
321 | gimple_bb (SSA_NAME_DEF_STMT (name)) == bb && | |
322 | m_cache.get_global_range (range, name)) | |
90e88fd3 | 323 | { |
35c78c6f | 324 | if (!range.varying_p ()) |
90e88fd3 | 325 | { |
35c78c6f AM |
326 | print_generic_expr (f, name, TDF_SLIM); |
327 | fprintf (f, " : "); | |
328 | range.dump (f); | |
329 | fprintf (f, "\n"); | |
90e88fd3 | 330 | } |
35c78c6f | 331 | |
90e88fd3 | 332 | } |
35c78c6f | 333 | } |
90e88fd3 | 334 | |
35c78c6f AM |
335 | // And now outgoing edges, if they define anything. |
336 | FOR_EACH_EDGE (e, ei, bb->succs) | |
337 | { | |
338 | for (x = 1; x < num_ssa_names; x++) | |
90e88fd3 | 339 | { |
35c78c6f | 340 | tree name = gimple_range_ssa_p (ssa_name (x)); |
8a22a10c AM |
341 | if (name && gori ().has_edge_range_p (name, e) |
342 | && m_cache.range_on_edge (range, e, name)) | |
90e88fd3 | 343 | { |
35c78c6f AM |
344 | gimple *s = SSA_NAME_DEF_STMT (name); |
345 | // Only print the range if this is the def block, or | |
346 | // the on entry cache for either end of the edge is | |
347 | // set. | |
348 | if ((s && bb == gimple_bb (s)) || | |
e68c8280 AM |
349 | m_cache.block_range (tmp_range, bb, name, false) || |
350 | m_cache.block_range (tmp_range, e->dest, name, false)) | |
90e88fd3 | 351 | { |
35c78c6f | 352 | if (!range.varying_p ()) |
90e88fd3 | 353 | { |
35c78c6f AM |
354 | fprintf (f, "%d->%d ", e->src->index, |
355 | e->dest->index); | |
356 | char c = ' '; | |
357 | if (e->flags & EDGE_TRUE_VALUE) | |
358 | fprintf (f, " (T)%c", c); | |
359 | else if (e->flags & EDGE_FALSE_VALUE) | |
360 | fprintf (f, " (F)%c", c); | |
361 | else | |
362 | fprintf (f, " "); | |
363 | print_generic_expr (f, name, TDF_SLIM); | |
364 | fprintf(f, " : \t"); | |
365 | range.dump(f); | |
366 | fprintf (f, "\n"); | |
90e88fd3 AM |
367 | } |
368 | } | |
369 | } | |
370 | } | |
371 | } | |
35c78c6f AM |
372 | } |
373 | ||
374 | // Print the known table values to file F. | |
375 | ||
376 | void | |
377 | gimple_ranger::dump (FILE *f) | |
378 | { | |
379 | basic_block bb; | |
380 | ||
381 | FOR_EACH_BB_FN (bb, cfun) | |
382 | dump_bb (f, bb); | |
90e88fd3 | 383 | |
47ea02bb | 384 | m_cache.dump (f); |
90e88fd3 AM |
385 | } |
386 | ||
77bf9f83 MS |
387 | /* Create a new ranger instance and associate it with function FUN. |
388 | Each call must be paired with a call to disable_ranger to release | |
389 | resources. */ | |
390 | ||
586d6f7a AH |
391 | gimple_ranger * |
392 | enable_ranger (struct function *fun) | |
393 | { | |
394 | gimple_ranger *r; | |
395 | ||
e68c8280 | 396 | r = new gimple_ranger; |
586d6f7a AH |
397 | fun->x_range_query = r; |
398 | ||
399 | return r; | |
400 | } | |
401 | ||
77bf9f83 MS |
402 | /* Destroy and release the ranger instance associated with function FUN |
403 | and replace it the global ranger. */ | |
404 | ||
586d6f7a AH |
405 | void |
406 | disable_ranger (struct function *fun) | |
407 | { | |
408 | delete fun->x_range_query; | |
409 | ||
410 | fun->x_range_query = &global_ranges; | |
411 | } |