From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 77293 invoked by alias); 20 Jun 2017 09:18:21 -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 77269 invoked by uid 89); 20 Jun 2017 09:18:20 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.8 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=cycle X-HELO: mail-ua0-f171.google.com Received: from mail-ua0-f171.google.com (HELO mail-ua0-f171.google.com) (209.85.217.171) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 20 Jun 2017 09:18:18 +0000 Received: by mail-ua0-f171.google.com with SMTP id d45so35121858uai.1 for ; Tue, 20 Jun 2017 02:18:18 -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=T4zSdPMdnz1Tkue30jBoZM5joZyoToYJQgA4xl2ylb4=; b=oJfFAnwWllgkxKZXRMha9hFmxqMC+Rh/RElULa4fFQPpyc159/M4Mu0sUR9zKwok/w xjhuUBmWL/LaA5XZ7JXfq3ZhYRbW9+8yYyWbPLUYTYaUbT8mHwwxQVD4YN9R4m6/hiZT keFlCrdiEVreyDbCulYHs2JF0WozePv0z3odZHPTgC7+dCZ0CglZCz+aL/omFg21bWow LeFwwt4XqjNrWK5kg/qflfUHlZ4sbfhSAhwjhAmIuNDId+CmIMr+rtii986YbYBDVWvE u9Ak7fe6TjFohATqAzn66ZhR9euRXnaYuL2nfBlTINWjgixqtV4dQr/+7QfqTqfepTri TClg== X-Gm-Message-State: AKS2vOzQuYy/pIe9MNUIOt0PYXJB8lO9meeeUSDOOImv0J3f87TFCLss /Z9lqsTSpp9CBOed4uiKZ96Nn5vrPA== X-Received: by 10.176.7.194 with SMTP id d2mr17341044uaf.61.1497950296561; Tue, 20 Jun 2017 02:18:16 -0700 (PDT) MIME-Version: 1.0 Received: by 10.103.49.142 with HTTP; Tue, 20 Jun 2017 02:18:15 -0700 (PDT) In-Reply-To: References: From: "Bin.Cheng" Date: Tue, 20 Jun 2017 09:18:00 -0000 Message-ID: Subject: Re: [PATCH GCC][11/13]Annotate partition by its parallelism execution type To: Richard Biener Cc: "gcc-patches@gcc.gnu.org" Content-Type: multipart/mixed; boundary="f403045ee78c517f0f055260bb21" X-IsSubscribed: yes X-SW-Source: 2017-06/txt/msg01410.txt.bz2 --f403045ee78c517f0f055260bb21 Content-Type: text/plain; charset="UTF-8" Content-length: 2440 On Fri, Jun 16, 2017 at 11:10 AM, Richard Biener wrote: > On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng wrote: >> Hi, >> This patch checks and records if partition can be executed in parallel by >> looking if there exists data dependence cycles. The information is needed >> for distribution because the idea is to distribute parallel type partitions >> away from sequential ones. I believe current distribution doesn't work >> very well because it does blind distribution/fusion. >> Bootstrap and test on x86_64 and AArch64. Is it OK? > > + /* In case of no data dependence. */ > + if (DDR_ARE_DEPENDENT (ddr) == chrec_known) > + return false; > + /* Or the data dependence can be resolved by compilation time alias > + check. */ > + else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)), > + get_alias_set (DR_REF (dr2)))) > + return false; > > dependence analysis should use TBAA already, in which cases do you need this? > It seems to fall foul of the easy mistake of not honoring GCCs memory model > as well ... see dr_may_alias_p. I see. Patch updated with this branch removed. > > + /* Further check if any data dependence prevents us from executing the > + partition parallelly. */ > + EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi) > + { > + dr1 = (*datarefs_vec)[i]; > + EXECUTE_IF_SET_IN_BITMAP (partition->writes, 0, j, bj) > + { > > what about write-write dependences? > > + EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi) > + { > + dr1 = (*datarefs_vec)[i]; > + EXECUTE_IF_SET_IN_BITMAP (partition->writes, i + 1, j, bj) > + { > + dr2 = (*datarefs_vec)[j]; > + /* Partition can only be executed sequentially if there is any > + data dependence cycle. */ > > exact copy of the loop nest follows?! Maybe you meant to iterate > over writes in the first loop. Yes, this is a copy-paste typo. Patch is also simplified because read/write are recorded together now. Is it OK? Thanks, bin 2017-06-07 Bin Cheng * tree-loop-distribution.c (enum partition_type): New. (struct partition): New field type. (partition_merge_into): Update partition type. (data_dep_in_cycle_p): New function. (build_rdg_partition_for_vertex): Compute partition type. (rdg_build_partitions): Dump partition type. --f403045ee78c517f0f055260bb21 Content-Type: text/x-patch; charset="US-ASCII"; name="0010-partition-type-20170607.txt.patch" Content-Disposition: attachment; filename="0010-partition-type-20170607.txt.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: f_j45cwz7r0 Content-length: 7426 RnJvbSBmMjMxMzM4M2NiNTE2YmFkYWNiZDk5YTViYzBhMGU0ZmNlZWYxYmJm IE1vbiBTZXAgMTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBCaW4gQ2hlbmcgPGJp bmNoZTAxQGUxMDg0NTEtbGluLmNhbWJyaWRnZS5hcm0uY29tPgpEYXRlOiBG cmksIDkgSnVuIDIwMTcgMTM6MTE6NTkgKzAxMDAKU3ViamVjdDogW1BBVENI IDEwLzEzXSBwYXJ0aXRpb24tdHlwZS0yMDE3MDYwNy50eHQKCi0tLQogZ2Nj L3RyZWUtbG9vcC1kaXN0cmlidXRpb24uYyB8IDkxICsrKysrKysrKysrKysr KysrKysrKysrKysrKysrKysrKysrKysrKysrLS0tCiAxIGZpbGUgY2hhbmdl ZCwgODUgaW5zZXJ0aW9ucygrKSwgNiBkZWxldGlvbnMoLSkKCmRpZmYgLS1n aXQgYS9nY2MvdHJlZS1sb29wLWRpc3RyaWJ1dGlvbi5jIGIvZ2NjL3RyZWUt bG9vcC1kaXN0cmlidXRpb24uYwppbmRleCBhMmU1NDNlLi5kNzQxZTllIDEw MDY0NAotLS0gYS9nY2MvdHJlZS1sb29wLWRpc3RyaWJ1dGlvbi5jCisrKyBi L2djYy90cmVlLWxvb3AtZGlzdHJpYnV0aW9uLmMKQEAgLTUyNiwxMSArNTI2 LDE5IEBAIGJ1aWxkX3JkZyAoc3RydWN0IGxvb3AgKmxvb3AsIGNvbnRyb2xf ZGVwZW5kZW5jZXMgKmNkKQogfQogCiAKLQorLyogS2luZCBvZiBkaXN0cmli dXRlZCBsb29wLiAgKi8KIGVudW0gcGFydGl0aW9uX2tpbmQgewogICAgIFBL SU5EX05PUk1BTCwgUEtJTkRfTUVNU0VULCBQS0lORF9NRU1DUFksIFBLSU5E X01FTU1PVkUKIH07CiAKKy8qIFR5cGUgb2YgZGlzdHJpYnV0ZWQgbG9vcC4g ICovCitlbnVtIHBhcnRpdGlvbl90eXBlIHsKKyAgICAvKiBUaGUgZGlzdHJp YnV0ZWQgbG9vcCBjYW4gYmUgZXhlY3V0ZWQgcGFyYWxsZWxseS4gICovCisg ICAgUFRZUEVfUEFSQUxMRUwgPSAwLAorICAgIC8qIFRoZSBkaXN0cmlidXRl ZCBsb29wIGhhcyB0byBiZSBleGVjdXRlZCBzZXF1ZW50aWFsbHkuICAqLwor ICAgIFBUWVBFX1NFUVVFTlRJQUwKK307CisKIC8qIFBhcnRpdGlvbiBmb3Ig bG9vcCBkaXN0cmlidXRpb24uICAqLwogc3RydWN0IHBhcnRpdGlvbgogewpA QCAtNTQ0LDYgKzU1Miw3IEBAIHN0cnVjdCBwYXJ0aXRpb24KICAgICAgbnVt YmVyIG9mIGxvb3AgKGxhdGNoKSBpdGVyYXRpb25zLiAgKi8KICAgYm9vbCBw bHVzX29uZTsKICAgZW51bSBwYXJ0aXRpb25fa2luZCBraW5kOworICBlbnVt IHBhcnRpdGlvbl90eXBlIHR5cGU7CiAgIC8qIGRhdGEtcmVmZXJlbmNlcyBh IGtpbmQgIT0gUEtJTkRfTk9STUFMIHBhcnRpdGlvbiBpcyBhYm91dC4gICov CiAgIGRhdGFfcmVmZXJlbmNlX3AgbWFpbl9kcjsKICAgZGF0YV9yZWZlcmVu Y2VfcCBzZWNvbmRhcnlfZHI7CkBAIC02MTksNiArNjI4LDkgQEAgc3RhdGlj IHZvaWQKIHBhcnRpdGlvbl9tZXJnZV9pbnRvIChwYXJ0aXRpb24gKmRlc3Qs IHBhcnRpdGlvbiAqcGFydGl0aW9uLCBlbnVtIGZ1c2VfdHlwZSBmdCkKIHsK ICAgZGVzdC0+a2luZCA9IFBLSU5EX05PUk1BTDsKKyAgaWYgKGRlc3QtPnR5 cGUgPT0gUFRZUEVfUEFSQUxMRUwpCisgICAgZGVzdC0+dHlwZSA9IHBhcnRp dGlvbi0+dHlwZTsKKwogICBiaXRtYXBfaW9yX2ludG8gKGRlc3QtPnN0bXRz LCBwYXJ0aXRpb24tPnN0bXRzKTsKICAgaWYgKHBhcnRpdGlvbl9yZWR1Y3Rp b25fcCAocGFydGl0aW9uKSkKICAgICBkZXN0LT5yZWR1Y3Rpb25fcCA9IHRy dWU7CkBAIC0xMTE1LDYgKzExMjcsNDIgQEAgZ2V0X2RhdGFfZGVwZW5kZW5j ZSAoc3RydWN0IGdyYXBoICpyZGcsIGRhdGFfcmVmZXJlbmNlX3AgYSwgZGF0 YV9yZWZlcmVuY2VfcCBiKQogICByZXR1cm4gKnNsb3Q7CiB9CiAKKy8qIElu IHJlZHVjZWQgZGVwZW5kZW5jZSBncmFwaCBSREcgZm9yIGxvb3AgZGlzdHJp YnV0aW9uLCByZXR1cm4gdHJ1ZSBpZgorICAgZGVwZW5kZW5jZSBiZXR3ZWVu IHJlZmVyZW5jZXMgRFIxIGFuZCBEUjIgbGVhZHMgdG8gYSBkZXBlbmRlbmNl IGN5Y2xlCisgICBhbmQgc3VjaCBkZXBlbmRlbmNlIGN5Y2xlIGNhbid0IGJl IHJlc29sdmVkIGJ5IHJ1bnRpbWUgYWxpYXMgY2hlY2suICAqLworCitzdGF0 aWMgYm9vbAorZGF0YV9kZXBfaW5fY3ljbGVfcCAoc3RydWN0IGdyYXBoICpy ZGcsCisJCSAgICAgZGF0YV9yZWZlcmVuY2VfcCBkcjEsIGRhdGFfcmVmZXJl bmNlX3AgZHIyKQoreworICBzdHJ1Y3QgZGF0YV9kZXBlbmRlbmNlX3JlbGF0 aW9uICpkZHI7CisKKyAgLyogUmUtc2h1ZmZsZSBkYXRhLXJlZnMgdG8gYmUg aW4gdG9wb2xvZ2ljYWwgb3JkZXIuICAqLworICBpZiAocmRnX3ZlcnRleF9m b3Jfc3RtdCAocmRnLCBEUl9TVE1UIChkcjEpKQorICAgICAgPiByZGdfdmVy dGV4X2Zvcl9zdG10IChyZGcsIERSX1NUTVQgKGRyMikpKQorICAgIHN0ZDo6 c3dhcCAoZHIxLCBkcjIpOworCisgIGRkciA9IGdldF9kYXRhX2RlcGVuZGVu Y2UgKHJkZywgZHIxLCBkcjIpOworCisgIC8qIEluIGNhc2Ugb2Ygbm8gZGF0 YSBkZXBlbmRlbmNlLiAgKi8KKyAgaWYgKEREUl9BUkVfREVQRU5ERU5UIChk ZHIpID09IGNocmVjX2tub3duKQorICAgIHJldHVybiBmYWxzZTsKKyAgLyog Rm9yIHVua25vd24gZGF0YSBkZXBlbmRlbmNlIG9yIGtub3duIGRhdGEgZGVw ZW5kZW5jZSB3aGljaCBjYW4ndCBiZQorICAgICBleHByZXNzZWQgaW4gY2xh c3NpYyBkaXN0YW5jZSB2ZWN0b3IsIHdlIGNoZWNrIGlmIGl0IGNhbiBiZSBy ZXNvbHZlZAorICAgICBieSBydW50aW1lIGFsaWFzIGNoZWNrLiAgSWYgeWVz LCB3ZSBzdGlsbCBjb25zaWRlciBkYXRhIGRlcGVuZGVuY2UKKyAgICAgYXMg d29uJ3QgaW50cm9kdWNlIGRhdGEgZGVwZW5kZW5jZSBjeWNsZS4gICovCisg IGVsc2UgaWYgKEREUl9BUkVfREVQRU5ERU5UIChkZHIpID09IGNocmVjX2Rv bnRfa25vdworCSAgIHx8IEREUl9OVU1fRElTVF9WRUNUUyAoZGRyKSA9PSAw KQorICAgIHJldHVybiAhcnVudGltZV9hbGlhc19jaGVja19wIChkZHIsIE5V TEwsIHRydWUpOworICBlbHNlIGlmIChERFJfTlVNX0RJU1RfVkVDVFMgKGRk cikgPiAxKQorICAgIHJldHVybiB0cnVlOworICBlbHNlIGlmIChERFJfUkVW RVJTRURfUCAoZGRyKQorCSAgIHx8IGxhbWJkYV92ZWN0b3JfemVyb3AgKERE Ul9ESVNUX1ZFQ1QgKGRkciwgMCksIDEpKQorICAgIHJldHVybiBmYWxzZTsK KworICByZXR1cm4gdHJ1ZTsKK30KKwogLyogUmV0dXJucyBhIHBhcnRpdGlv biB3aXRoIGFsbCB0aGUgc3RhdGVtZW50cyBuZWVkZWQgZm9yIGNvbXB1dGlu ZwogICAgdGhlIHZlcnRleCBWIG9mIHRoZSBSREcsIGFsc28gaW5jbHVkaW5n IHRoZSBsb29wIGV4aXQgY29uZGl0aW9ucy4gICovCiAKQEAgLTExMjUsNyAr MTE3Myw4IEBAIGJ1aWxkX3JkZ19wYXJ0aXRpb25fZm9yX3ZlcnRleCAoc3Ry dWN0IGdyYXBoICpyZGcsIGludCB2KQogICBhdXRvX3ZlYzxpbnQsIDM+IG5v ZGVzOwogICB1bnNpZ25lZCBpLCBqOwogICBpbnQgeDsKLSAgZGF0YV9yZWZl cmVuY2VfcCBkcjsKKyAgZGF0YV9yZWZlcmVuY2VfcCBkcjEsIGRyMjsKKyAg Yml0bWFwX2l0ZXJhdG9yIGJpLCBiajsKIAogICBncmFwaGRzX2RmcyAocmRn LCAmdiwgMSwgJm5vZGVzLCBmYWxzZSwgTlVMTCk7CiAKQEAgLTExMzUsMTUg KzExODQsNDQgQEAgYnVpbGRfcmRnX3BhcnRpdGlvbl9mb3JfdmVydGV4IChz dHJ1Y3QgZ3JhcGggKnJkZywgaW50IHYpCiAgICAgICBiaXRtYXBfc2V0X2Jp dCAocGFydGl0aW9uLT5sb29wcywKIAkJICAgICAgbG9vcF9jb250YWluaW5n X3N0bXQgKFJER19TVE1UIChyZGcsIHgpKS0+bnVtKTsKIAotICAgICAgZm9y IChqID0gMDsgUkRHX0RBVEFSRUZTIChyZGcsIHgpLml0ZXJhdGUgKGosICZk cik7ICsraikKKyAgICAgIGZvciAoaiA9IDA7IFJER19EQVRBUkVGUyAocmRn LCB4KS5pdGVyYXRlIChqLCAmZHIxKTsgKytqKQogCXsKLQkgIHVuc2lnbmVk IGlkeCA9ICh1bnNpZ25lZCkgRFJfSU5ERVggKGRyKTsKKwkgIHVuc2lnbmVk IGlkeCA9ICh1bnNpZ25lZCkgRFJfSU5ERVggKGRyMSk7CiAJICBnY2NfYXNz ZXJ0IChpZHggPCBkYXRhcmVmc192ZWMubGVuZ3RoICgpKTsKIAorCSAgLyog UGFydGl0aW9uIGNhbiBvbmx5IGJlIGV4ZWN1dGVkIHNlcXVlbnRpYWxseSBp ZiB0aGVyZSBpcyBhbnkKKwkgICAgIHVua25vd24gZGF0YSByZWZlcmVuY2Uu ICAqLworCSAgaWYgKCFEUl9CQVNFX0FERFJFU1MgKGRyMSkgfHwgIURSX09G RlNFVCAoZHIxKQorCSAgICAgIHx8ICFEUl9JTklUIChkcjEpIHx8ICFEUl9T VEVQIChkcjEpKQorCSAgICBwYXJ0aXRpb24tPnR5cGUgPSBQVFlQRV9TRVFV RU5USUFMOworCiAJICBiaXRtYXBfc2V0X2JpdCAocGFydGl0aW9uLT5kYXRh cmVmcywgaWR4KTsKIAl9CiAgICAgfQogCisgIGlmIChwYXJ0aXRpb24tPnR5 cGUgPT0gUFRZUEVfU0VRVUVOVElBTCkKKyAgICByZXR1cm4gcGFydGl0aW9u OworCisgIC8qIEZ1cnRoZXIgY2hlY2sgaWYgYW55IGRhdGEgZGVwZW5kZW5j ZSBwcmV2ZW50cyB1cyBmcm9tIGV4ZWN1dGluZyB0aGUKKyAgICAgcGFydGl0 aW9uIHBhcmFsbGVsbHkuICAqLworICBFWEVDVVRFX0lGX1NFVF9JTl9CSVRN QVAgKHBhcnRpdGlvbi0+ZGF0YXJlZnMsIDAsIGksIGJpKQorICAgIHsKKyAg ICAgIGRyMSA9IGRhdGFyZWZzX3ZlY1tpXTsKKyAgICAgIEVYRUNVVEVfSUZf U0VUX0lOX0JJVE1BUCAocGFydGl0aW9uLT5kYXRhcmVmcywgaSArIDEsIGos IGJqKQorCXsKKwkgIGRyMiA9IGRhdGFyZWZzX3ZlY1tqXTsKKwkgIGlmIChE Ul9JU19SRUFEIChkcjEpICYmIERSX0lTX1JFQUQgKGRyMikpCisJICAgIGNv bnRpbnVlOworCisJICAvKiBQYXJ0aXRpb24gY2FuIG9ubHkgYmUgZXhlY3V0 ZWQgc2VxdWVudGlhbGx5IGlmIHRoZXJlIGlzIGFueQorCSAgICAgZGF0YSBk ZXBlbmRlbmNlIGN5Y2xlLiAgKi8KKwkgIGlmIChkYXRhX2RlcF9pbl9jeWNs ZV9wIChyZGcsIGRyMSwgZHIyKSkKKwkgICAgeworCSAgICAgIHBhcnRpdGlv bi0+dHlwZSA9IFBUWVBFX1NFUVVFTlRJQUw7CisJICAgICAgcmV0dXJuIHBh cnRpdGlvbjsKKwkgICAgfQorCX0KKyAgICB9CiAgIHJldHVybiBwYXJ0aXRp b247CiB9CiAKQEAgLTEzODgsOCArMTQ2Niw5IEBAIHJkZ19idWlsZF9wYXJ0 aXRpb25zIChzdHJ1Y3QgZ3JhcGggKnJkZywKIAogICAgICAgaWYgKGR1bXBf ZmlsZSAmJiAoZHVtcF9mbGFncyAmIFRERl9ERVRBSUxTKSkKIAl7Ci0JICBm cHJpbnRmIChkdW1wX2ZpbGUsICJsZGlzdCB1c2VmdWwgcGFydGl0aW9uOlxu Iik7Ci0JICBkdW1wX2JpdG1hcCAoZHVtcF9maWxlLCBwYXJ0aXRpb24tPnN0 bXRzKTsKKwkgIGZwcmludGYgKGR1bXBfZmlsZSwgImxkaXN0IGNyZWF0ZXMg dXNlZnVsICVzIHBhcnRpdGlvbjpcbiIsCisJCSAgIHBhcnRpdGlvbi0+dHlw ZSA9PSBQVFlQRV9QQVJBTExFTCA/ICJwYXJhbGxlbCIgOiAic2VxdWVudCIp OworCSAgYml0bWFwX3ByaW50IChkdW1wX2ZpbGUsIHBhcnRpdGlvbi0+c3Rt dHMsICIgICIsICJcbiIpOwogCX0KIAogICAgICAgcGFydGl0aW9ucy0+c2Fm ZV9wdXNoIChwYXJ0aXRpb24pOwotLSAKMS45LjEKCg== --f403045ee78c517f0f055260bb21--