This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] tree level if-conversion for vectorizer
- From: Devang Patel <dpatel at apple dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Cc: Dorit Naishlos <DORIT at il dot ibm dot com>, Ayal Zaks <ZAKS at il dot ibm dot com>
- Date: Wed, 25 Aug 2004 19:23:21 -0700
- Subject: [PATCH] tree level if-conversion for vectorizer
This patch adds tree level if-conversion for vectorizer. This is the
first patch. Next patch (after couple of weeks) will add
auto-vectorizer support.
[ It is different from the one implemented in apple-ppc-branch in
following ways:
- This version is more restricted
- Does not need ssa renaming in the end
- In apple-ppc-branch if-converted loops are either vectorized or
discarded.
- In apple-ppc-branch companion vectorizer patch, vectorizes loop
using builtins. It is not yet ready for mainline. ]
Short description:
o Decide if loop is if-convertable or not.
o Walk all loop basic blocks in breadth first order (BFS order).
o Remove conditional statements (at the end of basic block)
and propogate condition into destination basic blcoks'
predicate list.
o Replace modify expression with conditional modify expression
using current basic block's condition.
o Merge all basic blocks
o Replace phi nodes with conditional modify expr
o Merge all basic blocks into header
This pass re-inserts COND_EXPR in statement list, but it does not
change gimplifier. Gimplifier continues to gimplify COND_EXPR as usual.
Here if-converted loops are supplied to later passes and code generator
so that they can take advantage of it. In my SPEC run, it does not
indicate performance degradation. If it is not desired than I can add
another patch to discard un-used if-converted loops (it'll need loop
versioning stuff from LNO).
At the moment, only statements inside loops are considered candidates.
It is possible to use this to if-convert simple
if-something1-else-something2 code that is not inside any loop. But,
right now focus is to help vectorizer.
While looking at if_converatable_loop_p(), you may feel like that it is
looking for any excuse it can find to not if-convert loop:-). And some
of the checks are redundant. The goal is to lift some of those
restrictions once vector conditional operation support is in.
Bootstrapped and tested on powerpc-darwin.
OK?
Thank you,
-
Devang
2004-08-25 Devang Patel <dpatel@apple.com>
* Makefile.in (OBJS-common): Add tree-if-conv.o
(tree-if-conv.o): New rule.
* cfgloop.c (flow_loop_exit_edges_find): Set EDGE_LOOP_EXIT
flag.
(get_loop_body_in_bfs_order): New.
* cfgloop.h (get_loop_body_in_bfs_order): New.
* expr.c (expand_expr_real_1): Handle COND_EXPR with void
operands.
* tree-flow.h (enum move_pos): Move here from ..
* tree-ssa-loop-im.c (enum move_pos): here.
(movement_possibility): Make externally visible.
* tree-gimple.c (is_gimple_stmt): Allow COND_EXPR.
* tree-optimize.c (init_tree_optimization_passes): New entry for
if conversion pass.
* tree-pass.h (pass_if_conversion): New.
* tree-ssa-loop.c (test_if_conversion): New.
(gate_tree_if_conversion): New.
(struct tree_opt_pass pass_if_conversion): New.
* tree-ssa-operands.c (build_ssa_operands): Handle MODIFY_EXPR
where
LHS is COND_EXPR.
(get_expr_operands): Same.
* tree-if-conv.c: New file.
testsuite:
* gcc.dg/tree-ssa/ifc-20040816-1.c: New test.
* gcc.dg/tree-ssa/ifc-20040816-2.c: New test.
Attachment:
ifc_mainline.take1.diff
Description: Binary data