From patchwork Tue Apr 10 00:52:31 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 133053 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp773590ljb; Mon, 9 Apr 2018 17:53:37 -0700 (PDT) X-Google-Smtp-Source: AIpwx481hs+FcHKabXiZBldFM9VQa2ix3T22D5yXf2wT9iWPfk7A5vEFoM42HoFQq5NfdbXrK6YK X-Received: by 2002:a17:902:24a5:: with SMTP id w34-v6mr40788787pla.328.1523321617348; Mon, 09 Apr 2018 17:53:37 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1523321617; cv=none; d=google.com; s=arc-20160816; b=rG/nTbPNgxaBMPjPRguicpu/5abjeJQUrytwMq68W/FRfBoiUvgQC2O+5LiUMdq7BF r3NrUZdYRfnpXopBf/llSjrp6QfBEnBSLBwSsWA5p4RnfrWLrEzrnAjrQ8J/DNOxue7G VMoTAN1Epgv+m/sTeBAQD2olD+XaYvpFC0qCSnRFogdaDhTFx3sV1YQLZ5zovjRJdCQp qlXiLcHD5W+6M9D5mcPAPDZ04Hhfr8uWMX+yuw3TzsSVALrM9KjhKYABALf1VE30ZJ7D aj/bxSVlv/TVUnM0155fSKasSKzq7tisNPbaS1Ah/lNzunCmwvrR3LclY1PSCncXvs9z iDSw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:subject:message-id:date:from:mime-version:delivered-to:sender :list-help:list-post:list-archive:list-unsubscribe:list-id :precedence:mailing-list:dkim-signature:domainkey-signature :arc-authentication-results; bh=k2y8jmxYEzrBdHUGI+fQwMOcQdWtwk4t9WezwM0vhV8=; b=mI483vZNZ1YdSGGcKqL1EQGll1UePyKlX6YxHa7msdAN+mb2DY56ZU/9i6OZz5r560 p7HlD1wDdsdZtnx0IWft4LVufZ8ViPZSWlJ+fJ+s+jkGPwgcEZ/3/HzQtb6ffrIFydz/ 5J/tCF2HWEo5LishVi8u4RmcRj6QjdJzB1m3O5EqEiw/uoI4M7wVScyvK0A3VgzTuGW4 FyFhzXXw8Ta/ZXz6cAy/zFiHeFF3miQjSfFPitTUAm4H+keoVGv1Moc6G4qPZstavBsi HoOVBxn8L6H3NNZAAmyw1/mMNRuZqeZ24E421/WYjKAdBOxay6hNc8wKakEDjwrt+kLi Tx1Q== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=NxxiFXd2; spf=pass (google.com: domain of gcc-patches-return-476099-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-476099-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id a15-v6si1447957pll.21.2018.04.09.17.53.36 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 09 Apr 2018 17:53:37 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-476099-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=NxxiFXd2; spf=pass (google.com: domain of gcc-patches-return-476099-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-476099-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:from:date:message-id:subject:to:content-type; q= dns; s=default; b=d+gyMqifeXy/CAnwFf7b3ZvrYqKAmUc86UBJ67ishH1vjq lqGk/lL6+/C3A1A+ADMpTvJTzFgGHu069WfWH0zBDowy6IjwqftHiBP5NBGavBwN M+p8n9ixDGaitBSXF4biRf7zW23wf/v8CGlBNKjZpZAAyPYMOHwUUjHaoEctE= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:from:date:message-id:subject:to:content-type; s= default; bh=W+VkwO0Kug2wfp0Oaf73NaXqWaE=; b=NxxiFXd2n14nlVWDP48g eZ4iD+5WMPIP1bTrgIZryRDf+vVAt5HXVgXK1cpSlcf2wAjmTgj43gdPZOavoRwv AcNTC9+1HnkTc5Vvri0LmzXYQ1PLiYcUDCQ10OjddYDvtAq0xNtqetU+u8LcRlxx 5riFMkZI3RPjkThSCSGx0Hw= Received: (qmail 65632 invoked by alias); 10 Apr 2018 00:53:17 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 65194 invoked by uid 89); 10 Apr 2018 00:53:15 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=obtained X-HELO: mail-io0-f181.google.com Received: from mail-io0-f181.google.com (HELO mail-io0-f181.google.com) (209.85.223.181) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 10 Apr 2018 00:53:13 +0000 Received: by mail-io0-f181.google.com with SMTP id x77so11822889ioi.2 for ; Mon, 09 Apr 2018 17:53:13 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=0xxrUcWU/goLTcAXHDzvqDdcuxZCfZtx//sMCQc9hb8=; b=t4SFk+BMrWZ4RuVECxb06MSf7kd+EDDOybPrNufeyOPjKS2KUcJgfldoRrz7c+QpZZ YEQlx9wua4UB5yfbbKhHUmk2KxtNAVi1AGaGXl18Zzrx4HYOASbvKBIaORnRNeidCyDJ 1X7xf7E1ajNvRutXts78YQSRw1rdwfEEybCY63fwxOgAmDbkb0ae9MRSY1/H6DGsoWoJ 6yYKsL9H1SQGPZ+DtivwYYZKCtu4Q/s2WaN6iEFbNn0qPSBSMiI1/MqX6X2YD0YmeRHZ iqaG54Jld5iVo6uF1JiKsKnXS8Bt5BHJxLWnyqeBZDH0Lr7qONhXCQmgS8SXLV1JwrgS wZMg== X-Gm-Message-State: ALQs6tBjE0gA2HlVQz3Jv5YAYYdRhNoZ8Txex+Z7+OraOdT39Dr4gMIt Tg2KgM0RypCnCc0QCdzIQFPm0Nh4EsaKZfMPdXomFJZYeL8= X-Received: by 10.107.178.14 with SMTP id b14mr1112898iof.294.1523321591626; Mon, 09 Apr 2018 17:53:11 -0700 (PDT) MIME-Version: 1.0 Received: by 10.192.174.131 with HTTP; Mon, 9 Apr 2018 17:52:31 -0700 (PDT) From: Kugan Vivekanandarajah Date: Tue, 10 Apr 2018 10:52:31 +1000 Message-ID: Subject: [RFC] Improve tree DSE To: GCC Patches X-IsSubscribed: yes I would like to queue this patch for stage1 review. In DSE, while in dse_classify_store, as soon as we see a PHI use statement that is part of the loop, we are immediately giving up. As far as I understand, this can be improved. Attached patch is trying to walk the uses of the PHI statement (by recursively calling dse_classify_store) and then making sure the obtained store is indeed redundant. This is partly as reported in one of the testcase from PR44612. But this PR is about other issues that is not handled in this patch. Bootstrapped and regression tested on aarch64-linux-gnu with no new regressions. Is this OK for next stage1? Thanks, Kugan gcc/ChangeLog: 2018-04-10 Kugan Vivekanandarajah * tree-ssa-dse.c (dse_classify_store): Handle recursive PHI. (dse_dom_walker::dse_optimize_stmt): Update call dse_classify_store. gcc/testsuite/ChangeLog: 2018-04-10 Kugan Vivekanandarajah * gcc.dg/tree-ssa/ssa-dse-31.c: New test. * gcc.dg/tree-ssa/ssa-dse-32.c: New test. >From 5751eaff3d1c263e8631d5a07e43fecaaa0e9d26 Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah Date: Tue, 10 Apr 2018 09:49:10 +1000 Subject: [PATCH] improve dse --- gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-31.c | 16 ++++++++++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-32.c | 23 ++++++++++++++ gcc/tree-ssa-dse.c | 51 ++++++++++++++++++++++++------ 3 files changed, 81 insertions(+), 9 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-31.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-32.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-31.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-31.c new file mode 100644 index 0000000..e4d71b2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-31.c @@ -0,0 +1,16 @@ + +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dse-details" } */ +#define SIZE 4 + +int main () +{ + static float a[SIZE]; + int i; + for (i = 0; i < SIZE; i++) + __builtin_memset ((void *) a, 0, sizeof(float)*3); + __builtin_memset ((void *) a, 0, sizeof(float)*SIZE); + return 0; +} + +/* { dg-final { scan-tree-dump-times "Deleted dead calls" 1 "dse1"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-32.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-32.c new file mode 100644 index 0000000..3d8fd5f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-32.c @@ -0,0 +1,23 @@ + +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dse-details" } */ +#define SIZE 4 + +void s4 (float *restrict a) +{ + (void) __builtin_memset ((void *) a, 0, sizeof(float)*SIZE); +} + + +int main () +{ + int i; + float a[10]; + printf("Start\n"); + for (i = 0; i < SIZE; i++) + s4 (a); + printf("Done\n"); + return 0; +} + +/* { dg-final { scan-tree-dump-times "Deleted dead calls" 1 "dse1"} } */ diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c index 9220fea..3513fda 100644 --- a/gcc/tree-ssa-dse.c +++ b/gcc/tree-ssa-dse.c @@ -521,11 +521,11 @@ live_bytes_read (ao_ref use_ref, ao_ref *ref, sbitmap live) Return TRUE if the above conditions are met, otherwise FALSE. */ static dse_store_status -dse_classify_store (ao_ref *ref, gimple *stmt, gimple **use_stmt, - bool byte_tracking_enabled, sbitmap live_bytes) +dse_classify_store (ao_ref *ref, gimple *stmt_outer, gimple *stmt, + gimple **use_stmt, bool byte_tracking_enabled, + sbitmap live_bytes, unsigned cnt = 0) { gimple *temp; - unsigned cnt = 0; *use_stmt = NULL; @@ -556,9 +556,11 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple **use_stmt, { cnt++; + if (use_stmt == stmt_outer) + continue; /* If we ever reach our DSE candidate stmt again fail. We cannot handle dead stores in loops. */ - if (use_stmt == stmt) + else if (use_stmt == stmt) { fail = true; BREAK_FROM_IMM_USE_STMT (ui); @@ -572,8 +574,6 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple **use_stmt, if (temp /* Make sure we are not in a loop latch block. */ || gimple_bb (stmt) == gimple_bb (use_stmt) - || dominated_by_p (CDI_DOMINATORS, - gimple_bb (stmt), gimple_bb (use_stmt)) /* We can look through PHIs to regions post-dominating the DSE candidate stmt. */ || !dominated_by_p (CDI_POST_DOMINATORS, @@ -582,8 +582,41 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple **use_stmt, fail = true; BREAK_FROM_IMM_USE_STMT (ui); } + else if (dominated_by_p (CDI_DOMINATORS, + gimple_bb (stmt), gimple_bb (use_stmt))) + { + gphi *phi = as_a (use_stmt); + gimple *def_stmt = SSA_NAME_DEF_STMT (PHI_RESULT (phi)); + enum dse_store_status status = DSE_STORE_LIVE; + ao_ref use_ref; + gimple *inner_use_stmt; + + /* If stmt dominates PHI stmt, follow the PHI stmt. */ + if (!temp) + status = dse_classify_store (ref, stmt, def_stmt, &inner_use_stmt, + byte_tracking_enabled, + live_bytes, cnt); + + if (status == DSE_STORE_DEAD + /* Makesure the use stmt found is post dominated. */ + && dominated_by_p (CDI_POST_DOMINATORS, + gimple_bb (stmt_outer), gimple_bb (inner_use_stmt)) + /* Also check that the store is redundant. */ + && initialize_ao_ref_for_dse (inner_use_stmt, &use_ref) + && valid_ao_ref_for_dse (&use_ref) + && use_ref.base == ref->base + && known_eq (use_ref.size, use_ref.max_size) + && known_ge (use_ref.size, ref->size) + && known_eq (use_ref.offset, ref->offset)) + temp = inner_use_stmt; + else + { + fail = true; + BREAK_FROM_IMM_USE_STMT (ui); + } + } /* Do not consider the PHI as use if it dominates the - stmt defining the virtual operand we are processing, + stmt defining the virtual operand we are processing, we have processed it already in this case. */ if (gimple_bb (defvar_def) != gimple_bb (use_stmt) && !dominated_by_p (CDI_DOMINATORS, @@ -799,7 +832,7 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) enum dse_store_status store_status; m_byte_tracking_enabled = setup_live_bytes_from_ref (&ref, m_live_bytes); - store_status = dse_classify_store (&ref, stmt, &use_stmt, + store_status = dse_classify_store (&ref, stmt, stmt, &use_stmt, m_byte_tracking_enabled, m_live_bytes); if (store_status == DSE_STORE_LIVE) @@ -834,7 +867,7 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) m_byte_tracking_enabled = setup_live_bytes_from_ref (&ref, m_live_bytes); enum dse_store_status store_status; - store_status = dse_classify_store (&ref, stmt, &use_stmt, + store_status = dse_classify_store (&ref, stmt, stmt, &use_stmt, m_byte_tracking_enabled, m_live_bytes); if (store_status == DSE_STORE_LIVE) -- 2.7.4