* 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

2 files changed, 63 insertions, 0 deletions

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index f09b9b16aaf..6ecde2e5563 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -350,6 +350,7 @@ Objective-C and Objective-C++ Dialects}.
 -fvariable-expansion-in-unroller @gol
 -ftree-pre  -ftree-ccp  -ftree-dce -ftree-loop-optimize @gol
 -ftree-loop-linear -ftree-loop-im -ftree-loop-ivcanon -fivopts @gol
+-fcheck-data-deps @gol
 -ftree-dominator-opts -ftree-dse -ftree-copyrename -ftree-sink @gol
 -ftree-ch -ftree-sra -ftree-ter -ftree-fre -ftree-vectorize @gol
 -ftree-vect-loop-version -ftree-salias -fipa-pta -fweb @gol
@@ -5447,6 +5448,10 @@ at @option{-O} and higher.
 Perform linear loop transformations on tree.  This flag can improve cache
 performance and allow further loop optimizations to take place.
 
+@item -fcheck-data-deps
+Compare the results of several data dependence analyzers.  This option
+is used for debugging the data dependence analyzers.
+
 @item -ftree-loop-im
 Perform loop invariant motion on trees.  This pass moves only invariants that
 would be hard to handle at RTL level (function calls, operations that expand to
@@ -6450,6 +6455,34 @@ optimization when a new iv is added to the set.
 Bound on size of expressions used in the scalar evolutions analyzer.
 Large expressions slow the analyzer.
 
+@item omega-max-vars
+The maximum number of variables in an Omega constraint system.
+The default value is 128.
+
+@item omega-max-geqs
+The maximum number of inequalities in an Omega constraint system.
+The default value is 256.
+
+@item omega-max-eqs
+The maximum number of equalities in an Omega constraint system.
+The default value is 128.
+
+@item omega-max-wild-cards
+The maximum number of wildcard variables that the Omega solver will
+be able to insert.  The default value is 18.
+
+@item omega-hash-table-size
+The size of the hash table in the Omega solver.  The default value is
+550.
+
+@item omega-max-keys
+The maximal number of keys used by the Omega solver.  The default
+value is 500.
+
+@item omega-eliminate-redundant-constraints
+When set to 1, use expensive methods to eliminate all redundant
+constraints.  The default value is 0.
+
 @item vect-max-version-checks
 The maximum number of runtime checks that can be performed when doing
 loop versioning in the vectorizer.  See option ftree-vect-loop-version
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}.