From efe126563bb8d28cb3958423a735d0021e75702f Mon Sep 17 00:00:00 2001 From: Feng Xue Date: Thu, 19 Sep 2019 14:16:01 +0000 Subject: [PATCH] Use post-dom info to update if/switch predicate 2019-09-19 Feng Xue * ipa-fnsummary.c (set_cond_stmt_execution_predicate): Do not compute trivial predicate for condition branch. (set_switch_stmt_execution_predicate): Do not compute trivial predicate for switch case. (compute_bb_predicates): Update predicate based on post-dominating relationship. (analyze_function_body): Calculate post-dominating information. 2019-09-19 Feng Xue * gcc.dg/ipa/pr91089.c: Add a new function and pattern. From-SVN: r275963 --- gcc/ChangeLog | 10 +++++ gcc/ipa-fnsummary.c | 78 ++++++++++++++++++++++++++++++++------ gcc/testsuite/ChangeLog | 5 +++ gcc/testsuite/gcc.dg/ipa/pr91089.c | 47 +++++++++++++++++++++++ 4 files changed, 128 insertions(+), 12 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 506e93d7..279974c 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,13 @@ +2019-09-19 Feng Xue + + * ipa-fnsummary.c (set_cond_stmt_execution_predicate): Do not compute + trivial predicate for condition branch. + (set_switch_stmt_execution_predicate): Do not compute trivial predicate + for switch case. + (compute_bb_predicates): Update predicate based on post-dominating + relationship. + (analyze_function_body): Calculate post-dominating information. + 2019-09-19 Richard Sandiford * tree-vectorizer.h (vectorizable_condition): Take an int diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c index 1bf1806..6de060a 100644 --- a/gcc/ipa-fnsummary.c +++ b/gcc/ipa-fnsummary.c @@ -1197,8 +1197,14 @@ set_cond_stmt_execution_predicate (struct ipa_func_body_info *fbi, ? code : inverted_code); /* invert_tree_comparison will return ERROR_MARK on FP comparsions that are not EQ/NE instead of returning proper - unordered one. Be sure it is not confused with NON_CONSTANT. */ - if (this_code != ERROR_MARK) + unordered one. Be sure it is not confused with NON_CONSTANT. + + And if the edge's target is the final block of diamond CFG graph + of this conditional statement, we do not need to compute + predicate for the edge because the final block's predicate must + be at least as that of the first block of the statement. */ + if (this_code != ERROR_MARK + && !dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)) { predicate p = add_condition (summary, index, size, &aggpos, this_code, @@ -1282,18 +1288,38 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, *(predicate *) e->aux = false; } + e = gimple_switch_edge (cfun, last, 0); + /* Set BOUND_COUNT to maximum count to bypass computing predicate for + default case if its target basic block is in convergence point of all + switch cases, which can be determined by checking whether it + post-dominates the switch statement. */ + if (dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)) + bound_count = INT_MAX; + n = gimple_switch_num_labels (last); for (case_idx = 1; case_idx < n; ++case_idx) { tree cl = gimple_switch_label (last, case_idx); - tree min, max; + tree min = CASE_LOW (cl); + tree max = CASE_HIGH (cl); predicate p; - e = gimple_switch_edge (cfun, last, case_idx); - min = CASE_LOW (cl); - max = CASE_HIGH (cl); + /* The case value might not have same type as switch expression, + extend the value based on the expression type. */ + if (TREE_TYPE (min) != type) + min = wide_int_to_tree (type, wi::to_wide (min)); if (!max) + max = min; + else if (TREE_TYPE (max) != type) + max = wide_int_to_tree (type, wi::to_wide (max)); + + /* The case's target basic block is in convergence point of all switch + cases, its predicate should be at least as that of the switch + statement. */ + if (dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)) + p = true; + else if (min == max) p = add_condition (summary, index, size, &aggpos, EQ_EXPR, unshare_expr_without_location (min)); else @@ -1305,6 +1331,7 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, unshare_expr_without_location (max)); p = p1 & p2; } + e = gimple_switch_edge (cfun, last, case_idx); *(class predicate *) e->aux = p.or_with (summary->conds, *(class predicate *) e->aux); @@ -1334,9 +1361,6 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, } } - if (!max) - max = min; - /* Create/extend a case range. And we count endpoints of range set, this number nearly equals to number of conditions that we will create for predicate of default case. */ @@ -1463,10 +1487,10 @@ compute_bb_predicates (struct ipa_func_body_info *fbi, break; } } - if (p == false) - gcc_checking_assert (!bb->aux); - else + if (p != false) { + basic_block pdom_bb; + if (!bb->aux) { done = false; @@ -1485,6 +1509,34 @@ compute_bb_predicates (struct ipa_func_body_info *fbi, *((predicate *) bb->aux) = p; } } + + /* For switch/if statement, we can OR-combine predicates of all + its cases/branches to get predicate for basic block in their + convergence point, but sometimes this will generate very + complicated predicate. Actually, we can get simplified + predicate in another way by using the fact that predicate + for a basic block must also hold true for its post dominators. + To be specific, basic block in convergence point of + conditional statement should include predicate of the + statement. */ + pdom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); + if (pdom_bb == EXIT_BLOCK_PTR_FOR_FN (my_function) || !pdom_bb) + ; + else if (!pdom_bb->aux) + { + done = false; + pdom_bb->aux = edge_predicate_pool.allocate (); + *((predicate *) pdom_bb->aux) = p; + } + else if (p != *(predicate *) pdom_bb->aux) + { + p = p.or_with (summary->conds, *(predicate *)pdom_bb->aux); + if (p != *(predicate *) pdom_bb->aux) + { + done = false; + *((predicate *) pdom_bb->aux) = p; + } + } } } } @@ -2089,6 +2141,7 @@ analyze_function_body (struct cgraph_node *node, bool early) if (opt_for_fn (node->decl, optimize)) { calculate_dominance_info (CDI_DOMINATORS); + calculate_dominance_info (CDI_POST_DOMINATORS); if (!early) loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); else @@ -2469,6 +2522,7 @@ analyze_function_body (struct cgraph_node *node, bool early) else if (!ipa_edge_args_sum) ipa_free_all_node_params (); free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); } if (dump_file) { diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index c5854bd..79de33c 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,8 +1,13 @@ +2019-09-19 Feng Xue + + * gcc.dg/ipa/pr91089.c: Add a new function and pattern. + 2019-09-19 Richard Biener PR tree-optimization/91812 * gcc.dg/torture/pr91812.c: New testcase. +>>>>>>> .r275960 2019-09-19 Tom Tromey * gnat.dg/bias1.adb: New testcase. diff --git a/gcc/testsuite/gcc.dg/ipa/pr91089.c b/gcc/testsuite/gcc.dg/ipa/pr91089.c index e9e206f..7509c62 100644 --- a/gcc/testsuite/gcc.dg/ipa/pr91089.c +++ b/gcc/testsuite/gcc.dg/ipa/pr91089.c @@ -41,6 +41,52 @@ int callee (int i) return data += i; } +int fn2 (); + +int callee_complex_predicate (int i) +{ + switch (i ) + { + case 0: + fn (); + fn (); + fn (); + case 1: + fn (); + fn (); + case -1: + fn (); + case -2: + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + data += i; + break; + } + + if (i == 1000) + { + int j; + + for (j = 0; j < 100; j++) + fn2 (); + } + return i + 3; +} + int caller () { return callee (-127) + @@ -60,3 +106,4 @@ int caller () /* { dg-final { scan-ipa-dump "op0 != 0" "fnsummary" } } */ /* { dg-final { scan-ipa-dump "op0 < 5" "fnsummary" } } */ /* { dg-final { scan-ipa-dump "op0 > 7" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "loop depth: 1 .+ time:\[ \]*\[0-9\]+ predicate: \\(op0 == 1000\\)\[\r\n]+" "fnsummary" } } */ -- 2.7.4