mklog: add subject line skeleton
[official-gcc.git] / gcc / gimple-range-gori.cc
blobb58f2493b111d00a3b85ddda8eb43c181e891930
1 /* Gimple range GORI functions.
2 Copyright (C) 2017-2021 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
6 This file is part of GCC.
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.
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.
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/>. */
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"
32 // Return TRUE if GS is a logical && or || expression.
34 static inline bool
35 is_gimple_logical_p (const gimple *gs)
37 // Look for boolean and/or condition.
38 if (is_gimple_assign (gs))
39 switch (gimple_expr_code (gs))
41 case TRUTH_AND_EXPR:
42 case TRUTH_OR_EXPR:
43 return true;
45 case BIT_AND_EXPR:
46 case BIT_IOR_EXPR:
47 // Bitwise operations on single bits are logical too.
48 if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)),
49 boolean_type_node))
50 return true;
51 break;
53 default:
54 break;
56 return false;
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.
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.
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.
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)
79 _1 : x_4(D)
80 _2 : 1 x_4(D)
81 q_5 : _1 _2 x_4(D)
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.
86 Checking the chain for _2 indicates that _1 and x_4 are used in
87 its evaluation.
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. */
94 // Construct a range_def_chain.
96 range_def_chain::range_def_chain ()
98 bitmap_obstack_initialize (&m_bitmaps);
99 m_def_chain.create (0);
100 m_def_chain.safe_grow_cleared (num_ssa_names);
101 m_logical_depth = 0;
104 // Destruct a range_def_chain.
106 range_def_chain::~range_def_chain ()
108 m_def_chain.release ();
109 bitmap_obstack_release (&m_bitmaps);
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.
115 bool
116 range_def_chain::in_chain_p (tree name, tree def)
118 gcc_checking_assert (gimple_range_ssa_p (def));
119 gcc_checking_assert (gimple_range_ssa_p (name));
121 // Get the defintion chain for DEF.
122 bitmap chain = get_def_chain (def);
124 if (chain == NULL)
125 return false;
126 return bitmap_bit_p (chain, SSA_NAME_VERSION (name));
129 // Add either IMP or the import list B to the import set of DATA.
131 void
132 range_def_chain::set_import (struct rdc &data, tree imp, bitmap b)
134 // If there are no imports, just return
135 if (imp == NULL_TREE && !b)
136 return;
137 if (!data.m_import)
138 data.m_import = BITMAP_ALLOC (&m_bitmaps);
139 if (imp != NULL_TREE)
140 bitmap_set_bit (data.m_import, SSA_NAME_VERSION (imp));
141 else
142 bitmap_ior_into (data.m_import, b);
145 // Return the import list for NAME.
147 bitmap
148 range_def_chain::get_imports (tree name)
150 if (!has_def_chain (name))
151 get_def_chain (name);
152 bitmap i = m_def_chain[SSA_NAME_VERSION (name)].m_import;
153 // Either this is a default def, OR imports must be a subset of exports.
154 gcc_checking_assert (!get_def_chain (name) || !i
155 || !bitmap_intersect_compl_p (i, get_def_chain (name)));
156 return i;
159 // Return true if IMPORT is an import to NAMEs def chain.
161 bool
162 range_def_chain::chain_import_p (tree name, tree import)
164 bitmap b = get_imports (name);
165 if (b)
166 return bitmap_bit_p (b, SSA_NAME_VERSION (import));
167 return false;
170 // Build def_chains for NAME if it is in BB. Copy the def chain into RESULT.
172 void
173 range_def_chain::register_dependency (tree name, tree dep, basic_block bb)
175 if (!gimple_range_ssa_p (dep))
176 return;
178 unsigned v = SSA_NAME_VERSION (name);
179 if (v >= m_def_chain.length ())
180 m_def_chain.safe_grow_cleared (num_ssa_names + 1);
181 struct rdc &src = m_def_chain[v];
182 gimple *def_stmt = SSA_NAME_DEF_STMT (dep);
183 unsigned dep_v = SSA_NAME_VERSION (dep);
184 bitmap b;
186 // Set the direct dependency cache entries.
187 if (!src.ssa1)
188 src.ssa1 = dep;
189 else if (!src.ssa2 && src.ssa1 != dep)
190 src.ssa2 = dep;
192 // Don't calculate imports or export/dep chains if BB is not provided.
193 // This is usually the case for when the temporal cache wants the direct
194 // dependencies of a stmt.
195 if (!bb)
196 return;
198 if (!src.bm)
199 src.bm = BITMAP_ALLOC (&m_bitmaps);
201 // Add this operand into the result.
202 bitmap_set_bit (src.bm, dep_v);
204 if (gimple_bb (def_stmt) == bb && !is_a<gphi *>(def_stmt))
206 // Get the def chain for the operand.
207 b = get_def_chain (dep);
208 // If there was one, copy it into result.
209 if (b)
210 bitmap_ior_into (src.bm, b);
211 // And copy the import list.
212 set_import (src, NULL_TREE, get_imports (dep));
214 else
215 // Originated outside the block, so it is an import.
216 set_import (src, dep, NULL);
219 bool
220 range_def_chain::def_chain_in_bitmap_p (tree name, bitmap b)
222 bitmap a = get_def_chain (name);
223 if (a && b)
224 return bitmap_intersect_p (a, b);
225 return false;
228 void
229 range_def_chain::add_def_chain_to_bitmap (bitmap b, tree name)
231 bitmap r = get_def_chain (name);
232 if (r)
233 bitmap_ior_into (b, r);
237 // Return TRUE if NAME has been processed for a def_chain.
239 inline bool
240 range_def_chain::has_def_chain (tree name)
242 // Ensure there is an entry in the internal vector.
243 unsigned v = SSA_NAME_VERSION (name);
244 if (v >= m_def_chain.length ())
245 m_def_chain.safe_grow_cleared (num_ssa_names + 1);
246 return (m_def_chain[v].ssa1 != 0);
251 // Calculate the def chain for NAME and all of its dependent
252 // operands. Only using names in the same BB. Return the bitmap of
253 // all names in the m_def_chain. This only works for supported range
254 // statements.
256 bitmap
257 range_def_chain::get_def_chain (tree name)
259 tree ssa1, ssa2, ssa3;
260 unsigned v = SSA_NAME_VERSION (name);
261 bool is_logical = false;
263 // If it has already been processed, just return the cached value.
264 if (has_def_chain (name))
265 return m_def_chain[v].bm;
267 // No definition chain for default defs.
268 if (SSA_NAME_IS_DEFAULT_DEF (name))
270 // A Default def is always an import.
271 set_import (m_def_chain[v], name, NULL);
272 return NULL;
275 gimple *stmt = SSA_NAME_DEF_STMT (name);
276 if (gimple_range_handler (stmt))
278 is_logical = is_gimple_logical_p (stmt);
279 // Terminate the def chains if we see too many cascading logical stmts.
280 if (is_logical)
282 if (m_logical_depth == param_ranger_logical_depth)
283 return NULL;
284 m_logical_depth++;
287 ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt));
288 ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt));
289 ssa3 = NULL_TREE;
291 else if (is_a<gassign *> (stmt)
292 && gimple_assign_rhs_code (stmt) == COND_EXPR)
294 gassign *st = as_a<gassign *> (stmt);
295 ssa1 = gimple_range_ssa_p (gimple_assign_rhs1 (st));
296 ssa2 = gimple_range_ssa_p (gimple_assign_rhs2 (st));
297 ssa3 = gimple_range_ssa_p (gimple_assign_rhs3 (st));
299 else
301 // Stmts not understood are always imports.
302 set_import (m_def_chain[v], name, NULL);
303 return NULL;
306 register_dependency (name, ssa1, gimple_bb (stmt));
307 register_dependency (name, ssa2, gimple_bb (stmt));
308 register_dependency (name, ssa3, gimple_bb (stmt));
309 // Stmts with no understandable operands are also imports.
310 if (!ssa1 && !ssa2 & !ssa3)
311 set_import (m_def_chain[v], name, NULL);
313 if (is_logical)
314 m_logical_depth--;
316 return m_def_chain[v].bm;
319 // Dump what we know for basic block BB to file F.
321 void
322 range_def_chain::dump (FILE *f, basic_block bb, const char *prefix)
324 unsigned x, y;
325 bitmap_iterator bi;
327 // Dump the def chain for each SSA_NAME defined in BB.
328 for (x = 1; x < num_ssa_names; x++)
330 tree name = ssa_name (x);
331 if (!name)
332 continue;
333 gimple *stmt = SSA_NAME_DEF_STMT (name);
334 if (!stmt || (bb && gimple_bb (stmt) != bb))
335 continue;
336 bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL);
337 if (chain && !bitmap_empty_p (chain))
339 fprintf (f, prefix);
340 print_generic_expr (f, name, TDF_SLIM);
341 fprintf (f, " : ");
343 bitmap imports = get_imports (name);
344 EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi)
346 print_generic_expr (f, ssa_name (y), TDF_SLIM);
347 if (imports && bitmap_bit_p (imports, y))
348 fprintf (f, "(I)");
349 fprintf (f, " ");
351 fprintf (f, "\n");
357 // -------------------------------------------------------------------
359 /* GORI_MAP is used to accumulate what SSA names in a block can
360 generate range information, and provides tools for the block ranger
361 to enable it to efficiently calculate these ranges.
363 GORI stands for "Generates Outgoing Range Information."
365 It utilizes the range_def_chain class to contruct def_chains.
366 Information for a basic block is calculated once and stored. It is
367 only calculated the first time a query is made. If no queries are
368 made, there is little overhead.
370 one bitmap is maintained for each basic block:
371 m_outgoing : a set bit indicates a range can be generated for a name.
373 Generally speaking, the m_outgoing vector is the union of the
374 entire def_chain of all SSA names used in the last statement of the
375 block which generate ranges. */
378 // Initialize a gori-map structure.
380 gori_map::gori_map ()
382 m_outgoing.create (0);
383 m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
384 m_incoming.create (0);
385 m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
386 m_maybe_variant = BITMAP_ALLOC (&m_bitmaps);
389 // Free any memory the GORI map allocated.
391 gori_map::~gori_map ()
393 m_incoming.release ();
394 m_outgoing.release ();
397 // Return the bitmap vector of all export from BB. Calculate if necessary.
399 bitmap
400 gori_map::exports (basic_block bb)
402 if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
403 calculate_gori (bb);
404 return m_outgoing[bb->index];
407 // Return the bitmap vector of all imports to BB. Calculate if necessary.
409 bitmap
410 gori_map::imports (basic_block bb)
412 if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
413 calculate_gori (bb);
414 return m_incoming[bb->index];
417 // Return true if NAME is can have ranges generated for it from basic
418 // block BB.
420 bool
421 gori_map::is_export_p (tree name, basic_block bb)
423 // If no BB is specified, test if it is exported anywhere in the IL.
424 if (!bb)
425 return bitmap_bit_p (m_maybe_variant, SSA_NAME_VERSION (name));
426 return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name));
429 // Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
431 void
432 gori_map::set_range_invariant (tree name)
434 bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name));
437 // Return true if NAME is an import to block BB.
439 bool
440 gori_map::is_import_p (tree name, basic_block bb)
442 // If no BB is specified, test if it is exported anywhere in the IL.
443 return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name));
446 // If NAME is non-NULL and defined in block BB, calculate the def
447 // chain and add it to m_outgoing.
449 void
450 gori_map::maybe_add_gori (tree name, basic_block bb)
452 if (name)
454 // Check if there is a def chain, regardless of the block.
455 add_def_chain_to_bitmap (m_outgoing[bb->index], name);
456 // Check for any imports.
457 bitmap imp = get_imports (name);
458 // If there were imports, add them so we can recompute
459 if (imp)
460 bitmap_ior_into (m_incoming[bb->index], imp);
461 // This name is always an import.
462 if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb)
463 bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name));
465 // Def chain doesn't include itself, and even if there isn't a
466 // def chain, this name should be added to exports.
467 bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name));
471 // Calculate all the required information for BB.
473 void
474 gori_map::calculate_gori (basic_block bb)
476 tree name;
477 if (bb->index >= (signed int)m_outgoing.length ())
479 m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
480 m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
482 gcc_checking_assert (m_outgoing[bb->index] == NULL);
483 m_outgoing[bb->index] = BITMAP_ALLOC (&m_bitmaps);
484 m_incoming[bb->index] = BITMAP_ALLOC (&m_bitmaps);
486 // If this block's last statement may generate range informaiton, go
487 // calculate it.
488 gimple *stmt = gimple_outgoing_range_stmt_p (bb);
489 if (!stmt)
490 return;
491 if (is_a<gcond *> (stmt))
493 gcond *gc = as_a<gcond *>(stmt);
494 name = gimple_range_ssa_p (gimple_cond_lhs (gc));
495 maybe_add_gori (name, gimple_bb (stmt));
497 name = gimple_range_ssa_p (gimple_cond_rhs (gc));
498 maybe_add_gori (name, gimple_bb (stmt));
500 else
502 gswitch *gs = as_a<gswitch *>(stmt);
503 name = gimple_range_ssa_p (gimple_switch_index (gs));
504 maybe_add_gori (name, gimple_bb (stmt));
506 // Add this bitmap to the aggregate list of all outgoing names.
507 bitmap_ior_into (m_maybe_variant, m_outgoing[bb->index]);
510 // Dump the table information for BB to file F.
512 void
513 gori_map::dump (FILE *f, basic_block bb, bool verbose)
515 // BB was not processed.
516 if (!m_outgoing[bb->index] || bitmap_empty_p (m_outgoing[bb->index]))
517 return;
519 tree name;
521 bitmap imp = imports (bb);
522 if (!bitmap_empty_p (imp))
524 if (verbose)
525 fprintf (f, "bb<%u> Imports: ",bb->index);
526 else
527 fprintf (f, "Imports: ");
528 FOR_EACH_GORI_IMPORT_NAME (*this, bb, name)
530 print_generic_expr (f, name, TDF_SLIM);
531 fprintf (f, " ");
533 fputc ('\n', f);
536 if (verbose)
537 fprintf (f, "bb<%u> Exports: ",bb->index);
538 else
539 fprintf (f, "Exports: ");
540 // Dump the export vector.
541 FOR_EACH_GORI_EXPORT_NAME (*this, bb, name)
543 print_generic_expr (f, name, TDF_SLIM);
544 fprintf (f, " ");
546 fputc ('\n', f);
548 range_def_chain::dump (f, bb, " ");
551 // Dump the entire GORI map structure to file F.
553 void
554 gori_map::dump (FILE *f)
556 basic_block bb;
557 FOR_EACH_BB_FN (bb, cfun)
558 dump (f, bb);
561 DEBUG_FUNCTION void
562 debug (gori_map &g)
564 g.dump (stderr);
567 // -------------------------------------------------------------------
569 // Construct a gori_compute object.
571 gori_compute::gori_compute ()
573 // Create a boolean_type true and false range.
574 m_bool_zero = int_range<2> (boolean_false_node, boolean_false_node);
575 m_bool_one = int_range<2> (boolean_true_node, boolean_true_node);
578 // Given the switch S, return an evaluation in R for NAME when the lhs
579 // evaluates to LHS. Returning false means the name being looked for
580 // was not resolvable.
582 bool
583 gori_compute::compute_operand_range_switch (irange &r, gswitch *s,
584 const irange &lhs,
585 tree name, fur_source &src)
587 tree op1 = gimple_switch_index (s);
589 // If name matches, the range is simply the range from the edge.
590 // Empty ranges are viral as they are on a path which isn't
591 // executable.
592 if (op1 == name || lhs.undefined_p ())
594 r = lhs;
595 return true;
598 // If op1 is in the defintion chain, pass lhs back.
599 if (gimple_range_ssa_p (op1) && in_chain_p (name, op1))
600 return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name, src);
602 return false;
606 // Return an evaluation for NAME as it would appear in STMT when the
607 // statement's lhs evaluates to LHS. If successful, return TRUE and
608 // store the evaluation in R, otherwise return FALSE.
610 bool
611 gori_compute::compute_operand_range (irange &r, gimple *stmt,
612 const irange &lhs, tree name,
613 fur_source &src)
615 // If the lhs doesn't tell us anything, neither will unwinding further.
616 if (lhs.varying_p ())
617 return false;
619 // Empty ranges are viral as they are on an unexecutable path.
620 if (lhs.undefined_p ())
622 r.set_undefined ();
623 return true;
625 if (is_a<gswitch *> (stmt))
626 return compute_operand_range_switch (r, as_a<gswitch *> (stmt), lhs, name,
627 src);
628 if (!gimple_range_handler (stmt))
629 return false;
631 tree op1 = gimple_range_ssa_p (gimple_range_operand1 (stmt));
632 tree op2 = gimple_range_ssa_p (gimple_range_operand2 (stmt));
634 // Handle end of lookup first.
635 if (op1 == name)
636 return compute_operand1_range (r, stmt, lhs, name, src);
637 if (op2 == name)
638 return compute_operand2_range (r, stmt, lhs, name, src);
640 // NAME is not in this stmt, but one of the names in it ought to be
641 // derived from it.
642 bool op1_in_chain = op1 && in_chain_p (name, op1);
643 bool op2_in_chain = op2 && in_chain_p (name, op2);
645 // If neither operand is derived, then this stmt tells us nothing.
646 if (!op1_in_chain && !op2_in_chain)
647 return false;
649 // Process logicals as they have special handling.
650 if (is_gimple_logical_p (stmt))
652 int_range_max op1_trange, op1_frange;
653 int_range_max op2_trange, op2_frange;
654 compute_logical_operands (op1_trange, op1_frange, stmt, lhs,
655 name, src, op1, op1_in_chain);
656 compute_logical_operands (op2_trange, op2_frange, stmt, lhs,
657 name, src, op2, op2_in_chain);
658 return logical_combine (r, gimple_expr_code (stmt), lhs,
659 op1_trange, op1_frange, op2_trange, op2_frange);
662 // Follow the appropriate operands now.
663 if (op1_in_chain && op2_in_chain)
664 return compute_operand1_and_operand2_range (r, stmt, lhs, name, src);
665 if (op1_in_chain)
666 return compute_operand1_range (r, stmt, lhs, name, src);
667 if (op2_in_chain)
668 return compute_operand2_range (r, stmt, lhs, name, src);
670 // If neither operand is derived, this statement tells us nothing.
671 return false;
675 // Return TRUE if range R is either a true or false compatible range.
677 static bool
678 range_is_either_true_or_false (const irange &r)
680 if (r.undefined_p ())
681 return false;
683 // This is complicated by the fact that Ada has multi-bit booleans,
684 // so true can be ~[0, 0] (i.e. [1,MAX]).
685 tree type = r.type ();
686 gcc_checking_assert (range_compatible_p (type, boolean_type_node));
687 return (r.singleton_p () || !r.contains_p (build_zero_cst (type)));
690 // Evaluate a binary logical expression by combining the true and
691 // false ranges for each of the operands based on the result value in
692 // the LHS.
694 bool
695 gori_compute::logical_combine (irange &r, enum tree_code code,
696 const irange &lhs,
697 const irange &op1_true, const irange &op1_false,
698 const irange &op2_true, const irange &op2_false)
700 if (op1_true.varying_p () && op1_false.varying_p ()
701 && op2_true.varying_p () && op2_false.varying_p ())
702 return false;
704 // This is not a simple fold of a logical expression, rather it
705 // determines ranges which flow through the logical expression.
707 // Assuming x_8 is an unsigned char, and relational statements:
708 // b_1 = x_8 < 20
709 // b_2 = x_8 > 5
710 // consider the logical expression and branch:
711 // c_2 = b_1 && b_2
712 // if (c_2)
714 // To determine the range of x_8 on either edge of the branch, one
715 // must first determine what the range of x_8 is when the boolean
716 // values of b_1 and b_2 are both true and false.
717 // b_1 TRUE x_8 = [0, 19]
718 // b_1 FALSE x_8 = [20, 255]
719 // b_2 TRUE x_8 = [6, 255]
720 // b_2 FALSE x_8 = [0,5].
722 // These ranges are then combined based on the expected outcome of
723 // the branch. The range on the TRUE side of the branch must satisfy
724 // b_1 == true && b_2 == true
726 // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
727 // must be true. The range of x_8 on the true side must be the
728 // intersection of both ranges since both must be true. Thus the
729 // range of x_8 on the true side is [6, 19].
731 // To determine the ranges on the FALSE side, all 3 combinations of
732 // failing ranges must be considered, and combined as any of them
733 // can cause the false result.
735 // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
736 // FALSE results and combine them. If we fell back to VARYING any
737 // range restrictions that have been discovered up to this point
738 // would be lost.
739 if (!range_is_either_true_or_false (lhs))
741 int_range_max r1;
742 if (logical_combine (r1, code, m_bool_zero, op1_true, op1_false,
743 op2_true, op2_false)
744 && logical_combine (r, code, m_bool_one, op1_true, op1_false,
745 op2_true, op2_false))
747 r.union_ (r1);
748 return true;
750 return false;
753 switch (code)
755 // A logical AND combines ranges from 2 boolean conditions.
756 // c_2 = b_1 && b_2
757 case TRUTH_AND_EXPR:
758 case BIT_AND_EXPR:
759 if (!lhs.zero_p ())
761 // The TRUE side is the intersection of the the 2 true ranges.
762 r = op1_true;
763 r.intersect (op2_true);
765 else
767 // The FALSE side is the union of the other 3 cases.
768 int_range_max ff (op1_false);
769 ff.intersect (op2_false);
770 int_range_max tf (op1_true);
771 tf.intersect (op2_false);
772 int_range_max ft (op1_false);
773 ft.intersect (op2_true);
774 r = ff;
775 r.union_ (tf);
776 r.union_ (ft);
778 break;
779 // A logical OR combines ranges from 2 boolean conditons.
780 // c_2 = b_1 || b_2
781 case TRUTH_OR_EXPR:
782 case BIT_IOR_EXPR:
783 if (lhs.zero_p ())
785 // An OR operation will only take the FALSE path if both
786 // operands are false simlulateously, which means they should
787 // be intersected. !(x || y) == !x && !y
788 r = op1_false;
789 r.intersect (op2_false);
791 else
793 // The TRUE side of an OR operation will be the union of
794 // the other three combinations.
795 int_range_max tt (op1_true);
796 tt.intersect (op2_true);
797 int_range_max tf (op1_true);
798 tf.intersect (op2_false);
799 int_range_max ft (op1_false);
800 ft.intersect (op2_true);
801 r = tt;
802 r.union_ (tf);
803 r.union_ (ft);
805 break;
806 default:
807 gcc_unreachable ();
810 return true;
814 // Given a logical STMT, calculate true and false ranges for each
815 // potential path of NAME, assuming NAME came through the OP chain if
816 // OP_IN_CHAIN is true.
818 void
819 gori_compute::compute_logical_operands (irange &true_range, irange &false_range,
820 gimple *stmt,
821 const irange &lhs,
822 tree name, fur_source &src,
823 tree op, bool op_in_chain)
825 gimple *src_stmt = gimple_range_ssa_p (op) ? SSA_NAME_DEF_STMT (op) : NULL;
826 if (!op_in_chain || !src_stmt || chain_import_p (gimple_get_lhs (stmt), op))
828 // If op is not in the def chain, or defined in this block,
829 // use its known value on entry to the block.
830 src.get_operand (true_range, name);
831 false_range = true_range;
832 return;
835 enum tree_code code = gimple_expr_code (stmt);
836 // Optimize [0 = x | y], since neither operand can ever be non-zero.
837 if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ())
839 if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name,
840 src))
841 src.get_operand (false_range, name);
842 true_range = false_range;
843 return;
846 // Optimize [1 = x & y], since neither operand can ever be zero.
847 if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one)
849 if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src))
850 src.get_operand (true_range, name);
851 false_range = true_range;
852 return;
855 // Calculate ranges for true and false on both sides, since the false
856 // path is not always a simple inversion of the true side.
857 if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src))
858 src.get_operand (true_range, name);
859 if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, src))
860 src.get_operand (false_range, name);
863 // Calculate a range for NAME from the operand 1 position of STMT
864 // assuming the result of the statement is LHS. Return the range in
865 // R, or false if no range could be calculated.
867 bool
868 gori_compute::compute_operand1_range (irange &r, gimple *stmt,
869 const irange &lhs, tree name,
870 fur_source &src)
872 int_range_max op1_range, op2_range;
873 tree op1 = gimple_range_operand1 (stmt);
874 tree op2 = gimple_range_operand2 (stmt);
876 // Fetch the known range for op1 in this block.
877 src.get_operand (op1_range, op1);
879 // Now range-op calcuate and put that result in r.
880 if (op2)
882 src.get_operand (op2_range, op2);
883 if (!gimple_range_calc_op1 (r, stmt, lhs, op2_range))
884 return false;
886 else
888 // We pass op1_range to the unary operation. Nomally it's a
889 // hidden range_for_type parameter, but sometimes having the
890 // actual range can result in better information.
891 if (!gimple_range_calc_op1 (r, stmt, lhs, op1_range))
892 return false;
895 // Intersect the calculated result with the known result and return if done.
896 if (op1 == name)
898 r.intersect (op1_range);
899 return true;
901 // If the calculation continues, we're using op1_range as the new LHS.
902 op1_range.intersect (r);
904 gimple *src_stmt = SSA_NAME_DEF_STMT (op1);
905 gcc_checking_assert (src_stmt);
907 // Then feed this range back as the LHS of the defining statement.
908 return compute_operand_range (r, src_stmt, op1_range, name, src);
912 // Calculate a range for NAME from the operand 2 position of S
913 // assuming the result of the statement is LHS. Return the range in
914 // R, or false if no range could be calculated.
916 bool
917 gori_compute::compute_operand2_range (irange &r, gimple *stmt,
918 const irange &lhs, tree name,
919 fur_source &src)
921 int_range_max op1_range, op2_range;
922 tree op1 = gimple_range_operand1 (stmt);
923 tree op2 = gimple_range_operand2 (stmt);
925 src.get_operand (op1_range, op1);
926 src.get_operand (op2_range, op2);
928 // Intersect with range for op2 based on lhs and op1.
929 if (!gimple_range_calc_op2 (r, stmt, lhs, op1_range))
930 return false;
932 // Intersect the calculated result with the known result and return if done.
933 if (op2 == name)
935 r.intersect (op2_range);
936 return true;
938 // If the calculation continues, we're using op2_range as the new LHS.
939 op2_range.intersect (r);
941 gimple *src_stmt = SSA_NAME_DEF_STMT (op2);
942 gcc_checking_assert (src_stmt);
943 // gcc_checking_assert (!is_import_p (op2, find.bb));
945 // Then feed this range back as the LHS of the defining statement.
946 return compute_operand_range (r, src_stmt, op2_range, name, src);
949 // Calculate a range for NAME from both operand positions of S
950 // assuming the result of the statement is LHS. Return the range in
951 // R, or false if no range could be calculated.
953 bool
954 gori_compute::compute_operand1_and_operand2_range (irange &r,
955 gimple *stmt,
956 const irange &lhs,
957 tree name,
958 fur_source &src)
960 int_range_max op_range;
962 // Calculate a good a range for op2. Since op1 == op2, this will
963 // have already included whatever the actual range of name is.
964 if (!compute_operand2_range (op_range, stmt, lhs, name, src))
965 return false;
967 // Now get the range thru op1.
968 if (!compute_operand1_range (r, stmt, lhs, name, src))
969 return false;
971 // Both operands have to be simultaneously true, so perform an intersection.
972 r.intersect (op_range);
973 return true;
975 // Return TRUE if a range can be calculated or recomputed for NAME on edge E.
977 bool
978 gori_compute::has_edge_range_p (tree name, edge e)
980 // Check if NAME is an export or can be recomputed.
981 if (e)
982 return is_export_p (name, e->src) || may_recompute_p (name, e);
984 // If no edge is specified, check if NAME can have a range calculated
985 // on any edge.
986 return is_export_p (name) || may_recompute_p (name);
989 // Dump what is known to GORI computes to listing file F.
991 void
992 gori_compute::dump (FILE *f)
994 gori_map::dump (f);
997 // Return TRUE if NAME can be recomputed on edge E. If any direct dependant
998 // is exported on edge E, it may change the computed value of NAME.
1000 bool
1001 gori_compute::may_recompute_p (tree name, edge e)
1003 tree dep1 = depend1 (name);
1004 tree dep2 = depend2 (name);
1006 // If the first dependency is not set, there is no recompuation.
1007 if (!dep1)
1008 return false;
1010 // Don't recalculate PHIs or statements with side_effects.
1011 gimple *s = SSA_NAME_DEF_STMT (name);
1012 if (is_a<gphi *> (s) || gimple_has_side_effects (s))
1013 return false;
1015 // If edge is specified, check if NAME can be recalculated on that edge.
1016 if (e)
1017 return ((is_export_p (dep1, e->src))
1018 || (dep2 && is_export_p (dep2, e->src)));
1020 return (is_export_p (dep1)) || (dep2 && is_export_p (dep2));
1023 // Calculate a range on edge E and return it in R. Try to evaluate a
1024 // range for NAME on this edge. Return FALSE if this is either not a
1025 // control edge or NAME is not defined by this edge.
1027 bool
1028 gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name,
1029 range_query &q)
1031 int_range_max lhs;
1033 gcc_checking_assert (gimple_range_ssa_p (name));
1034 // Determine if there is an outgoing edge.
1035 gimple *stmt = outgoing.edge_range_p (lhs, e);
1036 if (!stmt)
1037 return false;
1039 fur_stmt src (stmt, &q);
1041 // If NAME can be calculated on the edge, use that.
1042 if (is_export_p (name, e->src))
1044 if (compute_operand_range (r, stmt, lhs, name, src))
1046 // Sometimes compatible types get interchanged. See PR97360.
1047 // Make sure we are returning the type of the thing we asked for.
1048 if (!r.undefined_p () && r.type () != TREE_TYPE (name))
1050 gcc_checking_assert (range_compatible_p (r.type (),
1051 TREE_TYPE (name)));
1052 range_cast (r, TREE_TYPE (name));
1054 return true;
1057 // If NAME isn't exported, check if it can be recomputed.
1058 else if (may_recompute_p (name, e))
1060 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1062 if (dump_file && (dump_flags & TDF_DETAILS))
1064 fprintf (dump_file, "recomputation attempt on edge %d->%d for ",
1065 e->src->index, e->dest->index);
1066 print_generic_expr (dump_file, name, TDF_SLIM);
1068 // Simply calculate DEF_STMT on edge E using the range query Q.
1069 fold_range (r, def_stmt, e, &q);
1070 if (dump_file && (dump_flags & TDF_DETAILS))
1072 fprintf (dump_file, " : Calculated :");
1073 r.dump (dump_file);
1074 fputc ('\n', dump_file);
1076 return true;
1078 return false;
1082 // ------------------------------------------------------------------------
1083 // GORI iterator. Although we have bitmap iterators, don't expose that it
1084 // is currently a bitmap. Use an export iterator to hide future changes.
1086 // Construct a basic iterator over an export bitmap.
1088 gori_export_iterator::gori_export_iterator (bitmap b)
1090 bm = b;
1091 if (b)
1092 bmp_iter_set_init (&bi, b, 1, &y);
1096 // Move to the next export bitmap spot.
1098 void
1099 gori_export_iterator::next ()
1101 bmp_iter_next (&bi, &y);
1105 // Fetch the name of the next export in the export list. Return NULL if
1106 // iteration is done.
1108 tree
1109 gori_export_iterator::get_name ()
1111 if (!bm)
1112 return NULL_TREE;
1114 while (bmp_iter_set (&bi, &y))
1116 tree t = ssa_name (y);
1117 if (t)
1118 return t;
1119 next ();
1121 return NULL_TREE;