From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 18021 invoked by alias); 17 Oct 2014 13:08:07 -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 18009 invoked by uid 89); 17 Oct 2014 13:08:07 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.9 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-wi0-f177.google.com Received: from mail-wi0-f177.google.com (HELO mail-wi0-f177.google.com) (209.85.212.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Fri, 17 Oct 2014 13:08:05 +0000 Received: by mail-wi0-f177.google.com with SMTP id fb4so1201982wid.10 for ; Fri, 17 Oct 2014 06:08:01 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.194.239.164 with SMTP id vt4mr3274599wjc.131.1413551281897; Fri, 17 Oct 2014 06:08:01 -0700 (PDT) Received: by 10.216.174.194 with HTTP; Fri, 17 Oct 2014 06:08:01 -0700 (PDT) In-Reply-To: <544035C2.8000703@redhat.com> References: <544035C2.8000703@redhat.com> Date: Fri, 17 Oct 2014 13:31:00 -0000 Message-ID: Subject: Re: [PATCH] Simple improvement for predicate computation in if-convert phase. From: Yuri Rumyantsev To: Jeff Law Cc: gcc-patches , Igor Zamyatin , Richard Biener Content-Type: multipart/mixed; boundary=089e0149398c079f1905059e0e40 X-SW-Source: 2014-10/txt/msg01722.txt.bz2 --089e0149398c079f1905059e0e40 Content-Type: text/plain; charset=UTF-8 Content-length: 4189 Jeff, I prepared another patch that includes test-case as you requested. Below are answers on your questions. > First, for the benefit of anyone trying to understand what you're doing, defining what "cd equivalent" means would be >helpful. I added the following comment to function: fwe call basic blocks bb1 and bb2 cd-equivalent if they are executed under the same condition. Is it sufficient? >So, do you have a case where the dominated_by_p test above is true and is_predicated(bb) returns true as well? I think this >part of the change is largely responsible for the hack you're doing with having the function scoped static variable join_bb. I don't have such test-case and I assume that if bb is always executed, it is not predicated. I also deleted "join_bb" in my changes. Is it OK for trunk now. Thanks. Yuri. 2014-10-17 Yuri Rumyantsev gcc/ChangeLog * tree-if-conv.c (add_to_predicate_list): Check unconditionally that bb is always executed to early exit. Use predicate of cd-equivalent block for join blocks if it exists. (if_convertible_loop_p_1): Recompute POST_DOMINATOR tree. (tree_if_conversion): Free post-dominance information. gcc/testsuite/ChangeLog * gcc/dg/tree-ssa/ifc-cd.c: New test. 2014-10-17 1:16 GMT+04:00 Jeff Law : > On 10/16/14 05:52, Yuri Rumyantsev wrote: >> >> Hi All, >> >> Here is a simple enhancement for predicate computation in if-convert >> phase: >> >> We use notion of cd equivalence to get simpler predicate for >> join block, e.g. if join block has 2 predecessors with predicates >> p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of >> p1 & p2 | p1 & !p2. >> >> Bootstrap and regression testing did not show any new failures. >> >> Is it OK for trunk? >> >> gcc/ChangeLog >> 2014-10-16 Yuri Rumyantsev >> >> * tree-if-conv.c (add_to_predicate_list): Check unconditionally >> that bb is always executed to early exit. Use predicate of >> cd-equivalent block for join blocks if it exists. >> (if_convertible_loop_p_1): Recompute POST_DOMINATOR tree. >> (tree_if_conversion): Free post-dominance information. > > First, for the benefit of anyone trying to understand what you're doing, > defining what "cd equivalent" means would be helpful. > > >> >> >> if-conv.patch >> >> >> Index: tree-if-conv.c >> =================================================================== >> --- tree-if-conv.c (revision 216217) >> +++ tree-if-conv.c (working copy) >> @@ -396,25 +396,51 @@ >> } >> >> /* Add condition NC to the predicate list of basic block BB. LOOP is >> - the loop to be if-converted. */ >> + the loop to be if-converted. Use predicate of cd-equivalent block >> + for join bb if it exists. */ >> >> static inline void >> add_to_predicate_list (struct loop *loop, basic_block bb, tree nc) >> { >> tree bc, *tp; >> + basic_block dom_bb; >> + static basic_block join_bb = NULL; >> >> if (is_true_predicate (nc)) >> return; >> >> - if (!is_predicated (bb)) >> + /* If dominance tells us this basic block is always executed, >> + don't record any predicates for it. */ >> + if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) >> + return; > > So, do you have a case where the dominated_by_p test above is true and > is_predicated(bb) returns true as well? I think this part of the change is > largely responsible for the hack you're doing with having the function > scoped static variable join_bb. > > > > >> + >> + /* If predicate has been already set up for given bb using >> cd-equivalent >> + block predicate, simply escape. */ >> + if (join_bb == bb) >> + return; > > I *really* dislike the state you're carrying around via join_bb. > > ISTM that if you compute that there's an equivalence, then you just set the > predicate for the equivalent block and the right things would have happened > if you had not changed the test above. > > You also need a testcase. It doesn't have to be extensive, but at least > some basic "smoke test" to verify basic operation of this code. It's > perfectly fine to scan the debugging dumps for debug output. > > > jeff > > --089e0149398c079f1905059e0e40 Content-Type: application/octet-stream; name="if-conv.patch.new" Content-Disposition: attachment; filename="if-conv.patch.new" Content-Transfer-Encoding: base64 X-Attachment-Id: f_i1djxkgt0 Content-length: 4266 SW5kZXg6IHRlc3RzdWl0ZS9nY2MuZGcvdHJlZS1zc2EvaWZjLWNkLmMKPT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PQotLS0gdGVzdHN1aXRlL2djYy5kZy90cmVl LXNzYS9pZmMtY2QuYwkocmV2aXNpb24gMCkKKysrIHRlc3RzdWl0ZS9nY2Mu ZGcvdHJlZS1zc2EvaWZjLWNkLmMJKHdvcmtpbmcgY29weSkKQEAgLTAsMCAr MSwyOSBAQAorLyogeyBkZy1kbyBjb21waWxlIH0gKi8KKy8qIHsgZGctb3B0 aW9ucyAiLU8zIC1mZHVtcC10cmVlLWlmY3Z0LWRldGFpbHMgLWZ0cmVlLWxv b3AtaWYtY29udmVydC1zdG9yZXMiIH0gKi8KKwordm9pZCBmb28gKGludCAq eDEsIGludCAqeDIsIGludCAqeDMsIGludCAqeDQsIGludCAqeSkKK3sKKyAg aW50IGk7CisgIGludCBhMSwgYTIsIGEzLCBiMSwgYjI7CisKKyAgZm9yIChp PTA7IGk8MTI4OyBpKyspCisgICAgeworICAgICAgYTEgPSB4MVtpXTsKKyAg ICAgIGEyID0geDJbaV07CisgICAgICBhMyA9IHgzW2ldOworICAgICAgeVtp XSA9IDA7CisgICAgICBpZiAoeDRbaV0gPT0gMCkKKwl7CisJICBiMSA9IGEx ICsgMTsKKwkgIGlmIChhMiA+IDApCisJICAgIGIxKys7CisJICBhMSsrOwor CSAgaWYgKGEzIDwgMCkKKwkgICAgYjEtLTsKKwkgIHlbaV0gPSBiMTsKKwl9 CisgICAgfQorfQorCisvKiB7IGRnLWZpbmFsIHsgc2Nhbi10cmVlLWR1bXAt dGltZXMgIlVzZSBwcmVkaWNhdGUgb2YgYmIiIDggImlmY3Z0IiB9IH0gKi8K Ky8qIHsgZGctZmluYWwgeyBjbGVhbnVwLXRyZWUtZHVtcCAiaWZjdnQiIH0g fSAqLwpJbmRleDogdHJlZS1pZi1jb252LmMKPT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PQotLS0gdHJlZS1pZi1jb252LmMJKHJldmlzaW9uIDIxNjIxNykKKysr IHRyZWUtaWYtY29udi5jCSh3b3JraW5nIGNvcHkpCkBAIC0zOTYsMjUgKzM5 Niw0NCBAQAogfQogCiAvKiBBZGQgY29uZGl0aW9uIE5DIHRvIHRoZSBwcmVk aWNhdGUgbGlzdCBvZiBiYXNpYyBibG9jayBCQi4gIExPT1AgaXMKLSAgIHRo ZSBsb29wIHRvIGJlIGlmLWNvbnZlcnRlZC4gICovCisgICB0aGUgbG9vcCB0 byBiZSBpZi1jb252ZXJ0ZWQuIFVzZSBwcmVkaWNhdGUgb2YgY2QtZXF1aXZh bGVudCBibG9jaworICAgZm9yIGpvaW4gYmIgaWYgaXQgZXhpc3RzOiB3ZSBj YWxsIGJhc2ljIGJsb2NrcyBiYjEgYW5kIGJiMiAKKyAgIGNkLWVxdWl2YWxl bnQgaWYgdGhleSBhcmUgZXhlY3V0ZWQgdW5kZXIgdGhlIHNhbWUgY29uZGl0 aW9uLiAgKi8KIAogc3RhdGljIGlubGluZSB2b2lkCiBhZGRfdG9fcHJlZGlj YXRlX2xpc3QgKHN0cnVjdCBsb29wICpsb29wLCBiYXNpY19ibG9jayBiYiwg dHJlZSBuYykKIHsKICAgdHJlZSBiYywgKnRwOworICBiYXNpY19ibG9jayBk b21fYmI7CiAKICAgaWYgKGlzX3RydWVfcHJlZGljYXRlIChuYykpCiAgICAg cmV0dXJuOwogCi0gIGlmICghaXNfcHJlZGljYXRlZCAoYmIpKQorICAvKiBJ ZiBkb21pbmFuY2UgdGVsbHMgdXMgdGhpcyBiYXNpYyBibG9jayBpcyBhbHdh eXMgZXhlY3V0ZWQsCisgICAgIGRvbid0IHJlY29yZCBhbnkgcHJlZGljYXRl cyBmb3IgaXQuICAqLworICBpZiAoZG9taW5hdGVkX2J5X3AgKENESV9ET01J TkFUT1JTLCBsb29wLT5sYXRjaCwgYmIpKQorICAgIHJldHVybjsKKworICBk b21fYmIgPSBnZXRfaW1tZWRpYXRlX2RvbWluYXRvciAoQ0RJX0RPTUlOQVRP UlMsIGJiKTsKKyAgLyogV2UgdXNlIG5vdGlvbiBvZiBjZCBlcXVpdmFsZW5j ZSB0byBnZXQgc2ltcGxlciBwcmVkaWNhdGUgZm9yCisgICAgIGpvaW4gYmxv Y2ssIGUuZy4gaWYgam9pbiBibG9jayBoYXMgMiBwcmVkZWNlc3NvcnMgd2l0 aCBwcmVkaWNhdGVzCisgICAgIHAxICYgcDIgYW5kIHAxICYgIXAyLCB3ZSdk IGxpa2UgdG8gZ2V0IHAxIGZvciBpdCBpbnN0ZWFkIG9mCisgICAgIHAxICYg cDIgfCBwMSAmICFwMi4gICovCisgIGlmIChkb21fYmIgIT0gbG9vcC0+aGVh ZGVyCisgICAgICAmJiBnZXRfaW1tZWRpYXRlX2RvbWluYXRvciAoQ0RJX1BP U1RfRE9NSU5BVE9SUywgZG9tX2JiKSA9PSBiYikKICAgICB7Ci0gICAgICAv KiBJZiBkb21pbmFuY2UgdGVsbHMgdXMgdGhpcyBiYXNpYyBibG9jayBpcyBh bHdheXMgZXhlY3V0ZWQsIGRvbid0Ci0JIHJlY29yZCBhbnkgcHJlZGljYXRl cyBmb3IgaXQuICAqLwotICAgICAgaWYgKGRvbWluYXRlZF9ieV9wIChDRElf RE9NSU5BVE9SUywgbG9vcC0+bGF0Y2gsIGJiKSkKLQlyZXR1cm47CisgICAg ICBnY2NfYXNzZXJ0IChmbG93X2JiX2luc2lkZV9sb29wX3AgKGxvb3AsIGRv bV9iYikpOworICAgICAgYmMgPSBiYl9wcmVkaWNhdGUgKGRvbV9iYik7Cisg ICAgICBnY2NfYXNzZXJ0ICghaXNfdHJ1ZV9wcmVkaWNhdGUgKGJjKSk7Cisg ICAgICBzZXRfYmJfcHJlZGljYXRlIChiYiwgYmMpOworICAgICAgaWYgKGR1 bXBfZmlsZSAmJiAoZHVtcF9mbGFncyAmIFRERl9ERVRBSUxTKSkKKwlmcHJp bnRmIChkdW1wX2ZpbGUsICJVc2UgcHJlZGljYXRlIG9mIGJiIyVkIGZvciBi YiMlZFxuIiwKKwkJIGRvbV9iYi0+aW5kZXgsIGJiLT5pbmRleCk7CisgICAg ICByZXR1cm47CisgICAgfQogCi0gICAgICBiYyA9IG5jOwotICAgIH0KKyAg aWYgKCFpc19wcmVkaWNhdGVkIChiYikpCisgICAgYmMgPSBuYzsKICAgZWxz ZQogICAgIHsKICAgICAgIGJjID0gYmJfcHJlZGljYXRlIChiYik7CkBAIC0x MTc2LDYgKzExOTUsNyBAQAogICAgIHJldHVybiBmYWxzZTsKIAogICBjYWxj dWxhdGVfZG9taW5hbmNlX2luZm8gKENESV9ET01JTkFUT1JTKTsKKyAgY2Fs Y3VsYXRlX2RvbWluYW5jZV9pbmZvIChDRElfUE9TVF9ET01JTkFUT1JTKTsK IAogICAvKiBBbGxvdyBzdGF0ZW1lbnRzIHRoYXQgY2FuIGJlIGhhbmRsZWQg ZHVyaW5nIGlmLWNvbnZlcnNpb24uICAqLwogICBpZmNfYmJzID0gZ2V0X2xv b3BfYm9keV9pbl9pZl9jb252X29yZGVyIChsb29wKTsKQEAgLTIxNDgsNiAr MjE2OCw3IEBACiAgICAgICBmcmVlIChpZmNfYmJzKTsKICAgICAgIGlmY19i YnMgPSBOVUxMOwogICAgIH0KKyAgZnJlZV9kb21pbmFuY2VfaW5mbyAoQ0RJ X1BPU1RfRE9NSU5BVE9SUyk7CiAKICAgcmV0dXJuIHRvZG87CiB9Cg== --089e0149398c079f1905059e0e40--