From patchwork Mon Nov 16 22:29:20 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: 11910951 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 ECF356C1 for ; Mon, 16 Nov 2020 22:29:55 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C909D20E65 for ; Mon, 16 Nov 2020 22:29:55 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="s15OPqAV" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730113AbgKPW3f (ORCPT ); Mon, 16 Nov 2020 17:29:35 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35164 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726543AbgKPW3f (ORCPT ); Mon, 16 Nov 2020 17:29:35 -0500 Received: from mail-ej1-x644.google.com (mail-ej1-x644.google.com [IPv6:2a00:1450:4864:20::644]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2AD03C0613CF for ; Mon, 16 Nov 2020 14:29:35 -0800 (PST) Received: by mail-ej1-x644.google.com with SMTP id me8so26668637ejb.10 for ; Mon, 16 Nov 2020 14:29:35 -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=gFeoJ7Co8u7OfVlouvwI7kH2iObKo4KckGQrmSm11ck=; b=s15OPqAV4CofZPAIok3Lt8FsSGQ1IhP2uwbpaZMwo9xv4lXNC9GeIOhu5LpYaLs2YU sMRPWRguC/EOApr67dzgqwlERM94Hg8yokKsESnY+HAfu+jug0U/H1aikXAqr53hkFXn hMSv+LhWLIVrNjNbH+8XAjzVJ71SgkpAh4THS5xwZMndnCtMjN7B4D7wDN5IMSMuwcWl SI2odcD/yzaTAeXQLarAGNks5Rk0OoMGKmQzR3MtJVKyiLlxziMbtXiQqyHChxcV71Tc R55cTNwPkJJwXF7KRa7whLbNFHRgvrtebTG2bZystKGOUFySfamS/2CiME8hfTSkn5HD ajHw== 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=gFeoJ7Co8u7OfVlouvwI7kH2iObKo4KckGQrmSm11ck=; b=fA1OEG1ad8YpM+70r+xBCOx9jQH2FUsq1aR66RSFnQqJHZZUGPP/u+VBV8CZqMLdcd 5SXvKC2GgOFhQY7JFSPcL8dbG4EFPUbzfwyXFpyoYgnxAmGyV0WdIUAndjiUX3nU8eoW pf+9Tu+YPVvVs5AwaH0t6qSUr0XBD/6JndlScLA1DfUou/bA5/NNidFogDn7azSMCnDq 0H0UFAg7AwueoNc+V2J/R9IfKHpnUsTJJYdRe+YwgCAjydgkTCAiR00aDAlpqXL/9tlP T47sIrZhacjOaG4ZXCdqfpAkIdLxod67M8lYbVP+nwQVd3ReXofNHSGuIvvLACkTPneq 8hOQ== X-Gm-Message-State: AOAM530bKpmBHklDmGw0f7Q2O/pTufDOdZtGl7+AxIxy2hhh6v1V88Y1 QRTNNX4fIdy7NXdjKqaP6vIm+wUWZZg= X-Google-Smtp-Source: ABdhPJzSP1vRiQVUcCzA8NJavtpDPHV4XvtA3PywN7q+xpvzVai+YnmNMFqDZb2DKdgNyx1yRz2gYg== X-Received: by 2002:a17:906:5a97:: with SMTP id l23mr16129762ejq.232.1605565773611; Mon, 16 Nov 2020 14:29:33 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:a141:d91b:1f47:d972]) by smtp.gmail.com with ESMTPSA id bn25sm10805446ejb.76.2020.11.16.14.29.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 Nov 2020 14:29:33 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 1/8] testcase: avoid UNDEF Date: Mon, 16 Nov 2020 23:29:20 +0100 Message-Id: <20201116222927.51939-2-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> References: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Reduced testcases (with creduce, of course) often needlessly have undefined variables. Since these are untouched by the simplification code and should not be present in source code, they should be avoided in optimization testcases. So, defines 'x' to some value other than 0. Signed-off-by: Luc Van Oostenryck --- validation/optim/cse-size.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/validation/optim/cse-size.c b/validation/optim/cse-size.c index 5b31420c84ad..e1a5d492a666 100644 --- a/validation/optim/cse-size.c +++ b/validation/optim/cse-size.c @@ -1,7 +1,7 @@ static void foo(void) { unsigned short p = 0; - int x; + int x = 1; for (;;) if (p) @@ -13,5 +13,6 @@ static void foo(void) * check-command: test-linearize -Wno-decl $file * * check-output-ignore - * check-output-pattern(2): phi\\. + * check-output-pattern(0,1): phi\\. + * check-output-excludes: cbr */ From patchwork Mon Nov 16 22:29:21 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: 11910953 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 35CBC175A for ; Mon, 16 Nov 2020 22:29:56 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0E41220E65 for ; Mon, 16 Nov 2020 22:29:55 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="nRs6jVlB" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730126AbgKPW3g (ORCPT ); Mon, 16 Nov 2020 17:29:36 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35168 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726543AbgKPW3g (ORCPT ); Mon, 16 Nov 2020 17:29:36 -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 CF80EC0613CF for ; Mon, 16 Nov 2020 14:29:35 -0800 (PST) Received: by mail-ej1-x641.google.com with SMTP id y17so21020064ejh.11 for ; Mon, 16 Nov 2020 14:29:35 -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=nRs6jVlBu+PUCiQkJARlS4127ZhkRr5FgC9Y0tCMHi8YkeNXt0Q6N54Wr+P01DIGUZ zYaYyOtKChVCuU0f+V9HLHAeYBMzOsQ2V8H2iNCagmjN6OUvh+AmTIXiOj3xJFd+LXQ1 O6qEhBF4Djq9T4hm9hTtWdtIRsaIRT790UYccvlw/OOMhnwDMtZAkAp8Ug4bcSLOCPVJ 5GQpeTaWiV+CDM8q2z0zesAgzkamBqeYTcG0My385jz0f1ZoB12gZDol8zuDg3vGUo9v pTUyirU2XuV0MY89QnA3AkefWNPAeubN7/nRI8WgsRjlODQzoNQ6HJ82dGz8nfl43YN6 DbYQ== 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=LEkvXA8OONNaDrYWAoal43f0zPiT0GZypOeZUs5d8sy0XbuPDS5riikXbhnoBpnhjv MZAHSK8c/mECvVsi5y7b2u22BClKsJnbdwLIu6DJIWRaKDiGmftkAajCXqJaGL7rdwsj z7cNEeGX6HLkzi5lf6qYcXFN5fmTIee69+BoaSgzyUPF0j2Li0jTNQwOsbBLk+wXwHQA WaSRu+hinqFd8g7eACwaPyaTRApL7CKA5sV91wUB955FSUBfguh1+qbVxsDuBn690zUe s0kbUA+Xa+VwtCweYIYShCHirqAHad9esvMdu96Aw1tQm1GFAwyIs5shBGhX3u4kv9Yb VKuQ== X-Gm-Message-State: AOAM533d8jBvSmz+ir0P7U4NHDUCk0oBvXFVRoQnGhbepULEU7xriPIn ZVk8kyXLNeSidPTdUmGQ+SZ0i8xqV0E= X-Google-Smtp-Source: ABdhPJwfR8j5dJGVWOhSIIabgm3V9RJvKYNcE4FNopozzaQgWI1BpqseasYqwEaWYm88Wcl7R26Wuw== X-Received: by 2002:a17:906:1804:: with SMTP id v4mr16723142eje.201.1605565774417; Mon, 16 Nov 2020 14:29:34 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:a141:d91b:1f47:d972]) by smtp.gmail.com with ESMTPSA id bn25sm10805446ejb.76.2020.11.16.14.29.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 Nov 2020 14:29:33 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 2/8] cfg: add testcase for phi-adjusting during BB merge Date: Mon, 16 Nov 2020 23:29:21 +0100 Message-Id: <20201116222927.51939-3-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> References: <20201116222927.51939-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 Mon Nov 16 22:29:22 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: 11910955 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 75323139F for ; Mon, 16 Nov 2020 22:29:56 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 4E36820E65 for ; Mon, 16 Nov 2020 22:29:56 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="OvVBNuyI" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730133AbgKPW3h (ORCPT ); Mon, 16 Nov 2020 17:29:37 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35174 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726543AbgKPW3g (ORCPT ); Mon, 16 Nov 2020 17:29:36 -0500 Received: from mail-ej1-x642.google.com (mail-ej1-x642.google.com [IPv6:2a00:1450:4864:20::642]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 97AA0C0613CF for ; Mon, 16 Nov 2020 14:29:36 -0800 (PST) Received: by mail-ej1-x642.google.com with SMTP id za3so26684451ejb.5 for ; Mon, 16 Nov 2020 14:29:36 -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=81wWsgCfCpRqHeMvLjRhUTOdhmlgnZ/Rg1IK7eWxBcc=; b=OvVBNuyIuML8B8xc95eMMjIatxE0ym+WGkYOhpv3t2pgO1M6O2O416wuSOmaQqVYWB Oh2+XUV+3xmDgW0AMAmCbsyrYPnoHzLa0nMK6NV+CJshZOnC+uNkfuZfffJdkHg30N9x U/zTTx2TkU+YFREbFkpcEXjJ655XqRiAhZTlkp6lEW2EZxKIrj3zdoqfJwuwFVy4ChrR tJUwZjYbVQMuipjfx/RwHoWER83Ckrs5KvvrZyt+FBANxHCZ7jBGBvth8UA95qsVbdiL YebTvI/llywQSGIOYKBYtIhajJzp9FsMvLigu2bliXFbkF2KGIhvXxm5M+3j+B2idLFK lwEw== 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=81wWsgCfCpRqHeMvLjRhUTOdhmlgnZ/Rg1IK7eWxBcc=; b=jThARrBOKcWzTiZJ4gVbWy0fTcZIkSSlFuLFfYyiBrzt90Xj21M8cb979edmQeSFO2 8uhUT0W8zs3G/8STt4QrK7QxElrUuLJI6yVx/7JZABblK0Qf1ehJgEr9cCPZctG8jdOl kkp2vxYNw+H2stYHRml+wjshZNtyCk0X5+uOPHYMvdxMviZxLUQ/4cH3jbsrPzTgdnM9 /tJFEOy/XumDrT/jevTeVtwAceYqDQmAC7FTdB5RPnR28UZ9ZHsPycLioJDeWOii13+k HrL+BzE3GCHwVUOHCSjarF8g8amjYT6Y5MJI7QdupBPyLn+BR3Tu4TDit6MNRIVp+BLx h5eA== X-Gm-Message-State: AOAM533uJcEZfNLSemW5sljvwEQT3ILa2kWNg2CSVtJ9oUe/QBwQEQh+ Ll2ulUV+oOneM8fUOZnwaUySXvXf20Y= X-Google-Smtp-Source: ABdhPJyCH5mM2FIk/9//G/0sGj4iqQ+WLmy4Mox07oVLhptdVHbEhfu9Jp8zm/CM2jGoR4xxpe3xhg== X-Received: by 2002:a17:906:a891:: with SMTP id ha17mr16648850ejb.116.1605565775143; Mon, 16 Nov 2020 14:29:35 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:a141:d91b:1f47:d972]) by smtp.gmail.com with ESMTPSA id bn25sm10805446ejb.76.2020.11.16.14.29.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 Nov 2020 14:29:34 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 3/8] cfg: extract merge_bb() from pack_basic_blocks() Date: Mon, 16 Nov 2020 23:29:22 +0100 Message-Id: <20201116222927.51939-4-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> References: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Extract merge_bb() from pack_basic_blocks() in order to reuse this part of the code in other simplification/finer grained version of pack_basic_blocks(). Signed-off-by: Luc Van Oostenryck --- flow.c | 58 +++++++++++++++++++++++++++++++++++----------------------- 1 file changed, 35 insertions(+), 23 deletions(-) diff --git a/flow.c b/flow.c index ef8d04e5827f..9ae8612a2312 100644 --- a/flow.c +++ b/flow.c @@ -723,13 +723,46 @@ void vrfy_flow(struct entrypoint *ep) assert(!entry); } +/// +// merge two BBs +// @top: the first BB to be merged +// @bot: the second BB to be merged +static int merge_bb(struct basic_block *top, struct basic_block *bot) +{ + struct instruction *insn; + struct basic_block *bb; + + if (top == bot) + return 0; + + top->children = bot->children; + bot->children = NULL; + bot->parents = NULL; + + FOR_EACH_PTR(top->children, bb) { + replace_bb_in_list(&bb->parents, bot, top, 1); + } END_FOR_EACH_PTR(bb); + + kill_instruction(delete_last_instruction(&top->insns)); + FOR_EACH_PTR(bot->insns, insn) { + if (!insn->bb) + continue; + assert(insn->bb == bot); + insn->bb = top; + add_instruction(&top->insns, insn); + } END_FOR_EACH_PTR(insn); + bot->insns = NULL; + bot->ep = NULL; + return REPEAT_CFG_CLEANUP; +} + void pack_basic_blocks(struct entrypoint *ep) { struct basic_block *bb; /* See if we can merge a bb into another one.. */ FOR_EACH_PTR(ep->bbs, bb) { - struct instruction *first, *insn; + struct instruction *first; struct basic_block *parent, *child, *last; if (!bb_reachable(bb)) @@ -786,28 +819,7 @@ out: goto no_merge; } END_FOR_EACH_PTR(child); - /* - * Merge the two. - */ - repeat_phase |= REPEAT_CFG_CLEANUP; - - parent->children = bb->children; - bb->children = NULL; - bb->parents = NULL; - - FOR_EACH_PTR(parent->children, child) { - replace_bb_in_list(&child->parents, bb, parent, 0); - } END_FOR_EACH_PTR(child); - - kill_instruction(delete_last_instruction(&parent->insns)); - FOR_EACH_PTR(bb->insns, insn) { - if (!insn->bb) - continue; - assert(insn->bb == bb); - insn->bb = parent; - add_instruction(&parent->insns, insn); - } END_FOR_EACH_PTR(insn); - bb->insns = NULL; + repeat_phase |= merge_bb(parent, bb); no_merge: /* nothing to do */; From patchwork Mon Nov 16 22:29:23 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: 11910957 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 A81B717D5 for ; Mon, 16 Nov 2020 22:29:56 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 829DD20E65 for ; Mon, 16 Nov 2020 22:29:56 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="FBzQJ+QJ" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726543AbgKPW3i (ORCPT ); Mon, 16 Nov 2020 17:29:38 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35176 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730140AbgKPW3h (ORCPT ); Mon, 16 Nov 2020 17:29:37 -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 919DEC0613D2 for ; Mon, 16 Nov 2020 14:29:37 -0800 (PST) Received: by mail-ej1-x641.google.com with SMTP id me8so26668763ejb.10 for ; Mon, 16 Nov 2020 14:29:37 -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=UXXUGks/KJZwsWK+aJN+A937y2MkUQYrMzq6SrXlG0k=; b=FBzQJ+QJnRbRpKw7ETjDHRU1g7WEZv4Cu72Ps0s89WFHIbPZtrdPMkYK8JhbNlW4lB EvlC23LpA5cx13tyR6QKz96STfRRqhIjBGpMaywZSsa8Cz6cEruimZmEuicgd6ZuLLTc dn6oO1sQYG3vFV/AnTmHzA9EX+/g7aQV/rXSeJoo4aT9BJqw6nk6rLbcGjHVamyOOAts hfZmpSARWtceDz9LyPZwpyMNwKOca3KMFgBB3QOmJyQzRsrsjxhjGfTUFLUBP1BYUETu bEXpLFnTPvQXHAmoKzP9l0qP8oKztsYvJZfleUeya3JaNGFPswOBaTuP/8B/Y21xEUrl 48lQ== 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=UXXUGks/KJZwsWK+aJN+A937y2MkUQYrMzq6SrXlG0k=; b=nL+NMfabw+y0P1oTSAWz5PiKRqJZXBctlKHuvN9E42+byBunhSmPoEjOXjLAyoGMB0 0kZ9/wobhG+DBcEzPC+o3fGbYMP/EdpzEFGr1p71x6bgQuk0M43mwZW1MtC5nXxNFo1H 2liwg6P3L/yBFdOkJQ99z1KYtYg9/Wiu5q+shzN1p9hGYjFk/6sta6nLAYpI8s+88JMT /lvKFexZnFAo7/tPmp23rIH1sbgyyo0CjtJlWubH+hCBGUa+mm4Mu6t4vtTed2MZX1tF cCVoRlY3PliyXRAac5egxFyJOAR207TKKua4Rx4OvOYmUzzFDFluS/yE1Nk9rYO2uf16 Cyrw== X-Gm-Message-State: AOAM531mHF4VftNjakIeCEOsuiKPU1Ag2WxXnyelfGhqM7CikOwhCICj ai7+l2NtZB5e9Xp2qbNYnvsD4YiBcCw= X-Google-Smtp-Source: ABdhPJxVjkffvX9IdxdaLiOnpDvszjWFEWfxncCHDN366Z3B5Ftv65djn02SCSKeBcv3XN5fyETp4g== X-Received: by 2002:a17:906:b003:: with SMTP id v3mr17272815ejy.290.1605565776021; Mon, 16 Nov 2020 14:29:36 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:a141:d91b:1f47:d972]) by smtp.gmail.com with ESMTPSA id bn25sm10805446ejb.76.2020.11.16.14.29.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 Nov 2020 14:29:35 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 4/8] cfg: adjust phi-sources when merging BBs Date: Mon, 16 Nov 2020 23:29:23 +0100 Message-Id: <20201116222927.51939-5-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> References: <20201116222927.51939-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 | 42 +++++++++++++++++++++++++ validation/optim/merge_bbe-adjust_phi.c | 1 - 2 files changed, 42 insertions(+), 1 deletion(-) diff --git a/flow.c b/flow.c index 9ae8612a2312..e9c8f6b7355e 100644 --- a/flow.c +++ b/flow.c @@ -43,6 +43,25 @@ static int rewrite_branch(struct basic_block *bb, return 1; } +/// +// returns the phi-node corresponding to a phi-source +static struct instruction *get_phinode(struct instruction *phisrc) +{ + struct pseudo_user *pu; + + FOR_EACH_PTR(phisrc->target->users, pu) { + struct instruction *user; + + if (!pu) + continue; + user = pu->insn; + assert(user->opcode == OP_PHI); + return user; + } END_FOR_EACH_PTR(pu); + assert(0); +} + + /* * Return the known truth value of a pseudo, or -1 if * it's not known. @@ -723,6 +742,24 @@ void vrfy_flow(struct entrypoint *ep) assert(!entry); } +static void adjust_phisrc(struct basic_block *top, struct instruction *insn) +{ + struct instruction *user = get_phinode(insn); + pseudo_t 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); +} + /// // merge two BBs // @top: the first BB to be merged @@ -748,6 +785,11 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot) if (!insn->bb) continue; assert(insn->bb == bot); + switch (insn->opcode) { + case OP_PHISOURCE: + adjust_phisrc(top, insn); + break; + } insn->bb = top; add_instruction(&top->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\\. From patchwork Mon Nov 16 22:29:24 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: 11910959 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 E74686C1 for ; Mon, 16 Nov 2020 22:29:56 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C1B9E20E65 for ; Mon, 16 Nov 2020 22:29:56 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ImguAacp" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730144AbgKPW3j (ORCPT ); Mon, 16 Nov 2020 17:29:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35182 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730140AbgKPW3i (ORCPT ); Mon, 16 Nov 2020 17:29:38 -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 8F3CBC0613CF for ; Mon, 16 Nov 2020 14:29:38 -0800 (PST) Received: by mail-ej1-x641.google.com with SMTP id f23so26738488ejk.2 for ; Mon, 16 Nov 2020 14:29:38 -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=Y20OTX9TInFXtpPpAYcH9brk/dtoPFRCRKNZm0BdChE=; b=ImguAacp2RUO8Fxu3yW81XWcsTxbZy0L+FSIn20DARswIJ5DWa3TlxSgBziPdo6eve WJ2JMarY0/eTPzwK68diKGQ1UMoc43f8xjOlaHVMcWsGt1c2SannfSsYzHVSq8/shBks 4dBnKEGU8rUpAobe4503YEvSVln1q75y17RFk2bKsUtea/QoXr+NxQN6Qtsw8MlhUE9h UboE76JoGzNX0hAoWrJCOfZLsqZDE9zR+3eL9dEbrXrW69hsOstweAE0f+bJmunQ+xTb CvJT9JYNAscr8tz3FAGDCYTwYs88Qq3uGb0xTVprXhJVWlhCdPKenaqIFCaSyy4vVb+m GTxg== 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=Y20OTX9TInFXtpPpAYcH9brk/dtoPFRCRKNZm0BdChE=; b=EhtopznbEPDblNE+ORMkH8Rw94yGm3dtY0QlXNzEa4RiCw5vp1qTNtsNe5CD5ez6dc TjPReOdNj/kCWxFmXVFBVzGs7EkDbYHyxAe+aDLHb+oOJoyTGQMPBYIw+T9pg4VD82Tq A5KeO7tVArnr06b4sm6TeBEKDinR1nSKRo+EL7B3pGH96UhpEt7FL9iC0DpV+Mj39yjG i4L1TGKoayOd4UdV487RK8J2CmmJT+RIi4dGMTqje/ebD+dFHHzpjrPKOyqNr4BNe8xB kCm++UWnoYGfVteM9OOwEKFopx1uOss5n86NYFJzJHMFR8m5N9NUzWcpTjbXJnuKVx4F tcKg== X-Gm-Message-State: AOAM533xcNc34Tw6wo+qMnERaL9KDgsospT5t4iucVRXvultHfSc63Mq zRbOXrVZBv7E2+0b021S84NrGcryB0o= X-Google-Smtp-Source: ABdhPJw3mL8Ybv2NN8gLjFjKjVD99ucwBafKyd/l6DTRoDmdSu7SQHlMDtY8nZyCtv1TD8J4GGZH+A== X-Received: by 2002:a17:907:b01:: with SMTP id h1mr16019645ejl.10.1605565777161; Mon, 16 Nov 2020 14:29:37 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:a141:d91b:1f47:d972]) by smtp.gmail.com with ESMTPSA id bn25sm10805446ejb.76.2020.11.16.14.29.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 Nov 2020 14:29:36 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 5/8] cfg: adjust phi-nodes when merging BBs Date: Mon, 16 Nov 2020 23:29:24 +0100 Message-Id: <20201116222927.51939-6-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> References: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org When merging BBs, it's possible that the top BB feeds one or several phi-nodes in the bottom BB. Since phi-nodes only make sense for values incoming from the parent BBs, these phi-nodes can and should be removed when merging the BBs. So, when merging BBs, remove these related phi-nodes. Signed-off-by: Luc Van Oostenryck --- flow.c | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) diff --git a/flow.c b/flow.c index e9c8f6b7355e..23886f9d84fa 100644 --- a/flow.c +++ b/flow.c @@ -760,6 +760,26 @@ static void adjust_phisrc(struct basic_block *top, struct instruction *insn) } END_FOR_EACH_PTR(phi); } +static void adjust_phi(struct basic_block *top, struct instruction *insn) +{ + pseudo_t phi; + + FOR_EACH_PTR(insn->phi_list, phi) { + struct instruction *def; + + if (phi == VOID) + continue; + + def = phi->def; + if (def->bb != top) + continue; + + convert_instruction_target(insn, def->src); + kill_instruction(def); + kill_instruction(insn); + } END_FOR_EACH_PTR(phi); +} + /// // merge two BBs // @top: the first BB to be merged @@ -786,6 +806,9 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot) continue; assert(insn->bb == bot); switch (insn->opcode) { + case OP_PHI: + adjust_phi(top, insn); + continue; case OP_PHISOURCE: adjust_phisrc(top, insn); break; From patchwork Mon Nov 16 22:29:25 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: 11910961 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 32F051391 for ; Mon, 16 Nov 2020 22:29:57 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 09A5B20E65 for ; Mon, 16 Nov 2020 22:29:56 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="hJO35v+p" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730164AbgKPW3k (ORCPT ); Mon, 16 Nov 2020 17:29:40 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35186 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730156AbgKPW3k (ORCPT ); Mon, 16 Nov 2020 17:29:40 -0500 Received: from mail-ej1-x643.google.com (mail-ej1-x643.google.com [IPv6:2a00:1450:4864:20::643]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B061EC0613CF for ; Mon, 16 Nov 2020 14:29:39 -0800 (PST) Received: by mail-ej1-x643.google.com with SMTP id za3so26684591ejb.5 for ; Mon, 16 Nov 2020 14:29:39 -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=FA/hKoCDw1kyjHdjmVPcqeKfj2V8+QrYL9SmRN29fiY=; b=hJO35v+pxLLZom9fia+IV3KEy1vCrkX5/zBA9mXspBmdBi1IsSwlueN74ITMFZ+Rg/ QEFWVVyhPoEh5MiCw/VdezU3EuPKodhZyKTu/wtUZJXjDUzJuwCMuu9xopz0BmpKvTxp 133YUL+OWwluuLGjfvPvxdzIVWpMuR7/kyXyappyfOo9n+YHd1FS1LrDlXJKxUcxUHmL 9H7vzZBCu9uUqFVNeuldRAohiskA+wB9UvSn2wdl0WtYPsHdEgoHhPbN6aUlmWT4bhol nd4MlsTf4gtOYVkCD9zNwYgZxT0BwV4FUfh0ZPqyTxgYGsA4BYIvUj1zrdHIMEprKVeT 9r/Q== 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=FA/hKoCDw1kyjHdjmVPcqeKfj2V8+QrYL9SmRN29fiY=; b=SzVoqGJ1DuBfZIQsDbzjrUkOSXtJi1Rsq52GNDj3awpgKJExo1EZQNcMVYyLpZHaRg HIGugJL8zh8poh6M0zNq3uaUmplGySaPvs3N449Ak/mM+cn7lGNcLgkeot3t09QPjSUF FrafMJDrhxs6Soa5IKQnkY1/Tyfpxdo/M1H9RN2XIdw/iakVobde7AKWw1CQXPXd8soY TiWqozJg3prLpwmoKyTLPasM0aaCy9bMV7Dio7SMpI78QF4w2fublXqd58cz1MIFHICv SQXYj0vCg0xwYofa1RN3SzfxHn4mcaP8NJ30N9KGCVjQM0746/RVrj/gwa9vKpbHxPZC SrAg== X-Gm-Message-State: AOAM530iEIc87xg8buKN8yXb3s096pZXxbUBMpANwvO9T0K2H4+jQca4 M1vnYINjqqJBjyrnfAnh3a6vzWRFiK0= X-Google-Smtp-Source: ABdhPJzHRY9mwnmtNZo/XefRaWhqctBuLz5fvM8xcIzpDFjK0XR0jUeUfXHsdF+npBVSpeNJiovP4w== X-Received: by 2002:a17:906:6b86:: with SMTP id l6mr16685634ejr.524.1605565778229; Mon, 16 Nov 2020 14:29:38 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:a141:d91b:1f47:d972]) by smtp.gmail.com with ESMTPSA id bn25sm10805446ejb.76.2020.11.16.14.29.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 Nov 2020 14:29:37 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 6/8] cfg: add missing REPEAT_CFG_CLEANUP Date: Mon, 16 Nov 2020 23:29:25 +0100 Message-Id: <20201116222927.51939-7-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> References: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org simplify_branch() & insert_branch() convert a conditional branch into an unconditional one, removing a child which may then become unreachable. However, these function doesn't set REPEAT_CFG_CLEANUP and the unreachable child may not be removed. Fix this by setting the missing REPEAT_CFG_CLEANUP in these functions. Signed-off-by: Luc Van Oostenryck --- linearize.c | 1 + simplify.c | 2 +- 2 files changed, 2 insertions(+), 1 deletion(-) diff --git a/linearize.c b/linearize.c index ab91113d00eb..5d800b7f4006 100644 --- a/linearize.c +++ b/linearize.c @@ -726,6 +726,7 @@ void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic remove_parent(child, bb); } END_FOR_EACH_PTR(child); PACK_PTR_LIST(&bb->children); + repeat_phase |= REPEAT_CFG_CLEANUP; } diff --git a/simplify.c b/simplify.c index e58fb6cf3941..a0e23d6de01f 100644 --- a/simplify.c +++ b/simplify.c @@ -2048,7 +2048,7 @@ static int simplify_branch(struct instruction *insn) kill_use(&insn->cond); insn->cond = NULL; insn->opcode = OP_BR; - return REPEAT_CSE; + return REPEAT_CSE|REPEAT_CFG_CLEANUP; } /* Conditional on a SETNE $0 or SETEQ $0 */ From patchwork Mon Nov 16 22:29:26 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: 11910963 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 7069A175A for ; Mon, 16 Nov 2020 22:29:57 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 47B2020E65 for ; Mon, 16 Nov 2020 22:29:57 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jPSQCjiF" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730170AbgKPW3l (ORCPT ); Mon, 16 Nov 2020 17:29:41 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35192 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730156AbgKPW3l (ORCPT ); Mon, 16 Nov 2020 17:29:41 -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 F1E5EC0613CF for ; Mon, 16 Nov 2020 14:29:40 -0800 (PST) Received: by mail-ej1-x641.google.com with SMTP id o9so26690758ejg.1 for ; Mon, 16 Nov 2020 14:29:40 -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=PgWpMH1SC564URbBb9Lr8nEHsRZl17Lt/DPmAksvKU0=; b=jPSQCjiFJ8oXpIFFCo5jbLlOAJ3zRu3xWnR5NNT2vQ5DswMs0/+62Bov7l3XhFbxvF gcPTZECfL++zjRLxBrt8f+0WP7id7dDvQSLezKa8dJ8vhBr4gLu72eF3uLtAlk4K5P8e b4gkFO2AYvx4Jjxo1PCt34tbA9Yd1/PES3JOXQKFHBG9Jw7TujyzCX6pEsQW27DYjfCw 5m4C4cJMDS4lFAe/FwYE3v3HZH/PA/O07p2a5SMj6veYcQvVtKP+ZfEnzeu3CaaZmuH/ w2xGx/PceBW4Kug8eCO/6k19z9t279khF8UvnIeN+mkGWnvEjARA/B59SaagOFv8Q+Et WJRg== 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=PgWpMH1SC564URbBb9Lr8nEHsRZl17Lt/DPmAksvKU0=; b=a/ZCSGk6eKj7XFsO1BJkqcOjWjcmxU7hweofBdKtJZ+0RlZi0vY45nLq+uZGTSqyyJ Y6Om6p/fcG6BcCTHhxyND0jXFB2IPUnXWjcMxiEjw+RgbliprsYdxic7sToKxT6u2eXn coqrEe/5jnHeAdW6fMFc2nWfzKPgBFKHxyMUereldwjkEB5HWq74LQKCOXnd5z5tFWFy DGBSH2LmYefgzL6pARUdLiBNmh9jOeKDVHDJ2t7usa0BmLwsr36F+igO2kL4QkPwDABa bpd0Uh5LEC6Z1xAQoqI+cfIUWKW7LimXiIcpml0DPzFMScnREgIWE11G8BBTw2vn4AcK EyEw== X-Gm-Message-State: AOAM5322fERYXr2OQ3fmivjYvllNABRMu/hNaqvGcLLPjbfgY+RxOJYj pekBKRU6ckWw3Jhm5ZLI9mDTRrQO4nI= X-Google-Smtp-Source: ABdhPJyesGr7+rpo57pCZGcQQlSeXXcT03Qkx60hWkk0xZy91IOuqFz6OPS4OAQc3WaxlTvFowq8UQ== X-Received: by 2002:a17:906:3813:: with SMTP id v19mr16976905ejc.462.1605565779420; Mon, 16 Nov 2020 14:29:39 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:a141:d91b:1f47:d972]) by smtp.gmail.com with ESMTPSA id bn25sm10805446ejb.76.2020.11.16.14.29.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 Nov 2020 14:29:38 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 7/8] cfg: call simplify_memops() unconditionally. Date: Mon, 16 Nov 2020 23:29:26 +0100 Message-Id: <20201116222927.51939-8-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> References: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org Currently, in the main optimization loop, simplify_memops() is only called if REPEAT_SYMBOL_CLEANUP have been set. This has (at least) two problems: 1) simplify_memops() may itself create other 'symbol cleanup' opportunities. That's fine and when it happens REPEAT_SYMBOL_CLEANUP is correctly set but this is directly lost because repeat_phase is cleared just after. So, loads and stores are not always optimized away as they should. 2) Loads & stores are not always done directly on symbols, in fact, it often happens that they are done on some PSEUDO_REG. Here too, loads and stores are not always optimized away as they should. So, call simplify_memops() unconditionally. Note: this have only very small effects on the tests' running time: before after after too real 4m18.001s real 4m18.655s real 4m19.4 user 71m32.911s user 72m02.701s user 72m06.6 sys 29m06.523s sys 29m01.721s sys 29m06.8 which is under the noise I usually have. Signed-off-by: Luc Van Oostenryck --- memops.c | 2 ++ optimize.c | 4 +--- validation/optim/memops-missed01.c | 23 +++++++++++++++++++++++ validation/optim/memops-missed02.c | 14 ++++++++++++++ 4 files changed, 40 insertions(+), 3 deletions(-) create mode 100644 validation/optim/memops-missed01.c create mode 100644 validation/optim/memops-missed02.c diff --git a/memops.c b/memops.c index f071e556da8a..badcdbbb9378 100644 --- a/memops.c +++ b/memops.c @@ -146,10 +146,12 @@ static void simplify_loads(struct basic_block *bb) } rewrite_load_instruction(insn, dominators); } else { // cleanup pending phi-sources + int repeat = repeat_phase; pseudo_t phi; FOR_EACH_PTR(dominators, phi) { kill_instruction(phi->def); } END_FOR_EACH_PTR(phi); + repeat_phase = repeat; } } next_load: diff --git a/optimize.c b/optimize.c index bfab74c01b62..8ab105bccdce 100644 --- a/optimize.c +++ b/optimize.c @@ -84,9 +84,7 @@ repeat: kill_unreachable_bbs(ep); cse_eliminate(ep); - - if (repeat_phase & REPEAT_SYMBOL_CLEANUP) - simplify_memops(ep); + simplify_memops(ep); } while (repeat_phase); pack_basic_blocks(ep); if (repeat_phase & REPEAT_CFG_CLEANUP) diff --git a/validation/optim/memops-missed01.c b/validation/optim/memops-missed01.c new file mode 100644 index 000000000000..fc616f1976a1 --- /dev/null +++ b/validation/optim/memops-missed01.c @@ -0,0 +1,23 @@ +void bar(int); + +void foo(void) +{ + char buf[1] = { 42 }; + const char *p = buf; + const char **q = &p; + int ch = 0; + switch (**q) { + case 4: + ch = 2; + } + bar(ch); +} + +/* + * check-name: memops-missed01 + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: store\\. + * check-output-excludes: load\\. + */ diff --git a/validation/optim/memops-missed02.c b/validation/optim/memops-missed02.c new file mode 100644 index 000000000000..6f0286497943 --- /dev/null +++ b/validation/optim/memops-missed02.c @@ -0,0 +1,14 @@ +void foo(int a[]) +{ + int i, val; + for (;; i++) + val = a[i] ? a[i] : val; +} + +/* + * check-name: memops-missed02 + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-pattern(1): load\\. + */ From patchwork Mon Nov 16 22:29:27 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: 11910965 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 AF68317D5 for ; Mon, 16 Nov 2020 22:29:57 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 8726E20E65 for ; Mon, 16 Nov 2020 22:29:57 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="sSYl9dDs" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730196AbgKPW3n (ORCPT ); Mon, 16 Nov 2020 17:29:43 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35194 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730183AbgKPW3n (ORCPT ); Mon, 16 Nov 2020 17:29:43 -0500 Received: from mail-ed1-x541.google.com (mail-ed1-x541.google.com [IPv6:2a00:1450:4864:20::541]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EFB21C0613CF for ; Mon, 16 Nov 2020 14:29:41 -0800 (PST) Received: by mail-ed1-x541.google.com with SMTP id v22so20383781edt.9 for ; Mon, 16 Nov 2020 14:29: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=9ovcgFCBeKX8imgvBSGlqNn+DZPHjfrOkSCFV+vltzo=; b=sSYl9dDs9D0FHF+80aRV5UUNYCpeZSyNX20/MYn6rGPn5YubTfdeO2yG3jtyy0B0cP nFH6wCzqieq7lZZSRbgY4gSi691FaNRxzWPLUhYQC33FZefdaQdVpgwkkOiB9ZhCzCp+ aQyYOQIEfBXQQPbcbGhgkpHu7NjTocBIaTpyyb+BR/BFS0KFOS9NIVtF71mpdso8d9AN QF5Xurh72mYPAsEU6cOX8grv0VAvpStooazURHLxpHidgM4O4J1MxAPgCouJ1a2w6X3C 3cQ1xSWCuj3Z0xeUQ71SkfEp2BAHAe2ben5EFj+st4FziknTiaTZ32ALEPQFMy1SaD7J 05tA== 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=9ovcgFCBeKX8imgvBSGlqNn+DZPHjfrOkSCFV+vltzo=; b=F/N9bGgiSdxfkHPE+a3K4r1eh32d2Q2U3XLoH2+V7J/T42SNeZH26WrXUMK4MuKysO fqNkYizBffKpYh7qY6acd82lh3diX26R4cFP4xtqmGgGHdlRNvBp7mcIB/+/grWR1OTR cy/tEVhefpUElhxJwCZ97+8ZyOVQy+aO50wVkDF/oyZuExRT9tbWFJodPQzcrwjOkt2c OhSrZAffv0S6qRnfW9xfAvDLDf80ZzZifiZxFv7GrqWt7hUKyDl7hJxOL98T/z4btRF2 CgLkjhKCIOX3arpJO2UOLZpkPx0hHgF3Y/bjHOnfXAOpBdX65a9BZqRTp2k39nvCR62D A7YQ== X-Gm-Message-State: AOAM533vU/MDN8llx7CUsxGqEu9S5EHei+PLUOLOhH2GIDiDlSdUMPXL lw/IeyB2K4Q1neC02SijrgXmP2NXpIY= X-Google-Smtp-Source: ABdhPJw43gi6DJdHgau2KUz7wa043jg7lbXxZ9PiHSCqOJfstnv1iydHRo35SqVgeFFtSCqUyp5oNQ== X-Received: by 2002:aa7:d1d8:: with SMTP id g24mr18814837edp.324.1605565780307; Mon, 16 Nov 2020 14:29:40 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:b7fe:f700:a141:d91b:1f47:d972]) by smtp.gmail.com with ESMTPSA id bn25sm10805446ejb.76.2020.11.16.14.29.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 Nov 2020 14:29:39 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Luc Van Oostenryck Subject: [PATCH 8/8] cfg: early CFG simplification Date: Mon, 16 Nov 2020 23:29:27 +0100 Message-Id: <20201116222927.51939-9-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> References: <20201116222927.51939-1-luc.vanoostenryck@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org The linearization step sometimes creates a lot of intermediate basic blocks, often containing just a branch. Their presence often make things more complicated than needed (more work to do in later phases, visual clutter when inspection the IR 'by hand') and they can sometimes, indirectly hinder some optimizations. Happily, most of them can trivially be optimized away. So, add a CFG simplification phase running very early and doing: *) jump threading (eliminate jump to jump) *) merge single-child/sinle-parents basic blocks. These changes slightly decrease the number of 'context imbalance' warnings (32 less on a total of 995 warnings) and the size of the generated IR (only ~0.4% but this is very significant relatively to most other simplifications). They also seem to improve the kernel tests' running time: before after real 4m19.261s real 4m17.548s user 72m03.634s user 71m34.642s sys 29m05.573s sys 29m01.856s but it's probably just noise. Signed-off-by: Luc Van Oostenryck --- flow.c | 78 ++++++++++++++++++++ flow.h | 1 + optimize.c | 5 ++ validation/call-inlined.c | 4 + validation/expand/builtin_constant_inline0.c | 1 + validation/inline_base0.c | 3 + validation/linear/builtin_unreachable0.c | 4 +- validation/linear/builtin_unreachable1.c | 4 +- validation/linear/call-inline.c | 2 +- validation/mem2reg/cond-expr.c | 4 +- validation/mem2reg/cond-expr5.c | 5 +- validation/optim/cse-size.c | 2 +- 12 files changed, 102 insertions(+), 11 deletions(-) diff --git a/flow.c b/flow.c index 23886f9d84fa..f56e72db470c 100644 --- a/flow.c +++ b/flow.c @@ -121,6 +121,31 @@ static int bb_depends_on_phi(struct basic_block *target, struct basic_block *src return 0; } +/// +// does the BB contains ignorable instructions but a final branch? +// :note: something could be done for phi-sources but ... we'll see. +static bool bb_is_forwarder(struct basic_block *bb) +{ + struct instruction *insn; + + FOR_EACH_PTR(bb->insns, insn) { + if (!insn->bb) + continue; + switch (insn->opcode) { + case OP_NOP: + case OP_INLINED_CALL: + continue; + case OP_CBR: + case OP_BR: + return true; + default: + goto out; + } + } END_FOR_EACH_PTR(insn); +out: + return false; +} + /* * When we reach here, we have: * - a basic block that ends in a conditional branch and @@ -742,6 +767,22 @@ void vrfy_flow(struct entrypoint *ep) assert(!entry); } +static int retarget_parents(struct basic_block *bb, struct basic_block *target) +{ + struct basic_block *parent; + + /* + * We can't do FOR_EACH_PTR() here, because the parent list + * may change when we rewrite the parent. + */ + while ((parent = first_basic_block(bb->parents))) { + if (!rewrite_parent_branch(parent, bb, target)) + return 0; + } + kill_bb(bb); + return REPEAT_CFG_CLEANUP; +} + static void adjust_phisrc(struct basic_block *top, struct instruction *insn) { struct instruction *user = get_phinode(insn); @@ -821,6 +862,43 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot) return REPEAT_CFG_CLEANUP; } +/// +// early simplification of the CFG +// Three things are done here: +// # inactive BB are removed +// # branches to a 'forwarder' BB are redirected to the forwardee. +// # merge single-child/single-parent BBs. +int simplify_cfg_early(struct entrypoint *ep) +{ + struct basic_block *bb; + int changed = 0; + + FOR_EACH_PTR_REVERSE(ep->bbs, bb) { + struct instruction *insn; + struct basic_block *tgt; + + if (!bb->ep) { + DELETE_CURRENT_PTR(bb); + changed = REPEAT_CFG_CLEANUP; + continue; + } + + insn = last_instruction(bb->insns); + if (!insn) + continue; + switch (insn->opcode) { + case OP_BR: + tgt = insn->bb_true; + if (bb_is_forwarder(bb)) + changed |= retarget_parents(bb, tgt); + else if (bb_list_size(tgt->parents) == 1) + changed |= merge_bb(bb, tgt); + break; + } + } END_FOR_EACH_PTR_REVERSE(bb); + return changed; +} + void pack_basic_blocks(struct entrypoint *ep) { struct basic_block *bb; diff --git a/flow.h b/flow.h index 099767d408f5..19a743c83b94 100644 --- a/flow.h +++ b/flow.h @@ -18,6 +18,7 @@ extern void kill_dead_stores(struct entrypoint *ep, pseudo_t addr, int local); extern void simplify_symbol_usage(struct entrypoint *ep); extern void simplify_memops(struct entrypoint *ep); extern void pack_basic_blocks(struct entrypoint *ep); +extern int simplify_cfg_early(struct entrypoint *ep); extern void convert_instruction_target(struct instruction *insn, pseudo_t src); extern void remove_dead_insns(struct entrypoint *); diff --git a/optimize.c b/optimize.c index 8ab105bccdce..338714c78e68 100644 --- a/optimize.c +++ b/optimize.c @@ -57,6 +57,11 @@ void optimize(struct entrypoint *ep) kill_unreachable_bbs(ep); ir_validate(ep); + cfg_postorder(ep); + if (simplify_cfg_early(ep)) + kill_unreachable_bbs(ep); + ir_validate(ep); + domtree_build(ep); /* diff --git a/validation/call-inlined.c b/validation/call-inlined.c index 3612c5c42690..a6cb4b5b0976 100644 --- a/validation/call-inlined.c +++ b/validation/call-inlined.c @@ -28,12 +28,14 @@ foo: add.32 %r3 <- %arg1, %arg2 add.32 %r5 <- %r3, $1 + # call %r6 <- add, %r3, $1 ret.32 %r5 bar: .L3: + # call %r13 <- add, %r10, $1 ret @@ -41,6 +43,7 @@ bas: .L6: add.64 %r16 <- "abc", $1 + # call %r17 <- lstrip, %r14 ret.64 %r16 @@ -48,6 +51,7 @@ qus: .L9: add.64 %r21 <- messg, $1 + # call %r22 <- lstrip, %r19 ret.64 %r21 diff --git a/validation/expand/builtin_constant_inline0.c b/validation/expand/builtin_constant_inline0.c index a0057f2094b3..d72a211fd267 100644 --- a/validation/expand/builtin_constant_inline0.c +++ b/validation/expand/builtin_constant_inline0.c @@ -16,6 +16,7 @@ int foo(void) foo: .L0: + # call %r1 <- is_const, $42 ret.32 $42 diff --git a/validation/inline_base0.c b/validation/inline_base0.c index 517ee972ee05..698c760ff0be 100644 --- a/validation/inline_base0.c +++ b/validation/inline_base0.c @@ -27,6 +27,7 @@ foo0: .L0: add.32 %r5 <- %arg1, %arg2 + # call %r6 <- add, %r1, %r2 ret.32 %r5 @@ -34,12 +35,14 @@ foo1: .L3: add.32 %r10 <- %arg1, $1 + # call %r11 <- add, %r8, $1 ret.32 %r10 foo2: .L6: + # call %r13 <- add, $1, $2 ret.32 $3 diff --git a/validation/linear/builtin_unreachable0.c b/validation/linear/builtin_unreachable0.c index 911ed7f97f95..4fc564739e76 100644 --- a/validation/linear/builtin_unreachable0.c +++ b/validation/linear/builtin_unreachable0.c @@ -14,12 +14,12 @@ foo: .L0: seteq.32 %r2 <- %arg1, $3 - cbr %r2, .L1, .L3 + cbr %r2, .L1, .L2 .L1: unreachable -.L3: +.L2: ret.32 %arg1 diff --git a/validation/linear/builtin_unreachable1.c b/validation/linear/builtin_unreachable1.c index 70f6674c6443..2fc1d728d7d9 100644 --- a/validation/linear/builtin_unreachable1.c +++ b/validation/linear/builtin_unreachable1.c @@ -16,9 +16,9 @@ int foo(int c) foo: .L0: - cbr %arg1, .L3, .L2 + cbr %arg1, .L1, .L2 -.L3: +.L1: ret.32 $1 .L2: diff --git a/validation/linear/call-inline.c b/validation/linear/call-inline.c index dfd49b62c4b7..1ad785ee678b 100644 --- a/validation/linear/call-inline.c +++ b/validation/linear/call-inline.c @@ -13,6 +13,6 @@ int i3(void) { return (***fun)(); } // C99,C11 6.5.3.2p4 * * check-output-ignore * check-output-excludes: load - * check-output-excludes: call + * check-output-excludes: \\tcall * check-output-pattern(5): ret\\..* \\$42 */ diff --git a/validation/mem2reg/cond-expr.c b/validation/mem2reg/cond-expr.c index 8acb00ac950f..2474d65d8c64 100644 --- a/validation/mem2reg/cond-expr.c +++ b/validation/mem2reg/cond-expr.c @@ -9,6 +9,6 @@ int foo(int a, int b, int c) * check-name: cond-expr * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file * check-output-ignore - * check-output-pattern(2): phi\\. - * check-output-pattern(3): phisrc\\. + * check-output-pattern(1): phi\\. + * check-output-pattern(2): phisrc\\. */ diff --git a/validation/mem2reg/cond-expr5.c b/validation/mem2reg/cond-expr5.c index a3ce5e3a955e..beef8f258cd9 100644 --- a/validation/mem2reg/cond-expr5.c +++ b/validation/mem2reg/cond-expr5.c @@ -15,7 +15,6 @@ int foo(int p, int q, int a) * check-output-ignore * check-output-excludes: load\\. * check-output-excludes: store\\. - * check-output-excludes: phi\\..*, .*, .* - * check-output-pattern(3): phi\\. - * check-output-pattern(5): phisrc\\. + * check-output-pattern(2): phi\\. + * check-output-pattern(4): phisrc\\. */ diff --git a/validation/optim/cse-size.c b/validation/optim/cse-size.c index e1a5d492a666..0c0c2d1425ed 100644 --- a/validation/optim/cse-size.c +++ b/validation/optim/cse-size.c @@ -13,6 +13,6 @@ static void foo(void) * check-command: test-linearize -Wno-decl $file * * check-output-ignore - * check-output-pattern(0,1): phi\\. + * check-output-excludes: phi\\. * check-output-excludes: cbr */