| Message ID | 20150522123341.GD91616@kam.mff.cuni.cz |
|---|---|
| State | New |
| Headers | show |
On Fri, 22 May 2015, Jan Hubicka wrote: > Hi, > I am working on patch that makes operand_equal_p replace logic from > ipa-icf-gimple's compare_op via a valueizer hook. Currently the patch however > cuts number of merges on firefox to half (apparently becuase it gives up on > some tree codes too early) > The patch bellow merges code from ipa-icf-gimple.c that is missing in > fold-const and is needed. > > Bootstrapped/regtested x86_64-linux, OK? No, I don't like this. > Honza > > * fold-const.c (operand_equal_p): Handle OBJ_TYPE_REF, CONSTRUCTOR > and be more tolerant about FIELD_DECL. > * tree.c (add_expr): Handle FIELD_DECL. > (prototype_p, virtual_method_call_p, obj_type_ref_class): Constify. > * tree.h (prototype_p, virtual_method_call_p, obj_type_ref_class): > Constify. > Index: fold-const.c > =================================================================== > --- fold-const.c (revision 223500) > @@ -3037,6 +3058,40 @@ operand_equal_p (const_tree arg0, const_ > case DOT_PROD_EXPR: > return OP_SAME (0) && OP_SAME (1) && OP_SAME (2); > > + /* OBJ_TYPE_REF really is just a transparent wrapper around expression, > + but it holds additional type information for devirtualization that > + needs to be matched. We may want to intoruce OEP flag if we want > + to compare the actual value only, or if we also care about effects > + of potentially merging the code. This flag can bypass this check > + as well as the alias set matching in MEM_REF. */ > + case OBJ_TYPE_REF: > + { > + if (!operand_equal_p (OBJ_TYPE_REF_EXPR (arg0), > + OBJ_TYPE_REF_EXPR (arg1), flags)) > + return false; > + if (flag_devirtualize && virtual_method_call_p (arg0)) > + { > + if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (arg0)) > + != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (arg1))) > + return false; > + if (!types_same_for_odr (obj_type_ref_class (arg0), > + obj_type_ref_class (arg1))) > + return false; devirt machinery in operand_equal_p? please not. not more places! > + /* OBJ_TYPE_REF_OBJECT is used to track the instance of > + object THIS pointer points to. Checking that both > + addresses equal is safe approximation of the fact > + that dynamic types are equal. > + Do not care about the other flags, because this expression > + does not attribute to actual value of OBJ_TYPE_REF */ > + if (!operand_equal_p (OBJ_TYPE_REF_OBJECT (arg0), > + OBJ_TYPE_REF_OBJECT (arg1), > + OEP_ADDRESS_OF)) > + return false; > + } > + > + return true; > + } > + > default: > return 0; > } > @@ -3097,6 +3152,21 @@ operand_equal_p (const_tree arg0, const_ > } > > case tcc_declaration: > + /* At LTO time the FIELD_DECL may exist in multiple copies. > + We only care about offsets and bit offsets for operands. */ Err? Even at LTO time FIELD_DECLs should only appear once. So - testcase? IMHO most of this boils down to ICF being too strict about aliasing because it inlines merged bodies instead of original ones. > + if (TREE_CODE (arg0) == FIELD_DECL) > + { > + tree offset1 = DECL_FIELD_OFFSET (arg0); > + tree offset2 = DECL_FIELD_OFFSET (arg1); > + > + tree bit_offset1 = DECL_FIELD_BIT_OFFSET (arg0); > + tree bit_offset2 = DECL_FIELD_BIT_OFFSET (arg1); > + > + flags &= ~(OEP_CONSTANT_ADDRESS_OF|OEP_ADDRESS_OF); > + > + return operand_equal_p (offset1, offset2, flags) > + && operand_equal_p (bit_offset1, bit_offset2, flags); > + } > /* Consider __builtin_sqrt equal to sqrt. */ > return (TREE_CODE (arg0) == FUNCTION_DECL > && DECL_BUILT_IN (arg0) && DECL_BUILT_IN (arg1) > @@ -3104,12 +3174,50 @@ operand_equal_p (const_tree arg0, const_ > && DECL_FUNCTION_CODE (arg0) == DECL_FUNCTION_CODE (arg1)); > > default: case tcc_exceptional: > + /* In GIMPLE empty constructors are allowed in initializers of > + vector types. */ Why this comment about GIMPLE? This is about comparing GENERIC trees which of course can have CONSTRUCTORs of various sorts. > + if (TREE_CODE (arg0) == CONSTRUCTOR) > + { > + unsigned length1 = vec_safe_length (CONSTRUCTOR_ELTS (arg0)); > + unsigned length2 = vec_safe_length (CONSTRUCTOR_ELTS (arg1)); > + > + if (length1 != length2) > + return false; > + > + flags &= ~(OEP_CONSTANT_ADDRESS_OF|OEP_ADDRESS_OF); > + > + for (unsigned i = 0; i < length1; i++) > + if (!operand_equal_p (CONSTRUCTOR_ELT (arg0, i)->value, > + CONSTRUCTOR_ELT (arg1, i)->value, flags)) You need to compare ->index as well here. I'm not sure constructor values are sorted always so you might get very many false negatives. > + return false; > + > + return true; > + } > return 0; > } > > #undef OP_SAME > #undef OP_SAME_WITH_NULL > } > Index: tree.c > =================================================================== > --- tree.c (revision 223500) > +++ tree.c (working copy) > @@ -7647,6 +7647,12 @@ add_expr (const_tree t, inchash::hash &h > } > return; > } > + case FIELD_DECL: > + /* At LTO time the FIELD_DECL may exist in multiple copies. > + We only care about offsets and bit offsets for operands. */ So explain that this is the reason we don't want to hash by DECL_UID. I still think this is bogus. > + inchash::add_expr (DECL_FIELD_OFFSET (t), hstate); > + inchash::add_expr (DECL_FIELD_BIT_OFFSET (t), hstate); > + return; > case FUNCTION_DECL: > /* When referring to a built-in FUNCTION_DECL, use the __builtin__ form. > Otherwise nodes that compare equal according to operand_equal_p might > @@ -11579,7 +11585,7 @@ stdarg_p (const_tree fntype) > /* Return true if TYPE has a prototype. */ > > bool > -prototype_p (tree fntype) > +prototype_p (const_tree fntype) This and the following look like independent (and obvious) changes. > { > tree t; > > @@ -12005,7 +12011,7 @@ lhd_gcc_personality (void) > can't apply.) */ > > bool > -virtual_method_call_p (tree target) > +virtual_method_call_p (const_tree target) > { > if (TREE_CODE (target) != OBJ_TYPE_REF) > return false; > @@ -12026,7 +12032,7 @@ virtual_method_call_p (tree target) > /* REF is OBJ_TYPE_REF, return the class the ref corresponds to. */ > > tree > -obj_type_ref_class (tree ref) > +obj_type_ref_class (const_tree ref) > { > gcc_checking_assert (TREE_CODE (ref) == OBJ_TYPE_REF); > ref = TREE_TYPE (ref); > Index: tree.h > =================================================================== > --- tree.h (revision 223500) > +++ tree.h (working copy) > @@ -4375,7 +4375,7 @@ extern int operand_equal_for_phi_arg_p ( > extern tree create_artificial_label (location_t); > extern const char *get_name (tree); > extern bool stdarg_p (const_tree); > -extern bool prototype_p (tree); > +extern bool prototype_p (const_tree); > extern bool is_typedef_decl (tree x); > extern bool typedef_variant_p (tree); > extern bool auto_var_in_fn_p (const_tree, const_tree); > @@ -4544,8 +4544,8 @@ extern location_t *block_nonartificial_l > extern location_t tree_nonartificial_location (tree); > extern tree block_ultimate_origin (const_tree); > extern tree get_binfo_at_offset (tree, HOST_WIDE_INT, tree); > -extern bool virtual_method_call_p (tree); > -extern tree obj_type_ref_class (tree ref); > +extern bool virtual_method_call_p (const_tree); > +extern tree obj_type_ref_class (const_tree ref); > extern bool types_same_for_odr (const_tree type1, const_tree type2, > bool strict=false); > extern bool contains_bitfld_component_ref_p (const_tree); > >
> > + case OBJ_TYPE_REF: > > + { > > + if (!operand_equal_p (OBJ_TYPE_REF_EXPR (arg0), > > + OBJ_TYPE_REF_EXPR (arg1), flags)) > > + return false; > > + if (flag_devirtualize && virtual_method_call_p (arg0)) > > + { > > + if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (arg0)) > > + != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (arg1))) > > + return false; > > + if (!types_same_for_odr (obj_type_ref_class (arg0), > > + obj_type_ref_class (arg1))) > > + return false; > > devirt machinery in operand_equal_p? please not. not more places! OBJ_TYPE_REF explicitly says what is the type of class whose virtual method is called. It is GIMPLE operand expression like other, so I think we need to handle it. Actually I think I can just drop the flag_devirtualize check because with !flag_devirtualize we should simply avoid having OBJ_TYPE_REF around. That would make it looking less devirt specific. We can also test types for equivalence of main variant, but that would just introduce false positives when LTO did not merged two identical ODR types. It would be correct though. > > > + /* OBJ_TYPE_REF_OBJECT is used to track the instance of > > + object THIS pointer points to. Checking that both > > + addresses equal is safe approximation of the fact > > + that dynamic types are equal. > > + Do not care about the other flags, because this expression > > + does not attribute to actual value of OBJ_TYPE_REF */ > > + if (!operand_equal_p (OBJ_TYPE_REF_OBJECT (arg0), > > + OBJ_TYPE_REF_OBJECT (arg1), > > + OEP_ADDRESS_OF)) > > + return false; > > + } > > + > > + return true; > > + } > > + > > default: > > return 0; > > } > > @@ -3097,6 +3152,21 @@ operand_equal_p (const_tree arg0, const_ > > } > > > > case tcc_declaration: > > + /* At LTO time the FIELD_DECL may exist in multiple copies. > > + We only care about offsets and bit offsets for operands. */ > > Err? Even at LTO time FIELD_DECLs should only appear once. > So - testcase? FIELD_DECL has TREE_TYPE and TREE_TYPE may not get merged by LTO. So if the two expressions originate from two different units, we may have two semantically equivalent FIELD_DECLs (of compatible types and same offsets) that occupy different memory locations because their merging was prevented by something upstream (like complete wrt incmplete pointer in the type) > > + /* In GIMPLE empty constructors are allowed in initializers of > > + vector types. */ > > Why this comment about GIMPLE? This is about comparing GENERIC > trees which of course can have CONSTRUCTORs of various sorts. > > > + if (TREE_CODE (arg0) == CONSTRUCTOR) > > + { > > + unsigned length1 = vec_safe_length (CONSTRUCTOR_ELTS (arg0)); > > + unsigned length2 = vec_safe_length (CONSTRUCTOR_ELTS (arg1)); > > + > > + if (length1 != length2) > > + return false; > > + > > + flags &= ~(OEP_CONSTANT_ADDRESS_OF|OEP_ADDRESS_OF); > > + > > + for (unsigned i = 0; i < length1; i++) > > + if (!operand_equal_p (CONSTRUCTOR_ELT (arg0, i)->value, > > + CONSTRUCTOR_ELT (arg1, i)->value, flags)) > > You need to compare ->index as well here. I'm not sure constructor > values are sorted always so you might get very many false negatives. many false negatives is better than all false negatices :) You are right, either I should punt on non-empty constructors or compare the indexes, will do the second. > > + case FIELD_DECL: > > + /* At LTO time the FIELD_DECL may exist in multiple copies. > > + We only care about offsets and bit offsets for operands. */ > > So explain that this is the reason we don't want to hash by > DECL_UID. I still think this is bogus. Will do if we agree on having this. I know you would like ipa-icf to keep original bodies and use them for inlining declaring alias sets to be function local. This is wrong plan. Consder: void t(int *ptr) { *ptr=1; } int a(int *ptr1, int *ptr2) { int a = *ptr1; t(ptr2) return a+*ptr1; } long b(long *ptr1, int *ptr2) { int a = *ptr1; t(ptr2) return a+*ptr1; } here aliasing leads to the two options to be optimizer differently: a: .LFB1: .cfi_startproc movl 4(%esp), %edx movl 8(%esp), %ecx movl (%edx), %eax movl $1, (%ecx) addl (%edx), %eax ret .cfi_endproc b: .LFB2: .cfi_startproc movl 4(%esp), %eax movl 8(%esp), %edx movl (%eax), %eax movl $1, (%edx) addl %eax, %eax ret .cfi_endproc however with -fno-early-inlining the functions look identical (modulo alias sets) at ipa-icf time. If we merged a/b, we could get wrong code for a even though no inlining of a or b happens. So either we match the alias sets or we need to verify that the alias sets permit precisely the same set of optimizations with taking possible inlining into account. I also do not believe that TBAA should be function local. I believe it is useful to propagate stuff interprocedurally, like ipa-prop could be able to propagate this: long *ptr1; int *ptr2; t(int *ptr) { return *ptr; } wrap(int *ptr) { *ptr1=1; } call() { return wrap (*ptr2); } and we could have ipa-reference style pass that collect alias sets read/written by a function and uses it during local optimization to figure out if there is a true dependence between function call and memory store. Honza
> > > + case OBJ_TYPE_REF: > > > + { > > > + if (!operand_equal_p (OBJ_TYPE_REF_EXPR (arg0), > > > + OBJ_TYPE_REF_EXPR (arg1), flags)) > > > + return false; > > > + if (flag_devirtualize && virtual_method_call_p (arg0)) > > > + { > > > + if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (arg0)) > > > + != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (arg1))) > > > + return false; > > > + if (!types_same_for_odr (obj_type_ref_class (arg0), > > > + obj_type_ref_class (arg1))) > > > + return false; > > > > devirt machinery in operand_equal_p? please not. not more places! > > OBJ_TYPE_REF explicitly says what is the type of class whose virtual method is > called. It is GIMPLE operand expression like other, so I think we need to handle > it. > > Actually I think I can just drop the flag_devirtualize check because with > !flag_devirtualize we should simply avoid having OBJ_TYPE_REF around. That > would make it looking less devirt specific. We can also test types for > equivalence of main variant, but that would just introduce false positives when > LTO did not merged two identical ODR types. It would be correct though. After more tought, I indeed like the idea of having gimple specific matching code better (I managed to talk myself into the idea of unifying the code rather than duplicating everything, but handling generic is a pain) If we go this path, I think I can just withdraw OBJ_TYPE_REF change here. operand_equal_p conservatively consders every pair of two OBJ_TYPE_REFs different that is safe. Concerning the rest of the patch, I leave it up to your decision if we want to handle these in operand_equal_p or only at gimple level. thanks, Honza > > > > > + /* OBJ_TYPE_REF_OBJECT is used to track the instance of > > > + object THIS pointer points to. Checking that both > > > + addresses equal is safe approximation of the fact > > > + that dynamic types are equal. > > > + Do not care about the other flags, because this expression > > > + does not attribute to actual value of OBJ_TYPE_REF */ > > > + if (!operand_equal_p (OBJ_TYPE_REF_OBJECT (arg0), > > > + OBJ_TYPE_REF_OBJECT (arg1), > > > + OEP_ADDRESS_OF)) > > > + return false; > > > + } > > > + > > > + return true; > > > + } > > > + > > > default: > > > return 0; > > > } > > > @@ -3097,6 +3152,21 @@ operand_equal_p (const_tree arg0, const_ > > > } > > > > > > case tcc_declaration: > > > + /* At LTO time the FIELD_DECL may exist in multiple copies. > > > + We only care about offsets and bit offsets for operands. */ > > > > Err? Even at LTO time FIELD_DECLs should only appear once. > > So - testcase? > > FIELD_DECL has TREE_TYPE and TREE_TYPE may not get merged by LTO. So if the > two expressions originate from two different units, we may have two > semantically equivalent FIELD_DECLs (of compatible types and same offsets) that > occupy different memory locations because their merging was prevented by > something upstream (like complete wrt incmplete pointer in the type) > > > + /* In GIMPLE empty constructors are allowed in initializers of > > > + vector types. */ > > > > Why this comment about GIMPLE? This is about comparing GENERIC > > trees which of course can have CONSTRUCTORs of various sorts. > > > > > + if (TREE_CODE (arg0) == CONSTRUCTOR) > > > + { > > > + unsigned length1 = vec_safe_length (CONSTRUCTOR_ELTS (arg0)); > > > + unsigned length2 = vec_safe_length (CONSTRUCTOR_ELTS (arg1)); > > > + > > > + if (length1 != length2) > > > + return false; > > > + > > > + flags &= ~(OEP_CONSTANT_ADDRESS_OF|OEP_ADDRESS_OF); > > > + > > > + for (unsigned i = 0; i < length1; i++) > > > + if (!operand_equal_p (CONSTRUCTOR_ELT (arg0, i)->value, > > > + CONSTRUCTOR_ELT (arg1, i)->value, flags)) > > > > You need to compare ->index as well here. I'm not sure constructor > > values are sorted always so you might get very many false negatives. > > many false negatives is better than all false negatices :) > > You are right, either I should punt on non-empty constructors or compare > the indexes, will do the second. > > > > + case FIELD_DECL: > > > + /* At LTO time the FIELD_DECL may exist in multiple copies. > > > + We only care about offsets and bit offsets for operands. */ > > > > So explain that this is the reason we don't want to hash by > > DECL_UID. I still think this is bogus. > > Will do if we agree on having this. > > I know you would like ipa-icf to keep original bodies and use them for inlining > declaring alias sets to be function local. This is wrong plan. Consder: > > void t(int *ptr) > { > *ptr=1; > } > > int a(int *ptr1, int *ptr2) > { > int a = *ptr1; > t(ptr2) > return a+*ptr1; > } > > long b(long *ptr1, int *ptr2) > { > int a = *ptr1; > t(ptr2) > return a+*ptr1; > } > > here aliasing leads to the two options to be optimizer differently: > a: > .LFB1: > .cfi_startproc > movl 4(%esp), %edx > movl 8(%esp), %ecx > movl (%edx), %eax > movl $1, (%ecx) > addl (%edx), %eax > ret > .cfi_endproc > b: > .LFB2: > .cfi_startproc > movl 4(%esp), %eax > movl 8(%esp), %edx > movl (%eax), %eax > movl $1, (%edx) > addl %eax, %eax > ret > .cfi_endproc > > however with -fno-early-inlining the functions look identical (modulo alias > sets) at ipa-icf time. If we merged a/b, we could get wrong code for a > even though no inlining of a or b happens. > > So either we match the alias sets or we need to verify that the alias sets > permit precisely the same set of optimizations with taking possible inlining > into account. > > I also do not believe that TBAA should be function local. I believe it is > useful to propagate stuff interprocedurally, like ipa-prop could be able to > propagate this: > > long *ptr1; > int *ptr2; > t(int *ptr) > { > return *ptr; > } > wrap(int *ptr) > { > *ptr1=1; > } > call() > { > return wrap (*ptr2); > } > > and we could have ipa-reference style pass that collect alias sets read/written by a function > and uses it during local optimization to figure out if there is a true dependence > between function call and memory store. > > Honza
On Fri, 22 May 2015, Jan Hubicka wrote: > > > + case OBJ_TYPE_REF: > > > + { > > > + if (!operand_equal_p (OBJ_TYPE_REF_EXPR (arg0), > > > + OBJ_TYPE_REF_EXPR (arg1), flags)) > > > + return false; > > > + if (flag_devirtualize && virtual_method_call_p (arg0)) > > > + { > > > + if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (arg0)) > > > + != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (arg1))) > > > + return false; > > > + if (!types_same_for_odr (obj_type_ref_class (arg0), > > > + obj_type_ref_class (arg1))) > > > + return false; > > > > devirt machinery in operand_equal_p? please not. not more places! > > OBJ_TYPE_REF explicitly says what is the type of class whose virtual > method is called. It is GIMPLE operand expression like other, so I think > we need to handle it. > > Actually I think I can just drop the flag_devirtualize check because with > !flag_devirtualize we should simply avoid having OBJ_TYPE_REF around. That > would make it looking less devirt specific. We can also test types for > equivalence of main variant, but that would just introduce false positives when > LTO did not merged two identical ODR types. It would be correct though. Ok, please split it out without the devritualize bits. > > > > > + /* OBJ_TYPE_REF_OBJECT is used to track the instance of > > > + object THIS pointer points to. Checking that both > > > + addresses equal is safe approximation of the fact > > > + that dynamic types are equal. > > > + Do not care about the other flags, because this expression > > > + does not attribute to actual value of OBJ_TYPE_REF */ > > > + if (!operand_equal_p (OBJ_TYPE_REF_OBJECT (arg0), > > > + OBJ_TYPE_REF_OBJECT (arg1), > > > + OEP_ADDRESS_OF)) > > > + return false; > > > + } > > > + > > > + return true; > > > + } > > > + > > > default: > > > return 0; > > > } > > > @@ -3097,6 +3152,21 @@ operand_equal_p (const_tree arg0, const_ > > > } > > > > > > case tcc_declaration: > > > + /* At LTO time the FIELD_DECL may exist in multiple copies. > > > + We only care about offsets and bit offsets for operands. */ > > > > Err? Even at LTO time FIELD_DECLs should only appear once. > > So - testcase? > > FIELD_DECL has TREE_TYPE and TREE_TYPE may not get merged by LTO. So if > the two expressions originate from two different units, we may have two > semantically equivalent FIELD_DECLs (of compatible types and same > offsets) that occupy different memory locations because their merging > was prevented by something upstream (like complete wrt incmplete pointer > in the type) Still, operand_equal_p isn't about LTO, it's about GENERIC as created by FEs... > > > + /* In GIMPLE empty constructors are allowed in initializers of > > > + vector types. */ > > > > Why this comment about GIMPLE? This is about comparing GENERIC > > trees which of course can have CONSTRUCTORs of various sorts. > > > > > + if (TREE_CODE (arg0) == CONSTRUCTOR) > > > + { > > > + unsigned length1 = vec_safe_length (CONSTRUCTOR_ELTS (arg0)); > > > + unsigned length2 = vec_safe_length (CONSTRUCTOR_ELTS (arg1)); > > > + > > > + if (length1 != length2) > > > + return false; > > > + > > > + flags &= ~(OEP_CONSTANT_ADDRESS_OF|OEP_ADDRESS_OF); > > > + > > > + for (unsigned i = 0; i < length1; i++) > > > + if (!operand_equal_p (CONSTRUCTOR_ELT (arg0, i)->value, > > > + CONSTRUCTOR_ELT (arg1, i)->value, flags)) > > > > You need to compare ->index as well here. I'm not sure constructor > > values are sorted always so you might get very many false negatives. > > many false negatives is better than all false negatices :) > > You are right, either I should punt on non-empty constructors or compare > the indexes, will do the second. Thanks - please split it out to a separate patch. > > > + case FIELD_DECL: > > > + /* At LTO time the FIELD_DECL may exist in multiple copies. > > > + We only care about offsets and bit offsets for operands. */ > > > > So explain that this is the reason we don't want to hash by > > DECL_UID. I still think this is bogus. > > Will do if we agree on having this. > > I know you would like ipa-icf to keep original bodies and use them for > inlining declaring alias sets to be function local. This is wrong plan. > Consder: > > void t(int *ptr) > { > *ptr=1; > } > > int a(int *ptr1, int *ptr2) > { > int a = *ptr1; > t(ptr2) > return a+*ptr1; > } > > long b(long *ptr1, int *ptr2) > { > int a = *ptr1; > t(ptr2) > return a+*ptr1; > } > > here aliasing leads to the two options to be optimizer differently: > a: > .LFB1: > .cfi_startproc > movl 4(%esp), %edx > movl 8(%esp), %ecx > movl (%edx), %eax > movl $1, (%ecx) > addl (%edx), %eax > ret > .cfi_endproc > b: > .LFB2: > .cfi_startproc > movl 4(%esp), %eax > movl 8(%esp), %edx > movl (%eax), %eax > movl $1, (%edx) > addl %eax, %eax > ret > .cfi_endproc > > however with -fno-early-inlining the functions look identical (modulo alias > sets) at ipa-icf time. If we merged a/b, we could get wrong code for a > even though no inlining of a or b happens. First of all the return types don't agree so the testcase is bogus. > So either we match the alias sets or we need to verify that the alias sets > permit precisely the same set of optimizations with taking possible inlining > into account. Hmm, but then what makes ICF of a and b _with_ early inlining fail with -fno-tree-fre1? The casts from *ptr1 to int in the 'long' case. So I think I need to see a real testcase and then I'll show you even with no inlining after ICF you get wrong-code thus it is a bug in ICF ;) > I also do not believe that TBAA should be function local. I believe it is > useful to propagate stuff interprocedurally, like ipa-prop could be able to > propagate this: > > long *ptr1; > int *ptr2; > t(int *ptr) > { > return *ptr; > } > wrap(int *ptr) > { > *ptr1=1; > } > call() > { > return wrap (*ptr2); > } > > and we could have ipa-reference style pass that collect alias sets > read/written by a function and uses it during local optimization to > figure out if there is a true dependence between function call and > memory store. Sure, but after ICF there is no IPA propagation... Richard.
> > Will do if we agree on having this. > > > > I know you would like ipa-icf to keep original bodies and use them for > > inlining declaring alias sets to be function local. This is wrong plan. > > Consder: > > > > void t(int *ptr) > > { > > *ptr=1; > > } > > > > int a(int *ptr1, int *ptr2) > > { > > int a = *ptr1; > > t(ptr2) > > return a+*ptr1; > > } > > > > long b(long *ptr1, int *ptr2) > > { > > int a = *ptr1; > > t(ptr2) > > return a+*ptr1; > > } > > > > here aliasing leads to the two options to be optimizer differently: > > a: > > .LFB1: > > .cfi_startproc > > movl 4(%esp), %edx > > movl 8(%esp), %ecx > > movl (%edx), %eax > > movl $1, (%ecx) > > addl (%edx), %eax > > ret > > .cfi_endproc > > b: > > .LFB2: > > .cfi_startproc > > movl 4(%esp), %eax > > movl 8(%esp), %edx > > movl (%eax), %eax > > movl $1, (%edx) > > addl %eax, %eax > > ret > > .cfi_endproc > > > > however with -fno-early-inlining the functions look identical (modulo alias > > sets) at ipa-icf time. If we merged a/b, we could get wrong code for a > > even though no inlining of a or b happens. > > First of all the return types don't agree so the testcase is bogus. With -m32 they are types_compatible_p because they are of same size. > > > So either we match the alias sets or we need to verify that the alias sets > > permit precisely the same set of optimizations with taking possible inlining > > into account. > > Hmm, but then what makes ICF of a and b _with_ early inlining fail with > -fno-tree-fre1? The casts from *ptr1 to int in the 'long' case. Dereferencing *ptr1 that has different alias set in each function. > > So I think I need to see a real testcase and then I'll show you > even with no inlining after ICF you get wrong-code thus it is a bug > in ICF ;) I added the inline only to make it clear that the loads won't be optimized at early optimization time. long a(int *ptr1, int *ptr2) { int a = *ptr1; *ptr2=1; return a+*ptr1; } long b(long *ptr1, int *ptr2) { int a = *ptr1; *ptr2=1; return a+*ptr1; } with -fno-tree-fre may be more real a (int * ptr1, int * ptr2) { int a; int D.1380; long int D.1379; int _4; long int _5; <bb 2>: a_2 = *ptr1_1(D); *ptr2_3(D) = 1; _4 = *ptr1_1(D); _5 = _4 + a_2; <L0>: return _5; } ;; Function b (b, funcdef_no=1, decl_uid=1375, cgraph_uid=1) b (long int * ptr1, int * ptr2) { int a; long int D.1383; long int D.1382; long int _4; long int _5; <bb 2>: a_2 = *ptr1_1(D); *ptr2_3(D) = 1; _4 = *ptr1_1(D); _5 = _4 + a_2; <L0>: return _5; } > > > I also do not believe that TBAA should be function local. I believe it is > > useful to propagate stuff interprocedurally, like ipa-prop could be able to > > propagate this: > > > > long *ptr1; > > int *ptr2; > > t(int *ptr) > > { > > return *ptr; > > } > > wrap(int *ptr) > > { > > *ptr1=1; > > } > > call() > > { > > return wrap (*ptr2); > > } > > > > and we could have ipa-reference style pass that collect alias sets > > read/written by a function and uses it during local optimization to > > figure out if there is a true dependence between function call and > > memory store. > > Sure, but after ICF there is no IPA propagation... Doesn't matter if you propagate before or after ICF. If you do before, ICF would need to match/merge the alias set in optimization summary to be sure that the functions are same. Honza > > Richard. > > -- > Richard Biener <rguenther@suse.de> > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg)
On Tue, 26 May 2015, Jan Hubicka wrote: > > > Will do if we agree on having this. > > > > > > I know you would like ipa-icf to keep original bodies and use them for > > > inlining declaring alias sets to be function local. This is wrong plan. > > > Consder: > > > > > > void t(int *ptr) > > > { > > > *ptr=1; > > > } > > > > > > int a(int *ptr1, int *ptr2) > > > { > > > int a = *ptr1; > > > t(ptr2) > > > return a+*ptr1; > > > } > > > > > > long b(long *ptr1, int *ptr2) > > > { > > > int a = *ptr1; > > > t(ptr2) > > > return a+*ptr1; > > > } > > > > > > here aliasing leads to the two options to be optimizer differently: > > > a: > > > .LFB1: > > > .cfi_startproc > > > movl 4(%esp), %edx > > > movl 8(%esp), %ecx > > > movl (%edx), %eax > > > movl $1, (%ecx) > > > addl (%edx), %eax > > > ret > > > .cfi_endproc > > > b: > > > .LFB2: > > > .cfi_startproc > > > movl 4(%esp), %eax > > > movl 8(%esp), %edx > > > movl (%eax), %eax > > > movl $1, (%edx) > > > addl %eax, %eax > > > ret > > > .cfi_endproc > > > > > > however with -fno-early-inlining the functions look identical (modulo alias > > > sets) at ipa-icf time. If we merged a/b, we could get wrong code for a > > > even though no inlining of a or b happens. > > > > First of all the return types don't agree so the testcase is bogus. > > With -m32 they are types_compatible_p because they are of same size. > > > > > So either we match the alias sets or we need to verify that the alias sets > > > permit precisely the same set of optimizations with taking possible inlining > > > into account. > > > > Hmm, but then what makes ICF of a and b _with_ early inlining fail with > > -fno-tree-fre1? The casts from *ptr1 to int in the 'long' case. > > Dereferencing *ptr1 that has different alias set in each function. > > > > So I think I need to see a real testcase and then I'll show you > > even with no inlining after ICF you get wrong-code thus it is a bug > > in ICF ;) > > I added the inline only to make it clear that the loads won't be optimized > at early optimization time. > long a(int *ptr1, int *ptr2) > { > int a = *ptr1; > *ptr2=1; > return a+*ptr1; > } > > long b(long *ptr1, int *ptr2) > { > int a = *ptr1; > *ptr2=1; > return a+*ptr1; > } > > with -fno-tree-fre may be more real > > a (int * ptr1, int * ptr2) > { > int a; > int D.1380; > long int D.1379; > int _4; > long int _5; > > <bb 2>: > a_2 = *ptr1_1(D); > *ptr2_3(D) = 1; > _4 = *ptr1_1(D); > _5 = _4 + a_2; > > <L0>: > return _5; > > } > > ;; Function b (b, funcdef_no=1, decl_uid=1375, cgraph_uid=1) > > b (long int * ptr1, int * ptr2) > { > int a; > long int D.1383; > long int D.1382; > long int _4; > long int _5; > > <bb 2>: > a_2 = *ptr1_1(D); > *ptr2_3(D) = 1; > _4 = *ptr1_1(D); > _5 = _4 + a_2; > > <L0>: > return _5; > > } Yes, so this shows using original bodies for inlining isn't the issue. The issue is that we can't really ignore TBAA (completely?) when merging function bodies, independent of any issues that pop up when inlining merged bodies. We should have the above as testcase in the testsuite (with both source orders of a and b to make sure ICF will eventually pick both). Now the question is whether we can in some way still merge the above two functions and retain (some) TBAA, like by making sure to adjust all MEM_REFs to use union { type1; type2; } for the TBAA type... (eh). No longer globbing all pointer types will even make std::vector<ptr> no longer mergeable... Richard. > > > > > I also do not believe that TBAA should be function local. I believe it is > > > useful to propagate stuff interprocedurally, like ipa-prop could be able to > > > propagate this: > > > > > > long *ptr1; > > > int *ptr2; > > > t(int *ptr) > > > { > > > return *ptr; > > > } > > > wrap(int *ptr) > > > { > > > *ptr1=1; > > > } > > > call() > > > { > > > return wrap (*ptr2); > > > } > > > > > > and we could have ipa-reference style pass that collect alias sets > > > read/written by a function and uses it during local optimization to > > > figure out if there is a true dependence between function call and > > > memory store. > > > > Sure, but after ICF there is no IPA propagation... > Doesn't matter if you propagate before or after ICF. If you do before, ICF > would need to match/merge the alias set in optimization summary to be sure that > the functions are same. > > Honza > > > > Richard. > > > > -- > > Richard Biener <rguenther@suse.de> > > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg) > >
> Yes, so this shows using original bodies for inlining isn't the issue. > The issue is that we can't really ignore TBAA (completely?) when > merging function bodies, independent of any issues that pop up > when inlining merged bodies. We should have the above as testcase Yes. > in the testsuite (with both source orders of a and b to make sure > ICF will eventually pick both). > > Now the question is whether we can in some way still merge the above > two functions and retain (some) TBAA, like by making sure to adjust > all MEM_REFs to use union { type1; type2; } for the TBAA type... (eh). I discussed the plan with Martin. I think the first step would be to make this work at -Os in the following way 1) we will do unification ignoring alias sets completely 2) once equivalneces are stablished we verify what can be unified (icf_merge is not always doable) and fix the unification decisions. 3) For every function that remains in the program we produce list of other functions that was merged into it. For each of it we make sure that alias sets are conservative dropping to 0 where neccesary. 4) we apply the redirectinos and throw away original bodies (or keep them for inlining to improve debug info) This scheme is useful to merge other metadata, too (such as jump functions). Now for -O2 it will be harder to decide whether punt merging or drop alias set. We can even introduce the artificial union (as alias sets only or as types themselves) and do just as much of TBAA punting as needed. But I would build from experience above. > > No longer globbing all pointer types will even make std::vector<ptr> > no longer mergeable... Yep, we do not merge most of tyime anyway, as eventually ipa-icf gets sily enough to compare the pointed-to type or it tries to match FIELD_DECL references exactly. I plan to slowly work on that once we settle down currently open topics ;) Honza > > Richard. > > > > > > > > I also do not believe that TBAA should be function local. I believe it is > > > > useful to propagate stuff interprocedurally, like ipa-prop could be able to > > > > propagate this: > > > > > > > > long *ptr1; > > > > int *ptr2; > > > > t(int *ptr) > > > > { > > > > return *ptr; > > > > } > > > > wrap(int *ptr) > > > > { > > > > *ptr1=1; > > > > } > > > > call() > > > > { > > > > return wrap (*ptr2); > > > > } > > > > > > > > and we could have ipa-reference style pass that collect alias sets > > > > read/written by a function and uses it during local optimization to > > > > figure out if there is a true dependence between function call and > > > > memory store. > > > > > > Sure, but after ICF there is no IPA propagation... > > Doesn't matter if you propagate before or after ICF. If you do before, ICF > > would need to match/merge the alias set in optimization summary to be sure that > > the functions are same. > > > > Honza > > > > > > Richard. > > > > > > -- > > > Richard Biener <rguenther@suse.de> > > > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg) > > > > > > -- > Richard Biener <rguenther@suse.de> > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg)
Index: tree.c =================================================================== --- tree.c (revision 223500) +++ tree.c (working copy) @@ -7647,6 +7647,12 @@ add_expr (const_tree t, inchash::hash &h } return; } + case FIELD_DECL: + /* At LTO time the FIELD_DECL may exist in multiple copies. + We only care about offsets and bit offsets for operands. */ + inchash::add_expr (DECL_FIELD_OFFSET (t), hstate); + inchash::add_expr (DECL_FIELD_BIT_OFFSET (t), hstate); + return; case FUNCTION_DECL: /* When referring to a built-in FUNCTION_DECL, use the __builtin__ form. Otherwise nodes that compare equal according to operand_equal_p might @@ -11579,7 +11585,7 @@ stdarg_p (const_tree fntype) /* Return true if TYPE has a prototype. */ bool -prototype_p (tree fntype) +prototype_p (const_tree fntype) { tree t; @@ -12005,7 +12011,7 @@ lhd_gcc_personality (void) can't apply.) */ bool -virtual_method_call_p (tree target) +virtual_method_call_p (const_tree target) { if (TREE_CODE (target) != OBJ_TYPE_REF) return false; @@ -12026,7 +12032,7 @@ virtual_method_call_p (tree target) /* REF is OBJ_TYPE_REF, return the class the ref corresponds to. */ tree -obj_type_ref_class (tree ref) +obj_type_ref_class (const_tree ref) { gcc_checking_assert (TREE_CODE (ref) == OBJ_TYPE_REF); ref = TREE_TYPE (ref); Index: tree.h =================================================================== --- tree.h (revision 223500) +++ tree.h (working copy) @@ -4375,7 +4375,7 @@ extern int operand_equal_for_phi_arg_p ( extern tree create_artificial_label (location_t); extern const char *get_name (tree); extern bool stdarg_p (const_tree); -extern bool prototype_p (tree); +extern bool prototype_p (const_tree); extern bool is_typedef_decl (tree x); extern bool typedef_variant_p (tree); extern bool auto_var_in_fn_p (const_tree, const_tree); @@ -4544,8 +4544,8 @@ extern location_t *block_nonartificial_l extern location_t tree_nonartificial_location (tree); extern tree block_ultimate_origin (const_tree); extern tree get_binfo_at_offset (tree, HOST_WIDE_INT, tree); -extern bool virtual_method_call_p (tree); -extern tree obj_type_ref_class (tree ref); +extern bool virtual_method_call_p (const_tree); +extern tree obj_type_ref_class (const_tree ref); extern bool types_same_for_odr (const_tree type1, const_tree type2, bool strict=false); extern bool contains_bitfld_component_ref_p (const_tree);
Hi, I am working on patch that makes operand_equal_p replace logic from ipa-icf-gimple's compare_op via a valueizer hook. Currently the patch however cuts number of merges on firefox to half (apparently becuase it gives up on some tree codes too early) The patch bellow merges code from ipa-icf-gimple.c that is missing in fold-const and is needed. Bootstrapped/regtested x86_64-linux, OK? Honza * fold-const.c (operand_equal_p): Handle OBJ_TYPE_REF, CONSTRUCTOR and be more tolerant about FIELD_DECL. * tree.c (add_expr): Handle FIELD_DECL. (prototype_p, virtual_method_call_p, obj_type_ref_class): Constify. * tree.h (prototype_p, virtual_method_call_p, obj_type_ref_class): Constify. Index: fold-const.c =================================================================== --- fold-const.c (revision 223500) @@ -3037,6 +3058,40 @@ operand_equal_p (const_tree arg0, const_ case DOT_PROD_EXPR: return OP_SAME (0) && OP_SAME (1) && OP_SAME (2); + /* OBJ_TYPE_REF really is just a transparent wrapper around expression, + but it holds additional type information for devirtualization that + needs to be matched. We may want to intoruce OEP flag if we want + to compare the actual value only, or if we also care about effects + of potentially merging the code. This flag can bypass this check + as well as the alias set matching in MEM_REF. */ + case OBJ_TYPE_REF: + { + if (!operand_equal_p (OBJ_TYPE_REF_EXPR (arg0), + OBJ_TYPE_REF_EXPR (arg1), flags)) + return false; + if (flag_devirtualize && virtual_method_call_p (arg0)) + { + if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (arg0)) + != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (arg1))) + return false; + if (!types_same_for_odr (obj_type_ref_class (arg0), + obj_type_ref_class (arg1))) + return false; + /* OBJ_TYPE_REF_OBJECT is used to track the instance of + object THIS pointer points to. Checking that both + addresses equal is safe approximation of the fact + that dynamic types are equal. + Do not care about the other flags, because this expression + does not attribute to actual value of OBJ_TYPE_REF */ + if (!operand_equal_p (OBJ_TYPE_REF_OBJECT (arg0), + OBJ_TYPE_REF_OBJECT (arg1), + OEP_ADDRESS_OF)) + return false; + } + + return true; + } + default: return 0; } @@ -3097,6 +3152,21 @@ operand_equal_p (const_tree arg0, const_ } case tcc_declaration: + /* At LTO time the FIELD_DECL may exist in multiple copies. + We only care about offsets and bit offsets for operands. */ + if (TREE_CODE (arg0) == FIELD_DECL) + { + tree offset1 = DECL_FIELD_OFFSET (arg0); + tree offset2 = DECL_FIELD_OFFSET (arg1); + + tree bit_offset1 = DECL_FIELD_BIT_OFFSET (arg0); + tree bit_offset2 = DECL_FIELD_BIT_OFFSET (arg1); + + flags &= ~(OEP_CONSTANT_ADDRESS_OF|OEP_ADDRESS_OF); + + return operand_equal_p (offset1, offset2, flags) + && operand_equal_p (bit_offset1, bit_offset2, flags); + } /* Consider __builtin_sqrt equal to sqrt. */ return (TREE_CODE (arg0) == FUNCTION_DECL && DECL_BUILT_IN (arg0) && DECL_BUILT_IN (arg1) @@ -3104,12 +3174,50 @@ operand_equal_p (const_tree arg0, const_ && DECL_FUNCTION_CODE (arg0) == DECL_FUNCTION_CODE (arg1)); default: + /* In GIMPLE empty constructors are allowed in initializers of + vector types. */ + if (TREE_CODE (arg0) == CONSTRUCTOR) + { + unsigned length1 = vec_safe_length (CONSTRUCTOR_ELTS (arg0)); + unsigned length2 = vec_safe_length (CONSTRUCTOR_ELTS (arg1)); + + if (length1 != length2) + return false; + + flags &= ~(OEP_CONSTANT_ADDRESS_OF|OEP_ADDRESS_OF); + + for (unsigned i = 0; i < length1; i++) + if (!operand_equal_p (CONSTRUCTOR_ELT (arg0, i)->value, + CONSTRUCTOR_ELT (arg1, i)->value, flags)) + return false; + + return true; + } return 0; } #undef OP_SAME #undef OP_SAME_WITH_NULL }