Hi, I have attached revamped version of Kugan's original patch for type promotion (https://gcc.gnu.org/ml/gcc-patches/2014-09/msg00472.html) rebased on r249469. The motivation of the pass is to minimize generation of subregs to avoid redundant zero/sign extensions by carrying out computations in PROMOTE_MODE as much as possible on tree-level.
* Working of pass The pass is dominator-based, and tries to promote type of def to PROMOTE_MODE in each gimple stmt. Before beginning domwalk, all the default definitions are promoted to PROMOTE_MODE in promote_all_ssa_defined_with_nop (). The patch adds a new tree code SEXT_EXPR to represent sign-extension on tree level. CONVERT_EXPR is either replaced by an explicit sign or zero extension depending on the signedness of operands. The core of the pass is in following two routines: a) promote_ssa: This pass looks at the def of gimple_stmt, and promotes type of def to promoted_type in-place if possible. If it cannot promote def in-place, then it transforms: def = def_stmt to new_def = def_stmt def = convert_expr new_def where new_def is a clone of def, and type of def is set to promoted_type. b) fixup_use: The main intent is to "fix" uses of a promoted variable to preserve semantics of the code, for instance if the variable is used in stmt where it's original type is required. Another case is when def is not promoted by promote_ssa, but some uses could be promoted. promote_all_stmts () is the driver function that calls fixup_use and promote_ssa for each stmt within the basic block. The pass relies extensively on dom and vrp to remove redundancies generated by the pass and is thus enabled only if vrp is enabled. Issues: 1] Pass ordering: type-promote pass generates too many redundancies which can hamper other optimizations. One case I observed was on arm when it inhibited path splitting optimization because the number of stmts in basic block exceeded the value of param-max-jump-thread-duplication-stmts. So I placed the pass just before dom. I am not sure if this is a good approach. Maybe the pass itself should avoid generating redundant statements and not rely too much on dom and vrp ? 2] Redundant copies left after the pass: When it's safe, vrp optimzies _1 = op1 sext op2 into _1 = op1 which leaves redundant copies that are not optimized away at GIMPLE level. I placed pass_copy_prop after vrp to eliminate these copies but not sure if that is ideal. Maybe we should do this during vrp itself as this is the only case that generates redundant copies ? 3] Backward phi's: Since we traverse in dominated order, fixup_use() gets called first on a ssa_name that is an argument of a backward-phi. If it promotes the type and later if promote_ssa() decides that the ssa_name should not be promoted, then we have to again walk the backward phi's to undo the "incorrect" promotion, which is done by emitting a convert_expr back to the original type from promoted_type. While I suppose it shouldn't affect correctness, it generates redundant casts and was wondering if there's a better approach to handle this issue. * SPEC2k6 benchmarking: Results of benchmarking the patch for aarch64-linux-gnu cortex-a57: Improved: 401.bzip2 +2.11% 459.GemsFDTD +1.42% 464.h264ref +1.96% 471.omnetpp +1.05% 481.wrf +0.99% Regressed: 447.dealII -1.34% 450.soplex -1.54% 456.hmmer -3.79% 482.sphinx3 -2.95% The remaining benchmarks didn't have much difference. However there was some noise in the above run, and I suppose the numbers are not precise. I will give another run with benchmarking. There was no significant difference in code-size with and without patch for SPEC2k6. * Validation The patch passes bootstrap+test on x86_64-unknown-linux-gnu, arm-linux-gnueabihf, aarch64-linux-gnu and ppc64le-linux-gnu. On arm-linux-gnueabihf, and aarch64-linux-gnu, there is following fallout: 1] gcc.dg/attr-alloc_size-11.c missing range info for signed char (test for warnings, line 50) The issue seems to be that we call reset_flow_sensitive_info(def) if def is promoted and that invalidates value range which is probably causing the regression. 2] gcc.dg/fold-narrowbopcst-1.c scan-tree-dump optimized " = _.* \\\\+ 156" This requires adjusting the scan-dump. On ppc64le-linux-gnu, I am observing several regressions in the testsuite. Most of these seem to be because type-promotion is interfering with other optimizations, especially widening_mul and bswap pass. Also observed fallout for some cases due to interference with strlen, tail-call and jump-threading passes. I suppose I am not seeing these on arm/aarch64 because ppc64 defines PROMOTE_MODE to be DImode and aarch64 defines it to be SImode ? I am working to fix performance regressions. However I would be grateful to receive feedback on the pass, if it's going in the right direction. Thanks, Prathamesh
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 67d69c1c0d2..61e6df9acb2 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1564,6 +1564,7 @@ OBJS = \ tree-vect-slp.o \ tree-vectorizer.o \ tree-vrp.o \ + gimple-ssa-type-promote.o \ tree.o \ typed-splay-tree.o \ valtrack.o \ diff --git a/gcc/auto-profile.c b/gcc/auto-profile.c index 973d7af37ff..821963c4088 100644 --- a/gcc/auto-profile.c +++ b/gcc/auto-profile.c @@ -1328,7 +1328,7 @@ afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge) FOR_EACH_EDGE (e, ei, bb->succs) { unsigned i, total = 0; - edge only_one; + edge only_one = NULL; bool check_value_one = (((integer_onep (cmp_rhs)) ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR)) ^ ((e->flags & EDGE_TRUE_VALUE) != 0)); diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c index c1f80727d30..dec81b0c896 100644 --- a/gcc/cfgexpand.c +++ b/gcc/cfgexpand.c @@ -5118,6 +5118,18 @@ expand_debug_expr (tree exp) case FMA_EXPR: return simplify_gen_ternary (FMA, mode, inner_mode, op0, op1, op2); + case SEXT_EXPR: + gcc_assert (CONST_INT_P (op1)); + inner_mode = mode_for_size (INTVAL (op1), MODE_INT, 0); + gcc_assert (GET_MODE_BITSIZE (inner_mode) == INTVAL (op1)); + + if (mode != inner_mode) + op0 = simplify_gen_unary (SIGN_EXTEND, + mode, + gen_lowpart_SUBREG (inner_mode, op0), + inner_mode); + return op0; + default: flag_unsupported: if (flag_checking) diff --git a/gcc/common.opt b/gcc/common.opt index 4f9c3dcac3e..f9aa20cfffe 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -2590,6 +2590,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 7e7a16a5cb6..c3d168b3b3e 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -8547,6 +8547,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/expr.c b/gcc/expr.c index 5febf07929d..c853391996a 100644 --- a/gcc/expr.c +++ b/gcc/expr.c @@ -9560,6 +9560,25 @@ expand_expr_real_2 (sepops ops, rtx target, machine_mode tmode, TYPE_MODE (TREE_TYPE (treeop1)), op1, false); return dst; } + case SEXT_EXPR: + { + machine_mode inner_mode = mode_for_size (tree_to_uhwi (treeop1), + MODE_INT, 0); + rtx temp, result; + rtx op0 = expand_normal (treeop0); + op0 = force_reg (mode, op0); + if (mode != inner_mode) + { + result = gen_reg_rtx (mode); + temp = simplify_gen_unary (SIGN_EXTEND, mode, + gen_lowpart_SUBREG (inner_mode, op0), + inner_mode); + convert_move (result, temp, 0); + } + else + result = op0; + return result; + } default: gcc_unreachable (); diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 379a30ea285..758532b38a9 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -997,6 +997,10 @@ int_const_binop_1 (enum tree_code code, const_tree arg1, const_tree parg2, res = wi::bit_and (arg1, arg2); break; + case SEXT_EXPR: + res = wi::sext (arg1, arg2.to_uhwi ()); + break; + case RSHIFT_EXPR: case LSHIFT_EXPR: if (wi::neg_p (arg2)) diff --git a/gcc/gimple-ssa-type-promote.c b/gcc/gimple-ssa-type-promote.c new file mode 100644 index 00000000000..8789d210e04 --- /dev/null +++ b/gcc/gimple-ssa-type-promote.c @@ -0,0 +1,1096 @@ +/* Type promotion of SSA names to minimise redundant zero/sign extension. + Copyright (C) 2017 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 +<http://www.gnu.org/licenses/>. */ + +#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-vrp.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 minimize generation of RTL subregs + 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 <tree, ssa_name_info *> *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 == BIT_XOR_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; + + switch (gimple_code (stmt)) + { + case GIMPLE_ASSIGN: + /* 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 <gphi *> (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 <gcond *> (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. Return either of the following forms: + new_var = var sext_expr precision(inner_type) OR + new_var = var & mask(precision(inner_type)) +*/ + +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; +} + +static void +promote_gimple_asm (gasm *asm_stmt, tree def, tree promoted_type) +{ + for (unsigned i = 0; i < gimple_asm_noutputs (asm_stmt); i++) + { + tree link = gimple_asm_output_op (asm_stmt, i); + tree op = TREE_VALUE (link); + if (op == def) + { + tree new_def = copy_ssa_name (def); + copy_default_ssa (new_def, def); + set_ssa_promoted (new_def); + TREE_VALUE (link) = new_def; + gimple_asm_set_output_op (asm_stmt, i, link); + + TREE_TYPE (def) = promoted_type; + gimple *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 (asm_stmt)); + gimple_stmt_iterator gsi = gsi_for_stmt (asm_stmt); + gsi_insert_after (&gsi, copy_stmt, GSI_NEW_STMT); + + if (TREE_NO_WARNING (def)) + TREE_NO_WARNING (new_def) = 1; + return; + } + } +} + +/* + * Since def cannot be promoted in def_stmt, create an explicit promotion. + * Transform def = def_stmt + * To: + * new_def = def_stmt + * def = convert_expr new_def + * new_def is a clone of def, and def is now ssa_name with promoted_type. + */ + +static bool +promote_ssa_fallback (ssa_name_info *info, tree def, gimple *def_stmt) +{ + basic_block def_bb = gimple_bb (def_stmt); + bool insert_on_edge = false; + bool dump = dump_file && (dump_flags & TDF_DETAILS); + /* 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, def_bb->succs) + if (!(e->flags & EDGE_ABNORMAL)) + count ++; + + if (count != 1) + { + info->val_1 = def; + if (dump) + { + print_gimple_stmt (dump_file, def_stmt, 0); + fprintf (dump_file, "Not transforming, no normal edges found\n"); + } + return false; + } + insert_on_edge = true; + } + + if (dump) + { + fprintf (dump_file, "Transforming:\n"); + print_gimple_stmt (dump_file, def_stmt, 0); + } + + tree new_def = copy_ssa_name (def); + TREE_TYPE (def) = get_promoted_type (TREE_TYPE (def)); + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + set_ssa_promoted (new_def); + gimple_set_lhs (def_stmt, new_def); + gimple *copy_stmt = gimple_build_assign (def, NOP_EXPR, new_def); + gimple_set_location (copy_stmt, gimple_location (def_stmt)); + + if (insert_on_edge) + gsi_insert_on_edge (FALLTHRU_EDGE (def_bb), copy_stmt); + else + { + gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt); + gsi_insert_after (&gsi, copy_stmt, GSI_NEW_STMT); + } + + if (TREE_NO_WARNING (def)) + TREE_NO_WARNING (new_def) = 1; + + if (dump) + { + fprintf (dump_file, "To:\n"); + print_gimple_stmt (dump_file, def_stmt, 0); + print_gimple_stmt (dump_file, copy_stmt, 0); + putc ('\n', dump_file); + } + return true; +} + +/* + * Try to replace convert_expr with an explicit zero or sign extension. + * Case 1 - rhs_type and promoted_type are compatible. In this case, simply + * replace assign_stmt with either sign or zero extension and set type of + * def to promoted_type. + * + * Case 2 - rhs_type and promoted_type are not compatible, but rhs is + * recorded in ssa_name_info_map. In this case, transform: + * def = convert_expr rhs1 + * to + * new_def = rhs1 sext_expr/bit_and type_precision(info->type) + * where info is obtained from ssa_name_info_map for rhs + * and set type of def to promoted_type. + * + * Case 3 - rhs_type and promoted_type are not compatible and + * rhs1 is not recorded in ssa_name_info_map. In this case, + * do not promote def. + */ + +static bool +promote_convert_expr (gassign *assign_stmt, tree def, + tree promoted_type, gimple_stmt_iterator *gsi) +{ + enum tree_code code = gimple_assign_rhs_code (assign_stmt); + tree rhs = gimple_assign_rhs1 (assign_stmt); + tree rhs_type = TREE_TYPE (rhs); + tree original_type = TREE_TYPE (def); + bool dump = dump_file && (dump_flags & TDF_DETAILS); + + if (!type_precision_ok (rhs_type)) + return false; + + ssa_name_info *info = ssa_name_info_map->get_or_insert (rhs); + tree type = (info) ? info->type : TREE_TYPE (rhs); + + if (types_compatible_p (rhs_type, promoted_type)) + { + /* Case 1: Replace convert_expr by zero or sign extension. */ + + TREE_TYPE (def) = promoted_type; + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + + 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); + gimple *copy_stmt = zero_sign_extend_stmt (def, rhs, type); + gimple_set_location (copy_stmt, gimple_location (assign_stmt)); + + if (dump) + { + fprintf (dump_file, "Replacing:\n"); + print_gimple_stmt (dump_file, assign_stmt, 0); + fprintf (dump_file, "By:\n"); + print_gimple_stmt (dump_file, copy_stmt, 0); + putc ('\n', dump_file); + } + + gsi_replace (gsi, copy_stmt, false); + } + } + else if (info) + { + /* Case 2: If types are not compatible but rhs info is available then + Replace: + def = convert_expr rhs + By: + new_def = rhs sext_expr/bit_and_expr prec(info->type) + def = convert_expr new_def + */ + + TREE_TYPE (def) = promoted_type; + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + + tree new_def = copy_ssa_name (rhs); + SET_SSA_NAME_VAR_OR_IDENTIFIER (new_def, NULL_TREE); + gimple *copy_stmt = zero_sign_extend_stmt (new_def, rhs, type); + gimple_set_location (copy_stmt, gimple_location (assign_stmt)); + gimple_stmt_iterator gsi2 = gsi_for_stmt (assign_stmt); + gsi_insert_before (&gsi2, copy_stmt, GSI_NEW_STMT); + gassign *new_def_stmt = gimple_build_assign (def, code, new_def); + + if (dump) + { + fprintf (dump_file, "Replacing:\n"); + print_gimple_stmt (dump_file, assign_stmt, 0); + fprintf (dump_file, "By:\n"); + print_gimple_stmt (dump_file, copy_stmt, 0); + print_gimple_stmt (dump_file, new_def_stmt, 0); + putc ('\n', dump_file); + } + + gsi_replace (gsi, new_def_stmt, false); + + if (TREE_NO_WARNING (def)) + TREE_NO_WARNING (new_def) = 1; + } + else + { + /* Case 3: Do not promote def */ + set_ssa_promoted (def); + } + + return true; +} + +/* 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); + tree original_type = TREE_TYPE (def); + bool ret = true; + bool dump = dump_file && (dump_flags & TDF_DETAILS); + tree promoted_type = get_promoted_type (TREE_TYPE (def)); + + ssa_name_info *info; + 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); + if (dump) + { + fprintf (dump_file, "Promoting "); + print_generic_expr (dump_file, def, 0); + fprintf (dump_file, " in "); + print_gimple_stmt (dump_file, def_stmt, 0); + } + break; + + case GIMPLE_ASM: + promote_gimple_asm (as_a<gasm *> (def_stmt), def, promoted_type); + break; + + 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 + || TREE_CODE (TREE_TYPE (def)) == COMPLEX_TYPE + || VECTOR_TYPE_P (TREE_TYPE (def)) + || (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)) + || (CONVERT_EXPR_CODE_P (code) + && !promote_convert_expr (as_a<gassign *> (def_stmt), + def, promoted_type, gsi))) + ret = promote_ssa_fallback (info, def, def_stmt); + else + { + /* Promote def by fixing its type and make def anonymous. */ + promote_cst_in_stmt (def_stmt, promoted_type); + TREE_TYPE (def) = promoted_type; + SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE); + + if (dump) + { + fprintf (dump_file, "Promoting "); + print_generic_expr (dump_file, def, 0); + fprintf (dump_file, " in "); + print_gimple_stmt (dump_file, def_stmt, 0); + } + } + break; + } + + case GIMPLE_NOP: + gcc_unreachable (); + + default: + ret = promote_ssa_fallback (info, def, def_stmt); + break; + } + + if (ret) + reset_flow_sensitive_info (def); + return ret; +} + +static bool +fixup_gimple_assign (gassign *stmt, tree use, + gimple_stmt_iterator *gsi, use_operand_p op, + ssa_name_info *info) +{ + enum tree_code code = gimple_assign_rhs_code (stmt); + tree lhs = gimple_assign_lhs (stmt); + tree promoted_type = info->promoted_type; + tree old_type = info->type; + + /* 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_OPERAND_LENGTH (gimple_assign_rhs1 (stmt)) == 2) + { + tree op = gimple_assign_rhs1 (stmt); + tree op0 = TREE_OPERAND (op, 0); + tree op1 = TREE_OPERAND (op, 1); + + if (op0 == use || op1 == use) + { + if (TREE_TYPE (op0) != TREE_TYPE (op1)) + { + if (TREE_CODE (op0) == INTEGER_CST) + TREE_OPERAND (op, 0) = fold_convert (promoted_type, op0); + if (TREE_CODE (op1) == INTEGER_CST) + TREE_OPERAND (op, 1) = fold_convert (promoted_type, op1); + } + } + } + else if (TREE_CODE_CLASS (code) == tcc_comparison) + promote_cst_in_stmt (stmt, promoted_type); + + /* Do not promote if the following condition is true. */ + 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))) + return false; + + else if (TREE_TYPE (use) == old_type) + { + /* In case, promote_ssa did not promote def, we can promote + some uses of the def by creating a temp, which has promoted_type: + Transform use(x) + to: + temp = (promoted_type) x; + use(temp). */ + + tree temp = make_ssa_name (promoted_type, NULL); + gimple *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)) + { + /* 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); + gimple *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. */ + gimple *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); + gimple *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); + } + } + + return true; +} + +/* If ssa_name has been promoted by promote_ssa, but it's use in a + * particular stmt requires it's original type, then "fix" the use by emitting + * a cast back to original type. + * + * Transform use(x) where x is of promoted_type to: + * new_def = (original_type) x; + * use(new_def) + * + * Alternatively, if promote_ssa() chooses not to promote ssa_name but it's use in + * a particular stmt can be promoted then promote it by emitting cast to promoted_type. + * + * Transform use(x) where x is of original_type to: + * new_def = (promoted_type) x; + * use(new_def) + * + */ + +static void +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; + + 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: + do_not_promote = !fixup_gimple_assign (as_a<gassign *> (stmt), use, + gsi, op, *info); + 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<edge, va_gc> *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); + } +} + +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); + + /* FIXME: This is a hack to workaround ICE caused due to abnormal + control flow in which introduces phi in ENTRY's successor block, + that has the param as one of it's arguments. Creating + param = (promoted_type) new_def + thus results in define-after-use, which fails with verification. + */ + if (bb_has_abnormal_pred (bb)) + { + set_ssa_promoted (name); + continue; + } + + 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 <gphi *> (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<tree, ssa_name_info *>; + 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 && flag_tree_vrp; } + 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/match.pd b/gcc/match.pd index 7bd26763826..c319a265acd 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -3996,3 +3996,10 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) { CONSTRUCTOR_ELT (ctor, idx / k)->value; }) (BIT_FIELD_REF { CONSTRUCTOR_ELT (ctor, idx / k)->value; } @1 { bitsize_int ((idx % k) * width); }))))))))) + +(simplify + (sext (sext@2 @0 @1) @3) + (if (tree_int_cst_compare (@1, @3) <= 0) + @2 + (sext @0 @3))) + diff --git a/gcc/passes.def b/gcc/passes.def index 316e19d12e3..143a5d32068 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -322,10 +322,12 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_split_paths); NEXT_PASS (pass_tracer); NEXT_PASS (pass_thread_jumps); + NEXT_PASS (pass_type_promote); NEXT_PASS (pass_dominator, false /* may_peel_loop_headers_p */); NEXT_PASS (pass_strlen); NEXT_PASS (pass_thread_jumps); NEXT_PASS (pass_vrp, false /* warn_array_bounds_p */); + NEXT_PASS (pass_copy_prop); /* The only const/copy propagation opportunities left after DOM and VRP should be due to degenerate PHI nodes. So rather than run the full propagators, run a specialized pass which diff --git a/gcc/timevar.def b/gcc/timevar.def index 9ceda8a3268..d68f66330eb 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -289,6 +289,7 @@ DEFTIMEVAR (TV_TREE_UBSAN , "tree ubsan") DEFTIMEVAR (TV_INITIALIZE_RTL , "initialize rtl") DEFTIMEVAR (TV_GIMPLE_LADDRESS , "address lowering") DEFTIMEVAR (TV_TREE_LOOP_IFCVT , "tree loop if-conversion") +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-cfg.c b/gcc/tree-cfg.c index 589508df044..b73739b3e04 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -3907,6 +3907,18 @@ verify_gimple_assign_binary (gassign *stmt) return false; } + case SEXT_EXPR: + { + if (!INTEGRAL_TYPE_P (lhs_type) + || !useless_type_conversion_p (lhs_type, rhs1_type) + || !tree_fits_uhwi_p (rhs2)) + { + error ("invalid operands in sext expr"); + return true; + } + return false; + } + case VEC_WIDEN_LSHIFT_HI_EXPR: case VEC_WIDEN_LSHIFT_LO_EXPR: { diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c index aea8a79da14..2c8941e7217 100644 --- a/gcc/tree-inline.c +++ b/gcc/tree-inline.c @@ -3902,6 +3902,7 @@ estimate_operator_cost (enum tree_code code, eni_weights *weights, case BIT_XOR_EXPR: case BIT_AND_EXPR: case BIT_NOT_EXPR: + case SEXT_EXPR: case TRUTH_ANDIF_EXPR: case TRUTH_ORIF_EXPR: diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 2863f769610..a78f06ff757 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -445,6 +445,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_early_vrp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt); diff --git a/gcc/tree-pretty-print.c b/gcc/tree-pretty-print.c index b70e32573ee..7734319faf8 100644 --- a/gcc/tree-pretty-print.c +++ b/gcc/tree-pretty-print.c @@ -2131,6 +2131,14 @@ dump_generic_node (pretty_printer *pp, tree node, int spc, dump_flags_t flags, } break; + case SEXT_EXPR: + pp_string (pp, "SEXT_EXPR <"); + dump_generic_node (pp, TREE_OPERAND (node, 0), spc, flags, false); + pp_string (pp, ", "); + dump_generic_node (pp, TREE_OPERAND (node, 1), spc, flags, false); + pp_greater (pp); + break; + case MODIFY_EXPR: case INIT_EXPR: dump_generic_node (pp, TREE_OPERAND (node, 0), spc, flags, @@ -3797,6 +3805,9 @@ op_symbol_code (enum tree_code code) case MIN_EXPR: return "min"; + case SEXT_EXPR: + return "sext"; + default: return "<<< ??? >>>"; } diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c index b587599f8f8..38cdc6e236e 100644 --- a/gcc/tree-ssa-uninit.c +++ b/gcc/tree-ssa-uninit.c @@ -2144,7 +2144,9 @@ normalize_one_pred (pred_chain_union *norm_preds, pred_info pred) gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs); if (gimple_code (def_stmt) == GIMPLE_ASSIGN) and_or_code = gimple_assign_rhs_code (def_stmt); - if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR) + if (and_or_code != BIT_IOR_EXPR + && and_or_code != SEXT_EXPR + && and_or_code != BIT_AND_EXPR) { if (TREE_CODE_CLASS (and_or_code) == tcc_comparison) { @@ -2165,7 +2167,8 @@ normalize_one_pred (pred_chain_union *norm_preds, pred_info pred) normalize_one_pred_1 (norm_preds, &norm_chain, a_pred, and_or_code, &work_list, &mark_set); } - if (and_or_code == BIT_AND_EXPR) + if (and_or_code == BIT_AND_EXPR + || and_or_code == SEXT_EXPR) norm_preds->safe_push (norm_chain); work_list.release (); diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 9ca3924ea89..3de9c562edf 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -1971,6 +1971,7 @@ extract_range_from_binary_expr_1 (value_range *vr, && code != LSHIFT_EXPR && code != MIN_EXPR && code != MAX_EXPR + && code != SEXT_EXPR && code != BIT_AND_EXPR && code != BIT_IOR_EXPR && code != BIT_XOR_EXPR) @@ -2546,6 +2547,54 @@ extract_range_from_binary_expr_1 (value_range *vr, extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1); return; } + else if (code == SEXT_EXPR) + { + gcc_assert (range_int_cst_p (&vr1)); + HOST_WIDE_INT prec = tree_to_uhwi (vr1.min); + type = vr0.type; + wide_int tmin, tmax; + wide_int may_be_nonzero, must_be_nonzero; + + wide_int type_min = wi::min_value (prec, SIGNED); + wide_int type_max = wi::max_value (prec, SIGNED); + type_min = wide_int_to_tree (expr_type, type_min); + type_max = wide_int_to_tree (expr_type, type_max); + type_min = wi::sext (type_min, prec); + type_max = wi::sext (type_max, prec); + wide_int sign_bit + = wi::set_bit_in_zero (prec - 1, + TYPE_PRECISION (TREE_TYPE (vr0.min))); + if (zero_nonzero_bits_from_vr (expr_type, &vr0, + &may_be_nonzero, + &must_be_nonzero)) + { + if (wi::bit_and (must_be_nonzero, sign_bit) == sign_bit) + { + /* If to-be-extended sign bit is one. */ + tmin = type_min; + tmax = wi::zext (may_be_nonzero, prec); + } + else if (wi::bit_and (may_be_nonzero, sign_bit) + != sign_bit) + { + /* If to-be-extended sign bit is zero. */ + tmin = wi::zext (must_be_nonzero, prec); + tmax = wi::zext (may_be_nonzero, prec); + } + else + { + tmin = type_min; + tmax = type_max; + } + } + else + { + tmin = type_min; + tmax = type_max; + } + min = wide_int_to_tree (expr_type, tmin); + max = wide_int_to_tree (expr_type, tmax); + } else if (code == RSHIFT_EXPR || code == LSHIFT_EXPR) { @@ -9514,6 +9563,17 @@ simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) break; } break; + case SEXT_EXPR: + { + unsigned int prec = tree_to_uhwi (op1); + wide_int min = vr0.min; + wide_int max = vr0.max; + wide_int sext_min = wi::sext (min, prec); + wide_int sext_max = wi::sext (max, prec); + if (min == sext_min && max == sext_max) + op = op0; + } + break; default: gcc_unreachable (); } @@ -10354,6 +10414,7 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi) case BIT_AND_EXPR: case BIT_IOR_EXPR: + case SEXT_EXPR: /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR if all the bits being cleared are already cleared or all the bits being set are already set. */ diff --git a/gcc/tree.def b/gcc/tree.def index 0ec805903a9..b720fca6171 100644 --- a/gcc/tree.def +++ b/gcc/tree.def @@ -760,6 +760,11 @@ DEFTREECODE (BIT_XOR_EXPR, "bit_xor_expr", tcc_binary, 2) DEFTREECODE (BIT_AND_EXPR, "bit_and_expr", tcc_binary, 2) DEFTREECODE (BIT_NOT_EXPR, "bit_not_expr", tcc_unary, 1) +/* Sign-extend operation. It will sign extend first operand from + the sign bit specified by the second operand. The type of the + result is that of the first operand. */ +DEFTREECODE (SEXT_EXPR, "sext_expr", tcc_binary, 2) + /* ANDIF and ORIF allow the second operand not to be computed if the value of the expression is determined from the first operand. AND, OR, and XOR always compute the second operand whether its value is