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"
33 /* RANGE_DEF_CHAIN is used to determine what SSA names in a block can
34 have range information calculated for them, and what the
35 dependencies on each other are.
37 Information for a basic block is calculated once and stored. It is
38 only calculated the first time a query is made, so if no queries
39 are made, there is little overhead.
41 The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set
42 within this bitmap to indicate SSA names that are defined in the
43 SAME block and used to calculate this SSA name.
57 This dump indicates the bits set in the def_chain vector.
58 as well as demonstrates the def_chain bits for the related ssa_names.
60 Checking the chain for _2 indicates that _1 and x_4 are used in
63 Def chains also only include statements which are valid gimple
64 so a def chain will only span statements for which the range
65 engine implements operations for. */
73 bool has_def_chain (tree name
);
74 bitmap
get_def_chain (tree name
);
75 bool in_chain_p (tree name
, tree def
);
77 vec
<bitmap
> m_def_chain
; // SSA_NAME : def chain components.
78 void build_def_chain (tree name
, bitmap result
, basic_block bb
);
82 // Construct a range_def_chain.
84 range_def_chain::range_def_chain ()
86 m_def_chain
.create (0);
87 m_def_chain
.safe_grow_cleared (num_ssa_names
);
90 // Destruct a range_def_chain.
92 range_def_chain::~range_def_chain ()
95 for (x
= 0; x
< m_def_chain
.length (); ++x
)
97 BITMAP_FREE (m_def_chain
[x
]);
98 m_def_chain
.release ();
101 // Return true if NAME is in the def chain of DEF. If BB is provided,
102 // only return true if the defining statement of DEF is in BB.
105 range_def_chain::in_chain_p (tree name
, tree def
)
107 gcc_checking_assert (gimple_range_ssa_p (def
));
108 gcc_checking_assert (gimple_range_ssa_p (name
));
110 // Get the defintion chain for DEF.
111 bitmap chain
= get_def_chain (def
);
115 return bitmap_bit_p (chain
, SSA_NAME_VERSION (name
));
118 // Build def_chains for NAME if it is in BB. Copy the def chain into RESULT.
121 range_def_chain::build_def_chain (tree name
, bitmap result
, basic_block bb
)
124 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
125 // Add this operand into the result.
126 bitmap_set_bit (result
, SSA_NAME_VERSION (name
));
128 if (gimple_bb (def_stmt
) == bb
&& !is_a
<gphi
*>(def_stmt
))
130 // Get the def chain for the operand.
131 b
= get_def_chain (name
);
132 // If there was one, copy it into result.
134 bitmap_ior_into (result
, b
);
138 // Return TRUE if NAME has been processed for a def_chain.
141 range_def_chain::has_def_chain (tree name
)
143 // Ensure there is an entry in the internal vector.
144 unsigned v
= SSA_NAME_VERSION (name
);
145 if (v
>= m_def_chain
.length ())
146 m_def_chain
.safe_grow_cleared (num_ssa_names
+ 1);
147 return (m_def_chain
[v
] != NULL
);
150 // Calculate the def chain for NAME and all of its dependent
151 // operands. Only using names in the same BB. Return the bitmap of
152 // all names in the m_def_chain. This only works for supported range
156 range_def_chain::get_def_chain (tree name
)
158 tree ssa1
, ssa2
, ssa3
;
159 unsigned v
= SSA_NAME_VERSION (name
);
161 // If it has already been processed, just return the cached value.
162 if (has_def_chain (name
))
163 return m_def_chain
[v
];
165 // No definition chain for default defs.
166 if (SSA_NAME_IS_DEFAULT_DEF (name
))
169 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
170 if (gimple_range_handler (stmt
))
172 ssa1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
173 ssa2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
176 else if (is_a
<gassign
*> (stmt
)
177 && gimple_assign_rhs_code (stmt
) == COND_EXPR
)
179 gassign
*st
= as_a
<gassign
*> (stmt
);
180 ssa1
= gimple_range_ssa_p (gimple_assign_rhs1 (st
));
181 ssa2
= gimple_range_ssa_p (gimple_assign_rhs2 (st
));
182 ssa3
= gimple_range_ssa_p (gimple_assign_rhs3 (st
));
187 basic_block bb
= gimple_bb (stmt
);
189 m_def_chain
[v
] = BITMAP_ALLOC (NULL
);
192 build_def_chain (ssa1
, m_def_chain
[v
], bb
);
194 build_def_chain (ssa2
, m_def_chain
[v
], bb
);
196 build_def_chain (ssa3
, m_def_chain
[v
], bb
);
198 // If we run into pathological cases where the defintion chains are
199 // huge (ie huge basic block fully unrolled) we might be able to limit
200 // this by deciding here that if some criteria is satisfied, we change the
201 // def_chain back to be just the ssa-names. That will help prevent chains
202 // of a_2 = b_6 + a_8 from creating a pathological case.
203 return m_def_chain
[v
];
206 // -------------------------------------------------------------------
208 /* GORI_MAP is used to accumulate what SSA names in a block can
209 generate range information, and provides tools for the block ranger
210 to enable it to efficiently calculate these ranges.
212 GORI stands for "Generates Outgoing Range Information."
214 It utilizes the range_def_chain class to contruct def_chains.
215 Information for a basic block is calculated once and stored. It is
216 only calculated the first time a query is made. If no queries are
217 made, there is little overhead.
219 one bitmap is maintained for each basic block:
220 m_outgoing : a set bit indicates a range can be generated for a name.
222 Generally speaking, the m_outgoing vector is the union of the
223 entire def_chain of all SSA names used in the last statement of the
224 block which generate ranges. */
226 class gori_map
: public range_def_chain
232 bool is_export_p (tree name
, basic_block bb
= NULL
);
233 bool def_chain_in_export_p (tree name
, basic_block bb
);
234 bitmap
exports (basic_block bb
);
237 void dump (FILE *f
, basic_block bb
);
239 bitmap_obstack m_bitmaps
;
240 vec
<bitmap
> m_outgoing
; // BB: Outgoing ranges calculatable on edges
241 bitmap all_outgoing
; // All outgoing ranges combined.
242 void maybe_add_gori (tree name
, basic_block bb
);
243 void calculate_gori (basic_block bb
);
247 // Initialize a gori-map structure.
249 gori_map::gori_map ()
251 m_outgoing
.create (0);
252 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
253 bitmap_obstack_initialize (&m_bitmaps
);
254 all_outgoing
= BITMAP_ALLOC (&m_bitmaps
);
257 // Free any memory the GORI map allocated.
259 gori_map::~gori_map ()
261 bitmap_obstack_release (&m_bitmaps
);
262 m_outgoing
.release ();
265 // Return the bitmap vector of all export from BB. Calculate if necessary.
268 gori_map::exports (basic_block bb
)
270 if (!m_outgoing
[bb
->index
])
272 return m_outgoing
[bb
->index
];
275 // Return true if NAME is can have ranges generated for it from basic
279 gori_map::is_export_p (tree name
, basic_block bb
)
281 // If no BB is specified, test if it is exported anywhere in the IL.
283 return bitmap_bit_p (all_outgoing
, SSA_NAME_VERSION (name
));
284 return bitmap_bit_p (exports (bb
), SSA_NAME_VERSION (name
));
287 // Return true if any element in the def chain of NAME is in the
288 // export list for BB.
291 gori_map::def_chain_in_export_p (tree name
, basic_block bb
)
293 bitmap a
= exports (bb
);
294 bitmap b
= get_def_chain (name
);
296 return bitmap_intersect_p (a
, b
);
300 // If NAME is non-NULL and defined in block BB, calculate the def
301 // chain and add it to m_outgoing.
304 gori_map::maybe_add_gori (tree name
, basic_block bb
)
308 gimple
*s
= SSA_NAME_DEF_STMT (name
);
309 bitmap r
= get_def_chain (name
);
310 // Check if there is a def chain, and it is in this block.
311 if (r
&& gimple_bb (s
) == bb
)
312 bitmap_copy (m_outgoing
[bb
->index
], r
);
313 // Def chain doesn't include itself, and even if there isn't a
314 // def chain, this name should be added to exports.
315 bitmap_set_bit (m_outgoing
[bb
->index
], SSA_NAME_VERSION (name
));
319 // Calculate all the required information for BB.
322 gori_map::calculate_gori (basic_block bb
)
325 if (bb
->index
>= (signed int)m_outgoing
.length ())
326 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
327 gcc_checking_assert (m_outgoing
[bb
->index
] == NULL
);
328 m_outgoing
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
330 // If this block's last statement may generate range informaiton, go
332 gimple
*stmt
= gimple_outgoing_range_stmt_p (bb
);
335 if (is_a
<gcond
*> (stmt
))
337 gcond
*gc
= as_a
<gcond
*>(stmt
);
338 name
= gimple_range_ssa_p (gimple_cond_lhs (gc
));
339 maybe_add_gori (name
, gimple_bb (stmt
));
341 name
= gimple_range_ssa_p (gimple_cond_rhs (gc
));
342 maybe_add_gori (name
, gimple_bb (stmt
));
346 gswitch
*gs
= as_a
<gswitch
*>(stmt
);
347 name
= gimple_range_ssa_p (gimple_switch_index (gs
));
348 maybe_add_gori (name
, gimple_bb (stmt
));
350 // Add this bitmap to the aggregate list of all outgoing names.
351 bitmap_ior_into (all_outgoing
, m_outgoing
[bb
->index
]);
354 // Dump the table information for BB to file F.
357 gori_map::dump (FILE *f
, basic_block bb
)
360 const char *header_string
= "bb%-4d ";
361 const char *header2
= " ";
362 bool printed_something
= false;;
366 // BB was not processed.
367 if (!m_outgoing
[bb
->index
])
370 // Dump the def chain for each SSA_NAME defined in BB.
371 for (x
= 1; x
< num_ssa_names
; x
++)
373 tree name
= ssa_name (x
);
376 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
377 bitmap chain
= (has_def_chain (name
) ? get_def_chain (name
) : NULL
);
378 if (stmt
&& gimple_bb (stmt
) == bb
&& chain
&& !bitmap_empty_p (chain
))
380 fprintf (f
, header_string
, bb
->index
);
381 header_string
= header2
;
383 print_generic_expr (f
, name
, TDF_SLIM
);
385 EXECUTE_IF_SET_IN_BITMAP (chain
, 0, y
, bi
)
387 print_generic_expr (f
, ssa_name (y
), TDF_SLIM
);
394 printed_something
|= header
;
396 // Now dump the export vector.
398 EXECUTE_IF_SET_IN_BITMAP (m_outgoing
[bb
->index
], 0, y
, bi
)
402 fprintf (f
, header_string
, bb
->index
);
403 fprintf (f
, "exports: ");
404 header_string
= header2
;
407 print_generic_expr (f
, ssa_name (y
), TDF_SLIM
);
413 printed_something
|= header
;
414 if (printed_something
)
418 // Dump the entire GORI map structure to file F.
421 gori_map::dump (FILE *f
)
424 FOR_EACH_BB_FN (bb
, cfun
)
427 if (m_outgoing
[bb
->index
])
438 // -------------------------------------------------------------------
440 // Construct a gori_compute object.
442 gori_compute::gori_compute ()
444 // Create a boolean_type true and false range.
445 m_bool_zero
= int_range
<2> (boolean_false_node
, boolean_false_node
);
446 m_bool_one
= int_range
<2> (boolean_true_node
, boolean_true_node
);
447 m_gori_map
= new gori_map
;
448 unsigned x
, lim
= last_basic_block_for_fn (cfun
);
449 // Calculate outgoing range info upfront. This will fully populate the
450 // all_outgoing bitmap which will help eliminate processing of names
451 // which never have their ranges adjusted.
452 for (x
= 0; x
< lim
; x
++)
454 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, x
);
456 m_gori_map
->exports (bb
);
460 // Destruct a gori_compute_object.
462 gori_compute::~gori_compute ()
467 // Provide a default of VARYING for all incoming SSA names.
470 gori_compute::ssa_range_in_bb (irange
&r
, tree name
, basic_block
)
472 r
.set_varying (TREE_TYPE (name
));
476 gori_compute::expr_range_in_bb (irange
&r
, tree expr
, basic_block bb
)
478 if (gimple_range_ssa_p (expr
))
479 ssa_range_in_bb (r
, expr
, bb
);
481 get_tree_range (r
, expr
);
484 // Calculate the range for NAME if the lhs of statement S has the
485 // range LHS. Return the result in R. Return false if no range can be
489 gori_compute::compute_name_range_op (irange
&r
, gimple
*stmt
,
490 const irange
&lhs
, tree name
)
492 int_range_max op1_range
, op2_range
;
494 tree op1
= gimple_range_operand1 (stmt
);
495 tree op2
= gimple_range_operand2 (stmt
);
497 // Operand 1 is the name being looked for, evaluate it.
500 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
503 // The second parameter to a unary operation is the range
504 // for the type of operand1, but if it can be reduced
505 // further, the results will be better. Start with what we
506 // know of the range of OP1 instead of the full type.
507 return gimple_range_calc_op1 (r
, stmt
, lhs
, op1_range
);
509 // If we need the second operand, get a value and evaluate.
510 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
511 if (gimple_range_calc_op1 (r
, stmt
, lhs
, op2_range
))
512 r
.intersect (op1_range
);
520 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
521 expr_range_in_bb (r
, op2
, gimple_bb (stmt
));
522 if (gimple_range_calc_op2 (op2_range
, stmt
, lhs
, op1_range
))
523 r
.intersect (op2_range
);
529 // Given the switch S, return an evaluation in R for NAME when the lhs
530 // evaluates to LHS. Returning false means the name being looked for
531 // was not resolvable.
534 gori_compute::compute_operand_range_switch (irange
&r
, gswitch
*s
,
538 tree op1
= gimple_switch_index (s
);
540 // If name matches, the range is simply the range from the edge.
541 // Empty ranges are viral as they are on a path which isn't
543 if (op1
== name
|| lhs
.undefined_p ())
549 // If op1 is in the defintion chain, pass lhs back.
550 if (gimple_range_ssa_p (op1
) && m_gori_map
->in_chain_p (name
, op1
))
551 return compute_operand_range (r
, SSA_NAME_DEF_STMT (op1
), lhs
, name
);
556 // Return TRUE if GS is a logical && or || expression.
559 is_gimple_logical_p (const gimple
*gs
)
561 // Look for boolean and/or condition.
562 if (gimple_code (gs
) == GIMPLE_ASSIGN
)
563 switch (gimple_expr_code (gs
))
571 // Bitwise operations on single bits are logical too.
572 if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs
)),
583 // Return an evaluation for NAME as it would appear in STMT when the
584 // statement's lhs evaluates to LHS. If successful, return TRUE and
585 // store the evaluation in R, otherwise return FALSE.
588 gori_compute::compute_operand_range (irange
&r
, gimple
*stmt
,
589 const irange
&lhs
, tree name
)
591 // Empty ranges are viral as they are on an unexecutable path.
592 if (lhs
.undefined_p ())
597 if (is_a
<gswitch
*> (stmt
))
598 return compute_operand_range_switch (r
, as_a
<gswitch
*> (stmt
), lhs
, name
);
599 if (!gimple_range_handler (stmt
))
602 tree op1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
603 tree op2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
605 // The base ranger handles NAME on this statement.
606 if (op1
== name
|| op2
== name
)
607 return compute_name_range_op (r
, stmt
, lhs
, name
);
609 if (is_gimple_logical_p (stmt
))
610 return compute_logical_operands (r
, stmt
, lhs
, name
);
612 // NAME is not in this stmt, but one of the names in it ought to be
614 bool op1_in_chain
= op1
&& m_gori_map
->in_chain_p (name
, op1
);
615 bool op2_in_chain
= op2
&& m_gori_map
->in_chain_p (name
, op2
);
616 if (op1_in_chain
&& op2_in_chain
)
617 return compute_operand1_and_operand2_range (r
, stmt
, lhs
, name
);
619 return compute_operand1_range (r
, stmt
, lhs
, name
);
621 return compute_operand2_range (r
, stmt
, lhs
, name
);
623 // If neither operand is derived, this statement tells us nothing.
627 // Return TRUE if range R is either a true or false compatible range.
630 range_is_either_true_or_false (const irange
&r
)
632 if (r
.undefined_p ())
635 // This is complicated by the fact that Ada has multi-bit booleans,
636 // so true can be ~[0, 0] (i.e. [1,MAX]).
637 tree type
= r
.type ();
638 gcc_checking_assert (range_compatible_p (type
, boolean_type_node
));
639 return (r
.singleton_p () || !r
.contains_p (build_zero_cst (type
)));
642 // A pair of ranges for true/false paths.
647 tf_range (const irange
&t_range
, const irange
&f_range
)
649 true_range
= t_range
;
650 false_range
= f_range
;
652 int_range_max true_range
, false_range
;
655 // Evaluate a binary logical expression by combining the true and
656 // false ranges for each of the operands based on the result value in
660 gori_compute::logical_combine (irange
&r
, enum tree_code code
,
662 const tf_range
&op1
, const tf_range
&op2
)
664 if (op1
.true_range
.varying_p ()
665 && op1
.false_range
.varying_p ()
666 && op2
.true_range
.varying_p ()
667 && op2
.false_range
.varying_p ())
670 // This is not a simple fold of a logical expression, rather it
671 // determines ranges which flow through the logical expression.
673 // Assuming x_8 is an unsigned char, and relational statements:
676 // consider the logical expression and branch:
680 // To determine the range of x_8 on either edge of the branch, one
681 // must first determine what the range of x_8 is when the boolean
682 // values of b_1 and b_2 are both true and false.
683 // b_1 TRUE x_8 = [0, 19]
684 // b_1 FALSE x_8 = [20, 255]
685 // b_2 TRUE x_8 = [6, 255]
686 // b_2 FALSE x_8 = [0,5].
688 // These ranges are then combined based on the expected outcome of
689 // the branch. The range on the TRUE side of the branch must satisfy
690 // b_1 == true && b_2 == true
692 // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
693 // must be true. The range of x_8 on the true side must be the
694 // intersection of both ranges since both must be true. Thus the
695 // range of x_8 on the true side is [6, 19].
697 // To determine the ranges on the FALSE side, all 3 combinations of
698 // failing ranges must be considered, and combined as any of them
699 // can cause the false result.
701 // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
702 // FALSE results and combine them. If we fell back to VARYING any
703 // range restrictions that have been discovered up to this point
705 if (!range_is_either_true_or_false (lhs
))
708 if (logical_combine (r1
, code
, m_bool_zero
, op1
, op2
)
709 && logical_combine (r
, code
, m_bool_one
, op1
, op2
))
719 // A logical AND combines ranges from 2 boolean conditions.
725 // The TRUE side is the intersection of the the 2 true ranges.
727 r
.intersect (op2
.true_range
);
731 // The FALSE side is the union of the other 3 cases.
732 int_range_max
ff (op1
.false_range
);
733 ff
.intersect (op2
.false_range
);
734 int_range_max
tf (op1
.true_range
);
735 tf
.intersect (op2
.false_range
);
736 int_range_max
ft (op1
.false_range
);
737 ft
.intersect (op2
.true_range
);
743 // A logical OR combines ranges from 2 boolean conditons.
749 // An OR operation will only take the FALSE path if both
750 // operands are false simlulateously, which means they should
751 // be intersected. !(x || y) == !x && !y
753 r
.intersect (op2
.false_range
);
757 // The TRUE side of an OR operation will be the union of
758 // the other three combinations.
759 int_range_max
tt (op1
.true_range
);
760 tt
.intersect (op2
.true_range
);
761 int_range_max
tf (op1
.true_range
);
762 tf
.intersect (op2
.false_range
);
763 int_range_max
ft (op1
.false_range
);
764 ft
.intersect (op2
.true_range
);
777 // Helper function for compute_logical_operands_in_chain that computes
778 // the range of logical statements that can be computed without
779 // chasing down operands. These are things like [0 = x | y] where we
780 // know neither operand can be non-zero, or [1 = x & y] where we know
781 // neither operand can be zero.
784 gori_compute::optimize_logical_operands (tf_range
&range
,
790 enum tree_code code
= gimple_expr_code (stmt
);
792 // Optimize [0 = x | y], since neither operand can ever be non-zero.
793 if ((code
== BIT_IOR_EXPR
|| code
== TRUTH_OR_EXPR
) && lhs
.zero_p ())
795 if (!compute_operand_range (range
.false_range
, SSA_NAME_DEF_STMT (op
),
797 expr_range_in_bb (range
.false_range
, name
, gimple_bb (stmt
));
798 range
.true_range
= range
.false_range
;
801 // Optimize [1 = x & y], since neither operand can ever be zero.
802 if ((code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
) && lhs
== m_bool_one
)
804 if (!compute_operand_range (range
.true_range
, SSA_NAME_DEF_STMT (op
),
806 expr_range_in_bb (range
.true_range
, name
, gimple_bb (stmt
));
807 range
.false_range
= range
.true_range
;
813 // Given a logical STMT, calculate true and false ranges for each
814 // potential path of NAME, assuming NAME came through the OP chain if
815 // OP_IN_CHAIN is true.
818 gori_compute::compute_logical_operands_in_chain (tf_range
&range
,
822 tree op
, bool op_in_chain
)
824 gimple
*src_stmt
= gimple_range_ssa_p (op
) ? SSA_NAME_DEF_STMT (op
) : NULL
;
825 basic_block bb
= gimple_bb (stmt
);
826 if (!op_in_chain
|| (src_stmt
!= NULL
&& bb
!= gimple_bb (src_stmt
)))
828 // If op is not in the def chain, or defined in this block,
829 // use its known value on entry to the block.
830 expr_range_in_bb (range
.true_range
, name
, gimple_bb (stmt
));
831 range
.false_range
= range
.true_range
;
834 if (optimize_logical_operands (range
, stmt
, lhs
, name
, op
))
837 // Calculate ranges for true and false on both sides, since the false
838 // path is not always a simple inversion of the true side.
839 if (!compute_operand_range (range
.true_range
, src_stmt
, m_bool_one
, name
))
840 expr_range_in_bb (range
.true_range
, name
, bb
);
841 if (!compute_operand_range (range
.false_range
, src_stmt
, m_bool_zero
, name
))
842 expr_range_in_bb (range
.false_range
, name
, bb
);
845 // Given a logical STMT, calculate true and false for each potential
846 // path using NAME, and resolve the outcome based on the logical
850 gori_compute::compute_logical_operands (irange
&r
, gimple
*stmt
,
854 // Reaching this point means NAME is not in this stmt, but one of
855 // the names in it ought to be derived from it.
856 tree op1
= gimple_range_operand1 (stmt
);
857 tree op2
= gimple_range_operand2 (stmt
);
858 gcc_checking_assert (op1
!= name
&& op2
!= name
);
860 bool op1_in_chain
= (gimple_range_ssa_p (op1
)
861 && m_gori_map
->in_chain_p (name
, op1
));
862 bool op2_in_chain
= (gimple_range_ssa_p (op2
)
863 && m_gori_map
->in_chain_p (name
, op2
));
865 // If neither operand is derived, then this stmt tells us nothing.
866 if (!op1_in_chain
&& !op2_in_chain
)
869 tf_range op1_range
, op2_range
;
870 compute_logical_operands_in_chain (op1_range
, stmt
, lhs
,
871 name
, op1
, op1_in_chain
);
872 compute_logical_operands_in_chain (op2_range
, stmt
, lhs
,
873 name
, op2
, op2_in_chain
);
874 return logical_combine (r
, gimple_expr_code (stmt
), lhs
,
875 op1_range
, op2_range
);
878 // Calculate a range for NAME from the operand 1 position of STMT
879 // assuming the result of the statement is LHS. Return the range in
880 // R, or false if no range could be calculated.
883 gori_compute::compute_operand1_range (irange
&r
, gimple
*stmt
,
884 const irange
&lhs
, tree name
)
886 int_range_max op1_range
, op2_range
;
887 tree op1
= gimple_range_operand1 (stmt
);
888 tree op2
= gimple_range_operand2 (stmt
);
890 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
892 // Now calcuated the operand and put that result in r.
895 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
896 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op2_range
))
901 // We pass op1_range to the unary operation. Nomally it's a
902 // hidden range_for_type parameter, but sometimes having the
903 // actual range can result in better information.
904 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op1_range
))
908 // Intersect the calculated result with the known result.
909 op1_range
.intersect (r
);
911 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op1
);
912 // If def stmt is outside of this BB, then name must be an import.
913 if (!src_stmt
|| (gimple_bb (src_stmt
) != gimple_bb (stmt
)))
915 // If this isn't the right import statement, then abort calculation.
916 if (!src_stmt
|| gimple_get_lhs (src_stmt
) != name
)
918 return compute_name_range_op (r
, src_stmt
, op1_range
, name
);
920 // Then feed this range back as the LHS of the defining statement.
921 return compute_operand_range (r
, src_stmt
, op1_range
, name
);
925 // Calculate a range for NAME from the operand 2 position of S
926 // assuming the result of the statement is LHS. Return the range in
927 // R, or false if no range could be calculated.
930 gori_compute::compute_operand2_range (irange
&r
, gimple
*stmt
,
931 const irange
&lhs
, tree name
)
933 int_range_max op1_range
, op2_range
;
934 tree op1
= gimple_range_operand1 (stmt
);
935 tree op2
= gimple_range_operand2 (stmt
);
937 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
938 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
940 // Intersect with range for op2 based on lhs and op1.
941 if (!gimple_range_calc_op2 (r
, stmt
, lhs
, op1_range
))
943 op2_range
.intersect (r
);
945 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op2
);
946 // If def stmt is outside of this BB, then name must be an import.
947 if (!src_stmt
|| (gimple_bb (src_stmt
) != gimple_bb (stmt
)))
949 // If this isn't the right src statement, then abort calculation.
950 if (!src_stmt
|| gimple_get_lhs (src_stmt
) != name
)
952 return compute_name_range_op (r
, src_stmt
, op2_range
, name
);
954 // Then feed this range back as the LHS of the defining statement.
955 return compute_operand_range (r
, src_stmt
, op2_range
, name
);
958 // Calculate a range for NAME from both operand positions of S
959 // assuming the result of the statement is LHS. Return the range in
960 // R, or false if no range could be calculated.
963 gori_compute::compute_operand1_and_operand2_range
969 int_range_max op_range
;
971 // Calculate a good a range for op2. Since op1 == op2, this will
972 // have already included whatever the actual range of name is.
973 if (!compute_operand2_range (op_range
, stmt
, lhs
, name
))
976 // Now get the range thru op1.
977 if (!compute_operand1_range (r
, stmt
, lhs
, name
))
980 // Whichever range is the most permissive is the one we need to
981 // use. (?) OR is that true? Maybe this should be intersection?
986 // Return TRUE if a range can be calcalated for NAME on edge E.
989 gori_compute::has_edge_range_p (tree name
, edge e
)
991 // If no edge is specified, check if NAME is an export on any edge.
993 return m_gori_map
->is_export_p (name
);
995 return (m_gori_map
->is_export_p (name
, e
->src
)
996 || m_gori_map
->def_chain_in_export_p (name
, e
->src
));
999 // Dump what is known to GORI computes to listing file F.
1002 gori_compute::dump (FILE *f
)
1004 m_gori_map
->dump (f
);
1007 // Calculate a range on edge E and return it in R. Try to evaluate a
1008 // range for NAME on this edge. Return FALSE if this is either not a
1009 // control edge or NAME is not defined by this edge.
1012 gori_compute::outgoing_edge_range_p (irange
&r
, edge e
, tree name
)
1016 gcc_checking_assert (gimple_range_ssa_p (name
));
1017 // Determine if there is an outgoing edge.
1018 gimple
*stmt
= outgoing
.edge_range_p (lhs
, e
);
1022 // If NAME can be calculated on the edge, use that.
1023 if (m_gori_map
->is_export_p (name
, e
->src
))
1025 if (compute_operand_range (r
, stmt
, lhs
, name
))
1027 // Sometimes compatible types get interchanged. See PR97360.
1028 // Make sure we are returning the type of the thing we asked for.
1029 if (!r
.undefined_p () && r
.type () != TREE_TYPE (name
))
1031 gcc_checking_assert (range_compatible_p (r
.type (),
1033 range_cast (r
, TREE_TYPE (name
));
1041 // --------------------------------------------------------------------------
1043 // Cache for SSAs that appear on the RHS of a boolean assignment.
1045 // Boolean assignments of logical expressions (i.e. LHS = j_5 > 999)
1046 // have SSA operands whose range depend on the LHS of the assigment.
1047 // That is, the range of j_5 when LHS is true is different than when
1050 // This class caches the TRUE/FALSE ranges of such SSAs to avoid
1053 class logical_stmt_cache
1056 logical_stmt_cache ();
1057 ~logical_stmt_cache ();
1058 void set_range (tree lhs
, tree name
, const tf_range
&);
1059 bool get_range (tf_range
&r
, tree lhs
, tree name
) const;
1060 bool cacheable_p (gimple
*, const irange
*lhs_range
= NULL
) const;
1061 void dump (FILE *, gimple
*stmt
) const;
1062 tree
same_cached_name (tree lhs1
, tree lh2
) const;
1064 tree
cached_name (tree lhs
) const;
1065 void slot_diagnostics (tree lhs
, const tf_range
&range
) const;
1068 cache_entry (tree name
, const irange
&t_range
, const irange
&f_range
);
1069 void dump (FILE *out
) const;
1073 vec
<cache_entry
*> m_ssa_cache
;
1076 logical_stmt_cache::cache_entry::cache_entry (tree name
,
1077 const irange
&t_range
,
1078 const irange
&f_range
)
1079 : name (name
), range (t_range
, f_range
)
1083 logical_stmt_cache::logical_stmt_cache ()
1085 m_ssa_cache
.create (num_ssa_names
+ num_ssa_names
/ 10);
1086 m_ssa_cache
.safe_grow_cleared (num_ssa_names
);
1089 logical_stmt_cache::~logical_stmt_cache ()
1091 for (unsigned i
= 0; i
< m_ssa_cache
.length (); ++i
)
1093 delete m_ssa_cache
[i
];
1094 m_ssa_cache
.release ();
1097 // Dump cache_entry to OUT.
1100 logical_stmt_cache::cache_entry::dump (FILE *out
) const
1102 fprintf (out
, "name=");
1103 print_generic_expr (out
, name
, TDF_SLIM
);
1105 range
.true_range
.dump (out
);
1106 fprintf (out
, ", ");
1107 range
.false_range
.dump (out
);
1108 fprintf (out
, "\n");
1111 // Update range for cache entry of NAME as it appears in the defining
1112 // statement of LHS.
1115 logical_stmt_cache::set_range (tree lhs
, tree name
, const tf_range
&range
)
1117 unsigned version
= SSA_NAME_VERSION (lhs
);
1118 if (version
>= m_ssa_cache
.length ())
1119 m_ssa_cache
.safe_grow_cleared (num_ssa_names
+ num_ssa_names
/ 10);
1121 cache_entry
*slot
= m_ssa_cache
[version
];
1122 slot_diagnostics (lhs
, range
);
1125 // The IL must have changed. Update the carried SSA name for
1126 // consistency. Testcase is libgomp.fortran/doacross1.f90.
1127 if (slot
->name
!= name
)
1131 m_ssa_cache
[version
]
1132 = new cache_entry (name
, range
.true_range
, range
.false_range
);
1135 // If there is a cached entry of NAME, set it in R and return TRUE,
1136 // otherwise return FALSE. LHS is the defining statement where NAME
1140 logical_stmt_cache::get_range (tf_range
&r
, tree lhs
, tree name
) const
1142 gcc_checking_assert (cacheable_p (SSA_NAME_DEF_STMT (lhs
)));
1143 if (cached_name (lhs
) == name
)
1145 unsigned version
= SSA_NAME_VERSION (lhs
);
1146 if (m_ssa_cache
[version
])
1148 r
= m_ssa_cache
[version
]->range
;
1155 // If the defining statement of LHS is in the cache, return the SSA
1156 // operand being cached. That is, return SSA for LHS = SSA .RELOP. OP2.
1159 logical_stmt_cache::cached_name (tree lhs
) const
1161 unsigned version
= SSA_NAME_VERSION (lhs
);
1163 if (version
>= m_ssa_cache
.length ())
1166 if (m_ssa_cache
[version
])
1167 return m_ssa_cache
[version
]->name
;
1171 // Return TRUE if the cached name for LHS1 is the same as the
1172 // cached name for LHS2.
1175 logical_stmt_cache::same_cached_name (tree lhs1
, tree lhs2
) const
1177 tree name
= cached_name (lhs1
);
1178 if (name
&& name
== cached_name (lhs2
))
1183 // Return TRUE if STMT is a statement we are interested in caching.
1184 // LHS_RANGE is any known range for the LHS of STMT.
1187 logical_stmt_cache::cacheable_p (gimple
*stmt
, const irange
*lhs_range
) const
1189 if (gimple_code (stmt
) == GIMPLE_ASSIGN
1190 && types_compatible_p (TREE_TYPE (gimple_assign_lhs (stmt
)),
1192 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
1194 switch (gimple_expr_code (stmt
))
1196 case TRUTH_AND_EXPR
:
1200 return !lhs_range
|| range_is_either_true_or_false (*lhs_range
);
1208 // Output debugging diagnostics for the cache entry for LHS. RANGE is
1209 // the new range that is being cached.
1212 logical_stmt_cache::slot_diagnostics (tree lhs
, const tf_range
&range
) const
1214 gimple
*stmt
= SSA_NAME_DEF_STMT (lhs
);
1215 unsigned version
= SSA_NAME_VERSION (lhs
);
1216 cache_entry
*slot
= m_ssa_cache
[version
];
1220 if (DEBUG_RANGE_CACHE
)
1222 fprintf (dump_file
? dump_file
: stderr
, "registering range for: ");
1223 dump (dump_file
? dump_file
: stderr
, stmt
);
1227 if (DEBUG_RANGE_CACHE
)
1228 fprintf (dump_file
? dump_file
: stderr
,
1229 "reusing range for SSA #%d\n", version
);
1230 if (CHECKING_P
&& (slot
->range
.true_range
!= range
.true_range
1231 || slot
->range
.false_range
!= range
.false_range
))
1233 fprintf (stderr
, "FATAL: range altered for cached: ");
1234 dump (stderr
, stmt
);
1235 fprintf (stderr
, "Attempt to change to:\n");
1236 fprintf (stderr
, "TRUE=");
1237 range
.true_range
.dump (stderr
);
1238 fprintf (stderr
, ", FALSE=");
1239 range
.false_range
.dump (stderr
);
1240 fprintf (stderr
, "\n");
1245 // Dump the cache information for STMT.
1248 logical_stmt_cache::dump (FILE *out
, gimple
*stmt
) const
1250 tree lhs
= gimple_assign_lhs (stmt
);
1251 cache_entry
*entry
= m_ssa_cache
[SSA_NAME_VERSION (lhs
)];
1253 print_gimple_stmt (out
, stmt
, 0, TDF_SLIM
);
1256 fprintf (out
, "\tname = ");
1257 print_generic_expr (out
, entry
->name
);
1258 fprintf (out
, " lhs(%d)= ", SSA_NAME_VERSION (lhs
));
1259 print_generic_expr (out
, lhs
);
1260 fprintf (out
, "\n\tTRUE=");
1261 entry
->range
.true_range
.dump (out
);
1262 fprintf (out
, ", FALSE=");
1263 entry
->range
.false_range
.dump (out
);
1264 fprintf (out
, "\n");
1267 fprintf (out
, "[EMPTY]\n");
1270 gori_compute_cache::gori_compute_cache ()
1272 m_cache
= new logical_stmt_cache
;
1275 gori_compute_cache::~gori_compute_cache ()
1280 // Caching version of compute_operand_range. If NAME, as it appears
1281 // in STMT, has already been cached return it from the cache,
1282 // otherwise compute the operand range as normal and cache it.
1285 gori_compute_cache::compute_operand_range (irange
&r
, gimple
*stmt
,
1286 const irange
&lhs_range
, tree name
)
1288 bool cacheable
= m_cache
->cacheable_p (stmt
, &lhs_range
);
1291 tree lhs
= gimple_assign_lhs (stmt
);
1293 if (m_cache
->get_range (range
, lhs
, name
))
1295 if (lhs_range
.zero_p ())
1296 r
= range
.false_range
;
1298 r
= range
.true_range
;
1302 if (super::compute_operand_range (r
, stmt
, lhs_range
, name
))
1311 // Cache STMT if possible.
1314 gori_compute_cache::cache_stmt (gimple
*stmt
)
1316 gcc_checking_assert (m_cache
->cacheable_p (stmt
));
1317 enum tree_code code
= gimple_expr_code (stmt
);
1318 tree lhs
= gimple_assign_lhs (stmt
);
1319 tree op1
= gimple_range_operand1 (stmt
);
1320 tree op2
= gimple_range_operand2 (stmt
);
1321 int_range_max r_true_side
, r_false_side
;
1323 // LHS = s_5 && 999.
1324 if (TREE_CODE (op2
) == INTEGER_CST
)
1326 range_operator
*handler
= range_op_handler (code
, TREE_TYPE (lhs
));
1327 int_range_max op2_range
;
1328 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
1329 tree type
= TREE_TYPE (op1
);
1330 handler
->op1_range (r_true_side
, type
, m_bool_one
, op2_range
);
1331 handler
->op1_range (r_false_side
, type
, m_bool_zero
, op2_range
);
1332 m_cache
->set_range (lhs
, op1
, tf_range (r_true_side
, r_false_side
));
1334 // LHS = s_5 && b_8.
1335 else if (tree cached_name
= m_cache
->same_cached_name (op1
, op2
))
1337 tf_range op1_range
, op2_range
;
1338 bool ok
= m_cache
->get_range (op1_range
, op1
, cached_name
);
1339 ok
= ok
&& m_cache
->get_range (op2_range
, op2
, cached_name
);
1340 ok
= ok
&& logical_combine (r_true_side
, code
, m_bool_one
,
1341 op1_range
, op2_range
);
1342 ok
= ok
&& logical_combine (r_false_side
, code
, m_bool_zero
,
1343 op1_range
, op2_range
);
1344 gcc_checking_assert (ok
);
1346 m_cache
->set_range (lhs
, cached_name
,
1347 tf_range (r_true_side
, r_false_side
));