1 /* Gimple range GORI functions.
2 Copyright (C) 2017-2021 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "gimple-pretty-print.h"
30 #include "gimple-range.h"
32 // Return TRUE if GS is a logical && or || expression.
35 is_gimple_logical_p (const gimple
*gs
)
37 // Look for boolean and/or condition.
38 if (is_gimple_assign (gs
))
39 switch (gimple_expr_code (gs
))
47 // Bitwise operations on single bits are logical too.
48 if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs
)),
59 /* RANGE_DEF_CHAIN is used to determine which SSA names in a block can
60 have range information calculated for them, and what the
61 dependencies on each other are.
63 Information for a basic block is calculated once and stored. It is
64 only calculated the first time a query is made, so if no queries
65 are made, there is little overhead.
67 The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set
68 within this bitmap to indicate SSA names that are defined in the
69 SAME block and used to calculate this SSA name.
83 This dump indicates the bits set in the def_chain vector.
84 as well as demonstrates the def_chain bits for the related ssa_names.
86 Checking the chain for _2 indicates that _1 and x_4 are used in
89 Def chains also only include statements which are valid gimple
90 so a def chain will only span statements for which the range
91 engine implements operations for. */
94 // Construct a range_def_chain.
96 range_def_chain::range_def_chain ()
98 bitmap_obstack_initialize (&m_bitmaps
);
99 m_def_chain
.create (0);
100 m_def_chain
.safe_grow_cleared (num_ssa_names
);
104 // Destruct a range_def_chain.
106 range_def_chain::~range_def_chain ()
108 m_def_chain
.release ();
109 bitmap_obstack_release (&m_bitmaps
);
112 // Return true if NAME is in the def chain of DEF. If BB is provided,
113 // only return true if the defining statement of DEF is in BB.
116 range_def_chain::in_chain_p (tree name
, tree def
)
118 gcc_checking_assert (gimple_range_ssa_p (def
));
119 gcc_checking_assert (gimple_range_ssa_p (name
));
121 // Get the defintion chain for DEF.
122 bitmap chain
= get_def_chain (def
);
126 return bitmap_bit_p (chain
, SSA_NAME_VERSION (name
));
129 // Add either IMP or the import list B to the import set of DATA.
132 range_def_chain::set_import (struct rdc
&data
, tree imp
, bitmap b
)
134 // If there are no imports, just return
135 if (imp
== NULL_TREE
&& !b
)
138 data
.m_import
= BITMAP_ALLOC (&m_bitmaps
);
139 if (imp
!= NULL_TREE
)
140 bitmap_set_bit (data
.m_import
, SSA_NAME_VERSION (imp
));
142 bitmap_ior_into (data
.m_import
, b
);
145 // Return the import list for NAME.
148 range_def_chain::get_imports (tree name
)
150 if (!has_def_chain (name
))
151 get_def_chain (name
);
152 bitmap i
= m_def_chain
[SSA_NAME_VERSION (name
)].m_import
;
153 // Either this is a default def, OR imports must be a subset of exports.
154 gcc_checking_assert (!get_def_chain (name
) || !i
155 || !bitmap_intersect_compl_p (i
, get_def_chain (name
)));
159 // Return true if IMPORT is an import to NAMEs def chain.
162 range_def_chain::chain_import_p (tree name
, tree import
)
164 bitmap b
= get_imports (name
);
166 return bitmap_bit_p (b
, SSA_NAME_VERSION (import
));
170 // Build def_chains for NAME if it is in BB. Copy the def chain into RESULT.
173 range_def_chain::register_dependency (tree name
, tree dep
, basic_block bb
)
175 if (!gimple_range_ssa_p (dep
))
178 unsigned v
= SSA_NAME_VERSION (name
);
179 if (v
>= m_def_chain
.length ())
180 m_def_chain
.safe_grow_cleared (num_ssa_names
+ 1);
181 struct rdc
&src
= m_def_chain
[v
];
182 gimple
*def_stmt
= SSA_NAME_DEF_STMT (dep
);
183 unsigned dep_v
= SSA_NAME_VERSION (dep
);
186 // Set the direct dependency cache entries.
189 else if (!src
.ssa2
&& src
.ssa1
!= dep
)
192 // Don't calculate imports or export/dep chains if BB is not provided.
193 // This is usually the case for when the temporal cache wants the direct
194 // dependencies of a stmt.
199 src
.bm
= BITMAP_ALLOC (&m_bitmaps
);
201 // Add this operand into the result.
202 bitmap_set_bit (src
.bm
, dep_v
);
204 if (gimple_bb (def_stmt
) == bb
&& !is_a
<gphi
*>(def_stmt
))
206 // Get the def chain for the operand.
207 b
= get_def_chain (dep
);
208 // If there was one, copy it into result.
210 bitmap_ior_into (src
.bm
, b
);
211 // And copy the import list.
212 set_import (src
, NULL_TREE
, get_imports (dep
));
215 // Originated outside the block, so it is an import.
216 set_import (src
, dep
, NULL
);
220 range_def_chain::def_chain_in_bitmap_p (tree name
, bitmap b
)
222 bitmap a
= get_def_chain (name
);
224 return bitmap_intersect_p (a
, b
);
229 range_def_chain::add_def_chain_to_bitmap (bitmap b
, tree name
)
231 bitmap r
= get_def_chain (name
);
233 bitmap_ior_into (b
, r
);
237 // Return TRUE if NAME has been processed for a def_chain.
240 range_def_chain::has_def_chain (tree name
)
242 // Ensure there is an entry in the internal vector.
243 unsigned v
= SSA_NAME_VERSION (name
);
244 if (v
>= m_def_chain
.length ())
245 m_def_chain
.safe_grow_cleared (num_ssa_names
+ 1);
246 return (m_def_chain
[v
].ssa1
!= 0);
251 // Calculate the def chain for NAME and all of its dependent
252 // operands. Only using names in the same BB. Return the bitmap of
253 // all names in the m_def_chain. This only works for supported range
257 range_def_chain::get_def_chain (tree name
)
259 tree ssa1
, ssa2
, ssa3
;
260 unsigned v
= SSA_NAME_VERSION (name
);
261 bool is_logical
= false;
263 // If it has already been processed, just return the cached value.
264 if (has_def_chain (name
))
265 return m_def_chain
[v
].bm
;
267 // No definition chain for default defs.
268 if (SSA_NAME_IS_DEFAULT_DEF (name
))
270 // A Default def is always an import.
271 set_import (m_def_chain
[v
], name
, NULL
);
275 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
276 if (gimple_range_handler (stmt
))
278 is_logical
= is_gimple_logical_p (stmt
);
279 // Terminate the def chains if we see too many cascading logical stmts.
282 if (m_logical_depth
== param_ranger_logical_depth
)
287 ssa1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
288 ssa2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
291 else if (is_a
<gassign
*> (stmt
)
292 && gimple_assign_rhs_code (stmt
) == COND_EXPR
)
294 gassign
*st
= as_a
<gassign
*> (stmt
);
295 ssa1
= gimple_range_ssa_p (gimple_assign_rhs1 (st
));
296 ssa2
= gimple_range_ssa_p (gimple_assign_rhs2 (st
));
297 ssa3
= gimple_range_ssa_p (gimple_assign_rhs3 (st
));
301 // Stmts not understood are always imports.
302 set_import (m_def_chain
[v
], name
, NULL
);
306 register_dependency (name
, ssa1
, gimple_bb (stmt
));
307 register_dependency (name
, ssa2
, gimple_bb (stmt
));
308 register_dependency (name
, ssa3
, gimple_bb (stmt
));
309 // Stmts with no understandable operands are also imports.
310 if (!ssa1
&& !ssa2
& !ssa3
)
311 set_import (m_def_chain
[v
], name
, NULL
);
316 return m_def_chain
[v
].bm
;
319 // Dump what we know for basic block BB to file F.
322 range_def_chain::dump (FILE *f
, basic_block bb
, const char *prefix
)
327 // Dump the def chain for each SSA_NAME defined in BB.
328 for (x
= 1; x
< num_ssa_names
; x
++)
330 tree name
= ssa_name (x
);
333 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
334 if (!stmt
|| (bb
&& gimple_bb (stmt
) != bb
))
336 bitmap chain
= (has_def_chain (name
) ? get_def_chain (name
) : NULL
);
337 if (chain
&& !bitmap_empty_p (chain
))
340 print_generic_expr (f
, name
, TDF_SLIM
);
343 bitmap imports
= get_imports (name
);
344 EXECUTE_IF_SET_IN_BITMAP (chain
, 0, y
, bi
)
346 print_generic_expr (f
, ssa_name (y
), TDF_SLIM
);
347 if (imports
&& bitmap_bit_p (imports
, y
))
357 // -------------------------------------------------------------------
359 /* GORI_MAP is used to accumulate what SSA names in a block can
360 generate range information, and provides tools for the block ranger
361 to enable it to efficiently calculate these ranges.
363 GORI stands for "Generates Outgoing Range Information."
365 It utilizes the range_def_chain class to contruct def_chains.
366 Information for a basic block is calculated once and stored. It is
367 only calculated the first time a query is made. If no queries are
368 made, there is little overhead.
370 one bitmap is maintained for each basic block:
371 m_outgoing : a set bit indicates a range can be generated for a name.
373 Generally speaking, the m_outgoing vector is the union of the
374 entire def_chain of all SSA names used in the last statement of the
375 block which generate ranges. */
378 // Initialize a gori-map structure.
380 gori_map::gori_map ()
382 m_outgoing
.create (0);
383 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
384 m_incoming
.create (0);
385 m_incoming
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
386 m_maybe_variant
= BITMAP_ALLOC (&m_bitmaps
);
389 // Free any memory the GORI map allocated.
391 gori_map::~gori_map ()
393 m_incoming
.release ();
394 m_outgoing
.release ();
397 // Return the bitmap vector of all export from BB. Calculate if necessary.
400 gori_map::exports (basic_block bb
)
402 if (bb
->index
>= (signed int)m_outgoing
.length () || !m_outgoing
[bb
->index
])
404 return m_outgoing
[bb
->index
];
407 // Return the bitmap vector of all imports to BB. Calculate if necessary.
410 gori_map::imports (basic_block bb
)
412 if (bb
->index
>= (signed int)m_outgoing
.length () || !m_outgoing
[bb
->index
])
414 return m_incoming
[bb
->index
];
417 // Return true if NAME is can have ranges generated for it from basic
421 gori_map::is_export_p (tree name
, basic_block bb
)
423 // If no BB is specified, test if it is exported anywhere in the IL.
425 return bitmap_bit_p (m_maybe_variant
, SSA_NAME_VERSION (name
));
426 return bitmap_bit_p (exports (bb
), SSA_NAME_VERSION (name
));
429 // Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
432 gori_map::set_range_invariant (tree name
)
434 bitmap_clear_bit (m_maybe_variant
, SSA_NAME_VERSION (name
));
437 // Return true if NAME is an import to block BB.
440 gori_map::is_import_p (tree name
, basic_block bb
)
442 // If no BB is specified, test if it is exported anywhere in the IL.
443 return bitmap_bit_p (imports (bb
), SSA_NAME_VERSION (name
));
446 // If NAME is non-NULL and defined in block BB, calculate the def
447 // chain and add it to m_outgoing.
450 gori_map::maybe_add_gori (tree name
, basic_block bb
)
454 // Check if there is a def chain, regardless of the block.
455 add_def_chain_to_bitmap (m_outgoing
[bb
->index
], name
);
456 // Check for any imports.
457 bitmap imp
= get_imports (name
);
458 // If there were imports, add them so we can recompute
460 bitmap_ior_into (m_incoming
[bb
->index
], imp
);
461 // This name is always an import.
462 if (gimple_bb (SSA_NAME_DEF_STMT (name
)) != bb
)
463 bitmap_set_bit (m_incoming
[bb
->index
], SSA_NAME_VERSION (name
));
465 // Def chain doesn't include itself, and even if there isn't a
466 // def chain, this name should be added to exports.
467 bitmap_set_bit (m_outgoing
[bb
->index
], SSA_NAME_VERSION (name
));
471 // Calculate all the required information for BB.
474 gori_map::calculate_gori (basic_block bb
)
477 if (bb
->index
>= (signed int)m_outgoing
.length ())
479 m_outgoing
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
480 m_incoming
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
482 gcc_checking_assert (m_outgoing
[bb
->index
] == NULL
);
483 m_outgoing
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
484 m_incoming
[bb
->index
] = BITMAP_ALLOC (&m_bitmaps
);
486 // If this block's last statement may generate range informaiton, go
488 gimple
*stmt
= gimple_outgoing_range_stmt_p (bb
);
491 if (is_a
<gcond
*> (stmt
))
493 gcond
*gc
= as_a
<gcond
*>(stmt
);
494 name
= gimple_range_ssa_p (gimple_cond_lhs (gc
));
495 maybe_add_gori (name
, gimple_bb (stmt
));
497 name
= gimple_range_ssa_p (gimple_cond_rhs (gc
));
498 maybe_add_gori (name
, gimple_bb (stmt
));
502 gswitch
*gs
= as_a
<gswitch
*>(stmt
);
503 name
= gimple_range_ssa_p (gimple_switch_index (gs
));
504 maybe_add_gori (name
, gimple_bb (stmt
));
506 // Add this bitmap to the aggregate list of all outgoing names.
507 bitmap_ior_into (m_maybe_variant
, m_outgoing
[bb
->index
]);
510 // Dump the table information for BB to file F.
513 gori_map::dump (FILE *f
, basic_block bb
, bool verbose
)
515 // BB was not processed.
516 if (!m_outgoing
[bb
->index
] || bitmap_empty_p (m_outgoing
[bb
->index
]))
521 bitmap imp
= imports (bb
);
522 if (!bitmap_empty_p (imp
))
525 fprintf (f
, "bb<%u> Imports: ",bb
->index
);
527 fprintf (f
, "Imports: ");
528 FOR_EACH_GORI_IMPORT_NAME (*this, bb
, name
)
530 print_generic_expr (f
, name
, TDF_SLIM
);
537 fprintf (f
, "bb<%u> Exports: ",bb
->index
);
539 fprintf (f
, "Exports: ");
540 // Dump the export vector.
541 FOR_EACH_GORI_EXPORT_NAME (*this, bb
, name
)
543 print_generic_expr (f
, name
, TDF_SLIM
);
548 range_def_chain::dump (f
, bb
, " ");
551 // Dump the entire GORI map structure to file F.
554 gori_map::dump (FILE *f
)
557 FOR_EACH_BB_FN (bb
, cfun
)
567 // -------------------------------------------------------------------
569 // Construct a gori_compute object.
571 gori_compute::gori_compute ()
573 // Create a boolean_type true and false range.
574 m_bool_zero
= int_range
<2> (boolean_false_node
, boolean_false_node
);
575 m_bool_one
= int_range
<2> (boolean_true_node
, boolean_true_node
);
578 // Given the switch S, return an evaluation in R for NAME when the lhs
579 // evaluates to LHS. Returning false means the name being looked for
580 // was not resolvable.
583 gori_compute::compute_operand_range_switch (irange
&r
, gswitch
*s
,
585 tree name
, fur_source
&src
)
587 tree op1
= gimple_switch_index (s
);
589 // If name matches, the range is simply the range from the edge.
590 // Empty ranges are viral as they are on a path which isn't
592 if (op1
== name
|| lhs
.undefined_p ())
598 // If op1 is in the defintion chain, pass lhs back.
599 if (gimple_range_ssa_p (op1
) && in_chain_p (name
, op1
))
600 return compute_operand_range (r
, SSA_NAME_DEF_STMT (op1
), lhs
, name
, src
);
606 // Return an evaluation for NAME as it would appear in STMT when the
607 // statement's lhs evaluates to LHS. If successful, return TRUE and
608 // store the evaluation in R, otherwise return FALSE.
611 gori_compute::compute_operand_range (irange
&r
, gimple
*stmt
,
612 const irange
&lhs
, tree name
,
615 // If the lhs doesn't tell us anything, neither will unwinding further.
616 if (lhs
.varying_p ())
619 // Empty ranges are viral as they are on an unexecutable path.
620 if (lhs
.undefined_p ())
625 if (is_a
<gswitch
*> (stmt
))
626 return compute_operand_range_switch (r
, as_a
<gswitch
*> (stmt
), lhs
, name
,
628 if (!gimple_range_handler (stmt
))
631 tree op1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
632 tree op2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
634 // Handle end of lookup first.
636 return compute_operand1_range (r
, stmt
, lhs
, name
, src
);
638 return compute_operand2_range (r
, stmt
, lhs
, name
, src
);
640 // NAME is not in this stmt, but one of the names in it ought to be
642 bool op1_in_chain
= op1
&& in_chain_p (name
, op1
);
643 bool op2_in_chain
= op2
&& in_chain_p (name
, op2
);
645 // If neither operand is derived, then this stmt tells us nothing.
646 if (!op1_in_chain
&& !op2_in_chain
)
649 // Process logicals as they have special handling.
650 if (is_gimple_logical_p (stmt
))
652 int_range_max op1_trange
, op1_frange
;
653 int_range_max op2_trange
, op2_frange
;
654 compute_logical_operands (op1_trange
, op1_frange
, stmt
, lhs
,
655 name
, src
, op1
, op1_in_chain
);
656 compute_logical_operands (op2_trange
, op2_frange
, stmt
, lhs
,
657 name
, src
, op2
, op2_in_chain
);
658 return logical_combine (r
, gimple_expr_code (stmt
), lhs
,
659 op1_trange
, op1_frange
, op2_trange
, op2_frange
);
662 // Follow the appropriate operands now.
663 if (op1_in_chain
&& op2_in_chain
)
664 return compute_operand1_and_operand2_range (r
, stmt
, lhs
, name
, src
);
666 return compute_operand1_range (r
, stmt
, lhs
, name
, src
);
668 return compute_operand2_range (r
, stmt
, lhs
, name
, src
);
670 // If neither operand is derived, this statement tells us nothing.
675 // Return TRUE if range R is either a true or false compatible range.
678 range_is_either_true_or_false (const irange
&r
)
680 if (r
.undefined_p ())
683 // This is complicated by the fact that Ada has multi-bit booleans,
684 // so true can be ~[0, 0] (i.e. [1,MAX]).
685 tree type
= r
.type ();
686 gcc_checking_assert (range_compatible_p (type
, boolean_type_node
));
687 return (r
.singleton_p () || !r
.contains_p (build_zero_cst (type
)));
690 // Evaluate a binary logical expression by combining the true and
691 // false ranges for each of the operands based on the result value in
695 gori_compute::logical_combine (irange
&r
, enum tree_code code
,
697 const irange
&op1_true
, const irange
&op1_false
,
698 const irange
&op2_true
, const irange
&op2_false
)
700 if (op1_true
.varying_p () && op1_false
.varying_p ()
701 && op2_true
.varying_p () && op2_false
.varying_p ())
704 // This is not a simple fold of a logical expression, rather it
705 // determines ranges which flow through the logical expression.
707 // Assuming x_8 is an unsigned char, and relational statements:
710 // consider the logical expression and branch:
714 // To determine the range of x_8 on either edge of the branch, one
715 // must first determine what the range of x_8 is when the boolean
716 // values of b_1 and b_2 are both true and false.
717 // b_1 TRUE x_8 = [0, 19]
718 // b_1 FALSE x_8 = [20, 255]
719 // b_2 TRUE x_8 = [6, 255]
720 // b_2 FALSE x_8 = [0,5].
722 // These ranges are then combined based on the expected outcome of
723 // the branch. The range on the TRUE side of the branch must satisfy
724 // b_1 == true && b_2 == true
726 // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
727 // must be true. The range of x_8 on the true side must be the
728 // intersection of both ranges since both must be true. Thus the
729 // range of x_8 on the true side is [6, 19].
731 // To determine the ranges on the FALSE side, all 3 combinations of
732 // failing ranges must be considered, and combined as any of them
733 // can cause the false result.
735 // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
736 // FALSE results and combine them. If we fell back to VARYING any
737 // range restrictions that have been discovered up to this point
739 if (!range_is_either_true_or_false (lhs
))
742 if (logical_combine (r1
, code
, m_bool_zero
, op1_true
, op1_false
,
744 && logical_combine (r
, code
, m_bool_one
, op1_true
, op1_false
,
745 op2_true
, op2_false
))
755 // A logical AND combines ranges from 2 boolean conditions.
761 // The TRUE side is the intersection of the the 2 true ranges.
763 r
.intersect (op2_true
);
767 // The FALSE side is the union of the other 3 cases.
768 int_range_max
ff (op1_false
);
769 ff
.intersect (op2_false
);
770 int_range_max
tf (op1_true
);
771 tf
.intersect (op2_false
);
772 int_range_max
ft (op1_false
);
773 ft
.intersect (op2_true
);
779 // A logical OR combines ranges from 2 boolean conditons.
785 // An OR operation will only take the FALSE path if both
786 // operands are false simlulateously, which means they should
787 // be intersected. !(x || y) == !x && !y
789 r
.intersect (op2_false
);
793 // The TRUE side of an OR operation will be the union of
794 // the other three combinations.
795 int_range_max
tt (op1_true
);
796 tt
.intersect (op2_true
);
797 int_range_max
tf (op1_true
);
798 tf
.intersect (op2_false
);
799 int_range_max
ft (op1_false
);
800 ft
.intersect (op2_true
);
814 // Given a logical STMT, calculate true and false ranges for each
815 // potential path of NAME, assuming NAME came through the OP chain if
816 // OP_IN_CHAIN is true.
819 gori_compute::compute_logical_operands (irange
&true_range
, irange
&false_range
,
822 tree name
, fur_source
&src
,
823 tree op
, bool op_in_chain
)
825 gimple
*src_stmt
= gimple_range_ssa_p (op
) ? SSA_NAME_DEF_STMT (op
) : NULL
;
826 if (!op_in_chain
|| !src_stmt
|| chain_import_p (gimple_get_lhs (stmt
), op
))
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 src
.get_operand (true_range
, name
);
831 false_range
= true_range
;
835 enum tree_code code
= gimple_expr_code (stmt
);
836 // Optimize [0 = x | y], since neither operand can ever be non-zero.
837 if ((code
== BIT_IOR_EXPR
|| code
== TRUTH_OR_EXPR
) && lhs
.zero_p ())
839 if (!compute_operand_range (false_range
, src_stmt
, m_bool_zero
, name
,
841 src
.get_operand (false_range
, name
);
842 true_range
= false_range
;
846 // Optimize [1 = x & y], since neither operand can ever be zero.
847 if ((code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
) && lhs
== m_bool_one
)
849 if (!compute_operand_range (true_range
, src_stmt
, m_bool_one
, name
, src
))
850 src
.get_operand (true_range
, name
);
851 false_range
= true_range
;
855 // Calculate ranges for true and false on both sides, since the false
856 // path is not always a simple inversion of the true side.
857 if (!compute_operand_range (true_range
, src_stmt
, m_bool_one
, name
, src
))
858 src
.get_operand (true_range
, name
);
859 if (!compute_operand_range (false_range
, src_stmt
, m_bool_zero
, name
, src
))
860 src
.get_operand (false_range
, name
);
863 // Calculate a range for NAME from the operand 1 position of STMT
864 // assuming the result of the statement is LHS. Return the range in
865 // R, or false if no range could be calculated.
868 gori_compute::compute_operand1_range (irange
&r
, gimple
*stmt
,
869 const irange
&lhs
, tree name
,
872 int_range_max op1_range
, op2_range
;
873 tree op1
= gimple_range_operand1 (stmt
);
874 tree op2
= gimple_range_operand2 (stmt
);
876 // Fetch the known range for op1 in this block.
877 src
.get_operand (op1_range
, op1
);
879 // Now range-op calcuate and put that result in r.
882 src
.get_operand (op2_range
, op2
);
883 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op2_range
))
888 // We pass op1_range to the unary operation. Nomally it's a
889 // hidden range_for_type parameter, but sometimes having the
890 // actual range can result in better information.
891 if (!gimple_range_calc_op1 (r
, stmt
, lhs
, op1_range
))
895 // Intersect the calculated result with the known result and return if done.
898 r
.intersect (op1_range
);
901 // If the calculation continues, we're using op1_range as the new LHS.
902 op1_range
.intersect (r
);
904 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op1
);
905 gcc_checking_assert (src_stmt
);
907 // Then feed this range back as the LHS of the defining statement.
908 return compute_operand_range (r
, src_stmt
, op1_range
, name
, src
);
912 // Calculate a range for NAME from the operand 2 position of S
913 // assuming the result of the statement is LHS. Return the range in
914 // R, or false if no range could be calculated.
917 gori_compute::compute_operand2_range (irange
&r
, gimple
*stmt
,
918 const irange
&lhs
, tree name
,
921 int_range_max op1_range
, op2_range
;
922 tree op1
= gimple_range_operand1 (stmt
);
923 tree op2
= gimple_range_operand2 (stmt
);
925 src
.get_operand (op1_range
, op1
);
926 src
.get_operand (op2_range
, op2
);
928 // Intersect with range for op2 based on lhs and op1.
929 if (!gimple_range_calc_op2 (r
, stmt
, lhs
, op1_range
))
932 // Intersect the calculated result with the known result and return if done.
935 r
.intersect (op2_range
);
938 // If the calculation continues, we're using op2_range as the new LHS.
939 op2_range
.intersect (r
);
941 gimple
*src_stmt
= SSA_NAME_DEF_STMT (op2
);
942 gcc_checking_assert (src_stmt
);
943 // gcc_checking_assert (!is_import_p (op2, find.bb));
945 // Then feed this range back as the LHS of the defining statement.
946 return compute_operand_range (r
, src_stmt
, op2_range
, name
, src
);
949 // Calculate a range for NAME from both operand positions of S
950 // assuming the result of the statement is LHS. Return the range in
951 // R, or false if no range could be calculated.
954 gori_compute::compute_operand1_and_operand2_range (irange
&r
,
960 int_range_max op_range
;
962 // Calculate a good a range for op2. Since op1 == op2, this will
963 // have already included whatever the actual range of name is.
964 if (!compute_operand2_range (op_range
, stmt
, lhs
, name
, src
))
967 // Now get the range thru op1.
968 if (!compute_operand1_range (r
, stmt
, lhs
, name
, src
))
971 // Both operands have to be simultaneously true, so perform an intersection.
972 r
.intersect (op_range
);
975 // Return TRUE if a range can be calculated or recomputed for NAME on edge E.
978 gori_compute::has_edge_range_p (tree name
, edge e
)
980 // Check if NAME is an export or can be recomputed.
982 return is_export_p (name
, e
->src
) || may_recompute_p (name
, e
);
984 // If no edge is specified, check if NAME can have a range calculated
986 return is_export_p (name
) || may_recompute_p (name
);
989 // Dump what is known to GORI computes to listing file F.
992 gori_compute::dump (FILE *f
)
997 // Return TRUE if NAME can be recomputed on edge E. If any direct dependant
998 // is exported on edge E, it may change the computed value of NAME.
1001 gori_compute::may_recompute_p (tree name
, edge e
)
1003 tree dep1
= depend1 (name
);
1004 tree dep2
= depend2 (name
);
1006 // If the first dependency is not set, there is no recompuation.
1010 // Don't recalculate PHIs or statements with side_effects.
1011 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1012 if (is_a
<gphi
*> (s
) || gimple_has_side_effects (s
))
1015 // If edge is specified, check if NAME can be recalculated on that edge.
1017 return ((is_export_p (dep1
, e
->src
))
1018 || (dep2
&& is_export_p (dep2
, e
->src
)));
1020 return (is_export_p (dep1
)) || (dep2
&& is_export_p (dep2
));
1023 // Calculate a range on edge E and return it in R. Try to evaluate a
1024 // range for NAME on this edge. Return FALSE if this is either not a
1025 // control edge or NAME is not defined by this edge.
1028 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 fur_stmt
src (stmt
, &q
);
1041 // If NAME can be calculated on the edge, use that.
1042 if (is_export_p (name
, e
->src
))
1044 if (compute_operand_range (r
, stmt
, lhs
, name
, src
))
1046 // Sometimes compatible types get interchanged. See PR97360.
1047 // Make sure we are returning the type of the thing we asked for.
1048 if (!r
.undefined_p () && r
.type () != TREE_TYPE (name
))
1050 gcc_checking_assert (range_compatible_p (r
.type (),
1052 range_cast (r
, TREE_TYPE (name
));
1057 // If NAME isn't exported, check if it can be recomputed.
1058 else if (may_recompute_p (name
, e
))
1060 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1062 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1064 fprintf (dump_file
, "recomputation attempt on edge %d->%d for ",
1065 e
->src
->index
, e
->dest
->index
);
1066 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1068 // Simply calculate DEF_STMT on edge E using the range query Q.
1069 fold_range (r
, def_stmt
, e
, &q
);
1070 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1072 fprintf (dump_file
, " : Calculated :");
1074 fputc ('\n', dump_file
);
1082 // ------------------------------------------------------------------------
1083 // GORI iterator. Although we have bitmap iterators, don't expose that it
1084 // is currently a bitmap. Use an export iterator to hide future changes.
1086 // Construct a basic iterator over an export bitmap.
1088 gori_export_iterator::gori_export_iterator (bitmap b
)
1092 bmp_iter_set_init (&bi
, b
, 1, &y
);
1096 // Move to the next export bitmap spot.
1099 gori_export_iterator::next ()
1101 bmp_iter_next (&bi
, &y
);
1105 // Fetch the name of the next export in the export list. Return NULL if
1106 // iteration is done.
1109 gori_export_iterator::get_name ()
1114 while (bmp_iter_set (&bi
, &y
))
1116 tree t
= ssa_name (y
);