From patchwork Tue May 31 15:29:53 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Martin_Li=C5=A1ka?= X-Patchwork-Id: 629204 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 3rL5MD1mqzz9t7v for ; Thu, 2 Jun 2016 21:57:44 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=MWYgTLq/; 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 :resent-from:resent-to:resent-date:resent-message-id:message-id :in-reply-to:references:from:date:subject:to:cc; q=dns; s= default; b=WCe5u9Qcs0zwDK0ms6iwNlDuavzv+A3mxzewJSDmSudAwqwv6wYsa cg4HmmU+BJUwwVA/r4dwYOT6yS2aA0qHKuWGgYFj/0hz2FXpgziM4+QwlmuinzAp p+WWIdZb6o5f0va7X/UCDYg1lE37bqxeM2o1Z3XSf7wnMVsFDOdUbI= 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 :resent-from:resent-to:resent-date:resent-message-id:message-id :in-reply-to:references:from:date:subject:to:cc; s=default; bh=r v0Nhm70sjEJOFSbELR+d+gXBPM=; b=MWYgTLq/xHtE2lnRStJkX2uJ2SeI7ucWu xXz3RDFULLOLqfoQShy3vzehDWBCrYUZRYqwGbaxfPFKbhfeG4Q3ARdMl4Q1AQ9L yrQT+Lvy1YnUkA3022VUItQkw+CNN699km6AYC4HHH/CWStTJvtSX56mb+KN9sSR 0s49uU8wK8= Received: (qmail 84497 invoked by alias); 2 Jun 2016 11:57: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 83804 invoked by uid 89); 2 Jun 2016 11:57:21 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00, SPF_PASS autolearn=ham version=3.3.2 spammy=predict, 1-1, Cover X-HELO: mx2.suse.de Received: from mx2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Thu, 02 Jun 2016 11:57:00 +0000 Received: from relay2.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 9C3D5ACAE for ; Thu, 2 Jun 2016 11:56:57 +0000 (UTC) Resent-From: =?UTF-8?Q?Martin_Li=c5=a1ka?= Resent-To: GCC Patches Resent-Date: Thu, 2 Jun 2016 13:56:57 +0200 Resent-Message-ID: <33ce2a10-0f2a-b622-fbb8-3af66490863c@suse.cz> Resent-User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.1.0 Message-Id: <538d1a7d03b247eb05e2fb15761298a7082bd9c3.1464868111.git.mliska@suse.cz> In-Reply-To: References: From: marxin Date: Tue, 31 May 2016 17:29:53 +0200 Subject: [PATCH 2/2] Add edge predictions pruning To: gcc-patches@gcc.gnu.org Cc: hubicka@ucw.cz X-IsSubscribed: yes contrib/ChangeLog: 2016-06-01 Martin Liska * analyze_brprob.py: Cover new dump output format. gcc/ChangeLog: 2016-06-01 Martin Liska * predict.c (dump_prediction): Add new argument. (enum predictor_reason): New enum. (struct predictor_hash): New struct. (predictor_hash::hash): New function. (predictor_hash::equal): Likewise. (not_removed_prediction_p): New function. (prune_predictions_for_bb): Likewise. (combine_predictions_for_bb): Prune predictions. gcc/testsuite/ChangeLog: 2016-06-02 Martin Liska * g++.dg/predict-loop-exit-1.C: Cover new dump format. * g++.dg/predict-loop-exit-2.C: Likewise. * g++.dg/predict-loop-exit-3.C: Likewise. * gcc.dg/predict-1.c: Likewise. * gcc.dg/predict-3.c: Likewise. * gcc.dg/predict-4.c: Likewise. * gcc.dg/predict-5.c: Likewise. * gcc.dg/predict-6.c: Likewise. --- contrib/analyze_brprob.py | 10 +- gcc/predict.c | 171 ++++++++++++++++++++++++++--- gcc/testsuite/g++.dg/predict-loop-exit-1.C | 4 +- gcc/testsuite/g++.dg/predict-loop-exit-2.C | 4 +- gcc/testsuite/g++.dg/predict-loop-exit-3.C | 4 +- gcc/testsuite/gcc.dg/predict-1.c | 2 +- gcc/testsuite/gcc.dg/predict-3.c | 2 +- gcc/testsuite/gcc.dg/predict-4.c | 2 +- gcc/testsuite/gcc.dg/predict-5.c | 2 +- gcc/testsuite/gcc.dg/predict-6.c | 2 +- 10 files changed, 171 insertions(+), 32 deletions(-) diff --git a/contrib/analyze_brprob.py b/contrib/analyze_brprob.py index 36371ff..9416eed 100755 --- a/contrib/analyze_brprob.py +++ b/contrib/analyze_brprob.py @@ -122,14 +122,14 @@ if len(sys.argv) != 2: exit(1) profile = Profile(sys.argv[1]) -r = re.compile(' (.*) heuristics: (.*)%.*exec ([0-9]*) hit ([0-9]*)') +r = re.compile(' (.*) heuristics( of edge [0-9]*->[0-9]*)?( \\(.*\\))?: (.*)%.*exec ([0-9]*) hit ([0-9]*)') for l in open(profile.filename).readlines(): m = r.match(l) - if m != None: + if m != None and m.group(3) == None: name = m.group(1) - prediction = float(m.group(2)) - count = int(m.group(3)) - hits = int(m.group(4)) + prediction = float(m.group(4)) + count = int(m.group(5)) + hits = int(m.group(6)) profile.add(name, prediction, count, hits) diff --git a/gcc/predict.c b/gcc/predict.c index 51a9993..dab97ad 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -55,13 +55,25 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-loop.h" #include "tree-scalar-evolution.h" +enum predictor_reason +{ + NONE, + IGNORED, + SINGLE_EDGE_DUPLICATE, + EDGE_PAIR_DUPLICATE +}; + +static const char *reason_messages[] = {"", " (ignored)", + " (single edge duplicate)", " (edge pair duplicate)"}; + /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */ static sreal real_almost_one, real_br_prob_base, real_inv_br_prob_base, real_one_half, real_bb_freq_max; static void combine_predictions_for_insn (rtx_insn *, basic_block); -static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int); +static void dump_prediction (FILE *, enum br_predictor, int, basic_block, + enum predictor_reason, edge); static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction); static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction); static bool can_predict_insn_p (const rtx_insn *); @@ -724,7 +736,8 @@ invert_br_probabilities (rtx insn) static void dump_prediction (FILE *file, enum br_predictor predictor, int probability, - basic_block bb, int used) + basic_block bb, enum predictor_reason reason = NONE, + edge ep_edge = NULL) { edge e; edge_iterator ei; @@ -736,9 +749,17 @@ dump_prediction (FILE *file, enum br_predictor predictor, int probability, if (! (e->flags & EDGE_FALLTHRU)) break; - fprintf (file, " %s heuristics%s: %.1f%%", + char edge_info_str[128]; + if (ep_edge) + sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index, + ep_edge->dest->index); + else + edge_info_str[0] = '\0'; + + fprintf (file, " %s heuristics%s%s: %.1f%%", predictor_info[predictor].name, - used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE); + edge_info_str, reason_messages[reason], + probability * 100.0 / REG_BR_PROB_BASE); if (bb->count) { @@ -835,18 +856,18 @@ combine_predictions_for_insn (rtx_insn *insn, basic_block bb) if (!found) dump_prediction (dump_file, PRED_NO_PREDICTION, - combined_probability, bb, true); + combined_probability, bb); else { dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, - bb, !first_match); + bb, !first_match ? NONE : IGNORED); dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, - bb, first_match); + bb, first_match ? NONE: IGNORED); } if (first_match) combined_probability = best_probability; - dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true); + dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb); while (*pnote) { @@ -857,7 +878,8 @@ combine_predictions_for_insn (rtx_insn *insn, basic_block bb) int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1)); dump_prediction (dump_file, predictor, probability, bb, - !first_match || best_predictor == predictor); + (!first_match || best_predictor == predictor) + ? NONE : IGNORED); *pnote = XEXP (*pnote, 1); } else @@ -888,6 +910,121 @@ combine_predictions_for_insn (rtx_insn *insn, basic_block bb) single_succ_edge (bb)->probability = REG_BR_PROB_BASE; } +/* Edge prediction hash traits. */ + +struct predictor_hash: pointer_hash +{ + + static inline hashval_t hash (const edge_prediction *); + static inline bool equal (const edge_prediction *, const edge_prediction *); +}; + +/* Calculate hash value of an edge prediction P based on predictor and + normalized probability. */ + +inline hashval_t +predictor_hash::hash (const edge_prediction *p) +{ + inchash::hash hstate; + hstate.add_int (p->ep_predictor); + + int prob = p->ep_probability; + if (prob > REG_BR_PROB_BASE / 2) + prob = REG_BR_PROB_BASE - prob; + + hstate.add_int (prob); + + return hstate.end (); +} + +/* Return true whether edge predictions P1 and P2 use the same predictor and + have equal (or opposed probability). */ + +inline bool +predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2) +{ + return (p1->ep_predictor == p2->ep_predictor + && (p1->ep_probability == p2->ep_probability + || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability)); +} + +struct predictor_hash_traits: predictor_hash, + typed_noop_remove {}; + +/* Return true if edge prediction P is not in DATA hash set. */ + +static bool +not_removed_prediction_p (edge_prediction *p, void *data) +{ + hash_set *remove = (hash_set *) data; + return !remove->contains (p); +} + +/* Prune predictions for a basic block BB. Currently we do following + clean-up steps: + + 1) remove duplicate prediction that is guessed with the same probability + (different than 1/2) to both edge + 2) remove duplicates for a prediction that belongs with the same probability + to a single edge + + */ + +static void +prune_predictions_for_bb (basic_block bb) +{ + edge_prediction **preds = bb_predictions->get (bb); + + if (preds) + { + hash_table s (13); + hash_set remove; + + /* Step 1: identify predictors that should be removed. */ + for (edge_prediction *pred = *preds; pred; pred = pred->ep_next) + { + edge_prediction *existing = s.find (pred); + if (existing) + { + if (pred->ep_edge == existing->ep_edge + && pred->ep_probability == existing->ep_probability) + { + /* Remove a duplicate predictor. */ + dump_prediction (dump_file, pred->ep_predictor, + pred->ep_probability, bb, + SINGLE_EDGE_DUPLICATE, pred->ep_edge); + + remove.add (pred); + } + else if (pred->ep_edge != existing->ep_edge + && pred->ep_probability == existing->ep_probability + && pred->ep_probability != REG_BR_PROB_BASE / 2) + { + /* Remove both predictors as they predict the same + for both edges. */ + dump_prediction (dump_file, existing->ep_predictor, + pred->ep_probability, bb, + EDGE_PAIR_DUPLICATE, + existing->ep_edge); + dump_prediction (dump_file, pred->ep_predictor, + pred->ep_probability, bb, + EDGE_PAIR_DUPLICATE, + pred->ep_edge); + + remove.add (existing); + remove.add (pred); + } + } + + edge_prediction **slot2 = s.find_slot (pred, INSERT); + *slot2 = pred; + } + + /* Step 2: Remove predictors. */ + filter_predictions (preds, not_removed_prediction_p, &remove); + } +} + /* Combine predictions into single probability and store them into CFG. Remove now useless prediction entries. If DRY_RUN is set, only produce dumps and do not modify profile. */ @@ -936,7 +1073,10 @@ combine_predictions_for_bb (basic_block bb, bool dry_run) if (dump_file) fprintf (dump_file, "Predictions for bb %i\n", bb->index); + prune_predictions_for_bb (bb); + edge_prediction **preds = bb_predictions->get (bb); + if (preds) { /* We implement "first match" heuristics and use probability guessed @@ -1002,18 +1142,18 @@ combine_predictions_for_bb (basic_block bb, bool dry_run) first_match = true; if (!found) - dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true); + dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb); else { dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb, - !first_match); + !first_match ? NONE : IGNORED); dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb, - first_match); + first_match ? NONE : IGNORED); } if (first_match) combined_probability = best_probability; - dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true); + dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb); if (preds) { @@ -1022,10 +1162,9 @@ combine_predictions_for_bb (basic_block bb, bool dry_run) enum br_predictor predictor = pred->ep_predictor; int probability = pred->ep_probability; - if (pred->ep_edge != EDGE_SUCC (bb, 0)) - probability = REG_BR_PROB_BASE - probability; dump_prediction (dump_file, predictor, probability, bb, - !first_match || best_predictor == predictor); + (!first_match || best_predictor == predictor) + ? NONE : IGNORED, pred->ep_edge); } } clear_bb_predictions (bb); diff --git a/gcc/testsuite/g++.dg/predict-loop-exit-1.C b/gcc/testsuite/g++.dg/predict-loop-exit-1.C index 357397f..88262eb 100644 --- a/gcc/testsuite/g++.dg/predict-loop-exit-1.C +++ b/gcc/testsuite/g++.dg/predict-loop-exit-1.C @@ -9,5 +9,5 @@ void test() { return; } -/* { dg-final { scan-tree-dump-times "extra loop exit heuristics:" 2 "profile_estimate"} } */ -/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 3 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "extra loop exit heuristics of edge\[^:\]*:" 2 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "loop exit heuristics of edge\[^:\]*:" 3 "profile_estimate"} } */ diff --git a/gcc/testsuite/g++.dg/predict-loop-exit-2.C b/gcc/testsuite/g++.dg/predict-loop-exit-2.C index 172fab1..15e9866 100644 --- a/gcc/testsuite/g++.dg/predict-loop-exit-2.C +++ b/gcc/testsuite/g++.dg/predict-loop-exit-2.C @@ -9,5 +9,5 @@ void test() { return; } -/* { dg-final { scan-tree-dump-times "extra loop exit heuristics:" 1 "profile_estimate"} } */ -/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 2 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "extra loop exit heuristics of edge\[^:\]*:" 1 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "loop exit heuristics of edge\[^:\]*:" 2 "profile_estimate"} } */ diff --git a/gcc/testsuite/g++.dg/predict-loop-exit-3.C b/gcc/testsuite/g++.dg/predict-loop-exit-3.C index e6ceec8..61af84b 100644 --- a/gcc/testsuite/g++.dg/predict-loop-exit-3.C +++ b/gcc/testsuite/g++.dg/predict-loop-exit-3.C @@ -9,5 +9,5 @@ void test() { return; } -/* { dg-final { scan-tree-dump-times "extra loop exit heuristics:" 2 "profile_estimate"} } */ -/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 3 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "extra loop exit heuristics of edge\[^:\]*:" 2 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "loop exit heuristics of edge\[^:\]*:" 3 "profile_estimate"} } */ diff --git a/gcc/testsuite/gcc.dg/predict-1.c b/gcc/testsuite/gcc.dg/predict-1.c index a2a0604..852ccb1 100644 --- a/gcc/testsuite/gcc.dg/predict-1.c +++ b/gcc/testsuite/gcc.dg/predict-1.c @@ -23,4 +23,4 @@ void foo (int bound) } } -/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 5 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics of edge\[^:\]*: 0.0%" 5 "profile_estimate"} } */ diff --git a/gcc/testsuite/gcc.dg/predict-3.c b/gcc/testsuite/gcc.dg/predict-3.c index e1be7cc..d41a4ac 100644 --- a/gcc/testsuite/gcc.dg/predict-3.c +++ b/gcc/testsuite/gcc.dg/predict-3.c @@ -25,4 +25,4 @@ void foo (int bound) } } -/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 3 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics of edge\[^:\]*: 100.0%" 3 "profile_estimate"} } */ diff --git a/gcc/testsuite/gcc.dg/predict-4.c b/gcc/testsuite/gcc.dg/predict-4.c index 3e7fb74..5779da3 100644 --- a/gcc/testsuite/gcc.dg/predict-4.c +++ b/gcc/testsuite/gcc.dg/predict-4.c @@ -15,4 +15,4 @@ void foo (int bound) } } -/* { dg-final { scan-tree-dump "loop iv compare heuristics: 50.0%" "profile_estimate"} } */ +/* { dg-final { scan-tree-dump "loop iv compare heuristics of edge\[^:\]*: 50.0%" "profile_estimate"} } */ diff --git a/gcc/testsuite/gcc.dg/predict-5.c b/gcc/testsuite/gcc.dg/predict-5.c index 3e7cc6f..d9bc27e 100644 --- a/gcc/testsuite/gcc.dg/predict-5.c +++ b/gcc/testsuite/gcc.dg/predict-5.c @@ -21,4 +21,4 @@ void foo (int base, int bound) } } -/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics of edge\[^:\]*: 100.0%" 4 "profile_estimate"} } */ diff --git a/gcc/testsuite/gcc.dg/predict-6.c b/gcc/testsuite/gcc.dg/predict-6.c index cda30e2..608eb7b 100644 --- a/gcc/testsuite/gcc.dg/predict-6.c +++ b/gcc/testsuite/gcc.dg/predict-6.c @@ -21,4 +21,4 @@ void foo (int base, int bound) } } -/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 4 "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics of edge\[^:\]*: 0.0%" 4 "profile_estimate"} } */