From patchwork Mon May 16 00:45:58 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 67823 Delivered-To: patch@linaro.org Received: by 10.140.92.199 with SMTP id b65csp1285665qge; Sun, 15 May 2016 17:46:30 -0700 (PDT) X-Received: by 10.98.24.88 with SMTP id 85mr41745692pfy.52.1463359590697; Sun, 15 May 2016 17:46:30 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id z6si41858503pas.133.2016.05.15.17.46.30 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 15 May 2016 17:46:30 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-427325-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org; spf=pass (google.com: domain of gcc-patches-return-427325-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-427325-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:date:message-id:subject:from:to:content-type; q= dns; s=default; b=X8LJqdqERgkQ9jWiZeZU72jQppCqFFHhc03l7po/Sgl7XI QlBWVI8ceMkyvoURbOeiIv9RLCJe8c+nb0COcB4k9+x0JjkbYLwpdT89/M/uD+8d SDfTZBKC2+kEz5pxsNyC4lfUjrro9fZvPkk4Y8aVtOZ9q96GhBjsggFRicVYU= 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 :mime-version:date:message-id:subject:from:to:content-type; s= default; bh=Ma1CfBN3JSckyjxqUz51BcSTdok=; b=uHwprxxWdcj4D0SMG7gB nvX3sLXCSq77r+KkF0cbY0FzA9GBN+QMvXxhUyZN1IMUvjl8lFCOB2qfKjxOBNXi 8OkoV/dOstmdcSNwVD7LLHeLeZ/8xgkq/JfZKlM0hyP2t0kLddt4W3iVNyz2r6Np /ibmEMH7/wfXVy2pflceZgw= Received: (qmail 89895 invoked by alias); 16 May 2016 00:46: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 87515 invoked by uid 89); 16 May 2016 00:46:11 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=FORM, Sign, sk:people, sk:people. X-HELO: mail-qg0-f53.google.com Received: from mail-qg0-f53.google.com (HELO mail-qg0-f53.google.com) (209.85.192.53) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Mon, 16 May 2016 00:46:00 +0000 Received: by mail-qg0-f53.google.com with SMTP id f74so83160293qge.2 for ; Sun, 15 May 2016 17:46:00 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to; bh=vgrSG3vZXOdBL7j0cioC8Q1OPxfd9dHeQhQTFyuz3dw=; b=Z7yqdQRuDtuLJ9is8i4jEynPmhKeLGDQbsZp9MQszgt2lTaf5cGG3tIn7q7fTLAoLr vllqRV+2sGFmcJSC+31EiWqa6KD/Jrm1aZgPZzbmaLJAjXmrsEZXJtvlLGTov51Ocutv QcRguxZIVS0EA96iLeI3/pJi3S+Q1A8wRPE1/HnSEO52p9ye7DENbNDjEhsgzCj1dii4 V7CgSI0GBqJ1SIJ80Js0gYn0BU/2Srd15m0H2jojqsfHHwjN9CxCebMBbuR78X3rfZwu SnxhUzYdpg/KCNq1xTO+CdONd7mBwDNbrxIYA0tf4KiedDhiEGf1m6JqEqD3ikPdT8Q3 Pq0w== X-Gm-Message-State: AOPr4FUE6ZRP8PXzuBu+p4e3luUu8a445hVgaftLaD1RGgEIc3KT5T3bVmSnLw+H+FPsNjnKZyCd2yWfq+NxbKbF MIME-Version: 1.0 X-Received: by 10.140.163.85 with SMTP id j82mr27981258qhj.40.1463359558302; Sun, 15 May 2016 17:45:58 -0700 (PDT) Received: by 10.200.42.71 with HTTP; Sun, 15 May 2016 17:45:58 -0700 (PDT) Date: Mon, 16 May 2016 10:45:58 +1000 Message-ID: Subject: [RFC] Type promotion pass and elimination of zext/sext From: Kugan Vivekanandarajah To: Richard Biener , "gcc-patches@gcc.gnu.org" X-IsSubscribed: yes Hi Richard, Now that stage1 is open, I would like to get the type promotion passes reviewed again. I have tested the patches on aarch64, x86-64, and ppc64le without any new execution failures. There some test-cases that fails for patterns. I will address them after getting feedback on the basic structure. I am attaching the pass itself for the review. Other needed patches are in http://people.linaro.org/~kugan.vivekanandarajah/pass/ You reviewed some of them. But I will post again after the main pass is acceptable. They all have to go in together. Couple of changes from last time: 1. When we promote SSA as part of promote_ssa, we either promote the definition. Or create a copy stmt that is inserted after the stmt that define it. i.e, we want to promote the SSA and reflect the promotion on all the uses (we promote in place). We do this because, we don’t want to change all the uses. +/* Promote definition DEF to promoted type. If the stmt that defines def + is def_stmt, make the type of def promoted type. If the stmt is such + that, result of the def_stmt cannot be of promoted type, create a new_def + of the original_type and make the def_stmt assign its value to newdef. + Then, create a NOP_EXPR to convert new_def to def of promoted type. + + For example, for stmt with original_type char and promoted_type int: + char _1 = mem; + becomes: + char _2 = mem; + int _1 = (int)_2; + + If the def_stmt allows def to be promoted, promote def in-place + (and its arguments when needed). + + For example: + char _3 = _1 + _2; + becomes: + int _3 = _1 + _2; + Here, _1 and _2 will also be promoted. */ + However, if the defining stmt has to be the last stmt in the basic block (eg, stmt that can throw), and if there is more than one normal edges where we use this value, we cant insert the copy in all the edges. Please note that the copy stmt copes the value to promoted SSA with the same name. Therefore I had to return false in this case for promote_ssa and fixup uses. I ran into this while testing ppc64le. I am sure it can happen in other cases. 2. When the SSA defining statement is such that we cannot promote the definition as part of the stmt and we make a copy, I am also recording the original type copy and promoted copy to so that we can use them when we need. This can be improved. I will do that based on the feedback. Please let me know what you thing. Thanks, Kugan >From 332e0e9f938c6af50e826d8224d07ebf3678a0e0 Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah Date: Fri, 13 May 2016 13:41:01 +1000 Subject: [PATCH 4/4] Add new type promotion pass --- gcc/ChangeLog | 10 + gcc/Makefile.in | 1 + gcc/common.opt | 4 + gcc/doc/invoke.texi | 10 + gcc/gimple-ssa-type-promote.c | 958 ++++++++++++++++++++++++++++++++++++++++++ gcc/passes.def | 1 + gcc/timevar.def | 1 + gcc/tree-pass.h | 1 + 8 files changed, 986 insertions(+) create mode 100644 gcc/gimple-ssa-type-promote.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b31a444..5f2a90c 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,15 @@ 2016-05-12 Kugan Vivekanandarajah + * Makefile.in: Add gimple-ssa-type-promote.o. + * common.opt: New option -ftree-type-promote. + * doc/invoke.texi: Document -ftree-type-promote. + * gimple-ssa-type-promote.c: New file. + * passes.def: Define new pass_type_promote. + * timevar.def: Define new TV_TREE_TYPE_PROMOTE. + * tree-pass.h (make_pass_type_promote): New. + +2016-03-31 Kugan Vivekanandarajah + * auto-profile.c (afdo_propagate_circuit): Initialize only_one. * tree-ssa-uninit.c (normalize_one_pred): Handle SEXT_EXPR. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 6c5adc0..e00750c 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1522,6 +1522,7 @@ OBJS = \ tree-vect-slp.o \ tree-vectorizer.o \ tree-vrp.o \ + gimple-ssa-type-promote.o \ tree.o \ valtrack.o \ value-prof.o \ diff --git a/gcc/common.opt b/gcc/common.opt index 682cb41..f891c9d 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -2467,6 +2467,10 @@ Common Var(flag_unconstrained_commons) Optimization Assume common declarations may be overridden with ones with a larger trailing array. +ftree-type-promote +Common Report Var(flag_tree_type_promote) Init(1) Optimization +Perform Type Promotion on trees. + funit-at-a-time Common Report Var(flag_unit_at_a_time) Init(1) Compile whole compilation unit at a time. diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 1176d12..0b5a3e9 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -7619,6 +7619,16 @@ Split paths leading to loop backedges. This can improve dead code elimination and common subexpression elimination. This is enabled by default at @option{-O2} and above. +@item -ftree-type-promote +@opindex ftree-type-promote +This pass applies type promotion to SSA names in the function and +inserts appropriate truncations to preserve the semantics. Idea of +this pass is to promote operations such a way that we can minimise +generation of subreg in RTL, that intern results in removal of +redundant zero/sign extensions. + +This optimization is enabled by default. + @item -fsplit-ivs-in-unroller @opindex fsplit-ivs-in-unroller Enables expression of values of induction variables in later iterations diff --git a/gcc/gimple-ssa-type-promote.c b/gcc/gimple-ssa-type-promote.c new file mode 100644 index 0000000..319e63e --- /dev/null +++ b/gcc/gimple-ssa-type-promote.c @@ -0,0 +1,958 @@ +/* Type promotion of SSA names to minimise redundant zero/sign extension. + Copyright (C) 2015-2016 Free Software Foundation, Inc. + +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 "backend.h" +#include "hash-set.h" +#include "machmode.h" +#include "vec.h" +#include "double-int.h" +#include "input.h" +#include "symtab.h" +#include "wide-int.h" +#include "inchash.h" +#include "tree.h" +#include "fold-const.h" +#include "stor-layout.h" +#include "predict.h" +#include "function.h" +#include "dominance.h" +#include "cfg.h" +#include "basic-block.h" +#include "tree-ssa-alias.h" +#include "gimple-fold.h" +#include "tree-eh.h" +#include "gimple-expr.h" +#include "is-a.h" +#include "gimple.h" +#include "gimple-iterator.h" +#include "gimple-ssa.h" +#include "tree-phinodes.h" +#include "ssa-iterators.h" +#include "stringpool.h" +#include "tree-ssanames.h" +#include "tree-pass.h" +#include "gimple-pretty-print.h" +#include "langhooks.h" +#include "sbitmap.h" +#include "domwalk.h" +#include "tree-dfa.h" +#include "tree-ssa-loop-niter.h" + +/* This pass applies type promotion to SSA names in the function and + inserts appropriate truncations. Idea of this pass is to promote operations + such a way that we can minimise generation of subreg in RTL, + that in turn results in removal of redundant zero/sign extensions. This pass + will run prior to The VRP and DOM such that they will be able to optimise + redundant truncations and extensions. This is based on the discussion from + https://gcc.gnu.org/ml/gcc-patches/2014-09/msg00472.html. +*/ + +/* Structure to hold the type and promoted type for promoted ssa variables. */ +struct ssa_name_info +{ + tree ssa; /* Name of the SSA_NAME. */ + tree val_1; /* Value in original type, if present. */ + tree type; /* Original type of ssa. */ + tree promoted_type; /* Promoted type of ssa. */ +}; + +/* Obstack for ssa_name_info. */ +static struct obstack ssa_name_info_obstack; + +static unsigned n_ssa_val; +static sbitmap ssa_to_be_promoted_bitmap; +static hash_map *ssa_name_info_map; + +/* Is the type precision ok for promition. */ +static bool +type_precision_ok (tree type) +{ + return (TYPE_PRECISION (type) + == GET_MODE_PRECISION (TYPE_MODE (type))); +} + +/* Return the promoted type for TYPE. */ +static tree +get_promoted_type (tree type) +{ + tree promoted_type; + enum machine_mode mode; + int uns; + + if (POINTER_TYPE_P (type) + || !INTEGRAL_TYPE_P (type) + || !type_precision_ok (type)) + return type; + + mode = TYPE_MODE (type); +#ifdef PROMOTE_MODE + uns = TYPE_SIGN (type); + PROMOTE_MODE (mode, uns, type); +#endif + uns = TYPE_SIGN (type); + if (TYPE_PRECISION (type) == GET_MODE_PRECISION (mode)) + return type; + promoted_type + = build_nonstandard_integer_type (GET_MODE_PRECISION (mode), + uns); + gcc_assert (TYPE_PRECISION (promoted_type) == GET_MODE_PRECISION (mode)); + return promoted_type; +} + +/* Return true if ssa NAME is already considered for promotion. */ +static bool +ssa_promoted_p (tree name) +{ + gcc_assert (TREE_CODE (name) == SSA_NAME); + unsigned int index = SSA_NAME_VERSION (name); + if (index < n_ssa_val) + return bitmap_bit_p (ssa_to_be_promoted_bitmap, index); + return true; +} + +/* Set ssa NAME as considered for promotion. */ +static void +set_ssa_promoted (tree name) +{ + gcc_assert (TREE_CODE (name) == SSA_NAME); + unsigned int index = SSA_NAME_VERSION (name); + if (index < n_ssa_val) + bitmap_set_bit (ssa_to_be_promoted_bitmap, index); +} + +/* Return true if the tree CODE does not require the propmoted operand + to be truncated (when stray bits are set beyond the original type in + promoted mode) to preserve the semantics. */ +static bool +not_needed_truncated_operand_p (enum tree_code code) +{ + if (TREE_CODE_CLASS (code) == tcc_comparison + || code == TRUNC_DIV_EXPR + || code == CEIL_DIV_EXPR + || code == FLOOR_DIV_EXPR + || code == ROUND_DIV_EXPR + || code == TRUNC_MOD_EXPR + || code == CEIL_MOD_EXPR + || code == FLOOR_MOD_EXPR + || code == ROUND_MOD_EXPR + || code == LSHIFT_EXPR + || code == RSHIFT_EXPR + || code == MAX_EXPR + || code == MIN_EXPR) + return false; + else + return true; +} + +/* Return true if LHS will be promoted later. */ +static bool +tobe_promoted_p (tree lhs) +{ + if (TREE_CODE (lhs) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (lhs)) + && !VECTOR_TYPE_P (TREE_TYPE (lhs)) + && !POINTER_TYPE_P (TREE_TYPE (lhs)) + && !ssa_promoted_p (lhs) + && (get_promoted_type (TREE_TYPE (lhs)) + != TREE_TYPE (lhs))) + return true; + else + return false; +} + +/* Convert and sign-extend constant CST to TYPE. */ +static tree +fold_convert_sext (tree type, tree cst) +{ + wide_int wi_cons = fold_convert (type, cst); + wi_cons = wi::ext (wi_cons, TYPE_PRECISION (TREE_TYPE (cst)), SIGNED); + return wide_int_to_tree (type, wi_cons); +} + +/* Promote constants in STMT to TYPE. */ + +static void +promote_cst_in_stmt (gimple *stmt, tree type) +{ + tree op; + ssa_op_iter iter; + use_operand_p oprnd; + int index; + tree op0, op1; + + switch (gimple_code (stmt)) + { + case GIMPLE_ASSIGN: + if (gimple_assign_rhs_code (stmt) == COND_EXPR + && TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt)) == 2) + { + /* Promote INTEGER_CST that are tcc_compare arguments. */ + op = gimple_assign_rhs1 (stmt); + op0 = TREE_OPERAND (op, 0); + op1 = TREE_OPERAND (op, 1); + if (TREE_TYPE (op0) != TREE_TYPE (op1)) + { + if (TREE_CODE (op0) == INTEGER_CST) + TREE_OPERAND (op, 0) = fold_convert (type, op0); + if (TREE_CODE (op1) == INTEGER_CST) + TREE_OPERAND (op, 1) = fold_convert (type, op1); + } + } + /* Promote INTEGER_CST in GIMPLE_ASSIGN. */ + if (not_needed_truncated_operand_p (gimple_assign_rhs_code (stmt))) + { + op = gimple_assign_rhs3 (stmt); + if (op && TREE_CODE (op) == INTEGER_CST) + gimple_assign_set_rhs3 (stmt, fold_convert_sext (type, op)); + op = gimple_assign_rhs1 (stmt); + if (op && TREE_CODE (op) == INTEGER_CST) + gimple_assign_set_rhs1 (stmt, fold_convert_sext (type, op)); + op = gimple_assign_rhs2 (stmt); + if (op && TREE_CODE (op) == INTEGER_CST) + gimple_assign_set_rhs2 (stmt, fold_convert_sext (type, op)); + } + else + { + op = gimple_assign_rhs3 (stmt); + if (op && TREE_CODE (op) == INTEGER_CST) + gimple_assign_set_rhs3 (stmt, fold_convert (type, op)); + op = gimple_assign_rhs1 (stmt); + if (op && TREE_CODE (op) == INTEGER_CST) + gimple_assign_set_rhs1 (stmt, fold_convert (type, op)); + op = gimple_assign_rhs2 (stmt); + if (op && TREE_CODE (op) == INTEGER_CST) + gimple_assign_set_rhs2 (stmt, fold_convert (type, op)); + } + break; + + case GIMPLE_PHI: + { + /* Promote INTEGER_CST arguments to GIMPLE_PHI. */ + gphi *phi = as_a (stmt); + FOR_EACH_PHI_ARG (oprnd, phi, iter, SSA_OP_USE) + { + op = USE_FROM_PTR (oprnd); + index = PHI_ARG_INDEX_FROM_USE (oprnd); + if (TREE_CODE (op) == INTEGER_CST) + SET_PHI_ARG_DEF (phi, index, fold_convert (type, op)); + } + } + break; + + case GIMPLE_COND: + { + /* Promote INTEGER_CST that are GIMPLE_COND arguments. */ + gcond *cond = as_a (stmt); + op = gimple_cond_lhs (cond); + if (op && TREE_CODE (op) == INTEGER_CST) + gimple_cond_set_lhs (cond, fold_convert (type, op)); + + op = gimple_cond_rhs (cond); + if (op && TREE_CODE (op) == INTEGER_CST) + gimple_cond_set_rhs (cond, fold_convert (type, op)); + } + break; + + default: + gcc_unreachable (); + } +} + +/* Zero/sign extend VAR and truncate to INNER_TYPE. Assign the zero/sign + extended value in NEW_VAR. Gimple statement that performs the zero/sign + extension is returned. */ + +static gimple * +zero_sign_extend_stmt (tree new_var, tree var, tree inner_type) +{ + gcc_assert (TYPE_PRECISION (TREE_TYPE (var)) + == TYPE_PRECISION (TREE_TYPE (new_var))); + gcc_assert (TYPE_PRECISION (TREE_TYPE (var)) > TYPE_PRECISION (inner_type)); + gimple *stmt; + + if (TYPE_UNSIGNED (inner_type)) + { + /* Zero extend. */ + tree cst + = wide_int_to_tree (TREE_TYPE (var), + wi::mask (TYPE_PRECISION (inner_type), false, + TYPE_PRECISION (TREE_TYPE (var)))); + stmt = gimple_build_assign (new_var, BIT_AND_EXPR, var, cst); + } + else + /* Sign extend. */ + stmt = gimple_build_assign (new_var, SEXT_EXPR, var, + build_int_cst (TREE_TYPE (var), + TYPE_PRECISION (inner_type))); + return stmt; +} + +/* Copy default ssa definition FORM to TO. Used as a helper before promoting + the SSA. */ +static void +copy_default_ssa (tree to, tree from) +{ + SET_SSA_NAME_VAR_OR_IDENTIFIER (to, SSA_NAME_VAR (from)); + SSA_NAME_DEF_STMT (to) = SSA_NAME_DEF_STMT (from); + SET_SSA_NAME_VAR_OR_IDENTIFIER (from, NULL_TREE); + SSA_NAME_IS_DEFAULT_DEF (from) = 0; +} + +/* Promote definition DEF to promoted type. If the stmt that defines def + is def_stmt, make the type of def promoted type. If the stmt is such + that, result of the def_stmt cannot be of promoted type, create a new_def + of the original_type and make the def_stmt assign its value to newdef. + Then, create a NOP_EXPR to convert new_def to def of promoted type. + + For example, for stmt with original_type char and promoted_type int: + char _1 = mem; + becomes: + char _2 = mem; + int _1 = (int)_2; + + If the def_stmt allows def to be promoted, promote def in-place + (and its arguments when needed). + + For example: + char _3 = _1 + _2; + becomes: + int _3 = _1 + _2; + Here, _1 and _2 will also be promoted. */ + +static bool +promote_ssa (tree def, gimple_stmt_iterator *gsi) +{ + gimple *def_stmt = SSA_NAME_DEF_STMT (def); + gimple *copy_stmt = NULL; + gimple_stmt_iterator gsi2; + tree original_type = TREE_TYPE (def); + tree new_def = NULL_TREE; + ssa_name_info *info; + bool do_not_promote = false; + tree promoted_type = get_promoted_type (TREE_TYPE (def)); + + info = (ssa_name_info *) obstack_alloc (&ssa_name_info_obstack, + sizeof (ssa_name_info)); + info->type = original_type; + info->promoted_type = promoted_type; + info->ssa = def; + info->val_1 = NULL_TREE; + ssa_name_info_map->put (def, info); + + switch (gimple_code (def_stmt)) + { + case GIMPLE_PHI: + { + /* Promote def by fixing its type and make def anonymous. */ + TREE_TYPE (def) = promoted_type; + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + promote_cst_in_stmt (def_stmt, promoted_type); + break; + } + + case GIMPLE_ASM: + { + gasm *asm_stmt = as_a (def_stmt); + for (unsigned int i = 0; i < gimple_asm_noutputs (asm_stmt); ++i) + { + /* Promote def and copy (i.e. convert) the value defined + by asm to def. */ + tree link = gimple_asm_output_op (asm_stmt, i); + tree op = TREE_VALUE (link); + if (op == def) + { + new_def = copy_ssa_name (def); + set_ssa_promoted (new_def); + copy_default_ssa (new_def, def); + TREE_VALUE (link) = new_def; + gimple_asm_set_output_op (asm_stmt, i, link); + + TREE_TYPE (def) = promoted_type; + copy_stmt = gimple_build_assign (def, NOP_EXPR, new_def); + SSA_NAME_IS_DEFAULT_DEF (new_def) = 0; + gimple_set_location (copy_stmt, gimple_location (def_stmt)); + gsi2 = gsi_for_stmt (def_stmt); + gsi_insert_after (&gsi2, copy_stmt, GSI_NEW_STMT); + break; + } + } + break; + } + + case GIMPLE_NOP: + { + gcc_unreachable (); + } + + case GIMPLE_ASSIGN: + { + enum tree_code code = gimple_assign_rhs_code (def_stmt); + tree rhs = gimple_assign_rhs1 (def_stmt); + /* If SSA defintion in DEF_STMT cannot be promoted. */ + if (gimple_vuse (def_stmt) != NULL_TREE + || gimple_vdef (def_stmt) != NULL_TREE + || (ANY_INTEGRAL_TYPE_P (TREE_TYPE (def)) + && !operation_no_trapping_overflow (TREE_TYPE (def), code)) + || TREE_CODE_CLASS (code) == tcc_reference + || TREE_CODE_CLASS (code) == tcc_comparison + || code == LROTATE_EXPR + || code == RROTATE_EXPR + || code == VIEW_CONVERT_EXPR + || code == REALPART_EXPR + || code == IMAGPART_EXPR + || code == REDUC_PLUS_EXPR + || code == REDUC_MAX_EXPR + || code == REDUC_MIN_EXPR + || !INTEGRAL_TYPE_P (TREE_TYPE (rhs))) + { + do_not_promote = true; + } + else if (CONVERT_EXPR_CODE_P (code)) + { + if (!type_precision_ok (TREE_TYPE (rhs))) + { + do_not_promote = true; + } + else if (types_compatible_p (TREE_TYPE (rhs), promoted_type)) + { + /* As we travel statements in dominated order, arguments + of def_stmt will be visited before visiting def. If RHS + is already promoted and type is compatible, we can convert + them into ZERO/SIGN EXTEND stmt. */ + ssa_name_info *info = ssa_name_info_map->get_or_insert (rhs); + tree type; + if (info == NULL) + type = TREE_TYPE (rhs); + else + type = info->type; + if ((TYPE_PRECISION (original_type) + > TYPE_PRECISION (type)) + || (TYPE_UNSIGNED (original_type) + != TYPE_UNSIGNED (type))) + { + if (TYPE_PRECISION (original_type) < TYPE_PRECISION (type)) + type = original_type; + gcc_assert (type != NULL_TREE); + TREE_TYPE (def) = promoted_type; + copy_stmt = zero_sign_extend_stmt (def, rhs, type); + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + gsi_replace (gsi, copy_stmt, false); + } + else + { + TREE_TYPE (def) = promoted_type; + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + } + } + else + { + /* If RHS is not promoted OR their types are not + compatible, create NOP_EXPR that converts + RHS to promoted DEF type and perform a + ZERO/SIGN EXTEND to get the required value + from RHS. */ + ssa_name_info *info = ssa_name_info_map->get_or_insert (rhs); + if (info != NULL) + { + tree type = info->type; + new_def = copy_ssa_name (rhs); + SET_SSA_NAME_VAR_OR_IDENTIFIER (new_def, NULL_TREE); + TREE_TYPE (def) = promoted_type; + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + copy_stmt = zero_sign_extend_stmt (new_def, rhs, type); + gimple_set_location (copy_stmt, gimple_location (def_stmt)); + gsi2 = gsi_for_stmt (def_stmt); + gsi_insert_before (&gsi2, copy_stmt, GSI_NEW_STMT); + gassign *new_def_stmt = gimple_build_assign (def, code, new_def); + gsi_replace (gsi, new_def_stmt, false); + } + else + { + TREE_TYPE (def) = promoted_type; + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + } + } + } + else + { + /* Promote def by fixing its type and make def anonymous. */ + promote_cst_in_stmt (def_stmt, promoted_type); + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + TREE_TYPE (def) = promoted_type; + } + break; + } + + default: + do_not_promote = true; + break; + } + + if (do_not_promote) + { + /* Promote def and copy (i.e. convert) the value defined + by the stmt that cannot be promoted. */ + if (lookup_stmt_eh_lp (def_stmt) > 0 + || (gimple_code (def_stmt) == GIMPLE_CALL + && gimple_call_ctrl_altering_p (def_stmt))) + { + edge_iterator ei; + edge e; + int count = 0; + + FOR_EACH_EDGE (e, ei, gimple_bb (def_stmt)->succs) + { + if (!(e->flags & EDGE_ABNORMAL)) + count ++; + } + + if (count != 1) + { + info->val_1 = def; + return false; + } + + new_def = copy_ssa_name (def); + set_ssa_promoted (new_def); + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + TREE_TYPE (def) = promoted_type; + gimple_set_lhs (def_stmt, new_def); + copy_stmt = gimple_build_assign (def, NOP_EXPR, new_def); + gimple_set_location (copy_stmt, gimple_location (def_stmt)); + gsi_insert_on_edge (FALLTHRU_EDGE (gimple_bb (def_stmt)), + copy_stmt); + info->val_1 = new_def; + } + else + { + new_def = copy_ssa_name (def); + set_ssa_promoted (new_def); + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + TREE_TYPE (def) = promoted_type; + gimple_set_lhs (def_stmt, new_def); + copy_stmt = gimple_build_assign (def, NOP_EXPR, new_def); + gimple_set_location (copy_stmt, gimple_location (def_stmt)); + gsi2 = gsi_for_stmt (def_stmt); + gsi_insert_after (&gsi2, copy_stmt, GSI_NEW_STMT); + info->val_1 = new_def; + } + } + + reset_flow_sensitive_info (def); + if (new_def && TREE_NO_WARNING (def)) + TREE_NO_WARNING (new_def) = 1; + return true; +} + +/* Fix the (promoted) USE in stmts where USE cannot be be promoted. */ +static unsigned int +fixup_use (gimple *stmt, gimple_stmt_iterator *gsi, + use_operand_p op, tree use, int ind) +{ + gimple *copy_stmt; + ssa_name_info **info = ssa_name_info_map->get (use); + /* If USE is not promoted, nothing to do. */ + if (!info || *info == NULL) + return 0; + + tree promoted_type = (*info)->promoted_type; + tree old_type = (*info)->type; + bool do_not_promote = false; + + switch (gimple_code (stmt)) + { + case GIMPLE_DEBUG: + { + SET_USE (op, fold_convert (old_type, use)); + update_stmt (stmt); + break; + } + + case GIMPLE_ASM: + case GIMPLE_CALL: + case GIMPLE_RETURN: + case GIMPLE_SWITCH: + { + /* USE cannot be promoted here. */ + do_not_promote = true; + break; + } + + case GIMPLE_ASSIGN: + { + enum tree_code code = gimple_assign_rhs_code (stmt); + tree lhs = gimple_assign_lhs (stmt); + + /* If Use defintion in STMT cannot be promoted. */ + if (gimple_vuse (stmt) != NULL_TREE + || gimple_vdef (stmt) != NULL_TREE + || (ANY_INTEGRAL_TYPE_P (TREE_TYPE (lhs)) + && !operation_no_trapping_overflow (TREE_TYPE (lhs), code)) + || code == VIEW_CONVERT_EXPR + || code == LROTATE_EXPR + || code == RROTATE_EXPR + || code == CONSTRUCTOR + || code == BIT_FIELD_REF + || code == COMPLEX_EXPR + || VECTOR_TYPE_P (TREE_TYPE (lhs))) + { + do_not_promote = true; + } + else if (TREE_TYPE (use) == old_type) + { + if (TREE_CODE_CLASS (code) == tcc_comparison) + promote_cst_in_stmt (stmt, promoted_type); + tree temp = make_ssa_name (promoted_type, NULL); + copy_stmt = gimple_build_assign (temp, NOP_EXPR, use); + gimple_set_location (copy_stmt, gimple_location (stmt)); + gsi_insert_before (gsi, copy_stmt, GSI_NEW_STMT); + + SET_USE (op, temp); + update_stmt (stmt); + } + else if (!not_needed_truncated_operand_p (code)) + { + /* Promote the constant in comparison when other comparison + operand is promoted. All other constants are promoted as + part of promoting definition in promote_ssa. */ + if (TREE_CODE_CLASS (code) == tcc_comparison) + promote_cst_in_stmt (stmt, promoted_type); + /* In some stmts, value in USE has to be ZERO/SIGN + Extended based on the original type for correct + result. */ + tree temp = make_ssa_name (TREE_TYPE (use), NULL); + copy_stmt = zero_sign_extend_stmt (temp, use, old_type); + gimple_set_location (copy_stmt, gimple_location (stmt)); + gsi_insert_before (gsi, copy_stmt, GSI_NEW_STMT); + + SET_USE (op, temp); + update_stmt (stmt); + } + else if (CONVERT_EXPR_CODE_P (code) + || code == FLOAT_EXPR) + { + if (types_compatible_p (TREE_TYPE (lhs), promoted_type)) + { + /* Type of LHS and promoted RHS are compatible, we can + convert this into ZERO/SIGN EXTEND stmt. */ + copy_stmt = zero_sign_extend_stmt (lhs, use, old_type); + gimple_set_location (copy_stmt, gimple_location (stmt)); + set_ssa_promoted (lhs); + gsi_replace (gsi, copy_stmt, false); + } + else if (!tobe_promoted_p (lhs) + || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)) + || (TYPE_UNSIGNED (TREE_TYPE (use)) != TYPE_UNSIGNED (TREE_TYPE (lhs)))) + { + tree temp = make_ssa_name (TREE_TYPE (use), NULL); + copy_stmt = zero_sign_extend_stmt (temp, use, old_type); + gimple_set_location (copy_stmt, gimple_location (stmt)); + gsi_insert_before (gsi, copy_stmt, GSI_NEW_STMT); + SET_USE (op, temp); + update_stmt (stmt); + } + } + break; + } + + case GIMPLE_COND: + if (TREE_TYPE (use) == old_type) + { + tree temp = make_ssa_name (promoted_type, NULL); + copy_stmt = gimple_build_assign (temp, NOP_EXPR, use); + gimple_set_location (copy_stmt, gimple_location (stmt)); + gsi_insert_before (gsi, copy_stmt, GSI_NEW_STMT); + + SET_USE (op, temp); + promote_cst_in_stmt (stmt, promoted_type); + update_stmt (stmt); + } + else + { + /* In GIMPLE_COND, value in USE has to be ZERO/SIGN + Extended based on the original type for correct + result. */ + tree temp = make_ssa_name (TREE_TYPE (use), NULL); + copy_stmt = zero_sign_extend_stmt (temp, use, old_type); + gimple_set_location (copy_stmt, gimple_location (stmt)); + gsi_insert_before (gsi, copy_stmt, GSI_NEW_STMT); + SET_USE (op, temp); + promote_cst_in_stmt (stmt, promoted_type); + update_stmt (stmt); + } + break; + case GIMPLE_PHI: + if (!types_compatible_p (TREE_TYPE (use), promoted_type)) + { + tree temp = make_ssa_name (promoted_type, NULL); + copy_stmt = gimple_build_assign (temp, NOP_EXPR, use); + vec *preds = gimple_bb (stmt)->preds; + edge e = (*preds)[ind]; + gsi_insert_on_edge (e, copy_stmt); + + SET_USE (op, temp); + update_stmt (stmt); + } + break; + + default: + break; + } + + if (do_not_promote) + { + /* FOR stmts where USE cannot be promoted, create an + original type copy. */ + tree temp = (*info)->val_1; + if (temp == NULL_TREE) + { + temp = copy_ssa_name (use); + SET_SSA_NAME_VAR_OR_IDENTIFIER (temp, NULL_TREE); + set_ssa_promoted (temp); + TREE_TYPE (temp) = old_type; + copy_stmt = gimple_build_assign (temp, NOP_EXPR, use); + gimple_set_location (copy_stmt, gimple_location (stmt)); + gsi_insert_before (gsi, copy_stmt, GSI_NEW_STMT); + } + SET_USE (op, temp); + update_stmt (stmt); + } + return 0; +} + +static void +promote_all_ssa_defined_with_nop () +{ + unsigned n = num_ssa_names, i; + gimple_stmt_iterator gsi2; + tree new_def; + basic_block bb; + gimple *copy_stmt; + + for (i = 1; i < n; ++i) + { + tree name = ssa_name (i); + if (name + && gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_NOP + && tobe_promoted_p (name) + && !has_zero_uses (name)) + { + tree promoted_type = get_promoted_type (TREE_TYPE (name)); + ssa_name_info *info; + set_ssa_promoted (name); + info = (ssa_name_info *) obstack_alloc (&ssa_name_info_obstack, + sizeof (ssa_name_info)); + info->type = TREE_TYPE (name); + info->promoted_type = promoted_type; + info->ssa = name; + info->val_1 = NULL_TREE; + ssa_name_info_map->put (name, info); + + if (SSA_NAME_VAR (name) == NULL) + { + /* Promote def by fixing its type for anonymous def. */ + TREE_TYPE (name) = promoted_type; + } + else if (TREE_CODE (SSA_NAME_VAR (name)) != PARM_DECL) + { + bool no_warn = false; + location_t loc = DECL_SOURCE_LOCATION (SSA_NAME_VAR (name)); + if (TREE_NO_WARNING (SSA_NAME_VAR (name))) + no_warn = true; + tree var = create_tmp_reg (promoted_type); + DECL_NAME (var) = DECL_NAME (SSA_NAME_VAR (name)); + set_ssa_default_def (cfun, SSA_NAME_VAR (name), NULL_TREE); + TREE_TYPE (name) = promoted_type; + SET_SSA_NAME_VAR_OR_IDENTIFIER (name, var); + DECL_SOURCE_LOCATION (SSA_NAME_VAR (name)) = loc; + set_ssa_default_def (cfun, var, name); + if (no_warn) + TREE_NO_WARNING (var) = 1; + } + else + { + /* Create a promoted copy of parameters. */ + bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + gcc_assert (bb); + gsi2 = gsi_after_labels (bb); + /* Create new_def of the original type and set that to be the + parameter. */ + new_def = copy_ssa_name (name); + set_ssa_promoted (new_def); + set_ssa_default_def (cfun, SSA_NAME_VAR (name), new_def); + copy_default_ssa (new_def, name); + + /* Now promote the def and copy the value from parameter. */ + TREE_TYPE (name) = promoted_type; + copy_stmt = gimple_build_assign (name, NOP_EXPR, new_def); + SSA_NAME_DEF_STMT (name) = copy_stmt; + gsi_insert_before (&gsi2, copy_stmt, GSI_NEW_STMT); + info->val_1 = new_def; + } + reset_flow_sensitive_info (name); + } + } +} + +/* Promote all the stmts in the basic block. */ +static void +promote_all_stmts (basic_block bb) +{ + gimple_stmt_iterator gsi; + ssa_op_iter iter; + tree def, use; + use_operand_p op; + + for (gphi_iterator gpi = gsi_start_phis (bb); + !gsi_end_p (gpi); gsi_next (&gpi)) + { + gphi *phi = gpi.phi (); + int ind = 0; + FOR_EACH_PHI_ARG (op, phi, iter, SSA_OP_USE) + { + use = USE_FROM_PTR (op); + fixup_use (phi, &gsi, op, use, ind++); + } + + def = PHI_RESULT (phi); + if (tobe_promoted_p (def)) + promote_ssa (def, &gsi); + } + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE) + { + use = USE_FROM_PTR (op); + fixup_use (stmt, &gsi, op, use, 0); + } + + FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) + { + imm_use_iterator ui2; + gimple *use_stmt; + use_operand_p op2; + ssa_op_iter iter; + if (!tobe_promoted_p (def)) + continue; + if (promote_ssa (def, &gsi)) + continue; + /* If def cannot be promoted, fixup already promoted + PHI stmts that use def. We only have to do this + for (backward) PHI stmts as we are promoting in + dominance order. */ + FOR_EACH_IMM_USE_STMT (use_stmt, ui2, def) + { + int ind = 0; + if (gimple_code (use_stmt) != GIMPLE_PHI + || types_compatible_p (TREE_TYPE (def), + TREE_TYPE (PHI_RESULT (use_stmt)))) + continue; + FOR_EACH_PHI_ARG (op2, as_a (use_stmt), + iter, SSA_OP_USE) + { + if (def == USE_FROM_PTR (op2)) + fixup_use (use_stmt, NULL, op2, def, ind); + ind++; + } + } + } + } +} + +class type_promotion_dom_walker : public dom_walker +{ +public: + type_promotion_dom_walker (cdi_direction direction) + : dom_walker (direction) {} + virtual edge before_dom_children (basic_block bb) + { + promote_all_stmts (bb); + return NULL; + } +}; + +/* Main entry point to the pass. */ +static unsigned int +execute_type_promotion (void) +{ + n_ssa_val = num_ssa_names; + ssa_name_info_map = new hash_map; + ssa_to_be_promoted_bitmap = sbitmap_alloc (n_ssa_val); + bitmap_clear (ssa_to_be_promoted_bitmap); + + /* Create the obstack where ssa_name_info will reside. */ + gcc_obstack_init (&ssa_name_info_obstack); + + calculate_dominance_info (CDI_DOMINATORS); + promote_all_ssa_defined_with_nop (); + /* Walk the CFG in dominator order. */ + type_promotion_dom_walker (CDI_DOMINATORS) + .walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + gsi_commit_edge_inserts (); + + obstack_free (&ssa_name_info_obstack, NULL); + sbitmap_free (ssa_to_be_promoted_bitmap); + delete ssa_name_info_map; + return 0; +} + +namespace { +const pass_data pass_data_type_promotion = +{ + GIMPLE_PASS, /* type */ + "promotion", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_TREE_TYPE_PROMOTE, /* tv_id */ + PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + (TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all), +}; + +class pass_type_promotion : public gimple_opt_pass +{ +public: + pass_type_promotion (gcc::context *ctxt) + : gimple_opt_pass (pass_data_type_promotion, ctxt) + {} + + /* opt_pass methods: */ + opt_pass * clone () { return new pass_type_promotion (m_ctxt); } + virtual bool gate (function *) { return flag_tree_type_promote != 0; } + virtual unsigned int execute (function *) + { + return execute_type_promotion (); + } + +}; // class pass_type_promotion + +} // anon namespace + +gimple_opt_pass * +make_pass_type_promote (gcc::context *ctxt) +{ + return new pass_type_promotion (ctxt); +} + diff --git a/gcc/passes.def b/gcc/passes.def index 0e55829..3db6ff7 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -301,6 +301,7 @@ along with GCC; see the file COPYING3. If not see POP_INSERT_PASSES () NEXT_PASS (pass_simduid_cleanup); NEXT_PASS (pass_lower_vector_ssa); + NEXT_PASS (pass_type_promote); NEXT_PASS (pass_cse_reciprocals); NEXT_PASS (pass_reassoc, false /* insert_powi_p */); NEXT_PASS (pass_strength_reduction); diff --git a/gcc/timevar.def b/gcc/timevar.def index 76b008e..069dc3d 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -281,6 +281,7 @@ DEFTIMEVAR (TV_VTABLE_VERIFICATION , "vtable verification") DEFTIMEVAR (TV_TREE_UBSAN , "tree ubsan") DEFTIMEVAR (TV_INITIALIZE_RTL , "initialize rtl") DEFTIMEVAR (TV_GIMPLE_LADDRESS , "address lowering") +DEFTIMEVAR (TV_TREE_TYPE_PROMOTE , "tree type promote") /* Everything else in rest_of_compilation not included above. */ DEFTIMEVAR (TV_EARLY_LOCAL , "early local passes") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 66e103a..80d30e7 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -439,6 +439,7 @@ extern gimple_opt_pass *make_pass_fre (gcc::context *ctxt); extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt); extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt); extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_type_promote (gcc::context *ctxt); extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt); extern gimple_opt_pass *make_pass_return_slot (gcc::context *ctxt); -- 1.9.1