1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-dump.h"
34 #include "diagnostic.h"
36 #include "tree-scalar-evolution.h"
37 #include "tree-ssa-propagate.h"
38 #include "tree-chrec.h"
40 /* Set of SSA names found during the dominator traversal of a
41 sub-graph in maybe_add_assert_expr. */
44 /* Loop structure of the program. Used to analyze scalar evolutions
45 inside adjust_range_with_scev. */
46 static struct loops
*cfg_loops
;
48 /* Local functions. */
49 static int compare_values (tree val1
, tree val2
);
51 /* Given a conditional predicate COND that has WHICH as one of its
52 operands, return the other operand. No error checking is done.
53 This helper assumes that COND is a comparison and WHICH is one of
57 get_opposite_operand (tree cond
, tree which
)
59 if (TREE_OPERAND (cond
, 0) == which
)
60 return TREE_OPERAND (cond
, 1);
62 return TREE_OPERAND (cond
, 0);
66 /* Given a comparison code, return its opposite. Note that this is *not*
67 the same as inverting its truth value (invert_tree_comparison). Here we
68 just want to literally flip the comparison around.
70 So, '<' gets '>', '<=' gets '>='. Both '==' and '!=' are returned
74 opposite_comparison (enum tree_code code
)
107 /* Set value range VR to {T, MIN, MAX}. */
110 set_value_range (value_range
*vr
, enum value_range_type t
, tree min
, tree max
)
112 #if defined ENABLE_CHECKING
113 if (t
== VR_RANGE
|| t
== VR_ANTI_RANGE
)
117 gcc_assert (min
&& max
);
119 if (INTEGRAL_TYPE_P (TREE_TYPE (min
)) && t
== VR_ANTI_RANGE
)
120 gcc_assert (min
!= TYPE_MIN_VALUE (TREE_TYPE (min
))
121 || max
!= TYPE_MAX_VALUE (TREE_TYPE (max
)));
123 cmp
= compare_values (min
, max
);
124 gcc_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
129 && INTEGRAL_TYPE_P (TREE_TYPE (min
))
130 && min
== TYPE_MIN_VALUE (TREE_TYPE (min
))
131 && max
== TYPE_MAX_VALUE (TREE_TYPE (max
)))
133 /* Ranges that cover all the possible values for the type decay
135 vr
->type
= VR_VARYING
;
147 /* Similar to set_value_range but return true if any field of VR
148 changed from its previous value. */
151 update_value_range (value_range
*vr
, enum value_range_type t
, tree min
,
154 bool is_new
= vr
->type
!= t
|| vr
->min
!= min
|| vr
->max
!= max
;
156 set_value_range (vr
, t
, min
, max
);
162 /* Return value range information for VAR. Create an empty range if
166 get_value_range (tree var
)
171 vr
= SSA_NAME_VALUE_RANGE (var
);
175 /* Create a default value range. */
176 vr
= ggc_alloc (sizeof (*vr
));
177 memset ((void *) vr
, 0, sizeof (*vr
));
178 SSA_NAME_VALUE_RANGE (var
) = vr
;
180 /* If VAR is a default definition for a PARM_DECL, then we have to
181 assume a VARYING range for it. */
182 sym
= SSA_NAME_VAR (var
);
183 if (TREE_CODE (sym
) == PARM_DECL
&& var
== var_ann (sym
)->default_def
)
184 set_value_range (vr
, VR_VARYING
, NULL_TREE
, NULL_TREE
);
190 /* Return true if value range VR involves at least one symbol. */
193 symbolic_range_p (value_range
*vr
)
195 return (!is_gimple_min_invariant (vr
->min
)
196 || !is_gimple_min_invariant (vr
->max
));
200 /* Return true if EXPR computes a non-zero value. */
203 expr_computes_nonzero (tree expr
)
205 /* Type casts won't change anything, so just strip it. */
208 /* Calling alloca, guarantees that the value is non-NULL. */
209 if (alloca_call_p (expr
))
212 /* The address of a non-weak symbol is never NULL, unless the user
213 has requested not to remove NULL pointer checks. */
214 if (flag_delete_null_pointer_checks
215 && TREE_CODE (expr
) == ADDR_EXPR
216 && DECL_P (TREE_OPERAND (expr
, 0))
217 && !DECL_WEAK (TREE_OPERAND (expr
, 0)))
220 /* IOR of any value with a nonzero value will result in a nonzero
222 if (TREE_CODE (expr
) == BIT_IOR_EXPR
223 && integer_nonzerop (TREE_OPERAND (expr
, 1)))
230 /* Return true if VR is ~[0, 0]. */
233 range_is_nonnull (value_range
*vr
)
235 return vr
->type
== VR_ANTI_RANGE
236 && integer_zerop (vr
->min
)
237 && integer_zerop (vr
->max
);
241 /* Return true if VR is [0, 0]. */
244 range_is_null (value_range
*vr
)
246 return vr
->type
== VR_RANGE
247 && integer_zerop (vr
->min
)
248 && integer_zerop (vr
->max
);
252 /* Set value range VR to a non-NULL range of type TYPE. */
255 set_value_range_to_nonnull (value_range
*vr
, tree type
)
257 tree zero
= build_int_cst (type
, 0);
258 set_value_range (vr
, VR_ANTI_RANGE
, zero
, zero
);
262 /* Set value range VR to a NULL range of type TYPE. */
265 set_value_range_to_null (value_range
*vr
, tree type
)
267 tree zero
= build_int_cst (type
, 0);
268 set_value_range (vr
, VR_RANGE
, zero
, zero
);
272 /* Set value range VR to VR_VARYING. */
275 set_value_range_to_varying (value_range
*vr
)
277 set_value_range (vr
, VR_VARYING
, NULL_TREE
, NULL_TREE
);
281 /* Compare two values VAL1 and VAL2. Return
283 -2 if VAL1 and VAL2 cannot be compared at compile-time,
286 +1 if VAL1 > VAL2, and
289 This is similar to tree_int_cst_compare but supports pointer values
290 and values that cannot be compared at compile time. */
293 compare_values (tree val1
, tree val2
)
298 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
300 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1
))
301 == POINTER_TYPE_P (TREE_TYPE (val2
)));
303 /* Do some limited symbolic comparisons. */
304 if (!POINTER_TYPE_P (TREE_TYPE (val1
)))
306 /* We can determine some comparisons against +INF and -INF even
307 if the other value is an expression. */
308 if (val1
== TYPE_MAX_VALUE (TREE_TYPE (val1
))
309 && TREE_CODE (val2
) == MINUS_EXPR
)
311 /* +INF > NAME - CST. */
314 else if (val1
== TYPE_MIN_VALUE (TREE_TYPE (val1
))
315 && TREE_CODE (val2
) == PLUS_EXPR
)
317 /* -INF < NAME + CST. */
320 else if (TREE_CODE (val1
) == MINUS_EXPR
321 && val2
== TYPE_MAX_VALUE (TREE_TYPE (val2
)))
323 /* NAME - CST < +INF. */
326 else if (TREE_CODE (val1
) == PLUS_EXPR
327 && val2
== TYPE_MIN_VALUE (TREE_TYPE (val2
)))
329 /* NAME + CST > -INF. */
334 if ((TREE_CODE (val1
) == SSA_NAME
335 || TREE_CODE (val1
) == PLUS_EXPR
336 || TREE_CODE (val1
) == MINUS_EXPR
)
337 && (TREE_CODE (val2
) == SSA_NAME
338 || TREE_CODE (val2
) == PLUS_EXPR
339 || TREE_CODE (val2
) == MINUS_EXPR
))
343 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
344 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
345 same name, return -2. */
346 if (TREE_CODE (val1
) == SSA_NAME
)
353 n1
= TREE_OPERAND (val1
, 0);
354 c1
= TREE_OPERAND (val1
, 1);
357 if (TREE_CODE (val2
) == SSA_NAME
)
364 n2
= TREE_OPERAND (val2
, 0);
365 c2
= TREE_OPERAND (val2
, 1);
368 /* Both values must use the same name. */
372 if (TREE_CODE (val1
) == SSA_NAME
)
374 if (TREE_CODE (val2
) == SSA_NAME
)
377 else if (TREE_CODE (val2
) == PLUS_EXPR
)
378 /* NAME < NAME + CST */
380 else if (TREE_CODE (val2
) == MINUS_EXPR
)
381 /* NAME > NAME - CST */
384 else if (TREE_CODE (val1
) == PLUS_EXPR
)
386 if (TREE_CODE (val2
) == SSA_NAME
)
387 /* NAME + CST > NAME */
389 else if (TREE_CODE (val2
) == PLUS_EXPR
)
390 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
391 return compare_values (c1
, c2
);
392 else if (TREE_CODE (val2
) == MINUS_EXPR
)
393 /* NAME + CST1 > NAME - CST2 */
396 else if (TREE_CODE (val1
) == MINUS_EXPR
)
398 if (TREE_CODE (val2
) == SSA_NAME
)
399 /* NAME - CST < NAME */
401 else if (TREE_CODE (val2
) == PLUS_EXPR
)
402 /* NAME - CST1 < NAME + CST2 */
404 else if (TREE_CODE (val2
) == MINUS_EXPR
)
405 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
406 C1 and C2 are swapped in the call to compare_values. */
407 return compare_values (c2
, c1
);
413 /* We cannot compare non-constants. */
414 if (!is_gimple_min_invariant (val1
) || !is_gimple_min_invariant (val2
))
417 if (!POINTER_TYPE_P (TREE_TYPE (val1
)))
418 return tree_int_cst_compare (val1
, val2
);
423 /* First see if VAL1 and VAL2 are not the same. */
424 if (val1
== val2
|| operand_equal_p (val1
, val2
, 0))
427 /* If VAL1 is a lower address than VAL2, return -1. */
428 t
= fold_binary (LT_EXPR
, boolean_type_node
, val1
, val2
);
429 if (t
== boolean_true_node
)
432 /* If VAL1 is a higher address than VAL2, return +1. */
433 t
= fold_binary (GT_EXPR
, boolean_type_node
, val1
, val2
);
434 if (t
== boolean_true_node
)
437 /* If VAL1 is different than VAL2, return +2. */
438 t
= fold_binary (NE_EXPR
, boolean_type_node
, val1
, val2
);
439 if (t
== boolean_true_node
)
447 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
448 0 if VAL is not inside VR,
449 -2 if we cannot tell either way. */
452 value_inside_range (tree val
, value_range
*vr
)
456 cmp1
= compare_values (val
, vr
->min
);
457 if (cmp1
== -2 || cmp1
== 2)
460 cmp2
= compare_values (val
, vr
->max
);
461 if (cmp2
== -2 || cmp2
== 2)
464 return (cmp1
== 0 || cmp1
== 1) && (cmp2
== -1 || cmp2
== 0);
468 /* Return true if value ranges VR0 and VR1 have a non-empty
472 value_ranges_intersect_p (value_range
*vr0
, value_range
*vr1
)
474 return (value_inside_range (vr1
->min
, vr0
) == 1
475 || value_inside_range (vr1
->max
, vr0
) == 1
476 || value_inside_range (vr0
->min
, vr1
) == 1
477 || value_inside_range (vr0
->max
, vr1
) == 1);
481 /* Extract value range information from an ASSERT_EXPR EXPR and store
485 extract_range_from_assert (value_range
*vr_p
, tree expr
)
487 tree var
, cond
, limit
, type
;
489 enum tree_code cond_code
;
491 var
= ASSERT_EXPR_VAR (expr
);
492 cond
= ASSERT_EXPR_COND (expr
);
493 cond_code
= TREE_CODE (cond
);
495 gcc_assert (COMPARISON_CLASS_P (cond
));
497 /* Find VAR in the ASSERT_EXPR conditional. */
498 limit
= get_opposite_operand (cond
, var
);
499 type
= TREE_TYPE (limit
);
501 gcc_assert (limit
!= var
);
503 /* For pointer arithmetic, we only keep track of anti-ranges
504 (NE_EXPR). Notice that we don't need to handle EQ_EXPR in these
505 cases because assertions with equalities are never generated.
506 The assert pass generates straight assignments in those cases. */
507 if (POINTER_TYPE_P (type
) && cond_code
!= NE_EXPR
)
509 set_value_range_to_varying (vr_p
);
513 /* Special handling for integral types with super-types. Some FEs
514 construct integral types derived from other types and restrict
515 the range of values these new types may take.
517 It may happen that LIMIT is actually smaller than TYPE's minimum
518 value. For instance, the Ada FE is generating code like this
521 D.1480_32 = nam_30 - 300000361;
522 if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
524 D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
526 All the names are of type types__name_id___XDLU_300000000__399999999
527 which has min == 300000000 and max == 399999999. This means that
528 the ASSERT_EXPR would try to create the range [3000000, 1] which
531 The fact that the type specifies MIN and MAX values does not
532 automatically mean that every variable of that type will always
533 be within that range, so the predicate may well be true at run
534 time. If we had symbolic -INF and +INF values, we could
535 represent this range, but we currently represent -INF and +INF
536 using the type's min and max values.
538 So, the only sensible thing we can do for now is set the
539 resulting range to VR_VARYING. TODO, would having symbolic -INF
540 and +INF values be worth the trouble? */
541 if (TREE_TYPE (type
))
543 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
545 tree type_min
= TYPE_MIN_VALUE (type
);
546 int cmp
= compare_values (limit
, type_min
);
548 /* For < or <= comparisons, if LIMIT is smaller than
549 TYPE_MIN, set the range to VR_VARYING. */
550 if (cmp
== -1 || cmp
== 0)
552 set_value_range_to_varying (vr_p
);
556 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
558 tree type_max
= TYPE_MIN_VALUE (type
);
559 int cmp
= compare_values (limit
, type_max
);
561 /* For > or >= comparisons, if LIMIT is bigger than
562 TYPE_MAX, set the range to VR_VARYING. */
563 if (cmp
== 1 || cmp
== 0)
565 set_value_range_to_varying (vr_p
);
571 if (TREE_CODE (cond
) == NE_EXPR
)
572 set_value_range (vr_p
, VR_ANTI_RANGE
, limit
, limit
);
573 else if (TREE_CODE (cond
) == LE_EXPR
)
574 set_value_range (vr_p
, VR_RANGE
, TYPE_MIN_VALUE (type
), limit
);
575 else if (TREE_CODE (cond
) == LT_EXPR
)
577 tree one
= build_int_cst (type
, 1);
578 set_value_range (vr_p
, VR_RANGE
, TYPE_MIN_VALUE (type
),
579 fold (build (MINUS_EXPR
, type
, limit
, one
)));
581 else if (TREE_CODE (cond
) == GE_EXPR
)
582 set_value_range (vr_p
, VR_RANGE
, limit
, TYPE_MAX_VALUE (type
));
583 else if (TREE_CODE (cond
) == GT_EXPR
)
585 tree one
= build_int_cst (type
, 1);
586 set_value_range (vr_p
, VR_RANGE
,
587 fold (build (PLUS_EXPR
, type
, limit
, one
)),
588 TYPE_MAX_VALUE (type
));
593 /* If VAR already has a known range and the two ranges have a
594 non-empty intersection, we can refine the resulting range.
595 Since the assert expression creates an equivalency and at the
596 same time it asserts a predicate, we can take the intersection of
597 the two ranges to get better precision. */
598 var_vr
= get_value_range (var
);
599 if (var_vr
->type
== VR_RANGE
600 && vr_p
->type
== VR_RANGE
601 && value_ranges_intersect_p (var_vr
, vr_p
))
605 /* Use the larger of the two minimums. */
606 if (compare_values (vr_p
->min
, var_vr
->min
) == -1)
611 /* Use the smaller of the two maximums. */
612 if (compare_values (vr_p
->max
, var_vr
->max
) == 1)
617 set_value_range (vr_p
, vr_p
->type
, min
, max
);
622 /* Extract range information from SSA name VAR and store it in VR. If
623 VAR has an interesting range, use it. Otherwise, create the
624 range [VAR, VAR] and return it. This is useful in situations where
625 we may have conditionals testing values of VARYING names. For
632 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
636 extract_range_from_ssa_name (value_range
*vr
, tree var
)
638 value_range
*var_vr
= get_value_range (var
);
640 if (var_vr
->type
!= VR_UNDEFINED
&& var_vr
->type
!= VR_VARYING
)
643 set_value_range (vr
, VR_RANGE
, var
, var
);
647 /* Extract range information from a binary expression EXPR based on
648 the ranges of each of its operands and the expression code. */
651 extract_range_from_binary_expr (value_range
*vr
, tree expr
)
653 enum tree_code code
= TREE_CODE (expr
);
654 tree op0
, op1
, min
, max
;
655 value_range vr0
, vr1
;
658 /* Not all binary expressions can be applied to ranges in a
659 meaningful way. Handle only arithmetic operations. */
660 if (code
!= PLUS_EXPR
661 && code
!= MINUS_EXPR
663 && code
!= TRUNC_DIV_EXPR
664 && code
!= FLOOR_DIV_EXPR
665 && code
!= CEIL_DIV_EXPR
666 && code
!= EXACT_DIV_EXPR
667 && code
!= ROUND_DIV_EXPR
671 set_value_range_to_varying (vr
);
675 /* Get value ranges for each operand. For constant operands, create
676 a new value range with the operand to simplify processing. */
677 op0
= TREE_OPERAND (expr
, 0);
678 if (TREE_CODE (op0
) == SSA_NAME
)
679 vr0
= *(get_value_range (op0
));
682 if (is_gimple_min_invariant (op0
))
683 set_value_range (&vr0
, VR_RANGE
, op0
, op0
);
685 set_value_range_to_varying (&vr0
);
688 op1
= TREE_OPERAND (expr
, 1);
689 if (TREE_CODE (op1
) == SSA_NAME
)
690 vr1
= *(get_value_range (op1
));
693 if (is_gimple_min_invariant (op1
))
694 set_value_range (&vr1
, VR_RANGE
, op1
, op1
);
696 set_value_range_to_varying (&vr1
);
699 /* If either range is UNDEFINED, so is the result. */
700 if (vr0
.type
== VR_UNDEFINED
|| vr1
.type
== VR_UNDEFINED
)
702 set_value_range (vr
, VR_UNDEFINED
, NULL_TREE
, NULL_TREE
);
706 /* If either range is VARYING, so is the result. */
707 if (vr0
.type
== VR_VARYING
|| vr1
.type
== VR_VARYING
)
709 set_value_range_to_varying (vr
);
713 /* If the ranges are of different types, the result is VARYING. */
714 if (vr0
.type
!= vr1
.type
)
716 set_value_range_to_varying (vr
);
720 /* TODO. Refuse to do any symbolic range operations for now. */
721 if (symbolic_range_p (&vr0
) || symbolic_range_p (&vr1
))
723 set_value_range_to_varying (vr
);
727 /* Now evaluate the expression to determine the new range. */
728 if (POINTER_TYPE_P (TREE_TYPE (expr
))
729 || POINTER_TYPE_P (TREE_TYPE (op0
))
730 || POINTER_TYPE_P (TREE_TYPE (op1
)))
732 /* For pointer types, we are really only interested in asserting
733 whether the expression evaluates to non-NULL. FIXME. We
734 used to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR),
735 but ivopts is generating expressions with pointer
736 multiplication in them. */
737 if (code
== PLUS_EXPR
)
739 /* Assume that pointers can never wrap around. FIXME, Is
741 tree zero
= build_int_cst (TREE_TYPE (expr
), 0);
742 set_value_range (vr
, VR_ANTI_RANGE
, zero
, zero
);
746 /* Subtracting from a pointer, may yield 0, so just drop the
747 resulting range to varying. */
748 set_value_range_to_varying (vr
);
754 /* For integer ranges, apply the operation to each end of the
755 range and see what we end up with. */
756 if (code
== PLUS_EXPR
761 /* For operations that make the resulting range directly
762 proportional to the original ranges, apply the operation to
763 the same end of each range. */
764 min
= int_const_binop (code
, vr0
.min
, vr1
.min
, 0);
765 max
= int_const_binop (code
, vr0
.max
, vr1
.max
, 0);
769 /* For operations that make the resulting range inversely
770 proportional to the original ranges (-, /), apply the
771 operation to the opposite ends of each range. */
772 min
= int_const_binop (code
, vr0
.min
, vr1
.max
, 0);
773 max
= int_const_binop (code
, vr0
.max
, vr1
.min
, 0);
776 cmp
= compare_values (min
, max
);
777 if (cmp
== -2 || cmp
== 1)
779 /* If the new range has its limits swapped around (MIN > MAX),
780 then the operation caused one of them to wrap around, mark
781 the new range VARYING. */
782 set_value_range_to_varying (vr
);
785 set_value_range (vr
, vr0
.type
, min
, max
);
789 /* Like expr_computes_nonzero, but this function uses value ranges
793 vrp_expr_computes_nonzero (tree expr
)
795 if (expr_computes_nonzero (expr
))
798 /* If we have an expression of the form &X->a, then the expression
799 is nonnull if X is nonnull. */
800 if (TREE_CODE (expr
) == ADDR_EXPR
)
802 tree base
= get_base_address (TREE_OPERAND (expr
, 0));
804 if (base
!= NULL_TREE
805 && TREE_CODE (base
) == INDIRECT_REF
806 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
808 value_range
*vr
= get_value_range (TREE_OPERAND (base
, 0));
809 if (range_is_nonnull (vr
))
818 /* Extract range information from a unary expression EXPR based on
819 the range of its operand and the expression code. */
822 extract_range_from_unary_expr (value_range
*vr
, tree expr
)
824 enum tree_code code
= TREE_CODE (expr
);
829 /* Get value ranges for the operand. For constant operands, create
830 a new value range with the operand to simplify processing. */
831 op0
= TREE_OPERAND (expr
, 0);
832 if (TREE_CODE (op0
) == SSA_NAME
)
833 vr0
= *(get_value_range (op0
));
836 if (is_gimple_min_invariant (op0
))
837 set_value_range (&vr0
, VR_RANGE
, op0
, op0
);
839 set_value_range_to_varying (&vr0
);
842 /* If VR0 is UNDEFINED, so is the result. */
843 if (vr0
.type
== VR_UNDEFINED
)
845 set_value_range (vr
, VR_UNDEFINED
, NULL_TREE
, NULL_TREE
);
849 /* If VR0 is VARYING, so is the result. */
850 if (vr0
.type
== VR_VARYING
)
852 set_value_range_to_varying (vr
);
856 /* TODO. Refuse to do any symbolic range operations for now. */
857 if (symbolic_range_p (&vr0
))
859 set_value_range_to_varying (vr
);
863 /* If the operand is neither a pointer nor an integral type, set the
864 range to VARYING. TODO, we may set the range to non-zero. */
865 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
866 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
868 set_value_range_to_varying (vr
);
872 /* If the expression involves pointers, we are only interested in
873 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
874 if (POINTER_TYPE_P (TREE_TYPE (expr
)) || POINTER_TYPE_P (TREE_TYPE (op0
)))
876 if (range_is_nonnull (&vr0
) || expr_computes_nonzero (expr
))
877 set_value_range_to_nonnull (vr
, TREE_TYPE (expr
));
878 else if (range_is_null (&vr0
))
879 set_value_range_to_null (vr
, TREE_TYPE (expr
));
881 set_value_range_to_varying (vr
);
886 /* Handle unary expressions on integer ranges. */
887 if ((code
== NOP_EXPR
|| code
== CONVERT_EXPR
)
888 && (TYPE_SIZE (TREE_TYPE (vr0
.min
)) != TYPE_SIZE (TREE_TYPE (expr
))))
890 /* When converting types of different sizes, set the result to
891 VARYING. Things like sign extensions and precision loss may
892 change the range. For instance, if x_3 is of type 'long long
893 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
894 is impossible to know at compile time whether y_5 will be
896 set_value_range_to_varying (vr
);
900 /* Apply the operation to each end of the range and see what we end
902 min
= fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.min
);
903 max
= fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.max
);
905 cmp
= compare_values (min
, max
);
906 if (cmp
== -2 || cmp
== 1)
908 /* If the new range has its limits swapped around (MIN > MAX),
909 then the operation caused one of them to wrap around, mark
910 the new range VARYING. */
911 set_value_range_to_varying (vr
);
914 set_value_range (vr
, vr0
.type
, min
, max
);
918 /* Try to compute a useful range out of expression EXPR and store it
922 extract_range_from_expr (value_range
*vr
, tree expr
)
924 enum tree_code code
= TREE_CODE (expr
);
926 if (code
== ASSERT_EXPR
)
927 extract_range_from_assert (vr
, expr
);
928 else if (code
== SSA_NAME
)
929 extract_range_from_ssa_name (vr
, expr
);
930 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
931 extract_range_from_binary_expr (vr
, expr
);
932 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
933 extract_range_from_unary_expr (vr
, expr
);
934 else if (vrp_expr_computes_nonzero (expr
))
935 set_value_range_to_nonnull (vr
, TREE_TYPE (expr
));
936 else if (TREE_CODE (expr
) == INTEGER_CST
)
937 set_value_range (vr
, VR_RANGE
, expr
, expr
);
939 set_value_range_to_varying (vr
);
943 /* Given a range VR, a loop L and a variable VAR, determine whether it
944 would be profitable to adjust VR using scalar evolution information
945 for VAR. If so, update VR with the new limits. */
948 adjust_range_with_scev (value_range
*vr
, struct loop
*l
, tree var
)
950 tree init
, step
, chrec
;
953 /* TODO. Don't adjust anti-ranges. An anti-range may provide
954 better opportunities than a regular range, but I'm not sure. */
955 if (vr
->type
== VR_ANTI_RANGE
)
958 chrec
= analyze_scalar_evolution (l
, var
);
959 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
962 init
= CHREC_LEFT (chrec
);
963 step
= CHREC_RIGHT (chrec
);
965 /* If STEP is symbolic, we can't know whether INIT will be the
966 minimum or maximum value in the range. */
967 if (!is_gimple_min_invariant (step
))
970 /* FIXME. When dealing with unsigned types,
971 analyze_scalar_evolution sets STEP to very large unsigned values
972 when the evolution goes backwards. This confuses this analysis
973 because we think that INIT is the smallest value that the range
974 can take, instead of the largest. Ignore these chrecs for now. */
975 if (INTEGRAL_TYPE_P (TREE_TYPE (step
)) && TYPE_UNSIGNED (TREE_TYPE (step
)))
978 /* If STEP is negative, then INIT is the maximum value the range
979 will take. Otherwise, INIT is the minimum value. */
980 init_is_max
= (tree_int_cst_sgn (step
) < 0);
982 if (!POINTER_TYPE_P (TREE_TYPE (init
))
983 && (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
))
985 /* For VARYING or UNDEFINED ranges, just about anything we get
986 from scalar evolutions should be better. */
988 set_value_range (vr
, VR_RANGE
, TYPE_MIN_VALUE (TREE_TYPE (init
)), init
);
990 set_value_range (vr
, VR_RANGE
, init
, TYPE_MAX_VALUE (TREE_TYPE (init
)));
992 else if (vr
->type
== VR_RANGE
)
999 /* INIT is the maximum value. If INIT is lower than VR->MAX
1000 but no smaller than VR->MIN, set VR->MAX to INIT. */
1001 if (compare_values (init
, max
) == -1)
1005 /* If we just created an invalid range with the minimum
1006 greater than the maximum, take the minimum all the
1008 if (compare_values (min
, max
) == 1)
1009 min
= TYPE_MIN_VALUE (TREE_TYPE (min
));
1014 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1015 if (compare_values (init
, min
) == 1)
1019 /* If we just created an invalid range with the minimum
1020 greater than the maximum, take the maximum all the
1022 if (compare_values (min
, max
) == 1)
1023 max
= TYPE_MAX_VALUE (TREE_TYPE (max
));
1027 set_value_range (vr
, VR_RANGE
, min
, max
);
1032 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1034 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for all the
1035 values in the ranges.
1037 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1039 - Return NULL_TREE if it is not always possible to determine the value of
1043 compare_ranges (enum tree_code comp
, value_range
*vr0
, value_range
*vr1
)
1045 /* VARYING or UNDEFINED ranges cannot be compared. */
1046 if (vr0
->type
== VR_VARYING
1047 || vr0
->type
== VR_UNDEFINED
1048 || vr1
->type
== VR_VARYING
1049 || vr1
->type
== VR_UNDEFINED
)
1052 /* Anti-ranges need to be handled separately. */
1053 if (vr0
->type
== VR_ANTI_RANGE
|| vr1
->type
== VR_ANTI_RANGE
)
1055 /* If both are anti-ranges, then we cannot compute any
1057 if (vr0
->type
== VR_ANTI_RANGE
&& vr1
->type
== VR_ANTI_RANGE
)
1060 /* These comparisons are never statically computable. */
1067 /* Equality can be computed only between a range and an
1068 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1069 if (vr0
->type
== VR_RANGE
)
1071 /* To simplify processing, make VR0 the anti-range. */
1072 value_range
*tmp
= vr0
;
1077 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
1079 if (compare_values (vr0
->min
, vr1
->min
) == 0
1080 && compare_values (vr0
->max
, vr1
->max
) == 0)
1081 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1086 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1087 operands around and change the comparison code. */
1088 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1091 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
1097 if (comp
== EQ_EXPR
)
1099 /* Equality may only be computed if both ranges represent
1100 exactly one value. */
1101 if (compare_values (vr0
->min
, vr0
->max
) == 0
1102 && compare_values (vr1
->min
, vr1
->max
) == 0)
1104 int cmp_min
= compare_values (vr0
->min
, vr1
->min
);
1105 int cmp_max
= compare_values (vr0
->max
, vr1
->max
);
1106 if (cmp_min
== 0 && cmp_max
== 0)
1107 return boolean_true_node
;
1108 else if (cmp_min
!= -2 && cmp_max
!= -2)
1109 return boolean_false_node
;
1114 else if (comp
== NE_EXPR
)
1118 /* If VR0 is completely to the left or completely to the right
1119 of VR1, they are always different. Notice that we need to
1120 make sure that both comparisons yield similar results to
1121 avoid comparing values that cannot be compared at
1123 cmp1
= compare_values (vr0
->max
, vr1
->min
);
1124 cmp2
= compare_values (vr0
->min
, vr1
->max
);
1125 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
1126 return boolean_true_node
;
1128 /* If VR0 and VR1 represent a single value and are identical,
1130 else if (compare_values (vr0
->min
, vr0
->max
) == 0
1131 && compare_values (vr1
->min
, vr1
->max
) == 0
1132 && compare_values (vr0
->min
, vr1
->min
) == 0
1133 && compare_values (vr0
->max
, vr1
->max
) == 0)
1134 return boolean_false_node
;
1136 /* Otherwise, they may or may not be different. */
1140 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1144 /* If VR0 is to the left of VR1, return true. */
1145 tst
= compare_values (vr0
->max
, vr1
->min
);
1146 if ((comp
== LT_EXPR
&& tst
== -1)
1147 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1148 return boolean_true_node
;
1150 /* If VR0 is to the right of VR1, return false. */
1151 tst
= compare_values (vr0
->min
, vr1
->max
);
1152 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1153 || (comp
== LE_EXPR
&& tst
== 1))
1154 return boolean_false_node
;
1156 /* Otherwise, we don't know. */
1164 /* Given a value range VR, a value VAL and a comparison code COMP, return
1165 BOOLEAN_TRUE_NODE if VR COMP VR1 always returns true for all the
1166 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1167 always returns false. Return NULL_TREE if it is not always
1168 possible to determine the value of the comparison. */
1171 compare_range_with_value (enum tree_code comp
, value_range
*vr
, tree val
)
1173 if (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
)
1176 /* Anti-ranges need to be handled separately. */
1177 if (vr
->type
== VR_ANTI_RANGE
)
1179 /* For anti-ranges, the only predicates that we can compute at
1180 compile time are equality and inequality. */
1187 /* ~[VAL, VAL] == VAL is always false. */
1188 if (compare_values (vr
->min
, val
) == 0
1189 && compare_values (vr
->max
, val
) == 0)
1190 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1195 if (comp
== EQ_EXPR
)
1197 /* EQ_EXPR may only be computed if VR represents exactly
1199 if (compare_values (vr
->min
, vr
->max
) == 0)
1201 int cmp
= compare_values (vr
->min
, val
);
1203 return boolean_true_node
;
1204 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
1205 return boolean_false_node
;
1210 else if (comp
== NE_EXPR
)
1212 /* If VAL is not inside VR, then they are always different. */
1213 if (compare_values (vr
->max
, val
) == -1
1214 || compare_values (vr
->min
, val
) == 1)
1215 return boolean_true_node
;
1217 /* If VR represents exactly one value equal to VAL, then return
1219 if (compare_values (vr
->min
, vr
->max
) == 0
1220 && compare_values (vr
->min
, val
) == 0)
1221 return boolean_false_node
;
1223 /* Otherwise, they may or may not be different. */
1226 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1230 /* If VR is to the left of VAL, return true. */
1231 tst
= compare_values (vr
->max
, val
);
1232 if ((comp
== LT_EXPR
&& tst
== -1)
1233 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1234 return boolean_true_node
;
1236 /* If VR is to the right of VAL, return false. */
1237 tst
= compare_values (vr
->min
, val
);
1238 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1239 || (comp
== LE_EXPR
&& tst
== 1))
1240 return boolean_false_node
;
1242 /* Otherwise, we don't know. */
1245 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1249 /* If VR is to the right of VAL, return true. */
1250 tst
= compare_values (vr
->min
, val
);
1251 if ((comp
== GT_EXPR
&& tst
== 1)
1252 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
1253 return boolean_true_node
;
1255 /* If VR is to the left of VAL, return false. */
1256 tst
= compare_values (vr
->max
, val
);
1257 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
1258 || (comp
== GE_EXPR
&& tst
== -1))
1259 return boolean_false_node
;
1261 /* Otherwise, we don't know. */
1269 /* Debugging dumps. */
1272 dump_value_range (FILE *file
, value_range
*vr
)
1275 fprintf (file
, "[]");
1276 else if (vr
->type
== VR_UNDEFINED
)
1277 fprintf (file
, "UNDEFINED");
1278 else if (vr
->type
== VR_RANGE
|| vr
->type
== VR_ANTI_RANGE
)
1280 fprintf (file
, "%s[", (vr
->type
== VR_ANTI_RANGE
) ? "~" : "");
1281 print_generic_expr (file
, vr
->min
, 0);
1282 fprintf (file
, ", ");
1283 print_generic_expr (file
, vr
->max
, 0);
1284 fprintf (file
, "]");
1286 else if (vr
->type
== VR_VARYING
)
1287 fprintf (file
, "VARYING");
1289 fprintf (file
, "INVALID RANGE");
1293 /* Dump value range VR to stderr. */
1296 debug_value_range (value_range
*vr
)
1298 dump_value_range (stderr
, vr
);
1302 /* Dump value ranges of all SSA_NAMEs to FILE. */
1305 dump_all_value_ranges (FILE *file
)
1309 for (i
= 0; i
< num_ssa_names
; i
++)
1311 tree var
= ssa_name (i
);
1312 if (var
&& SSA_NAME_VALUE_RANGE (var
))
1314 print_generic_expr (file
, var
, 0);
1315 fprintf (file
, ": ");
1316 dump_value_range (file
, SSA_NAME_VALUE_RANGE (var
));
1317 fprintf (file
, "\n");
1321 fprintf (file
, "\n");
1325 /* Dump all value ranges to stderr. */
1328 debug_all_value_ranges (void)
1330 dump_all_value_ranges (stderr
);
1334 /*---------------------------------------------------------------------------
1335 Value Range Propagation
1336 ---------------------------------------------------------------------------*/
1338 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
1339 create a new SSA name N and return the assertion assignment
1340 'V = ASSERT_EXPR <V, V OP W>'. */
1343 build_assert_expr_for (tree cond
, tree v
)
1347 gcc_assert (TREE_CODE (v
) == SSA_NAME
);
1348 n
= duplicate_ssa_name (v
, NULL_TREE
);
1350 if (COMPARISON_CLASS_P (cond
))
1352 /* Build N = ASSERT_EXPR <V, COND>. As a special case, if the
1353 conditional is an EQ_EXPR (V == Z), just build the assignment
1355 if (TREE_CODE (cond
) == EQ_EXPR
)
1357 tree other
= get_opposite_operand (cond
, v
);
1358 assertion
= build (MODIFY_EXPR
, TREE_TYPE (v
), n
, other
);
1361 assertion
= build (MODIFY_EXPR
, TREE_TYPE (v
), n
,
1362 build (ASSERT_EXPR
, TREE_TYPE (v
), v
, cond
));
1364 else if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1366 /* Given !V, build the assignment N = false. */
1367 tree op0
= TREE_OPERAND (cond
, 0);
1368 gcc_assert (op0
== v
);
1369 assertion
= build (MODIFY_EXPR
, TREE_TYPE (v
), n
, boolean_false_node
);
1371 else if (TREE_CODE (cond
) == SSA_NAME
)
1373 /* Given V, build the assignment N = true. */
1374 gcc_assert (v
== cond
);
1375 assertion
= build (MODIFY_EXPR
, TREE_TYPE (v
), n
, boolean_true_node
);
1380 SSA_NAME_DEF_STMT (n
) = assertion
;
1382 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
1383 operand of the ASSERT_EXPR. Register the new name and the old one
1384 in the replacement table so that we can fix the SSA web after
1385 adding all the ASSERT_EXPRs. */
1386 register_new_name_mapping (n
, v
);
1392 /* Return false if EXPR is a predicate expression involving floating
1396 fp_predicate (tree expr
)
1398 return (COMPARISON_CLASS_P (expr
)
1399 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr
, 0))));
1403 /* Return an expression predicate that represents the range of values
1404 that can be taken by operand OP after STMT executes. */
1407 infer_value_range (tree stmt
, tree op
)
1409 /* Do not attempt to infer anything in names that flow through
1411 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
1414 if (POINTER_TYPE_P (TREE_TYPE (op
)))
1417 unsigned num_uses
, num_derefs
;
1419 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
1420 if (num_derefs
> 0 && flag_delete_null_pointer_checks
)
1422 /* We can only assume that a pointer dereference will yield
1423 non-NULL if -fdelete-null-pointer-checks is enabled. */
1424 tree null
= build_int_cst (TREE_TYPE (op
), 0);
1425 tree t
= build (NE_EXPR
, boolean_type_node
, op
, null
);
1434 /* Return true if OP is the result of an ASSERT_EXPR that tests the
1435 same condition as COND. */
1438 has_assert_expr (tree op
, tree cond
)
1440 tree def_stmt
= SSA_NAME_DEF_STMT (op
);
1441 tree assert_expr
, other_cond
, other_op
;
1443 /* If OP was not generated by an ASSERT_EXPR, return false. */
1444 if (TREE_CODE (def_stmt
) != MODIFY_EXPR
1445 || TREE_CODE (TREE_OPERAND (def_stmt
, 1)) != ASSERT_EXPR
)
1448 assert_expr
= TREE_OPERAND (def_stmt
, 1);
1449 other_cond
= ASSERT_EXPR_COND (assert_expr
);
1450 other_op
= ASSERT_EXPR_VAR (assert_expr
);
1452 if (TREE_CODE (cond
) == TREE_CODE (other_cond
))
1456 /* If COND is not a comparison predicate, something is wrong. */
1457 gcc_assert (COMPARISON_CLASS_P (cond
));
1459 /* Note that we only need to compare against one of the operands
1462 Suppose that we are about to insert the assertion ASSERT_EXPR
1463 <x_4, x_4 != 0> and the defining statement for x_4 is x_4 =
1464 ASSERT_EXPR <x_3, x_3 != 0>.
1466 In this case, we don't really want to insert a new
1467 ASSERT_EXPR for x_4 because that would be redundant. We
1468 already know that x_4 is not 0. So, when comparing the
1469 conditionals 'x_3 != 0' and 'x_4 != 0', we don't want to
1470 compare x_3 and x_4, we just want to compare the predicate's
1471 code (!=) and the other operand (0). */
1472 if (TREE_OPERAND (cond
, 0) == op
)
1473 t1
= TREE_OPERAND (cond
, 1);
1475 t1
= TREE_OPERAND (cond
, 0);
1477 if (TREE_OPERAND (other_cond
, 0) == other_op
)
1478 t2
= TREE_OPERAND (other_cond
, 1);
1480 t2
= TREE_OPERAND (other_cond
, 0);
1482 return (t1
== t2
|| operand_equal_p (t1
, t2
, 0));
1489 /* Traverse all the statements in block BB looking for used variables.
1490 Variables used in BB are added to bitmap FOUND. The algorithm
1491 works in three main parts:
1493 1- For every statement S in BB, all the variables used by S are
1494 added to bitmap FOUND.
1496 2- If statement S uses an operand N in a way that exposes a known
1497 value range for N, then if N was not already generated by an
1498 ASSERT_EXPR, create a new ASSERT_EXPR for N. For instance, if N
1499 is a pointer and the statement dereferences it, we can assume
1502 3- COND_EXPRs are a special case of #2. We can derive range
1503 information from the predicate but need to insert different
1504 ASSERT_EXPRs for each of the sub-graphs rooted at the
1505 conditional block. If the last statement of BB is a conditional
1506 expression of the form 'X op Y', then
1508 a) Remove X and Y from the set FOUND.
1510 b) If the conditional dominates its THEN_CLAUSE sub-graph,
1511 recurse into it. On return, if X and/or Y are marked in
1512 FOUND, then an ASSERT_EXPR is added for the corresponding
1515 c) Repeat step (b) on the ELSE_CLAUSE.
1517 d) Mark X and Y in FOUND.
1519 4- If BB does not end in a conditional expression, then we recurse
1520 into BB's dominator children.
1522 At the end of the recursive traversal, ASSERT_EXPRs will have been
1523 added to the edges of COND_EXPR blocks that have sub-graphs using
1524 one or both predicate operands. For instance,
1531 In this case, an assertion on the THEN clause is useful to
1532 determine that 'a' is always 9 on that edge. However, an assertion
1533 on the ELSE clause would be unnecessary.
1535 On exit from this function, all the names created by the newly
1536 inserted ASSERT_EXPRs need to be added to the SSA web by rewriting
1537 the SSA names that they replace.
1539 TODO. Handle SWITCH_EXPR. */
1542 maybe_add_assert_expr (basic_block bb
)
1544 block_stmt_iterator si
;
1548 /* Step 1. Mark all the SSA names used in BB in bitmap FOUND. */
1551 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
1556 stmt
= bsi_stmt (si
);
1558 /* Mark all the SSA names used by STMT in bitmap FOUND. If STMT
1559 is inside the sub-graph of a conditional block, when we
1560 return from this recursive walk, our parent will use the
1561 FOUND bitset to determine if one of the operands it was
1562 looking for was present in the sub-graph. */
1563 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
1567 /* If OP is used only once, namely in this STMT, don't
1568 bother inserting an ASSERT_EXPR for it. Such an
1569 ASSERT_EXPR would do nothing but increase compile time.
1570 Experiments show that with this simple check, we can save
1571 more than 20% of ASSERT_EXPRs. */
1572 if (has_single_use (op
))
1575 SET_BIT (found
, SSA_NAME_VERSION (op
));
1577 cond
= infer_value_range (stmt
, op
);
1581 /* Step 2. If OP is used in such a way that we can infer a
1582 value range for it, create a new ASSERT_EXPR for OP
1583 (unless OP already has an ASSERT_EXPR). */
1584 gcc_assert (!is_ctrl_stmt (stmt
));
1586 if (has_assert_expr (op
, cond
))
1589 if (!stmt_ends_bb_p (stmt
))
1591 /* If STMT does not end the block, we can insert the new
1592 assertion right after it. */
1593 tree t
= build_assert_expr_for (cond
, op
);
1594 bsi_insert_after (&si
, t
, BSI_NEW_STMT
);
1599 /* STMT must be the last statement in BB. We can only
1600 insert new assertions on the non-abnormal edge out of
1601 BB. Note that since STMT is not control flow, there
1602 may only be one non-abnormal edge out of BB. */
1606 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1607 if (!(e
->flags
& EDGE_ABNORMAL
))
1609 tree t
= build_assert_expr_for (cond
, op
);
1610 bsi_insert_on_edge (e
, t
);
1617 /* Remember the last statement of the block. */
1621 /* Step 3. If BB's last statement is a conditional expression
1622 involving integer operands, recurse into each of the sub-graphs
1623 rooted at BB to determine if we need to add ASSERT_EXPRs.
1624 Notice that we only care about the first operand of the
1625 conditional. Adding assertions for both operands may actually
1626 hinder VRP. FIXME, add example. */
1628 && TREE_CODE (last
) == COND_EXPR
1629 && !fp_predicate (COND_EXPR_COND (last
))
1630 && !ZERO_SSA_OPERANDS (last
, SSA_OP_USE
))
1638 cond
= COND_EXPR_COND (last
);
1640 /* Get just the first use operand. */
1641 FOR_EACH_SSA_TREE_OPERAND (op
, last
, iter
, SSA_OP_USE
)
1643 gcc_assert (op
!= NULL
);
1645 /* Do not attempt to infer anything in names that flow through
1647 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
1650 /* Remove the COND_EXPR operand from the FOUND bitmap.
1651 Otherwise, when we finish traversing each of the sub-graphs,
1652 we won't know whether the variables were found in the
1653 sub-graphs or if they had been found in a block upstream from
1655 RESET_BIT (found
, SSA_NAME_VERSION (op
));
1657 /* Look for uses of the operands in each of the sub-graphs
1658 rooted at BB. We need to check each of the outgoing edges
1659 separately, so that we know what kind of ASSERT_EXPR to
1661 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1663 /* If BB strictly dominates the sub-graph at E->DEST,
1666 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
1667 added
|= maybe_add_assert_expr (e
->dest
);
1669 /* Once we traversed the sub-graph, check if any block inside
1670 used either of the predicate's operands. If so, add the
1671 appropriate ASSERT_EXPR. */
1672 if (TEST_BIT (found
, SSA_NAME_VERSION (op
)))
1674 /* We found a use of OP in the sub-graph rooted at
1675 E->DEST. Add an ASSERT_EXPR according to whether
1676 E goes to THEN_CLAUSE or ELSE_CLAUSE. */
1679 if (e
->flags
& EDGE_TRUE_VALUE
)
1680 c
= unshare_expr (cond
);
1681 else if (e
->flags
& EDGE_FALSE_VALUE
)
1682 c
= invert_truthvalue (cond
);
1686 t
= build_assert_expr_for (c
, op
);
1687 bsi_insert_on_edge (e
, t
);
1692 /* Finally, mark all the COND_EXPR operands as found. */
1693 SET_BIT (found
, SSA_NAME_VERSION (op
));
1695 /* Recurse into the dominator children of BB that are not BB's
1696 immediate successors. Note that we have already visited BB's
1697 other dominator children above. */
1698 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
1700 son
= next_dom_son (CDI_DOMINATORS
, son
))
1702 if (find_edge (bb
, son
) == NULL
)
1703 added
|= maybe_add_assert_expr (son
);
1708 /* Step 4. Recurse into the dominator children of BB. */
1711 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
1713 son
= next_dom_son (CDI_DOMINATORS
, son
))
1714 added
|= maybe_add_assert_expr (son
);
1721 /* Traverse the flowgraph looking for conditional jumps to insert range
1722 expressions. These range expressions are meant to provide information
1723 to optimizations that need to reason in terms of value ranges. They
1724 will not be expanded into RTL. For instance, given:
1733 this pass will transform the code into:
1739 x = ASSERT_EXPR <x, x < y>
1744 y = ASSERT_EXPR <y, x <= y>
1748 The idea is that once copy and constant propagation have run, other
1749 optimizations will be able to determine what ranges of values can 'x'
1750 take in different paths of the code, simply by checking the reaching
1751 definition of 'x'. */
1754 insert_range_assertions (void)
1760 found
= sbitmap_alloc (num_ssa_names
);
1761 sbitmap_zero (found
);
1763 calculate_dominance_info (CDI_DOMINATORS
);
1765 update_ssa_p
= false;
1766 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
1767 if (maybe_add_assert_expr (e
->dest
))
1768 update_ssa_p
= true;
1772 bsi_commit_edge_inserts ();
1773 update_ssa (TODO_update_ssa_no_phi
);
1776 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1778 fprintf (dump_file
, "\nSSA form after inserting ASSERT_EXPRs\n");
1779 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1782 sbitmap_free (found
);
1786 /* Convert range assertion expressions into copies. FIXME, explain why. */
1789 remove_range_assertions (void)
1792 block_stmt_iterator si
;
1795 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
1797 tree stmt
= bsi_stmt (si
);
1799 if (TREE_CODE (stmt
) == MODIFY_EXPR
1800 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == ASSERT_EXPR
)
1802 tree rhs
= TREE_OPERAND (stmt
, 1);
1803 tree cond
= fold (ASSERT_EXPR_COND (rhs
));
1804 gcc_assert (cond
!= boolean_false_node
);
1805 TREE_OPERAND (stmt
, 1) = ASSERT_EXPR_VAR (rhs
);
1812 /* Return true if STMT is interesting for VRP. */
1815 stmt_interesting_for_vrp (tree stmt
)
1817 if (TREE_CODE (stmt
) == PHI_NODE
1818 && is_gimple_reg (PHI_RESULT (stmt
))
1819 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt
)))
1820 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt
)))))
1822 else if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1824 tree lhs
= TREE_OPERAND (stmt
, 0);
1826 if (TREE_CODE (lhs
) == SSA_NAME
1827 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1828 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
1829 && ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
1832 else if (TREE_CODE (stmt
) == COND_EXPR
|| TREE_CODE (stmt
) == SWITCH_EXPR
)
1839 /* Initialize local data structures for VRP. Return true if VRP
1840 is worth running (i.e. if we found any statements that could
1841 benefit from range information). */
1844 vrp_initialize (void)
1849 /* If we don't find any ASSERT_EXPRs in the code, there's no point
1855 block_stmt_iterator si
;
1858 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1860 if (!stmt_interesting_for_vrp (phi
))
1862 tree lhs
= PHI_RESULT (phi
);
1863 set_value_range_to_varying (get_value_range (lhs
));
1864 DONT_SIMULATE_AGAIN (phi
) = true;
1867 DONT_SIMULATE_AGAIN (phi
) = false;
1870 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
1872 tree stmt
= bsi_stmt (si
);
1874 if (!stmt_interesting_for_vrp (stmt
))
1878 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, i
, SSA_OP_DEF
)
1879 set_value_range_to_varying (get_value_range (def
));
1880 DONT_SIMULATE_AGAIN (stmt
) = true;
1884 if (TREE_CODE (stmt
) == MODIFY_EXPR
1885 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == ASSERT_EXPR
)
1888 DONT_SIMULATE_AGAIN (stmt
) = false;
1897 /* Visit assignment STMT. If it produces an interesting range, record
1898 the SSA name in *OUTPUT_P. */
1900 static enum ssa_prop_result
1901 vrp_visit_assignment (tree stmt
, tree
*output_p
)
1906 lhs
= TREE_OPERAND (stmt
, 0);
1907 rhs
= TREE_OPERAND (stmt
, 1);
1909 /* We only keep track of ranges in integral and pointer types. */
1910 if (TREE_CODE (lhs
) == SSA_NAME
1911 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1912 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
1914 value_range
*vr
, new_vr
;
1917 vr
= get_value_range (lhs
);
1918 extract_range_from_expr (&new_vr
, rhs
);
1920 /* If STMT is inside a loop, we may be able to know something
1921 else about the range of LHS by examining scalar evolution
1923 if (cfg_loops
&& (l
= loop_containing_stmt (stmt
)))
1924 adjust_range_with_scev (&new_vr
, l
, lhs
);
1926 if (update_value_range (vr
, new_vr
.type
, new_vr
.min
, new_vr
.max
))
1930 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1932 fprintf (dump_file
, "Found new range ");
1933 dump_value_range (dump_file
, &new_vr
);
1934 fprintf (dump_file
, " for ");
1935 print_generic_expr (dump_file
, lhs
, 0);
1936 fprintf (dump_file
, "\n\n");
1939 if (new_vr
.type
== VR_VARYING
)
1940 return SSA_PROP_VARYING
;
1942 return SSA_PROP_INTERESTING
;
1945 return SSA_PROP_NOT_INTERESTING
;
1948 /* Every other statements produces no useful ranges. */
1949 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
1950 set_value_range_to_varying (get_value_range (def
));
1952 return SSA_PROP_VARYING
;
1956 /* Given a conditional predicate COND, try to determine if COND yields
1957 true or false based on the value ranges of its operands. */
1960 vrp_evaluate_conditional (tree cond
)
1962 gcc_assert (TREE_CODE (cond
) == SSA_NAME
1963 || TREE_CODE_CLASS (TREE_CODE (cond
)) == tcc_comparison
);
1965 if (TREE_CODE (cond
) == SSA_NAME
)
1967 /* For SSA names, only return a truth value if the range is
1968 known and contains exactly one value. */
1969 value_range
*vr
= SSA_NAME_VALUE_RANGE (cond
);
1970 if (vr
&& vr
->type
== VR_RANGE
&& vr
->min
== vr
->max
)
1975 /* For comparisons, evaluate each operand and compare their
1978 value_range
*vr0
, *vr1
;
1980 op0
= TREE_OPERAND (cond
, 0);
1981 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? get_value_range (op0
) : NULL
;
1983 op1
= TREE_OPERAND (cond
, 1);
1984 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? get_value_range (op1
) : NULL
;
1987 return compare_ranges (TREE_CODE (cond
), vr0
, vr1
);
1988 else if (vr0
&& vr1
== NULL
)
1989 return compare_range_with_value (TREE_CODE (cond
), vr0
, op1
);
1990 else if (vr0
== NULL
&& vr1
)
1991 return compare_range_with_value (opposite_comparison (TREE_CODE (cond
)),
1995 /* Anything else cannot be computed statically. */
2000 /* Visit conditional statement STMT. If we can determine which edge
2001 will be taken out of STMT's basic block, record it in
2002 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
2003 SSA_PROP_VARYING. */
2005 static enum ssa_prop_result
2006 vrp_visit_cond_stmt (tree stmt
, edge
*taken_edge_p
)
2010 *taken_edge_p
= NULL
;
2012 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
2013 add ASSERT_EXPRs for them. */
2014 if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2015 return SSA_PROP_VARYING
;
2017 cond
= COND_EXPR_COND (stmt
);
2019 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2024 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
2025 print_generic_expr (dump_file
, cond
, 0);
2026 fprintf (dump_file
, "\nWith known ranges\n");
2028 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
2030 fprintf (dump_file
, "\t");
2031 print_generic_expr (dump_file
, use
, 0);
2032 fprintf (dump_file
, ": ");
2033 dump_value_range (dump_file
, SSA_NAME_VALUE_RANGE (use
));
2036 fprintf (dump_file
, "\n");
2039 /* Compute the value of the predicate COND by checking the known
2040 ranges of each of its operands. */
2041 val
= vrp_evaluate_conditional (cond
);
2043 *taken_edge_p
= find_taken_edge (bb_for_stmt (stmt
), val
);
2045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2047 fprintf (dump_file
, "\nPredicate evaluates to: ");
2048 if (val
== NULL_TREE
)
2049 fprintf (dump_file
, "DON'T KNOW\n");
2051 print_generic_stmt (dump_file
, val
, 0);
2054 return (*taken_edge_p
) ? SSA_PROP_INTERESTING
: SSA_PROP_VARYING
;
2058 /* Evaluate statement STMT. If the statement produces a useful range,
2059 return SSA_PROP_INTERESTING and record the SSA name with the
2060 interesting range into *OUTPUT_P.
2062 If STMT is a conditional branch and we can determine its truth
2063 value, the taken edge is recorded in *TAKEN_EDGE_P.
2065 If STMT produces a varying value, return SSA_PROP_VARYING. */
2067 static enum ssa_prop_result
2068 vrp_visit_stmt (tree stmt
, edge
*taken_edge_p
, tree
*output_p
)
2074 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2076 fprintf (dump_file
, "\nVisiting statement:\n");
2077 print_generic_stmt (dump_file
, stmt
, dump_flags
);
2078 fprintf (dump_file
, "\n");
2081 ann
= stmt_ann (stmt
);
2082 if (TREE_CODE (stmt
) == MODIFY_EXPR
2083 && ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
2084 return vrp_visit_assignment (stmt
, output_p
);
2085 else if (TREE_CODE (stmt
) == COND_EXPR
|| TREE_CODE (stmt
) == SWITCH_EXPR
)
2086 return vrp_visit_cond_stmt (stmt
, taken_edge_p
);
2088 /* All other statements produce nothing of interest for VRP, so mark
2089 their outputs varying and prevent further simulation. */
2090 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
2091 set_value_range_to_varying (get_value_range (def
));
2093 return SSA_PROP_VARYING
;
2097 /* Meet operation for value ranges. Given two value ranges VR0 and
2098 VR1, store in VR0 the result of meeting VR0 and VR1.
2100 The meeting rules are as follows:
2102 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
2104 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
2105 union of VR0 and VR1. */
2108 vrp_meet (value_range
*vr0
, value_range
*vr1
)
2110 if (vr0
->type
== VR_UNDEFINED
)
2116 if (vr1
->type
== VR_UNDEFINED
)
2118 /* Nothing to do. VR0 already has the resulting range. */
2122 if (vr0
->type
== VR_VARYING
)
2124 /* Nothing to do. VR0 already has the resulting range. */
2128 if (vr1
->type
== VR_VARYING
)
2134 /* If either is a symbolic range, drop to VARYING. */
2135 if (symbolic_range_p (vr0
) || symbolic_range_p (vr1
))
2137 set_value_range_to_varying (vr0
);
2141 if (vr0
->type
== VR_RANGE
&& vr1
->type
== VR_RANGE
)
2143 /* If VR0 and VR1 have a non-empty intersection, compute the
2144 union of both ranges. */
2145 if (value_ranges_intersect_p (vr0
, vr1
))
2152 /* The lower limit of the new range is the minimum of the
2154 if (compare_values (vr0
->min
, vr1
->min
) == 1)
2157 /* The upper limit of the new range is the maximum of the
2159 if (compare_values (vr0
->max
, vr1
->max
) == -1)
2162 set_value_range (vr0
, vr0
->type
, min
, max
);
2166 /* The two ranges don't intersect, set the result to VR_VARYING. */
2167 set_value_range_to_varying (vr0
);
2170 else if (vr0
->type
== VR_ANTI_RANGE
&& vr1
->type
== VR_ANTI_RANGE
)
2172 /* Two anti-ranges meet only if they are both identical. */
2173 if (compare_values (vr0
->min
, vr1
->min
) == 0
2174 && compare_values (vr0
->max
, vr1
->max
) == 0
2175 && compare_values (vr0
->min
, vr0
->max
) == 0)
2176 /* Nothing to do. */ ;
2178 set_value_range_to_varying (vr0
);
2180 else if (vr0
->type
== VR_ANTI_RANGE
|| vr1
->type
== VR_ANTI_RANGE
)
2182 /* A range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] meet
2183 only if the ranges have an empty intersection. The result of
2184 the meet operation is the anti-range. */
2185 if (!value_ranges_intersect_p (vr0
, vr1
))
2187 if (vr1
->type
== VR_ANTI_RANGE
)
2191 set_value_range_to_varying (vr0
);
2198 /* Visit all arguments for PHI node PHI that flow through executable
2199 edges. If a valid value range can be derived from all the incoming
2200 value ranges, set a new range for the LHS of PHI. */
2202 static enum ssa_prop_result
2203 vrp_visit_phi_node (tree phi
)
2206 tree lhs
= PHI_RESULT (phi
);
2207 value_range
*lhs_vr
= get_value_range (lhs
);
2208 value_range vr_result
= *lhs_vr
;
2210 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2212 fprintf (dump_file
, "\nVisiting PHI node: ");
2213 print_generic_expr (dump_file
, phi
, dump_flags
);
2216 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
2218 edge e
= PHI_ARG_EDGE (phi
, i
);
2220 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2223 "\n Argument #%d (%d -> %d %sexecutable)\n",
2224 i
, e
->src
->index
, e
->dest
->index
,
2225 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
2228 if (e
->flags
& EDGE_EXECUTABLE
)
2230 tree arg
= PHI_ARG_DEF (phi
, i
);
2233 if (TREE_CODE (arg
) == SSA_NAME
)
2234 vr_arg
= *(get_value_range (arg
));
2237 vr_arg
.type
= VR_RANGE
;
2242 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2244 fprintf (dump_file
, "\t");
2245 print_generic_expr (dump_file
, arg
, dump_flags
);
2246 fprintf (dump_file
, "\n\tValue: ");
2247 dump_value_range (dump_file
, &vr_arg
);
2248 fprintf (dump_file
, "\n");
2251 vrp_meet (&vr_result
, &vr_arg
);
2253 if (vr_result
.type
== VR_VARYING
)
2258 if (vr_result
.type
== VR_VARYING
)
2260 set_value_range_to_varying (lhs_vr
);
2261 return SSA_PROP_VARYING
;
2264 /* To prevent infinite iterations in the algorithm, derive ranges
2265 when the new value is slightly bigger or smaller than the
2267 if (lhs_vr
->type
== VR_RANGE
)
2269 if (!POINTER_TYPE_P (TREE_TYPE (lhs
)))
2271 int cmp_min
= compare_values (lhs_vr
->min
, vr_result
.min
);
2272 int cmp_max
= compare_values (lhs_vr
->max
, vr_result
.max
);
2274 /* If the new minimum is smaller or larger than the previous
2275 one, go all the way to -INF. In the first case, to avoid
2276 iterating millions of times to reach -INF, and in the
2277 other case to avoid infinite bouncing between different
2279 if (cmp_min
> 0 || cmp_min
< 0)
2280 vr_result
.min
= TYPE_MIN_VALUE (TREE_TYPE (vr_result
.min
));
2282 /* Similarly, if the new maximum is smaller or larger than
2283 the previous one, go all the way to +INF. */
2284 if (cmp_max
< 0 || cmp_max
> 0)
2285 vr_result
.max
= TYPE_MAX_VALUE (TREE_TYPE (vr_result
.max
));
2287 /* If we ended up with a (-INF, +INF) range, set it to
2289 if (vr_result
.min
== TYPE_MIN_VALUE (TREE_TYPE (vr_result
.min
))
2290 && vr_result
.max
== TYPE_MAX_VALUE (TREE_TYPE (vr_result
.max
)))
2292 set_value_range_to_varying (lhs_vr
);
2293 return SSA_PROP_VARYING
;
2298 /* If the new range is different than the previous value, keep
2300 if (update_value_range (lhs_vr
, vr_result
.type
, vr_result
.min
, vr_result
.max
))
2301 return SSA_PROP_INTERESTING
;
2303 /* Nothing changed, don't add outgoing edges. */
2304 return SSA_PROP_NOT_INTERESTING
;
2308 /* Traverse all the blocks folding conditionals with known ranges. */
2314 int num_pred_folded
= 0;
2318 fprintf (dump_file
, "\nValue ranges after VRP:\n\n");
2319 dump_all_value_ranges (dump_file
);
2320 fprintf (dump_file
, "\n");
2325 tree last
= last_stmt (bb
);
2326 if (last
&& TREE_CODE (last
) == COND_EXPR
)
2328 tree val
= vrp_evaluate_conditional (COND_EXPR_COND (last
));
2333 fprintf (dump_file
, "Folding predicate ");
2334 print_generic_expr (dump_file
, COND_EXPR_COND (last
), 0);
2335 fprintf (dump_file
, " to ");
2336 print_generic_expr (dump_file
, val
, 0);
2337 fprintf (dump_file
, "\n");
2341 COND_EXPR_COND (last
) = val
;
2347 if (dump_file
&& (dump_flags
& TDF_STATS
))
2348 fprintf (dump_file
, "\nNumber of predicates folded: %d\n\n",
2353 /* Main entry point to VRP (Value Range Propagation). This pass is
2354 loosely based on J. R. C. Patterson, ``Accurate Static Branch
2355 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
2356 Programming Language Design and Implementation, pp. 67-78, 1995.
2357 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
2359 This is essentially an SSA-CCP pass modified to deal with ranges
2360 instead of constants.
2362 TODO, the main difference between this pass and Patterson's is that
2363 we do not propagate edge probabilities. We only compute whether
2364 edges can be taken or not. That is, instead of having a spectrum
2365 of jump probabilities between 0 and 1, we only deal with 0, 1 and
2366 DON'T KNOW. In the future, it may be worthwhile to propagate
2367 probabilities to aid branch prediction. */
2372 insert_range_assertions ();
2374 cfg_loops
= loop_optimizer_init (NULL
);
2376 scev_initialize (cfg_loops
);
2378 if (vrp_initialize ())
2380 ssa_propagate (vrp_visit_stmt
, vrp_visit_phi_node
);
2387 loop_optimizer_finalize (cfg_loops
, NULL
);
2388 current_loops
= NULL
;
2391 remove_range_assertions ();
2397 return flag_tree_vrp
!= 0;
2400 struct tree_opt_pass pass_vrp
=
2403 gate_vrp
, /* gate */
2404 execute_vrp
, /* execute */
2407 0, /* static_pass_number */
2408 TV_TREE_VRP
, /* tv_id */
2409 PROP_ssa
| PROP_alias
, /* properties_required */
2410 0, /* properties_provided */
2411 0, /* properties_destroyed */
2412 0, /* todo_flags_start */
2417 | TODO_update_ssa
, /* todo_flags_finish */