Re: Omega data dependence test for trunk

[Diego Novillo <dnovillo at redhat dot com>]

Sebastian Pop wrote on 02/13/07 02:27:

> 	* doc/invoke.texi: Document -fcheck-data-deps, omega-max-vars,
> 	omega-max-geqs, omega-max-eqs, omega-max-wild-cards, 
> 	omega-hash-table-size, omega-max-keys.
> 	* tree-pass.h (pass_check_data_deps): Declared.
> 	* omega.c: New.
> 	* omega.h: New.
> 	* timevar.def (TV_CHECK_DATA_DEPS): Declared.
> 	* tree-ssa-loop.c (check_data_deps, gate_check_data_deps, 
> 	pass_check_data_deps): New.
> 	* tree-data-ref.c (init_data_ref): Remove declaration.
> 	(dump_data_dependence_relation): Dump DDR_INNER_LOOP.
> 	(analyze_array): Renamed init_array_ref, move up initializations.
> 	(init_data_ref): Renamed init_pointer_ref.  Moved before its call.
> 	Removed arguments that are set to NULL.
> 	(analyze_indirect_ref): Correct indentation, correct call to 
> 	init_pointer_ref.
> 	(object_analysis): Call init_array_ref instead of analyze_array.
> 	(initialize_data_dependence_relation): Initialize DDR_INNER_LOOP.
> 	(access_functions_are_affine_or_constant_p): Use DR_ACCESS_FNS instead
> 	of DR_ACCESS_FNS_ADDR.
> 	(init_omega_eq_with_af, omega_extract_distance_vectors, 
> 	omega_setup_subscript, init_omega_for_ddr_1, init_omega_for_ddr,
> 	ddr_consistent_p): New.
> 	(compute_affine_dependence): Check consistency of ddrs when 
> 	flag_check_data_deps is passed.
> 	(analyze_all_data_dependences): Uncomment.
> 	(tree_check_data_deps): New.
> 	* tree-data-ref.h: Include omega.h.
> 	(DR_ACCESS_FNS_ADDR): Removed.
> 	(data_dependence_relation): Add inner_loop.
> 	(DDR_INNER_LOOP): New.
> 	* common.opt (fcheck-data-deps): New.
> 	* tree-flow.h (tree_check_data_deps): Declare.
> 	* Makefile.in (TREE_DATA_REF_H): Depend on omega.h.
> 	(OBJS-common): Depend on omega.o.
> 	(omega.o): Define.
> 	* passes.c (pass_check_data_deps): Scheduled.
> 	* params.def (PARAM_OMEGA_MAX_VARS, PARAM_OMEGA_MAX_GEQS, 
> 	PARAM_OMEGA_MAX_EQS, PARAM_OMEGA_MAX_WILD_CARDS,
> 	PARAM_OMEGA_HASH_TABLE_SIZE, PARAM_OMEGA_MAX_KEYS,
> 	PARAM_VECT_MAX_VERSION_CHECKS): New.
> 
OK with some minor corrections.  Thanks for your patience.

Could you add an entry for the Omega solver in doc/loop.texi?  We need
enough high-level description so that people can get basic usage information.

> +/* Normalizes PB by removing redundant constraints.  Returns
> +   normalize_false when the constraints system has no solution,
> +   otherwise returns normalize_coupled or normalize_uncoupled.  */
> +
> +static normalize_return_type
> +normalize_omega_problem (omega_pb pb)
> +{

This could use some comments or, better, some factorization.  It's
rather long and cryptic.

> +/* Eliminate redundant equations in PB.  When EXPENSIVE is true, an
> +   extra step is performed.  Returns omega_false when there exist no
> +   solution, omega_true otherwise.  */
> +
> +enum omega_result
> +omega_eliminate_redundant (omega_pb pb, bool expensive)
> +{
> +  int c, e, e1, e2, e3, p, q, i, k, alpha, alpha1, alpha2, alpha3;
> +  bool *is_dead = (bool *) xmalloc (OMEGA_MAX_GEQS * sizeof (bool));
> +  omega_pb tmp_problem;
> +
> +  /* {P,Z,N}EQS = {Positive,Zero,Negative} Equations.  */
> +  unsigned int *peqs = (unsigned int *) xmalloc (OMEGA_MAX_GEQS
> +						 * sizeof (unsigned int));
> +  unsigned int *zeqs = (unsigned int *) xmalloc (OMEGA_MAX_GEQS
> +						 * sizeof (unsigned int));
> +  unsigned int *neqs = (unsigned int *) xmalloc (OMEGA_MAX_GEQS
> +						 * sizeof (unsigned int));
> +

Simpler to use XNEW.

> +			    }
> +			  return omega_false;

We are leaking memory here (the three *eqs arrays).


> +  /* ELIMINATE_REDUNDANT_CONSTRAINTS: use expensive methods to
> +     eliminate all redundant constraints
> +
> +     #ifdef ELIMINATE_REDUNDANT_CONSTRAINTS
> +     if (!omega_eliminate_redundant (pb, true))
> +     return;
> +     #endif
> +  */
> +

Are you thinking of resurrecting this?  Perhaps make it a --params?


> +  bool *is_red_var = (bool *) xmalloc (OMEGA_MAX_VARS * sizeof (bool));
> +  bool *is_dead_var = (bool *) xmalloc (OMEGA_MAX_VARS * sizeof (bool));
> +  bool *is_dead_geq = (bool *) xmalloc (OMEGA_MAX_GEQS * sizeof (bool));

XNEW.

> +/* */
> +
> +static enum omega_result
> +parallel_splinter (omega_pb pb, int e, int diff,
> +		   enum omega_result desired_res)

Ahem ;)  Several functions are still missing documentation for their
arguments as well.


> +/* Helper function: solve equations one at a time.  */
> +
> +static enum omega_result
> +omega_solve_geq (omega_pb pb, enum omega_result desired_res)
> +{

Another long and cryptic function.  Can it be factored or at least
heavily commented?

> +  /* 
> +     #ifdef clearForwardingPointers 
> +     for (i = 1; i <= pb->num_vars; i++)
> +     if (!omega_wildcard_p (pb, i))
> +     pb->forwarding_address[pb->var[i]] = 0; 
> +     #endif
> +  */
> +

Same question as before.  If this is not coming back, better take it out.

> +  /* Allocate and initialize PB.  */
> +  pb = (omega_pb) xcalloc (1, sizeof (struct omega_pb));
> +  pb->var = (int *) xcalloc (OMEGA_MAX_VARS + 2, sizeof (int));
> +  pb->forwarding_address = (int *) xcalloc (OMEGA_MAX_VARS + 2, sizeof (int));

XCNEW.