-/* 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 Free Software Foundation, Inc.
+ Changes copyright (C) 2005, 2006, 2007, 2008, 2009,
+ 2010 Free Software Foundation, Inc.
Contributed by Sebastian Pop <sebastian.pop@inria.fr>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* For a detailed description, see "Constraint-Based Array Dependence
Analysis" William Pugh, David Wonnacott, TOPLAS'98 and David
#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"
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
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. */
/* Debug problem PB. */
-void
+DEBUG_FUNCTION void
debug_omega_problem (omega_pb pb)
{
omega_print_problem (stderr, 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);
}
fprintf (file, "%s", omega_variable_to_str (pb, chain[0]));
-
+
for (multiprint = false, i = 1; i < m; i++)
{
v = chain[i - 1];
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)
{
static void
adding_equality_constraint (omega_pb pb, int e)
{
- if (original_problem != no_problem
+ if (original_problem != no_problem
&& original_problem != pb
&& !conservative)
{
{
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];
}
}
}
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],
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)
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]);
}
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]);
}
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]);
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))
{
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))
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];
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;
/* 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;
|| 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]
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);
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--)
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
- "Smoothing wierd equations; adding:\n");
+ "Smoothing weird equations; adding:\n");
omega_print_geq (dump_file, pb, &pb->geqs[e3]);
fprintf (dump_file, "\nto:\n");
omega_print_problem (dump_file, pb);
{
int e, e2;
int colors = 0;
- bool *is_dead = XNEWVEC (bool, OMEGA_MAX_GEQS);
+ bool *is_dead;
int found_something = 0;
for (e = 0; e < pb->num_geqs; e++)
if (colors < 2)
return;
+ is_dead = XNEWVEC (bool, OMEGA_MAX_GEQS);
+
for (e = 0; e < pb->num_geqs; e++)
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],
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;
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]);
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])
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)
omega_problem_reduced (omega_pb pb)
{
if (omega_verify_simplification
- && !in_approximate_mode
+ && !in_approximate_mode
&& verify_omega_pb (pb) == omega_false)
return;
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
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;
}
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;
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;
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;
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;
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,
"\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
upper_bound_count,
lower_bound_count, minC, maxC);
- neweqns = upper_bound_count * lower_bound_count;
score = maxC - minC;
if (best > score)
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 */
{
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))))
{
}
else
{
- if (!conservative
+ if (!conservative
&& (desired_res != omega_simplify
|| (lb_color == omega_black
&& ub_color == omega_black))
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))
{
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
{
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);
}
{
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);
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);
}
{
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;
continue;
else
{
- *lower_bound = *upper_bound =
+ *lower_bound = *upper_bound =
-pb->eqs[e].coef[i] * pb->eqs[e].coef[0];
return false;
}
|| (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)
{
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);