1 /* Gimple range GORI functions.
2 Copyright (C) 2017-2022 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 (vrange
&r
, const gimple
*stmt
, const vrange
&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 Value_Range
type_range (type
);
48 type_range
.set_varying (type
);
49 return range_op_handler (stmt
).op1_range (r
, type
, lhs_range
, type_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 (vrange
&r
, const gimple
*stmt
,
59 const vrange
&lhs_range
, const vrange
&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 tree op2_type
= TREE_TYPE (gimple_range_operand2 (stmt
));
76 Value_Range
trange (op2_type
);
77 trange
.set_varying (op2_type
);
78 return range_op_handler (stmt
).op1_range (r
, type
, lhs_range
, trange
);
80 return range_op_handler (stmt
).op1_range (r
, type
, lhs_range
, op2_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 (vrange
&r
, const gimple
*stmt
,
90 const vrange
&lhs_range
, const vrange
&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 tree op1_type
= TREE_TYPE (gimple_range_operand1 (stmt
));
101 Value_Range
trange (op1_type
);
102 trange
.set_varying (op1_type
);
103 return range_op_handler (stmt
).op2_range (r
, type
, lhs_range
, trange
);
105 return range_op_handler (stmt
).op2_range (r
, type
, lhs_range
,
109 // Return TRUE if GS is a logical && or || expression.
112 is_gimple_logical_p (const gimple
*gs
)
114 // Look for boolean and/or condition.
115 if (is_gimple_assign (gs
))
116 switch (gimple_expr_code (gs
))
124 // Bitwise operations on single bits are logical too.
125 if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs
)),
136 /* RANGE_DEF_CHAIN is used to determine which SSA names in a block can
137 have range information calculated for them, and what the
138 dependencies on each other are.
140 Information for a basic block is calculated once and stored. It is
141 only calculated the first time a query is made, so if no queries
142 are made, there is little overhead.
144 The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set
145 within this bitmap to indicate SSA names that are defined in the
146 SAME block and used to calculate this SSA name.
160 This dump indicates the bits set in the def_chain vector.
161 as well as demonstrates the def_chain bits for the related ssa_names.
163 Checking the chain for _2 indicates that _1 and x_4 are used in
166 Def chains also only include statements which are valid gimple
167 so a def chain will only span statements for which the range
168 engine implements operations for. */
171 // Construct a range_def_chain.
173 range_def_chain::range_def_chain ()
175 bitmap_obstack_initialize (&m_bitmaps
);
176 m_def_chain
.create (0);
177 m_def_chain
.safe_grow_cleared (num_ssa_names
);
181 // Destruct a range_def_chain.
183 range_def_chain::~range_def_chain ()
185 m_def_chain
.release ();
186 bitmap_obstack_release (&m_bitmaps
);
189 // Return true if NAME is in the def chain of DEF. If BB is provided,
190 // only return true if the defining statement of DEF is in BB.
193 range_def_chain::in_chain_p (tree name
, tree def
)
195 gcc_checking_assert (gimple_range_ssa_p (def
));
196 gcc_checking_assert (gimple_range_ssa_p (name
));
198 // Get the defintion chain for DEF.
199 bitmap chain
= get_def_chain (def
);
203 return bitmap_bit_p (chain
, SSA_NAME_VERSION (name
));
206 // Add either IMP or the import list B to the import set of DATA.
209 range_def_chain::set_import (struct rdc
&data
, tree imp
, bitmap b
)
211 // If there are no imports, just return
212 if (imp
== NULL_TREE
&& !b
)
215 data
.m_import
= BITMAP_ALLOC (&m_bitmaps
);
216 if (imp
!= NULL_TREE
)
217 bitmap_set_bit (data
.m_import
, SSA_NAME_VERSION (imp
));
219 bitmap_ior_into (data
.m_import
, b
);
222 // Return the import list for NAME.
225 range_def_chain::get_imports (tree name
)
227 if (!has_def_chain (name
))
228 get_def_chain (name
);
229 bitmap i
= m_def_chain
[SSA_NAME_VERSION (name
)].m_import
;
233 // Return true if IMPORT is an import to NAMEs def chain.
236 range_def_chain::chain_import_p (tree name
, tree import
)
238 bitmap b
= get_imports (name
);
240 return bitmap_bit_p (b
, SSA_NAME_VERSION (import
));
244 // Build def_chains for NAME if it is in BB. Copy the def chain into RESULT.
247 range_def_chain::register_dependency (tree name
, tree dep
, basic_block bb
)
249 if (!gimple_range_ssa_p (dep
))
252 unsigned v
= SSA_NAME_VERSION (name
);
253 if (v
>= m_def_chain
.length ())
254 m_def_chain
.safe_grow_cleared (num_ssa_names
+ 1);
255 struct rdc
&src
= m_def_chain
[v
];
256 gimple
*def_stmt
= SSA_NAME_DEF_STMT (dep
);
257 unsigned dep_v
= SSA_NAME_VERSION (dep
);
260 // Set the direct dependency cache entries.
263 else if (!src
.ssa2
&& src
.ssa1
!= dep
)
266 // Don't calculate imports or export/dep chains if BB is not provided.
267 // This is usually the case for when the temporal cache wants the direct
268 // dependencies of a stmt.
273 src
.bm
= BITMAP_ALLOC (&m_bitmaps
);
275 // Add this operand into the result.
276 bitmap_set_bit (src
.bm
, dep_v
);
278 if (gimple_bb (def_stmt
) == bb
&& !is_a
<gphi
*>(def_stmt
))
280 // Get the def chain for the operand.
281 b
= get_def_chain (dep
);
282 // If there was one, copy it into result. Access def_chain directly
283 // as the get_def_chain request above could reallocate the vector.
285 bitmap_ior_into (m_def_chain
[v
].bm
, b
);
286 // And copy the import list.
287 set_import (m_def_chain
[v
], NULL_TREE
, get_imports (dep
));
290 // Originated outside the block, so it is an import.
291 set_import (src
, dep
, NULL
);
295 range_def_chain::def_chain_in_bitmap_p (tree name
, bitmap b
)
297 bitmap a
= get_def_chain (name
);
299 return bitmap_intersect_p (a
, b
);
304 range_def_chain::add_def_chain_to_bitmap (bitmap b
, tree name
)
306 bitmap r
= get_def_chain (name
);
308 bitmap_ior_into (b
, r
);
312 // Return TRUE if NAME has been processed for a def_chain.
315 range_def_chain::has_def_chain (tree name
)
317 // Ensure there is an entry in the internal vector.
318 unsigned v
= SSA_NAME_VERSION (name
);
319 if (v
>= m_def_chain
.length ())
320 m_def_chain
.safe_grow_cleared (num_ssa_names
+ 1);
321 return (m_def_chain
[v
].ssa1
!= 0);
326 // Calculate the def chain for NAME and all of its dependent
327 // operands. Only using names in the same BB. Return the bitmap of
328 // all names in the m_def_chain. This only works for supported range
332 range_def_chain::get_def_chain (tree name
)
334 tree ssa1
, ssa2
, ssa3
;
335 unsigned v
= SSA_NAME_VERSION (name
);
337 // If it has already been processed, just return the cached value.
338 if (has_def_chain (name
) && m_def_chain
[v
].bm
)
339 return m_def_chain
[v
].bm
;
341 // No definition chain for default defs.
342 if (SSA_NAME_IS_DEFAULT_DEF (name
))
344 // A Default def is always an import.
345 set_import (m_def_chain
[v
], name
, NULL
);
349 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
350 if (range_op_handler (stmt
))
352 ssa1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
353 ssa2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
356 else if (is_a
<gassign
*> (stmt
)
357 && gimple_assign_rhs_code (stmt
) == COND_EXPR
)
359 gassign
*st
= as_a
<gassign
*> (stmt
);
360 ssa1
= gimple_range_ssa_p (gimple_assign_rhs1 (st
));
361 ssa2
= gimple_range_ssa_p (gimple_assign_rhs2 (st
));
362 ssa3
= gimple_range_ssa_p (gimple_assign_rhs3 (st
));
366 // Stmts not understood are always imports.
367 set_import (m_def_chain
[v
], name
, NULL
);
371 // Terminate the def chains if we see too many cascading stmts.
372 if (m_logical_depth
== param_ranger_logical_depth
)
375 // Increase the depth if we have a pair of ssa-names.
379 register_dependency (name
, ssa1
, gimple_bb (stmt
));
380 register_dependency (name
, ssa2
, gimple_bb (stmt
));
381 register_dependency (name
, ssa3
, gimple_bb (stmt
));
382 // Stmts with no understandable operands are also imports.
383 if (!ssa1
&& !ssa2
& !ssa3
)
384 set_import (m_def_chain
[v
], name
, NULL
);
389 return m_def_chain
[v
].bm
;
392 // Dump what we know for basic block BB to file F.
395 range_def_chain::dump (FILE *f
, basic_block bb
, const char *prefix
)
400 // Dump the def chain for each SSA_NAME defined in BB.
401 for (x
= 1; x
< num_ssa_names
; x
++)
403 tree name
= ssa_name (x
);
406 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
407 if (!stmt
|| (bb
&& gimple_bb (stmt
) != bb
))
409 bitmap chain
= (has_def_chain (name
) ? get_def_chain (name
) : NULL
);
410 if (chain
&& !bitmap_empty_p (chain
))
413 print_generic_expr (f
, name
, TDF_SLIM
);
416 bitmap imports
= get_imports (name
);
417 EXECUTE_IF_SET_IN_BITMAP (chain
, 0, y
, bi
)
419 print_generic_expr (f
, ssa_name (y
), TDF_SLIM
);
420 if (imports
&& bitmap_bit_p (imports
, y
))
430 // -------------------------------------------------------------------
432 /* GORI_MAP is used to accumulate what SSA names in a block can
433 generate range information, and provides tools for the block ranger
434 to enable it to efficiently calculate these ranges.
436 GORI stands for "Generates Outgoing Range Information."
438 It utilizes the range_def_chain class to contruct def_chains.
439 Information for a basic block is calculated once and stored. It is
440 only calculated the first time a query is made. If no queries are
441 made, there is little overhead.
443 one bitmap is maintained for each basic block:
444 m_outgoing : a set bit indicates a range can be generated for a name.
446 Generally speaking, the m_outgoing vector is the union of the
447 entire def_chain of all SSA names used in the last statement of the
448 block which generate ranges. */
451 // Initialize a gori-map structure.
453 gori_map::gori_map ()
455 m_outgoing
.create (0);
456 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
457 m_incoming
.create (0);
458 m_incoming
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
459 m_maybe_variant
= BITMAP_ALLOC (&m_bitmaps
);
462 // Free any memory the GORI map allocated.
464 gori_map::~gori_map ()
466 m_incoming
.release ();
467 m_outgoing
.release ();
470 // Return the bitmap vector of all export from BB. Calculate if necessary.
473 gori_map::exports (basic_block bb
)
475 if (bb
->index
>= (signed int)m_outgoing
.length () || !m_outgoing
[bb
->index
])
477 return m_outgoing
[bb
->index
];
480 // Return the bitmap vector of all imports to BB. Calculate if necessary.
483 gori_map::imports (basic_block bb
)
485 if (bb
->index
>= (signed int)m_outgoing
.length () || !m_outgoing
[bb
->index
])
487 return m_incoming
[bb
->index
];
490 // Return true if NAME is can have ranges generated for it from basic
494 gori_map::is_export_p (tree name
, basic_block bb
)
496 // If no BB is specified, test if it is exported anywhere in the IL.
498 return bitmap_bit_p (m_maybe_variant
, SSA_NAME_VERSION (name
));
499 return bitmap_bit_p (exports (bb
), SSA_NAME_VERSION (name
));
502 // Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
505 gori_map::set_range_invariant (tree name
)
507 bitmap_clear_bit (m_maybe_variant
, SSA_NAME_VERSION (name
));
510 // Return true if NAME is an import to block BB.
513 gori_map::is_import_p (tree name
, basic_block bb
)
515 // If no BB is specified, test if it is exported anywhere in the IL.
516 return bitmap_bit_p (imports (bb
), SSA_NAME_VERSION (name
));
519 // If NAME is non-NULL and defined in block BB, calculate the def
520 // chain and add it to m_outgoing.
523 gori_map::maybe_add_gori (tree name
, basic_block bb
)
527 // Check if there is a def chain, regardless of the block.
528 add_def_chain_to_bitmap (m_outgoing
[bb
->index
], name
);
529 // Check for any imports.
530 bitmap imp
= get_imports (name
);
531 // If there were imports, add them so we can recompute
533 bitmap_ior_into (m_incoming
[bb
->index
], imp
);
534 // This name is always an import.
535 if (gimple_bb (SSA_NAME_DEF_STMT (name
)) != bb
)
536 bitmap_set_bit (m_incoming
[bb
->index
], SSA_NAME_VERSION (name
));
538 // Def chain doesn't include itself, and even if there isn't a
539 // def chain, this name should be added to exports.
540 bitmap_set_bit (m_outgoing
[bb
->index
], SSA_NAME_VERSION (name
));
544 // Calculate all the required information for BB.
547 gori_map::calculate_gori (basic_block bb
)
550 if (bb
->index
>= (signed int)m_outgoing
.length ())
552 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
553 m_incoming
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
555 gcc_checking_assert (m_outgoing
[bb
->index
] == NULL
);
556 m_outgoing
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
557 m_incoming
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
559 if (single_succ_p (bb
))
562 // If this block's last statement may generate range informaiton, go
564 gimple
*stmt
= gimple_outgoing_range_stmt_p (bb
);
567 if (is_a
<gcond
*> (stmt
))
569 gcond
*gc
= as_a
<gcond
*>(stmt
);
570 name
= gimple_range_ssa_p (gimple_cond_lhs (gc
));
571 maybe_add_gori (name
, gimple_bb (stmt
));
573 name
= gimple_range_ssa_p (gimple_cond_rhs (gc
));
574 maybe_add_gori (name
, gimple_bb (stmt
));
578 // Do not process switches if they are too large.
579 if (EDGE_COUNT (bb
->succs
) > (unsigned)param_evrp_switch_limit
)
581 gswitch
*gs
= as_a
<gswitch
*>(stmt
);
582 name
= gimple_range_ssa_p (gimple_switch_index (gs
));
583 maybe_add_gori (name
, gimple_bb (stmt
));
585 // Add this bitmap to the aggregate list of all outgoing names.
586 bitmap_ior_into (m_maybe_variant
, m_outgoing
[bb
->index
]);
589 // Dump the table information for BB to file F.
592 gori_map::dump (FILE *f
, basic_block bb
, bool verbose
)
594 // BB was not processed.
595 if (!m_outgoing
[bb
->index
] || bitmap_empty_p (m_outgoing
[bb
->index
]))
600 bitmap imp
= imports (bb
);
601 if (!bitmap_empty_p (imp
))
604 fprintf (f
, "bb<%u> Imports: ",bb
->index
);
606 fprintf (f
, "Imports: ");
607 FOR_EACH_GORI_IMPORT_NAME (*this, bb
, name
)
609 print_generic_expr (f
, name
, TDF_SLIM
);
616 fprintf (f
, "bb<%u> Exports: ",bb
->index
);
618 fprintf (f
, "Exports: ");
619 // Dump the export vector.
620 FOR_EACH_GORI_EXPORT_NAME (*this, bb
, name
)
622 print_generic_expr (f
, name
, TDF_SLIM
);
627 range_def_chain::dump (f
, bb
, " ");
630 // Dump the entire GORI map structure to file F.
633 gori_map::dump (FILE *f
)
636 FOR_EACH_BB_FN (bb
, cfun
)
646 // -------------------------------------------------------------------
648 // Construct a gori_compute object.
650 gori_compute::gori_compute (int not_executable_flag
)
651 : outgoing (param_evrp_switch_limit
), tracer ("GORI ")
653 m_not_executable_flag
= not_executable_flag
;
654 // Create a boolean_type true and false range.
655 m_bool_zero
= int_range
<2> (boolean_false_node
, boolean_false_node
);
656 m_bool_one
= int_range
<2> (boolean_true_node
, boolean_true_node
);
657 if (dump_file
&& (param_ranger_debug
& RANGER_DEBUG_GORI
))
658 tracer
.enable_trace ();
661 // Given the switch S, return an evaluation in R for NAME when the lhs
662 // evaluates to LHS. Returning false means the name being looked for
663 // was not resolvable.
666 gori_compute::compute_operand_range_switch (vrange
&r
, gswitch
*s
,
668 tree name
, fur_source
&src
)
670 tree op1
= gimple_switch_index (s
);
672 // If name matches, the range is simply the range from the edge.
673 // Empty ranges are viral as they are on a path which isn't
675 if (op1
== name
|| lhs
.undefined_p ())
681 // If op1 is in the defintion chain, pass lhs back.
682 if (gimple_range_ssa_p (op1
) && in_chain_p (name
, op1
))
683 return compute_operand_range (r
, SSA_NAME_DEF_STMT (op1
), lhs
, name
, src
);
689 // Return an evaluation for NAME as it would appear in STMT when the
690 // statement's lhs evaluates to LHS. If successful, return TRUE and
691 // store the evaluation in R, otherwise return FALSE.
694 gori_compute::compute_operand_range (vrange
&r
, gimple
*stmt
,
695 const vrange
&lhs
, tree name
,
698 // If the lhs doesn't tell us anything, neither will unwinding further.
699 if (lhs
.varying_p ())
702 // Empty ranges are viral as they are on an unexecutable path.
703 if (lhs
.undefined_p ())
708 if (is_a
<gswitch
*> (stmt
))
709 return compute_operand_range_switch (r
, as_a
<gswitch
*> (stmt
), lhs
, name
,
711 if (!range_op_handler (stmt
))
714 tree op1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
715 tree op2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
717 // Handle end of lookup first.
719 return compute_operand1_range (r
, stmt
, lhs
, name
, src
);
721 return compute_operand2_range (r
, stmt
, lhs
, name
, src
);
723 // NAME is not in this stmt, but one of the names in it ought to be
725 bool op1_in_chain
= op1
&& in_chain_p (name
, op1
);
726 bool op2_in_chain
= op2
&& in_chain_p (name
, op2
);
728 // If neither operand is derived, then this stmt tells us nothing.
729 if (!op1_in_chain
&& !op2_in_chain
)
733 // Process logicals as they have special handling.
734 if (is_gimple_logical_p (stmt
))
737 if ((idx
= tracer
.header ("compute_operand ")))
739 print_generic_expr (dump_file
, name
, TDF_SLIM
);
740 fprintf (dump_file
, " with LHS = ");
741 lhs
.dump (dump_file
);
742 fprintf (dump_file
, " at stmt ");
743 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
746 tree type
= TREE_TYPE (name
);
747 Value_Range
op1_trange (type
), op1_frange (type
);
748 Value_Range
op2_trange (type
), op2_frange (type
);
749 compute_logical_operands (op1_trange
, op1_frange
, stmt
,
751 name
, src
, op1
, op1_in_chain
);
752 compute_logical_operands (op2_trange
, op2_frange
, stmt
,
754 name
, src
, op2
, op2_in_chain
);
755 res
= logical_combine (r
,
756 gimple_expr_code (stmt
),
758 op1_trange
, op1_frange
, op2_trange
, op2_frange
);
760 tracer
.trailer (idx
, "compute_operand", res
, name
, r
);
762 // Follow the appropriate operands now.
763 else if (op1_in_chain
&& op2_in_chain
)
764 res
= compute_operand1_and_operand2_range (r
, stmt
, lhs
, name
, src
);
765 else if (op1_in_chain
)
766 res
= compute_operand1_range (r
, stmt
, lhs
, name
, src
);
767 else if (op2_in_chain
)
768 res
= compute_operand2_range (r
, stmt
, lhs
, name
, src
);
772 // If neither operand is derived, this statement tells us nothing.
777 // Return TRUE if range R is either a true or false compatible range.
780 range_is_either_true_or_false (const irange
&r
)
782 if (r
.undefined_p ())
785 // This is complicated by the fact that Ada has multi-bit booleans,
786 // so true can be ~[0, 0] (i.e. [1,MAX]).
787 tree type
= r
.type ();
788 gcc_checking_assert (range_compatible_p (type
, boolean_type_node
));
789 return (r
.singleton_p () || !r
.contains_p (build_zero_cst (type
)));
792 // Evaluate a binary logical expression by combining the true and
793 // false ranges for each of the operands based on the result value in
797 gori_compute::logical_combine (vrange
&r
, enum tree_code code
,
799 const vrange
&op1_true
, const vrange
&op1_false
,
800 const vrange
&op2_true
, const vrange
&op2_false
)
802 if (op1_true
.varying_p () && op1_false
.varying_p ()
803 && op2_true
.varying_p () && op2_false
.varying_p ())
807 if ((idx
= tracer
.header ("logical_combine")))
813 fprintf (dump_file
, " || ");
817 fprintf (dump_file
, " && ");
822 fprintf (dump_file
, " with LHS = ");
823 lhs
.dump (dump_file
);
824 fputc ('\n', dump_file
);
826 tracer
.print (idx
, "op1_true = ");
827 op1_true
.dump (dump_file
);
828 fprintf (dump_file
, " op1_false = ");
829 op1_false
.dump (dump_file
);
830 fputc ('\n', dump_file
);
831 tracer
.print (idx
, "op2_true = ");
832 op2_true
.dump (dump_file
);
833 fprintf (dump_file
, " op2_false = ");
834 op2_false
.dump (dump_file
);
835 fputc ('\n', dump_file
);
838 // This is not a simple fold of a logical expression, rather it
839 // determines ranges which flow through the logical expression.
841 // Assuming x_8 is an unsigned char, and relational statements:
844 // consider the logical expression and branch:
848 // To determine the range of x_8 on either edge of the branch, one
849 // must first determine what the range of x_8 is when the boolean
850 // values of b_1 and b_2 are both true and false.
851 // b_1 TRUE x_8 = [0, 19]
852 // b_1 FALSE x_8 = [20, 255]
853 // b_2 TRUE x_8 = [6, 255]
854 // b_2 FALSE x_8 = [0,5].
856 // These ranges are then combined based on the expected outcome of
857 // the branch. The range on the TRUE side of the branch must satisfy
858 // b_1 == true && b_2 == true
860 // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
861 // must be true. The range of x_8 on the true side must be the
862 // intersection of both ranges since both must be true. Thus the
863 // range of x_8 on the true side is [6, 19].
865 // To determine the ranges on the FALSE side, all 3 combinations of
866 // failing ranges must be considered, and combined as any of them
867 // can cause the false result.
869 // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
870 // FALSE results and combine them. If we fell back to VARYING any
871 // range restrictions that have been discovered up to this point
873 if (!range_is_either_true_or_false (lhs
))
877 if (logical_combine (r1
, code
, m_bool_zero
, op1_true
, op1_false
,
879 && logical_combine (r
, code
, m_bool_one
, op1_true
, op1_false
,
880 op2_true
, op2_false
))
888 tracer
.trailer (idx
, "logical_combine", res
, NULL_TREE
, r
);
893 // A logical AND combines ranges from 2 boolean conditions.
899 // The TRUE side is the intersection of the 2 true ranges.
901 r
.intersect (op2_true
);
905 // The FALSE side is the union of the other 3 cases.
906 Value_Range
ff (op1_false
);
907 ff
.intersect (op2_false
);
908 Value_Range
tf (op1_true
);
909 tf
.intersect (op2_false
);
910 Value_Range
ft (op1_false
);
911 ft
.intersect (op2_true
);
917 // A logical OR combines ranges from 2 boolean conditons.
923 // An OR operation will only take the FALSE path if both
924 // operands are false simlulateously, which means they should
925 // be intersected. !(x || y) == !x && !y
927 r
.intersect (op2_false
);
931 // The TRUE side of an OR operation will be the union of
932 // the other three combinations.
933 Value_Range
tt (op1_true
);
934 tt
.intersect (op2_true
);
935 Value_Range
tf (op1_true
);
936 tf
.intersect (op2_false
);
937 Value_Range
ft (op1_false
);
938 ft
.intersect (op2_true
);
949 tracer
.trailer (idx
, "logical_combine", true, NULL_TREE
, r
);
954 // Given a logical STMT, calculate true and false ranges for each
955 // potential path of NAME, assuming NAME came through the OP chain if
956 // OP_IN_CHAIN is true.
959 gori_compute::compute_logical_operands (vrange
&true_range
, vrange
&false_range
,
962 tree name
, fur_source
&src
,
963 tree op
, bool op_in_chain
)
965 gimple
*src_stmt
= gimple_range_ssa_p (op
) ? SSA_NAME_DEF_STMT (op
) : NULL
;
966 if (!op_in_chain
|| !src_stmt
|| chain_import_p (gimple_get_lhs (stmt
), op
))
968 // If op is not in the def chain, or defined in this block,
969 // use its known value on entry to the block.
970 src
.get_operand (true_range
, name
);
971 false_range
= true_range
;
973 if ((idx
= tracer
.header ("logical_operand")))
975 print_generic_expr (dump_file
, op
, TDF_SLIM
);
976 fprintf (dump_file
, " not in computation chain. Queried.\n");
977 tracer
.trailer (idx
, "logical_operand", true, NULL_TREE
, true_range
);
982 enum tree_code code
= gimple_expr_code (stmt
);
983 // Optimize [0 = x | y], since neither operand can ever be non-zero.
984 if ((code
== BIT_IOR_EXPR
|| code
== TRUTH_OR_EXPR
) && lhs
.zero_p ())
986 if (!compute_operand_range (false_range
, src_stmt
, m_bool_zero
, name
,
988 src
.get_operand (false_range
, name
);
989 true_range
= false_range
;
993 // Optimize [1 = x & y], since neither operand can ever be zero.
994 if ((code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
) && lhs
== m_bool_one
)
996 if (!compute_operand_range (true_range
, src_stmt
, m_bool_one
, name
, src
))
997 src
.get_operand (true_range
, name
);
998 false_range
= true_range
;
1002 // Calculate ranges for true and false on both sides, since the false
1003 // path is not always a simple inversion of the true side.
1004 if (!compute_operand_range (true_range
, src_stmt
, m_bool_one
, name
, src
))
1005 src
.get_operand (true_range
, name
);
1006 if (!compute_operand_range (false_range
, src_stmt
, m_bool_zero
, name
, src
))
1007 src
.get_operand (false_range
, name
);
1010 // Calculate a range for NAME from the operand 1 position of STMT
1011 // assuming the result of the statement is LHS. Return the range in
1012 // R, or false if no range could be calculated.
1015 gori_compute::compute_operand1_range (vrange
&r
, gimple
*stmt
,
1016 const vrange
&lhs
, tree name
,
1019 tree op1
= gimple_range_operand1 (stmt
);
1020 tree op2
= gimple_range_operand2 (stmt
);
1021 Value_Range
op1_range (TREE_TYPE (op1
));
1022 Value_Range
tmp (TREE_TYPE (op1
));
1023 Value_Range
op2_range (op2
? TREE_TYPE (op2
) : TREE_TYPE (op1
));
1025 // Fetch the known range for op1 in this block.
1026 src
.get_operand (op1_range
, op1
);
1028 // Now range-op calcuate and put that result in r.
1031 src
.get_operand (op2_range
, op2
);
1032 if (!gimple_range_calc_op1 (tmp
, stmt
, lhs
, op2_range
))
1037 // We pass op1_range to the unary operation. Nomally it's a
1038 // hidden range_for_type parameter, but sometimes having the
1039 // actual range can result in better information.
1040 if (!gimple_range_calc_op1 (tmp
, stmt
, lhs
, op1_range
))
1045 if ((idx
= tracer
.header ("compute op 1 (")))
1047 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1048 fprintf (dump_file
, ") at ");
1049 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1050 tracer
.print (idx
, "LHS =");
1051 lhs
.dump (dump_file
);
1052 if (op2
&& TREE_CODE (op2
) == SSA_NAME
)
1054 fprintf (dump_file
, ", ");
1055 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1056 fprintf (dump_file
, " = ");
1057 op2_range
.dump (dump_file
);
1059 fprintf (dump_file
, "\n");
1060 tracer
.print (idx
, "Computes ");
1061 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1062 fprintf (dump_file
, " = ");
1063 tmp
.dump (dump_file
);
1064 fprintf (dump_file
, " intersect Known range : ");
1065 op1_range
.dump (dump_file
);
1066 fputc ('\n', dump_file
);
1068 // Intersect the calculated result with the known result and return if done.
1071 tmp
.intersect (op1_range
);
1074 tracer
.trailer (idx
, "produces ", true, name
, r
);
1077 // If the calculation continues, we're using op1_range as the new LHS.
1078 op1_range
.intersect (tmp
);
1081 tracer
.trailer (idx
, "produces ", true, op1
, op1_range
);
1082 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op1
);
1083 gcc_checking_assert (src_stmt
);
1085 // Then feed this range back as the LHS of the defining statement.
1086 return compute_operand_range (r
, src_stmt
, op1_range
, name
, src
);
1090 // Calculate a range for NAME from the operand 2 position of S
1091 // assuming the result of the statement is LHS. Return the range in
1092 // R, or false if no range could be calculated.
1095 gori_compute::compute_operand2_range (vrange
&r
, gimple
*stmt
,
1096 const vrange
&lhs
, tree name
,
1099 tree op1
= gimple_range_operand1 (stmt
);
1100 tree op2
= gimple_range_operand2 (stmt
);
1101 Value_Range
op1_range (TREE_TYPE (op1
));
1102 Value_Range
op2_range (TREE_TYPE (op2
));
1103 Value_Range
tmp (TREE_TYPE (op2
));
1105 src
.get_operand (op1_range
, op1
);
1106 src
.get_operand (op2_range
, op2
);
1108 // Intersect with range for op2 based on lhs and op1.
1109 if (!gimple_range_calc_op2 (tmp
, stmt
, lhs
, op1_range
))
1113 if ((idx
= tracer
.header ("compute op 2 (")))
1115 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1116 fprintf (dump_file
, ") at ");
1117 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1118 tracer
.print (idx
, "LHS = ");
1119 lhs
.dump (dump_file
);
1120 if (TREE_CODE (op1
) == SSA_NAME
)
1122 fprintf (dump_file
, ", ");
1123 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1124 fprintf (dump_file
, " = ");
1125 op1_range
.dump (dump_file
);
1127 fprintf (dump_file
, "\n");
1128 tracer
.print (idx
, "Computes ");
1129 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1130 fprintf (dump_file
, " = ");
1131 tmp
.dump (dump_file
);
1132 fprintf (dump_file
, " intersect Known range : ");
1133 op2_range
.dump (dump_file
);
1134 fputc ('\n', dump_file
);
1136 // Intersect the calculated result with the known result and return if done.
1139 tmp
.intersect (op2_range
);
1142 tracer
.trailer (idx
, " produces ", true, NULL_TREE
, r
);
1145 // If the calculation continues, we're using op2_range as the new LHS.
1146 op2_range
.intersect (tmp
);
1149 tracer
.trailer (idx
, " produces ", true, op2
, op2_range
);
1150 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op2
);
1151 gcc_checking_assert (src_stmt
);
1152 // gcc_checking_assert (!is_import_p (op2, find.bb));
1154 // Then feed this range back as the LHS of the defining statement.
1155 return compute_operand_range (r
, src_stmt
, op2_range
, name
, src
);
1158 // Calculate a range for NAME from both operand positions of S
1159 // assuming the result of the statement is LHS. Return the range in
1160 // R, or false if no range could be calculated.
1163 gori_compute::compute_operand1_and_operand2_range (vrange
&r
,
1169 Value_Range
op_range (TREE_TYPE (name
));
1171 // Calculate a good a range for op2. Since op1 == op2, this will
1172 // have already included whatever the actual range of name is.
1173 if (!compute_operand2_range (op_range
, stmt
, lhs
, name
, src
))
1176 // Now get the range thru op1.
1177 if (!compute_operand1_range (r
, stmt
, lhs
, name
, src
))
1180 // Both operands have to be simultaneously true, so perform an intersection.
1181 r
.intersect (op_range
);
1185 // Return TRUE if NAME can be recomputed on any edge exiting BB. If any
1186 // direct dependant is exported, it may also change the computed value of NAME.
1189 gori_compute::may_recompute_p (tree name
, basic_block bb
)
1191 tree dep1
= depend1 (name
);
1192 tree dep2
= depend2 (name
);
1194 // If the first dependency is not set, there is no recompuation.
1198 // Don't recalculate PHIs or statements with side_effects.
1199 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1200 if (is_a
<gphi
*> (s
) || gimple_has_side_effects (s
))
1203 // If edge is specified, check if NAME can be recalculated on that edge.
1205 return ((is_export_p (dep1
, bb
))
1206 || (dep2
&& is_export_p (dep2
, bb
)));
1208 return (is_export_p (dep1
)) || (dep2
&& is_export_p (dep2
));
1211 // Return TRUE if NAME can be recomputed on edge E. If any direct dependant
1212 // is exported on edge E, it may change the computed value of NAME.
1215 gori_compute::may_recompute_p (tree name
, edge e
)
1217 gcc_checking_assert (e
);
1218 return may_recompute_p (name
, e
->src
);
1222 // Return TRUE if a range can be calculated or recomputed for NAME on any
1226 gori_compute::has_edge_range_p (tree name
, basic_block bb
)
1228 // Check if NAME is an export or can be recomputed.
1230 return is_export_p (name
, bb
) || may_recompute_p (name
, bb
);
1232 // If no block is specified, check for anywhere in the IL.
1233 return is_export_p (name
) || may_recompute_p (name
);
1236 // Return TRUE if a range can be calculated or recomputed for NAME on edge E.
1239 gori_compute::has_edge_range_p (tree name
, edge e
)
1241 gcc_checking_assert (e
);
1242 return has_edge_range_p (name
, e
->src
);
1245 // Calculate a range on edge E and return it in R. Try to evaluate a
1246 // range for NAME on this edge. Return FALSE if this is either not a
1247 // control edge or NAME is not defined by this edge.
1250 gori_compute::outgoing_edge_range_p (vrange
&r
, edge e
, tree name
,
1255 if ((e
->flags
& m_not_executable_flag
))
1258 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1259 fprintf (dump_file
, "Outgoing edge %d->%d unexecutable.\n",
1260 e
->src
->index
, e
->dest
->index
);
1264 gcc_checking_assert (gimple_range_ssa_p (name
));
1266 // Determine if there is an outgoing edge.
1267 gimple
*stmt
= outgoing
.edge_range_p (lhs
, e
);
1271 fur_stmt
src (stmt
, &q
);
1272 // If NAME can be calculated on the edge, use that.
1273 if (is_export_p (name
, e
->src
))
1276 if ((idx
= tracer
.header ("outgoing_edge")))
1278 fprintf (dump_file
, " for ");
1279 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1280 fprintf (dump_file
, " on edge %d->%d\n",
1281 e
->src
->index
, e
->dest
->index
);
1283 if ((res
= compute_operand_range (r
, stmt
, lhs
, name
, src
)))
1285 // Sometimes compatible types get interchanged. See PR97360.
1286 // Make sure we are returning the type of the thing we asked for.
1287 if (!r
.undefined_p () && r
.type () != TREE_TYPE (name
))
1289 gcc_checking_assert (range_compatible_p (r
.type (),
1291 range_cast (r
, TREE_TYPE (name
));
1295 tracer
.trailer (idx
, "outgoing_edge", res
, name
, r
);
1298 // If NAME isn't exported, check if it can be recomputed.
1299 else if (may_recompute_p (name
, e
))
1301 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1303 if ((idx
= tracer
.header ("recomputation")))
1305 fprintf (dump_file
, " attempt on edge %d->%d for ",
1306 e
->src
->index
, e
->dest
->index
);
1307 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
1309 // Simply calculate DEF_STMT on edge E using the range query Q.
1310 fold_range (r
, def_stmt
, e
, &q
);
1312 tracer
.trailer (idx
, "recomputation", true, name
, r
);
1318 // Given COND ? OP1 : OP2 with ranges R1 for OP1 and R2 for OP2, Use gori
1319 // to further resolve R1 and R2 if there are any dependencies between
1320 // OP1 and COND or OP2 and COND. All values can are to be calculated using SRC
1321 // as the origination source location for operands..
1322 // Effectively, use COND an the edge condition and solve for OP1 on the true
1323 // edge and OP2 on the false edge.
1326 gori_compute::condexpr_adjust (vrange
&r1
, vrange
&r2
, gimple
*, tree cond
,
1327 tree op1
, tree op2
, fur_source
&src
)
1329 tree ssa1
= gimple_range_ssa_p (op1
);
1330 tree ssa2
= gimple_range_ssa_p (op2
);
1333 if (TREE_CODE (cond
) != SSA_NAME
)
1335 gassign
*cond_def
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (cond
));
1337 || TREE_CODE_CLASS (gimple_assign_rhs_code (cond_def
)) != tcc_comparison
)
1339 tree type
= TREE_TYPE (gimple_assign_rhs1 (cond_def
));
1340 if (!range_compatible_p (type
, TREE_TYPE (gimple_assign_rhs2 (cond_def
))))
1342 range_op_handler
hand (gimple_assign_rhs_code (cond_def
), type
);
1346 tree c1
= gimple_range_ssa_p (gimple_assign_rhs1 (cond_def
));
1347 tree c2
= gimple_range_ssa_p (gimple_assign_rhs2 (cond_def
));
1349 // Only solve if there is one SSA name in the condition.
1350 if ((!c1
&& !c2
) || (c1
&& c2
))
1353 // Pick up the current values of each part of the condition.
1354 tree rhs1
= gimple_assign_rhs1 (cond_def
);
1355 tree rhs2
= gimple_assign_rhs2 (cond_def
);
1356 Value_Range
cl (TREE_TYPE (rhs1
));
1357 Value_Range
cr (TREE_TYPE (rhs2
));
1358 src
.get_operand (cl
, rhs1
);
1359 src
.get_operand (cr
, rhs2
);
1361 tree cond_name
= c1
? c1
: c2
;
1362 gimple
*def_stmt
= SSA_NAME_DEF_STMT (cond_name
);
1364 // Evaluate the value of COND_NAME on the true and false edges, using either
1365 // the op1 or op2 routines based on its location.
1366 Value_Range
cond_true (type
), cond_false (type
);
1369 if (!hand
.op1_range (cond_false
, type
, m_bool_zero
, cr
))
1371 if (!hand
.op1_range (cond_true
, type
, m_bool_one
, cr
))
1373 cond_false
.intersect (cl
);
1374 cond_true
.intersect (cl
);
1378 if (!hand
.op2_range (cond_false
, type
, m_bool_zero
, cl
))
1380 if (!hand
.op2_range (cond_true
, type
, m_bool_one
, cl
))
1382 cond_false
.intersect (cr
);
1383 cond_true
.intersect (cr
);
1387 if ((idx
= tracer
.header ("cond_expr evaluation : ")))
1389 fprintf (dump_file
, " range1 = ");
1390 r1
.dump (dump_file
);
1391 fprintf (dump_file
, ", range2 = ");
1392 r1
.dump (dump_file
);
1393 fprintf (dump_file
, "\n");
1396 // Now solve for SSA1 or SSA2 if they are in the dependency chain.
1397 Value_Range
tmp (type
);
1398 if (ssa1
&& in_chain_p (ssa1
, cond_name
))
1400 if (compute_operand_range (tmp
, def_stmt
, cond_true
, ssa1
, src
))
1403 if (ssa2
&& in_chain_p (ssa2
, cond_name
))
1405 if (compute_operand_range (tmp
, def_stmt
, cond_false
, ssa2
, src
))
1410 tracer
.print (idx
, "outgoing: range1 = ");
1411 r1
.dump (dump_file
);
1412 fprintf (dump_file
, ", range2 = ");
1413 r1
.dump (dump_file
);
1414 fprintf (dump_file
, "\n");
1415 tracer
.trailer (idx
, "cond_expr", true, cond_name
, cond_true
);
1420 // Dump what is known to GORI computes to listing file F.
1423 gori_compute::dump (FILE *f
)
1428 // ------------------------------------------------------------------------
1429 // GORI iterator. Although we have bitmap iterators, don't expose that it
1430 // is currently a bitmap. Use an export iterator to hide future changes.
1432 // Construct a basic iterator over an export bitmap.
1434 gori_export_iterator::gori_export_iterator (bitmap b
)
1438 bmp_iter_set_init (&bi
, b
, 1, &y
);
1442 // Move to the next export bitmap spot.
1445 gori_export_iterator::next ()
1447 bmp_iter_next (&bi
, &y
);
1451 // Fetch the name of the next export in the export list. Return NULL if
1452 // iteration is done.
1455 gori_export_iterator::get_name ()
1460 while (bmp_iter_set (&bi
, &y
))
1462 tree t
= ssa_name (y
);