Line data Source code
1 : /* Gimple range GORI functions.
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
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 44990538 : is_gimple_logical_p (const gimple *gs)
36 : {
37 : // Look for boolean and/or condition.
38 44990538 : if (is_gimple_assign (gs))
39 17300356 : switch (gimple_expr_code (gs))
40 : {
41 : case TRUTH_AND_EXPR:
42 : case TRUTH_OR_EXPR:
43 : return true;
44 :
45 4505132 : case BIT_AND_EXPR:
46 4505132 : case BIT_IOR_EXPR:
47 : // Bitwise operations on single bits are logical too.
48 4505132 : 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 27881050 : range_def_chain::range_def_chain ()
97 : {
98 27881050 : bitmap_obstack_initialize (&m_bitmaps);
99 27881050 : m_def_chain.create (0);
100 55762100 : m_def_chain.safe_grow_cleared (num_ssa_names);
101 27881050 : m_logical_depth = 0;
102 27881050 : }
103 :
104 : // Destruct a range_def_chain.
105 :
106 27881049 : range_def_chain::~range_def_chain ()
107 : {
108 27881049 : m_def_chain.release ();
109 27881049 : bitmap_obstack_release (&m_bitmaps);
110 27881049 : }
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 135711024 : range_def_chain::in_chain_p (tree name, tree def)
117 : {
118 135711024 : gcc_checking_assert (gimple_range_ssa_p (def));
119 135711024 : gcc_checking_assert (gimple_range_ssa_p (name));
120 :
121 : // Get the definition chain for DEF.
122 135711024 : bitmap chain = get_def_chain (def);
123 :
124 135711024 : if (chain == NULL)
125 : return false;
126 99400368 : 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 305865536 : range_def_chain::set_import (struct rdc &data, tree imp, bitmap b)
133 : {
134 : // If there are no imports, just return
135 305865536 : if (imp == NULL_TREE && !b)
136 : return;
137 305692397 : if (!data.m_import)
138 143391457 : data.m_import = BITMAP_ALLOC (&m_bitmaps);
139 305692397 : if (imp != NULL_TREE)
140 264831068 : bitmap_set_bit (data.m_import, SSA_NAME_VERSION (imp));
141 : else
142 40861329 : bitmap_ior_into (data.m_import, b);
143 : }
144 :
145 : // Return the import list for NAME.
146 :
147 : bitmap
148 166795347 : range_def_chain::get_imports (tree name)
149 : {
150 166795347 : if (!has_def_chain (name))
151 100161872 : get_def_chain (name);
152 166795347 : bitmap i = m_def_chain[SSA_NAME_VERSION (name)].m_import;
153 166795347 : return i;
154 : }
155 :
156 : // Return true if IMPORT is an import to NAMEs def chain.
157 :
158 : bool
159 4556698 : range_def_chain::chain_import_p (tree name, tree import)
160 : {
161 4556698 : bitmap b = get_imports (name);
162 4556698 : if (b)
163 4552060 : 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 248287025 : range_def_chain::register_dependency (tree name, tree dep, basic_block bb)
171 : {
172 248287025 : if (!gimple_range_ssa_p (dep))
173 : return;
174 :
175 210126965 : unsigned v = SSA_NAME_VERSION (name);
176 210126965 : if (v >= m_def_chain.length ())
177 2458 : m_def_chain.safe_grow_cleared (num_ssa_names + 1);
178 210126965 : struct rdc &src = m_def_chain[v];
179 210126965 : gimple *def_stmt = SSA_NAME_DEF_STMT (dep);
180 210126965 : unsigned dep_v = SSA_NAME_VERSION (dep);
181 210126965 : bitmap b;
182 :
183 : // Set the direct dependency cache entries.
184 210126965 : if (!src.ssa1)
185 111811666 : src.ssa1 = SSA_NAME_VERSION (dep);
186 98315299 : else if (!src.ssa2 && src.ssa1 != SSA_NAME_VERSION (dep))
187 32998300 : 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 210126965 : if (!bb)
193 : return;
194 :
195 69147435 : if (!src.bm)
196 55442250 : src.bm = BITMAP_ALLOC (&m_bitmaps);
197 :
198 : // Add this operand into the result.
199 69147435 : bitmap_set_bit (src.bm, dep_v);
200 :
201 69147435 : if (gimple_bb (def_stmt) == bb && !is_a<gphi *>(def_stmt))
202 : {
203 : // Get the def chain for the operand.
204 41034468 : 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 41034468 : if (b)
208 24408377 : bitmap_ior_into (m_def_chain[v].bm, b);
209 : // And copy the import list.
210 41034468 : 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 28112967 : 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 121204051 : range_def_chain::add_def_chain_to_bitmap (bitmap b, tree name)
228 : {
229 121204051 : bitmap r = get_def_chain (name);
230 121204051 : if (r)
231 37668013 : bitmap_ior_into (b, r);
232 121204051 : }
233 :
234 :
235 : // Return TRUE if NAME has been processed for a def_chain.
236 :
237 : inline bool
238 565257166 : range_def_chain::has_def_chain (tree name)
239 : {
240 : // Ensure there is an entry in the internal vector.
241 565257166 : unsigned v = SSA_NAME_VERSION (name);
242 565257166 : if (v >= m_def_chain.length ())
243 244 : m_def_chain.safe_grow_cleared (num_ssa_names + 1);
244 565257166 : 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 398461567 : range_def_chain::get_def_chain (tree name)
256 : {
257 398461567 : tree ssa[3];
258 398461567 : unsigned v = SSA_NAME_VERSION (name);
259 :
260 : // If it has already been processed, just return the cached value.
261 398461567 : 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 292349590 : if (SSA_NAME_IS_DEFAULT_DEF (name))
266 : {
267 : // A Default def is always an import.
268 14948126 : set_import (m_def_chain[v], name, NULL);
269 14948126 : return NULL;
270 : }
271 :
272 277401464 : gimple *stmt = SSA_NAME_DEF_STMT (name);
273 277401464 : unsigned count = gimple_range_ssa_names (ssa, 3, stmt);
274 277401464 : if (count == 0)
275 : {
276 : // Stmts not understood or with no operands are always imports.
277 221769975 : set_import (m_def_chain[v], name, NULL);
278 221769975 : return NULL;
279 : }
280 :
281 : // Terminate the def chains if we see too many cascading stmts.
282 55631489 : 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 55442254 : if (count > 1)
287 13680172 : m_logical_depth++;
288 :
289 124589693 : for (unsigned x = 0; x < count; x++)
290 69147439 : register_dependency (name, ssa[x], gimple_bb (stmt));
291 :
292 55442254 : if (count > 1)
293 13680172 : m_logical_depth--;
294 :
295 55442254 : return m_def_chain[v].bm;
296 : }
297 :
298 : // Dump what we know for basic block BB to file F.
299 :
300 : void
301 115 : range_def_chain::dump (FILE *f, basic_block bb, const char *prefix)
302 : {
303 115 : unsigned x, y;
304 115 : bitmap_iterator bi;
305 :
306 : // Dump the def chain for each SSA_NAME defined in BB.
307 8363 : for (x = 1; x < num_ssa_names; x++)
308 : {
309 8248 : tree name = ssa_name (x);
310 8248 : if (!name)
311 3737 : continue;
312 4511 : gimple *stmt = SSA_NAME_DEF_STMT (name);
313 4511 : if (!stmt || (bb && gimple_bb (stmt) != bb))
314 4259 : continue;
315 252 : bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL);
316 148 : if (chain && !bitmap_empty_p (chain))
317 : {
318 130 : fprintf (f, prefix);
319 130 : print_generic_expr (f, name, TDF_SLIM);
320 130 : fprintf (f, " : ");
321 :
322 130 : bitmap imports = get_imports (name);
323 457 : EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi)
324 : {
325 327 : print_generic_expr (f, ssa_name (y), TDF_SLIM);
326 327 : if (imports && bitmap_bit_p (imports, y))
327 159 : fprintf (f, "(I)");
328 327 : fprintf (f, " ");
329 : }
330 130 : fprintf (f, "\n");
331 : }
332 : }
333 115 : }
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 27881050 : gori_map::gori_map ()
360 : {
361 27881050 : m_outgoing.create (0);
362 27881050 : m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
363 27881050 : m_incoming.create (0);
364 27881050 : m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
365 27881050 : m_maybe_variant = BITMAP_ALLOC (&m_bitmaps);
366 27881050 : }
367 :
368 : // Free any memory the GORI map allocated.
369 :
370 27881049 : gori_map::~gori_map ()
371 : {
372 27881049 : m_incoming.release ();
373 27881049 : m_outgoing.release ();
374 27881049 : }
375 :
376 : // Return the bitmap vector of all export from BB. Calculate if necessary.
377 :
378 : bitmap
379 1390438903 : gori_map::exports (basic_block bb)
380 : {
381 2780877806 : if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
382 311436755 : calculate_gori (bb);
383 1390438903 : return m_outgoing[bb->index];
384 : }
385 :
386 : // Return the bitmap vector of all exports AND their dependencies from BB
387 : // in TMPBIT. Calculate if necessary. Return TMPBIT.
388 :
389 : bitmap
390 230710 : gori_map::exports_and_deps (basic_block bb, bitmap tmpbit)
391 : {
392 461420 : if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
393 0 : calculate_gori (bb);
394 230710 : bitmap_copy (tmpbit, m_outgoing[bb->index]);
395 230710 : if (!bitmap_empty_p (tmpbit))
396 : {
397 230710 : tree name;
398 580714 : FOR_EACH_GORI_EXPORT_NAME (this, bb, name)
399 : {
400 350004 : bitmap dep = get_def_chain (name);
401 350004 : if (dep)
402 77339 : bitmap_ior_into (tmpbit, dep);
403 : }
404 : }
405 230710 : return tmpbit;
406 : }
407 :
408 : // Return the bitmap vector of all imports to BB. Calculate if necessary.
409 :
410 : bitmap
411 9470620 : gori_map::imports (basic_block bb)
412 : {
413 18941240 : if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
414 0 : calculate_gori (bb);
415 9470620 : return m_incoming[bb->index];
416 : }
417 :
418 : // Return true if NAME is can have ranges generated for it from basic
419 : // block BB.
420 :
421 : bool
422 1632633603 : gori_map::is_export_p (tree name, basic_block bb)
423 : {
424 : // If no BB is specified, test if it is exported anywhere in the IL.
425 1632633603 : if (!bb)
426 694789387 : return bitmap_bit_p (m_maybe_variant, SSA_NAME_VERSION (name));
427 937844216 : return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name));
428 : }
429 :
430 : // Set or clear the m_maybe_variant bit to determine if ranges will be tracked
431 : // for NAME. A clear bit means they will NOT be tracked.
432 :
433 : void
434 6392087 : gori_map::set_range_invariant (tree name, bool invariant)
435 : {
436 6392087 : if (invariant)
437 2335497 : bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name));
438 : else
439 4056590 : bitmap_set_bit (m_maybe_variant, SSA_NAME_VERSION (name));
440 6392087 : }
441 :
442 : // Return true if NAME is an import to block BB.
443 :
444 : bool
445 0 : gori_map::is_import_p (tree name, basic_block bb)
446 : {
447 : // If no BB is specified, test if it is exported anywhere in the IL.
448 0 : return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name));
449 : }
450 :
451 : // If NAME is non-NULL and defined in block BB, calculate the def
452 : // chain and add it to m_outgoing.
453 :
454 : void
455 196798021 : gori_map::maybe_add_gori (tree name, basic_block bb)
456 : {
457 196798021 : if (name)
458 : {
459 : // Check if there is a def chain, regardless of the block.
460 121204051 : add_def_chain_to_bitmap (m_outgoing[bb->index], name);
461 : // Check for any imports.
462 121204051 : bitmap imp = get_imports (name);
463 : // If there were imports, add them so we can recompute
464 121204051 : if (imp)
465 121202673 : bitmap_ior_into (m_incoming[bb->index], imp);
466 : // This name is always an import.
467 121204051 : if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb)
468 31017207 : bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name));
469 :
470 : // Def chain doesn't include itself, and even if there isn't a
471 : // def chain, this name should be added to exports.
472 121204051 : bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name));
473 : }
474 196798021 : }
475 :
476 : // Calculate all the required information for BB.
477 :
478 : void
479 311436755 : gori_map::calculate_gori (basic_block bb)
480 : {
481 311436755 : tree name;
482 622873510 : if (bb->index >= (signed int)m_outgoing.length ())
483 : {
484 942 : m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
485 942 : m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
486 : }
487 311436755 : gcc_checking_assert (m_outgoing[bb->index] == NULL);
488 311436755 : m_outgoing[bb->index] = BITMAP_ALLOC (&m_bitmaps);
489 311436755 : m_incoming[bb->index] = BITMAP_ALLOC (&m_bitmaps);
490 :
491 311436755 : if (single_succ_p (bb))
492 : return;
493 :
494 : // If this block's last statement may generate range information, go
495 : // calculate it.
496 162396058 : gimple *stmt = gimple_outgoing_range_stmt_p (bb);
497 162396058 : if (!stmt)
498 : return;
499 98633903 : if (is_a<gcond *> (stmt))
500 : {
501 98165453 : gcond *gc = as_a<gcond *>(stmt);
502 98165453 : name = gimple_range_ssa_p (gimple_cond_lhs (gc));
503 98165453 : maybe_add_gori (name, gimple_bb (stmt));
504 :
505 98165453 : name = gimple_range_ssa_p (gimple_cond_rhs (gc));
506 98165453 : maybe_add_gori (name, gimple_bb (stmt));
507 : }
508 : else
509 : {
510 : // Do not process switches if they are too large.
511 468450 : if (EDGE_COUNT (bb->succs) > (unsigned)param_vrp_switch_limit)
512 : return;
513 467115 : gswitch *gs = as_a<gswitch *>(stmt);
514 467115 : name = gimple_range_ssa_p (gimple_switch_index (gs));
515 467115 : maybe_add_gori (name, gimple_bb (stmt));
516 : }
517 : // Add this bitmap to the aggregate list of all outgoing names.
518 98632568 : bitmap_ior_into (m_maybe_variant, m_outgoing[bb->index]);
519 : }
520 :
521 : // Dump the table information for BB to file F.
522 :
523 : void
524 248 : gori_map::dump (FILE *f, basic_block bb, bool verbose)
525 : {
526 : // BB was not processed.
527 248 : if (!m_outgoing[bb->index] || bitmap_empty_p (m_outgoing[bb->index]))
528 : return;
529 :
530 115 : tree name;
531 :
532 115 : bitmap imp = imports (bb);
533 115 : if (!bitmap_empty_p (imp))
534 : {
535 115 : if (verbose)
536 0 : fprintf (f, "bb<%u> Imports: ",bb->index);
537 : else
538 115 : fprintf (f, "Imports: ");
539 275 : FOR_EACH_GORI_IMPORT_NAME (this, bb, name)
540 : {
541 160 : print_generic_expr (f, name, TDF_SLIM);
542 160 : fprintf (f, " ");
543 : }
544 115 : fputc ('\n', f);
545 : }
546 :
547 115 : if (verbose)
548 0 : fprintf (f, "bb<%u> Exports: ",bb->index);
549 : else
550 115 : fprintf (f, "Exports: ");
551 : // Dump the export vector.
552 384 : FOR_EACH_GORI_EXPORT_NAME (this, bb, name)
553 : {
554 269 : print_generic_expr (f, name, TDF_SLIM);
555 269 : fprintf (f, " ");
556 : }
557 115 : fputc ('\n', f);
558 :
559 115 : range_def_chain::dump (f, bb, " ");
560 : }
561 :
562 : // Dump the entire GORI map structure to file F.
563 :
564 : void
565 0 : gori_map::dump (FILE *f)
566 : {
567 0 : basic_block bb;
568 0 : FOR_EACH_BB_FN (bb, cfun)
569 0 : dump (f, bb);
570 0 : }
571 :
572 : DEBUG_FUNCTION void
573 0 : debug (gori_map &g)
574 : {
575 0 : g.dump (stderr);
576 0 : }
577 :
578 : // -------------------------------------------------------------------
579 :
580 : // Construct a gori_compute object.
581 :
582 27881050 : gori_compute::gori_compute (gori_map &map, int not_executable_flag,
583 27881050 : int sw_max_edges)
584 27881050 : : gimple_outgoing_range (sw_max_edges), m_map (map), tracer ("GORI ")
585 : {
586 27881050 : m_not_executable_flag = not_executable_flag;
587 : // Create a boolean_type true and false range.
588 27881050 : m_bool_zero = range_false ();
589 27881050 : m_bool_one = range_true ();
590 27881050 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_GORI))
591 0 : tracer.enable_trace ();
592 :
593 : // Reduce maximum recompute depth based on the size of the CFG to avoid
594 : // excessive compuations in large CFGs.
595 27881050 : m_recompute_depth = (int) param_ranger_recompute_depth
596 27881050 : - (int) last_basic_block_for_fn (cfun) / 4096;
597 27881050 : if (m_recompute_depth < 1)
598 0 : m_recompute_depth = 1;
599 27881050 : }
600 :
601 55762098 : gori_compute::~gori_compute ()
602 : {
603 55762098 : }
604 :
605 : // Given the switch S, return an evaluation in R for NAME when the lhs
606 : // evaluates to LHS. Returning false means the name being looked for
607 : // was not resolvable.
608 :
609 : bool
610 155041 : gori_compute::compute_operand_range_switch (vrange &r, gswitch *s,
611 : const vrange &lhs,
612 : tree name, fur_source &src)
613 : {
614 155041 : tree op1 = gimple_switch_index (s);
615 :
616 : // If name matches, the range is simply the range from the edge.
617 : // Empty ranges are viral as they are on a path which isn't
618 : // executable.
619 155041 : if (op1 == name || lhs.undefined_p ())
620 : {
621 112301 : r = lhs;
622 112301 : return true;
623 : }
624 :
625 : // If op1 is in the definition chain, pass lhs back.
626 42740 : if (gimple_range_ssa_p (op1) && m_map.in_chain_p (name, op1))
627 42650 : return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name, src);
628 :
629 : return false;
630 : }
631 :
632 :
633 : // Return an evaluation for NAME as it would appear in STMT when the
634 : // statement's lhs evaluates to LHS. If successful, return TRUE and
635 : // store the evaluation in R, otherwise return FALSE.
636 :
637 : bool
638 124848362 : gori_compute::compute_operand_range (vrange &r, gimple *stmt,
639 : const vrange &lhs, tree name,
640 : fur_source &src, value_relation *rel)
641 : {
642 124848362 : value_relation vrel;
643 124848362 : value_relation *vrel_ptr = rel;
644 : // Empty ranges are viral as they are on an unexecutable path.
645 124848362 : if (lhs.undefined_p ())
646 : {
647 73673 : r.set_undefined ();
648 73673 : return true;
649 : }
650 124774689 : if (is_a<gswitch *> (stmt))
651 155041 : return compute_operand_range_switch (r, as_a<gswitch *> (stmt), lhs, name,
652 155041 : src);
653 124619648 : gimple_range_op_handler handler (stmt);
654 124619648 : if (!handler)
655 : return false;
656 :
657 124445852 : tree op1 = gimple_range_ssa_p (handler.operand1 ());
658 124445852 : tree op2 = gimple_range_ssa_p (handler.operand2 ());
659 :
660 : // If there is a relation betwen op1 and op2, use it instead as it is
661 : // likely to be more applicable.
662 124445852 : if (op1 && op2)
663 : {
664 54601696 : value_range r1, r2;
665 54601696 : r1.set_varying (TREE_TYPE (op1));
666 54601696 : r2.set_varying (TREE_TYPE (op2));
667 54601696 : relation_kind k = handler.op1_op2_relation (lhs, r1, r2);
668 54601696 : if (k != VREL_VARYING)
669 : {
670 38663211 : vrel.set_relation (k, op1, op2);
671 38663211 : vrel_ptr = &vrel;
672 : }
673 54601696 : }
674 :
675 : // Handle end of lookup first.
676 124445852 : if (op1 == name)
677 59608632 : return compute_operand1_range (r, handler, lhs, src, vrel_ptr);
678 64837220 : if (op2 == name)
679 17356212 : return compute_operand2_range (r, handler, lhs, src, vrel_ptr);
680 :
681 : // NAME is not in this stmt, but one of the names in it ought to be
682 : // derived from it.
683 47481008 : bool op1_in_chain = op1 && m_map.in_chain_p (name, op1);
684 47481008 : bool op2_in_chain = op2 && m_map.in_chain_p (name, op2);
685 :
686 : // If neither operand is derived, then this stmt tells us nothing.
687 35506979 : if (!op1_in_chain && !op2_in_chain)
688 : return false;
689 :
690 : // If either operand is in the def chain of the other (or they are equal), it
691 : // will be evaluated twice and can result in an exponential time calculation.
692 : // Instead just evaluate the one operand.
693 46598475 : if (op1_in_chain && op2_in_chain)
694 : {
695 1971619 : if (m_map.in_chain_p (op1, op2) || op1 == op2)
696 : op1_in_chain = false;
697 1694838 : else if (m_map.in_chain_p (op2, op1))
698 61395 : op2_in_chain = false;
699 : }
700 :
701 46598475 : bool res = false;
702 : // If the lhs doesn't tell us anything only a relation can possibly enhance
703 : // the result.
704 46598475 : if (lhs.varying_p ())
705 : {
706 1694734 : if (!vrel_ptr)
707 : return false;
708 : // If there is a relation (ie: x != y) , it can only be relevant if
709 : // a) both elements are in the defchain
710 : // c = x > y // (x and y are in c's defchain)
711 1414386 : if (op1_in_chain)
712 1038560 : res = m_map.in_chain_p (vrel_ptr->op1 (), op1)
713 1038560 : && m_map.in_chain_p (vrel_ptr->op2 (), op1);
714 1414386 : if (!res && op2_in_chain)
715 413371 : res = m_map.in_chain_p (vrel_ptr->op1 (), op2)
716 413371 : || m_map.in_chain_p (vrel_ptr->op2 (), op2);
717 1001015 : if (!res)
718 : {
719 : // or b) one relation element is in the defchain of the other and the
720 : // other is the LHS of this stmt.
721 : // x = y + 2
722 1411094 : if (vrel_ptr->op1 () == handler.lhs ()
723 1411094 : && (vrel_ptr->op2 () == op1 || vrel_ptr->op2 () == op2))
724 : res = true;
725 1375815 : else if (vrel_ptr->op2 () == handler.lhs ()
726 1375815 : && (vrel_ptr->op1 () == op1 || vrel_ptr->op1 () == op2))
727 : res = true;
728 : }
729 : if (!res)
730 : return false;
731 : }
732 :
733 : // Process logicals as they have special handling.
734 44990490 : if (is_gimple_logical_p (stmt))
735 : {
736 : // If the lhs doesn't tell us anything, neither will combining operands.
737 3364802 : if (lhs.varying_p ())
738 : return false;
739 :
740 3364802 : unsigned idx;
741 3364802 : if ((idx = tracer.header ("compute_operand ")))
742 : {
743 0 : print_generic_expr (dump_file, name, TDF_SLIM);
744 0 : fprintf (dump_file, " with LHS = ");
745 0 : lhs.dump (dump_file);
746 0 : fprintf (dump_file, " at stmt ");
747 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
748 : }
749 :
750 3364802 : tree type = TREE_TYPE (name);
751 3364802 : value_range op1_trange (type), op1_frange (type);
752 3364802 : value_range op2_trange (type), op2_frange (type);
753 3364802 : compute_logical_operands (op1_trange, op1_frange, handler,
754 : as_a <irange> (lhs),
755 : name, src, op1, op1_in_chain);
756 3364802 : compute_logical_operands (op2_trange, op2_frange, handler,
757 : as_a <irange> (lhs),
758 : name, src, op2, op2_in_chain);
759 3364802 : res = logical_combine (r,
760 : gimple_expr_code (stmt),
761 : as_a <irange> (lhs),
762 3364802 : op1_trange, op1_frange, op2_trange, op2_frange);
763 3364802 : if (idx)
764 0 : tracer.trailer (idx, "compute_operand", res, name, r);
765 3364802 : return res;
766 3364802 : }
767 : // Follow the appropriate operands now.
768 41625688 : if (op1_in_chain && op2_in_chain)
769 404555 : return compute_operand1_and_operand2_range (r, handler, lhs, name, src,
770 404555 : vrel_ptr);
771 41221133 : value_range vr;
772 41221133 : gimple *src_stmt;
773 41221133 : if (op1_in_chain)
774 : {
775 32520948 : vr.set_type (TREE_TYPE (op1));
776 32520948 : if (!compute_operand1_range (vr, handler, lhs, src, vrel_ptr))
777 : return false;
778 31357883 : src_stmt = SSA_NAME_DEF_STMT (op1);
779 : }
780 : else
781 : {
782 8700185 : gcc_checking_assert (op2_in_chain);
783 8700185 : vr.set_type (TREE_TYPE (op2));
784 8700185 : if (!compute_operand2_range (vr, handler, lhs, src, vrel_ptr))
785 : return false;
786 8291488 : src_stmt = SSA_NAME_DEF_STMT (op2);
787 : }
788 :
789 39649371 : gcc_checking_assert (src_stmt);
790 : // Then feed this range back as the LHS of the defining statement.
791 39649371 : return compute_operand_range (r, src_stmt, vr, name, src, vrel_ptr);
792 : // If neither operand is derived, this statement tells us nothing.
793 41221133 : }
794 :
795 :
796 : // Return TRUE if range R is either a true or false compatible range.
797 :
798 : static bool
799 2775389 : range_is_either_true_or_false (const irange &r)
800 : {
801 2775389 : if (r.undefined_p ())
802 : return false;
803 :
804 : // This is complicated by the fact that Ada has multi-bit booleans,
805 : // so true can be ~[0, 0] (i.e. [1,MAX]).
806 2775389 : tree type = r.type ();
807 2775389 : gcc_checking_assert (range_compatible_p (type, boolean_type_node));
808 2775389 : return (r.singleton_p ()
809 2775389 : || !r.contains_p (wi::zero (TYPE_PRECISION (type))));
810 : }
811 :
812 : // Evaluate a binary logical expression by combining the true and
813 : // false ranges for each of the operands based on the result value in
814 : // the LHS.
815 :
816 : bool
817 3364802 : gori_compute::logical_combine (vrange &r, enum tree_code code,
818 : const irange &lhs,
819 : const vrange &op1_true, const vrange &op1_false,
820 : const vrange &op2_true, const vrange &op2_false)
821 : {
822 3364802 : if (op1_true.varying_p () && op1_false.varying_p ()
823 4462899 : && op2_true.varying_p () && op2_false.varying_p ())
824 : return false;
825 :
826 2775389 : unsigned idx;
827 2775389 : if ((idx = tracer.header ("logical_combine")))
828 : {
829 0 : switch (code)
830 : {
831 0 : case TRUTH_OR_EXPR:
832 0 : case BIT_IOR_EXPR:
833 0 : fprintf (dump_file, " || ");
834 0 : break;
835 0 : case TRUTH_AND_EXPR:
836 0 : case BIT_AND_EXPR:
837 0 : fprintf (dump_file, " && ");
838 0 : break;
839 : default:
840 : break;
841 : }
842 0 : fprintf (dump_file, " with LHS = ");
843 0 : lhs.dump (dump_file);
844 0 : fputc ('\n', dump_file);
845 :
846 0 : tracer.print (idx, "op1_true = ");
847 0 : op1_true.dump (dump_file);
848 0 : fprintf (dump_file, " op1_false = ");
849 0 : op1_false.dump (dump_file);
850 0 : fputc ('\n', dump_file);
851 0 : tracer.print (idx, "op2_true = ");
852 0 : op2_true.dump (dump_file);
853 0 : fprintf (dump_file, " op2_false = ");
854 0 : op2_false.dump (dump_file);
855 0 : fputc ('\n', dump_file);
856 : }
857 :
858 : // This is not a simple fold of a logical expression, rather it
859 : // determines ranges which flow through the logical expression.
860 : //
861 : // Assuming x_8 is an unsigned char, and relational statements:
862 : // b_1 = x_8 < 20
863 : // b_2 = x_8 > 5
864 : // consider the logical expression and branch:
865 : // c_2 = b_1 && b_2
866 : // if (c_2)
867 : //
868 : // To determine the range of x_8 on either edge of the branch, one
869 : // must first determine what the range of x_8 is when the boolean
870 : // values of b_1 and b_2 are both true and false.
871 : // b_1 TRUE x_8 = [0, 19]
872 : // b_1 FALSE x_8 = [20, 255]
873 : // b_2 TRUE x_8 = [6, 255]
874 : // b_2 FALSE x_8 = [0,5].
875 : //
876 : // These ranges are then combined based on the expected outcome of
877 : // the branch. The range on the TRUE side of the branch must satisfy
878 : // b_1 == true && b_2 == true
879 : //
880 : // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
881 : // must be true. The range of x_8 on the true side must be the
882 : // intersection of both ranges since both must be true. Thus the
883 : // range of x_8 on the true side is [6, 19].
884 : //
885 : // To determine the ranges on the FALSE side, all 3 combinations of
886 : // failing ranges must be considered, and combined as any of them
887 : // can cause the false result.
888 : //
889 : // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
890 : // FALSE results and combine them. If we fell back to VARYING any
891 : // range restrictions that have been discovered up to this point
892 : // would be lost.
893 2775389 : if (!range_is_either_true_or_false (lhs))
894 : {
895 0 : bool res;
896 0 : value_range r1 (r);
897 0 : if (logical_combine (r1, code, m_bool_zero, op1_true, op1_false,
898 : op2_true, op2_false)
899 0 : && logical_combine (r, code, m_bool_one, op1_true, op1_false,
900 : op2_true, op2_false))
901 : {
902 0 : r.union_ (r1);
903 0 : res = true;
904 : }
905 : else
906 : res = false;
907 0 : if (idx && res)
908 : {
909 0 : tracer.print (idx, "logical_combine produced ");
910 0 : r.dump (dump_file);
911 0 : fputc ('\n', dump_file);
912 : }
913 0 : return res;
914 0 : }
915 :
916 2775389 : switch (code)
917 : {
918 : // A logical AND combines ranges from 2 boolean conditions.
919 : // c_2 = b_1 && b_2
920 1788634 : case TRUTH_AND_EXPR:
921 1788634 : case BIT_AND_EXPR:
922 1788634 : if (!lhs.zero_p ())
923 : {
924 : // The TRUE side is the intersection of the 2 true ranges.
925 976565 : r = op1_true;
926 976565 : r.intersect (op2_true);
927 : }
928 : else
929 : {
930 : // The FALSE side is the union of the other 3 cases.
931 812069 : value_range ff (op1_false);
932 812069 : ff.intersect (op2_false);
933 812069 : value_range tf (op1_true);
934 812069 : tf.intersect (op2_false);
935 812069 : value_range ft (op1_false);
936 812069 : ft.intersect (op2_true);
937 812069 : r = ff;
938 812069 : r.union_ (tf);
939 812069 : r.union_ (ft);
940 812069 : }
941 : break;
942 : // A logical OR combines ranges from 2 boolean conditions.
943 : // c_2 = b_1 || b_2
944 986755 : case TRUTH_OR_EXPR:
945 986755 : case BIT_IOR_EXPR:
946 986755 : if (lhs.zero_p ())
947 : {
948 : // An OR operation will only take the FALSE path if both
949 : // operands are false simultaneously, which means they should
950 : // be intersected. !(x || y) == !x && !y
951 672792 : r = op1_false;
952 672792 : r.intersect (op2_false);
953 : }
954 : else
955 : {
956 : // The TRUE side of an OR operation will be the union of
957 : // the other three combinations.
958 313963 : value_range tt (op1_true);
959 313963 : tt.intersect (op2_true);
960 313963 : value_range tf (op1_true);
961 313963 : tf.intersect (op2_false);
962 313963 : value_range ft (op1_false);
963 313963 : ft.intersect (op2_true);
964 313963 : r = tt;
965 313963 : r.union_ (tf);
966 313963 : r.union_ (ft);
967 313963 : }
968 : break;
969 0 : default:
970 0 : gcc_unreachable ();
971 : }
972 :
973 2775389 : if (idx)
974 0 : tracer.trailer (idx, "logical_combine", true, NULL_TREE, r);
975 : return true;
976 : }
977 :
978 :
979 : // Given a logical STMT, calculate true and false ranges for each
980 : // potential path of NAME, assuming NAME came through the OP chain if
981 : // OP_IN_CHAIN is true.
982 :
983 : void
984 6729604 : gori_compute::compute_logical_operands (vrange &true_range, vrange &false_range,
985 : gimple_range_op_handler &handler,
986 : const irange &lhs,
987 : tree name, fur_source &src,
988 : tree op, bool op_in_chain)
989 : {
990 6729604 : gimple *stmt = handler.stmt ();
991 13459208 : gimple *src_stmt = gimple_range_ssa_p (op) ? SSA_NAME_DEF_STMT (op) : NULL;
992 6729604 : if (!op_in_chain || !src_stmt || m_map.chain_import_p (handler.lhs (), op))
993 : {
994 : // If op is not in the def chain, or defined in this block,
995 : // use its known value on entry to the block.
996 2202027 : src.get_operand (true_range, name);
997 2202027 : false_range = true_range;
998 2202027 : unsigned idx;
999 2202027 : if ((idx = tracer.header ("logical_operand")))
1000 : {
1001 0 : print_generic_expr (dump_file, op, TDF_SLIM);
1002 0 : fprintf (dump_file, " not in computation chain. Queried.\n");
1003 0 : tracer.trailer (idx, "logical_operand", true, NULL_TREE, true_range);
1004 : }
1005 2202027 : return;
1006 : }
1007 :
1008 4527577 : enum tree_code code = gimple_expr_code (stmt);
1009 : // Optimize [0 = x | y], since neither operand can ever be non-zero.
1010 4527577 : if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ())
1011 : {
1012 1119407 : if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name,
1013 : src))
1014 121120 : src.get_operand (false_range, name);
1015 1119407 : true_range = false_range;
1016 1119407 : return;
1017 : }
1018 :
1019 : // Optimize [1 = x & y], since neither operand can ever be zero.
1020 3408170 : if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one)
1021 : {
1022 1768522 : if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src))
1023 118578 : src.get_operand (true_range, name);
1024 1768522 : false_range = true_range;
1025 1768522 : return;
1026 : }
1027 :
1028 : // Calculate ranges for true and false on both sides, since the false
1029 : // path is not always a simple inversion of the true side.
1030 1639648 : if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src))
1031 147151 : src.get_operand (true_range, name);
1032 1639648 : if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, src))
1033 154908 : src.get_operand (false_range, name);
1034 : }
1035 :
1036 :
1037 : // This routine will try to refine the ranges of OP1 and OP2 given a relation
1038 : // K between them. In order to perform this refinement, one of the operands
1039 : // must be in the definition chain of the other. The use is refined using
1040 : // op1/op2_range on the statement, and the definition is then recalculated
1041 : // using the relation.
1042 :
1043 : bool
1044 38681387 : gori_compute::refine_using_relation (tree op1, vrange &op1_range,
1045 : tree op2, vrange &op2_range,
1046 : fur_source &src, relation_kind k)
1047 : {
1048 38681387 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1049 38681387 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1050 :
1051 38681387 : if (k == VREL_VARYING || k == VREL_EQ || k == VREL_UNDEFINED)
1052 : return false;
1053 :
1054 31775205 : bool change = false;
1055 31775205 : bool op1_def_p = m_map.in_chain_p (op2, op1);
1056 31775205 : if (!op1_def_p)
1057 31079285 : if (!m_map.in_chain_p (op1, op2))
1058 : return false;
1059 :
1060 1255488 : tree def_op = op1_def_p ? op1 : op2;
1061 1255488 : tree use_op = op1_def_p ? op2 : op1;
1062 :
1063 1255488 : if (!op1_def_p)
1064 1255488 : k = relation_swap (k);
1065 :
1066 : // op1_def is true if we want to look up op1, otherwise we want op2.
1067 : // if neither is the case, we returned in the above check.
1068 :
1069 1951408 : gimple *def_stmt = SSA_NAME_DEF_STMT (def_op);
1070 1951408 : gimple_range_op_handler op_handler (def_stmt);
1071 1951408 : if (!op_handler)
1072 : return false;
1073 1948357 : tree def_op1 = op_handler.operand1 ();
1074 1948357 : tree def_op2 = op_handler.operand2 ();
1075 : // if the def isn't binary, the relation will not be useful.
1076 1948357 : if (!def_op2)
1077 : return false;
1078 :
1079 : // Determine if op2 is directly referenced as an operand.
1080 1914542 : if (def_op1 == use_op)
1081 : {
1082 : // def_stmt has op1 in the 1st operand position.
1083 776023 : value_range other_op (TREE_TYPE (def_op2));
1084 776023 : src.get_operand (other_op, def_op2);
1085 :
1086 : // Using op1_range as the LHS, and relation REL, evaluate op2.
1087 776023 : tree type = TREE_TYPE (def_op1);
1088 776023 : value_range new_result (type);
1089 1348260 : if (!op_handler.op1_range (new_result, type,
1090 : op1_def_p ? op1_range : op2_range,
1091 776023 : other_op, relation_trio::lhs_op1 (k)))
1092 93129 : return false;
1093 682894 : if (op1_def_p)
1094 : {
1095 164307 : change |= op2_range.intersect (new_result);
1096 : // Recalculate op2.
1097 164307 : if (op_handler.fold_range (new_result, type, op2_range, other_op))
1098 : {
1099 164307 : change |= op1_range.intersect (new_result);
1100 : }
1101 : }
1102 : else
1103 : {
1104 518587 : change |= op1_range.intersect (new_result);
1105 : // Recalculate op1.
1106 518587 : if (op_handler.fold_range (new_result, type, op1_range, other_op))
1107 : {
1108 518587 : change |= op2_range.intersect (new_result);
1109 : }
1110 : }
1111 776023 : }
1112 1138519 : else if (def_op2 == use_op)
1113 : {
1114 : // def_stmt has op1 in the 1st operand position.
1115 615191 : value_range other_op (TREE_TYPE (def_op1));
1116 615191 : src.get_operand (other_op, def_op1);
1117 :
1118 : // Using op1_range as the LHS, and relation REL, evaluate op2.
1119 615191 : tree type = TREE_TYPE (def_op2);
1120 615191 : value_range new_result (type);
1121 1124637 : if (!op_handler.op2_range (new_result, type,
1122 : op1_def_p ? op1_range : op2_range,
1123 615191 : other_op, relation_trio::lhs_op2 (k)))
1124 8345 : return false;
1125 606846 : if (op1_def_p)
1126 : {
1127 102923 : change |= op2_range.intersect (new_result);
1128 : // Recalculate op1.
1129 102923 : if (op_handler.fold_range (new_result, type, other_op, op2_range))
1130 : {
1131 102923 : change |= op1_range.intersect (new_result);
1132 : }
1133 : }
1134 : else
1135 : {
1136 503923 : change |= op1_range.intersect (new_result);
1137 : // Recalculate op2.
1138 503923 : if (op_handler.fold_range (new_result, type, other_op, op1_range))
1139 : {
1140 503923 : change |= op2_range.intersect (new_result);
1141 : }
1142 : }
1143 615191 : }
1144 : return change;
1145 : }
1146 :
1147 : // Calculate a range for NAME from the operand 1 position of STMT
1148 : // assuming the result of the statement is LHS. Return the range in
1149 : // R, or false if no range could be calculated.
1150 :
1151 : bool
1152 92299259 : gori_compute::compute_operand1_range (vrange &r,
1153 : gimple_range_op_handler &handler,
1154 : const vrange &lhs,
1155 : fur_source &src, value_relation *rel)
1156 : {
1157 92299259 : gimple *stmt = handler.stmt ();
1158 92299259 : tree op1 = handler.operand1 ();
1159 92299259 : tree op2 = handler.operand2 ();
1160 92299259 : tree lhs_name = gimple_get_lhs (stmt);
1161 :
1162 92299259 : relation_trio trio;
1163 92299259 : if (rel)
1164 32858586 : trio = rel->create_trio (lhs_name, op1, op2);
1165 :
1166 92299259 : value_range op1_range (TREE_TYPE (op1));
1167 92299259 : value_range op2_range (op2 ? TREE_TYPE (op2) : TREE_TYPE (op1));
1168 :
1169 : // Fetch the known range for op1 in this block.
1170 92299259 : src.get_operand (op1_range, op1);
1171 :
1172 : // Now range-op calculate and put that result in r.
1173 92299259 : if (op2)
1174 : {
1175 81190553 : src.get_operand (op2_range, op2);
1176 :
1177 81190553 : relation_kind op_op = trio.op1_op2 ();
1178 81190553 : if (op_op != VREL_VARYING)
1179 19601597 : refine_using_relation (op1, op1_range, op2, op2_range, src, op_op);
1180 :
1181 : // If op1 == op2, create a new trio for just this call.
1182 81190553 : if (op1 == op2 && gimple_range_ssa_p (op1))
1183 102602 : trio = relation_trio (trio.lhs_op1 (), trio.lhs_op2 (), VREL_EQ);
1184 81190553 : if (!handler.calc_op1 (r, lhs, op2_range, trio))
1185 : return false;
1186 : }
1187 : else
1188 : {
1189 : // We pass op1_range to the unary operation. Normally it's a
1190 : // hidden range_for_type parameter, but sometimes having the
1191 : // actual range can result in better information.
1192 11108706 : if (!handler.calc_op1 (r, lhs, op1_range, trio))
1193 : return false;
1194 : }
1195 :
1196 89096970 : unsigned idx;
1197 89096970 : if ((idx = tracer.header ("compute op 1 (")))
1198 : {
1199 0 : print_generic_expr (dump_file, op1, TDF_SLIM);
1200 0 : fprintf (dump_file, ") at ");
1201 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1202 0 : tracer.print (idx, "LHS =");
1203 0 : lhs.dump (dump_file);
1204 0 : if (op2 && TREE_CODE (op2) == SSA_NAME)
1205 : {
1206 0 : fprintf (dump_file, ", ");
1207 0 : print_generic_expr (dump_file, op2, TDF_SLIM);
1208 0 : fprintf (dump_file, " = ");
1209 0 : op2_range.dump (dump_file);
1210 : }
1211 0 : fprintf (dump_file, "\n");
1212 0 : tracer.print (idx, "Computes ");
1213 0 : print_generic_expr (dump_file, op1, TDF_SLIM);
1214 0 : fprintf (dump_file, " = ");
1215 0 : r.dump (dump_file);
1216 0 : fprintf (dump_file, " intersect Known range : ");
1217 0 : op1_range.dump (dump_file);
1218 0 : fputc ('\n', dump_file);
1219 : }
1220 :
1221 89096970 : r.intersect (op1_range);
1222 89096970 : if (idx)
1223 0 : tracer.trailer (idx, "produces ", true, op1, r);
1224 : return true;
1225 92299259 : }
1226 :
1227 :
1228 : // Calculate a range for NAME from the operand 2 position of S
1229 : // assuming the result of the statement is LHS. Return the range in
1230 : // R, or false if no range could be calculated.
1231 :
1232 : bool
1233 26460952 : gori_compute::compute_operand2_range (vrange &r,
1234 : gimple_range_op_handler &handler,
1235 : const vrange &lhs,
1236 : fur_source &src, value_relation *rel)
1237 : {
1238 26460952 : gimple *stmt = handler.stmt ();
1239 26460952 : tree op1 = handler.operand1 ();
1240 26460952 : tree op2 = handler.operand2 ();
1241 26460952 : tree lhs_name = gimple_get_lhs (stmt);
1242 :
1243 26460952 : value_range op1_range (TREE_TYPE (op1));
1244 26460952 : value_range op2_range (TREE_TYPE (op2));
1245 :
1246 26460952 : src.get_operand (op1_range, op1);
1247 26460952 : src.get_operand (op2_range, op2);
1248 :
1249 26460952 : relation_trio trio;
1250 26460952 : if (rel)
1251 22170183 : trio = rel->create_trio (lhs_name, op1, op2);
1252 26460952 : relation_kind op_op = trio.op1_op2 ();
1253 :
1254 26460952 : if (op_op != VREL_VARYING)
1255 19079790 : refine_using_relation (op1, op1_range, op2, op2_range, src, op_op);
1256 :
1257 : // If op1 == op2, create a new trio for this stmt.
1258 26460952 : if (op1 == op2 && gimple_range_ssa_p (op1))
1259 35716 : trio = relation_trio (trio.lhs_op1 (), trio.lhs_op2 (), VREL_EQ);
1260 : // Intersect with range for op2 based on lhs and op1.
1261 26460952 : if (!handler.calc_op2 (r, lhs, op1_range, trio))
1262 : return false;
1263 :
1264 24135307 : unsigned idx;
1265 24135307 : if ((idx = tracer.header ("compute op 2 (")))
1266 : {
1267 0 : print_generic_expr (dump_file, op2, TDF_SLIM);
1268 0 : fprintf (dump_file, ") at ");
1269 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1270 0 : tracer.print (idx, "LHS = ");
1271 0 : lhs.dump (dump_file);
1272 0 : if (TREE_CODE (op1) == SSA_NAME)
1273 : {
1274 0 : fprintf (dump_file, ", ");
1275 0 : print_generic_expr (dump_file, op1, TDF_SLIM);
1276 0 : fprintf (dump_file, " = ");
1277 0 : op1_range.dump (dump_file);
1278 : }
1279 0 : fprintf (dump_file, "\n");
1280 0 : tracer.print (idx, "Computes ");
1281 0 : print_generic_expr (dump_file, op2, TDF_SLIM);
1282 0 : fprintf (dump_file, " = ");
1283 0 : r.dump (dump_file);
1284 0 : fprintf (dump_file, " intersect Known range : ");
1285 0 : op2_range.dump (dump_file);
1286 0 : fputc ('\n', dump_file);
1287 : }
1288 : // Intersect the calculated result with the known result and return if done.
1289 24135307 : r.intersect (op2_range);
1290 24135307 : if (idx)
1291 0 : tracer.trailer (idx, " produces ", true, op2, r);
1292 : return true;
1293 26460952 : }
1294 :
1295 : // Calculate a range for NAME from both operand positions of S
1296 : // assuming the result of the statement is LHS. Return the range in
1297 : // R, or false if no range could be calculated.
1298 :
1299 : bool
1300 404555 : gori_compute::compute_operand1_and_operand2_range (vrange &r,
1301 : gimple_range_op_handler
1302 : &handler,
1303 : const vrange &lhs,
1304 : tree name,
1305 : fur_source &src,
1306 : value_relation *rel)
1307 : {
1308 404555 : value_range op_range (TREE_TYPE (name));
1309 :
1310 404555 : value_range vr (TREE_TYPE (handler.operand2 ()));
1311 : // Calculate a good a range through op2.
1312 404555 : if (!compute_operand2_range (vr, handler, lhs, src, rel))
1313 : return false;
1314 384865 : gimple *src_stmt = SSA_NAME_DEF_STMT (handler.operand2 ());
1315 384865 : gcc_checking_assert (src_stmt);
1316 : // Then feed this range back as the LHS of the defining statement.
1317 384865 : if (!compute_operand_range (r, src_stmt, vr, name, src, rel))
1318 : return false;
1319 :
1320 : // Now get the range thru op1.
1321 169679 : vr.set_type (TREE_TYPE (handler.operand1 ()));
1322 169679 : if (!compute_operand1_range (vr, handler, lhs, src, rel))
1323 : return false;
1324 167050 : src_stmt = SSA_NAME_DEF_STMT (handler.operand1 ());
1325 167050 : gcc_checking_assert (src_stmt);
1326 : // Then feed this range back as the LHS of the defining statement.
1327 167050 : if (!compute_operand_range (op_range, src_stmt, vr, name, src, rel))
1328 : return false;
1329 :
1330 : // Both operands have to be simultaneously true, so perform an intersection.
1331 121286 : r.intersect (op_range);
1332 121286 : return true;
1333 404555 : }
1334 :
1335 : // Return TRUE if NAME can be recomputed on any edge exiting BB. If any
1336 : // direct dependent is exported, it may also change the computed value of NAME.
1337 :
1338 : bool
1339 1042505547 : gori_compute::may_recompute_p (tree name, basic_block bb, int depth)
1340 : {
1341 1042505547 : tree dep1 = m_map.depend1 (name);
1342 1042505547 : tree dep2 = m_map.depend2 (name);
1343 :
1344 : // If the first dependency is not set, there is no recomputation.
1345 : // Dependencies reflect original IL, not current state. Check if the
1346 : // SSA_NAME is still valid as well.
1347 1042505547 : if (!dep1)
1348 : return false;
1349 :
1350 : // Only recalculate range-op statements that are recomputable.
1351 786071592 : gimple *s = SSA_NAME_DEF_STMT (name);
1352 786071592 : gimple_range_op_handler handler (s);
1353 786071592 : if (!handler || !handler.recomputable_p ())
1354 : return false;
1355 :
1356 449853942 : if (!dep2)
1357 : {
1358 : // -1 indicates a default param, convert it to the real default.
1359 394943715 : if (depth == -1)
1360 347124770 : depth = m_recompute_depth;
1361 :
1362 394943715 : bool res = m_map.is_export_p (dep1, bb);
1363 394943715 : if (res || depth <= 1)
1364 : return res;
1365 : // Check another level of recomputation.
1366 352688391 : return may_recompute_p (dep1, bb, --depth);
1367 : }
1368 : // Two dependencies terminate the depth of the search.
1369 54910227 : return m_map.is_export_p (dep1, bb) || m_map.is_export_p (dep2, bb);
1370 : }
1371 :
1372 : // Return TRUE if NAME can be recomputed on edge E. If any direct dependent
1373 : // is exported on edge E, it may change the computed value of NAME.
1374 :
1375 : bool
1376 31467436 : gori_compute::may_recompute_p (tree name, edge e, int depth)
1377 : {
1378 31467436 : gcc_checking_assert (e);
1379 31467436 : return may_recompute_p (name, e->src, depth);
1380 : }
1381 :
1382 :
1383 : // Return TRUE if a range can be calculated or recomputed for NAME on any
1384 : // edge exiting BB.
1385 :
1386 : bool
1387 1025995003 : gori_compute::has_edge_range_p (tree name, basic_block bb)
1388 : {
1389 : // Check if NAME is an export or can be recomputed.
1390 1025995003 : if (bb)
1391 476106209 : return m_map.is_export_p (name, bb) || may_recompute_p (name, bb);
1392 :
1393 : // If no block is specified, check for anywhere in the IL.
1394 549888794 : return m_map.is_export_p (name) || may_recompute_p (name);
1395 : }
1396 :
1397 : // Return TRUE if a range can be calculated or recomputed for NAME on edge E.
1398 :
1399 : bool
1400 1885862 : gori_compute::has_edge_range_p (tree name, edge e)
1401 : {
1402 1885862 : gcc_checking_assert (e);
1403 1885862 : return has_edge_range_p (name, e->src);
1404 : }
1405 :
1406 : // Calculate a range on edge E and return it in R. Try to evaluate a
1407 : // range for NAME on this edge. Return FALSE if this is either not a
1408 : // control edge or NAME is not defined by this edge.
1409 :
1410 : bool
1411 161883499 : gori_compute::edge_range_p (vrange &r, edge e, tree name, range_query &q)
1412 : {
1413 161883499 : unsigned idx;
1414 :
1415 161883499 : if ((e->flags & m_not_executable_flag))
1416 : {
1417 48886 : r.set_undefined ();
1418 48886 : if (dump_file && (dump_flags & TDF_DETAILS))
1419 24 : fprintf (dump_file, "Outgoing edge %d->%d unexecutable.\n",
1420 24 : e->src->index, e->dest->index);
1421 48886 : return true;
1422 : }
1423 :
1424 161834613 : gcc_checking_assert (gimple_range_ssa_p (name));
1425 161834613 : int_range_max lhs;
1426 : // Determine if there is an outgoing edge.
1427 161834613 : gimple *stmt = gimple_outgoing_range::edge_range_p (lhs, e);
1428 161834613 : if (!stmt)
1429 : return false;
1430 :
1431 109903328 : fur_stmt src (stmt, &q);
1432 : // If NAME can be calculated on the edge, use that.
1433 109903328 : if (m_map.is_export_p (name, e->src))
1434 : {
1435 78435892 : bool res;
1436 78435892 : if ((idx = tracer.header ("outgoing_edge")))
1437 : {
1438 0 : fprintf (dump_file, " for ");
1439 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1440 0 : fprintf (dump_file, " on edge %d->%d\n",
1441 0 : e->src->index, e->dest->index);
1442 : }
1443 78435892 : if ((res = compute_operand_range (r, stmt, lhs, name, src)))
1444 : {
1445 : // Sometimes compatible types get interchanged. See PR97360.
1446 : // Make sure we are returning the type of the thing we asked for.
1447 70196290 : if (!r.undefined_p () && r.type () != TREE_TYPE (name))
1448 : {
1449 4689977 : gcc_checking_assert (range_compatible_p (r.type (),
1450 : TREE_TYPE (name)));
1451 4689977 : range_cast (r, TREE_TYPE (name));
1452 : }
1453 : }
1454 78435892 : if (idx)
1455 0 : tracer.trailer (idx, "outgoing_edge", res, name, r);
1456 78435892 : return res;
1457 : }
1458 : // If NAME isn't exported, check if it can be recomputed.
1459 31467436 : else if (may_recompute_p (name, e))
1460 : {
1461 7239829 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1462 :
1463 7239829 : if ((idx = tracer.header ("recomputation")))
1464 : {
1465 0 : fprintf (dump_file, " attempt on edge %d->%d for ",
1466 0 : e->src->index, e->dest->index);
1467 0 : print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM);
1468 : }
1469 : // Simply calculate DEF_STMT on edge E using the range query Q.
1470 7239829 : fold_range (r, def_stmt, e, &q);
1471 7239829 : if (idx)
1472 0 : tracer.trailer (idx, "recomputation", true, name, r);
1473 7239829 : return true;
1474 : }
1475 : return false;
1476 161834613 : }
1477 :
1478 : // Dump what is known to GORI computes to listing file F.
1479 :
1480 : void
1481 0 : gori_compute::dump (FILE *f)
1482 : {
1483 0 : m_map.gori_map::dump (f);
1484 0 : }
1485 :
1486 : // ------------------------------------------------------------------------
1487 : // GORI iterator. Although we have bitmap iterators, don't expose that it
1488 : // is currently a bitmap. Use an export iterator to hide future changes.
1489 :
1490 : // Construct a basic iterator over an export bitmap.
1491 :
1492 78893427 : gori_export_iterator::gori_export_iterator (bitmap b)
1493 : {
1494 78893427 : bm = b;
1495 78893427 : if (b)
1496 78893427 : bmp_iter_set_init (&bi, b, 1, &y);
1497 78893427 : }
1498 :
1499 :
1500 : // Move to the next export bitmap spot.
1501 :
1502 : void
1503 166037881 : gori_export_iterator::next ()
1504 : {
1505 166037881 : bmp_iter_next (&bi, &y);
1506 166037881 : }
1507 :
1508 :
1509 : // Fetch the name of the next export in the export list. Return NULL if
1510 : // iteration is done.
1511 :
1512 : tree
1513 244930648 : gori_export_iterator::get_name ()
1514 : {
1515 244930648 : if (!bm)
1516 : return NULL_TREE;
1517 :
1518 244931308 : while (bmp_iter_set (&bi, &y))
1519 : {
1520 166267429 : tree t = ssa_name (y);
1521 166267429 : if (t)
1522 : return t;
1523 660 : next ();
1524 : }
1525 : return NULL_TREE;
1526 : }
1527 :
1528 : // This is a helper class to set up STMT with a known LHS for further GORI
1529 : // processing.
1530 :
1531 56 : class gori_stmt_info : public gimple_range_op_handler
1532 : {
1533 : public:
1534 : gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q);
1535 : value_range op1_range;
1536 : value_range op2_range;
1537 : tree ssa1;
1538 : tree ssa2;
1539 : };
1540 :
1541 :
1542 : // Uses query Q to get the known ranges on STMT with a LHS range
1543 : // for op1_range and op2_range and set ssa1 and ssa2 if either or both of
1544 : // those operands are SSA_NAMES.
1545 :
1546 56 : gori_stmt_info::gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q)
1547 56 : : gimple_range_op_handler (stmt)
1548 : {
1549 56 : ssa1 = NULL;
1550 56 : ssa2 = NULL;
1551 : // Don't handle switches as yet for vector processing.
1552 56 : if (is_a<gswitch *> (stmt))
1553 : return;
1554 :
1555 : // No frther processing for VARYING or undefined.
1556 56 : if (lhs.undefined_p () || lhs.varying_p ())
1557 : return;
1558 :
1559 : // If there is no range-op handler, we are also done.
1560 56 : if (!*this)
1561 : return;
1562 :
1563 : // Only evaluate logical cases if both operands must be the same as the LHS.
1564 : // Otherwise its becomes exponential in time, as well as more complicated.
1565 48 : if (is_gimple_logical_p (stmt))
1566 : {
1567 0 : gcc_checking_assert (range_compatible_p (lhs.type (), boolean_type_node));
1568 0 : enum tree_code code = gimple_expr_code (stmt);
1569 0 : if (code == TRUTH_OR_EXPR || code == BIT_IOR_EXPR)
1570 : {
1571 : // [0, 0] = x || y means both x and y must be zero.
1572 0 : if (!lhs.singleton_p () || !lhs.zero_p ())
1573 0 : return;
1574 : }
1575 0 : else if (code == TRUTH_AND_EXPR || code == BIT_AND_EXPR)
1576 : {
1577 : // [1, 1] = x && y means both x and y must be one.
1578 0 : if (!lhs.singleton_p () || lhs.zero_p ())
1579 0 : return;
1580 : }
1581 : }
1582 :
1583 48 : tree op1 = operand1 ();
1584 48 : tree op2 = operand2 ();
1585 48 : ssa1 = gimple_range_ssa_p (op1);
1586 48 : ssa2 = gimple_range_ssa_p (op2);
1587 : // If both operands are the same, only process one of them.
1588 48 : if (ssa1 && ssa1 == ssa2)
1589 0 : ssa2 = NULL_TREE;
1590 :
1591 : // Extract current ranges for the operands.
1592 48 : fur_stmt src (stmt, q);
1593 48 : if (op1)
1594 : {
1595 48 : op1_range.set_type (TREE_TYPE (op1));
1596 48 : src.get_operand (op1_range, op1);
1597 : }
1598 :
1599 : // And satisfy the second operand for single op satements.
1600 48 : if (op2)
1601 : {
1602 34 : op2_range.set_type (TREE_TYPE (op2));
1603 34 : src.get_operand (op2_range, op2);
1604 : }
1605 14 : else if (op1)
1606 14 : op2_range = op1_range;
1607 : return;
1608 : }
1609 :
1610 :
1611 : // Process STMT using LHS as the range of the LHS. Invoke GORI processing
1612 : // to resolve ranges for all SSA_NAMES feeding STMT which may be altered
1613 : // based on LHS. Fill R with the results, and resolve all incoming
1614 : // ranges using range-query Q.
1615 :
1616 : static void
1617 28 : gori_calc_operands (vrange &lhs, gimple *stmt, ssa_cache &r, range_query *q)
1618 : {
1619 28 : struct gori_stmt_info si(lhs, stmt, q);
1620 28 : if (!si)
1621 5 : return;
1622 :
1623 23 : value_range tmp;
1624 : // Now evaluate operand ranges, and set them in the edge cache.
1625 : // If there was already a range, leave it and do no further evaluation.
1626 23 : if (si.ssa1 && !r.has_range (si.ssa1))
1627 : {
1628 20 : tmp.set_type (TREE_TYPE (si.ssa1));
1629 20 : if (si.calc_op1 (tmp, lhs, si.op2_range))
1630 20 : si.op1_range.intersect (tmp);
1631 20 : if (!si.op1_range.varying_p ())
1632 : {
1633 18 : r.set_range (si.ssa1, si.op1_range);
1634 18 : gimple *src = SSA_NAME_DEF_STMT (si.ssa1);
1635 : // If defintion is in the same basic lock, evaluate it.
1636 18 : if (src && gimple_bb (src) == gimple_bb (stmt))
1637 15 : gori_calc_operands (si.op1_range, src, r, q);
1638 : }
1639 : }
1640 :
1641 23 : if (si.ssa2 && !r.has_range (si.ssa2))
1642 : {
1643 5 : tmp.set_type (TREE_TYPE (si.ssa2));
1644 5 : if (si.calc_op2 (tmp, lhs, si.op1_range))
1645 5 : si.op2_range.intersect (tmp);
1646 5 : if (!si.op2_range.varying_p ())
1647 : {
1648 5 : r.set_range (si.ssa2, si.op2_range);
1649 5 : gimple *src = SSA_NAME_DEF_STMT (si.ssa2);
1650 5 : if (src && gimple_bb (src) == gimple_bb (stmt))
1651 5 : gori_calc_operands (si.op2_range, src, r, q);
1652 : }
1653 : }
1654 51 : }
1655 :
1656 : // Use ssa_cache R as a repository for all outgoing ranges on edge E that
1657 : // can be calculated. Use Q to establish starting edge ranges anbd to resolve
1658 : // operand values. If Q is NULL use the current range
1659 : // query available to the system.
1660 :
1661 : bool
1662 14 : gori_on_edge (ssa_cache &r, edge e, range_query *q)
1663 : {
1664 14 : if (!q)
1665 0 : q = get_range_query (cfun);
1666 : // Start with an empty vector
1667 14 : r.clear ();
1668 14 : int_range_max lhs;
1669 : // Determine if there is an outgoing edge.
1670 14 : gimple *stmt = q->gori ().edge_range_p (lhs, e);
1671 14 : if (!stmt)
1672 : return false;
1673 8 : gori_calc_operands (lhs, stmt, r, q);
1674 8 : return true;
1675 14 : }
1676 :
1677 : // Helper for GORI_NAME_ON_EDGE which uses query Q to determine if STMT
1678 : // provides a range for NAME, and returns it in R if so. If it does not,
1679 : // continue processing feeding statments until we run out of statements
1680 : // or fine a range for NAME.
1681 :
1682 : bool
1683 28 : gori_name_helper (vrange &r, tree name, vrange &lhs, gimple *stmt,
1684 : range_query *q)
1685 : {
1686 28 : struct gori_stmt_info si(lhs, stmt, q);
1687 28 : if (!si)
1688 : return false;
1689 :
1690 25 : if (si.ssa1 == name)
1691 4 : return si.calc_op1 (r, lhs, si.op2_range);
1692 21 : if (si.ssa2 == name)
1693 0 : return si.calc_op2 (r, lhs, si.op1_range);
1694 :
1695 21 : value_range tmp;
1696 : // Now evaluate operand ranges, and set them in the edge cache.
1697 : // If there was already a range, leave it and do no further evaluation.
1698 21 : if (si.ssa1)
1699 : {
1700 20 : tmp.set_type (TREE_TYPE (si.ssa1));
1701 20 : if (si.calc_op1 (tmp, lhs, si.op2_range))
1702 20 : si.op1_range.intersect (tmp);
1703 20 : gimple *src = SSA_NAME_DEF_STMT (si.ssa1);
1704 : // If defintion is in the same basic lock, evaluate it.
1705 20 : if (src && gimple_bb (src) == gimple_bb (stmt))
1706 7 : if (gori_name_helper (r, name, si.op1_range, src, q))
1707 : return true;
1708 : }
1709 :
1710 20 : if (si.ssa2)
1711 : {
1712 6 : tmp.set_type (TREE_TYPE (si.ssa2));
1713 6 : if (si.calc_op2 (tmp, lhs, si.op1_range))
1714 6 : si.op2_range.intersect (tmp);
1715 6 : gimple *src = SSA_NAME_DEF_STMT (si.ssa2);
1716 6 : if (src && gimple_bb (src) == gimple_bb (stmt))
1717 6 : if (gori_name_helper (r, name, si.op2_range, src, q))
1718 : return true;
1719 : }
1720 : return false;
1721 21 : }
1722 :
1723 : // Check if NAME has an outgoing range on edge E. Use query Q to evaluate
1724 : // the operands. Return TRUE and the range in R if there is an outgoing range.
1725 : // This is like gori_on_edge except it only looks for the single name and
1726 : // does not require an ssa_cache.
1727 :
1728 : bool
1729 21 : gori_name_on_edge (vrange &r, tree name, edge e, range_query *q)
1730 : {
1731 21 : int_range_max lhs;
1732 21 : gimple *stmt = gimple_outgoing_range_stmt_p (e->src);
1733 21 : if (!stmt || !is_a<gcond *> (stmt))
1734 : return false;
1735 15 : gcond_edge_range (lhs, e);
1736 15 : return gori_name_helper (r, name, lhs, stmt, q);
1737 21 : }
|
