From patchwork Tue Oct 10 20:23:38 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 824047 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-463896-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="QIYOflsB"; 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 3yBT8l58WXz9t5Q for ; Wed, 11 Oct 2017 07:23:51 +1100 (AEDT) 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:subject:message-id:mime-version:content-type; q=dns; s= default; b=D3DHAjIQDpVbc4LwfESOuCxlJkNYUcYgisAeAEA5fGG8JtqqsAUfE WGg4QaStZ9hNkvKFilF2U79i8zZmbIhey6XU1nkadi4576m30BFrguHUgxUxXG8W 2xwJhLXmWm6DEsi0HHXGAa7vkkji4mB/XPxlwMOcEhhvhORV84YOAg= 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:subject:message-id:mime-version:content-type; s= default; bh=67bOdeQEcmp6VM0FGQcnospX9Dc=; b=QIYOflsBBGkbBFmN9W3L 6EkP5JKAToG5depCqLGHuOt/XeRnO+q2mx7sdhD7xX+e6mHdGNvCDOx6fhWq+EmZ rX3hzvuviCVcvL5CNBKcjS+3V7bfApSZzaqMusinP9oOFXPguTvhcwGz0ffRnIza g1DiUmGjw3LWikAtfvTj5mc= Received: (qmail 936 invoked by alias); 10 Oct 2017 20:23:44 -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 130882 invoked by uid 89); 10 Oct 2017 20:23:43 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-9.5 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, KAM_LAZY_DOMAIN_SECURITY, RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=probabilities, scaling, (unknown) X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 10 Oct 2017 20:23:41 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 33E7B54728A; Tue, 10 Oct 2017 22:23:38 +0200 (CEST) Date: Tue, 10 Oct 2017 22:23:38 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de Subject: [RFC] overflow safe scaling of 64bit values Message-ID: <20171010202338.GB31031@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) Hi, in order to drop frequencies from basic blocks and counts from edges I need to make probabilities more precise (so we do not get all those roundoff errors from 10000-base fixpoint arithmetics). Increasing base is easy now, but it means that in temporaries one can get overflows easily. I need to compute (a*b)/c in a overflow safe way when a*b does not necessarily need to fit into 64bit integer. The following implement safe_scale_64bit for it but I am not quite sure if that is most reasonable implementation. (it uses builtins to detect overflows, inline 64bit computation if it is safe and 128bit computation if it is not). Any ideas for better version? If not I will go ahead with this variant and increase profile probability base. Honza * profile-count.h (slow_safe_scale_64bit): New function. (safe_scale_64bit): New inline. (profile_count::max_safe_multiplier): Remove; use safe_scale_64bit. Index: profile-count.h =================================================================== --- profile-count.h (revision 253512) +++ profile-count.h (working copy) @@ -43,6 +43,35 @@ enum profile_quality { #define RDIV(X,Y) (((X) + (Y) / 2) / (Y)) +bool slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res); + +/* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */ + +inline bool +safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res) +{ +#if (GCC_VERSION >= 5000) + uint64_t tmp; + if (!__builtin_mul_overflow (a, b, &tmp) + && !__builtin_add_overflow (tmp, c/2, &tmp)) + { + *res = tmp / c; + return true; + } + if (c == 1) + { + *res = (uint64_t) -1; + return false; + } +#else + if (a < ((uint64_t)1 << 31) + && b < ((uint64_t)1 << 31) + && c < ((uint64_t)1 << 31)) + return (a * b + (c / 2)) / c; +#endif + return slow_safe_scale_64bit (a, b, c, res); +} + /* Data type to hold probabilities. It implements fixed point arithmetics with capping so probability is always in range [0,1] and scaling requiring values greater than 1 needs to be represented otherwise. @@ -87,7 +116,8 @@ class GTY((user)) profile_probability static const int n_bits = 30; static const uint32_t max_probability = REG_BR_PROB_BASE; - static const uint32_t uninitialized_probability = ((uint32_t) 1 << n_bits) - 1; + static const uint32_t uninitialized_probability + = ((uint32_t) 1 << (n_bits - 1)) - 1; uint32_t m_val : 30; enum profile_quality m_quality : 2; @@ -535,11 +565,6 @@ class GTY(()) profile_count uint64_t m_val : n_bits; enum profile_quality m_quality : 2; - - /* Assume numbers smaller than this to multiply. This is set to make - testsuite pass, in future we may implement precise multiplication in higer - rangers. */ - static const uint64_t max_safe_multiplier = 131072; public: /* Used for counters which are expected to be never executed. */ @@ -790,12 +815,9 @@ public: return *this; profile_count ret; - /* Take care for overflows! */ - if (num.m_val < max_safe_multiplier || m_val < max_safe_multiplier) - ret.m_val = RDIV (m_val * num.m_val, den.m_val); - else - ret.m_val = RDIV (m_val * RDIV (num.m_val * max_safe_multiplier, - den.m_val), max_safe_multiplier); + uint64_t val; + safe_scale_64bit (m_val, num.m_val, den.m_val, &val); + ret.m_val = MIN (val, max_count); ret.m_quality = MIN (m_quality, profile_adjusted); return ret; } Index: profile-count.c =================================================================== --- profile-count.c (revision 253512) +++ profile-count.c (working copy) @@ -30,6 +30,7 @@ along with GCC; see the file COPYING3. #include "gimple.h" #include "data-streamer.h" #include "cgraph.h" +#include "wide-int.h" /* Dump THIS to F. */ @@ -194,3 +195,21 @@ profile_probability::stream_out (struct streamer_write_uhwi_stream (ob, m_val); streamer_write_uhwi_stream (ob, m_quality); } + +/* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */ + +bool +slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res) +{ + FIXED_WIDE_INT (128) tmp = a; + bool overflow; + tmp = wi::udiv_floor (wi::umul (tmp, b, &overflow) + (c / 2), c); + gcc_checking_assert (!overflow); + if (wi::fits_uhwi_p (tmp)) + { + *res = tmp.to_uhwi (); + return true; + } + *res = (uint64_t) -1; + return false; +}