From patchwork Fri Oct 10 14:24: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: 398614 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 066EC1400AB for ; Sat, 11 Oct 2014 01:25:20 +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=EqlKPWOgzDoG98qyl /oXW6TyBaOSAfG4uDVRwNQplE4eqJTF8dVv19zZVrj7uKlPNysvn5DHjDJP7tYkU YKH/CFMS9j0hqt16ZlwCL2BFY7qv39c+9dqOplJs+ki4ZPTIhCp6qYiFXdd4DQFw zRATiVIHAxiTtSgzJFkuxh9g4s= 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=5O88c5ulDf587Z9PGYsLXYX ARlw=; b=GgJz+K3e0cyMZR4XQ5mCaBSsDZmN7GRf/H0VePJXC4mBT2pJUqK8GxR eEr1i43Noord++JXJE4i8dviQCGcYVv1QwyvNaR0Y83xYFmbzrNG7t56ubjBNhz1 a1Vpqw3NhXtCiwKS79HQvo3mJ+mC1sKTj387AHR3AbayXQTMmirA= Received: (qmail 6651 invoked by alias); 10 Oct 2014 14:25:13 -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 6639 invoked by uid 89); 10 Oct 2014 14:25:13 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.5 required=5.0 tests=AWL, BAYES_50, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-pd0-f179.google.com Received: from mail-pd0-f179.google.com (HELO mail-pd0-f179.google.com) (209.85.192.179) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Fri, 10 Oct 2014 14:25:07 +0000 Received: by mail-pd0-f179.google.com with SMTP id r10so1737636pdi.38 for ; Fri, 10 Oct 2014 07:25:05 -0700 (PDT) X-Received: by 10.66.173.141 with SMTP id bk13mr4510512pac.137.1412951105779; Fri, 10 Oct 2014 07:25:05 -0700 (PDT) Received: from msticlxl57.ims.intel.com ([192.55.54.40]) by mx.google.com with ESMTPSA id gh3sm3669430pbc.16.2014.10.10.07.25.03 for (version=TLSv1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Fri, 10 Oct 2014 07:25:05 -0700 (PDT) Date: Fri, 10 Oct 2014 18:24:58 +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: <20141010142458.GB61068@msticlxl57.ims.intel.com> References: <20141008191658.GK13454@msticlxl57.ims.intel.com> <5436CF6F.30809@redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <5436CF6F.30809@redhat.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes 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" + +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; +}