From patchwork Mon Jun 19 13:40:30 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Bin.Cheng" X-Patchwork-Id: 777765 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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 3wrsYx15qSz9s89 for ; Mon, 19 Jun 2017 23:40:52 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="JP8alnIE"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; q=dns; s=default; b=I+2wqcw1xQYajR6 s/ZybgkD/b77YqA9L/XqRz2wvR6ALSFYgKwCi3lCxmYj9EmcWG+HUa0yiEeZN7RW SUb+XL24tNfhknM93zFrcy4ytrACvZd3hxKzFsJYXGpzecxyJXzimlJJaFrCOdjN v+FPjzUa0t/4A/soAu0GmibIt47o= 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 :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; s=default; bh=wVqUyHuWJE9ODYiVCYROO wVZXTs=; b=JP8alnIE2/OHeDRRQLQtSK+RrCskmy0TKuBEgNLSA3u5HqYb2eZQB F84XxMmQjg97LJfj1qiHrItLHiCxdPjVQ0mpB+sPxhsNyesceTWgzTi1O3/ZrtIZ rNmIEWqz+zdK+yF2UVF3viS+6p3o2Wn3KdMXjx7Ltn84mdZu6cgwSQ= Received: (qmail 101738 invoked by alias); 19 Jun 2017 13:40:34 -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 100705 invoked by uid 89); 19 Jun 2017 13:40:31 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.7 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=REF, primitive, Simply X-HELO: mail-ua0-f174.google.com Received: from mail-ua0-f174.google.com (HELO mail-ua0-f174.google.com) (209.85.217.174) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 19 Jun 2017 13:40:28 +0000 Received: by mail-ua0-f174.google.com with SMTP id j53so45432077uaa.2 for ; Mon, 19 Jun 2017 06:40:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=ebwf3JB3uvhsFMiGpMW5tPAzjVwkP9uRjkDCb0Y9JT4=; b=U9ykjclpFE3D8S7h2KftyPPaUyTm8BxhiqY05NWVrR7ij9rTuKii6I+PsWNUuTGDT9 hFQtsxiRIBbLye1pgOOPGxACfBAGHzZzh01Deod5RXTADuh1o/qECOGzwptbMByFQsvA 3v9twl/OyqA3ZEmlgbQJL/Dfi8FFmMxm1ZUwrJhD2QvUCF4QCflKFFHHqLBXpqLJSpBe 5n88VlYbmG70QetXKKGkedi31X1qW7VDKOHB1kdizC++ARRJbWBC08cPOa3mF4SjbTOm VN2JEToBkEOSqJO2DYWX5L2S1R86HVOzVmtgfI1kh7uD/W+vln/rb4kjj5w3RzC1pjwH rG3g== X-Gm-Message-State: AKS2vOzrZ3DMdsE3lEUiHG2cV2sejZCkfOdYy0zUGL6J1aXw7nLbc7Ww f2MNqMGKT17NpVyObM8U5+J1dbM2aA== X-Received: by 10.176.95.129 with SMTP id b1mr5123510uaj.144.1497879631609; Mon, 19 Jun 2017 06:40:31 -0700 (PDT) MIME-Version: 1.0 Received: by 10.103.49.142 with HTTP; Mon, 19 Jun 2017 06:40:30 -0700 (PDT) In-Reply-To: References: From: "Bin.Cheng" Date: Mon, 19 Jun 2017 14:40:30 +0100 Message-ID: Subject: Re: [PATCH GCC][09/13]Simply cost model merges partitions with the same references To: Richard Biener Cc: "gcc-patches@gcc.gnu.org" X-IsSubscribed: yes On Wed, Jun 14, 2017 at 2:54 PM, Richard Biener wrote: > On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng wrote: >> Hi, >> Current primitive cost model merges partitions with data references sharing the same >> base address. I believe it's designed to maximize data reuse in distribution, but >> that should be done by dedicated data reusing algorithm. At this stage of merging, >> we should be conservative and only merge partitions with the same references. >> Bootstrap and test on x86_64 and AArch64. Is it OK? > > Well, I'd say "conservative" is merging more, not less. For example > splitting a[i+1] from a[i] > would be bad(?), so I'd see to allow unequal DR_INIT as "equal" for > merging. Maybe > DR_INIT within a cacheline or so. > > How many extra distributions in say SPEC do you get from this change alone? Hi, I collected data for spec2006 only with/without this patch. I am a bit surprised that it doesn't change the number of distributed loops. > > It shows also that having partition->reads_and_writes would be nice > ... the code duplication Yeah, I merged read/write data references in previous patch, now this duplication is gone. Update patch attached. Is it OK? Thanks. bin 2017-06-07 Bin Cheng * tree-loop-distribution.c (ref_base_address): Delete. (similar_memory_accesses): Rename ... (share_memory_accesses): ... to this. Check if partitions access the same memory reference. (distribute_loop): Call share_memory_accesses. From 98af3ab3b309ac7e7b2fb3c6b55eb19a9004225c Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Fri, 9 Jun 2017 12:41:36 +0100 Subject: [PATCH 08/13] share-memory-access-20170608.txt --- gcc/tree-loop-distribution.c | 71 ++++++++++++++++++++------------------------ 1 file changed, 33 insertions(+), 38 deletions(-) diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index 03bb735..2e5a828 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -1268,30 +1268,16 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) } } -/* For a data reference REF, return the declaration of its base - address or NULL_TREE if the base is not determined. */ - -static tree -ref_base_address (data_reference_p dr) -{ - tree base_address = DR_BASE_ADDRESS (dr); - if (base_address - && TREE_CODE (base_address) == ADDR_EXPR) - return TREE_OPERAND (base_address, 0); - - return base_address; -} - -/* Returns true when PARTITION1 and PARTITION2 have similar memory - accesses in RDG. */ +/* Returns true when PARTITION1 and PARTITION2 access the same memory + object in RDG. */ static bool -similar_memory_accesses (struct graph *rdg, partition *partition1, - partition *partition2) +share_memory_accesses (struct graph *rdg, + partition *partition1, partition *partition2) { - unsigned i, j, k, l; + unsigned i, j; bitmap_iterator bi, bj; - data_reference_p ref1, ref2; + data_reference_p dr1, dr2; /* First check whether in the intersection of the two partitions are any loads or stores. Common loads are the situation that happens @@ -1301,23 +1287,32 @@ similar_memory_accesses (struct graph *rdg, partition *partition1, || RDG_MEM_READS_STMT (rdg, i)) return true; - /* Then check all data-references against each other. */ - EXECUTE_IF_SET_IN_BITMAP (partition1->stmts, 0, i, bi) - if (RDG_MEM_WRITE_STMT (rdg, i) - || RDG_MEM_READS_STMT (rdg, i)) - EXECUTE_IF_SET_IN_BITMAP (partition2->stmts, 0, j, bj) - if (RDG_MEM_WRITE_STMT (rdg, j) - || RDG_MEM_READS_STMT (rdg, j)) - { - FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg, i), k, ref1) - { - tree base1 = ref_base_address (ref1); - if (base1) - FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg, j), l, ref2) - if (base1 == ref_base_address (ref2)) - return true; - } - } + /* Then check whether the two partitions access the same memory object. */ + EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi) + { + gcc_assert (i < datarefs_vec.length ()); + dr1 = datarefs_vec[i]; + + if (!DR_BASE_ADDRESS (dr1) + || !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1)) + continue; + + EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, 0, j, bj) + { + gcc_assert (j < datarefs_vec.length ()); + dr2 = datarefs_vec[j]; + + if (!DR_BASE_ADDRESS (dr2) + || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2)) + continue; + + if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0) + && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0) + && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0) + && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0)) + return true; + } + } return false; } @@ -1654,7 +1649,7 @@ distribute_loop (struct loop *loop, vec stmts, for (int j = i + 1; partitions.iterate (j, &partition); ++j) { - if (similar_memory_accesses (rdg, into, partition)) + if (share_memory_accesses (rdg, into, partition)) { partition_merge_into (into, partition, FUSE_SHARE_REF); partitions.unordered_remove (j); -- 1.9.1