From patchwork Wed Aug 23 20:15:08 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: 9918243 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 16859602CB for ; Wed, 23 Aug 2017 20:16:08 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 095E028A29 for ; Wed, 23 Aug 2017 20:16:08 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id F26EC28A2D; Wed, 23 Aug 2017 20:16:07 +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 9083828A29 for ; Wed, 23 Aug 2017 20:16:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932629AbdHWUQH (ORCPT ); Wed, 23 Aug 2017 16:16:07 -0400 Received: from mail-wm0-f65.google.com ([74.125.82.65]:36802 "EHLO mail-wm0-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932443AbdHWUQG (ORCPT ); Wed, 23 Aug 2017 16:16:06 -0400 Received: by mail-wm0-f65.google.com with SMTP id f127so639315wmf.3 for ; Wed, 23 Aug 2017 13:16:06 -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:in-reply-to:references; bh=LZYqlqllAPfw6oLk8eAKmv93TeOsppdrUO8Xvdb5XGk=; b=ofXBL4q/K7ynp97PIB/S5KInfWs9wkHcSPWpMB016kxaX8QT8n8g1a3u0JT9/2iEUT n8HNDn43LQuxLEz2TQxCoLiRS2VxknXUzViHAdH3Yuf+mhXpy9Xlvl27u9RXC3JalMjd XCXlW+L/oUjwIdi4h3+iC+doe5EaJetl64vShhlu3nSMQ3Yahfo1ZGWXUwdBEvqXE4Ay SKImoymLj9LMJkuBPJ7j+vQC+eGXYmTP2dmvZXJSqP29C3PXeuApUjmq2Xde1YSRPP4/ YO8Oq2iyzEPjFhuSCajl8FDJOk933BOzWCxrzjFIhwV8Tzr17HZFSyrKPa8mF7irvGlf jkVg== 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; bh=LZYqlqllAPfw6oLk8eAKmv93TeOsppdrUO8Xvdb5XGk=; b=iJXTCG5ueNJ20+FiOAxNev/7MwMYdITxpZeimKqbP4Jv7NjLAc6xP1cMjU1HxiqRTc 0+j62K3W5CpijNxBwRFOIvi51JXWBGMbqVWfVALeJapI5jFKU5iq0HK0QG/lmhQOO4dn wBEiWlVyaPJV/jZ3nDZ9C8DdON/oJxJI2EmLrIjms5vPzZ+SuL0+7p49blLnmIH3x8z6 kuxJ/z+Hj8XTiYewetwwJrmxm18tQ0M9+9k8FBAwO55/YxcTEM3qFokbTQMu72m03wcZ qM4y/tvo3/RYLem7+2JMOkCcNqSx8EZuCuuiL7Y5Jcgi6bn/Pfe22VIKudRc8utMIRsp 1IkQ== X-Gm-Message-State: AHYfb5jbhrHjjNO8XgQH/2YFEIDY+JiskNPElZLgMPCl0LQ6JybaDkSL cOeou1EkXNWrFg/teQI= X-Received: by 10.80.240.19 with SMTP id r19mr4002098edl.154.1503519365151; Wed, 23 Aug 2017 13:16:05 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:4076:600:9020:103b:7912:3a40]) by smtp.gmail.com with ESMTPSA id e29sm1183374edd.88.2017.08.23.13.16.04 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 23 Aug 2017 13:16:04 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Christopher Li , Luc Van Oostenryck Subject: [RFC PATCH 02/48] remove trivial phi-nodes during clean_up_phi() Date: Wed, 23 Aug 2017 22:15:08 +0200 Message-Id: <20170823201554.90551-3-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.14.0 In-Reply-To: <20170823201554.90551-1-luc.vanoostenryck@gmail.com> References: <20170823201554.90551-1-luc.vanoostenryck@gmail.com> 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 In a set of related phi-nodes and phi-sources if all phi-sources but one correspond to the target of one of the phi-sources, then no phi-nodes is needed and all %phis can be replaced by the unique source. For example, if we have something like: foo: phisrc.32 %phi1 <- %arg1 br .L1 .L1: phi.32 %r2 <- %phi1, %phi2 phisrc.32 %phi2 <- %r2 ... we can see that %phi2 is the target of the phi-node that use it thus neither %phi2 nor %r2 are completly inter-dependent and the only true soure is %arg1. In this case %r2 can be replaced by %arg1 and the phi-node can be removed as well as its phi-sources. There are also more complex cases with several inter-related phi-nodes, the source of a phi-node being defined by another phi-node. Like for the simple case, if there is only a single independent source, all the related phi-nodes can be replaced by this unique true source and the the phi-sources can be removed. Removing these trivial phi-nodes will usually trigger other simplifications, especially those concerning the CFG. Signed-off-by: Luc Van Oostenryck --- simplify.c | 56 ++++++++++++++++++++++++++++------------- validation/optim/trivial-phis.c | 15 +++++++++++ 2 files changed, 54 insertions(+), 17 deletions(-) create mode 100644 validation/optim/trivial-phis.c diff --git a/simplify.c b/simplify.c index 2bc86f53e..766ac451d 100644 --- a/simplify.c +++ b/simplify.c @@ -133,37 +133,59 @@ static int if_convert_phi(struct instruction *insn) return REPEAT_CSE; } -static int clean_up_phi(struct instruction *insn) +static int trivial_phi(pseudo_t *same, struct instruction *insn, struct pseudo_list **list) { + pseudo_t target = insn->target; pseudo_t phi; - struct instruction *last; - int same; - last = NULL; - same = 1; + assert(insn->opcode == OP_PHI); + + if (pseudo_in_list(*list, target)) + return 1; + add_pseudo(list, target); + FOR_EACH_PTR(insn->phi_list, phi) { struct instruction *def; + pseudo_t src; + if (phi == VOID) continue; def = phi->def; - if (def->src1 == VOID || !def->bb) + assert(def->bb); + if (!def->bb) continue; - if (last) { - if (last->src1 != def->src1) - same = 0; + + src = def->src; // bypass OP_PHISRC & get the real source + + if (src == VOID || src == target || src == *same) + continue; + if (!*same) { + *same = src; continue; } - last = def; + if (src->type == PSEUDO_REG && src->def->opcode == OP_PHI) { + if (trivial_phi(same, src->def, list)) + continue; + } + return 0; } END_FOR_EACH_PTR(phi); - if (same) { - pseudo_t pseudo = last ? last->src1 : VOID; - convert_instruction_target(insn, pseudo); - kill_instruction(insn); - return REPEAT_CSE; - } + return 1; +} + +static int clean_up_phi(struct instruction *insn) +{ + struct pseudo_list *list = NULL; + pseudo_t same = NULL; + + if (!trivial_phi(&same, insn, &list)) + return if_convert_phi(insn); - return if_convert_phi(insn); + if (!same) + same = VOID; + convert_instruction_target(insn, same); + kill_instruction(insn); + return REPEAT_CSE; } static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count) diff --git a/validation/optim/trivial-phis.c b/validation/optim/trivial-phis.c new file mode 100644 index 000000000..9cb9a2c78 --- /dev/null +++ b/validation/optim/trivial-phis.c @@ -0,0 +1,15 @@ +void foo(int *p) +{ + int a = *p; + while (1) + a ^= 0; +} + +/* + * check-name: trivial phis + * check-command: test-linearize -Wno-decl $file + * check-output-ignore + * check-output-excludes: phi\\. + * check-output-excludes: phisrc\\. + * check-output-end + */