From patchwork Mon Oct 13 13:29:35 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Enkovich X-Patchwork-Id: 399178 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 270FB140092 for ; Tue, 14 Oct 2014 00:29:54 +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=IjAuyAziYPRVKtuZ+ 2XWHfopYMBi0IPXm9rUsWTQQEhS4DRVWsoaqzpOhX8MQwl3gfCjux0zSRClVZdvD K5p+99FBd4Vbq3lGjTCR9tImsIcnyxx7sw494dLaREKd4e4XF+5IhRZpBUuk7Lpy ApyXNOJpIVnRp9hN20+P2qQQ7A= 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=cp4cTCpYFCfU7rkUUrpZQcR iDyw=; b=mj/EWH7POz9gfGX2KB1/ZSCJ//EXrkjmTE+EwpWP1P3a5C303iRT/1Z t3EfDIW1z5wqp+gm3OZGqRH86P5ujipNWfFvC39vhNwSIH5NWl8nPn6AQGHMma9m amsAdQyT8Q8FHKt7BKFiIYhcvoOKWsfBUXedATDQwtg8pkXObplU= Received: (qmail 23795 invoked by alias); 13 Oct 2014 13:29:47 -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 23783 invoked by uid 89); 13 Oct 2014 13:29:46 -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-f176.google.com Received: from mail-pd0-f176.google.com (HELO mail-pd0-f176.google.com) (209.85.192.176) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Mon, 13 Oct 2014 13:29:43 +0000 Received: by mail-pd0-f176.google.com with SMTP id fp1so5568515pdb.21 for ; Mon, 13 Oct 2014 06:29:42 -0700 (PDT) X-Received: by 10.66.163.65 with SMTP id yg1mr23817657pab.33.1413206981987; Mon, 13 Oct 2014 06:29:41 -0700 (PDT) Received: from msticlxl57.ims.intel.com (fmdmzpr04-ext.fm.intel.com. [192.55.55.39]) by mx.google.com with ESMTPSA id f12sm11402607pat.36.2014.10.13.06.29.39 for (version=TLSv1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 13 Oct 2014 06:29:41 -0700 (PDT) Date: Mon, 13 Oct 2014 17:29:35 +0400 From: Ilya Enkovich To: Jeff Law Cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH, Pointer Bounds Checker 14/x] Passes [11/n] Optimization helpers Message-ID: <20141013132935.GE62841@msticlxl57.ims.intel.com> References: <20141008191658.GK13454@msticlxl57.ims.intel.com> <5436CF6F.30809@redhat.com> <20141010142458.GB61068@msticlxl57.ims.intel.com> <543805EF.9050906@redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <543805EF.9050906@redhat.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes On 10 Oct 10:14, Jeff Law wrote: > On 10/10/14 08:24, Ilya Enkovich wrote: > >On 09 Oct 12:09, Jeff Law wrote: > >>On 10/08/14 13:16, Ilya Enkovich wrote: > >>>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. > >>> > >>> > >>>+/* Find plynomial item in ADDR with var equal to VAR > >>s/plynomial/polynomial/ > >> > >>With nit fixed and functions moved into whatever new file gets > >>created for the optimization work this will be OK. > >>jeff > > > >Thanks for review! Here is a fixed version. > > > >Ilya > >-- > >2014-10-10 Ilya Enkovich > > > > * tree-chkp-opt.c: New. > > * Makefile.in (OBJS): Add tree-chkp-opt.o. > > > > > >diff --git a/gcc/Makefile.in b/gcc/Makefile.in > >index d8c8488..cd45b29 100644 > >--- a/gcc/Makefile.in > >+++ b/gcc/Makefile.in > >@@ -1389,6 +1389,7 @@ OBJS = \ > > tree-parloops.o \ > > tree-phinodes.o \ > > tree-chkp.o \ > >+ tree-chkp-opt.o \ > > tree-predcom.o \ > > tree-pretty-print.o \ > > tree-profile.o \ > >diff --git a/gcc/tree-chkp-opt.c b/gcc/tree-chkp-opt.c > >new file mode 100644 > >index 0000000..103c4bb > >--- /dev/null > >+++ b/gcc/tree-chkp-opt.c > >@@ -0,0 +1,463 @@ > >+/* Pointer Bounds Checker optimization pass. > >+ Copyright (C) 2014 Free Software Foundation, Inc. > >+ Contributed by Ilya Enkovich (ilya.enkovich@intel.com) > >+ > >+This file is part of GCC. > >+ > >+GCC is free software; you can redistribute it and/or modify it under > >+the terms of the GNU General Public License as published by the Free > >+Software Foundation; either version 3, or (at your option) any later > >+version. > >+ > >+GCC is distributed in the hope that it will be useful, but WITHOUT ANY > >+WARRANTY; without even the implied warranty of MERCHANTABILITY or > >+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License > >+for more details. > >+ > >+You should have received a copy of the GNU General Public License > >+along with GCC; see the file COPYING3. If not see > >+. */ > >+ > >+#include "config.h" > >+#include "system.h" > >+#include "coretypes.h" > >+#include "tree-core.h" > >+#include "stor-layout.h" > >+#include "varasm.h" > >+#include "tree.h" > >+#include "target.h" > >+#include "tree-iterator.h" > >+#include "tree-cfg.h" > >+#include "langhooks.h" > >+#include "tree-pass.h" > >+#include "hashtab.h" > >+#include "diagnostic.h" > >+#include "ggc.h" > >+#include "output.h" > >+#include "internal-fn.h" > >+#include "is-a.h" > >+#include "predict.h" > >+#include "cfgloop.h" > >+#include "stringpool.h" > >+#include "tree-ssa-alias.h" > >+#include "tree-ssanames.h" > >+#include "tree-ssa-operands.h" > >+#include "tree-ssa-address.h" > >+#include "tree-ssa.h" > >+#include "ipa-inline.h" > >+#include "basic-block.h" > >+#include "tree-ssa-loop-niter.h" > >+#include "gimple-expr.h" > >+#include "gimple.h" > >+#include "tree-phinodes.h" > >+#include "gimple-ssa.h" > >+#include "ssa-iterators.h" > >+#include "gimple-pretty-print.h" > >+#include "gimple-iterator.h" > >+#include "gimplify.h" > >+#include "gimplify-me.h" > >+#include "print-tree.h" > >+#include "expr.h" > >+#include "tree-ssa-propagate.h" > >+#include "gimple-fold.h" > >+#include "gimple-walk.h" > >+#include "tree-dfa.h" > >+#include "tree-chkp.h" > Thanks. Looks good. > > As a follow-up, can you try to trim down what appear to be the > over-zealous includes? It's a minor thing, but we are trying to be > a bit saner about that kind of stuff than we've been in the past. > > If you've already done that, then, well, we've clearly still got a > ways to go. For example, I can't see why you'd need output.h here > :-0 > > > Jeff Thanks for review! This includes list is from tree-chkp.c and surely is reducible. I also revisited tree-chkp.c and removed few includes from there. Here is a new version. Ilya --- 2014-10-10 Ilya Enkovich * tree-chkp-opt.c: New. * Makefile.in (OBJS): Add tree-chkp-opt.o. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index d8c8488..cd45b29 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1389,6 +1389,7 @@ OBJS = \ tree-parloops.o \ tree-phinodes.o \ tree-chkp.o \ + tree-chkp-opt.o \ tree-predcom.o \ tree-pretty-print.o \ tree-profile.o \ diff --git a/gcc/tree-chkp-opt.c b/gcc/tree-chkp-opt.c new file mode 100644 index 0000000..08be848 --- /dev/null +++ b/gcc/tree-chkp-opt.c @@ -0,0 +1,447 @@ +/* Pointer Bounds Checker optimization pass. + Copyright (C) 2014 Free Software Foundation, Inc. + Contributed by Ilya Enkovich (ilya.enkovich@intel.com) + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree-core.h" +#include "tree.h" +#include "target.h" +#include "tree-cfg.h" +#include "tree-pass.h" +#include "is-a.h" +#include "cfgloop.h" +#include "stringpool.h" +#include "tree-ssa-alias.h" +#include "tree-ssanames.h" +#include "tree-ssa-operands.h" +#include "tree-ssa-address.h" +#include "tree-ssa.h" +#include "basic-block.h" +#include "tree-ssa-loop-niter.h" +#include "gimple-expr.h" +#include "gimple.h" +#include "tree-phinodes.h" +#include "gimple-ssa.h" +#include "ssa-iterators.h" +#include "gimple-pretty-print.h" +#include "gimple-iterator.h" +#include "gimplify.h" +#include "gimplify-me.h" +#include "expr.h" +#include "tree-chkp.h" + +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 void chkp_collect_value (tree ssa_name, address_t &res); + +#define chkp_bndmk_fndecl \ + (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDMK)) +#define chkp_intersect_fndecl \ + (targetm.builtin_chkp_function (BUILT_IN_CHKP_INTERSECT)) +#define chkp_checkl_fndecl \ + (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDCL)) +#define chkp_checku_fndecl \ + (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDCU)) + +/* Comparator for pol_item structures I1 and I2 to be used + to find items with equal var. Also used for polynomial + sorting. */ +static 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 polynomial item in ADDR with var equal to VAR + and return its index. Return -1 if item was not + found. */ +static 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. */ +static 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. */ +static 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. */ +static 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. */ +static 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. */ +static 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. */ +static 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. */ +static 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. */ +static 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. */ +static 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. */ +static 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. */ +static 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; +}