From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id A67B43857B92; Thu, 4 Jan 2024 16:06:35 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A67B43857B92 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1704384395; bh=4vfhH0p0pepDx+71GX9DLJH9WsNmxKwLWw6Rv76jyCM=; h=From:To:Subject:Date:In-Reply-To:References:From; b=N08SUmwXsiOcH3RZWbh9qCoxclmONSYqlk/OwnxaLHpoX2cKwk0ZCdDZ1NMQW9Vef d/3WUQppWjngNfrB0A06A552hftGNXcu8mKwvUBE2M0cw4TZhkljMEMgX1hCX1BMY5 twDlD6dsWBR+3WFhyIv/z/W2ARCkwAoLqLyUkspo= From: "hubicka at ucw dot cz" To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/110852] [14 Regression] ICE: in get_predictor_value, at predict.cc:2695 with -O -fno-tree-fre and __builtin_expect() since r14-2219-geab57b825bcc35 Date: Thu, 04 Jan 2024 16:06:33 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: tree-optimization X-Bugzilla-Version: 14.0 X-Bugzilla-Keywords: ice-on-valid-code X-Bugzilla-Severity: normal X-Bugzilla-Who: hubicka at ucw dot cz X-Bugzilla-Status: NEW X-Bugzilla-Resolution: X-Bugzilla-Priority: P1 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: 14.0 X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 List-Id: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D110852 --- Comment #9 from Jan Hubicka --- > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D110852 >=20 > --- Comment #7 from Jakub Jelinek --- > So, what about following patch (which also fixes the ICE, would of course= need > to add the testcase) and doesn't regress any predict-*.c tests)? >=20 > --- gcc/predict.cc.jj 2024-01-03 11:51:32.000000000 +0100 > +++ gcc/predict.cc 2024-01-04 16:28:55.041507010 +0100 > @@ -2583,44 +2583,36 @@ expr_expected_value_1 (tree type, tree o > if (get_gimple_rhs_class (code) =3D=3D GIMPLE_BINARY_RHS) > { > tree res; > - tree nop0 =3D op0; > - tree nop1 =3D op1; > - if (TREE_CODE (op0) !=3D INTEGER_CST) > - { > - /* See if expected value of op0 is good enough to determine the > result. */ > - nop0 =3D expr_expected_value (op0, visited, predictor, probabil= ity); > - if (nop0 > - && (res =3D fold_build2 (code, type, nop0, op1)) !=3D NULL > - && TREE_CODE (res) =3D=3D INTEGER_CST) > - return res; > - if (!nop0) > - nop0 =3D op0; > - } By removing the logic we lose ability to optimize things like a =3D b * c; where b is predicted to value 0 and c has no useful prediction on it. > @@ -2631,6 +2623,9 @@ expr_expected_value_1 (tree type, tree o >=20 > if (predictor2 < *predictor) > *predictor =3D predictor2; > + if (*predictor !=3D PRED_BUILTIN_EXPECT > + && *predictor !=3D PRED_BUILTIN_EXPECT_WITH_PROBABILITY) > + *probability =3D -1; This still can "upgrade" prediction to a predictor of lower enm value but higher probability that is not conservative thing to do. >=20 > return res; > } I ended up with the folloing patch that also takes care of various cases of phi merging and downgrading the predictor to new PRED_COMBINED_VALUE_PREDICTION which can, like PRED_BUILTIN_EXPECT hold custom probability but it is not trued as FIRST_MATCH. What do you think? gcc/ChangeLog: * predict.cc (expr_expected_value_1): (get_predictor_value): * predict.def (PRED_COMBINED_VALUE_PREDICTIONS): diff --git a/gcc/predict.cc b/gcc/predict.cc index 2e9b7dd07a7..cdfaea1e607 100644 --- a/gcc/predict.cc +++ b/gcc/predict.cc @@ -2404,16 +2404,29 @@ 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) =3D=3D GIMPLE_PHI) + if (gphi *phi =3D dyn_cast (def)) { /* All the arguments of the PHI node must have the same constant length. */ - int i, n =3D gimple_phi_num_args (def); - tree val =3D NULL, new_val; + int i, n =3D gimple_phi_num_args (phi); + tree val =3D NULL; + bool has_nonzero_edge =3D false; + + /* If we already proved that given edge is unlikely, we do not ne= ed + to handle merging of the probabilities. */ + for (i =3D 0; i < n && !has_nonzero_edge; i++) + { + tree arg =3D PHI_ARG_DEF (phi, i); + if (arg =3D=3D PHI_RESULT (phi)) + continue; + profile_count cnt =3D gimple_phi_arg_edge (phi, i)->count (); + if (!cnt.initialized_p () || cnt.nonzero_p ()) + has_nonzero_edge =3D true; + } for (i =3D 0; i < n; i++) { - tree arg =3D PHI_ARG_DEF (def, i); + tree arg =3D PHI_ARG_DEF (phi, i); enum br_predictor predictor2; /* If this PHI has itself as an argument, we cannot @@ -2422,26 +2435,50 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, 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 =3D=3D PHI_RESULT (def)) + if (arg =3D=3D PHI_RESULT (phi)) continue; + /* Skip edges which we already predicted as unlikely. */ + if (has_nonzero_edge) + { + profile_count cnt =3D gimple_phi_arg_edge (phi, i)->count= (); + if (cnt.initialized_p () && !cnt.nonzero_p ()) + continue; + } HOST_WIDE_INT probability2; - new_val =3D expr_expected_value (arg, visited, &predictor2, - &probability2); + tree new_val =3D expr_expected_value (arg, visited, &predicto= r2, + &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 =3D new_val; *predictor =3D predictor2; *probability =3D probability2; + continue; } - if (!new_val) - return NULL; - if (!val) - val =3D 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 =3D get_predictor_value (*predictor, *probability); + int p2 =3D get_predictor_value (predictor2, probability2); + /* If both predictors agrees, it does not matter from which + edge we enter the basic block. */ + if (*predictor =3D=3D predictor2 && p1 =3D=3D 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 =3D PRED_COMBINED_VALUE_PREDICTIONS; + *probability =3D MIN (p1, p2); } return val; } @@ -2596,8 +2633,8 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, if (!nop0) nop0 =3D op0; } - enum br_predictor predictor2; - HOST_WIDE_INT probability2; + enum br_predictor predictor2 =3D PRED_UNCONDITIONAL; + HOST_WIDE_INT probability2 =3D -1; if (TREE_CODE (op1) !=3D INTEGER_CST) { /* See if expected value of op1 is good enough to determine the result. */ @@ -2613,24 +2650,39 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, if (!nop1) nop1 =3D op1; } + /* We already checked if folding one of arguments to constant is good enough. + Consequently failing to fold both means that we will not suceed determinging + the value. */ if (nop0 =3D=3D op0 || nop1 =3D=3D op1) return NULL; /* Finally see if we have two known values. */ res =3D fold_build2 (code, type, nop0, nop1); - if (TREE_CODE (res) =3D=3D INTEGER_CST - && TREE_CODE (nop0) =3D=3D INTEGER_CST - && TREE_CODE (nop1) =3D=3D INTEGER_CST) + if (TREE_CODE (res) =3D=3D INTEGER_CST) { - /* Combine binary predictions. */ - if (*probability !=3D -1 || probability2 !=3D -1) + HOST_WIDE_INT p1 =3D get_predictor_value (*predictor, *probabilit= y); + HOST_WIDE_INT p2 =3D get_predictor_value (predictor2, probability= 2); + + /* If one of predictions is sure, such as PRED_UNCONDITIONAL, we + can ignore it. */ + if (p2 =3D=3D PROB_ALWAYS) + return res; + if (p1 =3D=3D PROB_ALWAYS) { - HOST_WIDE_INT p1 =3D get_predictor_value (*predictor, *probability); - HOST_WIDE_INT p2 =3D get_predictor_value (predictor2, probability2); - *probability =3D RDIV (p1 * p2, REG_BR_PROB_BASE); + *predictor =3D predictor2; + *probability =3D probability2; + return res; } - - if (predictor2 < *predictor) - *predictor =3D predictor2; + /* Combine binary predictions. + Since we do not know about independence of predictors, we */ + *probability =3D 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 =3D PRED_COMBINED_VALUE_PREDICTIONS; return res; } @@ -2690,6 +2742,7 @@ 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: gcc_assert (probability !=3D -1); return probability; default: diff --git a/gcc/predict.def b/gcc/predict.def index ae7dd8239c5..4f3e519356d 100644 --- a/gcc/predict.def +++ b/gcc/predict.def @@ -94,6 +94,10 @@ DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed lo= op 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) + /* Branch containing goto is probably not taken. */ DEF_PREDICTOR (PRED_CONTINUE, "continue", HITRATE (67), 0)=