* doc/loop.texi: Document the Omega linear constraints solver.

	* 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, and 
	omega-eliminate-redundant-constraints.
	* 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,
	PARAM_OMEGA_ELIMINATE_REDUNDANT_CONSTRAINTS): New.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@122749 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 30 insertions, 0 deletions

diff --git a/gcc/doc/loop.texi b/gcc/doc/loop.texi
index 3f0076e8f79..c904a873541 100644
--- a/gcc/doc/loop.texi
+++ b/gcc/doc/loop.texi
@@ -26,6 +26,7 @@ variable analysis and number of iterations analysis).
 * Number of iterations::	Number of iterations analysis.
 * Dependency analysis::		Data dependency analysis.
 * Lambda::			Linear loop transformations framework.
+* Omega::			A solver for linear programming problems.
 @end menu
 
 @node Loop representation
@@ -623,3 +624,32 @@ Given a transformed loopnest, conversion back into gcc IR is done by
 @code{lambda_loopnest_to_gcc_loopnest}.  This function will modify the
 loops so that they match the transformed loopnest.
 
+
+@node Omega
+@section Omega a solver for linear programming problems
+@cindex Omega a solver for linear programming problems
+
+The data dependence analysis contains several solvers triggered
+sequentially from the less complex ones to the more sophisticated.
+For ensuring the consistency of the results of these solvers, a data
+dependence check pass has been implemented based on two different
+solvers.  The second method that has been integrated to GCC is based
+on the Omega dependence solver, written in the 1990's by William Pugh
+and David Wonnacott.  Data dependence tests can be formulated using a
+subset of the Presburger arithmetics that can be translated to linear
+constraint systems.  These linear constraint systems can then be
+solved using the Omega solver.
+
+The Omega solver is using Fourier-Motzkin's algorithm for variable
+elimination: a linear constraint system containing @code{n} variables
+is reduced to a linear constraint system with @code{n-1} variables.
+The Omega solver can also be used for solving other problems that can
+be expressed under the form of a system of linear equalities and
+inequalities.  The Omega solver is known to have an exponential worst
+case, also known under the name of ``omega nightmare'' in the
+literature, but in practice, the omega test is known to be efficient
+for the common data dependence tests.
+
+The interface used by the Omega solver for describing the linear
+programming problems is described in @file{omega.h}, and the solver is
+@code{omega_solve_problem}.