From patchwork Sat May 28 20:01:09 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Monakov X-Patchwork-Id: 627449 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 3rHDKm2ZKXz9t43 for ; Sun, 29 May 2016 06:01:31 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=gtYv3SvD; 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:mime-version:content-type; q=dns; s=default; b=Heg1+Y4aqOhWB+dUZQJHsWGWZZDtqE2Xw5TKMnqXLLsxiEwYaE epwS/qwKbm1dszibAC1jFyEOwNbxok1f1UsOYoRabTSIypy9Zx5Pr9/Yunfc5mDS B8GWteOUuihJ08vlRAayHp+0l/ed+HXK0Eb5NkMmVGqDzt4cMaMFRO/vE= 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:mime-version:content-type; s= default; bh=LdMNm9R4MKPiLCionC/CIMKubno=; b=gtYv3SvDdpJX/igNMpS/ 0Np5FrEzJ+4OHjy4KEHD6cNfMTPbQciIYyMjuzJrD8+tN9clkLabb6qRFilGkbMu N4usPMsY7ZtCwV4sZ7mu/umyq4wMYBwlTUFwQYA8r5z+VpyRgIRcCE2rt6P8yjsF 1aucute4eJ8z4OlTBqpWZ/U= Received: (qmail 89920 invoked by alias); 28 May 2016 20:01:23 -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 89905 invoked by uid 89); 28 May 2016 20:01:23 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.5 required=5.0 tests=AWL, BAYES_00, KAM_LAZY_DOMAIN_SECURITY, RCVD_IN_DNSWL_NONE, RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=dgfinal, dg-final, dg-options, dgoptions X-HELO: smtp.ispras.ru Received: from smtp.ispras.ru (HELO smtp.ispras.ru) (83.149.199.79) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sat, 28 May 2016 20:01:12 +0000 Received: from [10.10.3.121] (unknown [83.149.199.91]) by smtp.ispras.ru (Postfix) with ESMTP id 0B9F5203FB; Sat, 28 May 2016 23:01:09 +0300 (MSK) Date: Sat, 28 May 2016 23:01:09 +0300 (MSK) From: Alexander Monakov To: gcc-patches@gcc.gnu.org cc: Marc Glisse Subject: [PATCH] match.pd: optimize unsigned mul overflow check Message-ID: User-Agent: Alpine 2.20 (LNX 67 2015-01-07) MIME-Version: 1.0 Hello, For unsigned A, B, 'A > -1 / B' is a nice predicate for checking whether 'A*B' overflows (or 'B && A > -1 / B' if B may be zero). Let's optimize it to an invocation of __builtin_mul_overflow to avoid the divide operation. The following patch implements that as a match.pd transformation. It looks like there's a similar thing going on for add/sub overflow check in tree-ssa-math-opts, but handling this in match.pd seems reasonable. (user code using the above test would probably also compute 'A*B' a few statements later; notably, today GCC cannot CSE plain 'A*B' to REALPART_EXPR of the builtin call on GIMPLE; on x86 it gets cleaned up on RTL) Thanks to Marc for helping get this in shape on the Bugzilla. Bootstrapped and regtested on x86_64, OK for trunk? gcc/ 2016-05-28 Alexander Monakov Marc Glisse PR tree-optimization/71289 * match.pd (-1 / B < A, A > -1 / B): New transformations. gcc/testsuite/ 2016-05-28 Alexander Monakov PR tree-optimization/71289 * gcc.dg/pr71289.c: New test. diff --git a/gcc/match.pd b/gcc/match.pd index 8d05e86..953c070 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -2657,6 +2657,25 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) && types_match (TREE_TYPE (@0), TREE_TYPE (@1))) (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); })))) +/* For unsigned operands, A > -1 / B checks whether A * B would overflow. + Simplify it to __builtin_mul_overflow (A, B, ). */ +/* -1 / B < A */ +(for cmp (lt ge) + out (ne eq) + (simplify + (cmp (trunc_div:s integer_all_onesp @1) @0) + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) && !VECTOR_TYPE_P (TREE_TYPE (@0))) + (with { tree t = TREE_TYPE (@0), cpx = build_complex_type (t); } + (out (imagpart (IFN_MUL_OVERFLOW:cpx @0 @1)) { build_zero_cst (t); }))))) + +/* A > -1 / B */ +(for cmp (gt le) + out (ne eq) + (simplify + (cmp @0 (trunc_div:s integer_all_onesp @1)) + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) && !VECTOR_TYPE_P (TREE_TYPE (@0))) + (with { tree t = TREE_TYPE (@0), cpx = build_complex_type (t); } + (out (imagpart (IFN_MUL_OVERFLOW:cpx @0 @1)) { build_zero_cst (t); }))))) /* Simplification of math builtins. These rules must all be optimizations as well as IL simplifications. If there is a possibility that the new diff --git a/gcc/testsuite/gcc.dg/pr71289.c b/gcc/testsuite/gcc.dg/pr71289.c new file mode 100644 index 0000000..39837b9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr71289.c @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-optimized-raw" } */ + +int f(unsigned a, unsigned b, unsigned *c) +{ + if (a > -1 / b) + return -1; + *c = a * b; + return 0; +} + +void g(unsigned long long a, unsigned long long b, unsigned long long *c) +{ + if (a <= -1 / b) + *c = a * b; +} + +/* { dg-final { scan-tree-dump-not "trunc_div_expr" "optimized" } } */