From patchwork Tue May 9 22:06:19 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 9718991 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 72CA460236 for ; Tue, 9 May 2017 22:08:48 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6396428471 for ; Tue, 9 May 2017 22:08:48 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 57EFD28497; Tue, 9 May 2017 22:08:48 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.3 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, RCVD_IN_SORBS_SPAM, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E59BC28471 for ; Tue, 9 May 2017 22:08:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1750914AbdEIWIr (ORCPT ); Tue, 9 May 2017 18:08:47 -0400 Received: from mail-wr0-f193.google.com ([209.85.128.193]:33699 "EHLO mail-wr0-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750767AbdEIWIq (ORCPT ); Tue, 9 May 2017 18:08:46 -0400 Received: by mail-wr0-f193.google.com with SMTP id w50so3621014wrc.0 for ; Tue, 09 May 2017 15:08:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id; bh=NyI1X50regjTLEdkyHbkLwmJ51B3lRo2SG6Qc/qi8BQ=; b=GkRAMuDRTBGgLcm6g8gOwcHN1u03kf6D0Iw49ME0fIqfRBIwFV2iuleGXpLZmwJVvR Dx8tVG0BZ+fHtC6IU1REDGfD7KYou8nrSMSUaaed3w7r5y1YfcyCdFcnDfHcYFbsQLeR bZmaufsyKaa+Me3W4LeNz6klelPkKcsIR2vKmbqnRmk5s46kg4MRb3myBWAKATkTpkHY akOfbZ84eaXWMErimAhVWbiNYyq9R9SDLLLqtQLCU5f/cO37kZzXSHBhe+TmNvSHWqMC oktVEUtfsjoSrQe0xbgtSmU4Q+4xrasn0M4sCqAv32QNFW3t8fg9HhfPL6PUscagBbnp H+Eg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=NyI1X50regjTLEdkyHbkLwmJ51B3lRo2SG6Qc/qi8BQ=; b=IkyADH4Xa3rz4sQnA2vRhKenqA8prO54yux0nZMmt0d/lav2/qpsQV7vd7b54xijqX eZcwZ9YUqhfsRsb9GCsPG29ntfSYfkEDqb30F5qDeDoQ63gn2EkrfZIZaM+JX2hgON5I TA2jO+xPkphnMTX7HbhXnI4JvlgIc9y3HgamVJMlJiQoi9Ow+qUNvWjXxeBXgi2tlvnw r8FjozDp8lGeTW/VyeIF0doXZpEMrPtlaJy46dWROzejqvpnhvcbN5VRLjrW1CUmIQ90 H1/OlYIPyTsFLoLZ8STB8+8pTeyH3t5zrxTxyKvvUA6R3FoXFYiqBpG+XiFSBn2xOsig AeCw== X-Gm-Message-State: AODbwcCYjFo934XoxOia7+PAWy7Z6HW2yGl9Yz/JKot7e144WsCzsyMC R1/8OBIeRp2k/yshYQU= X-Received: by 10.28.203.143 with SMTP id b137mr1337550wmg.115.1494367725094; Tue, 09 May 2017 15:08:45 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:8f6:2d00:9f6:6944:14cc:3683]) by smtp.gmail.com with ESMTPSA id 188sm2293397wmf.29.2017.05.09.15.08.43 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 09 May 2017 15:08:44 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Christopher Li , Luc Van Oostenryck Subject: [PATCH] ignore VOID when trying to if-convert phi-nodes Date: Wed, 10 May 2017 00:06:19 +0200 Message-Id: <20170509220619.72375-1-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.12.0 Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Simple if-then-else expressions can often be replaced by an OP_SELECT. This is done in a very generic way by looking not at the test/if part but at OP_PHIs which contain exactly 2 values. An implementation detail makes that the address of valid OP_PHI's sources must not change, so the list holding these values must not be repacked and such. As consequence, when a value need to be removed from the list this value is simply replaced in the list by a VOID. These VOIDs must then be ignored when processing OP_PHI's sources. But for the if-conversion, these VOID are not ignored and are thus considered like any other value which in turn make miss some optimizatin opportunities. For example code like: int foo(int a) { if (a) return 0; else return 1; return 2; } will be linearized into something like: ... phi.32 %r2 <- %phi1, %phi2, VOID ret.32 %r2 where %phi1 & %phi2 correspond to the 'return 0' & 'return 1' and the VOID correspond to the dead 'return 2'. This code should be trivially be converted to a select but is not because the OP_PHI is considered as having 3 elements instead of 2. Fix this by filtering out these VOIDs before checking the conditions of the if-conversion. Signed-off-by: Luc Van Oostenryck --- simplify.c | 25 +++++++++++++++++++++++-- validation/optim/void-if-convert.c | 19 +++++++++++++++++++ 2 files changed, 42 insertions(+), 2 deletions(-) create mode 100644 validation/optim/void-if-convert.c diff --git a/simplify.c b/simplify.c index 5d00937f1..cf9ca15f2 100644 --- a/simplify.c +++ b/simplify.c @@ -26,16 +26,37 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud return first_basic_block(source->parents); } +/* + * Essentially the same as linearize_ptr_list() + * but ignoring VOID. + * Returns 0 if the the list contained the expected + * number of element, 1 or -1 if there was more or less. + */ +static int get_phi_list(pseudo_t array[], int n, struct pseudo_list *list) +{ + pseudo_t phi; + int i = 0; + + FOR_EACH_PTR(list, phi) { + if (phi == VOID) + continue; + if (i >= n) + return 1; + array[i++] = phi; + } END_FOR_EACH_PTR(phi); + return (i == n) ? 0 : -1; +} + static int if_convert_phi(struct instruction *insn) { - pseudo_t array[3]; + pseudo_t array[2]; struct basic_block *parents[3]; struct basic_block *bb, *bb1, *bb2, *source; struct instruction *br; pseudo_t p1, p2; bb = insn->bb; - if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2) + if (get_phi_list(array, 2, insn->phi_list) != 0) return 0; if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2) return 0; diff --git a/validation/optim/void-if-convert.c b/validation/optim/void-if-convert.c new file mode 100644 index 000000000..66513c4dc --- /dev/null +++ b/validation/optim/void-if-convert.c @@ -0,0 +1,19 @@ +int foo(int a) +{ + if (a) + return 0; + else + return 1; + return 2; +} + +/* + * check-name: Ignore VOID in if-convert + * check-command: test-linearize -Wno-decl $file + * check-output-ignore + * + * check-output-excludes: phisrc\\. + * check-output-excludes: phi\\. + * check-output-excludes: VOID + * check-output-contains: seteq\\. + */