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);
41 // An empty range is viral.
42 tree type
= TREE_TYPE (gimple_range_operand1 (stmt
));
43 if (lhs_range
.undefined_p ())
48 // Unary operations require the type of the first operand in the
49 // second range position.
50 int_range
<2> type_range (type
);
51 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
55 // Calculate what we can determine of the range of this statement's
56 // first operand if the lhs of the expression has the range LHS_RANGE
57 // and the second operand has the range OP2_RANGE. Return false if
58 // nothing can be determined.
61 gimple_range_calc_op1 (irange
&r
, const gimple
*stmt
,
62 const irange
&lhs_range
, const irange
&op2_range
)
64 // Unary operation are allowed to pass a range in for second operand
65 // as there are often additional restrictions beyond the type which
66 // can be imposed. See operator_cast::op1_range().
67 tree type
= TREE_TYPE (gimple_range_operand1 (stmt
));
68 // An empty range is viral.
69 if (op2_range
.undefined_p () || lhs_range
.undefined_p ())
74 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
78 // Calculate what we can determine of the range of this statement's
79 // second operand if the lhs of the expression has the range LHS_RANGE
80 // and the first operand has the range OP1_RANGE. Return false if
81 // nothing can be determined.
84 gimple_range_calc_op2 (irange
&r
, const gimple
*stmt
,
85 const irange
&lhs_range
, const irange
&op1_range
)
87 tree type
= TREE_TYPE (gimple_range_operand2 (stmt
));
88 // An empty range is viral.
89 if (op1_range
.undefined_p () || lhs_range
.undefined_p ())
94 return gimple_range_handler (stmt
)->op2_range (r
, type
, lhs_range
,
98 // Return TRUE if GS is a logical && or || expression.
101 is_gimple_logical_p (const gimple
*gs
)
103 // Look for boolean and/or condition.
104 if (is_gimple_assign (gs
))
105 switch (gimple_expr_code (gs
))
113 // Bitwise operations on single bits are logical too.
114 if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs
)),
125 /* RANGE_DEF_CHAIN is used to determine which SSA names in a block can
126 have range information calculated for them, and what the
127 dependencies on each other are.
129 Information for a basic block is calculated once and stored. It is
130 only calculated the first time a query is made, so if no queries
131 are made, there is little overhead.
133 The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set
134 within this bitmap to indicate SSA names that are defined in the
135 SAME block and used to calculate this SSA name.
149 This dump indicates the bits set in the def_chain vector.
150 as well as demonstrates the def_chain bits for the related ssa_names.
152 Checking the chain for _2 indicates that _1 and x_4 are used in
155 Def chains also only include statements which are valid gimple
156 so a def chain will only span statements for which the range
157 engine implements operations for. */
160 // Construct a range_def_chain.
162 range_def_chain::range_def_chain ()
164 bitmap_obstack_initialize (&m_bitmaps
);
165 m_def_chain
.create (0);
166 m_def_chain
.safe_grow_cleared (num_ssa_names
);
170 // Destruct a range_def_chain.
172 range_def_chain::~range_def_chain ()
174 m_def_chain
.release ();
175 bitmap_obstack_release (&m_bitmaps
);
178 // Return true if NAME is in the def chain of DEF. If BB is provided,
179 // only return true if the defining statement of DEF is in BB.
182 range_def_chain::in_chain_p (tree name
, tree def
)
184 gcc_checking_assert (gimple_range_ssa_p (def
));
185 gcc_checking_assert (gimple_range_ssa_p (name
));
187 // Get the defintion chain for DEF.
188 bitmap chain
= get_def_chain (def
);
192 return bitmap_bit_p (chain
, SSA_NAME_VERSION (name
));
195 // Add either IMP or the import list B to the import set of DATA.
198 range_def_chain::set_import (struct rdc
&data
, tree imp
, bitmap b
)
200 // If there are no imports, just return
201 if (imp
== NULL_TREE
&& !b
)
204 data
.m_import
= BITMAP_ALLOC (&m_bitmaps
);
205 if (imp
!= NULL_TREE
)
206 bitmap_set_bit (data
.m_import
, SSA_NAME_VERSION (imp
));
208 bitmap_ior_into (data
.m_import
, b
);
211 // Return the import list for NAME.
214 range_def_chain::get_imports (tree name
)
216 if (!has_def_chain (name
))
217 get_def_chain (name
);
218 bitmap i
= m_def_chain
[SSA_NAME_VERSION (name
)].m_import
;
219 // Either this is a default def, OR imports must be a subset of exports.
220 gcc_checking_assert (!get_def_chain (name
) || !i
221 || !bitmap_intersect_compl_p (i
, get_def_chain (name
)));
225 // Return true if IMPORT is an import to NAMEs def chain.
228 range_def_chain::chain_import_p (tree name
, tree import
)
230 bitmap b
= get_imports (name
);
232 return bitmap_bit_p (b
, SSA_NAME_VERSION (import
));
236 // Build def_chains for NAME if it is in BB. Copy the def chain into RESULT.
239 range_def_chain::register_dependency (tree name
, tree dep
, basic_block bb
)
241 if (!gimple_range_ssa_p (dep
))
244 unsigned v
= SSA_NAME_VERSION (name
);
245 if (v
>= m_def_chain
.length ())
246 m_def_chain
.safe_grow_cleared (num_ssa_names
+ 1);
247 struct rdc
&src
= m_def_chain
[v
];
248 gimple
*def_stmt
= SSA_NAME_DEF_STMT (dep
);
249 unsigned dep_v
= SSA_NAME_VERSION (dep
);
252 // Set the direct dependency cache entries.
255 else if (!src
.ssa2
&& src
.ssa1
!= dep
)
258 // Don't calculate imports or export/dep chains if BB is not provided.
259 // This is usually the case for when the temporal cache wants the direct
260 // dependencies of a stmt.
265 src
.bm
= BITMAP_ALLOC (&m_bitmaps
);
267 // Add this operand into the result.
268 bitmap_set_bit (src
.bm
, dep_v
);
270 if (gimple_bb (def_stmt
) == bb
&& !is_a
<gphi
*>(def_stmt
))
272 // Get the def chain for the operand.
273 b
= get_def_chain (dep
);
274 // If there was one, copy it into result.
276 bitmap_ior_into (src
.bm
, b
);
277 // And copy the import list.
278 set_import (src
, NULL_TREE
, get_imports (dep
));
281 // Originated outside the block, so it is an import.
282 set_import (src
, dep
, NULL
);
286 range_def_chain::def_chain_in_bitmap_p (tree name
, bitmap b
)
288 bitmap a
= get_def_chain (name
);
290 return bitmap_intersect_p (a
, b
);
295 range_def_chain::add_def_chain_to_bitmap (bitmap b
, tree name
)
297 bitmap r
= get_def_chain (name
);
299 bitmap_ior_into (b
, r
);
303 // Return TRUE if NAME has been processed for a def_chain.
306 range_def_chain::has_def_chain (tree name
)
308 // Ensure there is an entry in the internal vector.
309 unsigned v
= SSA_NAME_VERSION (name
);
310 if (v
>= m_def_chain
.length ())
311 m_def_chain
.safe_grow_cleared (num_ssa_names
+ 1);
312 return (m_def_chain
[v
].ssa1
!= 0);
317 // Calculate the def chain for NAME and all of its dependent
318 // operands. Only using names in the same BB. Return the bitmap of
319 // all names in the m_def_chain. This only works for supported range
323 range_def_chain::get_def_chain (tree name
)
325 tree ssa1
, ssa2
, ssa3
;
326 unsigned v
= SSA_NAME_VERSION (name
);
327 bool is_logical
= false;
329 // If it has already been processed, just return the cached value.
330 if (has_def_chain (name
))
331 return m_def_chain
[v
].bm
;
333 // No definition chain for default defs.
334 if (SSA_NAME_IS_DEFAULT_DEF (name
))
336 // A Default def is always an import.
337 set_import (m_def_chain
[v
], name
, NULL
);
341 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
342 if (gimple_range_handler (stmt
))
344 is_logical
= is_gimple_logical_p (stmt
);
345 // Terminate the def chains if we see too many cascading logical stmts.
348 if (m_logical_depth
== param_ranger_logical_depth
)
353 ssa1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
354 ssa2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
357 else if (is_a
<gassign
*> (stmt
)
358 && gimple_assign_rhs_code (stmt
) == COND_EXPR
)
360 gassign
*st
= as_a
<gassign
*> (stmt
);
361 ssa1
= gimple_range_ssa_p (gimple_assign_rhs1 (st
));
362 ssa2
= gimple_range_ssa_p (gimple_assign_rhs2 (st
));
363 ssa3
= gimple_range_ssa_p (gimple_assign_rhs3 (st
));
367 // Stmts not understood are always imports.
368 set_import (m_def_chain
[v
], name
, NULL
);
372 register_dependency (name
, ssa1
, gimple_bb (stmt
));
373 register_dependency (name
, ssa2
, gimple_bb (stmt
));
374 register_dependency (name
, ssa3
, gimple_bb (stmt
));
375 // Stmts with no understandable operands are also imports.
376 if (!ssa1
&& !ssa2
& !ssa3
)
377 set_import (m_def_chain
[v
], name
, NULL
);
382 return m_def_chain
[v
].bm
;
385 // Dump what we know for basic block BB to file F.
388 range_def_chain::dump (FILE *f
, basic_block bb
, const char *prefix
)
393 // Dump the def chain for each SSA_NAME defined in BB.
394 for (x
= 1; x
< num_ssa_names
; x
++)
396 tree name
= ssa_name (x
);
399 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
400 if (!stmt
|| (bb
&& gimple_bb (stmt
) != bb
))
402 bitmap chain
= (has_def_chain (name
) ? get_def_chain (name
) : NULL
);
403 if (chain
&& !bitmap_empty_p (chain
))
406 print_generic_expr (f
, name
, TDF_SLIM
);
409 bitmap imports
= get_imports (name
);
410 EXECUTE_IF_SET_IN_BITMAP (chain
, 0, y
, bi
)
412 print_generic_expr (f
, ssa_name (y
), TDF_SLIM
);
413 if (imports
&& bitmap_bit_p (imports
, y
))
423 // -------------------------------------------------------------------
425 /* GORI_MAP is used to accumulate what SSA names in a block can
426 generate range information, and provides tools for the block ranger
427 to enable it to efficiently calculate these ranges.
429 GORI stands for "Generates Outgoing Range Information."
431 It utilizes the range_def_chain class to contruct def_chains.
432 Information for a basic block is calculated once and stored. It is
433 only calculated the first time a query is made. If no queries are
434 made, there is little overhead.
436 one bitmap is maintained for each basic block:
437 m_outgoing : a set bit indicates a range can be generated for a name.
439 Generally speaking, the m_outgoing vector is the union of the
440 entire def_chain of all SSA names used in the last statement of the
441 block which generate ranges. */
444 // Initialize a gori-map structure.
446 gori_map::gori_map ()
448 m_outgoing
.create (0);
449 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
450 m_incoming
.create (0);
451 m_incoming
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
452 m_maybe_variant
= BITMAP_ALLOC (&m_bitmaps
);
455 // Free any memory the GORI map allocated.
457 gori_map::~gori_map ()
459 m_incoming
.release ();
460 m_outgoing
.release ();
463 // Return the bitmap vector of all export from BB. Calculate if necessary.
466 gori_map::exports (basic_block bb
)
468 if (bb
->index
>= (signed int)m_outgoing
.length () || !m_outgoing
[bb
->index
])
470 return m_outgoing
[bb
->index
];
473 // Return the bitmap vector of all imports to BB. Calculate if necessary.
476 gori_map::imports (basic_block bb
)
478 if (bb
->index
>= (signed int)m_outgoing
.length () || !m_outgoing
[bb
->index
])
480 return m_incoming
[bb
->index
];
483 // Return true if NAME is can have ranges generated for it from basic
487 gori_map::is_export_p (tree name
, basic_block bb
)
489 // If no BB is specified, test if it is exported anywhere in the IL.
491 return bitmap_bit_p (m_maybe_variant
, SSA_NAME_VERSION (name
));
492 return bitmap_bit_p (exports (bb
), SSA_NAME_VERSION (name
));
495 // Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
498 gori_map::set_range_invariant (tree name
)
500 bitmap_clear_bit (m_maybe_variant
, SSA_NAME_VERSION (name
));
503 // Return true if NAME is an import to block BB.
506 gori_map::is_import_p (tree name
, basic_block bb
)
508 // If no BB is specified, test if it is exported anywhere in the IL.
509 return bitmap_bit_p (imports (bb
), SSA_NAME_VERSION (name
));
512 // If NAME is non-NULL and defined in block BB, calculate the def
513 // chain and add it to m_outgoing.
516 gori_map::maybe_add_gori (tree name
, basic_block bb
)
520 // Check if there is a def chain, regardless of the block.
521 add_def_chain_to_bitmap (m_outgoing
[bb
->index
], name
);
522 // Check for any imports.
523 bitmap imp
= get_imports (name
);
524 // If there were imports, add them so we can recompute
526 bitmap_ior_into (m_incoming
[bb
->index
], imp
);
527 // This name is always an import.
528 if (gimple_bb (SSA_NAME_DEF_STMT (name
)) != bb
)
529 bitmap_set_bit (m_incoming
[bb
->index
], SSA_NAME_VERSION (name
));
531 // Def chain doesn't include itself, and even if there isn't a
532 // def chain, this name should be added to exports.
533 bitmap_set_bit (m_outgoing
[bb
->index
], SSA_NAME_VERSION (name
));
537 // Calculate all the required information for BB.
540 gori_map::calculate_gori (basic_block bb
)
543 if (bb
->index
>= (signed int)m_outgoing
.length ())
545 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
546 m_incoming
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
548 gcc_checking_assert (m_outgoing
[bb
->index
] == NULL
);
549 m_outgoing
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
550 m_incoming
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
552 // If this block's last statement may generate range informaiton, go
554 gimple
*stmt
= gimple_outgoing_range_stmt_p (bb
);
557 if (is_a
<gcond
*> (stmt
))
559 gcond
*gc
= as_a
<gcond
*>(stmt
);
560 name
= gimple_range_ssa_p (gimple_cond_lhs (gc
));
561 maybe_add_gori (name
, gimple_bb (stmt
));
563 name
= gimple_range_ssa_p (gimple_cond_rhs (gc
));
564 maybe_add_gori (name
, gimple_bb (stmt
));
568 // Do not process switches if they are too large.
569 if (EDGE_COUNT (bb
->succs
) > (unsigned)param_evrp_switch_limit
)
571 gswitch
*gs
= as_a
<gswitch
*>(stmt
);
572 name
= gimple_range_ssa_p (gimple_switch_index (gs
));
573 maybe_add_gori (name
, gimple_bb (stmt
));
575 // Add this bitmap to the aggregate list of all outgoing names.
576 bitmap_ior_into (m_maybe_variant
, m_outgoing
[bb
->index
]);
579 // Dump the table information for BB to file F.
582 gori_map::dump (FILE *f
, basic_block bb
, bool verbose
)
584 // BB was not processed.
585 if (!m_outgoing
[bb
->index
] || bitmap_empty_p (m_outgoing
[bb
->index
]))
590 bitmap imp
= imports (bb
);
591 if (!bitmap_empty_p (imp
))
594 fprintf (f
, "bb<%u> Imports: ",bb
->index
);
596 fprintf (f
, "Imports: ");
597 FOR_EACH_GORI_IMPORT_NAME (*this, bb
, name
)
599 print_generic_expr (f
, name
, TDF_SLIM
);
606 fprintf (f
, "bb<%u> Exports: ",bb
->index
);
608 fprintf (f
, "Exports: ");
609 // Dump the export vector.
610 FOR_EACH_GORI_EXPORT_NAME (*this, bb
, name
)
612 print_generic_expr (f
, name
, TDF_SLIM
);
617 range_def_chain::dump (f
, bb
, " ");
620 // Dump the entire GORI map structure to file F.
623 gori_map::dump (FILE *f
)
626 FOR_EACH_BB_FN (bb
, cfun
)
636 // -------------------------------------------------------------------
638 // Construct a gori_compute object.
640 gori_compute::gori_compute (int not_executable_flag
)
641 : outgoing (param_evrp_switch_limit
), tracer ("GORI ")
643 m_not_executable_flag
= not_executable_flag
;
644 // Create a boolean_type true and false range.
645 m_bool_zero
= int_range
<2> (boolean_false_node
, boolean_false_node
);
646 m_bool_one
= int_range
<2> (boolean_true_node
, boolean_true_node
);
647 if (dump_file
&& (param_evrp_mode
& EVRP_MODE_GORI
))
648 tracer
.enable_trace ();
651 // Given the switch S, return an evaluation in R for NAME when the lhs
652 // evaluates to LHS. Returning false means the name being looked for
653 // was not resolvable.
656 gori_compute::compute_operand_range_switch (irange
&r
, gswitch
*s
,
658 tree name
, fur_source
&src
)
660 tree op1
= gimple_switch_index (s
);
662 // If name matches, the range is simply the range from the edge.
663 // Empty ranges are viral as they are on a path which isn't
665 if (op1
== name
|| lhs
.undefined_p ())
671 // If op1 is in the defintion chain, pass lhs back.
672 if (gimple_range_ssa_p (op1
) && in_chain_p (name
, op1
))
673 return compute_operand_range (r
, SSA_NAME_DEF_STMT (op1
), lhs
, name
, src
);
679 // Return an evaluation for NAME as it would appear in STMT when the
680 // statement's lhs evaluates to LHS. If successful, return TRUE and
681 // store the evaluation in R, otherwise return FALSE.
684 gori_compute::compute_operand_range (irange
&r
, gimple
*stmt
,
685 const irange
&lhs
, tree name
,
688 // If the lhs doesn't tell us anything, neither will unwinding further.
689 if (lhs
.varying_p ())
692 // Empty ranges are viral as they are on an unexecutable path.
693 if (lhs
.undefined_p ())
698 if (is_a
<gswitch
*> (stmt
))
699 return compute_operand_range_switch (r
, as_a
<gswitch
*> (stmt
), lhs
, name
,
701 if (!gimple_range_handler (stmt
))
704 tree op1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
705 tree op2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
707 // Handle end of lookup first.
709 return compute_operand1_range (r
, stmt
, lhs
, name
, src
);
711 return compute_operand2_range (r
, stmt
, lhs
, name
, src
);
713 // NAME is not in this stmt, but one of the names in it ought to be
715 bool op1_in_chain
= op1
&& in_chain_p (name
, op1
);
716 bool op2_in_chain
= op2
&& in_chain_p (name
, op2
);
718 // If neither operand is derived, then this stmt tells us nothing.
719 if (!op1_in_chain
&& !op2_in_chain
)
723 // Process logicals as they have special handling.
724 if (is_gimple_logical_p (stmt
))
727 if ((idx
= tracer
.header ("compute_operand ")))
729 print_generic_expr (dump_file
, name
, TDF_SLIM
);
730 fprintf (dump_file
, " with LHS = ");
731 lhs
.dump (dump_file
);
732 fprintf (dump_file
, " at stmt ");
733 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
736 int_range_max op1_trange
, op1_frange
;
737 int_range_max op2_trange
, op2_frange
;
738 compute_logical_operands (op1_trange
, op1_frange
, stmt
, lhs
,
739 name
, src
, op1
, op1_in_chain
);
740 compute_logical_operands (op2_trange
, op2_frange
, stmt
, lhs
,
741 name
, src
, op2
, op2_in_chain
);
742 res
= logical_combine (r
, gimple_expr_code (stmt
), lhs
,
743 op1_trange
, op1_frange
, op2_trange
, op2_frange
);
745 tracer
.trailer (idx
, "compute_operand", res
, name
, r
);
747 // Follow the appropriate operands now.
748 else if (op1_in_chain
&& op2_in_chain
)
749 res
= compute_operand1_and_operand2_range (r
, stmt
, lhs
, name
, src
);
750 else if (op1_in_chain
)
751 res
= compute_operand1_range (r
, stmt
, lhs
, name
, src
);
752 else if (op2_in_chain
)
753 res
= compute_operand2_range (r
, stmt
, lhs
, name
, src
);
757 // If neither operand is derived, this statement tells us nothing.
762 // Return TRUE if range R is either a true or false compatible range.
765 range_is_either_true_or_false (const irange
&r
)
767 if (r
.undefined_p ())
770 // This is complicated by the fact that Ada has multi-bit booleans,
771 // so true can be ~[0, 0] (i.e. [1,MAX]).
772 tree type
= r
.type ();
773 gcc_checking_assert (range_compatible_p (type
, boolean_type_node
));
774 return (r
.singleton_p () || !r
.contains_p (build_zero_cst (type
)));
777 // Evaluate a binary logical expression by combining the true and
778 // false ranges for each of the operands based on the result value in
782 gori_compute::logical_combine (irange
&r
, enum tree_code code
,
784 const irange
&op1_true
, const irange
&op1_false
,
785 const irange
&op2_true
, const irange
&op2_false
)
787 if (op1_true
.varying_p () && op1_false
.varying_p ()
788 && op2_true
.varying_p () && op2_false
.varying_p ())
792 if ((idx
= tracer
.header ("logical_combine")))
798 fprintf (dump_file
, " || ");
802 fprintf (dump_file
, " && ");
807 fprintf (dump_file
, " with LHS = ");
808 lhs
.dump (dump_file
);
809 fputc ('\n', dump_file
);
811 tracer
.print (idx
, "op1_true = ");
812 op1_true
.dump (dump_file
);
813 fprintf (dump_file
, " op1_false = ");
814 op1_false
.dump (dump_file
);
815 fputc ('\n', dump_file
);
816 tracer
.print (idx
, "op2_true = ");
817 op2_true
.dump (dump_file
);
818 fprintf (dump_file
, " op2_false = ");
819 op2_false
.dump (dump_file
);
820 fputc ('\n', dump_file
);
823 // This is not a simple fold of a logical expression, rather it
824 // determines ranges which flow through the logical expression.
826 // Assuming x_8 is an unsigned char, and relational statements:
829 // consider the logical expression and branch:
833 // To determine the range of x_8 on either edge of the branch, one
834 // must first determine what the range of x_8 is when the boolean
835 // values of b_1 and b_2 are both true and false.
836 // b_1 TRUE x_8 = [0, 19]
837 // b_1 FALSE x_8 = [20, 255]
838 // b_2 TRUE x_8 = [6, 255]
839 // b_2 FALSE x_8 = [0,5].
841 // These ranges are then combined based on the expected outcome of
842 // the branch. The range on the TRUE side of the branch must satisfy
843 // b_1 == true && b_2 == true
845 // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
846 // must be true. The range of x_8 on the true side must be the
847 // intersection of both ranges since both must be true. Thus the
848 // range of x_8 on the true side is [6, 19].
850 // To determine the ranges on the FALSE side, all 3 combinations of
851 // failing ranges must be considered, and combined as any of them
852 // can cause the false result.
854 // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
855 // FALSE results and combine them. If we fell back to VARYING any
856 // range restrictions that have been discovered up to this point
858 if (!range_is_either_true_or_false (lhs
))
862 if (logical_combine (r1
, code
, m_bool_zero
, op1_true
, op1_false
,
864 && logical_combine (r
, code
, m_bool_one
, op1_true
, op1_false
,
865 op2_true
, op2_false
))
873 tracer
.trailer (idx
, "logical_combine", res
, NULL_TREE
, r
);
878 // A logical AND combines ranges from 2 boolean conditions.
884 // The TRUE side is the intersection of the the 2 true ranges.
886 r
.intersect (op2_true
);
890 // The FALSE side is the union of the other 3 cases.
891 int_range_max
ff (op1_false
);
892 ff
.intersect (op2_false
);
893 int_range_max
tf (op1_true
);
894 tf
.intersect (op2_false
);
895 int_range_max
ft (op1_false
);
896 ft
.intersect (op2_true
);
902 // A logical OR combines ranges from 2 boolean conditons.
908 // An OR operation will only take the FALSE path if both
909 // operands are false simlulateously, which means they should
910 // be intersected. !(x || y) == !x && !y
912 r
.intersect (op2_false
);
916 // The TRUE side of an OR operation will be the union of
917 // the other three combinations.
918 int_range_max
tt (op1_true
);
919 tt
.intersect (op2_true
);
920 int_range_max
tf (op1_true
);
921 tf
.intersect (op2_false
);
922 int_range_max
ft (op1_false
);
923 ft
.intersect (op2_true
);
934 tracer
.trailer (idx
, "logical_combine", true, NULL_TREE
, r
);
939 // Given a logical STMT, calculate true and false ranges for each
940 // potential path of NAME, assuming NAME came through the OP chain if
941 // OP_IN_CHAIN is true.
944 gori_compute::compute_logical_operands (irange
&true_range
, irange
&false_range
,
947 tree name
, fur_source
&src
,
948 tree op
, bool op_in_chain
)
950 gimple
*src_stmt
= gimple_range_ssa_p (op
) ? SSA_NAME_DEF_STMT (op
) : NULL
;
951 if (!op_in_chain
|| !src_stmt
|| chain_import_p (gimple_get_lhs (stmt
), op
))
953 // If op is not in the def chain, or defined in this block,
954 // use its known value on entry to the block.
955 src
.get_operand (true_range
, name
);
956 false_range
= true_range
;
958 if ((idx
= tracer
.header ("logical_operand")))
960 print_generic_expr (dump_file
, op
, TDF_SLIM
);
961 fprintf (dump_file
, " not in computation chain. Queried.\n");
962 tracer
.trailer (idx
, "logical_operand", true, NULL_TREE
, true_range
);
967 enum tree_code code
= gimple_expr_code (stmt
);
968 // Optimize [0 = x | y], since neither operand can ever be non-zero.
969 if ((code
== BIT_IOR_EXPR
|| code
== TRUTH_OR_EXPR
) && lhs
.zero_p ())
971 if (!compute_operand_range (false_range
, src_stmt
, m_bool_zero
, name
,
973 src
.get_operand (false_range
, name
);
974 true_range
= false_range
;
978 // Optimize [1 = x & y], since neither operand can ever be zero.
979 if ((code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
) && lhs
== m_bool_one
)
981 if (!compute_operand_range (true_range
, src_stmt
, m_bool_one
, name
, src
))
982 src
.get_operand (true_range
, name
);
983 false_range
= true_range
;
987 // Calculate ranges for true and false on both sides, since the false
988 // path is not always a simple inversion of the true side.
989 if (!compute_operand_range (true_range
, src_stmt
, m_bool_one
, name
, src
))
990 src
.get_operand (true_range
, name
);
991 if (!compute_operand_range (false_range
, src_stmt
, m_bool_zero
, name
, src
))
992 src
.get_operand (false_range
, name
);
995 // Calculate a range for NAME from the operand 1 position of STMT
996 // assuming the result of the statement is LHS. Return the range in
997 // R, or false if no range could be calculated.
1000 gori_compute::compute_operand1_range (irange
&r
, gimple
*stmt
,
1001 const irange
&lhs
, tree name
,
1004 int_range_max op1_range
, op2_range
;
1005 tree op1
= gimple_range_operand1 (stmt
);
1006 tree op2
= gimple_range_operand2 (stmt
);
1008 // Fetch the known range for op1 in this block.
1009 src
.get_operand (op1_range
, op1
);
1011 // Now range-op calcuate and put that result in r.
1014 src
.get_operand (op2_range
, op2
);
1015 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op2_range
))
1020 // We pass op1_range to the unary operation. Nomally it's a
1021 // hidden range_for_type parameter, but sometimes having the
1022 // actual range can result in better information.
1023 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op1_range
))
1028 if ((idx
= tracer
.header ("compute op 1 (")))
1030 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1031 fprintf (dump_file
, ") at ");
1032 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1033 tracer
.print (idx
, "LHS =");
1034 lhs
.dump (dump_file
);
1035 if (op2
&& TREE_CODE (op2
) == SSA_NAME
)
1037 fprintf (dump_file
, ", ");
1038 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1039 fprintf (dump_file
, " = ");
1040 op2_range
.dump (dump_file
);
1042 fprintf (dump_file
, "\n");
1043 tracer
.print (idx
, "Computes ");
1044 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1045 fprintf (dump_file
, " = ");
1047 fprintf (dump_file
, " intersect Known range : ");
1048 op1_range
.dump (dump_file
);
1049 fputc ('\n', dump_file
);
1051 // Intersect the calculated result with the known result and return if done.
1054 r
.intersect (op1_range
);
1056 tracer
.trailer (idx
, "produces ", true, name
, r
);
1059 // If the calculation continues, we're using op1_range as the new LHS.
1060 op1_range
.intersect (r
);
1063 tracer
.trailer (idx
, "produces ", true, op1
, op1_range
);
1064 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op1
);
1065 gcc_checking_assert (src_stmt
);
1067 // Then feed this range back as the LHS of the defining statement.
1068 return compute_operand_range (r
, src_stmt
, op1_range
, name
, src
);
1072 // Calculate a range for NAME from the operand 2 position of S
1073 // assuming the result of the statement is LHS. Return the range in
1074 // R, or false if no range could be calculated.
1077 gori_compute::compute_operand2_range (irange
&r
, gimple
*stmt
,
1078 const irange
&lhs
, tree name
,
1081 int_range_max op1_range
, op2_range
;
1082 tree op1
= gimple_range_operand1 (stmt
);
1083 tree op2
= gimple_range_operand2 (stmt
);
1085 src
.get_operand (op1_range
, op1
);
1086 src
.get_operand (op2_range
, op2
);
1088 // Intersect with range for op2 based on lhs and op1.
1089 if (!gimple_range_calc_op2 (r
, stmt
, lhs
, op1_range
))
1093 if ((idx
= tracer
.header ("compute op 2 (")))
1095 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1096 fprintf (dump_file
, ") at ");
1097 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1098 tracer
.print (idx
, "LHS = ");
1099 lhs
.dump (dump_file
);
1100 if (TREE_CODE (op1
) == SSA_NAME
)
1102 fprintf (dump_file
, ", ");
1103 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
1104 fprintf (dump_file
, " = ");
1105 op1_range
.dump (dump_file
);
1107 fprintf (dump_file
, "\n");
1108 tracer
.print (idx
, "Computes ");
1109 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
1110 fprintf (dump_file
, " = ");
1112 fprintf (dump_file
, " intersect Known range : ");
1113 op2_range
.dump (dump_file
);
1114 fputc ('\n', dump_file
);
1116 // Intersect the calculated result with the known result and return if done.
1119 r
.intersect (op2_range
);
1121 tracer
.trailer (idx
, " produces ", true, NULL_TREE
, r
);
1124 // If the calculation continues, we're using op2_range as the new LHS.
1125 op2_range
.intersect (r
);
1128 tracer
.trailer (idx
, " produces ", true, op2
, op2_range
);
1129 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op2
);
1130 gcc_checking_assert (src_stmt
);
1131 // gcc_checking_assert (!is_import_p (op2, find.bb));
1133 // Then feed this range back as the LHS of the defining statement.
1134 return compute_operand_range (r
, src_stmt
, op2_range
, name
, src
);
1137 // Calculate a range for NAME from both operand positions of S
1138 // assuming the result of the statement is LHS. Return the range in
1139 // R, or false if no range could be calculated.
1142 gori_compute::compute_operand1_and_operand2_range (irange
&r
,
1148 int_range_max op_range
;
1150 // Calculate a good a range for op2. Since op1 == op2, this will
1151 // have already included whatever the actual range of name is.
1152 if (!compute_operand2_range (op_range
, stmt
, lhs
, name
, src
))
1155 // Now get the range thru op1.
1156 if (!compute_operand1_range (r
, stmt
, lhs
, name
, src
))
1159 // Both operands have to be simultaneously true, so perform an intersection.
1160 r
.intersect (op_range
);
1163 // Return TRUE if a range can be calculated or recomputed for NAME on edge E.
1166 gori_compute::has_edge_range_p (tree name
, edge e
)
1168 // Check if NAME is an export or can be recomputed.
1170 return is_export_p (name
, e
->src
) || may_recompute_p (name
, e
);
1172 // If no edge is specified, check if NAME can have a range calculated
1174 return is_export_p (name
) || may_recompute_p (name
);
1177 // Dump what is known to GORI computes to listing file F.
1180 gori_compute::dump (FILE *f
)
1185 // Return TRUE if NAME can be recomputed on edge E. If any direct dependant
1186 // is exported on edge E, it may change the computed value of NAME.
1189 gori_compute::may_recompute_p (tree name
, edge e
)
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
, e
->src
))
1206 || (dep2
&& is_export_p (dep2
, e
->src
)));
1208 return (is_export_p (dep1
)) || (dep2
&& is_export_p (dep2
));
1211 // Calculate a range on edge E and return it in R. Try to evaluate a
1212 // range for NAME on this edge. Return FALSE if this is either not a
1213 // control edge or NAME is not defined by this edge.
1216 gori_compute::outgoing_edge_range_p (irange
&r
, edge e
, tree name
,
1222 if ((e
->flags
& m_not_executable_flag
))
1225 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1226 fprintf (dump_file
, "Outgoing edge %d->%d unexecutable.\n",
1227 e
->src
->index
, e
->dest
->index
);
1231 gcc_checking_assert (gimple_range_ssa_p (name
));
1232 // Determine if there is an outgoing edge.
1233 gimple
*stmt
= outgoing
.edge_range_p (lhs
, e
);
1237 fur_stmt
src (stmt
, &q
);
1238 // If NAME can be calculated on the edge, use that.
1239 if (is_export_p (name
, e
->src
))
1242 if ((idx
= tracer
.header ("outgoing_edge")))
1244 fprintf (dump_file
, " for ");
1245 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1246 fprintf (dump_file
, " on edge %d->%d\n",
1247 e
->src
->index
, e
->dest
->index
);
1249 if ((res
= compute_operand_range (r
, stmt
, lhs
, name
, src
)))
1251 // Sometimes compatible types get interchanged. See PR97360.
1252 // Make sure we are returning the type of the thing we asked for.
1253 if (!r
.undefined_p () && r
.type () != TREE_TYPE (name
))
1255 gcc_checking_assert (range_compatible_p (r
.type (),
1257 range_cast (r
, TREE_TYPE (name
));
1261 tracer
.trailer (idx
, "outgoing_edge", res
, name
, r
);
1264 // If NAME isn't exported, check if it can be recomputed.
1265 else if (may_recompute_p (name
, e
))
1267 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1269 if ((idx
= tracer
.header ("recomputation")))
1271 fprintf (dump_file
, " attempt on edge %d->%d for ",
1272 e
->src
->index
, e
->dest
->index
);
1273 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
1275 // Simply calculate DEF_STMT on edge E using the range query Q.
1276 fold_range (r
, def_stmt
, e
, &q
);
1278 tracer
.trailer (idx
, "recomputation", true, name
, r
);
1285 // ------------------------------------------------------------------------
1286 // GORI iterator. Although we have bitmap iterators, don't expose that it
1287 // is currently a bitmap. Use an export iterator to hide future changes.
1289 // Construct a basic iterator over an export bitmap.
1291 gori_export_iterator::gori_export_iterator (bitmap b
)
1295 bmp_iter_set_init (&bi
, b
, 1, &y
);
1299 // Move to the next export bitmap spot.
1302 gori_export_iterator::next ()
1304 bmp_iter_next (&bi
, &y
);
1308 // Fetch the name of the next export in the export list. Return NULL if
1309 // iteration is done.
1312 gori_export_iterator::get_name ()
1317 while (bmp_iter_set (&bi
, &y
))
1319 tree t
= ssa_name (y
);