[PATCH 3/5] IPA ICF pass

[Martin Liška]

On 06/26/2014 08:46 PM, Jan Hubicka wrote:
> Jeff,
> thanks for review! I did some passes over the patch before it got to the ML, I am
> happy to have independent opinion.
>>> +@item -fipa-icf
>>> +@opindex fipa-icf
>>> +Perform Identical Code Folding for functions and read-only variables.
>>> +Behavior is similar to Gold Linker ICF optimization. Symbols proved
>>> +as semantically equivalent are redirected to corresponding symbol. The pass
>>> +sensitively decides for usage of alias, thunk or local redirection.
>>> +This flag is enabled by default at @option{-O2}.
>> So you've added this at -O2, what is the general compile-time
>> impact? Would it make more sense to instead have it be part of -O3,
>> particularly since ICF is rarely going to improve performance (sans
>> icache issues).
> I think code size optimization not sacrifying any (or too much of) performance are
> generally very welcome at -O2.  Compared to LLVM and Microsoft compilers we are
> on code bloat side at -O2.
>
> http://hubicka.blogspot.ca/2014/04/linktime-optimization-in-gcc-2-firefox.html
> has some numbers for -O2 GGC/LLVM.
>
> I believe this is result of tunning for relatively small benchamrks (SPECS) and
> I hope we could revisit -O2 for code size considerations for 4.10 somewhat.  If
> tuned well, ICF has no reason to be expnesive wrt compile time. So lets shoot
> for that.  The considerable donwside of enabling ICF IMO should be only
> disturbing effect on debug info.
>>> +  return true;
>>> +}
>> Isn't this really checking for equivalence? "do correspond" seems
>> awkward here.
> The function turns the names equivalent on first invocation for a given name
> and later checks that this tentative equivalence holds.
>
> Not sure what is best name for it (originaly it was verify that did not sound
> right to me either)
>>> +
>>> +/* Verification function for edges E1 and E2.  */
>>> +
>>> +bool
>>> +func_checker::compare_edge (edge e1, edge e2)
>>> +{
>>> +  if (e1->flags != e2->flags)
>>> +    return false;
>> Presumably there's no flags we can safely ignore.  So absolute
>> equality seems reasonable here.
> Yep
>>> +/* Compare two types if are same aliases in case of strict aliasing
>>> +   is enabled.  */
>>> +bool
>>> +sem_item::compare_for_aliasing (tree t1, tree t2)
>>> +{
>>> +  if (flag_strict_aliasing)
>>> +    {
>>> +      alias_set_type s1 = get_deref_alias_set (TREE_TYPE (t1));
>>> +      alias_set_type s2 = get_deref_alias_set (TREE_TYPE (t2));
>>> +
>>> +      return s1 == s2;
>>> +    }
>>> +
>>> +  return true;
>>> +}
>> Is returning TRUE really the conservatively correct thing to do in
>> the absence of aliasing information?  Isn't that case really "I
>> don't know" in which case the proper return value is FALSE?
> I think with -fno-strict-aliasing the set should be 0 (Richi?) and thus we can
> compare for equality.  We probably can be on agressive side and let 0 alias
> set prevail the non-0.  But that can be done incrementally.
>
> We also need to match type inheritance equality for polymorphic types. I will
> add function for that into ipa-devirt.

Hi,
    I would welcome help with type comparison function sensitive to type inheritance.

>
>>> +/* References independent hash function.  */
>>> +
>>> +hashval_t
>>> +sem_function::get_hash (void)
>>> +{
>>> +  if(!hash)
>>> +    {
>>> +      hash = 177454; /* Random number for function type.  */
>>> +
>>> +      hash = iterative_hash_object (arg_count, hash);
>>> +      hash = iterative_hash_object (bb_count, hash);
>>> +      hash = iterative_hash_object (edge_count, hash);
>>> +      hash = iterative_hash_object (cfg_checksum, hash);
>> Does CFG_CHECKSUM encompass the bb/edge counts?
> It is one used by profiling code to match profiles, so it should.
>>> +    SE_EXIT_FALSE();
>>> +
>>> +  if (!equals_wpa (item))
>>> +    return false;
>>> +
>>> +  /* Checking function arguments.  */
>>> +  tree decl1 = DECL_ATTRIBUTES (decl);
>>> +  tree decl2 = DECL_ATTRIBUTES (compared_func->decl);
>> So are there any attributes we can safely ignore?  Probably not.
>> However, we ought to handle the case where the attributes appear in
>> different orders.
> There are few, like we can ignore "weak" or "visibility" attribute because we do
> produce alias with proper visibility anyway.  My plan is to start removing those
> attributes from declarations once they are turned into suitable representation
> in symbol table (or for attributes like const/noreturn/pure where we have explicit
> decl flags).  This will make our life bit easier later, too.
>
> We probably then can whitelist some attributes, but I would deal with this later.
>>> +/* Returns cgraph_node.  */
>>> +
>>> +struct cgraph_node *
>>> +sem_function::get_node (void)
>>> +{
>>> +  return cgraph (node);
>>> +}
>>> +
>>> +/* Initialize semantic item by info reachable during LTO WPA phase.  */
>>> +
>>> +void
>>> +sem_function::init_wpa (void)
>>> +{
>>> +  parse_tree_args ();
>>> +}
>> inline? Worth or not worth the headache?
> We ought to autoinline simple wrappers even at -Os (for size)
> (I am not agains explicit inline keywords here tough)
>>
>>> +
>>> +bool
>>> +sem_function::compare_bb (sem_bb_t *bb1, sem_bb_t *bb2, tree func1, tree func2)
>> So this routine walks down the gimple statements and compares them
>> for equality.  Would it make sense to have the equality testing in
>> gimple?  That way if someone adds a new gimple code the places they
>> need to check/update are at least somewhat more localized?
> There are few places that does equality testing (tailmerge) AFAIK.  They are all somewhat
> different - I think we can export this equality machinery with reosnable API and try to turn
> those to use it, but it may be good incremental project IMO.
I definitely agree with aforementioned approach. The pass has few places where we can approve it to catch more-complex semantically equivalent functions and variables. These corner cases can improve the pass, but I would expect just small gain.

Majority of observations was added to this new version of the pass. I moved GIMPLE related comparison machinery to a separate file (ipa-icf-gimple.c). I hope it is acceptable for better pass understanding. Further enhancement would require introduction of a new API and as Honza said that could be good incremental project.

Thank you,
Martin

gcc/ChangeLog

2014-06-13  Martin Liska  <mliska@suse.cz>
         Jan Hubicka  <hubicka@ucw.cz>

     * Makefile.in: New pass object file added.
     * common.opt: New -fipa-icf flag introduced.
     * doc/invoke.texi: Documentation enhanced for the pass.
     * lto-section-in.c: New LTO section for a summary created by IPA-ICF.
     * lto-streamer.h: New section name introduced.
     * opts.c: Optimization is added to -O2.
     * passes.def: New pass added.
     * timevar.def: New time var for IPA-ICF.
     * tree-pass.h: Pass construction function.
     * ipa-icf.h: New pass header file added.
     * ipa-icf.c: New pass source file added.
     * ipa-icf-gimple.c: Likewise.

>>
>>> +
>>> +      for (i = 0; i < size1; ++i)
>>> +	{
>>> +	  t1 = gimple_phi_arg (phi1, i)->def;
>>> +	  t2 = gimple_phi_arg (phi2, i)->def;
>>> +
>>> +	  if (!compare_operand (t1, t2, func1, func2))
>>> +	    SE_EXIT_FALSE ();
>>> +
>>> +	  e1 = gimple_phi_arg_edge (phi1, i);
>>> +	  e2 = gimple_phi_arg_edge (phi2, i);
>>> +
>>> +	  if (!checker.compare_edge (e1, e2))
>>> +	    SE_EXIT_FALSE ();
>>> +	}
>> I don't think we guarantee any particular order on the PHI args.
>> ISTM you'd want to sort them or something so as not to reject a
>> possible duplicate simply because of ordering issues.
>>
>> Related, I'm not sure bb indexes are even guaranteed to have any
>> stable ordering.  So ISTM you'd want to do something like a DFS walk
>> to set a index for each block, then sort the PHI arguments based on
>> DFS index to get a stable, consistent check here.
> Yep, there are no resonable orders on it.  If function starts same in source code they ought
> to end up same here.  Plan was to first match for exact equality and then play with
> smarter tricks here.
>> I'm starting to gloss over things....  It feels like we've got too
>> much stuff in this one file.  Breaking things out would help (like
>> for example the hashing/equality bits).  I'd like to see things
>> broken out a bit and reposted for further reviewing.
> Yep, the pass has grown up to be rather long. The gimple equality testing is the
> main body of work, so perhaps doing this in separate file is good idea.
>
> Honza
>> Jeff

-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-IPA-ICF-pass.patch
Type: text/x-patch
Size: 114253 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20140630/35fa6b13/attachment.bin>