From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 36572 invoked by alias); 12 Nov 2015 14:55:15 -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 36351 invoked by uid 89); 12 Nov 2015 14:55:14 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.5 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; Thu, 12 Nov 2015 14:55:11 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id A21ABAD04 for ; Thu, 12 Nov 2015 14:54:45 +0000 (UTC) Date: Thu, 12 Nov 2015 14:55:00 -0000 From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Fix possible correctness issue in BB dependence analysis 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/msg01535.txt.bz2 This fixes BB vectorization dependence analysis to not rely on all instances being vectorized. The dependence check - gimple *earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb)); - if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt)))) - { - /* That only holds for load-store pairs taking part in vectorization. */ - if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dra))) - && STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (drb)))) - return false; effectively does that and we remove instances later. I wasn't able to build a testcase showing this defect as we always fail vectorization for some other reason. Still the following fixes this and implements this special case instance-local only. Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk. Richard. 2015-11-12 Richard Biener * tree-vectorizer.h (vect_slp_analyze_data_ref_dependences): Rename to vect_slp_analyze_instance_dependence. * tree-vect-data-refs.c (vect_slp_analyze_data_ref_dependence): Remove WAR special-case. (vect_slp_analyze_node_dependences): Instead add more specific code here, not relying on other instances being vectorized. (vect_slp_analyze_instance_dependence): Adjust accordingly. * tree-vect-slp.c (vect_build_slp_tree_1): Remove excessive vertical space in dump files. (vect_print_slp_tree): Likewise. (vect_analyze_slp_instance): Dump a header for the final SLP tree. (vect_slp_analyze_bb_1): Delay computing relevant stmts and not vectorized stmts until after dependence analysis removed instances. Merge alignment and dependence checks. * tree-vectorizer.c (pass_slp_vectorize::execute): Clear visited flag on all stmts. Index: gcc/tree-vectorizer.h =================================================================== *** gcc/tree-vectorizer.h (revision 230216) --- gcc/tree-vectorizer.h (working copy) *************** extern enum dr_alignment_support vect_su *** 1009,1015 **** extern tree vect_get_smallest_scalar_type (gimple *, HOST_WIDE_INT *, HOST_WIDE_INT *); 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); --- 1009,1015 ---- extern tree vect_get_smallest_scalar_type (gimple *, HOST_WIDE_INT *, HOST_WIDE_INT *); extern bool vect_analyze_data_ref_dependences (loop_vec_info, int *); ! extern bool vect_slp_analyze_instance_dependence (slp_instance); 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); Index: gcc/tree-vect-data-refs.c =================================================================== *** gcc/tree-vect-data-refs.c (revision 230216) --- gcc/tree-vect-data-refs.c (working copy) *************** vect_slp_analyze_data_ref_dependence (st *** 537,568 **** dump_printf (MSG_NOTE, "\n"); } - /* We do not vectorize basic blocks with write-write dependencies. */ - if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb)) - return true; - - /* If we have a read-write dependence check that the load is before the store. - When we vectorize basic blocks, vector load can be only before - corresponding scalar load, and vector store can be only after its - corresponding scalar store. So the order of the acceses is preserved in - case the load is before the store. */ - gimple *earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb)); - if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt)))) - { - /* That only holds for load-store pairs taking part in vectorization. */ - if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dra))) - && STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (drb)))) - return false; - } - return true; } ! /* Analyze dependences involved in the transform of SLP NODE. */ static bool ! vect_slp_analyze_node_dependences (slp_instance instance, slp_tree node) { /* This walks over all stmts involved in the SLP load/store done in NODE verifying we can sink them up to the last stmt in the --- 559,575 ---- dump_printf (MSG_NOTE, "\n"); } return true; } ! /* Analyze dependences involved in the transform of SLP NODE. STORES ! contain the vector of scalar stores of this instance if we are ! disambiguating the loads. */ static bool ! vect_slp_analyze_node_dependences (slp_instance instance, slp_tree node, ! vec stores, gimple *last_store) { /* This walks over all stmts involved in the SLP load/store done in NODE verifying we can sink them up to the last stmt in the *************** vect_slp_analyze_node_dependences (slp_i *** 584,598 **** /* If we couldn't record a (single) data reference for this stmt we have to give up. */ data_reference *dr_b = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt)); if (!dr_b) return false; ddr_p ddr = initialize_data_dependence_relation (dr_a, dr_b, vNULL); if (vect_slp_analyze_data_ref_dependence (ddr)) { - /* ??? If the dependence analysis failed we can resort to the - alias oracle which can handle more kinds of stmts. */ free_dependence_relation (ddr); return false; } --- 591,630 ---- /* If we couldn't record a (single) data reference for this stmt we have to give up. */ + /* ??? Here and below if dependence analysis fails we can resort + to the alias oracle which can handle more kinds of stmts. */ data_reference *dr_b = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt)); if (!dr_b) return false; + /* If we run into a store of this same instance (we've just + marked those) then delay dependence checking until we run + into the last store because this is where it will have + been sunk to (and we verify if we can do that as well). */ + if (gimple_visited_p (stmt)) + { + if (stmt != last_store) + continue; + unsigned i; + gimple *store; + FOR_EACH_VEC_ELT (stores, i, store) + { + data_reference *store_dr + = STMT_VINFO_DATA_REF (vinfo_for_stmt (store)); + ddr_p ddr = initialize_data_dependence_relation + (dr_a, store_dr, vNULL); + if (vect_slp_analyze_data_ref_dependence (ddr)) + { + free_dependence_relation (ddr); + return false; + } + free_dependence_relation (ddr); + } + } + ddr_p ddr = initialize_data_dependence_relation (dr_a, dr_b, vNULL); if (vect_slp_analyze_data_ref_dependence (ddr)) { free_dependence_relation (ddr); return false; } *************** vect_slp_analyze_node_dependences (slp_i *** 610,661 **** the maximum vectorization factor the data dependences allow. */ bool ! vect_slp_analyze_data_ref_dependences (bb_vec_info bb_vinfo) { if (dump_enabled_p ()) dump_printf_loc (MSG_NOTE, vect_location, ! "=== vect_slp_analyze_data_ref_dependences ===\n"); ! slp_instance instance; ! slp_tree load; ! unsigned int i, j; ! for (i = 0; BB_VINFO_SLP_INSTANCES (bb_vinfo).iterate (i, &instance); ) { ! bool remove = false; ! /* Verify we can sink loads to the vectorized stmt insert location. */ ! FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance), j, load) ! if (! vect_slp_analyze_node_dependences (instance, load)) ! { ! remove = true; ! break; ! } ! /* Verify we can sink stores to the vectorized stmt insert location. */ ! slp_tree store = SLP_INSTANCE_TREE (instance); ! if (!remove ! && STMT_VINFO_DATA_REF ! (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (store)[0])) ! && ! vect_slp_analyze_node_dependences (instance, store)) ! remove = true; ! if (remove) ! { ! 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 ()) ! return false; ! return true; ! } /* Function vect_compute_data_ref_alignment --- 642,694 ---- the maximum vectorization factor the data dependences allow. */ bool ! vect_slp_analyze_instance_dependence (slp_instance instance) { if (dump_enabled_p ()) dump_printf_loc (MSG_NOTE, vect_location, ! "=== vect_slp_analyze_instance_dependence ===\n"); ! /* The stores of this instance are at the root of the SLP tree. */ ! slp_tree store = SLP_INSTANCE_TREE (instance); ! if (! STMT_VINFO_DATA_REF (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (store)[0]))) ! store = NULL; ! ! /* Verify we can sink stores to the vectorized stmt insert location. */ ! gimple *last_store = NULL; ! if (store) { ! if (! vect_slp_analyze_node_dependences (instance, store, vNULL, NULL)) ! return false; ! ! /* Mark stores in this instance and remember the last one. */ ! last_store = vect_find_last_scalar_stmt_in_slp (store); ! for (unsigned k = 0; k < SLP_INSTANCE_GROUP_SIZE (instance); ++k) ! gimple_set_visited (SLP_TREE_SCALAR_STMTS (store)[k], true); } ! bool res = true; ! /* Verify we can sink loads to the vectorized stmt insert location, ! special-casing stores of this instance. */ ! slp_tree load; ! unsigned int i; ! FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance), i, load) ! if (! vect_slp_analyze_node_dependences (instance, load, ! store ! ? SLP_TREE_SCALAR_STMTS (store) ! : vNULL, last_store)) ! { ! res = false; ! break; ! } ! ! /* Unset the visited flag. */ ! if (store) ! for (unsigned k = 0; k < SLP_INSTANCE_GROUP_SIZE (instance); ++k) ! gimple_set_visited (SLP_TREE_SCALAR_STMTS (store)[k], false); + return res; + } /* Function vect_compute_data_ref_alignment Index: gcc/tree-vect-slp.c =================================================================== *** gcc/tree-vect-slp.c (revision 230216) --- gcc/tree-vect-slp.c (working copy) *************** vect_build_slp_tree_1 (vec_info *vinfo, *** 458,464 **** { dump_printf_loc (MSG_NOTE, vect_location, "Build SLP for "); dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0); - dump_printf (MSG_NOTE, "\n"); } /* Fail to vectorize statements marked as unvectorizable. */ --- 458,463 ---- *************** vect_build_slp_tree (vec_info *vinfo, *** 1114,1120 **** /* Dump a slp tree NODE using flags specified in DUMP_KIND. */ static void ! vect_print_slp_tree (int dump_kind, slp_tree node) { int i; gimple *stmt; --- 1113,1119 ---- /* Dump a slp tree NODE using flags specified in DUMP_KIND. */ static void ! vect_print_slp_tree (int dump_kind, location_t loc, slp_tree node) { int i; gimple *stmt; *************** vect_print_slp_tree (int dump_kind, slp_ *** 1123,1138 **** if (!node) return; ! dump_printf (dump_kind, "node "); FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt) { ! dump_printf (dump_kind, "\n\tstmt %d ", i); dump_gimple_stmt (dump_kind, TDF_SLIM, stmt, 0); } - dump_printf (dump_kind, "\n"); - FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) ! vect_print_slp_tree (dump_kind, child); } --- 1122,1135 ---- if (!node) return; ! dump_printf_loc (dump_kind, loc, "node\n"); FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt) { ! dump_printf_loc (dump_kind, loc, "\tstmt %d ", i); dump_gimple_stmt (dump_kind, TDF_SLIM, stmt, 0); } FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) ! vect_print_slp_tree (dump_kind, loc, child); } *************** vect_analyze_slp_instance (vec_info *vin *** 1756,1762 **** vinfo->slp_instances.safe_push (new_instance); if (dump_enabled_p ()) ! vect_print_slp_tree (MSG_NOTE, node); return true; } --- 1753,1763 ---- vinfo->slp_instances.safe_push (new_instance); if (dump_enabled_p ()) ! { ! dump_printf_loc (MSG_NOTE, vect_location, ! "Final SLP tree for instance:\n"); ! vect_print_slp_tree (MSG_NOTE, vect_location, node); ! } return true; } *************** vect_slp_analyze_bb_1 (gimple_stmt_itera *** 2294,2300 **** bool &fatal) { bb_vec_info bb_vinfo; - vec slp_instances; slp_instance instance; int i; int min_vf = 2; --- 2295,2300 ---- *************** vect_slp_analyze_bb_1 (gimple_stmt_itera *** 2389,2399 **** 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: "); --- 2389,2400 ---- return NULL; } ! /* Analyze and verify the alignment of data references and the ! dependence 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) ! || ! vect_slp_analyze_instance_dependence (instance)) { dump_printf_loc (MSG_NOTE, vect_location, "removing SLP instance operations starting from: "); *************** vect_slp_analyze_bb_1 (gimple_stmt_itera *** 2404,2428 **** 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 - relevant. */ - FOR_EACH_VEC_ELT (slp_instances, i, instance) - { - vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1); - vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance)); - } - /* Mark all the statements that we do not want to vectorize. */ for (gimple_stmt_iterator gsi = bb_vinfo->region_begin; gsi_stmt (gsi) != gsi_stmt (bb_vinfo->region_end); gsi_next (&gsi)) --- 2405,2424 ---- BB_VINFO_SLP_INSTANCES (bb_vinfo).ordered_remove (i); continue; } + + /* Mark all the statements that we want to vectorize as pure SLP and + relevant. */ + vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1); + vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance)); + i++; } if (! BB_VINFO_SLP_INSTANCES (bb_vinfo).length ()) { destroy_bb_vec_info (bb_vinfo); return NULL; } /* Mark all the statements that we do not want to vectorize. */ for (gimple_stmt_iterator gsi = bb_vinfo->region_begin; gsi_stmt (gsi) != gsi_stmt (bb_vinfo->region_end); gsi_next (&gsi)) *************** vect_slp_analyze_bb_1 (gimple_stmt_itera *** 2432,2451 **** STMT_VINFO_VECTORIZABLE (vinfo) = false; } - /* 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_slp_analyze_operations (BB_VINFO_SLP_INSTANCES (bb_vinfo), BB_VINFO_TARGET_COST_DATA (bb_vinfo))) { --- 2428,2433 ---- Index: gcc/tree-vectorizer.c =================================================================== --- gcc/tree-vectorizer.c (revision 230260) +++ gcc/tree-vectorizer.c (working copy) @@ -719,12 +719,16 @@ pass_slp_vectorize::execute (function *f scev_initialize (); } - /* Mark all stmts as not belonging to the current region. */ + /* Mark all stmts as not belonging to the current region and unvisited. */ FOR_EACH_BB_FN (bb, fun) { for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - gimple_set_uid (gsi_stmt (gsi), -1); + { + gimple *stmt = gsi_stmt (gsi); + gimple_set_uid (stmt, -1); + gimple_set_visited (stmt, false); + } } init_stmt_vec_info_vec ();