On Sun, 8 Nov 2020, Jan Hubicka wrote:
> Hello,
> I would like to finally address the problem with ipa-icf being overly
> conservating on memory operand equality and having overly weak hash
> function. This leads to code size, compile time and compile time memory
> use regressions sompared to earlier versions where we merged more
> aggressively because of weaker TBAA.
>
> Basically comparing memory operand should match for memory accesses that
> does same base+offset computations and have same behaviour WRT TBAA.
> When optimizing for size we would like to discard TBAA info in the case
> of TBAA mismatch if they perform same actual load.
>
> From past discussion we conlcuded that operand_equal_p (in fold-const)
> is not good place to address this since it is used for generic trees as
> well. The TBAA matching/hashing is best done in tree-ssa-alias since it
> is inherently tied to its internals.
>
> I would like to do following
> 1) keep track what parameters are memory operands. This is implemented
> in the attached patch.
> 2) Add ao_ref interface for hasing and comparing references inheriting
> fold-const.h:operand_compare which then can feed ICF equivalences
> adding:
>
> int ao_ref_compare (ao_ref ref1, ao_ref ref2)
>
> It will return mask how refs differ:
>
> AO_REF_SEMANTICS if the actual access is different
> (i.e. different base, offset or size of the access)
> AO_REF_BASE_ALIAS_SET if base alias set differs.
> AO_REF_ALIAS_SET if base ref set differs.
> AO_REF_ACCESS_PATH if access path differs.
>
> and
>
> ao_ref_hash (ao_ref hash, int flags)
>
> which will compute hashtable where flags are same AO_REF as above.
>
> Initial implementation can compare alias sets for !LTO and for LTO
> compare TYPE_MAIN_VARIANTS. We currently have no way to hash access
> types for LTO, I plan to add that incremntally.
>
> 3) Make ipa_icf use ao_ref_compare == 0 to do current merging and
> !(ao_ref_compare & AO_REF_SEMANTICS) for size optimized code.
>
> 4) Add way of hading alias sets for LTO. This can be done by moving
> canonical type hash out of lto that I think would be nice cleanup
> anyway. I have older patch for that (it needs to be untied from
> TYPE_CANONICAL computation by adding extra hashtable but it has no
> performance impact)
>
> Other alternative is to simply collect list of types relevant and
> compare them at WPA time as done by earlier Martin's patch.
>
> Later we could play with merging TBAA mismatches memory references with
> -O2+ and clearing them only for uninlined clones, but this is tricky and
> can wait for next stage1.
>
> Does this make sense?
Well, guess we have to see if it works out and how ugly it will be.
Definitely not sth to rush for this stage1 ...
> Attached patch implements set 1. I use walk_stmt_load_store_ops to
> discover memor operands by storing them to pointer set. This has the
> expense of extra hashing. An alternative would be to embed the logic
> into icf walkers, but it seems to be fast enough and I do not see
> that as a good motivation to duplicate the logic into comparsion and
> hashers.
>
> I have bootstrapped/regtstested on x86_64 and would like to commit it
> after some discussion tomorrow.
>
> Honza
>
>
> 2020-11-08 Jan Hubicka <hubi...@ucw.cz>
>
> * ipa-icf-gimple.c: Include gimple-walk.h.
> (func_checker::compare_ssa_name): Update call of compare_operand.
> (func_checker::hash_operand): Fix comment and add variant taking
> operand_access_type parameter.
> (func_checker::compare_operand): Add operand_access_type parameter.
> (func_checker::compare_asm_inputs_outputs): Add
> operand_access_type_map parameter; update use of
> func_checker::compare_operand.
> (func_checker::compare_gimple_call): Update use of
> func_checker::compare_operand.
> (func_checker::compare_gimple_assign): Likewise.
> (func_checker::compare_gimple_cond): Likewise.
> (func_checker::compare_gimple_switch): Likewise.
> (func_checker::compare_gimple_return): Likewise.
> (func_checker::compare_gimple_goto): Likewise.
> (func_checker::compare_gimple_asm): Likewise.
> (visit_load_store): New static functio.
> (func_checker::classify_operands): New member function.
> (func_checker::get_operand_access_type): New member function.
> * ipa-icf-gimple.h (func_checker::operand_access_type): New enum
> (func_checker::operand_access_type_map): New typedef.
> (func_checker::compare_operand): Update prototype.
> (func_checker::compare_asm_inputs_outputs): Likewise.
> (func_checker::cleassify_operands): Declare.
> (func_checker::get_operand_access_type): Declare.
> (func_checker::hash_operand): New variant with operand_access_type.
> * ipa-icf.c (sem_function::hash_stmt): Update uses of hash_operand.
> (sem_function::compare_phi_node): Update use of compare_operand.
> * tree-ssa-structalias.c (find_func_aliases_for_builtin_call):
>
> diff --git a/gcc/ipa-icf-gimple.c b/gcc/ipa-icf-gimple.c
> index d5423a7e9b2..f75951f7c49 100644
> --- a/gcc/ipa-icf-gimple.c
> +++ b/gcc/ipa-icf-gimple.c
> @@ -38,6 +38,7 @@ along with GCC; see the file COPYING3. If not see
> #include "builtins.h"
> #include "cfgloop.h"
> #include "attribs.h"
> +#include "gimple-walk.h"
>
> #include "ipa-icf-gimple.h"
>
> @@ -109,7 +110,7 @@ func_checker::compare_ssa_name (const_tree t1, const_tree
> t2)
> tree b1 = SSA_NAME_VAR (t1);
> tree b2 = SSA_NAME_VAR (t2);
>
> - return compare_operand (b1, b2);
> + return compare_operand (b1, b2, OP_NORMAL);
> }
>
> return true;
> @@ -212,8 +213,8 @@ func_checker::compatible_types_p (tree t1, tree t2)
> return true;
> }
>
> -/* Function compare for equality given trees T1 and T2 which
> - can be either a constant or a declaration type. */
> +/* Add hash of ARG to HSTATE. FLAGS have same meaning
> + as for operand_equal_p. Works only if operand acces type is OP_NORMAL.
> */
>
> void
> func_checker::hash_operand (const_tree arg, inchash::hash &hstate,
> @@ -246,6 +247,16 @@ func_checker::hash_operand (const_tree arg,
> inchash::hash &hstate,
> return operand_compare::hash_operand (arg, hstate, flags);
> }
>
> +/* Add hash of ARG accesses according to ACCESS to HSTATE.
> + FLAGS have same meaning as for operand_equal_p. */
> +
> +void
> +func_checker::hash_operand (const_tree arg, inchash::hash &hstate,
> + unsigned int flags, operand_access_type)
> +{
> + return hash_operand (arg, hstate, flags);
> +}
> +
> bool
> func_checker::operand_equal_p (const_tree t1, const_tree t2,
> unsigned int flags)
> @@ -291,12 +302,13 @@ func_checker::operand_equal_p (const_tree t1,
> const_tree t2,
> return operand_compare::operand_equal_p (t1, t2, flags);
> }
>
> -/* Function responsible for comparison of various operands T1 and T2.
> +/* Function responsible for comparison of various operands T1 and T2
> + which are accessed as ACCESS.
> If these components, from functions FUNC1 and FUNC2, are equal, true
> is returned. */
>
> bool
> -func_checker::compare_operand (tree t1, tree t2)
> +func_checker::compare_operand (tree t1, tree t2, operand_access_type access)
> {
> if (!t1 && !t2)
> return true;
> @@ -304,11 +316,21 @@ func_checker::compare_operand (tree t1, tree t2)
> return false;
> if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
> return true;
> - return return_false_with_msg ("operand_equal_p failed");
> + switch (access)
> + {
> + case OP_MEMORY:
> + return return_false_with_msg
> + ("operand_equal_p failed (access == memory)");
> + case OP_NORMAL:
> + return return_false_with_msg
> + ("operand_equal_p failed (access == normal)");
> + }
> + gcc_unreachable ();
> }
>
> bool
> -func_checker::compare_asm_inputs_outputs (tree t1, tree t2)
> +func_checker::compare_asm_inputs_outputs (tree t1, tree t2,
> + operand_access_type_map *map)
> {
> gcc_assert (TREE_CODE (t1) == TREE_LIST);
> gcc_assert (TREE_CODE (t2) == TREE_LIST);
> @@ -318,7 +340,8 @@ func_checker::compare_asm_inputs_outputs (tree t1, tree
> t2)
> if (!t2)
> return false;
>
> - if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2)))
> + if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2),
> + get_operand_access_type (map, t1)))
> return return_false ();
>
> tree p1 = TREE_PURPOSE (t1);
> @@ -545,9 +568,12 @@ func_checker::compare_gimple_call (gcall *s1, gcall *s2)
> if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
> return false;
>
> + operand_access_type_map map (5);
> + classify_operands (s1, &map);
> +
> t1 = gimple_call_fn (s1);
> t2 = gimple_call_fn (s2);
> - if (!compare_operand (t1, t2))
> + if (!compare_operand (t1, t2, get_operand_access_type (&map, t1)))
> return return_false ();
>
> /* Compare flags. */
> @@ -579,7 +605,8 @@ func_checker::compare_gimple_call (gcall *s1, gcall *s2)
> tree chain2 = gimple_call_chain (s2);
> if ((chain1 && !chain2)
> || (!chain1 && chain2)
> - || !compare_operand (chain1, chain2))
> + || !compare_operand (chain1, chain2,
> + get_operand_access_type (&map, chain1)))
> return return_false_with_msg ("static call chains are different");
>
> /* Checking of argument. */
> @@ -588,7 +615,7 @@ func_checker::compare_gimple_call (gcall *s1, gcall *s2)
> t1 = gimple_call_arg (s1, i);
> t2 = gimple_call_arg (s2, i);
>
> - if (!compare_operand (t1, t2))
> + if (!compare_operand (t1, t2, get_operand_access_type (&map, t1)))
> return return_false_with_msg ("GIMPLE call operands are different");
> }
>
> @@ -596,7 +623,7 @@ func_checker::compare_gimple_call (gcall *s1, gcall *s2)
> t1 = gimple_get_lhs (s1);
> t2 = gimple_get_lhs (s2);
>
> - return compare_operand (t1, t2);
> + return compare_operand (t1, t2, get_operand_access_type (&map, t1));
> }
>
>
> @@ -622,6 +649,9 @@ func_checker::compare_gimple_assign (gimple *s1, gimple
> *s2)
> if (code1 != code2)
> return false;
>
> + operand_access_type_map map (5);
> + classify_operands (s1, &map);
> +
> for (i = 0; i < gimple_num_ops (s1); i++)
> {
> arg1 = gimple_op (s1, i);
> @@ -634,7 +664,7 @@ func_checker::compare_gimple_assign (gimple *s1, gimple
> *s2)
> return return_false_with_msg ("GIMPLE NOP LHS type mismatch");
> }
>
> - if (!compare_operand (arg1, arg2))
> + if (!compare_operand (arg1, arg2, get_operand_access_type (&map,
> arg1)))
> return return_false_with_msg ("GIMPLE assignment operands "
> "are different");
> }
> @@ -661,13 +691,13 @@ func_checker::compare_gimple_cond (gimple *s1, gimple
> *s2)
> t1 = gimple_cond_lhs (s1);
> t2 = gimple_cond_lhs (s2);
>
> - if (!compare_operand (t1, t2))
> + if (!compare_operand (t1, t2, OP_NORMAL))
> return false;
>
> t1 = gimple_cond_rhs (s1);
> t2 = gimple_cond_rhs (s2);
>
> - return compare_operand (t1, t2);
> + return compare_operand (t1, t2, OP_NORMAL);
> }
>
> /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
> @@ -706,7 +736,7 @@ func_checker::compare_gimple_switch (const gswitch *g1,
> const gswitch *g2)
> tree t1 = gimple_switch_index (g1);
> tree t2 = gimple_switch_index (g2);
>
> - if (!compare_operand (t1, t2))
> + if (!compare_operand (t1, t2, OP_NORMAL))
> return false;
>
> for (i = 0; i < lsize1; i++)
> @@ -733,7 +763,7 @@ func_checker::compare_gimple_switch (const gswitch *g1,
> const gswitch *g2)
> label1 = CASE_LABEL (label1);
> label2 = CASE_LABEL (label2);
>
> - if (!compare_operand (label1, label2))
> + if (!compare_operand (label1, label2, OP_NORMAL))
> return return_false_with_msg ("switch label_exprs are different");
> }
> else if (!tree_int_cst_equal (label1, label2))
> @@ -758,7 +788,10 @@ func_checker::compare_gimple_return (const greturn *g1,
> const greturn *g2)
> if (t1 == NULL && t2 == NULL)
> return true;
> else
> - return compare_operand (t1, t2);
> + {
> + operand_access_type_map map (3);
> + return compare_operand (t1, t2, get_operand_access_type (&map, t1));
> + }
> }
>
> /* Verifies for given GIMPLEs S1 and S2 that
> @@ -775,7 +808,7 @@ func_checker::compare_gimple_goto (gimple *g1, gimple *g2)
> if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) !=
> SSA_NAME)
> return false;
>
> - return compare_operand (dest1, dest2);
> + return compare_operand (dest1, dest2, OP_NORMAL);
> }
>
> /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
> @@ -819,12 +852,15 @@ func_checker::compare_gimple_asm (const gasm *g1, const
> gasm *g2)
> if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
> return return_false_with_msg ("ASM strings are different");
>
> + operand_access_type_map map (5);
> + classify_operands (g1, &map);
> +
> for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
> {
> tree input1 = gimple_asm_input_op (g1, i);
> tree input2 = gimple_asm_input_op (g2, i);
>
> - if (!compare_asm_inputs_outputs (input1, input2))
> + if (!compare_asm_inputs_outputs (input1, input2, &map))
> return return_false_with_msg ("ASM input is different");
> }
>
> @@ -833,7 +869,7 @@ func_checker::compare_gimple_asm (const gasm *g1, const
> gasm *g2)
> tree output1 = gimple_asm_output_op (g1, i);
> tree output2 = gimple_asm_output_op (g2, i);
>
> - if (!compare_asm_inputs_outputs (output1, output2))
> + if (!compare_asm_inputs_outputs (output1, output2, &map))
> return return_false_with_msg ("ASM output is different");
> }
>
> @@ -850,4 +886,35 @@ func_checker::compare_gimple_asm (const gasm *g1, const
> gasm *g2)
> return true;
> }
>
> +/* Helper for func_checker::classify_operands. Record that T is a load. */
> +
> +static bool
> +visit_load_store (gimple *, tree t, tree, void *data)
> +{
> + func_checker::operand_access_type_map *map =
> + (func_checker::operand_access_type_map *) data;
> + map->add (t);
> + return false;
> +}
> +
> +/* Compute hash map determining access types of operands. */
> +
> +void
> +func_checker::classify_operands (const gimple *stmt,
> + operand_access_type_map *map)
> +{
> + walk_stmt_load_store_ops (const_cast <gimple *> (stmt),
> + (void *)map, visit_load_store, visit_load_store);
> +}
> +
> +/* Return access type of a given operand. */
> +
> +func_checker::operand_access_type
> +func_checker::get_operand_access_type (operand_access_type_map *map, tree t)
> +{
> + if (map->contains (t))
> + return OP_MEMORY;
> + return OP_NORMAL;
> +}
> +
> } // ipa_icf_gimple namespace
> diff --git a/gcc/ipa-icf-gimple.h b/gcc/ipa-icf-gimple.h
> index 28459d217ea..ed2da18d5b7 100644
> --- a/gcc/ipa-icf-gimple.h
> +++ b/gcc/ipa-icf-gimple.h
> @@ -200,14 +200,19 @@ public:
> /* Verification function for declaration trees T1 and T2. */
> bool compare_decl (const_tree t1, const_tree t2);
>
> + /* Compute hash map MAP that determines loads and stores of STMT. */
> + enum operand_access_type {OP_MEMORY, OP_NORMAL};
> + typedef hash_set<tree> operand_access_type_map;
> +
> /* Function responsible for comparison of various operands T1 and T2.
> If these components, from functions FUNC1 and FUNC2, are equal, true
> is returned. */
> - bool compare_operand (tree t1, tree t2);
> + bool compare_operand (tree t1, tree t2, operand_access_type type);
>
> /* Compares GIMPLE ASM inputs (or outputs) where we iterate tree chain
> and compare both TREE_PURPOSEs and TREE_VALUEs. */
> - bool compare_asm_inputs_outputs (tree t1, tree t2);
> + bool compare_asm_inputs_outputs (tree t1, tree t2,
> + operand_access_type_map *map);
>
> /* Verifies that trees T1 and T2, representing function declarations
> are equivalent from perspective of ICF. */
> @@ -230,7 +235,13 @@ public:
> first parameter of a function. */
> static bool compatible_types_p (tree t1, tree t2);
>
> + /* Compute hash map determining access types of operands. */
> + static void classify_operands (const gimple *stmt,
> + operand_access_type_map *map);
>
> + /* Return access type of a given operand. */
> + static operand_access_type get_operand_access_type
> + (operand_access_type_map *map, tree);
> private:
> /* Vector mapping source SSA names to target ones. */
> vec <int> m_source_ssa_names;
> @@ -272,6 +283,8 @@ public:
> /* Generate a hash value for an expression. This can be used iteratively
> by passing a previous result as the HSTATE argument. */
> virtual void hash_operand (const_tree, inchash::hash &, unsigned flags);
> + void hash_operand (const_tree, inchash::hash &, unsigned flags,
> + operand_access_type access);
> };
>
> } // ipa_icf_gimple namespace
> diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
> index 8cae076b3ce..83f9786b4b2 100644
> --- a/gcc/ipa-icf.c
> +++ b/gcc/ipa-icf.c
> @@ -1419,33 +1419,32 @@ sem_function::hash_stmt (gimple *stmt, inchash::hash
> &hstate)
> {
> case GIMPLE_SWITCH:
> m_checker->hash_operand (gimple_switch_index (as_a <gswitch *> (stmt)),
> - hstate, 0);
> + hstate, 0, func_checker::OP_NORMAL);
> break;
> case GIMPLE_ASSIGN:
> hstate.add_int (gimple_assign_rhs_code (stmt));
> - if (commutative_tree_code (gimple_assign_rhs_code (stmt))
> - || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
> - {
> - m_checker->hash_operand (gimple_assign_rhs1 (stmt), hstate, 0);
> - m_checker->hash_operand (gimple_assign_rhs2 (stmt), hstate, 0);
> - if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
> - m_checker->hash_operand (gimple_assign_rhs3 (stmt), hstate, 0);
> - m_checker->hash_operand (gimple_assign_lhs (stmt), hstate, 0);
> - }
> /* fall through */
> case GIMPLE_CALL:
> case GIMPLE_ASM:
> case GIMPLE_COND:
> case GIMPLE_GOTO:
> case GIMPLE_RETURN:
> - /* All these statements are equivalent if their operands are. */
> - for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
> - m_checker->hash_operand (gimple_op (stmt, i), hstate, 0);
> - /* Consider nocf_check attribute in hash as it affects code
> - generation. */
> - if (code == GIMPLE_CALL
> - && flag_cf_protection & CF_BRANCH)
> - hstate.add_flag (gimple_call_nocf_check_p (as_a <gcall *> (stmt)));
> + {
> + func_checker::operand_access_type_map map (5);
> + func_checker::classify_operands (stmt, &map);
> +
> + /* All these statements are equivalent if their operands are. */
> + for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
> + m_checker->hash_operand (gimple_op (stmt, i), hstate, 0,
> + func_checker::get_operand_access_type
> + (&map, gimple_op (stmt, i)));
> + /* Consider nocf_check attribute in hash as it affects code
> + generation. */
> + if (code == GIMPLE_CALL
> + && flag_cf_protection & CF_BRANCH)
> + hstate.add_flag (gimple_call_nocf_check_p (as_a <gcall *> (stmt)));
> + }
> + break;
> default:
> break;
> }
> @@ -1534,7 +1533,8 @@ sem_function::compare_phi_node (basic_block bb1,
> basic_block bb2)
> tree phi_result1 = gimple_phi_result (phi1);
> tree phi_result2 = gimple_phi_result (phi2);
>
> - if (!m_checker->compare_operand (phi_result1, phi_result2))
> + if (!m_checker->compare_operand (phi_result1, phi_result2,
> + func_checker::OP_NORMAL))
> return return_false_with_msg ("PHI results are different");
>
> size1 = gimple_phi_num_args (phi1);
> @@ -1548,7 +1548,7 @@ sem_function::compare_phi_node (basic_block bb1,
> basic_block bb2)
> t1 = gimple_phi_arg (phi1, i)->def;
> t2 = gimple_phi_arg (phi2, i)->def;
>
> - if (!m_checker->compare_operand (t1, t2))
> + if (!m_checker->compare_operand (t1, t2, func_checker::OP_NORMAL))
> return return_false ();
>
> e1 = gimple_phi_arg_edge (phi1, i);
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imend
