From patchwork Mon Oct 13 20:57:47 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Enkovich X-Patchwork-Id: 399313 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 1F34D140119 for ; Tue, 14 Oct 2014 07:58:11 +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:references:mime-version :content-type:in-reply-to; q=dns; s=default; b=lO/yoMbsBdBFbeCpR H8GiWh7ImCKpfTGeRX7BLwdOsMUe9mtcVwtG2xYBmdNYWmHzEl7o/n7fyxcZCTzZ c49QwbxWs/DtNGSpZUwPpTSXhOnKHA2mMX3kxEK9o2RHeWXbyxASk2z+fcJCvQBg 7qgelSdLB9kLhjRjUQLhL0lEyU= 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:references:mime-version :content-type:in-reply-to; s=default; bh=9Ge2N1ohLXJDB6Gxmi1ArT/ thh8=; b=oUfpz7p6po3viGJAy087BymaZpzbIV+IeGp8un9i7KJrvV0CBe6uRzN OI/RhRp2niQicJmvYjEaaeC8GeiDjJOrvbgml6rQTNFNi6m8mo915TewihOv9AyK JjP0/7BGpEJ/UVovPZZ+OANQzN2Doa0ElbQ8dDfZpoi0i/8CLVM4= Received: (qmail 13889 invoked by alias); 13 Oct 2014 20:58:03 -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 13873 invoked by uid 89); 13 Oct 2014 20:58:03 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 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; Mon, 13 Oct 2014 20:58:01 +0000 Received: by mail-pd0-f177.google.com with SMTP id v10so6223231pde.36 for ; Mon, 13 Oct 2014 13:57:59 -0700 (PDT) X-Received: by 10.70.132.133 with SMTP id ou5mr769543pdb.51.1413233879324; Mon, 13 Oct 2014 13:57:59 -0700 (PDT) Received: from msticlxl57.ims.intel.com (fmdmzpr04-ext.fm.intel.com. [192.55.55.39]) by mx.google.com with ESMTPSA id fb5sm12202992pab.23.2014.10.13.13.57.57 for (version=TLSv1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 13 Oct 2014 13:57:58 -0700 (PDT) Date: Tue, 14 Oct 2014 00:57:47 +0400 From: Ilya Enkovich To: Jeff Law Cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH, Pointer Bounds Checker 14/x] Passes [13/n] Optimize bounds intersections Message-ID: <20141013205747.GA58443@msticlxl57.ims.intel.com> References: <20141008191913.GM13454@msticlxl57.ims.intel.com> <5436CE4F.9070002@redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <5436CE4F.9070002@redhat.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes On 09 Oct 12:05, Jeff Law wrote: > On 10/08/14 13:19, Ilya Enkovich wrote: > >Hi, > > > >This patch adds removal of unnecessary intersections into checker optimizations. > > > >Thanks, > >Ilya > >-- > >2014-10-08 Ilya Enkovich > > > > * tree-chkp.c (chkp_release_check_info): New. > > (chkp_init_check_info): New. > > (chkp_gather_checks_info): New. > > (chkp_get_check_result): New. > > (chkp_use_outer_bounds_if_possible): New. > > (chkp_remove_excess_intersections): New. > > (chkp_opt_execute): Run intersections removal > > algorithm. > Usual comment about basic tests and pulling the optimization work > into its own file. > > > + > >+/* Find all checks in current function and store info about them > >+ in check_infos. */ > >+void > >+chkp_gather_checks_info (void) > >+{ > >+ basic_block bb; > >+ gimple_stmt_iterator i; > >+ > >+ if (dump_file && (dump_flags & TDF_DETAILS)) > >+ fprintf (dump_file, "Gathering information about checks...\n"); > >+ > >+ chkp_init_check_info (); > >+ > >+ FOR_EACH_BB_FN (bb, cfun) > >+ { > >+ struct bb_checks *bbc = &check_infos[bb->index]; > >+ > >+ if (dump_file && (dump_flags & TDF_DETAILS)) > >+ fprintf (dump_file, "Searching checks in BB%d...\n", bb->index); > >+ > >+ for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) > >+ { > >+ gimple stmt = gsi_stmt (i); > >+ > >+ if (gimple_code (stmt) != GIMPLE_CALL) > >+ continue; > >+ > >+ if (gimple_call_fndecl (stmt) == chkp_checkl_fndecl > >+ || gimple_call_fndecl (stmt) == chkp_checku_fndecl) > >+ { > >+ struct check_info ci; > >+ > >+ chkp_fill_check_info (stmt, &ci); > >+ bbc->checks.safe_push (ci); > >+ > >+ if (dump_file && (dump_flags & TDF_DETAILS)) > >+ { > >+ fprintf (dump_file, "Adding check information:\n"); > >+ fprintf (dump_file, " bounds: "); > >+ print_generic_expr (dump_file, ci.bounds, 0); > >+ fprintf (dump_file, "\n address: "); > >+ chkp_print_addr (ci.addr); > >+ fprintf (dump_file, "\n check: "); > >+ print_gimple_stmt (dump_file, stmt, 0, 0); > >+ } > >+ } > >+ } > >+ } > >+} > So I wonder if it makes sense to structure your optimization passes as: > > gather_info > opt1 > opt2 > opt3 > ... > release > > > The reason being it looks like you do a number of walks over the > blocks and statements in the block to gather information. ISTM you > could do it once for all these optimizations and save youself some > walking time. This patch is the first one using check infos. Following optimizations are inserted between checks info computation and its release introduced here as you suggest. > > This patch looks fine. > > jeff > Here is an updated version with tests added. Thanks, Ilya --- gcc/ 2014-10-13 Ilya Enkovich * tree-chkp-opt.c (chkp_release_check_info): New. (chkp_init_check_info): New. (chkp_gather_checks_info): New. (chkp_get_check_result): New. (chkp_use_outer_bounds_if_possible): New. (chkp_remove_excess_intersections): New. (chkp_opt_execute): Run intersections removal algorithm. gcc/testsuites/ 2014-10-13 Ilya Enkovich * gcc.target/i386/chkp-remove-bndint-1.c: New. * gcc.target/i386/chkp-remove-bndint-2.c: New. diff --git a/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-1.c b/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-1.c new file mode 100644 index 0000000..db71004 --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-1.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-fcheck-pointer-bounds -mmpx -O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-not "bndint" "optimized" } } */ + + +struct S +{ + int a; + int b; + int c; +}; + +int test (struct S *ps) +{ + int *pi = &ps->b; + return *pi; +} diff --git a/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-2.c b/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-2.c new file mode 100644 index 0000000..c97ac27 --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-2.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-fcheck-pointer-bounds -mmpx -O2 -fdump-tree-optimized -Wchkp" } */ +/* { dg-final { scan-tree-dump-not "bndint" "optimized" } } */ + + +struct S +{ + int a; + int b; + int c; +}; + +int test (struct S *ps) +{ + int *pi = &ps->b; + return *(pi + 1); /* { dg-warning "memory access check always fail" "" } */ +} diff --git a/gcc/tree-chkp-opt.c b/gcc/tree-chkp-opt.c index 56315c0..b3b7295 100644 --- a/gcc/tree-chkp-opt.c +++ b/gcc/tree-chkp-opt.c @@ -448,6 +448,336 @@ chkp_fill_check_info (gimple stmt, struct check_info *ci) ci->stmt = stmt; } +/* Release structures holding check information + for current function. */ +static void +chkp_release_check_info (void) +{ + unsigned int n, m; + + if (check_infos.exists ()) + { + for (n = 0; n < check_infos.length (); n++) + { + for (m = 0; m < check_infos[n].checks.length (); m++) + if (check_infos[n].checks[m].addr.pol.exists ()) + check_infos[n].checks[m].addr.pol.release (); + check_infos[n].checks.release (); + } + check_infos.release (); + } +} + +/* Create structures to hold check information + for current function. */ +static void +chkp_init_check_info (void) +{ + struct bb_checks empty_bbc; + int n; + + empty_bbc.checks = vNULL; + + chkp_release_check_info (); + + check_infos.create (last_basic_block_for_fn (cfun)); + for (n = 0; n < last_basic_block_for_fn (cfun); n++) + { + check_infos.safe_push (empty_bbc); + check_infos.last ().checks.create (0); + } +} + +/* Find all checks in current function and store info about them + in check_infos. */ +static void +chkp_gather_checks_info (void) +{ + basic_block bb; + gimple_stmt_iterator i; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Gathering information about checks...\n"); + + chkp_init_check_info (); + + FOR_EACH_BB_FN (bb, cfun) + { + struct bb_checks *bbc = &check_infos[bb->index]; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Searching checks in BB%d...\n", bb->index); + + for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) + { + gimple stmt = gsi_stmt (i); + + if (gimple_code (stmt) != GIMPLE_CALL) + continue; + + if (gimple_call_fndecl (stmt) == chkp_checkl_fndecl + || gimple_call_fndecl (stmt) == chkp_checku_fndecl) + { + struct check_info ci; + + chkp_fill_check_info (stmt, &ci); + bbc->checks.safe_push (ci); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Adding check information:\n"); + fprintf (dump_file, " bounds: "); + print_generic_expr (dump_file, ci.bounds, 0); + fprintf (dump_file, "\n address: "); + chkp_print_addr (ci.addr); + fprintf (dump_file, "\n check: "); + print_gimple_stmt (dump_file, stmt, 0, 0); + } + } + } + } +} + +/* Return 1 if check CI against BOUNDS always pass, + -1 if check CI against BOUNDS always fails and + 0 if we cannot compute check result. */ +static int +chkp_get_check_result (struct check_info *ci, tree bounds) +{ + gimple bnd_def; + address_t bound_val; + int sign, res = 0; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Trying to compute result of the check\n"); + fprintf (dump_file, " check: "); + print_gimple_stmt (dump_file, ci->stmt, 0, 0); + fprintf (dump_file, " address: "); + chkp_print_addr (ci->addr); + fprintf (dump_file, "\n bounds: "); + print_generic_expr (dump_file, bounds, 0); + fprintf (dump_file, "\n"); + } + + if (TREE_CODE (bounds) != SSA_NAME) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " result: bounds tree code is not ssa_name\n"); + return 0; + } + + bnd_def = SSA_NAME_DEF_STMT (bounds); + /* Currently we handle cases when bounds are result of bndmk + or loaded static bounds var. */ + if (gimple_code (bnd_def) == GIMPLE_CALL + && gimple_call_fndecl (bnd_def) == chkp_bndmk_fndecl) + { + bound_val.pol.create (0); + chkp_collect_value (gimple_call_arg (bnd_def, 0), bound_val); + if (ci->type == CHECK_UPPER_BOUND) + { + address_t size_val; + size_val.pol.create (0); + chkp_collect_value (gimple_call_arg (bnd_def, 1), size_val); + chkp_add_addr_addr (bound_val, size_val); + size_val.pol.release (); + chkp_add_addr_item (bound_val, integer_minus_one_node, NULL); + } + } + else if (gimple_code (bnd_def) == GIMPLE_ASSIGN + && gimple_assign_rhs1 (bnd_def) == chkp_get_zero_bounds_var ()) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " result: always pass with zero bounds\n"); + return 1; + } + else if (gimple_code (bnd_def) == GIMPLE_ASSIGN + && gimple_assign_rhs1 (bnd_def) == chkp_get_none_bounds_var ()) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " result: always fails with none bounds\n"); + return -1; + } + else if (gimple_code (bnd_def) == GIMPLE_ASSIGN + && TREE_CODE (gimple_assign_rhs1 (bnd_def)) == VAR_DECL) + { + tree bnd_var = gimple_assign_rhs1 (bnd_def); + tree var; + tree size; + + if (!DECL_INITIAL (bnd_var) + || DECL_INITIAL (bnd_var) == error_mark_node) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " result: cannot compute bounds\n"); + return 0; + } + + gcc_assert (TREE_CODE (DECL_INITIAL (bnd_var)) == ADDR_EXPR); + var = TREE_OPERAND (DECL_INITIAL (bnd_var), 0); + + bound_val.pol.create (0); + chkp_collect_value (DECL_INITIAL (bnd_var), bound_val); + if (ci->type == CHECK_UPPER_BOUND) + { + if (TREE_CODE (var) == VAR_DECL) + { + if (DECL_SIZE (var) + && !chkp_variable_size_type (TREE_TYPE (var))) + size = DECL_SIZE_UNIT (var); + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " result: cannot compute bounds\n"); + return 0; + } + } + else + { + gcc_assert (TREE_CODE (var) == STRING_CST); + size = build_int_cst (size_type_node, + TREE_STRING_LENGTH (var)); + } + + address_t size_val; + size_val.pol.create (0); + chkp_collect_value (size, size_val); + chkp_add_addr_addr (bound_val, size_val); + size_val.pol.release (); + chkp_add_addr_item (bound_val, integer_minus_one_node, NULL); + } + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " result: cannot compute bounds\n"); + return 0; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " bound value: "); + chkp_print_addr (bound_val); + fprintf (dump_file, "\n"); + } + + chkp_sub_addr_addr (bound_val, ci->addr); + + if (!chkp_is_constant_addr (bound_val, &sign)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " result: cannot compute result\n"); + + res = 0; + } + else if (sign == 0 + || (ci->type == CHECK_UPPER_BOUND && sign > 0) + || (ci->type == CHECK_LOWER_BOUND && sign < 0)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " result: always pass\n"); + + res = 1; + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " result: always fail\n"); + + res = -1; + } + + bound_val.pol.release (); + + return res; +} + +/* For bounds used in CI check if bounds are produced by + intersection and we may use outer bounds instead. If + transformation is possible then fix check statement and + recompute its info. */ +static void +chkp_use_outer_bounds_if_possible (struct check_info *ci) +{ + gimple bnd_def; + tree bnd1, bnd2, bnd_res = NULL; + int check_res1, check_res2; + + if (TREE_CODE (ci->bounds) != SSA_NAME) + return; + + bnd_def = SSA_NAME_DEF_STMT (ci->bounds); + if (gimple_code (bnd_def) != GIMPLE_CALL + || gimple_call_fndecl (bnd_def) != chkp_intersect_fndecl) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Check if bounds intersection is redundant: \n"); + fprintf (dump_file, " check: "); + print_gimple_stmt (dump_file, ci->stmt, 0, 0); + fprintf (dump_file, " intersection: "); + print_gimple_stmt (dump_file, bnd_def, 0, 0); + fprintf (dump_file, "\n"); + } + + bnd1 = gimple_call_arg (bnd_def, 0); + bnd2 = gimple_call_arg (bnd_def, 1); + + check_res1 = chkp_get_check_result (ci, bnd1); + check_res2 = chkp_get_check_result (ci, bnd2); + if (check_res1 == 1) + bnd_res = bnd2; + else if (check_res1 == -1) + bnd_res = bnd1; + else if (check_res2 == 1) + bnd_res = bnd1; + else if (check_res2 == -1) + bnd_res = bnd2; + + if (bnd_res) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " action: use "); + print_generic_expr (dump_file, bnd2, 0); + fprintf (dump_file, " instead of "); + print_generic_expr (dump_file, ci->bounds, 0); + fprintf (dump_file, "\n"); + } + + ci->bounds = bnd_res; + gimple_call_set_arg (ci->stmt, 1, bnd_res); + update_stmt (ci->stmt); + chkp_fill_check_info (ci->stmt, ci); + } +} + +/* Try to find checks whose bounds were produced by intersection + which does not affect check result. In such check outer bounds + are used instead. It allows to remove excess intersections + and helps to compare checks. */ +static void +chkp_remove_excess_intersections (void) +{ + basic_block bb; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Searching for redundant bounds intersections...\n"); + + FOR_EACH_BB_FN (bb, cfun) + { + struct bb_checks *bbc = &check_infos[bb->index]; + unsigned int no; + + /* Iterate through all found checks in BB. */ + for (no = 0; no < bbc->checks.length (); no++) + if (bbc->checks[no].stmt) + chkp_use_outer_bounds_if_possible (&bbc->checks[no]); + } +} + /* Return fast version of string function FNCODE. */ static tree chkp_get_nobnd_fndecl (enum built_in_function fncode) @@ -711,6 +1041,12 @@ chkp_opt_execute (void) and thus we put it before checks search. */ chkp_optimize_string_function_calls (); + chkp_gather_checks_info (); + + chkp_remove_excess_intersections (); + + chkp_release_check_info (); + chkp_opt_fini (); return 0;