This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [patch] for PR 18529


On Thu, 18 Nov 2004, Zdenek Dvorak wrote:
>
> 	* tree-ssa-loop-niter.c (number_of_iterations_cond): Fold the
> 	expressions before futher processing.

The change to number_of_iterations_cond is OK for mainline, but I'm
unhappy with the other changes to fold.


As mentioned by Zack, "subst" is a terrible function name.  A more
suitable function name might have been "fold_replace_tree" analogous
to "simplify_replace_rtx".  However, yet again I'm concerned that
potentially O(n^2) algorithms are unsuitable for "fold".

As you know, fold is called whilst building trees in the parser,
which means that "t" should be treated as potentially unbounded in
size.  Your "subst" however recursively traverses this entire tree
to perform its substituions.  Hence, yet again pathological expressions
such as "a == 1 && b == 2 && c == 3 && d == 4 && e == 5 && ..." can
result in exponential compile-time behaviour.

More importantly, fold doesn't normally ever have to worry about
constant propagation and copy propagation within a single expression
because the compiler has special-purpose tree-ssa passes to perform
exactly these optimizations!

Instead the correct place to handle this type of "custom" local
theorem proving is in tree-ssa-loop-niter.  Given that you have
a condition "x < y" and some additional information, such as "y == 0",
the best way to check whether the condition is always true or always
false is probably not to create the expression "y == 0 && x < y" and
coerce "fold" to perform the expensive (and otherwise unnessary)
logical inferences.



> +   if (!operand_equal_p (a1,
> + 			build2 (PLUS_EXPR, typea, a,
> + 				build_int_cst_type (typea, 1)), 0))
> +     return NULL_TREE;


This is much better written as

	if (TREE_CODE (a1) != PLUS_EXPR
	    || !integer_onep (TREE_OPERAND (a1, 1))
	    || !operand_equal_p (TREE_OPERAND (a1, 0), a, 0))
	  return NULL_TREE.

This avoids allocating tree nodes just to check that "a1 == a + 1".


Could you explain why PR/18529 isn't better resolved elsewhere in
the compiler?

Roger
--


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]