From patchwork Sun Jun 10 22:13:28 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Sebor X-Patchwork-Id: 927441 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-479416-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="mq0nyc2d"; 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 413r5S2dZSz9s01 for ; Mon, 11 Jun 2018 08:13:46 +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:from :subject:to:message-id:date:mime-version:content-type; q=dns; s= default; b=qn9ZixM+CTGHv2ZplC8IcKxRRV3CAISiE0zuWVroKbc8dSKpTLh5Y qzx/yIOfjeU8ZOOHG5VY5TipFxXorw4kca18bur14OEmk9+DrrSxuG5xxmoKXnER 5fLjPhYZGGSm6jsFMJJlVx0b/rQMelW61YP8tvC+aF//DMhYhE+Qf4= 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:from :subject:to:message-id:date:mime-version:content-type; s= default; bh=YCJK9hFQ7fyiP5PMRS1PVQxTgP8=; b=mq0nyc2dLFXesQyiHtj/ lfzw5yagAfRDyPKb8k/opnwhPYjD+NoiWEBRUYXkB1JgsnkAg+3LcLJpS4fBeuP8 FhB2+KOMWVwV5w47ZqsT/XNvJ9RG+B8xhYaYbtVrYetgebdKVetZXFoDKzt17aYz ZdqEtQUhjWY/MVrPc6x0vo4= Received: (qmail 64714 invoked by alias); 10 Jun 2018 22:13:39 -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 64702 invoked by uid 89); 10 Jun 2018 22:13:39 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.2 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=came, 261284, VR_ANTI_RANGE, Hx-spam-relays-external:209.85.218.66 X-HELO: mail-oi0-f66.google.com Received: from mail-oi0-f66.google.com (HELO mail-oi0-f66.google.com) (209.85.218.66) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 10 Jun 2018 22:13:33 +0000 Received: by mail-oi0-f66.google.com with SMTP id i205-v6so16292361oib.1 for ; Sun, 10 Jun 2018 15:13:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:subject:to:message-id:date:user-agent :mime-version; bh=hv0ZYyZZDzxvu0Yc3dYExPjmWkd5YOQ8Ub8K1EPOJu8=; b=DlLwFJKxy+hRQMz/nqJTDSSUjPLzgZERkk4g36OcZBMeL27YyO3YaNp0re1v1+GorR ysdCx+RV9PyjqE7gyyiNqkh7/DkzO2mGeYQ2GxcH20D30/vVpSZOqhR9CS4Rsm23azAU fwMuNkUbjawsOQgX+cXHYmWgrAYbBzPw+BLHLbDyMvhqr/g/mhnokedTUDa1oXRukNwF fluJjHVraS+XyijXGIYcnRTeKItRo8026M+/FZtj90ABgqf6TgwixiexMPj8/iQwHTo7 FSE3YCWaJDa3zsZWINF91JNdeIycbiPcXm2T1LJSDkjAVsyWRiyWPE/whdIOKoCkUqIE s8hw== X-Gm-Message-State: APt69E2HFk6nwn9Lck1LkwXqMtxmyXynnV0ce26ArgBvDg4hIeiO/bjr V1szvaJqqkPe4x7/Jmqy+8SAuw== X-Google-Smtp-Source: ADUXVKKXeaT+OjHhBGCaVSGSu9Tp1WGFCD4zHijW+HWiZBKDyvEyfEdQoLGZKWV5/qjpMwGkhl/4zw== X-Received: by 2002:aca:c617:: with SMTP id w23-v6mr6650040oif.63.1528668811605; Sun, 10 Jun 2018 15:13:31 -0700 (PDT) Received: from localhost.localdomain (75-166-107-65.hlrn.qwest.net. [75.166.107.65]) by smtp.gmail.com with ESMTPSA id f64-v6sm16981339oib.10.2018.06.10.15.13.29 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 10 Jun 2018 15:13:30 -0700 (PDT) From: Martin Sebor Subject: [PATCH] handle non-constant character assignments in strlen (PR 86083) To: Gcc Patch List Message-ID: <91a6d30a-3ec8-10a8-ed9f-200fff51b770@gmail.com> Date: Sun, 10 Jun 2018 16:13:28 -0600 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.8.0 MIME-Version: 1.0 X-IsSubscribed: yes In the long resolved pr57230 I came across a discussion of an enhancement to the strlen pass to also handle non-const char assignments into the middle of known strings, in addition to assignments where the stored value is known. Storing non-nul into the middle of a string of known length means that its length can be assumed to stay the same, exposing more strlen optimization opportunities. The attached patch implements this idea. (I looked for a simple function that returns true/false based on whether a SSA_NAME is or isn't definitely non-zero but couldn't find one so I created one though it seems that extending one of the existing functions might be a better approach?) In a GCC build the patch discovers 40 non-nul stores out of 70 instances where range info is available (all in libstdc++), so it gives some, albeit very small, improvement. Martin PR tree-optimization/86083 - handle non-constant assignments in strlen gcc/ChangeLog: PR tree-optimization/86083 * tree-ssa-strlen.c (value_is_nonzero): New static function. (handle_char_store): Call it. gcc/testsuite/ChangeLog: PR tree-optimization/86083 * gcc.dg/strlenopt-44.c: New test. Index: gcc/tree-ssa-strlen.c =================================================================== --- gcc/tree-ssa-strlen.c (revision 261284) +++ gcc/tree-ssa-strlen.c (working copy) @@ -3126,6 +3126,27 @@ get_string_cst_length (tree rhs) return -1; } +/* Return true iff EXP has a non-zero value, false otherwise. */ + +static bool +value_is_nonzero (tree exp) +{ + if (TREE_CODE (exp) != SSA_NAME) + return integer_nonzerop (exp); + + wide_int min, max; + value_range_type rng = get_range_info (exp, &min, &max); + + if (rng == VR_RANGE) + return wi::gts_p (min, wi::zero (min.get_precision ())); + + if (rng == VR_ANTI_RANGE) + return (wi::les_p (min, wi::zero (min.get_precision ())) + && wi::les_p (wi::zero (min.get_precision ()), max)); + + return false; +} + /* Handle a single character store. */ static bool @@ -3165,9 +3186,7 @@ handle_char_store (gimple_stmt_iterator *gsi) } bool storing_zero_p = initializer_zerop (rhs); - bool storing_nonzero_p = (!storing_zero_p - && TREE_CODE (rhs) == INTEGER_CST - && integer_nonzerop (rhs)); + bool storing_nonzero_p = !storing_zero_p && value_is_nonzero (rhs); /* Set to the length of the string being assigned if known. */ HOST_WIDE_INT rhslen; Index: gcc/testsuite/gcc.dg/strlenopt-44.c =================================================================== --- gcc/testsuite/gcc.dg/strlenopt-44.c (nonexistent) +++ gcc/testsuite/gcc.dg/strlenopt-44.c (working copy) @@ -0,0 +1,79 @@ +/* PR tree-optimization/86083 - handle non-constant assignments in strlen + { dg-do compile } + { dg-options "-O2 -Wall -fdump-tree-optimized" } */ + +#include "range.h" +#include "strlenopt.h" + +#define CAT(x, y) x ## y +#define CONCAT(x, y) CAT (x, y) +#define FAILNAME(name) CONCAT (call_ ## name ##_on_line_, __LINE__) + +#define FAIL(name) do { \ + extern void FAILNAME (name) (void); \ + FAILNAME (name)(); \ + } while (0) + +/* Macro to emit a call to funcation named + call_in_true_branch_not_eliminated_on_line_NNN() + for each call that's expected to be eliminated. The dg-final + scan-tree-dump-time directive at the bottom of the test verifies + that no such call appears in output. */ +#define ASSERT_ELIM(expr) \ + if (!(expr)) FAIL (in_true_branch_not_eliminated); else (void)0 + +/* Macro to emit a call to a function named + call_made_in_{true,false}_branch_on_line_NNN() + for each call that's expected to be retained. The dg-final + scan-tree-dump-time directive at the bottom of the test verifies + that the expected number of both kinds of calls appears in output + (a pair for each line with the invocation of the KEEP() macro. */ +#define ASSERT_KEEP(expr) \ + if (expr) \ + FAIL (made_in_true_branch); \ + else \ + FAIL (made_in_false_branch) + + +#define ELIM(init, i, c, res) \ + do { \ + char a[] = init; \ + a[i] = c; \ + ASSERT_ELIM (strlen (a) == res); \ + } while (0) + +#define KEEP(init, i, c, res) \ + do { \ + char a[] = init; \ + a[i] = c; \ + ASSERT_KEEP (strlen (a) == res); \ + } while (0) + +void test_elim (void) +{ + ELIM ("1", 0, UR (1, 2), 1); + ELIM ("1", 0, UR (1, 127), 1); + ELIM ("1", 0, UR ('0', '9'), 1); + + ELIM ("12", 0, UR (1, 127), 2); + ELIM ("12", 1, UR (1, 127), 2); + + ELIM ("123", 0, UR (1, 9), 3); + ELIM ("123", 1, UR (10, 99), 3); + ELIM ("123", 2, UR (100, 127), 3); +} + +#line 1000 + +void test_keep (void) +{ + size_t uchar_max = (unsigned char)-1; + + KEEP ("1", 0, UR (1, uchar_max + 1), 1); + KEEP ("1\0\3", 1, UR (1, 2), 1); +} + +/* { dg-final { scan-tree-dump-times "call_in_true_branch_not_eliminated_" 0 "optimized" } } + + { dg-final { scan-tree-dump-times "call_made_in_true_branch_on_line_1\[0-9\]\[0-9\]\[0-9\]" 2 "optimized" } } + { dg-final { scan-tree-dump-times "call_made_in_false_branch_on_line_1\[0-9\]\[0-9\]\[0-9\]" 2 "optimized" } } */