? testsuite/gcc.dg/vect/vect-reduc-1.c ? testsuite/gcc.dg/vect/vect-reduc-2.c ? testsuite/gcc.dg/vect/vect-reduc-3.c cvs diff: Diffing . Index: tree-flow.h =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v retrieving revision 2.109 diff -c -3 -p -r2.109 tree-flow.h *** tree-flow.h 17 May 2005 20:28:22 -0000 2.109 --- tree-flow.h 26 May 2005 11:26:42 -0000 *************** struct tree_ann_common_d GTY(()) *** 121,126 **** --- 121,130 ---- /* Annotation type. */ enum tree_ann_type type; + /* Auxiliary info specific to a pass. At all times, this + should either point to valid data or be NULL. */ + PTR GTY ((skip (""))) aux; + /* The value handle for this expression. Used by GVN-PRE. */ tree GTY((skip)) value_handle; }; *************** struct stmt_ann_d GTY(()) *** 321,330 **** pass which needs statement UIDs. */ unsigned int uid; - /* Auxiliary info specific to a pass. At all times, this - should either point to valid data or be NULL. */ - PTR GTY ((skip (""))) aux; - /* Linked list of histograms for value-based profiling. This is really a struct histogram_value*. We use void* to avoid having to export that everywhere, and to avoid having to put it in GC memory. */ --- 325,330 ---- Index: tree-ssa-loop-im.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-im.c,v retrieving revision 2.41 diff -c -3 -p -r2.41 tree-ssa-loop-im.c *** tree-ssa-loop-im.c 12 May 2005 19:41:10 -0000 2.41 --- tree-ssa-loop-im.c 26 May 2005 11:26:43 -0000 *************** struct lim_aux_data *** 102,108 **** #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \ ? NULL \ ! : (struct lim_aux_data *) (stmt_ann (STMT)->aux)) /* Description of a memory reference location for store motion. */ --- 102,108 ---- #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \ ? NULL \ ! : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux)) /* Description of a memory reference location for store motion. */ *************** determine_invariantness_stmt (struct dom *** 631,637 **** stmt = stmt1; } ! stmt_ann (stmt)->aux = xcalloc (1, sizeof (struct lim_aux_data)); LIM_DATA (stmt)->always_executed_in = outermost; if (maybe_never && pos == MOVE_PRESERVE_EXECUTION) --- 631,637 ---- stmt = stmt1; } ! stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data)); LIM_DATA (stmt)->always_executed_in = outermost; if (maybe_never && pos == MOVE_PRESERVE_EXECUTION) *************** move_computations_stmt (struct dom_walk_ *** 722,728 **** cost = LIM_DATA (stmt)->cost; level = LIM_DATA (stmt)->tgt_loop; free_lim_aux_data (LIM_DATA (stmt)); ! stmt_ann (stmt)->aux = NULL; if (!level) { --- 722,728 ---- cost = LIM_DATA (stmt)->cost; level = LIM_DATA (stmt)->tgt_loop; free_lim_aux_data (LIM_DATA (stmt)); ! stmt_ann (stmt)->common.aux = NULL; if (!level) { *************** schedule_sm (struct loop *loop, edge *ex *** 951,957 **** /* Emit the load & stores. */ load = build (MODIFY_EXPR, void_type_node, tmp_var, ref); ! get_stmt_ann (load)->aux = xcalloc (1, sizeof (struct lim_aux_data)); LIM_DATA (load)->max_loop = loop; LIM_DATA (load)->tgt_loop = loop; --- 951,957 ---- /* Emit the load & stores. */ load = build (MODIFY_EXPR, void_type_node, tmp_var, ref); ! get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data)); LIM_DATA (load)->max_loop = loop; LIM_DATA (load)->tgt_loop = loop; Index: tree-vect-analyze.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-vect-analyze.c,v retrieving revision 2.23 diff -c -3 -p -r2.23 tree-vect-analyze.c *** tree-vect-analyze.c 3 May 2005 12:19:50 -0000 2.23 --- tree-vect-analyze.c 26 May 2005 11:26:44 -0000 *************** Software Foundation, 59 Temple Place - S *** 43,49 **** static loop_vec_info vect_analyze_loop_form (struct loop *); static bool vect_analyze_data_refs (loop_vec_info); static bool vect_mark_stmts_to_be_vectorized (loop_vec_info); ! static bool vect_analyze_scalar_cycles (loop_vec_info); static bool vect_analyze_data_ref_accesses (loop_vec_info); static bool vect_analyze_data_ref_dependences (loop_vec_info); static bool vect_analyze_data_refs_alignment (loop_vec_info); --- 43,49 ---- static loop_vec_info vect_analyze_loop_form (struct loop *); static bool vect_analyze_data_refs (loop_vec_info); static bool vect_mark_stmts_to_be_vectorized (loop_vec_info); ! static void vect_analyze_scalar_cycles (loop_vec_info); static bool vect_analyze_data_ref_accesses (loop_vec_info); static bool vect_analyze_data_ref_dependences (loop_vec_info); static bool vect_analyze_data_refs_alignment (loop_vec_info); *************** static bool vect_determine_vectorization *** 54,61 **** /* Utility functions for the analyses. */ static bool exist_non_indexing_operands_for_use_p (tree, tree); ! static void vect_mark_relevant (VEC(tree,heap) **, tree); ! static bool vect_stmt_relevant_p (tree, loop_vec_info); static tree vect_get_loop_niters (struct loop *, tree *); static bool vect_analyze_data_ref_dependence (struct data_reference *, struct data_reference *, loop_vec_info); --- 54,61 ---- /* Utility functions for the analyses. */ static bool exist_non_indexing_operands_for_use_p (tree, tree); ! static void vect_mark_relevant (VEC(tree,heap) **, tree, bool, bool); ! static bool vect_stmt_relevant_p (tree, loop_vec_info, bool *, bool *); static tree vect_get_loop_niters (struct loop *, tree *); static bool vect_analyze_data_ref_dependence (struct data_reference *, struct data_reference *, loop_vec_info); *************** vect_determine_vectorization_factor (loo *** 345,352 **** gcc_assert (stmt_info); /* skip stmts which do not need to be vectorized. */ ! if (!STMT_VINFO_RELEVANT_P (stmt_info)) ! continue; if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt)))) { --- 345,357 ---- gcc_assert (stmt_info); /* skip stmts which do not need to be vectorized. */ ! if (!STMT_VINFO_RELEVANT_P (stmt_info) ! && !STMT_VINFO_LIVE_P (stmt_info)) ! { ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "skip."); ! continue; ! } if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt)))) { *************** vect_analyze_operations (loop_vec_info l *** 445,450 **** --- 450,458 ---- unsigned int vectorization_factor = 0; int i; bool ok; + tree phi; + stmt_vec_info stmt_info; + bool need_to_vectorize = false; if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "=== vect_analyze_operations ==="); *************** vect_analyze_operations (loop_vec_info l *** 456,461 **** --- 464,492 ---- { basic_block bb = bbs[i]; + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + stmt_info = vinfo_for_stmt (phi); + if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) + { + fprintf (vect_dump, "examining phi: "); + print_generic_expr (vect_dump, phi, TDF_SLIM); + } + + gcc_assert (stmt_info); + + if (STMT_VINFO_LIVE_P (stmt_info)) + { + /* FORNOW: not yet supported. */ + if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, + LOOP_LOC (loop_vinfo))) + fprintf (vect_dump, "not vectorized: value used after loop."); + return false; + } + + gcc_assert (!STMT_VINFO_RELEVANT_P (stmt_info)); + } + for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) { tree stmt = bsi_stmt (si); *************** vect_analyze_operations (loop_vec_info l *** 476,517 **** - computations that are used only for array indexing or loop control */ ! if (!STMT_VINFO_RELEVANT_P (stmt_info)) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "irrelevant."); continue; } - #ifdef ENABLE_CHECKING if (STMT_VINFO_RELEVANT_P (stmt_info)) { gcc_assert (!VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt)))); gcc_assert (STMT_VINFO_VECTYPE (stmt_info)); - } #endif ! ok = (vectorizable_operation (stmt, NULL, NULL) ! || vectorizable_assignment (stmt, NULL, NULL) ! || vectorizable_load (stmt, NULL, NULL) ! || vectorizable_store (stmt, NULL, NULL) ! || vectorizable_condition (stmt, NULL, NULL)); ! if (!ok) { ! if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, ! LOOP_LOC (loop_vinfo))) { ! fprintf (vect_dump, "not vectorized: stmt not supported: "); ! print_generic_expr (vect_dump, stmt, TDF_SLIM); } - return false; } ! } ! } /* TODO: Analyze cost. Decide if worth while to vectorize. */ if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) && vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, --- 507,584 ---- - computations that are used only for array indexing or loop control */ ! if (!STMT_VINFO_RELEVANT_P (stmt_info) ! && !STMT_VINFO_LIVE_P (stmt_info)) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "irrelevant."); continue; } if (STMT_VINFO_RELEVANT_P (stmt_info)) { + #ifdef ENABLE_CHECKING gcc_assert (!VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt)))); gcc_assert (STMT_VINFO_VECTYPE (stmt_info)); #endif + ok = (vectorizable_operation (stmt, NULL, NULL) + || vectorizable_assignment (stmt, NULL, NULL) + || vectorizable_load (stmt, NULL, NULL) + || vectorizable_store (stmt, NULL, NULL) + || vectorizable_condition (stmt, NULL, NULL)); ! if (!ok) ! { ! if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, ! LOOP_LOC (loop_vinfo))) ! { ! fprintf (vect_dump, ! "not vectorized: relevant stmt not supported: "); ! print_generic_expr (vect_dump, stmt, TDF_SLIM); ! } ! return false; ! } ! need_to_vectorize = true; ! } ! if (STMT_VINFO_LIVE_P (stmt_info)) { ! ok = vectorizable_live_operation (stmt, NULL, NULL); ! ! if (!ok) { ! if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, ! LOOP_LOC (loop_vinfo))) ! { ! fprintf (vect_dump, ! "not vectorized: live stmt not supported: "); ! print_generic_expr (vect_dump, stmt, TDF_SLIM); ! } ! return false; } } ! } /* stmts in bb */ ! } /* bbs */ /* TODO: Analyze cost. Decide if worth while to vectorize. */ + /* All operations in the loop are either irrelevant (deal with loop + control, or dead), or only used outside the loop and can be moved + out of the loop (e.g. invariants, inductions). The loop can be + optimized away by scalar optimizations. We're better off not + touching this loop. */ + if (!need_to_vectorize) + { + if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo))) + fprintf (vect_dump, + "All the computation can be taken out of the loop."); + if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, + LOOP_LOC (loop_vinfo))) + fprintf (vect_dump, + "not vectorized: redundant loop. no profit to vectorize."); + return false; + } + if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) && vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, *************** exist_non_indexing_operands_for_use_p (t *** 602,641 **** /* Function vect_analyze_scalar_cycles. Examine the cross iteration def-use cycles of scalar variables, by ! analyzing the loop (scalar) PHIs; verify that the cross iteration def-use ! cycles that they represent do not impede vectorization. - FORNOW: Reduction as in the following loop, is not supported yet: loop1: for (i=0; inum, access_fn, &dummy, &dummy)) { ! if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, ! LOOP_LOC (loop_vinfo))) ! fprintf (vect_dump, "not vectorized: unsupported scalar cycle."); ! return false; } } ! return true; } --- 755,786 ---- print_generic_expr (vect_dump, access_fn, TDF_SLIM); } ! if (vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy)) { ! if (vect_print_dump_info (REPORT_DETAILS,LOOP_LOC (loop_vinfo))) ! fprintf (vect_dump, "Detected induction."); ! STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def; ! continue; } + + /* TODO: handle invariant phis */ + + reduc_stmt = vect_is_simple_reduction (loop, phi); + if (reduc_stmt) + { + if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo))) + fprintf (vect_dump, "Detected reduction."); + STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def; + STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) = + vect_reduction_def; + } + else + if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo))) + fprintf (vect_dump, "Unknown def-use cycle pattern."); + } ! return; } *************** vect_analyze_data_refs (loop_vec_info lo *** 2050,2088 **** Mark STMT as "relevant for vectorization" and add it to WORKLIST. */ static void ! vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt) { ! stmt_vec_info stmt_info; if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "mark relevant."); ! if (TREE_CODE (stmt) == PHI_NODE) ! { ! VEC_safe_push (tree, heap, *worklist, stmt); ! return; ! } ! stmt_info = vinfo_for_stmt (stmt); ! if (!stmt_info) ! { ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! { ! fprintf (vect_dump, "mark relevant: no stmt info!!."); ! print_generic_expr (vect_dump, stmt, TDF_SLIM); ! } ! return; ! } ! if (STMT_VINFO_RELEVANT_P (stmt_info)) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "already marked relevant."); return; } - STMT_VINFO_RELEVANT_P (stmt_info) = 1; VEC_safe_push (tree, heap, *worklist, stmt); } --- 2125,2156 ---- Mark STMT as "relevant for vectorization" and add it to WORKLIST. */ static void ! vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt, ! bool relevant_p, bool live_p) { ! stmt_vec_info stmt_info = vinfo_for_stmt (stmt); ! bool save_relevant_p = STMT_VINFO_RELEVANT_P (stmt_info); ! bool save_live_p = STMT_VINFO_LIVE_P (stmt_info); if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "mark relevant %d, live %d.",relevant_p, live_p); ! STMT_VINFO_LIVE_P (stmt_info) |= live_p; ! if (TREE_CODE (stmt) == PHI_NODE) ! /* Don't mark as relevant because it's not going to vectorized. */ ! return; ! STMT_VINFO_RELEVANT_P (stmt_info) |= relevant_p; ! if (STMT_VINFO_RELEVANT_P (stmt_info) == save_relevant_p ! && STMT_VINFO_LIVE_P (stmt_info) == save_live_p) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "already marked relevant/live."); return; } VEC_safe_push (tree, heap, *worklist, stmt); } *************** vect_mark_relevant (VEC(tree,heap) **wor *** 2100,2106 **** CHECKME: what other side effects would the vectorizer allow? */ static bool ! vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo) { struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); ssa_op_iter op_iter; --- 2168,2175 ---- CHECKME: what other side effects would the vectorizer allow? */ static bool ! vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo, ! bool *relevant_p, bool *live_p) { struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); ssa_op_iter op_iter; *************** vect_stmt_relevant_p (tree stmt, loop_ve *** 2108,2116 **** use_operand_p use_p; def_operand_p def_p; /* cond stmt other than loop exit cond. */ if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo))) ! return true; /* changing memory. */ if (TREE_CODE (stmt) != PHI_NODE) --- 2177,2188 ---- use_operand_p use_p; def_operand_p def_p; + *relevant_p = false; + *live_p = false; + /* cond stmt other than loop exit cond. */ if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo))) ! *relevant_p = true; /* changing memory. */ if (TREE_CODE (stmt) != PHI_NODE) *************** vect_stmt_relevant_p (tree stmt, loop_ve *** 2118,2124 **** { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs."); ! return true; } /* uses outside the loop. */ --- 2190,2196 ---- { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs."); ! *relevant_p = true; } /* uses outside the loop. */ *************** vect_stmt_relevant_p (tree stmt, loop_ve *** 2131,2142 **** { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop."); ! return true; } } } ! return false; } --- 2203,2220 ---- { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop."); ! #ifdef ENABLE_CHECKING ! /* We expect all such uses to be in the loop exit phis ! (because of loop closed form) */ ! gcc_assert (TREE_CODE (USE_STMT (use_p)) == PHI_NODE); ! gcc_assert (bb == loop->single_exit->dest); ! #endif ! *live_p = true; } } } ! return (*live_p || *relevant_p); } *************** vect_mark_stmts_to_be_vectorized (loop_v *** 2165,2180 **** unsigned int nbbs = loop->num_nodes; block_stmt_iterator si; tree stmt, use; ssa_op_iter iter; unsigned int i; ! int j; ! stmt_vec_info stmt_info; basic_block bb; tree phi; if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ==="); bb = loop->header; for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { --- 2243,2265 ---- unsigned int nbbs = loop->num_nodes; block_stmt_iterator si; tree stmt, use; + stmt_ann_t ann; ssa_op_iter iter; unsigned int i; ! stmt_vec_info stmt_vinfo; basic_block bb; tree phi; + bool relevant_p, live_p; + tree def, def_stmt; + enum vect_def_type dt; if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ==="); + worklist = VEC_alloc (tree, heap, 64); + + /* 1. Init worklist. */ + bb = loop->header; for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { *************** vect_mark_stmts_to_be_vectorized (loop_v *** 2184,2202 **** print_generic_expr (vect_dump, phi, TDF_SLIM); } ! if (vect_stmt_relevant_p (phi, loop_vinfo)) ! { ! if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, ! LOOP_LOC (loop_vinfo))) ! fprintf (vect_dump, "unsupported reduction/induction."); ! return false; ! } } - worklist = VEC_alloc (tree, heap, 64); - - /* 1. Init worklist. */ - for (i = 0; i < nbbs; i++) { bb = bbs[i]; --- 2269,2278 ---- print_generic_expr (vect_dump, phi, TDF_SLIM); } ! if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant_p, &live_p)) ! vect_mark_relevant (&worklist, phi, relevant_p, live_p); } for (i = 0; i < nbbs; i++) { bb = bbs[i]; *************** vect_mark_stmts_to_be_vectorized (loop_v *** 2210,2220 **** print_generic_expr (vect_dump, stmt, TDF_SLIM); } ! stmt_info = vinfo_for_stmt (stmt); ! STMT_VINFO_RELEVANT_P (stmt_info) = 0; ! ! if (vect_stmt_relevant_p (stmt, loop_vinfo)) ! vect_mark_relevant (&worklist, stmt); } } --- 2286,2293 ---- print_generic_expr (vect_dump, stmt, TDF_SLIM); } ! if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant_p, &live_p)) ! vect_mark_relevant (&worklist, stmt, relevant_p, live_p); } } *************** vect_mark_stmts_to_be_vectorized (loop_v *** 2231,2291 **** print_generic_expr (vect_dump, stmt, TDF_SLIM); } ! /* Examine the USES in this statement. Mark all the statements which ! feed this statement's uses as "relevant", unless the USE is used as ! an array index. */ ! if (TREE_CODE (stmt) == PHI_NODE) ! { ! /* follow the def-use chain inside the loop. */ ! for (j = 0; j < PHI_NUM_ARGS (stmt); j++) ! { ! tree arg = PHI_ARG_DEF (stmt, j); ! tree def_stmt = NULL_TREE; ! basic_block bb; ! if (!vect_is_simple_use (arg, loop_vinfo, &def_stmt)) ! { ! if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, ! LOOP_LOC (loop_vinfo))) ! fprintf (vect_dump, "not vectorized: unsupported use in stmt."); ! VEC_free (tree, heap, worklist); ! return false; ! } ! if (!def_stmt) ! continue; ! ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! { ! fprintf (vect_dump, "worklist: def_stmt: "); ! print_generic_expr (vect_dump, def_stmt, TDF_SLIM); ! } ! ! bb = bb_for_stmt (def_stmt); ! if (flow_bb_inside_loop_p (loop, bb)) ! vect_mark_relevant (&worklist, def_stmt); ! } ! } FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) { - /* We are only interested in uses that need to be vectorized. Uses that are used for address computation are not considered relevant. */ if (exist_non_indexing_operands_for_use_p (use, stmt)) { ! tree def_stmt = NULL_TREE; ! basic_block bb; ! if (!vect_is_simple_use (use, loop_vinfo, &def_stmt)) { if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, LOOP_LOC (loop_vinfo))) ! fprintf (vect_dump, "not vectorized: unsupported use in stmt."); VEC_free (tree, heap, worklist); return false; } ! if (!def_stmt) continue; if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) --- 2304,2368 ---- print_generic_expr (vect_dump, stmt, TDF_SLIM); } ! /* Examine the USEs of STMT. For each ssa-name USE thta is defined ! in the loop, mark the stmt that defines it (DEF_STMT) as ! relevant/irrelevant and live/dead according to the liveness and ! relevance properties of STMT. ! */ ! ! gcc_assert (TREE_CODE (stmt) != PHI_NODE); ! ! ann = stmt_ann (stmt); ! stmt_vinfo = vinfo_for_stmt (stmt); ! ! relevant_p = STMT_VINFO_RELEVANT_P (stmt_vinfo); ! live_p = STMT_VINFO_LIVE_P (stmt_vinfo); ! ! /* Generally, the liveness and relevance properties of STMT are ! propagated to the DEF_STMTs of its USEs: ! STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p ! STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- relevant_p ! ! Exceptions: ! ! - if USE is used only for address computations (e.g. array indexing), ! which does not need to be directly vectorized, then the ! liveness/relevance of the respective DEF_STMT is left unchanged. ! ! - if STMT has been identified as defining a reduction variable, then: ! STMT_VINFO_LIVE_P (DEF_STMT_info) <-- false ! STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- true ! because even though STMT is classified as live (since it defines a ! value that is used across loop iterations) and irrelevant (since it ! is not used inside the loop), it will be vectorized, and therefore ! the corresponding DEF_STMTs need to marked as relevant. ! */ ! if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def) ! { ! gcc_assert (!relevant_p && live_p); ! relevant_p = true; ! live_p = false; ! } FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) { /* We are only interested in uses that need to be vectorized. Uses that are used for address computation are not considered relevant. */ if (exist_non_indexing_operands_for_use_p (use, stmt)) { ! if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt)) { if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, LOOP_LOC (loop_vinfo))) ! fprintf (vect_dump, ! "not vectorized: unsupported use in stmt."); VEC_free (tree, heap, worklist); return false; } ! if (!def_stmt || IS_EMPTY_STMT (def_stmt)) continue; if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) *************** vect_mark_stmts_to_be_vectorized (loop_v *** 2295,2302 **** } bb = bb_for_stmt (def_stmt); ! if (flow_bb_inside_loop_p (loop, bb)) ! vect_mark_relevant (&worklist, def_stmt); } } } /* while worklist */ --- 2372,2387 ---- } bb = bb_for_stmt (def_stmt); ! if (!flow_bb_inside_loop_p (loop, bb)) ! continue; ! ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! { ! fprintf (vect_dump, "def_stmt: "); ! print_generic_expr (vect_dump, def_stmt, TDF_SLIM); ! } ! ! vect_mark_relevant (&worklist, def_stmt, relevant_p, live_p); } } } /* while worklist */ *************** vect_can_advance_ivs_p (loop_vec_info lo *** 2324,2329 **** --- 2409,2417 ---- /* Analyze phi functions of the loop header. */ + if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) + fprintf (vect_dump, "=== vect_can_advance_ivs_p ==="); + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { tree access_fn = NULL; *************** vect_can_advance_ivs_p (loop_vec_info lo *** 2366,2372 **** evolution_part = evolution_part_in_loop_num (access_fn, loop->num); if (evolution_part == NULL_TREE) ! return false; /* FORNOW: We do not transform initial conditions of IVs which evolution functions are a polynomial of degree >= 2. */ --- 2454,2464 ---- evolution_part = evolution_part_in_loop_num (access_fn, loop->num); if (evolution_part == NULL_TREE) ! { ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "No evolution."); ! return false; ! } /* FORNOW: We do not transform initial conditions of IVs which evolution functions are a polynomial of degree >= 2. */ *************** vect_analyze_loop (struct loop *loop) *** 2583,2588 **** --- 2675,2685 ---- return NULL; } + /* Classify all cross-iteration scalar data-flow cycles. + Cross-iteration cycles caused by virtual phis are analyzed separately. */ + + vect_analyze_scalar_cycles (loop_vinfo); + /* Data-flow analysis to detect stmts that do not need to be vectorized. */ ok = vect_mark_stmts_to_be_vectorized (loop_vinfo); *************** vect_analyze_loop (struct loop *loop) *** 2594,2611 **** return NULL; } - /* Check that all cross-iteration scalar data-flow cycles are OK. - Cross-iteration cycles caused by virtual phis are analyzed separately. */ - - ok = vect_analyze_scalar_cycles (loop_vinfo); - if (!ok) - { - if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo))) - fprintf (vect_dump, "bad scalar cycle."); - destroy_loop_vec_info (loop_vinfo); - return NULL; - } - ok = vect_determine_vectorization_factor (loop_vinfo); if (!ok) { --- 2691,2696 ---- Index: tree-vect-transform.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-vect-transform.c,v retrieving revision 2.19 diff -c -3 -p -r2.19 tree-vect-transform.c *** tree-vect-transform.c 3 May 2005 12:19:50 -0000 2.19 --- tree-vect-transform.c 26 May 2005 11:26:44 -0000 *************** vect_create_index_for_vector_ref (loop_v *** 146,152 **** create_iv (init, step, NULL_TREE, loop, &incr_bsi, insert_after, &indx_before_incr, &indx_after_incr); incr = bsi_stmt (incr_bsi); ! set_stmt_info (stmt_ann (incr), new_stmt_vec_info (incr, loop_vinfo)); return indx_before_incr; } --- 146,152 ---- create_iv (init, step, NULL_TREE, loop, &incr_bsi, insert_after, &indx_before_incr, &indx_after_incr); incr = bsi_stmt (incr_bsi); ! set_stmt_info ((tree_ann_t)stmt_ann (incr), new_stmt_vec_info (incr, loop_vinfo)); return indx_before_incr; } *************** vect_get_vec_def_for_operand (tree op, t *** 516,527 **** tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo); int nunits = TYPE_VECTOR_SUBPARTS (vectype); loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo); - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); - basic_block bb; tree vec_inv; tree t = NULL_TREE; tree def; int i; if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) { --- 513,525 ---- tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo); int nunits = TYPE_VECTOR_SUBPARTS (vectype); loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo); tree vec_inv; + tree vec_cst; tree t = NULL_TREE; tree def; int i; + enum vect_def_type dt; + bool is_simple_use; if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) { *************** vect_get_vec_def_for_operand (tree op, t *** 529,631 **** print_generic_expr (vect_dump, op, TDF_SLIM); } ! /** ===> Case 1: operand is a constant. **/ ! ! if (TREE_CODE (op) == INTEGER_CST || TREE_CODE (op) == REAL_CST) { ! /* Create 'vect_cst_ = {cst,cst,...,cst}' */ ! ! tree vec_cst; ! ! /* Build a tree with vector elements. */ ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits); ! ! for (i = nunits - 1; i >= 0; --i) { ! t = tree_cons (NULL_TREE, op, t); } - vec_cst = build_vector (vectype, t); - return vect_init_vector (stmt, vec_cst); - } - - gcc_assert (TREE_CODE (op) == SSA_NAME); - - /** ===> Case 2: operand is an SSA_NAME - find the stmt that defines it. **/ - - def_stmt = SSA_NAME_DEF_STMT (op); - def_stmt_info = vinfo_for_stmt (def_stmt); - - if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) - { - fprintf (vect_dump, "vect_get_vec_def_for_operand: def_stmt: "); - print_generic_expr (vect_dump, def_stmt, TDF_SLIM); - } - - - /** ==> Case 2.1: operand is defined inside the loop. **/ - - if (def_stmt_info) - { - /* Get the def from the vectorized stmt. */ - - vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info); - gcc_assert (vec_stmt); - vec_oprnd = TREE_OPERAND (vec_stmt, 0); - return vec_oprnd; } ! /** ==> Case 2.2: operand is defined by the loop-header phi-node - ! it is a reduction/induction. **/ ! ! bb = bb_for_stmt (def_stmt); ! if (TREE_CODE (def_stmt) == PHI_NODE && flow_bb_inside_loop_p (loop, bb)) { ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "reduction/induction - unsupported."); ! internal_error ("no support for reduction/induction"); /* FORNOW */ ! } ! ! ! /** ==> Case 2.3: operand is defined outside the loop - ! it is a loop invariant. */ - switch (TREE_CODE (def_stmt)) - { - case PHI_NODE: - def = PHI_RESULT (def_stmt); - break; - case MODIFY_EXPR: - def = TREE_OPERAND (def_stmt, 0); - break; - case NOP_EXPR: - def = TREE_OPERAND (def_stmt, 0); - gcc_assert (IS_EMPTY_STMT (def_stmt)); - def = op; - break; default: ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! { ! fprintf (vect_dump, "unsupported defining stmt: "); ! print_generic_expr (vect_dump, def_stmt, TDF_SLIM); ! } ! internal_error ("unsupported defining stmt"); ! } ! ! /* Build a tree with vector elements. ! Create 'vec_inv = {inv,inv,..,inv}' */ ! ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "Create vector_inv."); ! ! for (i = nunits - 1; i >= 0; --i) ! { ! t = tree_cons (NULL_TREE, def, t); } - - vec_inv = build_constructor (vectype, t); - return vect_init_vector (stmt, vec_inv); } --- 527,606 ---- print_generic_expr (vect_dump, op, TDF_SLIM); } ! is_simple_use = vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt); ! gcc_assert (is_simple_use); ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) { ! if (def) { ! fprintf (vect_dump, "def = "); ! print_generic_expr (vect_dump, def, TDF_SLIM); ! } ! if (def_stmt) ! { ! fprintf (vect_dump, " def_stmt = "); ! print_generic_expr (vect_dump, def_stmt, TDF_SLIM); } } + /* FORNOW */ + gcc_assert (dt != vect_reduction_def); ! switch (dt) { ! /* Case 1: operand is a constant. */ ! case vect_constant_def: ! { ! /* Create 'vect_cst_ = {cst,cst,...,cst}' */ ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits); ! ! for (i = nunits - 1; i >= 0; --i) ! { ! t = tree_cons (NULL_TREE, op, t); ! } ! vec_cst = build_vector (vectype, t); ! return vect_init_vector (stmt, vec_cst); ! } ! ! /* Case 2: operand is defined outside the loop - loop invariant. */ ! case vect_invariant_def: ! { ! /* Create 'vec_inv = {inv,inv,..,inv}' */ ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "Create vector_inv."); ! ! for (i = nunits - 1; i >= 0; --i) ! { ! t = tree_cons (NULL_TREE, def, t); ! } ! ! vec_inv = build_constructor (vectype, t); ! return vect_init_vector (stmt, vec_inv); ! } ! ! /* Case 3: operand is defined inside the loop. */ ! case vect_loop_def: ! { ! /* Get the def from the vectorized stmt. */ ! def_stmt_info = vinfo_for_stmt (def_stmt); ! vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info); ! gcc_assert (vec_stmt); ! vec_oprnd = TREE_OPERAND (vec_stmt, 0); ! return vec_oprnd; ! } ! ! /* Case 4: operand is defined by loop-header phi - induction. */ ! case vect_induction_def: ! { ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "induction - unsupported."); ! internal_error ("no support for induction"); /* FORNOW */ ! } default: ! gcc_unreachable (); } } *************** vectorizable_assignment (tree stmt, bloc *** 675,682 **** --- 650,664 ---- tree vectype = STMT_VINFO_VECTYPE (stmt_info); loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info); tree new_temp; + tree def, def_stmt; + enum vect_def_type dt; /* Is vectorizable assignment? */ + if (!STMT_VINFO_RELEVANT_P (stmt_info)) + return false; + #ifdef ENABLE_CHECKING + gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def); + #endif if (TREE_CODE (stmt) != MODIFY_EXPR) return false; *************** vectorizable_assignment (tree stmt, bloc *** 686,692 **** return false; op = TREE_OPERAND (stmt, 1); ! if (!vect_is_simple_use (op, loop_vinfo, NULL)) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "use not simple."); --- 668,674 ---- return false; op = TREE_OPERAND (stmt, 1); ! if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt)) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "use not simple."); *************** vect_min_worthwhile_factor (enum tree_co *** 746,751 **** --- 728,734 ---- } } + /* Function vectorizable_operation. Check if STMT performs a binary or unary operation that can be vectorized. *************** vectorizable_operation (tree stmt, block *** 771,778 **** --- 754,777 ---- int op_type; tree op; optab optab; + tree def, def_stmt; + enum vect_def_type dt; /* Is STMT a vectorizable binary/unary operation? */ + if (!STMT_VINFO_RELEVANT_P (stmt_info)) + return false; + #ifdef ENABLE_CHECKING + gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def); + #endif + + if (STMT_VINFO_LIVE_P (stmt_info)) + { + /* FORNOW: not yet supported. */ + if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo))) + fprintf (vect_dump, "value used after loop."); + return false; + } + if (TREE_CODE (stmt) != MODIFY_EXPR) return false; *************** vectorizable_operation (tree stmt, block *** 795,801 **** for (i = 0; i < op_type; i++) { op = TREE_OPERAND (operation, i); ! if (!vect_is_simple_use (op, loop_vinfo, NULL)) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "use not simple."); --- 794,800 ---- for (i = 0; i < op_type; i++) { op = TREE_OPERAND (operation, i); ! if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt)) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "use not simple."); *************** vectorizable_store (tree stmt, block_stm *** 892,898 **** tree dummy; enum dr_alignment_support alignment_support_cheme; ssa_op_iter iter; ! tree def; /* Is vectorizable store? */ --- 891,899 ---- tree dummy; enum dr_alignment_support alignment_support_cheme; ssa_op_iter iter; ! def_operand_p def_p; ! tree def, def_stmt; ! enum vect_def_type dt; /* Is vectorizable store? */ *************** vectorizable_store (tree stmt, block_stm *** 905,911 **** return false; op = TREE_OPERAND (stmt, 1); ! if (!vect_is_simple_use (op, loop_vinfo, NULL)) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "use not simple."); --- 906,912 ---- return false; op = TREE_OPERAND (stmt, 1); ! if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt)) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "use not simple."); *************** vectorizable_load (tree stmt, block_stmt *** 994,999 **** --- 998,1016 ---- enum dr_alignment_support alignment_support_cheme; /* Is vectorizable load? */ + if (!STMT_VINFO_RELEVANT_P (stmt_info)) + return false; + #ifdef ENABLE_CHECKING + gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def); + #endif + + if (STMT_VINFO_LIVE_P (stmt_info)) + { + /* FORNOW: not yet supported. */ + if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo))) + fprintf (vect_dump, "value used after loop."); + return false; + } if (TREE_CODE (stmt) != MODIFY_EXPR) return false; *************** vectorizable_load (tree stmt, block_stmt *** 1173,1178 **** --- 1190,1253 ---- return true; } + + /* Function vectorizable_live_operation. + + STMT computes a value that is used outside the loop. Check if + it can be supported. */ + + bool + vectorizable_live_operation (tree stmt, + block_stmt_iterator *bsi ATTRIBUTE_UNUSED, + tree *vec_stmt ATTRIBUTE_UNUSED) + { + tree operation; + stmt_vec_info stmt_info = vinfo_for_stmt (stmt); + loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info); + int i; + enum tree_code code; + int op_type; + tree op; + tree def, def_stmt; + enum vect_def_type dt; + + if (!STMT_VINFO_LIVE_P (stmt_info)) + return false; + + if (TREE_CODE (stmt) != MODIFY_EXPR) + return false; + + if (TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME) + return false; + + operation = TREE_OPERAND (stmt, 1); + code = TREE_CODE (operation); + + op_type = TREE_CODE_LENGTH (code); + + /* FORNOW: support only if all uses are invariant. This means + that the scalar operations can remain in place, unvectorized. + The original last scalar value that they compute will be used. */ + + for (i = 0; i < op_type; i++) + { + op = TREE_OPERAND (operation, i); + if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt)) + { + if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) + fprintf (vect_dump, "use not simple."); + return false; + } + + if (dt != vect_invariant_def && dt != vect_constant_def) + return false; + } + + /* No transformation is required for the cases we currently support. */ + return true; + } + + /* Function vect_is_simple_cond. Input: *************** static bool *** 1186,1191 **** --- 1261,1268 ---- vect_is_simple_cond (tree cond, loop_vec_info loop_vinfo) { tree lhs, rhs; + tree def; + enum vect_def_type dt; if (!COMPARISON_CLASS_P (cond)) return false; *************** vect_is_simple_cond (tree cond, loop_vec *** 1196,1202 **** if (TREE_CODE (lhs) == SSA_NAME) { tree lhs_def_stmt = SSA_NAME_DEF_STMT (lhs); ! if (!vect_is_simple_use (lhs, loop_vinfo, &lhs_def_stmt)) return false; } else if (TREE_CODE (lhs) != INTEGER_CST && TREE_CODE (lhs) != REAL_CST) --- 1273,1279 ---- if (TREE_CODE (lhs) == SSA_NAME) { tree lhs_def_stmt = SSA_NAME_DEF_STMT (lhs); ! if (!vect_is_simple_use (lhs, loop_vinfo, &lhs_def_stmt, &def, &dt)) return false; } else if (TREE_CODE (lhs) != INTEGER_CST && TREE_CODE (lhs) != REAL_CST) *************** vect_is_simple_cond (tree cond, loop_vec *** 1205,1211 **** if (TREE_CODE (rhs) == SSA_NAME) { tree rhs_def_stmt = SSA_NAME_DEF_STMT (rhs); ! if (!vect_is_simple_use (rhs, loop_vinfo, &rhs_def_stmt)) return false; } else if (TREE_CODE (rhs) != INTEGER_CST && TREE_CODE (rhs) != REAL_CST) --- 1282,1288 ---- if (TREE_CODE (rhs) == SSA_NAME) { tree rhs_def_stmt = SSA_NAME_DEF_STMT (rhs); ! if (!vect_is_simple_use (rhs, loop_vinfo, &rhs_def_stmt, &def, &dt)) return false; } else if (TREE_CODE (rhs) != INTEGER_CST && TREE_CODE (rhs) != REAL_CST) *************** vectorizable_condition (tree stmt, block *** 1237,1246 **** --- 1314,1337 ---- tree new_temp; loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info); enum machine_mode vec_mode; + tree def; + enum vect_def_type dt; if (!STMT_VINFO_RELEVANT_P (stmt_info)) return false; + #ifdef ENABLE_CHECKING + gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def); + #endif + + if (STMT_VINFO_LIVE_P (stmt_info)) + { + /* FORNOW: not yet supported. */ + if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo))) + fprintf (vect_dump, "value used after loop."); + return false; + } + if (TREE_CODE (stmt) != MODIFY_EXPR) return false; *************** vectorizable_condition (tree stmt, block *** 1259,1265 **** if (TREE_CODE (then_clause) == SSA_NAME) { tree then_def_stmt = SSA_NAME_DEF_STMT (then_clause); ! if (!vect_is_simple_use (then_clause, loop_vinfo, &then_def_stmt)) return false; } else if (TREE_CODE (then_clause) != INTEGER_CST --- 1350,1357 ---- if (TREE_CODE (then_clause) == SSA_NAME) { tree then_def_stmt = SSA_NAME_DEF_STMT (then_clause); ! if (!vect_is_simple_use (then_clause, loop_vinfo, ! &then_def_stmt, &def, &dt)) return false; } else if (TREE_CODE (then_clause) != INTEGER_CST *************** vectorizable_condition (tree stmt, block *** 1269,1275 **** if (TREE_CODE (else_clause) == SSA_NAME) { tree else_def_stmt = SSA_NAME_DEF_STMT (else_clause); ! if (!vect_is_simple_use (else_clause, loop_vinfo, &else_def_stmt)) return false; } else if (TREE_CODE (else_clause) != INTEGER_CST --- 1361,1368 ---- if (TREE_CODE (else_clause) == SSA_NAME) { tree else_def_stmt = SSA_NAME_DEF_STMT (else_clause); ! if (!vect_is_simple_use (else_clause, loop_vinfo, ! &else_def_stmt, &def, &dt)) return false; } else if (TREE_CODE (else_clause) != INTEGER_CST *************** vect_transform_stmt (tree stmt, block_st *** 1325,1367 **** stmt_vec_info stmt_info = vinfo_for_stmt (stmt); bool done; ! switch (STMT_VINFO_TYPE (stmt_info)) { ! case op_vec_info_type: ! done = vectorizable_operation (stmt, bsi, &vec_stmt); ! gcc_assert (done); ! break; ! case assignment_vec_info_type: ! done = vectorizable_assignment (stmt, bsi, &vec_stmt); ! gcc_assert (done); ! break; ! ! case load_vec_info_type: ! done = vectorizable_load (stmt, bsi, &vec_stmt); ! gcc_assert (done); ! break; ! ! case store_vec_info_type: ! done = vectorizable_store (stmt, bsi, &vec_stmt); ! gcc_assert (done); ! is_store = true; ! break; ! case condition_vec_info_type: ! done = vectorizable_condition (stmt, bsi, &vec_stmt); gcc_assert (done); - break; - - default: - if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) - fprintf (vect_dump, "stmt not supported."); - gcc_unreachable (); } ! STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt; ! ! return is_store; } --- 1418,1469 ---- stmt_vec_info stmt_info = vinfo_for_stmt (stmt); bool done; ! if (STMT_VINFO_RELEVANT_P (stmt_info)) { ! switch (STMT_VINFO_TYPE (stmt_info)) ! { ! case op_vec_info_type: ! done = vectorizable_operation (stmt, bsi, &vec_stmt); ! gcc_assert (done); ! break; ! ! case assignment_vec_info_type: ! done = vectorizable_assignment (stmt, bsi, &vec_stmt); ! gcc_assert (done); ! break; ! ! case load_vec_info_type: ! done = vectorizable_load (stmt, bsi, &vec_stmt); ! gcc_assert (done); ! break; ! ! case store_vec_info_type: ! done = vectorizable_store (stmt, bsi, &vec_stmt); ! gcc_assert (done); ! is_store = true; ! break; ! ! case condition_vec_info_type: ! done = vectorizable_condition (stmt, bsi, &vec_stmt); ! gcc_assert (done); ! break; ! ! default: ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "stmt not supported."); ! gcc_unreachable (); ! } ! STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt; ! } ! if (STMT_VINFO_LIVE_P (stmt_info)) ! { ! done = vectorizable_live_operation (stmt, bsi, &vec_stmt); gcc_assert (done); } ! return is_store; } *************** vect_update_ivs_after_vectorizer (loop_v *** 1600,1605 **** --- 1702,1713 ---- tree var, stmt, ni, ni_name; block_stmt_iterator last_bsi; + if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) + { + fprintf (vect_dump, "vect_update_ivs_after_vectorizer: phi: "); + print_generic_expr (vect_dump, phi, TDF_SLIM); + } + /* Skip virtual phi's. */ if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) { *************** vect_transform_loop (loop_vec_info loop_ *** 2014,2020 **** /* Free the attached stmt_vec_info and remove the stmt. */ stmt_ann_t ann = stmt_ann (stmt); free (stmt_info); ! set_stmt_info (ann, NULL); bsi_remove (&si); continue; } --- 2122,2128 ---- /* Free the attached stmt_vec_info and remove the stmt. */ stmt_ann_t ann = stmt_ann (stmt); free (stmt_info); ! set_stmt_info ((tree_ann_t)ann, NULL); bsi_remove (&si); continue; } Index: tree-vectorizer.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-vectorizer.c,v retrieving revision 2.90 diff -c -3 -p -r2.90 tree-vectorizer.c *** tree-vectorizer.c 3 May 2005 12:19:50 -0000 2.90 --- tree-vectorizer.c 26 May 2005 11:26:44 -0000 *************** new_stmt_vec_info (tree stmt, loop_vec_i *** 1331,1339 **** --- 1331,1344 ---- STMT_VINFO_STMT (res) = stmt; STMT_VINFO_LOOP_VINFO (res) = loop_vinfo; STMT_VINFO_RELEVANT_P (res) = 0; + STMT_VINFO_LIVE_P (res) = 0; STMT_VINFO_VECTYPE (res) = NULL; STMT_VINFO_VEC_STMT (res) = NULL; STMT_VINFO_DATA_REF (res) = NULL; + if (TREE_CODE (stmt) == PHI_NODE) + STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type; + else + STMT_VINFO_DEF_TYPE (res) = vect_loop_def; STMT_VINFO_MEMTAG (res) = NULL; STMT_VINFO_PTR_INFO (res) = NULL; STMT_VINFO_SUBVARS (res) = NULL; *************** new_loop_vec_info (struct loop *loop) *** 1368,1380 **** for (i = 0; i < loop->num_nodes; i++) { basic_block bb = bbs[i]; for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) { tree stmt = bsi_stmt (si); stmt_ann_t ann; ann = stmt_ann (stmt); ! set_stmt_info (ann, new_stmt_vec_info (stmt, res)); } } --- 1373,1393 ---- for (i = 0; i < loop->num_nodes; i++) { basic_block bb = bbs[i]; + tree phi; + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + tree_ann_t ann = get_tree_ann (phi); + set_stmt_info (ann, new_stmt_vec_info (phi, res)); + } + for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) { tree stmt = bsi_stmt (si); stmt_ann_t ann; ann = stmt_ann (stmt); ! set_stmt_info ((tree_ann_t)ann, new_stmt_vec_info (stmt, res)); } } *************** destroy_loop_vec_info (loop_vec_info loo *** 1421,1433 **** for (j = 0; j < nbbs; j++) { basic_block bb = bbs[j]; for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) { tree stmt = bsi_stmt (si); stmt_ann_t ann = stmt_ann (stmt); stmt_vec_info stmt_info = vinfo_for_stmt (stmt); free (stmt_info); ! set_stmt_info (ann, NULL); } } --- 1434,1459 ---- for (j = 0; j < nbbs; j++) { basic_block bb = bbs[j]; + tree phi; + stmt_vec_info stmt_info; + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + tree_ann_t ann = get_tree_ann (phi); + + stmt_info = vinfo_for_stmt (phi); + free (stmt_info); + set_stmt_info (ann, NULL); + } + for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) { tree stmt = bsi_stmt (si); stmt_ann_t ann = stmt_ann (stmt); + stmt_vec_info stmt_info = vinfo_for_stmt (stmt); free (stmt_info); ! set_stmt_info ((tree_ann_t)ann, NULL); } } *************** vect_supportable_dr_alignment (struct da *** 1589,1652 **** in reduction/induction computations). */ bool ! vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def) { - tree def_stmt; basic_block bb; struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); ! if (def) ! *def = NULL_TREE; ! if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST) ! return true; ! if (TREE_CODE (operand) != SSA_NAME) ! return false; ! ! def_stmt = SSA_NAME_DEF_STMT (operand); ! if (def_stmt == NULL_TREE ) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "no def_stmt."); return false; } /* empty stmt is expected only in case of a function argument. (Otherwise - we expect a phi_node or a modify_expr). */ ! if (IS_EMPTY_STMT (def_stmt)) { ! tree arg = TREE_OPERAND (def_stmt, 0); if (TREE_CODE (arg) == INTEGER_CST || TREE_CODE (arg) == REAL_CST) ! return true; if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! { ! fprintf (vect_dump, "Unexpected empty stmt: "); ! print_generic_expr (vect_dump, def_stmt, TDF_SLIM); ! } ! return false; } ! /* phi_node inside the loop indicates an induction/reduction pattern. ! This is not supported yet. */ ! bb = bb_for_stmt (def_stmt); ! if (TREE_CODE (def_stmt) == PHI_NODE && flow_bb_inside_loop_p (loop, bb)) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "reduction/induction - unsupported."); ! return false; /* FORNOW: not supported yet. */ } ! /* Expecting a modify_expr or a phi_node. */ ! if (TREE_CODE (def_stmt) == MODIFY_EXPR ! || TREE_CODE (def_stmt) == PHI_NODE) { ! if (def) ! *def = def_stmt; ! return true; } ! return false; } --- 1615,1762 ---- in reduction/induction computations). */ bool ! vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def_stmt, ! tree *def, enum vect_def_type *dt) { basic_block bb; + stmt_vec_info stmt_vinfo; struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); ! *def_stmt = NULL_TREE; ! *def = NULL_TREE; ! ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! { ! fprintf (vect_dump, "vect_is_simple_use: operand "); ! print_generic_expr (vect_dump, operand, TDF_SLIM); ! } ! if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST) ! { ! *dt = vect_constant_def; ! return true; ! } ! if (TREE_CODE (operand) != SSA_NAME) ! { ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "not ssa-name."); ! return false; ! } ! ! *def_stmt = SSA_NAME_DEF_STMT (operand); ! if (*def_stmt == NULL_TREE ) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) fprintf (vect_dump, "no def_stmt."); return false; } + if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) + { + fprintf (vect_dump, "def_stmt: "); + print_generic_expr (vect_dump, *def_stmt, TDF_SLIM); + } + /* empty stmt is expected only in case of a function argument. (Otherwise - we expect a phi_node or a modify_expr). */ ! if (IS_EMPTY_STMT (*def_stmt)) { ! tree arg = TREE_OPERAND (*def_stmt, 0); if (TREE_CODE (arg) == INTEGER_CST || TREE_CODE (arg) == REAL_CST) ! { ! *def = operand; ! *dt = vect_invariant_def; ! return true; ! } ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "Unexpected empty stmt."); ! return false; } ! bb = bb_for_stmt (*def_stmt); ! if (!flow_bb_inside_loop_p (loop, bb)) ! *dt = vect_invariant_def; ! else ! { ! stmt_vinfo = vinfo_for_stmt (*def_stmt); ! *dt = STMT_VINFO_DEF_TYPE (stmt_vinfo); ! } ! ! if (*dt == vect_unknown_def_type) { if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "Unsupported pattern."); ! return false; } ! /* stmts inside the loop that have been identified as performing ! a reduction operation cannot have uses in the loop. */ ! if (*dt == vect_reduction_def && TREE_CODE (*def_stmt) != PHI_NODE) { ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "reduction used in loop."); ! return false; ! } ! ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "type of def: %d.",*dt); ! ! switch (TREE_CODE (*def_stmt)) ! { ! case PHI_NODE: ! *def = PHI_RESULT (*def_stmt); ! gcc_assert (*dt == vect_induction_def || *dt == vect_reduction_def ! || *dt == vect_invariant_def); ! break; ! ! case MODIFY_EXPR: ! *def = TREE_OPERAND (*def_stmt, 0); ! gcc_assert (*dt == vect_loop_def || *dt == vect_invariant_def); ! break; ! ! default: ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "unsupported defining stmt: "); ! return false; ! } ! ! if (*dt == vect_induction_def) ! { ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "induction not supported."); ! return false; } ! return true; ! } ! ! ! /* Function vect_is_simple_reduction ! ! TODO: ! Detect a cross-iteration def-use cucle that represents a simple ! reduction computation. We look for the followng pattern: ! ! loop_header: ! a1 = phi < a0, a2 > ! a3 = ... ! a2 = operation (a3, a1) ! ! such that: ! 1. operation is... ! 2. no uses for a2 in the loop (elsewhere) */ ! ! tree ! vect_is_simple_reduction (struct loop *loop ATTRIBUTE_UNUSED, ! tree phi ATTRIBUTE_UNUSED) ! { ! /* FORNOW */ ! if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) ! fprintf (vect_dump, "reduction: unknown pattern."); ! ! return NULL_TREE; } Index: tree-vectorizer.h =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-vectorizer.h,v retrieving revision 2.20 diff -c -3 -p -r2.20 tree-vectorizer.h *** tree-vectorizer.h 3 May 2005 20:18:32 -0000 2.20 --- tree-vectorizer.h 26 May 2005 11:26:44 -0000 *************** enum dr_alignment_support { *** 56,61 **** --- 56,71 ---- dr_aligned }; + /* Define type of def-use cross-iteraiton cycle. */ + enum vect_def_type { + vect_constant_def, + vect_invariant_def, + vect_loop_def, + vect_induction_def, + vect_reduction_def, + vect_unknown_def_type + }; + /* Define verbosity levels. */ enum verbosity_levels { REPORT_NONE, *************** typedef struct _stmt_vec_info { *** 163,168 **** --- 173,182 ---- indicates whether the stmt needs to be vectorized. */ bool relevant; + /* Indicates whether this stmts is part of a computation whose result is + used outside the loop. */ + bool live; + /* The vector type to be used. */ tree vectype; *************** typedef struct _stmt_vec_info { *** 215,220 **** --- 229,238 ---- /* Alignment information. The offset of the data-reference from its base in bytes. */ tree misalignment; + + /* Classify the def of this stmt. */ + enum vect_def_type def_type; + } *stmt_vec_info; /* Access Functions. */ *************** typedef struct _stmt_vec_info { *** 222,227 **** --- 240,246 ---- #define STMT_VINFO_STMT(S) (S)->stmt #define STMT_VINFO_LOOP_VINFO(S) (S)->loop_vinfo #define STMT_VINFO_RELEVANT_P(S) (S)->relevant + #define STMT_VINFO_LIVE_P(S) (S)->live #define STMT_VINFO_VECTYPE(S) (S)->vectype #define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt #define STMT_VINFO_DATA_REF(S) (S)->data_ref_info *************** typedef struct _stmt_vec_info { *** 233,254 **** #define STMT_VINFO_VECT_STEP(S) (S)->step #define STMT_VINFO_VECT_BASE_ALIGNED_P(S) (S)->base_aligned_p #define STMT_VINFO_VECT_MISALIGNMENT(S) (S)->misalignment ! static inline void set_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info); static inline stmt_vec_info vinfo_for_stmt (tree stmt); static inline void ! set_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info) { if (ann) ! ann->aux = (char *) stmt_info; } static inline stmt_vec_info vinfo_for_stmt (tree stmt) { ! stmt_ann_t ann = stmt_ann (stmt); ! return ann ? (stmt_vec_info) ann->aux : NULL; } /*-----------------------------------------------------------------*/ --- 252,274 ---- #define STMT_VINFO_VECT_STEP(S) (S)->step #define STMT_VINFO_VECT_BASE_ALIGNED_P(S) (S)->base_aligned_p #define STMT_VINFO_VECT_MISALIGNMENT(S) (S)->misalignment + #define STMT_VINFO_DEF_TYPE(S) (S)->def_type ! static inline void set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info); static inline stmt_vec_info vinfo_for_stmt (tree stmt); static inline void ! set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info) { if (ann) ! ann->common.aux = (char *) stmt_info; } static inline stmt_vec_info vinfo_for_stmt (tree stmt) { ! tree_ann_t ann = tree_ann (stmt); ! return ann ? (stmt_vec_info) ann->common.aux : NULL; } /*-----------------------------------------------------------------*/ *************** extern void slpeel_verify_cfg_after_peel *** 309,316 **** /** In tree-vectorizer.c **/ extern tree vect_strip_conversion (tree); extern tree get_vectype_for_scalar_type (tree); ! extern bool vect_is_simple_use (tree , loop_vec_info, tree *); extern bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *); extern bool vect_can_force_dr_alignment_p (tree, unsigned int); extern enum dr_alignment_support vect_supportable_dr_alignment (struct data_reference *); --- 329,338 ---- /** In tree-vectorizer.c **/ extern tree vect_strip_conversion (tree); extern tree get_vectype_for_scalar_type (tree); ! extern bool vect_is_simple_use (tree, loop_vec_info, tree *, tree *, ! enum vect_def_type *); extern bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *); + extern tree vect_is_simple_reduction (struct loop *, tree); extern bool vect_can_force_dr_alignment_p (tree, unsigned int); extern enum dr_alignment_support vect_supportable_dr_alignment (struct data_reference *); *************** extern bool vectorizable_store (tree, bl *** 331,336 **** --- 353,359 ---- extern bool vectorizable_operation (tree, block_stmt_iterator *, tree *); extern bool vectorizable_assignment (tree, block_stmt_iterator *, tree *); extern bool vectorizable_condition (tree, block_stmt_iterator *, tree *); + extern bool vectorizable_live_operation (tree, block_stmt_iterator *, tree *); /* Driver for transformation stage. */ extern void vect_transform_loop (loop_vec_info, struct loops *); Index: testsuite/gcc.dg/vect/vect-62.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/vect/vect-62.c,v retrieving revision 1.6 diff -c -3 -p -r1.6 vect-62.c *** testsuite/gcc.dg/vect/vect-62.c 31 Mar 2005 18:34:19 -0000 1.6 --- testsuite/gcc.dg/vect/vect-62.c 26 May 2005 11:26:50 -0000 *************** int main1 () *** 32,38 **** } /* Multidimensional array. Aligned. The "inner" dimensions ! are invariant in the inner loop. Store. */ for (i = 0; i < N; i++) { for (j = 0; j < N; j++) --- 32,40 ---- } /* Multidimensional array. Aligned. The "inner" dimensions ! are invariant in the inner loop. Vectorizable, but the ! vectorizer detects that everything is invariant and that ! the loop is better left untouched. (it should be optimized away). */ for (i = 0; i < N; i++) { for (j = 0; j < N; j++) *************** int main (void) *** 62,67 **** return main1 (); } ! /* { dg-final { scan-tree-dump-times "vectorized 2 loops" 1 "vect" } } */ /* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 0 "vect" } } */ /* { dg-final { cleanup-tree-dump "vect" } } */ --- 64,70 ---- return main1 (); } ! /* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */ /* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 0 "vect" } } */ + /* { dg-final { scan-tree-dump-times "not vectorized: redundant loop. no profit to vectorize." 1 "vect" } } */ /* { dg-final { cleanup-tree-dump "vect" } } */