| Message ID | 20201108180707.GA19115@kam.mff.cuni.cz |
|---|---|
| State | New |
| Headers | show |
| Series | Improve handling of memory operands in ipa-icf 1/4 | expand |
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 <hubicka@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); >
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);
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? 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 <hubicka@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):