| Message ID | 20141008192227.GO13454@msticlxl57.ims.intel.com |
|---|---|
| State | New |
| Headers | show |
On 10/08/14 13:22, Ilya Enkovich wrote: > Hi, > > This patch adds removal of redundant (covered by other) checks into checker optimization. > > Thanks, > Ilya > -- > 2014-10-08 Ilya Enkovich <ilya.enkovich@intel.com> > > * tree-chkp.c (chkp_compare_checks): New. > (chkp_remove_redundant_checks): New. > (chkp_opt_execute): Run redundant checks removal > algorithm. Wouldn't pure removal be better modeled in existing optimizers? DOM would seem to be a natural fit? Similarly, isn't the swapping very similar to a reverse DOM walk DSE-like optimizer? Deferring further review until those questions are answered? jeff
2014-10-09 21:41 GMT+04:00 Jeff Law <law@redhat.com>: > On 10/08/14 13:22, Ilya Enkovich wrote: >> >> Hi, >> >> This patch adds removal of redundant (covered by other) checks into >> checker optimization. >> >> Thanks, >> Ilya >> -- >> 2014-10-08 Ilya Enkovich <ilya.enkovich@intel.com> >> >> * tree-chkp.c (chkp_compare_checks): New. >> (chkp_remove_redundant_checks): New. >> (chkp_opt_execute): Run redundant checks removal >> algorithm. > > > Wouldn't pure removal be better modeled in existing optimizers? DOM would > seem to be a natural fit? > > Similarly, isn't the swapping very similar to a reverse DOM walk DSE-like > optimizer? > > Deferring further review until those questions are answered? > > jeff > > Checks and and intersection removal code was added as a simple pass catching trivial cases. I'm sure there are optimizations having common elements with what checker optimizer does. But initially we didn't want to adopt existing optimizers because GIMPLE representation of instrumentation was not stable and also we still don't know what are important targets for optimizations. The plan is to have stable version first. After enabling we want to make performance analysis and determine which optimizations are most required (it may appear checks removal doesn't give any significant performance gain at all), determine which of current infrastructure may be re-used (if any) and implement proper checker optimization. Current optimizer is a simple code cleanup. I do not think we should make any significant rework of it as a part of enabling. If current approach seems to require significant changes to go to trunk then it should be probably delayed and go separately from instrumentation pass. Thanks, Ilya
On 10/10/14 09:50, Ilya Enkovich wrote: > Checks and and intersection removal code was added as a simple pass > catching trivial cases. I'm sure there are optimizations having > common elements with what checker optimizer does. But initially we > didn't want to adopt existing optimizers because GIMPLE representation > of instrumentation was not stable and also we still don't know what > are important targets for optimizations. Understood. > > The plan is to have stable version first. After enabling we want to > make performance analysis and determine which optimizations are most > required (it may appear checks removal doesn't give any significant > performance gain at all), determine which of current infrastructure > may be re-used (if any) and implement proper checker optimization. > > Current optimizer is a simple code cleanup. I do not think we should > make any significant rework of it as a part of enabling. If current > approach seems to require significant changes to go to trunk then it > should be probably delayed and go separately from instrumentation > pass. Well, I think it should be trivial to handle the redundant check elimination in DOM. Most likely eliminate_redundant_computations needs some work to allow it to look inside those checks and get them recorded into its tables. With that in place, DOM should optimize this stuff without further intervention. It's probably less code than you've already written :-) The swapping variant feels like it should be simple to implement with the existing dominator walkers. But I haven't thought nearly as much about that one. jeff
2014-10-10 20:56 GMT+04:00 Jeff Law <law@redhat.com>: > On 10/10/14 09:50, Ilya Enkovich wrote: >> >> Checks and and intersection removal code was added as a simple pass >> catching trivial cases. I'm sure there are optimizations having >> common elements with what checker optimizer does. But initially we >> didn't want to adopt existing optimizers because GIMPLE representation >> of instrumentation was not stable and also we still don't know what >> are important targets for optimizations. > > Understood. > >> >> The plan is to have stable version first. After enabling we want to >> make performance analysis and determine which optimizations are most >> required (it may appear checks removal doesn't give any significant >> performance gain at all), determine which of current infrastructure >> may be re-used (if any) and implement proper checker optimization. >> >> Current optimizer is a simple code cleanup. I do not think we should >> make any significant rework of it as a part of enabling. If current >> approach seems to require significant changes to go to trunk then it >> should be probably delayed and go separately from instrumentation >> pass. > > Well, I think it should be trivial to handle the redundant check elimination > in DOM. > > Most likely eliminate_redundant_computations needs some work to allow it to > look inside those checks and get them recorded into its tables. With that > in place, DOM should optimize this stuff without further intervention. It's > probably less code than you've already written :-) > > The swapping variant feels like it should be simple to implement with the > existing dominator walkers. But I haven't thought nearly as much about that > one. > > jeff I'll look into DOM and a possibility to use it for checks removal. But I give higher priority to builtins instrumentation and therefore prefer to delay this one and return to it after builtins instrumentation work or in case there is some spare time for it. This patch is not critical for checker functionality and may be excluded from initial commit. Thanks, Ilya
On 10/13/14 08:58, Ilya Enkovich wrote: > > I'll look into DOM and a possibility to use it for checks removal. > But I give higher priority to builtins instrumentation and therefore > prefer to delay this one and return to it after builtins > instrumentation work or in case there is some spare time for it. This > patch is not critical for checker functionality and may be excluded > from initial commit. OK. When you're ready to look at DOM, don't hesitate to contact me. I probably know that code better than anyone. jeff
diff --git a/gcc/tree-chkp.c b/gcc/tree-chkp.c index ade546b..37ab729 100644 --- a/gcc/tree-chkp.c +++ b/gcc/tree-chkp.c @@ -4972,6 +4972,211 @@ chkp_remove_constant_checks (void) } } +/* Compare two checks CI1 and CI2 to find redundant one. + CI1 is known to dominate CI2. POSTDOM indicated if + CI2 postdominateds CI1. + + Few conditions are checked to find redundant check: + 1. Checks has the same type + 2. Checks use the same bounds + 3. One check fail means other check fail + 4. Stronger check is always executed if weaker one is executed + + If redundant check is found it is removed. If removed check is CI1 + then CI2 is moved to CI1's position to avoid bound violation happened + before check is executed. */ +void +chkp_compare_checks (struct check_info *ci1, + struct check_info *ci2, + bool postdom) +{ + address_t delta; + int sign; + + if (ci1->type != ci2->type) + return; + + if (ci1->bounds != ci2->bounds) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Comparing checks...\n"); + fprintf (dump_file, " First check: "); + print_gimple_stmt (dump_file, ci1->stmt, 0, 0); + fprintf (dump_file, " Second check: "); + print_gimple_stmt (dump_file, ci2->stmt, 0, 0); + } + + delta.pol = ci1->addr.pol.copy (); + chkp_sub_addr_addr (delta, ci2->addr); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Delta: "); + chkp_print_addr (delta); + fprintf (dump_file, "\n"); + } + + if (!chkp_is_constant_addr (delta, &sign)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Action: skip (delta is not constant)\n"); + } + else + { + if (sign) + { + if ((sign > 0 && ci1->type == CHECK_UPPER_BOUND) + || (sign < 0 && ci1->type == CHECK_LOWER_BOUND)) + { + gimple_stmt_iterator i = gsi_for_stmt (ci2->stmt); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Action: delete the second check\n"); + + gsi_remove (&i, true); + unlink_stmt_vdef (ci2->stmt); + release_defs (ci2->stmt); + ci2->stmt = NULL; + } + else if (postdom) + { + gimple_stmt_iterator i = gsi_for_stmt (ci2->stmt); + gimple_seq seq = NULL; + tree addr = gimple_call_arg (ci1->stmt, 0); + unsigned int n; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Action: replace the first " + "check with the second one\n"); + + gsi_remove (&i, true); + unlink_stmt_vdef (ci2->stmt); + release_defs (ci2->stmt); + ci2->stmt = NULL; + + for (n = 0; n < delta.pol.length (); n++) + if (delta.pol[n].var == NULL) + { + tree tmp = fold_build2 (MINUS_EXPR, + TREE_TYPE (delta.pol[n].cst), + integer_zero_node, + delta.pol[n].cst); + addr = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (addr), + addr, convert_to_ptrofftype (tmp)); + } + else if (integer_onep (delta.pol[n].cst)) + { + tree tmp = fold_build2 (MINUS_EXPR, + TREE_TYPE (delta.pol[n].var), + integer_zero_node, + delta.pol[n].var); + addr = build2 (POINTER_PLUS_EXPR, TREE_TYPE (addr), + addr, convert_to_ptrofftype (tmp)); + } + else if (tree_int_cst_compare (delta.pol[n].cst, + integer_minus_one_node) == 0) + addr = build2 (POINTER_PLUS_EXPR, TREE_TYPE (addr), + addr, convert_to_ptrofftype (delta.pol[n].var)); + else + { + tree tmp = fold_build2 (MULT_EXPR, + TREE_TYPE (delta.pol[n].var), + delta.pol[n].var, + delta.pol[n].cst); + tmp = fold_build2 (MINUS_EXPR, TREE_TYPE (tmp), + integer_zero_node, tmp); + addr = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (addr), + addr, convert_to_ptrofftype (tmp)); + } + + addr = force_gimple_operand (unshare_expr (addr), &seq, + true, NULL_TREE); + + i = gsi_for_stmt (ci1->stmt); + gsi_insert_seq_before (&i, seq, GSI_CONTINUE_LINKING); + gimple_call_set_arg (ci1->stmt, 0, addr); + update_stmt (ci1->stmt); + + ci1->addr.pol.release (); + chkp_fill_check_info (ci1->stmt, ci1); + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Action: skip (the first check is " + "not post-dominanted by the second check)\n"); + } + } + else + { + gimple_stmt_iterator i = gsi_for_stmt (ci2->stmt); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + " Action: delete the second check (same addresses)\n"); + + gsi_remove (&i, true); + unlink_stmt_vdef (ci2->stmt); + release_defs (ci2->stmt); + ci2->stmt = NULL; + } + } + + delta.pol.release (); +} + +/* Here we try to find checks which are covered by other checks + and thus can be removed. To do it we simply find all pairs of + checks where the first check dominates the second one and + call chkp_compare_checks to find and remove redundant ones. */ +void +chkp_remove_redundant_checks (void) +{ + basic_block bb; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Searching for redundant checks...\n"); + + FOR_EACH_BB_FN (bb, cfun) + { + struct bb_checks *bbc = &check_infos[bb->index]; + unsigned int no; + + /* Iterate throw all found checks in BB. */ + for (no = 0; no < bbc->checks.length (); no++) + if (bbc->checks[no].stmt) + { + vec<basic_block> dom_bbs; + unsigned bb_no, other; + + /* Compare check with all other following checks in this BB. */ + for (other = no + 1; other < bbc->checks.length (); other++) + if (bbc->checks[other].stmt) + chkp_compare_checks (&bbc->checks[no], &bbc->checks[other], + true); + + /* Now compare with checks in BBs dominated by current one. */ + dom_bbs = get_all_dominated_blocks (CDI_DOMINATORS, bb); + for (bb_no = 0; bb_no < dom_bbs.length (); bb_no++) + { + struct bb_checks *dom_bbc = &check_infos[dom_bbs[bb_no]->index]; + + if (dom_bbs[bb_no] == bb) + continue; + + for (other = 0; other < dom_bbc->checks.length (); other++) + if (dom_bbc->checks[other].stmt) + chkp_compare_checks (&bbc->checks[no], + &dom_bbc->checks[other], + dominated_by_p (CDI_POST_DOMINATORS, bb, + dom_bbs[bb_no])); + } + } + } +} + /* Return fast version of string function FNCODE. */ tree chkp_get_nobnd_fndecl (enum built_in_function fncode) @@ -5257,6 +5462,8 @@ chkp_opt_execute (void) chkp_remove_constant_checks (); + chkp_remove_redundant_checks (); + chkp_release_check_info (); chkp_opt_fini ();