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: 896453 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-476099-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=linaro.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="PU//E0r6"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 40KpZL75Nmz9s1X for ; Tue, 10 Apr 2018 10:53:30 +1000 (AEST) 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=WG4mug06Dy7YFHyT/28pRMLOww2GwMrL3h+L6tqLAw12Fl Sw+k16+6XziTEW/Y82LK7pg4yiaMJuQHgL9AWvz3kwxFKrr8RCLnJuF/ln0SQKMA gaBfQDfQjHf4dlRuHsOXtvYdtkHDqVDzW+8HDmuIYkcsleNLrNZE2ONSVlNFQ= 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=PU//E0r6G+f4zPPUy4Zv WIgaT3FJO2VXmwBcmc9d5SPulBB1vaK3S8+otevieGW4XiGEXq4p9fSn59OyF25e KauBlkGPyWiXwmVp4MGvY6OQEyvcsz1k9YOp5q4AvYDlNHnnbrejU97Hc6HaMXl5 CJuQx2btBg1eYm69BuxyW80= 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-Google-Smtp-Source: AIpwx49v16iM794/xdXW9hj6CLdSJfl+xiQDHW+0UwDE0QGSt1fjKuW96gsHSzTsv9MN6RUpOZWQbrJxZLhFqul5ihI= 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