From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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-Archive: List-Post: List-Help: Sender: gcc-patches-owner@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 10:22:00 -0000 Message-ID: Subject: Re: [PATCH GCC][10/13]Compute and cache data dependence relation To: Richard Biener Cc: "gcc-patches@gcc.gnu.org" Content-Type: multipart/mixed; boundary="001a114e549ad5d41105529df931" X-IsSubscribed: yes X-SW-Source: 2017-06/txt/msg01754.txt.bz2 --001a114e549ad5d41105529df931 Content-Type: text/plain; charset="UTF-8" Content-length: 2731 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. --001a114e549ad5d41105529df931 Content-Type: text/x-patch; charset="US-ASCII"; name="0009-cache-data-dependence-20170609.txt.patch" Content-Disposition: attachment; filename="0009-cache-data-dependence-20170609.txt.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: f_j49pja9j0 Content-length: 7691 RnJvbSBmMWJjNTQzN2ExODZhZjIyMzk4YzZhYjcwNzFiYTFlZjhkMGRkODk3 IE1vbiBTZXAgMTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBCaW4gQ2hlbmcgPGJp bmNoZTAxQGUxMDg0NTEtbGluLmNhbWJyaWRnZS5hcm0uY29tPgpEYXRlOiBG cmksIDkgSnVuIDIwMTcgMTM6MDI6MDkgKzAxMDAKU3ViamVjdDogW1BBVENI IDA5LzEzXSBjYWNoZS1kYXRhLWRlcGVuZGVuY2UtMjAxNzA2MDkudHh0Cgot LS0KIGdjYy90cmVlLWxvb3AtZGlzdHJpYnV0aW9uLmMgfCA5OSArKysrKysr KysrKysrKysrKysrKysrKysrKysrKysrKy0tLS0tLS0tLS0tLQogMSBmaWxl IGNoYW5nZWQsIDczIGluc2VydGlvbnMoKyksIDI2IGRlbGV0aW9ucygtKQoK ZGlmZiAtLWdpdCBhL2djYy90cmVlLWxvb3AtZGlzdHJpYnV0aW9uLmMgYi9n Y2MvdHJlZS1sb29wLWRpc3RyaWJ1dGlvbi5jCmluZGV4IDExOTg2M2YuLjUx NmQ1ZjcgMTAwNjQ0Ci0tLSBhL2djYy90cmVlLWxvb3AtZGlzdHJpYnV0aW9u LmMKKysrIGIvZ2NjL3RyZWUtbG9vcC1kaXN0cmlidXRpb24uYwpAQCAtNzAs NiArNzAsMzUgQEAgYWxvbmcgd2l0aCBHQ0M7IHNlZSB0aGUgZmlsZSBDT1BZ SU5HMy4gIElmIG5vdCBzZWUKICNkZWZpbmUgTUFYX0RBVEFSRUZTX05VTSBc CiAJKCh1bnNpZ25lZCkgUEFSQU1fVkFMVUUgKFBBUkFNX0xPT1BfTUFYX0RB VEFSRUZTX0ZPUl9EQVRBREVQUykpCiAKKy8qIEhhc2h0YWJsZSBoZWxwZXJz LiAgKi8KKworc3RydWN0IGRkcl9oYXNoZXIgOiBub2ZyZWVfcHRyX2hhc2gg PHN0cnVjdCBkYXRhX2RlcGVuZGVuY2VfcmVsYXRpb24+Cit7CisgIHN0YXRp YyBpbmxpbmUgaGFzaHZhbF90IGhhc2ggKGNvbnN0IGRhdGFfZGVwZW5kZW5j ZV9yZWxhdGlvbiAqKTsKKyAgc3RhdGljIGlubGluZSBib29sIGVxdWFsIChj b25zdCBkYXRhX2RlcGVuZGVuY2VfcmVsYXRpb24gKiwKKwkJCSAgICBjb25z dCBkYXRhX2RlcGVuZGVuY2VfcmVsYXRpb24gKik7Cit9OworCisvKiBIYXNo IGZ1bmN0aW9uIGZvciBkYXRhIGRlcGVuZGVuY2UuICAqLworCitpbmxpbmUg aGFzaHZhbF90CitkZHJfaGFzaGVyOjpoYXNoIChjb25zdCBkYXRhX2RlcGVu ZGVuY2VfcmVsYXRpb24gKmRkcikKK3sKKyAgaW5jaGFzaDo6aGFzaCBoOwor ICBoLmFkZF9wdHIgKEREUl9BIChkZHIpKTsKKyAgaC5hZGRfcHRyIChERFJf QiAoZGRyKSk7CisgIHJldHVybiBoLmVuZCAoKTsKK30KKworLyogSGFzaCB0 YWJsZSBlcXVhbGl0eSBmdW5jdGlvbiBmb3IgZGF0YSBkZXBlbmRlbmNlLiAg Ki8KKworaW5saW5lIGJvb2wKK2Rkcl9oYXNoZXI6OmVxdWFsIChjb25zdCBk YXRhX2RlcGVuZGVuY2VfcmVsYXRpb24gKmRkcjEsCisJCSAgIGNvbnN0IGRh dGFfZGVwZW5kZW5jZV9yZWxhdGlvbiAqZGRyMikKK3sKKyAgcmV0dXJuIChE RFJfQSAoZGRyMSkgPT0gRERSX0EgKGRkcjIpICYmIEREUl9CIChkZHIxKSA9 PSBERFJfQiAoZGRyMikpOworfQorCiAvKiBUaGUgbG9vcCAobmVzdCkgdG8g YmUgZGlzdHJpYnV0ZWQuICAqLwogc3RhdGljIHZlYzxsb29wX3A+IGxvb3Bf bmVzdDsKIApAQCAtNzksNiArMTA4LDEwIEBAIHN0YXRpYyB2ZWM8ZGF0YV9y ZWZlcmVuY2VfcD4gZGF0YXJlZnNfdmVjOwogLyogU3RvcmUgaW5kZXggb2Yg ZGF0YSByZWZlcmVuY2UgaW4gYXV4IGZpZWxkLiAgKi8KICNkZWZpbmUgRFJf SU5ERVgoZHIpICAgICAgKCh1aW50cHRyX3QpIChkciktPmF1eCkKIAorLyog SGFzaCB0YWJsZSBmb3IgZGF0YSBkZXBlbmRlbmNlIHJlbGF0aW9uIGluIHRo ZSBsb29wIHRvIGJlIGRpc3RyaWJ1dGVkLiAgKi8KK3N0YXRpYyBoYXNoX3Rh YmxlPGRkcl9oYXNoZXI+IGRkcnNfdGFibGUgKDM4OSk7CisKKwogLyogQSBS ZWR1Y2VkIERlcGVuZGVuY2UgR3JhcGggKFJERykgdmVydGV4IHJlcHJlc2Vu dGluZyBhIHN0YXRlbWVudC4gICovCiBzdHJ1Y3QgcmRnX3ZlcnRleAogewpA QCAtMTA1Nyw2ICsxMDkwLDMyIEBAIGdlbmVyYXRlX2NvZGVfZm9yX3BhcnRp dGlvbiAoc3RydWN0IGxvb3AgKmxvb3AsCiAgIHJldHVybiBmYWxzZTsKIH0K IAorLyogUmV0dXJuIGRhdGEgZGVwZW5kZW5jZSByZWxhdGlvbiBmb3IgZGF0 YSByZWZlcmVuY2VzIEEgYW5kIEIuICBUaGUgdHdvCisgICBkYXRhIHJlZmVy ZW5jZXMgbXVzdCBiZSBpbiBsZXhpY29ncmFwaGljIG9yZGVyIHdydG8gcmVk dWNlZCBkZXBlbmRlbmNlCisgICBncmFwaCBSREcuICBXZSBmaXJzdGx5IHRy eSB0byBmaW5kIGRkciBmcm9tIGdsb2JhbCBkZHIgaGFzaCB0YWJsZS4gIElm CisgICBpdCBkb2Vzbid0IGV4aXN0LCBjb21wdXRlIHRoZSBkZHIgYW5kIGNh Y2hlIGl0LiAgKi8KKworc3RhdGljIGRhdGFfZGVwZW5kZW5jZV9yZWxhdGlv biAqCitnZXRfZGF0YV9kZXBlbmRlbmNlIChzdHJ1Y3QgZ3JhcGggKnJkZywg ZGF0YV9yZWZlcmVuY2VfcCBhLCBkYXRhX3JlZmVyZW5jZV9wIGIpCit7Cisg IHN0cnVjdCBkYXRhX2RlcGVuZGVuY2VfcmVsYXRpb24gZW50LCAqKnNsb3Q7 CisgIHN0cnVjdCBkYXRhX2RlcGVuZGVuY2VfcmVsYXRpb24gKmRkcjsKKwor ICBnY2NfYXNzZXJ0IChEUl9JU19XUklURSAoYSkgfHwgRFJfSVNfV1JJVEUg KGIpKTsKKyAgZ2NjX2Fzc2VydCAocmRnX3ZlcnRleF9mb3Jfc3RtdCAocmRn LCBEUl9TVE1UIChhKSkKKwkgICAgICA8PSByZGdfdmVydGV4X2Zvcl9zdG10 IChyZGcsIERSX1NUTVQgKGIpKSk7CisgIGVudC5hID0gYTsKKyAgZW50LmIg PSBiOworICBzbG90ID0gZGRyc190YWJsZS5maW5kX3Nsb3QgKCZlbnQsIElO U0VSVCk7CisgIGlmICgqc2xvdCA9PSBOVUxMKQorICAgIHsKKyAgICAgIGRk ciA9IGluaXRpYWxpemVfZGF0YV9kZXBlbmRlbmNlX3JlbGF0aW9uIChhLCBi LCBsb29wX25lc3QpOworICAgICAgY29tcHV0ZV9hZmZpbmVfZGVwZW5kZW5j ZSAoZGRyLCBsb29wX25lc3RbMF0pOworICAgICAgKnNsb3QgPSBkZHI7Cisg ICAgfQorCisgIHJldHVybiAqc2xvdDsKK30KIAogLyogUmV0dXJucyBhIHBh cnRpdGlvbiB3aXRoIGFsbCB0aGUgc3RhdGVtZW50cyBuZWVkZWQgZm9yIGNv bXB1dGluZwogICAgdGhlIHZlcnRleCBWIG9mIHRoZSBSREcsIGFsc28gaW5j bHVkaW5nIHRoZSBsb29wIGV4aXQgY29uZGl0aW9ucy4gICovCkBAIC0xMjIz LDQ0ICsxMjgyLDI3IEBAIGNsYXNzaWZ5X3BhcnRpdGlvbiAobG9vcF9wIGxv b3AsIHN0cnVjdCBncmFwaCAqcmRnLCBwYXJ0aXRpb24gKnBhcnRpdGlvbikK IAlyZXR1cm47CiAgICAgICAvKiBOb3cgY2hlY2sgdGhhdCBpZiB0aGVyZSBp cyBhIGRlcGVuZGVuY2UgdGhpcyBkZXBlbmRlbmNlIGlzCiAgICAgICAgICBv ZiBhIHN1aXRhYmxlIGZvcm0gZm9yIG1lbW1vdmUuICAqLwotICAgICAgdmVj PGxvb3BfcD4gbG9vcHMgPSB2TlVMTDsKLSAgICAgIGRkcl9wIGRkcjsKLSAg ICAgIGxvb3BzLnNhZmVfcHVzaCAobG9vcCk7Ci0gICAgICBkZHIgPSBpbml0 aWFsaXplX2RhdGFfZGVwZW5kZW5jZV9yZWxhdGlvbiAoc2luZ2xlX2xvYWQs IHNpbmdsZV9zdG9yZSwKLQkJCQkJCSBsb29wcyk7Ci0gICAgICBjb21wdXRl X2FmZmluZV9kZXBlbmRlbmNlIChkZHIsIGxvb3ApOworICAgICAgZGRyX3Ag ZGRyID0gZ2V0X2RhdGFfZGVwZW5kZW5jZSAocmRnLCBzaW5nbGVfbG9hZCwg c2luZ2xlX3N0b3JlKTsKICAgICAgIGlmIChERFJfQVJFX0RFUEVOREVOVCAo ZGRyKSA9PSBjaHJlY19kb250X2tub3cpCi0JewotCSAgZnJlZV9kZXBlbmRl bmNlX3JlbGF0aW9uIChkZHIpOwotCSAgbG9vcHMucmVsZWFzZSAoKTsKLQkg IHJldHVybjsKLQl9CisJcmV0dXJuOworCiAgICAgICBpZiAoRERSX0FSRV9E RVBFTkRFTlQgKGRkcikgIT0gY2hyZWNfa25vd24pCiAJewogCSAgaWYgKERE Ul9OVU1fRElTVF9WRUNUUyAoZGRyKSA9PSAwKQotCSAgICB7Ci0JICAgICAg ZnJlZV9kZXBlbmRlbmNlX3JlbGF0aW9uIChkZHIpOwotCSAgICAgIGxvb3Bz LnJlbGVhc2UgKCk7Ci0JICAgICAgcmV0dXJuOwotCSAgICB9CisJICAgIHJl dHVybjsKKwogCSAgbGFtYmRhX3ZlY3RvciBkaXN0X3Y7CiAJICBGT1JfRUFD SF9WRUNfRUxUIChERFJfRElTVF9WRUNUUyAoZGRyKSwgaSwgZGlzdF92KQog CSAgICB7CiAJICAgICAgaW50IGRpc3QgPSBkaXN0X3ZbaW5kZXhfaW5fbG9v cF9uZXN0IChsb29wLT5udW0sCiAJCQkJCQkgICAgRERSX0xPT1BfTkVTVCAo ZGRyKSldOwogCSAgICAgIGlmIChkaXN0ID4gMCAmJiAhRERSX1JFVkVSU0VE X1AgKGRkcikpCi0JCXsKLQkJICBmcmVlX2RlcGVuZGVuY2VfcmVsYXRpb24g KGRkcik7Ci0JCSAgbG9vcHMucmVsZWFzZSAoKTsKLQkJICByZXR1cm47Ci0J CX0KKwkJcmV0dXJuOwogCSAgICB9CiAJICBwYXJ0aXRpb24tPmtpbmQgPSBQ S0lORF9NRU1NT1ZFOwogCX0KICAgICAgIGVsc2UKIAlwYXJ0aXRpb24tPmtp bmQgPSBQS0lORF9NRU1DUFk7Ci0gICAgICBmcmVlX2RlcGVuZGVuY2VfcmVs YXRpb24gKGRkcik7Ci0gICAgICBsb29wcy5yZWxlYXNlICgpOwogICAgICAg cGFydGl0aW9uLT5tYWluX2RyID0gc2luZ2xlX3N0b3JlOwogICAgICAgcGFy dGl0aW9uLT5zZWNvbmRhcnlfZHIgPSBzaW5nbGVfbG9hZDsKICAgICAgIHBh cnRpdGlvbi0+bml0ZXIgPSBuYl9pdGVyOwpAQCAtMTQ3Miw4ICsxNTE0LDcg QEAgcGdfYWRkX2RlcGVuZGVuY2VfZWRnZXMgKHN0cnVjdCBncmFwaCAqcmRn LCBpbnQgZGlyLAogCSAgICAgIHN0ZDo6c3dhcCAoZHIxLCBkcjIpOwogCSAg ICAgIHRoaXNfZGlyID0gLXRoaXNfZGlyOwogCSAgICB9Ci0JICBkZHIgPSBp bml0aWFsaXplX2RhdGFfZGVwZW5kZW5jZV9yZWxhdGlvbiAoZHIxLCBkcjIs IGxvb3BfbmVzdCk7Ci0JICBjb21wdXRlX2FmZmluZV9kZXBlbmRlbmNlIChk ZHIsIGxvb3BfbmVzdFswXSk7CisJICBkZHIgPSBnZXRfZGF0YV9kZXBlbmRl bmNlIChyZGcsIGRyMSwgZHIyKTsKIAkgIGlmIChERFJfQVJFX0RFUEVOREVO VCAoZGRyKSA9PSBjaHJlY19kb250X2tub3cpCiAJICAgIHRoaXNfZGlyID0g MjsKIAkgIGVsc2UgaWYgKEREUl9BUkVfREVQRU5ERU5UIChkZHIpID09IE5V TExfVFJFRSkKQEAgLTE0OTksNyArMTU0MCw2IEBAIHBnX2FkZF9kZXBlbmRl bmNlX2VkZ2VzIChzdHJ1Y3QgZ3JhcGggKnJkZywgaW50IGRpciwKIAkgICAg fQogCSAgZWxzZQogCSAgICB0aGlzX2RpciA9IDA7Ci0JICBmcmVlX2RlcGVu ZGVuY2VfcmVsYXRpb24gKGRkcik7CiAJICBpZiAodGhpc19kaXIgPT0gMikK IAkgICAgcmV0dXJuIDI7CiAJICBlbHNlIGlmIChkaXIgPT0gMCkKQEAgLTE3 NjIsNiArMTgwMiwxMyBAQCBkaXN0cmlidXRlX2xvb3AgKHN0cnVjdCBsb29w ICpsb29wLCB2ZWM8Z2ltcGxlICo+IHN0bXRzLAogIGxkaXN0X2RvbmU6CiAg IGxvb3BfbmVzdC5yZWxlYXNlICgpOwogICBmcmVlX2RhdGFfcmVmcyAoZGF0 YXJlZnNfdmVjKTsKKyAgZm9yIChoYXNoX3RhYmxlPGRkcl9oYXNoZXI+Ojpp dGVyYXRvciBpdGVyID0gZGRyc190YWJsZS5iZWdpbiAoKTsKKyAgICAgICBp dGVyICE9IGRkcnNfdGFibGUuZW5kICgpOyArK2l0ZXIpCisgICAgeworICAg ICAgZnJlZV9kZXBlbmRlbmNlX3JlbGF0aW9uICgqaXRlcik7CisgICAgICAq aXRlciA9IE5VTEw7CisgICAgfQorICBkZHJzX3RhYmxlLmVtcHR5ICgpOwog CiAgIEZPUl9FQUNIX1ZFQ19FTFQgKHBhcnRpdGlvbnMsIGksIHBhcnRpdGlv bikKICAgICBwYXJ0aXRpb25fZnJlZSAocGFydGl0aW9uKTsKLS0gCjEuOS4x Cgo= --001a114e549ad5d41105529df931--