https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110852
--- Comment #9 from Jan Hubicka <hubicka at ucw dot cz> --- > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110852 > > --- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> --- > 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)? > > --- 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) == GIMPLE_BINARY_RHS) > { > tree res; > - tree nop0 = op0; > - tree nop1 = op1; > - if (TREE_CODE (op0) != INTEGER_CST) > - { > - /* See if expected value of op0 is good enough to determine the > result. */ > - nop0 = expr_expected_value (op0, visited, predictor, probability); > - if (nop0 > - && (res = fold_build2 (code, type, nop0, op1)) != NULL > - && TREE_CODE (res) == INTEGER_CST) > - return res; > - if (!nop0) > - nop0 = op0; > - } By removing the logic we lose ability to optimize things like a = 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 > > if (predictor2 < *predictor) > *predictor = predictor2; > + if (*predictor != PRED_BUILTIN_EXPECT > + && *predictor != PRED_BUILTIN_EXPECT_WITH_PROBABILITY) > + *probability = -1; This still can "upgrade" prediction to a predictor of lower enm value but higher probability that is not conservative thing to do. > > 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) == GIMPLE_PHI) + if (gphi *phi = dyn_cast <gphi *> (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 @@ -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 == PHI_RESULT (def)) + if (arg == PHI_RESULT (phi)) continue; + /* Skip edges which we already predicted as unlikely. */ + 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 agrees, 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; + *probability = MIN (p1, p2); } return val; } @@ -2596,8 +2633,8 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, 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. */ @@ -2613,24 +2650,39 @@ 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 suceed 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 */ + *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 +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 != -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 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) + /* Branch containing goto is probably not taken. */ DEF_PREDICTOR (PRED_CONTINUE, "continue", HITRATE (67), 0)
