From 40923b202de784a0554d6a084464da3c1be4d976 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Fri, 3 Sep 2004 20:27:01 -0700 Subject: [PATCH] Tree level if-conversion for vectorizer. * 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. * tree-flow.h (enum move_pos): Move here from .. * tree-ssa-loop-im.c (enum move_pos): here. (movement_possibility): Make externally visible. * tree-optimize.c (init_tree_optimization_passes): New entry for if conversion pass. * tree-pass.h (pass_if_conversion): New. * tree-ssa-operands.c (get_expr_operands): Handle COND_EXPR. * tree-if-conv.c: New file. * doc/passes.texi: Document tree if-conversion pass. * doc/tree-ssa.texi: Same. testsuite: * gcc.dg/tree-ssa/ifc-20040816-1.c: New test. * gcc.dg/tree-ssa/ifc-20040816-2.c: New test. From-SVN: r87073 --- gcc/ChangeLog | 18 + gcc/Makefile.in | 6 +- gcc/cfgloop.c | 59 +- gcc/cfgloop.h | 1 + gcc/doc/passes.texi | 9 + gcc/doc/tree-ssa.texi | 3 + gcc/testsuite/ChangeLog | 5 + gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-1.c | 36 + gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-2.c | 37 + gcc/tree-flow.h | 16 + gcc/tree-if-conv.c | 1102 ++++++++++++++++++++++++ gcc/tree-optimize.c | 1 + gcc/tree-pass.h | 1 + gcc/tree-ssa-loop-im.c | 12 +- gcc/tree-ssa-operands.c | 7 +- 15 files changed, 1299 insertions(+), 14 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-2.c create mode 100644 gcc/tree-if-conv.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 743aad8..30a50be 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,21 @@ +2004-09-03 Devang Patel + + * 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. + * tree-flow.h (enum move_pos): Move here from .. + * tree-ssa-loop-im.c (enum move_pos): here. + (movement_possibility): Make externally visible. + * tree-optimize.c (init_tree_optimization_passes): New entry for + if conversion pass. + * tree-pass.h (pass_if_conversion): New. + * tree-ssa-operands.c (get_expr_operands): Handle COND_EXPR. + * tree-if-conv.c: New file. + * doc/passes.texi: Document tree if-conversion pass. + * doc/tree-ssa.texi: Same. + 2004-09-03 H.J. Lu PR target/14925: diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 5990d2a..887b30f 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -887,7 +887,6 @@ C_AND_OBJC_OBJS = attribs.o c-errors.o c-lex.o c-pragma.o c-decl.o c-typeck.o \ C_OBJS = c-parse.o c-lang.o stub-objc.o $(C_AND_OBJC_OBJS) # Language-independent object files. - OBJS-common = \ tree-chrec.o tree-scalar-evolution.o tree-data-ref.o \ tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o \ @@ -900,6 +899,7 @@ OBJS-common = \ tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \ tree-ssa-loop-niter.o tree-ssa-loop-manip.o tree-ssa-threadupdate.o \ tree-vectorizer.o tree-ssa-loop-ivcanon.o tree-ssa-propagate.o \ + tree-if-conv.o \ alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \ cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \ cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \ @@ -1688,6 +1688,10 @@ tree-tailcall.o : tree-tailcall.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ tree-nested.o: tree-nested.c $(CONFIG_H) $(SYSTEM_H) $(TM_H) $(TREE_H) \ $(RTL_H) $(TM_P_H) function.h tree-dump.h tree-inline.h tree-iterator.h \ tree-gimple.h cgraph.h $(EXPR_H) langhooks.h $(GGC_H) gt-tree-nested.h +tree-if-conv.o: tree-if-conv.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ + $(TREE_H) flags.h $(TIMEVAR_H) varray.h $(BASIC_BLOCK_H) $(TREE_FLOW_H) \ + cfgloop.h $(RTL_H) c-common.h tree-chrec.h tree-data-ref.h \ + tree-scalar-evolution.h tree-pass.h tree-iterator.o : tree-iterator.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \ coretypes.h $(GGC_H) tree-iterator.h tree-gimple.h gt-tree-iterator.h tree-dfa.o : tree-dfa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index b5553d2..892b70d 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -315,7 +315,10 @@ flow_loop_exit_edges_find (struct loop *loop) basic_block dest = e->dest; if (!flow_bb_inside_loop_p (loop, dest)) - loop->exit_edges[num_exits++] = e; + { + e->flags |= EDGE_LOOP_EXIT; + loop->exit_edges[num_exits++] = e; + } } } free (bbs); @@ -1085,6 +1088,60 @@ get_loop_body_in_dom_order (const struct loop *loop) return tovisit; } +/* Get body of a LOOP in breadth first sort order. */ + +basic_block * +get_loop_body_in_bfs_order (const struct loop *loop) +{ + basic_block *blocks; + basic_block bb; + bitmap visited; + unsigned int i = 0; + unsigned int vc = 1; + + if (!loop->num_nodes) + abort (); + + if (loop->latch == EXIT_BLOCK_PTR) + abort (); + + blocks = xcalloc (loop->num_nodes, sizeof (basic_block)); + visited = BITMAP_XMALLOC (); + + bb = loop->header; + while (i < loop->num_nodes) + { + edge e; + + if (!bitmap_bit_p (visited, bb->index)) + { + /* This basic block is now visited */ + bitmap_set_bit (visited, bb->index); + blocks[i++] = bb; + } + + for (e = bb->succ; e; e = e->succ_next) + { + if (flow_bb_inside_loop_p (loop, e->dest)) + { + if (!bitmap_bit_p (visited, e->dest->index)) + { + bitmap_set_bit (visited, e->dest->index); + blocks[i++] = e->dest; + } + } + } + + if (i < vc) + abort (); + + bb = blocks[vc++]; + } + + BITMAP_XFREE (visited); + return blocks; +} + /* Gets exit edges of a LOOP, returning their number in N_EDGES. */ edge * get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges) diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 3dce20a..60c80ce 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -272,6 +272,7 @@ extern unsigned get_loop_level (const struct loop *); /* Loops & cfg manipulation. */ extern basic_block *get_loop_body (const struct loop *); extern basic_block *get_loop_body_in_dom_order (const struct loop *); +extern basic_block *get_loop_body_in_bfs_order (const struct loop *); extern edge *get_loop_exit_edges (const struct loop *, unsigned *); extern unsigned num_loop_branches (const struct loop *); diff --git a/gcc/doc/passes.texi b/gcc/doc/passes.texi index 9af3659..16de6ea 100644 --- a/gcc/doc/passes.texi +++ b/gcc/doc/passes.texi @@ -385,6 +385,15 @@ The optimizations also use various utility functions contained in @file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and @file{cfgloopmanip.c}. +@item Tree level if-conversion for vectorizer + +This pass applies if-conversion to simple loops to help vectorizer. +We identify if convertable loops, if-convert statements and merge +basic blocks in one big block. The idea is to present loop in such +form so that vectorizer can have one to one mapping between statements +and available vector operations. This patch re-introduces COND_EXPR +at GIMPLE level. This pass is located in @file{tree-if-conv.c}. + @item Conditional constant propagation This pass relaxes a lattice of values in order to identify those diff --git a/gcc/doc/tree-ssa.texi b/gcc/doc/tree-ssa.texi index e54383a..1c88e9f 100644 --- a/gcc/doc/tree-ssa.texi +++ b/gcc/doc/tree-ssa.texi @@ -260,6 +260,9 @@ becomes a = T1; @end smallexample +Tree level if-conversion pass re-introduces @code{?:} expression, if appropriate. +It is used to vectorize loops with conditions using vector conditional operations. + Note that in GIMPLE, @code{if} statements are also represented using @code{COND_EXPR}, as described below. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 8cae9a8..276c31d 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2004-09-03 Devang Patel + + * gcc.dg/tree-ssa/ifc-20040816-1.c: New test. + * gcc.dg/tree-ssa/ifc-20040816-2.c: New test. + 2004-09-03 Jan Beulich * g++.dg/abi/bitfield5.C: Use -mno-ms-bitfields. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-1.c new file mode 100644 index 0000000..2290563 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-1.c @@ -0,0 +1,36 @@ +/* { dg-do compile } */ +/* { dg-options "-c -O2 -fdump-tree-ifcvt-stats" { target *-*-* } } */ + +#include +#include + +#define N 16 +#define MAX 42 + +extern void abort(void); + +int main1 () +{ + int A[N] = {36,39,42,45,43,32,21,12,23,34,45,56,67,78,89,11}; + + int i, j; + + for (i = 0; i < N; i++) + { + j = A[i]; + A[i] = ( j >= MAX ? MAX : 0); + } + + /* check results: */ + for (i = 0; i < N; i++) + { + if (A[i] > MAX) + abort (); + } + + return 0; +} + + + +/* { dg-final { scan-tree-dump-times "Applying if-conversion" 1 "ifcvt" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-2.c new file mode 100644 index 0000000..47ac652 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-2.c @@ -0,0 +1,37 @@ +/* { dg-do compile } */ +/* { dg-options "-c -O2 -fdump-tree-ifcvt-stats" { target *-*-* } } */ + +typedef float afloat __attribute__ ((__aligned__(16))); +void foo(const afloat * __restrict__ zr_in, + const afloat * __restrict__ zi_in, + const afloat * __restrict__ zk_in, + afloat * __restrict__ zr_out, + afloat * __restrict__ zi_out, + afloat * __restrict__ zk_out, + float cr, float ci) +{ + unsigned int pi; + float tmp_r, tmp_i, tmp_k; + for (pi = 0; pi < (512)*(512); pi++) { + float zr = zr_in[pi]; + float zi = zi_in[pi]; + float zk = zk_in[pi]; + + if (zr*zr + zi*zi >= 4.0f) { + tmp_r = zr; + tmp_i = zi; + tmp_k = zk; + } else { + tmp_r = (zr*zr - zi*zi + cr); + tmp_i = (2 * zr * zi + ci); + tmp_k = zk + 1.0f; + } + zr_out[pi] = tmp_r; + zi_out[pi] = tmp_i; + zk_out[pi] = tmp_k; + } +} + + +/* { dg-final { scan-tree-dump-times "Applying if-conversion" 1 "ifcvt" } } */ + diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index a82c90b..19d0b14 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -654,6 +654,22 @@ bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *); void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator *, bool, tree *, tree *); +/* In tree-ssa-loop-im.c */ +/* The possibilities of statement movement. */ + +enum move_pos + { + MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */ + MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement + become executed -- memory accesses, ... */ + MOVE_POSSIBLE /* Unlimited movement. */ + }; +extern enum move_pos movement_possibility (tree); + +/* In tree-if-conv.c */ +bool tree_if_conversion (struct loop *, bool); + + /* In tree-flow-inline.h */ static inline int phi_arg_from_edge (tree, edge); static inline bool is_call_clobbered (tree); diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c new file mode 100644 index 0000000..e435512 --- /dev/null +++ b/gcc/tree-if-conv.c @@ -0,0 +1,1102 @@ +/* If-conversion for vectorizer. + Copyright (C) 2004 Free Software Foundation, Inc. + Contributed by Devang Patel + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +/* This pass implements tree level if-conversion transformation of loops. + Initial goal is to help vectorizer vectorize loops with conditions. + + A short description of if-conversion: + + o Decide if a 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 + + Sample transformation: + + INPUT + ----- + + # i_23 = PHI <0(0), i_18(10)>; + :; + j_15 = A[i_23]; + if (j_15 > 41) goto ; else goto ; + + :; + goto (); + + :; + + # iftmp.2_4 = PHI <0(8), 42(2)>; + :; + A[i_23] = iftmp.2_4; + i_18 = i_23 + 1; + if (i_18 <= 15) goto ; else goto ; + + :; + goto (); + + :; + + OUTPUT + ------ + + # i_23 = PHI <0(0), i_18(10)>; + :; + j_15 = A[i_23]; + + :; + iftmp.2_4 = j_15 > 41 ? 42 : 0; + A[i_23] = iftmp.2_4; + i_18 = i_23 + 1; + if (i_18 <= 15) goto ; else goto ; + + :; + goto (); + + :; +*/ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "errors.h" +#include "tree.h" +#include "c-common.h" +#include "flags.h" +#include "timevar.h" +#include "varray.h" +#include "rtl.h" +#include "basic-block.h" +#include "diagnostic.h" +#include "tree-flow.h" +#include "tree-dump.h" +#include "cfgloop.h" +#include "tree-chrec.h" +#include "tree-data-ref.h" +#include "tree-scalar-evolution.h" +#include "tree-pass.h" +#include "target.h" + +/* local function prototypes */ +static void main_tree_if_conversion (void); +static tree tree_if_convert_stmt (struct loop *loop, tree, tree, + block_stmt_iterator *); +static void tree_if_convert_cond_expr (struct loop *, tree, tree, + block_stmt_iterator *); +static bool if_convertable_phi_p (struct loop *, basic_block, tree); +static bool if_convertable_modify_expr_p (struct loop *, basic_block, tree); +static bool if_convertable_stmt_p (struct loop *, basic_block, tree); +static bool if_convertable_bb_p (struct loop *, basic_block, bool); +static bool if_convertable_loop_p (struct loop *, bool); +static void add_to_predicate_list (basic_block, tree); +static tree add_to_dst_predicate_list (struct loop * loop, tree, tree, tree, + block_stmt_iterator *); +static void clean_predicate_lists (struct loop *loop); +static bool find_phi_replacement_condition (basic_block, tree *, + block_stmt_iterator *); +static void replace_phi_with_cond_modify_expr (tree, tree, bool, + block_stmt_iterator *); +static void process_phi_nodes (struct loop *); +static void combine_blocks (struct loop *); +static tree ifc_temp_var (tree, tree); +static bool pred_blocks_visited_p (basic_block, bitmap *); +static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop); +static bool bb_with_exit_edge_p (basic_block); + +/* List of basic blocks in if-conversion-suitable order. */ +static basic_block *ifc_bbs; + +/* Main entry point. + Apply if-conversion to the LOOP. Return true if successful otherwise return + false. If false is returned then loop remains unchanged. + FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used + for vectorizer or not. If it is used for vectorizer, additional checks are + used. (Vectorization checks are not yet imlemented). */ + +bool +tree_if_conversion (struct loop *loop, bool for_vectorizer) +{ + basic_block bb; + block_stmt_iterator itr; + tree cond; + unsigned int i; + + ifc_bbs = NULL; + + /* if-conversion is not appropriate for all loops. First, check if loop is + if-convertable or not. */ + if (!if_convertable_loop_p (loop, for_vectorizer)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file,"-------------------------\n"); + if (ifc_bbs) + { + free (ifc_bbs); + ifc_bbs = NULL; + } + free_dominance_info (CDI_POST_DOMINATORS); + free_df (); + return false; + } + + cond = NULL_TREE; + + /* Do actual work now. */ + for (i = 0; i < loop->num_nodes; i++) + { + bb = ifc_bbs [i]; + + /* Update condition using predicate list. */ + cond = bb->aux; + + /* Process all statements in this basic block. + Remove conditional expresion, if any, and annotate + destination basic block(s) appropriately. */ + for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */) + { + tree t = bsi_stmt (itr); + cond = tree_if_convert_stmt (loop, t, cond, &itr); + if (!bsi_end_p (itr)) + bsi_next (&itr); + } + + /* If current bb has only one successor, then consider it as an + unconditional goto. */ + if (bb->succ && !bb->succ->succ_next) + { + basic_block bb_n = bb->succ->dest; + if (cond != NULL_TREE) + add_to_predicate_list (bb_n, cond); + cond = NULL_TREE; + } + } + + /* Now, all statements are if-converted and basic blocks are + annotated appropriately. Combine all basic block into one huge + basic block. */ + combine_blocks (loop); + + /* clean up */ + clean_predicate_lists (loop); + free (ifc_bbs); + ifc_bbs = NULL; + free_df (); + + return true; +} + +/* if-convert stmt T which is part of LOOP. + If T is a MODIFY_EXPR than it is converted into conditional modify + expression using COND. For conditional expressions, add condition in the + destination basic block's predicate list and remove conditional + expression itself. BSI is the iterator used to traverse statements of + loop. It is used here when it is required to delete current statement. */ + +static tree +tree_if_convert_stmt (struct loop * loop, tree t, tree cond, + block_stmt_iterator *bsi) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "------if-convert stmt\n"); + print_generic_stmt (dump_file, t, TDF_SLIM); + print_generic_stmt (dump_file, cond, TDF_SLIM); + } + + switch (TREE_CODE (t)) + { + /* Labels are harmless here. */ + case LABEL_EXPR: + break; + + case MODIFY_EXPR: + /* This modify_expr is killing previous value of LHS. Appropriate value will + be selected by PHI node based on condition. It is possible that before + this transformation, PHI nodes was selecting default value and now it will + use this new value. This is OK because it does not change validity the + program. */ + break; + + case GOTO_EXPR: + /* Unconditional goto */ + add_to_predicate_list (bb_for_stmt (TREE_OPERAND (t, 1)), cond); + bsi_remove (bsi); + cond = NULL_TREE; + break; + + case COND_EXPR: + /* Update destination blocks' predicate list and remove this + condition expression. */ + tree_if_convert_cond_expr (loop, t, cond, bsi); + cond = NULL_TREE; + break; + + default: + abort (); + break; + } + return cond; +} + +/* STMT is COND_EXPR. Update two destination's predicate list. + Remove COND_EXPR, if it is not the loop exit condition. Otherwise + update loop exit condition appropriatly. BSI is the iterator + used to traverse statement list. STMT is part of loop LOOP. */ + +static void +tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond, + block_stmt_iterator *bsi) +{ + tree then_clause, else_clause, c, new_cond; + new_cond = NULL_TREE; + +#ifdef ENABLE_CHECKING + if (TREE_CODE (stmt) != COND_EXPR) + abort (); +#endif + + c = TREE_OPERAND (stmt, 0); + then_clause = TREE_OPERAND (stmt, 1); + else_clause = TREE_OPERAND (stmt, 2); + + /* Create temp. for condition. */ + if (!is_gimple_reg (c)) + { + tree new_stmt; + new_stmt = ifc_temp_var (TREE_TYPE (c), unshare_expr (c)); + bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); + c = TREE_OPERAND (new_stmt, 0); + } + + /* Add new condition into destination's predicate list. */ + if (then_clause) + /* if 'c' is true then then_clause is reached. */ + new_cond = add_to_dst_predicate_list (loop, then_clause, cond, c, bsi); + + if (else_clause) + { + /* if 'c' is false then else_clause is reached. */ + tree c2 = build1 (TRUTH_NOT_EXPR, + boolean_type_node, + unshare_expr (c)); + add_to_dst_predicate_list (loop, else_clause, cond, c2, bsi); + } + + /* Now this conditional statement is redundent. Remove it. + But, do not remove exit condition! Update exit condition + using new condition. */ + if (!bb_with_exit_edge_p (bb_for_stmt (stmt))) + { + bsi_remove (bsi); + cond = NULL_TREE; + } + else if (new_cond != NULL_TREE) + { + TREE_OPERAND (stmt, 0) = new_cond; + modify_stmt (stmt); + } + return; +} + +/* Return true, iff PHI is if-convertable. PHI is part of loop LOOP + and it belongs to basic block BB. + PHI is not if-convertable + - if it has more than 2 arguments. + - Virtual PHI is immediately used in another PHI node. */ + +static bool +if_convertable_phi_p (struct loop *loop, basic_block bb, tree phi) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "-------------------------\n"); + print_generic_stmt (dump_file, phi, TDF_SLIM); + } + + if (bb != loop->header && PHI_NUM_ARGS (phi) != 2) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "More than two phi node args.\n"); + return false; + } + + if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) + { + int j; + dataflow_t df = get_immediate_uses (phi); + int num_uses = num_immediate_uses (df); + for (j = 0; j < num_uses; j++) + { + tree use = immediate_use (df, j); + if (TREE_CODE (use) == PHI_NODE) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Difficult to handle this virtual phi.\n"); + return false; + } + } + } + + return true; +} + +/* Return true, if M_EXPR is if-convertable. + MODIFY_EXPR is not if-convertable if, + - It is not movable. + - It could trap. + - LHS is not var decl. + MODIFY_EXPR is part of block BB, which is inside loop LOOP. +*/ + +static bool +if_convertable_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "-------------------------\n"); + print_generic_stmt (dump_file, m_expr, TDF_SLIM); + } + + /* Be conservative and do not handle immovable expressions. */ + if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "stmt is movable. Don't take risk\n"); + return false; + } + + /* See if it needs speculative loading or not. */ + if (bb != loop->header + && tree_could_trap_p (TREE_OPERAND (m_expr, 1))) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "tree could trap...\n"); + return false; + } + + if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "CALL_EXPR \n"); + return false; + } + + if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME + && bb != loop->header + && !bb_with_exit_edge_p (bb)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "LHS is not var\n"); + print_generic_stmt (dump_file, m_expr, TDF_SLIM); + } + return false; + } + + + return true; +} + +/* Return true, iff STMT is if-convertable. + Statement is if-convertable if, + - It is if-converatable MODIFY_EXPR + - IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR. + STMT is inside block BB, which is inside loop LOOP. */ + +static bool +if_convertable_stmt_p (struct loop *loop, basic_block bb, tree stmt) +{ + switch (TREE_CODE (stmt)) + { + case LABEL_EXPR: + break; + + case MODIFY_EXPR: + + if (!if_convertable_modify_expr_p (loop, bb, stmt)) + return false; + break; + + case GOTO_EXPR: + case COND_EXPR: + break; + + default: + /* Don't know what to do with 'em so don't do anything. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "don't know what to do\n"); + print_generic_stmt (dump_file, stmt, TDF_SLIM); + } + return false; + break; + } + + return true; +} + +/* Return true, iff BB is if-convertable. + Note: This routine does _not_ check basic block statements and phis. + Basic block is not if-converatable if, + - Basic block is non-empty and it is after exit block (in BFS order). + - Basic block is after exit block but before latch. + - Basic block edge(s) is not normal. + EXIT_BB_SEEN is true if basic block with exit edge is already seen. + BB is inside loop LOOP. */ + +static bool +if_convertable_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen) +{ + edge e; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "----------[%d]-------------\n", bb->index); + + if (exit_bb_seen) + { + if (bb != loop->latch) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "basic block after exit bb but before latch\n"); + return false; + } + else if (!empty_block_p (bb)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "non empty basic block after exit bb\n"); + return false; + } + } + + /* Be less adveturous and handle only normal edges. */ + for (e = bb->succ; e; e = e->succ_next) + if (e->flags & + (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file,"Difficult to handle edges\n"); + return false; + } + + return true; +} + +/* Return true, iff LOOP is if-convertable. + LOOP is if-convertable if, + - It is innermost. + - It has two or more basic blocks. + - It has only one exit. + - Loop header is not the exit edge. + - If its basic blocks and phi nodes are if convertable. See above for + more info. + FOR_VECTORIZER enables vectorizer specific checks. For example, support + for vector conditions, data dependency checks etc.. (Not implemented yet). */ + +static bool +if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) +{ + tree phi; + basic_block bb; + block_stmt_iterator itr; + unsigned int i; + edge e; + bool exit_bb_seen = false; + + /* Handle only inner most loop. */ + if (!loop || loop->inner) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "not inner most loop\n"); + return false; + } + + flow_loop_scan (loop, LOOP_ALL); + + /* If only one block, no need for if-conversion. */ + if (loop->num_nodes <= 2) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "less thant 2 basic blocks\n"); + return false; + } + + /* More than one loop exit is too much to handle. */ + if (loop->num_exits > 1) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "multiple exits\n"); + return false; + } + + /* ??? Check target's vector conditional operation support for vectorizer. */ + + /* If one of the loop header's edge is exit edge then do not apply + if-conversion. */ + for (e = loop->header->succ; e; e = e->succ_next) + if ( e->flags & EDGE_LOOP_EXIT) + return false; + + compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL); + + calculate_dominance_info (CDI_DOMINATORS); + calculate_dominance_info (CDI_POST_DOMINATORS); + + /* Allow statements that can be handled during if-conversion. */ + ifc_bbs = get_loop_body_in_if_conv_order (loop); + if (!ifc_bbs) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file,"Irreducible loop\n"); + free_dominance_info (CDI_POST_DOMINATORS); + return false; + } + + for (i = 0; i < loop->num_nodes; i++) + { + bb = ifc_bbs[i]; + + if (!if_convertable_bb_p (loop, bb, exit_bb_seen)) + return false; + + /* Check statements. */ + for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr)) + if (!if_convertable_stmt_p (loop, bb, bsi_stmt (itr))) + return false; + /* ??? Check data dependency for vectorizer. */ + + /* What about phi nodes ? */ + for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + if (!if_convertable_phi_p (loop, bb, phi)) + return false; + + if (bb_with_exit_edge_p (bb)) + exit_bb_seen = true; + } + + /* OK. Did not find any potential issues so go ahead in if-convert + this loop. Now there is no looking back. */ + if (dump_file) + fprintf (dump_file,"Applying if-conversion\n"); + + free_dominance_info (CDI_POST_DOMINATORS); + return true; +} + +/* Add condition COND into predicate list of basic block BB. */ + +static void +add_to_predicate_list (basic_block bb, tree new_cond) +{ + tree cond = bb->aux; + + if (cond) + cond = fold (build (TRUTH_OR_EXPR, boolean_type_node, + unshare_expr (cond), new_cond)); + else + cond = new_cond; + + bb->aux = cond; +} + +/* Add condition COND into DST's predicate list. PREV_COND is + existing condition. */ + +static tree +add_to_dst_predicate_list (struct loop * loop, tree dst, + tree prev_cond, tree cond, + block_stmt_iterator *bsi) +{ + basic_block bb; + tree new_cond = NULL_TREE; + +#ifdef ENABLE_CHECKING + if (TREE_CODE (dst) != GOTO_EXPR) + abort (); +#endif + bb = label_to_block (TREE_OPERAND (dst, 0)); + if (!flow_bb_inside_loop_p (loop, bb)) + return NULL_TREE; + + if (prev_cond == boolean_true_node || !prev_cond) + new_cond = unshare_expr (cond); + else + { + tree tmp_stmt; + /* new_cond == prev_cond AND cond */ + tree tmp = build (TRUTH_AND_EXPR, boolean_type_node, + unshare_expr (prev_cond), cond); + tmp_stmt = ifc_temp_var (boolean_type_node, tmp); + bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT); + new_cond = TREE_OPERAND (tmp_stmt, 0); + } + add_to_predicate_list (bb, new_cond); + return new_cond; +} + +/* During if-conversion aux field from basic block is used to hold predicate + list. Clean each basic block's predicate list for the given LOOP. */ + +static void +clean_predicate_lists (struct loop *loop) +{ + unsigned int i; + + for (i = 0; i < loop->num_nodes; i++) + ifc_bbs[i]->aux = NULL; +} + +/* Basic block BB has two predecessors. Using predecessor's aux field, set + appropriate condition COND for the PHI node replacement. Return true if + phi arguments are condition is selected from second predecessor. */ + +static bool +find_phi_replacement_condition (basic_block bb, tree *cond, + block_stmt_iterator *bsi) +{ + edge e; + basic_block p1 = NULL; + basic_block p2 = NULL; + bool switch_args = false; + tree tmp_cond; + + for (e = bb->pred; e; e = e->pred_next) + { + if (p1 == NULL) + p1 = e->src; + else if (p2 == NULL) + p2 = e->src; + else + /* More than two predecessors. This is not expected. */ + abort (); + } + + /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ + tmp_cond = p1->aux; + if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) + { + *cond = p2->aux; + switch_args = true; + } + else + { + *cond = p1->aux; + switch_args = false; + } + + /* Create temp. for the condition. Vectorizier prefers to have gimple + value as condition. Various targets use different means to communicate + condition in vector compare operation. Using gimple value allows compiler + to emit vector compare and select RTL without exposing compare's result. */ + if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond)) + { + tree new_stmt; + + new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); + bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT); + bsi_next (bsi); + *cond = TREE_OPERAND (new_stmt, 0); + } + +#ifdef ENABLE_CHECKING + if (*cond == NULL_TREE) + abort (); +#endif + + return switch_args; +} + + +/* Replace PHI node with conditional modify expr using COND. + This routine does not handle PHI nodes with more than two arguments. + For example, + S1: A = PHI num_nodes; + unsigned int i; + + /* Replace phi nodes with cond. modify expr. */ + for (i = 1; i < orig_loop_num_nodes; i++) + { + tree phi, cond; + block_stmt_iterator bsi; + bool switch_args = false; + bb = ifc_bbs[i]; + + if (bb == loop->header || bb == loop->latch) + continue; + + phi = phi_nodes (bb); + bsi = bsi_start (bb); + + /* BB has two predecessors. Using predecessor's aux field, set + appropriate condition for the PHI node replacement. */ + if (phi) + switch_args = find_phi_replacement_condition (bb, &cond, &bsi); + + while (phi) + { + tree next = TREE_CHAIN (phi); + replace_phi_with_cond_modify_expr (phi, cond, switch_args, &bsi); + release_phi_node (phi); + phi = next; + } + bb_ann (bb)->phi_nodes = NULL; + } + return; +} + +/* Combine all basic block from the given LOOP into one or two super + basic block. Replace PHI nodes with conditional modify expression. */ + +static void +combine_blocks (struct loop *loop) +{ + basic_block bb, exit_bb, merge_target_bb; + unsigned int orig_loop_num_nodes = loop->num_nodes; + unsigned int i; + + /* Process phi nodes to prepare blocks for merge. */ + process_phi_nodes (loop); + + exit_bb = NULL; + + /* Merge basic blocks */ + merge_target_bb = loop->header; + for (i = 1; i < orig_loop_num_nodes; i++) + { + edge e; + block_stmt_iterator bsi; + tree_stmt_iterator last; + + bb = ifc_bbs[i]; + + if (bb == loop->latch) + continue; + + if (!exit_bb && bb_with_exit_edge_p (bb)) + exit_bb = bb; + + if (bb == exit_bb) + { + edge new_e; + + /* Connect this node with loop header. */ + new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU); + set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]); + + if (exit_bb != loop->latch) + { + /* Redirect non-exit edge to loop->latch. */ + for (e = bb->succ; e; e = e->succ_next) + if (!(e->flags & EDGE_LOOP_EXIT)) + { + redirect_edge_and_branch (e, loop->latch); + set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb); + } + } + continue; + } + + /* It is time to remove this basic block. First remove edges. */ + while (bb->succ != NULL) + ssa_remove_edge (bb->succ); + while (bb->pred != NULL) + ssa_remove_edge (bb->pred); + + /* Remove labels and make stmts member of loop->header. */ + for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) + { + if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR) + bsi_remove (&bsi); + else + { + set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb); + bsi_next (&bsi); + } + } + + /* Update stmt list. */ + last = tsi_last (merge_target_bb->stmt_list); + tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT); + bb->stmt_list = NULL; + + /* Update dominator info. */ + if (dom_computed[CDI_DOMINATORS]) + delete_from_dominance_info (CDI_DOMINATORS, bb); + if (dom_computed[CDI_POST_DOMINATORS]) + delete_from_dominance_info (CDI_POST_DOMINATORS, bb); + + /* Remove basic block. */ + remove_bb_from_loops (bb); + expunge_block (bb); + } +} + +/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP + to the new variable. */ + +static tree +ifc_temp_var (tree type, tree exp) +{ + const char *name = "_ifc_"; + tree var, stmt, new_name; + + if (is_gimple_reg (exp)) + return exp; + + /* Create new temporary variable. */ + var = create_tmp_var (type, name); + add_referenced_tmp_var (var); + + /* Build new statement to assigne EXP to new variable. */ + stmt = build (MODIFY_EXPR, type, var, exp); + + /* Get SSA name for the new variable and set make new statement + its definition statment. */ + new_name = make_ssa_name (var, stmt); + TREE_OPERAND (stmt, 0) = new_name; + SSA_NAME_DEF_STMT (new_name) = stmt; + + return stmt; +} + + +/* Return TRUE iff, all pred blocks of BB are visited. + Bitmap VISITED keeps history of visited blocks. */ + +static bool +pred_blocks_visited_p (basic_block bb, bitmap *visited) +{ + edge e; + for (e = bb->pred; e; e = e->pred_next) + if (!bitmap_bit_p (*visited, e->src->index)) + return false; + + return true; +} + +/* Get body of a LOOP in suitable order for if-conversion. + It is caller's responsibility to deallocate basic block + list. If-conversion suitable order is, BFS order with one + additional constraint. Select block in BFS block, if all + pred are already selected. */ + +static basic_block * +get_loop_body_in_if_conv_order (const struct loop *loop) +{ + basic_block *blocks, *blocks_in_bfs_order; + basic_block bb; + bitmap visited; + unsigned int index = 0; + unsigned int visited_count = 0; + + if (!loop->num_nodes) + abort (); + + if (loop->latch == EXIT_BLOCK_PTR) + abort (); + + blocks = xcalloc (loop->num_nodes, sizeof (basic_block)); + visited = BITMAP_XMALLOC (); + + blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); + + index = 0; + while (index < loop->num_nodes) + { + bb = blocks_in_bfs_order [index]; + + if (bb->flags & BB_IRREDUCIBLE_LOOP) + { + free (blocks_in_bfs_order); + BITMAP_FREE (visited); + free (blocks); + return NULL; + } + if (!bitmap_bit_p (visited, bb->index)) + { + if (pred_blocks_visited_p (bb, &visited) + || bb == loop->header) + { + /* This block is now visited. */ + bitmap_set_bit (visited, bb->index); + blocks[visited_count++] = bb; + } + } + index++; + if (index == loop->num_nodes + && visited_count != loop->num_nodes) + { + /* Not done yet. */ + index = 0; + } + } + free (blocks_in_bfs_order); + BITMAP_XFREE (visited); + return blocks; +} + +/* Return true if one of the basic block BB edge is loop exit. */ + +static bool +bb_with_exit_edge_p (basic_block bb) +{ + edge e; + bool exit_edge_found = false; + + for (e = bb->succ; e && !exit_edge_found ; e = e->succ_next) + if (e->flags & EDGE_LOOP_EXIT) + exit_edge_found = true; + + return exit_edge_found; +} + +/* Tree if-conversion pass management. */ + +static void +main_tree_if_conversion (void) +{ + unsigned i, loop_num; + struct loop *loop; + + if (!current_loops) + return; + + loop_num = current_loops->num; + for (i = 0; i < loop_num; i++) + { + loop = current_loops->parray[i]; + if (!loop) + continue; + + tree_if_conversion (loop, true); + } + +} + +static bool +gate_tree_if_conversion (void) +{ + return true; +} + +struct tree_opt_pass pass_if_conversion = +{ + "ifcvt", /* name */ + gate_tree_if_conversion, /* gate */ + main_tree_if_conversion, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + TODO_dump_func, /* todo_flags_start */ + TODO_dump_func + | TODO_verify_ssa + | TODO_verify_stmts + | TODO_verify_flow /* todo_flags_finish */ +}; + diff --git a/gcc/tree-optimize.c b/gcc/tree-optimize.c index f14f1b0..e3dcc95 100644 --- a/gcc/tree-optimize.c +++ b/gcc/tree-optimize.c @@ -368,6 +368,7 @@ init_tree_optimization_passes (void) NEXT_PASS (pass_loop_init); NEXT_PASS (pass_lim); NEXT_PASS (pass_iv_canon); + NEXT_PASS (pass_if_conversion); NEXT_PASS (pass_vectorize); NEXT_PASS (pass_complete_unroll); NEXT_PASS (pass_loop_done); diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 0609adc..0712a4e 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -110,6 +110,7 @@ extern struct tree_opt_pass pass_loop; extern struct tree_opt_pass pass_loop_init; extern struct tree_opt_pass pass_lim; extern struct tree_opt_pass pass_iv_canon; +extern struct tree_opt_pass pass_if_conversion; extern struct tree_opt_pass pass_vectorize; extern struct tree_opt_pass pass_complete_unroll; extern struct tree_opt_pass pass_loop_done; diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index c5de645..6aad731 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -47,16 +47,6 @@ struct depend struct depend *next; }; -/* The possibilities of statement movement. */ - -enum move_pos -{ - MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */ - MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement - become executed -- memory accesses, ... */ - MOVE_POSSIBLE /* Unlimited movement. */ -}; - /* The auxiliary data kept for each statement. */ struct lim_aux_data @@ -170,7 +160,7 @@ for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data) because it may trap), return MOVE_PRESERVE_EXECUTION. Otherwise return MOVE_IMPOSSIBLE. */ -static enum move_pos +enum move_pos movement_possibility (tree stmt) { tree lhs, rhs; diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c index a87d845..200f4b5 100644 --- a/gcc/tree-ssa-operands.c +++ b/gcc/tree-ssa-operands.c @@ -625,7 +625,6 @@ finalize_ssa_vuses (vuse_optype *old_ops_p) return vuse_ops; } - /* Return a new v_must_def operand vector for STMT, comparing to OLD_OPS_P. */ static v_must_def_optype @@ -1081,6 +1080,12 @@ get_expr_operands (tree stmt, tree *expr_p, int flags) get_call_expr_operands (stmt, expr); return; + case COND_EXPR: + get_expr_operands (stmt, &COND_EXPR_COND (expr), opf_none); + get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_none); + get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none); + return; + case MODIFY_EXPR: { int subflags; -- 2.7.4