This is the mail archive of the
mailing list for the GCC project.
Re: [patch] for PR 18529
- From: Roger Sayle <roger at eyesopen dot com>
- To: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Thu, 18 Nov 2004 20:28:01 -0700 (MST)
- Subject: 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)
> + 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))
This avoids allocating tree nodes just to check that "a1 == a + 1".
Could you explain why PR/18529 isn't better resolved elsewhere in