From patchwork Wed Oct 8 19:22:27 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Enkovich X-Patchwork-Id: 397702 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id E0435140076 for ; Thu, 9 Oct 2014 06:22:45 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:mime-version:content-type; q=dns; s=default; b=FnLvVc/uiYaeKfqZt8+FkqnU5IQzlIkn52xjHgXr9IvuhJs5p3 X53gMRJm1+2TdnAwb297xJeuCpV1W/QTxHIe+xXz8buuxqDmpJwI6bYbbkN1Zyse DBqGPhYICYqdko/ekhtNY8zWMoWD46Ecmo8xNQGMKCOigaeiK++TJLvPc= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:mime-version:content-type; s= default; bh=gzzM7ceWjTMosNrRPaucQxCjqlI=; b=X4irhagPPKFHIGL4xHvT ulY30h5SaWI4anPjPMiknlceRS60BglO1Ie89cp8+EFku4yPXJnAJGaYRuBpXmPQ AhUjBOPgpZthIaeGSLXaADaveFLWrN7R1KUiLryn6x5MCuYmSZ2gnQGsoNduHZhj eLVhNsuakCeyXYl9ZpR8VWY= Received: (qmail 21873 invoked by alias); 8 Oct 2014 19:22:38 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 21864 invoked by uid 89); 8 Oct 2014 19:22:37 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.8 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-pd0-f177.google.com Received: from mail-pd0-f177.google.com (HELO mail-pd0-f177.google.com) (209.85.192.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Wed, 08 Oct 2014 19:22:35 +0000 Received: by mail-pd0-f177.google.com with SMTP id v10so7234539pde.8 for ; Wed, 08 Oct 2014 12:22:33 -0700 (PDT) X-Received: by 10.66.151.200 with SMTP id us8mr4939753pab.40.1412796153656; Wed, 08 Oct 2014 12:22:33 -0700 (PDT) Received: from msticlxl57.ims.intel.com (fmdmzpr03-ext.fm.intel.com. [192.55.54.38]) by mx.google.com with ESMTPSA id d9sm710943pdp.44.2014.10.08.12.22.31 for (version=TLSv1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 08 Oct 2014 12:22:33 -0700 (PDT) Date: Wed, 8 Oct 2014 23:22:27 +0400 From: Ilya Enkovich To: gcc-patches@gcc.gnu.org Cc: Jeff Law Subject: [PATCH, Pointer Bounds Checker 14/x] Passes [15/n] Optimize redundant checks Message-ID: <20141008192227.GO13454@msticlxl57.ims.intel.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes Hi, This patch adds removal of redundant (covered by other) checks into checker optimization. Thanks, Ilya --- 2014-10-08 Ilya Enkovich * tree-chkp.c (chkp_compare_checks): New. (chkp_remove_redundant_checks): New. (chkp_opt_execute): Run redundant checks removal algorithm. 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 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 ();