From patchwork Fri Apr 21 14:06:59 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 753420 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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 3w8cxk2C6nz9s03 for ; Sat, 22 Apr 2017 00:07:18 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="IqTy+DMo"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:reply-to:mime-version :content-type; q=dns; s=default; b=IgU4UvyAFPTBOL8x59w9db5fr8e5F EQGbLfm4sPgPk9Uw6R+30S702EH5e9O9rPRZusbvehQ0Al2YE0yYYdPccCLytPm1 bfqSUKx7DFEkNTfAqE4kBRmkj5BG9kSHVWsxiqmr7ggiEhxubLz0UrKDnt8MCb8E PLNknEPhA9R4gE= 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:date :from:to:cc:subject:message-id:reply-to:mime-version :content-type; s=default; bh=H8jQh+e3g1TeNouMW13T3Ek+uN0=; b=IqT y+DMo1nrc4jtrL7frPwii3L5sXxS7JMg11/TKyZLJG8aSqZ9P25JACmAGEzJWGib 8WxQIq2gXupb8vGqW3xsKqwgYGjgMCRhda704aGge9P/Um9Y44nvlABrjxFQkfGg dkcwLg0HjejtX6sy3yWAYxTxCfMKCC7CfH0HOtXE= Received: (qmail 80493 invoked by alias); 21 Apr 2017 14:07:05 -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 80437 invoked by uid 89); 21 Apr 2017 14:07:05 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-15.9 required=5.0 tests=BAYES_00, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_LAZY_DOMAIN_SECURITY, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=communicate X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 21 Apr 2017 14:07:02 +0000 Received: from smtp.corp.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 187198E676; Fri, 21 Apr 2017 14:07:03 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 187198E676 Authentication-Results: ext-mx01.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx01.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=jakub@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 187198E676 Received: from tucnak.zalov.cz (ovpn-116-29.ams2.redhat.com [10.36.116.29]) by smtp.corp.redhat.com (Postfix) with ESMTPS id B12CD80DF7; Fri, 21 Apr 2017 14:07:02 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.15.2/8.15.2) with ESMTP id v3LE70WM025965; Fri, 21 Apr 2017 16:07:00 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.15.2/8.15.2/Submit) id v3LE6x2w025964; Fri, 21 Apr 2017 16:06:59 +0200 Date: Fri, 21 Apr 2017 16:06:59 +0200 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [RFC PATCH] Optimize in VRP loads from constant arrays Message-ID: <20170421140659.GB1809@tucnak> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.7.1 (2016-10-04) X-IsSubscribed: yes Hi! This patch attempts to implement the optimization mentioned in http://gcc.gnu.org/ml/gcc-patches/2017-02/msg00945.html If we know a (relatively small) value range for ARRAY_REF index in constant array load and the values in the array for all the indexes in the array are the same (and constant), we can just replace the load with the constant. Shall I introduce a param for the size of the range to consider? 2017-04-21 Jakub Jelinek * tree-vrp.c: Include gimplify.h. (load_index): New variable. (simplify_load_valueize, simplify_load_using_ranges): New functions. (simplify_stmt_using_ranges): Use simplify_load_using_ranges. * gcc.dg/tree-ssa/vrp113.c: New test. Jakub --- gcc/tree-vrp.c.jj 2017-04-20 08:19:27.000000000 +0200 +++ gcc/tree-vrp.c 2017-04-21 15:35:25.869856659 +0200 @@ -62,6 +62,7 @@ along with GCC; see the file COPYING3. #include "alloc-pool.h" #include "domwalk.h" #include "tree-cfgcleanup.h" +#include "gimplify.h" #define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL } @@ -10442,6 +10443,96 @@ simplify_float_conversion_using_ranges ( return true; } +/* Variables used to communicate index and its current value + between simplify_load_using_ranges and its valueize function. */ +static tree load_index[2]; + +/* Valueize callback for simplify_load_using_ranges. */ + +static tree +simplify_load_valueize (tree name) +{ + if (name == load_index[0]) + return load_index[1]; + return name; +} + +/* Simplify a constant load if there is a single ARRAY_REF among + handled components, we have a narrow range for the index and + constant loads with all the indexes in the range yield the same + constant. */ + +static bool +simplify_load_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) +{ + tree rhs = gimple_assign_rhs1 (stmt); + tree t, *p = NULL; + tree index = NULL_TREE; + value_range *vr = NULL; + for (t = rhs; handled_component_p (t); t = TREE_OPERAND (t, 0)) + switch (TREE_CODE (t)) + { + case ARRAY_REF: + if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST) + break; + if (TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME) + { + if (index) + return false; + index = TREE_OPERAND (t, 1); + vr = get_value_range (index); + if (!range_int_cst_p (vr) + || is_overflow_infinity (vr->min) + || is_overflow_infinity (vr->max) + || tree_int_cst_sgn (vr->min) < 0) + return false; + wide_int diff = vr->max; + diff -= vr->min; + /* As we have to check every index in the range, avoid + doing it too many times. */ + if (!wi::ltu_p (diff, 256)) + return false; + } + break; + case ARRAY_RANGE_REF: + return false; + default: + break; + } + if (index == NULL_TREE) + return false; + load_index[0] = index; + load_index[1] = vr->min; + tree c = fold_const_aggregate_ref_1 (rhs, simplify_load_valueize); + /* fold_const_aggregate_ref_1 can unfortunately only valueize a very + small subset of expressions so far. */ + if (c == NULL_TREE) + { + rhs = unshare_expr (rhs); + for (t = rhs; + TREE_CODE (t) != ARRAY_REF || TREE_OPERAND (t, 1) != index; + t = TREE_OPERAND (t, 0)) + ; + p = &TREE_OPERAND (t, 1); + *p = load_index[1]; + c = fold_const_aggregate_ref_1 (rhs, simplify_load_valueize); + } + if (c == NULL_TREE || !is_gimple_min_invariant (c)) + return false; + wide_int w = vr->min; + while (wi::ne_p (w, vr->max)) + { + load_index[1] = wide_int_to_tree (TREE_TYPE (vr->min), ++w); + if (p) + *p = load_index[1]; + tree c2 = fold_const_aggregate_ref_1 (rhs, simplify_load_valueize); + if (c2 == NULL_TREE || !operand_equal_p (c, c2, 0)) + return false; + } + gimple_assign_set_rhs_from_tree (gsi, c); + return true; +} + /* Simplify an internal fn call using ranges if possible. */ static bool @@ -10709,6 +10800,8 @@ simplify_stmt_using_ranges (gimple_stmt_ return simplify_min_or_max_using_ranges (gsi, stmt); default: + if (gimple_assign_single_p (stmt) && handled_component_p (rhs1)) + return simplify_load_using_ranges (gsi, stmt); break; } } --- gcc/testsuite/gcc.dg/tree-ssa/vrp113.c.jj 2017-04-21 15:43:36.291436020 +0200 +++ gcc/testsuite/gcc.dg/tree-ssa/vrp113.c 2017-04-21 15:50:16.751173243 +0200 @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp1-details" } */ + +struct S { int a, b; }; +const struct S v[16] = { { 1, 2 }, { 1, 2 }, { 1, 2 }, { 1, 2 }, { 2, 3 }, { 4, 5 } }; + +int +foo (int x) +{ + return v[x & 3].a + v[(x & 1) + 2].b + "abcd\4\4\4\4\4\4\4\4efgh"[(x & 7) + 4]; +} + +/* { dg-final { scan-tree-dump "Folding statement: \[_a-z0-9\]+ = v\\\[\[_a-z0-9\]+\\\]\.a;\[\n\r]Folded into: \[_a-z0-9]+ = 1;" "vrp1" } } */ +/* { dg-final { scan-tree-dump "Folding statement: \[_a-z0-9\]+ = v\\\[\[_a-z0-9\]+\\\]\.b;\[\n\r]Folded into: \[_a-z0-9]+ = 2;" "vrp1" } } */ +/* { dg-final { scan-tree-dump "Folding statement: \[_a-z0-9\]+ = \"\[^\n\r]*\"\\\[\[_a-z0-9\]+\\\];\[\n\r]Folded into: \[_a-z0-9]+ = 4;" "vrp1" } } */