From patchwork Wed Jan 17 12:45:18 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 188821 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7300:42cf:b0:101:a8e8:374 with SMTP id q15csp882031dye; Wed, 17 Jan 2024 04:46:20 -0800 (PST) X-Google-Smtp-Source: AGHT+IF95yac76KzButL9GIWXDuWxlzBXsixe053DRgq005EhrpjI5bPbamoN39Ap6IhV8MN1CMp X-Received: by 2002:a05:620a:10b3:b0:783:4308:b41f with SMTP id h19-20020a05620a10b300b007834308b41fmr8334177qkk.122.1705495579863; Wed, 17 Jan 2024 04:46:19 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1705495579; cv=pass; d=google.com; s=arc-20160816; b=fNkk+bDJpMBBnLm4W22W7Lp1n0O2A3Iadj0qZ1aC9Rs0po+CMA2DCAagvWuTsbcrCd J2EPLvMQnNJVbXo8jPyxYHZ6F5/UG4Rf+ot6Anc5W1VUrjcIU+w0wLNmuHNBpC/PKlf1 k+jx/2O7+2F3+es3pAPOIu2DQOod+YDKxkuJsXJ/sETEwNemYb2gMLoCfWgk9GctT8IV ReoOsryOMgNfhzSixq3Bfy3PyTnrgF+5eJwgA7mO+eNPNiw/3ubTp804pgU6U5mlV01i b0vw5acTX+YKfvnKB+uyFUKNWDPKsHrsxgRdTGZD24ys1W+5d4GNPv7tWFCwL9VZYuoz RVRg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-disposition :mime-version:message-id:subject:to:from:date:dkim-signature :arc-filter:dmarc-filter:delivered-to; bh=59UIBok1AiDECzob4eQ6D8tN9aUSQDbUb7R8jJ6ymHU=; fh=+j3J1HHpdUv2+eUvkMKwDGvBISkQJs7/IFA38c9ZRbY=; b=yBI5iK3pSOdJvm3gkNQDnWXILnvK9UDTJELfLXn3r9ZY6xlCERfCYnctU/REW9pOPm dMAUtfG0JY22sYdqiJ2WWY6adaTUlzwYJvjVHNcrTWCG2ZgzVzfyZhki0ojkHGn2ur6D zcc0O2co6hCPCraylvCxJdmGV7Ps5lmdqTQ/7NTjhZJ1GoBv9ZzCt/aYzjWUlwhbu3tK nTUp+N5bRiSgL4EVQEFkiz5TvEYdCBLI+G3uLO8UcPUZMsuadRgtAXau0qGoxs37xhmN D3obONdjcRwP5BOrHgQnncB4iK3D0OD6M2DgvLDhYu6/l3xl0mozkh3nzh6uQlvhRQuw 2cIw== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@ucw.cz header.s=gen1 header.b="Uv+F1/cv"; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=ucw.cz Received: from server2.sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id v16-20020a05620a0f1000b0078310243965si12619892qkl.256.2024.01.17.04.46.19 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 17 Jan 2024 04:46:19 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@ucw.cz header.s=gen1 header.b="Uv+F1/cv"; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=ucw.cz Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8D347385841C for ; Wed, 17 Jan 2024 12:46:19 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16]) by sourceware.org (Postfix) with ESMTPS id 58586385840F for ; Wed, 17 Jan 2024 12:45:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 58586385840F 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 58586385840F 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=1705495523; cv=none; b=rBTvYP3iH/y9qgU1zjnojAJkBlhAwqEEub6bRSetKNA2+YOjd4Qs1yxqrd4SZaSxXml/QYkh6p01+UDhPPX2TBWMQgGzSfC/UgHkI14fpNSJU0vUDY6g9z8qrc+1FGHm5wmrnXwDf0gYGAoYJ7ymBMH+EsN/JTXk5LomMRtTCY8= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705495523; c=relaxed/simple; bh=0DfFfZsJJvIjAaCg6mMyqykRE02DViX/ThpnZO44Cdw=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:MIME-Version; b=VkoiM62+WaTZ/u5ZtRuDzxec+twII4/B9uS8+Cc64x7ti1PQH1Lc0mjPraAD9QfMEwqCgaILbfL4uMcwy8KicDfSBZprIMljQ9v0q8L//E7nEkgGsk3oQ3PgPqHpgKasC7nHs/xUVPItgDUaJ9B97/xPNntfwAUP7ovj+q227k0= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id A5D21283B52; Wed, 17 Jan 2024 13:45:18 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ucw.cz; s=gen1; t=1705495518; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type; bh=59UIBok1AiDECzob4eQ6D8tN9aUSQDbUb7R8jJ6ymHU=; b=Uv+F1/cvdfVoB+dYrm3yqWjr6K7evBvyRFm/zGn7yoL1rZeg4D4pmWuNE6zy9UjyxtMzsT JYTC11rzajZXdAEQvFx6fzQaNb/RL4C6iz6k4KGzzcwupuTGVqrffVFZh4Z61JWGwZUcl4 F9wrzgY/FSSvIIwmd/bCZdRtrKBTjzE= Date: Wed, 17 Jan 2024 13:45:18 +0100 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, jakub@redhat.com Subject: Fix merging of value predictors Message-ID: MIME-Version: 1.0 Content-Disposition: inline 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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1788341733386143084 X-GMAIL-MSGID: 1788341733386143084 Hi, expr_expected_value is doing some guesswork when it is merging two or more independent value predictions either in PHI node or in binary operation. Since we do not know how the predictions interact with each other, we can not really merge the values precisely. The previous logic merged the prediciton and picked the later predictor (since predict.def is sorted by reliability). This however leads to troubles with __builtin_expect_with_probability since it is special cased as a predictor with custom probabilities. If this predictor is downgraded to something else, we ICE since we have prediction given by predictor that is not expected to have customprobability. This patch fixies it by inventing new predictors PRED_COMBINED_VALUE_PREDICTIONS and PRED_COMBINED_VALUE_PREDICTIONS_PHI which also allows custom values but are considered less reliable then __builtin_expect_with_probability (they are combined by ds theory rather then by first match). This is less likely going to lead to very stupid decisions if combining does not work as expected. I also updated the code to be bit more careful about merging values and do not downgrade the precision when unnecesary (as tested by new testcases). Bootstrapped/regtested x86_64-linux, will commit it tomorrow if there are no complains. 2024-01-17 Jan Hubicka Jakub Jelinek PR tree-optimization/110852 gcc/ChangeLog: * predict.cc (expr_expected_value_1): (get_predictor_value): * predict.def (PRED_COMBINED_VALUE_PREDICTIONS): (PRED_COMBINED_VALUE_PREDICTIONS_PHI): gcc/testsuite/ChangeLog: * gcc.dg/predict-18.c: * 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..f9d73c5eb1a 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 determinging 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"} } */