From patchwork Wed Oct 8 19:16:58 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Enkovich X-Patchwork-Id: 397698 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 94DF61400EA for ; Thu, 9 Oct 2014 06:17:16 +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=ZWzuq9Zl3574gzeolTU+EdfO3iNOG1VUfsMNROo5bVor0oIlKN iJ40TIu2QORdkEZIBMugPEgNe1Os1JINyT8WVUBJSo+cVlGqrAQQQG+/Mk7BAX/6 uV45c+T69moZDJFcCb6vfytGJYdYRgnIZWvP83/dZIFC4NoARWSFO9Uy4= 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=lUe+hbvrd0jYjDF7v2ePyaEqssw=; b=W9Tf+nRyK+/F3eE+IFnl CuLlzIOSrw6qRFcZGY3lmCsMUb1IZoOk5mLJMh3wxkU4FUZe+2aui9sYRjwPqeN0 G7+l1REd8I3S5mFkExsAqJIKswPt3j4L8cQpFyWBMAytzvcojmS49mcn+mAD2DDm qHjkJPjMeqdDNN5SRBMJqrk= Received: (qmail 15485 invoked by alias); 8 Oct 2014 19:17:09 -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 15475 invoked by uid 89); 8 Oct 2014 19:17:08 -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-pa0-f49.google.com Received: from mail-pa0-f49.google.com (HELO mail-pa0-f49.google.com) (209.85.220.49) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Wed, 08 Oct 2014 19:17:07 +0000 Received: by mail-pa0-f49.google.com with SMTP id hz1so9415384pad.8 for ; Wed, 08 Oct 2014 12:17:05 -0700 (PDT) X-Received: by 10.70.88.197 with SMTP id bi5mr13620418pdb.80.1412795825088; Wed, 08 Oct 2014 12:17:05 -0700 (PDT) Received: from msticlxl57.ims.intel.com ([192.55.55.41]) by mx.google.com with ESMTPSA id nx6sm698802pab.46.2014.10.08.12.17.03 for (version=TLSv1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 08 Oct 2014 12:17:04 -0700 (PDT) Date: Wed, 8 Oct 2014 23:16:58 +0400 From: Ilya Enkovich To: gcc-patches@gcc.gnu.org Cc: Jeff Law Subject: [PATCH, Pointer Bounds Checker 14/x] Passes [11/n] Optimization helpers Message-ID: <20141008191658.GK13454@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 introduces structures and manipulation functions used by simple checker optimizations. Structures are used to hold checks information - type of check and checked address in a polinomial form. Thanks, Ilya --- 2014-10-08 Ilya Enkovich * tree-chkp.c (check_type): New. (pol_item): New. (address_t): New. (check_info): New. (bb_checks): New. (chkp_pol_item_compare): New. (chkp_pol_find): New. (chkp_extend_const): New. (chkp_add_addr_item): New. (chkp_sub_addr_item): New. (chkp_add_addr_addr): New. (chkp_sub_addr_addr): New. (chkp_mult_addr): New. (chkp_is_constant_addr): New. (chkp_print_addr): New. (chkp_collect_addr_value): New. (chkp_collect_value): New. (chkp_fill_check_info): New. diff --git a/gcc/tree-chkp.c b/gcc/tree-chkp.c index 6f73699..aae9681 100644 --- a/gcc/tree-chkp.c +++ b/gcc/tree-chkp.c @@ -328,10 +328,47 @@ along with GCC; see the file COPYING3. If not see typedef void (*assign_handler)(tree, tree, void *); +enum check_type +{ + CHECK_LOWER_BOUND, + CHECK_UPPER_BOUND +}; + +struct pol_item +{ + tree cst; + tree var; +}; + +struct address_t +{ + vec pol; +}; + +/* Structure to hold check informtation. */ +struct check_info +{ + /* Type of the check. */ + check_type type; + /* Address used for the check. */ + address_t addr; + /* Bounds used for the check. */ + tree bounds; + /* Check statement. Can be NULL for removed checks. */ + gimple stmt; +}; + +/* Structure to hold checks information for BB. */ +struct bb_checks +{ + vec checks; +}; + static tree chkp_get_zero_bounds (); static tree chkp_find_bounds (tree ptr, gimple_stmt_iterator *iter); static tree chkp_find_bounds_loaded (tree ptr, tree ptr_src, gimple_stmt_iterator *iter); +static void chkp_collect_value (tree ssa_name, address_t &res); static void chkp_parse_array_and_component_ref (tree node, tree *ptr, tree *elt, bool *safe, bool *bitfield, @@ -4179,6 +4216,357 @@ chkp_gate (void) || lookup_attribute ("chkp ctor", DECL_ATTRIBUTES (cfun->decl)); } +/* Comparator for pol_item structures I1 and I2 to be used + to find items with equal var. Also used for polynomial + sorting. */ +int +chkp_pol_item_compare (const void *i1, const void *i2) +{ + const struct pol_item *p1 = (const struct pol_item *)i1; + const struct pol_item *p2 = (const struct pol_item *)i2; + + if (p1->var == p2->var) + return 0; + else if (p1->var > p2->var) + return 1; + else + return -1; +} + +/* Find plynomial item in ADDR with var equal to VAR + and return its index. Return -1 if item was not + found. */ +int +chkp_pol_find (address_t &addr, tree var) +{ + int left = 0; + int right = addr.pol.length () - 1; + int n; + + while (right >= left) + { + n = (left + right) / 2; + + if (addr.pol[n].var == var + || (var && addr.pol[n].var + && TREE_CODE (var) == ADDR_EXPR + && TREE_CODE (addr.pol[n].var) == ADDR_EXPR + && TREE_OPERAND (var, 0) == TREE_OPERAND (addr.pol[n].var, 0))) + return n; + else if (addr.pol[n].var > var) + right = n - 1; + else + left = n + 1; + } + + return -1; +} + +/* Return constant CST extended to size type. */ +tree +chkp_extend_const (tree cst) +{ + if (TYPE_PRECISION (TREE_TYPE (cst)) < TYPE_PRECISION (size_type_node)) + return build_int_cst_type (size_type_node, tree_to_shwi (cst)); + + return cst; +} + +/* Add polynomial item CST * VAR to ADDR. */ +void +chkp_add_addr_item (address_t &addr, tree cst, tree var) +{ + int n = chkp_pol_find (addr, var); + + cst = chkp_extend_const (cst); + + if (n < 0) + { + struct pol_item item; + item.cst = cst; + item.var = var; + + addr.pol.safe_push (item); + addr.pol.qsort (&chkp_pol_item_compare); + } + else + { + addr.pol[n].cst = fold_build2 (PLUS_EXPR, TREE_TYPE (addr.pol[n].cst), + addr.pol[n].cst, cst); + if (TREE_CODE (addr.pol[n].cst) == INTEGER_CST + && integer_zerop (addr.pol[n].cst)) + addr.pol.ordered_remove (n); + } +} + +/* Subtract polynomial item CST * VAR from ADDR. */ +void +chkp_sub_addr_item (address_t &addr, tree cst, tree var) +{ + int n = chkp_pol_find (addr, var); + + cst = chkp_extend_const (cst); + + if (n < 0) + { + struct pol_item item; + item.cst = fold_build2 (MINUS_EXPR, TREE_TYPE (cst), + integer_zero_node, cst); + item.var = var; + + addr.pol.safe_push (item); + addr.pol.qsort (&chkp_pol_item_compare); + } + else + { + addr.pol[n].cst = fold_build2 (MINUS_EXPR, TREE_TYPE (addr.pol[n].cst), + addr.pol[n].cst, cst); + if (TREE_CODE (addr.pol[n].cst) == INTEGER_CST + && integer_zerop (addr.pol[n].cst)) + addr.pol.ordered_remove (n); + } +} + +/* Add address DELTA to ADDR. */ +void +chkp_add_addr_addr (address_t &addr, address_t &delta) +{ + unsigned int i; + for (i = 0; i < delta.pol.length (); i++) + chkp_add_addr_item (addr, delta.pol[i].cst, delta.pol[i].var); +} + +/* Subtract address DELTA from ADDR. */ +void +chkp_sub_addr_addr (address_t &addr, address_t &delta) +{ + unsigned int i; + for (i = 0; i < delta.pol.length (); i++) + chkp_sub_addr_item (addr, delta.pol[i].cst, delta.pol[i].var); +} + +/* Mutiply address ADDR by integer constant MULT. */ +void +chkp_mult_addr (address_t &addr, tree mult) +{ + unsigned int i; + for (i = 0; i < addr.pol.length (); i++) + addr.pol[i].cst = fold_build2 (MULT_EXPR, TREE_TYPE (addr.pol[i].cst), + addr.pol[i].cst, mult); +} + +/* Return 1 if we may prove ADDR has a constant value with + determined sign, which is put into *SIGN. Otherwise + return 0. */ +bool +chkp_is_constant_addr (const address_t &addr, int *sign) +{ + *sign = 0; + + if (addr.pol.length () == 0) + return true; + else if (addr.pol.length () > 1) + return false; + else if (addr.pol[0].var) + return false; + else if (integer_zerop (addr.pol[0].cst)) + *sign = 0; + else if (tree_int_cst_sign_bit (addr.pol[0].cst)) + *sign = -1; + else + *sign = 1; + + return true; +} + +/* Dump ADDR into dump_file. */ +void +chkp_print_addr (const address_t &addr) +{ + unsigned int n = 0; + for (n = 0; n < addr.pol.length (); n++) + { + if (n > 0) + fprintf (dump_file, " + "); + + if (addr.pol[n].var == NULL_TREE) + print_generic_expr (dump_file, addr.pol[n].cst, 0); + else + { + if (TREE_CODE (addr.pol[n].cst) != INTEGER_CST + || !integer_onep (addr.pol[n].cst)) + { + print_generic_expr (dump_file, addr.pol[n].cst, 0); + fprintf (dump_file, " * "); + } + print_generic_expr (dump_file, addr.pol[n].var, 0); + } + } +} + +/* Compute value of PTR and put it into address RES. + PTR has to be ADDR_EXPR. */ +void +chkp_collect_addr_value (tree ptr, address_t &res) +{ + tree obj = TREE_OPERAND (ptr, 0); + address_t addr; + + switch (TREE_CODE (obj)) + { + case INDIRECT_REF: + chkp_collect_value (TREE_OPERAND (obj, 0), res); + break; + + case MEM_REF: + chkp_collect_value (TREE_OPERAND (obj, 0), res); + addr.pol.create (0); + chkp_collect_value (TREE_OPERAND (obj, 1), addr); + chkp_add_addr_addr (res, addr); + addr.pol.release (); + break; + + case ARRAY_REF: + chkp_collect_value (build_fold_addr_expr (TREE_OPERAND (obj, 0)), res); + addr.pol.create (0); + chkp_collect_value (TREE_OPERAND (obj, 1), addr); + chkp_mult_addr (addr, array_ref_element_size (obj)); + chkp_add_addr_addr (res, addr); + addr.pol.release (); + break; + + case COMPONENT_REF: + { + tree str = TREE_OPERAND (obj, 0); + tree field = TREE_OPERAND (obj, 1); + chkp_collect_value (build_fold_addr_expr (str), res); + addr.pol.create (0); + chkp_collect_value (component_ref_field_offset (obj), addr); + chkp_add_addr_addr (res, addr); + addr.pol.release (); + if (DECL_FIELD_BIT_OFFSET (field)) + { + addr.pol.create (0); + chkp_collect_value (fold_build2 (TRUNC_DIV_EXPR, size_type_node, + DECL_FIELD_BIT_OFFSET (field), + size_int (BITS_PER_UNIT)), + addr); + chkp_add_addr_addr (res, addr); + addr.pol.release (); + } + } + break; + + default: + chkp_add_addr_item (res, integer_one_node, ptr); + break; + } +} + +/* Compute value of PTR and put it into address RES. */ +void +chkp_collect_value (tree ptr, address_t &res) +{ + gimple def_stmt; + enum gimple_code code; + enum tree_code rhs_code; + address_t addr; + tree rhs1; + + if (TREE_CODE (ptr) == INTEGER_CST) + { + chkp_add_addr_item (res, ptr, NULL); + return; + } + else if (TREE_CODE (ptr) == ADDR_EXPR) + { + chkp_collect_addr_value (ptr, res); + return; + } + else if (TREE_CODE (ptr) != SSA_NAME) + { + chkp_add_addr_item (res, integer_one_node, ptr); + return; + } + + /* Now we handle the case when polynomial is computed + for SSA NAME. */ + def_stmt = SSA_NAME_DEF_STMT (ptr); + code = gimple_code (def_stmt); + + /* Currently we do not walk through statements other + than assignment. */ + if (code != GIMPLE_ASSIGN) + { + chkp_add_addr_item (res, integer_one_node, ptr); + return; + } + + rhs_code = gimple_assign_rhs_code (def_stmt); + rhs1 = gimple_assign_rhs1 (def_stmt); + + switch (rhs_code) + { + case SSA_NAME: + case INTEGER_CST: + case ADDR_EXPR: + chkp_collect_value (rhs1, res); + break; + + case PLUS_EXPR: + case POINTER_PLUS_EXPR: + chkp_collect_value (rhs1, res); + addr.pol.create (0); + chkp_collect_value (gimple_assign_rhs2 (def_stmt), addr); + chkp_add_addr_addr (res, addr); + addr.pol.release (); + break; + + case MINUS_EXPR: + chkp_collect_value (rhs1, res); + addr.pol.create (0); + chkp_collect_value (gimple_assign_rhs2 (def_stmt), addr); + chkp_sub_addr_addr (res, addr); + addr.pol.release (); + break; + + case MULT_EXPR: + if (TREE_CODE (rhs1) == SSA_NAME + && TREE_CODE (gimple_assign_rhs2 (def_stmt)) == INTEGER_CST) + { + chkp_collect_value (rhs1, res); + chkp_mult_addr (res, gimple_assign_rhs2 (def_stmt)); + } + else if (TREE_CODE (gimple_assign_rhs2 (def_stmt)) == SSA_NAME + && TREE_CODE (rhs1) == INTEGER_CST) + { + chkp_collect_value (gimple_assign_rhs2 (def_stmt), res); + chkp_mult_addr (res, rhs1); + } + else + chkp_add_addr_item (res, integer_one_node, ptr); + break; + + default: + chkp_add_addr_item (res, integer_one_node, ptr); + break; + } +} + +/* Fill check_info structure *CI with information about + check STMT. */ +void +chkp_fill_check_info (gimple stmt, struct check_info *ci) +{ + ci->addr.pol.create (0); + ci->bounds = gimple_call_arg (stmt, 1); + chkp_collect_value (gimple_call_arg (stmt, 0), ci->addr); + ci->type = (gimple_call_fndecl (stmt) == chkp_checkl_fndecl + ? CHECK_LOWER_BOUND + : CHECK_UPPER_BOUND); + ci->stmt = stmt; +} + namespace { const pass_data pass_data_chkp =