Mercurial > hg > CbC > CbC_gcc
comparison gcc/tree-ssa-loop-niter.c @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 12 Feb 2010 23:39:51 +0900 |
parents | 58ad6c70ea60 |
children | b7f97abdc517 |
comparison
equal
deleted
inserted
replaced
52:c156f1bd5cd9 | 55:77e2b8dfacca |
---|---|
1 /* Functions to determine/estimate number of iterations of a loop. | 1 /* Functions to determine/estimate number of iterations of a loop. |
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, | 2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, |
3 Inc. | 3 Inc. |
4 | 4 |
5 This file is part of GCC. | 5 This file is part of GCC. |
6 | 6 |
7 GCC is free software; you can redistribute it and/or modify it | 7 GCC is free software; you can redistribute it and/or modify it |
8 under the terms of the GNU General Public License as published by the | 8 under the terms of the GNU General Public License as published by the |
9 Free Software Foundation; either version 3, or (at your option) any | 9 Free Software Foundation; either version 3, or (at your option) any |
10 later version. | 10 later version. |
11 | 11 |
12 GCC is distributed in the hope that it will be useful, but WITHOUT | 12 GCC is distributed in the hope that it will be useful, but WITHOUT |
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
15 for more details. | 15 for more details. |
16 | 16 |
17 You should have received a copy of the GNU General Public License | 17 You should have received a copy of the GNU General Public License |
18 along with GCC; see the file COPYING3. If not see | 18 along with GCC; see the file COPYING3. If not see |
19 <http://www.gnu.org/licenses/>. */ | 19 <http://www.gnu.org/licenses/>. */ |
20 | 20 |
21 #include "config.h" | 21 #include "config.h" |
92 if (TREE_CODE (op1) != INTEGER_CST) | 92 if (TREE_CODE (op1) != INTEGER_CST) |
93 break; | 93 break; |
94 | 94 |
95 *var = op0; | 95 *var = op0; |
96 /* Always sign extend the offset. */ | 96 /* Always sign extend the offset. */ |
97 off = double_int_sext (tree_to_double_int (op1), | 97 off = tree_to_double_int (op1); |
98 TYPE_PRECISION (type)); | 98 if (negate) |
99 off = double_int_neg (off); | |
100 off = double_int_sext (off, TYPE_PRECISION (type)); | |
99 mpz_set_double_int (offset, off, false); | 101 mpz_set_double_int (offset, off, false); |
100 break; | 102 break; |
101 | 103 |
102 case INTEGER_CST: | 104 case INTEGER_CST: |
103 *var = build_int_cst_type (type, 0); | 105 *var = build_int_cst_type (type, 0); |
253 } | 255 } |
254 | 256 |
255 return; | 257 return; |
256 default: | 258 default: |
257 return; | 259 return; |
258 } | 260 } |
259 | 261 |
260 mpz_init (offc0); | 262 mpz_init (offc0); |
261 mpz_init (offc1); | 263 mpz_init (offc1); |
262 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0); | 264 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0); |
263 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1); | 265 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1); |
295 | 297 |
296 The overflows and underflows may complicate things a bit; each | 298 The overflows and underflows may complicate things a bit; each |
297 overflow decreases the appropriate offset by M, and underflow | 299 overflow decreases the appropriate offset by M, and underflow |
298 increases it by M. The above inequality would not necessarily be | 300 increases it by M. The above inequality would not necessarily be |
299 true if | 301 true if |
300 | 302 |
301 -- VARX + OFFX underflows and VARX + OFFC0 does not, or | 303 -- VARX + OFFX underflows and VARX + OFFC0 does not, or |
302 VARX + OFFC0 overflows, but VARX + OFFX does not. | 304 VARX + OFFC0 overflows, but VARX + OFFX does not. |
303 This may only happen if OFFX < OFFC0. | 305 This may only happen if OFFX < OFFC0. |
304 -- VARY + OFFY overflows and VARY + OFFC1 does not, or | 306 -- VARY + OFFY overflows and VARY + OFFC1 does not, or |
305 VARY + OFFC1 underflows and VARY + OFFY does not. | 307 VARY + OFFC1 underflows and VARY + OFFY does not. |
350 } | 352 } |
351 | 353 |
352 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS. | 354 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS. |
353 The subtraction is considered to be performed in arbitrary precision, | 355 The subtraction is considered to be performed in arbitrary precision, |
354 without overflows. | 356 without overflows. |
355 | 357 |
356 We do not attempt to be too clever regarding the value ranges of X and | 358 We do not attempt to be too clever regarding the value ranges of X and |
357 Y; most of the time, they are just integers or ssa names offsetted by | 359 Y; most of the time, they are just integers or ssa names offsetted by |
358 integer. However, we try to use the information contained in the | 360 integer. However, we try to use the information contained in the |
359 comparisons before the loop (usually created by loop header copying). */ | 361 comparisons before the loop (usually created by loop header copying). */ |
360 | 362 |
648 assumption, build_int_cst (niter_type, 0)); | 650 assumption, build_int_cst (niter_type, 0)); |
649 if (!integer_nonzerop (assumption)) | 651 if (!integer_nonzerop (assumption)) |
650 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, | 652 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, |
651 niter->assumptions, assumption); | 653 niter->assumptions, assumption); |
652 } | 654 } |
653 | 655 |
654 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d); | 656 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d); |
655 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound)); | 657 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound)); |
656 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound); | 658 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound); |
657 return true; | 659 return true; |
658 } | 660 } |
845 if (integer_zerop (assumption)) | 847 if (integer_zerop (assumption)) |
846 return false; | 848 return false; |
847 if (!integer_nonzerop (assumption)) | 849 if (!integer_nonzerop (assumption)) |
848 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, | 850 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, |
849 niter->assumptions, assumption); | 851 niter->assumptions, assumption); |
850 | 852 |
851 iv0->no_overflow = true; | 853 iv0->no_overflow = true; |
852 iv1->no_overflow = true; | 854 iv1->no_overflow = true; |
853 return true; | 855 return true; |
854 } | 856 } |
855 | 857 |
867 double_int dstep; | 869 double_int dstep; |
868 mpz_t mstep, max; | 870 mpz_t mstep, max; |
869 | 871 |
870 /* We are going to compute the number of iterations as | 872 /* We are going to compute the number of iterations as |
871 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned | 873 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned |
872 variant of TYPE. This formula only works if | 874 variant of TYPE. This formula only works if |
873 | 875 |
874 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1 | 876 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1 |
875 | 877 |
876 (where MAX is the maximum value of the unsigned variant of TYPE, and | 878 (where MAX is the maximum value of the unsigned variant of TYPE, and |
877 the computations in this formula are performed in full precision | 879 the computations in this formula are performed in full precision |
878 (without overflows). | 880 (without overflows). |
879 | 881 |
880 Usually, for loops with exit condition iv0->base + step * i < iv1->base, | 882 Usually, for loops with exit condition iv0->base + step * i < iv1->base, |
881 we have a condition of form iv0->base - step < iv1->base before the loop, | 883 we have a condition of form iv0->base - step < iv1->base before the loop, |
882 and for loops iv0->base < iv1->base - step * i the condition | 884 and for loops iv0->base < iv1->base - step * i the condition |
883 iv0->base < iv1->base + step, due to loop header copying, which enable us | 885 iv0->base < iv1->base + step, due to loop header copying, which enable us |
884 to prove the lower bound. | 886 to prove the lower bound. |
885 | 887 |
886 The upper bound is more complicated. Unless the expressions for initial | 888 The upper bound is more complicated. Unless the expressions for initial |
887 and final value themselves contain enough information, we usually cannot | 889 and final value themselves contain enough information, we usually cannot |
888 derive it from the context. */ | 890 derive it from the context. */ |
889 | 891 |
890 /* First check whether the answer does not follow from the bounds we gathered | 892 /* First check whether the answer does not follow from the bounds we gathered |
918 mpz_clear (mstep); | 920 mpz_clear (mstep); |
919 mpz_clear (max); | 921 mpz_clear (max); |
920 | 922 |
921 if (rolls_p && no_overflow_p) | 923 if (rolls_p && no_overflow_p) |
922 return; | 924 return; |
923 | 925 |
924 type1 = type; | 926 type1 = type; |
925 if (POINTER_TYPE_P (type)) | 927 if (POINTER_TYPE_P (type)) |
926 type1 = sizetype; | 928 type1 = sizetype; |
927 | 929 |
928 /* Now the hard part; we must formulate the assumption(s) as expressions, and | 930 /* Now the hard part; we must formulate the assumption(s) as expressions, and |
943 assumption = fold_build2 (GE_EXPR, boolean_type_node, | 945 assumption = fold_build2 (GE_EXPR, boolean_type_node, |
944 iv0->base, bound); | 946 iv0->base, bound); |
945 } | 947 } |
946 | 948 |
947 /* And then we can compute iv0->base - diff, and compare it with | 949 /* And then we can compute iv0->base - diff, and compare it with |
948 iv1->base. */ | 950 iv1->base. */ |
949 mbzl = fold_build2 (MINUS_EXPR, type1, | 951 mbzl = fold_build2 (MINUS_EXPR, type1, |
950 fold_convert (type1, iv0->base), diff); | 952 fold_convert (type1, iv0->base), diff); |
951 mbzr = fold_convert (type1, iv1->base); | 953 mbzr = fold_convert (type1, iv1->base); |
952 } | 954 } |
953 else | 955 else |
954 { | 956 { |
1018 /* for (i = iv0->base; i < iv1->base; i++) | 1020 /* for (i = iv0->base; i < iv1->base; i++) |
1019 | 1021 |
1020 or | 1022 or |
1021 | 1023 |
1022 for (i = iv1->base; i > iv0->base; i--). | 1024 for (i = iv1->base; i > iv0->base; i--). |
1023 | 1025 |
1024 In both cases # of iterations is iv1->base - iv0->base, assuming that | 1026 In both cases # of iterations is iv1->base - iv0->base, assuming that |
1025 iv1->base >= iv0->base. | 1027 iv1->base >= iv0->base. |
1026 | 1028 |
1027 First try to derive a lower bound on the value of | 1029 First try to derive a lower bound on the value of |
1028 iv1->base - iv0->base, computed in full precision. If the difference | 1030 iv1->base - iv0->base, computed in full precision. If the difference |
1106 | 1108 |
1107 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff | 1109 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff |
1108 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest | 1110 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest |
1109 value of the type. This we must know anyway, since if it is | 1111 value of the type. This we must know anyway, since if it is |
1110 equal to this value, the loop rolls forever. We do not check | 1112 equal to this value, the loop rolls forever. We do not check |
1111 this condition for pointer type ivs, as the code cannot rely on | 1113 this condition for pointer type ivs, as the code cannot rely on |
1112 the object to that the pointer points being placed at the end of | 1114 the object to that the pointer points being placed at the end of |
1113 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is | 1115 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is |
1114 not defined for pointers). */ | 1116 not defined for pointers). */ |
1115 | 1117 |
1116 if (!exit_must_be_taken && !POINTER_TYPE_P (type)) | 1118 if (!exit_must_be_taken && !POINTER_TYPE_P (type)) |
1181 | 1183 |
1182 ONLY_EXIT is true if we are sure this is the only way the loop could be | 1184 ONLY_EXIT is true if we are sure this is the only way the loop could be |
1183 exited (including possibly non-returning function calls, exceptions, etc.) | 1185 exited (including possibly non-returning function calls, exceptions, etc.) |
1184 -- in this case we can use the information whether the control induction | 1186 -- in this case we can use the information whether the control induction |
1185 variables can overflow or not in a more efficient way. | 1187 variables can overflow or not in a more efficient way. |
1186 | 1188 |
1187 The results (number of iterations and assumptions as described in | 1189 The results (number of iterations and assumptions as described in |
1188 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER. | 1190 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER. |
1189 Returns false if it fails to determine number of iterations, true if it | 1191 Returns false if it fails to determine number of iterations, true if it |
1190 was determined (possibly with some assumptions). */ | 1192 was determined (possibly with some assumptions). */ |
1191 | 1193 |
1278 { | 1280 { |
1279 niter->niter = build_int_cst (unsigned_type_for (type), 0); | 1281 niter->niter = build_int_cst (unsigned_type_for (type), 0); |
1280 niter->max = double_int_zero; | 1282 niter->max = double_int_zero; |
1281 return true; | 1283 return true; |
1282 } | 1284 } |
1283 | 1285 |
1284 /* OK, now we know we have a senseful loop. Handle several cases, depending | 1286 /* OK, now we know we have a senseful loop. Handle several cases, depending |
1285 on what comparison operator is used. */ | 1287 on what comparison operator is used. */ |
1286 bound_difference (loop, iv1->base, iv0->base, &bnds); | 1288 bound_difference (loop, iv1->base, iv0->base, &bnds); |
1287 | 1289 |
1288 if (dump_file && (dump_flags & TDF_DETAILS)) | 1290 if (dump_file && (dump_flags & TDF_DETAILS)) |
1799 break; | 1801 break; |
1800 | 1802 |
1801 default: | 1803 default: |
1802 return false; | 1804 return false; |
1803 } | 1805 } |
1804 | 1806 |
1805 op0 = gimple_cond_lhs (stmt); | 1807 op0 = gimple_cond_lhs (stmt); |
1806 op1 = gimple_cond_rhs (stmt); | 1808 op1 = gimple_cond_rhs (stmt); |
1807 type = TREE_TYPE (op0); | 1809 type = TREE_TYPE (op0); |
1808 | 1810 |
1809 if (TREE_CODE (type) != INTEGER_TYPE | 1811 if (TREE_CODE (type) != INTEGER_TYPE |
1810 && !POINTER_TYPE_P (type)) | 1812 && !POINTER_TYPE_P (type)) |
1811 return false; | 1813 return false; |
1812 | 1814 |
1813 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false)) | 1815 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false)) |
1814 return false; | 1816 return false; |
1815 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false)) | 1817 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false)) |
1816 return false; | 1818 return false; |
1817 | 1819 |
1860 | 1862 |
1861 if (warn) | 1863 if (warn) |
1862 { | 1864 { |
1863 const char *wording; | 1865 const char *wording; |
1864 location_t loc = gimple_location (stmt); | 1866 location_t loc = gimple_location (stmt); |
1865 | 1867 |
1866 /* We can provide a more specific warning if one of the operator is | 1868 /* We can provide a more specific warning if one of the operator is |
1867 constant and the other advances by +1 or -1. */ | 1869 constant and the other advances by +1 or -1. */ |
1868 if (!integer_zerop (iv1.step) | 1870 if (!integer_zerop (iv1.step) |
1869 ? (integer_zerop (iv0.step) | 1871 ? (integer_zerop (iv0.step) |
1870 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step))) | 1872 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step))) |
1872 wording = | 1874 wording = |
1873 flag_unsafe_loop_optimizations | 1875 flag_unsafe_loop_optimizations |
1874 ? N_("assuming that the loop is not infinite") | 1876 ? N_("assuming that the loop is not infinite") |
1875 : N_("cannot optimize possibly infinite loops"); | 1877 : N_("cannot optimize possibly infinite loops"); |
1876 else | 1878 else |
1877 wording = | 1879 wording = |
1878 flag_unsafe_loop_optimizations | 1880 flag_unsafe_loop_optimizations |
1879 ? N_("assuming that the loop counter does not overflow") | 1881 ? N_("assuming that the loop counter does not overflow") |
1880 : N_("cannot optimize loop, the loop counter may overflow"); | 1882 : N_("cannot optimize loop, the loop counter may overflow"); |
1881 | 1883 |
1882 if (LOCATION_LINE (loc) > 0) | 1884 warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location, |
1883 warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording)); | 1885 OPT_Wunsafe_loop_optimizations, "%s", gettext (wording)); |
1884 else | |
1885 warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording)); | |
1886 } | 1886 } |
1887 | 1887 |
1888 return flag_unsafe_loop_optimizations; | 1888 return flag_unsafe_loop_optimizations; |
1889 } | 1889 } |
1890 | 1890 |
1954 VEC_free (edge, heap, exits); | 1954 VEC_free (edge, heap, exits); |
1955 | 1955 |
1956 return niter ? niter : chrec_dont_know; | 1956 return niter ? niter : chrec_dont_know; |
1957 } | 1957 } |
1958 | 1958 |
1959 /* Return true if loop is known to have bounded number of iterations. */ | |
1960 | |
1961 bool | |
1962 finite_loop_p (struct loop *loop) | |
1963 { | |
1964 unsigned i; | |
1965 VEC (edge, heap) *exits; | |
1966 edge ex; | |
1967 struct tree_niter_desc desc; | |
1968 bool finite = false; | |
1969 | |
1970 if (flag_unsafe_loop_optimizations) | |
1971 return true; | |
1972 if ((TREE_READONLY (current_function_decl) | |
1973 || DECL_PURE_P (current_function_decl)) | |
1974 && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)) | |
1975 { | |
1976 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1977 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n", | |
1978 loop->num); | |
1979 return true; | |
1980 } | |
1981 | |
1982 exits = get_loop_exit_edges (loop); | |
1983 for (i = 0; VEC_iterate (edge, exits, i, ex); i++) | |
1984 { | |
1985 if (!just_once_each_iteration_p (loop, ex->src)) | |
1986 continue; | |
1987 | |
1988 if (number_of_iterations_exit (loop, ex, &desc, false)) | |
1989 { | |
1990 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1991 { | |
1992 fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num); | |
1993 print_generic_expr (dump_file, desc.niter, TDF_SLIM); | |
1994 fprintf (dump_file, " times\n"); | |
1995 } | |
1996 finite = true; | |
1997 break; | |
1998 } | |
1999 } | |
2000 VEC_free (edge, heap, exits); | |
2001 return finite; | |
2002 } | |
2003 | |
1959 /* | 2004 /* |
1960 | 2005 |
1961 Analysis of a number of iterations of a loop by a brute-force evaluation. | 2006 Analysis of a number of iterations of a loop by a brute-force evaluation. |
1962 | 2007 |
1963 */ | 2008 */ |
1980 enum tree_code code; | 2025 enum tree_code code; |
1981 | 2026 |
1982 if (!bb | 2027 if (!bb |
1983 || !flow_bb_inside_loop_p (loop, bb)) | 2028 || !flow_bb_inside_loop_p (loop, bb)) |
1984 return NULL; | 2029 return NULL; |
1985 | 2030 |
1986 if (gimple_code (stmt) == GIMPLE_PHI) | 2031 if (gimple_code (stmt) == GIMPLE_PHI) |
1987 { | 2032 { |
1988 if (bb == loop->header) | 2033 if (bb == loop->header) |
1989 return stmt; | 2034 return stmt; |
1990 | 2035 |
1994 if (gimple_code (stmt) != GIMPLE_ASSIGN) | 2039 if (gimple_code (stmt) != GIMPLE_ASSIGN) |
1995 return NULL; | 2040 return NULL; |
1996 | 2041 |
1997 code = gimple_assign_rhs_code (stmt); | 2042 code = gimple_assign_rhs_code (stmt); |
1998 if (gimple_references_memory_p (stmt) | 2043 if (gimple_references_memory_p (stmt) |
1999 /* Before alias information is computed, operand scanning marks | |
2000 statements that write memory volatile. However, the statements | |
2001 that only read memory are not marked, thus gimple_references_memory_p | |
2002 returns false for them. */ | |
2003 || TREE_CODE_CLASS (code) == tcc_reference | 2044 || TREE_CODE_CLASS (code) == tcc_reference |
2004 || TREE_CODE_CLASS (code) == tcc_declaration | 2045 || (code == ADDR_EXPR |
2005 || SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P) | 2046 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))) |
2006 return NULL; | 2047 return NULL; |
2007 | 2048 |
2008 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); | 2049 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); |
2009 if (use == NULL_USE_OPERAND_P) | 2050 if (use == NULL_TREE) |
2010 return NULL; | 2051 return NULL; |
2011 | 2052 |
2012 return chain_of_csts_start (loop, use); | 2053 return chain_of_csts_start (loop, use); |
2013 } | 2054 } |
2014 | 2055 |
2017 | 2058 |
2018 * the derivation of X consists only from operations with constants | 2059 * the derivation of X consists only from operations with constants |
2019 * the initial value of the phi node is constant | 2060 * the initial value of the phi node is constant |
2020 * the value of the phi node in the next iteration can be derived from the | 2061 * the value of the phi node in the next iteration can be derived from the |
2021 value in the current iteration by a chain of operations with constants. | 2062 value in the current iteration by a chain of operations with constants. |
2022 | 2063 |
2023 If such phi node exists, it is returned, otherwise NULL is returned. */ | 2064 If such phi node exists, it is returned, otherwise NULL is returned. */ |
2024 | 2065 |
2025 static gimple | 2066 static gimple |
2026 get_base_for (struct loop *loop, tree x) | 2067 get_base_for (struct loop *loop, tree x) |
2027 { | 2068 { |
2048 return NULL; | 2089 return NULL; |
2049 | 2090 |
2050 return phi; | 2091 return phi; |
2051 } | 2092 } |
2052 | 2093 |
2053 /* Given an expression X, then | 2094 /* Given an expression X, then |
2054 | 2095 |
2055 * if X is NULL_TREE, we return the constant BASE. | 2096 * if X is NULL_TREE, we return the constant BASE. |
2056 * otherwise X is a SSA name, whose value in the considered loop is derived | 2097 * otherwise X is a SSA name, whose value in the considered loop is derived |
2057 by a chain of operations with constant from a result of a phi node in | 2098 by a chain of operations with constant from a result of a phi node in |
2058 the header of the loop. Then we return value of X when the value of the | 2099 the header of the loop. Then we return value of X when the value of the |
2059 result of this phi node is given by the constant BASE. */ | 2100 result of this phi node is given by the constant BASE. */ |
2211 VEC (edge, heap) *exits = get_loop_exit_edges (loop); | 2252 VEC (edge, heap) *exits = get_loop_exit_edges (loop); |
2212 edge ex; | 2253 edge ex; |
2213 tree niter = NULL_TREE, aniter; | 2254 tree niter = NULL_TREE, aniter; |
2214 | 2255 |
2215 *exit = NULL; | 2256 *exit = NULL; |
2257 | |
2258 /* Loops with multiple exits are expensive to handle and less important. */ | |
2259 if (!flag_expensive_optimizations | |
2260 && VEC_length (edge, exits) > 1) | |
2261 return chrec_dont_know; | |
2262 | |
2216 for (i = 0; VEC_iterate (edge, exits, i, ex); i++) | 2263 for (i = 0; VEC_iterate (edge, exits, i, ex); i++) |
2217 { | 2264 { |
2218 if (!just_once_each_iteration_p (loop, ex->src)) | 2265 if (!just_once_each_iteration_p (loop, ex->src)) |
2219 continue; | 2266 continue; |
2220 | 2267 |
2258 } | 2305 } |
2259 | 2306 |
2260 /* Returns a constant upper bound on the value of expression VAL. VAL | 2307 /* Returns a constant upper bound on the value of expression VAL. VAL |
2261 is considered to be unsigned. If its type is signed, its value must | 2308 is considered to be unsigned. If its type is signed, its value must |
2262 be nonnegative. */ | 2309 be nonnegative. */ |
2263 | 2310 |
2264 static double_int | 2311 static double_int |
2265 derive_constant_upper_bound (tree val) | 2312 derive_constant_upper_bound (tree val) |
2266 { | 2313 { |
2267 enum tree_code code; | 2314 enum tree_code code; |
2268 tree op0, op1; | 2315 tree op0, op1; |
2272 } | 2319 } |
2273 | 2320 |
2274 /* Returns a constant upper bound on the value of expression OP0 CODE OP1, | 2321 /* Returns a constant upper bound on the value of expression OP0 CODE OP1, |
2275 whose type is TYPE. The expression is considered to be unsigned. If | 2322 whose type is TYPE. The expression is considered to be unsigned. If |
2276 its type is signed, its value must be nonnegative. */ | 2323 its type is signed, its value must be nonnegative. */ |
2277 | 2324 |
2278 static double_int | 2325 static double_int |
2279 derive_constant_upper_bound_ops (tree type, tree op0, | 2326 derive_constant_upper_bound_ops (tree type, tree op0, |
2280 enum tree_code code, tree op1) | 2327 enum tree_code code, tree op1) |
2281 { | 2328 { |
2282 tree subtype, maxt; | 2329 tree subtype, maxt; |
2404 if (gimple_code (stmt) != GIMPLE_ASSIGN | 2451 if (gimple_code (stmt) != GIMPLE_ASSIGN |
2405 || gimple_assign_lhs (stmt) != op0) | 2452 || gimple_assign_lhs (stmt) != op0) |
2406 return max; | 2453 return max; |
2407 return derive_constant_upper_bound_assign (stmt); | 2454 return derive_constant_upper_bound_assign (stmt); |
2408 | 2455 |
2409 default: | 2456 default: |
2410 return max; | 2457 return max; |
2411 } | 2458 } |
2412 } | 2459 } |
2413 | 2460 |
2414 /* Records that every statement in LOOP is executed I_BOUND times. | 2461 /* Records that every statement in LOOP is executed I_BOUND times. |
2565 | 2612 |
2566 /* Returns true if REF is a reference to an array at the end of a dynamically | 2613 /* Returns true if REF is a reference to an array at the end of a dynamically |
2567 allocated structure. If this is the case, the array may be allocated larger | 2614 allocated structure. If this is the case, the array may be allocated larger |
2568 than its upper bound implies. */ | 2615 than its upper bound implies. */ |
2569 | 2616 |
2570 static bool | 2617 bool |
2571 array_at_struct_end_p (tree ref) | 2618 array_at_struct_end_p (tree ref) |
2572 { | 2619 { |
2573 tree base = get_base_address (ref); | 2620 tree base = get_base_address (ref); |
2574 tree parent, field; | 2621 tree parent, field; |
2575 | 2622 |
2576 /* Unless the reference is through a pointer, the size of the array matches | 2623 /* Unless the reference is through a pointer, the size of the array matches |
2577 its declaration. */ | 2624 its declaration. */ |
2578 if (!base || !INDIRECT_REF_P (base)) | 2625 if (!base || !INDIRECT_REF_P (base)) |
2579 return false; | 2626 return false; |
2580 | 2627 |
2581 for (;handled_component_p (ref); ref = parent) | 2628 for (;handled_component_p (ref); ref = parent) |
2582 { | 2629 { |
2583 parent = TREE_OPERAND (ref, 0); | 2630 parent = TREE_OPERAND (ref, 0); |
2584 | 2631 |
2585 if (TREE_CODE (ref) == COMPONENT_REF) | 2632 if (TREE_CODE (ref) == COMPONENT_REF) |
2650 || chrec_contains_symbols_defined_in_loop (init, loop->num)) | 2697 || chrec_contains_symbols_defined_in_loop (init, loop->num)) |
2651 return true; | 2698 return true; |
2652 | 2699 |
2653 low = array_ref_low_bound (base); | 2700 low = array_ref_low_bound (base); |
2654 high = array_ref_up_bound (base); | 2701 high = array_ref_up_bound (base); |
2655 | 2702 |
2656 /* The case of nonconstant bounds could be handled, but it would be | 2703 /* The case of nonconstant bounds could be handled, but it would be |
2657 complicated. */ | 2704 complicated. */ |
2658 if (TREE_CODE (low) != INTEGER_CST | 2705 if (TREE_CODE (low) != INTEGER_CST |
2659 || !high | 2706 || !high |
2660 || TREE_CODE (high) != INTEGER_CST) | 2707 || TREE_CODE (high) != INTEGER_CST) |
2684 | 2731 |
2685 if (sign) | 2732 if (sign) |
2686 next = fold_binary (PLUS_EXPR, type, low, step); | 2733 next = fold_binary (PLUS_EXPR, type, low, step); |
2687 else | 2734 else |
2688 next = fold_binary (PLUS_EXPR, type, high, step); | 2735 next = fold_binary (PLUS_EXPR, type, high, step); |
2689 | 2736 |
2690 if (tree_int_cst_compare (low, next) <= 0 | 2737 if (tree_int_cst_compare (low, next) <= 0 |
2691 && tree_int_cst_compare (next, high) <= 0) | 2738 && tree_int_cst_compare (next, high) <= 0) |
2692 return true; | 2739 return true; |
2693 | 2740 |
2694 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper); | 2741 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper); |
2804 unsigned i; | 2851 unsigned i; |
2805 basic_block *bbs; | 2852 basic_block *bbs; |
2806 gimple_stmt_iterator bsi; | 2853 gimple_stmt_iterator bsi; |
2807 basic_block bb; | 2854 basic_block bb; |
2808 bool reliable; | 2855 bool reliable; |
2809 | 2856 |
2810 bbs = get_loop_body (loop); | 2857 bbs = get_loop_body (loop); |
2811 | 2858 |
2812 for (i = 0; i < loop->num_nodes; i++) | 2859 for (i = 0; i < loop->num_nodes; i++) |
2813 { | 2860 { |
2814 bb = bbs[i]; | 2861 bb = bbs[i]; |
2884 record_estimate (loop, niter, niter_desc.max, | 2931 record_estimate (loop, niter, niter_desc.max, |
2885 last_stmt (ex->src), | 2932 last_stmt (ex->src), |
2886 true, true, true); | 2933 true, true, true); |
2887 } | 2934 } |
2888 VEC_free (edge, heap, exits); | 2935 VEC_free (edge, heap, exits); |
2889 | 2936 |
2890 infer_loop_bounds_from_undefined (loop); | 2937 infer_loop_bounds_from_undefined (loop); |
2891 | 2938 |
2892 /* If we have a measured profile, use it to estimate the number of | 2939 /* If we have a measured profile, use it to estimate the number of |
2893 iterations. */ | 2940 iterations. */ |
2894 if (loop->header->count != 0) | 2941 if (loop->header->count != 0) |
2964 NITER_BOUND. If STMT is NULL, we must prove this bound for all | 3011 NITER_BOUND. If STMT is NULL, we must prove this bound for all |
2965 statements in the loop. */ | 3012 statements in the loop. */ |
2966 | 3013 |
2967 static bool | 3014 static bool |
2968 n_of_executions_at_most (gimple stmt, | 3015 n_of_executions_at_most (gimple stmt, |
2969 struct nb_iter_bound *niter_bound, | 3016 struct nb_iter_bound *niter_bound, |
2970 tree niter) | 3017 tree niter) |
2971 { | 3018 { |
2972 double_int bound = niter_bound->bound; | 3019 double_int bound = niter_bound->bound; |
2973 tree nit_type = TREE_TYPE (niter), e; | 3020 tree nit_type = TREE_TYPE (niter), e; |
2974 enum tree_code cmp; | 3021 enum tree_code cmp; |
2980 if (!double_int_fits_to_tree_p (nit_type, bound)) | 3027 if (!double_int_fits_to_tree_p (nit_type, bound)) |
2981 return false; | 3028 return false; |
2982 | 3029 |
2983 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 | 3030 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 |
2984 times. This means that: | 3031 times. This means that: |
2985 | 3032 |
2986 -- if NITER_BOUND->is_exit is true, then everything before | 3033 -- if NITER_BOUND->is_exit is true, then everything before |
2987 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 | 3034 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 |
2988 times, and everything after it at most NITER_BOUND->bound times. | 3035 times, and everything after it at most NITER_BOUND->bound times. |
2989 | 3036 |
2990 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT | 3037 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT |
3040 /* Return false only when the induction variable BASE + STEP * I is | 3087 /* Return false only when the induction variable BASE + STEP * I is |
3041 known to not overflow: i.e. when the number of iterations is small | 3088 known to not overflow: i.e. when the number of iterations is small |
3042 enough with respect to the step and initial condition in order to | 3089 enough with respect to the step and initial condition in order to |
3043 keep the evolution confined in TYPEs bounds. Return true when the | 3090 keep the evolution confined in TYPEs bounds. Return true when the |
3044 iv is known to overflow or when the property is not computable. | 3091 iv is known to overflow or when the property is not computable. |
3045 | 3092 |
3046 USE_OVERFLOW_SEMANTICS is true if this function should assume that | 3093 USE_OVERFLOW_SEMANTICS is true if this function should assume that |
3047 the rules for overflow of the given language apply (e.g., that signed | 3094 the rules for overflow of the given language apply (e.g., that signed |
3048 arithmetics in C does not overflow). */ | 3095 arithmetics in C does not overflow). */ |
3049 | 3096 |
3050 bool | 3097 bool |
3051 scev_probably_wraps_p (tree base, tree step, | 3098 scev_probably_wraps_p (tree base, tree step, |
3052 gimple at_stmt, struct loop *loop, | 3099 gimple at_stmt, struct loop *loop, |
3053 bool use_overflow_semantics) | 3100 bool use_overflow_semantics) |
3054 { | 3101 { |
3055 struct nb_iter_bound *bound; | 3102 struct nb_iter_bound *bound; |
3056 tree delta, step_abs; | 3103 tree delta, step_abs; |
3060 /* FIXME: We really need something like | 3107 /* FIXME: We really need something like |
3061 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html. | 3108 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html. |
3062 | 3109 |
3063 We used to test for the following situation that frequently appears | 3110 We used to test for the following situation that frequently appears |
3064 during address arithmetics: | 3111 during address arithmetics: |
3065 | 3112 |
3066 D.1621_13 = (long unsigned intD.4) D.1620_12; | 3113 D.1621_13 = (long unsigned intD.4) D.1620_12; |
3067 D.1622_14 = D.1621_13 * 8; | 3114 D.1622_14 = D.1621_13 * 8; |
3068 D.1623_15 = (doubleD.29 *) D.1622_14; | 3115 D.1623_15 = (doubleD.29 *) D.1622_14; |
3069 | 3116 |
3070 And derived that the sequence corresponding to D_14 | 3117 And derived that the sequence corresponding to D_14 |