From 209ca542cadd7ae7dc174bc74e066ed1de246672 Mon Sep 17 00:00:00 2001 From: Prathamesh Kulkarni Date: Fri, 26 Aug 2016 08:05:39 +0000 Subject: [PATCH] Patch for performing interprocedural bitwise constant propagation. 2016-08-26 Prathamesh Kulkarni Martin Jambhor * common.opt: New option -fipa-bit-cp. * doc/invoke.texi: Document -fipa-bit-cp. * opts.c (default_options_table): Add entry for -fipa-bit-cp. (enable_fdo_optimizations): Check for flag_ipa_bit_cp. * tree-ssa-ccp.h: New header file. * tree-ssa-ccp.c: Include tree-ssa-ccp.h (bit_value_binop_1): Change to bit_value_binop_1 and export it. Replace all occurences of tree parameter by two new params: signop, int. (bit_value_unop_1): Change to bit_value_unop and export it. Replace all occurences of tree parameter by two new params: signop, int. (bit_value_binop): Change call from bit_value_binop_1 to bit_value_binop. (bit_value_assume_aligned): Likewise. (bit_value_unop): Change call from bit_value_unop_1 to bit_value_unop. (do_ssa_ccp): Pass nonzero_p || flag_ipa_cp_bit instead of nonzero_p to ccp_finalize. (ccp_finalize): Skip processing if val->mask == 0. * ipa-cp.c: Include tree-ssa-ccp.h (ipcp_bits_lattice): New class. (ipcp_param_lattice (bits_lattice): New member. (print_all_lattices): Call ipcp_bits_lattice::print. (set_all_contains_variable): Call ipcp_bits_lattice::set_to_bottom. (initialize_node_lattices): Likewise. (propagate_bits_accross_jump_function): New function. (propagate_constants_accross_call): Call propagate_bits_accross_jump_function. (ipcp_propagate_stage): Store parameter types when in_lto_p is true. (ipcp_store_bits_results): New function. (ipcp_driver): Call ipcp_store_bits_results. * ipa-prop.h (ipa_bits): New struct. (ipa_jump_func): Add new member bits of type ipa_bits. (ipa_param_descriptor): Change decl to decl_or_type. (ipa_get_param): Change decl to decl_or_type and assert on PARM_DECL. (ipa_get_type): New function. (ipcp_transformation_summary): New member bits. * ipa-prop.c (ipa_get_param_decl_index_1): s/decl/decl_or_type. (ipa_populate_param_decls): Likewise. (ipa_dump_param): Likewise. (ipa_print_node_jump_functions_for_edge): Pretty-print ipa_bits jump function. (ipa_set_jf_unknown): Set ipa_bits::known to false. (ipa_compute_jump_functions_for_edge): Compute jump function for bits propagation. (ipa_node_params_t::duplicate): Copy src->bits into dst->bits. (ipa_write_jump_function): Add streaming for ipa_bits. (ipa_read_jump_function): Add support for reading streamed ipa_bits. (write_ipcp_transformation_info): Add streaming for ipa_bits summary for ltrans. (read_ipcp_transfomration_info): Add support for reading streamed ipa_bits. (ipcp_update_bits): New function. (ipcp_transform_function): Call ipcp_update_bits. testsuite/ * gcc.dg/ipa/propbits-1.c: New test-case. * gcc.dg/ipa/propbits-2.c: Likewise. * gcc.dg/ipa/propbits-3.c: Likewise. Co-Authored-By: Martin Jambor From-SVN: r239769 --- gcc/ChangeLog | 57 ++++ gcc/common.opt | 4 + gcc/doc/invoke.texi | 9 +- gcc/ipa-cp.c | 384 ++++++++++++++++++++++++++ gcc/ipa-prop.c | 163 ++++++++++- gcc/ipa-prop.h | 47 +++- gcc/opts.c | 4 + gcc/testsuite/ChangeLog | 7 + gcc/testsuite/gcc.dg/ipa/propbits-1.c | 19 ++ gcc/testsuite/gcc.dg/ipa/propbits-2.c | 41 +++ gcc/testsuite/gcc.dg/ipa/propbits-3.c | 22 ++ gcc/tree-ssa-ccp.c | 92 +++--- gcc/tree-ssa-ccp.h | 29 ++ 13 files changed, 825 insertions(+), 53 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/ipa/propbits-1.c create mode 100644 gcc/testsuite/gcc.dg/ipa/propbits-2.c create mode 100644 gcc/testsuite/gcc.dg/ipa/propbits-3.c create mode 100644 gcc/tree-ssa-ccp.h diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 8c9d505094f..d4360f766f5 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,60 @@ +2016-08-26 Prathamesh Kulkarni + Martin Jambhor + + * common.opt: New option -fipa-bit-cp. + * doc/invoke.texi: Document -fipa-bit-cp. + * opts.c (default_options_table): Add entry for -fipa-bit-cp. + (enable_fdo_optimizations): Check for flag_ipa_bit_cp. + * tree-ssa-ccp.h: New header file. + * tree-ssa-ccp.c: Include tree-ssa-ccp.h + (bit_value_binop_1): Change to bit_value_binop_1 and export it. + Replace all occurences of tree parameter by two new params: signop, int. + (bit_value_unop_1): Change to bit_value_unop and export it. + Replace all occurences of tree parameter by two new params: signop, + int. + (bit_value_binop): Change call from bit_value_binop_1 to + bit_value_binop. + (bit_value_assume_aligned): Likewise. + (bit_value_unop): Change call from bit_value_unop_1 to bit_value_unop. + (do_ssa_ccp): Pass nonzero_p || flag_ipa_cp_bit instead of nonzero_p + to ccp_finalize. + (ccp_finalize): Skip processing if val->mask == 0. + * ipa-cp.c: Include tree-ssa-ccp.h + (ipcp_bits_lattice): New class. + (ipcp_param_lattice (bits_lattice): New member. + (print_all_lattices): Call ipcp_bits_lattice::print. + (set_all_contains_variable): Call ipcp_bits_lattice::set_to_bottom. + (initialize_node_lattices): Likewise. + (propagate_bits_accross_jump_function): New function. + (propagate_constants_accross_call): Call + propagate_bits_accross_jump_function. + (ipcp_propagate_stage): Store parameter types when in_lto_p is true. + (ipcp_store_bits_results): New function. + (ipcp_driver): Call ipcp_store_bits_results. + * ipa-prop.h (ipa_bits): New struct. + (ipa_jump_func): Add new member bits of type ipa_bits. + (ipa_param_descriptor): Change decl to decl_or_type. + (ipa_get_param): Change decl to decl_or_type and assert on + PARM_DECL. + (ipa_get_type): New function. + (ipcp_transformation_summary): New member bits. + * ipa-prop.c (ipa_get_param_decl_index_1): s/decl/decl_or_type. + (ipa_populate_param_decls): Likewise. + (ipa_dump_param): Likewise. + (ipa_print_node_jump_functions_for_edge): Pretty-print ipa_bits jump + function. + (ipa_set_jf_unknown): Set ipa_bits::known to false. + (ipa_compute_jump_functions_for_edge): Compute jump function for bits + propagation. + (ipa_node_params_t::duplicate): Copy src->bits into dst->bits. + (ipa_write_jump_function): Add streaming for ipa_bits. + (ipa_read_jump_function): Add support for reading streamed ipa_bits. + (write_ipcp_transformation_info): Add streaming for ipa_bits + summary for ltrans. + (read_ipcp_transfomration_info): Add support for reading streamed ipa_bits. + (ipcp_update_bits): New function. + (ipcp_transform_function): Call ipcp_update_bits. + 2016-08-25 Szabolcs Nagy * config/mips/linux.h (MUSL_DYNAMIC_LINKER32): Update. diff --git a/gcc/common.opt b/gcc/common.opt index 65a976213df..fd1ac87ddab 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1561,6 +1561,10 @@ fipa-cp-alignment Common Report Var(flag_ipa_cp_alignment) Optimization Perform alignment discovery and propagation to make Interprocedural constant propagation stronger. +fipa-bit-cp +Common Report Var(flag_ipa_bit_cp) Optimization +Perform interprocedural bitwise constant propagation. + fipa-profile Common Report Var(flag_ipa_profile) Init(0) Optimization Perform interprocedural profile propagation. diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 1f045013549..baae0bd9bfd 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -358,7 +358,7 @@ Objective-C and Objective-C++ Dialects}. -fgcse-sm -fhoist-adjacent-loads -fif-conversion @gol -fif-conversion2 -findirect-inlining @gol -finline-functions -finline-functions-called-once -finline-limit=@var{n} @gol --finline-small-functions -fipa-cp -fipa-cp-clone -fipa-cp-alignment @gol +-finline-small-functions -fipa-cp -fipa-cp-clone -fipa-cp-alignment -fipa-bit-cp @gol -fipa-pta -fipa-profile -fipa-pure-const -fipa-reference -fipa-icf @gol -fira-algorithm=@var{algorithm} @gol -fira-region=@var{region} -fira-hoist-pressure @gol @@ -6370,6 +6370,7 @@ also turns on the following optimization flags: -findirect-inlining @gol -fipa-cp @gol -fipa-cp-alignment @gol +-fipa-bit-cp @gol -fipa-sra @gol -fipa-icf @gol -fisolate-erroneous-paths-dereference @gol @@ -7378,6 +7379,12 @@ parameters to support better vectorization and string operations. This flag is enabled by default at @option{-O2} and @option{-Os}. It requires that @option{-fipa-cp} is enabled. +@item -fipa-bit-cp +@opindex -fipa-bit-cp +When enabled, perform ipa bitwise constant propagation. This flag is +enabled by default at @option{-O2}. It requires that @option{-fipa-cp} +is enabled. + @item -fipa-icf @opindex fipa-icf Perform Identical Code Folding for functions and read-only variables. diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c index 5b6cb9a143f..9514dd18177 100644 --- a/gcc/ipa-cp.c +++ b/gcc/ipa-cp.c @@ -120,6 +120,7 @@ along with GCC; see the file COPYING3. If not see #include "params.h" #include "ipa-inline.h" #include "ipa-utils.h" +#include "tree-ssa-ccp.h" template class ipcp_value; @@ -266,6 +267,60 @@ private: bool meet_with_1 (unsigned new_align, unsigned new_misalign); }; +/* Lattice of known bits, only capable of holding one value. + Bitwise constant propagation propagates which bits of a + value are constant. + For eg: + int f(int x) + { + return some_op (x); + } + + int f1(int y) + { + if (cond) + return f (y & 0xff); + else + return f (y & 0xf); + } + + In the above case, the param 'x' will always have all + the bits (except the bits in lsb) set to 0. + Hence the mask of 'x' would be 0xff. The mask + reflects that the bits in lsb are unknown. + The actual propagated value is given by m_value & ~m_mask. */ + +class ipcp_bits_lattice +{ +public: + bool bottom_p () { return m_lattice_val == IPA_BITS_VARYING; } + bool top_p () { return m_lattice_val == IPA_BITS_UNDEFINED; } + bool constant_p () { return m_lattice_val == IPA_BITS_CONSTANT; } + bool set_to_bottom (); + bool set_to_constant (widest_int, widest_int); + + widest_int get_value () { return m_value; } + widest_int get_mask () { return m_mask; } + + bool meet_with (ipcp_bits_lattice& other, unsigned, signop, + enum tree_code, tree); + + bool meet_with (widest_int, widest_int, unsigned); + + void print (FILE *); + +private: + enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING } m_lattice_val; + + /* Similar to ccp_lattice_t, mask represents which bits of value are constant. + If a bit in mask is set to 0, then the corresponding bit in + value is known to be constant. */ + widest_int m_value, m_mask; + + bool meet_with_1 (widest_int, widest_int, unsigned); + void get_value_and_mask (tree, widest_int *, widest_int *); +}; + /* Structure containing lattices for a parameter itself and for pieces of aggregates that are passed in the parameter or by a reference in a parameter plus some other useful flags. */ @@ -281,6 +336,8 @@ public: ipcp_agg_lattice *aggs; /* Lattice describing known alignment. */ ipcp_alignment_lattice alignment; + /* Lattice describing known bits. */ + ipcp_bits_lattice bits_lattice; /* Number of aggregate lattices */ int aggs_count; /* True if aggregate data were passed by reference (as opposed to by @@ -458,6 +515,21 @@ ipcp_alignment_lattice::print (FILE * f) fprintf (f, " Alignment %u, misalignment %u\n", align, misalign); } +void +ipcp_bits_lattice::print (FILE *f) +{ + if (top_p ()) + fprintf (f, " Bits unknown (TOP)\n"); + else if (bottom_p ()) + fprintf (f, " Bits unusable (BOTTOM)\n"); + else + { + fprintf (f, " Bits: value = "); print_hex (get_value (), f); + fprintf (f, ", mask = "); print_hex (get_mask (), f); + fprintf (f, "\n"); + } +} + /* Print all ipcp_lattices of all functions to F. */ static void @@ -484,6 +556,7 @@ print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits) fprintf (f, " ctxs: "); plats->ctxlat.print (f, dump_sources, dump_benefits); plats->alignment.print (f); + plats->bits_lattice.print (f); if (plats->virt_call) fprintf (f, " virt_call flag set\n"); @@ -911,6 +984,151 @@ ipcp_alignment_lattice::meet_with (const ipcp_alignment_lattice &other, return meet_with_1 (other.align, adjusted_misalign); } +/* Set lattice value to bottom, if it already isn't the case. */ + +bool +ipcp_bits_lattice::set_to_bottom () +{ + if (bottom_p ()) + return false; + m_lattice_val = IPA_BITS_VARYING; + m_value = 0; + m_mask = -1; + return true; +} + +/* Set to constant if it isn't already. Only meant to be called + when switching state from TOP. */ + +bool +ipcp_bits_lattice::set_to_constant (widest_int value, widest_int mask) +{ + gcc_assert (top_p ()); + m_lattice_val = IPA_BITS_CONSTANT; + m_value = value; + m_mask = mask; + return true; +} + +/* Convert operand to value, mask form. */ + +void +ipcp_bits_lattice::get_value_and_mask (tree operand, widest_int *valuep, widest_int *maskp) +{ + wide_int get_nonzero_bits (const_tree); + + if (TREE_CODE (operand) == INTEGER_CST) + { + *valuep = wi::to_widest (operand); + *maskp = 0; + } + else + { + *valuep = 0; + *maskp = -1; + } +} + +/* Meet operation, similar to ccp_lattice_meet, we xor values + if this->value, value have different values at same bit positions, we want + to drop that bit to varying. Return true if mask is changed. + This function assumes that the lattice value is in CONSTANT state */ + +bool +ipcp_bits_lattice::meet_with_1 (widest_int value, widest_int mask, + unsigned precision) +{ + gcc_assert (constant_p ()); + + widest_int old_mask = m_mask; + m_mask = (m_mask | mask) | (m_value ^ value); + + if (wi::sext (m_mask, precision) == -1) + return set_to_bottom (); + + return m_mask != old_mask; +} + +/* Meet the bits lattice with operand + described by ctxlat.set_contains_variable (); ret |= set_agg_lats_contain_variable (plats); ret |= plats->alignment.set_to_bottom (); + ret |= plats->bits_lattice.set_to_bottom (); return ret; } @@ -1003,6 +1222,7 @@ initialize_node_lattices (struct cgraph_node *node) plats->ctxlat.set_to_bottom (); set_agg_lats_to_bottom (plats); plats->alignment.set_to_bottom (); + plats->bits_lattice.set_to_bottom (); } else set_all_contains_variable (plats); @@ -1621,6 +1841,78 @@ propagate_alignment_accross_jump_function (cgraph_edge *cs, } } +/* Propagate bits across jfunc that is associated with + edge cs and update dest_lattice accordingly. */ + +bool +propagate_bits_accross_jump_function (cgraph_edge *cs, int idx, ipa_jump_func *jfunc, + ipcp_bits_lattice *dest_lattice) +{ + if (dest_lattice->bottom_p ()) + return false; + + enum availability availability; + cgraph_node *callee = cs->callee->function_symbol (&availability); + struct ipa_node_params *callee_info = IPA_NODE_REF (callee); + tree parm_type = ipa_get_type (callee_info, idx); + + /* For K&R C programs, ipa_get_type() could return NULL_TREE. + Avoid the transform for these cases. */ + if (!parm_type) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Setting dest_lattice to bottom, because" + "param %i type is NULL for %s\n", idx, + cs->callee->name ()); + + return dest_lattice->set_to_bottom (); + } + + unsigned precision = TYPE_PRECISION (parm_type); + signop sgn = TYPE_SIGN (parm_type); + + if (jfunc->type == IPA_JF_PASS_THROUGH) + { + struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); + enum tree_code code = ipa_get_jf_pass_through_operation (jfunc); + tree operand = NULL_TREE; + + if (code != NOP_EXPR) + operand = ipa_get_jf_pass_through_operand (jfunc); + + int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); + struct ipcp_param_lattices *src_lats + = ipa_get_parm_lattices (caller_info, src_idx); + + /* Try to propagate bits if src_lattice is bottom, but jfunc is known. + for eg consider: + int f(int x) + { + g (x & 0xff); + } + Assume lattice for x is bottom, however we can still propagate + result of x & 0xff == 0xff, which gets computed during ccp1 pass + and we store it in jump function during analysis stage. */ + + if (src_lats->bits_lattice.bottom_p () + && jfunc->bits.known) + return dest_lattice->meet_with (jfunc->bits.value, jfunc->bits.mask, + precision); + else + return dest_lattice->meet_with (src_lats->bits_lattice, precision, sgn, + code, operand); + } + + else if (jfunc->type == IPA_JF_ANCESTOR) + return dest_lattice->set_to_bottom (); + + else if (jfunc->bits.known) + return dest_lattice->meet_with (jfunc->bits.value, jfunc->bits.mask, precision); + + else + return dest_lattice->set_to_bottom (); +} + /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all other cases, return false). If there are no aggregate items, set @@ -1968,6 +2260,8 @@ propagate_constants_accross_call (struct cgraph_edge *cs) &dest_plats->ctxlat); ret |= propagate_alignment_accross_jump_function (cs, jump_func, &dest_plats->alignment); + ret |= propagate_bits_accross_jump_function (cs, i, jump_func, + &dest_plats->bits_lattice); ret |= propagate_aggs_accross_jump_function (cs, jump_func, dest_plats); } @@ -2936,6 +3230,19 @@ ipcp_propagate_stage (struct ipa_topo_info *topo) { struct ipa_node_params *info = IPA_NODE_REF (node); + /* In LTO we do not have PARM_DECLs but we would still like to be able to + look at types of parameters. */ + if (in_lto_p) + { + tree t = TYPE_ARG_TYPES (TREE_TYPE (node->decl)); + for (int k = 0; k < ipa_get_param_count (info) && t; k++) + { + gcc_assert (t != void_list_node); + info->descriptors[k].decl_or_type = TREE_VALUE (t); + t = t ? TREE_CHAIN (t) : NULL; + } + } + determine_versionability (node, info); if (node->has_gimple_body_p ()) { @@ -4592,6 +4899,81 @@ ipcp_store_alignment_results (void) } } +/* Look up all the bits information that we have discovered and copy it over + to the transformation summary. */ + +static void +ipcp_store_bits_results (void) +{ + cgraph_node *node; + + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) + { + ipa_node_params *info = IPA_NODE_REF (node); + bool dumped_sth = false; + bool found_useful_result = false; + + if (!opt_for_fn (node->decl, flag_ipa_bit_cp)) + { + if (dump_file) + fprintf (dump_file, "Not considering %s for ipa bitwise propagation " + "; -fipa-cp-bit: disabled.\n", + node->name ()); + continue; + } + + if (info->ipcp_orig_node) + info = IPA_NODE_REF (info->ipcp_orig_node); + + unsigned count = ipa_get_param_count (info); + for (unsigned i = 0; i < count; i++) + { + ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + if (plats->bits_lattice.constant_p ()) + { + found_useful_result = true; + break; + } + } + + if (!found_useful_result) + continue; + + ipcp_grow_transformations_if_necessary (); + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + vec_safe_reserve_exact (ts->bits, count); + + for (unsigned i = 0; i < count; i++) + { + ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + ipa_bits bits_jfunc; + + if (plats->bits_lattice.constant_p ()) + { + bits_jfunc.known = true; + bits_jfunc.value = plats->bits_lattice.get_value (); + bits_jfunc.mask = plats->bits_lattice.get_mask (); + } + else + bits_jfunc.known = false; + + ts->bits->quick_push (bits_jfunc); + if (!dump_file || !bits_jfunc.known) + continue; + if (!dumped_sth) + { + fprintf (dump_file, "Propagated bits info for function %s/%i:\n", + node->name (), node->order); + dumped_sth = true; + } + fprintf (dump_file, " param %i: value = ", i); + print_hex (bits_jfunc.value, dump_file); + fprintf (dump_file, ", mask = "); + print_hex (bits_jfunc.mask, dump_file); + fprintf (dump_file, "\n"); + } + } +} /* The IPCP driver. */ static unsigned int @@ -4625,6 +5007,8 @@ ipcp_driver (void) ipcp_decision_stage (&topo); /* Store results of alignment propagation. */ ipcp_store_alignment_results (); + /* Store results of bits propagation. */ + ipcp_store_bits_results (); /* Free all IPCP structures. */ free_toporder_info (&topo); diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c index 4385614e330..16297817f95 100644 --- a/gcc/ipa-prop.c +++ b/gcc/ipa-prop.c @@ -105,7 +105,7 @@ ipa_get_param_decl_index_1 (vec descriptors, tree ptree) count = descriptors.length (); for (i = 0; i < count; i++) - if (descriptors[i].decl == ptree) + if (descriptors[i].decl_or_type == ptree) return i; return -1; @@ -138,7 +138,7 @@ ipa_populate_param_decls (struct cgraph_node *node, param_num = 0; for (parm = fnargs; parm; parm = DECL_CHAIN (parm)) { - descriptors[param_num].decl = parm; + descriptors[param_num].decl_or_type = parm; descriptors[param_num].move_cost = estimate_move_cost (TREE_TYPE (parm), true); param_num++; @@ -168,10 +168,10 @@ void ipa_dump_param (FILE *file, struct ipa_node_params *info, int i) { fprintf (file, "param #%i", i); - if (info->descriptors[i].decl) + if (info->descriptors[i].decl_or_type) { fprintf (file, " "); - print_generic_expr (file, info->descriptors[i].decl, 0); + print_generic_expr (file, info->descriptors[i].decl_or_type, 0); } } @@ -302,6 +302,15 @@ ipa_print_node_jump_functions_for_edge (FILE *f, struct cgraph_edge *cs) } else fprintf (f, " Unknown alignment\n"); + + if (jump_func->bits.known) + { + fprintf (f, " value: "); print_hex (jump_func->bits.value, f); + fprintf (f, ", mask: "); print_hex (jump_func->bits.mask, f); + fprintf (f, "\n"); + } + else + fprintf (f, " Unknown bits\n"); } } @@ -381,6 +390,7 @@ ipa_set_jf_unknown (struct ipa_jump_func *jfunc) { jfunc->type = IPA_JF_UNKNOWN; jfunc->alignment.known = false; + jfunc->bits.known = false; } /* Set JFUNC to be a copy of another jmp (to be used by jump function @@ -1674,6 +1684,26 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi, else gcc_assert (!jfunc->alignment.known); + if (INTEGRAL_TYPE_P (TREE_TYPE (arg)) + && (TREE_CODE (arg) == SSA_NAME || TREE_CODE (arg) == INTEGER_CST)) + { + jfunc->bits.known = true; + + if (TREE_CODE (arg) == SSA_NAME) + { + jfunc->bits.value = 0; + jfunc->bits.mask = widest_int::from (get_nonzero_bits (arg), + TYPE_SIGN (TREE_TYPE (arg))); + } + else + { + jfunc->bits.value = wi::to_widest (arg); + jfunc->bits.mask = 0; + } + } + else + gcc_assert (!jfunc->bits.known); + if (is_gimple_ip_invariant (arg) || (TREE_CODE (arg) == VAR_DECL && is_global_var (arg) @@ -3690,6 +3720,18 @@ ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst, for (unsigned i = 0; i < src_alignments->length (); ++i) dst_alignments->quick_push ((*src_alignments)[i]); } + + if (src_trans && vec_safe_length (src_trans->bits) > 0) + { + ipcp_grow_transformations_if_necessary (); + src_trans = ipcp_get_transformation_summary (src); + const vec *src_bits = src_trans->bits; + vec *&dst_bits + = ipcp_get_transformation_summary (dst)->bits; + vec_safe_reserve_exact (dst_bits, src_bits->length ()); + for (unsigned i = 0; i < src_bits->length (); ++i) + dst_bits->quick_push ((*src_bits)[i]); + } } /* Register our cgraph hooks if they are not already there. */ @@ -4609,6 +4651,15 @@ ipa_write_jump_function (struct output_block *ob, streamer_write_uhwi (ob, jump_func->alignment.align); streamer_write_uhwi (ob, jump_func->alignment.misalign); } + + bp = bitpack_create (ob->main_stream); + bp_pack_value (&bp, jump_func->bits.known, 1); + streamer_write_bitpack (&bp); + if (jump_func->bits.known) + { + streamer_write_widest_int (ob, jump_func->bits.value); + streamer_write_widest_int (ob, jump_func->bits.mask); + } } /* Read in jump function JUMP_FUNC from IB. */ @@ -4685,6 +4736,17 @@ ipa_read_jump_function (struct lto_input_block *ib, } else jump_func->alignment.known = false; + + bp = streamer_read_bitpack (ib); + bool bits_known = bp_unpack_value (&bp, 1); + if (bits_known) + { + jump_func->bits.known = true; + jump_func->bits.value = streamer_read_widest_int (ib); + jump_func->bits.mask = streamer_read_widest_int (ib); + } + else + jump_func->bits.known = false; } /* Stream out parts of cgraph_indirect_call_info corresponding to CS that are @@ -5050,6 +5112,28 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node) } else streamer_write_uhwi (ob, 0); + + ts = ipcp_get_transformation_summary (node); + if (ts && vec_safe_length (ts->bits) > 0) + { + count = ts->bits->length (); + streamer_write_uhwi (ob, count); + + for (unsigned i = 0; i < count; ++i) + { + const ipa_bits& bits_jfunc = (*ts->bits)[i]; + struct bitpack_d bp = bitpack_create (ob->main_stream); + bp_pack_value (&bp, bits_jfunc.known, 1); + streamer_write_bitpack (&bp); + if (bits_jfunc.known) + { + streamer_write_widest_int (ob, bits_jfunc.value); + streamer_write_widest_int (ob, bits_jfunc.mask); + } + } + } + else + streamer_write_uhwi (ob, 0); } /* Stream in the aggregate value replacement chain for NODE from IB. */ @@ -5102,6 +5186,26 @@ read_ipcp_transformation_info (lto_input_block *ib, cgraph_node *node, } } } + + count = streamer_read_uhwi (ib); + if (count > 0) + { + ipcp_grow_transformations_if_necessary (); + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + vec_safe_grow_cleared (ts->bits, count); + + for (i = 0; i < count; i++) + { + ipa_bits& bits_jfunc = (*ts->bits)[i]; + struct bitpack_d bp = streamer_read_bitpack (ib); + bits_jfunc.known = bp_unpack_value (&bp, 1); + if (bits_jfunc.known) + { + bits_jfunc.value = streamer_read_widest_int (ib); + bits_jfunc.mask = streamer_read_widest_int (ib); + } + } + } } /* Write all aggregate replacement for nodes in set. */ @@ -5404,6 +5508,56 @@ ipcp_update_alignments (struct cgraph_node *node) } } +/* Update bits info of formal parameters as described in + ipcp_transformation_summary. */ + +static void +ipcp_update_bits (struct cgraph_node *node) +{ + tree parm = DECL_ARGUMENTS (node->decl); + tree next_parm = parm; + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + + if (!ts || vec_safe_length (ts->bits) == 0) + return; + + vec &bits = *ts->bits; + unsigned count = bits.length (); + + for (unsigned i = 0; i < count; ++i, parm = next_parm) + { + if (node->clone.combined_args_to_skip + && bitmap_bit_p (node->clone.combined_args_to_skip, i)) + continue; + + gcc_checking_assert (parm); + next_parm = DECL_CHAIN (parm); + + if (!bits[i].known + || !INTEGRAL_TYPE_P (TREE_TYPE (parm)) + || !is_gimple_reg (parm)) + continue; + + tree ddef = ssa_default_def (DECL_STRUCT_FUNCTION (node->decl), parm); + if (!ddef) + continue; + + if (dump_file) + { + fprintf (dump_file, "Adjusting mask for param %u to ", i); + print_hex (bits[i].mask, dump_file); + fprintf (dump_file, "\n"); + } + + unsigned prec = TYPE_PRECISION (TREE_TYPE (ddef)); + signop sgn = TYPE_SIGN (TREE_TYPE (ddef)); + + wide_int nonzero_bits = wide_int::from (bits[i].mask, prec, UNSIGNED) + | wide_int::from (bits[i].value, prec, sgn); + set_nonzero_bits (ddef, nonzero_bits); + } +} + /* IPCP transformation phase doing propagation of aggregate values. */ unsigned int @@ -5423,6 +5577,7 @@ ipcp_transform_function (struct cgraph_node *node) node->name (), node->order); ipcp_update_alignments (node); + ipcp_update_bits (node); aggval = ipa_get_agg_replacements_for_node (node); if (!aggval) return 0; diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index e32d078edb3..e5a56daeced 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -154,6 +154,19 @@ struct GTY(()) ipa_alignment unsigned misalign; }; +/* Information about zero/non-zero bits. */ +struct GTY(()) ipa_bits +{ + /* The propagated value. */ + widest_int value; + /* Mask corresponding to the value. + Similar to ccp_lattice_t, if xth bit of mask is 0, + implies xth bit of value is constant. */ + widest_int mask; + /* True if jump function is known. */ + bool known; +}; + /* A jump function for a callsite represents the values passed as actual arguments of the callsite. See enum jump_func_type for the various types of jump functions supported. */ @@ -166,6 +179,9 @@ struct GTY (()) ipa_jump_func /* Information about alignment of pointers. */ struct ipa_alignment alignment; + /* Information about zero/non-zero bits. */ + struct ipa_bits bits; + enum jump_func_type type; /* Represents a value of a jump function. pass_through is used only in jump function context. constant represents the actual constant in constant jump @@ -283,8 +299,11 @@ ipa_get_jf_ancestor_type_preserved (struct ipa_jump_func *jfunc) struct ipa_param_descriptor { - /* PARAM_DECL of this parameter. */ - tree decl; + /* In analysis and modification phase, this is the PARAM_DECL of this + parameter, in IPA LTO phase, this is the type of the the described + parameter or NULL if not known. Do not read this field directly but + through ipa_get_param and ipa_get_type as appropriate. */ + tree decl_or_type; /* If all uses of the parameter are described by ipa-prop structures, this says how many there are. If any use could not be described by means of ipa-prop structures, this is IPA_UNDESCRIBED_USE. */ @@ -402,13 +421,31 @@ ipa_get_param_count (struct ipa_node_params *info) /* Return the declaration of Ith formal parameter of the function corresponding to INFO. Note there is no setter function as this array is built just once - using ipa_initialize_node_params. */ + using ipa_initialize_node_params. This function should not be called in + WPA. */ static inline tree ipa_get_param (struct ipa_node_params *info, int i) { gcc_checking_assert (!flag_wpa); - return info->descriptors[i].decl; + tree t = info->descriptors[i].decl_or_type; + gcc_checking_assert (TREE_CODE (t) == PARM_DECL); + return t; +} + +/* Return the type of Ith formal parameter of the function corresponding + to INFO if it is known or NULL if not. */ + +static inline tree +ipa_get_type (struct ipa_node_params *info, int i) +{ + tree t = info->descriptors[i].decl_or_type; + if (!t) + return NULL; + if (TYPE_P (t)) + return t; + gcc_checking_assert (TREE_CODE (t) == PARM_DECL); + return TREE_TYPE (t); } /* Return the move cost of Ith formal parameter of the function corresponding @@ -482,6 +519,8 @@ struct GTY(()) ipcp_transformation_summary ipa_agg_replacement_value *agg_values; /* Alignment information for pointers. */ vec *alignments; + /* Known bits information. */ + vec *bits; }; void ipa_set_node_agg_value_chain (struct cgraph_node *node, diff --git a/gcc/opts.c b/gcc/opts.c index b927640c1f7..bc0570dbd5e 100644 --- a/gcc/opts.c +++ b/gcc/opts.c @@ -505,6 +505,7 @@ static const struct default_options default_options_table[] = { OPT_LEVELS_2_PLUS, OPT_ftree_switch_conversion, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fipa_cp, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fipa_cp_alignment, NULL, 1 }, + { OPT_LEVELS_2_PLUS, OPT_fipa_bit_cp, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fdevirtualize, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fdevirtualize_speculatively, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fipa_sra, NULL, 1 }, @@ -1422,6 +1423,9 @@ enable_fdo_optimizations (struct gcc_options *opts, if (!opts_set->x_flag_ipa_cp_alignment && value && opts->x_flag_ipa_cp) opts->x_flag_ipa_cp_alignment = value; + if (!opts_set->x_flag_ipa_bit_cp + && value && opts->x_flag_ipa_cp) + opts->x_flag_ipa_bit_cp = value; if (!opts_set->x_flag_predictive_commoning) opts->x_flag_predictive_commoning = value; if (!opts_set->x_flag_unswitch_loops) diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index c39e1914efc..e51756d2d97 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,10 @@ +2016-08-26 Prathamesh Kulkarni + Martin Jambhor + + * gcc.dg/ipa/propbits-1.c: New test-case. + * gcc.dg/ipa/propbits-2.c: Likewise. + * gcc.dg/ipa/propbits-3.c: Likewise. + 2016-08-25 Steven g. Kargl PR fortran/77351 diff --git a/gcc/testsuite/gcc.dg/ipa/propbits-1.c b/gcc/testsuite/gcc.dg/ipa/propbits-1.c new file mode 100644 index 00000000000..8ec372d81f0 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/propbits-1.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fno-early-inlining -fdump-ipa-cp" } */ + +__attribute__((noinline)) +static int f(int x) +{ + int some_op(int); + return some_op (x); +} + +int main(void) +{ + int a = f(1); + int b = f(2); + int c = f(4); + return a + b + c; +} + +/* { dg-final { scan-ipa-dump "Adjusting mask for param 0 to 0x7" "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/propbits-2.c b/gcc/testsuite/gcc.dg/ipa/propbits-2.c new file mode 100644 index 00000000000..3a960f03108 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/propbits-2.c @@ -0,0 +1,41 @@ +/* x's mask should be meet(0xc, 0x3) == 0xf */ + +/* { dg-do compile } */ +/* { dg-options "-O2 -fno-early-inlining -fdump-ipa-cp" } */ + +extern int pass_test (); +extern int fail_test (); + +__attribute__((noinline)) +static int f1(int x) +{ + if ((x & ~0xf) == 0) + return pass_test (); + else + return fail_test (); +} + +__attribute__((noinline)) +static int f2(int y) +{ + return f1(y & 0x03); +} + +__attribute__((noinline)) +static int f3(int z) +{ + return f1(z & 0xc); +} + +extern int a; +extern int b; + +int main(void) +{ + int k = f2(a); + int l = f3(b); + return k + l; +} + +/* { dg-final { scan-ipa-dump "Adjusting mask for param 0 to 0xf" "cp" } } */ +/* { dg-final { scan-dump-tree-not "fail_test" "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/propbits-3.c b/gcc/testsuite/gcc.dg/ipa/propbits-3.c new file mode 100644 index 00000000000..44744cdde02 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/propbits-3.c @@ -0,0 +1,22 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fno-early-inlining -fdump-ipa-cp" } */ + +__attribute__((noinline)) +static int f(int x) +{ + extern int limit; + extern int f2(int); + + if (x == limit) + return x; + int k = f(x + 1); + return f2 (k); +} + +int main(int argc, char **argv) +{ + int k = f(argc & 0xff); + return k; +} + +/* { dg-final { scan-ipa-dump-not "Adjusting mask for" "cp" } } */ diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c index 5d5386e4f8f..987130403ce 100644 --- a/gcc/tree-ssa-ccp.c +++ b/gcc/tree-ssa-ccp.c @@ -142,7 +142,7 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "stor-layout.h" #include "optabs-query.h" - +#include "tree-ssa-ccp.h" /* Possible lattice values. */ typedef enum @@ -536,9 +536,9 @@ set_lattice_value (tree var, ccp_prop_value_t *new_val) static ccp_prop_value_t get_value_for_expr (tree, bool); static ccp_prop_value_t bit_value_binop (enum tree_code, tree, tree, tree); -static void bit_value_binop_1 (enum tree_code, tree, widest_int *, widest_int *, - tree, const widest_int &, const widest_int &, - tree, const widest_int &, const widest_int &); +void bit_value_binop (enum tree_code, signop, int, widest_int *, widest_int *, + signop, int, const widest_int &, const widest_int &, + signop, int, const widest_int &, const widest_int &); /* Return a widest_int that can be used for bitwise simplifications from VAL. */ @@ -894,7 +894,7 @@ do_dbg_cnt (void) Return TRUE when something was optimized. */ static bool -ccp_finalize (bool nonzero_p) +ccp_finalize (bool nonzero_p) { bool something_changed; unsigned i; @@ -920,7 +920,8 @@ ccp_finalize (bool nonzero_p) val = get_value (name); if (val->lattice_val != CONSTANT - || TREE_CODE (val->value) != INTEGER_CST) + || TREE_CODE (val->value) != INTEGER_CST + || val->mask == 0) continue; if (POINTER_TYPE_P (TREE_TYPE (name))) @@ -1224,10 +1225,11 @@ ccp_fold (gimple *stmt) RVAL and RMASK representing a value of type RTYPE and set the value, mask pair *VAL and *MASK to the result. */ -static void -bit_value_unop_1 (enum tree_code code, tree type, - widest_int *val, widest_int *mask, - tree rtype, const widest_int &rval, const widest_int &rmask) +void +bit_value_unop (enum tree_code code, signop type_sgn, int type_precision, + widest_int *val, widest_int *mask, + signop rtype_sgn, int rtype_precision, + const widest_int &rval, const widest_int &rmask) { switch (code) { @@ -1240,25 +1242,23 @@ bit_value_unop_1 (enum tree_code code, tree type, { widest_int temv, temm; /* Return ~rval + 1. */ - bit_value_unop_1 (BIT_NOT_EXPR, type, &temv, &temm, type, rval, rmask); - bit_value_binop_1 (PLUS_EXPR, type, val, mask, - type, temv, temm, type, 1, 0); + bit_value_unop (BIT_NOT_EXPR, type_sgn, type_precision, &temv, &temm, + type_sgn, type_precision, rval, rmask); + bit_value_binop (PLUS_EXPR, type_sgn, type_precision, val, mask, + type_sgn, type_precision, temv, temm, + type_sgn, type_precision, 1, 0); break; } CASE_CONVERT: { - signop sgn; - /* First extend mask and value according to the original type. */ - sgn = TYPE_SIGN (rtype); - *mask = wi::ext (rmask, TYPE_PRECISION (rtype), sgn); - *val = wi::ext (rval, TYPE_PRECISION (rtype), sgn); + *mask = wi::ext (rmask, rtype_precision, rtype_sgn); + *val = wi::ext (rval, rtype_precision, rtype_sgn); /* Then extend mask and value according to the target type. */ - sgn = TYPE_SIGN (type); - *mask = wi::ext (*mask, TYPE_PRECISION (type), sgn); - *val = wi::ext (*val, TYPE_PRECISION (type), sgn); + *mask = wi::ext (*mask, type_precision, type_sgn); + *val = wi::ext (*val, type_precision, type_sgn); break; } @@ -1272,15 +1272,14 @@ bit_value_unop_1 (enum tree_code code, tree type, R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */ -static void -bit_value_binop_1 (enum tree_code code, tree type, - widest_int *val, widest_int *mask, - tree r1type, const widest_int &r1val, - const widest_int &r1mask, tree r2type, - const widest_int &r2val, const widest_int &r2mask) +void +bit_value_binop (enum tree_code code, signop sgn, int width, + widest_int *val, widest_int *mask, + signop r1type_sgn, int r1type_precision, + const widest_int &r1val, const widest_int &r1mask, + signop r2type_sgn, int r2type_precision, + const widest_int &r2val, const widest_int &r2mask) { - signop sgn = TYPE_SIGN (type); - int width = TYPE_PRECISION (type); bool swap_p = false; /* Assume we'll get a constant result. Use an initial non varying @@ -1406,11 +1405,11 @@ bit_value_binop_1 (enum tree_code code, tree type, case MINUS_EXPR: { widest_int temv, temm; - bit_value_unop_1 (NEGATE_EXPR, r2type, &temv, &temm, - r2type, r2val, r2mask); - bit_value_binop_1 (PLUS_EXPR, type, val, mask, - r1type, r1val, r1mask, - r2type, temv, temm); + bit_value_unop (NEGATE_EXPR, r2type_sgn, r2type_precision, &temv, &temm, + r2type_sgn, r2type_precision, r2val, r2mask); + bit_value_binop (PLUS_EXPR, sgn, width, val, mask, + r1type_sgn, r1type_precision, r1val, r1mask, + r2type_sgn, r2type_precision, temv, temm); break; } @@ -1472,7 +1471,7 @@ bit_value_binop_1 (enum tree_code code, tree type, break; /* For comparisons the signedness is in the comparison operands. */ - sgn = TYPE_SIGN (r1type); + sgn = r1type_sgn; /* If we know the most significant bits we know the values value ranges by means of treating varying bits as zero @@ -1525,8 +1524,9 @@ bit_value_unop (enum tree_code code, tree type, tree rhs) gcc_assert ((rval.lattice_val == CONSTANT && TREE_CODE (rval.value) == INTEGER_CST) || wi::sext (rval.mask, TYPE_PRECISION (TREE_TYPE (rhs))) == -1); - bit_value_unop_1 (code, type, &value, &mask, - TREE_TYPE (rhs), value_to_wide_int (rval), rval.mask); + bit_value_unop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask, + TYPE_SIGN (TREE_TYPE (rhs)), TYPE_PRECISION (TREE_TYPE (rhs)), + value_to_wide_int (rval), rval.mask); if (wi::sext (mask, TYPE_PRECISION (type)) != -1) { val.lattice_val = CONSTANT; @@ -1571,9 +1571,12 @@ bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2) && TREE_CODE (r2val.value) == INTEGER_CST) || wi::sext (r2val.mask, TYPE_PRECISION (TREE_TYPE (rhs2))) == -1); - bit_value_binop_1 (code, type, &value, &mask, - TREE_TYPE (rhs1), value_to_wide_int (r1val), r1val.mask, - TREE_TYPE (rhs2), value_to_wide_int (r2val), r2val.mask); + bit_value_binop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask, + TYPE_SIGN (TREE_TYPE (rhs1)), TYPE_PRECISION (TREE_TYPE (rhs1)), + value_to_wide_int (r1val), r1val.mask, + TYPE_SIGN (TREE_TYPE (rhs2)), TYPE_PRECISION (TREE_TYPE (rhs2)), + value_to_wide_int (r2val), r2val.mask); + if (wi::sext (mask, TYPE_PRECISION (type)) != -1) { val.lattice_val = CONSTANT; @@ -1672,9 +1675,10 @@ bit_value_assume_aligned (gimple *stmt, tree attr, ccp_prop_value_t ptrval, align = build_int_cst_type (type, -aligni); alignval = get_value_for_expr (align, true); - bit_value_binop_1 (BIT_AND_EXPR, type, &value, &mask, - type, value_to_wide_int (ptrval), ptrval.mask, - type, value_to_wide_int (alignval), alignval.mask); + bit_value_binop (BIT_AND_EXPR, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask, + TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (ptrval), ptrval.mask, + TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (alignval), alignval.mask); + if (wi::sext (mask, TYPE_PRECISION (type)) != -1) { val.lattice_val = CONSTANT; @@ -2409,7 +2413,7 @@ do_ssa_ccp (bool nonzero_p) ccp_initialize (); ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node); - if (ccp_finalize (nonzero_p)) + if (ccp_finalize (nonzero_p || flag_ipa_bit_cp)) { todo = (TODO_cleanup_cfg | TODO_update_ssa); diff --git a/gcc/tree-ssa-ccp.h b/gcc/tree-ssa-ccp.h new file mode 100644 index 00000000000..35383c5e942 --- /dev/null +++ b/gcc/tree-ssa-ccp.h @@ -0,0 +1,29 @@ +/* Copyright (C) 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 +. */ + +#ifndef TREE_SSA_CCP_H +#define TREE_SSA_CCP_H + +void bit_value_binop (enum tree_code, signop, int, widest_int *, widest_int *, + signop, int, const widest_int &, const widest_int &, + signop, int, const widest_int &, const widest_int &); + +void bit_value_unop (enum tree_code, signop, int, widest_int *, widest_int *, + signop, int, const widest_int &, const widest_int &); + +#endif -- 2.30.2