diff options
| -rw-r--r-- | gcc/ChangeLog | 5 | ||||
| -rw-r--r-- | gcc/predict.c | 84 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 6 | ||||
| -rw-r--r-- | gcc/testsuite/g++.dg/predict-loop-exit-1.C | 13 | ||||
| -rw-r--r-- | gcc/testsuite/g++.dg/predict-loop-exit-2.C | 13 | ||||
| -rw-r--r-- | gcc/testsuite/g++.dg/predict-loop-exit-3.C | 13 |
6 files changed, 133 insertions, 1 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 39e23bd..14bdc37 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,8 @@ +2012-10-08 Dehao Chen <dehao@google.com> + + * predict.c (predict_loops): Predict for short-circuit conditions. + (predict_extra_loop_exits): New Function. + 2012-10-08 Steven Bosscher <steven@gcc.gnu.org> * bitmap.h (bitmap_and_into): Update prototype. diff --git a/gcc/predict.c b/gcc/predict.c index f0db9f4..4917399 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -1296,7 +1296,87 @@ predict_iv_comparison (struct loop *loop, basic_block bb, predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN); } } - + +/* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop + exits are resulted from short-circuit conditions that will generate an + if_tmp. E.g.: + + if (foo() || global > 10) + break; + + This will be translated into: + + BB3: + loop header... + BB4: + if foo() goto BB6 else goto BB5 + BB5: + if global > 10 goto BB6 else goto BB7 + BB6: + goto BB7 + BB7: + iftmp = (PHI 0(BB5), 1(BB6)) + if iftmp == 1 goto BB8 else goto BB3 + BB8: + outside of the loop... + + The edge BB7->BB8 is loop exit because BB8 is outside of the loop. + From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop + exits. This function takes BB7->BB8 as input, and finds out the extra loop + exits to predict them using PRED_LOOP_EXIT. */ + +static void +predict_extra_loop_exits (edge exit_edge) +{ + unsigned i; + bool check_value_one; + gimple phi_stmt; + tree cmp_rhs, cmp_lhs; + gimple cmp_stmt = last_stmt (exit_edge->src); + + if (!cmp_stmt || gimple_code (cmp_stmt) != GIMPLE_COND) + return; + cmp_rhs = gimple_cond_rhs (cmp_stmt); + cmp_lhs = gimple_cond_lhs (cmp_stmt); + if (!TREE_CONSTANT (cmp_rhs) + || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs))) + return; + if (TREE_CODE (cmp_lhs) != SSA_NAME) + return; + + /* If check_value_one is true, only the phi_args with value '1' will lead + to loop exit. Otherwise, only the phi_args with value '0' will lead to + loop exit. */ + check_value_one = (((integer_onep (cmp_rhs)) + ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR)) + ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0)); + + phi_stmt = SSA_NAME_DEF_STMT (cmp_lhs); + if (!phi_stmt || gimple_code (phi_stmt) != GIMPLE_PHI) + return; + + for (i = 0; i < gimple_phi_num_args (phi_stmt); i++) + { + edge e1; + edge_iterator ei; + tree val = gimple_phi_arg_def (phi_stmt, i); + edge e = gimple_phi_arg_edge (phi_stmt, i); + + if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val))) + continue; + if ((check_value_one ^ integer_onep (val)) == 1) + continue; + if (EDGE_COUNT (e->src->succs) != 1) + { + predict_paths_leading_to_edge (e, PRED_LOOP_EXIT, NOT_TAKEN); + continue; + } + + FOR_EACH_EDGE (e1, ei, e->src->preds) + predict_paths_leading_to_edge (e1, PRED_LOOP_EXIT, NOT_TAKEN); + } +} + /* Predict edge probabilities by exploiting loop structure. */ static void @@ -1332,6 +1412,8 @@ predict_loops (void) int probability; enum br_predictor predictor; + predict_extra_loop_exits (ex); + if (number_of_iterations_exit (loop, ex, &niter_desc, false)) niter = niter_desc.niter; if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST) diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 9b0c0ba..1345f72f 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2012-10-08 Dehao Chen <dehao@google.com> + + * g++.dg/predict-loop-exit-1.C: New. + * g++.dg/predict-loop-exit-2.C: New. + * g++.dg/predict-loop-exit-3.C: New. + 2012-10-08 Rainer Orth <ro@CeBiTec.Uni-Bielefeld.DE> * gcc.target/i386/pr54445-1.c: Require tls_runtime, add tls options. diff --git a/gcc/testsuite/g++.dg/predict-loop-exit-1.C b/gcc/testsuite/g++.dg/predict-loop-exit-1.C new file mode 100644 index 0000000..2289552 --- /dev/null +++ b/gcc/testsuite/g++.dg/predict-loop-exit-1.C @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +int g; +int foo(); +void test() { + while (foo() && g < 10) + g++; + return; +} + +/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 3 "profile_estimate"} } */ +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ diff --git a/gcc/testsuite/g++.dg/predict-loop-exit-2.C b/gcc/testsuite/g++.dg/predict-loop-exit-2.C new file mode 100644 index 0000000..1a5880b --- /dev/null +++ b/gcc/testsuite/g++.dg/predict-loop-exit-2.C @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +int g; +int foo(); +void test() { + while (foo() || g < 10) + g++; + return; +} + +/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 2 "profile_estimate"} } */ +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ diff --git a/gcc/testsuite/g++.dg/predict-loop-exit-3.C b/gcc/testsuite/g++.dg/predict-loop-exit-3.C new file mode 100644 index 0000000..9afc78e --- /dev/null +++ b/gcc/testsuite/g++.dg/predict-loop-exit-3.C @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +int g; +int foo(); +void test() { + while (foo() && (g < 10 || g > 20)) + g++; + return; +} + +/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 3 "profile_estimate"} } */ +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ |