From patchwork Mon Nov 11 18:47:49 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1193066 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-512990-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=arm.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="lWyEGZAU"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47BfyX697Nz9sTb for ; Tue, 12 Nov 2019 05:48:03 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:references:date:in-reply-to:message-id:mime-version :content-type; q=dns; s=default; b=PS4CTHej6JBlKOUBsQslZm0gmvO53 hgVxoMn5eTB6NzWDGGBn+KpTojLMgP3HA2HZlqAz30Mgs2/bzXCrLCkZlxv4rfpX /vl2up0UfDVxGG+FoOoOutHb44VR2PZK0pkvW9ZBc2/XEVF082iRQL7TFPufIGzm 6q+BAXe6nyy3DM= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:references:date:in-reply-to:message-id:mime-version :content-type; s=default; bh=RHYx7kFtKjH2OaAJGg8Yw9RJWY4=; b=lWy EGZAUcSExBF81ymTwzXu3GXkhUgYFu0n+A/lLtaOOa/eNVIH/bvwJ2/PTpctJS3Y 80IOnTJMQkTkcl89wz4vPPYaVVnwgrj3FsNn7DRYu3WSoJgT8KnlN2nCK6LpLtX9 0+/fTEyTakQgM7/SZC9rOsvwUWu/7L50Ttg76fkU= Received: (qmail 6986 invoked by alias); 11 Nov 2019 18:47:55 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 6970 invoked by uid 89); 11 Nov 2019 18:47:54 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-9.3 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, SPF_PASS autolearn=ham version=3.3.1 spammy= X-HELO: foss.arm.com Received: from foss.arm.com (HELO foss.arm.com) (217.140.110.172) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 11 Nov 2019 18:47:52 +0000 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 8148D1FB for ; Mon, 11 Nov 2019 10:47:50 -0800 (PST) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.126]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 28BBD3F52E for ; Mon, 11 Nov 2019 10:47:50 -0800 (PST) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [3/8] Add flags to dr_with_seg_len_pair_t References: Date: Mon, 11 Nov 2019 18:47:49 +0000 In-Reply-To: (Richard Sandiford's message of "Mon, 11 Nov 2019 18:45:00 +0000") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.1 (gnu/linux) MIME-Version: 1.0 X-IsSubscribed: yes This patch adds a bunch of flags to dr_with_seg_len_pair_t, for use by later patches. The update to tree-loop-distribution.c is conservatively correct, but might be tweakable later. 2019-11-11 Richard Sandiford gcc/ * tree-data-ref.h (DR_ALIAS_RAW, DR_ALIAS_WAR, DR_ALIAS_WAW) (DR_ALIAS_ARBITRARY, DR_ALIAS_SWAPPED, DR_ALIAS_UNSWAPPED): New flags. (dr_with_seg_len_pair_t::sequencing): New enum. (dr_with_seg_len_pair_t::flags): New member variable. (dr_with_seg_len_pair_t::dr_with_seg_len_pair_t): Take a sequencing parameter and initialize the flags member variable. * tree-loop-distribution.c (compute_alias_check_pairs): Update call accordingly. * tree-vect-data-refs.c (vect_prune_runtime_alias_test_list): Likewise. Ensure the two data references in an alias pair are in statement order, if there is a defined order. * tree-data-ref.c (prune_runtime_alias_test_list): Use DR_ALIAS_SWAPPED and DR_ALIAS_UNSWAPPED to record whether we've swapped the references in a dr_with_seg_len_pair_t. OR together the flags when merging two dr_with_seg_len_pair_ts. After merging, try to restore the original dr_with_seg_len order, updating the flags if that fails. Index: gcc/tree-data-ref.h =================================================================== --- gcc/tree-data-ref.h 2019-07-10 19:41:26.383898124 +0100 +++ gcc/tree-data-ref.h 2019-11-11 18:30:50.527193443 +0000 @@ -222,20 +222,107 @@ typedef struct data_reference *data_refe unsigned int align; }; +/* Flags that describe a potential alias between two dr_with_seg_lens. + In general, each pair of dr_with_seg_lens represents a composite of + multiple access pairs P, so testing flags like DR_IS_READ on the DRs + does not give meaningful information. + + DR_ALIAS_RAW: + There is a pair in P for which the second reference is a read + and the first is a write. + + DR_ALIAS_WAR: + There is a pair in P for which the second reference is a write + and the first is a read. + + DR_ALIAS_WAW: + There is a pair in P for which both references are writes. + + DR_ALIAS_ARBITRARY: + Either + (a) it isn't possible to classify one pair in P as RAW, WAW or WAR; or + (b) there is a pair in P that breaks the ordering assumption below. + + This flag overrides the RAW, WAR and WAW flags above. + + DR_ALIAS_UNSWAPPED: + DR_ALIAS_SWAPPED: + Temporary flags that indicate whether there is a pair P whose + DRs have or haven't been swapped around. + + The ordering assumption mentioned above is that for every pair + (DR_A, DR_B) in P: + + (1) The original code accesses n elements for DR_A and n elements for DR_B, + interleaved as follows: + + one access of size DR_A.access_size at DR_A.dr + one access of size DR_B.access_size at DR_B.dr + one access of size DR_A.access_size at DR_A.dr + STEP_A + one access of size DR_B.access_size at DR_B.dr + STEP_B + one access of size DR_A.access_size at DR_A.dr + STEP_A * 2 + one access of size DR_B.access_size at DR_B.dr + STEP_B * 2 + ... + + (2) The new code accesses the same data in exactly two chunks: + + one group of accesses spanning |DR_A.seg_len| + DR_A.access_size + one group of accesses spanning |DR_B.seg_len| + DR_B.access_size + + A pair might break this assumption if the DR_A and DR_B accesses + in the original or the new code are mingled in some way. For example, + if DR_A.access_size represents the effect of two individual writes + to nearby locations, the pair breaks the assumption if those writes + occur either side of the access for DR_B. + + Note that DR_ALIAS_ARBITRARY describes whether the ordering assumption + fails to hold for any individual pair in P. If the assumption *does* + hold for every pair in P, it doesn't matter whether it holds for the + composite pair or not. In other words, P should represent the complete + set of pairs that the composite pair is testing, so only the ordering + of two accesses in the same member of P matters. */ +const unsigned int DR_ALIAS_RAW = 1U << 0; +const unsigned int DR_ALIAS_WAR = 1U << 1; +const unsigned int DR_ALIAS_WAW = 1U << 2; +const unsigned int DR_ALIAS_ARBITRARY = 1U << 3; +const unsigned int DR_ALIAS_SWAPPED = 1U << 4; +const unsigned int DR_ALIAS_UNSWAPPED = 1U << 5; + /* This struct contains two dr_with_seg_len objects with aliasing data refs. Two comparisons are generated from them. */ class dr_with_seg_len_pair_t { public: - dr_with_seg_len_pair_t (const dr_with_seg_len& d1, - const dr_with_seg_len& d2) - : first (d1), second (d2) {} + /* WELL_ORDERED indicates that the ordering assumption described above + DR_ALIAS_ARBITRARY holds. REORDERED indicates that it doesn't. */ + enum sequencing { WELL_ORDERED, REORDERED }; + + dr_with_seg_len_pair_t (const dr_with_seg_len &, + const dr_with_seg_len &, sequencing); dr_with_seg_len first; dr_with_seg_len second; + unsigned int flags; }; +inline dr_with_seg_len_pair_t:: +dr_with_seg_len_pair_t (const dr_with_seg_len &d1, const dr_with_seg_len &d2, + sequencing seq) + : first (d1), second (d2), flags (0) +{ + if (DR_IS_READ (d1.dr) && DR_IS_WRITE (d2.dr)) + flags |= DR_ALIAS_WAR; + else if (DR_IS_WRITE (d1.dr) && DR_IS_READ (d2.dr)) + flags |= DR_ALIAS_RAW; + else if (DR_IS_WRITE (d1.dr) && DR_IS_WRITE (d2.dr)) + flags |= DR_ALIAS_WAW; + else + gcc_unreachable (); + if (seq == REORDERED) + flags |= DR_ALIAS_ARBITRARY; +} + enum data_dependence_direction { dir_positive, dir_negative, Index: gcc/tree-loop-distribution.c =================================================================== --- gcc/tree-loop-distribution.c 2019-11-11 18:30:43.207244530 +0000 +++ gcc/tree-loop-distribution.c 2019-11-11 18:30:50.527193443 +0000 @@ -2477,7 +2477,9 @@ compute_alias_check_pairs (class loop *l dr_with_seg_len_pair_t dr_with_seg_len_pair (dr_with_seg_len (dr_a, seg_length_a, access_size_a, align_a), - dr_with_seg_len (dr_b, seg_length_b, access_size_b, align_b)); + dr_with_seg_len (dr_b, seg_length_b, access_size_b, align_b), + /* ??? Would WELL_ORDERED be safe? */ + dr_with_seg_len_pair_t::REORDERED); comp_alias_pairs->safe_push (dr_with_seg_len_pair); } Index: gcc/tree-vect-data-refs.c =================================================================== --- gcc/tree-vect-data-refs.c 2019-11-11 18:30:43.207244530 +0000 +++ gcc/tree-vect-data-refs.c 2019-11-11 18:30:50.531193415 +0000 @@ -3509,10 +3509,13 @@ vect_prune_runtime_alias_test_list (loop dr_vec_info *dr_info_b = loop_vinfo->lookup_dr (DDR_B (ddr)); stmt_vec_info stmt_info_b = dr_info_b->stmt; + bool preserves_scalar_order_p + = vect_preserves_scalar_order_p (dr_info_a, dr_info_b); + /* Skip the pair if inter-iteration dependencies are irrelevant and intra-iteration dependencies are guaranteed to be honored. */ if (ignore_step_p - && (vect_preserves_scalar_order_p (dr_info_a, dr_info_b) + && (preserves_scalar_order_p || vectorizable_with_step_bound_p (dr_info_a, dr_info_b, &lower_bound))) { @@ -3630,11 +3633,21 @@ vect_prune_runtime_alias_test_list (loop stmt_info_b->stmt); } + dr_with_seg_len dr_a (dr_info_a->dr, segment_length_a, + access_size_a, align_a); + dr_with_seg_len dr_b (dr_info_b->dr, segment_length_b, + access_size_b, align_b); + /* Canonicalize the order to be the one that's needed for accurate + RAW, WAR and WAW flags, in cases where the data references are + well-ordered. The order doesn't really matter otherwise, + but we might as well be consistent. */ + if (get_later_stmt (stmt_info_a, stmt_info_b) == stmt_info_a) + std::swap (dr_a, dr_b); + dr_with_seg_len_pair_t dr_with_seg_len_pair - (dr_with_seg_len (dr_info_a->dr, segment_length_a, - access_size_a, align_a), - dr_with_seg_len (dr_info_b->dr, segment_length_b, - access_size_b, align_b)); + (dr_a, dr_b, (preserves_scalar_order_p + ? dr_with_seg_len_pair_t::WELL_ORDERED + : dr_with_seg_len_pair_t::REORDERED)); comp_alias_ddrs.safe_push (dr_with_seg_len_pair); } Index: gcc/tree-data-ref.c =================================================================== --- gcc/tree-data-ref.c 2019-11-11 18:30:47.199216669 +0000 +++ gcc/tree-data-ref.c 2019-11-11 18:30:50.527193443 +0000 @@ -1503,7 +1503,12 @@ prune_runtime_alias_test_list (vec 0) - std::swap (alias_pair->first, alias_pair->second); + { + std::swap (alias_pair->first, alias_pair->second); + alias_pair->flags |= DR_ALIAS_SWAPPED; + } + else + alias_pair->flags |= DR_ALIAS_UNSWAPPED; } /* Sort the collected data ref pairs so that we can scan them once to @@ -1515,10 +1520,13 @@ prune_runtime_alias_test_list (veclength (); ++i) { /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2). */ - dr_with_seg_len *dr_a1 = &(*alias_pairs)[i-1].first, - *dr_b1 = &(*alias_pairs)[i-1].second, - *dr_a2 = &(*alias_pairs)[i].first, - *dr_b2 = &(*alias_pairs)[i].second; + dr_with_seg_len_pair_t *alias_pair1 = &(*alias_pairs)[i - 1]; + dr_with_seg_len_pair_t *alias_pair2 = &(*alias_pairs)[i]; + + dr_with_seg_len *dr_a1 = &alias_pair1->first; + dr_with_seg_len *dr_b1 = &alias_pair1->second; + dr_with_seg_len *dr_a2 = &alias_pair2->first; + dr_with_seg_len *dr_b2 = &alias_pair2->second; /* Remove duplicate data ref pairs. */ if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2) @@ -1527,6 +1535,7 @@ prune_runtime_alias_test_list (vecdr), DR_REF (dr_b1->dr), DR_REF (dr_a2->dr), DR_REF (dr_b2->dr)); + alias_pair1->flags |= alias_pair2->flags; alias_pairs->ordered_remove (i--); continue; } @@ -1632,10 +1641,26 @@ prune_runtime_alias_test_list (vecdr), DR_REF (dr_b1->dr), DR_REF (dr_a2->dr), DR_REF (dr_b2->dr)); + alias_pair1->flags |= alias_pair2->flags; alias_pairs->ordered_remove (i); i--; } } + + /* Try to restore the original dr_with_seg_len order within each + dr_with_seg_len_pair_t. If we ended up combining swapped and + unswapped pairs into the same check, we have to invalidate any + RAW, WAR and WAW information for it. */ + FOR_EACH_VEC_ELT (*alias_pairs, i, alias_pair) + { + unsigned int swap_mask = (DR_ALIAS_SWAPPED | DR_ALIAS_UNSWAPPED); + unsigned int swapped = (alias_pair->flags & swap_mask); + if (swapped == DR_ALIAS_SWAPPED) + std::swap (alias_pair->first, alias_pair->second); + else if (swapped != DR_ALIAS_UNSWAPPED) + alias_pair->flags |= DR_ALIAS_ARBITRARY; + alias_pair->flags &= ~swap_mask; + } } /* Given LOOP's two data references and segment lengths described by DR_A