X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fomega.c;h=c8768d8b441b861bcb5efbb1e8b4b93d30d746dd;hb=7b54e46d42d74e741f3fdbf670a2a48d33572cbd;hp=8f0470f6dfd64d65c722a82e827ddd9eef4f2688;hpb=f0b5f617f9a1bfcecedbf6927598405d7f896419;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/omega.c b/gcc/omega.c index 8f0470f6dfd..c8768d8b441 100644 --- a/gcc/omega.c +++ b/gcc/omega.c @@ -1,12 +1,12 @@ -/* Source code for an implementation of the Omega test, an integer - programming algorithm for dependence analysis, by William Pugh, +/* Source code for an implementation of the Omega test, an integer + programming algorithm for dependence analysis, by William Pugh, appeared in Supercomputing '91 and CACM Aug 92. This code has no license restrictions, and is considered public domain. - Changes copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, - Inc. + Changes copyright (C) 2005, 2006, 2007, 2008, 2009, + 2010 Free Software Foundation, Inc. Contributed by Sebastian Pop This file is part of GCC. @@ -34,12 +34,8 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "errors.h" -#include "ggc.h" #include "tree.h" -#include "diagnostic.h" -#include "varray.h" +#include "diagnostic-core.h" #include "tree-pass.h" #include "omega.h" @@ -114,37 +110,6 @@ int_mod (int a, int b) return a - b * int_div (a, b); } -/* For X and Y positive integers, return X multiplied by Y and check - that the result does not overflow. */ - -static inline int -check_pos_mul (int x, int y) -{ - if (x != 0) - gcc_assert ((INT_MAX) / x > y); - - return x * y; -} - -/* Return X multiplied by Y and check that the result does not - overflow. */ - -static inline int -check_mul (int x, int y) -{ - if (x >= 0) - { - if (y >= 0) - return check_pos_mul (x, y); - else - return -check_pos_mul (x, -y); - } - else if (y >= 0) - return -check_pos_mul (-x, y); - else - return check_pos_mul (-x, -y); -} - /* Test whether equation E is red. */ static inline bool @@ -185,24 +150,6 @@ omega_no_procedure (omega_pb pb ATTRIBUTE_UNUSED) void (*omega_when_reduced) (omega_pb) = omega_no_procedure; -/* Compute the greatest common divisor of A and B. */ - -static inline int -gcd (int b, int a) -{ - if (b == 1) - return 1; - - while (b != 0) - { - int t = b; - b = a % b; - a = t; - } - - return a; -} - /* Print to FILE from PB equation E with all its coefficients multiplied by C. */ @@ -365,7 +312,7 @@ omega_print_vars (FILE *file, omega_pb pb) /* Debug problem PB. */ -void +DEBUG_FUNCTION void debug_omega_problem (omega_pb pb) { omega_print_problem (stderr, pb); @@ -508,7 +455,7 @@ omega_pretty_print_problem (FILE *file, omega_pb pb) none, le, lt } partial_order_type; - partial_order_type **po = XNEWVEC (partial_order_type *, + partial_order_type **po = XNEWVEC (partial_order_type *, OMEGA_MAX_VARS * OMEGA_MAX_VARS); int **po_eq = XNEWVEC (int *, OMEGA_MAX_VARS * OMEGA_MAX_VARS); int *last_links = XNEWVEC (int, OMEGA_MAX_VARS); @@ -674,7 +621,7 @@ omega_pretty_print_problem (FILE *file, omega_pb pb) } fprintf (file, "%s", omega_variable_to_str (pb, chain[0])); - + for (multiprint = false, i = 1; i < m; i++) { v = chain[i - 1]; @@ -1306,12 +1253,12 @@ verify_omega_pb (omega_pb pb) enum omega_result result; int e; bool any_color = false; - omega_pb tmp_problem = XNEW (struct omega_pb); + omega_pb tmp_problem = XNEW (struct omega_pb_d); omega_copy_problem (tmp_problem, pb); tmp_problem->safe_vars = 0; tmp_problem->num_subs = 0; - + for (e = pb->num_geqs - 1; e >= 0; e--) if (pb->geqs[e].color == omega_red) { @@ -1359,7 +1306,7 @@ verify_omega_pb (omega_pb pb) static void adding_equality_constraint (omega_pb pb, int e) { - if (original_problem != no_problem + if (original_problem != no_problem && original_problem != pb && !conservative) { @@ -1526,7 +1473,7 @@ normalize_omega_problem (omega_pb pb) { i = packing[i0]; pb->geqs[e].coef[i] = pb->geqs[e].coef[i] / g; - hashCode = hashCode * hash_key_multiplier * (i + 3) + hashCode = hashCode * hash_key_multiplier * (i + 3) + pb->geqs[e].coef[i]; } } @@ -1644,7 +1591,7 @@ normalize_omega_problem (omega_pb pb) } if (pb->geqs[e2].coef[0] == -cTerm - && (create_color + && (create_color || pb->geqs[e].color == omega_black)) { omega_copy_eqn (&pb->eqs[pb->num_eqs], &pb->geqs[e], @@ -1686,7 +1633,7 @@ normalize_omega_problem (omega_pb pb) e2 = fast_lookup[MAX_KEYS + eKey]; - if (e2 < e && pb->geqs[e2].key == eKey + if (e2 < e && pb->geqs[e2].key == eKey && pb->geqs[e2].color == omega_black) { if (pb->geqs[e2].coef[0] > cTerm) @@ -1835,7 +1782,7 @@ cleanout_wildcards (omega_pb pb) for (e2 = pb->num_eqs - 1; e2 >= 0; e2--) if (e != e2 && pb->eqs[e2].coef[i] && (pb->eqs[e2].color == omega_red - || (pb->eqs[e2].color == omega_black + || (pb->eqs[e2].color == omega_black && pb->eqs[e].color == omega_black))) { eqn eqn = &(pb->eqs[e2]); @@ -1854,9 +1801,9 @@ cleanout_wildcards (omega_pb pb) } for (e2 = pb->num_geqs - 1; e2 >= 0; e2--) - if (pb->geqs[e2].coef[i] + if (pb->geqs[e2].coef[i] && (pb->geqs[e2].color == omega_red - || (pb->eqs[e].color == omega_black + || (pb->eqs[e].color == omega_black && pb->geqs[e2].color == omega_black))) { eqn eqn = &(pb->geqs[e2]); @@ -1876,9 +1823,9 @@ cleanout_wildcards (omega_pb pb) } for (e2 = pb->num_subs - 1; e2 >= 0; e2--) - if (pb->subs[e2].coef[i] + if (pb->subs[e2].coef[i] && (pb->subs[e2].color == omega_red - || (pb->subs[e2].color == omega_black + || (pb->subs[e2].color == omega_black && pb->eqs[e].color == omega_black))) { eqn eqn = &(pb->subs[e2]); @@ -1976,10 +1923,10 @@ omega_unprotect_1 (omega_pb pb, int *idx, bool *unprotect) static void resurrect_subs (omega_pb pb) { - if (pb->num_subs > 0 + if (pb->num_subs > 0 && please_no_equalities_in_simplified_problems == 0) { - int i, e, n, m; + int i, e, m; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -1993,7 +1940,6 @@ resurrect_subs (omega_pb pb) omega_unprotect_1 (pb, &i, NULL); m = pb->num_subs; - n = MAX (pb->num_vars, pb->safe_vars + m); for (e = pb->num_geqs - 1; e >= 0; e--) if (single_var_geq (&pb->geqs[e], pb->num_vars)) @@ -2133,7 +2079,7 @@ omega_eliminate_redundant (omega_pb pb, bool expensive) continue; foundPQ: - pz = ((zeqs[e1] & zeqs[e2]) | (peqs[e1] & neqs[e2]) + pz = ((zeqs[e1] & zeqs[e2]) | (peqs[e1] & neqs[e2]) | (neqs[e1] & peqs[e2])); pp = peqs[e1] | peqs[e2]; pn = neqs[e1] | neqs[e2]; @@ -2163,7 +2109,7 @@ omega_eliminate_redundant (omega_pb pb, bool expensive) if (alpha3 > 0) { /* Trying to prove e3 is redundant. */ - if (!implies (peqs[e3], pp) + if (!implies (peqs[e3], pp) || !implies (neqs[e3], pn)) goto nextE3; @@ -2207,7 +2153,7 @@ omega_eliminate_redundant (omega_pb pb, bool expensive) /* Trying to prove e3 <= 0 and therefore e3 = 0, or trying to prove e3 < 0, and therefore the problem has no solutions. */ - if (!implies (peqs[e3], pn) + if (!implies (peqs[e3], pn) || !implies (neqs[e3], pp)) goto nextE3; @@ -2216,7 +2162,6 @@ omega_eliminate_redundant (omega_pb pb, bool expensive) || pb->geqs[e3].color == omega_red) goto nextE3; - alpha3 = alpha3; /* verify alpha1*v1+alpha2*v2 = alpha3*v3 */ for (k = pb->num_vars; k >= 1; k--) if (alpha3 * pb->geqs[e3].coef[k] @@ -2268,7 +2213,7 @@ omega_eliminate_redundant (omega_pb pb, bool expensive) fprintf (dump_file, "\n\n"); } - omega_copy_eqn (&pb->eqs[pb->num_eqs++], + omega_copy_eqn (&pb->eqs[pb->num_eqs++], &pb->geqs[e3], pb->num_vars); gcc_assert (pb->num_eqs <= OMEGA_MAX_EQS); adding_equality_constraint (pb, pb->num_eqs - 1); @@ -2287,7 +2232,7 @@ omega_eliminate_redundant (omega_pb pb, bool expensive) if (!expensive) goto eliminate_redundant_done; - tmp_problem = XNEW (struct omega_pb); + tmp_problem = XNEW (struct omega_pb_d); conservative++; for (e = pb->num_geqs - 1; e >= 0; e--) @@ -2470,12 +2415,12 @@ coalesce (omega_pb pb) is_dead[e] = false; for (e = 0; e < pb->num_geqs; e++) - if (pb->geqs[e].color == omega_red + if (pb->geqs[e].color == omega_red && !pb->geqs[e].touched) for (e2 = e + 1; e2 < pb->num_geqs; e2++) - if (!pb->geqs[e2].touched + if (!pb->geqs[e2].touched && pb->geqs[e].key == -pb->geqs[e2].key - && pb->geqs[e].coef[0] == -pb->geqs[e2].coef[0] + && pb->geqs[e].coef[0] == -pb->geqs[e2].coef[0] && pb->geqs[e2].color == omega_red) { omega_copy_eqn (&pb->eqs[pb->num_eqs++], &pb->geqs[e], @@ -2528,7 +2473,7 @@ omega_eliminate_red (omega_pb pb, bool eliminate_all) for (e = pb->num_geqs - 1; e >= 0; e--) if (pb->geqs[e].color == omega_black && !is_dead[e]) for (e2 = e - 1; e2 >= 0; e2--) - if (pb->geqs[e2].color == omega_black + if (pb->geqs[e2].color == omega_black && !is_dead[e2]) { a = 0; @@ -2558,7 +2503,7 @@ omega_eliminate_red (omega_pb pb, bool eliminate_all) for (e3 = pb->num_geqs - 1; e3 >= 0; e3--) if (pb->geqs[e3].color == omega_red) { - alpha1 = (pb->geqs[e2].coef[j] * pb->geqs[e3].coef[i] + alpha1 = (pb->geqs[e2].coef[j] * pb->geqs[e3].coef[i] - pb->geqs[e2].coef[i] * pb->geqs[e3].coef[j]); alpha2 = -(pb->geqs[e].coef[j] * pb->geqs[e3].coef[i] - pb->geqs[e].coef[i] * pb->geqs[e3].coef[j]); @@ -2578,7 +2523,7 @@ omega_eliminate_red (omega_pb pb, bool eliminate_all) for (k = pb->num_vars; k >= 0; k--) { - c = (alpha1 * pb->geqs[e].coef[k] + c = (alpha1 * pb->geqs[e].coef[k] + alpha2 * pb->geqs[e2].coef[k]); if (c != a * pb->geqs[e3].coef[k]) @@ -2649,7 +2594,7 @@ omega_eliminate_red (omega_pb pb, bool eliminate_all) return; conservative++; - tmp_problem = XNEW (struct omega_pb); + tmp_problem = XNEW (struct omega_pb_d); for (e = pb->num_geqs - 1; e >= 0; e--) if (pb->geqs[e].color == omega_red) @@ -2744,7 +2689,7 @@ static void omega_problem_reduced (omega_pb pb) { if (omega_verify_simplification - && !in_approximate_mode + && !in_approximate_mode && verify_omega_pb (pb) == omega_false) return; @@ -2757,7 +2702,7 @@ omega_problem_reduced (omega_pb pb) if (!please_no_equalities_in_simplified_problems) coalesce (pb); - if (omega_reduce_with_subs + if (omega_reduce_with_subs || please_no_equalities_in_simplified_problems) chain_unprotect (pb); else @@ -3049,7 +2994,8 @@ omega_do_elimination (omega_pb pb, int e, int i) eqn->coef[j] *= a; k = eqn->coef[i]; eqn->coef[i] = 0; - eqn->color |= sub->color; + if (sub->color == omega_red) + eqn->color = omega_red; for (j = n_vars; j >= 0; j--) eqn->coef[j] -= sub->coef[j] * k / c; } @@ -3448,7 +3394,7 @@ omega_solve_eq (omega_pb pb, enum omega_result desired_res) j = 0; for (i = pb->num_vars; i != sv; i--) - if (pb->eqs[e].coef[i] != 0 + if (pb->eqs[e].coef[i] != 0 && factor > abs (pb->eqs[e].coef[i]) + 1) { factor = abs (pb->eqs[e].coef[i]) + 1; @@ -3491,7 +3437,7 @@ parallel_splinter (omega_pb pb, int e, int diff, omega_print_problem (dump_file, pb); } - tmp_problem = XNEW (struct omega_pb); + tmp_problem = XNEW (struct omega_pb_d); omega_copy_eqn (&pb->eqs[0], &pb->geqs[e], pb->num_vars); pb->num_eqs = 1; @@ -3591,7 +3537,7 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) c = int_div (c, -a); if (upper_bound > c - || (upper_bound == c + || (upper_bound == c && !omega_eqn_is_red (&pb->geqs[e], desired_res))) { upper_bound = c; @@ -3723,7 +3669,6 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) int max_splinters = 1; bool exact = false; bool lucky_exact = false; - int neweqns = 0; int best = (INT_MAX); int j = 0, jLe = 0, jLowerBoundCount = 0; @@ -3857,12 +3802,12 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) lucky = (diff >= (Uc - 1) * (Lc - 1)); } - if (maxC == 1 - || minC == -1 - || lucky + if (maxC == 1 + || minC == -1 + || lucky || in_approximate_mode) { - neweqns = score = upper_bound_count * lower_bound_count; + score = upper_bound_count * lower_bound_count; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, @@ -3870,7 +3815,7 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) "\nlucky = %d, in_approximate_mode=%d \n", omega_variable_to_str (pb, i), upper_bound_count, - lower_bound_count, minC, maxC, lucky, + lower_bound_count, minC, maxC, lucky, in_approximate_mode); if (!exact @@ -3898,7 +3843,6 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) upper_bound_count, lower_bound_count, minC, maxC); - neweqns = upper_bound_count * lower_bound_count; score = maxC - minC; if (best > score) @@ -3932,8 +3876,8 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) max_splinters += -minC - 1; else max_splinters += - check_pos_mul ((pb->geqs[e].coef[i] - 1), - (-minC - 1)) / (-minC) + 1; + pos_mul_hwi ((pb->geqs[e].coef[i] - 1), + (-minC - 1)) / (-minC) + 1; } /* #ifdef Omega3 */ @@ -4163,9 +4107,9 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) { constantTerm = -int_div (constantTerm, coefficient); - if (constantTerm > lower_bound - || (constantTerm == lower_bound - && (desired_res != omega_simplify + if (constantTerm > lower_bound + || (constantTerm == lower_bound + && (desired_res != omega_simplify || (pb->geqs[Ue].color == omega_black && pb->geqs[Le].color == omega_black)))) { @@ -4285,7 +4229,7 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) } else { - if (!conservative + if (!conservative && (desired_res != omega_simplify || (lb_color == omega_black && ub_color == omega_black)) @@ -4346,8 +4290,8 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) for (k = 0; k <= n_vars; k++) pb->geqs[Ue].coef[k] = - check_mul (pb->geqs[Ue].coef[k], Lc) + - check_mul (lbeqn->coef[k], Uc); + mul_hwi (pb->geqs[Ue].coef[k], Lc) + + mul_hwi (lbeqn->coef[k], Uc); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -4409,13 +4353,13 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) for (k = n_vars; k >= 0; k--) pb->geqs[e2].coef[k] = - check_mul (pb->geqs[Ue].coef[k], Lc) + - check_mul (pb->geqs[Le].coef[k], Uc); + mul_hwi (pb->geqs[Ue].coef[k], Lc) + + mul_hwi (pb->geqs[Le].coef[k], Uc); pb->geqs[e2].coef[n_vars + 1] = 0; pb->geqs[e2].touched = 1; - if (pb->geqs[Ue].color == omega_red + if (pb->geqs[Ue].color == omega_red || pb->geqs[Le].color == omega_red) pb->geqs[e2].color = omega_red; else @@ -4531,8 +4475,8 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) { for (k = n_vars; k >= 0; k--) iS->geqs[e2].coef[k] = rS->geqs[e2].coef[k] = - check_mul (pb->geqs[Ue].coef[k], Lc) + - check_mul (pb->geqs[Le].coef[k], Uc); + mul_hwi (pb->geqs[Ue].coef[k], Lc) + + mul_hwi (pb->geqs[Le].coef[k], Uc); iS->geqs[e2].coef[0] -= (Uc - 1) * (Lc - 1); } @@ -4803,7 +4747,7 @@ omega_solve_problem (omega_pb pb, enum omega_result desired_res) { if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, + fprintf (dump_file, "Solve depth = %d, in_approximate_mode = %d, aborting\n", omega_solve_depth, in_approximate_mode); omega_print_problem (dump_file, pb); @@ -4831,7 +4775,7 @@ omega_solve_problem (omega_pb pb, enum omega_result desired_res) if (!omega_reduce_with_subs) { resurrect_subs (pb); - gcc_assert (please_no_equalities_in_simplified_problems + gcc_assert (please_no_equalities_in_simplified_problems || !result || pb->num_subs == 0); } @@ -5117,7 +5061,7 @@ omega_unprotect_variable (omega_pb pb, int var) { for (e = pb->num_geqs - 1; e >= 0; e--) { - pb->geqs[e].coef[pb->num_vars] = + pb->geqs[e].coef[pb->num_vars] = pb->geqs[e].coef[pb->safe_vars]; pb->geqs[e].coef[pb->safe_vars] = 0; @@ -5310,7 +5254,7 @@ omega_query_variable (omega_pb pb, int i, int *lower_bound, int *upper_bound) continue; else { - *lower_bound = *upper_bound = + *lower_bound = *upper_bound = -pb->eqs[e].coef[i] * pb->eqs[e].coef[0]; return false; } @@ -5425,7 +5369,7 @@ omega_query_variable_bounds (omega_pb pb, int i, int *l, int *u) || (pb->num_vars == 1 && pb->forwarding_address[i] == 1)) return false; - if (abs (pb->forwarding_address[i]) == 1 + if (abs (pb->forwarding_address[i]) == 1 && pb->num_vars + pb->num_subs == 2 && pb->num_eqs + pb->num_subs == 1) { @@ -5499,7 +5443,7 @@ omega_alloc_problem (int nvars, int nprot) omega_initialize (); /* Allocate and initialize PB. */ - pb = XCNEW (struct omega_pb); + pb = XCNEW (struct omega_pb_d); pb->var = XCNEWVEC (int, OMEGA_MAX_VARS + 2); pb->forwarding_address = XCNEWVEC (int, OMEGA_MAX_VARS + 2); pb->geqs = omega_alloc_eqns (0, OMEGA_MAX_GEQS);