-/* 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, 2009 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.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.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];
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);
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])
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
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;
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)
{
OSDN Git Service
