From patchwork Wed Nov 11 23:52:31 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 11898805 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 5BB86139F for ; Thu, 12 Nov 2020 01:47:57 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3356721534 for ; Thu, 12 Nov 2020 01:47:57 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="p4Z54kLi" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728173AbgKLBdr (ORCPT ); Wed, 11 Nov 2020 20:33:47 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36742 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727983AbgKKXwn (ORCPT ); Wed, 11 Nov 2020 18:52:43 -0500 Received: from mail-ed1-x544.google.com (mail-ed1-x544.google.com [IPv6:2a00:1450:4864:20::544]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 00BA7C0613D4 for ; Wed, 11 Nov 2020 15:52:41 -0800 (PST) Received: by mail-ed1-x544.google.com with SMTP id o20so4198210eds.3 for ; Wed, 11 Nov 2020 15:52:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=wCzkEW5xYB1muF+vJ/f8y4UbBC3rxlh1rEGtYpd9n+A=; b=p4Z54kLigVmS52pGYYgv0TvzVirM6B8q2pXATV4e3a8lYsBHkU1U2I5SacNdhrbRSn yHhGwSXj8zaOf+JXCvyVJE3GNSfXW3avkG82QVpbWyBtKYgXG2Hyim0lQyv91qhxFnCc 2pd2S+yaPdZ9ZKrvuKumUN57VrbolKnCZJ9GULXeFkWLvTFbrW9uTwHGM3xyyoKLWpQ7 g3mew3Ju5+KZePzTtDs2CzKCXsayelIvMmtnGXKT37a9cZCnS6YQqDY9kUL+OzRAG6ii qKHQL1KuZJ0PTTU54CvqrW82qW0rxPTXcML2mkg+hCHHMvnHDk+MYGpHMBnyztoISm94 V7Ew== 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:in-reply-to :references:mime-version:content-transfer-encoding; bh=wCzkEW5xYB1muF+vJ/f8y4UbBC3rxlh1rEGtYpd9n+A=; b=WCwg1yXZbDtCooOq8wP5kYmRXLXQtdGnDndKR019iohd/6B/IMCWo2A/SfC9svmkNI YvoZxVuJr6Ne+lD/ArpWlLmcV+kA0bzSjVJDC1VM4TWPnbpUCZ8EyG3NoLbHczNdCrkS 1kCcMJzZ3rnEox4Riy/PQhnkh5hPaPn9e/T/wImLBPMRsWWXFXqf8nx3klsyWDvFJV5l kXiDWKia5g8R7s470Xk8aSc12/gO3PXb29+NPamYsAQgHNvC96T15ok+LUaFIDiNc40e 57nwMbS5qc3yLr3AwjaT4pvTXAPJqeGypUDc76oT5pofg7x1k4VAjuzel1RfNidDqmN+ IlNw== X-Gm-Message-State: AOAM533NWVImkWjPKCNAxSwvR5rTVF41YYiAAaus1K5wvn572XINr6F8 d89KTtM0V6aRQdBwGKLei8Unc42kJaU= X-Google-Smtp-Source: ABdhPJzI+ENj4OV2kyS+JQRy49TT1mnH+Li+o7tG8OQf+CWxQSLyPsqtlNGOtpaDTj7YPc05HgecjA== X-Received: by 2002:a50:a40a:: with SMTP id u10mr2182841edb.16.1605138760481; Wed, 11 Nov 2020 15:52:40 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:28a7:5fc2:f4ab:be33]) by smtp.gmail.com with ESMTPSA id 1sm1391398ejt.107.2020.11.11.15.52.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 15:52:40 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 1/2] add testcase for phi-adjusting during BB merge Date: Thu, 12 Nov 2020 00:52:31 +0100 Message-Id: <20201111235232.78450-2-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201111235232.78450-1-luc.vanoostenryck@gmail.com> References: <20201111235232.78450-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org When merging BBs, phi-sources from the bottom BB should 'overwrite' the ones from the top BB which should be ignored. Add a testcase from the incoming fix. Signed-off-by: Luc Van Oostenryck --- validation/optim/merge_bbe-adjust_phi.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) create mode 100644 validation/optim/merge_bbe-adjust_phi.c diff --git a/validation/optim/merge_bbe-adjust_phi.c b/validation/optim/merge_bbe-adjust_phi.c new file mode 100644 index 000000000000..de4c54cc6d49 --- /dev/null +++ b/validation/optim/merge_bbe-adjust_phi.c @@ -0,0 +1,24 @@ +extern int array[2]; + +static inline int stupid_select(int idx) +{ + if (idx) + idx = 0; + return array[idx]; +} + +int select(void) +{ + int d = stupid_select(-1); + return d; +} + +/* + * check-name: merge_bbe-adjust_phi + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-excludes: phisrc\\. + * check-output-excludes: phi\\. + */ From patchwork Wed Nov 11 23:52:32 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 11898803 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 258EB1391 for ; Thu, 12 Nov 2020 01:47:48 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id EA4BD205ED for ; Thu, 12 Nov 2020 01:47:47 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Gd7yX4ap" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727983AbgKLBds (ORCPT ); Wed, 11 Nov 2020 20:33:48 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36746 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727984AbgKKXwo (ORCPT ); Wed, 11 Nov 2020 18:52:44 -0500 Received: from mail-ej1-x641.google.com (mail-ej1-x641.google.com [IPv6:2a00:1450:4864:20::641]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E9397C0613D6 for ; Wed, 11 Nov 2020 15:52:42 -0800 (PST) Received: by mail-ej1-x641.google.com with SMTP id f20so5162151ejz.4 for ; Wed, 11 Nov 2020 15:52:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=Gykk8oENS8LeP841rrJGoHp56EyOJvm2mZytIseKdn8=; b=Gd7yX4apIrbtFacvQRzUvkAGorHMMXHMj5L3VmSFAtWxTjpYRNLBXKYsOeoOfy1NZI NUMTsuS70BN6aZ4HnjuQqOHdBaxMec5A7xUTqX6FZNBo2QUIdgU6zYmdS3jJVue27u+K XqLAw2dw5xfnt7BHabUh6D0OuX3BiCtVS0JjL6+0MrHYKEp/3ePyR8xIR+Ip44MTiQPM 25o/+1JGdoyLooCqioXCN+V+zlU4M/VKMxisaY7JFXaRWULFaZsMOygO3gGWo/izzOs7 aTbKoduqCWNILbf74s1zmtX5/skkf8zS9GgbO9bn5afoFk7ecI+5IkPJvVBqqfJp/ETY RvMQ== 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:in-reply-to :references:mime-version:content-transfer-encoding; bh=Gykk8oENS8LeP841rrJGoHp56EyOJvm2mZytIseKdn8=; b=DSfytfBUgGmFDPt4VEUibDsUg0YeBhGuCWArh++kRlVPunA7GhhKsvOz7rIO6xA5qz NbhoUoMVvxudluXkcQbghYX3qKDjTGUl5ERtcNeQYqPpyNc4jXaRL6oBOgPu9XmutVOo llC3lijXvR3YiCv7837/Qhc9xoLZ6bUFcXIrlhxSKXBCU+LvLmOfadc7GGYTVlQA1TO8 UuhyHXR9Gi3uo/sSlUK7WLW88MI+j4IOroVa2Tk7pL1POm+n/GBq8vAETlPZUbRfzrs2 7fe7xox4HaG0ftD8GTblDEsl6Gvgo9Qg9ORWVv93JBhQzFwkuJT8WSjlIq7boWSE/DSw Aedg== X-Gm-Message-State: AOAM530dq0cctFMJw4BSMgNUQFLKuIVOq0jV8iimFBJXeT0tr8IBfxi9 StpFhWr8QsZgg5ox8nPoFf99awFdhl4= X-Google-Smtp-Source: ABdhPJxi7Gi/g8aZYyVLIO4KXOX/q5eloZufSrB81fOY/ZqNFTnWWOA5cm/pgyqQPmCDsz4i8A8Meg== X-Received: by 2002:a17:906:66c9:: with SMTP id k9mr28749474ejp.204.1605138761458; Wed, 11 Nov 2020 15:52:41 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:28a7:5fc2:f4ab:be33]) by smtp.gmail.com with ESMTPSA id 1sm1391398ejt.107.2020.11.11.15.52.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 15:52:40 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 2/2] adjust phi-sources when merging BBs Date: Thu, 12 Nov 2020 00:52:32 +0100 Message-Id: <20201111235232.78450-3-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201111235232.78450-1-luc.vanoostenryck@gmail.com> References: <20201111235232.78450-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org When merging two basic blocks, it may happen that both of theses blocks contain a phi-source for the same phi-node. In this case, only the phi-source from the bottom BB must be taken in account, it kinda overwrites the value from the top BB and the phi-source from the top BB must be ignored, in fact it must be removed. However, it is not the case and this extra phi-source creates different kind of problems. Among other things, it hinders further simplifications. For example, the following code: extern int array[2]; static inline int stupid_select(int idx) { if (idx) idx = 0; return array[idx]; } int select(void) { int d = stupid_select(-1); return d; } should boil down to a simple dereference of the array with an index of zero, like: select: load.32 %r8 <- 0[array] ret.32 %r8 but currently gives: select: phisrc.32 %phi3(idx) <- $0xffffffff phisrc.32 %phi4(idx) <- $0 phi.32 %r12(idx) <- %phi3(idx), %phi4(idx) sext.64 %r5 <- (32) %r12(idx) mul.64 %r6 <- %r5, $4 add.64 %r7 <- %r6, array load.32 %r8 <- 0[%r7] ret.32 %r8 This patch takes care of the problem by: * when merging 2 BBs, check when reaching a phi-source in the bottom BB * if one is found, look after sibling phi-sources * remove such sibling if belonging to the top BB. With this change, the code above gives: select: phisrc.32 %phi4(idx) <- $0 phi.32 %r12(idx) <- %phi4(idx) sext.64 %r5 <- (32) %r12(idx) mul.64 %r6 <- %r5, $4 add.64 %r7 <- %r6, array load.32 %r8 <- 0[%r7] ret.32 %r8 which can the be simplified into the expected result. Signed-off-by: Luc Van Oostenryck --- flow.c | 28 +++++++++++++++++++++++++ validation/optim/merge_bbe-adjust_phi.c | 1 - 2 files changed, 28 insertions(+), 1 deletion(-) diff --git a/flow.c b/flow.c index ef8d04e5827f..a74769c37659 100644 --- a/flow.c +++ b/flow.c @@ -723,6 +723,32 @@ void vrfy_flow(struct entrypoint *ep) assert(!entry); } +static void adjust_phi(struct basic_block *top, struct instruction *insn) +{ + struct pseudo_user *pu; + + FOR_EACH_PTR(insn->target->users, pu) { + struct instruction *user; + pseudo_t phi; + + if (!pu) + continue; + user = pu->insn; + assert(user->opcode == OP_PHI); + FOR_EACH_PTR(user->phi_list, phi) { + struct instruction *phisrc; + + if (phi == VOID) + continue; + phisrc = phi->def; + if (phisrc->bb != top) + continue; + REPLACE_CURRENT_PTR(phi, VOID); + kill_instruction(phisrc); + } END_FOR_EACH_PTR(phi); + } END_FOR_EACH_PTR(pu); +} + void pack_basic_blocks(struct entrypoint *ep) { struct basic_block *bb; @@ -804,6 +830,8 @@ out: if (!insn->bb) continue; assert(insn->bb == bb); + if (insn->opcode == OP_PHISOURCE) + adjust_phi(parent, insn); insn->bb = parent; add_instruction(&parent->insns, insn); } END_FOR_EACH_PTR(insn); diff --git a/validation/optim/merge_bbe-adjust_phi.c b/validation/optim/merge_bbe-adjust_phi.c index de4c54cc6d49..6a8ebb73a62d 100644 --- a/validation/optim/merge_bbe-adjust_phi.c +++ b/validation/optim/merge_bbe-adjust_phi.c @@ -16,7 +16,6 @@ int select(void) /* * check-name: merge_bbe-adjust_phi * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-excludes: phisrc\\.