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
);
235 void set_range_invariant (tree name
);
238 void dump (FILE *f
, basic_block bb
);
240 bitmap_obstack m_bitmaps
;
241 vec
<bitmap
> m_outgoing
; // BB: Outgoing ranges calculatable on edges
242 bitmap m_maybe_variant
; // Names which might have outgoing ranges.
243 void maybe_add_gori (tree name
, basic_block bb
);
244 void calculate_gori (basic_block bb
);
248 // Initialize a gori-map structure.
250 gori_map::gori_map ()
252 m_outgoing
.create (0);
253 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
254 bitmap_obstack_initialize (&m_bitmaps
);
255 m_maybe_variant
= BITMAP_ALLOC (&m_bitmaps
);
258 // Free any memory the GORI map allocated.
260 gori_map::~gori_map ()
262 bitmap_obstack_release (&m_bitmaps
);
263 m_outgoing
.release ();
266 // Return the bitmap vector of all export from BB. Calculate if necessary.
269 gori_map::exports (basic_block bb
)
271 if (!m_outgoing
[bb
->index
])
273 return m_outgoing
[bb
->index
];
276 // Return true if NAME is can have ranges generated for it from basic
280 gori_map::is_export_p (tree name
, basic_block bb
)
282 // If no BB is specified, test if it is exported anywhere in the IL.
284 return bitmap_bit_p (m_maybe_variant
, SSA_NAME_VERSION (name
));
285 return bitmap_bit_p (exports (bb
), SSA_NAME_VERSION (name
));
288 // Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
291 gori_map::set_range_invariant (tree name
)
293 bitmap_clear_bit (m_maybe_variant
, SSA_NAME_VERSION (name
));
296 // Return true if any element in the def chain of NAME is in the
297 // export list for BB.
300 gori_map::def_chain_in_export_p (tree name
, basic_block bb
)
302 bitmap a
= exports (bb
);
303 bitmap b
= get_def_chain (name
);
305 return bitmap_intersect_p (a
, b
);
309 // If NAME is non-NULL and defined in block BB, calculate the def
310 // chain and add it to m_outgoing.
313 gori_map::maybe_add_gori (tree name
, basic_block bb
)
317 gimple
*s
= SSA_NAME_DEF_STMT (name
);
318 bitmap r
= get_def_chain (name
);
319 // Check if there is a def chain, and it is in this block.
320 if (r
&& gimple_bb (s
) == bb
)
321 bitmap_copy (m_outgoing
[bb
->index
], r
);
322 // Def chain doesn't include itself, and even if there isn't a
323 // def chain, this name should be added to exports.
324 bitmap_set_bit (m_outgoing
[bb
->index
], SSA_NAME_VERSION (name
));
328 // Calculate all the required information for BB.
331 gori_map::calculate_gori (basic_block bb
)
334 if (bb
->index
>= (signed int)m_outgoing
.length ())
335 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
336 gcc_checking_assert (m_outgoing
[bb
->index
] == NULL
);
337 m_outgoing
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
339 // If this block's last statement may generate range informaiton, go
341 gimple
*stmt
= gimple_outgoing_range_stmt_p (bb
);
344 if (is_a
<gcond
*> (stmt
))
346 gcond
*gc
= as_a
<gcond
*>(stmt
);
347 name
= gimple_range_ssa_p (gimple_cond_lhs (gc
));
348 maybe_add_gori (name
, gimple_bb (stmt
));
350 name
= gimple_range_ssa_p (gimple_cond_rhs (gc
));
351 maybe_add_gori (name
, gimple_bb (stmt
));
355 gswitch
*gs
= as_a
<gswitch
*>(stmt
);
356 name
= gimple_range_ssa_p (gimple_switch_index (gs
));
357 maybe_add_gori (name
, gimple_bb (stmt
));
359 // Add this bitmap to the aggregate list of all outgoing names.
360 bitmap_ior_into (m_maybe_variant
, m_outgoing
[bb
->index
]);
363 // Dump the table information for BB to file F.
366 gori_map::dump (FILE *f
, basic_block bb
)
369 const char *header_string
= "bb%-4d ";
370 const char *header2
= " ";
371 bool printed_something
= false;;
375 // BB was not processed.
376 if (!m_outgoing
[bb
->index
])
379 // Dump the def chain for each SSA_NAME defined in BB.
380 for (x
= 1; x
< num_ssa_names
; x
++)
382 tree name
= ssa_name (x
);
385 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
386 bitmap chain
= (has_def_chain (name
) ? get_def_chain (name
) : NULL
);
387 if (stmt
&& gimple_bb (stmt
) == bb
&& chain
&& !bitmap_empty_p (chain
))
389 fprintf (f
, header_string
, bb
->index
);
390 header_string
= header2
;
392 print_generic_expr (f
, name
, TDF_SLIM
);
394 EXECUTE_IF_SET_IN_BITMAP (chain
, 0, y
, bi
)
396 print_generic_expr (f
, ssa_name (y
), TDF_SLIM
);
403 printed_something
|= header
;
405 // Now dump the export vector.
407 EXECUTE_IF_SET_IN_BITMAP (m_outgoing
[bb
->index
], 0, y
, bi
)
411 fprintf (f
, header_string
, bb
->index
);
412 fprintf (f
, "exports: ");
413 header_string
= header2
;
416 print_generic_expr (f
, ssa_name (y
), TDF_SLIM
);
422 printed_something
|= header
;
423 if (printed_something
)
427 // Dump the entire GORI map structure to file F.
430 gori_map::dump (FILE *f
)
433 FOR_EACH_BB_FN (bb
, cfun
)
436 if (m_outgoing
[bb
->index
])
447 // -------------------------------------------------------------------
449 // Construct a gori_compute object.
451 gori_compute::gori_compute ()
453 // Create a boolean_type true and false range.
454 m_bool_zero
= int_range
<2> (boolean_false_node
, boolean_false_node
);
455 m_bool_one
= int_range
<2> (boolean_true_node
, boolean_true_node
);
456 m_gori_map
= new gori_map
;
457 unsigned x
, lim
= last_basic_block_for_fn (cfun
);
458 // Calculate outgoing range info upfront. This will fully populate the
459 // m_maybe_variant bitmap which will help eliminate processing of names
460 // which never have their ranges adjusted.
461 for (x
= 0; x
< lim
; x
++)
463 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, x
);
465 m_gori_map
->exports (bb
);
469 // Destruct a gori_compute_object.
471 gori_compute::~gori_compute ()
476 // Provide a default of VARYING for all incoming SSA names.
479 gori_compute::ssa_range_in_bb (irange
&r
, tree name
, basic_block
)
481 r
.set_varying (TREE_TYPE (name
));
485 gori_compute::expr_range_in_bb (irange
&r
, tree expr
, basic_block bb
)
487 if (gimple_range_ssa_p (expr
))
488 ssa_range_in_bb (r
, expr
, bb
);
490 get_tree_range (r
, expr
);
493 // Calculate the range for NAME if the lhs of statement S has the
494 // range LHS. Return the result in R. Return false if no range can be
498 gori_compute::compute_name_range_op (irange
&r
, gimple
*stmt
,
499 const irange
&lhs
, tree name
)
501 int_range_max op1_range
, op2_range
;
503 tree op1
= gimple_range_operand1 (stmt
);
504 tree op2
= gimple_range_operand2 (stmt
);
506 // Operand 1 is the name being looked for, evaluate it.
509 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
512 // The second parameter to a unary operation is the range
513 // for the type of operand1, but if it can be reduced
514 // further, the results will be better. Start with what we
515 // know of the range of OP1 instead of the full type.
516 return gimple_range_calc_op1 (r
, stmt
, lhs
, op1_range
);
518 // If we need the second operand, get a value and evaluate.
519 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
520 if (gimple_range_calc_op1 (r
, stmt
, lhs
, op2_range
))
521 r
.intersect (op1_range
);
529 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
530 expr_range_in_bb (r
, op2
, gimple_bb (stmt
));
531 if (gimple_range_calc_op2 (op2_range
, stmt
, lhs
, op1_range
))
532 r
.intersect (op2_range
);
538 // Given the switch S, return an evaluation in R for NAME when the lhs
539 // evaluates to LHS. Returning false means the name being looked for
540 // was not resolvable.
543 gori_compute::compute_operand_range_switch (irange
&r
, gswitch
*s
,
547 tree op1
= gimple_switch_index (s
);
549 // If name matches, the range is simply the range from the edge.
550 // Empty ranges are viral as they are on a path which isn't
552 if (op1
== name
|| lhs
.undefined_p ())
558 // If op1 is in the defintion chain, pass lhs back.
559 if (gimple_range_ssa_p (op1
) && m_gori_map
->in_chain_p (name
, op1
))
560 return compute_operand_range (r
, SSA_NAME_DEF_STMT (op1
), lhs
, name
);
565 // Return TRUE if GS is a logical && or || expression.
568 is_gimple_logical_p (const gimple
*gs
)
570 // Look for boolean and/or condition.
571 if (gimple_code (gs
) == GIMPLE_ASSIGN
)
572 switch (gimple_expr_code (gs
))
580 // Bitwise operations on single bits are logical too.
581 if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs
)),
592 // Return an evaluation for NAME as it would appear in STMT when the
593 // statement's lhs evaluates to LHS. If successful, return TRUE and
594 // store the evaluation in R, otherwise return FALSE.
597 gori_compute::compute_operand_range (irange
&r
, gimple
*stmt
,
598 const irange
&lhs
, tree name
)
600 // Empty ranges are viral as they are on an unexecutable path.
601 if (lhs
.undefined_p ())
606 if (is_a
<gswitch
*> (stmt
))
607 return compute_operand_range_switch (r
, as_a
<gswitch
*> (stmt
), lhs
, name
);
608 if (!gimple_range_handler (stmt
))
611 tree op1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
612 tree op2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
614 // The base ranger handles NAME on this statement.
615 if (op1
== name
|| op2
== name
)
616 return compute_name_range_op (r
, stmt
, lhs
, name
);
618 if (is_gimple_logical_p (stmt
))
619 return compute_logical_operands (r
, stmt
, lhs
, name
);
621 // NAME is not in this stmt, but one of the names in it ought to be
623 bool op1_in_chain
= op1
&& m_gori_map
->in_chain_p (name
, op1
);
624 bool op2_in_chain
= op2
&& m_gori_map
->in_chain_p (name
, op2
);
625 if (op1_in_chain
&& op2_in_chain
)
626 return compute_operand1_and_operand2_range (r
, stmt
, lhs
, name
);
628 return compute_operand1_range (r
, stmt
, lhs
, name
);
630 return compute_operand2_range (r
, stmt
, lhs
, name
);
632 // If neither operand is derived, this statement tells us nothing.
636 // Return TRUE if range R is either a true or false compatible range.
639 range_is_either_true_or_false (const irange
&r
)
641 if (r
.undefined_p ())
644 // This is complicated by the fact that Ada has multi-bit booleans,
645 // so true can be ~[0, 0] (i.e. [1,MAX]).
646 tree type
= r
.type ();
647 gcc_checking_assert (range_compatible_p (type
, boolean_type_node
));
648 return (r
.singleton_p () || !r
.contains_p (build_zero_cst (type
)));
651 // A pair of ranges for true/false paths.
656 tf_range (const irange
&t_range
, const irange
&f_range
)
658 true_range
= t_range
;
659 false_range
= f_range
;
661 int_range_max true_range
, false_range
;
664 // Evaluate a binary logical expression by combining the true and
665 // false ranges for each of the operands based on the result value in
669 gori_compute::logical_combine (irange
&r
, enum tree_code code
,
671 const tf_range
&op1
, const tf_range
&op2
)
673 if (op1
.true_range
.varying_p ()
674 && op1
.false_range
.varying_p ()
675 && op2
.true_range
.varying_p ()
676 && op2
.false_range
.varying_p ())
679 // This is not a simple fold of a logical expression, rather it
680 // determines ranges which flow through the logical expression.
682 // Assuming x_8 is an unsigned char, and relational statements:
685 // consider the logical expression and branch:
689 // To determine the range of x_8 on either edge of the branch, one
690 // must first determine what the range of x_8 is when the boolean
691 // values of b_1 and b_2 are both true and false.
692 // b_1 TRUE x_8 = [0, 19]
693 // b_1 FALSE x_8 = [20, 255]
694 // b_2 TRUE x_8 = [6, 255]
695 // b_2 FALSE x_8 = [0,5].
697 // These ranges are then combined based on the expected outcome of
698 // the branch. The range on the TRUE side of the branch must satisfy
699 // b_1 == true && b_2 == true
701 // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
702 // must be true. The range of x_8 on the true side must be the
703 // intersection of both ranges since both must be true. Thus the
704 // range of x_8 on the true side is [6, 19].
706 // To determine the ranges on the FALSE side, all 3 combinations of
707 // failing ranges must be considered, and combined as any of them
708 // can cause the false result.
710 // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
711 // FALSE results and combine them. If we fell back to VARYING any
712 // range restrictions that have been discovered up to this point
714 if (!range_is_either_true_or_false (lhs
))
717 if (logical_combine (r1
, code
, m_bool_zero
, op1
, op2
)
718 && logical_combine (r
, code
, m_bool_one
, op1
, op2
))
728 // A logical AND combines ranges from 2 boolean conditions.
734 // The TRUE side is the intersection of the the 2 true ranges.
736 r
.intersect (op2
.true_range
);
740 // The FALSE side is the union of the other 3 cases.
741 int_range_max
ff (op1
.false_range
);
742 ff
.intersect (op2
.false_range
);
743 int_range_max
tf (op1
.true_range
);
744 tf
.intersect (op2
.false_range
);
745 int_range_max
ft (op1
.false_range
);
746 ft
.intersect (op2
.true_range
);
752 // A logical OR combines ranges from 2 boolean conditons.
758 // An OR operation will only take the FALSE path if both
759 // operands are false simlulateously, which means they should
760 // be intersected. !(x || y) == !x && !y
762 r
.intersect (op2
.false_range
);
766 // The TRUE side of an OR operation will be the union of
767 // the other three combinations.
768 int_range_max
tt (op1
.true_range
);
769 tt
.intersect (op2
.true_range
);
770 int_range_max
tf (op1
.true_range
);
771 tf
.intersect (op2
.false_range
);
772 int_range_max
ft (op1
.false_range
);
773 ft
.intersect (op2
.true_range
);
786 // Helper function for compute_logical_operands_in_chain that computes
787 // the range of logical statements that can be computed without
788 // chasing down operands. These are things like [0 = x | y] where we
789 // know neither operand can be non-zero, or [1 = x & y] where we know
790 // neither operand can be zero.
793 gori_compute::optimize_logical_operands (tf_range
&range
,
799 enum tree_code code
= gimple_expr_code (stmt
);
801 // Optimize [0 = x | y], since neither operand can ever be non-zero.
802 if ((code
== BIT_IOR_EXPR
|| code
== TRUTH_OR_EXPR
) && lhs
.zero_p ())
804 if (!compute_operand_range (range
.false_range
, SSA_NAME_DEF_STMT (op
),
806 expr_range_in_bb (range
.false_range
, name
, gimple_bb (stmt
));
807 range
.true_range
= range
.false_range
;
810 // Optimize [1 = x & y], since neither operand can ever be zero.
811 if ((code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
) && lhs
== m_bool_one
)
813 if (!compute_operand_range (range
.true_range
, SSA_NAME_DEF_STMT (op
),
815 expr_range_in_bb (range
.true_range
, name
, gimple_bb (stmt
));
816 range
.false_range
= range
.true_range
;
822 // Given a logical STMT, calculate true and false ranges for each
823 // potential path of NAME, assuming NAME came through the OP chain if
824 // OP_IN_CHAIN is true.
827 gori_compute::compute_logical_operands_in_chain (tf_range
&range
,
831 tree op
, bool op_in_chain
)
833 gimple
*src_stmt
= gimple_range_ssa_p (op
) ? SSA_NAME_DEF_STMT (op
) : NULL
;
834 basic_block bb
= gimple_bb (stmt
);
835 if (!op_in_chain
|| (src_stmt
!= NULL
&& bb
!= gimple_bb (src_stmt
)))
837 // If op is not in the def chain, or defined in this block,
838 // use its known value on entry to the block.
839 expr_range_in_bb (range
.true_range
, name
, gimple_bb (stmt
));
840 range
.false_range
= range
.true_range
;
843 if (optimize_logical_operands (range
, stmt
, lhs
, name
, op
))
846 // Calculate ranges for true and false on both sides, since the false
847 // path is not always a simple inversion of the true side.
848 if (!compute_operand_range (range
.true_range
, src_stmt
, m_bool_one
, name
))
849 expr_range_in_bb (range
.true_range
, name
, bb
);
850 if (!compute_operand_range (range
.false_range
, src_stmt
, m_bool_zero
, name
))
851 expr_range_in_bb (range
.false_range
, name
, bb
);
854 // Given a logical STMT, calculate true and false for each potential
855 // path using NAME, and resolve the outcome based on the logical
859 gori_compute::compute_logical_operands (irange
&r
, gimple
*stmt
,
863 // Reaching this point means NAME is not in this stmt, but one of
864 // the names in it ought to be derived from it.
865 tree op1
= gimple_range_operand1 (stmt
);
866 tree op2
= gimple_range_operand2 (stmt
);
867 gcc_checking_assert (op1
!= name
&& op2
!= name
);
869 bool op1_in_chain
= (gimple_range_ssa_p (op1
)
870 && m_gori_map
->in_chain_p (name
, op1
));
871 bool op2_in_chain
= (gimple_range_ssa_p (op2
)
872 && m_gori_map
->in_chain_p (name
, op2
));
874 // If neither operand is derived, then this stmt tells us nothing.
875 if (!op1_in_chain
&& !op2_in_chain
)
878 tf_range op1_range
, op2_range
;
879 compute_logical_operands_in_chain (op1_range
, stmt
, lhs
,
880 name
, op1
, op1_in_chain
);
881 compute_logical_operands_in_chain (op2_range
, stmt
, lhs
,
882 name
, op2
, op2_in_chain
);
883 return logical_combine (r
, gimple_expr_code (stmt
), lhs
,
884 op1_range
, op2_range
);
887 // Calculate a range for NAME from the operand 1 position of STMT
888 // assuming the result of the statement is LHS. Return the range in
889 // R, or false if no range could be calculated.
892 gori_compute::compute_operand1_range (irange
&r
, gimple
*stmt
,
893 const irange
&lhs
, tree name
)
895 int_range_max op1_range
, op2_range
;
896 tree op1
= gimple_range_operand1 (stmt
);
897 tree op2
= gimple_range_operand2 (stmt
);
899 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
901 // Now calcuated the operand and put that result in r.
904 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
905 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op2_range
))
910 // We pass op1_range to the unary operation. Nomally it's a
911 // hidden range_for_type parameter, but sometimes having the
912 // actual range can result in better information.
913 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op1_range
))
917 // Intersect the calculated result with the known result.
918 op1_range
.intersect (r
);
920 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op1
);
921 // If def stmt is outside of this BB, then name must be an import.
922 if (!src_stmt
|| (gimple_bb (src_stmt
) != gimple_bb (stmt
)))
924 // If this isn't the right import statement, then abort calculation.
925 if (!src_stmt
|| gimple_get_lhs (src_stmt
) != name
)
927 return compute_name_range_op (r
, src_stmt
, op1_range
, name
);
929 // Then feed this range back as the LHS of the defining statement.
930 return compute_operand_range (r
, src_stmt
, op1_range
, name
);
934 // Calculate a range for NAME from the operand 2 position of S
935 // assuming the result of the statement is LHS. Return the range in
936 // R, or false if no range could be calculated.
939 gori_compute::compute_operand2_range (irange
&r
, gimple
*stmt
,
940 const irange
&lhs
, tree name
)
942 int_range_max op1_range
, op2_range
;
943 tree op1
= gimple_range_operand1 (stmt
);
944 tree op2
= gimple_range_operand2 (stmt
);
946 expr_range_in_bb (op1_range
, op1
, gimple_bb (stmt
));
947 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
949 // Intersect with range for op2 based on lhs and op1.
950 if (!gimple_range_calc_op2 (r
, stmt
, lhs
, op1_range
))
952 op2_range
.intersect (r
);
954 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op2
);
955 // If def stmt is outside of this BB, then name must be an import.
956 if (!src_stmt
|| (gimple_bb (src_stmt
) != gimple_bb (stmt
)))
958 // If this isn't the right src statement, then abort calculation.
959 if (!src_stmt
|| gimple_get_lhs (src_stmt
) != name
)
961 return compute_name_range_op (r
, src_stmt
, op2_range
, name
);
963 // Then feed this range back as the LHS of the defining statement.
964 return compute_operand_range (r
, src_stmt
, op2_range
, name
);
967 // Calculate a range for NAME from both operand positions of S
968 // assuming the result of the statement is LHS. Return the range in
969 // R, or false if no range could be calculated.
972 gori_compute::compute_operand1_and_operand2_range
978 int_range_max op_range
;
980 // Calculate a good a range for op2. Since op1 == op2, this will
981 // have already included whatever the actual range of name is.
982 if (!compute_operand2_range (op_range
, stmt
, lhs
, name
))
985 // Now get the range thru op1.
986 if (!compute_operand1_range (r
, stmt
, lhs
, name
))
989 // Whichever range is the most permissive is the one we need to
990 // use. (?) OR is that true? Maybe this should be intersection?
995 // Return TRUE if a range can be calcalated for NAME on edge E.
998 gori_compute::has_edge_range_p (tree name
, edge e
)
1000 // If no edge is specified, check if NAME is an export on any edge.
1002 return m_gori_map
->is_export_p (name
);
1004 return (m_gori_map
->is_export_p (name
, e
->src
)
1005 || m_gori_map
->def_chain_in_export_p (name
, e
->src
));
1008 // Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
1011 gori_compute::set_range_invariant (tree name
)
1013 m_gori_map
->set_range_invariant (name
);
1016 // Dump what is known to GORI computes to listing file F.
1019 gori_compute::dump (FILE *f
)
1021 m_gori_map
->dump (f
);
1024 // Calculate a range on edge E and return it in R. Try to evaluate a
1025 // range for NAME on this edge. Return FALSE if this is either not a
1026 // control edge or NAME is not defined by this edge.
1029 gori_compute::outgoing_edge_range_p (irange
&r
, edge e
, tree name
)
1033 gcc_checking_assert (gimple_range_ssa_p (name
));
1034 // Determine if there is an outgoing edge.
1035 gimple
*stmt
= outgoing
.edge_range_p (lhs
, e
);
1039 // If NAME can be calculated on the edge, use that.
1040 if (m_gori_map
->is_export_p (name
, e
->src
))
1042 if (compute_operand_range (r
, stmt
, lhs
, name
))
1044 // Sometimes compatible types get interchanged. See PR97360.
1045 // Make sure we are returning the type of the thing we asked for.
1046 if (!r
.undefined_p () && r
.type () != TREE_TYPE (name
))
1048 gcc_checking_assert (range_compatible_p (r
.type (),
1050 range_cast (r
, TREE_TYPE (name
));
1058 // --------------------------------------------------------------------------
1060 // Cache for SSAs that appear on the RHS of a boolean assignment.
1062 // Boolean assignments of logical expressions (i.e. LHS = j_5 > 999)
1063 // have SSA operands whose range depend on the LHS of the assigment.
1064 // That is, the range of j_5 when LHS is true is different than when
1067 // This class caches the TRUE/FALSE ranges of such SSAs to avoid
1070 class logical_stmt_cache
1073 logical_stmt_cache ();
1074 ~logical_stmt_cache ();
1075 void set_range (tree lhs
, tree name
, const tf_range
&);
1076 bool get_range (tf_range
&r
, tree lhs
, tree name
) const;
1077 bool cacheable_p (gimple
*, const irange
*lhs_range
= NULL
) const;
1078 void dump (FILE *, gimple
*stmt
) const;
1079 tree
same_cached_name (tree lhs1
, tree lh2
) const;
1081 tree
cached_name (tree lhs
) const;
1082 void slot_diagnostics (tree lhs
, const tf_range
&range
) const;
1085 cache_entry (tree name
, const irange
&t_range
, const irange
&f_range
);
1086 void dump (FILE *out
) const;
1090 vec
<cache_entry
*> m_ssa_cache
;
1093 logical_stmt_cache::cache_entry::cache_entry (tree name
,
1094 const irange
&t_range
,
1095 const irange
&f_range
)
1096 : name (name
), range (t_range
, f_range
)
1100 logical_stmt_cache::logical_stmt_cache ()
1102 m_ssa_cache
.create (num_ssa_names
+ num_ssa_names
/ 10);
1103 m_ssa_cache
.safe_grow_cleared (num_ssa_names
);
1106 logical_stmt_cache::~logical_stmt_cache ()
1108 for (unsigned i
= 0; i
< m_ssa_cache
.length (); ++i
)
1110 delete m_ssa_cache
[i
];
1111 m_ssa_cache
.release ();
1114 // Dump cache_entry to OUT.
1117 logical_stmt_cache::cache_entry::dump (FILE *out
) const
1119 fprintf (out
, "name=");
1120 print_generic_expr (out
, name
, TDF_SLIM
);
1122 range
.true_range
.dump (out
);
1123 fprintf (out
, ", ");
1124 range
.false_range
.dump (out
);
1125 fprintf (out
, "\n");
1128 // Update range for cache entry of NAME as it appears in the defining
1129 // statement of LHS.
1132 logical_stmt_cache::set_range (tree lhs
, tree name
, const tf_range
&range
)
1134 unsigned version
= SSA_NAME_VERSION (lhs
);
1135 if (version
>= m_ssa_cache
.length ())
1136 m_ssa_cache
.safe_grow_cleared (num_ssa_names
+ num_ssa_names
/ 10);
1138 cache_entry
*slot
= m_ssa_cache
[version
];
1139 slot_diagnostics (lhs
, range
);
1142 // The IL must have changed. Update the carried SSA name for
1143 // consistency. Testcase is libgomp.fortran/doacross1.f90.
1144 if (slot
->name
!= name
)
1148 m_ssa_cache
[version
]
1149 = new cache_entry (name
, range
.true_range
, range
.false_range
);
1152 // If there is a cached entry of NAME, set it in R and return TRUE,
1153 // otherwise return FALSE. LHS is the defining statement where NAME
1157 logical_stmt_cache::get_range (tf_range
&r
, tree lhs
, tree name
) const
1159 gcc_checking_assert (cacheable_p (SSA_NAME_DEF_STMT (lhs
)));
1160 if (cached_name (lhs
) == name
)
1162 unsigned version
= SSA_NAME_VERSION (lhs
);
1163 if (m_ssa_cache
[version
])
1165 r
= m_ssa_cache
[version
]->range
;
1172 // If the defining statement of LHS is in the cache, return the SSA
1173 // operand being cached. That is, return SSA for LHS = SSA .RELOP. OP2.
1176 logical_stmt_cache::cached_name (tree lhs
) const
1178 unsigned version
= SSA_NAME_VERSION (lhs
);
1180 if (version
>= m_ssa_cache
.length ())
1183 if (m_ssa_cache
[version
])
1184 return m_ssa_cache
[version
]->name
;
1188 // Return TRUE if the cached name for LHS1 is the same as the
1189 // cached name for LHS2.
1192 logical_stmt_cache::same_cached_name (tree lhs1
, tree lhs2
) const
1194 tree name
= cached_name (lhs1
);
1195 if (name
&& name
== cached_name (lhs2
))
1200 // Return TRUE if STMT is a statement we are interested in caching.
1201 // LHS_RANGE is any known range for the LHS of STMT.
1204 logical_stmt_cache::cacheable_p (gimple
*stmt
, const irange
*lhs_range
) const
1206 if (gimple_code (stmt
) == GIMPLE_ASSIGN
1207 && types_compatible_p (TREE_TYPE (gimple_assign_lhs (stmt
)),
1209 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
1211 switch (gimple_expr_code (stmt
))
1213 case TRUTH_AND_EXPR
:
1217 return !lhs_range
|| range_is_either_true_or_false (*lhs_range
);
1225 // Output debugging diagnostics for the cache entry for LHS. RANGE is
1226 // the new range that is being cached.
1229 logical_stmt_cache::slot_diagnostics (tree lhs
, const tf_range
&range
) const
1231 gimple
*stmt
= SSA_NAME_DEF_STMT (lhs
);
1232 unsigned version
= SSA_NAME_VERSION (lhs
);
1233 cache_entry
*slot
= m_ssa_cache
[version
];
1237 if (DEBUG_RANGE_CACHE
)
1239 fprintf (dump_file
? dump_file
: stderr
, "registering range for: ");
1240 dump (dump_file
? dump_file
: stderr
, stmt
);
1244 if (DEBUG_RANGE_CACHE
)
1245 fprintf (dump_file
? dump_file
: stderr
,
1246 "reusing range for SSA #%d\n", version
);
1247 if (CHECKING_P
&& (slot
->range
.true_range
!= range
.true_range
1248 || slot
->range
.false_range
!= range
.false_range
))
1250 fprintf (stderr
, "FATAL: range altered for cached: ");
1251 dump (stderr
, stmt
);
1252 fprintf (stderr
, "Attempt to change to:\n");
1253 fprintf (stderr
, "TRUE=");
1254 range
.true_range
.dump (stderr
);
1255 fprintf (stderr
, ", FALSE=");
1256 range
.false_range
.dump (stderr
);
1257 fprintf (stderr
, "\n");
1262 // Dump the cache information for STMT.
1265 logical_stmt_cache::dump (FILE *out
, gimple
*stmt
) const
1267 tree lhs
= gimple_assign_lhs (stmt
);
1268 cache_entry
*entry
= m_ssa_cache
[SSA_NAME_VERSION (lhs
)];
1270 print_gimple_stmt (out
, stmt
, 0, TDF_SLIM
);
1273 fprintf (out
, "\tname = ");
1274 print_generic_expr (out
, entry
->name
);
1275 fprintf (out
, " lhs(%d)= ", SSA_NAME_VERSION (lhs
));
1276 print_generic_expr (out
, lhs
);
1277 fprintf (out
, "\n\tTRUE=");
1278 entry
->range
.true_range
.dump (out
);
1279 fprintf (out
, ", FALSE=");
1280 entry
->range
.false_range
.dump (out
);
1281 fprintf (out
, "\n");
1284 fprintf (out
, "[EMPTY]\n");
1287 gori_compute_cache::gori_compute_cache ()
1289 m_cache
= new logical_stmt_cache
;
1292 gori_compute_cache::~gori_compute_cache ()
1297 // Caching version of compute_operand_range. If NAME, as it appears
1298 // in STMT, has already been cached return it from the cache,
1299 // otherwise compute the operand range as normal and cache it.
1302 gori_compute_cache::compute_operand_range (irange
&r
, gimple
*stmt
,
1303 const irange
&lhs_range
, tree name
)
1305 bool cacheable
= m_cache
->cacheable_p (stmt
, &lhs_range
);
1308 tree lhs
= gimple_assign_lhs (stmt
);
1310 if (m_cache
->get_range (range
, lhs
, name
))
1312 if (lhs_range
.zero_p ())
1313 r
= range
.false_range
;
1315 r
= range
.true_range
;
1319 if (super::compute_operand_range (r
, stmt
, lhs_range
, name
))
1328 // Cache STMT if possible.
1331 gori_compute_cache::cache_stmt (gimple
*stmt
)
1333 gcc_checking_assert (m_cache
->cacheable_p (stmt
));
1334 enum tree_code code
= gimple_expr_code (stmt
);
1335 tree lhs
= gimple_assign_lhs (stmt
);
1336 tree op1
= gimple_range_operand1 (stmt
);
1337 tree op2
= gimple_range_operand2 (stmt
);
1338 int_range_max r_true_side
, r_false_side
;
1340 // LHS = s_5 && 999.
1341 if (TREE_CODE (op2
) == INTEGER_CST
)
1343 range_operator
*handler
= range_op_handler (code
, TREE_TYPE (lhs
));
1344 int_range_max op2_range
;
1345 expr_range_in_bb (op2_range
, op2
, gimple_bb (stmt
));
1346 tree type
= TREE_TYPE (op1
);
1347 handler
->op1_range (r_true_side
, type
, m_bool_one
, op2_range
);
1348 handler
->op1_range (r_false_side
, type
, m_bool_zero
, op2_range
);
1349 m_cache
->set_range (lhs
, op1
, tf_range (r_true_side
, r_false_side
));
1351 // LHS = s_5 && b_8.
1352 else if (tree cached_name
= m_cache
->same_cached_name (op1
, op2
))
1354 tf_range op1_range
, op2_range
;
1355 bool ok
= m_cache
->get_range (op1_range
, op1
, cached_name
);
1356 ok
= ok
&& m_cache
->get_range (op2_range
, op2
, cached_name
);
1357 ok
= ok
&& logical_combine (r_true_side
, code
, m_bool_one
,
1358 op1_range
, op2_range
);
1359 ok
= ok
&& logical_combine (r_false_side
, code
, m_bool_zero
,
1360 op1_range
, op2_range
);
1361 gcc_checking_assert (ok
);
1363 m_cache
->set_range (lhs
, cached_name
,
1364 tf_range (r_true_side
, r_false_side
));