From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 36891 invoked by alias); 11 Nov 2015 14:29:27 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 36880 invoked by uid 89); 11 Nov 2015 14:29:26 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.4 required=5.0 tests=AWL,BAYES_50,KAM_ASCII_DIVIDERS,RP_MATCHES_RCVD,SPF_PASS autolearn=no version=3.3.2 X-HELO: mx2.suse.de Received: from mx2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Wed, 11 Nov 2015 14:29:23 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 8734BABE5 for ; Wed, 11 Nov 2015 14:28:59 +0000 (UTC) Date: Wed, 11 Nov 2015 14:29:00 -0000 From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] More compile-time saving in BB vectorization Message-ID: User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2015-11/txt/msg01380.txt.bz2 This saves some more compile-time avoiding vector size iteration for trivial fails. It also improves time spent by not giving up completely for all SLP instances if one fails to vectorize because of alignment issues. And it sneaks in a correctness fix for a previous change. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. Richard. 2015-11-11 Richard Biener * tree-vectorizer.h (vect_slp_analyze_and_verify_instance_alignment): Declare. (vect_analyze_data_refs_alignment): Make loop vect specific. (vect_verify_datarefs_alignment): Likewise. * tree-vect-data-refs.c (vect_slp_analyze_data_ref_dependences): Add missing continue. (vect_compute_data_ref_alignment): Export. (vect_compute_data_refs_alignment): Merge into... (vect_analyze_data_refs_alignment): ... this. (verify_data_ref_alignment): Split out from ... (vect_verify_datarefs_alignment): ... here. (vect_slp_analyze_and_verify_node_alignment): New function. (vect_slp_analyze_and_verify_instance_alignment): Likewise. * tree-vect-slp.c (vect_supported_load_permutation_p): Remove misplaced checks on alignment. (vect_slp_analyze_bb_1): Add fatal output parameter. Do alignment analysis after SLP discovery and do it per instance. (vect_slp_bb): When vect_slp_analyze_bb_1 fatally failed do not bother to re-try using different vector sizes. Index: gcc/tree-vectorizer.h =================================================================== *** gcc/tree-vectorizer.h (revision 230155) --- gcc/tree-vectorizer.h (working copy) *************** extern tree vect_get_smallest_scalar_typ *** 1011,1018 **** extern bool vect_analyze_data_ref_dependences (loop_vec_info, int *); extern bool vect_slp_analyze_data_ref_dependences (bb_vec_info); extern bool vect_enhance_data_refs_alignment (loop_vec_info); ! extern bool vect_analyze_data_refs_alignment (vec_info *); ! extern bool vect_verify_datarefs_alignment (vec_info *); extern bool vect_analyze_data_ref_accesses (vec_info *); extern bool vect_prune_runtime_alias_test_list (loop_vec_info); extern tree vect_check_gather_scatter (gimple *, loop_vec_info, tree *, tree *, --- 1011,1019 ---- extern bool vect_analyze_data_ref_dependences (loop_vec_info, int *); extern bool vect_slp_analyze_data_ref_dependences (bb_vec_info); extern bool vect_enhance_data_refs_alignment (loop_vec_info); ! extern bool vect_analyze_data_refs_alignment (loop_vec_info); ! extern bool vect_verify_datarefs_alignment (loop_vec_info); ! extern bool vect_slp_analyze_and_verify_instance_alignment (slp_instance); extern bool vect_analyze_data_ref_accesses (vec_info *); extern bool vect_prune_runtime_alias_test_list (loop_vec_info); extern tree vect_check_gather_scatter (gimple *, loop_vec_info, tree *, tree *, Index: gcc/tree-vect-data-refs.c =================================================================== *** gcc/tree-vect-data-refs.c (revision 230155) --- gcc/tree-vect-data-refs.c (working copy) *************** vect_slp_analyze_data_ref_dependences (b *** 645,650 **** --- 645,651 ---- (SLP_INSTANCE_TREE (instance))[0], 0); vect_free_slp_instance (instance); BB_VINFO_SLP_INSTANCES (bb_vinfo).ordered_remove (i); + continue; } i++; } *************** vect_slp_analyze_data_ref_dependences (b *** 668,674 **** FOR NOW: No analysis is actually performed. Misalignment is calculated only for trivial cases. TODO. */ ! static bool vect_compute_data_ref_alignment (struct data_reference *dr) { gimple *stmt = DR_STMT (dr); --- 669,675 ---- FOR NOW: No analysis is actually performed. Misalignment is calculated only for trivial cases. TODO. */ ! bool vect_compute_data_ref_alignment (struct data_reference *dr) { gimple *stmt = DR_STMT (dr); *************** vect_compute_data_ref_alignment (struct *** 838,882 **** } - /* Function vect_compute_data_refs_alignment - - Compute the misalignment of data references in the loop. - Return FALSE if a data reference is found that cannot be vectorized. */ - - static bool - vect_compute_data_refs_alignment (vec_info *vinfo) - { - vec datarefs = vinfo->datarefs; - struct data_reference *dr; - unsigned int i; - - FOR_EACH_VEC_ELT (datarefs, i, dr) - { - stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr)); - if (STMT_VINFO_VECTORIZABLE (stmt_info) - && !vect_compute_data_ref_alignment (dr)) - { - /* Strided accesses perform only component accesses, misalignment - information is irrelevant for them. */ - if (STMT_VINFO_STRIDED_P (stmt_info) - && !STMT_VINFO_GROUPED_ACCESS (stmt_info)) - continue; - - if (is_a (vinfo)) - { - /* Mark unsupported statement as unvectorizable. */ - STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false; - continue; - } - else - return false; - } - } - - return true; - } - - /* Function vect_update_misalignment_for_peel DR - the data reference whose misalignment is to be adjusted. --- 839,844 ---- *************** vect_update_misalignment_for_peel (struc *** 936,998 **** } /* Function vect_verify_datarefs_alignment Return TRUE if all data references in the loop can be handled with respect to alignment. */ bool ! vect_verify_datarefs_alignment (vec_info *vinfo) { vec datarefs = vinfo->datarefs; struct data_reference *dr; - enum dr_alignment_support supportable_dr_alignment; unsigned int i; FOR_EACH_VEC_ELT (datarefs, i, dr) ! { ! gimple *stmt = DR_STMT (dr); ! stmt_vec_info stmt_info = vinfo_for_stmt (stmt); ! ! if (!STMT_VINFO_RELEVANT_P (stmt_info)) ! continue; ! ! /* For interleaving, only the alignment of the first access matters. ! Skip statements marked as not vectorizable. */ ! if ((STMT_VINFO_GROUPED_ACCESS (stmt_info) ! && GROUP_FIRST_ELEMENT (stmt_info) != stmt) ! || !STMT_VINFO_VECTORIZABLE (stmt_info)) ! continue; ! ! /* Strided accesses perform only component accesses, alignment is ! irrelevant for them. */ ! if (STMT_VINFO_STRIDED_P (stmt_info) ! && !STMT_VINFO_GROUPED_ACCESS (stmt_info)) ! continue; ! ! supportable_dr_alignment = vect_supportable_dr_alignment (dr, false); ! if (!supportable_dr_alignment) ! { ! if (dump_enabled_p ()) ! { ! if (DR_IS_READ (dr)) ! dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, ! "not vectorized: unsupported unaligned load."); ! else ! dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, ! "not vectorized: unsupported unaligned " ! "store."); - dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, - DR_REF (dr)); - dump_printf (MSG_MISSED_OPTIMIZATION, "\n"); - } - return false; - } - if (supportable_dr_alignment != dr_aligned && dump_enabled_p ()) - dump_printf_loc (MSG_NOTE, vect_location, - "Vectorizing an unaligned access.\n"); - } return true; } --- 898,973 ---- } + /* Function verify_data_ref_alignment + + Return TRUE if DR can be handled with respect to alignment. */ + + static bool + verify_data_ref_alignment (data_reference_p dr) + { + enum dr_alignment_support supportable_dr_alignment; + gimple *stmt = DR_STMT (dr); + stmt_vec_info stmt_info = vinfo_for_stmt (stmt); + + if (!STMT_VINFO_RELEVANT_P (stmt_info)) + return true; + + /* For interleaving, only the alignment of the first access matters. + Skip statements marked as not vectorizable. */ + if ((STMT_VINFO_GROUPED_ACCESS (stmt_info) + && GROUP_FIRST_ELEMENT (stmt_info) != stmt) + || !STMT_VINFO_VECTORIZABLE (stmt_info)) + return true; + + /* Strided accesses perform only component accesses, alignment is + irrelevant for them. */ + if (STMT_VINFO_STRIDED_P (stmt_info) + && !STMT_VINFO_GROUPED_ACCESS (stmt_info)) + return true; + + supportable_dr_alignment = vect_supportable_dr_alignment (dr, false); + if (!supportable_dr_alignment) + { + if (dump_enabled_p ()) + { + if (DR_IS_READ (dr)) + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, + "not vectorized: unsupported unaligned load."); + else + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, + "not vectorized: unsupported unaligned " + "store."); + + dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, + DR_REF (dr)); + dump_printf (MSG_MISSED_OPTIMIZATION, "\n"); + } + return false; + } + + if (supportable_dr_alignment != dr_aligned && dump_enabled_p ()) + dump_printf_loc (MSG_NOTE, vect_location, + "Vectorizing an unaligned access.\n"); + + return true; + } + /* Function vect_verify_datarefs_alignment Return TRUE if all data references in the loop can be handled with respect to alignment. */ bool ! vect_verify_datarefs_alignment (loop_vec_info vinfo) { vec datarefs = vinfo->datarefs; struct data_reference *dr; unsigned int i; FOR_EACH_VEC_ELT (datarefs, i, dr) ! if (! verify_data_ref_alignment (dr)) ! return false; return true; } *************** vect_find_same_alignment_drs (struct dat *** 2064,2070 **** Return FALSE if a data reference is found that cannot be vectorized. */ bool ! vect_analyze_data_refs_alignment (vec_info *vinfo) { if (dump_enabled_p ()) dump_printf_loc (MSG_NOTE, vect_location, --- 2039,2045 ---- Return FALSE if a data reference is found that cannot be vectorized. */ bool ! vect_analyze_data_refs_alignment (loop_vec_info vinfo) { if (dump_enabled_p ()) dump_printf_loc (MSG_NOTE, vect_location, *************** vect_analyze_data_refs_alignment (vec_in *** 2072,2098 **** /* Mark groups of data references with same alignment using data dependence information. */ ! if (is_a (vinfo)) { ! vec ddrs = vinfo->ddrs; ! struct data_dependence_relation *ddr; ! unsigned int i; ! FOR_EACH_VEC_ELT (ddrs, i, ddr) ! vect_find_same_alignment_drs (ddr, as_a (vinfo)); } ! if (!vect_compute_data_refs_alignment (vinfo)) { ! if (dump_enabled_p ()) ! dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, ! "not vectorized: can't calculate alignment " ! "for data ref.\n"); ! return false; } return true; } /* Analyze groups of accesses: check that DR belongs to a group of --- 2047,2145 ---- /* Mark groups of data references with same alignment using data dependence information. */ ! vec ddrs = vinfo->ddrs; ! struct data_dependence_relation *ddr; ! unsigned int i; ! ! FOR_EACH_VEC_ELT (ddrs, i, ddr) ! vect_find_same_alignment_drs (ddr, vinfo); ! ! vec datarefs = vinfo->datarefs; ! struct data_reference *dr; ! ! FOR_EACH_VEC_ELT (datarefs, i, dr) { ! stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr)); ! if (STMT_VINFO_VECTORIZABLE (stmt_info) ! && !vect_compute_data_ref_alignment (dr)) ! { ! /* Strided accesses perform only component accesses, misalignment ! information is irrelevant for them. */ ! if (STMT_VINFO_STRIDED_P (stmt_info) ! && !STMT_VINFO_GROUPED_ACCESS (stmt_info)) ! continue; ! if (dump_enabled_p ()) ! dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, ! "not vectorized: can't calculate alignment " ! "for data ref.\n"); ! ! return false; ! } } ! return true; ! } ! ! ! /* Analyze alignment of DRs of stmts in NODE. */ ! ! static bool ! vect_slp_analyze_and_verify_node_alignment (slp_tree node) ! { ! unsigned i; ! gimple *stmt; ! FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt) { ! stmt_vec_info stmt_info = vinfo_for_stmt (stmt); ! ! /* Strided accesses perform only component accesses, misalignment ! information is irrelevant for them. */ ! if (STMT_VINFO_STRIDED_P (stmt_info) ! && !STMT_VINFO_GROUPED_ACCESS (stmt_info)) ! continue; ! ! data_reference_p dr = STMT_VINFO_DATA_REF (stmt_info); ! if (! vect_compute_data_ref_alignment (dr) ! || ! verify_data_ref_alignment (dr)) ! { ! if (dump_enabled_p ()) ! dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, ! "not vectorized: bad data alignment in basic " ! "block.\n"); ! return false; ! } } return true; } + + /* Function vect_slp_analyze_instance_alignment + + Analyze the alignment of the data-references in the SLP instance. + Return FALSE if a data reference is found that cannot be vectorized. */ + + bool + vect_slp_analyze_and_verify_instance_alignment (slp_instance instance) + { + if (dump_enabled_p ()) + dump_printf_loc (MSG_NOTE, vect_location, + "=== vect_slp_analyze_and_verify_instance_alignment ===\n"); + + slp_tree node; + unsigned i; + FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance), i, node) + if (! vect_slp_analyze_and_verify_node_alignment (node)) + return false; + + node = SLP_INSTANCE_TREE (instance); + if (STMT_VINFO_DATA_REF (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node)[0])) + && ! vect_slp_analyze_and_verify_node_alignment + (SLP_INSTANCE_TREE (instance))) + return false; + + return true; + } /* Analyze groups of accesses: check that DR belongs to a group of Index: gcc/tree-vect-slp.c =================================================================== *** gcc/tree-vect-slp.c (revision 230155) --- gcc/tree-vect-slp.c (working copy) *************** vect_supported_load_permutation_p (slp_i *** 1282,1289 **** unsigned int group_size = SLP_INSTANCE_GROUP_SIZE (slp_instn); unsigned int i, j, k, next; slp_tree node; ! gimple *stmt, *load, *next_load, *first_load; ! struct data_reference *dr; if (dump_enabled_p ()) { --- 1282,1288 ---- unsigned int group_size = SLP_INSTANCE_GROUP_SIZE (slp_instn); unsigned int i, j, k, next; slp_tree node; ! gimple *stmt, *load, *next_load; if (dump_enabled_p ()) { *************** vect_supported_load_permutation_p (slp_i *** 1365,1397 **** } } } - - /* Check that the alignment of the first load in every subchain, i.e., - the first statement in every load node, is supported. - ??? This belongs in alignment checking. */ - FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node) - { - first_load = SLP_TREE_SCALAR_STMTS (node)[0]; - if (first_load != GROUP_FIRST_ELEMENT (vinfo_for_stmt (first_load))) - { - dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_load)); - if (vect_supportable_dr_alignment (dr, false) - == dr_unaligned_unsupported) - { - if (dump_enabled_p ()) - { - dump_printf_loc (MSG_MISSED_OPTIMIZATION, - vect_location, - "unsupported unaligned load "); - dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, - first_load, 0); - dump_printf (MSG_MISSED_OPTIMIZATION, "\n"); - } - return false; - } - } - } - return true; } --- 1364,1369 ---- *************** vect_bb_vectorization_profitable_p (bb_v *** 2311,2322 **** return true; } ! /* Check if the basic block can be vectorized. */ static bb_vec_info vect_slp_analyze_bb_1 (gimple_stmt_iterator region_begin, gimple_stmt_iterator region_end, ! vec datarefs, int n_stmts) { bb_vec_info bb_vinfo; vec slp_instances; --- 2283,2297 ---- return true; } ! /* Check if the basic block can be vectorized. Returns a bb_vec_info ! if so and sets fatal to true if failure is independent of ! current_vector_size. */ static bb_vec_info vect_slp_analyze_bb_1 (gimple_stmt_iterator region_begin, gimple_stmt_iterator region_end, ! vec datarefs, int n_stmts, ! bool &fatal) { bb_vec_info bb_vinfo; vec slp_instances; *************** vect_slp_analyze_bb_1 (gimple_stmt_itera *** 2324,2329 **** --- 2299,2307 ---- int i; int min_vf = 2; + /* The first group of checks is independent of the vector size. */ + fatal = true; + if (n_stmts > PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB)) { if (dump_enabled_p ()) *************** vect_slp_analyze_bb_1 (gimple_stmt_itera *** 2375,2393 **** return NULL; } ! vect_pattern_recog (bb_vinfo); ! ! if (!vect_analyze_data_refs_alignment (bb_vinfo)) { if (dump_enabled_p ()) ! dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, ! "not vectorized: bad data alignment in basic " ! "block.\n"); destroy_bb_vec_info (bb_vinfo); return NULL; } /* Check the SLP opportunities in the basic block, analyze and build SLP trees. */ if (!vect_analyze_slp (bb_vinfo, n_stmts)) --- 2353,2377 ---- return NULL; } ! /* If there are no grouped stores in the region there is no need ! to continue with pattern recog as vect_analyze_slp will fail ! anyway. */ ! if (bb_vinfo->grouped_stores.is_empty ()) { if (dump_enabled_p ()) ! dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, ! "not vectorized: no grouped stores in " ! "basic block.\n"); destroy_bb_vec_info (bb_vinfo); return NULL; } + /* While the rest of the analysis below depends on it in some way. */ + fatal = false; + + vect_pattern_recog (bb_vinfo); + /* Check the SLP opportunities in the basic block, analyze and build SLP trees. */ if (!vect_analyze_slp (bb_vinfo, n_stmts)) *************** vect_slp_analyze_bb_1 (gimple_stmt_itera *** 2405,2410 **** --- 2389,2418 ---- return NULL; } + /* Analyze and verify the alignment of data references in the SLP + instances. */ + for (i = 0; BB_VINFO_SLP_INSTANCES (bb_vinfo).iterate (i, &instance); ) + { + if (! vect_slp_analyze_and_verify_instance_alignment (instance)) + { + dump_printf_loc (MSG_NOTE, vect_location, + "removing SLP instance operations starting from: "); + dump_gimple_stmt (MSG_NOTE, TDF_SLIM, + SLP_TREE_SCALAR_STMTS + (SLP_INSTANCE_TREE (instance))[0], 0); + vect_free_slp_instance (instance); + BB_VINFO_SLP_INSTANCES (bb_vinfo).ordered_remove (i); + continue; + } + i++; + } + + if (! BB_VINFO_SLP_INSTANCES (bb_vinfo).length ()) + { + destroy_bb_vec_info (bb_vinfo); + return NULL; + } + slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo); /* Mark all the statements that we want to vectorize as pure SLP and *************** vect_slp_analyze_bb_1 (gimple_stmt_itera *** 2427,2449 **** /* Analyze dependences. At this point all stmts not participating in vectorization have to be marked. Dependence analysis assumes that we either vectorize all SLP instances or none at all. */ ! if (!vect_slp_analyze_data_ref_dependences (bb_vinfo)) ! { ! if (dump_enabled_p ()) ! dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, ! "not vectorized: unhandled data dependence " ! "in basic block.\n"); ! ! destroy_bb_vec_info (bb_vinfo); ! return NULL; ! } ! ! if (!vect_verify_datarefs_alignment (bb_vinfo)) { if (dump_enabled_p ()) ! dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, ! "not vectorized: unsupported alignment in basic " ! "block.\n"); destroy_bb_vec_info (bb_vinfo); return NULL; } --- 2435,2447 ---- /* Analyze dependences. At this point all stmts not participating in vectorization have to be marked. Dependence analysis assumes that we either vectorize all SLP instances or none at all. */ ! if (! vect_slp_analyze_data_ref_dependences (bb_vinfo)) { if (dump_enabled_p ()) ! dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, ! "not vectorized: unhandled data dependence " ! "in basic block.\n"); ! destroy_bb_vec_info (bb_vinfo); return NULL; } *************** vect_slp_bb (basic_block bb) *** 2533,2540 **** gimple_stmt_iterator region_end = gsi; bool vectorized = false; bb_vinfo = vect_slp_analyze_bb_1 (region_begin, region_end, ! datarefs, insns); if (bb_vinfo && dbg_cnt (vect_slp)) { --- 2531,2539 ---- gimple_stmt_iterator region_end = gsi; bool vectorized = false; + bool fatal = false; bb_vinfo = vect_slp_analyze_bb_1 (region_begin, region_end, ! datarefs, insns, fatal); if (bb_vinfo && dbg_cnt (vect_slp)) { *************** vect_slp_bb (basic_block bb) *** 2559,2565 **** vector_sizes &= ~current_vector_size; if (vectorized || vector_sizes == 0 ! || current_vector_size == 0) { if (gsi_end_p (region_end)) break; --- 2558,2567 ---- vector_sizes &= ~current_vector_size; if (vectorized || vector_sizes == 0 ! || current_vector_size == 0 ! /* If vect_slp_analyze_bb_1 signaled that analysis for all ! vector sizes will fail do not bother iterating. */ ! || fatal) { if (gsi_end_p (region_end)) break;