Branch data Line data Source code
1 : : /* Gimple range GORI functions.
2 : : Copyright (C) 2017-2024 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
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"
26 : : #include "tree.h"
27 : : #include "gimple.h"
28 : : #include "ssa.h"
29 : : #include "gimple-pretty-print.h"
30 : : #include "gimple-range.h"
31 : :
32 : : // Return TRUE if GS is a logical && or || expression.
33 : :
34 : : static inline bool
35 : 29590822 : is_gimple_logical_p (const gimple *gs)
36 : : {
37 : : // Look for boolean and/or condition.
38 : 29590822 : if (is_gimple_assign (gs))
39 : 11349451 : switch (gimple_expr_code (gs))
40 : : {
41 : : case TRUTH_AND_EXPR:
42 : : case TRUTH_OR_EXPR:
43 : : return true;
44 : :
45 : 3518439 : case BIT_AND_EXPR:
46 : 3518439 : case BIT_IOR_EXPR:
47 : : // Bitwise operations on single bits are logical too.
48 : 3518439 : if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)),
49 : : boolean_type_node))
50 : : return true;
51 : : break;
52 : :
53 : : default:
54 : : break;
55 : : }
56 : : return false;
57 : : }
58 : :
59 : : /* RANGE_DEF_CHAIN is used to determine which SSA names in a block can
60 : : have range information calculated for them, and what the
61 : : dependencies on each other are.
62 : :
63 : : Information for a basic block is calculated once and stored. It is
64 : : only calculated the first time a query is made, so if no queries
65 : : are made, there is little overhead.
66 : :
67 : : The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set
68 : : within this bitmap to indicate SSA names that are defined in the
69 : : SAME block and used to calculate this SSA name.
70 : :
71 : :
72 : : <bb 2> :
73 : : _1 = x_4(D) + -2;
74 : : _2 = _1 * 4;
75 : : j_7 = foo ();
76 : : q_5 = _2 + 3;
77 : : if (q_5 <= 13)
78 : :
79 : : _1 : x_4(D)
80 : : _2 : 1 x_4(D)
81 : : q_5 : _1 _2 x_4(D)
82 : :
83 : : This dump indicates the bits set in the def_chain vector.
84 : : as well as demonstrates the def_chain bits for the related ssa_names.
85 : :
86 : : Checking the chain for _2 indicates that _1 and x_4 are used in
87 : : its evaluation.
88 : :
89 : : Def chains also only include statements which are valid gimple
90 : : so a def chain will only span statements for which the range
91 : : engine implements operations for. */
92 : :
93 : :
94 : : // Construct a range_def_chain.
95 : :
96 : 24313476 : range_def_chain::range_def_chain ()
97 : : {
98 : 24313476 : bitmap_obstack_initialize (&m_bitmaps);
99 : 24313476 : m_def_chain.create (0);
100 : 48626952 : m_def_chain.safe_grow_cleared (num_ssa_names);
101 : 24313476 : m_logical_depth = 0;
102 : 24313476 : }
103 : :
104 : : // Destruct a range_def_chain.
105 : :
106 : 24313476 : range_def_chain::~range_def_chain ()
107 : : {
108 : 24313476 : m_def_chain.release ();
109 : 24313476 : bitmap_obstack_release (&m_bitmaps);
110 : 24313476 : }
111 : :
112 : : // Return true if NAME is in the def chain of DEF. If BB is provided,
113 : : // only return true if the defining statement of DEF is in BB.
114 : :
115 : : bool
116 : 87800596 : range_def_chain::in_chain_p (tree name, tree def)
117 : : {
118 : 87800596 : gcc_checking_assert (gimple_range_ssa_p (def));
119 : 87800596 : gcc_checking_assert (gimple_range_ssa_p (name));
120 : :
121 : : // Get the definition chain for DEF.
122 : 87800596 : bitmap chain = get_def_chain (def);
123 : :
124 : 87800596 : if (chain == NULL)
125 : : return false;
126 : 63720331 : return bitmap_bit_p (chain, SSA_NAME_VERSION (name));
127 : : }
128 : :
129 : : // Add either IMP or the import list B to the import set of DATA.
130 : :
131 : : void
132 : 231751240 : range_def_chain::set_import (struct rdc &data, tree imp, bitmap b)
133 : : {
134 : : // If there are no imports, just return
135 : 231751240 : if (imp == NULL_TREE && !b)
136 : : return;
137 : 231635415 : if (!data.m_import)
138 : 111412710 : data.m_import = BITMAP_ALLOC (&m_bitmaps);
139 : 231635415 : if (imp != NULL_TREE)
140 : 200285900 : bitmap_set_bit (data.m_import, SSA_NAME_VERSION (imp));
141 : : else
142 : 31349515 : bitmap_ior_into (data.m_import, b);
143 : : }
144 : :
145 : : // Return the import list for NAME.
146 : :
147 : : bitmap
148 : 127593074 : range_def_chain::get_imports (tree name)
149 : : {
150 : 127593074 : if (!has_def_chain (name))
151 : 77900798 : get_def_chain (name);
152 : 127593074 : bitmap i = m_def_chain[SSA_NAME_VERSION (name)].m_import;
153 : 127593074 : return i;
154 : : }
155 : :
156 : : // Return true if IMPORT is an import to NAMEs def chain.
157 : :
158 : : bool
159 : 3635089 : range_def_chain::chain_import_p (tree name, tree import)
160 : : {
161 : 3635089 : bitmap b = get_imports (name);
162 : 3635089 : if (b)
163 : 3631241 : return bitmap_bit_p (b, SSA_NAME_VERSION (import));
164 : : return false;
165 : : }
166 : :
167 : : // Build def_chains for NAME if it is in BB. Copy the def chain into RESULT.
168 : :
169 : : void
170 : 190206727 : range_def_chain::register_dependency (tree name, tree dep, basic_block bb)
171 : : {
172 : 190206727 : if (!gimple_range_ssa_p (dep))
173 : : return;
174 : :
175 : 160815374 : unsigned v = SSA_NAME_VERSION (name);
176 : 321630748 : if (v >= m_def_chain.length ())
177 : 302 : m_def_chain.safe_grow_cleared (num_ssa_names + 1);
178 : 160815374 : struct rdc &src = m_def_chain[v];
179 : 160815374 : gimple *def_stmt = SSA_NAME_DEF_STMT (dep);
180 : 160815374 : unsigned dep_v = SSA_NAME_VERSION (dep);
181 : 160815374 : bitmap b;
182 : :
183 : : // Set the direct dependency cache entries.
184 : 160815374 : if (!src.ssa1)
185 : 85284510 : src.ssa1 = SSA_NAME_VERSION (dep);
186 : 75530864 : else if (!src.ssa2 && src.ssa1 != SSA_NAME_VERSION (dep))
187 : 24984110 : src.ssa2 = SSA_NAME_VERSION (dep);
188 : :
189 : : // Don't calculate imports or export/dep chains if BB is not provided.
190 : : // This is usually the case for when the temporal cache wants the direct
191 : : // dependencies of a stmt.
192 : 160815374 : if (!bb)
193 : : return;
194 : :
195 : 52003796 : if (!src.bm)
196 : 41742754 : src.bm = BITMAP_ALLOC (&m_bitmaps);
197 : :
198 : : // Add this operand into the result.
199 : 52003796 : bitmap_set_bit (src.bm, dep_v);
200 : :
201 : 52003796 : if (gimple_bb (def_stmt) == bb && !is_a<gphi *>(def_stmt))
202 : : {
203 : : // Get the def chain for the operand.
204 : 31465340 : b = get_def_chain (dep);
205 : : // If there was one, copy it into result. Access def_chain directly
206 : : // as the get_def_chain request above could reallocate the vector.
207 : 31465340 : if (b)
208 : 18535016 : bitmap_ior_into (m_def_chain[v].bm, b);
209 : : // And copy the import list.
210 : 31465340 : set_import (m_def_chain[v], NULL_TREE, get_imports (dep));
211 : : }
212 : : else
213 : : // Originated outside the block, so it is an import.
214 : 20538456 : set_import (src, dep, NULL);
215 : : }
216 : :
217 : : bool
218 : 0 : range_def_chain::def_chain_in_bitmap_p (tree name, bitmap b)
219 : : {
220 : 0 : bitmap a = get_def_chain (name);
221 : 0 : if (a && b)
222 : 0 : return bitmap_intersect_p (a, b);
223 : : return false;
224 : : }
225 : :
226 : : void
227 : 92492513 : range_def_chain::add_def_chain_to_bitmap (bitmap b, tree name)
228 : : {
229 : 92492513 : bitmap r = get_def_chain (name);
230 : 92492513 : if (r)
231 : 27521976 : bitmap_ior_into (b, r);
232 : 92492513 : }
233 : :
234 : :
235 : : // Return TRUE if NAME has been processed for a def_chain.
236 : :
237 : : inline bool
238 : 417252727 : range_def_chain::has_def_chain (tree name)
239 : : {
240 : : // Ensure there is an entry in the internal vector.
241 : 417252727 : unsigned v = SSA_NAME_VERSION (name);
242 : 834505454 : if (v >= m_def_chain.length ())
243 : 1306 : m_def_chain.safe_grow_cleared (num_ssa_names + 1);
244 : 417252727 : return (m_def_chain[v].ssa1 != 0);
245 : : }
246 : :
247 : :
248 : :
249 : : // Calculate the def chain for NAME and all of its dependent
250 : : // operands. Only using names in the same BB. Return the bitmap of
251 : : // all names in the m_def_chain. This only works for supported range
252 : : // statements.
253 : :
254 : : bitmap
255 : 289659394 : range_def_chain::get_def_chain (tree name)
256 : : {
257 : 289659394 : tree ssa[3];
258 : 289659394 : unsigned v = SSA_NAME_VERSION (name);
259 : :
260 : : // If it has already been processed, just return the cached value.
261 : 289659394 : if (has_def_chain (name) && m_def_chain[v].bm)
262 : : return m_def_chain[v].bm;
263 : :
264 : : // No definition chain for default defs.
265 : 221624693 : if (SSA_NAME_IS_DEFAULT_DEF (name))
266 : : {
267 : : // A Default def is always an import.
268 : 12047354 : set_import (m_def_chain[v], name, NULL);
269 : 12047354 : return NULL;
270 : : }
271 : :
272 : 209577339 : gimple *stmt = SSA_NAME_DEF_STMT (name);
273 : 209577339 : unsigned count = gimple_range_ssa_names (ssa, 3, stmt);
274 : 209577339 : if (count == 0)
275 : : {
276 : : // Stmts not understood or with no operands are always imports.
277 : 167700090 : set_import (m_def_chain[v], name, NULL);
278 : 167700090 : return NULL;
279 : : }
280 : :
281 : : // Terminate the def chains if we see too many cascading stmts.
282 : 41877249 : if (m_logical_depth == param_ranger_logical_depth)
283 : : return NULL;
284 : :
285 : : // Increase the depth if we have a pair of ssa-names.
286 : 41742754 : if (count > 1)
287 : 10246712 : m_logical_depth++;
288 : :
289 : 93746550 : for (unsigned x = 0; x < count; x++)
290 : 52003796 : register_dependency (name, ssa[x], gimple_bb (stmt));
291 : :
292 : 41742754 : if (count > 1)
293 : 10246712 : m_logical_depth--;
294 : :
295 : 41742754 : return m_def_chain[v].bm;
296 : : }
297 : :
298 : : // Dump what we know for basic block BB to file F.
299 : :
300 : : void
301 : 117 : range_def_chain::dump (FILE *f, basic_block bb, const char *prefix)
302 : : {
303 : 117 : unsigned x, y;
304 : 117 : bitmap_iterator bi;
305 : :
306 : : // Dump the def chain for each SSA_NAME defined in BB.
307 : 16972 : for (x = 1; x < num_ssa_names; x++)
308 : : {
309 : 8369 : tree name = ssa_name (x);
310 : 8369 : if (!name)
311 : 3733 : continue;
312 : 4636 : gimple *stmt = SSA_NAME_DEF_STMT (name);
313 : 4636 : if (!stmt || (bb && gimple_bb (stmt) != bb))
314 : 4377 : continue;
315 : 8516 : bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL);
316 : 147 : if (chain && !bitmap_empty_p (chain))
317 : : {
318 : 132 : fprintf (f, prefix);
319 : 132 : print_generic_expr (f, name, TDF_SLIM);
320 : 132 : fprintf (f, " : ");
321 : :
322 : 132 : bitmap imports = get_imports (name);
323 : 463 : EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi)
324 : : {
325 : 331 : print_generic_expr (f, ssa_name (y), TDF_SLIM);
326 : 331 : if (imports && bitmap_bit_p (imports, y))
327 : 161 : fprintf (f, "(I)");
328 : 331 : fprintf (f, " ");
329 : : }
330 : 132 : fprintf (f, "\n");
331 : : }
332 : : }
333 : 117 : }
334 : :
335 : :
336 : : // -------------------------------------------------------------------
337 : :
338 : : /* GORI_MAP is used to accumulate what SSA names in a block can
339 : : generate range information, and provides tools for the block ranger
340 : : to enable it to efficiently calculate these ranges.
341 : :
342 : : GORI stands for "Generates Outgoing Range Information."
343 : :
344 : : It utilizes the range_def_chain class to construct def_chains.
345 : : Information for a basic block is calculated once and stored. It is
346 : : only calculated the first time a query is made. If no queries are
347 : : made, there is little overhead.
348 : :
349 : : one bitmap is maintained for each basic block:
350 : : m_outgoing : a set bit indicates a range can be generated for a name.
351 : :
352 : : Generally speaking, the m_outgoing vector is the union of the
353 : : entire def_chain of all SSA names used in the last statement of the
354 : : block which generate ranges. */
355 : :
356 : :
357 : : // Initialize a gori-map structure.
358 : :
359 : 24313476 : gori_map::gori_map ()
360 : : {
361 : 24313476 : m_outgoing.create (0);
362 : 24313476 : m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
363 : 24313476 : m_incoming.create (0);
364 : 24313476 : m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
365 : 24313476 : m_maybe_variant = BITMAP_ALLOC (&m_bitmaps);
366 : 24313476 : }
367 : :
368 : : // Free any memory the GORI map allocated.
369 : :
370 : 24313476 : gori_map::~gori_map ()
371 : : {
372 : 24313476 : m_incoming.release ();
373 : 24313476 : m_outgoing.release ();
374 : 24313476 : }
375 : :
376 : : // Return the bitmap vector of all export from BB. Calculate if necessary.
377 : :
378 : : bitmap
379 : 995099826 : gori_map::exports (basic_block bb)
380 : : {
381 : 1990199652 : if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
382 : 253927492 : calculate_gori (bb);
383 : 995099826 : return m_outgoing[bb->index];
384 : : }
385 : :
386 : : // Return the bitmap vector of all imports to BB. Calculate if necessary.
387 : :
388 : : bitmap
389 : 9096640 : gori_map::imports (basic_block bb)
390 : : {
391 : 18193280 : if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
392 : 0 : calculate_gori (bb);
393 : 9096640 : return m_incoming[bb->index];
394 : : }
395 : :
396 : : // Return true if NAME is can have ranges generated for it from basic
397 : : // block BB.
398 : :
399 : : bool
400 : 1118720150 : gori_map::is_export_p (tree name, basic_block bb)
401 : : {
402 : : // If no BB is specified, test if it is exported anywhere in the IL.
403 : 1118720150 : if (!bb)
404 : 494505423 : return bitmap_bit_p (m_maybe_variant, SSA_NAME_VERSION (name));
405 : 624214727 : return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name));
406 : : }
407 : :
408 : : // Set or clear the m_maybe_variant bit to determine if ranges will be tracked
409 : : // for NAME. A clear bit means they will NOT be tracked.
410 : :
411 : : void
412 : 5549901 : gori_map::set_range_invariant (tree name, bool invariant)
413 : : {
414 : 5549901 : if (invariant)
415 : 1769459 : bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name));
416 : : else
417 : 3780442 : bitmap_set_bit (m_maybe_variant, SSA_NAME_VERSION (name));
418 : 5549901 : }
419 : :
420 : : // Return true if NAME is an import to block BB.
421 : :
422 : : bool
423 : 0 : gori_map::is_import_p (tree name, basic_block bb)
424 : : {
425 : : // If no BB is specified, test if it is exported anywhere in the IL.
426 : 0 : return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name));
427 : : }
428 : :
429 : : // If NAME is non-NULL and defined in block BB, calculate the def
430 : : // chain and add it to m_outgoing.
431 : :
432 : : void
433 : 151816464 : gori_map::maybe_add_gori (tree name, basic_block bb)
434 : : {
435 : 151816464 : if (name)
436 : : {
437 : : // Check if there is a def chain, regardless of the block.
438 : 92492513 : add_def_chain_to_bitmap (m_outgoing[bb->index], name);
439 : : // Check for any imports.
440 : 92492513 : bitmap imp = get_imports (name);
441 : : // If there were imports, add them so we can recompute
442 : 92492513 : if (imp)
443 : 92491000 : bitmap_ior_into (m_incoming[bb->index], imp);
444 : : // This name is always an import.
445 : 92492513 : if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb)
446 : 22246068 : bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name));
447 : :
448 : : // Def chain doesn't include itself, and even if there isn't a
449 : : // def chain, this name should be added to exports.
450 : 92492513 : bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name));
451 : : }
452 : 151816464 : }
453 : :
454 : : // Calculate all the required information for BB.
455 : :
456 : : void
457 : 253927492 : gori_map::calculate_gori (basic_block bb)
458 : : {
459 : 253927492 : tree name;
460 : 507854984 : if (bb->index >= (signed int)m_outgoing.length ())
461 : : {
462 : 77 : m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
463 : 77 : m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
464 : : }
465 : 253927492 : gcc_checking_assert (m_outgoing[bb->index] == NULL);
466 : 253927492 : m_outgoing[bb->index] = BITMAP_ALLOC (&m_bitmaps);
467 : 253927492 : m_incoming[bb->index] = BITMAP_ALLOC (&m_bitmaps);
468 : :
469 : 253927492 : if (single_succ_p (bb))
470 : : return;
471 : :
472 : : // If this block's last statement may generate range information, go
473 : : // calculate it.
474 : 131263434 : gimple *stmt = gimple_outgoing_range_stmt_p (bb);
475 : 131263434 : if (!stmt)
476 : : return;
477 : 76109099 : if (is_a<gcond *> (stmt))
478 : : {
479 : 75708607 : gcond *gc = as_a<gcond *>(stmt);
480 : 75708607 : name = gimple_range_ssa_p (gimple_cond_lhs (gc));
481 : 75708607 : maybe_add_gori (name, gimple_bb (stmt));
482 : :
483 : 75708607 : name = gimple_range_ssa_p (gimple_cond_rhs (gc));
484 : 75708607 : maybe_add_gori (name, gimple_bb (stmt));
485 : : }
486 : : else
487 : : {
488 : : // Do not process switches if they are too large.
489 : 800984 : if (EDGE_COUNT (bb->succs) > (unsigned)param_vrp_switch_limit)
490 : : return;
491 : 399250 : gswitch *gs = as_a<gswitch *>(stmt);
492 : 399250 : name = gimple_range_ssa_p (gimple_switch_index (gs));
493 : 399250 : maybe_add_gori (name, gimple_bb (stmt));
494 : : }
495 : : // Add this bitmap to the aggregate list of all outgoing names.
496 : 76107857 : bitmap_ior_into (m_maybe_variant, m_outgoing[bb->index]);
497 : : }
498 : :
499 : : // Dump the table information for BB to file F.
500 : :
501 : : void
502 : 259 : gori_map::dump (FILE *f, basic_block bb, bool verbose)
503 : : {
504 : : // BB was not processed.
505 : 259 : if (!m_outgoing[bb->index] || bitmap_empty_p (m_outgoing[bb->index]))
506 : : return;
507 : :
508 : 117 : tree name;
509 : :
510 : 117 : bitmap imp = imports (bb);
511 : 117 : if (!bitmap_empty_p (imp))
512 : : {
513 : 117 : if (verbose)
514 : 0 : fprintf (f, "bb<%u> Imports: ",bb->index);
515 : : else
516 : 117 : fprintf (f, "Imports: ");
517 : 276 : FOR_EACH_GORI_IMPORT_NAME (*this, bb, name)
518 : : {
519 : 159 : print_generic_expr (f, name, TDF_SLIM);
520 : 159 : fprintf (f, " ");
521 : : }
522 : 117 : fputc ('\n', f);
523 : : }
524 : :
525 : 117 : if (verbose)
526 : 0 : fprintf (f, "bb<%u> Exports: ",bb->index);
527 : : else
528 : 117 : fprintf (f, "Exports: ");
529 : : // Dump the export vector.
530 : 382 : FOR_EACH_GORI_EXPORT_NAME (*this, bb, name)
531 : : {
532 : 265 : print_generic_expr (f, name, TDF_SLIM);
533 : 265 : fprintf (f, " ");
534 : : }
535 : 117 : fputc ('\n', f);
536 : :
537 : 117 : range_def_chain::dump (f, bb, " ");
538 : : }
539 : :
540 : : // Dump the entire GORI map structure to file F.
541 : :
542 : : void
543 : 0 : gori_map::dump (FILE *f)
544 : : {
545 : 0 : basic_block bb;
546 : 0 : FOR_EACH_BB_FN (bb, cfun)
547 : 0 : dump (f, bb);
548 : 0 : }
549 : :
550 : : DEBUG_FUNCTION void
551 : 0 : debug (gori_map &g)
552 : : {
553 : 0 : g.dump (stderr);
554 : 0 : }
555 : :
556 : : // -------------------------------------------------------------------
557 : :
558 : : // Construct a gori_compute object.
559 : :
560 : 24313476 : gori_compute::gori_compute (int not_executable_flag)
561 : 24313476 : : outgoing (param_vrp_switch_limit), tracer ("GORI ")
562 : : {
563 : 24313476 : m_not_executable_flag = not_executable_flag;
564 : : // Create a boolean_type true and false range.
565 : 24313476 : m_bool_zero = range_false ();
566 : 24313476 : m_bool_one = range_true ();
567 : 24313476 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_GORI))
568 : 0 : tracer.enable_trace ();
569 : 24313476 : }
570 : :
571 : : // Given the switch S, return an evaluation in R for NAME when the lhs
572 : : // evaluates to LHS. Returning false means the name being looked for
573 : : // was not resolvable.
574 : :
575 : : bool
576 : 143520 : gori_compute::compute_operand_range_switch (vrange &r, gswitch *s,
577 : : const vrange &lhs,
578 : : tree name, fur_source &src)
579 : : {
580 : 143520 : tree op1 = gimple_switch_index (s);
581 : :
582 : : // If name matches, the range is simply the range from the edge.
583 : : // Empty ranges are viral as they are on a path which isn't
584 : : // executable.
585 : 143520 : if (op1 == name || lhs.undefined_p ())
586 : : {
587 : 103913 : r = lhs;
588 : 103913 : return true;
589 : : }
590 : :
591 : : // If op1 is in the definition chain, pass lhs back.
592 : 39607 : if (gimple_range_ssa_p (op1) && in_chain_p (name, op1))
593 : 39472 : return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name, src);
594 : :
595 : : return false;
596 : : }
597 : :
598 : :
599 : : // Return an evaluation for NAME as it would appear in STMT when the
600 : : // statement's lhs evaluates to LHS. If successful, return TRUE and
601 : : // store the evaluation in R, otherwise return FALSE.
602 : :
603 : : bool
604 : 83623524 : gori_compute::compute_operand_range (vrange &r, gimple *stmt,
605 : : const vrange &lhs, tree name,
606 : : fur_source &src, value_relation *rel)
607 : : {
608 : 83623524 : value_relation vrel;
609 : 83623524 : value_relation *vrel_ptr = rel;
610 : : // Empty ranges are viral as they are on an unexecutable path.
611 : 83623524 : if (lhs.undefined_p ())
612 : : {
613 : 35255 : r.set_undefined ();
614 : 35255 : return true;
615 : : }
616 : 83588269 : if (is_a<gswitch *> (stmt))
617 : 143520 : return compute_operand_range_switch (r, as_a<gswitch *> (stmt), lhs, name,
618 : 143520 : src);
619 : 83444749 : gimple_range_op_handler handler (stmt);
620 : 83444749 : if (!handler)
621 : : return false;
622 : :
623 : 83341328 : tree op1 = gimple_range_ssa_p (handler.operand1 ());
624 : 83341328 : tree op2 = gimple_range_ssa_p (handler.operand2 ());
625 : :
626 : : // If there is a relation betwen op1 and op2, use it instead as it is
627 : : // likely to be more applicable.
628 : 83341328 : if (op1 && op2)
629 : : {
630 : 35418945 : Value_Range r1, r2;
631 : 35418945 : r1.set_varying (TREE_TYPE (op1));
632 : 35418945 : r2.set_varying (TREE_TYPE (op2));
633 : 35418945 : relation_kind k = handler.op1_op2_relation (lhs, r1, r2);
634 : 35418945 : if (k != VREL_VARYING)
635 : : {
636 : 24935943 : vrel.set_relation (k, op1, op2);
637 : 24935943 : vrel_ptr = &vrel;
638 : : }
639 : 35418945 : }
640 : :
641 : : // Handle end of lookup first.
642 : 83341328 : if (op1 == name)
643 : 40510097 : return compute_operand1_range (r, handler, lhs, src, vrel_ptr);
644 : 42831231 : if (op2 == name)
645 : 11691665 : return compute_operand2_range (r, handler, lhs, src, vrel_ptr);
646 : :
647 : : // NAME is not in this stmt, but one of the names in it ought to be
648 : : // derived from it.
649 : 31139566 : bool op1_in_chain = op1 && in_chain_p (name, op1);
650 : 31139566 : bool op2_in_chain = op2 && in_chain_p (name, op2);
651 : :
652 : : // If neither operand is derived, then this stmt tells us nothing.
653 : 31139566 : if (!op1_in_chain && !op2_in_chain)
654 : : return false;
655 : :
656 : : // If either operand is in the def chain of the other (or they are equal), it
657 : : // will be evaluated twice and can result in an exponential time calculation.
658 : : // Instead just evaluate the one operand.
659 : 30586989 : if (op1_in_chain && op2_in_chain)
660 : : {
661 : 1510801 : if (in_chain_p (op1, op2) || op1 == op2)
662 : : op1_in_chain = false;
663 : 1347052 : else if (in_chain_p (op2, op1))
664 : 114028 : op2_in_chain = false;
665 : : }
666 : :
667 : 30586989 : bool res = false;
668 : : // If the lhs doesn't tell us anything only a relation can possibly enhance
669 : : // the result.
670 : 30586989 : if (lhs.varying_p ())
671 : : {
672 : 1064555 : if (!vrel_ptr)
673 : : return false;
674 : : // If there is a relation (ie: x != y) , it can only be relevant if
675 : : // a) both elements are in the defchain
676 : : // c = x > y // (x and y are in c's defchain)
677 : 875244 : if (op1_in_chain)
678 : 632181 : res = in_chain_p (vrel_ptr->op1 (), op1)
679 : 632181 : && in_chain_p (vrel_ptr->op2 (), op1);
680 : 875244 : if (!res && op2_in_chain)
681 : 263090 : res = in_chain_p (vrel_ptr->op1 (), op2)
682 : 263090 : || in_chain_p (vrel_ptr->op2 (), op2);
683 : 612154 : if (!res)
684 : : {
685 : : // or b) one relation element is in the defchain of the other and the
686 : : // other is the LHS of this stmt.
687 : : // x = y + 2
688 : 873075 : if (vrel_ptr->op1 () == handler.lhs ()
689 : 873075 : && (vrel_ptr->op2 () == op1 || vrel_ptr->op2 () == op2))
690 : : res = true;
691 : 846191 : else if (vrel_ptr->op2 () == handler.lhs ()
692 : 846191 : && (vrel_ptr->op1 () == op1 || vrel_ptr->op1 () == op2))
693 : : res = true;
694 : : }
695 : : if (!res)
696 : : return false;
697 : : }
698 : :
699 : : // Process logicals as they have special handling.
700 : 29590822 : if (is_gimple_logical_p (stmt))
701 : : {
702 : : // If the lhs doesn't tell us anything, neither will combining operands.
703 : 2682750 : if (lhs.varying_p ())
704 : : return false;
705 : :
706 : 2682750 : unsigned idx;
707 : 2682750 : if ((idx = tracer.header ("compute_operand ")))
708 : : {
709 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
710 : 0 : fprintf (dump_file, " with LHS = ");
711 : 0 : lhs.dump (dump_file);
712 : 0 : fprintf (dump_file, " at stmt ");
713 : 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
714 : : }
715 : :
716 : 2682750 : tree type = TREE_TYPE (name);
717 : 2682750 : Value_Range op1_trange (type), op1_frange (type);
718 : 2682750 : Value_Range op2_trange (type), op2_frange (type);
719 : 2682750 : compute_logical_operands (op1_trange, op1_frange, handler,
720 : : as_a <irange> (lhs),
721 : : name, src, op1, op1_in_chain);
722 : 2682750 : compute_logical_operands (op2_trange, op2_frange, handler,
723 : : as_a <irange> (lhs),
724 : : name, src, op2, op2_in_chain);
725 : 2682750 : res = logical_combine (r,
726 : : gimple_expr_code (stmt),
727 : : as_a <irange> (lhs),
728 : : op1_trange, op1_frange, op2_trange, op2_frange);
729 : 2682750 : if (idx)
730 : 0 : tracer.trailer (idx, "compute_operand", res, name, r);
731 : 2682750 : return res;
732 : 2682750 : }
733 : : // Follow the appropriate operands now.
734 : 26908072 : if (op1_in_chain && op2_in_chain)
735 : 262429 : return compute_operand1_and_operand2_range (r, handler, lhs, name, src,
736 : 262429 : vrel_ptr);
737 : 26645643 : Value_Range vr;
738 : 26645643 : gimple *src_stmt;
739 : 26645643 : if (op1_in_chain)
740 : : {
741 : 21221270 : vr.set_type (TREE_TYPE (op1));
742 : 21221270 : if (!compute_operand1_range (vr, handler, lhs, src, vrel_ptr))
743 : : return false;
744 : 20521178 : src_stmt = SSA_NAME_DEF_STMT (op1);
745 : : }
746 : : else
747 : : {
748 : 5424373 : gcc_checking_assert (op2_in_chain);
749 : 5424373 : vr.set_type (TREE_TYPE (op2));
750 : 5424373 : if (!compute_operand2_range (vr, handler, lhs, src, vrel_ptr))
751 : : return false;
752 : 5118287 : src_stmt = SSA_NAME_DEF_STMT (op2);
753 : : }
754 : :
755 : 25639465 : gcc_checking_assert (src_stmt);
756 : : // Then feed this range back as the LHS of the defining statement.
757 : 25639465 : return compute_operand_range (r, src_stmt, vr, name, src, vrel_ptr);
758 : : // If neither operand is derived, this statement tells us nothing.
759 : 26645643 : }
760 : :
761 : :
762 : : // Return TRUE if range R is either a true or false compatible range.
763 : :
764 : : static bool
765 : 2233878 : range_is_either_true_or_false (const irange &r)
766 : : {
767 : 2233878 : if (r.undefined_p ())
768 : : return false;
769 : :
770 : : // This is complicated by the fact that Ada has multi-bit booleans,
771 : : // so true can be ~[0, 0] (i.e. [1,MAX]).
772 : 2233878 : tree type = r.type ();
773 : 2233878 : gcc_checking_assert (range_compatible_p (type, boolean_type_node));
774 : 2233878 : return (r.singleton_p ()
775 : 2233878 : || !r.contains_p (wi::zero (TYPE_PRECISION (type))));
776 : : }
777 : :
778 : : // Evaluate a binary logical expression by combining the true and
779 : : // false ranges for each of the operands based on the result value in
780 : : // the LHS.
781 : :
782 : : bool
783 : 2682750 : gori_compute::logical_combine (vrange &r, enum tree_code code,
784 : : const irange &lhs,
785 : : const vrange &op1_true, const vrange &op1_false,
786 : : const vrange &op2_true, const vrange &op2_false)
787 : : {
788 : 2682750 : if (op1_true.varying_p () && op1_false.varying_p ()
789 : 3582148 : && op2_true.varying_p () && op2_false.varying_p ())
790 : : return false;
791 : :
792 : 2233878 : unsigned idx;
793 : 2233878 : if ((idx = tracer.header ("logical_combine")))
794 : : {
795 : 0 : switch (code)
796 : : {
797 : 0 : case TRUTH_OR_EXPR:
798 : 0 : case BIT_IOR_EXPR:
799 : 0 : fprintf (dump_file, " || ");
800 : 0 : break;
801 : 0 : case TRUTH_AND_EXPR:
802 : 0 : case BIT_AND_EXPR:
803 : 0 : fprintf (dump_file, " && ");
804 : 0 : break;
805 : : default:
806 : : break;
807 : : }
808 : 0 : fprintf (dump_file, " with LHS = ");
809 : 0 : lhs.dump (dump_file);
810 : 0 : fputc ('\n', dump_file);
811 : :
812 : 0 : tracer.print (idx, "op1_true = ");
813 : 0 : op1_true.dump (dump_file);
814 : 0 : fprintf (dump_file, " op1_false = ");
815 : 0 : op1_false.dump (dump_file);
816 : 0 : fputc ('\n', dump_file);
817 : 0 : tracer.print (idx, "op2_true = ");
818 : 0 : op2_true.dump (dump_file);
819 : 0 : fprintf (dump_file, " op2_false = ");
820 : 0 : op2_false.dump (dump_file);
821 : 0 : fputc ('\n', dump_file);
822 : : }
823 : :
824 : : // This is not a simple fold of a logical expression, rather it
825 : : // determines ranges which flow through the logical expression.
826 : : //
827 : : // Assuming x_8 is an unsigned char, and relational statements:
828 : : // b_1 = x_8 < 20
829 : : // b_2 = x_8 > 5
830 : : // consider the logical expression and branch:
831 : : // c_2 = b_1 && b_2
832 : : // if (c_2)
833 : : //
834 : : // To determine the range of x_8 on either edge of the branch, one
835 : : // must first determine what the range of x_8 is when the boolean
836 : : // values of b_1 and b_2 are both true and false.
837 : : // b_1 TRUE x_8 = [0, 19]
838 : : // b_1 FALSE x_8 = [20, 255]
839 : : // b_2 TRUE x_8 = [6, 255]
840 : : // b_2 FALSE x_8 = [0,5].
841 : : //
842 : : // These ranges are then combined based on the expected outcome of
843 : : // the branch. The range on the TRUE side of the branch must satisfy
844 : : // b_1 == true && b_2 == true
845 : : //
846 : : // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
847 : : // must be true. The range of x_8 on the true side must be the
848 : : // intersection of both ranges since both must be true. Thus the
849 : : // range of x_8 on the true side is [6, 19].
850 : : //
851 : : // To determine the ranges on the FALSE side, all 3 combinations of
852 : : // failing ranges must be considered, and combined as any of them
853 : : // can cause the false result.
854 : : //
855 : : // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
856 : : // FALSE results and combine them. If we fell back to VARYING any
857 : : // range restrictions that have been discovered up to this point
858 : : // would be lost.
859 : 2233878 : if (!range_is_either_true_or_false (lhs))
860 : : {
861 : 0 : bool res;
862 : 0 : Value_Range r1 (r);
863 : 0 : if (logical_combine (r1, code, m_bool_zero, op1_true, op1_false,
864 : : op2_true, op2_false)
865 : 0 : && logical_combine (r, code, m_bool_one, op1_true, op1_false,
866 : : op2_true, op2_false))
867 : : {
868 : 0 : r.union_ (r1);
869 : 0 : res = true;
870 : : }
871 : : else
872 : : res = false;
873 : 0 : if (idx && res)
874 : : {
875 : 0 : tracer.print (idx, "logical_combine produced ");
876 : 0 : r.dump (dump_file);
877 : 0 : fputc ('\n', dump_file);
878 : : }
879 : 0 : return res;
880 : 0 : }
881 : :
882 : 2233878 : switch (code)
883 : : {
884 : : // A logical AND combines ranges from 2 boolean conditions.
885 : : // c_2 = b_1 && b_2
886 : 1518636 : case TRUTH_AND_EXPR:
887 : 1518636 : case BIT_AND_EXPR:
888 : 1518636 : if (!lhs.zero_p ())
889 : : {
890 : : // The TRUE side is the intersection of the 2 true ranges.
891 : 808289 : r = op1_true;
892 : 808289 : r.intersect (op2_true);
893 : : }
894 : : else
895 : : {
896 : : // The FALSE side is the union of the other 3 cases.
897 : 710347 : Value_Range ff (op1_false);
898 : 710347 : ff.intersect (op2_false);
899 : 710347 : Value_Range tf (op1_true);
900 : 710347 : tf.intersect (op2_false);
901 : 710347 : Value_Range ft (op1_false);
902 : 710347 : ft.intersect (op2_true);
903 : 710347 : r = ff;
904 : 710347 : r.union_ (tf);
905 : 710347 : r.union_ (ft);
906 : 710347 : }
907 : : break;
908 : : // A logical OR combines ranges from 2 boolean conditions.
909 : : // c_2 = b_1 || b_2
910 : 715242 : case TRUTH_OR_EXPR:
911 : 715242 : case BIT_IOR_EXPR:
912 : 715242 : if (lhs.zero_p ())
913 : : {
914 : : // An OR operation will only take the FALSE path if both
915 : : // operands are false simultaneously, which means they should
916 : : // be intersected. !(x || y) == !x && !y
917 : 485504 : r = op1_false;
918 : 485504 : r.intersect (op2_false);
919 : : }
920 : : else
921 : : {
922 : : // The TRUE side of an OR operation will be the union of
923 : : // the other three combinations.
924 : 229738 : Value_Range tt (op1_true);
925 : 229738 : tt.intersect (op2_true);
926 : 229738 : Value_Range tf (op1_true);
927 : 229738 : tf.intersect (op2_false);
928 : 229738 : Value_Range ft (op1_false);
929 : 229738 : ft.intersect (op2_true);
930 : 229738 : r = tt;
931 : 229738 : r.union_ (tf);
932 : 229738 : r.union_ (ft);
933 : 229738 : }
934 : : break;
935 : 0 : default:
936 : 0 : gcc_unreachable ();
937 : : }
938 : :
939 : 2233878 : if (idx)
940 : 0 : tracer.trailer (idx, "logical_combine", true, NULL_TREE, r);
941 : : return true;
942 : : }
943 : :
944 : :
945 : : // Given a logical STMT, calculate true and false ranges for each
946 : : // potential path of NAME, assuming NAME came through the OP chain if
947 : : // OP_IN_CHAIN is true.
948 : :
949 : : void
950 : 5365500 : gori_compute::compute_logical_operands (vrange &true_range, vrange &false_range,
951 : : gimple_range_op_handler &handler,
952 : : const irange &lhs,
953 : : tree name, fur_source &src,
954 : : tree op, bool op_in_chain)
955 : : {
956 : 5365500 : gimple *stmt = handler.stmt ();
957 : 10731000 : gimple *src_stmt = gimple_range_ssa_p (op) ? SSA_NAME_DEF_STMT (op) : NULL;
958 : 5365500 : if (!op_in_chain || !src_stmt || chain_import_p (handler.lhs (), op))
959 : : {
960 : : // If op is not in the def chain, or defined in this block,
961 : : // use its known value on entry to the block.
962 : 1755282 : src.get_operand (true_range, name);
963 : 1755282 : false_range = true_range;
964 : 1755282 : unsigned idx;
965 : 1755282 : if ((idx = tracer.header ("logical_operand")))
966 : : {
967 : 0 : print_generic_expr (dump_file, op, TDF_SLIM);
968 : 0 : fprintf (dump_file, " not in computation chain. Queried.\n");
969 : 0 : tracer.trailer (idx, "logical_operand", true, NULL_TREE, true_range);
970 : : }
971 : 1755282 : return;
972 : : }
973 : :
974 : 3610218 : enum tree_code code = gimple_expr_code (stmt);
975 : : // Optimize [0 = x | y], since neither operand can ever be non-zero.
976 : 3610218 : if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ())
977 : : {
978 : 811340 : if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name,
979 : : src))
980 : 66117 : src.get_operand (false_range, name);
981 : 811340 : true_range = false_range;
982 : 811340 : return;
983 : : }
984 : :
985 : : // Optimize [1 = x & y], since neither operand can ever be zero.
986 : 2798878 : if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one)
987 : : {
988 : 1477473 : if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src))
989 : 111418 : src.get_operand (true_range, name);
990 : 1477473 : false_range = true_range;
991 : 1477473 : return;
992 : : }
993 : :
994 : : // Calculate ranges for true and false on both sides, since the false
995 : : // path is not always a simple inversion of the true side.
996 : 1321405 : if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src))
997 : 110831 : src.get_operand (true_range, name);
998 : 1321405 : if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, src))
999 : 114311 : src.get_operand (false_range, name);
1000 : : }
1001 : :
1002 : :
1003 : : // This routine will try to refine the ranges of OP1 and OP2 given a relation
1004 : : // K between them. In order to perform this refinement, one of the operands
1005 : : // must be in the definition chain of the other. The use is refined using
1006 : : // op1/op2_range on the statement, and the definition is then recalculated
1007 : : // using the relation.
1008 : :
1009 : : bool
1010 : 24942816 : gori_compute::refine_using_relation (tree op1, vrange &op1_range,
1011 : : tree op2, vrange &op2_range,
1012 : : fur_source &src, relation_kind k)
1013 : : {
1014 : 24942816 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1015 : 24942816 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1016 : :
1017 : 24942816 : if (k == VREL_VARYING || k == VREL_EQ || k == VREL_UNDEFINED)
1018 : : return false;
1019 : :
1020 : 20314409 : bool change = false;
1021 : 20314409 : bool op1_def_p = in_chain_p (op2, op1);
1022 : 20314409 : if (!op1_def_p)
1023 : 19893882 : if (!in_chain_p (op1, op2))
1024 : : return false;
1025 : :
1026 : : tree def_op = op1_def_p ? op1 : op2;
1027 : 1411363 : tree use_op = op1_def_p ? op2 : op1;
1028 : :
1029 : 1411363 : if (!op1_def_p)
1030 : 990836 : k = relation_swap (k);
1031 : :
1032 : : // op1_def is true if we want to look up op1, otherwise we want op2.
1033 : : // if neither is the case, we returned in the above check.
1034 : :
1035 : 1411363 : gimple *def_stmt = SSA_NAME_DEF_STMT (def_op);
1036 : 1411363 : gimple_range_op_handler op_handler (def_stmt);
1037 : 1411363 : if (!op_handler)
1038 : : return false;
1039 : 1407728 : tree def_op1 = op_handler.operand1 ();
1040 : 1407728 : tree def_op2 = op_handler.operand2 ();
1041 : : // if the def isn't binary, the relation will not be useful.
1042 : 1407728 : if (!def_op2)
1043 : : return false;
1044 : :
1045 : : // Determine if op2 is directly referenced as an operand.
1046 : 1388186 : if (def_op1 == use_op)
1047 : : {
1048 : : // def_stmt has op1 in the 1st operand position.
1049 : 634857 : Value_Range other_op (TREE_TYPE (def_op2));
1050 : 634857 : src.get_operand (other_op, def_op2);
1051 : :
1052 : : // Using op1_range as the LHS, and relation REL, evaluate op2.
1053 : 634857 : tree type = TREE_TYPE (def_op1);
1054 : 634857 : Value_Range new_result (type);
1055 : 1010160 : if (!op_handler.op1_range (new_result, type,
1056 : : op1_def_p ? op1_range : op2_range,
1057 : : other_op, relation_trio::lhs_op1 (k)))
1058 : 77315 : return false;
1059 : 557542 : if (op1_def_p)
1060 : : {
1061 : 217678 : change |= op2_range.intersect (new_result);
1062 : : // Recalculate op2.
1063 : 217678 : if (op_handler.fold_range (new_result, type, op2_range, other_op))
1064 : : {
1065 : 217678 : change |= op1_range.intersect (new_result);
1066 : : }
1067 : : }
1068 : : else
1069 : : {
1070 : 339864 : change |= op1_range.intersect (new_result);
1071 : : // Recalculate op1.
1072 : 339864 : if (op_handler.fold_range (new_result, type, op1_range, other_op))
1073 : : {
1074 : 339864 : change |= op2_range.intersect (new_result);
1075 : : }
1076 : : }
1077 : 634857 : }
1078 : 753329 : else if (def_op2 == use_op)
1079 : : {
1080 : : // def_stmt has op1 in the 1st operand position.
1081 : 520124 : Value_Range other_op (TREE_TYPE (def_op1));
1082 : 520124 : src.get_operand (other_op, def_op1);
1083 : :
1084 : : // Using op1_range as the LHS, and relation REL, evaluate op2.
1085 : 520124 : tree type = TREE_TYPE (def_op2);
1086 : 520124 : Value_Range new_result (type);
1087 : 952283 : if (!op_handler.op2_range (new_result, type,
1088 : : op1_def_p ? op1_range : op2_range,
1089 : : other_op, relation_trio::lhs_op2 (k)))
1090 : 5948 : return false;
1091 : 514176 : if (op1_def_p)
1092 : : {
1093 : 85408 : change |= op2_range.intersect (new_result);
1094 : : // Recalculate op1.
1095 : 85408 : if (op_handler.fold_range (new_result, type, other_op, op2_range))
1096 : : {
1097 : 85408 : change |= op1_range.intersect (new_result);
1098 : : }
1099 : : }
1100 : : else
1101 : : {
1102 : 428768 : change |= op1_range.intersect (new_result);
1103 : : // Recalculate op2.
1104 : 428768 : if (op_handler.fold_range (new_result, type, other_op, op1_range))
1105 : : {
1106 : 428768 : change |= op2_range.intersect (new_result);
1107 : : }
1108 : : }
1109 : 520124 : }
1110 : : return change;
1111 : : }
1112 : :
1113 : : // Calculate a range for NAME from the operand 1 position of STMT
1114 : : // assuming the result of the statement is LHS. Return the range in
1115 : : // R, or false if no range could be calculated.
1116 : :
1117 : : bool
1118 : 61841092 : gori_compute::compute_operand1_range (vrange &r,
1119 : : gimple_range_op_handler &handler,
1120 : : const vrange &lhs,
1121 : : fur_source &src, value_relation *rel)
1122 : : {
1123 : 61841092 : gimple *stmt = handler.stmt ();
1124 : 61841092 : tree op1 = handler.operand1 ();
1125 : 61841092 : tree op2 = handler.operand2 ();
1126 : 61841092 : tree lhs_name = gimple_get_lhs (stmt);
1127 : :
1128 : 61841092 : relation_trio trio;
1129 : 61841092 : if (rel)
1130 : 20570160 : trio = rel->create_trio (lhs_name, op1, op2);
1131 : :
1132 : 61841092 : Value_Range op1_range (TREE_TYPE (op1));
1133 : 61841092 : Value_Range op2_range (op2 ? TREE_TYPE (op2) : TREE_TYPE (op1));
1134 : :
1135 : : // Fetch the known range for op1 in this block.
1136 : 61841092 : src.get_operand (op1_range, op1);
1137 : :
1138 : : // Now range-op calculate and put that result in r.
1139 : 61841092 : if (op2)
1140 : : {
1141 : 54122975 : src.get_operand (op2_range, op2);
1142 : :
1143 : 54122975 : relation_kind op_op = trio.op1_op2 ();
1144 : 54122975 : if (op_op != VREL_VARYING)
1145 : 12522497 : refine_using_relation (op1, op1_range, op2, op2_range, src, op_op);
1146 : :
1147 : : // If op1 == op2, create a new trio for just this call.
1148 : 54122975 : if (op1 == op2 && gimple_range_ssa_p (op1))
1149 : 70220 : trio = relation_trio (trio.lhs_op1 (), trio.lhs_op2 (), VREL_EQ);
1150 : 54122975 : if (!handler.calc_op1 (r, lhs, op2_range, trio))
1151 : : return false;
1152 : : }
1153 : : else
1154 : : {
1155 : : // We pass op1_range to the unary operation. Normally it's a
1156 : : // hidden range_for_type parameter, but sometimes having the
1157 : : // actual range can result in better information.
1158 : 7718117 : if (!handler.calc_op1 (r, lhs, op1_range, trio))
1159 : : return false;
1160 : : }
1161 : :
1162 : 59918011 : unsigned idx;
1163 : 59918011 : if ((idx = tracer.header ("compute op 1 (")))
1164 : : {
1165 : 0 : print_generic_expr (dump_file, op1, TDF_SLIM);
1166 : 0 : fprintf (dump_file, ") at ");
1167 : 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1168 : 0 : tracer.print (idx, "LHS =");
1169 : 0 : lhs.dump (dump_file);
1170 : 0 : if (op2 && TREE_CODE (op2) == SSA_NAME)
1171 : : {
1172 : 0 : fprintf (dump_file, ", ");
1173 : 0 : print_generic_expr (dump_file, op2, TDF_SLIM);
1174 : 0 : fprintf (dump_file, " = ");
1175 : 0 : op2_range.dump (dump_file);
1176 : : }
1177 : 0 : fprintf (dump_file, "\n");
1178 : 0 : tracer.print (idx, "Computes ");
1179 : 0 : print_generic_expr (dump_file, op1, TDF_SLIM);
1180 : 0 : fprintf (dump_file, " = ");
1181 : 0 : r.dump (dump_file);
1182 : 0 : fprintf (dump_file, " intersect Known range : ");
1183 : 0 : op1_range.dump (dump_file);
1184 : 0 : fputc ('\n', dump_file);
1185 : : }
1186 : :
1187 : 59918011 : r.intersect (op1_range);
1188 : 59918011 : if (idx)
1189 : 0 : tracer.trailer (idx, "produces ", true, op1, r);
1190 : : return true;
1191 : 61841092 : }
1192 : :
1193 : :
1194 : : // Calculate a range for NAME from the operand 2 position of S
1195 : : // assuming the result of the statement is LHS. Return the range in
1196 : : // R, or false if no range could be calculated.
1197 : :
1198 : : bool
1199 : 17378467 : gori_compute::compute_operand2_range (vrange &r,
1200 : : gimple_range_op_handler &handler,
1201 : : const vrange &lhs,
1202 : : fur_source &src, value_relation *rel)
1203 : : {
1204 : 17378467 : gimple *stmt = handler.stmt ();
1205 : 17378467 : tree op1 = handler.operand1 ();
1206 : 17378467 : tree op2 = handler.operand2 ();
1207 : 17378467 : tree lhs_name = gimple_get_lhs (stmt);
1208 : :
1209 : 17378467 : Value_Range op1_range (TREE_TYPE (op1));
1210 : 17378467 : Value_Range op2_range (TREE_TYPE (op2));
1211 : :
1212 : 17378467 : src.get_operand (op1_range, op1);
1213 : 17378467 : src.get_operand (op2_range, op2);
1214 : :
1215 : 17378467 : relation_trio trio;
1216 : 17378467 : if (rel)
1217 : 14060016 : trio = rel->create_trio (lhs_name, op1, op2);
1218 : 17378467 : relation_kind op_op = trio.op1_op2 ();
1219 : :
1220 : 17378467 : if (op_op != VREL_VARYING)
1221 : 12420319 : refine_using_relation (op1, op1_range, op2, op2_range, src, op_op);
1222 : :
1223 : : // If op1 == op2, create a new trio for this stmt.
1224 : 17378467 : if (op1 == op2 && gimple_range_ssa_p (op1))
1225 : 29660 : trio = relation_trio (trio.lhs_op1 (), trio.lhs_op2 (), VREL_EQ);
1226 : : // Intersect with range for op2 based on lhs and op1.
1227 : 17378467 : if (!handler.calc_op2 (r, lhs, op1_range, trio))
1228 : : return false;
1229 : :
1230 : 15922472 : unsigned idx;
1231 : 15922472 : if ((idx = tracer.header ("compute op 2 (")))
1232 : : {
1233 : 0 : print_generic_expr (dump_file, op2, TDF_SLIM);
1234 : 0 : fprintf (dump_file, ") at ");
1235 : 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1236 : 0 : tracer.print (idx, "LHS = ");
1237 : 0 : lhs.dump (dump_file);
1238 : 0 : if (TREE_CODE (op1) == SSA_NAME)
1239 : : {
1240 : 0 : fprintf (dump_file, ", ");
1241 : 0 : print_generic_expr (dump_file, op1, TDF_SLIM);
1242 : 0 : fprintf (dump_file, " = ");
1243 : 0 : op1_range.dump (dump_file);
1244 : : }
1245 : 0 : fprintf (dump_file, "\n");
1246 : 0 : tracer.print (idx, "Computes ");
1247 : 0 : print_generic_expr (dump_file, op2, TDF_SLIM);
1248 : 0 : fprintf (dump_file, " = ");
1249 : 0 : r.dump (dump_file);
1250 : 0 : fprintf (dump_file, " intersect Known range : ");
1251 : 0 : op2_range.dump (dump_file);
1252 : 0 : fputc ('\n', dump_file);
1253 : : }
1254 : : // Intersect the calculated result with the known result and return if done.
1255 : 15922472 : r.intersect (op2_range);
1256 : 15922472 : if (idx)
1257 : 0 : tracer.trailer (idx, " produces ", true, op2, r);
1258 : : return true;
1259 : 17378467 : }
1260 : :
1261 : : // Calculate a range for NAME from both operand positions of S
1262 : : // assuming the result of the statement is LHS. Return the range in
1263 : : // R, or false if no range could be calculated.
1264 : :
1265 : : bool
1266 : 262429 : gori_compute::compute_operand1_and_operand2_range (vrange &r,
1267 : : gimple_range_op_handler
1268 : : &handler,
1269 : : const vrange &lhs,
1270 : : tree name,
1271 : : fur_source &src,
1272 : : value_relation *rel)
1273 : : {
1274 : 262429 : Value_Range op_range (TREE_TYPE (name));
1275 : :
1276 : 262429 : Value_Range vr (TREE_TYPE (handler.operand2 ()));
1277 : : // Calculate a good a range through op2.
1278 : 262429 : if (!compute_operand2_range (vr, handler, lhs, src, rel))
1279 : : return false;
1280 : 247686 : gimple *src_stmt = SSA_NAME_DEF_STMT (handler.operand2 ());
1281 : 247686 : gcc_checking_assert (src_stmt);
1282 : : // Then feed this range back as the LHS of the defining statement.
1283 : 247686 : if (!compute_operand_range (r, src_stmt, vr, name, src, rel))
1284 : : return false;
1285 : :
1286 : : // Now get the range thru op1.
1287 : 109725 : vr.set_type (TREE_TYPE (handler.operand1 ()));
1288 : 109725 : if (!compute_operand1_range (vr, handler, lhs, src, rel))
1289 : : return false;
1290 : 109723 : src_stmt = SSA_NAME_DEF_STMT (handler.operand1 ());
1291 : 109723 : gcc_checking_assert (src_stmt);
1292 : : // Then feed this range back as the LHS of the defining statement.
1293 : 109723 : if (!compute_operand_range (op_range, src_stmt, vr, name, src, rel))
1294 : : return false;
1295 : :
1296 : : // Both operands have to be simultaneously true, so perform an intersection.
1297 : 92874 : r.intersect (op_range);
1298 : 92874 : return true;
1299 : 262429 : }
1300 : :
1301 : : // Return TRUE if NAME can be recomputed on any edge exiting BB. If any
1302 : : // direct dependent is exported, it may also change the computed value of NAME.
1303 : :
1304 : : bool
1305 : 506715051 : gori_compute::may_recompute_p (tree name, basic_block bb, int depth)
1306 : : {
1307 : 730144888 : tree dep1 = depend1 (name);
1308 : 730144888 : tree dep2 = depend2 (name);
1309 : :
1310 : : // If the first dependency is not set, there is no recomputation.
1311 : : // Dependencies reflect original IL, not current state. Check if the
1312 : : // SSA_NAME is still valid as well.
1313 : 730144888 : if (!dep1)
1314 : : return false;
1315 : :
1316 : : // Don't recalculate PHIs or statements with side_effects.
1317 : 504852168 : gimple *s = SSA_NAME_DEF_STMT (name);
1318 : 504852168 : if (is_a<gphi *> (s) || gimple_has_side_effects (s))
1319 : 202348369 : return false;
1320 : :
1321 : 302503799 : if (!dep2)
1322 : : {
1323 : : // -1 indicates a default param, convert it to the real default.
1324 : 255257637 : if (depth == -1)
1325 : : {
1326 : 217208773 : depth = (int)param_ranger_recompute_depth;
1327 : 217208773 : gcc_checking_assert (depth >= 1);
1328 : : }
1329 : :
1330 : 255257637 : bool res = (bb ? is_export_p (dep1, bb) : is_export_p (dep1));
1331 : 255257637 : if (res || depth <= 1)
1332 : : return res;
1333 : : // Check another level of recomputation.
1334 : 223429837 : return may_recompute_p (dep1, bb, --depth);
1335 : : }
1336 : : // Two dependencies terminate the depth of the search.
1337 : 47246162 : if (bb)
1338 : 17757067 : return is_export_p (dep1, bb) || is_export_p (dep2, bb);
1339 : : else
1340 : 29489095 : return is_export_p (dep1) || is_export_p (dep2);
1341 : : }
1342 : :
1343 : : // Return TRUE if NAME can be recomputed on edge E. If any direct dependent
1344 : : // is exported on edge E, it may change the computed value of NAME.
1345 : :
1346 : : bool
1347 : 17718086 : gori_compute::may_recompute_p (tree name, edge e, int depth)
1348 : : {
1349 : 17718086 : gcc_checking_assert (e);
1350 : 17718086 : return may_recompute_p (name, e->src, depth);
1351 : : }
1352 : :
1353 : :
1354 : : // Return TRUE if a range can be calculated or recomputed for NAME on any
1355 : : // edge exiting BB.
1356 : :
1357 : : bool
1358 : 704518818 : gori_compute::has_edge_range_p (tree name, basic_block bb)
1359 : : {
1360 : : // Check if NAME is an export or can be recomputed.
1361 : 704518818 : if (bb)
1362 : 339170410 : return is_export_p (name, bb) || may_recompute_p (name, bb);
1363 : :
1364 : : // If no block is specified, check for anywhere in the IL.
1365 : 365348408 : return is_export_p (name) || may_recompute_p (name);
1366 : : }
1367 : :
1368 : : // Return TRUE if a range can be calculated or recomputed for NAME on edge E.
1369 : :
1370 : : bool
1371 : 41528 : gori_compute::has_edge_range_p (tree name, edge e)
1372 : : {
1373 : 41528 : gcc_checking_assert (e);
1374 : 41528 : return has_edge_range_p (name, e->src);
1375 : : }
1376 : :
1377 : : // Calculate a range on edge E and return it in R. Try to evaluate a
1378 : : // range for NAME on this edge. Return FALSE if this is either not a
1379 : : // control edge or NAME is not defined by this edge.
1380 : :
1381 : : bool
1382 : 107609992 : gori_compute::outgoing_edge_range_p (vrange &r, edge e, tree name,
1383 : : range_query &q)
1384 : : {
1385 : 107609992 : unsigned idx;
1386 : :
1387 : 107609992 : if ((e->flags & m_not_executable_flag))
1388 : : {
1389 : 34345 : r.set_undefined ();
1390 : 34345 : if (dump_file && (dump_flags & TDF_DETAILS))
1391 : 24 : fprintf (dump_file, "Outgoing edge %d->%d unexecutable.\n",
1392 : 24 : e->src->index, e->dest->index);
1393 : 34345 : return true;
1394 : : }
1395 : :
1396 : 107575647 : gcc_checking_assert (gimple_range_ssa_p (name));
1397 : 107575647 : int_range_max lhs;
1398 : : // Determine if there is an outgoing edge.
1399 : 107575647 : gimple *stmt = outgoing.edge_range_p (lhs, e);
1400 : 107575647 : if (!stmt)
1401 : : return false;
1402 : :
1403 : 70372994 : fur_stmt src (stmt, &q);
1404 : : // If NAME can be calculated on the edge, use that.
1405 : 70372994 : if (is_export_p (name, e->src))
1406 : : {
1407 : 52654908 : bool res;
1408 : 52654908 : if ((idx = tracer.header ("outgoing_edge")))
1409 : : {
1410 : 0 : fprintf (dump_file, " for ");
1411 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1412 : 0 : fprintf (dump_file, " on edge %d->%d\n",
1413 : 0 : e->src->index, e->dest->index);
1414 : : }
1415 : 52654908 : if ((res = compute_operand_range (r, stmt, lhs, name, src)))
1416 : : {
1417 : : // Sometimes compatible types get interchanged. See PR97360.
1418 : : // Make sure we are returning the type of the thing we asked for.
1419 : 47577341 : if (!r.undefined_p () && r.type () != TREE_TYPE (name))
1420 : : {
1421 : 3416319 : gcc_checking_assert (range_compatible_p (r.type (),
1422 : : TREE_TYPE (name)));
1423 : 3416319 : range_cast (r, TREE_TYPE (name));
1424 : : }
1425 : : }
1426 : 52654908 : if (idx)
1427 : 0 : tracer.trailer (idx, "outgoing_edge", res, name, r);
1428 : 52654908 : return res;
1429 : : }
1430 : : // If NAME isn't exported, check if it can be recomputed.
1431 : 17718086 : else if (may_recompute_p (name, e))
1432 : : {
1433 : 4774237 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1434 : :
1435 : 4774237 : if ((idx = tracer.header ("recomputation")))
1436 : : {
1437 : 0 : fprintf (dump_file, " attempt on edge %d->%d for ",
1438 : 0 : e->src->index, e->dest->index);
1439 : 0 : print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM);
1440 : : }
1441 : : // Simply calculate DEF_STMT on edge E using the range query Q.
1442 : 4774237 : fold_range (r, def_stmt, e, &q);
1443 : 4774237 : if (idx)
1444 : 0 : tracer.trailer (idx, "recomputation", true, name, r);
1445 : 4774237 : return true;
1446 : : }
1447 : : return false;
1448 : 107575647 : }
1449 : :
1450 : : // Given COND ? OP1 : OP2 with ranges R1 for OP1 and R2 for OP2, Use gori
1451 : : // to further resolve R1 and R2 if there are any dependencies between
1452 : : // OP1 and COND or OP2 and COND. All values can are to be calculated using SRC
1453 : : // as the origination source location for operands..
1454 : : // Effectively, use COND an the edge condition and solve for OP1 on the true
1455 : : // edge and OP2 on the false edge.
1456 : :
1457 : : bool
1458 : 50750 : gori_compute::condexpr_adjust (vrange &r1, vrange &r2, gimple *, tree cond,
1459 : : tree op1, tree op2, fur_source &src)
1460 : : {
1461 : 50750 : tree ssa1 = gimple_range_ssa_p (op1);
1462 : 50750 : tree ssa2 = gimple_range_ssa_p (op2);
1463 : 50750 : if (!ssa1 && !ssa2)
1464 : : return false;
1465 : 44561 : if (TREE_CODE (cond) != SSA_NAME)
1466 : : return false;
1467 : 80591 : gassign *cond_def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (cond));
1468 : 44533 : if (!cond_def
1469 : 44533 : || TREE_CODE_CLASS (gimple_assign_rhs_code (cond_def)) != tcc_comparison)
1470 : : return false;
1471 : 44016 : tree type = TREE_TYPE (gimple_assign_rhs1 (cond_def));
1472 : 88032 : if (!range_compatible_p (type, TREE_TYPE (gimple_assign_rhs2 (cond_def))))
1473 : : return false;
1474 : 44016 : range_op_handler hand (gimple_assign_rhs_code (cond_def));
1475 : 44016 : if (!hand)
1476 : : return false;
1477 : :
1478 : 44016 : tree c1 = gimple_range_ssa_p (gimple_assign_rhs1 (cond_def));
1479 : 88032 : tree c2 = gimple_range_ssa_p (gimple_assign_rhs2 (cond_def));
1480 : :
1481 : : // Only solve if there is one SSA name in the condition.
1482 : 44016 : if ((!c1 && !c2) || (c1 && c2))
1483 : : return false;
1484 : :
1485 : : // Pick up the current values of each part of the condition.
1486 : 14692 : tree rhs1 = gimple_assign_rhs1 (cond_def);
1487 : 14692 : tree rhs2 = gimple_assign_rhs2 (cond_def);
1488 : 14692 : Value_Range cl (TREE_TYPE (rhs1));
1489 : 14692 : Value_Range cr (TREE_TYPE (rhs2));
1490 : 14692 : src.get_operand (cl, rhs1);
1491 : 14692 : src.get_operand (cr, rhs2);
1492 : :
1493 : 14692 : tree cond_name = c1 ? c1 : c2;
1494 : 14692 : gimple *def_stmt = SSA_NAME_DEF_STMT (cond_name);
1495 : :
1496 : : // Evaluate the value of COND_NAME on the true and false edges, using either
1497 : : // the op1 or op2 routines based on its location.
1498 : 14692 : Value_Range cond_true (type), cond_false (type);
1499 : 14692 : if (c1)
1500 : : {
1501 : 14692 : if (!hand.op1_range (cond_false, type, m_bool_zero, cr))
1502 : : return false;
1503 : 14692 : if (!hand.op1_range (cond_true, type, m_bool_one, cr))
1504 : : return false;
1505 : 14692 : cond_false.intersect (cl);
1506 : 14692 : cond_true.intersect (cl);
1507 : : }
1508 : : else
1509 : : {
1510 : 0 : if (!hand.op2_range (cond_false, type, m_bool_zero, cl))
1511 : : return false;
1512 : 0 : if (!hand.op2_range (cond_true, type, m_bool_one, cl))
1513 : : return false;
1514 : 0 : cond_false.intersect (cr);
1515 : 0 : cond_true.intersect (cr);
1516 : : }
1517 : :
1518 : 14692 : unsigned idx;
1519 : 14692 : if ((idx = tracer.header ("cond_expr evaluation : ")))
1520 : : {
1521 : 0 : fprintf (dump_file, " range1 = ");
1522 : 0 : r1.dump (dump_file);
1523 : 0 : fprintf (dump_file, ", range2 = ");
1524 : 0 : r1.dump (dump_file);
1525 : 0 : fprintf (dump_file, "\n");
1526 : : }
1527 : :
1528 : : // Now solve for SSA1 or SSA2 if they are in the dependency chain.
1529 : 14692 : if (ssa1 && in_chain_p (ssa1, cond_name))
1530 : : {
1531 : 310 : Value_Range tmp1 (TREE_TYPE (ssa1));
1532 : 310 : if (compute_operand_range (tmp1, def_stmt, cond_true, ssa1, src))
1533 : 310 : r1.intersect (tmp1);
1534 : 310 : }
1535 : 14692 : if (ssa2 && in_chain_p (ssa2, cond_name))
1536 : : {
1537 : 30 : Value_Range tmp2 (TREE_TYPE (ssa2));
1538 : 30 : if (compute_operand_range (tmp2, def_stmt, cond_false, ssa2, src))
1539 : 26 : r2.intersect (tmp2);
1540 : 30 : }
1541 : 14692 : if (idx)
1542 : : {
1543 : 0 : tracer.print (idx, "outgoing: range1 = ");
1544 : 0 : r1.dump (dump_file);
1545 : 0 : fprintf (dump_file, ", range2 = ");
1546 : 0 : r1.dump (dump_file);
1547 : 0 : fprintf (dump_file, "\n");
1548 : 0 : tracer.trailer (idx, "cond_expr", true, cond_name, cond_true);
1549 : : }
1550 : : return true;
1551 : 14692 : }
1552 : :
1553 : : // Dump what is known to GORI computes to listing file F.
1554 : :
1555 : : void
1556 : 0 : gori_compute::dump (FILE *f)
1557 : : {
1558 : 0 : gori_map::dump (f);
1559 : 0 : }
1560 : :
1561 : : // ------------------------------------------------------------------------
1562 : : // GORI iterator. Although we have bitmap iterators, don't expose that it
1563 : : // is currently a bitmap. Use an export iterator to hide future changes.
1564 : :
1565 : : // Construct a basic iterator over an export bitmap.
1566 : :
1567 : 65816205 : gori_export_iterator::gori_export_iterator (bitmap b)
1568 : : {
1569 : 65816205 : bm = b;
1570 : 65816205 : if (b)
1571 : 65816205 : bmp_iter_set_init (&bi, b, 1, &y);
1572 : 65816205 : }
1573 : :
1574 : :
1575 : : // Move to the next export bitmap spot.
1576 : :
1577 : : void
1578 : 136250601 : gori_export_iterator::next ()
1579 : : {
1580 : 136250601 : bmp_iter_next (&bi, &y);
1581 : 136250601 : }
1582 : :
1583 : :
1584 : : // Fetch the name of the next export in the export list. Return NULL if
1585 : : // iteration is done.
1586 : :
1587 : : tree
1588 : 202066159 : gori_export_iterator::get_name ()
1589 : : {
1590 : 202066159 : if (!bm)
1591 : : return NULL_TREE;
1592 : :
1593 : 202066806 : while (bmp_iter_set (&bi, &y))
1594 : : {
1595 : 136336562 : tree t = ssa_name (y);
1596 : 136336562 : if (t)
1597 : 136335915 : return t;
1598 : 647 : next ();
1599 : : }
1600 : : return NULL_TREE;
1601 : : }
1602 : :
1603 : : // This is a helper class to set up STMT with a known LHS for further GORI
1604 : : // processing.
1605 : :
1606 : 0 : class gori_stmt_info : public gimple_range_op_handler
1607 : : {
1608 : : public:
1609 : : gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q);
1610 : : Value_Range op1_range;
1611 : : Value_Range op2_range;
1612 : : tree ssa1;
1613 : : tree ssa2;
1614 : : };
1615 : :
1616 : :
1617 : : // Uses query Q to get the known ranges on STMT with a LHS range
1618 : : // for op1_range and op2_range and set ssa1 and ssa2 if either or both of
1619 : : // those operands are SSA_NAMES.
1620 : :
1621 : 0 : gori_stmt_info::gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q)
1622 : 0 : : gimple_range_op_handler (stmt)
1623 : : {
1624 : 0 : ssa1 = NULL;
1625 : 0 : ssa2 = NULL;
1626 : : // Don't handle switches as yet for vector processing.
1627 : 0 : if (is_a<gswitch *> (stmt))
1628 : : return;
1629 : :
1630 : : // No frther processing for VARYING or undefined.
1631 : 0 : if (lhs.undefined_p () || lhs.varying_p ())
1632 : : return;
1633 : :
1634 : : // If there is no range-op handler, we are also done.
1635 : 0 : if (!*this)
1636 : : return;
1637 : :
1638 : : // Only evaluate logical cases if both operands must be the same as the LHS.
1639 : : // Otherwise its becomes exponential in time, as well as more complicated.
1640 : 0 : if (is_gimple_logical_p (stmt))
1641 : : {
1642 : 0 : gcc_checking_assert (range_compatible_p (lhs.type (), boolean_type_node));
1643 : 0 : enum tree_code code = gimple_expr_code (stmt);
1644 : 0 : if (code == TRUTH_OR_EXPR || code == BIT_IOR_EXPR)
1645 : : {
1646 : : // [0, 0] = x || y means both x and y must be zero.
1647 : 0 : if (!lhs.singleton_p () || !lhs.zero_p ())
1648 : 0 : return;
1649 : : }
1650 : 0 : else if (code == TRUTH_AND_EXPR || code == BIT_AND_EXPR)
1651 : : {
1652 : : // [1, 1] = x && y means both x and y must be one.
1653 : 0 : if (!lhs.singleton_p () || lhs.zero_p ())
1654 : 0 : return;
1655 : : }
1656 : : }
1657 : :
1658 : 0 : tree op1 = operand1 ();
1659 : 0 : tree op2 = operand2 ();
1660 : 0 : ssa1 = gimple_range_ssa_p (op1);
1661 : 0 : ssa2 = gimple_range_ssa_p (op2);
1662 : : // If both operands are the same, only process one of them.
1663 : 0 : if (ssa1 && ssa1 == ssa2)
1664 : 0 : ssa2 = NULL_TREE;
1665 : :
1666 : : // Extract current ranges for the operands.
1667 : 0 : fur_stmt src (stmt, q);
1668 : 0 : if (op1)
1669 : : {
1670 : 0 : op1_range.set_type (TREE_TYPE (op1));
1671 : 0 : src.get_operand (op1_range, op1);
1672 : : }
1673 : :
1674 : : // And satisfy the second operand for single op satements.
1675 : 0 : if (op2)
1676 : : {
1677 : 0 : op2_range.set_type (TREE_TYPE (op2));
1678 : 0 : src.get_operand (op2_range, op2);
1679 : : }
1680 : 0 : else if (op1)
1681 : 0 : op2_range = op1_range;
1682 : : return;
1683 : : }
1684 : :
1685 : :
1686 : : // Process STMT using LHS as the range of the LHS. Invoke GORI processing
1687 : : // to resolve ranges for all SSA_NAMES feeding STMT which may be altered
1688 : : // based on LHS. Fill R with the results, and resolve all incoming
1689 : : // ranges using range-query Q.
1690 : :
1691 : : static void
1692 : 0 : gori_calc_operands (vrange &lhs, gimple *stmt, ssa_cache &r, range_query *q)
1693 : : {
1694 : 0 : struct gori_stmt_info si(lhs, stmt, q);
1695 : 0 : if (!si)
1696 : 0 : return;
1697 : :
1698 : 0 : Value_Range tmp;
1699 : : // Now evaluate operand ranges, and set them in the edge cache.
1700 : : // If there was already a range, leave it and do no further evaluation.
1701 : 0 : if (si.ssa1 && !r.has_range (si.ssa1))
1702 : : {
1703 : 0 : tmp.set_type (TREE_TYPE (si.ssa1));
1704 : 0 : if (si.calc_op1 (tmp, lhs, si.op2_range))
1705 : 0 : si.op1_range.intersect (tmp);
1706 : 0 : r.set_range (si.ssa1, si.op1_range);
1707 : 0 : gimple *src = SSA_NAME_DEF_STMT (si.ssa1);
1708 : : // If defintion is in the same basic lock, evaluate it.
1709 : 0 : if (src && gimple_bb (src) == gimple_bb (stmt))
1710 : 0 : gori_calc_operands (si.op1_range, src, r, q);
1711 : : }
1712 : :
1713 : 0 : if (si.ssa2 && !r.has_range (si.ssa2))
1714 : : {
1715 : 0 : tmp.set_type (TREE_TYPE (si.ssa2));
1716 : 0 : if (si.calc_op2 (tmp, lhs, si.op1_range))
1717 : 0 : si.op2_range.intersect (tmp);
1718 : 0 : r.set_range (si.ssa2, si.op2_range);
1719 : 0 : gimple *src = SSA_NAME_DEF_STMT (si.ssa2);
1720 : 0 : if (src && gimple_bb (src) == gimple_bb (stmt))
1721 : 0 : gori_calc_operands (si.op2_range, src, r, q);
1722 : : }
1723 : 0 : }
1724 : :
1725 : : // Use ssa_cache R as a repository for all outgoing ranges on edge E that
1726 : : // can be calculated. Use OGR if present to establish starting edge ranges,
1727 : : // and Q to resolve operand values. If Q is NULL use the current range
1728 : : // query available to the system.
1729 : :
1730 : : bool
1731 : 0 : gori_on_edge (ssa_cache &r, edge e, range_query *q, gimple_outgoing_range *ogr)
1732 : : {
1733 : : // Start with an empty vector
1734 : 0 : r.clear ();
1735 : 0 : int_range_max lhs;
1736 : : // Determine if there is an outgoing edge.
1737 : 0 : gimple *stmt;
1738 : 0 : if (ogr)
1739 : 0 : stmt = ogr->edge_range_p (lhs, e);
1740 : : else
1741 : : {
1742 : 0 : stmt = gimple_outgoing_range_stmt_p (e->src);
1743 : 0 : if (stmt && is_a<gcond *> (stmt))
1744 : 0 : gcond_edge_range (lhs, e);
1745 : : else
1746 : : stmt = NULL;
1747 : : }
1748 : 0 : if (!stmt)
1749 : 0 : return false;
1750 : 0 : gori_calc_operands (lhs, stmt, r, q);
1751 : 0 : return true;
1752 : 0 : }
1753 : :
1754 : : // Helper for GORI_NAME_ON_EDGE which uses query Q to determine if STMT
1755 : : // provides a range for NAME, and returns it in R if so. If it does not,
1756 : : // continue processing feeding statments until we run out of statements
1757 : : // or fine a range for NAME.
1758 : :
1759 : : bool
1760 : 0 : gori_name_helper (vrange &r, tree name, vrange &lhs, gimple *stmt,
1761 : : range_query *q)
1762 : : {
1763 : 0 : struct gori_stmt_info si(lhs, stmt, q);
1764 : 0 : if (!si)
1765 : : return false;
1766 : :
1767 : 0 : if (si.ssa1 == name)
1768 : 0 : return si.calc_op1 (r, lhs, si.op2_range);
1769 : 0 : if (si.ssa2 == name)
1770 : 0 : return si.calc_op2 (r, lhs, si.op1_range);
1771 : :
1772 : 0 : Value_Range tmp;
1773 : : // Now evaluate operand ranges, and set them in the edge cache.
1774 : : // If there was already a range, leave it and do no further evaluation.
1775 : 0 : if (si.ssa1)
1776 : : {
1777 : 0 : tmp.set_type (TREE_TYPE (si.ssa1));
1778 : 0 : if (si.calc_op1 (tmp, lhs, si.op2_range))
1779 : 0 : si.op1_range.intersect (tmp);
1780 : 0 : gimple *src = SSA_NAME_DEF_STMT (si.ssa1);
1781 : : // If defintion is in the same basic lock, evaluate it.
1782 : 0 : if (src && gimple_bb (src) == gimple_bb (stmt))
1783 : 0 : if (gori_name_helper (r, name, si.op1_range, src, q))
1784 : : return true;
1785 : : }
1786 : :
1787 : 0 : if (si.ssa2)
1788 : : {
1789 : 0 : tmp.set_type (TREE_TYPE (si.ssa2));
1790 : 0 : if (si.calc_op2 (tmp, lhs, si.op1_range))
1791 : 0 : si.op2_range.intersect (tmp);
1792 : 0 : gimple *src = SSA_NAME_DEF_STMT (si.ssa2);
1793 : 0 : if (src && gimple_bb (src) == gimple_bb (stmt))
1794 : 0 : if (gori_name_helper (r, name, si.op2_range, src, q))
1795 : : return true;
1796 : : }
1797 : : return false;
1798 : 0 : }
1799 : :
1800 : : // Check if NAME has an outgoing range on edge E. Use query Q to evaluate
1801 : : // the operands. Return TRUE and the range in R if there is an outgoing range.
1802 : : // This is like gori_on_edge except it only looks for the single name and
1803 : : // does not require an ssa_cache.
1804 : :
1805 : : bool
1806 : 0 : gori_name_on_edge (vrange &r, tree name, edge e, range_query *q)
1807 : : {
1808 : 0 : int_range_max lhs;
1809 : 0 : gimple *stmt = gimple_outgoing_range_stmt_p (e->src);
1810 : 0 : if (!stmt || !is_a<gcond *> (stmt))
1811 : : return false;
1812 : 0 : gcond_edge_range (lhs, e);
1813 : 0 : return gori_name_helper (r, name, lhs, stmt, q);
1814 : 0 : }
|
