From patchwork Thu Oct 12 18:50:45 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 825017 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-464058-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="XGjZbmxN"; 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 3yCg0k2jztz9sNw for ; Fri, 13 Oct 2017 05:51:01 +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=nvkMxAbNk53tPL3RpCyVplaRtsSrgEBm12au8VzfvVhqZiUYxQN7g lJbi/yVrXVgUjRy68b+OsjYR//MkuzMpupKQn6JqmyYC1cytQMTjPxcQOmCUxbp+ 7cTmQWlVt8aG1emAxGzE4zG5bZMRa6GUgy7OX8fBw5DiNE8ivnHiRg= 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=QByDEj6dczcnAtxGiMObHhD/kOs=; b=XGjZbmxNfm/wGcLh1sFh h+D4ZFjYvNUDScSqVE+jgZtJhkDCNEJG6/XUlP5UPIojEVZLEQ5RiCAx7Vu88o3x piiXjpSYhDOVae2nxn3KvjB9R6oCgY80+QljNaAO0qMribSw0OFNCu4zw5bfkXUM 4U+lmZNDn3OF7eciD6FzSvY= Received: (qmail 118313 invoked by alias); 12 Oct 2017 18:50:52 -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 118250 invoked by uid 89); 12 Oct 2017 18:50:51 -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= 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; Thu, 12 Oct 2017 18:50:48 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id A145C54527C; Thu, 12 Oct 2017 20:50:45 +0200 (CEST) Date: Thu, 12 Oct 2017 20:50:45 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org Subject: Increase base of profile probabilities Message-ID: <20171012185045.GA98802@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) Hi, this patch makes profile probability use more precise representation and takes care of places where 32bit artithmetic will possibly overflow. This will make it possible to drop counts on edges next. Bootstrapped/regtested x86_64-linux, comitted. Honza * profile-count.c (safe_scale_64bit): Fix GCC4.x path. (profile_probability): Set max_probability to (uint32_t) 1 << (n_bits - 2) and update accessors to avoid overlfows in temporaries. * profile-count.c (profile_probability::differs_from_p): Do not rely on max_probaiblity == 10000 * gcc.dg/predict-13.c: Update template for probaility change. * gcc.dg/predict-8.c: Likewise. Index: profile-count.c =================================================================== --- profile-count.c (revision 253683) +++ profile-count.c (working copy) @@ -147,12 +147,12 @@ profile_probability::differs_from_p (pro { if (!initialized_p () || !other.initialized_p ()) return false; - if ((uint64_t)m_val - (uint64_t)other.m_val < 10 - || (uint64_t)other.m_val - (uint64_t)m_val < 10) + if ((uint64_t)m_val - (uint64_t)other.m_val < max_probability / 1000 + || (uint64_t)other.m_val - (uint64_t)max_probability < 1000) return false; if (!other.m_val) return true; - int64_t ratio = m_val * 100 / other.m_val; + int64_t ratio = (int64_t)m_val * 100 / other.m_val; return ratio < 99 || ratio > 101; } Index: profile-count.h =================================================================== --- profile-count.h (revision 253683) +++ profile-count.h (working copy) @@ -67,7 +67,10 @@ safe_scale_64bit (uint64_t a, uint64_t b if (a < ((uint64_t)1 << 31) && b < ((uint64_t)1 << 31) && c < ((uint64_t)1 << 31)) - return (a * b + (c / 2)) / c; + { + *res = (a * b + (c / 2)) / c; + return true; + } #endif return slow_safe_scale_64bit (a, b, c, res); } @@ -111,11 +114,10 @@ safe_scale_64bit (uint64_t a, uint64_t b class GTY((user)) profile_probability { - /* For now use values in range 0...REG_BR_PROB_BASE. Later we can use full - precision of 30 bits available. */ - static const int n_bits = 30; - static const uint32_t max_probability = REG_BR_PROB_BASE; + /* We can technically use ((uint32_t) 1 << (n_bits - 1)) - 2 but that + will lead to harder multiplication sequences. */ + static const uint32_t max_probability = (uint32_t) 1 << (n_bits - 2); static const uint32_t uninitialized_probability = ((uint32_t) 1 << (n_bits - 1)) - 1; @@ -210,14 +212,14 @@ public: { profile_probability ret; gcc_checking_assert (v >= 0 && v <= REG_BR_PROB_BASE); - ret.m_val = RDIV (v * max_probability, REG_BR_PROB_BASE); + ret.m_val = RDIV (v * (uint64_t) max_probability, REG_BR_PROB_BASE); ret.m_quality = profile_guessed; return ret; } int to_reg_br_prob_base () const { gcc_checking_assert (initialized_p ()); - return RDIV (m_val * REG_BR_PROB_BASE, max_probability); + return RDIV (m_val * (uint64_t) REG_BR_PROB_BASE, max_probability); } /* Conversion to and from RTL representation of profile probabilities. */ @@ -246,7 +248,12 @@ public: if (val1 > val2) ret.m_val = max_probability; else - ret.m_val = RDIV (val1 * max_probability, val2); + { + uint64_t tmp; + safe_scale_64bit (val1, max_probability, val2, &tmp); + gcc_checking_assert (tmp <= max_probability); + ret.m_val = tmp; + } ret.m_quality = profile_precise; return ret; } @@ -443,8 +450,9 @@ public: if (!initialized_p ()) return profile_probability::uninitialized (); profile_probability ret; - ret.m_val = MIN (RDIV (m_val * num, den), - max_probability); + uint64_t tmp; + safe_scale_64bit (m_val, num, den, &tmp); + ret.m_val = MIN (tmp, max_probability); ret.m_quality = MIN (m_quality, profile_adjusted); return ret; } @@ -482,7 +490,7 @@ public: if (m_val == uninitialized_probability) return m_quality == profile_guessed; else - return m_val <= REG_BR_PROB_BASE; + return m_val <= max_probability; } /* Comparsions are three-state and conservative. False is returned if @@ -781,8 +789,10 @@ public: if (!initialized_p ()) return profile_count::uninitialized (); profile_count ret; - ret.m_val = RDIV (m_val * prob.m_val, - profile_probability::max_probability); + uint64_t tmp; + safe_scale_64bit (m_val, prob.m_val, profile_probability::max_probability, + &tmp); + ret.m_val = tmp; ret.m_quality = MIN (m_quality, prob.m_quality); return ret; } @@ -794,11 +804,11 @@ public: if (!initialized_p ()) return profile_count::uninitialized (); profile_count ret; + uint64_t tmp; + gcc_checking_assert (num >= 0 && den > 0); - /* FIXME: shrink wrapping violates this sanity check. */ - gcc_checking_assert ((num <= REG_BR_PROB_BASE - || den <= REG_BR_PROB_BASE) || 1); - ret.m_val = RDIV (m_val * num, den); + safe_scale_64bit (m_val, num, den, &tmp); + ret.m_val = MIN (tmp, max_count); ret.m_quality = MIN (m_quality, profile_adjusted); return ret; } Index: testsuite/gcc.dg/predict-13.c =================================================================== --- testsuite/gcc.dg/predict-13.c (revision 253683) +++ testsuite/gcc.dg/predict-13.c (working copy) @@ -21,4 +21,4 @@ int main(int argc, char **argv) } /* { dg-final { scan-tree-dump-times "combined heuristics of edge\[^:\]*: 33.3%" 3 "profile_estimate"} } */ -/* { dg-final { scan-tree-dump-times "combined heuristics of edge\[^:\]*: 0.0%" 2 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "combined heuristics of edge\[^:\]*: 0.1%" 2 "profile_estimate"} } */ Index: testsuite/gcc.dg/predict-8.c =================================================================== --- testsuite/gcc.dg/predict-8.c (revision 253683) +++ testsuite/gcc.dg/predict-8.c (working copy) @@ -1,5 +1,5 @@ /* { dg-do compile { target { i?86-*-* x86_64-*-* } } } */ -/* { dg-options "-O2 -fdump-rtl-expand" } */ +/* { dg-options "-O2 -fdump-rtl-expand-details-blocks" } */ int foo(float a, float b) { if (a == b) @@ -8,4 +8,4 @@ int foo(float a, float b) { return 2; } -/* { dg-final { scan-rtl-dump-times "REG_BR_PROB 400 " 1 "expand"} } */ +/* { dg-final { scan-rtl-dump-times "99.0. .guessed" 1 "expand"} } */