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)
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/>. */
24 #include "coretypes.h"
29 #include "gimple-pretty-print.h"
30 #include "gimple-range.h"
32 // Calculate what we can determine of the range of this unary
33 // statement's operand if the lhs of the expression has the range
34 // LHS_RANGE. Return false if nothing can be determined.
37 gimple_range_calc_op1 (irange
&r
, const gimple
*stmt
, const irange
&lhs_range
)
39 gcc_checking_assert (gimple_num_ops (stmt
) < 3);
40 // Give up on empty ranges.
41 if (lhs_range
.undefined_p ())
44 // Unary operations require the type of the first operand in the
45 // second range position.
46 tree type
= TREE_TYPE (gimple_range_operand1 (stmt
));
47 int_range
<2> type_range (type
);
48 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
52 // Calculate what we can determine of the range of this statement's
53 // first operand if the lhs of the expression has the range LHS_RANGE
54 // and the second operand has the range OP2_RANGE. Return false if
55 // nothing can be determined.
58 gimple_range_calc_op1 (irange
&r
, const gimple
*stmt
,
59 const irange
&lhs_range
, const irange
&op2_range
)
61 // Give up on empty ranges.
62 if (lhs_range
.undefined_p ())
65 // Unary operation are allowed to pass a range in for second operand
66 // as there are often additional restrictions beyond the type which
67 // can be imposed. See operator_cast::op1_range().
68 tree type
= TREE_TYPE (gimple_range_operand1 (stmt
));
69 // If op2 is undefined, solve as if it is varying.
70 if (op2_range
.undefined_p ())
72 // This is sometimes invoked on single operand stmts.
73 if (gimple_num_ops (stmt
) < 3)
75 int_range
<2> trange (TREE_TYPE (gimple_range_operand2 (stmt
)));
76 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
79 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
83 // Calculate what we can determine of the range of this statement's
84 // second operand if the lhs of the expression has the range LHS_RANGE
85 // and the first operand has the range OP1_RANGE. Return false if
86 // nothing can be determined.
89 gimple_range_calc_op2 (irange
&r
, const gimple
*stmt
,
90 const irange
&lhs_range
, const irange
&op1_range
)
92 // Give up on empty ranges.
93 if (lhs_range
.undefined_p ())
96 tree type
= TREE_TYPE (gimple_range_operand2 (stmt
));
97 // If op1 is undefined, solve as if it is varying.
98 if (op1_range
.undefined_p ())
100 int_range
<2> trange (TREE_TYPE (gimple_range_operand1 (stmt
)));
101 return gimple_range_handler (stmt
)->op2_range (r
, type
, lhs_range
,
104 return gimple_range_handler (stmt
)->op2_range (r
, type
, lhs_range
,
108 // Return TRUE if GS is a logical && or || expression.
111 is_gimple_logical_p (const gimple
*gs
)
113 // Look for boolean and/or condition.
114 if (is_gimple_assign (gs
))
115 switch (gimple_expr_code (gs
))
123 // Bitwise operations on single bits are logical too.
124 if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs
)),
135 /* RANGE_DEF_CHAIN is used to determine which SSA names in a block can
136 have range information calculated for them, and what the
137 dependencies on each other are.
139 Information for a basic block is calculated once and stored. It is
140 only calculated the first time a query is made, so if no queries
141 are made, there is little overhead.
143 The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set
144 within this bitmap to indicate SSA names that are defined in the
145 SAME block and used to calculate this SSA name.
159 This dump indicates the bits set in the def_chain vector.
160 as well as demonstrates the def_chain bits for the related ssa_names.
162 Checking the chain for _2 indicates that _1 and x_4 are used in
165 Def chains also only include statements which are valid gimple
166 so a def chain will only span statements for which the range
167 engine implements operations for. */
170 // Construct a range_def_chain.
172 range_def_chain::range_def_chain ()
174 bitmap_obstack_initialize (&m_bitmaps
);
175 m_def_chain
.create (0);
176 m_def_chain
.safe_grow_cleared (num_ssa_names
);
180 // Destruct a range_def_chain.
182 range_def_chain::~range_def_chain ()
184 m_def_chain
.release ();
185 bitmap_obstack_release (&m_bitmaps
);
188 // Return true if NAME is in the def chain of DEF. If BB is provided,
189 // only return true if the defining statement of DEF is in BB.
192 range_def_chain::in_chain_p (tree name
, tree def
)
194 gcc_checking_assert (gimple_range_ssa_p (def
));
195 gcc_checking_assert (gimple_range_ssa_p (name
));
197 // Get the defintion chain for DEF.
198 bitmap chain
= get_def_chain (def
);
202 return bitmap_bit_p (chain
, SSA_NAME_VERSION (name
));
205 // Add either IMP or the import list B to the import set of DATA.
208 range_def_chain::set_import (struct rdc
&data
, tree imp
, bitmap b
)
210 // If there are no imports, just return
211 if (imp
== NULL_TREE
&& !b
)
214 data
.m_import
= BITMAP_ALLOC (&m_bitmaps
);
215 if (imp
!= NULL_TREE
)
216 bitmap_set_bit (data
.m_import
, SSA_NAME_VERSION (imp
));
218 bitmap_ior_into (data
.m_import
, b
);
221 // Return the import list for NAME.
224 range_def_chain::get_imports (tree name
)
226 if (!has_def_chain (name
))
227 get_def_chain (name
);
228 bitmap i
= m_def_chain
[SSA_NAME_VERSION (name
)].m_import
;
232 // Return true if IMPORT is an import to NAMEs def chain.
235 range_def_chain::chain_import_p (tree name
, tree import
)
237 bitmap b
= get_imports (name
);
239 return bitmap_bit_p (b
, SSA_NAME_VERSION (import
));
243 // Build def_chains for NAME if it is in BB. Copy the def chain into RESULT.
246 range_def_chain::register_dependency (tree name
, tree dep
, basic_block bb
)
248 if (!gimple_range_ssa_p (dep
))
251 unsigned v
= SSA_NAME_VERSION (name
);
252 if (v
>= m_def_chain
.length ())
253 m_def_chain
.safe_grow_cleared (num_ssa_names
+ 1);
254 struct rdc
&src
= m_def_chain
[v
];
255 gimple
*def_stmt
= SSA_NAME_DEF_STMT (dep
);
256 unsigned dep_v
= SSA_NAME_VERSION (dep
);
259 // Set the direct dependency cache entries.
262 else if (!src
.ssa2
&& src
.ssa1
!= dep
)
265 // Don't calculate imports or export/dep chains if BB is not provided.
266 // This is usually the case for when the temporal cache wants the direct
267 // dependencies of a stmt.
272 src
.bm
= BITMAP_ALLOC (&m_bitmaps
);
274 // Add this operand into the result.
275 bitmap_set_bit (src
.bm
, dep_v
);
277 if (gimple_bb (def_stmt
) == bb
&& !is_a
<gphi
*>(def_stmt
))
279 // Get the def chain for the operand.
280 b
= get_def_chain (dep
);
281 // If there was one, copy it into result. Access def_chain directly
282 // as the get_def_chain request above could reallocate the vector.
284 bitmap_ior_into (m_def_chain
[v
].bm
, b
);
285 // And copy the import list.
286 set_import (m_def_chain
[v
], NULL_TREE
, get_imports (dep
));
289 // Originated outside the block, so it is an import.
290 set_import (src
, dep
, NULL
);
294 range_def_chain::def_chain_in_bitmap_p (tree name
, bitmap b
)
296 bitmap a
= get_def_chain (name
);
298 return bitmap_intersect_p (a
, b
);
303 range_def_chain::add_def_chain_to_bitmap (bitmap b
, tree name
)
305 bitmap r
= get_def_chain (name
);
307 bitmap_ior_into (b
, r
);
311 // Return TRUE if NAME has been processed for a def_chain.
314 range_def_chain::has_def_chain (tree name
)
316 // Ensure there is an entry in the internal vector.
317 unsigned v
= SSA_NAME_VERSION (name
);
318 if (v
>= m_def_chain
.length ())
319 m_def_chain
.safe_grow_cleared (num_ssa_names
+ 1);
320 return (m_def_chain
[v
].ssa1
!= 0);
325 // Calculate the def chain for NAME and all of its dependent
326 // operands. Only using names in the same BB. Return the bitmap of
327 // all names in the m_def_chain. This only works for supported range
331 range_def_chain::get_def_chain (tree name
)
333 tree ssa1
, ssa2
, ssa3
;
334 unsigned v
= SSA_NAME_VERSION (name
);
336 // If it has already been processed, just return the cached value.
337 if (has_def_chain (name
))
338 return m_def_chain
[v
].bm
;
340 // No definition chain for default defs.
341 if (SSA_NAME_IS_DEFAULT_DEF (name
))
343 // A Default def is always an import.
344 set_import (m_def_chain
[v
], name
, NULL
);
348 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
349 if (gimple_range_handler (stmt
))
351 ssa1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
352 ssa2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
355 else if (is_a
<gassign
*> (stmt
)
356 && gimple_assign_rhs_code (stmt
) == COND_EXPR
)
358 gassign
*st
= as_a
<gassign
*> (stmt
);
359 ssa1
= gimple_range_ssa_p (gimple_assign_rhs1 (st
));
360 ssa2
= gimple_range_ssa_p (gimple_assign_rhs2 (st
));
361 ssa3
= gimple_range_ssa_p (gimple_assign_rhs3 (st
));
365 // Stmts not understood are always imports.
366 set_import (m_def_chain
[v
], name
, NULL
);
370 // Terminate the def chains if we see too many cascading stmts.
371 if (m_logical_depth
== param_ranger_logical_depth
)
374 // Increase the depth if we have a pair of ssa-names.
378 register_dependency (name
, ssa1
, gimple_bb (stmt
));
379 register_dependency (name
, ssa2
, gimple_bb (stmt
));
380 register_dependency (name
, ssa3
, gimple_bb (stmt
));
381 // Stmts with no understandable operands are also imports.
382 if (!ssa1
&& !ssa2
& !ssa3
)
383 set_import (m_def_chain
[v
], name
, NULL
);
388 return m_def_chain
[v
].bm
;
391 // Dump what we know for basic block BB to file F.
394 range_def_chain::dump (FILE *f
, basic_block bb
, const char *prefix
)
399 // Dump the def chain for each SSA_NAME defined in BB.
400 for (x
= 1; x
< num_ssa_names
; x
++)
402 tree name
= ssa_name (x
);
405 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
406 if (!stmt
|| (bb
&& gimple_bb (stmt
) != bb
))
408 bitmap chain
= (has_def_chain (name
) ? get_def_chain (name
) : NULL
);
409 if (chain
&& !bitmap_empty_p (chain
))
412 print_generic_expr (f
, name
, TDF_SLIM
);
415 bitmap imports
= get_imports (name
);
416 EXECUTE_IF_SET_IN_BITMAP (chain
, 0, y
, bi
)
418 print_generic_expr (f
, ssa_name (y
), TDF_SLIM
);
419 if (imports
&& bitmap_bit_p (imports
, y
))
429 // -------------------------------------------------------------------
431 /* GORI_MAP is used to accumulate what SSA names in a block can
432 generate range information, and provides tools for the block ranger
433 to enable it to efficiently calculate these ranges.
435 GORI stands for "Generates Outgoing Range Information."
437 It utilizes the range_def_chain class to contruct def_chains.
438 Information for a basic block is calculated once and stored. It is
439 only calculated the first time a query is made. If no queries are
440 made, there is little overhead.
442 one bitmap is maintained for each basic block:
443 m_outgoing : a set bit indicates a range can be generated for a name.
445 Generally speaking, the m_outgoing vector is the union of the
446 entire def_chain of all SSA names used in the last statement of the
447 block which generate ranges. */
450 // Initialize a gori-map structure.
452 gori_map::gori_map ()
454 m_outgoing
.create (0);
455 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
456 m_incoming
.create (0);
457 m_incoming
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
458 m_maybe_variant
= BITMAP_ALLOC (&m_bitmaps
);
461 // Free any memory the GORI map allocated.
463 gori_map::~gori_map ()
465 m_incoming
.release ();
466 m_outgoing
.release ();
469 // Return the bitmap vector of all export from BB. Calculate if necessary.
472 gori_map::exports (basic_block bb
)
474 if (bb
->index
>= (signed int)m_outgoing
.length () || !m_outgoing
[bb
->index
])
476 return m_outgoing
[bb
->index
];
479 // Return the bitmap vector of all imports to BB. Calculate if necessary.
482 gori_map::imports (basic_block bb
)
484 if (bb
->index
>= (signed int)m_outgoing
.length () || !m_outgoing
[bb
->index
])
486 return m_incoming
[bb
->index
];
489 // Return true if NAME is can have ranges generated for it from basic
493 gori_map::is_export_p (tree name
, basic_block bb
)
495 // If no BB is specified, test if it is exported anywhere in the IL.
497 return bitmap_bit_p (m_maybe_variant
, SSA_NAME_VERSION (name
));
498 return bitmap_bit_p (exports (bb
), SSA_NAME_VERSION (name
));
501 // Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
504 gori_map::set_range_invariant (tree name
)
506 bitmap_clear_bit (m_maybe_variant
, SSA_NAME_VERSION (name
));
509 // Return true if NAME is an import to block BB.
512 gori_map::is_import_p (tree name
, basic_block bb
)
514 // If no BB is specified, test if it is exported anywhere in the IL.
515 return bitmap_bit_p (imports (bb
), SSA_NAME_VERSION (name
));
518 // If NAME is non-NULL and defined in block BB, calculate the def
519 // chain and add it to m_outgoing.
522 gori_map::maybe_add_gori (tree name
, basic_block bb
)
526 // Check if there is a def chain, regardless of the block.
527 add_def_chain_to_bitmap (m_outgoing
[bb
->index
], name
);
528 // Check for any imports.
529 bitmap imp
= get_imports (name
);
530 // If there were imports, add them so we can recompute
532 bitmap_ior_into (m_incoming
[bb
->index
], imp
);
533 // This name is always an import.
534 if (gimple_bb (SSA_NAME_DEF_STMT (name
)) != bb
)
535 bitmap_set_bit (m_incoming
[bb
->index
], SSA_NAME_VERSION (name
));
537 // Def chain doesn't include itself, and even if there isn't a
538 // def chain, this name should be added to exports.
539 bitmap_set_bit (m_outgoing
[bb
->index
], SSA_NAME_VERSION (name
));
543 // Calculate all the required information for BB.
546 gori_map::calculate_gori (basic_block bb
)
549 if (bb
->index
>= (signed int)m_outgoing
.length ())
551 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
552 m_incoming
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
554 gcc_checking_assert (m_outgoing
[bb
->index
] == NULL
);
555 m_outgoing
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
556 m_incoming
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
558 // If this block's last statement may generate range informaiton, go
560 gimple
*stmt
= gimple_outgoing_range_stmt_p (bb
);
563 if (is_a
<gcond
*> (stmt
))
565 gcond
*gc
= as_a
<gcond
*>(stmt
);
566 name
= gimple_range_ssa_p (gimple_cond_lhs (gc
));
567 maybe_add_gori (name
, gimple_bb (stmt
));
569 name
= gimple_range_ssa_p (gimple_cond_rhs (gc
));
570 maybe_add_gori (name
, gimple_bb (stmt
));
574 // Do not process switches if they are too large.
575 if (EDGE_COUNT (bb
->succs
) > (unsigned)param_evrp_switch_limit
)
577 gswitch
*gs
= as_a
<gswitch
*>(stmt
);
578 name
= gimple_range_ssa_p (gimple_switch_index (gs
));
579 maybe_add_gori (name
, gimple_bb (stmt
));
581 // Add this bitmap to the aggregate list of all outgoing names.
582 bitmap_ior_into (m_maybe_variant
, m_outgoing
[bb
->index
]);
585 // Dump the table information for BB to file F.
588 gori_map::dump (FILE *f
, basic_block bb
, bool verbose
)
590 // BB was not processed.
591 if (!m_outgoing
[bb
->index
] || bitmap_empty_p (m_outgoing
[bb
->index
]))
596 bitmap imp
= imports (bb
);
597 if (!bitmap_empty_p (imp
))
600 fprintf (f
, "bb<%u> Imports: ",bb
->index
);
602 fprintf (f
, "Imports: ");
603 FOR_EACH_GORI_IMPORT_NAME (*this, bb
, name
)
605 print_generic_expr (f
, name
, TDF_SLIM
);
612 fprintf (f
, "bb<%u> Exports: ",bb
->index
);
614 fprintf (f
, "Exports: ");
615 // Dump the export vector.
616 FOR_EACH_GORI_EXPORT_NAME (*this, bb
, name
)
618 print_generic_expr (f
, name
, TDF_SLIM
);
623 range_def_chain::dump (f
, bb
, " ");
626 // Dump the entire GORI map structure to file F.
629 gori_map::dump (FILE *f
)
632 FOR_EACH_BB_FN (bb
, cfun
)
642 // -------------------------------------------------------------------
644 // Construct a gori_compute object.
646 gori_compute::gori_compute (int not_executable_flag
)
647 : outgoing (param_evrp_switch_limit
), tracer ("GORI ")
649 m_not_executable_flag
= not_executable_flag
;
650 // Create a boolean_type true and false range.
651 m_bool_zero
= int_range
<2> (boolean_false_node
, boolean_false_node
);
652 m_bool_one
= int_range
<2> (boolean_true_node
, boolean_true_node
);
653 if (dump_file
&& (param_ranger_debug
& RANGER_DEBUG_GORI
))
654 tracer
.enable_trace ();
657 // Given the switch S, return an evaluation in R for NAME when the lhs
658 // evaluates to LHS. Returning false means the name being looked for
659 // was not resolvable.
662 gori_compute::compute_operand_range_switch (irange
&r
, gswitch
*s
,
664 tree name
, fur_source
&src
)
666 tree op1
= gimple_switch_index (s
);
668 // If name matches, the range is simply the range from the edge.
669 // Empty ranges are viral as they are on a path which isn't
671 if (op1
== name
|| lhs
.undefined_p ())
677 // If op1 is in the defintion chain, pass lhs back.
678 if (gimple_range_ssa_p (op1
) && in_chain_p (name
, op1
))
679 return compute_operand_range (r
, SSA_NAME_DEF_STMT (op1
), lhs
, name
, src
);
685 // Return an evaluation for NAME as it would appear in STMT when the
686 // statement's lhs evaluates to LHS. If successful, return TRUE and
687 // store the evaluation in R, otherwise return FALSE.
690 gori_compute::compute_operand_range (irange
&r
, gimple
*stmt
,
691 const irange
&lhs
, tree name
,
694 // If the lhs doesn't tell us anything, neither will unwinding further.
695 if (lhs
.varying_p ())
698 // Empty ranges are viral as they are on an unexecutable path.
699 if (lhs
.undefined_p ())
704 if (is_a
<gswitch
*> (stmt
))
705 return compute_operand_range_switch (r
, as_a
<gswitch
*> (stmt
), lhs
, name
,
707 if (!gimple_range_handler (stmt
))
710 tree op1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
711 tree op2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
713 // Handle end of lookup first.
715 return compute_operand1_range (r
, stmt
, lhs
, name
, src
);
717 return compute_operand2_range (r
, stmt
, lhs
, name
, src
);
719 // NAME is not in this stmt, but one of the names in it ought to be
721 bool op1_in_chain
= op1
&& in_chain_p (name
, op1
);
722 bool op2_in_chain
= op2
&& in_chain_p (name
, op2
);
724 // If neither operand is derived, then this stmt tells us nothing.
725 if (!op1_in_chain
&& !op2_in_chain
)
729 // Process logicals as they have special handling.
730 if (is_gimple_logical_p (stmt
))
733 if ((idx
= tracer
.header ("compute_operand ")))
735 print_generic_expr (dump_file
, name
, TDF_SLIM
);
736 fprintf (dump_file
, " with LHS = ");
737 lhs
.dump (dump_file
);
738 fprintf (dump_file
, " at stmt ");
739 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
742 int_range_max op1_trange
, op1_frange
;
743 int_range_max op2_trange
, op2_frange
;
744 compute_logical_operands (op1_trange
, op1_frange
, stmt
, lhs
,
745 name
, src
, op1
, op1_in_chain
);
746 compute_logical_operands (op2_trange
, op2_frange
, stmt
, lhs
,
747 name
, src
, op2
, op2_in_chain
);
748 res
= logical_combine (r
, gimple_expr_code (stmt
), lhs
,
749 op1_trange
, op1_frange
, op2_trange
, op2_frange
);
751 tracer
.trailer (idx
, "compute_operand", res
, name
, r
);
753 // Follow the appropriate operands now.
754 else if (op1_in_chain
&& op2_in_chain
)
755 res
= compute_operand1_and_operand2_range (r
, stmt
, lhs
, name
, src
);
756 else if (op1_in_chain
)
757 res
= compute_operand1_range (r
, stmt
, lhs
, name
, src
);
758 else if (op2_in_chain
)
759 res
= compute_operand2_range (r
, stmt
, lhs
, name
, src
);
763 // If neither operand is derived, this statement tells us nothing.
768 // Return TRUE if range R is either a true or false compatible range.
771 range_is_either_true_or_false (const irange
&r
)
773 if (r
.undefined_p ())
776 // This is complicated by the fact that Ada has multi-bit booleans,
777 // so true can be ~[0, 0] (i.e. [1,MAX]).
778 tree type
= r
.type ();
779 gcc_checking_assert (range_compatible_p (type
, boolean_type_node
));
780 return (r
.singleton_p () || !r
.contains_p (build_zero_cst (type
)));
783 // Evaluate a binary logical expression by combining the true and
784 // false ranges for each of the operands based on the result value in
788 gori_compute::logical_combine (irange
&r
, enum tree_code code
,
790 const irange
&op1_true
, const irange
&op1_false
,
791 const irange
&op2_true
, const irange
&op2_false
)
793 if (op1_true
.varying_p () && op1_false
.varying_p ()
794 && op2_true
.varying_p () && op2_false
.varying_p ())
798 if ((idx
= tracer
.header ("logical_combine")))
804 fprintf (dump_file
, " || ");
808 fprintf (dump_file
, " && ");
813 fprintf (dump_file
, " with LHS = ");
814 lhs
.dump (dump_file
);
815 fputc ('\n', dump_file
);
817 tracer
.print (idx
, "op1_true = ");
818 op1_true
.dump (dump_file
);
819 fprintf (dump_file
, " op1_false = ");
820 op1_false
.dump (dump_file
);
821 fputc ('\n', dump_file
);
822 tracer
.print (idx
, "op2_true = ");
823 op2_true
.dump (dump_file
);
824 fprintf (dump_file
, " op2_false = ");
825 op2_false
.dump (dump_file
);
826 fputc ('\n', dump_file
);
829 // This is not a simple fold of a logical expression, rather it
830 // determines ranges which flow through the logical expression.
832 // Assuming x_8 is an unsigned char, and relational statements:
835 // consider the logical expression and branch:
839 // To determine the range of x_8 on either edge of the branch, one
840 // must first determine what the range of x_8 is when the boolean
841 // values of b_1 and b_2 are both true and false.
842 // b_1 TRUE x_8 = [0, 19]
843 // b_1 FALSE x_8 = [20, 255]
844 // b_2 TRUE x_8 = [6, 255]
845 // b_2 FALSE x_8 = [0,5].
847 // These ranges are then combined based on the expected outcome of
848 // the branch. The range on the TRUE side of the branch must satisfy
849 // b_1 == true && b_2 == true
851 // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
852 // must be true. The range of x_8 on the true side must be the
853 // intersection of both ranges since both must be true. Thus the
854 // range of x_8 on the true side is [6, 19].
856 // To determine the ranges on the FALSE side, all 3 combinations of
857 // failing ranges must be considered, and combined as any of them
858 // can cause the false result.
860 // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
861 // FALSE results and combine them. If we fell back to VARYING any
862 // range restrictions that have been discovered up to this point
864 if (!range_is_either_true_or_false (lhs
))
868 if (logical_combine (r1
, code
, m_bool_zero
, op1_true
, op1_false
,
870 && logical_combine (r
, code
, m_bool_one
, op1_true
, op1_false
,
871 op2_true
, op2_false
))
879 tracer
.trailer (idx
, "logical_combine", res
, NULL_TREE
, r
);
884 // A logical AND combines ranges from 2 boolean conditions.
890 // The TRUE side is the intersection of the the 2 true ranges.
892 r
.intersect (op2_true
);
896 // The FALSE side is the union of the other 3 cases.
897 int_range_max
ff (op1_false
);
898 ff
.intersect (op2_false
);
899 int_range_max
tf (op1_true
);
900 tf
.intersect (op2_false
);
901 int_range_max
ft (op1_false
);
902 ft
.intersect (op2_true
);
908 // A logical OR combines ranges from 2 boolean conditons.
914 // An OR operation will only take the FALSE path if both
915 // operands are false simlulateously, which means they should
916 // be intersected. !(x || y) == !x && !y
918 r
.intersect (op2_false
);
922 // The TRUE side of an OR operation will be the union of
923 // the other three combinations.
924 int_range_max
tt (op1_true
);
925 tt
.intersect (op2_true
);
926 int_range_max
tf (op1_true
);
927 tf
.intersect (op2_false
);
928 int_range_max
ft (op1_false
);
929 ft
.intersect (op2_true
);
940 tracer
.trailer (idx
, "logical_combine", true, NULL_TREE
, r
);
945 // Given a logical STMT, calculate true and false ranges for each
946 // potential path of NAME, assuming NAME came through the OP chain if
947 // OP_IN_CHAIN is true.
950 gori_compute::compute_logical_operands (irange
&true_range
, irange
&false_range
,
953 tree name
, fur_source
&src
,
954 tree op
, bool op_in_chain
)
956 gimple
*src_stmt
= gimple_range_ssa_p (op
) ? SSA_NAME_DEF_STMT (op
) : NULL
;
957 if (!op_in_chain
|| !src_stmt
|| chain_import_p (gimple_get_lhs (stmt
), op
))
959 // If op is not in the def chain, or defined in this block,
960 // use its known value on entry to the block.
961 src
.get_operand (true_range
, name
);
962 false_range
= true_range
;
964 if ((idx
= tracer
.header ("logical_operand")))
966 print_generic_expr (dump_file
, op
, TDF_SLIM
);
967 fprintf (dump_file
, " not in computation chain. Queried.\n");
968 tracer
.trailer (idx
, "logical_operand", true, NULL_TREE
, true_range
);
973 enum tree_code code
= gimple_expr_code (stmt
);
974 // Optimize [0 = x | y], since neither operand can ever be non-zero.
975 if ((code
== BIT_IOR_EXPR
|| code
== TRUTH_OR_EXPR
) && lhs
.zero_p ())
977 if (!compute_operand_range (false_range
, src_stmt
, m_bool_zero
, name
,
979 src
.get_operand (false_range
, name
);
980 true_range
= false_range
;
984 // Optimize [1 = x & y], since neither operand can ever be zero.
985 if ((code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
) && lhs
== m_bool_one
)
987 if (!compute_operand_range (true_range
, src_stmt
, m_bool_one
, name
, src
))
988 src
.get_operand (true_range
, name
);
989 false_range
= true_range
;
993 // Calculate ranges for true and false on both sides, since the false
994 // path is not always a simple inversion of the true side.
995 if (!compute_operand_range (true_range
, src_stmt
, m_bool_one
, name
, src
))
996 src
.get_operand (true_range
, name
);
997 if (!compute_operand_range (false_range
, src_stmt
, m_bool_zero
, name
, src
))
998 src
.get_operand (false_range
, name
);
1001 // Calculate a range for NAME from the operand 1 position of STMT
1002 // assuming the result of the statement is LHS. Return the range in
1003 // R, or false if no range could be calculated.
1006 gori_compute::compute_operand1_range (irange
&r
, gimple
*stmt
,
1007 const irange
&lhs
, tree name
,
1010 int_range_max op1_range
, op2_range
;
1011 tree op1
= gimple_range_operand1 (stmt
);
1012 tree op2
= gimple_range_operand2 (stmt
);
1014 // Fetch the known range for op1 in this block.
1015 src
.get_operand (op1_range
, op1
);
1017 // Now range-op calcuate and put that result in r.
1020 src
.get_operand (op2_range
, op2
);
1021 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op2_range
))
1026 // We pass op1_range to the unary operation. Nomally it's a
1027 // hidden range_for_type parameter, but sometimes having the
1028 // actual range can result in better information.
1029 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op1_range
))
1034 if ((idx
= tracer
.header ("compute op 1 (")))
1036 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1037 fprintf (dump_file
, ") at ");
1038 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1039 tracer
.print (idx
, "LHS =");
1040 lhs
.dump (dump_file
);
1041 if (op2
&& TREE_CODE (op2
) == SSA_NAME
)
1043 fprintf (dump_file
, ", ");
1044 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1045 fprintf (dump_file
, " = ");
1046 op2_range
.dump (dump_file
);
1048 fprintf (dump_file
, "\n");
1049 tracer
.print (idx
, "Computes ");
1050 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1051 fprintf (dump_file
, " = ");
1053 fprintf (dump_file
, " intersect Known range : ");
1054 op1_range
.dump (dump_file
);
1055 fputc ('\n', dump_file
);
1057 // Intersect the calculated result with the known result and return if done.
1060 r
.intersect (op1_range
);
1062 tracer
.trailer (idx
, "produces ", true, name
, r
);
1065 // If the calculation continues, we're using op1_range as the new LHS.
1066 op1_range
.intersect (r
);
1069 tracer
.trailer (idx
, "produces ", true, op1
, op1_range
);
1070 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op1
);
1071 gcc_checking_assert (src_stmt
);
1073 // Then feed this range back as the LHS of the defining statement.
1074 return compute_operand_range (r
, src_stmt
, op1_range
, name
, src
);
1078 // Calculate a range for NAME from the operand 2 position of S
1079 // assuming the result of the statement is LHS. Return the range in
1080 // R, or false if no range could be calculated.
1083 gori_compute::compute_operand2_range (irange
&r
, gimple
*stmt
,
1084 const irange
&lhs
, tree name
,
1087 int_range_max op1_range
, op2_range
;
1088 tree op1
= gimple_range_operand1 (stmt
);
1089 tree op2
= gimple_range_operand2 (stmt
);
1091 src
.get_operand (op1_range
, op1
);
1092 src
.get_operand (op2_range
, op2
);
1094 // Intersect with range for op2 based on lhs and op1.
1095 if (!gimple_range_calc_op2 (r
, stmt
, lhs
, op1_range
))
1099 if ((idx
= tracer
.header ("compute op 2 (")))
1101 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1102 fprintf (dump_file
, ") at ");
1103 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1104 tracer
.print (idx
, "LHS = ");
1105 lhs
.dump (dump_file
);
1106 if (TREE_CODE (op1
) == SSA_NAME
)
1108 fprintf (dump_file
, ", ");
1109 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1110 fprintf (dump_file
, " = ");
1111 op1_range
.dump (dump_file
);
1113 fprintf (dump_file
, "\n");
1114 tracer
.print (idx
, "Computes ");
1115 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1116 fprintf (dump_file
, " = ");
1118 fprintf (dump_file
, " intersect Known range : ");
1119 op2_range
.dump (dump_file
);
1120 fputc ('\n', dump_file
);
1122 // Intersect the calculated result with the known result and return if done.
1125 r
.intersect (op2_range
);
1127 tracer
.trailer (idx
, " produces ", true, NULL_TREE
, r
);
1130 // If the calculation continues, we're using op2_range as the new LHS.
1131 op2_range
.intersect (r
);
1134 tracer
.trailer (idx
, " produces ", true, op2
, op2_range
);
1135 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op2
);
1136 gcc_checking_assert (src_stmt
);
1137 // gcc_checking_assert (!is_import_p (op2, find.bb));
1139 // Then feed this range back as the LHS of the defining statement.
1140 return compute_operand_range (r
, src_stmt
, op2_range
, name
, src
);
1143 // Calculate a range for NAME from both operand positions of S
1144 // assuming the result of the statement is LHS. Return the range in
1145 // R, or false if no range could be calculated.
1148 gori_compute::compute_operand1_and_operand2_range (irange
&r
,
1154 int_range_max op_range
;
1156 // Calculate a good a range for op2. Since op1 == op2, this will
1157 // have already included whatever the actual range of name is.
1158 if (!compute_operand2_range (op_range
, stmt
, lhs
, name
, src
))
1161 // Now get the range thru op1.
1162 if (!compute_operand1_range (r
, stmt
, lhs
, name
, src
))
1165 // Both operands have to be simultaneously true, so perform an intersection.
1166 r
.intersect (op_range
);
1169 // Return TRUE if a range can be calculated or recomputed for NAME on edge E.
1172 gori_compute::has_edge_range_p (tree name
, edge e
)
1174 // Check if NAME is an export or can be recomputed.
1176 return is_export_p (name
, e
->src
) || may_recompute_p (name
, e
);
1178 // If no edge is specified, check if NAME can have a range calculated
1180 return is_export_p (name
) || may_recompute_p (name
);
1183 // Dump what is known to GORI computes to listing file F.
1186 gori_compute::dump (FILE *f
)
1191 // Return TRUE if NAME can be recomputed on edge E. If any direct dependant
1192 // is exported on edge E, it may change the computed value of NAME.
1195 gori_compute::may_recompute_p (tree name
, edge e
)
1197 tree dep1
= depend1 (name
);
1198 tree dep2
= depend2 (name
);
1200 // If the first dependency is not set, there is no recompuation.
1204 // Don't recalculate PHIs or statements with side_effects.
1205 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1206 if (is_a
<gphi
*> (s
) || gimple_has_side_effects (s
))
1209 // If edge is specified, check if NAME can be recalculated on that edge.
1211 return ((is_export_p (dep1
, e
->src
))
1212 || (dep2
&& is_export_p (dep2
, e
->src
)));
1214 return (is_export_p (dep1
)) || (dep2
&& is_export_p (dep2
));
1217 // Calculate a range on edge E and return it in R. Try to evaluate a
1218 // range for NAME on this edge. Return FALSE if this is either not a
1219 // control edge or NAME is not defined by this edge.
1222 gori_compute::outgoing_edge_range_p (irange
&r
, edge e
, tree name
,
1228 if ((e
->flags
& m_not_executable_flag
))
1231 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1232 fprintf (dump_file
, "Outgoing edge %d->%d unexecutable.\n",
1233 e
->src
->index
, e
->dest
->index
);
1237 gcc_checking_assert (gimple_range_ssa_p (name
));
1238 // Determine if there is an outgoing edge.
1239 gimple
*stmt
= outgoing
.edge_range_p (lhs
, e
);
1243 fur_stmt
src (stmt
, &q
);
1244 // If NAME can be calculated on the edge, use that.
1245 if (is_export_p (name
, e
->src
))
1248 if ((idx
= tracer
.header ("outgoing_edge")))
1250 fprintf (dump_file
, " for ");
1251 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1252 fprintf (dump_file
, " on edge %d->%d\n",
1253 e
->src
->index
, e
->dest
->index
);
1255 if ((res
= compute_operand_range (r
, stmt
, lhs
, name
, src
)))
1257 // Sometimes compatible types get interchanged. See PR97360.
1258 // Make sure we are returning the type of the thing we asked for.
1259 if (!r
.undefined_p () && r
.type () != TREE_TYPE (name
))
1261 gcc_checking_assert (range_compatible_p (r
.type (),
1263 range_cast (r
, TREE_TYPE (name
));
1267 tracer
.trailer (idx
, "outgoing_edge", res
, name
, r
);
1270 // If NAME isn't exported, check if it can be recomputed.
1271 else if (may_recompute_p (name
, e
))
1273 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1275 if ((idx
= tracer
.header ("recomputation")))
1277 fprintf (dump_file
, " attempt on edge %d->%d for ",
1278 e
->src
->index
, e
->dest
->index
);
1279 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
1281 // Simply calculate DEF_STMT on edge E using the range query Q.
1282 fold_range (r
, def_stmt
, e
, &q
);
1284 tracer
.trailer (idx
, "recomputation", true, name
, r
);
1291 // ------------------------------------------------------------------------
1292 // GORI iterator. Although we have bitmap iterators, don't expose that it
1293 // is currently a bitmap. Use an export iterator to hide future changes.
1295 // Construct a basic iterator over an export bitmap.
1297 gori_export_iterator::gori_export_iterator (bitmap b
)
1301 bmp_iter_set_init (&bi
, b
, 1, &y
);
1305 // Move to the next export bitmap spot.
1308 gori_export_iterator::next ()
1310 bmp_iter_next (&bi
, &y
);
1314 // Fetch the name of the next export in the export list. Return NULL if
1315 // iteration is done.
1318 gori_export_iterator::get_name ()
1323 while (bmp_iter_set (&bi
, &y
))
1325 tree t
= ssa_name (y
);