Re: [4.2 projects] Omega data dependence test

[Diego Novillo <dnovillo at redhat dot com>]

I guess your idea is to use Omega as one of the data dependency
analyzers in GRAPHITE?  Omega is generally a fairly expensive
analyzer, is your goal replacing the data dependency routines that we
already have in tree-data-ref.c?

I'm a bit concerned about a potential explosion of different
experimental analyzers.  I'm not opposed to extending GCC's
capabilities in this area, on the contrary, we badly need smarter LNO
techniques.  However, I also don't want to move into a purely research
direction.  What are your long terms plans here?

A bit of usage documentation, including a brief overview of how the
solver works and examples at the top of the file would be useful.

I still have not finished reading the whole patch.  It mostly looks fine,
though.  Instead of waiting until I'm done with it, we can get started with
some initial feedback.

> Index: omega.c
> ===================================================================
> --- omega.c	(revision 0)
> +++ omega.c	(revision 0)
> @@ -0,0 +1,5575 @@
> +/* 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.
> +
Hmm, I do not know how we handle public domain code in GCC.  You will
have to ask the SC about this.

> +bool omega_reduce_with_subs = true;
> +bool omega_verify_simplification = false;
> +
Comment.

> +#ifndef APROX
> +#define APROX 0
> +#endif
> +
Where do you expect this to be defined?  Needs comment.

> +#define KEY_MULT 31
> +
Comment.

> +#ifdef SINGLE_RESULT
> +#define return_single_result  1
> +#else
> +static int return_single_result = 0;
> +#endif
> +
No.  Convert to --params.  Please don't define an object that is
sometimes a macro and sometimes a variable.

> +static int may_be_red = 0;
> +#define HASH_TABLE_SIZE PARAM_VALUE (PARAM_OMEGA_HASH_TABLE_SIZE)
> +#define MAX_KEYS PARAM_VALUE (PARAM_OMEGA_MAX_KEYS)
> +
> +static eqn hash_master;
> +static bool non_convex = false;
> +static bool do_it_again;
> +static int conservative = 0;
> +static int next_key;
> +static char wild_name[200][40];
> +static int next_wild_card = 0;
> +static enum omega_result omega_found_reduction;
> +static int *packing;
> +static bool in_approximate_mode = 0;
> +static bool create_color = false;
> +static int please_no_equalities_in_simplified_problems = 0;
> +static int hash_version = 0;
> +
> +omega_pb no_problem = (omega_pb) 0;
> +omega_pb original_problem = (omega_pb) 0;
> +
>
Document all these symbols.

> +/* Set *M to the maximum of *M and X.  */
> +
> +static inline void
> +set_max (int *m, int x)
> +{
> +  if (*m < x)
> +    *m = x;
> +}
> +
> +/* Set *M to the minimum of *M and X.  */
> +
> +static inline void
> +set_min (int *m, int x)
> +{
> +  if (*m > x)
> +    *m = x;
> +}
> +
Why not return it the min and max?

> +/* Don't use this; instead, use omega_alloc_problem.  This initializes
> +   static vars for problem PB.  FIXME: remove those static vars.  */
> +
What static vars?  Why remove them?  The comment says not to use this
function.  Why have it?


> +		if (pb->geqs[e].coef[0] > 0 || pb->geqs[e].coef[0] < -1
> +		    || v2 <= 0 || v3 > 0
> +		    || pb->geqs[e].coef[v1] * pb->geqs[e].coef[v2] != -1)
>
Line up predicates vertically.

> +
> +/* Delete inequality E from problem PB that has N_VARS variables.  */
> +
s/N_VARS/NV/

> +static void
> +omega_delete_geq (omega_pb pb, int e, int nv)
>
or s/NV/N_VARS/

> +/* Helper function.  */
> +
>
Missing documentation on arguments.  There's several instances all
throughout.

> +
> +static int *fast_lookup;
> +static int *fast_lookup_red;
> +
> +typedef enum {
> +  normalize_false,
> +  normalize_uncoupled,
> +  normalize_coupled
> +} normalize_return_type;
> +
Documentation missing.

> +/* */
> +
>
Missing comment.

> +/* Helper function: solve equations one at a time.  */
> +
>
Documentation missing for arguments.

> +static enum omega_result
> +omega_solve_geq (omega_pb pb, enum omega_result desired_res)
> +{
>
Is there a way of modularizing this function into helpers?  There are
other multi-screen functions floating about.  This is more a
suggestion than a demand.  If there is no graceful way of splitting it
up, then that's fine.

> +		fprintf (dump_file,
> +			 "For %s, exact, score = %d*%d, range = %d ... %d, \nlucky = %d,
APROX = %d, in_approximate_mode=%d \n",
>
Split up this string.

> +/* Return true if red equations constrain the set of possible solutions.
> +   We assume that there are solutions to the black equations by
> +   themselves, so if there is no solution to the combined problem, we
> +   return true.  */
> +
> +bool
> +omega_problem_has_red_equations (omega_pb pb)
>
Document PB.

> +/* Calls omega_simplify_problem in approximate mode.  */
> +
>
Document argument PB.

> +/* Make variable VAR unprotected: it then can be eliminated.  */
> +
> +void
> +omega_unprotect_variable (omega_pb pb, int var)
>
Document argument PB.

> +/* Unprotects VAR and simplifies PB.  */
> +
> +enum omega_result
> +omega_constrain_variable_sign (omega_pb pb, enum omega_eqn_color color,
> +			       int var, int sign)
> +{
>
Document COLOR and SIGN.

> +  /* Private (not used outside the solver).  */
> +  int hash_version;
> +  /* Private (not used outside the solver).  */
> +  bool variables_initialized;
> +  /* Private (not used outside the solver).  */
> +  bool variables_freed;
> +
These private fields still need documentation.

> +  /* Index or name of variables.  Negative integers are reserved for
> +     wildcard variables.  Maps the index of variables in the original
> +     problem to the new index of the variable.  The index for a
> +     variable in the coef array of an equation can change as some
> +     variables are eliminated.  */
> +  int *var;
> +
> +  /* */
> +  int *forwarding_address;
> +
Missing documentation.