From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16]) by sourceware.org (Postfix) with ESMTPS id 1D83E3858D33 for ; Wed, 17 Jan 2024 13:20:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1D83E3858D33 Authentication-Results: sourceware.org; dmarc=fail (p=none dis=none) header.from=ucw.cz Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=kam.mff.cuni.cz ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 1D83E3858D33 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.113.20.16 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705497654; cv=none; b=RbqiMM8HWFCb7QSKbGMDbHl7EHNxZ2afNnQIyfQeT/eScHpvE5CfaS6FAYpwOxqtGLoLp1r0IFuv2hWiLRbcfxCCCPA3ieVqEZQ4vJ7JWZkZaudmbHnLjZRmiR7WTlbSg+nlgAbf2SNKHJLT9OSY7g76rUOPb1FSlArgI8tc61Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705497654; c=relaxed/simple; bh=tv/JCB1urtpW2bhMXNozo1raQdDqqOnghhPVngVn3L0=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:MIME-Version; b=DlURrHVho6/EVRIMneBiq8hRJmvNhBr410zQLizbqIGUFwejtf4YWAQwUXNHdFum0guLqyY85pQbzwCyVq4UWAvf66RslY5H6soHk83HJ9c34yq2n+9jgEIBGJ2yigdoWva1jmPCbzq1RTp9Y7hAQesX5jk86nCmb3VVkm29Dqw= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id E3266283B5C; Wed, 17 Jan 2024 14:20:49 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ucw.cz; s=gen1; t=1705497649; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=EPxO0XJV0orIPILuUhFZBVn4KrdjaXQ3ze2EPmx5QrQ=; b=SugUR/mzyrYmO6U0HJl0MsjsUapFG4g5ZVcLDiTDSAatRqbiIktLpyWXF5SIc2UAqpjmDL goSPL8Q96HlpIRJWqiJeVM48L0sdaVMoApKA5bByp9sPetnM1R7Y8duml55UUzWKJ6MBLO ZW5qm4MfUzvx491JQiRwug/XRWLbv54= Date: Wed, 17 Jan 2024 14:20:49 +0100 From: Jan Hubicka To: Jakub Jelinek Cc: gcc-patches@gcc.gnu.org Subject: Re: Fix merging of value predictors Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-Spam-Status: No, score=-10.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,GIT_PATCH_0,HEADER_FROM_DIFFERENT_DOMAINS,JMQ_SPF_NEUTRAL,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: > > Please fill in what has changed, both for predict-18.c and predict.{cc,def} > changes. Sorry, I re-generated the patch after fixing some typos and forgot to copy over the changelog. > > > @@ -2613,24 +2658,40 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, > > if (!nop1) > > nop1 = op1; > > } > > + /* We already checked if folding one of arguments to constant is good > > + enough. Consequently failing to fold both means that we will not > > + succeed determinging the value. */ > > s/determinging/determining/ Fixed. I am re-testing the following and will commit if it succeeds (on x86_64-linux) 2024-01-17 Jan Hubicka Jakub Jelinek PR tree-optimization/110852 gcc/ChangeLog: * predict.cc (expr_expected_value_1): Fix profile merging of PHI and binary operations (get_predictor_value): Handle PRED_COMBINED_VALUE_PREDICTIONS and PRED_COMBINED_VALUE_PREDICTIONS_PHI * predict.def (PRED_COMBINED_VALUE_PREDICTIONS): New predictor. (PRED_COMBINED_VALUE_PREDICTIONS_PHI): New predictor. gcc/testsuite/ChangeLog: * gcc.dg/predict-18.c: Update template to expect combined value predictor. * gcc.dg/predict-23.c: New test. * gcc.dg/tree-ssa/predict-1.c: New test. * gcc.dg/tree-ssa/predict-2.c: New test. * gcc.dg/tree-ssa/predict-3.c: New test. diff --git a/gcc/predict.cc b/gcc/predict.cc index 84cbe3ffc61..c1c48bf3df1 100644 --- a/gcc/predict.cc +++ b/gcc/predict.cc @@ -2404,44 +2404,78 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0))) return NULL; - if (gimple_code (def) == GIMPLE_PHI) + if (gphi *phi = dyn_cast (def)) { /* All the arguments of the PHI node must have the same constant length. */ - int i, n = gimple_phi_num_args (def); - tree val = NULL, new_val; + int i, n = gimple_phi_num_args (phi); + tree val = NULL; + bool has_nonzero_edge = false; + + /* If we already proved that given edge is unlikely, we do not need + to handle merging of the probabilities. */ + for (i = 0; i < n && !has_nonzero_edge; i++) + { + tree arg = PHI_ARG_DEF (phi, i); + if (arg == PHI_RESULT (phi)) + continue; + profile_count cnt = gimple_phi_arg_edge (phi, i)->count (); + if (!cnt.initialized_p () || cnt.nonzero_p ()) + has_nonzero_edge = true; + } for (i = 0; i < n; i++) { - tree arg = PHI_ARG_DEF (def, i); + tree arg = PHI_ARG_DEF (phi, i); enum br_predictor predictor2; - /* If this PHI has itself as an argument, we cannot - determine the string length of this argument. However, - if we can find an expected constant value for the other - PHI args then we can still be sure that this is - likely a constant. So be optimistic and just - continue with the next argument. */ - if (arg == PHI_RESULT (def)) + /* Skip self-referring parameters, since they does not change + expected value. */ + if (arg == PHI_RESULT (phi)) continue; + /* Skip edges which we already predicted as executing + zero times. */ + if (has_nonzero_edge) + { + profile_count cnt = gimple_phi_arg_edge (phi, i)->count (); + if (cnt.initialized_p () && !cnt.nonzero_p ()) + continue; + } HOST_WIDE_INT probability2; - new_val = expr_expected_value (arg, visited, &predictor2, - &probability2); + tree new_val = expr_expected_value (arg, visited, &predictor2, + &probability2); + /* If we know nothing about value, give up. */ + if (!new_val) + return NULL; - /* It is difficult to combine value predictors. Simply assume - that later predictor is weaker and take its prediction. */ - if (*predictor < predictor2) + /* If this is a first edge, trust its prediction. */ + if (!val) { + val = new_val; *predictor = predictor2; *probability = probability2; + continue; } - if (!new_val) - return NULL; - if (!val) - val = new_val; - else if (!operand_equal_p (val, new_val, false)) + /* If there are two different values, give up. */ + if (!operand_equal_p (val, new_val, false)) return NULL; + + int p1 = get_predictor_value (*predictor, *probability); + int p2 = get_predictor_value (predictor2, probability2); + /* If both predictors agree, it does not matter from which + edge we enter the basic block. */ + if (*predictor == predictor2 && p1 == p2) + continue; + /* The general case has no precise solution, since we do not + know probabilities of incomming edges, yet. + Still if value is predicted over all incomming edges, we + can hope it will be indeed the case. Conservatively + downgrade prediction quality (so first match merging is not + performed) and take least successful prediction. */ + + *predictor = PRED_COMBINED_VALUE_PREDICTIONS_PHI; + *probability = MIN (p1, p2); } return val; } @@ -2585,6 +2619,10 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree res; tree nop0 = op0; tree nop1 = op1; + + /* First handle situation where single op is enough to determine final + value. In this case we can do better job by avoiding the prediction + merging. */ if (TREE_CODE (op0) != INTEGER_CST) { /* See if expected value of op0 is good enough to determine the result. */ @@ -2592,12 +2630,18 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, if (nop0 && (res = fold_build2 (code, type, nop0, op1)) != NULL && TREE_CODE (res) == INTEGER_CST) + /* We are now getting conservative probability. Consider for + example: + op0 * op1 + If op0 is 0 with probability p, then we will ignore the + posibility that op0 != 0 and op1 == 0. It does not seem to be + worthwhile to downgrade prediciton quality for this. */ return res; if (!nop0) nop0 = op0; } - enum br_predictor predictor2; - HOST_WIDE_INT probability2; + enum br_predictor predictor2 = PRED_UNCONDITIONAL; + HOST_WIDE_INT probability2 = -1; if (TREE_CODE (op1) != INTEGER_CST) { /* See if expected value of op1 is good enough to determine the result. */ @@ -2606,6 +2650,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, && (res = fold_build2 (code, type, op0, nop1)) != NULL && TREE_CODE (res) == INTEGER_CST) { + /* Similarly as above we now get conservative probability. */ *predictor = predictor2; *probability = probability2; return res; @@ -2613,24 +2658,40 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, if (!nop1) nop1 = op1; } + /* We already checked if folding one of arguments to constant is good + enough. Consequently failing to fold both means that we will not + succeed determining the value. */ if (nop0 == op0 || nop1 == op1) return NULL; /* Finally see if we have two known values. */ res = fold_build2 (code, type, nop0, nop1); - if (TREE_CODE (res) == INTEGER_CST - && TREE_CODE (nop0) == INTEGER_CST - && TREE_CODE (nop1) == INTEGER_CST) + if (TREE_CODE (res) == INTEGER_CST) { - /* Combine binary predictions. */ - if (*probability != -1 || probability2 != -1) + HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability); + HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2); + + /* If one of predictions is sure, such as PRED_UNCONDITIONAL, we + can ignore it. */ + if (p2 == PROB_ALWAYS) + return res; + if (p1 == PROB_ALWAYS) { - HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability); - HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2); - *probability = RDIV (p1 * p2, REG_BR_PROB_BASE); + *predictor = predictor2; + *probability = probability2; + return res; } - - if (predictor2 < *predictor) - *predictor = predictor2; + /* Combine binary predictions. + Since we do not know about independence of predictors, we + can not determine value precisely. */ + *probability = RDIV (p1 * p2, REG_BR_PROB_BASE); + /* If we no longer track useful information, give up. */ + if (!*probability) + return NULL; + /* Otherwise mark that prediction is a result of combining + different heuristics, since we do not want it to participate + in first match merging. It is no longer reliable since + we do not know if the probabilities are indpenendet. */ + *predictor = PRED_COMBINED_VALUE_PREDICTIONS; return res; } @@ -2690,6 +2751,8 @@ get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability) { case PRED_BUILTIN_EXPECT: case PRED_BUILTIN_EXPECT_WITH_PROBABILITY: + case PRED_COMBINED_VALUE_PREDICTIONS_PHI: + case PRED_COMBINED_VALUE_PREDICTIONS: gcc_assert (probability != -1); return probability; default: diff --git a/gcc/predict.def b/gcc/predict.def index 10cd73a9026..0b567842361 100644 --- a/gcc/predict.def +++ b/gcc/predict.def @@ -94,6 +94,16 @@ DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations", DEF_PREDICTOR (PRED_LOOP_ITERATIONS_MAX, "guessed loop iterations", PROB_UNINITIALIZED, PRED_FLAG_FIRST_MATCH) +/* Prediction which is an outcome of combining multiple value predictions. */ +DEF_PREDICTOR (PRED_COMBINED_VALUE_PREDICTIONS, + "combined value predictions", PROB_UNINITIALIZED, 0) + +/* Prediction which is an outcome of combining multiple value predictions + on PHI statement (this is less accurate since we do not know reverse + edge probabilities at that time). */ +DEF_PREDICTOR (PRED_COMBINED_VALUE_PREDICTIONS_PHI, + "combined value predictions", PROB_UNINITIALIZED, 0) + /* Branch containing goto is probably not taken. */ DEF_PREDICTOR (PRED_CONTINUE, "continue", HITRATE (67), 0) diff --git a/gcc/testsuite/gcc.dg/predict-18.c b/gcc/testsuite/gcc.dg/predict-18.c index 073e742d849..718eaf33c39 100644 --- a/gcc/testsuite/gcc.dg/predict-18.c +++ b/gcc/testsuite/gcc.dg/predict-18.c @@ -33,9 +33,9 @@ void foo (int a, int b) global++; } -/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 54.00%" "profile_estimate"} } */ +/* { dg-final { scan-tree-dump "combined value predictions heuristics of edge .*->.*: 54.00%" "profile_estimate"} } */ /* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 77.70%" "profile_estimate"} } */ -/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 98.96%" "profile_estimate"} } */ -/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 71.99%" "profile_estimate"} } */ +/* { dg-final { scan-tree-dump "combined value predictions heuristics of edge .*->.*: 98.96%" "profile_estimate"} } */ +/* { dg-final { scan-tree-dump "combined value predictions heuristics of edge .*->.*: 71.99%" "profile_estimate"} } */ /* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 40.00%" "profile_estimate"} } */ /* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 35.01%" "profile_estimate"} } */ diff --git a/gcc/testsuite/gcc.dg/predict-23.c b/gcc/testsuite/gcc.dg/predict-23.c new file mode 100644 index 00000000000..7700bb34a07 --- /dev/null +++ b/gcc/testsuite/gcc.dg/predict-23.c @@ -0,0 +1,11 @@ +/* PR tree-optimization/110852 */ +/* { dg-options "-O1 -fno-tree-fre" } */ + +unsigned i, j; + +unsigned +foo (void) +{ + unsigned u = __builtin_expect (i, 0); + return 4 - (u < (j || i)); +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/predict-1.c b/gcc/testsuite/gcc.dg/tree-ssa/predict-1.c new file mode 100644 index 00000000000..1824643d75d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/predict-1.c @@ -0,0 +1,10 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ +int test2(); +int +test (int a, int b) +{ + if (__builtin_expect_with_probability (a, 0, 0.4)/__builtin_expect_with_probability (b, 5, 0.2)) + test2(); +} +/* { dg-final { scan-tree-dump-times "first match heuristics: 60.00" 1 "profile_estimate"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/predict-2.c b/gcc/testsuite/gcc.dg/tree-ssa/predict-2.c new file mode 100644 index 00000000000..80c84f1b235 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/predict-2.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ +int test2(); +int +test (int a, int b) +{ + if (__builtin_expect_with_probability (a, 0, 0.8)+__builtin_expect_with_probability (b, 5, 0.9) == 5) + test2(); +} +/* Combining two predictions together can not be done precisely, so check that result is DS theory. */ +/* { dg-final { scan-tree-dump-times "combined value predictions heuristics of edge .->.: 72.00" 1 "profile_estimate"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/predict-3.c b/gcc/testsuite/gcc.dg/tree-ssa/predict-3.c new file mode 100644 index 00000000000..9da58861854 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/predict-3.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ +int test2(); +int +test (int p, int a, int b, int c) +{ + int d; + if (p) + d = __builtin_expect_with_probability (a, 0, 0.8) * b; + else + d = __builtin_expect_with_probability (a, 0, 0.8) * c; + if (d) + test2(); +} +/* { dg-final { scan-tree-dump-times "first match heuristics: 20.00" 1 "profile_estimate"} } */