From patchwork Fri Jun 23 10:22:17 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Bin.Cheng" X-Patchwork-Id: 779936 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 3wvDzj6j64z9s7M for ; Fri, 23 Jun 2017 20:22:57 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="QnjfULcw"; 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=WMiZNZvBh48tWlc rDrYvmxnx+8DBrJwmDT0W/1Z0aA1dT7UmyR0TmjcxwAZso46+Znvlo5rzoQ4mEVW MvF1i82Su+6qUekeq01Y0YAUMBRGYIXWnz1jBPoSXp8183m2OsVtpHeCCyrojH7p jOU2Qw2+2CjUu1KzfUPdIEOuonOQ= 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=gT3A9vneZDo/levuDzeQ1 dZ1Ddg=; b=QnjfULcw0dK1RtFpyQyMGZX0T1LlHnNBrV/29o2NaAluyzim/plaQ DH5H+oXPFU33sIBatE/jraI1fEgCIXOBT0hNpFStQoIJS7TJyH7acinWNZP1jV/6 hgLTJKZV+M4dJzKssdRM6/rLm5ebSGZwz9N56ycmU+qdR0RDP6dmpw= Received: (qmail 39616 invoked by alias); 23 Jun 2017 10:22:27 -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 39263 invoked by uid 89); 23 Jun 2017 10:22:25 -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=Hx-spam-relays-external:sk:mail-vk, H*RU:sk:mail-vk, H*r:sk:mail-vk X-HELO: mail-vk0-f66.google.com Received: from mail-vk0-f66.google.com (HELO mail-vk0-f66.google.com) (209.85.213.66) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 23 Jun 2017 10:22:20 +0000 Received: by mail-vk0-f66.google.com with SMTP id 82so411974vki.0 for ; Fri, 23 Jun 2017 03:22:19 -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=Mr/jE3jsBOnQ9mFeFHiZT497nr765Q15snheFj381Ao=; b=cGDpAktsHZkdJVQE63DKnNHr6S+BEgno4+zxEDZuYRDNKVMj20Hww50NQ7hLa8LtxS Sz3bPdcgfmXGH5PHEIIWJRTYSz7kT+O9fFU6vLpp5Jo9ZNRAXvgngCJPI4Dczy4NCmep dGAhKnQvkH/WhBBbaJ0Pz8lMkKTKM4XwpY+COOtyNbCg4Rtj5J/NxYDLc2Hp2WbhWYH5 aVquKn4xIZPiiz1Dc1nOysjU1RvjZYBEkrVYiHMfyb9V9hwDARidtweEoUhBsH61h9QQ GUCq8XBS7ulpiRuHzptpfs/fFBvL+3uS9i/LEWX0vKn1pp32jaE3/YLhMIlpKdvl6UUK 85Ug== X-Gm-Message-State: AKS2vOzWTL+Hr7gsNO3ecJwNM9+IoDArFt2QNbVM7ySMZQs/3JQ6wH88 uVo0ah/xbsldnH5ATcGvTghDMX3b2g== X-Received: by 10.31.84.4 with SMTP id i4mr2321865vkb.142.1498213338403; Fri, 23 Jun 2017 03:22:18 -0700 (PDT) MIME-Version: 1.0 Received: by 10.103.49.142 with HTTP; Fri, 23 Jun 2017 03:22:17 -0700 (PDT) In-Reply-To: References: From: "Bin.Cheng" Date: Fri, 23 Jun 2017 11:22:17 +0100 Message-ID: Subject: Re: [PATCH GCC][10/13]Compute and cache data dependence relation To: Richard Biener Cc: "gcc-patches@gcc.gnu.org" X-IsSubscribed: yes On Tue, Jun 20, 2017 at 12:32 PM, Richard Biener wrote: > On Tue, Jun 20, 2017 at 11:15 AM, Bin.Cheng wrote: >> On Fri, Jun 16, 2017 at 11:03 AM, Richard Biener >> wrote: >>> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng wrote: >>>> Hi, >>>> This patch computes and caches data dependence relation in a hash table >>>> so that it can be queried multiple times later for partition dependence >>>> check. >>>> Bootstrap and test on x86_64 and AArch64. Is it OK? >>> >>> +/* Vector of data dependence relations. */ >>> +static vec *ddrs_vec; >>> + >>> +/* Hash table for data dependence relation in the loop to be distributed. */ >>> +static hash_table *ddrs_table; >>> >>> avoid the extra indirection. >>> >>> +/* Hashtable entry for data reference relation. */ >>> +struct ddr_entry >>> +{ >>> + data_reference_p a; >>> + data_reference_p b; >>> + ddr_p ddr; >>> + hashval_t hash; >>> +}; >>> ... >>> +/* Hash table equality function for data reference relation. */ >>> + >>> +inline bool >>> +ddr_entry_hasher::equal (const ddr_entry *entry1, const ddr_entry *entry2) >>> +{ >>> + return (entry1->hash == entry2->hash >>> + && DR_STMT (entry1->a) == DR_STMT (entry2->a) >>> + && DR_STMT (entry1->b) == DR_STMT (entry2->b) >>> + && operand_equal_p (DR_REF (entry1->a), DR_REF (entry2->a), 0) >>> + && operand_equal_p (DR_REF (entry1->b), DR_REF (entry2->b), 0)); >>> +} >>> >>> what's the issue with using hash_table with a custom hasher? >>> That is, simply key on the dataref pointers (hash them, compare those >>> for equality)? >>> >>> Your scheme looks too complicated / expensive to me ... >>> >>> You can drop ddrs_vec needed only for memory removal if you traverse >>> the hashtable. >> Thanks for reviewing. Patch simplified as suggested. Is it OK? > > +inline hashval_t > +ddr_hasher::hash (const data_dependence_relation *ddr) > +{ > + return iterative_hash_object (DDR_A (ddr), > + iterative_hash_object (DDR_B (ddr), 0)); > +} > + > > please use > > inchash::hash h; > h.add_ptr (DDR_A (ddr)); > h.add_ptr (DDR_B (ddr)); > return h.end (); > > Ok with that change. Done, patch updated. Thanks, bin > > Richard. > >> Thanks, >> bin >> 2017-06-17 Bin Cheng >> >> * tree-loop-distribution.c (struct ddr_hasher): New. >> (ddr_hasher::hash, ::equal, get_data_dependence): New function. >> (ddrs_table): New. >> (classify_partition): Call get_data_dependence. >> (pg_add_dependence_edges): Ditto. >> (distribute_loop): Release data dependence hash table. From f1bc5437a186af22398c6ab7071ba1ef8d0dd897 Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Fri, 9 Jun 2017 13:02:09 +0100 Subject: [PATCH 09/13] cache-data-dependence-20170609.txt --- gcc/tree-loop-distribution.c | 99 ++++++++++++++++++++++++++++++++------------ 1 file changed, 73 insertions(+), 26 deletions(-) diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index 119863f..516d5f7 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -70,6 +70,35 @@ along with GCC; see the file COPYING3. If not see #define MAX_DATAREFS_NUM \ ((unsigned) PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS)) +/* Hashtable helpers. */ + +struct ddr_hasher : nofree_ptr_hash +{ + static inline hashval_t hash (const data_dependence_relation *); + static inline bool equal (const data_dependence_relation *, + const data_dependence_relation *); +}; + +/* Hash function for data dependence. */ + +inline hashval_t +ddr_hasher::hash (const data_dependence_relation *ddr) +{ + inchash::hash h; + h.add_ptr (DDR_A (ddr)); + h.add_ptr (DDR_B (ddr)); + return h.end (); +} + +/* Hash table equality function for data dependence. */ + +inline bool +ddr_hasher::equal (const data_dependence_relation *ddr1, + const data_dependence_relation *ddr2) +{ + return (DDR_A (ddr1) == DDR_A (ddr2) && DDR_B (ddr1) == DDR_B (ddr2)); +} + /* The loop (nest) to be distributed. */ static vec loop_nest; @@ -79,6 +108,10 @@ static vec datarefs_vec; /* Store index of data reference in aux field. */ #define DR_INDEX(dr) ((uintptr_t) (dr)->aux) +/* Hash table for data dependence relation in the loop to be distributed. */ +static hash_table ddrs_table (389); + + /* A Reduced Dependence Graph (RDG) vertex representing a statement. */ struct rdg_vertex { @@ -1057,6 +1090,32 @@ generate_code_for_partition (struct loop *loop, return false; } +/* Return data dependence relation for data references A and B. The two + data references must be in lexicographic order wrto reduced dependence + graph RDG. We firstly try to find ddr from global ddr hash table. If + it doesn't exist, compute the ddr and cache it. */ + +static data_dependence_relation * +get_data_dependence (struct graph *rdg, data_reference_p a, data_reference_p b) +{ + struct data_dependence_relation ent, **slot; + struct data_dependence_relation *ddr; + + gcc_assert (DR_IS_WRITE (a) || DR_IS_WRITE (b)); + gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a)) + <= rdg_vertex_for_stmt (rdg, DR_STMT (b))); + ent.a = a; + ent.b = b; + slot = ddrs_table.find_slot (&ent, INSERT); + if (*slot == NULL) + { + ddr = initialize_data_dependence_relation (a, b, loop_nest); + compute_affine_dependence (ddr, loop_nest[0]); + *slot = ddr; + } + + return *slot; +} /* Returns a partition with all the statements needed for computing the vertex V of the RDG, also including the loop exit conditions. */ @@ -1223,44 +1282,27 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) return; /* Now check that if there is a dependence this dependence is of a suitable form for memmove. */ - vec loops = vNULL; - ddr_p ddr; - loops.safe_push (loop); - ddr = initialize_data_dependence_relation (single_load, single_store, - loops); - compute_affine_dependence (ddr, loop); + ddr_p ddr = get_data_dependence (rdg, single_load, single_store); if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) - { - free_dependence_relation (ddr); - loops.release (); - return; - } + return; + if (DDR_ARE_DEPENDENT (ddr) != chrec_known) { if (DDR_NUM_DIST_VECTS (ddr) == 0) - { - free_dependence_relation (ddr); - loops.release (); - return; - } + return; + lambda_vector dist_v; FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v) { int dist = dist_v[index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr))]; if (dist > 0 && !DDR_REVERSED_P (ddr)) - { - free_dependence_relation (ddr); - loops.release (); - return; - } + return; } partition->kind = PKIND_MEMMOVE; } else partition->kind = PKIND_MEMCPY; - free_dependence_relation (ddr); - loops.release (); partition->main_dr = single_store; partition->secondary_dr = single_load; partition->niter = nb_iter; @@ -1472,8 +1514,7 @@ pg_add_dependence_edges (struct graph *rdg, int dir, std::swap (dr1, dr2); this_dir = -this_dir; } - ddr = initialize_data_dependence_relation (dr1, dr2, loop_nest); - compute_affine_dependence (ddr, loop_nest[0]); + ddr = get_data_dependence (rdg, dr1, dr2); if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) this_dir = 2; else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) @@ -1499,7 +1540,6 @@ pg_add_dependence_edges (struct graph *rdg, int dir, } else this_dir = 0; - free_dependence_relation (ddr); if (this_dir == 2) return 2; else if (dir == 0) @@ -1762,6 +1802,13 @@ distribute_loop (struct loop *loop, vec stmts, ldist_done: loop_nest.release (); free_data_refs (datarefs_vec); + for (hash_table::iterator iter = ddrs_table.begin (); + iter != ddrs_table.end (); ++iter) + { + free_dependence_relation (*iter); + *iter = NULL; + } + ddrs_table.empty (); FOR_EACH_VEC_ELT (partitions, i, partition) partition_free (partition); -- 1.9.1