CbC/CbC_gcc: gcc/omega.c comparison

comparison gcc/omega.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	a06113de4d67
children	b7f97abdc517

comparison

equal deleted inserted replaced

-:c156f1bd5cd9
+:77e2b8dfacca
 /* 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,
+Changes copyright (C) 2005, 2006, 2007, 2008, 2009 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 "errors.h"
 #include "ggc.h"
 #include "tree.h"
 #include "diagnostic.h"
 #include "varray.h"
 #include "tree-pass.h"
 typedef enum {
 none, le, lt
 } 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);
 int *first_links = XNEWVEC (int, OMEGA_MAX_VARS);
 int *chain_length = XNEWVEC (int, OMEGA_MAX_VARS);
 	      chain[m++] = v2;
 	      v = v2;
 	    }
 	  fprintf (file, "%s", omega_variable_to_str (pb, chain[0]));
 	  for (multiprint = false, i = 1; i < m; i++)
 	    {
 	      v = chain[i - 1];
 	      v2 = chain[i];
 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)
 {
 	any_color = true;
 	break;
 /* Add a new equality to problem PB at last position E.  */
 static void
 adding_equality_constraint (omega_pb pb, int e)
 {
 if (original_problem != no_problem
 && original_problem != pb
 && !conservative)
 {
 int i, j;
 int e2 = original_problem->num_eqs++;
 		  for (; i0 >= 0; i0--)
 		    {
 		      i = packing[i0];
 		      pb->geqs[e].coef[i] = pb->geqs[e].coef[i] / g;
 		      hashCode = hashCode * hash_key_multiplier * (i + 3)
 			+ pb->geqs[e].coef[i];
 		    }
 		}
 	      g2 = abs (hashCode);
 		      }
 		    return normalize_false;
 		  }
 		if (pb->geqs[e2].coef[0] == -cTerm
 		    && (create_color
 			|| pb->geqs[e].color == omega_black))
 		  {
 		    omega_copy_eqn (&pb->eqs[pb->num_eqs], &pb->geqs[e],
 				    pb->num_vars);
 		    if (pb->geqs[e].color == omega_black)
 		  }
 	      }
 	    e2 = fast_lookup[MAX_KEYS + eKey];
 	    if (e2 < e && pb->geqs[e2].key == eKey
 		&& pb->geqs[e2].color == omega_black)
 	      {
 		if (pb->geqs[e2].coef[0] > cTerm)
 		  {
 		    if (pb->geqs[e].color == omega_black)
 		}
 	      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[e].color == omega_black)))
 		  {
 		    eqn eqn = &(pb->eqs[e2]);
 		    int var, k;
 		    eqn->coef[i] = 0;
 		    divide_eqn_by_gcd (eqn, n_vars);
 		  }
 	      for (e2 = pb->num_geqs - 1; e2 >= 0; e2--)
 		if (pb->geqs[e2].coef[i]
 		    && (pb->geqs[e2].color == omega_red
 			|| (pb->eqs[e].color == omega_black
 			    && pb->geqs[e2].color == omega_black)))
 		  {
 		    eqn eqn = &(pb->geqs[e2]);
 		    int var, k;
 		    eqn->touched = 1;
 		    renormalize = true;
 		  }
 	      for (e2 = pb->num_subs - 1; e2 >= 0; e2--)
 		if (pb->subs[e2].coef[i]
 		    && (pb->subs[e2].color == omega_red
 			|| (pb->subs[e2].color == omega_black
 			    && pb->eqs[e].color == omega_black)))
 		  {
 		    eqn eqn = &(pb->subs[e2]);
 		    int var, k;
 substituted variables in PB.  */
 static void
 resurrect_subs (omega_pb pb)
 {
 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))
 	{
 	  fprintf (dump_file,
 		   "problem reduced, bringing variables back to life\n");
 for (i = 1; omega_safe_var_p (pb, i); i++)
 	if (omega_wildcard_p (pb, i))
 	  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))
 	  {
 	    if (!omega_safe_var_p (pb, abs (pb->geqs[e].key)))
 		  goto foundPQ;
 	    continue;
 	  foundPQ:
 	    pz = ((zeqs[e1] & zeqs[e2]) | (peqs[e1] & neqs[e2])
 		  | (neqs[e1] & peqs[e2]));
 	    pp = peqs[e1] | peqs[e2];
 	    pn = neqs[e1] | neqs[e2];
 	    for (e3 = pb->num_geqs - 1; e3 >= 0; e3--)
 		    }
 		  if (alpha3 > 0)
 		    {
 		      /* Trying to prove e3 is redundant.  */
 		      if (!implies (peqs[e3], pp)
 			  || !implies (neqs[e3], pn))
 			goto nextE3;
 		      if (pb->geqs[e3].color == omega_black
 			  && (pb->geqs[e1].color == omega_red
 		  else
 		    {
 		      /* 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)
 			  || !implies (neqs[e3], pp))
 			goto nextE3;
 		      if (pb->geqs[e1].color == omega_red
 			  || pb->geqs[e2].color == omega_red
 			      fprintf (dump_file, "\n=> inverse ");
 			      omega_print_geq (dump_file, pb, &(pb->geqs[e3]));
 			      fprintf (dump_file, "\n\n");
 			    }
 			  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[e3] = true;
 			}
 omega_delete_geq (pb, e, pb->num_vars);
 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))
 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
 	&& !pb->geqs[e].touched)
 for (e2 = e + 1; e2 < pb->num_geqs; e2++)
 	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[e2].color == omega_red)
 	  {
 	    omega_copy_eqn (&pb->eqs[pb->num_eqs++], &pb->geqs[e],
 			    pb->num_vars);
 	    gcc_assert (pb->num_eqs <= OMEGA_MAX_EQS);
 is_dead[e] = false;
 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
 	    && !is_dead[e2])
 	  {
 	    a = 0;
 	    for (i = pb->num_vars; i > 1; i--)
 	      }
 	    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]
 			    - 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]);
 		  if ((a > 0 && alpha1 > 0 && alpha2 > 0)
 			  fprintf (dump_file, "\n");
 			}
 		      for (k = pb->num_vars; k >= 0; k--)
 			{
 			  c = (alpha1 * pb->geqs[e].coef[k]
 			       + alpha2 * pb->geqs[e2].coef[k]);
 			  if (c != a * pb->geqs[e3].coef[k])
 			    break;
 if (!omega_verify_simplification
 && verify_omega_pb (pb) == omega_false)
 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)
 {
 	if (dump_file && (dump_flags & TDF_DETAILS))
 static void
 omega_problem_reduced (omega_pb pb)
 {
 if (omega_verify_simplification
 && !in_approximate_mode
 && verify_omega_pb (pb) == omega_false)
 return;
 if (PARAM_VALUE (PARAM_OMEGA_ELIMINATE_REDUNDANT_CONSTRAINTS)
 && !omega_eliminate_redundant (pb, true))
 omega_found_reduction = omega_true;
 if (!please_no_equalities_in_simplified_problems)
 coalesce (pb);
 if (omega_reduce_with_subs
 || please_no_equalities_in_simplified_problems)
 chain_unprotect (pb);
 else
 resurrect_subs (pb);
 	    int j, k;
 	    for (j = n_vars; j >= 0; j--)
 	      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;
 	  }
 for (e = pb->num_geqs - 1; e >= 0; e--)
 		  continue;
 		}
 	      j = 0;
 	      for (i = pb->num_vars; i != sv; i--)
 		if (pb->eqs[e].coef[i] != 0
 		    && factor > abs (pb->eqs[e].coef[i]) + 1)
 		  {
 		    factor = abs (pb->eqs[e].coef[i]) + 1;
 		    j = i;
 		  }
 {
 fprintf (dump_file, "Using parallel splintering\n");
 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;
 for (i = 0; i <= diff; i++)
 {
 	      {
 		if (a != -1)
 		  c = int_div (c, -a);
 		if (upper_bound > c
 		    || (upper_bound == c
 			&& !omega_eqn_is_red (&pb->geqs[e], desired_res)))
 		  {
 		    upper_bound = c;
 		    u_color = pb->geqs[e].color;
 		  }
 int e2, Le = 0, Ue;
 bool possible_easy_int_solution;
 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;
 eliminate_again = false;
 	      int diff =
 		Lc * pb->geqs[ub].coef[0] + Uc * pb->geqs[lb].coef[0];
 	      lucky = (diff >= (Uc - 1) * (Lc - 1));
 	    }
 	  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,
 			 "For %s, exact, score = %d*%d, range = %d ... %d,"
 			 "\nlucky = %d, in_approximate_mode=%d \n",
 			 omega_variable_to_str (pb, i),
 			 upper_bound_count,
 			 lower_bound_count, minC, maxC, lucky,
 			 in_approximate_mode);
 	      if (!exact
 		  || score < best)
 		{
 			 "range = %d ... %d \n",
 			 omega_variable_to_str (pb, i),
 			 upper_bound_count,
 			 lower_bound_count, minC, maxC);
-	      neweqns = upper_bound_count * lower_bound_count;
 	      score = maxC - minC;
 	      if (best > score)
 		{
 		  best = score;
 			if (coefficient > 0)
 			  {
 			    constantTerm = -int_div (constantTerm, coefficient);
 			    if (constantTerm > lower_bound
 				|| (constantTerm == lower_bound
 				    && (desired_res != omega_simplify
 					|| (pb->geqs[Ue].color == omega_black
 					    && pb->geqs[Le].color == omega_black))))
 			      {
 				lower_bound = constantTerm;
 				lb_color = (pb->geqs[Ue].color == omega_red
 		  omega_problem_reduced (pb);
 		  return omega_false;
 		}
 	      else
 		{
 		  if (!conservative
 		      && (desired_res != omega_simplify
 			  || (lb_color == omega_black
 			      && ub_color == omega_black))
 		      && original_problem != no_problem
 		      && lower_bound == upper_bound)
 				  check_mul (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
 				  || pb->geqs[Le].color == omega_red)
 				pb->geqs[e2].color = omega_red;
 			      else
 				pb->geqs[e2].color = omega_black;
 if (omega_solve_depth > 50)
 {
 if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file,
 		   "Solve depth = %d, in_approximate_mode = %d, aborting\n",
 		   omega_solve_depth, in_approximate_mode);
 	  omega_print_problem (dump_file, pb);
 	}
 gcc_assert (0);
 omega_solve_depth--;
 if (!omega_reduce_with_subs)
 {
 resurrect_subs (pb);
 gcc_assert (please_no_equalities_in_simplified_problems
 		  || !result || pb->num_subs == 0);
 }
 return result;
 }
 	    if (pb->safe_vars < pb->num_vars)
 	      {
 		for (e = pb->num_geqs - 1; e >= 0; e--)
 		  {
 		    pb->geqs[e].coef[pb->num_vars] =
 		      pb->geqs[e].coef[pb->safe_vars];
 		    pb->geqs[e].coef[pb->safe_vars] = 0;
 		  }
 	if (!is_simple)
 	  continue;
 	else
 	  {
 	    *lower_bound = *upper_bound =
 	      -pb->eqs[e].coef[i] * pb->eqs[e].coef[0];
 	    return false;
 	  }
 }
 if (!omega_query_variable (pb, i, l, u)
 || (pb->num_vars == 1 && pb->forwarding_address[i] == 1))
 return false;
 if (abs (pb->forwarding_address[i]) == 1
 && pb->num_vars + pb->num_subs == 2
 && pb->num_eqs + pb->num_subs == 1)
 {
 bool could_be_zero;
 query_coupled_variable (pb, i, l, u, &could_be_zero, neg_infinity,
 gcc_assert (nvars <= OMEGA_MAX_VARS);
 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);
 pb->eqs = omega_alloc_eqns (0, OMEGA_MAX_EQS);
 pb->subs = omega_alloc_eqns (0, OMEGA_MAX_VARS + 1);

Mercurial > hg > CbC > CbC_gcc

comparison gcc/omega.c @ 55:77e2b8dfacca gcc-4.4.5