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 // Set or clear the m_maybe_variant bit to determine if ranges will be tracked
503 // for NAME. A clear bit means they will NOT be tracked.
506 gori_map::set_range_invariant (tree name
, bool invariant
)
509 bitmap_clear_bit (m_maybe_variant
, SSA_NAME_VERSION (name
));
511 bitmap_set_bit (m_maybe_variant
, SSA_NAME_VERSION (name
));
514 // Return true if NAME is an import to block BB.
517 gori_map::is_import_p (tree name
, basic_block bb
)
519 // If no BB is specified, test if it is exported anywhere in the IL.
520 return bitmap_bit_p (imports (bb
), SSA_NAME_VERSION (name
));
523 // If NAME is non-NULL and defined in block BB, calculate the def
524 // chain and add it to m_outgoing.
527 gori_map::maybe_add_gori (tree name
, basic_block bb
)
531 // Check if there is a def chain, regardless of the block.
532 add_def_chain_to_bitmap (m_outgoing
[bb
->index
], name
);
533 // Check for any imports.
534 bitmap imp
= get_imports (name
);
535 // If there were imports, add them so we can recompute
537 bitmap_ior_into (m_incoming
[bb
->index
], imp
);
538 // This name is always an import.
539 if (gimple_bb (SSA_NAME_DEF_STMT (name
)) != bb
)
540 bitmap_set_bit (m_incoming
[bb
->index
], SSA_NAME_VERSION (name
));
542 // Def chain doesn't include itself, and even if there isn't a
543 // def chain, this name should be added to exports.
544 bitmap_set_bit (m_outgoing
[bb
->index
], SSA_NAME_VERSION (name
));
548 // Calculate all the required information for BB.
551 gori_map::calculate_gori (basic_block bb
)
554 if (bb
->index
>= (signed int)m_outgoing
.length ())
556 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
557 m_incoming
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
559 gcc_checking_assert (m_outgoing
[bb
->index
] == NULL
);
560 m_outgoing
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
561 m_incoming
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
563 if (single_succ_p (bb
))
566 // If this block's last statement may generate range informaiton, go
568 gimple
*stmt
= gimple_outgoing_range_stmt_p (bb
);
571 if (is_a
<gcond
*> (stmt
))
573 gcond
*gc
= as_a
<gcond
*>(stmt
);
574 name
= gimple_range_ssa_p (gimple_cond_lhs (gc
));
575 maybe_add_gori (name
, gimple_bb (stmt
));
577 name
= gimple_range_ssa_p (gimple_cond_rhs (gc
));
578 maybe_add_gori (name
, gimple_bb (stmt
));
582 // Do not process switches if they are too large.
583 if (EDGE_COUNT (bb
->succs
) > (unsigned)param_evrp_switch_limit
)
585 gswitch
*gs
= as_a
<gswitch
*>(stmt
);
586 name
= gimple_range_ssa_p (gimple_switch_index (gs
));
587 maybe_add_gori (name
, gimple_bb (stmt
));
589 // Add this bitmap to the aggregate list of all outgoing names.
590 bitmap_ior_into (m_maybe_variant
, m_outgoing
[bb
->index
]);
593 // Dump the table information for BB to file F.
596 gori_map::dump (FILE *f
, basic_block bb
, bool verbose
)
598 // BB was not processed.
599 if (!m_outgoing
[bb
->index
] || bitmap_empty_p (m_outgoing
[bb
->index
]))
604 bitmap imp
= imports (bb
);
605 if (!bitmap_empty_p (imp
))
608 fprintf (f
, "bb<%u> Imports: ",bb
->index
);
610 fprintf (f
, "Imports: ");
611 FOR_EACH_GORI_IMPORT_NAME (*this, bb
, name
)
613 print_generic_expr (f
, name
, TDF_SLIM
);
620 fprintf (f
, "bb<%u> Exports: ",bb
->index
);
622 fprintf (f
, "Exports: ");
623 // Dump the export vector.
624 FOR_EACH_GORI_EXPORT_NAME (*this, bb
, name
)
626 print_generic_expr (f
, name
, TDF_SLIM
);
631 range_def_chain::dump (f
, bb
, " ");
634 // Dump the entire GORI map structure to file F.
637 gori_map::dump (FILE *f
)
640 FOR_EACH_BB_FN (bb
, cfun
)
650 // -------------------------------------------------------------------
652 // Construct a gori_compute object.
654 gori_compute::gori_compute (int not_executable_flag
)
655 : outgoing (param_evrp_switch_limit
), tracer ("GORI ")
657 m_not_executable_flag
= not_executable_flag
;
658 // Create a boolean_type true and false range.
659 m_bool_zero
= int_range
<2> (boolean_false_node
, boolean_false_node
);
660 m_bool_one
= int_range
<2> (boolean_true_node
, boolean_true_node
);
661 if (dump_file
&& (param_ranger_debug
& RANGER_DEBUG_GORI
))
662 tracer
.enable_trace ();
665 // Given the switch S, return an evaluation in R for NAME when the lhs
666 // evaluates to LHS. Returning false means the name being looked for
667 // was not resolvable.
670 gori_compute::compute_operand_range_switch (vrange
&r
, gswitch
*s
,
672 tree name
, fur_source
&src
)
674 tree op1
= gimple_switch_index (s
);
676 // If name matches, the range is simply the range from the edge.
677 // Empty ranges are viral as they are on a path which isn't
679 if (op1
== name
|| lhs
.undefined_p ())
685 // If op1 is in the defintion chain, pass lhs back.
686 if (gimple_range_ssa_p (op1
) && in_chain_p (name
, op1
))
687 return compute_operand_range (r
, SSA_NAME_DEF_STMT (op1
), lhs
, name
, src
);
693 // Return an evaluation for NAME as it would appear in STMT when the
694 // statement's lhs evaluates to LHS. If successful, return TRUE and
695 // store the evaluation in R, otherwise return FALSE.
698 gori_compute::compute_operand_range (vrange
&r
, gimple
*stmt
,
699 const vrange
&lhs
, tree name
,
702 // If the lhs doesn't tell us anything, neither will unwinding further.
703 if (lhs
.varying_p ())
706 // Empty ranges are viral as they are on an unexecutable path.
707 if (lhs
.undefined_p ())
712 if (is_a
<gswitch
*> (stmt
))
713 return compute_operand_range_switch (r
, as_a
<gswitch
*> (stmt
), lhs
, name
,
715 if (!range_op_handler (stmt
))
718 tree op1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
719 tree op2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
721 // Handle end of lookup first.
723 return compute_operand1_range (r
, stmt
, lhs
, name
, src
);
725 return compute_operand2_range (r
, stmt
, lhs
, name
, src
);
727 // NAME is not in this stmt, but one of the names in it ought to be
729 bool op1_in_chain
= op1
&& in_chain_p (name
, op1
);
730 bool op2_in_chain
= op2
&& in_chain_p (name
, op2
);
732 // If neither operand is derived, then this stmt tells us nothing.
733 if (!op1_in_chain
&& !op2_in_chain
)
737 // Process logicals as they have special handling.
738 if (is_gimple_logical_p (stmt
))
741 if ((idx
= tracer
.header ("compute_operand ")))
743 print_generic_expr (dump_file
, name
, TDF_SLIM
);
744 fprintf (dump_file
, " with LHS = ");
745 lhs
.dump (dump_file
);
746 fprintf (dump_file
, " at stmt ");
747 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
750 tree type
= TREE_TYPE (name
);
751 Value_Range
op1_trange (type
), op1_frange (type
);
752 Value_Range
op2_trange (type
), op2_frange (type
);
753 compute_logical_operands (op1_trange
, op1_frange
, stmt
,
755 name
, src
, op1
, op1_in_chain
);
756 compute_logical_operands (op2_trange
, op2_frange
, stmt
,
758 name
, src
, op2
, op2_in_chain
);
759 res
= logical_combine (r
,
760 gimple_expr_code (stmt
),
762 op1_trange
, op1_frange
, op2_trange
, op2_frange
);
764 tracer
.trailer (idx
, "compute_operand", res
, name
, r
);
766 // Follow the appropriate operands now.
767 else if (op1_in_chain
&& op2_in_chain
)
768 res
= compute_operand1_and_operand2_range (r
, stmt
, lhs
, name
, src
);
769 else if (op1_in_chain
)
770 res
= compute_operand1_range (r
, stmt
, lhs
, name
, src
);
771 else if (op2_in_chain
)
772 res
= compute_operand2_range (r
, stmt
, lhs
, name
, src
);
776 // If neither operand is derived, this statement tells us nothing.
781 // Return TRUE if range R is either a true or false compatible range.
784 range_is_either_true_or_false (const irange
&r
)
786 if (r
.undefined_p ())
789 // This is complicated by the fact that Ada has multi-bit booleans,
790 // so true can be ~[0, 0] (i.e. [1,MAX]).
791 tree type
= r
.type ();
792 gcc_checking_assert (range_compatible_p (type
, boolean_type_node
));
793 return (r
.singleton_p () || !r
.contains_p (build_zero_cst (type
)));
796 // Evaluate a binary logical expression by combining the true and
797 // false ranges for each of the operands based on the result value in
801 gori_compute::logical_combine (vrange
&r
, enum tree_code code
,
803 const vrange
&op1_true
, const vrange
&op1_false
,
804 const vrange
&op2_true
, const vrange
&op2_false
)
806 if (op1_true
.varying_p () && op1_false
.varying_p ()
807 && op2_true
.varying_p () && op2_false
.varying_p ())
811 if ((idx
= tracer
.header ("logical_combine")))
817 fprintf (dump_file
, " || ");
821 fprintf (dump_file
, " && ");
826 fprintf (dump_file
, " with LHS = ");
827 lhs
.dump (dump_file
);
828 fputc ('\n', dump_file
);
830 tracer
.print (idx
, "op1_true = ");
831 op1_true
.dump (dump_file
);
832 fprintf (dump_file
, " op1_false = ");
833 op1_false
.dump (dump_file
);
834 fputc ('\n', dump_file
);
835 tracer
.print (idx
, "op2_true = ");
836 op2_true
.dump (dump_file
);
837 fprintf (dump_file
, " op2_false = ");
838 op2_false
.dump (dump_file
);
839 fputc ('\n', dump_file
);
842 // This is not a simple fold of a logical expression, rather it
843 // determines ranges which flow through the logical expression.
845 // Assuming x_8 is an unsigned char, and relational statements:
848 // consider the logical expression and branch:
852 // To determine the range of x_8 on either edge of the branch, one
853 // must first determine what the range of x_8 is when the boolean
854 // values of b_1 and b_2 are both true and false.
855 // b_1 TRUE x_8 = [0, 19]
856 // b_1 FALSE x_8 = [20, 255]
857 // b_2 TRUE x_8 = [6, 255]
858 // b_2 FALSE x_8 = [0,5].
860 // These ranges are then combined based on the expected outcome of
861 // the branch. The range on the TRUE side of the branch must satisfy
862 // b_1 == true && b_2 == true
864 // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
865 // must be true. The range of x_8 on the true side must be the
866 // intersection of both ranges since both must be true. Thus the
867 // range of x_8 on the true side is [6, 19].
869 // To determine the ranges on the FALSE side, all 3 combinations of
870 // failing ranges must be considered, and combined as any of them
871 // can cause the false result.
873 // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
874 // FALSE results and combine them. If we fell back to VARYING any
875 // range restrictions that have been discovered up to this point
877 if (!range_is_either_true_or_false (lhs
))
881 if (logical_combine (r1
, code
, m_bool_zero
, op1_true
, op1_false
,
883 && logical_combine (r
, code
, m_bool_one
, op1_true
, op1_false
,
884 op2_true
, op2_false
))
892 tracer
.trailer (idx
, "logical_combine", res
, NULL_TREE
, r
);
897 // A logical AND combines ranges from 2 boolean conditions.
903 // The TRUE side is the intersection of the 2 true ranges.
905 r
.intersect (op2_true
);
909 // The FALSE side is the union of the other 3 cases.
910 Value_Range
ff (op1_false
);
911 ff
.intersect (op2_false
);
912 Value_Range
tf (op1_true
);
913 tf
.intersect (op2_false
);
914 Value_Range
ft (op1_false
);
915 ft
.intersect (op2_true
);
921 // A logical OR combines ranges from 2 boolean conditons.
927 // An OR operation will only take the FALSE path if both
928 // operands are false simlulateously, which means they should
929 // be intersected. !(x || y) == !x && !y
931 r
.intersect (op2_false
);
935 // The TRUE side of an OR operation will be the union of
936 // the other three combinations.
937 Value_Range
tt (op1_true
);
938 tt
.intersect (op2_true
);
939 Value_Range
tf (op1_true
);
940 tf
.intersect (op2_false
);
941 Value_Range
ft (op1_false
);
942 ft
.intersect (op2_true
);
953 tracer
.trailer (idx
, "logical_combine", true, NULL_TREE
, r
);
958 // Given a logical STMT, calculate true and false ranges for each
959 // potential path of NAME, assuming NAME came through the OP chain if
960 // OP_IN_CHAIN is true.
963 gori_compute::compute_logical_operands (vrange
&true_range
, vrange
&false_range
,
966 tree name
, fur_source
&src
,
967 tree op
, bool op_in_chain
)
969 gimple
*src_stmt
= gimple_range_ssa_p (op
) ? SSA_NAME_DEF_STMT (op
) : NULL
;
970 if (!op_in_chain
|| !src_stmt
|| chain_import_p (gimple_get_lhs (stmt
), op
))
972 // If op is not in the def chain, or defined in this block,
973 // use its known value on entry to the block.
974 src
.get_operand (true_range
, name
);
975 false_range
= true_range
;
977 if ((idx
= tracer
.header ("logical_operand")))
979 print_generic_expr (dump_file
, op
, TDF_SLIM
);
980 fprintf (dump_file
, " not in computation chain. Queried.\n");
981 tracer
.trailer (idx
, "logical_operand", true, NULL_TREE
, true_range
);
986 enum tree_code code
= gimple_expr_code (stmt
);
987 // Optimize [0 = x | y], since neither operand can ever be non-zero.
988 if ((code
== BIT_IOR_EXPR
|| code
== TRUTH_OR_EXPR
) && lhs
.zero_p ())
990 if (!compute_operand_range (false_range
, src_stmt
, m_bool_zero
, name
,
992 src
.get_operand (false_range
, name
);
993 true_range
= false_range
;
997 // Optimize [1 = x & y], since neither operand can ever be zero.
998 if ((code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
) && lhs
== m_bool_one
)
1000 if (!compute_operand_range (true_range
, src_stmt
, m_bool_one
, name
, src
))
1001 src
.get_operand (true_range
, name
);
1002 false_range
= true_range
;
1006 // Calculate ranges for true and false on both sides, since the false
1007 // path is not always a simple inversion of the true side.
1008 if (!compute_operand_range (true_range
, src_stmt
, m_bool_one
, name
, src
))
1009 src
.get_operand (true_range
, name
);
1010 if (!compute_operand_range (false_range
, src_stmt
, m_bool_zero
, name
, src
))
1011 src
.get_operand (false_range
, name
);
1014 // Calculate a range for NAME from the operand 1 position of STMT
1015 // assuming the result of the statement is LHS. Return the range in
1016 // R, or false if no range could be calculated.
1019 gori_compute::compute_operand1_range (vrange
&r
, gimple
*stmt
,
1020 const vrange
&lhs
, tree name
,
1023 tree op1
= gimple_range_operand1 (stmt
);
1024 tree op2
= gimple_range_operand2 (stmt
);
1025 Value_Range
op1_range (TREE_TYPE (op1
));
1026 Value_Range
tmp (TREE_TYPE (op1
));
1027 Value_Range
op2_range (op2
? TREE_TYPE (op2
) : TREE_TYPE (op1
));
1029 // Fetch the known range for op1 in this block.
1030 src
.get_operand (op1_range
, op1
);
1032 // Now range-op calcuate and put that result in r.
1035 src
.get_operand (op2_range
, op2
);
1036 if (!gimple_range_calc_op1 (tmp
, stmt
, lhs
, op2_range
))
1041 // We pass op1_range to the unary operation. Nomally it's a
1042 // hidden range_for_type parameter, but sometimes having the
1043 // actual range can result in better information.
1044 if (!gimple_range_calc_op1 (tmp
, stmt
, lhs
, op1_range
))
1049 if ((idx
= tracer
.header ("compute op 1 (")))
1051 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1052 fprintf (dump_file
, ") at ");
1053 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1054 tracer
.print (idx
, "LHS =");
1055 lhs
.dump (dump_file
);
1056 if (op2
&& TREE_CODE (op2
) == SSA_NAME
)
1058 fprintf (dump_file
, ", ");
1059 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1060 fprintf (dump_file
, " = ");
1061 op2_range
.dump (dump_file
);
1063 fprintf (dump_file
, "\n");
1064 tracer
.print (idx
, "Computes ");
1065 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1066 fprintf (dump_file
, " = ");
1067 tmp
.dump (dump_file
);
1068 fprintf (dump_file
, " intersect Known range : ");
1069 op1_range
.dump (dump_file
);
1070 fputc ('\n', dump_file
);
1072 // Intersect the calculated result with the known result and return if done.
1075 tmp
.intersect (op1_range
);
1078 tracer
.trailer (idx
, "produces ", true, name
, r
);
1081 // If the calculation continues, we're using op1_range as the new LHS.
1082 op1_range
.intersect (tmp
);
1085 tracer
.trailer (idx
, "produces ", true, op1
, op1_range
);
1086 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op1
);
1087 gcc_checking_assert (src_stmt
);
1089 // Then feed this range back as the LHS of the defining statement.
1090 return compute_operand_range (r
, src_stmt
, op1_range
, name
, src
);
1094 // Calculate a range for NAME from the operand 2 position of S
1095 // assuming the result of the statement is LHS. Return the range in
1096 // R, or false if no range could be calculated.
1099 gori_compute::compute_operand2_range (vrange
&r
, gimple
*stmt
,
1100 const vrange
&lhs
, tree name
,
1103 tree op1
= gimple_range_operand1 (stmt
);
1104 tree op2
= gimple_range_operand2 (stmt
);
1105 Value_Range
op1_range (TREE_TYPE (op1
));
1106 Value_Range
op2_range (TREE_TYPE (op2
));
1107 Value_Range
tmp (TREE_TYPE (op2
));
1109 src
.get_operand (op1_range
, op1
);
1110 src
.get_operand (op2_range
, op2
);
1112 // Intersect with range for op2 based on lhs and op1.
1113 if (!gimple_range_calc_op2 (tmp
, stmt
, lhs
, op1_range
))
1117 if ((idx
= tracer
.header ("compute op 2 (")))
1119 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1120 fprintf (dump_file
, ") at ");
1121 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1122 tracer
.print (idx
, "LHS = ");
1123 lhs
.dump (dump_file
);
1124 if (TREE_CODE (op1
) == SSA_NAME
)
1126 fprintf (dump_file
, ", ");
1127 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1128 fprintf (dump_file
, " = ");
1129 op1_range
.dump (dump_file
);
1131 fprintf (dump_file
, "\n");
1132 tracer
.print (idx
, "Computes ");
1133 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1134 fprintf (dump_file
, " = ");
1135 tmp
.dump (dump_file
);
1136 fprintf (dump_file
, " intersect Known range : ");
1137 op2_range
.dump (dump_file
);
1138 fputc ('\n', dump_file
);
1140 // Intersect the calculated result with the known result and return if done.
1143 tmp
.intersect (op2_range
);
1146 tracer
.trailer (idx
, " produces ", true, NULL_TREE
, r
);
1149 // If the calculation continues, we're using op2_range as the new LHS.
1150 op2_range
.intersect (tmp
);
1153 tracer
.trailer (idx
, " produces ", true, op2
, op2_range
);
1154 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op2
);
1155 gcc_checking_assert (src_stmt
);
1156 // gcc_checking_assert (!is_import_p (op2, find.bb));
1158 // Then feed this range back as the LHS of the defining statement.
1159 return compute_operand_range (r
, src_stmt
, op2_range
, name
, src
);
1162 // Calculate a range for NAME from both operand positions of S
1163 // assuming the result of the statement is LHS. Return the range in
1164 // R, or false if no range could be calculated.
1167 gori_compute::compute_operand1_and_operand2_range (vrange
&r
,
1173 Value_Range
op_range (TREE_TYPE (name
));
1175 // Calculate a good a range for op2. Since op1 == op2, this will
1176 // have already included whatever the actual range of name is.
1177 if (!compute_operand2_range (op_range
, stmt
, lhs
, name
, src
))
1180 // Now get the range thru op1.
1181 if (!compute_operand1_range (r
, stmt
, lhs
, name
, src
))
1184 // Both operands have to be simultaneously true, so perform an intersection.
1185 r
.intersect (op_range
);
1189 // Return TRUE if NAME can be recomputed on any edge exiting BB. If any
1190 // direct dependant is exported, it may also change the computed value of NAME.
1193 gori_compute::may_recompute_p (tree name
, basic_block bb
)
1195 tree dep1
= depend1 (name
);
1196 tree dep2
= depend2 (name
);
1198 // If the first dependency is not set, there is no recompuation.
1202 // Don't recalculate PHIs or statements with side_effects.
1203 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1204 if (is_a
<gphi
*> (s
) || gimple_has_side_effects (s
))
1207 // If edge is specified, check if NAME can be recalculated on that edge.
1209 return ((is_export_p (dep1
, bb
))
1210 || (dep2
&& is_export_p (dep2
, bb
)));
1212 return (is_export_p (dep1
)) || (dep2
&& is_export_p (dep2
));
1215 // Return TRUE if NAME can be recomputed on edge E. If any direct dependant
1216 // is exported on edge E, it may change the computed value of NAME.
1219 gori_compute::may_recompute_p (tree name
, edge e
)
1221 gcc_checking_assert (e
);
1222 return may_recompute_p (name
, e
->src
);
1226 // Return TRUE if a range can be calculated or recomputed for NAME on any
1230 gori_compute::has_edge_range_p (tree name
, basic_block bb
)
1232 // Check if NAME is an export or can be recomputed.
1234 return is_export_p (name
, bb
) || may_recompute_p (name
, bb
);
1236 // If no block is specified, check for anywhere in the IL.
1237 return is_export_p (name
) || may_recompute_p (name
);
1240 // Return TRUE if a range can be calculated or recomputed for NAME on edge E.
1243 gori_compute::has_edge_range_p (tree name
, edge e
)
1245 gcc_checking_assert (e
);
1246 return has_edge_range_p (name
, e
->src
);
1249 // Calculate a range on edge E and return it in R. Try to evaluate a
1250 // range for NAME on this edge. Return FALSE if this is either not a
1251 // control edge or NAME is not defined by this edge.
1254 gori_compute::outgoing_edge_range_p (vrange
&r
, edge e
, tree name
,
1259 if ((e
->flags
& m_not_executable_flag
))
1262 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1263 fprintf (dump_file
, "Outgoing edge %d->%d unexecutable.\n",
1264 e
->src
->index
, e
->dest
->index
);
1268 gcc_checking_assert (gimple_range_ssa_p (name
));
1270 // Determine if there is an outgoing edge.
1271 gimple
*stmt
= outgoing
.edge_range_p (lhs
, e
);
1275 fur_stmt
src (stmt
, &q
);
1276 // If NAME can be calculated on the edge, use that.
1277 if (is_export_p (name
, e
->src
))
1280 if ((idx
= tracer
.header ("outgoing_edge")))
1282 fprintf (dump_file
, " for ");
1283 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1284 fprintf (dump_file
, " on edge %d->%d\n",
1285 e
->src
->index
, e
->dest
->index
);
1287 if ((res
= compute_operand_range (r
, stmt
, lhs
, name
, src
)))
1289 // Sometimes compatible types get interchanged. See PR97360.
1290 // Make sure we are returning the type of the thing we asked for.
1291 if (!r
.undefined_p () && r
.type () != TREE_TYPE (name
))
1293 gcc_checking_assert (range_compatible_p (r
.type (),
1295 range_cast (r
, TREE_TYPE (name
));
1299 tracer
.trailer (idx
, "outgoing_edge", res
, name
, r
);
1302 // If NAME isn't exported, check if it can be recomputed.
1303 else if (may_recompute_p (name
, e
))
1305 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1307 if ((idx
= tracer
.header ("recomputation")))
1309 fprintf (dump_file
, " attempt on edge %d->%d for ",
1310 e
->src
->index
, e
->dest
->index
);
1311 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
1313 // Simply calculate DEF_STMT on edge E using the range query Q.
1314 fold_range (r
, def_stmt
, e
, &q
);
1316 tracer
.trailer (idx
, "recomputation", true, name
, r
);
1322 // Given COND ? OP1 : OP2 with ranges R1 for OP1 and R2 for OP2, Use gori
1323 // to further resolve R1 and R2 if there are any dependencies between
1324 // OP1 and COND or OP2 and COND. All values can are to be calculated using SRC
1325 // as the origination source location for operands..
1326 // Effectively, use COND an the edge condition and solve for OP1 on the true
1327 // edge and OP2 on the false edge.
1330 gori_compute::condexpr_adjust (vrange
&r1
, vrange
&r2
, gimple
*, tree cond
,
1331 tree op1
, tree op2
, fur_source
&src
)
1333 tree ssa1
= gimple_range_ssa_p (op1
);
1334 tree ssa2
= gimple_range_ssa_p (op2
);
1337 if (TREE_CODE (cond
) != SSA_NAME
)
1339 gassign
*cond_def
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (cond
));
1341 || TREE_CODE_CLASS (gimple_assign_rhs_code (cond_def
)) != tcc_comparison
)
1343 tree type
= TREE_TYPE (gimple_assign_rhs1 (cond_def
));
1344 if (!range_compatible_p (type
, TREE_TYPE (gimple_assign_rhs2 (cond_def
))))
1346 range_op_handler
hand (gimple_assign_rhs_code (cond_def
), type
);
1350 tree c1
= gimple_range_ssa_p (gimple_assign_rhs1 (cond_def
));
1351 tree c2
= gimple_range_ssa_p (gimple_assign_rhs2 (cond_def
));
1353 // Only solve if there is one SSA name in the condition.
1354 if ((!c1
&& !c2
) || (c1
&& c2
))
1357 // Pick up the current values of each part of the condition.
1358 tree rhs1
= gimple_assign_rhs1 (cond_def
);
1359 tree rhs2
= gimple_assign_rhs2 (cond_def
);
1360 Value_Range
cl (TREE_TYPE (rhs1
));
1361 Value_Range
cr (TREE_TYPE (rhs2
));
1362 src
.get_operand (cl
, rhs1
);
1363 src
.get_operand (cr
, rhs2
);
1365 tree cond_name
= c1
? c1
: c2
;
1366 gimple
*def_stmt
= SSA_NAME_DEF_STMT (cond_name
);
1368 // Evaluate the value of COND_NAME on the true and false edges, using either
1369 // the op1 or op2 routines based on its location.
1370 Value_Range
cond_true (type
), cond_false (type
);
1373 if (!hand
.op1_range (cond_false
, type
, m_bool_zero
, cr
))
1375 if (!hand
.op1_range (cond_true
, type
, m_bool_one
, cr
))
1377 cond_false
.intersect (cl
);
1378 cond_true
.intersect (cl
);
1382 if (!hand
.op2_range (cond_false
, type
, m_bool_zero
, cl
))
1384 if (!hand
.op2_range (cond_true
, type
, m_bool_one
, cl
))
1386 cond_false
.intersect (cr
);
1387 cond_true
.intersect (cr
);
1391 if ((idx
= tracer
.header ("cond_expr evaluation : ")))
1393 fprintf (dump_file
, " range1 = ");
1394 r1
.dump (dump_file
);
1395 fprintf (dump_file
, ", range2 = ");
1396 r1
.dump (dump_file
);
1397 fprintf (dump_file
, "\n");
1400 // Now solve for SSA1 or SSA2 if they are in the dependency chain.
1401 Value_Range
tmp (type
);
1402 if (ssa1
&& in_chain_p (ssa1
, cond_name
))
1404 if (compute_operand_range (tmp
, def_stmt
, cond_true
, ssa1
, src
))
1407 if (ssa2
&& in_chain_p (ssa2
, cond_name
))
1409 if (compute_operand_range (tmp
, def_stmt
, cond_false
, ssa2
, src
))
1414 tracer
.print (idx
, "outgoing: range1 = ");
1415 r1
.dump (dump_file
);
1416 fprintf (dump_file
, ", range2 = ");
1417 r1
.dump (dump_file
);
1418 fprintf (dump_file
, "\n");
1419 tracer
.trailer (idx
, "cond_expr", true, cond_name
, cond_true
);
1424 // Dump what is known to GORI computes to listing file F.
1427 gori_compute::dump (FILE *f
)
1432 // ------------------------------------------------------------------------
1433 // GORI iterator. Although we have bitmap iterators, don't expose that it
1434 // is currently a bitmap. Use an export iterator to hide future changes.
1436 // Construct a basic iterator over an export bitmap.
1438 gori_export_iterator::gori_export_iterator (bitmap b
)
1442 bmp_iter_set_init (&bi
, b
, 1, &y
);
1446 // Move to the next export bitmap spot.
1449 gori_export_iterator::next ()
1451 bmp_iter_next (&bi
, &y
);
1455 // Fetch the name of the next export in the export list. Return NULL if
1456 // iteration is done.
1459 gori_export_iterator::get_name ()
1464 while (bmp_iter_set (&bi
, &y
))
1466 tree t
= ssa_name (y
);