From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx0a-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by sourceware.org (Postfix) with ESMTPS id EC0EC3853C1C for ; Fri, 23 Jul 2021 08:41:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EC0EC3853C1C Received: from pps.filterd (m0098416.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.43/8.16.0.43) with SMTP id 16N8cIGZ153177; Fri, 23 Jul 2021 04:41:40 -0400 Received: from pps.reinject (localhost [127.0.0.1]) by mx0b-001b2d01.pphosted.com with ESMTP id 39ysah1s5r-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 23 Jul 2021 04:41:40 -0400 Received: from m0098416.ppops.net (m0098416.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.43/8.16.0.43) with SMTP id 16N8coIK156065; Fri, 23 Jul 2021 04:41:40 -0400 Received: from ppma03fra.de.ibm.com (6b.4a.5195.ip4.static.sl-reverse.com [149.81.74.107]) by mx0b-001b2d01.pphosted.com with ESMTP id 39ysah1s4y-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 23 Jul 2021 04:41:39 -0400 Received: from pps.filterd (ppma03fra.de.ibm.com [127.0.0.1]) by ppma03fra.de.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 16N8Y49e007197; Fri, 23 Jul 2021 08:41:38 GMT Received: from b06cxnps3075.portsmouth.uk.ibm.com (d06relay10.portsmouth.uk.ibm.com [9.149.109.195]) by ppma03fra.de.ibm.com with ESMTP id 39upu89sga-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 23 Jul 2021 08:41:37 +0000 Received: from d06av22.portsmouth.uk.ibm.com (d06av22.portsmouth.uk.ibm.com [9.149.105.58]) by b06cxnps3075.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 16N8fZeD36897106 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 23 Jul 2021 08:41:35 GMT Received: from d06av22.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 73F8C4C050; Fri, 23 Jul 2021 08:41:35 +0000 (GMT) Received: from d06av22.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 0800A4C044; Fri, 23 Jul 2021 08:41:32 +0000 (GMT) Received: from KewenLins-MacBook-Pro.local (unknown [9.200.59.223]) by d06av22.portsmouth.uk.ibm.com (Postfix) with ESMTP; Fri, 23 Jul 2021 08:41:31 +0000 (GMT) Subject: [PATCH] Make loops_list support an optional loop_p root To: Richard Biener Cc: GCC Patches , Jakub Jelinek , Jonathan Wakely , Segher Boessenkool , Richard Sandiford , Trevor Saunders , Martin Sebor , Bill Schmidt References: <0a8b77ba-1d54-1eff-b54d-d2cb1e769e09@linux.ibm.com> From: "Kewen.Lin" Message-ID: <61ac669c-7293-f53a-20c7-158b5a813cee@linux.ibm.com> Date: Fri, 23 Jul 2021 16:41:30 +0800 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.10.0 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------FE6443C1567822CA1C6E7A33" Content-Language: en-US X-TM-AS-GCONF: 00 X-Proofpoint-ORIG-GUID: kcqxlUpkcRD1ub3Bcmo2NYePH3oaA9T- X-Proofpoint-GUID: b9IB0oKCQeAQ-fTT8JnEUshczh5O9cj1 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.391, 18.0.790 definitions=2021-07-23_04:2021-07-23, 2021-07-23 signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 clxscore=1015 mlxscore=0 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 impostorscore=0 suspectscore=0 mlxlogscore=999 lowpriorityscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104190000 definitions=main-2107230049 X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 23 Jul 2021 08:41:44 -0000 This is a multi-part message in MIME format. --------------FE6443C1567822CA1C6E7A33 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit on 2021/7/22 下午8:56, Richard Biener wrote: > On Tue, Jul 20, 2021 at 4:37 > PM Kewen.Lin wrote: >> >> Hi, >> >> This v2 has addressed some review comments/suggestions: >> >> - Use "!=" instead of "<" in function operator!= (const Iter &rhs) >> - Add new CTOR loops_list (struct loops *loops, unsigned flags) >> to support loop hierarchy tree rather than just a function, >> and adjust to use loops* accordingly. > > I actually meant struct loop *, not struct loops * ;) At the point > we pondered to make loop invariant motion work on single > loop nests we gave up not only but also because it iterates > over the loop nest but all the iterators only ever can process > all loops, not say, all loops inside a specific 'loop' (and > including that 'loop' if LI_INCLUDE_ROOT). So the > CTOR would take the 'root' of the loop tree as argument. > > I see that doesn't trivially fit how loops_list works, at least > not for LI_ONLY_INNERMOST. But I guess FROM_INNERMOST > could be adjusted to do ONLY_INNERMOST as well? > Thanks for the clarification! I just realized that the previous version with struct loops* is problematic, all traversal is still bounded with outer_loop == NULL. I think what you expect is to respect the given loop_p root boundary. Since we just record the loops' nums, I think we still need the function* fn? So I add one optional argument loop_p root and update the visiting codes accordingly. Before this change, the previous visiting uses the outer_loop == NULL as the termination condition, it perfectly includes the root itself, but with this given root, we have to use it as the termination condition to avoid to iterate onto its possible existing next. For LI_ONLY_INNERMOST, I was thinking whether we can use the code like: struct loops *fn_loops = loops_for_fn (fn)->larray; for (i = 0; vec_safe_iterate (fn_loops, i, &aloop); i++) if (aloop != NULL && aloop->inner == NULL && flow_loop_nested_p (tree_root, aloop)) this->to_visit.quick_push (aloop->num); it has the stable bound, but if the given root only has several child loops, it can be much worse if there are many loops in fn. It seems impossible to predict the given root loop hierarchy size, maybe we can still use the original linear searching for the case loops_for_fn (fn) == root? But since this visiting seems not so performance critical, I chose to share the code originally used for FROM_INNERMOST, hope it can have better readability and maintainability. Bootstrapped and regtested on powerpc64le-linux-gnu P9, x86_64-redhat-linux and aarch64-linux-gnu, also bootstrapped on ppc64le P9 with bootstrap-O3 config. Does the attached patch meet what you expect? BR, Kewen ----- gcc/ChangeLog: * cfgloop.h (loops_list::loops_list): Add one optional argument root and adjust accordingly. --------------FE6443C1567822CA1C6E7A33 Content-Type: text/plain; charset=UTF-8; x-mac-type="0"; x-mac-creator="0"; name="loop_root.diff" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="loop_root.diff" ZGlmZiAtLWdpdCBhL2djYy9jZmdsb29wLmggYi9nY2MvY2ZnbG9vcC5oCmluZGV4IDc0MWRm NDRlYTUxLi5mNzE0OGRmMTc1OCAxMDA2NDQKLS0tIGEvZ2NjL2NmZ2xvb3AuaAorKysgYi9n Y2MvY2ZnbG9vcC5oCkBAIC02NjksMTMgKzY2OSwxNSBAQCBhc19jb25zdCAoVCAmdCkKIH0K IAogLyogQSBsaXN0IGZvciB2aXNpdGluZyBsb29wcywgd2hpY2ggY29udGFpbnMgdGhlIGxv b3AgbnVtYmVycyBpbnN0ZWFkIG9mCi0gICB0aGUgbG9vcCBwb2ludGVycy4gIFRoZSBzY29w ZSBpcyByZXN0cmljdGVkIGluIGZ1bmN0aW9uIEZOIGFuZCB0aGUKLSAgIHZpc2l0aW5nIG9y ZGVyIGlzIHNwZWNpZmllZCBieSBGTEFHUy4gICovCisgICB0aGUgbG9vcCBwb2ludGVycy4g IElmIHRoZSBsb29wIFJPT1QgaXMgb2ZmZXJlZCAobm9uLW51bGwpLCB0aGUgdmlzaXRpbmcK KyAgIHdpbGwgc3RhcnQgZnJvbSBpdCwgb3RoZXJ3aXNlIGl0IHdvdWxkIHN0YXJ0IGZyb20g bG9vcHNfZm9yX2ZuIChGTikKKyAgIGluc3RlYWQuICBUaGUgc2NvcGUgaXMgcmVzdHJpY3Rl ZCBpbiBmdW5jdGlvbiBGTiBhbmQgdGhlIHZpc2l0aW5nIG9yZGVyCisgICBpcyBzcGVjaWZp ZWQgYnkgRkxBR1MuICAqLwogCiBjbGFzcyBsb29wc19saXN0CiB7CiBwdWJsaWM6Ci0gIGxv b3BzX2xpc3QgKGZ1bmN0aW9uICpmbiwgdW5zaWduZWQgZmxhZ3MpOworICBsb29wc19saXN0 IChmdW5jdGlvbiAqZm4sIHVuc2lnbmVkIGZsYWdzLCBsb29wX3Agcm9vdCA9IG51bGxwdHIp OwogCiAgIHRlbXBsYXRlIDx0eXBlbmFtZSBUPiBjbGFzcyBJdGVyCiAgIHsKQEAgLTc4Miw3 MSArNzg0LDk0IEBAIGxvb3BzX2xpc3Q6Okl0ZXI8VD46OmZpbGxfY3Vycl9sb29wICgpCiB9 CiAKIC8qIFNldCB1cCB0aGUgbG9vcHMgbGlzdCB0byB2aXNpdCBhY2NvcmRpbmcgdG8gdGhl IHNwZWNpZmllZAotICAgZnVuY3Rpb24gc2NvcGUgRk4gYW5kIGl0ZXJhdGluZyBvcmRlciBG TEFHUy4gICovCisgICBmdW5jdGlvbiBzY29wZSBGTiBhbmQgaXRlcmF0aW5nIG9yZGVyIEZM QUdTLiAgSWYgUk9PVCBpcworICAgbm90IG51bGwsIHRoZSB2aXNpdGluZyB3b3VsZCBzdGFy dCBmcm9tIGl0LCBvdGhlcndpc2UgaXQKKyAgIHdpbGwgc3RhcnQgZnJvbSB0cmVlX3Jvb3Qg b2YgbG9vcHNfZm9yX2ZuIChGTikuICAqLwogCi1pbmxpbmUgbG9vcHNfbGlzdDo6bG9vcHNf bGlzdCAoZnVuY3Rpb24gKmZuLCB1bnNpZ25lZCBmbGFncykKK2lubGluZSBsb29wc19saXN0 Ojpsb29wc19saXN0IChmdW5jdGlvbiAqZm4sIHVuc2lnbmVkIGZsYWdzLCBsb29wX3Agcm9v dCkKIHsKICAgY2xhc3MgbG9vcCAqYWxvb3A7Ci0gIHVuc2lnbmVkIGk7CiAgIGludCBtbjsK IAorICBzdHJ1Y3QgbG9vcHMgKmxvb3BzID0gbG9vcHNfZm9yX2ZuIChmbik7CisgIGdjY19h c3NlcnQgKCFyb290IHx8IGxvb3BzKTsKKwogICB0aGlzLT5mbiA9IGZuOwotICBpZiAoIWxv b3BzX2Zvcl9mbiAoZm4pKQorICBpZiAoIWxvb3BzKQogICAgIHJldHVybjsKIAorICBsb29w X3AgdHJlZV9yb290ID0gcm9vdCA/IHJvb3QgOiBsb29wcy0+dHJlZV9yb290OworCiAgIHRo aXMtPnRvX3Zpc2l0LnJlc2VydmVfZXhhY3QgKG51bWJlcl9vZl9sb29wcyAoZm4pKTsKLSAg bW4gPSAoZmxhZ3MgJiBMSV9JTkNMVURFX1JPT1QpID8gMCA6IDE7CisgIG1uID0gKGZsYWdz ICYgTElfSU5DTFVERV9ST09UKSA/IC0xIDogdHJlZV9yb290LT5udW07CiAKLSAgaWYgKGZs YWdzICYgTElfT05MWV9JTk5FUk1PU1QpCi0gICAgewotICAgICAgZm9yIChpID0gMDsgdmVj X3NhZmVfaXRlcmF0ZSAobG9vcHNfZm9yX2ZuIChmbiktPmxhcnJheSwgaSwgJmFsb29wKTsg aSsrKQotCWlmIChhbG9vcCAhPSBOVUxMCi0JICAgICYmIGFsb29wLT5pbm5lciA9PSBOVUxM Ci0JICAgICYmIGFsb29wLT5udW0gPj0gbW4pCisgIC8qIFRoZSBoZWxwZXIgZnVuY3Rpb24g Zm9yIExJX0ZST01fSU5ORVJNT1NUIGFuZCBMSV9PTkxZX0lOTkVSTU9TVAorICAgICB2aXNp dGluZywgT05MWV9QVVNIX0lOTkVSTU9TVF9QIGluZGljYXRlcyB3aGV0aGVyIG9ubHkgcHVz aAorICAgICB0aGUgaW5uZXJtb3N0IGxvb3AsIGl0J3MgdHJ1ZSBmb3IgTElfT05MWV9JTk5F Uk1PU1QgdmlzaXRpbmcKKyAgICAgd2hpbGUgZmFsc2UgZm9yIExJX0ZST01fSU5ORVJNT1NU IHZpc2l0aW5nLiAgKi8KKyAgYXV0byB2aXNpdF9mcm9tX2lubmVybW9zdCA9IFsmXSAoYm9v bCBvbmx5X3B1c2hfaW5uZXJtb3N0X3ApCisgIHsKKyAgICAvKiBQdXNoIHRoZSBsb29wcyB0 byBMSS0+VE9fVklTSVQgaW4gcG9zdG9yZGVyLiAgKi8KKworICAgIC8qIEVhcmx5IGhhbmRs ZSB0cmVlX3Jvb3Qgd2l0aG91dCBhbnkgaW5uZXIgbG9vcHMsIG1ha2UgbGF0ZXIKKyAgICAg ICBwcm9jZXNzaW5nIHNpbXBsZXIsIHRoYXQgaXMgdGhlIHdoaWxlIGxvb3AgY2FuIG9ubHkg Y2FyZQorICAgICAgIGFib3V0IGxvb3BzIHdoaWNoIGFyZW4ndCBwb3NzaWJsZSB0byBiZSB0 cmVlX3Jvb3QuICAqLworICAgIGlmICghdHJlZV9yb290LT5pbm5lcikKKyAgICAgIHsKKwlp ZiAodHJlZV9yb290LT5udW0gIT0gbW4pCisJICB0aGlzLT50b192aXNpdC5xdWlja19wdXNo ICh0cmVlX3Jvb3QtPm51bSk7CisJcmV0dXJuOworICAgICAgfQorCisgICAgZm9yIChhbG9v cCA9IHRyZWVfcm9vdDsKKwlhbG9vcC0+aW5uZXIgIT0gTlVMTDsKKwlhbG9vcCA9IGFsb29w LT5pbm5lcikKKyAgICAgIGNvbnRpbnVlOworCisgICAgd2hpbGUgKDEpCisgICAgICB7CisJ Z2NjX2Fzc2VydCAoYWxvb3AgIT0gdHJlZV9yb290KTsKKwlpZiAoIW9ubHlfcHVzaF9pbm5l cm1vc3RfcCB8fCBhbG9vcC0+aW5uZXIgPT0gTlVMTCkKIAkgIHRoaXMtPnRvX3Zpc2l0LnF1 aWNrX3B1c2ggKGFsb29wLT5udW0pOwotICAgIH0KLSAgZWxzZSBpZiAoZmxhZ3MgJiBMSV9G Uk9NX0lOTkVSTU9TVCkKLSAgICB7Ci0gICAgICAvKiBQdXNoIHRoZSBsb29wcyB0byBMSS0+ VE9fVklTSVQgaW4gcG9zdG9yZGVyLiAgKi8KLSAgICAgIGZvciAoYWxvb3AgPSBsb29wc19m b3JfZm4gKGZuKS0+dHJlZV9yb290OwotCSAgIGFsb29wLT5pbm5lciAhPSBOVUxMOwotCSAg IGFsb29wID0gYWxvb3AtPmlubmVyKQotCWNvbnRpbnVlOwogCi0gICAgICB3aGlsZSAoMSkK LQl7Ci0JICBpZiAoYWxvb3AtPm51bSA+PSBtbikKLQkgICAgdGhpcy0+dG9fdmlzaXQucXVp Y2tfcHVzaCAoYWxvb3AtPm51bSk7CisJaWYgKGFsb29wLT5uZXh0KQorCSAgeworCSAgICBm b3IgKGFsb29wID0gYWxvb3AtPm5leHQ7CisJCSBhbG9vcC0+aW5uZXIgIT0gTlVMTDsKKwkJ IGFsb29wID0gYWxvb3AtPmlubmVyKQorCSAgICAgIGNvbnRpbnVlOworCSAgfQorCWVsc2Ug aWYgKGxvb3Bfb3V0ZXIgKGFsb29wKSA9PSB0cmVlX3Jvb3QpCisJICBicmVhazsKKwllbHNl CisJICBhbG9vcCA9IGxvb3Bfb3V0ZXIgKGFsb29wKTsKKyAgICAgIH0KKworICAgIC8qIFJl Y29uc2lkZXIgdHJlZV9yb290IHNpbmNlIHRoZSBwcmV2aW91cyBsb29wIGRvZXNuJ3QgaGFu ZGxlIGl0LiAgKi8KKyAgICBpZiAoIW9ubHlfcHVzaF9pbm5lcm1vc3RfcCAmJiB0cmVlX3Jv b3QtPm51bSAhPSBtbikKKyAgICAgIHRoaXMtPnRvX3Zpc2l0LnF1aWNrX3B1c2ggKHRyZWVf cm9vdC0+bnVtKTsKKyAgfTsKIAotCSAgaWYgKGFsb29wLT5uZXh0KQotCSAgICB7Ci0JICAg ICAgZm9yIChhbG9vcCA9IGFsb29wLT5uZXh0OwotCQkgICBhbG9vcC0+aW5uZXIgIT0gTlVM TDsKLQkJICAgYWxvb3AgPSBhbG9vcC0+aW5uZXIpCi0JCWNvbnRpbnVlOwotCSAgICB9Ci0J ICBlbHNlIGlmICghbG9vcF9vdXRlciAoYWxvb3ApKQotCSAgICBicmVhazsKLQkgIGVsc2UK LQkgICAgYWxvb3AgPSBsb29wX291dGVyIChhbG9vcCk7Ci0JfQotICAgIH0KKyAgaWYgKGZs YWdzICYgTElfT05MWV9JTk5FUk1PU1QpCisgICAgdmlzaXRfZnJvbV9pbm5lcm1vc3QgKHRy dWUpOworICBlbHNlIGlmIChmbGFncyAmIExJX0ZST01fSU5ORVJNT1NUKQorICAgIHZpc2l0 X2Zyb21faW5uZXJtb3N0IChmYWxzZSk7CiAgIGVsc2UKICAgICB7CiAgICAgICAvKiBQdXNo IHRoZSBsb29wcyB0byBMSS0+VE9fVklTSVQgaW4gcHJlb3JkZXIuICAqLwotICAgICAgYWxv b3AgPSBsb29wc19mb3JfZm4gKGZuKS0+dHJlZV9yb290OworICAgICAgYWxvb3AgPSB0cmVl X3Jvb3Q7CiAgICAgICB3aGlsZSAoMSkKIAl7Ci0JICBpZiAoYWxvb3AtPm51bSA+PSBtbikK KwkgIGlmIChhbG9vcC0+bnVtICE9IG1uKQogCSAgICB0aGlzLT50b192aXNpdC5xdWlja19w dXNoIChhbG9vcC0+bnVtKTsKIAogCSAgaWYgKGFsb29wLT5pbm5lciAhPSBOVUxMKQogCSAg ICBhbG9vcCA9IGFsb29wLT5pbm5lcjsKIAkgIGVsc2UKIAkgICAgewotCSAgICAgIHdoaWxl IChhbG9vcCAhPSBOVUxMICYmIGFsb29wLT5uZXh0ID09IE5VTEwpCisJICAgICAgd2hpbGUg KGFsb29wICE9IHRyZWVfcm9vdCAmJiBhbG9vcC0+bmV4dCA9PSBOVUxMKQogCQlhbG9vcCA9 IGxvb3Bfb3V0ZXIgKGFsb29wKTsKLQkgICAgICBpZiAoYWxvb3AgPT0gTlVMTCkKKwkgICAg ICBpZiAoYWxvb3AgPT0gdHJlZV9yb290KQogCQlicmVhazsKIAkgICAgICBhbG9vcCA9IGFs b29wLT5uZXh0OwogCSAgICB9Cg== --------------FE6443C1567822CA1C6E7A33--