1 /* Gimple range GORI functions.
2 Copyright (C) 2017-2020 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
);
233 bool def_chain_in_export_p (tree name
, basic_block bb
);
236 void dump (FILE *f
, basic_block bb
);
238 bitmap_obstack m_bitmaps
;
239 vec
<bitmap
> m_outgoing
; // BB: Outgoing ranges calculatable on edges
240 void maybe_add_gori (tree name
, basic_block bb
);
241 void calculate_gori (basic_block bb
);
242 bitmap
exports (basic_block bb
);
246 // Initialize a gori-map structure.
248 gori_map::gori_map ()
250 m_outgoing
.create (0);
251 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
252 bitmap_obstack_initialize (&m_bitmaps
);
255 // Free any memory the GORI map allocated.
257 gori_map::~gori_map ()
259 bitmap_obstack_release (&m_bitmaps
);
260 m_outgoing
.release ();
263 // Return the bitmap vector of all export from BB. Calculate if necessary.
266 gori_map::exports (basic_block bb
)
268 if (!m_outgoing
[bb
->index
])
270 return m_outgoing
[bb
->index
];
273 // Return true if NAME is can have ranges generated for it from basic
277 gori_map::is_export_p (tree name
, basic_block bb
)
279 return bitmap_bit_p (exports (bb
), SSA_NAME_VERSION (name
));
282 // Return true if any element in the def chain of NAME is in the
283 // export list for BB.
286 gori_map::def_chain_in_export_p (tree name
, basic_block bb
)
288 bitmap a
= exports (bb
);
289 bitmap b
= get_def_chain (name
);
291 return bitmap_intersect_p (a
, b
);
295 // If NAME is non-NULL and defined in block BB, calculate the def
296 // chain and add it to m_outgoing.
299 gori_map::maybe_add_gori (tree name
, basic_block bb
)
303 gimple
*s
= SSA_NAME_DEF_STMT (name
);
304 bitmap r
= get_def_chain (name
);
305 // Check if there is a def chain, and it is in this block.
306 if (r
&& gimple_bb (s
) == bb
)
307 bitmap_copy (m_outgoing
[bb
->index
], r
);
308 // Def chain doesn't include itself, and even if there isn't a
309 // def chain, this name should be added to exports.
310 bitmap_set_bit (m_outgoing
[bb
->index
], SSA_NAME_VERSION (name
));
314 // Calculate all the required information for BB.
317 gori_map::calculate_gori (basic_block bb
)
320 if (bb
->index
>= (signed int)m_outgoing
.length ())
321 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
322 gcc_checking_assert (m_outgoing
[bb
->index
] == NULL
);
323 m_outgoing
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
325 // If this block's last statement may generate range informaiton, go
327 gimple
*stmt
= gimple_outgoing_range_stmt_p (bb
);
330 if (is_a
<gcond
*> (stmt
))
332 gcond
*gc
= as_a
<gcond
*>(stmt
);
333 name
= gimple_range_ssa_p (gimple_cond_lhs (gc
));
334 maybe_add_gori (name
, gimple_bb (stmt
));
336 name
= gimple_range_ssa_p (gimple_cond_rhs (gc
));
337 maybe_add_gori (name
, gimple_bb (stmt
));
341 gswitch
*gs
= as_a
<gswitch
*>(stmt
);
342 name
= gimple_range_ssa_p (gimple_switch_index (gs
));
343 maybe_add_gori (name
, gimple_bb (stmt
));
347 // Dump the table information for BB to file F.
350 gori_map::dump (FILE *f
, basic_block bb
)
353 const char *header_string
= "bb%-4d ";
354 const char *header2
= " ";
355 bool printed_something
= false;;
359 // BB was not processed.
360 if (!m_outgoing
[bb
->index
])
363 // Dump the def chain for each SSA_NAME defined in BB.
364 for (x
= 1; x
< num_ssa_names
; x
++)
366 tree name
= ssa_name (x
);
369 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
370 bitmap chain
= (has_def_chain (name
) ? get_def_chain (name
) : NULL
);
371 if (stmt
&& gimple_bb (stmt
) == bb
&& chain
&& !bitmap_empty_p (chain
))
373 fprintf (f
, header_string
, bb
->index
);
374 header_string
= header2
;
376 print_generic_expr (f
, name
, TDF_SLIM
);
378 EXECUTE_IF_SET_IN_BITMAP (chain
, 0, y
, bi
)
380 print_generic_expr (f
, ssa_name (y
), TDF_SLIM
);
387 printed_something
|= header
;
389 // Now dump the export vector.
391 EXECUTE_IF_SET_IN_BITMAP (m_outgoing
[bb
->index
], 0, y
, bi
)
395 fprintf (f
, header_string
, bb
->index
);
396 fprintf (f
, "exports: ");
397 header_string
= header2
;
400 print_generic_expr (f
, ssa_name (y
), TDF_SLIM
);
406 printed_something
|= header
;
407 if (printed_something
)
411 // Dump the entire GORI map structure to file F.
414 gori_map::dump (FILE *f
)
417 FOR_EACH_BB_FN (bb
, cfun
)
420 if (m_outgoing
[bb
->index
])
431 // -------------------------------------------------------------------
433 // Construct a gori_compute object.
435 gori_compute::gori_compute ()
437 // Create a boolean_type true and false range.
438 m_bool_zero
= int_range
<2> (boolean_false_node
, boolean_false_node
);
439 m_bool_one
= int_range
<2> (boolean_true_node
, boolean_true_node
);
440 m_gori_map
= new gori_map
;
443 // Destruct a gori_compute_object.
445 gori_compute::~gori_compute ()
450 // Provide a default of VARYING for all incoming SSA names.
453 gori_compute::ssa_range_in_bb (irange
&r
, tree name
, basic_block
)
455 r
.set_varying (TREE_TYPE (name
));
459 gori_compute::expr_range_in_bb (irange
&r
, tree expr
, basic_block bb
)
461 if (gimple_range_ssa_p (expr
))
462 ssa_range_in_bb (r
, expr
, bb
);
464 get_tree_range (r
, expr
);
467 // Calculate the range for NAME if the lhs of statement S has the
468 // range LHS. Return the result in R. Return false if no range can be
472 gori_compute::compute_name_range_op (irange
&r
, gimple
*stmt
,
473 const irange
&lhs
, tree name
)
475 int_range_max op1_range
, op2_range
;
477 tree op1
= gimple_range_operand1 (stmt
);
478 tree op2
= gimple_range_operand2 (stmt
);
480 // Operand 1 is the name being looked for, evaluate it.
483 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
486 // The second parameter to a unary operation is the range
487 // for the type of operand1, but if it can be reduced
488 // further, the results will be better. Start with what we
489 // know of the range of OP1 instead of the full type.
490 return gimple_range_calc_op1 (r
, stmt
, lhs
, op1_range
);
492 // If we need the second operand, get a value and evaluate.
493 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
494 if (gimple_range_calc_op1 (r
, stmt
, lhs
, op2_range
))
495 r
.intersect (op1_range
);
503 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
504 expr_range_in_bb (r
, op2
, gimple_bb (stmt
));
505 if (gimple_range_calc_op2 (op2_range
, stmt
, lhs
, op1_range
))
506 r
.intersect (op2_range
);
512 // Given the switch S, return an evaluation in R for NAME when the lhs
513 // evaluates to LHS. Returning false means the name being looked for
514 // was not resolvable.
517 gori_compute::compute_operand_range_switch (irange
&r
, gswitch
*s
,
521 tree op1
= gimple_switch_index (s
);
523 // If name matches, the range is simply the range from the edge.
524 // Empty ranges are viral as they are on a path which isn't
526 if (op1
== name
|| lhs
.undefined_p ())
532 // If op1 is in the defintion chain, pass lhs back.
533 if (gimple_range_ssa_p (op1
) && m_gori_map
->in_chain_p (name
, op1
))
534 return compute_operand_range (r
, SSA_NAME_DEF_STMT (op1
), lhs
, name
);
539 // Return TRUE if GS is a logical && or || expression.
542 is_gimple_logical_p (const gimple
*gs
)
544 // Look for boolean and/or condition.
545 if (gimple_code (gs
) == GIMPLE_ASSIGN
)
546 switch (gimple_expr_code (gs
))
554 // Bitwise operations on single bits are logical too.
555 if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs
)),
566 // Return an evaluation for NAME as it would appear in STMT when the
567 // statement's lhs evaluates to LHS. If successful, return TRUE and
568 // store the evaluation in R, otherwise return FALSE.
571 gori_compute::compute_operand_range (irange
&r
, gimple
*stmt
,
572 const irange
&lhs
, tree name
)
574 // Empty ranges are viral as they are on an unexecutable path.
575 if (lhs
.undefined_p ())
580 if (is_a
<gswitch
*> (stmt
))
581 return compute_operand_range_switch (r
, as_a
<gswitch
*> (stmt
), lhs
, name
);
582 if (!gimple_range_handler (stmt
))
585 tree op1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
586 tree op2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
588 // The base ranger handles NAME on this statement.
589 if (op1
== name
|| op2
== name
)
590 return compute_name_range_op (r
, stmt
, lhs
, name
);
592 if (is_gimple_logical_p (stmt
))
593 return compute_logical_operands (r
, stmt
, lhs
, name
);
595 // NAME is not in this stmt, but one of the names in it ought to be
597 bool op1_in_chain
= op1
&& m_gori_map
->in_chain_p (name
, op1
);
598 bool op2_in_chain
= op2
&& m_gori_map
->in_chain_p (name
, op2
);
599 if (op1_in_chain
&& op2_in_chain
)
600 return compute_operand1_and_operand2_range (r
, stmt
, lhs
, name
);
602 return compute_operand1_range (r
, stmt
, lhs
, name
);
604 return compute_operand2_range (r
, stmt
, lhs
, name
);
606 // If neither operand is derived, this statement tells us nothing.
610 // Return TRUE if range R is either a true or false compatible range.
613 range_is_either_true_or_false (const irange
&r
)
615 if (r
.undefined_p ())
618 // This is complicated by the fact that Ada has multi-bit booleans,
619 // so true can be ~[0, 0] (i.e. [1,MAX]).
620 tree type
= r
.type ();
621 gcc_checking_assert (range_compatible_p (type
, boolean_type_node
));
622 return (r
.singleton_p () || !r
.contains_p (build_zero_cst (type
)));
625 // A pair of ranges for true/false paths.
630 tf_range (const irange
&t_range
, const irange
&f_range
)
632 true_range
= t_range
;
633 false_range
= f_range
;
635 int_range_max true_range
, false_range
;
638 // Evaluate a binary logical expression by combining the true and
639 // false ranges for each of the operands based on the result value in
643 gori_compute::logical_combine (irange
&r
, enum tree_code code
,
645 const tf_range
&op1
, const tf_range
&op2
)
647 if (op1
.true_range
.varying_p ()
648 && op1
.false_range
.varying_p ()
649 && op2
.true_range
.varying_p ()
650 && op2
.false_range
.varying_p ())
653 // This is not a simple fold of a logical expression, rather it
654 // determines ranges which flow through the logical expression.
656 // Assuming x_8 is an unsigned char, and relational statements:
659 // consider the logical expression and branch:
663 // To determine the range of x_8 on either edge of the branch, one
664 // must first determine what the range of x_8 is when the boolean
665 // values of b_1 and b_2 are both true and false.
666 // b_1 TRUE x_8 = [0, 19]
667 // b_1 FALSE x_8 = [20, 255]
668 // b_2 TRUE x_8 = [6, 255]
669 // b_2 FALSE x_8 = [0,5].
671 // These ranges are then combined based on the expected outcome of
672 // the branch. The range on the TRUE side of the branch must satisfy
673 // b_1 == true && b_2 == true
675 // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
676 // must be true. The range of x_8 on the true side must be the
677 // intersection of both ranges since both must be true. Thus the
678 // range of x_8 on the true side is [6, 19].
680 // To determine the ranges on the FALSE side, all 3 combinations of
681 // failing ranges must be considered, and combined as any of them
682 // can cause the false result.
684 // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
685 // FALSE results and combine them. If we fell back to VARYING any
686 // range restrictions that have been discovered up to this point
688 if (!range_is_either_true_or_false (lhs
))
691 if (logical_combine (r1
, code
, m_bool_zero
, op1
, op2
)
692 && logical_combine (r
, code
, m_bool_one
, op1
, op2
))
702 // A logical AND combines ranges from 2 boolean conditions.
708 // The TRUE side is the intersection of the the 2 true ranges.
710 r
.intersect (op2
.true_range
);
714 // The FALSE side is the union of the other 3 cases.
715 int_range_max
ff (op1
.false_range
);
716 ff
.intersect (op2
.false_range
);
717 int_range_max
tf (op1
.true_range
);
718 tf
.intersect (op2
.false_range
);
719 int_range_max
ft (op1
.false_range
);
720 ft
.intersect (op2
.true_range
);
726 // A logical OR combines ranges from 2 boolean conditons.
732 // An OR operation will only take the FALSE path if both
733 // operands are false simlulateously, which means they should
734 // be intersected. !(x || y) == !x && !y
736 r
.intersect (op2
.false_range
);
740 // The TRUE side of an OR operation will be the union of
741 // the other three combinations.
742 int_range_max
tt (op1
.true_range
);
743 tt
.intersect (op2
.true_range
);
744 int_range_max
tf (op1
.true_range
);
745 tf
.intersect (op2
.false_range
);
746 int_range_max
ft (op1
.false_range
);
747 ft
.intersect (op2
.true_range
);
760 // Helper function for compute_logical_operands_in_chain that computes
761 // the range of logical statements that can be computed without
762 // chasing down operands. These are things like [0 = x | y] where we
763 // know neither operand can be non-zero, or [1 = x & y] where we know
764 // neither operand can be zero.
767 gori_compute::optimize_logical_operands (tf_range
&range
,
773 enum tree_code code
= gimple_expr_code (stmt
);
775 // Optimize [0 = x | y], since neither operand can ever be non-zero.
776 if ((code
== BIT_IOR_EXPR
|| code
== TRUTH_OR_EXPR
) && lhs
.zero_p ())
778 if (!compute_operand_range (range
.false_range
, SSA_NAME_DEF_STMT (op
),
780 expr_range_in_bb (range
.false_range
, name
, gimple_bb (stmt
));
781 range
.true_range
= range
.false_range
;
784 // Optimize [1 = x & y], since neither operand can ever be zero.
785 if ((code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
) && lhs
== m_bool_one
)
787 if (!compute_operand_range (range
.true_range
, SSA_NAME_DEF_STMT (op
),
789 expr_range_in_bb (range
.true_range
, name
, gimple_bb (stmt
));
790 range
.false_range
= range
.true_range
;
796 // Given a logical STMT, calculate true and false ranges for each
797 // potential path of NAME, assuming NAME came through the OP chain if
798 // OP_IN_CHAIN is true.
801 gori_compute::compute_logical_operands_in_chain (tf_range
&range
,
805 tree op
, bool op_in_chain
)
807 gimple
*src_stmt
= gimple_range_ssa_p (op
) ? SSA_NAME_DEF_STMT (op
) : NULL
;
808 basic_block bb
= gimple_bb (stmt
);
809 if (!op_in_chain
|| (src_stmt
!= NULL
&& bb
!= gimple_bb (src_stmt
)))
811 // If op is not in the def chain, or defined in this block,
812 // use its known value on entry to the block.
813 expr_range_in_bb (range
.true_range
, name
, gimple_bb (stmt
));
814 range
.false_range
= range
.true_range
;
817 if (optimize_logical_operands (range
, stmt
, lhs
, name
, op
))
820 // Calculate ranges for true and false on both sides, since the false
821 // path is not always a simple inversion of the true side.
822 if (!compute_operand_range (range
.true_range
, src_stmt
, m_bool_one
, name
))
823 expr_range_in_bb (range
.true_range
, name
, bb
);
824 if (!compute_operand_range (range
.false_range
, src_stmt
, m_bool_zero
, name
))
825 expr_range_in_bb (range
.false_range
, name
, bb
);
828 // Given a logical STMT, calculate true and false for each potential
829 // path using NAME, and resolve the outcome based on the logical
833 gori_compute::compute_logical_operands (irange
&r
, gimple
*stmt
,
837 // Reaching this point means NAME is not in this stmt, but one of
838 // the names in it ought to be derived from it.
839 tree op1
= gimple_range_operand1 (stmt
);
840 tree op2
= gimple_range_operand2 (stmt
);
841 gcc_checking_assert (op1
!= name
&& op2
!= name
);
843 bool op1_in_chain
= (gimple_range_ssa_p (op1
)
844 && m_gori_map
->in_chain_p (name
, op1
));
845 bool op2_in_chain
= (gimple_range_ssa_p (op2
)
846 && m_gori_map
->in_chain_p (name
, op2
));
848 // If neither operand is derived, then this stmt tells us nothing.
849 if (!op1_in_chain
&& !op2_in_chain
)
852 tf_range op1_range
, op2_range
;
853 compute_logical_operands_in_chain (op1_range
, stmt
, lhs
,
854 name
, op1
, op1_in_chain
);
855 compute_logical_operands_in_chain (op2_range
, stmt
, lhs
,
856 name
, op2
, op2_in_chain
);
857 return logical_combine (r
, gimple_expr_code (stmt
), lhs
,
858 op1_range
, op2_range
);
861 // Calculate a range for NAME from the operand 1 position of STMT
862 // assuming the result of the statement is LHS. Return the range in
863 // R, or false if no range could be calculated.
866 gori_compute::compute_operand1_range (irange
&r
, gimple
*stmt
,
867 const irange
&lhs
, tree name
)
869 int_range_max op1_range
, op2_range
;
870 tree op1
= gimple_range_operand1 (stmt
);
871 tree op2
= gimple_range_operand2 (stmt
);
873 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
875 // Now calcuated the operand and put that result in r.
878 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
879 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op2_range
))
884 // We pass op1_range to the unary operation. Nomally it's a
885 // hidden range_for_type parameter, but sometimes having the
886 // actual range can result in better information.
887 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op1_range
))
891 // Intersect the calculated result with the known result.
892 op1_range
.intersect (r
);
894 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op1
);
895 // If def stmt is outside of this BB, then name must be an import.
896 if (!src_stmt
|| (gimple_bb (src_stmt
) != gimple_bb (stmt
)))
898 // If this isn't the right import statement, then abort calculation.
899 if (!src_stmt
|| gimple_get_lhs (src_stmt
) != name
)
901 return compute_name_range_op (r
, src_stmt
, op1_range
, name
);
903 // Then feed this range back as the LHS of the defining statement.
904 return compute_operand_range (r
, src_stmt
, op1_range
, name
);
908 // Calculate a range for NAME from the operand 2 position of S
909 // assuming the result of the statement is LHS. Return the range in
910 // R, or false if no range could be calculated.
913 gori_compute::compute_operand2_range (irange
&r
, gimple
*stmt
,
914 const irange
&lhs
, tree name
)
916 int_range_max op1_range
, op2_range
;
917 tree op1
= gimple_range_operand1 (stmt
);
918 tree op2
= gimple_range_operand2 (stmt
);
920 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
921 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
923 // Intersect with range for op2 based on lhs and op1.
924 if (!gimple_range_calc_op2 (r
, stmt
, lhs
, op1_range
))
926 op2_range
.intersect (r
);
928 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op2
);
929 // If def stmt is outside of this BB, then name must be an import.
930 if (!src_stmt
|| (gimple_bb (src_stmt
) != gimple_bb (stmt
)))
932 // If this isn't the right src statement, then abort calculation.
933 if (!src_stmt
|| gimple_get_lhs (src_stmt
) != name
)
935 return compute_name_range_op (r
, src_stmt
, op2_range
, name
);
937 // Then feed this range back as the LHS of the defining statement.
938 return compute_operand_range (r
, src_stmt
, op2_range
, name
);
941 // Calculate a range for NAME from both operand positions of S
942 // assuming the result of the statement is LHS. Return the range in
943 // R, or false if no range could be calculated.
946 gori_compute::compute_operand1_and_operand2_range
952 int_range_max op_range
;
954 // Calculate a good a range for op2. Since op1 == op2, this will
955 // have already included whatever the actual range of name is.
956 if (!compute_operand2_range (op_range
, stmt
, lhs
, name
))
959 // Now get the range thru op1.
960 if (!compute_operand1_range (r
, stmt
, lhs
, name
))
963 // Whichever range is the most permissive is the one we need to
964 // use. (?) OR is that true? Maybe this should be intersection?
969 // Return TRUE if a range can be calcalated for NAME on edge E.
972 gori_compute::has_edge_range_p (edge e
, tree name
)
974 return (m_gori_map
->is_export_p (name
, e
->src
)
975 || m_gori_map
->def_chain_in_export_p (name
, e
->src
));
978 // Dump what is known to GORI computes to listing file F.
981 gori_compute::dump (FILE *f
)
983 m_gori_map
->dump (f
);
986 // Calculate a range on edge E and return it in R. Try to evaluate a
987 // range for NAME on this edge. Return FALSE if this is either not a
988 // control edge or NAME is not defined by this edge.
991 gori_compute::outgoing_edge_range_p (irange
&r
, edge e
, tree name
)
995 gcc_checking_assert (gimple_range_ssa_p (name
));
996 // Determine if there is an outgoing edge.
997 gimple
*stmt
= outgoing
.edge_range_p (lhs
, e
);
1001 // If NAME can be calculated on the edge, use that.
1002 if (m_gori_map
->is_export_p (name
, e
->src
))
1004 if (compute_operand_range (r
, stmt
, lhs
, name
))
1006 // Sometimes compatible types get interchanged. See PR97360.
1007 // Make sure we are returning the type of the thing we asked for.
1008 if (!r
.undefined_p () && r
.type () != TREE_TYPE (name
))
1010 gcc_checking_assert (range_compatible_p (r
.type (),
1012 range_cast (r
, TREE_TYPE (name
));
1020 // --------------------------------------------------------------------------
1022 // Cache for SSAs that appear on the RHS of a boolean assignment.
1024 // Boolean assignments of logical expressions (i.e. LHS = j_5 > 999)
1025 // have SSA operands whose range depend on the LHS of the assigment.
1026 // That is, the range of j_5 when LHS is true is different than when
1029 // This class caches the TRUE/FALSE ranges of such SSAs to avoid
1032 class logical_stmt_cache
1035 logical_stmt_cache ();
1036 ~logical_stmt_cache ();
1037 void set_range (tree lhs
, tree name
, const tf_range
&);
1038 bool get_range (tf_range
&r
, tree lhs
, tree name
) const;
1039 bool cacheable_p (gimple
*, const irange
*lhs_range
= NULL
) const;
1040 void dump (FILE *, gimple
*stmt
) const;
1041 tree
same_cached_name (tree lhs1
, tree lh2
) const;
1043 tree
cached_name (tree lhs
) const;
1044 void slot_diagnostics (tree lhs
, const tf_range
&range
) const;
1047 cache_entry (tree name
, const irange
&t_range
, const irange
&f_range
);
1048 void dump (FILE *out
) const;
1052 vec
<cache_entry
*> m_ssa_cache
;
1055 logical_stmt_cache::cache_entry::cache_entry (tree name
,
1056 const irange
&t_range
,
1057 const irange
&f_range
)
1058 : name (name
), range (t_range
, f_range
)
1062 logical_stmt_cache::logical_stmt_cache ()
1064 m_ssa_cache
.create (num_ssa_names
+ num_ssa_names
/ 10);
1065 m_ssa_cache
.safe_grow_cleared (num_ssa_names
);
1068 logical_stmt_cache::~logical_stmt_cache ()
1070 for (unsigned i
= 0; i
< m_ssa_cache
.length (); ++i
)
1072 delete m_ssa_cache
[i
];
1073 m_ssa_cache
.release ();
1076 // Dump cache_entry to OUT.
1079 logical_stmt_cache::cache_entry::dump (FILE *out
) const
1081 fprintf (out
, "name=");
1082 print_generic_expr (out
, name
, TDF_SLIM
);
1084 range
.true_range
.dump (out
);
1085 fprintf (out
, ", ");
1086 range
.false_range
.dump (out
);
1087 fprintf (out
, "\n");
1090 // Update range for cache entry of NAME as it appears in the defining
1091 // statement of LHS.
1094 logical_stmt_cache::set_range (tree lhs
, tree name
, const tf_range
&range
)
1096 unsigned version
= SSA_NAME_VERSION (lhs
);
1097 if (version
>= m_ssa_cache
.length ())
1098 m_ssa_cache
.safe_grow_cleared (num_ssa_names
+ num_ssa_names
/ 10);
1100 cache_entry
*slot
= m_ssa_cache
[version
];
1101 slot_diagnostics (lhs
, range
);
1104 // The IL must have changed. Update the carried SSA name for
1105 // consistency. Testcase is libgomp.fortran/doacross1.f90.
1106 if (slot
->name
!= name
)
1110 m_ssa_cache
[version
]
1111 = new cache_entry (name
, range
.true_range
, range
.false_range
);
1114 // If there is a cached entry of NAME, set it in R and return TRUE,
1115 // otherwise return FALSE. LHS is the defining statement where NAME
1119 logical_stmt_cache::get_range (tf_range
&r
, tree lhs
, tree name
) const
1121 gcc_checking_assert (cacheable_p (SSA_NAME_DEF_STMT (lhs
)));
1122 if (cached_name (lhs
) == name
)
1124 unsigned version
= SSA_NAME_VERSION (lhs
);
1125 if (m_ssa_cache
[version
])
1127 r
= m_ssa_cache
[version
]->range
;
1134 // If the defining statement of LHS is in the cache, return the SSA
1135 // operand being cached. That is, return SSA for LHS = SSA .RELOP. OP2.
1138 logical_stmt_cache::cached_name (tree lhs
) const
1140 unsigned version
= SSA_NAME_VERSION (lhs
);
1142 if (version
>= m_ssa_cache
.length ())
1145 if (m_ssa_cache
[version
])
1146 return m_ssa_cache
[version
]->name
;
1150 // Return TRUE if the cached name for LHS1 is the same as the
1151 // cached name for LHS2.
1154 logical_stmt_cache::same_cached_name (tree lhs1
, tree lhs2
) const
1156 tree name
= cached_name (lhs1
);
1157 if (name
&& name
== cached_name (lhs2
))
1162 // Return TRUE if STMT is a statement we are interested in caching.
1163 // LHS_RANGE is any known range for the LHS of STMT.
1166 logical_stmt_cache::cacheable_p (gimple
*stmt
, const irange
*lhs_range
) const
1168 if (gimple_code (stmt
) == GIMPLE_ASSIGN
1169 && types_compatible_p (TREE_TYPE (gimple_assign_lhs (stmt
)),
1171 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
1173 switch (gimple_expr_code (stmt
))
1175 case TRUTH_AND_EXPR
:
1179 return !lhs_range
|| range_is_either_true_or_false (*lhs_range
);
1187 // Output debugging diagnostics for the cache entry for LHS. RANGE is
1188 // the new range that is being cached.
1191 logical_stmt_cache::slot_diagnostics (tree lhs
, const tf_range
&range
) const
1193 gimple
*stmt
= SSA_NAME_DEF_STMT (lhs
);
1194 unsigned version
= SSA_NAME_VERSION (lhs
);
1195 cache_entry
*slot
= m_ssa_cache
[version
];
1199 if (DEBUG_RANGE_CACHE
)
1201 fprintf (dump_file
? dump_file
: stderr
, "registering range for: ");
1202 dump (dump_file
? dump_file
: stderr
, stmt
);
1206 if (DEBUG_RANGE_CACHE
)
1207 fprintf (dump_file
? dump_file
: stderr
,
1208 "reusing range for SSA #%d\n", version
);
1209 if (CHECKING_P
&& (slot
->range
.true_range
!= range
.true_range
1210 || slot
->range
.false_range
!= range
.false_range
))
1212 fprintf (stderr
, "FATAL: range altered for cached: ");
1213 dump (stderr
, stmt
);
1214 fprintf (stderr
, "Attempt to change to:\n");
1215 fprintf (stderr
, "TRUE=");
1216 range
.true_range
.dump (stderr
);
1217 fprintf (stderr
, ", FALSE=");
1218 range
.false_range
.dump (stderr
);
1219 fprintf (stderr
, "\n");
1224 // Dump the cache information for STMT.
1227 logical_stmt_cache::dump (FILE *out
, gimple
*stmt
) const
1229 tree lhs
= gimple_assign_lhs (stmt
);
1230 cache_entry
*entry
= m_ssa_cache
[SSA_NAME_VERSION (lhs
)];
1232 print_gimple_stmt (out
, stmt
, 0, TDF_SLIM
);
1235 fprintf (out
, "\tname = ");
1236 print_generic_expr (out
, entry
->name
);
1237 fprintf (out
, " lhs(%d)= ", SSA_NAME_VERSION (lhs
));
1238 print_generic_expr (out
, lhs
);
1239 fprintf (out
, "\n\tTRUE=");
1240 entry
->range
.true_range
.dump (out
);
1241 fprintf (out
, ", FALSE=");
1242 entry
->range
.false_range
.dump (out
);
1243 fprintf (out
, "\n");
1246 fprintf (out
, "[EMPTY]\n");
1249 gori_compute_cache::gori_compute_cache ()
1251 m_cache
= new logical_stmt_cache
;
1254 gori_compute_cache::~gori_compute_cache ()
1259 // Caching version of compute_operand_range. If NAME, as it appears
1260 // in STMT, has already been cached return it from the cache,
1261 // otherwise compute the operand range as normal and cache it.
1264 gori_compute_cache::compute_operand_range (irange
&r
, gimple
*stmt
,
1265 const irange
&lhs_range
, tree name
)
1267 bool cacheable
= m_cache
->cacheable_p (stmt
, &lhs_range
);
1270 tree lhs
= gimple_assign_lhs (stmt
);
1272 if (m_cache
->get_range (range
, lhs
, name
))
1274 if (lhs_range
.zero_p ())
1275 r
= range
.false_range
;
1277 r
= range
.true_range
;
1281 if (super::compute_operand_range (r
, stmt
, lhs_range
, name
))
1290 // Cache STMT if possible.
1293 gori_compute_cache::cache_stmt (gimple
*stmt
)
1295 gcc_checking_assert (m_cache
->cacheable_p (stmt
));
1296 enum tree_code code
= gimple_expr_code (stmt
);
1297 tree lhs
= gimple_assign_lhs (stmt
);
1298 tree op1
= gimple_range_operand1 (stmt
);
1299 tree op2
= gimple_range_operand2 (stmt
);
1300 int_range_max r_true_side
, r_false_side
;
1302 // LHS = s_5 && 999.
1303 if (TREE_CODE (op2
) == INTEGER_CST
)
1305 range_operator
*handler
= range_op_handler (code
, TREE_TYPE (lhs
));
1306 int_range_max op2_range
;
1307 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
1308 tree type
= TREE_TYPE (op1
);
1309 handler
->op1_range (r_true_side
, type
, m_bool_one
, op2_range
);
1310 handler
->op1_range (r_false_side
, type
, m_bool_zero
, op2_range
);
1311 m_cache
->set_range (lhs
, op1
, tf_range (r_true_side
, r_false_side
));
1313 // LHS = s_5 && b_8.
1314 else if (tree cached_name
= m_cache
->same_cached_name (op1
, op2
))
1316 tf_range op1_range
, op2_range
;
1317 bool ok
= m_cache
->get_range (op1_range
, op1
, cached_name
);
1318 ok
= ok
&& m_cache
->get_range (op2_range
, op2
, cached_name
);
1319 ok
= ok
&& logical_combine (r_true_side
, code
, m_bool_one
,
1320 op1_range
, op2_range
);
1321 ok
= ok
&& logical_combine (r_false_side
, code
, m_bool_zero
,
1322 op1_range
, op2_range
);
1323 gcc_checking_assert (ok
);
1325 m_cache
->set_range (lhs
, cached_name
,
1326 tf_range (r_true_side
, r_false_side
));