From patchwork Sat Aug 27 15:53:23 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Linus Torvalds X-Patchwork-Id: 1104572 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by demeter2.kernel.org (8.14.4/8.14.4) with ESMTP id p7RFrpDS010763 for ; Sat, 27 Aug 2011 15:53:52 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1750906Ab1H0Pxt (ORCPT ); Sat, 27 Aug 2011 11:53:49 -0400 Received: from smtp1.linux-foundation.org ([140.211.169.13]:36875 "EHLO smtp1.linux-foundation.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750858Ab1H0Pxs (ORCPT ); Sat, 27 Aug 2011 11:53:48 -0400 Received: from mail-ww0-f44.google.com (mail-ww0-f44.google.com [74.125.82.44]) (authenticated bits=0) by smtp1.linux-foundation.org (8.14.2/8.13.5/Debian-3ubuntu1.1) with ESMTP id p7RFrkRG021444 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=FAIL) for ; Sat, 27 Aug 2011 08:53:47 -0700 Received: by wwf5 with SMTP id 5so4432016wwf.1 for ; Sat, 27 Aug 2011 08:53:45 -0700 (PDT) Received: by 10.216.56.2 with SMTP id l2mr2873657wec.70.1314460425061; Sat, 27 Aug 2011 08:53:45 -0700 (PDT) MIME-Version: 1.0 Received: by 10.216.187.66 with HTTP; Sat, 27 Aug 2011 08:53:23 -0700 (PDT) In-Reply-To: <4E590F22.6030800@garzik.org> References: <4E588EB8.80808@garzik.org> <201108271334.17659.kdudka@redhat.com> <4E590F22.6030800@garzik.org> From: Linus Torvalds Date: Sat, 27 Aug 2011 08:53:23 -0700 Message-ID: Subject: Re: linearize bug? To: Jeff Garzik Cc: Kamil Dudka , Sparse Mailing-list , Pekka J Enberg X-Spam-Status: No, hits=-103.003 required=5 tests=AWL, BAYES_00, USER_IN_WHITELIST X-Spam-Checker-Version: SpamAssassin 3.2.4-osdl_revision__1.47__ X-MIMEDefang-Filter: lf$Revision: 1.188 $ X-Scanned-By: MIMEDefang 2.63 on 140.211.169.13 Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.6 (demeter2.kernel.org [140.211.167.43]); Sat, 27 Aug 2011 15:53:52 +0000 (UTC) On Sat, Aug 27, 2011 at 8:37 AM, Jeff Garzik wrote: > > On our point of view, we probably prefer to simply turn off as many > transformations as possible.  They just waste time, when an optimizing LLVM > backend is going to perform the same transformations anyway. I disagree - mainly because I don't think we're interested in the back end, are we? If we were doing LLVM hacking, then I'd agree. But as it is, we're supposed to improve sparse, not LLVM, so we should make sure that the _sparse_ output makes sense, and LLVM is just a code generator, no? Also, I suspect LLVM has an easier time of it if we were to generate straightforward code rather than the extra basic blocks we do now. So with the attached patch, your test-case turns into t.c:1:5: warning: symbol 'foo' was not declared. Should it be static? foo: .L0x7fc91affa010: phisrc.32 %phi2(x) <- %arg1 phisrc.32 %phi4(x) <- %arg1 phisrc.32 %phi6(i) <- $0 br .L0x7fc91affa058 .L0x7fc91affa058: phi.32 %r3 <- %phi4(x), %phi5(x) add.32 %r5 <- %r3, $42 phisrc.32 %phi3(x) <- %r5 phisrc.32 %phi5(x) <- %r5 phi.32 %r7 <- %phi6(i), %phi7(i) add.32 %r8 <- %r7, $1 setlt.32 %r10 <- %r8, $10 phisrc.32 %phi7(i) <- %r8 br %r10, .L0x7fc91affa058, .L0x7fc91affa130 .L0x7fc91affa130: ret.32 %r3 which looks messy due to all the phi's (that we don't combine - the patch includes Kamil's "don't combine" thing), but looks simpler otherwise. Now sparse has optimized away the entry conditional (simply because it got linearized separately and then the optimization was a trivial constant one). phi2/phi3 are both dead, but theor 'phisrc' instructions haven't been killed. Ugly. The attached patch is ENTIRELY UNTESTED. The only thing I tested it on is your test-case. Running "make test" requires stuff that I don't even have installed, and I'm lazy ;^o Linus cse.c | 7 ------- linearize.c | 14 +++++--------- 2 files changed, 5 insertions(+), 16 deletions(-) diff --git a/cse.c b/cse.c index 2a1574531993..2aabb65785f0 100644 --- a/cse.c +++ b/cse.c @@ -317,13 +317,6 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction b2 = i2->bb; /* - * PHI-nodes do not care where they are - the only thing that matters - * are the PHI _sources_. - */ - if (i1->opcode == OP_PHI) - return cse_one_instruction(i1, i2); - - /* * Currently we only handle the uninteresting degenerate case where * the CSE is inside one basic-block. */ diff --git a/linearize.c b/linearize.c index f2034ce93572..06128ed5b5ee 100644 --- a/linearize.c +++ b/linearize.c @@ -2060,16 +2060,10 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt) concat_symbol_list(stmt->iterator_syms, &ep->syms); linearize_statement(ep, pre_statement); - loop_body = loop_top = alloc_basic_block(ep, stmt->pos); + loop_body = alloc_basic_block(ep, stmt->pos); loop_continue = alloc_basic_block(ep, stmt->pos); loop_end = alloc_basic_block(ep, stmt->pos); - /* An empty post-condition means that it's the same as the pre-condition */ - if (!post_condition) { - loop_top = alloc_basic_block(ep, stmt->pos); - set_activeblock(ep, loop_top); - } - if (pre_condition) linearize_cond_branch(ep, pre_condition, loop_body, loop_end); @@ -2082,10 +2076,12 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt) set_activeblock(ep, loop_continue); linearize_statement(ep, post_statement); + + /* No post-condition means that it's the same as the pre-condition */ if (!post_condition) - add_goto(ep, loop_top); + linearize_cond_branch(ep, pre_condition, loop_body, loop_end); else - linearize_cond_branch(ep, post_condition, loop_top, loop_end); + linearize_cond_branch(ep, post_condition, loop_body, loop_end); set_activeblock(ep, loop_end); break; }